[OS] 5-3. 프로세스 스케줄링 알고리즘 - SPN, SRTN, HRRN

목차

1. 스케줄링의 목적
2. 스케줄링 기준 및 단계
3. 스케줄링 정책
4. 기본 스케줄링 알고리즘들
5. Case study

Basic Scheduling algorithms

공평성을 고려한 방식

• FCFS (First Come First Service)
• RR (Round Robin)

효율성을 고려한 방식

• SPN (Shortest Process Next)
• SRTN (Shortest Remaining Time Next)
• HRRN (High Response Ratio Next)

BT예측문제를 개선한 방식

• MLQ (Multi level Queue)
• MFQ (Multi level Feedback Queue)

---

SPN (Shortest Process Next)

FCFS에서 실행시간이 긴 프로세스로 인해 짧은 시간의 프로세스들이 오랜 시간을 기다려야하는 문제를 해결하기 위한 방법

• Non preemptive scheduling
• 스케줄링 기준 (Criteria)
  • 실행시간 (burst time 기준)
  • Burst time 가장 작은 프로세스를 먼저 처리

SJF(Shortest Job First) scheduling

마트에서의 긴 대기열

장점

• 평균 대기시간 (WT) 최소화
• 시스템 내 프로세스 수 최소화
  
  • 스케줄링 부하 감소, 메모리 절약 => 시스템 효율 향상
• 많은 프로세스들에게 빠른 응답 시간 제공

단점

• Starvation (무한대기) 현상 발생
  • BT가 긴 프로세스는 자원을 할당 받지 못 할 수 있음
  • BT가 3인 프로세스가 먼저 도착했더라도 이보다 BT가 짧은 P2,P3,P4...가 계속 온다면 양보해 줘야 하는 문제점 발생
    • Aging 등으로 해결 (e.g., HRRN)
• 정확한 실행시간을 알 수 없음 (BT시간..)
  • 실행시간 예측 기법이 필요

Column1	Column2	Column3	Column4	Column5	Column6
Process ID	Arrival time	Burst time (BT)	Waiting time (WT) = TT-BT	Turnaround time (TT)	Normalized TT (NTT) = TT/BT
P1	0	3	0	3	3/3 = 1
P2	1	7	12	19	19/7 = 2.7
P3	3	2	0	2	2/2 = 1
P4	5	5	0	5	5/5 = 1
P5	6	3	4	7	7/3 = 2.3

 

SRTN (Shortest Remaining Time Next)

남은시간이 가장 적은 프로세스를 먼저 스케줄링하는 방식

• SPN을 변형한 기법
• Preemptive scheduling (선점형) : 잔여시간이 적은 프로세스가 CPU점유
• 잔여 실행 시간이 더 적은 프로세스가 ready 상태가 되면 선점됨

장점

• SPN 의 장점 극대화 (WT 최소화)

단점

• 프로세스 생성시, 총 실행 시간 예측이 필요함
• BT예측이 어려움
• 잔여 실행을 계속 추적해야 함 = overhead 발생
• Context switching overhead

=>구현 및 사용이 비현실적

 

HRRN (High Response Ratio Next)

SPN 의 변형중 현실적인 기법 (SPN의 문제점 (기아현상))

SPN + Aging concepts, Non preemptive scheduling

Aging concepts

프로세스의 대기 시간 (WT) 을 고려하여 기회를 제공

스케줄링 기준

Response ratio 가 높은 프로세스 우선

𝑹𝒆𝒔𝒑𝒐𝒏𝒔𝒆𝒓𝒂𝒕𝒊𝒐 (응답률) = ( 𝑾𝑻 + 𝑩𝑻 ) / 𝑩𝑻 (BT대비 WT를 얼마나 소비했는가를 수직적으로 나타냄)

• SPN 의 장점 + Starvation 방지
• 실행 시간 예측 기법 필요 (오버헤드발생)

Process ID	Arrival time	Burst time (BT)	Waiting time (WT) = TT-BT	Turnaround time (TT)	Normalized TT (NTT) = TT/BT
P1	0	3	0	3	3/3 = 1
P2	1	7	2	9	9/7 = 1.29
P3	3	2	7	9	9/2 = 4.5
P4	5	5	10	15	15/5 = 3
P5	6	3	6	9	9/3 = 3

 

 

---

본 포스트는 KOREATECH의 HPC LAB. Duksu Kim 교수님 OS강의를 기반으로 정리한 내용입니다.

상업적 의도가 아닌 공부한 것을 정리해 놓은 목적으로 게시한 포스트입니다. 

아래의 출처에서 자세한 내용을 수강하실 수 있습니다.

https://www.youtube.com/playlist?list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN

---