Operating Systems - CH5 CPU Schedling

CPU-I/O Burst Cycle

process execution包含 CPU execution 和 I/O wait

CPU Scheduler = short-term scheduler

• 從ready queue 裡 挑出process給CPU執行
• CPU Sceduling decision 發生當
  • 從running 到 wait
  • terminated
  • 從 wait 到 ready (preemptive)
  • 從running 到 ready (preemptive)

Dispatcher

• 將CPU的控制權授予經由short-term scheduler選擇的process
• 會做以下工作
  • context switching
  • 從 monitor mode 跳到 user mode
  • 跳到 user program 裡的執行位置 來restart program
• dispatch latency
  • 上述三項工作總和，即停止process並開始另一process的時間

Scheduling algorothm optimization Criteria

• max CPU utiliztion
• max throughput: 讓整體可以服務的process越多越好
• min turnaround time: 執行process時間越短越好
• min waiting time
• min response time

FCFS Scehduling

Convoy effect: short process 在 long process之後

Short-Job-First Scheduling

困難在於要知道下一個 CPU request的長度, could ask the user

Shortest-remaining-time-first

預測他們後來抵達時間，挑選最短的做，會preemptive

Priority Scheduling

• 加上一個priority number 給each process
• 可能造成 Starvation
• 解決辦法
  • Aging: 當process停留一段時間後，我們會提高它的priority，避免starvation

Round Robin(RR)

• 每個process給一段cpu time( time quantum q )
•  performance
  • q large -> 等於是FIFO
  • q small -> 必須大於context switch time，不然會一直造成context swotch
• 有比較高的turn around time，但是有比較好的response time

Multilevel Queue

1. Def：
   1. 將單一  一層的ready queue進一步分成許多不同優先權等級的ready queue
   2. 前面的是interactive (RR)， 後面是BATCH (FCFS)
   3. Queue與Queue之間的排班是採取preemptive priority法則居多
   4. 每個Queue中可有自己的排班法則，如：RR, FCFS, ...
   5. 不允許process在各個queue中移動
2. 特點：
   1. 增加排程的flexibility
   2. Unfair
   3. Preemptive
   4. 會有starvation

Multilevel feedback queue

1. Def：
   與Multilevel Queue類似(1,2,3相同)
   差別在於"允許process在各個queue之間移動"，以防止starvation情況
2. 作法：
   1. 採取類似"Aging"技術，每隔一段時間，將各process往上提升到上一層Queue中
      ∴在經過有限時間後，在Lowest priority queue中的process會被至於Highest priority queue中
   2. 亦可配合"降級"之動作
      當上層queue中的process取得CPU後，若未能在quantum內完成工作，則此process在放棄CPU後，會被置於比較下層的Queue中
3. 特點：
   1. Preemptive
   2. Unfair
   3. No starvation
   4. 設計上最為複雜
4. RR包含於Multilevel(Feedback) Queue
   (通常，越上層的Queue，其Quantum較小，越下層越大)

Summary

1. Fair：
   1. FCFS
   2. RR
2. No starvation：
   1. FCFS
   2. RR
   3. Multilevel Feedback Queue
3. Non-preemptive：
   1. FCFS
   2. SJF
   3. Non-preemptive priority
4. Preemptive
   1. SRJF
   2. Preemptive Priority
   3. RR
   4. Multilevel Queue
   5. Multilevel Feedback Queue

• 公平，可插隊，不會餓死的 RR

Thread scheduling

• 不只process需要排程，thread也需要
• 如果在Many-to-one 和many-to-many model，user-level thread就必須經過Scheduling，scheduling competition within process,這個過程稱為process-contention scope (PCS), 通常會給priority
• 另外一個是由Kernel thread 來schedule，要跟所有thread競爭， 被稱為system-contention scope (SCS)由系統來做

Multiple-Processor Scheduling

• Asymmetric multiprocessing(非對稱式) 其中一個CPU來主導他可以存取的，Data-sharing也是由他負責，所以稱為非對稱。
• Symmetric multiprocessing (SMP)(對稱式的) 每一個process自己來做Scheduling
• Processor affinity 盡量讓process在同一個CPU執行
  • hard affinity 強制性，強制不能轉移
  • soft affinity

Sun Solaris

• priority-based scheduling

Windows

• priority-based preemptive scheduling

Little's law: 離開queue的process 一定要跟進來queue的process 一樣多

Simulations: 模擬，時間可以變動

Emulation: 真實模擬，時間是真實的，仿真

參考資料：

1.  http://wayne.cif.takming.edu.tw/os/os_5.pdf
2.  http://www.csie.ntnu.edu.tw/~swanky/os/chap4.htm
3.  http://sls.weco.net/node/21325