第3章處理機(jī)調(diào)度_第1頁
第3章處理機(jī)調(diào)度_第2頁
第3章處理機(jī)調(diào)度_第3頁
第3章處理機(jī)調(diào)度_第4頁
第3章處理機(jī)調(diào)度_第5頁
已閱讀5頁,還剩144頁未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

操作系統(tǒng)院(系):計算機(jī)科學(xué)與技術(shù)學(xué)院研究室:軟件支持技術(shù)教師:王紅濱第三章處理機(jī)調(diào)度與死鎖2025/1/141內(nèi)容概述3.1處理機(jī)調(diào)度的基本概念3.2調(diào)度算法

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

3.4多處理機(jī)系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測與解除操作系統(tǒng)中離不開調(diào)度。處理機(jī)是計算機(jī)系統(tǒng)中最為重要的資源之一。處理機(jī)調(diào)度的主要任務(wù)是分配處理機(jī)。在多道程序環(huán)境下,進(jìn)程數(shù)目通常多于處理機(jī)的數(shù)目。系統(tǒng)必須按一定方法動態(tài)地把處理機(jī)分配給就緒隊列中的一個進(jìn)程。處理機(jī)利用率和系統(tǒng)性能(吞吐量、響應(yīng)時間)在很大程度上取決于處理機(jī)調(diào)度。2025/1/1423.1處理機(jī)調(diào)度的基本概念3.1.1高級、中級和低級調(diào)度3.1.2調(diào)度隊列模型3.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則2025/1/1433.1.1高級、中級和低級調(diào)度1.高級調(diào)度(HighScheduling)又稱為作業(yè)調(diào)度或長程調(diào)度(Long-TermScheduling)將外存上處于后備隊列上的作業(yè)調(diào)入內(nèi)存,并創(chuàng)建進(jìn)程、分配資源,安排在就緒隊列上有時也稱為接納調(diào)度(AdmissionScheduling)2025/1/1441.高級調(diào)度(HighScheduling)在每次執(zhí)行作業(yè)調(diào)度時,都須做出以下兩個決定。(1)接納多少個作業(yè)取決于多道程序度(DegreeofMultiprogramming),即允許多少個作業(yè)同時在內(nèi)存中運(yùn)行作業(yè)太少資源利用率低作業(yè)太多服務(wù)質(zhì)量下降(2)接納哪些作業(yè)作業(yè)調(diào)度算法先來先服務(wù)短作業(yè)優(yōu)先優(yōu)先權(quán)高優(yōu)先2025/1/1452.低級調(diào)度(LowLevelScheduling)也稱為進(jìn)程調(diào)度或短程調(diào)度(Short-TermScheduling),決定就緒隊列中的哪個進(jìn)程應(yīng)獲得處理機(jī)。常見的低級調(diào)度有非搶占方式和搶占方式兩種(1)非搶占方式(Non-preemptiveMode)(非剝奪方式)一旦將處理機(jī)分配給某進(jìn)程,便讓該進(jìn)程一直執(zhí)行,直至該進(jìn)程完成或阻塞時再分配給其他進(jìn)程引起進(jìn)程調(diào)度的因素有以下幾種正在執(zhí)行的進(jìn)程執(zhí)行完畢,或因發(fā)生某事件而不能再繼續(xù)執(zhí)行執(zhí)行中的進(jìn)程因提出I/O請求而暫停執(zhí)行;在進(jìn)程通信或同步過程中執(zhí)行了某種原語操作,如P操作(wait操作)、Block原語等優(yōu)點(diǎn):簡單,系統(tǒng)開銷小缺點(diǎn):不適合時間要求嚴(yán)格的實(shí)時系統(tǒng)2025/1/146(2)搶占方式(PreemptiveMode)(剝奪方式)允許調(diào)度程序根據(jù)某種原則,暫停正在執(zhí)行的進(jìn)程,將處理機(jī)分配給其他進(jìn)程搶占式調(diào)度主要有以下原則①優(yōu)先權(quán)原則:重要作業(yè)賦予高優(yōu)先權(quán),優(yōu)先占用處理機(jī)②短作業(yè)(進(jìn)程)優(yōu)先原則:執(zhí)行時間短的進(jìn)程優(yōu)先執(zhí)行③時間片原則:時間片用完后停止執(zhí)行,適用于分時系統(tǒng)2.低級調(diào)度(LowLevelScheduling)特點(diǎn):它增加了進(jìn)程調(diào)度的次數(shù),增加了系統(tǒng)的開銷,但保證了系統(tǒng)的實(shí)時性2025/1/147中級調(diào)度又稱中程調(diào)度(Medium-TermScheduling)引入中級調(diào)度的主要目的,是為了提高內(nèi)存利用率和系統(tǒng)吞吐量使那些暫時不能運(yùn)行的進(jìn)程不再占用寶貴的內(nèi)存資源,而將它們調(diào)至外存上去等待,把此時的進(jìn)程狀態(tài)稱為就緒駐外存狀態(tài)或掛起狀態(tài)。當(dāng)這些進(jìn)程重又具備運(yùn)行條件、且內(nèi)存又稍有空閑時,由中級調(diào)度來決定把外存上的哪些又具備運(yùn)行條件的就緒進(jìn)程,重新調(diào)入內(nèi)存,并修改其狀態(tài)為就緒狀態(tài),掛在就緒隊列上等待進(jìn)程調(diào)度3.中級調(diào)度(Intermediate-LevelScheduling)對換功能2025/1/148三種調(diào)度總結(jié)運(yùn)行頻率: 低級調(diào)度>中級調(diào)度>高級調(diào)度2025/1/1493.1.1高級、中級和低級調(diào)度3.1.2調(diào)度隊列模型3.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則3.1處理機(jī)調(diào)度的基本概念2025/1/14103.1.2調(diào)度隊列模型1.僅有進(jìn)程調(diào)度的調(diào)度隊列模型在分時系統(tǒng)中,通常僅設(shè)有進(jìn)程調(diào)度,用戶鍵入命令和數(shù)據(jù),都直接進(jìn)入內(nèi)存,系統(tǒng)可以把就緒進(jìn)程組織成一個隊列每個進(jìn)程在執(zhí)行時,可能有以下三種情況

①進(jìn)程在給定時間片內(nèi)已完成,釋放處理機(jī)后為完成狀態(tài)

②進(jìn)程在時間片內(nèi)未完成,進(jìn)入就緒隊列末尾

③進(jìn)程在執(zhí)行期間因某事件而阻塞,進(jìn)入阻塞隊列2025/1/1411圖3-1僅具有進(jìn)程調(diào)度的調(diào)度隊列模型①②③2025/1/14122.具有高級和低級調(diào)度的調(diào)度隊列模型在批處理系統(tǒng)中,不僅需要進(jìn)程調(diào)度,而且還要有作業(yè)調(diào)度該模型與上一模型主要區(qū)別在于:

(1)就緒隊列的形式在批處理系統(tǒng)中,常用優(yōu)先權(quán)隊列。進(jìn)程進(jìn)入就緒隊列時,按優(yōu)先權(quán)高低插入相應(yīng)位置

(2)設(shè)置多個阻塞隊列根據(jù)事件的不同設(shè)置多個隊列提高效率2025/1/1413圖3-2具有高、低兩級調(diào)度的調(diào)度隊列模型①②③2025/1/1414圖3-2’兩級調(diào)度簡化調(diào)度隊列模型圖2025/1/14153.同時具有三級調(diào)度的調(diào)度隊列模型在引入中級調(diào)度后,可把就緒分為內(nèi)存就緒和外存就緒(就緒掛起);阻塞也可分為內(nèi)存阻塞和外存阻塞(阻塞掛起)圖3-3具有三級調(diào)度時的調(diào)度隊列模型①②③2025/1/14163.1處理機(jī)調(diào)度的基本概念3.1.1高級、中級和低級調(diào)度3.1.2調(diào)度隊列模型3.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則2025/1/14173.1.3選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則1.面向用戶的準(zhǔn)則(1)周轉(zhuǎn)時間短??砂哑骄苻D(zhuǎn)時間描述為:作業(yè)的周轉(zhuǎn)時間T與系統(tǒng)為它提供服務(wù)的時間TS之比,即W=T/TS

,稱為帶權(quán)周轉(zhuǎn)時間,而平均帶權(quán)周轉(zhuǎn)時間則可表示為:2025/1/1418面向用戶的準(zhǔn)則……(2)響應(yīng)時間快

①響應(yīng)時間是指從用戶通過鍵盤提交一個請求開始,直至系統(tǒng)中首次產(chǎn)生響應(yīng)為止的時間。②響應(yīng)時間包括鍵盤輸入請求信息傳送到處理機(jī)的時間、處理機(jī)對請求的處理時間和響應(yīng)信息送回到終端的時間(3)截止時間保證

①截止時間是指某任務(wù)必須開始執(zhí)行的最遲時間或必須完成的最遲時間②截止時間是實(shí)時系統(tǒng)中的重要指標(biāo)(4)優(yōu)先權(quán)準(zhǔn)則①在批處理、實(shí)時和分時系統(tǒng)中都可以選擇優(yōu)先權(quán)準(zhǔn)則,以便讓緊急任務(wù)先處理②有時還選擇搶占式調(diào)度方式常用于評價分時系統(tǒng)2025/1/14192.面向系統(tǒng)的準(zhǔn)則

(1)系統(tǒng)吞吐量高吞吐量指單位時間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)作業(yè)調(diào)度的方式和算法對吞吐量的大小有較大影響(2)處理機(jī)利用率高(3)各類資源的平衡利用使內(nèi)存、外存和I/O設(shè)備的利用率高2025/1/1420內(nèi)容概述3.1處理機(jī)調(diào)度的基本概念3.2調(diào)度算法

3.3實(shí)時調(diào)度3.4多處理機(jī)系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測與解除2025/1/1421在OS中調(diào)度的實(shí)質(zhì)是一種資源分配,因而調(diào)度算法是指:根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法對不同的系統(tǒng)和系統(tǒng)目標(biāo),通常采用不同的算法,如短作業(yè)優(yōu)先,時間片輪轉(zhuǎn)等有些算法適用于作業(yè)調(diào)度,有些適用于進(jìn)程調(diào)度,有些兩者皆可2025/1/14223.2調(diào)度算法內(nèi)存總量:100K,采用不移動的可變分區(qū)方式。作業(yè)名進(jìn)入磁盤時間需要服務(wù)時間主存量要求A 10:06 42分 15KB 10:18 30分 60KC 10:30 24分 50KD 10:36 24分 10KE 10:42 12分 20K周轉(zhuǎn)時間=結(jié)束執(zhí)行時間-進(jìn)入磁盤時間帶權(quán)周轉(zhuǎn)時間=周轉(zhuǎn)時間/服務(wù)時間高響應(yīng)比=(等待時間+服務(wù)時間)/服務(wù)時間或=等待時間/服務(wù)時間2025/1/14233.2.1先來先服務(wù)和短作業(yè)優(yōu)先算法3.2.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法3.2.3基于時間片的輪轉(zhuǎn)調(diào)度算法3.2調(diào)度算法2025/1/14243.2.1先來先服務(wù)和短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法1.先來先服務(wù)調(diào)度算法(FCFS)按照作業(yè)進(jìn)入系統(tǒng)的先后次序進(jìn)行調(diào)度,先進(jìn)入系統(tǒng)者先調(diào)度;即啟動等待時間最長的作業(yè)是一種最簡單的調(diào)度算法,即可用于作業(yè)調(diào)度,也可用于進(jìn)程調(diào)度FCFS算法比較有利于長作業(yè)(進(jìn)程),而不利于短作業(yè)(進(jìn)程)2025/1/1425內(nèi)存無限大,作業(yè)調(diào)度和進(jìn)程調(diào)度都采用FCFS作業(yè)名進(jìn)入磁盤需要服務(wù)裝入主存開始執(zhí)行結(jié)束執(zhí)行周轉(zhuǎn)帶權(quán)周轉(zhuǎn) 時間 時間時間時間時間時間時間A 01 B 1 100 C 2 1 D 3 100 執(zhí)行順序:A->B->C->D周轉(zhuǎn)時間=結(jié)束執(zhí)行時間-進(jìn)入磁盤時間帶權(quán)周轉(zhuǎn)時間=周轉(zhuǎn)時間/服務(wù)時間00111131101100121022021991.99101102100100先來先服務(wù)調(diào)度算法(FCFS)平均值:10025.99752025/1/1426內(nèi)存總量:100K,采用不移動的可變分區(qū)方式。作業(yè)調(diào)度和進(jìn)程調(diào)度都采用FCFS作業(yè)名進(jìn)入磁盤需要服務(wù)主存量裝入主存開始執(zhí)行結(jié)束執(zhí)行周轉(zhuǎn)帶權(quán)周轉(zhuǎn) 時間 時間要求時間時間時間時間時間A 10:0642分 15KB 10:18 30分 60KC 10:30 24分 50KD 10:36 24分 10KE 10:42 12分 20K執(zhí)行順序:A->B->D->C->E周轉(zhuǎn)時間=結(jié)束執(zhí)行時間-進(jìn)入磁盤時間帶權(quán)周轉(zhuǎn)時間=周轉(zhuǎn)時間/服務(wù)時間10:0610:0610:4842110:1810:3610:4811:1860211:1811:1811:1811:42662.7511:4212:0696412:0612:18968先來先服務(wù)調(diào)度算法(FCFS)平均值:

723.552025/1/14272.短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P)F短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P)F,以要求運(yùn)行時間長短進(jìn)行調(diào)度,即啟動要求運(yùn)行時間最短的作業(yè)可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度短作業(yè)優(yōu)先(SJF)的調(diào)度算法,是從后備隊列中選擇一個或若干個估計運(yùn)行時間最短的作業(yè),將它們調(diào)入內(nèi)存運(yùn)行;而短進(jìn)程優(yōu)先(SPF)調(diào)度算法,則是從就緒隊列中選出一估計運(yùn)行時間最短的進(jìn)程,將處理機(jī)分配給它,使它立即執(zhí)行并一直執(zhí)行到完成,或發(fā)生某事件而被阻塞放棄處理機(jī)時,再重新調(diào)度2025/1/1428內(nèi)存無限大,作業(yè)調(diào)度和進(jìn)程調(diào)度都采用FCFS作業(yè)名進(jìn)入磁盤需要服務(wù)裝入主存開始執(zhí)行結(jié)束執(zhí)行周轉(zhuǎn)帶權(quán)周轉(zhuǎn) 時間 時間時間時間時間時間時間A 04 B 1 3 C 2 5 D 3 2 E 4 4執(zhí)行順序:A->B->C->D->E作業(yè)調(diào)度FCFS和進(jìn)程調(diào)度都采用SJFA 04 B 1 3 C 2 5 D 3 2 E 4 4周轉(zhuǎn)時間=結(jié)束執(zhí)行時間-進(jìn)入磁盤時間帶權(quán)周轉(zhuǎn)時間=周轉(zhuǎn)時間/服務(wù)時間0044113476221214115.5712102短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P)F41418143.500441136988/324631.513181616/5491399/4平均值:

92.8平均值:

82.1執(zhí)行順序:A->D->B->E->C2025/1/1429內(nèi)存總量:100K,采用不移動的可變分區(qū)方式。作業(yè)調(diào)度采用SJF和進(jìn)程調(diào)度采用FCFS作業(yè)名進(jìn)入磁盤需要服務(wù)主存量裝入主存開始執(zhí)行結(jié)束執(zhí)行周轉(zhuǎn)帶權(quán)周轉(zhuǎn) 時間 時間要求時間時間時間時間時間A 10:0642分 15KB 10:18 30分 60KC 10:30 24分 50KD 10:36 24分 10KE 10:42 12分 20K執(zhí)行順序:A->B->D->E->C周轉(zhuǎn)時間=結(jié)束執(zhí)行時間-進(jìn)入磁盤時間帶權(quán)周轉(zhuǎn)時間=周轉(zhuǎn)時間/服務(wù)時間高響應(yīng)比=(等待時間+服務(wù)時間)/服務(wù)時間或=等待時間/服務(wù)時間10:0610:0610:4842110:1810:3610:4811:1860211:1811:1811:1811:42662.7511:5412:181084.511:4211:54726短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P)F平均值:

69.63.252025/1/1430SJ(P)F調(diào)度算法也存在不容忽視的缺點(diǎn):(1)該算法對長作業(yè)不利,如作業(yè)C的周轉(zhuǎn)時間由10增至16,其帶權(quán)周轉(zhuǎn)時間由2增至3.2。更嚴(yán)重的是,如果有一長作業(yè)(進(jìn)程)進(jìn)入系統(tǒng)的后備隊列(就緒隊列),由于調(diào)度程序總是優(yōu)先調(diào)度那些(即使是后進(jìn)來的)短作業(yè)(進(jìn)程),將導(dǎo)致長作業(yè)(進(jìn)程)長期不被調(diào)度。(2)該算法完全未考慮作業(yè)的緊迫程度,因而不能保證緊迫性作業(yè)(進(jìn)程)會被及時處理。(3)由于作業(yè)(進(jìn)程)的長短只是根據(jù)用戶所提供的估計執(zhí)行時間而定的,而用戶又可能會有意或無意地縮短其作業(yè)的估計運(yùn)行時間,致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。2025/1/14313.2.1先來先服務(wù)和短作業(yè)優(yōu)先算法3.2.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法3.2.3基于時間片的輪轉(zhuǎn)調(diào)度算法3.2調(diào)度算法2025/1/14323.2.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法1.優(yōu)先權(quán)調(diào)度算法的類型(1)非搶占式優(yōu)先權(quán)算法系統(tǒng)一旦把處理機(jī)分配給就緒隊列中優(yōu)先權(quán)最高的進(jìn)程后,該進(jìn)程便一直執(zhí)行下去,直至完成;或因發(fā)生某事件使該進(jìn)程放棄處理機(jī)時,系統(tǒng)方可再將處理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程。主要用于批處理系統(tǒng)中,也可用于某些對實(shí)時性要求不嚴(yán)的實(shí)時系統(tǒng)中。2025/1/1433

(2)搶占式優(yōu)先權(quán)調(diào)度算法系統(tǒng)同樣是把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程,使之執(zhí)行。但在其執(zhí)行期間,只要又出現(xiàn)了另一個其優(yōu)先權(quán)更高的進(jìn)程,進(jìn)程調(diào)度程序就立即停止當(dāng)前進(jìn)程(原優(yōu)先權(quán)最高的進(jìn)程)的執(zhí)行,重新將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程。在采用這種調(diào)度算法時,每當(dāng)系統(tǒng)中出現(xiàn)一個新的就緒進(jìn)程i時,就將其優(yōu)先權(quán)Pi與正在執(zhí)行的進(jìn)程j的優(yōu)先權(quán)Pj進(jìn)行比較。如果Pi≤Pj,原進(jìn)程Pj便繼續(xù)執(zhí)行;但如果是Pi>Pj,則立即停止Pj的執(zhí)行,做進(jìn)程切換,使i進(jìn)程投入執(zhí)行。搶占式的優(yōu)先權(quán)調(diào)度算法,能更好地滿足緊迫作業(yè)的要求,故而常用于要求比較嚴(yán)格的實(shí)時系統(tǒng)中,以及對性能要求較高的批處理和分時系統(tǒng)中。2025/1/14342.優(yōu)先權(quán)的類型1)靜態(tài)優(yōu)先權(quán)

靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時確定的,且在進(jìn)程的整個運(yùn)行期間保持不變。一般地,優(yōu)先權(quán)是利用某一范圍內(nèi)的一個整數(shù)來表示的,例如,0~7或0~255中的某一整數(shù),又把該整數(shù)稱為優(yōu)先數(shù)。只是具體用法各異:有的系統(tǒng)用“0”表示最高優(yōu)先權(quán),當(dāng)數(shù)值愈大時,其優(yōu)先權(quán)愈低;而有的系統(tǒng)恰恰相反。2025/1/1435確定進(jìn)程優(yōu)先權(quán)的依據(jù)有如下三個方面: (1)進(jìn)程類型系統(tǒng)進(jìn)程優(yōu)先級高于用戶進(jìn)程 (2)進(jìn)程對資源的需求執(zhí)行時間短,內(nèi)存要求小的進(jìn)程,有較高優(yōu)先權(quán)。 (3)用戶要求根據(jù)用戶進(jìn)程緊迫程度及用戶所付費(fèi)用的多少來確定。靜態(tài)優(yōu)先權(quán)特點(diǎn):(1)系統(tǒng)簡單易行。(2)系統(tǒng)開銷小。(3)不夠精確。(4)一般用在要求不高的系統(tǒng)中。2025/1/14362)動態(tài)優(yōu)先權(quán)在創(chuàng)建進(jìn)程時所賦予的優(yōu)先權(quán),是可以隨進(jìn)程的推進(jìn)或隨其等待時間的增加而改變的,以便獲得更好的調(diào)度性能。例如,我們可以規(guī)定,在就緒隊列中的進(jìn)程,隨其等待時間的增長,其優(yōu)先權(quán)以速率a提高。若所有的進(jìn)程都具有相同的優(yōu)先權(quán)初值,則顯然是最先進(jìn)入就緒隊列的進(jìn)程,將因其動態(tài)優(yōu)先權(quán)變得最高而優(yōu)先獲得處理機(jī),此即先來先服務(wù)FCFS算法。若所有的就緒進(jìn)程具有各不相同的優(yōu)先權(quán)初值,那么,對于優(yōu)先權(quán)初值低的進(jìn)程,在等待了足夠的時間后,其優(yōu)先權(quán)便可能升為最高,從而可以獲得處理機(jī)當(dāng)采用搶占式優(yōu)先權(quán)調(diào)度算法時,如果再規(guī)定當(dāng)前進(jìn)程的優(yōu)先權(quán)以速率b下降,則可防止一個長作業(yè)長期地壟斷處理機(jī)。2025/1/14373.高響應(yīng)比優(yōu)先調(diào)度算法(HRF)該算法是FCFS和SJF的結(jié)合,克服了兩種算法的缺點(diǎn)響應(yīng)比最高的作業(yè)優(yōu)先啟動由于等待時間與服務(wù)時間之和,就是系統(tǒng)對該作業(yè)的響應(yīng)時間,故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此,又可表示為2025/1/1438作業(yè)名進(jìn)入磁盤時間需要服務(wù)時間響應(yīng)比1響應(yīng)比2A 8:5090分 B 9:00 24分 C 9:30 60分

高響應(yīng)比1=等待時間/服務(wù)時間高響應(yīng)比2=(等待時間+服務(wù)時間)/服務(wù)時間40/90=4/9高響應(yīng)比優(yōu)先調(diào)度算法(40+90)/90=4/9+130/24=5/4(30+24)/24=5/4+10/60=0(0+60)/60=1設(shè)9:30進(jìn)行調(diào)度:作業(yè)名進(jìn)入磁盤時間需要服務(wù)時間響應(yīng)比1響應(yīng)比2A 8:5090分

C 9:30 60分 64/90=32/45(64+90)/90=32/45+124/60=2/5(24+60)/60=2/5+1當(dāng)B執(zhí)行完后,又要在9:54進(jìn)行調(diào)度:√√2025/1/1439對高響應(yīng)比優(yōu)先調(diào)度算法(HRF)的解釋(1)如果作業(yè)的等待時間相同,則要求服務(wù)的時間愈短,其優(yōu)先權(quán)愈高,因而該算法有利于短作業(yè)。(2)當(dāng)要求服務(wù)的時間相同時,作業(yè)的優(yōu)先權(quán)決定于其等待時間,等待時間愈長,其優(yōu)先權(quán)愈高,因而它實(shí)現(xiàn)的是先來先服務(wù)。(3)對于長作業(yè),作業(yè)的優(yōu)先級可以隨等待時間的增加而提高,當(dāng)其等待時間足夠長時,其優(yōu)先級便可升到很高,從而也可獲得處理機(jī)。高響應(yīng)比1=等待時間/服務(wù)時間2025/1/14403.2.1先來先服務(wù)和短作業(yè)優(yōu)先算法3.2.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法3.2.3基于時間片的輪轉(zhuǎn)調(diào)度算法3.2調(diào)度算法2025/1/14413.2.3基于時間片的輪轉(zhuǎn)調(diào)度算法1.時間片輪轉(zhuǎn)法在早期的時間片輪轉(zhuǎn)法中,系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)的原則,排成一個隊列,每次調(diào)度時,把CPU分配給隊首進(jìn)程,并令其執(zhí)行一個時間片,時間片的大小從幾ms到幾百ms當(dāng)執(zhí)行的時間片用完時,由一個計時器發(fā)出時鐘中斷請求,調(diào)度程序便據(jù)此信號來停止該進(jìn)程的執(zhí)行,并將它送往就緒隊列的末尾;然后,再把處理機(jī)分配給就緒隊列中新的隊首進(jìn)程,同時也讓它執(zhí)行一個時間片可以保證就緒隊列中的所有進(jìn)程,在一給定的時間內(nèi),均能獲得一時間片的處理機(jī)執(zhí)行時間2025/1/1442內(nèi)存無限大。作業(yè)調(diào)度采用FCFS和進(jìn)程調(diào)度采用時間片的輪轉(zhuǎn)q=1作業(yè)進(jìn)入需要裝入開始執(zhí)行執(zhí)行開始執(zhí)行執(zhí)行開始執(zhí)行執(zhí)行開始執(zhí)行執(zhí)行完成周轉(zhuǎn)帶權(quán)名 磁盤服務(wù)主存執(zhí)行時間后執(zhí)行時間后執(zhí)行時間后執(zhí)行時間后周轉(zhuǎn)A04 B13 C24 D32 E44 完成順序:D->B->A->C->E周轉(zhuǎn)時間=結(jié)束執(zhí)行時間-進(jìn)入磁盤時間帶權(quán)周轉(zhuǎn)時間=周轉(zhuǎn)時間/服務(wù)時間高響應(yīng)比=(等待時間+服務(wù)時間)/服務(wù)時間或=等待時間/服務(wù)時間001131124312141時間片的輪轉(zhuǎn)平均值:

11.83.431243556879111116798101011121311111112131414151611115161796312113.6715153.7517133.2516143.5第三版書27次印刷,新來進(jìn)程排在隊頭第三版書30多次印刷,新來進(jìn)程排在隊尾2025/1/1443內(nèi)存無限大。作業(yè)調(diào)度采用FCFS和進(jìn)程調(diào)度采用時間片的輪轉(zhuǎn)q=4作業(yè)進(jìn)入需要裝入開始執(zhí)行執(zhí)行開始執(zhí)行執(zhí)行開始執(zhí)行執(zhí)行開始執(zhí)行執(zhí)行完成周轉(zhuǎn)帶權(quán)名 磁盤服務(wù)主存執(zhí)行時間后執(zhí)行時間后執(zhí)行時間后執(zhí)行時間后周轉(zhuǎn)A04 B13 C24 D32 E44 完成順序:A->B->C->D->E周轉(zhuǎn)時間=結(jié)束執(zhí)行時間-進(jìn)入磁盤時間帶權(quán)周轉(zhuǎn)時間=周轉(zhuǎn)時間/服務(wù)時間高響應(yīng)比=(等待時間+服務(wù)時間)/服務(wù)時間或=等待時間/服務(wù)時間00413432411274134時間片的輪轉(zhuǎn)平均值:

8.42.7471311171310576244117133.251192.25第三版書27次印刷,新來進(jìn)程排在隊尾2025/1/1444圖3-7多級反饋隊列調(diào)度算法2.多級反饋隊列調(diào)度算法優(yōu)先級高2025/1/1445設(shè)置多個就緒隊列,并為各個隊列賦予不同的優(yōu)先級第一個隊列的優(yōu)先級最高,第二個隊列次之,其余各隊列的優(yōu)先權(quán)逐個降低。該算法賦予各個隊列中進(jìn)程執(zhí)行時間片的大小也各不相同,在優(yōu)先權(quán)愈高的隊列中,為每個進(jìn)程所規(guī)定的執(zhí)行時間片就愈小。例如,第二個隊列的時間片要比第一個隊列的時間片長一倍,……,第i+1個隊列的時間片要比第i個隊列的時間片長一倍。調(diào)度方式當(dāng)一個新進(jìn)程進(jìn)入內(nèi)存后,首先將它放入第一隊列的末尾,按FCFS原則排隊等待調(diào)度當(dāng)輪到該進(jìn)程執(zhí)行時,如它能在該時間片內(nèi)完成,便可準(zhǔn)備撤離系統(tǒng);如果它在一個時間片結(jié)束時尚未完成,調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第二隊列的末尾,再同樣地按FCFS原則等待調(diào)度執(zhí)行;如果它在第二隊列中運(yùn)行一個時間片后仍未完成,再依次將它放入第三隊列,……,如此下去,當(dāng)一個長作業(yè)(進(jìn)程)從第一隊列依次降到第n隊列后,在第n隊列中便采取按時間片輪轉(zhuǎn)的方式運(yùn)行。2025/1/1446僅當(dāng)?shù)谝魂犃锌臻e時,調(diào)度程序才調(diào)度第二隊列中的進(jìn)程運(yùn)行;僅當(dāng)?shù)?~(i-1)隊列均空時,才會調(diào)度第i隊列中的進(jìn)程運(yùn)行。如果處理機(jī)正在第i隊列中為某進(jìn)程服務(wù)時,又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊列(第1~(i-1)中的任何一個隊列),則此時新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī),即由調(diào)度程序把正在運(yùn)行的進(jìn)程放回到第i隊列的末尾,把處理機(jī)分配給新到的高優(yōu)先權(quán)進(jìn)程。2025/1/14473.多級反饋隊列調(diào)度算法的性能(1)終端型作業(yè)用戶終端型作業(yè)用戶所提交的作業(yè)多屬于交互型作業(yè),通常較小,系統(tǒng)只要能使這些作業(yè)在第一隊列所規(guī)定的時間片內(nèi)完成即可(2)短批處理作業(yè)用戶若在第1隊列中執(zhí)行一個時間片即可完成,便可獲得與終端型作業(yè)一樣的響應(yīng)時間如在第一個隊列中不能完成,只需在第2、3隊列中各執(zhí)行一個時間片(3)長批處理作業(yè)用戶長作業(yè)將依次在第1,2,3…,n隊列中執(zhí)行,最終按輪轉(zhuǎn)方式運(yùn)行2025/1/1448內(nèi)容概述3.1處理機(jī)調(diào)度的基本概念3.2調(diào)度算法3.3實(shí)時調(diào)度

3.4多處理機(jī)系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測與解除2025/1/14493.3實(shí)時調(diào)度3.3.1實(shí)現(xiàn)實(shí)時調(diào)度的基本條件3.3.2實(shí)時調(diào)度算法的分類3.3.3常用的幾種實(shí)時調(diào)度算法2025/1/14503.3.1實(shí)現(xiàn)實(shí)時調(diào)度的基本條件1.提供必要的信息(1)就緒時間 該任務(wù)成為就緒狀態(tài)的起始時間。(2)開始截止時間和完成截止時間(3)處理時間 指一個任務(wù)從開始執(zhí)行直至完成所需要的時間。(4)資源要求 執(zhí)行時所需資源。(5)優(yōu)先級 重大任務(wù),賦予“絕對”優(yōu)先級,無重大影響,可賦予“相對”優(yōu)先級。2025/1/14512.系統(tǒng)處理能力強(qiáng)在實(shí)時系統(tǒng)中,通常都有著多個實(shí)時任務(wù)。若處理機(jī)的處理能力不夠強(qiáng),則有可能因處理機(jī)忙不過來而使某些實(shí)時任務(wù)不能得到及時處理,從而導(dǎo)致發(fā)生難以預(yù)料的后果。假定系統(tǒng)中有m個周期性的硬實(shí)時任務(wù),它們的處理時間可表示為Ci,周期時間表示為Pi,則在單處理機(jī)情況下,必須滿足下面的限制條件,系統(tǒng)才是可調(diào)度的。2025/1/1452假如系統(tǒng)中有6個硬實(shí)時任務(wù),它們的周期時間都是50ms,而每次的處理時間為10ms,則不難算出,此時是不能滿足上式的,因而系統(tǒng)是 的。

解決的方法是提高系統(tǒng)的處理能力,其途徑有二:其一仍是采用單處理機(jī)系統(tǒng),但須增強(qiáng)其處理能力,以顯著地減少對每一個任務(wù)的處理時間;其二是采用多處理機(jī)系統(tǒng)。假定系統(tǒng)中的處理機(jī)數(shù)為N,則應(yīng)將上述的限制條件改為:不可調(diào)度2025/1/14533.采用搶占式調(diào)度機(jī)制當(dāng)一個優(yōu)先權(quán)更高的任務(wù)到達(dá)時,允許將當(dāng)前任務(wù)暫時掛起,而令高優(yōu)先權(quán)任務(wù)立即投入運(yùn)行,這樣便可滿足該硬實(shí)時任務(wù)對截止時間的要求。但這種調(diào)度機(jī)制比較復(fù)雜。對于一些小的實(shí)時系統(tǒng),如果能預(yù)知任務(wù)的開始截止時間,則對實(shí)時任務(wù)的調(diào)度可采用非搶占調(diào)度機(jī)制,以簡化調(diào)度程序和對任務(wù)調(diào)度時所花費(fèi)的系統(tǒng)開銷。但在設(shè)計這種調(diào)度機(jī)制時,應(yīng)使所有的實(shí)時任務(wù)都比較小,并在執(zhí)行完關(guān)鍵性程序和臨界區(qū)后,能及時地將自己阻塞起來,以便釋放出處理機(jī),供調(diào)度程序去調(diào)度那種開始截止時間即將到達(dá)的任務(wù)。2025/1/14544.具有快速切換機(jī)制該機(jī)制應(yīng)具有如下兩方面的能力:(1)對外部中斷的快速響應(yīng)能力。為使在緊迫的外部事件請求中斷時系統(tǒng)能及時響應(yīng),要求系統(tǒng)具有快速硬件中斷機(jī)構(gòu),還應(yīng)使禁止中斷的時間間隔盡量短,以免耽誤時機(jī)(其它緊迫任務(wù))。(2)快速的任務(wù)分派能力。在完成任務(wù)調(diào)度后,便應(yīng)進(jìn)行任務(wù)切換。為了提高分派程序進(jìn)行任務(wù)切換時的速度,應(yīng)使系統(tǒng)中的每個運(yùn)行功能單位適當(dāng)?shù)男?以減少任務(wù)切換的時間開銷。2025/1/14553.3實(shí)時調(diào)度3.3.1實(shí)現(xiàn)實(shí)時調(diào)度的基本條件3.3.2實(shí)時調(diào)度算法的分類3.3.3常用的幾種實(shí)時調(diào)度算法2025/1/14563.3.2實(shí)時調(diào)度算法的分類根據(jù)實(shí)時任務(wù)性質(zhì)的不同,可將實(shí)時調(diào)度算法分為:(1)硬實(shí)時調(diào)度算法(2)軟實(shí)時調(diào)度算法按調(diào)度方式的不同,可將實(shí)時調(diào)度算法分為:(1)非搶占調(diào)度算法(2)搶占調(diào)度算法因調(diào)度程序調(diào)度時間的不同,可將實(shí)時調(diào)度算法分為:(1)靜態(tài)調(diào)度算法(2)動態(tài)調(diào)度算法在多處理機(jī)環(huán)境下,可將實(shí)時調(diào)度算法分為:(1)集中式調(diào)度算法(2)分布式調(diào)度算法2025/1/14571.非搶占式調(diào)度算法(1)非搶占式輪轉(zhuǎn)調(diào)度算法

常用于工業(yè)生產(chǎn)的群控系統(tǒng)中調(diào)度程序每次選擇隊列中的第一個任務(wù)運(yùn)行一個任務(wù)運(yùn)行后排在輪轉(zhuǎn)隊列的末尾,等待下次調(diào)度可用于要求不太嚴(yán)格的實(shí)時控制系統(tǒng)中可獲得僅數(shù)秒至數(shù)十秒的響應(yīng)時間按調(diào)度方式的不同,可將實(shí)時調(diào)度算法分為:圖3-6實(shí)時進(jìn)程調(diào)度2025/1/14581.非搶占式調(diào)度算法(1)…(2)非搶占式優(yōu)先調(diào)度算法為時間要求嚴(yán)格的任務(wù)分配較高優(yōu)先級當(dāng)優(yōu)先權(quán)高的實(shí)時任務(wù)到來時,排在就緒隊列的隊首等待調(diào)度有可能獲得僅數(shù)秒至數(shù)百毫秒級的響應(yīng)時間圖3-6實(shí)時進(jìn)程調(diào)度2025/1/14592.搶占式調(diào)度算法(根據(jù)搶占發(fā)生時間的不同)(1)基于時鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法某實(shí)時任務(wù)到達(dá)后,若優(yōu)先級高于當(dāng)前正在執(zhí)行任務(wù)的優(yōu)先級,并不立即搶占當(dāng)前任務(wù)的處理機(jī),而是等到時鐘中斷到來后調(diào)度程序才剝奪當(dāng)前任務(wù)的執(zhí)行(幾十至幾毫秒)圖3-6實(shí)時進(jìn)程調(diào)度2025/1/14602.搶占式調(diào)度算法(根據(jù)搶占發(fā)生時間的不同)(1)…(2)立即搶占(ImmediatePreemption)的優(yōu)先權(quán)調(diào)度算法一旦有外部中斷,只要當(dāng)前任務(wù)不在臨界區(qū)內(nèi),便立即剝奪當(dāng)前任務(wù)的執(zhí)行,交處理機(jī)分配給要求中斷的緊迫任務(wù)(幾至0.1毫秒…)圖3-6實(shí)時進(jìn)程調(diào)度2025/1/14613.3實(shí)時調(diào)度3.3.1實(shí)現(xiàn)實(shí)時調(diào)度的基本條件3.3.2實(shí)時調(diào)度算法的分類3.3.3常用的幾種實(shí)時調(diào)度算法2025/1/14623.3.3常用的幾種實(shí)時調(diào)度算法圖3-9EDF算法用于非搶占調(diào)度方式1.最早截止時間優(yōu)先EDF(EarliestDeadlineFirst)算法根據(jù)任務(wù)的開始截止時間來確定任務(wù)的優(yōu)先級,截止時間越早優(yōu)先級越高既可用于搶占式調(diào)度也可用于非搶占式調(diào)度方式2025/1/14632.最低松弛度優(yōu)先即LLF(LeastLaxityFirst)算法根據(jù)任務(wù)緊急(或松弛)的程度,來確定任務(wù)的優(yōu)先級。任務(wù)的緊急程度愈高,為該任務(wù)所賦予的優(yōu)先級就愈高,以使之優(yōu)先執(zhí)行例如,一個任務(wù)在200ms時必須完成,而它本身所需的運(yùn)行時間就有80ms,因此,調(diào)度程序必須在120ms之前調(diào)度執(zhí)行,該任務(wù)的緊急程度(松弛程度)為120ms在實(shí)現(xiàn)該算法時要求系統(tǒng)中有一個按松弛度排序的實(shí)時任務(wù)就緒隊列,松弛度最低的任務(wù)排在隊列最前面,調(diào)度程序總是選擇就緒隊列中的隊首任務(wù)執(zhí)行該算法主要用于可搶占調(diào)度方式中2025/1/1464假如在一個實(shí)時系統(tǒng)中,有兩個周期性實(shí)時任務(wù)A和B,任務(wù)A要求每20ms執(zhí)行一次,執(zhí)行時間為10ms;任務(wù)B只要求每50ms執(zhí)行一次,執(zhí)行時間為25ms處理能力需求:2025/1/1465在剛開始時(t1=0),A1必須在20ms時完成,而它本身運(yùn)行又需10ms,可算出A1的松弛度為10ms;B1必須在50ms時完成,而它本身運(yùn)行就需25ms,可算出B1的松弛度為25ms,故調(diào)度程序應(yīng)先調(diào)度A1執(zhí)行。在t2=10ms時,A2的松弛度可按下式算出:

A2的松弛度=必須完成時間-其本身的運(yùn)行時間-當(dāng)前時間

=40ms-10ms-10ms=20ms

B1的松弛度=必須完成時間-其本身的運(yùn)行時間-當(dāng)前時間

=50ms-25ms-10ms=15ms圖3-11A和B任務(wù)每次必須完成的時間2025/1/1466故調(diào)度程序應(yīng)選擇B1運(yùn)行。在t3=30ms時,A2的松弛度已減為0(即40-10-30),而B1的松弛度為15ms(即50-5-30),于是調(diào)度程序應(yīng)搶占B1的處理機(jī)而調(diào)度A2運(yùn)行。在t4=40ms時,A3的松弛度為10ms(即60-10-40),而B1的松弛度僅為5ms(即50-5-40),故又應(yīng)重新調(diào)度B1執(zhí)行。在t5=45ms時,B1執(zhí)行完成,而此時A3的松弛度已減為5ms(即60-10-45),而B2的松弛度為30ms(即100-25-45),于是又應(yīng)調(diào)度A3執(zhí)行。在t6=55ms時,任務(wù)A尚未進(jìn)入第4周期,而任務(wù)B已進(jìn)入第2周期,故再調(diào)度B2執(zhí)行。在t7=70ms時,A4的松弛度已減至0ms(即80-10-70),而B2的松弛度為20ms(即100-10-70),故此時調(diào)度又應(yīng)搶占B2的處理機(jī)而調(diào)度A4執(zhí)行。t2=10ms2025/1/1467圖3-12利用ELLF算法進(jìn)行調(diào)度的情況2025/1/1468內(nèi)容概述3.1處理機(jī)調(diào)度的基本概念3.2調(diào)度算法3.3實(shí)時調(diào)度3.4多處理機(jī)系統(tǒng)中的調(diào)度

3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測與解除2025/1/14693.4多處理機(jī)系統(tǒng)中的調(diào)度3.4.1多處理機(jī)系統(tǒng)的類型3.4.2進(jìn)程分配方式3.4.3進(jìn)程(線程)調(diào)度方式2025/1/14703.4.1多處理器系統(tǒng)的類型(1)緊密耦合(TightlyCoupled)MPS(MultiProcessorSystem)

通常是通過高速總線或高速交叉開關(guān),來實(shí)現(xiàn)多個處理器之間的互連共享主存儲器系統(tǒng)和I/O設(shè)備,并要求將主存儲器劃分為若干個能獨(dú)立訪問的存儲器模塊,以便多個處理機(jī)能同時對主存進(jìn)行訪問。系統(tǒng)中的所有資源和進(jìn)程,都由操作系統(tǒng)實(shí)施統(tǒng)一的控制和管理(2)松散耦合(LooselyCoupled)MPS在松散耦合MPS中,通常是通過通道或通信線路,來實(shí)現(xiàn)多臺計算機(jī)之間的互連每臺計算機(jī)都有自己的存儲器和I/O設(shè)備,并配置了OS來管理本地資源和在本地運(yùn)行的進(jìn)程。因此,每一臺計算機(jī)都能獨(dú)立地工作,必要時可通過通信線路與其它計算機(jī)交換信息,以及協(xié)調(diào)它們之間的工作1.根據(jù)多處理器之間耦合的緊密程度分為:2025/1/14712.根據(jù)系統(tǒng)中所用處理器的相同與否,可將MPS分為如下兩類(1)對稱多處理器系統(tǒng)SMPS(SymmetricMultiProcessorSystem)在系統(tǒng)中所包含的各處理器單元,在功能和結(jié)構(gòu)上都是相同的,當(dāng)前的絕大多數(shù)MPS都屬于SMP系統(tǒng)例如,IBM公司的SR/6000ModelF50,便是利用4片PowerPC處理器構(gòu)成的。(2)非對稱多處理器系統(tǒng)在系統(tǒng)中有多種類型的處理單元,它們的功能和結(jié)構(gòu)各不相同,其中只有一個主處理器,有多個從處理器2025/1/14723.4多處理機(jī)系統(tǒng)中的調(diào)度3.4.1多處理機(jī)系統(tǒng)的類型3.4.2進(jìn)程分配方式3.4.3進(jìn)程(線程)調(diào)度方式2025/1/14733.4.2進(jìn)程分配方式1.對稱多處理器系統(tǒng)中的進(jìn)程分配方式在SMP系統(tǒng)中,所有的處理器都是相同的,因而可把所有的處理器作為一個處理器池(Processorpool),由調(diào)度程序或基于處理器的請求,將任何一個進(jìn)程分配給池中的任何一個處理器去處理在進(jìn)行進(jìn)程分配時,可采用以下兩種:(1)靜態(tài)分配(StaticAssigenment)方式一個進(jìn)程從一開始執(zhí)行到完成都被固定地分配到一個處理器上去執(zhí)行。必須為每個處理器單獨(dú)安排一個就緒隊列。優(yōu)點(diǎn):進(jìn)程調(diào)度的開銷小缺點(diǎn):會使各處理器的忙閑不均2025/1/1474(2)動態(tài)分配(DynamicAssgement)方式在系統(tǒng)中設(shè)置公共就緒隊列,分配時可將進(jìn)程分配到任一個處理器上。消除了各處理器忙閑不均的現(xiàn)象,但對于松耦合系統(tǒng),在一個處理器A上的進(jìn)程轉(zhuǎn)至B上運(yùn)行時,必須將A處理器所保存的信息傳給B優(yōu)點(diǎn):消除了各個處理器忙閑不均的現(xiàn)象2025/1/14752.非對稱MPS中的進(jìn)程分配方式對于非對稱MPS,其OS大多采用主—從(Master-Slave)式OS,即OS的核心部分駐留在一臺主機(jī)上(Master),而從機(jī)(Slave)上只是用戶程序,進(jìn)程調(diào)度只由主機(jī)執(zhí)行每當(dāng)從機(jī)空閑時,便向主機(jī)發(fā)送一索求進(jìn)程的信號,然后,便等待主機(jī)為它分配進(jìn)程在主機(jī)中保持有一個就緒隊列,只要就緒隊列不空,主機(jī)便從其隊首摘下一進(jìn)程分配給請求的從機(jī)從機(jī)接收到分配的進(jìn)程后便運(yùn)行該進(jìn)程,該進(jìn)程結(jié)束后從機(jī)又向主機(jī)發(fā)出請求優(yōu)點(diǎn):系統(tǒng)處理比較簡單缺點(diǎn):有“瓶頸”(主機(jī))2025/1/14763.4多處理機(jī)系統(tǒng)中的調(diào)度3.4.1多處理機(jī)系統(tǒng)的類型3.4.2進(jìn)程分配方式3.4.3進(jìn)程(線程)調(diào)度方式2025/1/14773.4.3進(jìn)程(線程)調(diào)度方式1.自調(diào)度(Self-Scheduling)方式(1)自調(diào)度機(jī)制自調(diào)度方式是最簡單的一種調(diào)度方式,直接由單處理機(jī)環(huán)境下的調(diào)度方式演變而來在系統(tǒng)中設(shè)置有一個公共的進(jìn)程或線程就緒隊列,所有的處理器在空閑時,都可自己到該隊列中取得一進(jìn)程(或線程)來運(yùn)行在自調(diào)度方式中,可采用在單處理機(jī)環(huán)境下所用的調(diào)度算法,如先來先服務(wù)(FCFS)調(diào)度算法、最高優(yōu)先權(quán)優(yōu)先(FPF)調(diào)度算法和搶占式最高優(yōu)先權(quán)優(yōu)先調(diào)度算法等2025/1/1478(2)自調(diào)度方式的優(yōu)點(diǎn)系統(tǒng)中的公共就緒隊列可按照單處理機(jī)系統(tǒng)中所采用的各種方式加以組織;其調(diào)度算法也可沿用單處理機(jī)系統(tǒng)所用的算法,亦即,很容易將單處理機(jī)環(huán)境下的調(diào)度機(jī)制移植到多處理機(jī)系統(tǒng)中,故它仍然是當(dāng)前多處理機(jī)系統(tǒng)中較常用的調(diào)度方式只要系統(tǒng)中有任務(wù),或者說只要公共就緒隊列不空,就不會出現(xiàn)處理機(jī)空閑的情況,也不會發(fā)生處理器忙閑不均的現(xiàn)象,因而有利于提高處理器的利用率2025/1/1479(3)自調(diào)度方式的缺點(diǎn)瓶頸問題

整個系統(tǒng)中只設(shè)一個就緒隊列,各處理器必須互斥的訪問低效性 當(dāng)線程阻塞后重新就緒時,只能進(jìn)入這個就緒隊列,但卻很少可能在原來的處理器上運(yùn)行,要重新拷貝運(yùn)行數(shù)據(jù)線程切換頻繁 互相合作的線程很難同時運(yùn)行2025/1/1480圖兩種分配處理器時間的方法2.成組調(diào)度(GangScheduling)方式

將一個進(jìn)程中的一組線程分配到一組處理器上去執(zhí)行在成組調(diào)度時,如何為應(yīng)用程序分配處理器時間(1)面向所有應(yīng)用程序平均分配處理器時間(2)面向所有線程平均分配處理器時間2025/1/14813.專用處理器分配(DedicatedProcessorAssignment)方式在一個應(yīng)用程序執(zhí)行期間,專門為該應(yīng)用程序分配一組處理器,每個線程一個,這組處理器為該程序?qū)S?直至完成這種方式的主要理由如下在含有幾百或幾個處理器的系統(tǒng)中,每個處理器的投資只占很小一部分,性能的重要性要高于對單個處理器利用率的考慮每個進(jìn)程或線程專用一個處理器可以完全避免進(jìn)程或線程的切換2025/1/1482圖線程數(shù)對加速比的影響系統(tǒng)一共有16個處理器,當(dāng)兩個進(jìn)程都各有8個線程時,正好是每個線程能分得1臺處理器;當(dāng)超過16個線程時,就不能保證每個線程有1臺處理器,因而出現(xiàn)線程切換問題。線程數(shù)愈多時切換就愈頻繁,反而會使加速比下降。2025/1/1483作業(yè)設(shè)有四道作業(yè),它們的提交時間和運(yùn)行時間如下表:作業(yè)號提交時刻(時)運(yùn)行時間(小時)18.002.0028.500.5039.000.1049.500.20求:試給出下面兩種調(diào)度算法下,作業(yè)的執(zhí)行順序,平均周轉(zhuǎn)時間和帶權(quán)平均周轉(zhuǎn)時間。(注意:作業(yè)調(diào)度與進(jìn)程調(diào)度均采用該調(diào)度算法,內(nèi)存無限大,作業(yè)為純計算型。要求寫出每個作業(yè)的裝入主存時間、開始執(zhí)行時間,結(jié)束執(zhí)行時間,周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間,調(diào)度時間忽略不計,保留小數(shù)點(diǎn)后兩位)(1)先來先服務(wù)FCFS調(diào)度算法。(2)短作業(yè)優(yōu)先SJF調(diào)度算法。2025/1/1484內(nèi)存無限大,作業(yè)調(diào)度和進(jìn)程調(diào)度都采用FCFS作業(yè)名提交運(yùn)行裝入主存開始執(zhí)行結(jié)束執(zhí)行周轉(zhuǎn)帶權(quán)周轉(zhuǎn) 時間 時間時間時間時間時間時間18.002.00 28.50 0.50 39.00 0.10 49.50 0.20 執(zhí)行順序:1->2->3->4周轉(zhuǎn)時間=結(jié)束執(zhí)行時間-提交時間帶權(quán)周轉(zhuǎn)時間=周轉(zhuǎn)時間/運(yùn)行時間(1)先來先服務(wù)調(diào)度算法(FCFS)8.008.0010.00218.509.5010.0010.50249.0010.6010.801.36.510.5010.601.616平均值:1.736.882025/1/1485內(nèi)存無限大,作業(yè)調(diào)度和進(jìn)程調(diào)度都采用SJF作業(yè)名提交運(yùn)行裝入主存開始執(zhí)行結(jié)束執(zhí)行周轉(zhuǎn)帶權(quán)周轉(zhuǎn) 時間 時間時間時間時間時間時間18.002.00 28.50 0.50 39.00 0.10 49.50 0.20 執(zhí)行順序:1->3->4->2周轉(zhuǎn)時間=結(jié)束執(zhí)行時間-提交時間帶權(quán)周轉(zhuǎn)時間=周轉(zhuǎn)時間/運(yùn)行時間(2)短作業(yè)優(yōu)先調(diào)度算法(SJF)8.008.0010.00218.509.5010.3010.802.34.69.0010.1010.300.8410.0010.101.111平均值:1.555.152025/1/1486內(nèi)容概述3.1處理機(jī)調(diào)度的基本概念3.2調(diào)度算法3.3實(shí)時調(diào)度3.4多處理機(jī)系統(tǒng)中的調(diào)度

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

3.6預(yù)防死鎖的方法3.7死鎖的檢測與解除2025/1/14873.5產(chǎn)生死鎖的原因和必要條件3.5.1產(chǎn)生死鎖的原因3.5.2產(chǎn)生死鎖的必要條件3.5.3處理死鎖的基本方法2025/1/1488例:有兩個進(jìn)程PA和PB,它們在運(yùn)行的過程中要共享使用兩個獨(dú)占設(shè)備R1和R2。設(shè)SR1為設(shè)備R1的互斥信號量,初值為1;SR2為設(shè)備R2的互斥信號量,初值為1;兩個進(jìn)程并發(fā)執(zhí)行的程序如下:死鎖的概念:是指多個進(jìn)程因競爭資源而造成的一種僵局,若無外力的作用,這些進(jìn)程將都不能再繼續(xù)執(zhí)行。2025/1/14893.5.1產(chǎn)生死鎖的原因(1)競爭資源引起進(jìn)程死鎖可剝奪和非剝奪性資源可剝奪性資源是指進(jìn)程在獲得這類資源后,該資源可以再被其他進(jìn)程或系統(tǒng)剝奪,如處理機(jī)、內(nèi)存等不可剝奪性資源是指當(dāng)系統(tǒng)把這類資源分配給某個進(jìn)程后,再不能強(qiáng)行收回,只能在進(jìn)程用完后自行釋放,如磁帶機(jī)、打印機(jī)等競爭非剝奪性資源系統(tǒng)中的非剝奪性資源由于數(shù)量有限而不能滿足進(jìn)程運(yùn)行的需要,進(jìn)程在運(yùn)行過程中因爭奪這些資源而限入僵局2025/1/1490圖3-13I/O設(shè)備共享時的死鎖情況請求請求配分已配分已2025/1/1491圖3-14進(jìn)程之間通信時的死鎖競爭臨時性資源臨時性資源區(qū)別于永久性資源,指由一個進(jìn)程產(chǎn)生,被另一進(jìn)程使用后就再也無用的資源,也稱為消耗性資源申請釋放申請釋放申請釋放2025/1/14922.進(jìn)程推進(jìn)順序不當(dāng)引起死鎖圖3-15進(jìn)程推進(jìn)順序?qū)λ梨i的影響P1進(jìn)程進(jìn)度P2進(jìn)程進(jìn)度2025/1/1493若并發(fā)進(jìn)程P1和P2按曲線④所示的順序推進(jìn),它們將進(jìn)入不安全區(qū)D內(nèi)。此時P1保持了資源R1,P2保持了資源R2,系統(tǒng)處于不安全狀態(tài)。因為,這時兩進(jìn)程再向前推進(jìn),便可能發(fā)生死鎖。例如,當(dāng)P1運(yùn)行到P1;Request(R2)時,將因R2已被P2占用而阻塞;當(dāng)P2運(yùn)行到P2;Request(R1)時,也將因R1已被P1占用而阻塞,于是發(fā)生了進(jìn)程死鎖2025/1/14943.5產(chǎn)生死鎖的原因和必要條件3.5.1產(chǎn)生死鎖的原因3.5.2產(chǎn)生死鎖的必要條件3.5.3處理死鎖的基本方法2025/1/14953.5.2產(chǎn)生死鎖的必要條件1.互斥條件進(jìn)程對所分配到的資源進(jìn)行排它性的使用。臨界(獨(dú)占)資源,即一次只有一個進(jìn)程可以使用資源。2.請求和保持條件進(jìn)程已經(jīng)至少保持了一個資源,但又提出了新的資源請求,而該資源又已被其他進(jìn)程占有。3.不剝奪條件進(jìn)程已獲得的資源在未使用完之前不能被剝奪。4.環(huán)路等待條件在發(fā)生死鎖時,必然存在一個進(jìn)程--資源的環(huán)形鏈。當(dāng)計算機(jī)系統(tǒng)同時具備下面4個必要條件時,會發(fā)生死鎖。只要有一個必要條件不滿足,則死鎖就可以排除。2025/1/14963.5產(chǎn)生死鎖的原因和必要條件3.5.1產(chǎn)生死鎖的原因3.5.2產(chǎn)生死鎖的必要條件3.5.3處理死鎖的基本方法2025/1/14973.5.3處理死鎖的基本方法(1)預(yù)防死鎖。 通過設(shè)置限制條件,破壞產(chǎn)生死鎖的必要條件的一個或幾個。(2)避免死鎖。在分配資源時,用某種方法防止系統(tǒng)進(jìn)入不安全的狀態(tài)。(3)檢測死鎖。 確定與死鎖有關(guān)的進(jìn)程和資源,采取措施,清除死鎖。(4)解除死鎖。 與檢測死鎖配套的一種措施。2025/1/1498內(nèi)容概述3.1處理機(jī)調(diào)度的基本概念3.2調(diào)度算法3.3實(shí)時調(diào)度3.4多處理機(jī)系統(tǒng)中的調(diào)度3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法

3.7死鎖的檢測與解除2025/1/14993.6預(yù)防死鎖的方法3.6.1預(yù)防死鎖3.6.2系統(tǒng)安全狀態(tài)3.6.3利用銀行家算法避免死鎖2025/1/141003.6.1預(yù)防死鎖摒棄“請求和保持”條件2.摒棄“不剝奪”條件3.摒棄“環(huán)路等待”條件原理該方法是通過對資源分配的原則進(jìn)行限制,從而使產(chǎn)生死鎖的四個必要條件中的第2、3、4個條件之一不能成立,來預(yù)防產(chǎn)生死鎖。

互斥:這個條件不可能被禁止。2025/1/14101預(yù)防死鎖1.摒棄“請求和保持”條件所有進(jìn)程在開始運(yùn)行之前必須一次性的申請整個運(yùn)行過程所需的全部資源。優(yōu)點(diǎn):簡單、易于實(shí)現(xiàn)、安全。缺點(diǎn):(1)資源浪費(fèi)嚴(yán)重(2)進(jìn)程延遲運(yùn)行2025/1/14102預(yù)防死鎖2.摒棄“不剝奪”條件系統(tǒng)規(guī)定:進(jìn)程逐個地申請所需資源當(dāng)一個已經(jīng)保持了某些資源的進(jìn)程申請新資源而不能得到滿足時,必須放棄所有已保持的資源實(shí)現(xiàn)復(fù)雜、代價高昴(例如:打印機(jī))2025/1/14103預(yù)防死鎖3.摒棄“環(huán)路等待”條件系統(tǒng)將所有資源按類型分配序號并排隊(例如打印機(jī)為1、磁帶機(jī)為2、磁盤為3、等等)。所有進(jìn)程申請資源必須按序號遞增的順序?qū)Ρ惹皟煞N方法:資源利用率和系統(tǒng)吞吐量較高缺點(diǎn):(1)序號固定,限制了新設(shè)備類型的增加(2)資源浪費(fèi)(不像前邊那么嚴(yán)重,考慮進(jìn)程使用資源順序了)(3)限制用戶自由編程(因限制了序號)2025/1/14104例如:進(jìn)程PA,使用資源的順序是R1,R2;

進(jìn)程PB,使用資源的順序是R2,R1;若采用無限制條件,有可能形成環(huán)路條件,造成死鎖。采用有序資源分配法:R1的編號為1,R2的編號為2;PA:申請次序應(yīng)是:R1,R2

PB:申請次序應(yīng)是:R1,R2

這樣就破壞了環(huán)路條件,避免了死鎖的發(fā)生。2025/1/141053.6預(yù)防死鎖的方法3.6.1預(yù)防死鎖3.6.2系統(tǒng)安全狀態(tài)3.6.3利用銀行家算法避免死鎖2025/1/141061.安全狀態(tài)之例我們通過一個例子來說明安全性。假定系統(tǒng)中有三個進(jìn)程P1、P2和P3,共有12臺磁帶機(jī)。進(jìn)程P1總共要求10臺磁帶機(jī),P2和P3分別要求4臺和9臺。假設(shè)在T0時刻,進(jìn)程P1、P2和P3已分別獲得5臺、2臺和2臺磁帶機(jī),尚有3臺空閑未分配,如下表所示:進(jìn)程最大需求已分配可用P1P2P3104952233.6.2系統(tǒng)安全狀態(tài) 在死鎖的避免中,所施加的限制較弱,將獲得較好一些的系統(tǒng)性能。該方法把系統(tǒng)狀態(tài)分為安全狀態(tài)和不安全狀態(tài),只要能使系統(tǒng)始終處于安全狀態(tài),便可以避免發(fā)生死鎖。P3(1)2025/1/141071.安全狀態(tài)在避免死鎖的方法中,允許進(jìn)程動態(tài)地申請資源,但系統(tǒng)在進(jìn)行資源分配之前,應(yīng)先計算此次資源分配的安全性。若此次分配不會導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài),則將資源分配給進(jìn)程;否則,令進(jìn)程等待。所謂安全狀態(tài),是指系統(tǒng)能按某種進(jìn)程順序(P1,P2,…,Pn)(稱〈P1,P2,…,Pn〉序列為安全序列),來為每個進(jìn)程Pi分配其所需資源,直至滿足每個進(jìn)程對資源的最大需求,使每個進(jìn)程都可順利地完成。如果系統(tǒng)無法找到這樣一個安全序列,則稱系統(tǒng)處于不安全狀態(tài)。2025/1/141083.由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換如果不按照安全序列分配資源,則系統(tǒng)可能會由安全狀態(tài)進(jìn)入不安全狀態(tài)例如,在T0時刻以后,P3又請求1臺磁帶機(jī),若此時系統(tǒng)把剩余3臺中的1臺分配給P3,則系統(tǒng)便進(jìn)入不安全狀態(tài)。因為,此時也無法再找到一個安全序列,例如,把其余的2臺分配給P2,這樣,在P2完成后只能釋放出4臺,既不能滿足P1尚需5臺的要求,也不能滿足P3尚需6臺的要求,致使它們都無法推進(jìn)到完成,彼此都在等待對方釋放資源,即陷入僵局,結(jié)果導(dǎo)致死鎖2025/1/141093.6預(yù)防死鎖的方法3.6.1預(yù)防死鎖3.6.2系統(tǒng)安全狀態(tài)3.6.3利用銀行家算法避免死鎖2025/1/14110例子:假定系統(tǒng)有10個資源(為了說明問題的簡單,不管它是什么資源),目前分配的情況如上表:此時,系統(tǒng)中只剩下2個資源,這時就要考察能滿足哪個進(jìn)程,不能滿足P和R的最大要求,能滿足Q,于是將剩下的2個資源分配給Q,Q就能完成,然后釋放所占用的6個資源。可滿足P,也可滿足R,這時不論分給誰都能保證完成。銀行家算法的設(shè)計思想是:當(dāng)用戶申請一組資源時,系統(tǒng)必須做出判斷;如果把這些資源分出去,系統(tǒng)是否還處于安全狀態(tài)。若是,就可以分出這些資源;否則,該申請暫不予滿足。2025/1/141113.6.3利用銀行家算法避免死鎖1.銀行家算法中的數(shù)據(jù)結(jié)構(gòu)(1)可利用資源向量Available這是一個含有m個元素的數(shù)組,其中的每一個元素代表一類可利用的資源數(shù)目,其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目,其數(shù)值隨該類資源的分配和回收而動態(tài)地改變。如果Available[j]=K,則表示系統(tǒng)中現(xiàn)有Rj類資源K個(2)最大需求矩陣Max這是一個n×m的矩陣,它定義了系統(tǒng)中n個進(jìn)程中的每一個進(jìn)程對m類資源的最大需求。如果Max[i,j]=K,則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K2025/1/14112

(2)分配矩陣Allocation這也是一個n×m的矩陣,它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocation[i,j]=K,則表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K(3)需求矩陣Need這也是一個n×m的矩陣,用以表示每一個進(jìn)程尚需的各類資源數(shù)。如果Need[i,j]=K,則表示進(jìn)程i還需要Rj類資源K個,方能完成其任務(wù)

Need[i,j]=Max[i,j]-Allocation[i,j]2025/1/141132.銀行家算法設(shè)Requesti是進(jìn)程Pi的請求向量,如果Requesti(1,0,2),表示進(jìn)程Pi需要1個R1類型的資源,需要0個R2類型的資源,需要2個R3類型的資源。當(dāng)Pi發(fā)出資源請求后,系統(tǒng)按下述步驟進(jìn)行檢查:(1)如果Requesti≤Needi,便轉(zhuǎn)向步驟2;否則認(rèn)為出錯,因為它所需要的資源數(shù)已超過它所宣布的最大值(2)如果Requesti≤Available,便轉(zhuǎn)向步驟(3);否則,表示尚無足夠資源,Pi須等待(3)系統(tǒng)試探著把資源分配給進(jìn)程Pi,并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值; Available:=Available-Requesti; Allocationi:=Allocationi+Requesti; Needi:=Needi-Requesti;(4)系統(tǒng)執(zhí)行安全性算法,檢查此次資源分配后,系統(tǒng)是否處于安全狀態(tài)。若安全,才正式將資源分配給進(jìn)程Pi,以完成本次分配;否則,將本次的試探分配作廢,恢復(fù)原來的資源分配狀態(tài),讓進(jìn)程Pi等待2025/1/141143.安全性算法(1)設(shè)置兩個向量初值;①工作向量Work;它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目,它含有m個元素,在執(zhí)行安全算法開始時,Work:=Available;②Finish[];它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程,使之運(yùn)行完成。開始時先做Finish[i]:=false;當(dāng)有足夠資源分配給進(jìn)程時,再令Finish[i]:=true(2)從進(jìn)程集合中找到一個能滿足下述條件的進(jìn)程;①Finish[i]=false; ②Needi≤Work;若找到,執(zhí)行步驟(3),否則,執(zhí)行步驟(4)2025/1/14115(3)當(dāng)進(jìn)程Pi獲得資源后,可順利執(zhí)行,直至完成,并釋放出分配給它的資源,故應(yīng)執(zhí)行;

Work:=Work+Allocation;Finish[i]:=true;gotostep2;(4)如果所有進(jìn)程的Finish[i]=true都滿足,則表示系統(tǒng)處于安全狀態(tài);否則,系統(tǒng)處于不安全狀態(tài)2025/1/14116最大需求已分配 可用資源(Max)(Allocation) (Available)P0753010 332P1322200P2902302P3222211P4433002743還需要(Need)1226000114314.銀行家算法之例假定系統(tǒng)中有五個進(jìn)程{P0,P1,P2,P3,P4}和三類資源{A,B,C},各種資源的數(shù)量分別為10、5、7,在T0時刻的資源分配情況如圖所示。Work=Available=(3,3,2)Finish[]分配給P1,完成后Work=(5,3,2)ture分配給P3,完成后Work=(7,4,3)ture分配給P4,完成后Work=(7,4,5)ture分配給P0,完成后Work=(7,5,5)ture分配給P2,完成后Work=(10,5,7)ture(1)T0時刻的安全性:在該時刻存在著一個安全序列{P1,P3,P4,P0,P2},故系統(tǒng)是安全的。2025/1/14117(2)P1請求資源:P1發(fā)出請求向量Request1(1,0,2),系統(tǒng)按銀行家算法進(jìn)行檢查:①Request1(1,0,2)≤Need1(1,2,2)②Request1(1,0,2)≤Available(3,3,2)③系統(tǒng)先假定可為P1分配資源,并修改Available,Allocation1和Need1向量,由此形成的資源變化情況如圖3-15中的圓括號所示。④再利用安全性算法檢查此時系統(tǒng)是否安全。2025/1/14118最大需求已分配 可用資源(Max)(Allocation) (Available)P0753010 230

P1322302

P2902302P3222211P4433002743還需要(Need)020600011431Work=Available=(2,3,0)Finish[]分配給P1,完成后Work=(5,3,2)ture分配給P3,完成后Work=(7,4,3)ture分配給P4,完成后Work=(7,4,5)ture分配給P0,完成后Work=(7,5,5)ture分配給P2,完成后Work=(10,5,7)tureRequest1(1,0,2)在該時刻存在著一個安全序列{P1,P3,P4,P0,P2},故系統(tǒng)是安全的,可以分配。2025/1/14119(3)P4請求資源:P4發(fā)出請求向量Request4(3,3,0),系統(tǒng)按銀行家算法進(jìn)行檢查:①Request4(3,3,0)≤Need4(4,3,1);②Request4(3,3,0)≤Available(2,3,0),讓P4等待。(4)P0請求資源:P0發(fā)出請求向量Requst0(0,2,0),系統(tǒng)按銀行家算法進(jìn)行檢查:①Request0(0,2,0)≤Need0(7,4,3);②Request0(0,2,0)≤Available(2,3,0);③系統(tǒng)暫時先假定可為P0分配資源,并修改有關(guān)數(shù)據(jù),如圖3-18所示。不可以分配2025/1/14120最大需求已分配 可用資源(Max)(Allocation) (Available)P0753030

210

P1322302P2902302P3222211P4433002723還需要(Need)020600011431Work=Available=(2,1,0)Finish[]不能滿足任何進(jìn)程的需要,故系統(tǒng)進(jìn)入不安全狀態(tài),此時系統(tǒng)不能分配資源給P0不可以分配Requst0(0,2,0)P0

7,4,32025/1/14121(5)P0請求資源:P0發(fā)出請求向量Request0(0,1,0),系統(tǒng)按銀行家算法進(jìn)行檢查:①Request0(0,1,0)≤Need0(7,4,3)②Request0(0,1,0)≤Available(2,3,0)③系統(tǒng)先假定可為P0分配資源,并修改Available,Allocation0和Need0向量,如下所示。④再利用安全性算法檢查此時系統(tǒng)是否安全。2025/1/14122最大需求已分配 可用資源(Max)(Allocation) (Available)P0753020

220

P1322302P2902302P3222211P4433002733還需要(Need)020600011431Work=Available=(2,2,0)Finish[]分配給P1,完成后Work=(5,2,2)ture分配給P3,完成后Work=(7,3,3)ture分配給P4,完成后Work=(7,3,5)ture分配給P0,完成后Work=(7,5,5)ture分配給P2,完成后Work=(10,5,7)tureRequest0(0,1,0)在該時刻存在著一個安全序列{P1

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論