이번 포스팅은 CPU 스케줄링에 대해 알아보겠습니다.
프로세스의 실행은 보통 CPU burst(계산을 수행하는 구간)와 I/O burst(I/O 요청 후 완료를 기다리는 구간)가 번갈아 나타납니다. 계산을 수행하는 동안에는 CPU를 점유하지만, 파일을 읽거나 쓰는 단계에서는 I/O가 끝날 때까지 대기 상태로 전환되어 CPU를 사용하지 않습니다.
이런 실행 패턴에 따라 프로세스의 특성도 나뉩니다.
CPU 사용 비중이 큰 프로세스는 CPU-bound process, I/O 요청이 잦아 대기 시간이 상대적으로 큰 프로세스는 I/O-bound process라고 합니다.
CPU 스케줄링이 필요한 이유는 여러 프로세스가 동시에 존재하는 환경에서 CPU를 공정하면서도 효율적으로 배분해야 하기 때문입니다. 특히 I/O-bound 프로세스는 CPU를 오래 점유하기보다는 짧게 실행한 뒤 다시 I/O를 요청하거나 이벤트를 처리하는 패턴을 반복하는 경우가 많습니다. 사용자 입력 처리, 네트워크 요청 처리, UI 갱신 같은 대화형(interactive) 작업이 대표적이며, 보통 ‘짧은 CPU burst → I/O burst’가 계속 반복됩니다. 이때 I/O가 끝나 준비 상태인 프로세스가 CPU를 늦게 받으면, 이벤트 처리가 밀려 입력 지연이나 화면 끊김이 발생합니다. 그래서 스케줄러는 우선순위나 선점(Preemptive) 같은 정책을 통해, 이런 작업들이 짧은 CPU 시간을 빠르게 확보하도록 설계됩니다.
결국 CPU 스케줄링은 두 가지 질문으로 정리할 수 있습니다.
- 다음 CPU를 누구에게 줄 것인가?
- 그 프로세스가 CPU를 얼마나 오래 쓰게 할 것인가?
이 의사결정은 운영체제의 스케줄러가 담당합니다. 스케줄러는 준비 큐에 있는 후보들 중에서 정책에 따라 다음 실행 대상을 고릅니다. 다만 선택 이후 실제로 CPU를 넘기고 실행 상태로 전환하는 단계가 필요한데, 이 역할을 하는 것이 디스패처(Dispatcher)입니다. 디스패처는 문맥 교환을 수행하고, 선택된 프로세스가 실제로 실행되도록 제어를 전달합니다.
그렇다면 스케줄러는 “누구에게, 얼마나”를 결정할 때 기준이 있어야 하는데, 이때 사용되는 대표적인 평가 기준을 Scheduling Criteria라고 합니다.
Scheduling Criteria
대표적인 평가 기준에는 5가지가 있습니다.
CPU Utilization: CPU가 쉬지 않고 계속 사용돼야 함Throughput: 단위 시간당 완료된 작업 수Turnaround Time: CPU burst에 들어와서 I/O하러 나갈때까지 걸린 전체 시간Waiting Time: CPU burst에 들어와서 기다린 전체 시간Response Time: CPU burst에 들어와서 최초로 CPU를 얻기까지 걸린 시간
시스템 측면에서 CPU Utilization과 Throughput이 높아야 좋고, 프로세스 측면에서 Turnaround Time, Waiting Time, Response Time이 적어야 좋습니다.
이를 기반으로 다양한 Scheduling Algorithm을 선택하여 스케줄링 하면 됩니다.
Scheduling Algorithm
스케줄링 알고리즘에는 대표적인 알고리즘 4가지가 있는데, 각 알고리즘을 간략하게 살펴 보겠습니다.
스케줄링 알고리즘을 좀 더 자세히 보고 싶으면 ⭐여기를 접속하여 학습하는 것을 추천 드립니다.
First-Come First-Service(FCFS)
FCFS는 준비 큐에 먼저 도착한 프로세스부터 CPU를 할당하는 비선점형 스케줄링입니다.
FCFS는 먼저 도착한 프로세스 부터 CPU를 할당하기 때문에, CPU brust가 작은 프로세스가 CPU brust가 큰 프로세스 작업이 끝날때까지 많이 기다려야하는 문제가 있습니다. → Convoy Effect
Shortest-Job-First(SJF)
SJF는 CPU brust가 가장 짧은 프로세스를 먼저 스케줄링합니다.
SJF는 선점형과 비선점형으로 나뉩니다. 선점형 SJF는 현재 수행중인 프로세스의 남은 CPU brust보다 더 짧은 CPU brust를 가진 프로세스가 있다면, 더 짧은 CPU brust를 가진 프로세스에게 CPU를 제공합니다.
SJF는 CPU brust가 가장 짧은 프로세스에게 먼저 CPU를 제공하기 때문에, 주어진 프로세스들에 대해 minimum average waiting time을 보장합니다. 하지만, SJF 알고리즘에는 Starvation(기아) 문제가 있습니다. CPU brust가 짧은 프로세스가 계속해서 들어온다면, CPU brust가 큰 프로세스는 계속 기다려야하는 문제가 있습니다.
Priority
우선순위 알고리즘은 말 그대로 우선순위가 높은 프로세스에 CPU를 제공하는 것입니다. 우선순위 알고리즘도 SJF 알고리즘처럼 Starvation 문제가 있는데, Aging기법을 활용하면 해결할 수 있습니다.
Round Robin(RR)
RR 알고리즘은 현재 제일 많이 사용되고 있는 스케줄링의 근간입니다. RR은 각 프로세스에 동일한 Time Quantum을 부여하여 CPU를 번갈아 제공하는 선점형 스케줄링입니다.
RR의 Quantum이 크면 FCFS 알고리즘과 성능이 비슷해지고, Quantum이 작으면 context switch 오버헤드가 커집니다. 일반적으로 SJF 알고리즘보다 turnaround time이 길지만, response time이 더 짧은 특징이 있습니다.
Multilevel Queue
지금까지는 하나의 Ready Queue를 기준으로 CPU 스케줄링을 설명했습니다.
하나의 Read Queue가 아닌 위 사진처럼 다양한 Queue를 기반으로 CPU 스케줄링을 할 수 있습니다.
위 사진처럼 다양한 큐에 알고리즘을 각각 설정할 수 있습니다. 이를 Multilevel Feedback Queue라고 합니다.
Conclusion
이번 포스팅에서는 CPU 스케줄링에 대해 알아 보았습니다. 또한, CPU 스케줄링의 대표적인 평가 기준과 알고리즘에 대해 알아봤습니다. 다음 포스팅에서는 프로세스 동기화(Process Synchronization)에 대해 알아보겠습니다.
References
[2] Operating System Concepts(Silberschatz, Galvin and Gagne)