CPU 스케줄링 (CPU Scheduling)

CPU 스케줄링(CPU Scheduling)은 운영체제가 준비 상태에 있는 여러 프로세스 가운데 다음에 CPU를 사용할 프로세스를 고르는 작업이다. CPU는 한 번에 하나의 명령 흐름만 실행할 수 있으므로, 스케줄링 정책이 시스템의 처리량과 응답성을 사실상 결정한다. 어떤 기준으로 프로세스를 고르고 언제 CPU를 빼앗는지에 따라 다양한 알고리즘이 존재한다.

왜 CPU 스케줄링이 필요한가

프로그램의 실행은 CPU 연산 구간(CPU burst)과 입출력 대기 구간(I/O burst)이 번갈아 나타나는 형태를 띤다. 어떤 프로세스가 디스크 읽기를 기다리는 동안 CPU를 놀리는 것은 낭비이므로, 운영체제는 그 시간에 다른 프로세스에 CPU를 배정해 전체 활용률을 높인다. 이것이 다중 프로그래밍(multiprogramming)의 핵심이고, CPU 스케줄러는 이를 실현하는 장치다.

스케줄링 결정이 일어나는 시점은 크게 네 가지다. 실행 중인 프로세스가 입출력을 요청해 대기 상태로 바뀔 때, 프로세스가 종료될 때, 인터럽트로 인해 실행 중인 프로세스가 준비 상태로 밀려날 때, 그리고 대기하던 프로세스가 준비 상태로 돌아올 때다. 앞의 두 경우에만 스케줄링하면 비선점(non-preemptive) 방식이고, 네 경우 모두에서 CPU를 회수할 수 있으면 선점(preemptive) 방식이다.

CPU 스케줄러와 함께 언급되는 것이 디스패처(dispatcher)다. 스케줄러가 다음 프로세스를 고르면, 디스패처는 문맥 교환(context switching)과 사용자 모드 전환, 해당 지점으로의 점프를 수행해 실제로 CPU를 넘긴다. 이때 걸리는 시간을 디스패치 지연(dispatch latency)이라고 하며, 스케줄링이 잦을수록 이 오버헤드가 누적되므로 정책 설계에서 무시할 수 없다.

스케줄링 성능을 재는 기준

알고리즘을 비교할 때는 여러 지표를 함께 본다. CPU 이용률(utilization)은 CPU가 놀지 않고 일한 비율이고, 처리량(throughput)은 단위 시간당 완료한 프로세스 수다. 총처리 시간(turnaround time)은 프로세스 제출부터 완료까지 걸린 시간, 대기 시간(waiting time)은 준비 큐에서 기다린 시간의 합, 응답 시간(response time)은 요청 후 첫 반응까지의 시간이다. 일괄 처리 시스템은 처리량을, 대화형 시스템은 응답 시간을 우선하는 식으로 목표가 달라진다.

대표 알고리즘 비교

알고리즘	선점 여부	선택 기준	특징과 한계
선입선출(FCFS)	비선점	도착 순서	구현이 단순하지만 긴 작업 뒤에 짧은 작업이 몰려 기다리는 호위 효과(convoy effect)가 생긴다
최단 작업 우선(SJF)	비선점	다음 CPU burst가 가장 짧은 것	평균 대기 시간이 이론상 최소지만 burst 길이를 미리 알 수 없어 예측에 의존한다
최소 잔여 시간 우선(SRTF)	선점	남은 실행 시간이 가장 짧은 것	SJF의 선점형이며 긴 작업이 계속 밀리는 기아(starvation)가 발생할 수 있다
우선순위(Priority)	둘 다 가능	우선순위 값	낮은 우선순위의 기아를 막기 위해 대기 시간에 따라 우선순위를 올리는 에이징(aging)을 쓴다
라운드 로빈(RR)	선점	도착 순서에 시간 할당량 적용	타임 퀀텀(time quantum)마다 교대해 응답성이 좋으나 퀀텀이 너무 짧으면 문맥 교환 비용이 커진다
다단계 피드백 큐(MLFQ)	선점	큐 수준과 이력	CPU를 오래 쓰면 낮은 큐로 내려보내 대화형 작업을 우대하며 실제 운영체제 정책의 기반이 된다

시간:  0    4    8    12   16   18   20
실행:  P1 | P2 | P3 | P1 | P3 | P1
설명:  P1은 4만큼 쓰고 큐 뒤로, P2는 4에 끝남,
      P3은 4 사용 후 잔여 2, P1 잔여 6 중 4 사용,
      P3 잔여 2 완료, 마지막으로 P1 잔여 2 완료