處理機(jī)調(diào)度與死鎖

處理機(jī)調(diào)度的層次

高級(jí)調(diào)度/作業(yè)調(diào)度/長程調(diào)度

• 作用：將外存后備隊(duì)列中的作業(yè)調(diào)入內(nèi)存
• 對(duì)象：作業(yè)

作業(yè)：比程序更泛的一個(gè)概念，通常包含程序、數(shù)據(jù)以及作業(yè)說明書，批處理系統(tǒng)中，以作業(yè)為基本單位從外存調(diào)入內(nèi)存

作業(yè)步：作業(yè)中的步驟

作業(yè)流：進(jìn)入系統(tǒng)后，在外存中排隊(duì)的作業(yè)，形成輸入作業(yè)流，在系統(tǒng)控制下進(jìn)行處理，形成處理作業(yè)流

作業(yè)控制塊：JCB，是作業(yè)在系統(tǒng)中存在的標(biāo)志，保存了系統(tǒng)對(duì)作業(yè)進(jìn)行管理和調(diào)度所需要的全部信息

低級(jí)調(diào)度/進(jìn)程調(diào)度/短程調(diào)度

• 作用：決定哪個(gè)進(jìn)程應(yīng)該獲得處理機(jī)
• 對(duì)象：進(jìn)程
• 基本機(jī)制
  • 排隊(duì)器：提高進(jìn)程調(diào)度的效率，將就緒的進(jìn)程按照一定的方法排成一個(gè)或者多個(gè)隊(duì)列
  • 分派器：把由進(jìn)程調(diào)度所選中的進(jìn)程，從就緒隊(duì)列中取出，然后進(jìn)行上下文切換，將處理機(jī)分配給它
  • 上下文切換機(jī)制：當(dāng)對(duì)處理機(jī)進(jìn)行切換時(shí)，會(huì)執(zhí)行兩次上下文切換，1. 保存當(dāng)前進(jìn)程的上下文，載入分派程序上下文，2. 移出分派進(jìn)程，載入新選進(jìn)程的上下文信息
• 調(diào)度方式
  • 非搶占式方式：只要進(jìn)程在執(zhí)行，則不搶占其處理機(jī)
  • 搶占方式
    • 優(yōu)先權(quán)原則：允許優(yōu)先權(quán)高的進(jìn)程搶占當(dāng)前進(jìn)程的處理機(jī)
    • 短作業(yè)/進(jìn)程優(yōu)先
    • 時(shí)間片原則

中級(jí)調(diào)度/中程調(diào)度

• 作用：提高內(nèi)存利用率和系統(tǒng)吞吐量，將暫時(shí)不能運(yùn)行的進(jìn)程調(diào)至外存上等待，也就是將其掛起
• 對(duì)象：進(jìn)程

調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則

調(diào)度隊(duì)列模型

• 僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型
• 具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型
  • 就緒隊(duì)列一般采用高優(yōu)先權(quán)優(yōu)先調(diào)度算法
  • 設(shè)置多個(gè)阻塞隊(duì)列
• 同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型

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

• 面向用戶的準(zhǔn)則
  • 周轉(zhuǎn)時(shí)間短
    • 周轉(zhuǎn)時(shí)間：作業(yè)從被提交到作業(yè)完成這段時(shí)間(作業(yè)在外存后備隊(duì)列等待調(diào)度的時(shí)間，進(jìn)程就緒隊(duì)列上等待時(shí)間，進(jìn)程在CPU上執(zhí)行的時(shí)間，進(jìn)程等待I/O操作完成的時(shí)間)
    • 平均帶權(quán)周轉(zhuǎn)時(shí)間：W = 1/n * sum(Ti/Ts) 其中Ti 指的是作業(yè)的周轉(zhuǎn)時(shí)間，Ts指的是作業(yè)的服務(wù)時(shí)間
  • 響應(yīng)時(shí)間快
    • 響應(yīng)時(shí)間：從請(qǐng)求發(fā)出到收到回應(yīng)的時(shí)間
  • 截止時(shí)間的保證
    • 截止時(shí)間：任務(wù)必須開始執(zhí)行的最遲時(shí)間
  • 優(yōu)先權(quán)保證
• 面向系統(tǒng)的準(zhǔn)則
  • 系統(tǒng)吞吐量高
    • 吞吐量：單位時(shí)間內(nèi)完成的作業(yè)數(shù)
  • 處理機(jī)利用率好
  • 各類資源的平均使用

調(diào)度算法

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

• 應(yīng)用場(chǎng)景：作業(yè)調(diào)度、進(jìn)程調(diào)度
• 運(yùn)作方式
  • 作業(yè)調(diào)度：每次調(diào)度都是從后備隊(duì)列中選擇一個(gè)或者多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)，將其調(diào)入內(nèi)存
  • 進(jìn)程調(diào)度：從就緒隊(duì)列中選擇一個(gè)最先進(jìn)入該隊(duì)列的進(jìn)程，為其分配處理機(jī)
• 特性：有利于長作業(yè)/進(jìn)程，不利于短作業(yè)/進(jìn)程

• 案例

  
  
  先來先服務(wù)調(diào)度算法
  
  

  可以看到，D的要求服務(wù)時(shí)間只有2，但是其帶權(quán)周轉(zhuǎn)時(shí)間到達(dá)5.5，而長作業(yè)C的周轉(zhuǎn)時(shí)間則只有2，可以得出結(jié)論，先來先服務(wù)調(diào)度算法有利于CPU繁忙型的作業(yè)

短作業(yè)/進(jìn)程優(yōu)先調(diào)度算法(SJF/SPF)

• 應(yīng)用場(chǎng)景：作業(yè)調(diào)度、進(jìn)程調(diào)度
• 運(yùn)行方式
  • 作業(yè)調(diào)度：從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將其調(diào)入內(nèi)存運(yùn)行
  • 進(jìn)程調(diào)度：從就緒隊(duì)列中選出一個(gè)估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使其一直執(zhí)行到完成，或者因某事而被阻塞放棄處理機(jī)時(shí)再重新調(diào)度
• 特性：有效降低作業(yè)的平均等待時(shí)間，提高系統(tǒng)的吞吐量

• 案例

  
  
  短作業(yè)優(yōu)先調(diào)度算法
  
  

  可以看到，無論是平均周轉(zhuǎn)時(shí)間還是帶權(quán)平均周轉(zhuǎn)時(shí)間，短作業(yè)優(yōu)先調(diào)度算法均低于先來先服務(wù)調(diào)度算法，尤其是短作業(yè)D的帶權(quán)周轉(zhuǎn)時(shí)間，從5.5下降到1.5

• 缺點(diǎn)：對(duì)長作業(yè)不利，可能導(dǎo)致長作業(yè)一直未能分配到處理機(jī)，完全未考慮作業(yè)的緊迫程度，作業(yè)長短只是估計(jì)值，并不一定準(zhǔn)確

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

• 應(yīng)用場(chǎng)景：作業(yè)調(diào)度、進(jìn)程調(diào)度
• 運(yùn)行方式
  • 作業(yè)調(diào)度：從后備隊(duì)列中選擇若干個(gè)優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存
  • 進(jìn)程調(diào)度：把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程
• 細(xì)分
  • 非搶占式優(yōu)先權(quán)調(diào)度算法
    • 一旦把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程便可以一直執(zhí)行下去，直至完成；或者因某事而主動(dòng)放棄處理機(jī)
  • 搶占式優(yōu)先權(quán)調(diào)度算法
    • 在執(zhí)行期間，如果出現(xiàn)了另一個(gè)優(yōu)先權(quán)更高的進(jìn)程，進(jìn)程調(diào)度程序立即停止當(dāng)前進(jìn)程，重新將處理機(jī)分配給新來的優(yōu)先權(quán)最高的進(jìn)程
• 優(yōu)先權(quán)類型
  • 靜態(tài)優(yōu)先權(quán)：創(chuàng)建進(jìn)程時(shí)確定，并且在進(jìn)程運(yùn)行期間一直保持不變
  • 動(dòng)態(tài)優(yōu)先權(quán)：在運(yùn)行期間可以動(dòng)態(tài)改變進(jìn)程的進(jìn)程的優(yōu)先權(quán)
• 高響應(yīng)比優(yōu)先調(diào)度算法
  • 動(dòng)態(tài)地調(diào)整優(yōu)先權(quán)的一種基于搶占式的調(diào)度算法
  • 響應(yīng)比：Rp = (等待時(shí)間+要求服務(wù)時(shí)間)/要求服務(wù)時(shí)間 = (響應(yīng)時(shí)間)/要求服務(wù)時(shí)間
  • 特點(diǎn)：既照顧了短作業(yè)、也考慮了作業(yè)到達(dá)次序，也能保證長作業(yè)能夠得到服務(wù)，但是每次調(diào)度前，都需要做響應(yīng)比計(jì)算

基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法

時(shí)間片輪轉(zhuǎn)法

多級(jí)反饋調(diào)度算法

1. 設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)，第一個(gè)隊(duì)列優(yōu)先級(jí)最高，依次遞減，各個(gè)隊(duì)列的執(zhí)行時(shí)間片也不同，優(yōu)先權(quán)越高，時(shí)間片越短，依次增加一倍
2. 當(dāng)一個(gè)新的進(jìn)程進(jìn)入內(nèi)存之后，將其放入第一隊(duì)列的末尾，按照FCFS原則排隊(duì)等待調(diào)度，如果在指定時(shí)間內(nèi)未能完成，則轉(zhuǎn)入第二隊(duì)列的末尾...
3. 只有當(dāng)?shù)谝魂?duì)列為空時(shí)，調(diào)度程序才會(huì)啟動(dòng)第二隊(duì)列中的進(jìn)程運(yùn)行，僅當(dāng)?shù)?_{i-1隊(duì)列中均為空時(shí)，才會(huì)調(diào)度第i隊(duì)列中，如果處理機(jī)此時(shí)在為i隊(duì)列某進(jìn)程服務(wù)，有新的進(jìn)程進(jìn)入1}i-1中任意隊(duì)列，則發(fā)生調(diào)度，先執(zhí)行該進(jìn)程，并且把當(dāng)前進(jìn)程放入i隊(duì)列的末尾

性能：滿足多種作業(yè)的需求。

實(shí)時(shí)調(diào)度

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

• 提供必要的信息
  • 就緒時(shí)間
  • 開始截止時(shí)間和完成截止時(shí)間
  • 處理時(shí)間
  • 資源要求
  • 優(yōu)先級(jí)
• 系統(tǒng)處理能力強(qiáng)
• 假設(shè)有m個(gè)硬實(shí)時(shí)任務(wù)，則需要滿足 sum(ci/pi) <=1 ci為執(zhí)行該進(jìn)程所需時(shí)間，pi為該進(jìn)程的周期時(shí)間
• 采用搶占式調(diào)度機(jī)制
• 具有快速切換機(jī)制
  • 對(duì)外部中斷的快速響應(yīng)能力
  • 快速的任務(wù)分派能力

實(shí)時(shí)調(diào)度算法的分類

• 非搶占式調(diào)度算法(小型實(shí)時(shí)系統(tǒng)、要求不太嚴(yán)格的實(shí)時(shí)控制系統(tǒng))
  • 非搶占式輪轉(zhuǎn)調(diào)度算法
  • 非搶占式優(yōu)先調(diào)度算法
• 搶占式調(diào)度算法(要求比較嚴(yán)格)
  • 基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法：時(shí)鐘中斷到來才發(fā)生切換
  • 立即搶占的優(yōu)先權(quán)調(diào)度算法

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

• 最早截止時(shí)間優(yōu)先(EDF)算法
• 非搶占式調(diào)度方式用于非周期性實(shí)時(shí)任務(wù)
• 搶占式調(diào)度方式用于周期性實(shí)時(shí)任務(wù)
• 最低松弛度/緊急程度優(yōu)先(LLF)算法
  • 松弛度 = 截止時(shí)間 - 完成該任務(wù)所需要的時(shí)間 - 當(dāng)前時(shí)間
  • 松弛程度越低越先調(diào)度

產(chǎn)生死鎖的原因和必要條件

死鎖：多個(gè)進(jìn)程在運(yùn)行過程中因爭(zhēng)奪資源而造成的一種僵局，在沒有外力的作用下，它們都無法再向前進(jìn)

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

• 競(jìng)爭(zhēng)資源：共享資源數(shù)量不足以滿足進(jìn)程的需要
• 進(jìn)程間的推進(jìn)順序非法：請(qǐng)求和釋放資源的順序不當(dāng)

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

• 互斥條件：一段時(shí)間內(nèi)某個(gè)資源只能被一個(gè)進(jìn)程占用
• 請(qǐng)求和釋放：進(jìn)程至少擁有一個(gè)資源，并且又請(qǐng)求了其他資源
• 不剝奪資源：進(jìn)程已經(jīng)擁有的資源，在未使用完之前，不能別剝奪，只能使用完自己釋放
• 環(huán)路等待：發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程-資源的環(huán)形鏈

預(yù)防死鎖的產(chǎn)生

所謂預(yù)防死鎖，其實(shí)就是破壞產(chǎn)生死鎖的四個(gè)必要條件之一，使得死鎖條件不成立，從而達(dá)到預(yù)防死鎖的目的

• 摒棄請(qǐng)求和保持條件：一次性申請(qǐng)所需要的全部資源，只要有一種資源不滿足，則先等待
  • 缺點(diǎn)：資源利用率低，進(jìn)程延遲運(yùn)行
• 摒棄不剝奪條件：當(dāng)一個(gè)進(jìn)程申請(qǐng)資源不滿足時(shí)，釋放自己擁有的所有資源，以后重新申請(qǐng)
  • 缺點(diǎn)：復(fù)雜、代價(jià)大
• 摒棄環(huán)路等待條件：所有資源進(jìn)行線性排隊(duì)，賦予不同的序號(hào)，請(qǐng)求資源時(shí)，只能按照資源序號(hào)遞增的次序提出
  • 缺點(diǎn)：資源序號(hào)必須穩(wěn)定、限制編程的簡單性

避免死鎖的產(chǎn)生

把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)處理安全狀態(tài)，就可以避免死鎖

• 安全狀態(tài)

  • 允許系統(tǒng)動(dòng)態(tài)地申請(qǐng)資源，但系統(tǒng)在進(jìn)行資源分配之前，應(yīng)先計(jì)算此次資源分配的安全性
  • 安全狀態(tài)：系統(tǒng)能按照某種進(jìn)程順序(p1, p2, p3, ...)稱其為安全序列來為每個(gè)進(jìn)程Pj分配其所需要的資源

• 銀行家算法 -- 避免死鎖的有效方法

  • 數(shù)據(jù)結(jié)構(gòu)
    • 可利用資源向量 Available：m個(gè)元素的數(shù)組，初始值為系統(tǒng)中所分配的該類全部可用資源的數(shù)目
    • 最大需求矩陣 Max：n*m矩陣，定義了n個(gè)進(jìn)程中每個(gè)進(jìn)程對(duì)m類資源的最大需求
    • 分配矩陣 Allocation：n*m矩陣，定義了系統(tǒng)中每一類資源當(dāng)前已經(jīng)分配給進(jìn)程的資源數(shù)
    • 需求矩陣 Need：n*m矩陣，用于表示每一個(gè)進(jìn)程尚需的各類資源數(shù)
    • Need[i, j] = Max[i, j] - Allocation[i, j]
  • 銀行家算法
    • 假設(shè)：Ri是進(jìn)程Pi的請(qǐng)求向量，若Ri[j] = k， 則表示Pi需要k個(gè)Rj類型的資源
    1. 如果Ri[j] <= Need[i, j]，則轉(zhuǎn)向2，否則出錯(cuò)：請(qǐng)求資源多于需要的資源
    2. 如果Ri[j] <= Available[j]，轉(zhuǎn)向3，否則，表示目前暫無資源可用，Pi需要等待
    3. 系統(tǒng)嘗試分配資源給Pi，并且修改下面信息
    • Available[j]：= Avaliale[j] - Ri[j]
    • Allocation[i,j] = Allcation[i, j] + Ri[j]
    • Need[i, j] = Need[i, j] - Ri[j]
    4. 執(zhí)行安全性算法，檢查此次分配后系統(tǒng)是否處于安全狀態(tài)，如果安全，才真正將資源分配給進(jìn)程Pi，否則，將資源恢復(fù)為原來的狀態(tài)，讓Pi等待
  • 安全性算法
    1. 設(shè)置兩個(gè)向量
    • 工作向量Work，表示系統(tǒng)可提供給進(jìn)程所需的各類資源數(shù)目，含有m個(gè)元素，開始時(shí)，Work：= Available
    • Finish，表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成，初始值為Finish[i]：= false，當(dāng)有足夠資源時(shí)，再令Finish[i]：= true
    2. 從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程
    • Finish[i]：= false
    • Need[i ,j] <= Work[j]， 若找到，執(zhí)行下面步驟3，否則，執(zhí)行步驟4
    3. 當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出給它的資源
    • Work[j]：= Work[j] + Allocation[i ,j]
    • Finish[i]：= true
    • 繼續(xù)執(zhí)行步驟2
    4. 如果所有的Finish[i] = true 滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)

  • 案例

    
    
    t0時(shí)刻資源分配情況
    
    

    求問t0時(shí)刻的安全性：

    
    
    一種可行的分配順序
    
    從而可以得出一種滿足條件的順序，也就是說明當(dāng)前狀態(tài)是安全的
    如果P1發(fā)出請(qǐng)求向量req(1, 0, 2)，問是否可以分配
    

    先檢查 req(1, 0, 2) <= Need(1, 2, 2) 滿足，
    再檢查req(1, 0, 2) <= Available(3, 3, 2) 滿足，嘗試將該請(qǐng)求的資源進(jìn)行分配，然后重新計(jì)算一下能否滿足安全算法即可，這里省略

死鎖的檢測(cè)與解除

• 資源分配圖：圓圈代表進(jìn)程，方框代表資源，方框中的點(diǎn)代表資源的數(shù)量
• 死鎖定理：如果能將該資源分配圖簡化到所有的節(jié)點(diǎn)都是孤立節(jié)點(diǎn)，則說明不存在死鎖，否則，存在死鎖

死鎖解除

• 剝掉資源：從其他進(jìn)程剝奪資源，分配給死鎖進(jìn)程，使其打破死鎖
• 撤銷進(jìn)程
  • 撤銷所有死鎖進(jìn)程
  • 每次選擇代價(jià)最小的進(jìn)程進(jìn)行撤銷，直至死鎖解除