CPU 스케줄링

서론

 스케줄러(Scheduler)는 언제, 어떤 프로세스를 선택해서 CPU에서 실행시킬지 결정하는 모듈이다. 멀티프로그래밍의 목적은 CPU 효율을 극대화하는 것이므로 적절한 스케줄링이 필수적이다. 기본적으로 프로세스는 CPU만 사용하는 단계(CPU burst)와 I/O 작업만 하는 단계(I/O burst)의 반복으로 구성된 사이클 형태로 수행된다. 이러한 여러 작업이 혼재되어 있기 때문에 CPU 스케줄링이 필요하다. CPU Scheduler는 메모리에서 Ready 상태의 프로세스 중 어떤 프로세스를 CPU에 할당할지 선택한다. CPU 스케줄링으로 인해 프로세스의 상태는 다음과 같이 변경될 수 있다:

1. Running → Waiting(Blocked): I/O 요청이나 자식 프로세스의 종료를 기다리는 경우
2. Running → Ready: 인터럽트가 발생한 경우
3. Waiting → Ready: I/O 작업이 끝난 경우
4. Terminate: 프로세스가 종료되는 경우

여기서 1)과 4)는 Non-preemptive (비선점) 방식이고, 그 외의 모든 과정은 preemptive(선점) 방식이다. Preemptive 방식은 운영체제가 강제로 프로세스의 사용권을 통제하는 방식이고, Non-preemptive 방식은 프로세스가 스스로 다음 프로세스에게 자리를 넘겨주는 방식이다. Preemptive 스케줄링은 여러 프로세스가 데이터를 공유하는 경우, 경쟁 상태(Race condition)를 초래할 수 있다. 만약 한 프로세스가 데이터를 수정하는 동안 다른 프로세스의 수행을 위해 중단된다면, 다른 프로세스는 일관성이 없는 상태의 데이터를 읽게 될 수 있다. Dispatcher는 CPU의 제어권을 스케줄러에 의해 선택된 프로세스에게 넘겨주는 모듈이다. Context switching이나 커널 모드에서 유저 모드로의 전환 작업 등을 수행하며, 한 프로세스를 멈추고 다른 프로세스를 실행하는 데 걸리는 시간을 Dispatch latency라고 한다.

CPU 스케줄링의 종류

FCFS (First-Come, First-Served)

 FCFS는 가장 단순한 CPU 스케줄링 알고리즘으로, 프로세스가 도착한 순서대로 CPU를 할당하는 방식이다. 프로세스가 큐에 도착하면, 그 순서대로 처리된다. 이는 이해하기 쉽고 구현이 간단하지만, 프로세스의 도착 순서에 따라 비효율적일 수 있다.

 FCFS의 주요 특징은 비선점형 방식으로 동작한다는 점이다. 이는 한 프로세스가 CPU를 점유하면, 해당 프로세스가 완료될 때까지 다른 프로세스는 CPU를 사용할 수 없음을 의미한다. 이로 인해 긴 프로세스가 먼저 도착하면 이후의 짧은 프로세스들이 오랜 시간 대기하게 되는 "Convoy Effect"가 발생할 수 있다. 또한, 프로세스의 대기 시간이 도착 순서에 크게 좌우되므로, 평균 대기 시간이 비효율적으로 길어질 수 있다.

SJF (Shortest Job First)

 SJF는 각 프로세스의 예상 실행 시간을 기준으로, 가장 짧은 실행 시간을 가진 프로세스에 CPU를 먼저 할당하는 방식이다. 이는 평균 대기 시간을 최소화하는 데 효과적이다.

 SJF는 선점형과 비선점형 두 가지 방식으로 구현될 수 있다. 비선점형 SJF는 현재 실행 중인 프로세스가 종료될 때까지 기다리지만, 선점형 SJF (또는 SRTF, Shortest Remaining Time First)는 더 짧은 작업이 도착하면 현재 실행 중인 프로세스를 중단하고 새로운 프로세스를 실행한다. 이는 평균 대기 시간을 줄이지만, 실행 시간을 정확하게 예측해야 하는 어려움이 있다. 또한, 짧은 프로세스가 계속해서 도착하면 긴 프로세스는 계속 대기하게 되는 "Starvation" 문제가 발생할 수 있다.

Priority Scheduling

 Priority Scheduling은 각 프로세스에 우선순위를 부여하고, 높은 우선순위를 가진 프로세스에 CPU를 먼저 할당하는 방식이다. 이는 중요한 작업을 먼저 처리할 수 있게 한다.

 이 알고리즘은 선점형과 비선점형으로 나뉜다. 선점형 방식에서는 높은 우선순위를 가진 프로세스가 도착하면 현재 실행 중인 프로세스를 중단하고 CPU를 할당하며, 비선점형 방식에서는 현재 프로세스가 완료될 때까지 기다린다. 우선순위는 프로세스의 중요도, 필요 자원, 사용자 요구 등에 따라 결정된다. 그러나 우선순위가 낮은 프로세스는 무기한 대기할 수 있는 "Starvation" 문제가 있으며, 이를 해결하기 위해 우선순위를 동적으로 조정하는 "Aging" 기법이 사용될 수 있다.

Round Robin (RR)

 Round Robin은 프로세스들에게 공평하게 CPU 시간을 할당하는 방식으로, 각 프로세스는 동일한 시간 간격 (Time Quantum) 동안 CPU를 사용한다. 이는 시간 공유 시스템에서 주로 사용된다.

 Round Robin의 주요 특징은 선점형 방식으로, 각 프로세스는 정해진 시간 동안만 CPU를 사용하고, 시간이 초과되면 다음 프로세스에게 CPU를 넘긴다. 이는 모든 프로세스가 공평하게 CPU를 사용할 수 있게 하며, 긴 프로세스가 시스템을 독점하는 것을 방지한다. 그러나 Time Quantum의 크기가 성능에 큰 영향을 미치는데, 너무 짧으면 문맥 전환 오버헤드가 증가하고, 너무 길면 반응 시간이 증가할 수 있다.

Multilevel Queue Scheduling

 Multilevel Queue Scheduling은 프로세스를 여러 개의 큐로 나누고, 각 큐에 다른 스케줄링 알고리즘을 적용하는 방식이다. 큐는 일반적으로 프로세스의 특성에 따라 분류된다.

 이 알고리즘은 시스템의 요구에 맞게 유연하게 설계할 수 있다. 예를 들어, 상위 큐는 짧은 반응 시간이 필요한 대화형 작업을 처리하고, 하위 큐는 긴 배치 작업을 처리할 수 있다. 각 큐는 독립적으로 관리되며, 큐 간의 프로세스 이동은 제한적이거나 허용되지 않는다. 이는 다양한 프로세스 요구를 효과적으로 처리할 수 있지만, 큐 간의 적절한 우선순위와 스케줄링 알고리즘을 설정하는 것이 중요하다.

Multilevel Feedback Queue Scheduling

 Multilevel Feedback Queue Scheduling은 Multilevel Queue Scheduling의 변형으로, 프로세스가 실행되면서 다른 큐로 이동할 수 있는 방식이다. 이는 프로세스의 동작에 따라 동적으로 우선순위를 조정할 수 있다.

 이 알고리즘의 주요 특징은 유연성과 공정성이다. 프로세스는 초기에는 높은 우선순위 큐에 배치되지만, 할당된 시간을 초과하면 낮은 우선순위 큐로 이동한다. 이는 CPU 시간을 공평하게 분배하고, 모든 프로세스가 적절한 시간을 사용할 수 있도록 한다. 또한, 장기적으로 CPU를 많이 사용하는 프로세스는 낮은 우선순위 큐로 이동하므로, 시스템 자원의 효율성을 높일 수 있다.

결론

CPU 스케줄링은 운영 체제의 성능과 효율성을 결정짓는 중요한 요소이다. 각 스케줄링 알고리즘은 고유한 장단점을 가지며, 특정 상황과 요구에 따라 적절한 알고리즘을 선택하는 것이 중요하다. 프로세스의 특성과 시스템 요구를 고려하여 최적의 스케줄링 방식을 선택함으로써 시스템 성능을 극대화하고, 공정한 자원 분배를 실현할 수 있다.

참고자료

 

• Wikipedia. (n.d.). Scheduling (computing). Retrieved from Wikipedia
• Wikipedia. (n.d.). Round-robin scheduling. Retrieved from Wikipedia
• Wikipedia. (n.d.). Multilevel feedback queue. Retrieved from Wikipedia
• Wikipedia. (n.d.). Shortest remaining time. Retrieved from Wikipedia
• Wikipedia. (n.d.). Rate-monotonic scheduling. Retrieved from Wikipedia
• "CPU Scheduling Algorithms: A Survey," ProQuest. Retrieved from ProQuest
• "An Optimum Multilevel CPU Scheduling Algorithm," IEEE Xplore. Retrieved from IEEE Xplore