프로세스 스케줄링: 단계와 알고리즘

스케줄링

스케줄링은 여러 프로세스가 번갈아 사용하는 자원을 어떤 시점에 어떤 프로세스에 할당할지 결정하는 일이며, 그 방법에 따라 시스템 성능이 달라진다. 목적은 다음과 같다.

• 자원 할당의 공정성 보장
• 단위 시간당 처리량 최대화 (CPU 활용 최대화)
• 예측 가능성 보장
• 오버헤드 최소화 (문맥 교환 비용 최소화)

스케줄링 수행 단계

장기 스케줄러 (작업 선택)

• 디스크에서 어떤 프로그램을 가져와 커널에 등록할지, 즉 어떤 프로세스를 준비 큐에 넣을지 결정한다. 작업 스케줄러, 승인 스케줄러라고도 한다.
• 메모리에 동시에 올라가 있는 프로세스의 수, 곧 다중 프로그래밍의 정도(degree of multiprogramming)를 조절한다.
• 가끔 호출되므로 상대적으로 느린 속도가 허용된다.

중기 스케줄러 (사용 권한 부여)

• 너무 많은 프로세스에 메모리를 할당해 시스템 성능이 떨어질 때, 메모리에 적재된 프로세스의 수를 동적으로 조절한다.
• 장기와 단기 사이의 완충 역할을 하며, 스와핑 기능의 일부로 이해할 수 있다.
• 중기 스케줄러가 등장하면서 프로세스 상태에 중지(Suspended) 상태가 추가되었다. 중지 상태의 프로세스는 메모리를 통째로 빼앗기고 디스크로 스왑 아웃된다. (프로세스의 상태 변화 참고)

단기 스케줄러 (프로세서 할당, 디스패칭)

• 메모리 안의 준비 상태 프로세스 중 다음에 실행할 프로세스를 선택해 CPU를 할당한다. CPU 스케줄러라고도 하며, 일반적으로 스케줄러라고 하면 단기 스케줄러를 뜻한다.
• 시분할 시스템에서는 타이머 인터럽트가 발생하면 호출된다.
• 밀리초 이하의 시간 단위로 매우 빈번하게 호출되므로 수행 속도가 빨라야 한다.

현대 OS의 스케줄러

현대의 운영체제는 일반적으로 장기 스케줄러를 두지 않는다. 과거에는 적은 메모리를 많은 프로세스에 나눠 주면 프로세스당 메모리가 너무 적어져 장기 스케줄러가 이를 조절했지만, 지금은 프로세스가 시작되면 곧바로 메모리를 할당해 준비 큐에 넣는다.

선점과 비선점

선점 스케줄링

다른 프로세스가 사용 중인 프로세서를 빼앗을 수 있는 스케줄링이다.

• 프로세스 하나가 프로세서를 장시간 독점하는 것을 막는다.
• 우선순위가 높은 프로세스를 긴급하게 처리할 수 있다.
• 대화식 시분할 시스템이나 실시간 시스템에서 빠른 응답 시간을 유지하려면 필수다.
• 오버헤드가 커질 수 있다.

비선점 스케줄링

다른 프로세스가 사용 중인 프로세서를 빼앗을 수 없다.

• 모든 프로세스가 공정하게 관리된다.
• 응답 시간을 예측하기 쉽다.

알고리즘 평가 기준

• 프로세서 사용률
• 처리율
• 반환시간
• 대기시간
• 반응시간

스케줄링 알고리즘

알고리즘	선점 여부	핵심
FCFS	비선점	먼저 온 순서대로
SJF	비선점	실행 시간이 짧은 순서대로
SRT	선점	남은 실행 시간이 짧은 순서대로
우선순위	비선점 또는 선점	우선순위가 높은 순서대로
Round Robin	선점	정해진 시간만큼 돌아가며
HRN	비선점	응답률이 높은 순서대로
MLQ / MFQ	선점	우선순위별로 준비 큐를 여러 개 운영

선입선처리 (FCFS, First Come First Served)

먼저 들어온 프로세스를 먼저 처리하는 비선점 방식으로, 스케줄링 알고리즘 중 가장 단순하다.

• 장점: 단순하고, 모든 프로세스가 언젠가는 처리된다.
• 단점: 긴 작업이 앞에 있으면 짧은 작업도 오래 기다려야 한다. 일괄 처리 시스템에서는 효율적이지만 빠른 응답이 필요한 대화식 시스템에는 적합하지 않다.

최소 작업 우선 (SJF, Shortest Job First)

실행 시간이 가장 짧은 프로세스를 먼저 처리하는 비선점 방식이다.

• 장점: 평균 대기시간이 가장 짧다.
• 단점: 실행 시간이 긴 작업은 기아 상태에 빠질 수 있고, 실행 시간을 미리 정확히 알기 어렵다.

SRT (Shortest Remaining Time)

SJF에 선점을 적용한 알고리즘이다. 남은 실행 시간이 더 짧은 프로세스가 들어오면 실행 중인 프로세스에서 CPU를 빼앗는다.

우선순위 스케줄링

우선순위가 높은 순으로 처리하고, 우선순위가 같으면 선입선처리로 처리한다.

• 문제점: 우선순위가 낮은 프로세스가 무한정 연기되는 기아가 발생할 수 있다.
• 해결: 오래 대기한 프로세스의 우선순위를 점진적으로 높이는 에이징을 적용한다.

라운드 로빈 (Round-Robin)

시분할 시스템을 위해 설계된 선점형 알고리즘이다. 준비 큐를 순환 큐로 만들어, 스케줄러가 큐를 돌면서 프로세스마다 정해진 규정 시간량(time slice)만큼 프로세서를 제공한다. 모든 프로세스에 같은 시간을 주므로 공정하다.

Time Slice 크기의 Trade-off

• 보통 10ms~100ms 정도를 할당한다.
• 너무 작으면 Context Switching이 빈번해져 성능이 나빠진다. 규정 시간량은 문맥 교환에 드는 시간보다 충분히 커야 한다.
• 너무 크면 FCFS와 똑같이 동작한다.

HRN (Highest Response-ratio Next)

SJF의 약점인 긴 작업과 짧은 작업 사이의 지나친 불평등을 보완한 비선점 우선순위 스케줄링이다. 우선순위를 (대기시간 + 서비스시간) / 서비스시간으로 계산하므로, 오래 기다린 프로세스일수록 우선순위가 높아진다.

우선순위를 계속 계산해야 하므로 오버헤드가 높을 수 있다.

다단계 큐 (MLQ, Multi Level Queue)

우선순위별로 준비 큐를 여러 개 두는 선점형 알고리즘이다.

• Level 2 큐의 작업을 수행하다가 Level 1 큐에 작업이 들어오면 Level 1부터 처리한다.
• Level 1 큐의 작업을 모두 끝내야 Level 2 큐의 작업을 수행할 수 있다.
• 큐마다 스케줄링 알고리즘을 따로 둘 수 있다. (예: RR)
• 한번 큐에 들어간 작업은 다른 큐로 이동할 수 없어, 우선순위가 낮은 큐의 작업이 기아 상태에 빠질 수 있다.

다단계 피드백 큐 (MFQ, Multi Level Feedback Queue)

MLQ와 달리 작업이 큐 사이를 이동할 수 있다.

• 상위 큐에서 하위 큐로 갈수록 할당 시간(time quantum)이 길어진다.
• MLQ에서 우선순위가 낮은 큐의 작업이 기아 상태에 빠질 수 있다는 문제를 해결한다.
• 내 생각: 에이징 기법을 활용하면 Level 2 큐에서 오래 기다린 작업을 Level 1 큐로 옮길 수 있을 것 같다.

상시로 돌아가야 하는 프로세스가 있다면 어떤 알고리즘이 좋을까? MFQ가 적합하다고 생각한다. 작업을 공평하게 처리하면서 기아 상태가 발생하지 않는 알고리즘이기 때문이다.

스레드 단위의 스케줄링은 Thread Scheduling에서 이어서 다룬다.

참고

• 운영체제: 그림으로 배우는 구조와 원리 (한빛아카데미)