🗓 Preemptive(선점 스케줄링)
선점 스케줄링은 하나의 프로세스가 CPU를 할당받아 실행하고 있을 때 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법이다.
- 주로 빠른 응답 시간을 요구하는 대화식 시분할 시스템에 사용됨
- 종류 : FCFS, SJF, HRN, RR, SRT
FCFS(First Come First Service) = FIFO
FCFS는 선입선출(Fisrt In First Out)로, 준비상태 큐에 도착한 순서에 따라 차례로 CPU를 할당하는 기법이다.
| 작업 | 도착 시간 | CPU Burst Time(사용시간) |
|---|---|---|
| JOB1 | 0 | 13 |
| JOB2 | 3 | 35 |
| JOB3 | 8 | 2 |
✩ 대기 시간 = 바로 앞 프로세스까지의 진행 시간
✩ 반환 시간 = 대기시간 + 실행 시간
- JOB1 : 도착하자마자 실행하여 13에서 작업이 완료되므로,
대기 시간 : 0, 반환 시간 : 13 - JOB2 : 3에 도착하여 JOB1이 완료될 때까지 대기한 후 JOB1이 완료된 13에서 실행을 시작하여 48에 작업이 완료되므로,
대기 시간 : 10, 반환 시간 : (10+35)45 - JOB3 : 8에 도착하여 JOB2가 완료될 때까지 대기한 후 JOB2가 완료된 48에서 실행을 시작하여 50에 작업이 완료되므로,
대기 시간 : 40, 반환 시간 : (40+2)42
✩ 평균 실행 시간 : (13 + 35 + 2) / 3 = 16.66
✩ 평균 대기 시간 : (0 + 10 + 40) / 3 = 16.66
✩ 평균 반환 시간 : (13 + 45 + 42) / 3 = 33.33
SJF(Shortest Job First)
SJF는 준비상태 큐에서 기다리고 있는 프로세스 중에서 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 기법이다.
- 가장 적은 평균 대기 시간을 제공하는 최적 알고리즘
- 실행 시간이 긴 프로세스는 실행시간이 짧은 프로세스에게 할당 순위가 밀려 무한 연기 상태가 발생될 수 있다.
| 프로세스 번호 | 실행 시간 | 프로세스 번호 | 실행 시간 | 대기 시간 | 반환 시간 | |
|---|---|---|---|---|---|---|
| P1 | 7 | P4 | 3 | 0 | 3 | |
| P2 | 8 | P3 | 4 | 3 | 7 | |
| P3 | 4 | P1 | 7 | 7 | 14 | |
| P4 | 3 | P2 | 8 | 14 | 22 |
✩ 평균 대기 시간 : (0 + 3 + 7 + 14) / 4 = 6
✩ 평균 반환 시간 : (3 + 7 +14 + 22) / 4 = 11.5
HRN(Highest Response-ratio Next)
HRN은 대기 시간과 서비스(실행) 시간을 이용하는 기법이다.
- 우선순위를 계한하여 그 숫자가 가장 높은 것부터 낮은 순으로 우선순위가 부여됨
- 우선순위 계산식 :
(대기 시간 + 서비스 시간) / 서비스 시간
| 프로세스 번호 | 실행 시간 | 대기 시간 | 우선순위 계산 |
|---|---|---|---|
| P1 | 20 | 10 | (20+10)/20 = 1.5 |
| P2 | 4 | 20 | (4+20)/4 = 6 |
| P3 | 6 | 10 | (6+10)/6 = 2.6 |
우선순위 : P2 → P3 → P1
RR(Round Robin)
RR은 각 프로세스를 시간 할당량(Time Slice, Quantum)동안만 실행한 후 실행이 완료되지 않으면 다음 프로세스에게 CPU를 넘겨주는 기법이다.
- 시분할 시스템(Time Sharting System)을 위해 고안된 방식으로, 할당되는 시간의 크기가 작으면 작은 프로세스들에게 유리
- 할당되는 시간이 클 경우 FCFS 기법과 같아지고, 할당되는 시간이 작을 경우 문맥 교환 및 오버헤드가 자주 발생되어 요청된 작업을 신속히 처리할 수 없음
⏱️ 시간 할당량 (Time Quantum): 3
- Time Quantum = 3
→ 프로세스는 최대 3 단위 시간만 실행하고 양보(남은 시간이 있다면 큐 맨 뒤로 이동) - 도착 시간이 빠른 순서대로 Ready Queue에 들어감
- 시간 흐름에 따라 새 프로세스가 도착하면 그때 큐에 추가
🔍 주어진 프로세스 정보:
| 프로세스 번호 | 도착 시간(Arrival Time) | 실행 시간(Burst Time) |
|---|---|---|
| P1 | 0 | 5 |
| P2 | 1 | 3 |
| P3 | 2 | 8 |
| P4 | 3 | 6 |
🧩 RR 스케줄링 진행 과정:
t=0~3: P1 도착 → P1 실행(5 → 2 남음) → 큐 뒤로
t=1: P2 도착
t=2: P3 도착
t=3~6: P2 실행(3 → 0) → P2 종료
t=3: P4 도착
t=6~9: P3 실행(8-3) → 큐 뒤로
t=9~12: P4 실행(6-3) → 큐 뒤로
t=12~14: 남은 P1 2 실행 → P1 종료
t=14~17: 남은 P3 5 실행(5-3) → 큐 뒤로
t=17~20: 남은 P4 3 실행(3-0) → P4 종료
t=20~22: 남은 P3 2 실행 → P3 종료🕓 실행 타임라인 (Gantt Chart):
| 0 | 3 | 6 | 9 | 12 | 14 | 17 | 20 | 22 |
| P1 | P2 | P3 | P4 | P1 | P3 | P4 | P3 |📊 대기 시간 계산
✩ 대기 시간 = 종료 시간 - 도착 시간 - 실행 시간
✩ 평균 대기 시간 : (9+2+12+11)/4 = 34/4 =8.5
SRT(Shortest Remaining Time)
SRT는 남은 실행 시간이 가장 짧은 프로세스를 우선 실행하는 방식이다. 이는 선점형 스케줄링 알고리즘으로, 새로운 프로세스가 도착했을 때 현재 실행 중인 프로세스보다 남은 실행 시간이 짧다면, 현재 실행 중인 프로세스를 중단하고 새로 도착한 프로세스를 실행합니다.
- 시분할 시스템에 유용하며, 준비 상태 큐에 있는 각 프로세스의 실행 시간을 추적하여 보유하고 있어야 하므로 오버헤드가 증가함
🔍 주어진 프로세스 정보:
| 프로세스 번호 | 도착 시간(Arrival Time) | 실행 시간(Burst Time) |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |
🧩 SRT 스케줄링 진행 과정:
t=0: P1 도착 → 실행 시작 (남은 8)
t=1: P2 도착(P2 남은 시간 4 < P1 남은 시간 7) → 선점 발생 → P2 실행
t=2: P3 도착(P3 남은 시간 9 > P2 남은 시간 3) → P2 유지
t=3: P4 도착(P4 남은 시간 5 > P2 남은 시간 2) → P2 유지
t=5: P2 종료 → 남은: "P1(7), P3(9), P4(5)" → P4 선택
t=10: P4 종료 → 남은: "P1(7), P3(9)" → P1 선택
t=17: P1 종료 → 남은: P3(9) → P3 선택
t=26: P3 종료🕓 실행 타임라인 (Gantt Chart):
0 1 5 10 17 26
| P1 | P2 | P4 | P1 | P3 |📊 대기 시간 계산
✩ 대기 시간 = 종료 시간 - 도착 시간 - 실행 시간(CPU에서 실제로 사용된 시간)
- 각 프로세스가 CPU에서 실제 실행된 시간을 제외하고 기다린 시간을 의미
- 프로세스가 도착한 이후부터 종료되기 전까지의 전체 시간에서 실제 CPU에서 실행된 시간을 뺀 값
✩ 평균 대기 시간 : ( 9 + 0 + 15 + 2 ) / 4 = 6.5
참고,
길벗알앤디. 『정보처리기사 실기 단기완성』. 길벗. 2023.
