[OS] Lecture 5. Process Scheduling (3/4) - SPN, SRTN, HRRN

SPN(Shorest Process Next)= burst time이 가장 작은 프로세스 먼저 처리하자!

- Non-preemptive scheduling. 자원 뺏길 수 X

- 스케줄링 기준: burst time

- burst time이 가장 작은 프로세스 먼저 처리

- SJF(Shortest Job First) scheduling

- ex) 소량 상품 전용 계산대

 

장점:

- 평균 대기시간(WT) 최소

- 시스템 내 프로세스 수 최소화 

- 스케줄링 부하 감소. 메모리 감소-> 효율 향상

- 많은 프로세스 빠른 응답 시간 제공

 

단점: 

- starvation(기아) 현상 발생= 무한대기

- BT가 긴 프로세스는 자원을 할당 받지 못 할 수 있음(Aging으로 해결. HRRN) 

- 정확한 실행시간 알 수 없음. BT 예측 기법 필요

---

SRTN(Shortest Remaining Time Next)= 남은 시간 적은 프로세스 먼저!

- SPN 변형

- preemtive scheduling. 잔여 실행 시간이 더 적은 프로세스가 ready 상태가 되면 선점 됨.

- 장점: SPN 극대화(평균 대기시간 최소화, 시스템 내 프로세스 최소화)

- 단점: 

1. 프로세스 생성 시, BT 예측 필요

2. 잔여 실행 시간 추적 필요-> overhead

3. context switching overhead

4. 구현 비현실적

---

HRRN(High Response Ratio Next) 

- SPN 변형 

- Non-preemptive scheduling

- Aging concepts: 프로세스 대기시간(WT)을 고려하여 기회 제공

- 스케줄링 기준: Response ratio(응답률)  가 높은 프로세스 우선

- Response ratio=(WT+BT)/BT= TT/BT =필요한  BT 대비 얼마나 기다렸는가. 클 수록 대기시간이 길다.

- SPN의 장점+ starvation 방지

- BT 예측 기법 필요-> overhead

---

목적: Fairness(공평성) 

- FCFS(First Come First Service) 

- RR(Round Robin)

 

목적: Efficiency/Performance

- SPN(Shortest Process Next)

- SRTN(Shortest Remaining Time Next) 

- HRRN(High Response Ratio Next)

- 문제점: BT 예측 overhead

- 대안: MLQ, MFQ