作業系統 - 學習筆記 (4) 排程

發表於 分類於

本文介紹作業系統「排程」的基礎概念，主要是在講四種演算法：FCFS、Priority Scheduling、SJF、RR，並說明各演算法延伸出的概念。

排程的四種演算法

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

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

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