[정처기 실기] 프로세스 스케줄링
정보처리기사 실기 — 프로세스 스케줄링 (평균 대기·반환 시간)
0. 한눈에 보기
| 항목 | 내용 |
|---|---|
| 출제 포인트 | 간트 차트 작성 → 대기 시간·반환 시간 계산 → 평균 구하기 |
| 핵심 공식 | 반환 = 완료 − 도착 / 대기 = 반환 − 실행 (= 완료 − 도착 − 실행) |
| 자주 나오는 알고리즘 | FCFS, SJF, SRT, HRN, Round Robin |
1. 핵심 개념
1.1 용어 정리
| 용어 | 영어 | 정의 |
|---|---|---|
| 도착 시간 | Arrival Time | 프로세스가 Ready Queue에 들어온 시각 |
| 실행 시간 | Burst Time / Service Time | CPU에서 실제로 실행되는 시간 |
| 완료 시간 | Completion Time | 프로세스가 끝난 시각 |
| 대기 시간 | Waiting Time | Ready Queue에서 기다린 총 시간 |
| 반환 시간 | Turnaround Time | 도착 → 완료까지 걸린 총 시간 |
| 응답 시간 | Response Time | 도착 후 처음 CPU를 받을 때까지 걸린 시간 |
1.2 필수 공식 — 암기
| 지표 | 공식 |
|---|---|
| 반환 시간 | 완료 시간 − 도착 시간 |
| 대기 시간 | 반환 시간 − 실행 시간 |
| (= 완료 시간 − 도착 시간 − 실행 시간) | |
| 평균 대기 시간 | (P1 대기 + P2 대기 + …) ÷ 프로세스 수 |
| 평균 반환 시간 | (P1 반환 + P2 반환 + …) ÷ 프로세스 수 |
반환 = 대기 + 실행 관계를 반드시 기억할 것.
1.3 선점형 vs 비선점형
| 구분 | 설명 | 해당 알고리즘 |
|---|---|---|
| 비선점형 | CPU 할당받으면 끝날 때까지 유지 | FCFS, 비선점 SJF, HRN |
| 선점형 | 실행 중 더 우선 프로세스가 오면 CPU 빼앗김 | SRT, Round Robin, 선점 우선순위 |
2. 스케줄링 알고리즘 요약
| 알고리즘 | 영어 | 선점 | 선택 기준 | 특징 |
|---|---|---|---|---|
| FCFS | First Come First Served | X | 도착 순서 | FIFO, Convoy Effect(호위 효과) |
| SJF | Shortest Job First | X | 실행 시간 짧은 것 | 평균 대기 시간 최소 (이론상) |
| SRT | Shortest Remaining Time | O | 남은 실행 시간 짧은 것 | 선점형 SJF |
| HRN | Highest Response Ratio Next | X | 응답률 높은 것 | SJF의 기아(Starvation) 완화 |
| RR | Round Robin | O | 시간 할당량(Time Quantum) 순환 | 공정성, 시분할 |
HRN 응답률 공식
응답률 = (대기 시간 + 실행 시간) ÷ 실행 시간
= (현재까지 기다린 시간 + 서비스 시간) ÷ 서비스 시간
스케줄링 결정 시점마다 Ready Queue의 각 프로세스 응답률을 계산 → 가장 큰 프로세스 실행.
3. 풀이 방법 (4단계)
Step 1 — 표 정리
문제에서 주어진 프로세스 / 도착 시간 / 실행 시간 표를 그대로 옮긴다.
Step 2 — 간트 차트(Gantt Chart) 작성
- 가로축 = 시간(ms)
- 각 프로세스가 CPU를 언제~언제 쓰는지 막대로 표시
- 도착 시각 이전에는 실행 불가
- 선점형은 남은 실행 시간을 계속 갱신
Step 3 — 프로세스별 완료·대기·반환 계산
| 프로세스 | 도착 | 실행 | 완료 | 반환 (완료−도착) | 대기 (반환−실행) |
|---|
Step 4 — 평균 계산
평균 대기 = Σ 대기 시간 ÷ n
평균 반환 = Σ 반환 시간 ÷ n
4. 기출 예제 — 공통 프로세스 표
아래 모든 알고리즘 풀이는 동일한 표를 사용한다.
| 프로세스 | 도착 시간 (ms) | 실행 시간 (ms) |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |
5. 알고리즘별 풀이
5.1 FCFS (First Come First Served)
도착 순서대로 실행. 선점 없음.
간트 차트
| P1 (8) | P2 (4) | P3 (9) | P4 (5) |
0 8 12 21 26
계산
| 프로세스 | 도착 | 실행 | 완료 | 반환 | 대기 |
|---|---|---|---|---|---|
| P1 | 0 | 8 | 8 | 8 − 0 = 8 | 8 − 8 = 0 |
| P2 | 1 | 4 | 12 | 12 − 1 = 11 | 11 − 4 = 7 |
| P3 | 2 | 9 | 21 | 21 − 2 = 19 | 19 − 9 = 10 |
| P4 | 3 | 5 | 26 | 26 − 3 = 23 | 23 − 5 = 18 |
| 결과 | 값 |
|---|---|
| 평균 대기 시간 | (0 + 7 + 10 + 18) ÷ 4 = 8.75 ms |
| 평균 반환 시간 | (8 + 11 + 19 + 23) ÷ 4 = 15.25 ms |
5.2 SJF (Shortest Job First) — 비선점형
CPU가 비는 순간, Ready Queue에서 실행 시간이 가장 짧은 프로세스 선택.
선택 순서
- t=0 → P1만 도착 → P1 실행 (0~8)
- t=8 → P2(4), P3(9), P4(5) → P2(4) 선택 (8~12)
- t=12 → P3(9), P4(5) → P4(5) 선택 (12~17)
- t=17 → P3(9) (17~26)
간트 차트
| P1 (8) | P2 (4) | P4 (5) | P3 (9) |
0 8 12 17 26
계산
| 프로세스 | 도착 | 실행 | 완료 | 반환 | 대기 |
|---|---|---|---|---|---|
| P1 | 0 | 8 | 8 | 8 | 0 |
| P2 | 1 | 4 | 12 | 11 | 7 |
| P4 | 3 | 5 | 17 | 14 | 9 |
| P3 | 2 | 9 | 26 | 24 | 15 |
| 결과 | 값 |
|---|---|
| 평균 대기 시간 | (0 + 7 + 9 + 15) ÷ 4 = 7.75 ms |
| 평균 반환 시간 | (8 + 11 + 14 + 24) ÷ 4 = 14.25 ms |
5.3 SRT (Shortest Remaining Time) — 선점형 SJF
남은 실행 시간이 더 짧은 프로세스가 도착하면 즉시 선점.
실행 흐름
| 시각 | 이벤트 | CPU |
|---|---|---|
| 0 | P1 시작 (남은 8) | P1 |
| 1 | P2 도착 (4) < P1 남은 7 → 선점 | P2 |
| 5 | P2 완료. P4(5) < P1(7) < P3(9) | P4 |
| 10 | P4 완료. P1(7) < P3(9) | P1 |
| 17 | P1 완료 | P3 |
| 26 | P3 완료 | — |
간트 차트
|P1| P2 (4) | P4 (5) | P1 (7) | P3 (9) |
0 1 5 10 17 26
계산
| 프로세스 | 도착 | 실행 | 완료 | 반환 | 대기 |
|---|---|---|---|---|---|
| P1 | 0 | 8 | 17 | 17 − 0 = 17 | 17 − 8 = 9 |
| P2 | 1 | 4 | 5 | 5 − 1 = 4 | 4 − 4 = 0 |
| P3 | 2 | 9 | 26 | 26 − 2 = 24 | 24 − 9 = 15 |
| P4 | 3 | 5 | 10 | 10 − 3 = 7 | 7 − 5 = 2 |
| 결과 | 값 |
|---|---|
| 평균 대기 시간 | (9 + 0 + 15 + 2) ÷ 4 = 6.5 ms |
| 평균 반환 시간 | (17 + 4 + 24 + 7) ÷ 4 = 13 ms |
FCFS·SJF보다 평균 대기·반환 시간이 짧아지는 경우가 많다.
5.4 HRN (Highest Response Ratio Next)
응답률 = (대기 + 실행) ÷ 실행 → 가장 높은 프로세스 실행 (비선점).
t=8 시점 (P1 완료, P2·P3·P4 대기 중)
| 프로세스 | 대기 | 실행 | 응답률 |
|---|---|---|---|
| P2 | 7 | 4 | (7+4)/4 = 2.75 ← 최대 |
| P3 | 6 | 9 | (6+9)/9 = 1.67 |
| P4 | 5 | 5 | (5+5)/5 = 2.0 |
→ P2 실행 (8~12)
t=12 시점
| 프로세스 | 대기 | 실행 | 응답률 |
|---|---|---|---|
| P4 | 9 | 5 | (9+5)/5 = 2.8 ← 최대 |
| P3 | 10 | 9 | (10+9)/9 ≈ 2.11 |
→ P4 실행 (1217) → P3 (1726)
간트 차트 (이 예제에서는 SJF와 동일)
| P1 (8) | P2 (4) | P4 (5) | P3 (9) |
0 8 12 17 26
| 결과 | 값 | |------| | | 평균 대기 시간 | 7.75 ms | | 평균 반환 시간 | 14.25 ms |
이 표에서는 SJF와 결과가 같지만, 대기가 길어진 프로세스는 HRN에서 응답률이 올라가 실행 기회를 받는다.
5.5 Round Robin (RR) — 시간 할당량 q = 4 ms
FIFO + 시간 할당량. q만큼 실행 후 큐 맨 뒤로 → 선점형.
풀이 팁
- Ready Queue를 종이에 적고 1번부터 q만큼 실행
- 실행 중 새 프로세스 도착 → 큐 뒤에 추가
- q 끝나면 다음 프로세스로 (현재 프로세스는 남은 시간 있으면 큐 뒤로)
간트 차트
|P1 (4) | P2 (4) | P3 (4) | P4 (4) | P1 (4) | P3 (4) | P4 (1) | P3 (1) |
0 4 8 12 16 20 24 25 26
완료 시각: P2=8, P1=20, P4=25, P3=26
계산
| 프로세스 | 도착 | 실행 | 완료 | 반환 | 대기 |
|---|---|---|---|---|---|
| P1 | 0 | 8 | 20 | 20 | 20 − 8 = 12 |
| P2 | 1 | 4 | 8 | 7 | 7 − 4 = 3 |
| P3 | 2 | 9 | 26 | 24 | 24 − 9 = 15 |
| P4 | 3 | 5 | 25 | 22 | 22 − 5 = 17 |
| 결과 | 값 |
|---|---|
| 평균 대기 시간 | (12 + 3 + 15 + 17) ÷ 4 = 11.75 ms |
| 평균 반환 시간 | (20 + 7 + 24 + 22) ÷ 4 = 18.25 ms |
q가 크면 FCFS에 가깝고, 작으면 문맥 교환은 늘지만 응답성은 좋아진다.
6. 알고리즘 비교 (예제 표 기준)
| 알고리즘 | 평균 대기 (ms) | 평균 반환 (ms) | 비고 |
|---|---|---|---|
| FCFS | 8.75 | 15.25 | 가장 단순, P4 대기 18로 불리 |
| SJF (비선점) | 7.75 | 14.25 | 짧은 작업 우선 |
| SRT (선점) | 6.5 | 13 | 이 예제에서 최소 |
| HRN | 7.75 | 14.25 | SJF와 동일 (표에 따라 다름) |
| RR (q=4) | 11.75 | 18.25 | 공정하지만 평균은 길어질 수 있음 |
7. 시험에서 자주 틀리는 포인트
| 실수 | 올바른 처리 |
|---|---|
| 반환·대기 혼동 | 반환 = 완료 − 도착, 대기 = 반환 − 실행 |
| 선점형에서 실행 시간 그대로 사용 | 남은 실행 시간으로 비교 (SRT, RR) |
| 도착 전 실행 | 도착 시각 이후에만 Ready Queue 진입 |
| RR 큐 순서 | 실행 끝난 프로세스 → 큐 맨 뒤 |
| HRN 시점 | CPU 비는 순간마다 응답률 재계산 |
| 평균 계산 | 합 ÷ 프로세스 개수 (표 행 수) |
8. RR 빠른 풀이 템플릿
[Ready Queue] P1 → P2 → P3 → … (1번부터 q만큼)
O = 도착 (큐에 추가)
V = 실행 (q 또는 남은 시간만큼)
X = 대기 (큐에서 순서 기다림)
한 칸(V) 끝나면 → 남은 시간 있으면 큐 뒤로 / 없으면 완료 기록