操作系统原理之进程调度与死锁(三)
一、進程調度的功能與時機
進程調度：進程調度的功能由操作系統(tǒng)的進程調度程序完成
具體任務：按照某種策略和算法從就緒態(tài)進程中為當前空閑的CPU選擇在其上運行的新進程。
進程調度的時機：進程正常或異常結束、進程阻塞、有更高優(yōu)先級進程到來、時間?用完時都會導致進程調度。
二、進程調度算法
進程調度算法是指從就緒態(tài)的進程隊列中，選擇一個或幾個進程為期分配cpu。
什么樣的算法是好的算法？
- 周轉時間短：作業(yè)從提交給系統(tǒng)開始，到作業(yè)完成，花費時間短
? ? ? ?
? ? ? ? ? ? ? ?
?
- 響應時間快：從用戶提交作業(yè)開始，到系統(tǒng)開始響應，花費時間短
- 截止時間的保證：保證作業(yè)在“開始截止時間”前開始，在“完成截止時間”前完成
- 系統(tǒng)吞吐量高：系統(tǒng)在單位時間內完成的作業(yè)量多
- 處理機利用率好：CPU的利用率盡可能高
進程調度算法：
先來先服務調度算法（FCFS） ：從就緒隊列的隊首選擇最先到達就緒隊列的進程，為該進程分配CPU
周轉時間=進程的周轉時間
系統(tǒng)平均周轉時間=所有進程的周轉時間之和，然后除以進程個數(shù)
?帶全平均周轉時間w=每個進程的周轉時間除以該進程的服務時間，然后相加，最后除以進程個數(shù)
缺點：服務時間段的進程等待時間較長，整個周轉時間較長。
?
短進程優(yōu)先調度算法（SPF）：從就緒隊列中選擇估計運行時間最短的進程，為該進程分配CPU
?優(yōu)點 ：與FCFS算法相比，短進程優(yōu)先算法能有效降低進程的平均等待時間，提高系統(tǒng)吞吐量
? 缺點： 對長進程不利；不能保證緊迫進程的處理；進程長短由用戶估計，不一定準確。
優(yōu)先權調度算法：統(tǒng)將CPU分配給就緒隊列中優(yōu)先權最高的進程?
- 非搶占式：運行期間，有更高優(yōu)先權的進程到來，也不能剝奪CPU
- 搶占式：運行期間，有更高優(yōu)先權的進程到來，就可以搶占CPU
優(yōu)先權類型
- 靜態(tài)優(yōu)先權：創(chuàng)建時確定，運行期間保持不變?
- 動態(tài)優(yōu)先權：創(chuàng)建時確定，隨著進程推進或等待時間增加而改變
該算法存在的問題：無窮阻塞(饑餓問題)；解決的方案（老化技術）：增加等待時間很長的進程的優(yōu)先權?
時間片輪轉調度算法（RR）：
系統(tǒng)將所有就緒進程按先來先服務的原則，排成一個隊列，每次調度時把CPU分給隊首進程，并令其執(zhí)行一個時間片。當時間片用完時，調度程序終止當前進程的執(zhí)行，并將它送到就緒隊列的隊尾。
?
?
1、時間片?小確定時
T=Nq? ? ? ?T:系統(tǒng)響應時間? ? ? ? N:進程數(shù)量? ? ?q:時間片
- 系統(tǒng)對響應時間的要求：響應時間要求越短，時間片越小
- 就緒隊列中進程的數(shù)目：進程數(shù)量越多，時間片越小
- 系統(tǒng)的處理能力：處理能力越好，時間片越小
【例】進程A、B、C、D需要運行的時間分別為20ms、10 ms、15 ms、5 ms，均在0時刻到達。到達的先后次序為A、B、C、D。如果時間片分別為1 ms和5ms，計算各個進程的帶權周轉時間和平均帶權周轉時間。
?
?
?
多級隊列調度算法：將就緒隊列分成多個獨?隊列，每個隊列有自己的調度算法
優(yōu)先級高隊列??p1 、p2、 p3 、p4? ? ?
優(yōu)先級低隊列??p5、 p6 、p7? ? ? ? ? ? ?
多級反饋隊列調度算法：建立多個優(yōu)先權不同的就緒隊列，每個隊列有大小不同的時間片
?隊列優(yōu)先權越高，時間片越短
?隊列優(yōu)先權越低，時間片越長
?
?三、實時系統(tǒng)中的調度
實現(xiàn)實時調度的基本條件：
1、提供必要的調度信息：就緒時間 、開始截止時間 、完成截止時間、處理時間、 資源要求 、優(yōu)先級
2、系統(tǒng)處理能力強：假定系統(tǒng)中有m個周期性的實時進程，它們的處理時間可表示為Ci，周期時間表示為Pi，則在單處理機情況下，必須滿足如下公式的限制條件：
?
?
3、采用搶占式調度機制(使用最廣泛的方式)
4、具有快速切換機制：? ?對外部中斷的快速響應能力? ??快速的進程切換能力
?
常用的實時調度算法：
?1、最早截止時間優(yōu)先算法EDF（淘寶&京東）：開始截止時間越早，進程優(yōu)先級越高，越優(yōu)先獲得CPU
?
?2、最低松弛度優(yōu)先算法LLF：根據(jù)實時進程的緊迫程度來進行調度的算法
四、進程切換
進程切換的含義：當前正在執(zhí)行的進程成為被替換進程，讓出其所使?的CPU，以運行被進程調度程序選中的新進程。
進程切換的步驟：
- 保存包括程序計數(shù)?和其他寄存?在內的CPU上下文環(huán)境
- 更新被替換進程的進程控制塊
- 修改進程狀態(tài)，把執(zhí)行態(tài)改為就緒態(tài)或阻塞態(tài)
- 將被替換進程的進程控制塊移到就緒隊列或阻塞隊列
- 執(zhí)行通過進程調度程序選擇的新進程，并更新該進程的進程控制塊
- 更新內存管理的數(shù)據(jù)結構
- 恢復被調度程序選中的進程的硬件上下文
五、 多處理器調度
1、多處理?系統(tǒng)的類型：
- 緊密耦合??共享主存儲?和I/O設備
- 松弛耦合??有各自的存儲?和I/O設備
- 對稱??處理單元功能和結構相同
- 非對稱??有多種類型的處理單元??一個主處理?，多個從處理?
2、多處理?系統(tǒng)的進程分配方式:
? ?對稱系統(tǒng)分配方式:
? ? 靜態(tài)分配：就緒隊列的進程只能在與就緒隊列對應的處理?上運行。
動態(tài)分配：進程隨機地被分配到當時處于空閑狀態(tài)的某一處理?上執(zhí)行。
? ?對稱系統(tǒng)分配方式：主-從式分配方式（大多采用）
3、進程（線程）的調度方式
?調度? ?最常用最簡單的方式：采?自調度的系統(tǒng)中設置有一個公共的就緒隊列，任何一個空閑的處理?都可以自行從該就緒隊列中選取一個進程或者一個線程運行。
?
?
?
?
?成組調度
?
?
?
專?處理?分配
六、 死鎖
死鎖的定義：由于多個進程競爭共享資源而引起的進程不能向前推進的僵死狀態(tài)稱為死鎖
產(chǎn)生死鎖的原因：競爭共享資源且分配資源的順序不當
1、產(chǎn)生死鎖的必要條件
- 互斥條件：只有一個資源，要么你用，要么我用
- 請求和保持條件：必須保持自己的條件，不能相讓
- 不剝奪條件：不能搶占他人資源
- 環(huán)路等待條件：
2、處理死鎖的基本方法
- 死鎖的預防 通過破壞死鎖的產(chǎn)生條件來保證不發(fā)生死鎖
- 死鎖的檢測? ? ? ? 檢測當前系統(tǒng)是否出現(xiàn)死鎖
- 死鎖的避免? ? ? ? 通過算法合理分配資源來保證不發(fā)生死鎖
- 死鎖的解除? ? ? ? 檢測到系統(tǒng)有死鎖后進行解除
處理死鎖的基本方法有：預防死鎖、避免死鎖、檢測并解除死鎖和忽略死鎖問題
?
###############################處理死鎖的基本方法詳解###########################
1、死鎖的預防
?
?
?2、死鎖的避免
?
?
?例如：
?
?
?
銀行家算法：一個進程提出資源請求后，系統(tǒng)先進行資源的試分配，分配后檢測系統(tǒng)是否安全。銀行家算法的實質是避免系統(tǒng)進入不安全狀態(tài)。
例如：5個進程p0、p1、p2、p3、p4 3種類型的資源A、B、C?
?
?
?
?
3、死鎖的檢測
何時調用檢測算法
- 死鎖可能發(fā)生的頻率 ，發(fā)生頻率很高時需要檢測
- 死鎖發(fā)生時受影響的進程數(shù)量，受影響的進程數(shù)量較多
資源分配圖
?
?系統(tǒng)初始化時分配給p1兩個資源，p1又主動請求一個資源
系統(tǒng)初始化時分配給p2兩個資源，p2又主動請求一個資源
?
死鎖定理
用于檢測系統(tǒng)所處的資源分配狀態(tài)是否為死鎖狀態(tài)
? ? ? S為死鎖狀態(tài)的充分條件是當且僅當S狀態(tài)的資源分配圖是不可完全簡化的，即資源分配圖是不是可以把申請資源的線全部消掉。
?
?4、死鎖的解除
解除途徑
- 進程終止? ?終止所有死鎖進程；一次只終止一個處于死鎖的進程，直到死鎖解除
- 資源搶占? ?逐步從進程中搶占資源給其他進程使用，直到死鎖被打破為止
?
轉載于:https://www.cnblogs.com/jalja/p/11432035.html
總結
以上是生活随笔為你收集整理的操作系统原理之进程调度与死锁(三)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 扫描枪连接zebra打印机打印条码标签无
- 下一篇： 农行k宝申请信用卡秒拒？顺利批卡有妙招