CPU 스케줄링 — 선점 vs 비선점

정의 — CPU를 누구에게 줄 것인가

CPU는 한 순간에 한 프로세스만 실행할 수 있다(코어 하나 기준). 준비 큐(ready queue)에는 실행을 기다리는 프로세스가 여럿 대기하는데, 이 중 다음에 CPU를 받을 프로세스를 고르는 일이 CPU 스케줄링이다. 목표는 CPU 이용률과 처리량은 높이고, 대기 시간·응답 시간·반환 시간은 줄이는 것이다.

핵심 구분 — 선점 vs 비선점

모든 스케줄링 알고리즘은 하나의 질문으로 갈린다: 실행 중인 프로세스에게서 CPU를 강제로 빼앗을 수 있는가?

비선점(non-preemptive): 한번 CPU를 받으면 스스로 끝내거나 입출력을 기다릴 때까지 계속 쓴다. 문맥 교환이 적어 오버헤드가 낮지만, 긴 작업 하나가 짧은 작업들을 오래 기다리게 할 수 있다.
선점(preemptive): 우선순위가 더 높은 프로세스가 오거나 할당 시간이 끝나면 CPU를 빼앗는다. 응답성이 좋아 대화형·실시간 시스템에 적합하지만, 문맥 교환 비용이 든다.

대표 알고리즘

비선점 계열

FCFS(First Come First Served): 도착 순서대로. 구현이 가장 단순하지만, 긴 프로세스 뒤의 짧은 프로세스들이 줄줄이 기다리는 호위 효과(convoy effect)가 생긴다.
SJF(Shortest Job First): 실행 시간이 가장 짧은 것부터. 평균 대기 시간이 이론상 최소지만, 긴 프로세스가 계속 밀리는 기아(starvation)가 생길 수 있다.
HRN(Highest Response-ratio Next): SJF의 기아를 보완. 우선순위를 다음 공식으로 계산해 값이 큰 것부터 실행한다.

우선순위 = (대기 시간 + 서비스 시간) / 서비스 시간

오래 기다릴수록 분자가 커져 긴 프로세스도 언젠가 뽑힌다(에이징 효과가 공식에 내장).

선점 계열

RR(Round Robin): 시간 할당량(time quantum)만큼 돌아가며 실행. 할당량이 너무 크면 FCFS와 비슷해지고, 너무 작으면 문맥 교환 오버헤드가 커진다. 시분할 시스템의 기본.
SRT(Shortest Remaining Time): SJF의 선점 버전. 남은 실행 시간이 더 짧은 프로세스가 도착하면 CPU를 빼앗는다.
다단계 큐 / 다단계 피드백 큐: 준비 큐를 여러 개로 나눠 큐마다 다른 정책을 쓴다. 피드백 큐는 프로세스가 큐 사이를 이동할 수 있어 유연하다.

예시 — FCFS 평균 대기 시간 계산

프로세스 P1(실행 24), P2(실행 3), P3(실행 3)이 이 순서로 동시에 도착했다고 하자(단위: ms).

실행 순서: P1(0~~24) → P2(24~~27) → P3(27~30)
대기 시간: P1=0, P2=24, P3=27 → 평균 (0+24+27)/3 = 17ms

순서를 P2 → P3 → P1로 바꾸면(SJF) 대기 시간이 P2=0, P3=3, P1=6으로 평균 3ms가 된다. 같은 작업이라도 순서가 평균 대기 시간을 크게 바꾼다는 것이 스케줄링의 존재 이유다.

시험에 자주 나오는 포인트

선점/비선점 분류: FCFS·SJF·HRN은 비선점, RR·SRT·다단계 피드백 큐는 선점. 매칭 문제로 가장 자주 나온다.
HRN 공식: (대기 시간 + 서비스 시간) / 서비스 시간. 값이 큰 쪽이 먼저다. 계산 문제로 출제된다.
평균 대기 시간 계산: 위 예시처럼 도착·실행 시간 표를 주고 FCFS·SJF·RR의 평균 대기 시간을 구하게 한다. 간트 차트를 그려 풀면 실수가 준다.
SRT는 SJF의 선점형이라는 대응 관계, RR의 타임 퀀텀 크기에 따른 동작 변화.
기아와 에이징: 기아는 우선순위가 낮아 계속 밀리는 현상, 에이징은 기다린 시간에 비례해 우선순위를 올려주는 해결책.