CPU 스케줄링
쉽게 말하면
CPU는 하나인데 일하려는 프로세스는 여럿이라 순서를 정해야 해요. 이걸 스케줄링이라 해요. 온 순서대로(FCFS), 짧은 일 먼저(SJF), 오래 기다린 일에 가산점(HRN), 정해진 시간만큼 돌아가며(RR) 같은 방법이 있어요. 한번 CPU를 잡으면 끝까지 쓰는 비선점 방식과, 더 급한 일이 오면 빼앗을 수 있는 선점 방식으로 나뉘어요. 시험에는 평균 대기 시간 계산이 자주 나와요.
시험용 정의
CPU 스케줄링은 준비 상태의 프로세스 중 어느 것에 CPU를 줄지 정하는 것이다. 비선점 방식은 CPU를 받은 프로세스가 끝날 때까지 빼앗지 않는다: FCFS(FIFO, 먼저 온 순서), SJF(실행 시간이 가장 짧은 것 먼저, 평균 대기 시간 최소, 긴 작업은 기아 가능), HRN(SJF의 기아를 보완, 우선순위 = (대기 시간 + 서비스 시간) / 서비스 시간), 우선순위, 기한부. 선점 방식은 실행 중에도 CPU를 빼앗을 수 있다: RR(라운드 로빈, 같은 시간 할당량만큼 돌아가며), SRT(남은 실행 시간이 가장 짧은 것, SJF의 선점형), 선점 우선순위, 다단계 큐(MLQ), 다단계 피드백 큐(MLFQ). 대기 시간 = 시작 시간 − 도착 시간, 반환 시간 = 종료 시간 − 도착 시간 = 대기 시간 + 실행 시간이다.
비유로 이해하기
놀이공원 줄이다. FCFS는 그냥 온 순서, SJF는 금방 타는 사람 먼저, HRN은 오래 기다린 사람에게 가산점, RR은 한 사람당 5분씩 돌아가며 타는 방식이다.
자세히
그림으로 보기: FCFS와 SJF 비교
먼저 알아 둘 말
| 말 | 뜻 |
|---|---|
| 선점 / 비선점 | 실행 중인 프로세스의 CPU를 빼앗을 수 있음 / 없음 |
| 서비스(실행) 시간 | 프로세스가 CPU를 써야 하는 시간 |
| 대기 시간 | 준비 큐에서 기다린 시간 |
| 반환 시간 | 도착부터 끝날 때까지 걸린 시간 |
| 시간 할당량(타임 슬라이스) | RR에서 한 번에 쓰는 CPU 시간 |
| 기아 상태 | 우선순위가 낮아 계속 밀려 실행되지 못하는 상태 |
계산 예: 모두 0초에 도착 (P1 6, P2 3, P3 8, P4 2)
| 방식 | 실행 순서 | 대기 시간 | 평균 대기 | 평균 반환 |
|---|---|---|---|---|
| FCFS | P1 → P2 → P3 → P4 | 0, 6, 9, 17 | 32 / 4 = 8 | (6 + 9 + 17 + 19) / 4 = 12.75 |
| SJF | P4 → P2 → P1 → P3 | P4 0, P2 2, P1 5, P3 11 | 18 / 4 = 4.5 | (2 + 5 + 11 + 19) / 4 = 9.25 |
RR 예: 할당량 4 (P1 6, P2 3, P3 8, 모두 0초 도착)
P1(0~4) → P2(4~7, 끝) → P3(7~11) → P1(11~13, 끝) → P3(13~17, 끝). 종료 시각 P2 7, P1 13, P3 17.
할당량이 너무 크면 FCFS와 같아지고, 너무 작으면 문맥 교환이 잦아 오버헤드가 커진다.
HRN 예
| 작업 | 대기 시간 | 서비스 시간 | 우선순위 |
|---|---|---|---|
| A | 10 | 5 | (10 + 5) / 5 = 3 |
| B | 6 | 2 | (6 + 2) / 2 = 4 ← 가장 먼저 |
| C | 20 | 10 | (20 + 10) / 10 = 3 |
기출에서 더 나온 것
| 말 | 뜻 |
|---|---|
| SSTF 디스크 스케줄링 | 현재 헤드 위치에서 가장 가까운 요청부터 처리한다 |
| FCFS 디스크 스케줄링 | 요청이 들어온 순서대로 처리한다 |
| SCAN | 헤드가 한 방향으로 끝까지 가며 처리하고 되돌아온다 |
시험에 이렇게 나와요
- HRN 우선순위 → (대기 시간 + 서비스 시간) / 서비스 시간, 값이 큰 것부터
- HRN → SJF의 긴 작업 차별을 보완
- SJF → 실행 시간이 가장 짧은 작업부터
- 처리 순서 문제 → 표를 보고 우선순위를 직접 계산
확인 문제
Q1. HRN 스케줄링에서 대기 시간이 10, 서비스 시간이 5인 작업의 우선순위 값은?
- 0.5
- 2
- 3
- 15
정답 보기
3번 3
HRN 우선순위 = (대기 시간 + 서비스 시간) / 서비스 시간 = (10 + 5) / 5 = 3. 값이 클수록 먼저 실행된다.
Q2. 선점형 스케줄링 기법은?
- HRN
- SJF
- FCFS
- RR
정답 보기
4번 RR
RR·SRT·다단계 큐가 선점형.
Q3. 작업 A(실행 5), B(실행 3), C(실행 1)가 모두 0초에 도착할 때 SJF의 평균 대기 시간은?
- 1.67
- 2
- 3
- 4.33
정답 보기
1번 1.67
C(0) → B(1) → A(4). (0 + 1 + 4) / 3 ≈ 1.67.
Q4. SJF의 단점인 긴 작업의 기아 현상을 보완해 대기 시간을 우선순위에 반영한 기법은?
- FCFS
- SRT
- HRN
- RR
정답 보기
3번 HRN
HRN은 오래 기다리면 우선순위가 올라간다.
Q5. SRT 스케줄링에 대한 설명으로 옳은 것은?
- 비선점 방식이다
- 남은 실행 시간이 가장 짧은 프로세스에 CPU를 준다
- 시간 할당량만큼씩 돌아가며 처리한다
- 도착 순서대로 처리한다
정답 보기
2번 남은 실행 시간이 가장 짧은 프로세스에 CPU를 준다
남은 실행 시간이 가장 짧은 프로세스에 CPU를 준다. SJF를 선점 방식으로 바꾼 것이다. 도착 순서는 FCFS, 시간 할당량은 RR이다.
헷갈리기 쉬운 O·X
HRN에서는 계산한 우선순위 값이 작을수록 먼저 실행된다.
정답 보기
X 클수록 먼저.
RR에서 시간 할당량이 아주 크면 FCFS와 비슷해진다.
정답 보기
O
FCFS는 선점형 스케줄링이다.
정답 보기
X 비선점형이다.