CPU 스케줄링

CPU 스케줄링은 실행할 준비가 된 여러 프로세스(process) 가운데 누구에게 CPU를 먼저, 얼마 동안 줄지 정하는 일이다. 이 결정을 내리는 커널(kernel)의 부분을 스케줄러(scheduler)라고 한다. 같은 작업들이라도 순서만 바꾸면 작업들이 기다리는 평균 대기 시간(waiting time)이 몇 배씩 달라지고, 화면이 멈칫하느냐 부드럽게 반응하느냐도 갈린다. 알고리즘을 가르는 질문은 둘이다. 실행 중인 프로세스에게서 CPU를 도중에 빼앗을 수 있는가, 즉 선점(preemption)을 하는가, 그리고 다음 차례를 무엇으로 고르는가.

왜 스케줄링이 필요한가

프로세스는 CPU로 계산하는 구간과 디스크·네트워크 응답을 기다리는 구간을 번갈아 오간다. 앞의 구간을 CPU 버스트(CPU burst), 뒤의 구간을 입출력 버스트(I/O burst)라고 부른다. 입출력을 기다리는 동안 CPU를 쥐고 있으면 낭비이므로, 그 프로세스는 CPU를 내놓고 대기 상태(waiting state)로 간다. 입출력이 끝날 때까지는 CPU를 받을 수 없는 상태다. 스케줄러는 빈 CPU에 준비 큐(ready queue)에서 기다리던 다른 프로세스를 올린다. 한 프로세스가 기다리는 동안 다른 프로세스가 계산하게 해야 CPU가 놀지 않는다.

프로세스는 성격에 따라 둘로 나눠 볼 수 있다. CPU 버스트가 길고 입출력이 드문 CPU 중심(CPU-bound) 프로세스가 있고, 짧게 계산하고 금방 입출력을 기다리는 입출력 중심(I/O-bound) 프로세스가 있다. 동영상 인코딩은 앞쪽이고, 키 입력에 반응하는 편집기는 뒤쪽이다. 좋은 스케줄러는 입출력 중심 프로세스를 빨리 돌려 반응성을 지키면서도 CPU 중심 프로세스를 굶기지 않는다.

선점과 비선점

비선점(non-preemptive) 스케줄링에서는 CPU를 받은 프로세스가 끝나거나 입출력을 요청해 스스로 CPU를 내놓을 때까지 계속 실행한다. 구현이 단순하고 문맥 교환(context switch)이 적다. 문맥 교환 동안 CPU는 실제 작업 대신 상태를 저장하고 불러오는 데 시간을 쓰므로, 적을수록 그 낭비가 준다. 대신 긴 작업 하나가 CPU를 붙잡으면 뒤의 짧은 작업이 모두 기다린다.

선점 스케줄링에서는 커널이 실행 중인 프로세스에게서 CPU를 도중에 빼앗을 수 있다. 하드웨어 타이머가 일정 간격으로 타이머 인터럽트(interrupt)를 걸면 커널이 제어권을 되찾고, 계속 실행시킬지 다른 프로세스로 바꿀지 판단한다. 리눅스·윈도우·macOS 같은 현대 범용 운영체제는 선점형이다. 언제든 끼어들 수 있으므로 공유 데이터를 고치던 도중에 CPU를 빼앗길 수 있다. 그러면 끼어든 프로세스가 반쯤 고쳐진 값을 보게 되고, 실행 순서에 따라 결과가 달라지는 경쟁 상태(race condition)가 생긴다. 그래서 이런 구간은 동기화로 막아야 한다.

좋고 나쁨을 재는 기준

스케줄링 알고리즘은 아래 기준으로 비교한다. 이 가운데 처리량(throughput)은 단위 시간에 끝낸 작업 수를 뜻한다. 기준끼리 서로 부딪히기 때문에, 한 기준을 좋게 만들면 다른 기준이 나빠지는 일이 흔하다.

기준	뜻	좋은 방향
CPU 이용률(utilization)	CPU가 놀지 않고 일한 시간의 비율	높게
처리량	단위 시간에 끝낸 작업 수	높게
반환 시간(turnaround time)	도착부터 완료까지 걸린 시간	짧게
대기 시간	준비 큐에서 기다린 시간의 합	짧게
응답 시간(response time)	도착부터 처음 CPU를 받기까지 걸린 시간	짧게

반환 시간과 대기 시간은 배치 작업처럼 "언제 끝나느냐"가 중요할 때의 기준이다. 응답 시간은 사람이 화면 앞에서 기다리는 대화형 작업의 기준이다.

FCFS: 온 순서대로

FCFS(First-Come First-Served, 선입 선처리)는 준비 큐에 먼저 도착한 프로세스부터 끝날 때까지 실행하는 비선점 방식이다. 가장 단순하지만 도착 순서에 따라 성능이 크게 흔들린다. 세 프로세스가 시각 0에 함께 도착했고 CPU 버스트가 P1 24ms, P2 3ms, P3 3ms라고 하자.

실행 순서	각자 기다린 시간	평균
P1 → P2 → P3	0, 24, 27	17ms
P2 → P3 → P1	0, 3, 6	3ms

순서만 바꿨는데 평균 대기 시간이 17ms에서 3ms로 줄었다. 앞의 경우처럼 긴 작업 하나 뒤에 짧은 작업들이 줄줄이 묶여 기다리는 현상을 호위 효과(convoy effect)라고 한다. 느린 트럭 뒤에 승용차들이 줄지어 서는 모습에서 온 이름이다.

이어지는 내용은 CPU 스케줄링 2에서 다룬다.

면접 포인트

• "선점과 비선점의 차이는?" → 실행 중인 프로세스의 CPU를 커널이 빼앗을 수 있느냐. 선점은 타이머 인터럽트로 제어권을 되찾는다.
• "스케줄링 알고리즘은 무엇으로 비교하나요?" → CPU 이용률·처리량은 높게, 반환 시간·대기 시간·응답 시간은 짧게. 배치 작업은 반환·대기 시간, 대화형 작업은 응답 시간이 기준이다.
• "호위 효과란?" → FCFS에서 긴 작업 하나 뒤에 짧은 작업들이 묶여 평균 대기 시간이 길어지는 현상. 같은 작업도 순서만 바꾸면 평균 17ms가 3ms로 준다.