5. 프로세스 스케줄링 (3) - SPN, SRTN, HRRN

출처 : https://www.youtube.com/watch?v=keY9Wi7scEs&t=3s

 

 

 

SPN (Shortest-Process-Next) : Burst time이 짧은 애를 먼저 처리해주는 스케줄링 기법

 

FCFS 알고리즘의 경우 나의 burst time이 짧을 지라도 오래 기달려야 한다는 문제점이 있었다. 그래서 burst time이 짧은 애를 먼저 처리하자는 idea가 등장했다.

 

• Non-preemptive scheduling (비선점 스케줄링 : 누구도 내 것을 뺐을 수 없음)
• 스케줄링 기준
  • 실행시간 (burst time 기준)
  • Burst time 가장 작은 프로세스를 먼저 처리
    • SJF(Shortest Job First) scheduling

 

 

SPN(Shortest Process Next)

 

• 장점
  • 평균 대기시간(Waiting Time) 최소화
  • 시스템 내 프로세스 수 최소화 (Burst time이 짧은 것을 빠르게 처리하므로)
    • 스케줄링 부하 감소, 메모리 절약 -> 시스템 효율 향상
  • 많은 프로세스들에게 빠른 응답 시간 제공
• 단점
  • Starvation(무한 대기) 현상 발생
    • Burst Time이 긴 프로세스는 자원을 계속 할당 받지 못할 수 있음
      • Aging 등으로 해결 (e.g., HRRN)
    • 정확한 실행시간을 알 수 없음
      • 실행시간 예측 기법이 필요

 

 

맨 처음 P1이 0초에 ready queue에 들어왔을 때 아무도 없으므로 바로 프로세서를 할당받는다. Non-preemptive이므로 3초동안 작업을 수행한다. 따라서 WT = 0초, TT = 3초, NTT = 3 / 3 = 1 이 된다.

 

P1의 작업이 수행되는 동안 P2와 P3가 ready queue에 들어왔다. 이때, P3의 burst time이 더 적으므로 P3가 먼저 프로세서를 할당받는다. 따라서 P3의 WT = 0초(3초에 ready queue에 들어와서 3초에 작업을 시작하므로), TT = 2초, NTT = 2 / 2 = 1 이 된다.

 

P3의 작업이 수행되는 동안 P4가 ready queue에 들어왔다. 이때, ready queue에는 P2와 P4가 들어있는데, P4의 BT가 더 적으므로 P4가 프로세서를 할당받는다. 따라서 P4의 WT = 0초 (5초에 들어와서 5초에 작업 시작), TT = 5초, NTT = 5 / 5 = 1 이 된다.

 

P4의 작업이 수행되는 동안 P5가 ready queue에 들어왔다. 이때, ready queue에는 P2와 P5가 들어있는데, P5의 BT가 더 적으므로 P5가 프로세서를 할당받는다. 따라서 P5의 WT = 4초(6초에 들어와서 10초에 작업 시작), TT = 7초 (4초 + 3초), NTT = 7 / 3 = 2.3 이 된다.

 

마지막으로 P2의 작업이 시작되어서, P2의 WT = 12초(1초에 들어와서 13초에 시작), TT = 19초 (12 + 7), NTT = 19 / 7 = 2.7 이 된다.

 

정리하면 아래 그림과 같다.

 

P2의 경우 1초에 와서 굉장히 초반에 ready queue에 들어왔지만 가장 마지막에 작업을 처리하였다. 이것이 starvation(무한 대기)이다.

 

 

SRTN (Shortest Remaining Time Next) : 남은 실행 시간이 더 적은 것을 먼저 처리하는 스케줄링 기법

 

• SPN의 변형
• Preemptive scheduling (선점 스케줄링 : 누가 와서 내 것을 빼앗을 수 있음)
  • 잔여 실행 시간이 더 적은 프로세스가 ready 상태가 되면 선점됨
• 장점
  • SPN의 장점 극대화
• 단점
  • 프로세스 생성시, 총 실행 시간 예측이 필요함
  • 잔여 실행을 계속 추적해야 함 = overhead
  • Context switching overhead
• 구현 및 사용이 비현실적 (잔여 실행 시간을 계속 알아야 하기 때문)

 

0초

맨처음 P1이 도착했을 때, ready queue에 아무도 없으므로 프로세서를 할당받는다.

 

1초

P2가 ready queue에 들어온다. 하지만 P1(BT : 2초), P2(BT: 7초)를 비교했을 때 P1이 BT가 더 적으므로 P1이 계속 프로세서를 할당받는다.

 

3초

P1의 작업이 모두 끝난다. P3가 ready queue에 들어온다. P2(BT : 7초), P3(BT : 2초)를 비교했을 때, P3가 더 적으므로 P3가 프로세서를 할당받는다.

 

5초

P3의 작업이 끝난다. P4가 ready queue에 들어온다. P2(BT : 7초), P4(BT : 5초)를 비교했을 때, P4가 더 적으므로 P4가 프로세서를 할당받는다.

 

6초

P5가 ready queue에 들어온다. P2(BT : 7초), P4(BT : 4초), P5(BT : 3초)를 비교했을 때, P5가 가장 BT가 작으므로 P5가 프로세서를 할당받는다.

 

9초

P5의 작업이 끝난다. P2(BT : 7초), P4(BT : 4초)를 비교했을 때, P4의 BT가 더 작으므로 P4가 프로세서를 할당받는다.

 

13초

P4의 작업이 끝난다. P2만 남아있으므로 P2가 프로세서를 할당받는다.

 

20초

P2의 작업이 끝난다.

 

정리하면 다음과 같다.

Process ID	Arrival Time	Burst Time	Waiting Time	Turnaround Time	Normalized TT
P1	0	3	0	3	3 / 3 = 1
P2	1	7	12	19	19 / 7 = 2.6
P3	3	2	0	2	2 / 2 = 1
P4	5	5	3	8	8 / 5 = 1.6
P5	6	3	0	3	3 / 3 = 1

 

 

 

 

HRRN (High-Response-Ratio-Next) : 실행시간 대비 얼마나 기다렸는가를 기준으로 우선순위를 매기는 스케줄링 기법

 

• SPN의 변형
  • SPN + Aging concepts, Non-preemptive scheduling
• Aging concepts (Age 즉, 나이가 많은 애를 고려하겠다.)
  • 프로세스의 대기 시간(WT)을 고려하여 기회를 제공
• 스케줄링 기준
  • Response ratio가 높은 프로세스 우선
• Response ratio = (WT+BT) / BT (내가 필요한 시간 대비 얼마나 기다렸느냐)
  • SPN의 장점 + starvation 방지
  • 실행 시간 예측 기법 필요 (overhead)

 

 

0초

P1만 있으므로 WT = 0초, TT = 3초, NTT = 3 / 3 = 1 이 된다.

 

3초

P1의 작업이 끝났다. P1의 작업이 수행되는 동안, P2( (2+7) / 7 = 1.29 )와 P3( 2 / 2 = 1)가 ready queue에 들어왔다. P2의 response ratio가 더 높으므로 P2가 프로세서를 할당받는다. P2의 WT = 2초, TT = 9초, NTT = 9 / 7 = 1.29가 된다.

 

10초

P2의 작업이 끝났다. P2의 작업이 수행되는 동안 P4, P5가 ready queue에 들어왔다. P3( (7+2) / 2 = 4.5), P4( (5+5) / 5 = 2), P5( (4+3) / 3 = 2.3) 중에 P3의 response ratio가 가장 높으므로 P3가 프로세서를 할당받는다. 3초에 들어와서 12초에 작업이 끝나므로 TT = 9초, WT = 7초, NTT = 9 / 2 = 4.5가 된다.

 

12초

P3의 작업이 끝났다. P4( (7 + 5) / 5 = 2.4), P5( (6+3) / 3 = 3) 중에 P5의 response ratio가 더 높으므로 P5가 프로세서를 할당받는다. P5는 6초에 ready queue에 들어와 15초에 작업이 끝나므로, TT = 9초, WT = 9 - 3 = 6초, NTT = 9 / 3 = 3이 된다.

 

15초

P5의 작업이 끝났다. P4가 프로세서를 할당받아 20초에 작업을 끝마친다. P4는 5초에 ready queue에 들어와 20초에 작업이 끝나므로 TT = 15초, WT = 15 - 5 = 10초, NTT = 15 / 5 = 3이 된다.

 

정리하면 아래 그림과 같다.

 

 

 

이전 장에서 배운 FCFS, RR은 Fairness(공평성)을 중점적으로 보는 스케줄링 기법이라면, 이번에 배운 SPN, SRTN, HRRN은 Efficiency와 Performance를 중점적으로 보는 스케줄링 기법이라고 할 수 있다. 성능은 높일 수 있었지만 실행시간을 예측해야 하고, 이것을 정확히 예측하는 것이 힘들다는 문제점이 있다.