[OS] Processor Scheduling
Terminology
- CPU Burst: CPU to execute Time
- I/O Burst: wait for I/O Time
Type of scheduling
1. Long-term scheduling
- 디스크에 있는 프로세스 중 어느 프로세스를 메모리로 적재할지 결정
2. Medium-term scheduling
- multiprogramming을 관리하는 경우
- 어떤 프로세스를 디스크로 swap할지 결정
3. Short-term scheduling
- 메모리에 있는 프로세스 중 어느 프로세스를 수행할지 결정
Scheduling Criteria
- system oriented: throughput, processor utilization, fairness, fair-share
- user oreinted: turnaround time, response time, deadline
Selection Function
w: time spent in system; 지금까지 시스템에서 기다리는데 걸린 시간 -> 대기 시간
e: time spent in execution; 지금까지 실행하는데 걸린 시간 -> 실행 시간
s: total service time required including e; 요구되는 실제 서비스 시간 -> 구현 힒듬
Decision Mode
- Non-preemptive: 비선점모드
- Preemptive: 선점모드; more process switch -> more overhead
FIFO
- selection Function: max[w], FIFO에서는 constant
- Decision Mode: Non-preemptive
- 특징
1) 구현의 단순함
2) 기아 발생 X
3) long process에게는 적합
Convoy Effect
: long에 막혀 short process 수행이 진행되지 않는 현상
Shortest Process Next (SPN)
- selection Function: min[s]
- Decision Mode: Non-preemptive
- 특징
1) TAT 관점에서는 좋아짐
2) 기아 문제 발생
3) service time 예측이 어려움 -> 구현이 어려움
FIFO vs SPN
-> 수행시간 (service time)이 비슷하다면 service time 예측에 필요한 비용이 존재하므로 항상 SPN이 좋다고 말할 수 없다.
Shortest Remaining Time (SRT)
- selection Function: min[s - e]
- Decision Mode: preemptive
- 특징
1) TAT 관점 optimal
2) process switch에 의해 overhead 발생
3) 기아 문제 발생
4) service time 예측이 어려움 -> 구현이 어려움
Highest Response Ratio Next (HRRN)
- selection Function: max[1 + w/s]
- Decision Mode: Non-preemptive
- 특징
1) short process 우대
2) 기아 발생을 막는 용도
Round-Robin
- selection Function: constant
- Decision Mode: preemptive
- 특징
1) FIFO의 convoy effect를 해결하기 위함
2) preempt 되기 전 time slice를 부여 받음
3) n개의 프로세스, q의 time slice가 있다면, (n - 1)q의 시간을 넘지 않음
4) long process 우세 -> long은 부여받은 time slice 모두 소진, short는 반
- shorter time slice
1) better response time
2) q가 작을수록 process switch overhead 증가
-> SPN
- longer time slice
1) worse response time
2) overhead 감소
-> FIFO
Virtual Round Robin (VRR)
- 특징
1) short process에게 이점을 주는 방식
2) 레디 큐보다 보조큐에 우선순위를 둠
-> time slice에 못 쓴 시간에 대한 균형을 맞
Multi-Level Feedback Queues
-특징
1) 여러개의 queue를 설정
2) time slice를 모두 소진 -> long이라는 의미 -> 강등시킴
3) time slice를 2배씩 증가 -> 마지막은 FIFO로 진행
4) 기아 문제 발생 -> promotion을 시킴 -> HRRN에서 사용된 waiting time을 이용하여 승급
5) 큐의 개수, time slice 등에 따라 다양함