[CS] Process Scheduler #3

이 포스팅은 한국기술교육대학교 김덕수 교수님의 운영체제 강의를 참고하여 작성되었습니다.

 

기본 스케줄링 알고리즘

• FCFS (First-Come-First-Service)
• RR (Round-Robin)
• SPN (Shortest-Process-Next)
• SRTN (Shortest Remaining Time Next)
• HRRN (High-Response-Ratio-Next)
• MLQ (Multi-level Queue)
• MFQ (Multi-level Feedback Queue)

 

SRN (Shortest-Process-Next)

Non-preemptive scheduling

스케줄링 기준 : 실행시간 (burst time 기준), Burst time 가장 작은 프로세스를 먼저 처리

"소량 상품 계산대"

 

장점

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

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

스케줄링 부하 감소, 메모리 절약 > 시스템 효율 향상

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

단점

- Starvation (무한대기) 현상 발생

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

- 정확한 실행시간을 알 수 없음

실행시간 예측 기법이 필요 > Terminate 상태에 수집된 정보들로 예측하지만 정확하지 않다

 

김덕수 교수님의 운영체제 강의 자료 中

위 그림에서 P2에게 기아현상Starvation이 발생한다.

 

SRTN (Shortest Remaining Time Next)

SPN의 변형

Preemptive scheduling

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

장점

- SPN의 장점 극대화

단점

- 프로세스 생성시, 총 실행 시간 예측이 필요함

- 잔여 실행을 계속 추적해야 함 = overhead

- Context switching overhead

 

구현 및 사용이 비현실적이다.

 

HRRN (High-Response-Ratio-Next)

SPN의 변형 "SPN의 문제 기아현상을 피하기 위해"

- SPN + Aging concepts, Non-preemptive scheduling

Aging concepts

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

스케줄링 기준

- Response ratio가 높은 프로세스 우선

Response ratio = (WT + BT) / BT  "응답률, BT대비 얼마나 기다렸는가"

- SPN의 장점 + Starvation 방지

- 실행 시간 예측 기법 필요 (overhead)

김덕수 교수님의 운영 체제 강의자료 中

 

Basic Scheduling algorithms

김덕수 교수님의 운영 체제 강의자료 中

 

 

긴 글 읽어주셔서 감사드립니다.

22.12.16