CS/OS

5. 프로세스 스케줄링 (3)

🥭맹2 2021. 5. 10. 21:58

현 포스팅에서는 3, 4, 5인 SPN, SRTN, HRRN을 다룹니다

Basic Scheduling algorithms

Shortest-Process-Next

ex 소량 계산대

실행 시간 (burst time)이 가장 작은 프로세스를 먼저 처리
FCFS의 문제점 : ready-queue 도착 기준으로 프로세서를 할당하기 때문에 뒤에 존재하는 프로세스의 burst time(실행 시간)이 짧더라도, 앞의 프로세스가 끝날 때까지 기다려야함.
Non-preemptive scheduling : 한 번 할당 받으면 한 번에 끝냄
스케줄링 기준(Criteria)
- 실행시간 (burst time 기준)
- burst time이 가장 작은 프로세스를 먼저 처리
  - SJF(Shortest Job First) scheduling
장점
- 평균 대기시간(WT) 최소화
- 시스템 내 프로세스 수 최소화 : 짧은 거 먼저 빨리 끝내니까
  - 스케줄링 부하 감소 : 짧은 거 먼저 빨리 끝내니까
  - 메모리 절약 : 짧은 거 먼저 빨리 끝내니까
  - 스케줄링 부하 감소, 메모리 절약이 되므로 - > 시스템 효율이 향상됨
- 많은 프로세스들에게 빠른 응답 시간을 제공해줌
단점
- Starvation (무한 대기) 현상 발생
  - BT가 긴 프로세스는 자원을 할당 받지 못할 수 있음
- 정확한 실행시간을 알 수 없음
  - BT를 기준으로 할당 기준을 정하는데, 각 프로세스의 정확한 BT를 아는 것이 불가능하므로, 실행 시간 예측 기법이 필요함

P2에 기아현상(starvation) 발생

Shortest Remaining Time Next

남은 시간을 기준으로 프로세서 할당
SPN을 변형 한 것
Preemptive scheduling
- 잔여 실행 시간이 더 적은 프로세스가 ready 상태가 되면 선점됨
장점
- SPN의 장점 극대화
  - SPN의 장점
    1. 평균 대기 시간 최소화
    2. 시스템 내 프로세스 수 최소화
단점
- 프로세스 생성 시, 총 실행시간(Burst time) 예측이 필요함
- 잔여 실행 시간을 계속 추적해야 함 => overhead
- preemptive scheduling이므로 context switching overhead발생
구현 및 사용이 비현실적임
- 이유
  1. 정확한 BT를 아는 것이 어려움
  2. 잔여 실행 시간을 계속 추적하는 것이 현실적으로 어려움

High-Response-Ratio-Next

SPN에 Aging concepts를 추가한 알고리즘
- SPN의 문제인 starvation을 해결하기 위한 방법 : aging concepts
SPN과 동일하게 Non-preemptive scheduling
스케줄링 기준 (Criteria)
- Response ratio가 높은 프로세스 우선
장점 : SPN의 장점 + starvation 방지
- SPN의 장점 : 평균 대기 시간 최소화, 시스템 내 프로세스 수 최소화
단점
- 실행 시간(BT) 예측 기법 필요함
  - 실행 시간을 예측함에 따라 overhead가 발생

-> 필요한 BT(실행 시간) 대비 얼마나 기다렸는지 == response ratio

FCFS, RR은 먼저 ready-queue에 들어온 것을 먼저 처리하기 때문에 공평하다
SPN, SRTN, HRRN은 시스템의 효율성과 성능을 높여준다.
- 하지만, 실행시간을 예측하는데에 있어서 overhead(부하)가 발생하는 것
- 또한, 실행 시간을 예측하는 것이 힘들고, 정확하지 않다.
- 이러한 문제를 해결해 준 것이 MLQ, MFQ임 -> 다음 포스팅으로 고고~!