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

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

1、第三章處理機調(diào)度與死鎖3.1處理機調(diào)度的基本概念3.1.1高級、中級和低級調(diào)度1.高級調(diào)度(HighScheduling)又稱作業(yè)調(diào)度、長程調(diào)度：決定把外存上處于后備隊列中的哪些作業(yè)調(diào)入內(nèi)存，并為之創(chuàng)建進程、分配必要的資源，然后，再將新創(chuàng)建的進程排在就緒隊列中。1.高級調(diào)度(HighScheduling)批處理系統(tǒng)：需作業(yè)調(diào)度分時系統(tǒng)：無需作業(yè)調(diào)度實時系統(tǒng)：通常無需作業(yè)調(diào)度在每次執(zhí)行作業(yè)調(diào)度時，都須做出以下兩個決定：1)接納多少個作業(yè)2)接納哪些作業(yè)1.高級調(diào)度(HighScheduling)2.低級調(diào)

2、度(LowLevelScheduling)進程調(diào)度、短程調(diào)度：決定就緒隊列中哪個進程應(yīng)獲得處理機，然后再由分派程序執(zhí)行把處理機分配給該進程的具體操作。三種類型的OS均需配置進程調(diào)度2.低級調(diào)度(LowLevelScheduling)進程調(diào)度方式：1)非搶占方式(Non-preemptiveMode)進程一旦獲得CPU則一直執(zhí)行，直至完成或被阻塞。采用非搶占方式，引起進程調(diào)度的因素：①正在執(zhí)行的進程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行；②執(zhí)行中的進程因提出I/O請求而暫停執(zhí)行；③在進程通信或同步過程中

3、執(zhí)行了某種原語操作，如P操作(wait操作)、Block原語、Wakeup原語等。2)搶占方式(PreemptiveMode)正在執(zhí)行的進程可以被中途剝奪CPU使用權(quán)進程調(diào)度方式搶占的原則有：優(yōu)先權(quán)原則。(2)短作業(yè)(進程)優(yōu)先原則(3)時間片原則。3.中級調(diào)度(Intermediate-LevelScheduling)中級調(diào)度又稱中程調(diào)度(Medium-TermScheduling)。引入的主要目的：是為了提高內(nèi)存利用率和系統(tǒng)吞吐量（存儲器管理的對換）中程調(diào)度：將那些暫時不能運行的進程不再占用寶貴的內(nèi)

4、存資源，而將它們調(diào)至外存上去等待，把此時的進程狀態(tài)稱為就緒駐外存狀態(tài)或掛起狀態(tài)。當這些進程重又具備運行條件、且內(nèi)存又稍有空閑時，由中級調(diào)度來決定把外存上的哪些又具備運行條件的就緒進程，重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊列上等待進程調(diào)度。3.1.2調(diào)度隊列模型1.僅有進程調(diào)度的調(diào)度隊列模型2.具有高級和低級調(diào)度的調(diào)度隊列模型(1)就緒隊列的形式：優(yōu)先權(quán)隊列、無序鏈表等(2)設(shè)置多個阻塞隊列：每個隊列對應(yīng)于某一種進程阻塞事件該模型與上一模型的主要區(qū)別在于如下兩個方面：2.具有高級和低級調(diào)度的調(diào)度

5、隊列模型3.同時具有三級調(diào)度的調(diào)度隊列模型3.1.3選擇調(diào)度方式和調(diào)度算法的若干準則1.面向用戶的準則(1)周轉(zhuǎn)時間短。周轉(zhuǎn)時間的長短是評價批處理系統(tǒng)性能、選擇作業(yè)調(diào)度方式與算法的重要準則之一周轉(zhuǎn)時間：從作業(yè)提交給系統(tǒng)開始，到作業(yè)完成為之的這段時間間隔（作業(yè)周轉(zhuǎn)時間）作業(yè)在外存后備隊列上等待（作業(yè)）調(diào)度的時間進程在就緒隊列上等待進程調(diào)度的時間進程在CPU上執(zhí)行的時間進程等待I/O操作完成的時間(1)周轉(zhuǎn)時間短。平均周轉(zhuǎn)時間：帶權(quán)周轉(zhuǎn)時間：W=T/TS平均帶權(quán)周轉(zhuǎn)時間:(1)周轉(zhuǎn)時間短。(2)響應(yīng)時間快響應(yīng)

6、時間的長短是評價分時系統(tǒng)性能、選擇分時系統(tǒng)中進程調(diào)度算法的重要準則之一響應(yīng)時間：用戶通過鍵盤提交一個請求開始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時間，或者說直至屏幕上顯示出結(jié)果為止的一段時間間隔鍵盤輸入的請求信息傳送到處理機的時間處理機對請求信息進行處理的時間形成的響應(yīng)信息回送到終端顯示器的時間(3)截止時間的保證截止時間是評價實時系統(tǒng)性能的重要指標，是選擇實時調(diào)度算法的重要準則截止時間：某任務(wù)必須開始執(zhí)行的最遲時間或必須完成的最遲時間(4)優(yōu)先權(quán)準則三種系統(tǒng)均可應(yīng)用本準則2.面向系統(tǒng)的準則(1)系統(tǒng)吞吐量高評

7、價批處理系統(tǒng)吞吐量：單位時間內(nèi)所完成的作業(yè)數(shù)(2)處理機利用率好大中型系統(tǒng)中要考慮(3)各類資源的平衡利用大中型系統(tǒng)中要考慮3.2調(diào)度算法調(diào)度算法：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法3.2.1先來先服務(wù)和短作業(yè)(進程)優(yōu)先調(diào)度算法1.先來先服務(wù)（FCFS）調(diào)度算法特點：可用于作業(yè)調(diào)度、也可用于進程調(diào)度利于長作業(yè)（進程）、不利于短作業(yè)（進程）利于CPU繁忙型作業(yè)，不利于I/O繁忙型的作業(yè)(進程)FCFS實例1.先來先服務(wù)調(diào)度算法平均周轉(zhuǎn)時間：平均帶權(quán)周轉(zhuǎn)時間2.短作業(yè)(進程)優(yōu)先調(diào)度算法短作業(yè)優(yōu)先(

8、SJF)調(diào)度算法：從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)存運行。短進程優(yōu)先(SPF)調(diào)度算法：從就緒隊列中選出一估計運行時間最短的進程，將處理機分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機時，再重新調(diào)度。平均周轉(zhuǎn)時間：帶權(quán)周轉(zhuǎn)時間：W=T/TS平均帶權(quán)周轉(zhuǎn)時間:優(yōu)點：有效的降低作業(yè)的平均等待時間，提高了系統(tǒng)的吞吐量。缺點：對長作業(yè)不利完全未考慮作業(yè)的緊迫程度作業(yè)的運行時間不