🗓 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는 현재 실행중인 프로세스의 남은 시간과 준비상태 큐에 새로 도착한 프로세스의 실행 시간을 비교하여 가장 짧은 실행 시간을 요구하는 프로세스에게 CPU를 할당하는 기법이다.

• 시분할 시스템에 유용하며, 준비 상태 큐에 있는 각 프로세스의 실행 시간을 추적하여 보유하고 있어야 하므로 오버헤드가 증가함

---

참고,
길벗알앤디. 『정보처리기사 실기 단기완성』. 길벗. 2023.