排程的四種演算法

FCFS

  • 先來先做
  • Convoy effect

    • 很多短時間的 Process,都在等一個長時間的 Process 時,所產生的效應

Priority Scheduling

  • 號碼牌 (Priority) + FCFS
  • Starvation

    • 解決方法:Aging → 將等待了長時間的 Process 的優先權提高

SJF

選擇執行當前 Process 裡 Burst Time 最小者。

  • Non-preemptive SJF:不會被插隊
  • Preemptive SJF:可以插隊,又稱 Shortest-remaining-time-first

RR

  • q + FCFS
  • 公平輪流

    • q 太大:等於 FCFS
    • q 太小:Context Switch 過多

Multilevel Queue

  • 把 Ready Queue 分成兩種 queue

    • Foreground queue

      • 需交談
      • I/O Bound Process
      • FCFS
    • Background queue

      • 需批次處理
      • RR
  • 缺點:有些 process 可能做上面的演算法比較好,但是不能上去做

Multilevel Feedback Queue

  • 允許 Process 在 queue 之間移動,是一種 Aging 技術的形式
  • 比起 Multilevel Queue,可以互相連通,較靈活

硬體多工

Muti-processor

  • Asymmetric multiprocessing

    • 非對稱式
    • 其中一個 CPU 主導排程分配
  • Symmetric multiprocessing

    • SMP
    • 每一個 Process 自己來做 Scheduling
    • 現在電腦大多都是 SMP 架構

Multicore Processors

多顆 CPU 封裝成一顆,比 Muti-processor 更快更省電。

SMP 架構中,CPU 的溝通問題

溝通問題:NUMA

local/remote data access 時間不一致的現象。

解決方法:Process affinity

盡量安排所有東西都在同一個 processor 上做,盡量減少跨部門動作。

  • 硬性 hard affinity:強迫安排
  • 軟性 soft affinity:盡量安排

但是這樣處理的結果,導致某些 CPU 閒置 (idle) 或 Overload!

再次解決:Load balancing

  • Push migration:Loading 太重的 processor 丟掉工作
  • Pull migration:閒置的 processor 去其他 CPU 拿工作

Real-Time System

保證每個 Process 可以被即時執行,不會有很長的等待時間,且能夠在 Deadline 前完成任務。

一般 Real-Time System 分成兩類:

  • Soft Real-Time System:盡量達到即時(影片播放器)
  • Hard Real-Time System:不允許延遲(煞車系統、安全氣囊)

Real-Time Scheduling

Rate Montonic Scheduling

  • 一般 Real time 中最常使用到的演算法
  • 類似 SJF,Process 的週期 (Period time) 愈短者,優先權 (Priority) 愈高
  • 缺點是可能會超出 Deadline

Earliest Deadline First Scheduling (EDF)

  • 上述 Rate Montonic Scheduling 的改善方式
  • 愈接近 Deadline 的 Process 給予愈高的優先權 (Priority)

Proportional Share Scheduling

  • 比較注重公平性
  • 類似 RR 演算法
  • 平均分配固定的區隔時間

例如:當前總共 CPU 時間是 T,共有 N 個 process 要分享 (N < T),則每個 process 輪流做 N/T 的時間。

評估最合適的演算法

Deterministic Modeling

每個演算法都給一個固定的工作量去做,看哪個花得時間最少。

Queuing Model

使用 Little Formula 的統計結果來評估。

Simulation

模擬當時的環境情況,並隨機產生數據去測試。

Implementation

全部拿去實際操作,但非常耗時、耗資源。

以上資源是我自己整理過後的筆記,若有錯誤歡迎隨時和我聯繫