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

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

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

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

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

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

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

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

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

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