CPU 스케줄링은 왜 필요한가

5편에서 다중 프로그래밍과 시분할 시스템을 배우며 “메모리에 여러 프로세스를 동시에 올려놓고 CPU를 번갈아 준다”고 했다. 그런데 CPU는 한 순간에 하나의 프로세스만 실행할 수 있다. 준비 큐(ready queue)에 프로세스가 5개 있다면, 이 중 어떤 프로세스에게 먼저, 얼마 동안 CPU를 줄 것인가를 결정하는 규칙이 필요하다. 이 결정을 내리는 운영체제의 구성 요소를 CPU 스케줄러(scheduler)라 하고, 그 규칙을 CPU 스케줄링 알고리즘이라 한다.

쉽게 말하면: CPU 스케줄링은 손님이 여러 명 대기 중인 창구에서 “다음 손님을 어떤 순서로, 얼마나 오래 응대할지” 정하는 규칙이다.

6편에서 배운 프로세스 상태도를 다시 떠올려 보자. 프로세스는 준비(ready) 상태의 큐에서 기다리다가, 스케줄러가 선택하면 실행(running) 상태로 넘어간다. 이 “선택하는 행위”를 디스패치(dispatch)라 하고, 이를 담당하는 운영체제 모듈을 디스패처(dispatcher)라 한다. 스케줄러가 “누구를 다음에 실행할지 결정”하는 정책 담당자라면, 디스패처는 그 결정에 따라 “실제로 CPU를 넘기는 작업(문맥 교환, 사용자 모드 전환, 프로그램 재개)“을 수행하는 실행 담당자다.

디스패처가 하나의 프로세스에서 다른 프로세스로 CPU 제어권을 넘기는 데 걸리는 시간을 디스패치 지연(dispatch latency)이라 한다. 이 지연 시간 자체도 순수한 오버헤드이므로, 스케줄링 정책을 설계할 때는 “얼마나 자주 스케줄링 결정을 내리는가”도 함께 고려해야 한다. 너무 자주 바꾸면 디스패치 지연이 누적되어 손해다.

스케줄링 평가 기준 (성능 지표)

어떤 스케줄링 알고리즘이 “좋다”는 것을 판단하려면 기준이 있어야 한다. 독학사 시험에서는 이 다섯 가지 지표의 정의와, “값이 클수록 좋은지 작을수록 좋은지”를 정확히 구분하는 문제가 자주 나온다.

이 다섯 지표 중 다음 편의 계산 문제에서 실제로 손으로 구하게 될 것은 반환 시간과 대기 시간이다. 정의를 수식으로 정리하면 다음과 같다.

• 완료 시각: 프로세스가 CPU에서 마지막 실행을 끝내고 종료된 시각
• 도착 시각: 프로세스가 준비 큐에 처음 들어온 시각

• 실행 시간(burst time, CPU 버스트 시간): 그 프로세스가 CPU를 실제로 사용해야 하는 총 시간
• 즉 대기 시간은 “전체 걸린 시간에서 실제로 일한 시간을 뺀 나머지”, 곧 순수하게 기다리기만 한 시간이다

자주 틀리는 점: 대기 시간을 “준비 큐에 처음 들어가서부터 처음 실행되기까지의 시간”으로만 생각하기 쉽다. 그러나 라운드 로빈처럼 한 프로세스가 여러 번 끊겼다가 재개되는 스케줄링에서는, 중간에 실행이 끊기고 다시 준비 큐로 돌아가 기다린 시간까지 전부 합산해야 정확한 대기 시간이 된다. 그래서 실무적으로는 위 공식(반환 시간 − 실행 시간)으로 한 번에 구하는 것이 실수를 줄이는 방법이다.

이 지표들 사이에는 트레이드오프(trade-off, 상충 관계)가 있다. 예를 들어 CPU 이용률과 처리량을 극대화하는 정책은 짧은 작업을 이것저것 자주 스케줄링해야 할 수 있는데, 이는 개별 프로세스의 응답 시간을 들쭉날쭉하게 만들 수 있다. “모든 지표를 동시에 최고로 만드는 완벽한 알고리즘은 없다”는 것이 8편에서 여러 알고리즘을 비교하는 이유다.

선점형 스케줄링과 비선점형 스케줄링

CPU 스케줄링 결정은 다음 네 가지 상황에서 일어날 수 있다.

1. 프로세스가 실행 상태에서 대기 상태로 바뀔 때(예: 입출력 요청)
2. 프로세스가 실행 상태에서 종료될 때
3. 프로세스가 실행 상태에서 준비 상태로 바뀔 때(예: 인터럽트 발생)
4. 프로세스가 대기 상태에서 준비 상태로 바뀔 때(예: 입출력 완료)

이 중 1번과 2번만 허용하는 스케줄링을 비선점형(non-preemptive), 3번과 4번까지 허용하는 스케줄링을 선점형(preemptive)이라 한다.

비선점형 스케줄링 (non-preemptive scheduling)

한 프로세스가 CPU를 잡으면, 그 프로세스가 스스로 CPU를 반납(종료 또는 입출력 요청)할 때까지 다른 프로세스가 끼어들 수 없다. 6편의 상태 전이도에서 “실행 → 준비”로 가는 화살표(선점)가 아예 일어나지 않는 방식이다.

• 장점: 문맥 교환이 자주 일어나지 않아 오버헤드가 적다. 구현이 단순하다.
• 단점: 실행 시간이 긴 프로세스 하나가 CPU를 오래 붙잡으면, 뒤에 대기하는 짧은 프로세스들이 한없이 기다려야 한다.

선점형 스케줄링 (preemptive scheduling)

더 우선순위가 높은 프로세스가 나타나거나 시간 할당량이 끝나면, 실행 중이던 프로세스라도 강제로 CPU를 빼앗아 다른 프로세스에게 줄 수 있다. 현대의 시분할 시스템은 거의 대부분 선점형이다.

• 장점: 응답 시간을 짧게 유지할 수 있어 대화형(interactive) 시스템에 적합하다. 중요한 작업을 빠르게 처리할 수 있다.
• 단점: 문맥 교환이 자주 일어나 오버헤드가 커진다. 여러 프로세스가 동시에 공유 자원에 접근하다 중간에 끊기면 데이터 일관성 문제(경쟁 조건, race condition)가 발생할 수 있다 — 이 문제는 9~10편의 동기화 주제로 이어진다.

비유: 비선점형은 한 사람이 발표를 끝까지 마치고 나서야 다음 사람이 발표를 시작할 수 있는 세미나이고, 선점형은 사회자가 “시간 다 됐습니다, 다음 분!”이라고 중간에 끊고 순서를 넘기는 세미나다.

스케줄링 큐와 다단계 관점

준비 큐(ready queue)는 CPU를 기다리는 프로세스들의 대기 줄이다. 입출력을 기다리는 프로세스들은 각 장치별 대기 큐(device queue, 또는 waiting queue)에 따로 들어간다. 프로세스는 일생 동안 준비 큐와 여러 대기 큐 사이를 오간다.

이 그림은 6편의 상태 전이도를 큐 중심으로 다시 그린 것이다. 스케줄러는 이 그림에서 “준비 큐 → CPU” 화살표가 일어날 때마다 누구를 보낼지 결정하는 주체다. 이 결정 방식이 무엇이냐에 따라 다음 편에서 배울 FCFS, SJF, SRTF, RR, 우선순위, HRRN 같은 이름이 붙는다.

스케줄러의 세 종류(장기·중기·단기)

시스템에 따라 스케줄링 결정을 내리는 계층이 여러 개로 나뉘기도 한다. 독학사 시험에서는 이름과 역할을 정의 수준으로 구분할 수 있으면 충분하다.

• 장기 스케줄러(long-term scheduler, job scheduler): 디스크에 대기 중인 작업 중 어떤 것을 메모리에 적재해 준비 큐에 넣을지 결정한다. 메모리에 올라가는 프로세스 수(다중 프로그래밍 정도)를 조절한다. 상대적으로 드물게 호출된다.
• 단기 스케줄러(short-term scheduler, CPU scheduler): 준비 큐의 프로세스 중 누구에게 다음 CPU를 줄지 결정한다. 매우 자주(밀리초 단위로) 호출되므로 속도가 빨라야 한다. 8편에서 다루는 알고리즘들이 바로 이 단기 스케줄러의 정책이다.
• 중기 스케줄러(medium-term scheduler): 메모리가 부족해지면 일부 프로세스를 통째로 디스크로 내보냈다가(스와핑, swapping) 나중에 다시 불러들이는 결정을 담당한다. 다중 프로그래밍 정도를 완화해 시스템 부하를 조절한다.

핵심 정리

• CPU 스케줄러는 준비 큐에서 다음에 실행할 프로세스를 결정하고, 디스패처는 그 결정을 실제 문맥 교환으로 수행하며 이때 걸리는 시간이 디스패치 지연이다.
• 평가 지표는 CPU 이용률·처리량(높을수록 좋음), 반환 시간·대기 시간·응답 시간(낮을수록 좋음)이며, 반환 시간 = 완료 시각 − 도착 시각, 대기 시간 = 반환 시간 − 실행 시간이다.
• 비선점형은 프로세스가 스스로 CPU를 반납할 때까지 기다리고, 선점형은 시간 할당량 만료나 우선순위 역전 시 강제로 CPU를 빼앗을 수 있다.
• 모든 지표를 동시에 최적화하는 알고리즘은 없으며, 이 상충 관계가 다음 편에서 여러 알고리즘을 비교하는 이유다.
• 장기·중기·단기 스케줄러는 각각 다중 프로그래밍 정도 조절, 스와핑, CPU 배정이라는 서로 다른 층위의 결정을 담당한다.

마무리 복습

참고 자료

• KOCW 운영체제 강의자료 - 스케줄링/동기화/가상메모리 
• 길벗 운영체제 도서 정보 
• 국가평생교육진흥원 과목별 평가영역