1. Basic Concepts

Resource Scheduling

Multiprogramming에 의해 여러개의 process가 동시에 memory에 load될 수 있다. 이 process들은 CPU time, disk space 등의 shared resource를 이용한다.
→ Who gets it next? How long can they keep it?

CPU Burst

OS는 code execution과 I/O operation을 번갈아가면서 CPU-I/O burst cycle을 돈다. CPU burst가 CPU scheduling의 entity가 된다.

CPU Scheduler

Process의 state인 Ready, Running, Waiting마다 queue를 가지게 된다. Running → Ready, Running → Waiting, Waiting → Ready, Terminates 네 가지 transition이 일어날때 scheduling이 필요하다.

2. Scheduling Policies

Objective

• Maximize Resource utilization
• Minimize context switches & overhead
• Distribute cpu cycles fairly

Metrics

• Throughput : 시간당 수행하는 프로셋의 개수
• Turnaround time : 특정 process를 수행하는 데에 걸리는 시간
• Waiting Time : Ready queue에서 기다리는 시간
• Response time : Request 후 첫번째 응담까지 걸리는 시간

Policies

1. First In First Out

• Convoy Effect : 시간이 오래 걸리는 process가 먼저 도착할 경우, 효율이 떨어진다.

2. Shortest Job First

• Preemptive vs Nonpreemptive
  새로운 process가 중간에 도착하였을 때, burst time이 더 작다면 preemptive하게 switch된다.
• optimal하나 특정 Job이 얼마나 걸릴지 알 수 없다.
  • Exponential moving average와 같은 방법으로 predict한다. $\tau_{n+1} = \alpha t_n + (1-\alpha)\tau_n$

3. Round Robin

• FIFO의 non-preemptive하다는 문제를 해결하기 위해 timer를 달아 one time slice가 지나면 switch한다.
• RR vs FIFO? process간 burst의 차이가 클수록 RR이 효율적이다.
• 적당한 time slice의 크기를 정하는 것이 중요하다. 너무 길다면 monopolize한다는 문제가 생기고 너무 작다면 context switch overhead가 커진다. 주로 1~10ms를 선택한다.
• I/O intensive process의 경우, time slice가 작을때 I/O utilization이 더 높고 response time도 줄어든다. CPU intensive process의 경우, time slice가 작을 경우 overhead가 커져 클 때가 더욱 효율적이다.
  → 어떤 process냐에 따라 적절한 time slice의 크기가 달라진다.

4. Multi-level Feedback Queue

• Priority에 따라 서로 다른 runqueue를 가지고 다른 크기의 time slice를 가진다.
• new process는 I/O intensive하다고 가정하고 높은 priority에 넣고, time slice가 끝나기 전에 blocking되지 않는다면 우선순위를 증가시킨다.
  

3. Fair Share Scheduling of Linux

Fair Share Scheduling

각 process의 weight을 정하고, weight에 비례하도록 cpu time을 분배한다. 이때 time은 descrete하여 불가피한 unfairness가 생긴다.
아래 식을 만족할때 perfectly fair하다.

Measurement - CPU time lag

실제로 받은 CPU time과 ideal할 경우 받았어야 하는 CPU time의 차를 minimize한다.

Policies

1. Generalized Processor Sharing

시간을 inifinitesimally small time으로 쪼개어 scheduling한다. ideal한 case이다.
시간은 descrete하기 때문에 이처럼 분배하는 것은 불가능하고 timer interrupt overhead가 발생한다.

2. Weighted Round Robin (WRR)

Round robin interval period를 time slice로 쪼개어 weight에 비례하도록 각 task가 CPU time을 나누어 가진다.
scheduling overhead는 O(1)으로 작으나, weight이 커질수록 lag가 커져 fairness가 weak하다.

3. Weighted Fair Queueing (WFQ)

Virtual time (VT)은 CPU을 받은 physical time을 weight로 나눈 값으로, weight에 대해 얼만큼의 시간을 받았는지를 의미한다. 1 tick period 후의 VT인 Virtual finish time을 기준으로 run queue를 sort한다.
sorting을 해야하기 떄문에 scheduling overhaed가 O(n)/O(logn)으로 크다. Strong fairness가 보장된다.

4. Completely Fair Scheduler (CFS)

• Con Kolivas's RSDL vs Ingo Molna's CFS
• weight에 비례하여 cpu time을 가지는 WRR + virtual runtime을 기준으로 sorting하는 WFQ
• 각 CPU는 각각의 run queue를 가진다.
• red-black tree로 sort

Summary