《OS調(diào)度與死鎖》PPT課件

《《OS調(diào)度與死鎖》PPT課件》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第3章調(diào)度與死鎖操作系統(tǒng)原理與Windows2003實踐教程1第三章　調(diào)度與死鎖3.1處理機調(diào)度3.2調(diào)度算法3.3死鎖3.4死鎖的預(yù)防3.5死鎖的避免和銀行家算法3.6死鎖的檢測與解除3.7Windows2003處理器3.8本章小結(jié)23.1處理器調(diào)度3.1.1調(diào)度的層次3.1.2進程調(diào)度3.1.3調(diào)度隊列模型3調(diào)度的層次高級調(diào)度：也稱作業(yè)調(diào)度中級調(diào)度：即交換調(diào)度低級調(diào)度：也稱進程調(diào)度4processerprocesserRAMmemory高級調(diào)度中級調(diào)度低級調(diào)度5高級調(diào)度也稱為作業(yè)調(diào)度或宏觀調(diào)度高級調(diào)度的時間尺度通常是分

2、鐘、小時或天中級調(diào)度涉及進程在內(nèi)外存間的交換，從存儲器資源管理的角度來看，把進程的部分或全部換出到外存上，可為當前運行進程的執(zhí)行提供所需內(nèi)存空間，將當前進程所需部分換入到內(nèi)存。指令和數(shù)據(jù)必須在內(nèi)存里才能被處理機直接訪問低級調(diào)度也稱微觀調(diào)度，從處理機資源分配的角度來看，處理機需要經(jīng)常選擇就緒進程或線程進入運行狀態(tài)，低級調(diào)度的時間尺度通常是毫秒級的。由于低級調(diào)度算法的頻繁使用，要求在實現(xiàn)時做到高效6處理機的三級調(diào)度7作業(yè)調(diào)度與進程調(diào)度8處理機調(diào)度與進程狀態(tài)轉(zhuǎn)換9進程調(diào)度進程調(diào)度的功能記錄系統(tǒng)中所有進程的狀態(tài)、優(yōu)先數(shù)和資源需求確

3、定調(diào)度算法分配處理器給進程10進程調(diào)度的時機：正在執(zhí)行的進程執(zhí)行完畢執(zhí)行進程調(diào)用阻塞原語將自己阻塞起來變?yōu)樽枞麪顟B(tài)執(zhí)行進程調(diào)用P操作，因資源不足而被阻塞；或調(diào)用V操作激活了等待資源的進程隊列。執(zhí)行進程提出I/O請求，被阻塞分時系統(tǒng)中時間片用完執(zhí)行系統(tǒng)調(diào)用完畢，由系統(tǒng)程序返回用戶進程時，可認為系統(tǒng)進程執(zhí)行完畢，從而可調(diào)度選擇一新的用戶進程執(zhí)行。11調(diào)度隊列模型具有一級調(diào)度的調(diào)度隊列模型12兩級調(diào)度簡化隊列圖13具有高、低兩級調(diào)度的調(diào)度隊列模型14具有三級調(diào)度的調(diào)度隊列模型153.2調(diào)度算法3.2.1算法的衡量3.2.2先來先

4、服務(wù)調(diào)度算法3.2.3短者優(yōu)先調(diào)度算法3.2.4最短剩余時間優(yōu)先調(diào)度算法3.2.5最高響應(yīng)比優(yōu)先調(diào)度算法3.2.6時間片輪轉(zhuǎn)法3.2.7優(yōu)先級調(diào)度算法3.2.8多級反饋隊列調(diào)度算法16確定調(diào)度策略時應(yīng)考慮的主要因素：所用算法應(yīng)保證實現(xiàn)系統(tǒng)的設(shè)計目標公平性原則均衡使用資源兼顧響應(yīng)時間和資源利用率基于相對優(yōu)先級，但避免無限延期系統(tǒng)開銷不應(yīng)大大17算法的衡量常用的評價準則包括：CPU利用率吞吐量周轉(zhuǎn)時間就緒等待時間響應(yīng)時間18CPU利用率：CPU利用率＝CPU有效工作時間／CPU總運行時間CPU總運行時間＝CPU有效工作時間＋C

5、PU空閑時間19吞吐量：單位時間內(nèi)CPU完成作業(yè)的數(shù)量20周轉(zhuǎn)時間：Ti＝tci－tsi其中，tsi表示作業(yè)i的提交時間，即作業(yè)i到達系統(tǒng)的時間；tci表示作業(yè)i的完成時刻平均周轉(zhuǎn)時間：21就緒等待時間：作業(yè)在就緒隊列中的等待時間22響應(yīng)時間：從提交第一個請求到產(chǎn)生第一個響應(yīng)所用的時間23先來先服務(wù)調(diào)度算法實現(xiàn)思想：“排隊買票”，即按照作業(yè)到達系統(tǒng)或是進程進入就緒隊列的先后次序作為選擇依據(jù)就緒隊列（后備隊列）按照進入的先后次序為序，選擇時選取隊列的隊首進程（作業(yè)）24【例3-1】假設(shè)一個系統(tǒng)有5個進程P1、P2、P3、P4

6、、P5，已知它們的到達時間和運行時間，用FCFS算法進行調(diào)度。2526周轉(zhuǎn)時間/服務(wù)時間27FCFS的優(yōu)點：簡單、容易實現(xiàn)有利于長進程（作業(yè)），不利于短進程（作業(yè)）有利于CPU型作業(yè)，不利于I/O型作業(yè)FCFS的缺點：屬于不可搶占策略，表面上對于所有的作業(yè)和進程都是公平的，但系統(tǒng)吞吐量不大，效率較低28短者優(yōu)先調(diào)度算法實現(xiàn)思想：從就緒隊列中挑選所需的運行時間（估計時間）最短的進程（作業(yè)）運行就緒隊列（后備隊列）按照進程（作業(yè)）的運行為序，選擇時選取隊列的隊首進程（作業(yè)）即為最短者，新來的進程（作業(yè)）依據(jù)運行時間的長短插入到

7、隊列的合適位置。29【例3-2】設(shè)系統(tǒng)中有5個進程中A，B，C，D，E，它們到來的時間依次為0，1，2，3，4，運行時間依次為4，3，5，2，4，試用FCFC算法和短者優(yōu)先調(diào)度算法調(diào)度。FCFS：進程的執(zhí)行順序依次為A→B→C→D→ESJF：進程的執(zhí)行順序依次為A→D→B→E→C。3031SJF（SPF）的優(yōu)點：簡單、容易實現(xiàn)有利于短進程（作業(yè)），不利于長進程（作業(yè)）有利于保障系統(tǒng)吞吐量SJF（SPF）的缺點：對于長進程（作業(yè)）是不公平的32最短剩余時間優(yōu)先調(diào)度算法實現(xiàn)思想：讓運行到進程完成時所需運行時間最短的進程優(yōu)先得到

8、處理，其中包括新進入系統(tǒng)的進程。就緒隊列（后備隊列）按照進程（作業(yè)）的剩余運行時間的長短為序，選擇時選取隊列的隊首進程（作業(yè)）即為最短者，新入隊的進程（作業(yè)）依據(jù)剩余運行時間的長短插入到隊列的合適位置。33優(yōu)點：可以用于分時系統(tǒng)，保證及時響應(yīng)用戶要求屬于可搶占策略，使短進程一進入系統(tǒng)就能立即得到服務(wù)，從