changed 4 years ago  
Published Linked with GitHub

OS筆記-Chapter 5: CPU Scheduling

tags: OS

目錄

基本觀念

  • 在單一處理器系統裡，同一時間只能有一個行程在執行，多元程式規劃(multiprogramming)的目的就是隨時保有一個行程在執行

  • 行程是由CPU執行時間及I/O等待時間所組成的週期(cycle)

    • CPU分割(CPU burst)
    • I/O分割(I/O burst)

  • CPU分割統計，一般都為指數或超指數型，這個分布方式對於選取一個適當的CPU排班演算法來說是一項非常重要的資料

  • 短程排班程式/CPU排班程式(short-term scheduler):自記憶體中準備要執行的行程中選出一個，將CPU配置給它

  • CPU排班的決策發生在下面四種狀況

    1. 當一行程從執行狀態轉變成等待狀態時(I/O要求或wait())
    2. 當一行程從執行狀態轉變成就緒狀態時(interrupt)
    3. 當一行程從等待狀態轉變成就緒狀態時(I/O結束)
    4. 當一行程終止時

  • 上述四種狀況為不可搶先(nonpreemptive)/合作(cooperative)

    • 一旦CPU配置給一個行程，此行程將保有CPU，直到中止或轉換到等待狀態

  • 可搶先排班(preemptive)

    • 在存取共用資料時可能造成競爭情況(race condition)，搶先的行程與原行程的資料不一致
    • 當核心在處理系統呼叫時很可能要修改一些重要的資料結構，如果這個時候搶先的行程修改了相同的核心資料結構，這樣很可能造成系統當機。
    • 一般來說，作業系統需要能夠隨時接收中斷，但為了解決上述問題，當系統進入系統呼叫後，就將系統中斷關閉，結束系統呼叫時，再將中斷開啟，以確保核心資料結構的一致性

  • 分派程式(dispatcher)

    • 將CPU控制權交給短程排班程式所選出的行程的模組
      • 轉換內容
      • 轉換成使用者模式
      • 跳躍到使用者程式的適當位置以便重新開始程式
    • 分派潛伏期(Dispatch latency):分派程式用來停止一個行程並開始另一個行程所用的時間

排班原則(Scheduling Criteria)

  • CPU使用率(CPU utilization):使CPU盡可能的忙碌

  • 產量(Throughput):單位時間內所完成的數量

  • 回復時間(Turnaround time):行程完成所花費的時間，包括:進入等待記憶體、就緒佇列等待、CPU執行、I/O等等

  • 等候時間(waiting time):在就緒佇列等待的時間

  • 反應時間(response time):提出一個要求到第一個反應的時間

  • 最佳化

    • Max CPU utilization
    • Max throughput
    • Min turnaround time
    • Min waiting time
    • Min response time

排班演算法(Scheduling Algorithm)

  • 先來先做(FCFS,First-Come First-Served):

    • 使用先進先出佇列(FIFO,First-in First-Out)
    • 平均等待時間長
    • P1先，平均等待時間:(0+24+27)/3=17
    • P1最後，平均等待時間:(3+6)/3=3
    • 護送現象(convoy effect):所有行程都在等一個大行程離開CPU，造成CPU和裝置使用率降低
    • 不可搶先

  • 最短工作先做(SJF,Shortest-Job-First)

    • 可以得到一組行程的最小平均等待時間(3+9+16)/4=7
    • 難以得知下一個CPU要求的長度(難以找到最短的)
    • 預測下一個CPU要求的長度
      • 下個CPU分割的預估通常是根據前幾次CPU分割所測得的值之指數平均值(exponential average)
    • τ₀=10、α=1/2
    • 可搶先或不可搶先
    • 可搶先稱為生於時間最短的先做(shortest-remaining-time-first)

  • 優先權排班(Priority Scheduling)

    • 可搶先或不可搶先
    • 無限期阻塞/飢餓(indefinite blocking/starvation):優先權低的行程一直等待CPU
    • 老化(aging):一段時間，調高等待行程的優先權

  • 依序循環(RR,Round Robin)

    • 為了分時系統所設計
    • 可搶先，行程交互使用CPU
    • 時間量/時間片段(time quantum/time slice):定義一個小的時間單位
    • 平均等待時間較長
    • 除非只有一個行程，不然不會有一個行程分配CPU的時間超過時間量
    • 時間量:q=4，(10-4)+(4)+(7)/3=5.66

    • 時間量極大時，等同於FCFS。時間量極小時，造成內容轉換的負擔
    • 通常CPU分割的80%應該小於時間量
    • 回復時間不因時間量增加有所改進

  • 多層佇列(Multilevel Queue)

    • 分成多層佇列，每層佇列分別使用自己的排班法則
    • 每層之間不能轉移
    • 分層之間:
      • 除非前面都空了，後面才能分配CPU
      • 或分配80%的CPU時間給前面的佇列，20%給後面

  • 多層回饋佇列(Multilevel Feedback Queue)

    • 允許行程在分層之間移動
    • 第一層執行不完的就放到第二層，第二層執行不完的就放到第三層
    • 較長的行程會自動放到較底層
    • 隨著時間，較底層的，也會漸漸地移往高優先序，以免飢餓
    • 最通用的CPU排班演算法
    • 最複雜的CPU排班演算法

演算法評估(Algorithm Evaluation)

  • 分析式評估(analytic evaluation):使用所給予演算法和系統工作量產生一個公式或數字，以此評估性能

  • 定量模式(deterministic modeling):一種分析式評估，取一個特定的工作量，並針對每種演算法評估效能

    • 例如:
      • FCFS:(10+39+42+49)/5=28
      • SJF:(3+10+20+32)/5=13
      • RR:((10+20+2)+(20)+(23)+(30+10))/5=23

  • 佇列模式(Queueing Models)

    • 定出CPU和I/O分割的分布情況
    • 指數型分布
    • 可計算出平均產量、利用率、等待時間等等
    • Little’s Formula:n=λxW
      • 平均佇列長度n
      • 新行程平均到達比率λ
      • 平均等待時間W

  • 模擬(Simulations)

    • 更準確的評估

  • 實做(Implementation)

    • 即使是模擬精確度也有限
    • 將程式碼直接放入系統評估工作情形
    • 困難:
      • 代價高(撰寫程式碼等等)
      • 環境不一樣
Select a repo