테마
CPU 스케줄링
CPU 스케줄링(CPU scheduling)은 준비 상태의 프로세스 중 다음에 누가 CPU를 쓸지 정하는 일이다. 순서만 바꿔도 기다리는 시간이 크게 달라지므로 여러 기법이 있다. 실기 시험에서는 기법의 이름과 선점 여부, HRN(Highest Response-ratio Next, 응답률 우선)의 우선순위 공식을 묻고, 도착·실행 시간표를 주고 평균 대기 시간과 평균 반환 시간을 계산하게 한다. 기법별 장단점의 원리는 CS 카테고리의 CPU 스케줄링 문서가 다룬다.
선점과 비선점
비선점(non-preemptive) 기법은 한 프로세스가 CPU를 잡으면 끝나거나 스스로 내놓을 때까지 뺏지 않는다. 선점(preemptive) 기법은 더 급한 프로세스가 오거나 시간이 다 되면 CPU를 빼앗아 넘긴다.
| 구분 | 기법 |
|---|---|
| 비선점 | FCFS, SJF, HRN, 우선순위(비선점형) |
| 선점 | SRT(Shortest Remaining Time, 남은 시간 최소 우선), RR, 우선순위(선점형), MLQ, MLFQ |
기법별 규칙
FCFS(First Come First Served, 선입선처리): 먼저 도착한 순서대로 처리한다. 먼저 들어온 것을 먼저 처리한다고 해서 선입선출(FIFO, First In First Out)이라고도 한다. 긴 작업 뒤의 짧은 작업이 오래 기다린다.
SJF(Shortest Job First, 최단 작업 우선): 실행 시간이 가장 짧은 프로세스부터 처리한다. 모든 프로세스가 함께 기다릴 때 비선점 기법 가운데 평균 대기 시간이 가장 짧지만, 긴 작업은 계속 밀려 기아 상태(starvation) 에 빠질 수 있다.
HRN(Highest Response-ratio Next): SJF의 기아를 줄이려고 기다린 시간을 반영한다. 아래 응답률이 큰 순서로 처리한다. 오래 기다리면 분자가 커져 긴 작업도 결국 차례가 온다.
우선순위 = (대기 시간 + 서비스 시간) ÷ 서비스 시간
SRT(Shortest Remaining Time): SJF의 선점형이다. 새 프로세스가 도착할 때마다 남은 실행 시간을 비교해 가장 짧은 쪽에 CPU를 준다.
RR(Round Robin, 순환 할당): 시분할 시스템(time-sharing system)을 위해 고안됐다. 도착 순서대로 돌되 각자 시간 할당량(time quantum) 만큼만 실행하고 큐 뒤로 간다. 할당량이 너무 크면 FCFS와 같아지고, 너무 작으면 문맥 교환(context switch)이 잦아 오버헤드(overhead)가 커진다.
우선순위(priority): 정해진 우선순위가 높은 것부터 처리한다. 낮은 쪽의 기아를 막으려고 오래 기다린 프로세스의 우선순위를 점점 올리는 것을 에이징(aging) 이라 한다.
MLQ(Multi-Level Queue, 다단계 큐): 프로세스를 성격별로 여러 큐에 고정 배치하고 큐마다 다른 기법을 쓴다. 큐 사이 이동이 없다.
MLFQ(Multi-Level Feedback Queue, 다단계 피드백 큐): 큐 사이 이동을 허용한다. 할당량을 다 쓴 프로세스는 아래 큐로 내려가, CPU를 오래 쓰는 작업은 점점 뒤로 밀린다.
계산 절차
반환 시간 = 완료 시각 − 도착 시각, 대기 시간 = 반환 시간 − 실행 시간이다. 간트 차트(Gantt chart)를 먼저 그리고 각 프로세스의 완료 시각을 읽으면 두 값이 나온다. 아래 표는 P1(도착 0, 실행 7), P2(2, 4), P3(3, 1), P4(5, 4)를 시뮬레이터로 계산한 결과다. 기준이 같으면 먼저 도착한 쪽을 고른다.
| 기법 | 실행 순서 | 평균 반환 | 평균 대기 |
|---|---|---|---|
| FCFS | P1 → P2 → P3 → P4 | 9 | 5 |
| SJF | P1 → P3 → P2 → P4 | 8.25 | 4.25 |
| SRT | P1 → P2 → P3 → P2 → P4 → P1 | 7 | 3 |
| RR(할당량 4) | P1 → P2 → P3 → P1 → P4 | 8.75 | 4.75 |
SJF는 비선점이라 시각 0에 혼자 도착한 P1이 7까지 다 쓴다. 그다음 시각 7에 기다리는 P2·P3·P4 중 가장 짧은 P3이 먼저다. HRN으로 시각 7의 응답률을 구하면 P2 = (5+4)/4 = 2.25, P3 = (4+1)/1 = 5, P4 = (2+4)/4 = 1.5라 P3이 먼저다.
시험 포인트
- "(대기 시간 + 서비스 시간) / 서비스 시간" → HRN, 값이 클수록 먼저.
- "SJF의 선점형, 남은 시간 비교" → SRT. "시간 할당량만큼 돌아가며" → RR.
- "오래 기다린 프로세스의 우선순위를 높여 기아 방지" → 에이징.
- 반환 = 완료 − 도착, 대기 = 반환 − 실행. 평균은 프로세스 수로 나눈다.