2017年8月20日 星期日

OS - Ch5 排程 CPU Scheduling

於
標籤：
 

FCFS, SJF, RR 介紹，注意不同排程的優缺點；最近多處理器架構也越來越夯啦。
2015.1.15 初版
2017.8.20 二版





一、CPU 排程簡介


OS 用 multiprogramming 方法得到 CPU 最大使用率，一般 process 一開始都是 CPU Burst，交由 CPU 去處理該 process，接著是 I/O Burst，做 I/O 資料的傳送。在正常的狀況下，process 就在這兩個狀態間一直循環，最後會呼叫一個終止行程執行的 system call 作為行程的結束。

CPU scheduling 從在 ready queue 的 process 中挑選 process 進入 CPU 執行。CPU scheduling 選擇的 process 會在以下情況改變 :

  • Switches from running to waiting state. 
  • Switches from running to ready state. e.g. time sharing 因為 time out 回到 ready 
  • Switches from waiting to ready.
  • Terminates 


[注意] Scheduling under only 1 and 4 is nonpreemptive


1. Preemptive vs Cooperative


Preemptive scheduling (當前主流)

  • Higher responsiveness
  • Hard to share resources race conditions
  • Higher overheads

Cooperative scheduling

  • Simpler in design
  • Poor responsiveness
  • Potential hazards


2. Dispatcher


dispatcher 負責將 CPU 控制權交給經由 Short-term scheduler 所挑選出的 process。

下列情況Dispatcher須執行：

  • switching context
  • switching to user mode
  • jumping to the proper location in the user program to restart that program


[注意] Dispatch latency – time it takes for the dispatcher to stop one process and start another running  ( Context-switch overhead )


3. Scheduling Criteria


  • CPU utilization：CPU process exec. / CPU total time，CPU 使用的時間
  • Throughput：單位時間內完成的工作數目
  • Turnaround time：完成時間 (完成-到達)，進去process到出來花的時間
  • Waiting time：waiting in the ready queue
  • Response time：自使用者命令交付到系統產生第一個回應所需的時間 (time-sharing system, user-interactive App 特別重視)


[用心去感覺]

 i. 綠色越大越好，紅色越小越好。
ii. throughput vs waiting time : 雖然一直小的效能好，但一直先做小的，大的會餓死。




二、排程演算法



1. FCFS (First-come,First-served) 排程



就是一般的序列，不可插隊(Non-preemptible)。

  • 優點：很公平
  • 缺點：低 CPU 利用度


護衛效應 (Convoy Effect)

很多 process 均在等待一個需要很長 CPU Time 來完成工作 process，造成平均等待時間大幅增加的不良現象。對 I/O-bound process 有極糟糕的影響，會造成低 I/O 利用度。


2. SJF (Shortest-Job-First) 排程






短任務先做，分可插隊與不可插隊。

  • 優點：short waiting time.
    • SJF (nonpreemptive) : optimal in terms of total waiting time if bursts all ready at 0
    • SRTF (preemptive) : optimal in terms of total waiting time if jobs'arrival times are arbitrary
  • 缺點：Not fair, starvation issue (low priority processes may never execute)
    • Solution：Aging – as time progresses increase the priority of the process


Determining Length of Next CPU Burst

 It is hard to know the precise length of a CPU burst in advance.

  • $t_n = $ 上一次預估的 CPU Burst Time
  • $\tau_{n} = $ 上一次實際的 CPU Burst Time
  • $\tau_{n+1} = $ 此次預估的 CPU Burst Time
  • $\alpha = $ 分配比率，常用 $\alpha = \frac{1}{2}$



3. RR (Round Robin) 排程




知更鳥式循環排程法，分時系統所使用的排程法。

  • 優點：
    • No process waits more than (n-1)q time units. 
    • better response (Users feel that processes run "smoothly slow")
  • Performance：
    • q large：FIFO 
    • q small：q must be large with respect to context switch, otherwise overhead is too high 
    • Better response <— (小) Time quantum (大) —> better turnaround time 


4. Multi-level queue


Ready queue is partitioned into separate queues. Each queue has its own scheduling algorithm. e.g.

  • foreground (interactive) – RR
  • background (batch) – FCFS


5. Multi-level feedback queue


A process can move between the various queues. Aging can be implemented this way.

e.g. Three queues :

  • Q0 – RR with time quantum 8 milliseconds (If not finish, moved to  next queue.)
  • Q1 – RR time quantum 16 milliseconds
  • Q2 – FCFS



[用心去感覺] I/O-bound and CPU-bound proces in m-queue

Why do we prefer I/O-bound processes?

  • To improve I/O utilization (vs the convoy effect of FCFS)
  • To improve the responsiveness (in favor of interactive processes)

Why CPU processes are given to larger time quantum?

  • To improve the throughput / turnaround.




三、Multiple-Processor Scheduling (處理器之間)


Processor affinity : Processor affinity takes advantage of the fact that remnants of a process that was run on a given processor may remain in that processor's state (for example, data in the cache memory) after another process was run on that processor.

load balancing :

  • Push migration – push a process away from a heavily loaded processor to an idle processor
  • Pull migration – pull a waiting process from a heavily loaded processor into an idle processor


[感覺] The two issues conflict with each other!




References


Scheduling, Part 2: Scheduling Processes: Algorithms
http://cs241.cs.illinois.edu/scheduling-part-2-scheduling-processes-algorithms.html

Abraham Silberschatz, Peter B. Galvin, Greg Gagne - Operating System Concepts 8th Edition
https://www.amazon.com/Operating-System-Concepts-Abraham-Silberschatz/dp/0470128720

聯合大學陳士杰教授課程教材
http://web.nuu.edu.tw/~sjchen/

洪逸 - 作業系統金寶典
http://m.sanmin.com.tw/product/index/001601057
技術提供：Blogger.
 
© 2023 Mr. Opengate