CPU調(diào)度

原文地址： https://qjm253.cn/2018/06/29/os_03/

CPU調(diào)度的基本概念

  • 主要目標：使CPU的利用率最大化（也是多道程序設計的目標）

  • 并行與并發(fā)

    • 并行

      并行指的是兩個事件在同一時刻同時發(fā)送。

      并行圖示
      并行圖示

      => 如果兩個進程需要并行運行的話，系統(tǒng)必須具有多處理器結構

    • 并發(fā)

      并發(fā)指的是兩個事件在一個時間段內(nèi)交替發(fā)生，在宏觀上看，時間段內(nèi)兩個事件都發(fā)生了。

      并發(fā)圖示
      并發(fā)圖示

      => 上圖以單核并發(fā)為例，兩個進程在一個時間段內(nèi)交替運行，快速切換，宏觀上看起來是都在運行。（時分的思想）

  • CPU-I/O 區(qū)間周期

    一個進程的運行周期是由CPU區(qū)間和I/O區(qū)間的交替序列組成的（也就是說，一個進程在使用CPU進行計算和進程I/O操作兩種狀態(tài)之間反復切換）

    CPU區(qū)間和I/O區(qū)間交替圖示
    CPU區(qū)間和I/O區(qū)間交替圖示
    • I/O約束程序通常具有很多短CPU區(qū)間，CPU約束程序可能有少量長CPU區(qū)間。
    • 進程這種I/O區(qū)間和CPU區(qū)間交替分布，并且分布不均勻的特性，有助于選擇合適的CPU調(diào)度算法

  • CPU調(diào)度

    CPU調(diào)度 = CPU調(diào)度程序 + 派遣程序


    CPU調(diào)度的組成
    CPU調(diào)度的組成

  • CPU調(diào)度程序

    CPU調(diào)度程序 也稱 短期調(diào)度程序（short-term scheduler）。每當CPU空閑的時候，操作系統(tǒng)通過運行CPU調(diào)度程序從就緒隊列當中選擇一個進程來執(zhí)行。

    • 調(diào)度的時機

      進程狀態(tài)圖
      進程狀態(tài)圖
      1. Running => Waiting （非搶占點）
      2. Running => Ready （搶占點）
      3. Waiting => Ready （搶占點）
      4. Running => Terminated （非搶占點）

      => 其中搶占點是有可能發(fā)生搶占式調(diào)度的點

    • 搶占式調(diào)度與非搶占式調(diào)度

      • 非搶占式調(diào)度
        當線程終止或阻塞是發(fā)生調(diào)度 => “主動讓出”
      • 搶占式調(diào)度
        允許邏輯上將可繼續(xù)運行的線程在運行過程中暫停的調(diào)度方式 => “被迫讓出”

  • 派遣程序

    派遣程序（dispatcher）是一個模塊，在調(diào)度程序選中 下一個要執(zhí)行的進程后，派遣程序 負責將CPU的控制權交給選中的進程。

    • 任務

      • 切換上下文 => 如果需要的話保存舊進程的狀態(tài)，恢復選中進程的狀態(tài)
      • 切換到用戶模式 => 調(diào)度程序是在內(nèi)核態(tài)運行的，所以要恢復到用戶模式以便選中進程執(zhí)行
      • 跳轉(zhuǎn)到應用程序的合適位置，開始執(zhí)行 => 通常是跳到被選中進程的下一條待執(zhí)行的指令處，開始執(zhí)行。

    • 派遣延遲

      從就得任務暫停并保存狀態(tài)，到新的任務在CPU上開始執(zhí)行這段時間間隔

調(diào)度準則

如何判斷調(diào)度算法的好壞？有何標準？

  • CPU利用率

    CPU利用率（CPU utilization）=> 原則上，讓CPU越忙越好，即CPU使用率越高越好

  • 吞吐量

    吞吐量（throughput）指的是一個單位時間內(nèi)完成的進程的數(shù)量 => 目標當然是讓吞吐量越大越好

  • 周轉(zhuǎn)時間

    周轉(zhuǎn)時間（Turnaround time）指的是一個進程從提交到執(zhí)行完成所經(jīng)歷的時間。=> 目標當然是周轉(zhuǎn)時間越短越好

  • 等待時間

    等待時間（Waiting time）指的是進程在就緒隊列里面等待的時間長度。（CPU調(diào)度算法 并不影響進程運行和執(zhí)行I/O的時間，只會影響進程在就緒隊列中等待所花的時間）=> 對于一個進程來說，等待時間當然是越短越好

  • 響應時間

    響應時間（Response time）指的是在分時系統(tǒng)內(nèi)，用戶發(fā)出一個請求，到該請求得到響應的時間間隔長度

需要使得CPU的使用率和吞吐量最大化，而使周轉(zhuǎn)時間、等待時間和響應時間最小化。但是這些因子有些是沖突的，比如如果想要讓吞吐量最大化就勢必要讓短進程都優(yōu)先執(zhí)行，這樣就會使得長進程的等待時間和響應時間增長。在絕大多數(shù)的情況下需要優(yōu)化取平均值，而在一些特定情況可能只關心其中的一部分因子。

調(diào)度算法

  • FCFS
  • SJF
  • SRTF
  • Priority Scheduling
  • Round-Robin

  • 平均等待時間 = ((總的周轉(zhuǎn)時間) - (總的執(zhí)行時間)) / 完成的進程數(shù)量

  • 先到先服務（First Come First Serve, FCFS）

    FCFS的思想很簡單，就緒隊列用一個FIFO（First In, First Out）隊列實現(xiàn)。有新的進程到來就放到隊列尾，每當有CPU空閑則將其分配給隊頭的進程。這種實現(xiàn)是非搶占式的，進程一旦分配到CPU，就會一直占有CPU直到進程執(zhí)行完或者進程需要處理I/O主動放棄CPU的使用權。一旦等待I/O的進程處理完I/O，就會重新回到就緒隊列當中，放到隊列尾。

    FCFS示意圖
    FCFS示意圖

    • 舉個栗子

      下圖為P1、P2、P3三個進程執(zhí)行所需要的時間，認為他們均在0時刻到來。(單位為ms)

      {% img /img/os/os_23.png %}

      • 假設到來的順序為：P1、P2、P3
        {% img /img/os/os_24.png 上述到來順序的甘特圖表示%}
        • 平均周轉(zhuǎn)時間 = (24 + 27 + 30) / 3 = 27ms
        • 平均等待時間 = ((24 + 27 + 30) - (24 + 3 + 3)) / 3 = 17ms
      • 假設到來的順序為：P2、P3、P1
        {% img /img/os/os_25.png 上述到來順序的甘特圖表示%}
        • 平均周轉(zhuǎn)時間 = (3 + 6 + 30) / 3 = 13ms
        • 平均等待時間 = ((3 + 6 + 30) - (24 + 3 + 3)) / 3 = 3ms

    • FCFS的問題

      • 受進程區(qū)間時間和到來順序的影響較大
        從上面的栗子里面也可以看出，F(xiàn)CFS的性能受進程的區(qū)間時間和到來順序的影響比較大。如果進程CPU的區(qū)間變動很大，那么性能也會飄忽不定。
      • 護航效應
        因為FCFS算法是非搶占式的，允許一個進程長期占有CPU時間。如果有一個很大的進程占據(jù)CPU，而其他進程都在等待這個長進程的結束，便產(chǎn)生了護航效應（convoy effect）。

  • 短作業(yè)優(yōu)先算法（Shortest-Job-First, SJF）

    • 如果以平均等待時間為指標，那SJF是最優(yōu)的調(diào)度
    • SJF算法也是非搶占的

    每次進行調(diào)度的時候，優(yōu)先選擇下一個CPU周期（執(zhí)行時間）最短的進程。也就是，調(diào)度的時候，系統(tǒng)去就緒隊列里面找到執(zhí)行所需要時間最短的進程，分配給它CPU讓它去執(zhí)行。

    • 栗子1

      下圖為P1、P2、P3、P4四個進程執(zhí)行所需要的時間，認為他們均在0時刻到來。(單位為ms)

      SJF調(diào)度示例1
      SJF調(diào)度示例1

      它們的到來順序為P1、P2、P3、P4，則對應的Gant圖如下：
      SJF調(diào)度Gant圖1
      SJF調(diào)度Gant圖1

      • 平均周轉(zhuǎn)時間 = (3 + 9 + 16 + 24) / 4 = 13ms
      • 平均等待時間 = ((3 + 9 + 16 + 24) - (6 + 8 + 7 + 3)) / 4 = 7ms

    • 栗子2

      下圖為P1、P2、P3、P4四個進程的到來時間和執(zhí)行所需要的時間。（單位為ms）

      SJF調(diào)度示例2
      SJF調(diào)度示例2

      采用SJF調(diào)度，執(zhí)行順序?qū)腉ant圖如下：
      SJF調(diào)度Gant圖2
      SJF調(diào)度Gant圖2

      • 平均周轉(zhuǎn)時間 = (6 + (9 - 5) + (16 - 4) + (24 - 2)) / 4 = 11ms
      • 平均等待時間 = ((6 + (9 - 5) + (16 - 4) + (24 - 2)) - (6 + 8 + 7 + 3)) / 4 = 5ms

    • SJF調(diào)度算法存在的問題

      因為一個進程沒有執(zhí)行，所以我們并不知道它會運行多久，也就是說我們無法準確的知道進程的CPU周期長度。只能根據(jù)進程CPU周期的歷史數(shù)據(jù)，堆下一個CPU周期長度進行預測。=> 采用指數(shù)平均方法（exponential averaging）

    • 指數(shù)平均方法

      τn+1 = α tn + (1 - α) τn

      • tn：第n個進程的CPU周期（actutal length of nth CPU burst）
      • τn+1：對下一個進程的CPU周期的預測值（predicted value for the next CPU burst）
      • α：0 ≤ α ≤ 1。通常取 1/2
      • 離現(xiàn)在越久的歷史數(shù)據(jù)，對預測結果的影響越弱
      采用指數(shù)平均的方法預測下一進程CPU周期
      采用指數(shù)平均的方法預測下一進程CPU周期

  • 最短剩余時間算法（Shortest-Remain-Time-First scheduling, SRTF）

    SRTF算法實際上是一種特殊的SJF算法，它是一種允許搶占的SJF算法。

    • 每當一個新進程進入就緒隊列，就會產(chǎn)生一個搶占點。

    • 如果就緒隊列中的進程的剩余執(zhí)行時間比正在執(zhí)行的進程的短，就會搶占掉正在執(zhí)行的進程。

    • 舉個栗子

      下圖為P1、P2、P3、P4四個進程的到來時間和執(zhí)行所需要的時間。（單位為ms）

      SRTF調(diào)度示例
      SRTF調(diào)度示例

      采用SRTF調(diào)度，執(zhí)行順序?qū)腉ant圖如下：
      SJF調(diào)度Gant圖
      SJF調(diào)度Gant圖

      • 平均周轉(zhuǎn)時間 = ((5 - 1) + (10 - 3) + (17 - 0) + (26 - 2)) / 4 = 13ms
      • 平均等待時間 = (((5 - 1) + (10 - 3) + (17 - 0) + (26 - 2)) - (8 + 4 + 9 + 5)) / 4 = 6.5ms

  • 優(yōu)先級調(diào)度算法（priority scheduling）

    優(yōu)先級調(diào)度算法（priority scheduling）的核心思想是給每一個進程賦予一個優(yōu)先級，每次調(diào)度的時候選擇選中優(yōu)先級最高的進程執(zhí)行。

    • SJF是一種特殊的優(yōu)先級調(diào)度算法

      SJF 也是基于優(yōu)先級的，預測出的 下一個CPU周期越短，優(yōu)先級越高

    • 搶占與非搶占

      • 非搶占式（Nonpreemptive）優(yōu)先級調(diào)度
        非搶占的模式下，一個新進程到達，無論其優(yōu)先級如何，都只是將其放到就緒隊列等待。
      • 搶占式（Preemptive）優(yōu)先級調(diào)度
        在搶占模式下，一個新進程到達，如果其優(yōu)先級比正在執(zhí)行的進程的優(yōu)先級高，便會搶占正在執(zhí)行進程的CPU

    • 優(yōu)先級算法存在的問題

      優(yōu)先級算法存在的主要問題是無窮阻塞（indefinite blocking）/ 饑餓（starvation）。=> 低優(yōu)先級的進程可能永遠得不到執(zhí)行

    • 老化（Aging）=> 解決饑餓問題

      逐漸增加在系統(tǒng)中等待很長時間的進程的優(yōu)先級，增加其執(zhí)行的可能性。

    • 舉個栗子

      下圖為P1、P2、P3、P4、P5五個進程的優(yōu)先級和執(zhí)行所需要的時間，認為他們均在0時刻到來。（單位為ms）
      優(yōu)先級調(diào)度示例
      優(yōu)先級調(diào)度示例

      采用優(yōu)先級調(diào)度，執(zhí)行順序?qū)腉ant圖如下：
      優(yōu)先級調(diào)度Gant圖
      優(yōu)先級調(diào)度Gant圖
      • 平均周轉(zhuǎn)時間 = (1 + 6 + 16 + 18 + 19) / 5 = 12ms
      • 平均等待時間 = ((1 + 6 + 16 + 18 + 19) - (10 + 1 + 2 + 1 + 5)) / 5 = 8.2ms

  • 輪轉(zhuǎn)調(diào)度算法（Round Robin scheduling, RR）

    輪轉(zhuǎn)調(diào)度（Round Robin, RR）的核心思想類似于FCFS，但是增加了搶占機制。定義一個較短的時間間隔，稱為時間片（time quantum, or time slice）。進程每次在CPU上執(zhí)行的時間間隔不會超過一個時間片的長度。

    • 執(zhí)行過程

      • 首先就緒隊列維護為一個FIFO隊列，每次調(diào)度的時候從隊首取一個進程*。
      • 一個新的進程被選中而得到執(zhí)行時，會設置一個定時器在一個時間片之后中斷。
      • 如果進程在一個時間片內(nèi)執(zhí)行完畢了，會主動釋放CPU，調(diào)度程序會取出就緒隊列中的下一個進程執(zhí)行。
      • 如果進程執(zhí)行滿一個時間片，但是沒有執(zhí)行完。則定時器會超時并引發(fā)操作系統(tǒng)超時中斷，然后進行上下文切換。進程被放到就緒隊列 隊尾，接著調(diào)度程序會選擇就緒隊列的下一個進程執(zhí)行。

    • 輪轉(zhuǎn)調(diào)度的效率問題

      時間片的大小通常在10~100ms

      • 時間片太大 => 等同于FCFS
      • 時間片太小 => 上下文切換過于頻繁

    • 舉個栗子

      下圖為P1、P2、P3三個進程的優(yōu)先級和執(zhí)行所需要的時間，認為他們均在0時刻到來。（單位為ms）

      RR調(diào)度示例
      RR調(diào)度示例

      采用RR調(diào)度，執(zhí)行順序?qū)腉ant圖如下：
      RR調(diào)度Gant圖
      RR調(diào)度Gant圖

  • 最高響應比優(yōu)先調(diào)度算法（擴展）

    在批處理操作系統(tǒng)中，常用短作業(yè)優(yōu)先調(diào)度算法。但短作業(yè)優(yōu)先調(diào)度算法有一個致命的弱點，那就是長進程可能會被餓死

    最高響應比優(yōu)先調(diào)度是對短作業(yè)優(yōu)先調(diào)度的改進

    • 優(yōu)先權

      P = (W + T) / T
      • W: 進程等待時間
      • T: 進程執(zhí)行時間

    • 規(guī)則

      • 優(yōu)先權P被稱為響應比，又被稱為進程的帶權周轉(zhuǎn)時間，響應比越大，調(diào)度優(yōu)先權越高
      • 采取非搶占方式進行調(diào)度

  • 多級隊列調(diào)度（Multilevel Queue）

    多級隊列（Multilevel Queue）的思想：將就緒隊列拆分為多個，每個隊列可以各自采取不同的調(diào)度算法，隊列之前按優(yōu)先級的高低來進行調(diào)度。

    多級隊列調(diào)度
    多級隊列調(diào)度

    對于如何在多個隊列之間均衡時間，有下列兩種方式：

    • 固定優(yōu)先級：每個隊列被賦予特定的優(yōu)先級，高優(yōu)先級隊列中的進程先得到調(diào)度?？赡艽嬖陴囸I問題（低優(yōu)先級隊列中的進程餓死）。
    • 時間片：給每個隊列賦予一定的時間片，分配有一定的原則（并非完全等額分配）。例如可以80%的時間保證賦予前臺進程，20%時間賦予后臺進程

  • 多級反饋隊列（Multilevel Feedback Queue）

    多級反饋隊列（Multilevel Feedback Queue）解決多級隊列中存在的饑餓問題：將較長時間得不到調(diào)度的進程移動到更高優(yōu)先級的隊列

    多級反饋隊列
    多級反饋隊列

線程調(diào)度（Thread Scheduling）

  • 用戶級線程與內(nèi)核級線程的區(qū)別：內(nèi)核對內(nèi)核級線程進行調(diào)度（***Distinction between user-level and kernel-level threads ***）

  • 當操作系統(tǒng)支持線程機制時，線程成為調(diào)度的基本單位（When threads supported, threads scheduled, not processes）

  • 多對一、多對多線程模型中，線程庫負責對輕量級線程上的多個用戶線程進行調(diào)度（Many-to-one and many-to-many models, thread library schedules user-level threads to run on LWP）

  • 內(nèi)核級線程在全系統(tǒng)范圍競爭CPU時間（***Kernel thread scheduled onto available CPU is system-contention scope (SCS) – competition among all threads in system ***）

  • pthread線程庫中允許在創(chuàng)建線程時指定競爭域（PCS/SCS）（API allows specifying either PCS or SCS during thread creation）

?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容