🗓 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, 반환 시간 : 45 - JOB3 : 8에 도착하여 JOB2가 완료될 때까지 대기한 후 JOB2가 완료된 48에서 실행을 시작하여 50에 작업이 완료되므로,
대기 시간 : 40, 반환 시간 : 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)/2 = 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 기법과 같아지고, 할당되는 시간이 작을 경우 문맥 교환 및 오버헤드가 자주 발생되어 요청된 작업을 신속히 처리할 수 없음
SRT(Shortest Remaining Time)
SRT는 남은 실행 시간이 가장 짧은 프로세스를 우선 실행하는 방식이다. 이는 선점형 스케줄링 알고리즘으로, 새로운 프로세스가 도착했을 때 현재 실행 중인 프로세스보다 남은 실행 시간이 짧다면, 현재 실행 중인 프로세스를 중단하고 새로 도착한 프로세스를 실행합니다.
- 시분할 시스템에 유용하며, 준비 상태 큐에 있는 각 프로세스의 실행 시간을 추적하여 보유하고 있어야 하므로 오버헤드가 증가함
| 프로세스 번호 | 도착 시간(Arrival Time) | 실행 시간(Burst Time) | 종료 시간 | 대기 시간(종료 시간 - 도착 시간 - 실행 시간) |
|---|---|---|---|---|
| P1 | 0 | 8 | 17 | 17 - 0 - 8 = 9 |
| P2 | 1 | 4 | 5 | 5 - 1 - 4 = 0 |
| P3 | 2 | 9 | 26 | 26 - 2 - 9 = 15 |
| P4 | 3 | 5 | 10 | 10 - 3 - 5 = 2 |
SRT 스케줄링 진행 과정:
0: P1 들어옴 (남은 시간 8 → 7) P1 실행
1: P2 들어옴 (남은 시간 4 → 3, 잔여시간이 가장 적음) P2 실행
2: P3 들어옴 P2 실행
3: P4 들어옴 P2 실행
4: P2 실행 (남은 시간 1 → 0)
5: → P2 종료
5~9: P4 실행 (남은 시간 5 → 0, P2 종료 후 잔여시간이 최처)
10: → P4 종료
10~16: P1 실행 (남은 시간 7 → 0, P4 종료 후 잔여시간이 최처)
17: → P1 종료
17~25: P3 실행 (남은 시간 9 → 0) → P3 종료
26: → P3 종료✩ 대기 시간 = 종료 시간 - 도착 시간 - 실행 시간(CPU에서 실제로 사용된 시간)
- 각 프로세스가 CPU에서 실제 실행된 시간을 제외하고 기다린 시간을 의미
- 프로세스가 도착한 이후부터 종료되기 전까지의 전체 시간에서 실제 CPU에서 실행된 시간을 뺀 값.
P1 대기시간: 0에서 한 번 실행, 1에서 실행되기 직전인 9초까지. "9초"
P2 대기시간: 들어오자마자 실행되고 끝남. "0초"
P3 대기시간: 들어온 2에서부터 실행되기 직전인 16초까지 "15초"
P4 대기시간: 들어온 3에서부터 실행되기 직전인 4초까지 "2초"✩ 평균 대기 시간 : ( 9 + 0 + 15 + 2 ) / 4 = 6.5
참고,
길벗알앤디. 『정보처리기사 실기 단기완성』. 길벗. 2023.
