進(jìn)程調(diào)度與死鎖

第三章 進(jìn)程調(diào)度與死鎖

進(jìn)程調(diào)度的功能與時機(jī)

進(jìn)程調(diào)度的功能

進(jìn)程調(diào)度的功能由操作系統(tǒng)的 進(jìn)程調(diào)度程序 來完成。

按照某種策略和算法 從就緒進(jìn)程中為當(dāng)前空閑的CPU選擇在其上運(yùn)行的新進(jìn)程。

進(jìn)程調(diào)度的時機(jī)

  1. 進(jìn)程正常結(jié)束；
  2. 進(jìn)程異常結(jié)束；
  3. 進(jìn)程阻塞；
  4. 有更高優(yōu)先級進(jìn)程到來；
  5. 時間片用完；

進(jìn)程調(diào)度算法

進(jìn)程調(diào)度算法和輸入/輸出設(shè)備的速度都會影響系統(tǒng)的 響應(yīng)時間。

選擇調(diào)度方式和算法的若干準(zhǔn)則

  1. 周轉(zhuǎn)時間短；
  2. 響應(yīng)時間快；
  3. 截止時間的保證；
  4. 系統(tǒng)吞吐量高；
  5. 處理機(jī)利用率好；

周轉(zhuǎn)時間的相關(guān)計(jì)算

周轉(zhuǎn)時間 = 外存等待時間 + 就緒隊(duì)列等待時間 + 服務(wù)（執(zhí)行）時間 + 等待I/O操作完成

平均周轉(zhuǎn)時間 = \frac{1}{n} * [\sum_{i=0}^{n}{T_{i}}]

平均周轉(zhuǎn)時間 = \frac{1}{n} * (T_{1} + T_{2} + ... + T_{n})

帶權(quán)平均周轉(zhuǎn)時間 = \frac{1}{n} * [\sum_{i=0}^{n}{\frac{T_{i}}{TS_{i}}}]

帶權(quán)平均周轉(zhuǎn)時間 = \frac{1}{n} * (\frac{T_{1}}{TS_{1}} + \frac{T_{2}}{TS_{2}} + ... + \frac{T_{i}}{TS_{i}})

TS：服務(wù)時間：CPU執(zhí)行的時間

響應(yīng)時間，用戶提交一個請求直至系統(tǒng)首次產(chǎn)生響應(yīng)的時間。包括：

  1. 輸入設(shè)備輸入的請求信息傳送到處理機(jī)的時間；
  2. 處理機(jī)對請求信息進(jìn)行處理的時間；
  3. 將所形成的響應(yīng)信息回送到終端顯示器的時間；

調(diào)度算法

先來先服務(wù)算法

英文：First-Come，F(xiàn)irst-Served，FCFS

含義：從就緒隊(duì)列的隊(duì)首 選擇最先到達(dá)就緒隊(duì)列的進(jìn)程，為該進(jìn)程分配CPU。

適合：長進(jìn)程、CPU繁忙進(jìn)程

調(diào)度算法-先來先服務(wù)調(diào)度算法FCFS.png

短進(jìn)程優(yōu)先調(diào)度算法

英文：Shortest-Porcess-First，SPF

含義：從就緒隊(duì)列中 選擇估計(jì)運(yùn)行時間最短的進(jìn)程，為該進(jìn)程分配CPU。

優(yōu)點(diǎn)：與FCFS算法相比，短進(jìn)程優(yōu)先算法能有效 降低進(jìn)程的平均等待時間，提高系統(tǒng)吞吐量。

缺點(diǎn)：

  1. 對長進(jìn)程不利；
  2. 不能保證緊迫進(jìn)程的處理；
  3. 進(jìn)程長短由用戶估計(jì)，不一定準(zhǔn)確；
調(diào)度算法-短進(jìn)程優(yōu)先調(diào)度算法SPF.png

優(yōu)先權(quán)調(diào)度算法

英文：Priority-Scheduling Lgorithm

含義：該算法中，系統(tǒng)將CPU分配給就緒隊(duì)列中 優(yōu)先級最高的進(jìn)程。

存在的問題：無窮阻塞（饑餓問題）。

解決的方案：增加等待時間很長的進(jìn)程的優(yōu)先級 —— 老化技術(shù)。

類型：

  1. 非搶占式：運(yùn)行期間，有更高優(yōu)先級的進(jìn)程到來，也 不能 剝奪CPU；
  2. 搶占式：運(yùn)行期間，有更高優(yōu)先級的進(jìn)程到來，就 可以 剝奪CPU；

優(yōu)先權(quán)類型：

  1. 靜態(tài)優(yōu)先權(quán)：創(chuàng)建時確定，運(yùn)行期間 保持不變；
    • 根據(jù) 進(jìn)程的類型、進(jìn)程需要的資源數(shù)量和用戶的要求 來決定；
  2. 動態(tài)優(yōu)先權(quán)：創(chuàng)建時確定，隨著進(jìn)程推進(jìn)或等待時間增加而 改變；

時間片輪轉(zhuǎn)調(diào)度算法

英文：Round-Robin，RR

含義：每次把CPU分給隊(duì)首進(jìn)程，令其執(zhí)行一個時間片。

時間片大?。?strong>10-100ms

時間片很大 = 先來先服務(wù)調(diào)度程序

時間片很?。涸龃驝PU對進(jìn)程切換和調(diào)度的開銷

時間片大小的 確定條件：

  1. 系統(tǒng)對 響應(yīng)時間 的要求：響應(yīng)時間要求越短，時間片越?。?/li>
  2. 就緒隊(duì)列 中進(jìn)程的數(shù)目：進(jìn)程數(shù)量越多，時間片越?。?/li>
  3. 系統(tǒng)的 處理能力：處理能力越好，時間片越小；

linux 2.4 的時間片為：50ms

多級隊(duì)列調(diào)度算法

含義：將就緒隊(duì)列分成多個獨(dú)立隊(duì)列，每個隊(duì)列都有自己的調(diào)度算法。

不足：不夠靈活，對低優(yōu)先級進(jìn)程會存在無窮阻塞（饑餓）問題。

Minix 把對任務(wù)進(jìn)程和服務(wù)進(jìn)程采用 基于優(yōu)先權(quán)的非搶占式調(diào)度。

多級反饋隊(duì)列調(diào)度算法

含義：建立多個優(yōu)先級不同的就緒隊(duì)列，每個隊(duì)列有大小不同的時間片。

優(yōu)點(diǎn)：相對靈活，不會出現(xiàn)無窮阻塞（饑餓）問題。

實(shí)時系統(tǒng)中的調(diào)度

實(shí)時系統(tǒng)計(jì)算的 正確性 取決于 計(jì)算的邏輯結(jié)果的正確性 和 計(jì)算的時間。

實(shí)時調(diào)度的基本條件

  1. 提供必要的調(diào)度信息：
    • 就緒時間；
    • 開始截止時間；
    • 完成截止時間；
    • 處理時間；
    • 資源要求；
    • 優(yōu)先級；
  2. 系統(tǒng)處理能力強(qiáng)；
  3. 采用搶占式調(diào)度機(jī)制；
  4. 具有快速切換機(jī)制：
    • 對外部中斷的快速響應(yīng)能力：快速的硬件中斷機(jī)構(gòu)、中斷的時間間隔盡可能短；
    • 快速的進(jìn)程切換能力：減少進(jìn)程切換的開銷；

常用的實(shí)時調(diào)度算法

  1. 最早截止時間優(yōu)先算法 EDF：開始截止時間 越早，進(jìn)程優(yōu)先級越高，越優(yōu)先獲得CPU；
  2. 最低松弛度優(yōu)先算法 LLF：進(jìn)程的 緊迫程度 越小，進(jìn)程優(yōu)先級越高；

松弛度：表示一個實(shí)時進(jìn)程的緊迫程度。

緊迫程度 = T - T_{C} - T_{S}

T：完成截止時間

T_{C}：當(dāng)前時間

T_{S}：處理完該任務(wù)需要的時間

進(jìn)程切換

進(jìn)程切換的含義

當(dāng)前正在執(zhí)行的進(jìn)程成為被替換進(jìn)程，讓出其所使用的CPU，以運(yùn)行被進(jìn)程調(diào)度程序選擇的新進(jìn)程，這個過程稱為 進(jìn)程切換。

進(jìn)程切換的步驟

  1. 保存CPU上下文環(huán)境；
  2. 更新進(jìn)程1的進(jìn)程控制塊；
  3. 修改進(jìn)程1的進(jìn)程狀態(tài)；（執(zhí)行態(tài) -> 就緒態(tài)或阻塞態(tài)）
  4. 移動進(jìn)程1的進(jìn)程控制塊到就緒隊(duì)列或阻塞隊(duì)列；
  5. 調(diào)度新程序，更新進(jìn)程2的進(jìn)程控制塊；
  6. 更新內(nèi)存管理的數(shù)據(jù)結(jié)構(gòu)；
  7. 恢復(fù)進(jìn)程的硬件上下文；

多處理器調(diào)度

多處理器系統(tǒng)的類型

根據(jù)處理器的 耦合程度 分類：

  1. 緊密耦合 多處理器系統(tǒng)：共享主存儲器（內(nèi)存）和I/O設(shè)備；
  2. 松弛耦合 多處理器系統(tǒng)：有各自的存儲器和I/O設(shè)備；

根據(jù)處理器的 結(jié)構(gòu)功能是否相同 分類：

  1. 對稱 多處理器系統(tǒng)：處理單元（CPU）功能和結(jié)構(gòu)相同；
  2. 非對稱 多處理器系統(tǒng)：有多種類型的處理單元，一個主處理器，多個從處理器；

多處理器系統(tǒng)的進(jìn)程分配方式

對稱系統(tǒng)分配方式

  1. 靜態(tài)分配：
    • 就緒隊(duì)列的進(jìn)程只能在與就緒隊(duì)列對應(yīng)的處理器上運(yùn)行；
    • 優(yōu)點(diǎn)：進(jìn)程調(diào)度的開銷??；
  2. 動態(tài)分配：
    • 進(jìn)程隨機(jī)地被分配到當(dāng)時處于空閑狀態(tài)的某一處理器上執(zhí)行；
    • 所有就緒進(jìn)程都放在一個 公共的就緒隊(duì)列 中；
    • 優(yōu)點(diǎn)：考慮服務(wù)器的 負(fù)載平衡問題，分配給空閑進(jìn)程；
對稱系統(tǒng)分配方式.png

非對稱系統(tǒng)分配方式

  1. 主-從式操作系統(tǒng)；
非對稱系統(tǒng)分配方式.png

進(jìn)程（線程）的調(diào)度方式

  1. 自調(diào)度；
  2. 成組調(diào)度；
  3. 專用處理器分配；

自調(diào)度

最常用最簡單 的方式。

自調(diào)度的 優(yōu)點(diǎn)：

  1. 易移植：很容易將單處理器環(huán)境下所用的調(diào)度機(jī)制移植到多處理器環(huán)境中；
  2. 有利于 提高CPU的利用率：不會出現(xiàn)處理器空閑或忙閑的情況；

自調(diào)度的 缺點(diǎn)：

  1. 瓶頸問題：處理器數(shù)量很多時；
  2. 低效性：多次更換處理器；
  3. 線程切換頻繁：某些線程因其合作的線程未獲得處理器而阻塞導(dǎo)致進(jìn)程切換；

成組調(diào)度

系統(tǒng)將一組相互合作的進(jìn)程或線程同時分配到同一組處理器上運(yùn)行，進(jìn)程或線程與處理器一一對應(yīng)。

成組調(diào)度的 優(yōu)點(diǎn)：

  1. 減少線程切換；
  2. 減少調(diào)度開銷；

成組調(diào)度采用兩種方式為應(yīng)用程序分配處理器時間：

  1. 面向所有的 應(yīng)用程序 平均分配處理器時間；
  2. 面向所有的 線程 平均分配處理器時間；

專用處理器分配

在程序執(zhí)行期間，專門為該程序分配一組處理器，每個線程一個。

專用處理器分配的 優(yōu)點(diǎn)：

  1. 加成程序運(yùn)行速度；
  2. 避免進(jìn)程切換；

專用處理器分配的 缺點(diǎn)：

  1. 處理器資源嚴(yán)重浪費(fèi)；

死鎖

死鎖的定義

由于 多個進(jìn)程競爭共享資源 而引起的 進(jìn)程不能向前推進(jìn) 的僵死狀態(tài)稱為 死鎖。

產(chǎn)生死鎖的原因

競爭 共享資源且分配資源的 順序不當(dāng)。

產(chǎn)生的必要條件

  1. 互斥條件；
  2. 請求和保持條件；
  3. 不剝奪條件；
  4. 環(huán)路等待條件；

只有當(dāng) 四個條件同時滿足 時才會產(chǎn)生死鎖。

處理死鎖的基本方法

  1. 死鎖的 預(yù)防：通過 破環(huán)死鎖的產(chǎn)生條件 來保證不發(fā)生死鎖；
  2. 死鎖的 避免：通過 算法合理分配資源 來保證不發(fā)生死鎖；
  3. 死鎖的 檢測：檢索當(dāng)前系統(tǒng)是否出現(xiàn)死鎖；
  4. 死鎖的 解除：檢索到系統(tǒng)有死鎖后進(jìn)行解除；
  5. 死鎖的 忽略；

死鎖的預(yù)防

保證產(chǎn)生死鎖的必要條件中，至少其中一個條件不成立。

  1. 摒棄 請求和保持條件：要求進(jìn)程一次性 申請 需要的 全部資源，申請其他資源前 釋放 已經(jīng)占用的資源；
  2. 摒棄 不剝奪條件：系統(tǒng) 搶占 被占用的資源分配給需要的進(jìn)程；
    • 缺點(diǎn)：實(shí)現(xiàn)復(fù)雜，代價高；
  3. 摒棄 環(huán)路等待條件：進(jìn)程必須 按規(guī)定的順序 申請 資源（打印機(jī)、磁盤）；
    • 缺點(diǎn)：限制了新設(shè)備的增加，資源浪費(fèi)，用戶編程麻煩；

死鎖的避免

通過資源合理分配使系統(tǒng)處于 安全狀態(tài)。

安全狀態(tài) ？：能夠找到一個進(jìn)程 執(zhí)行序列，按照這個序列會每個進(jìn)程分配資源，就可以保證進(jìn)程資源分配和執(zhí)行順利完成，不會發(fā)生死鎖。

設(shè)系統(tǒng)有一類數(shù)量為 M 的獨(dú)占性資源，系統(tǒng)中有 N 個進(jìn)程競爭該類資源，每個進(jìn)程對資源的最大需求為 W。當(dāng)滿足 N * (W-1) + 1 <= M 時，系統(tǒng)處于安全狀態(tài)。

死鎖的避免.png

銀行家算法：一個進(jìn)程提出資源請求后，系統(tǒng)先進(jìn)行資源的試分配，分配后檢測系統(tǒng)是否安全。

任何時刻都能至少保證一個進(jìn)程獲得所需要的全部資源。

銀行家算法.png

死鎖的檢測

何時調(diào)用 檢測算法 ？：

  1. 死鎖可能發(fā)生的 頻率；
  2. 死鎖發(fā)生時受影響的 進(jìn)程數(shù)量；

資源分配圖：

資源分配圖.png

死鎖定理：S為死鎖狀態(tài) 的充分條件是當(dāng)前僅當(dāng)S狀態(tài)的 資源分配圖是不可完全簡化的（上圖的資源分配圖是可以被簡化的）。

死鎖定理用于檢測系統(tǒng)所處的資源分配狀態(tài)是否為死鎖狀態(tài)。

死鎖的解除

  1. 進(jìn)程終止：
    • 終止所有死鎖進(jìn)程；
    • 一次只終止一個處于死鎖狀態(tài)的進(jìn)程，直到死鎖接觸；
  2. 資源搶占：
    • 逐步從進(jìn)程中搶占資源給其他進(jìn)程使用直到死鎖被打破為止；

搶占的代價最小，死鎖進(jìn)程擁有的資源數(shù)量、死鎖進(jìn)程到目前為止已經(jīng)消耗的執(zhí)行時間。

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

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

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