topic★★★★★난이도 · 약 30분
CPU 스케줄링
준비 큐에서 다음 실행할 프로세스를 선택하는 알고리즘. 평균 대기·반환 시간으로 평가한다.
#OS#스케줄링#실기계산
왜 배우는가
실기 계산 문제의 단골. FCFS와 SJF의 간트 차트를 손으로 그려 평균 대기 시간(WT)을 계산할 수 있어야 한다. 선점/비선점 구분도 단답형으로 매회 출제된다.
은 운영체제가 여러 프로세스 중 누구에게 CPU를 줄지 결정하는 정책이다. 크게 비선점(Non-preemptive) 과 선점(Preemptive) 으로 나뉜다.
| 분류 | 알고리즘 | 특징 |
|---|---|---|
| 비선점 | FCFS | 도착 순서대로, 구현 단순 |
| 비선점 | SJF | 실행시간 짧은 것 우선 (기아 발생) |
| 비선점 | 대기시간 고려해 기아 해결 | |
| 비선점 | 우선순위 | 정적/동적 우선순위 |
| 선점 | Round Robin | 시간 할당량(Quantum) 단위 순환 |
| 선점 | SRT | SJF의 선점 버전 |
| 선점 | 다단계 피드백 큐 | 여러 큐를 오가며 우선순위 조정 |
HRN 공식 — 우선순위 = (대기시간 + 서비스시간) / 서비스시간. 공식 자체가 실기 단답형으로 출제된다.
아래 시뮬레이터에서 같은 4개 프로세스에 대해 FCFS / SJF / Round Robin을 번갈아 선택해 보자. 평균 대기 시간이 알고리즘마다 얼마나 달라지는지 직접 확인할 수 있다.
알고리즘:
| 프로세스 | 도착 (AT) | 실행 (BT) | 완료 (CT) | 대기 (WT) | 반환 (TAT) |
|---|---|---|---|---|---|
| P1 | 0 | 7 | 7 | 0 | 7 |
| P2 | 2 | 4 | 11 | 5 | 9 |
| P3 | 4 | 1 | 12 | 7 | 8 |
| P4 | 5 | 4 | 16 | 7 | 11 |
Gantt Chart
P1
P2
P3
P4
07111216
평균 대기 시간
4.75
평균 반환 시간
8.75
알고리즘을 바꾸면 같은 프로세스 집합에 대해 결과가 어떻게 달라지는지 비교해 보자.
계산 공식 — 대기시간(WT) = 반환시간(TAT) − 실행시간(BT). 반환시간(TAT) = 완료시간(CT) − 도착시간(AT).
실기 드릴 3문항
edit실기 드릴 · 단답형
SJF의 기아(starvation) 문제를 해결하기 위해 대기시간을 우선순위 계산에 반영하는 비선점 스케줄링 알고리즘은?
edit실기 드릴 · 단답형
다음 4개 프로세스에 대해 FCFS로 스케줄링할 때 평균 대기 시간은? P1(AT=0, BT=7), P2(AT=2, BT=4), P3(AT=4, BT=1), P4(AT=5, BT=4)
check_circle실기 드릴 · OX
Round Robin은 선점형 스케줄링 알고리즘이다.