[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 등에 따라 다양함