操作系統(tǒng)原理-第四章 處理機調(diào)度(有答案)

1、第四章處理機調(diào)度4.3習題4.3.1選擇最合適的答案1某系統(tǒng)采用了銀行家算法，則下列敘述正確的是（）。系統(tǒng)處于不安全狀態(tài)時一定會發(fā)生死鎖系統(tǒng)處于不安全狀態(tài)時可能會發(fā)生死鎖系統(tǒng)處于安全狀態(tài)時可能會發(fā)生死鎖系統(tǒng)處于安全狀態(tài)時一定會發(fā)生死鎖銀行家算法中的數(shù)據(jù)結(jié)構(gòu)包括有可利用資源向量Available、最大需求矩陣Max、分配矩陣Allocation、需求矩陣Need,下列選項正確的是（）。Maxi,j=Allocationi,j+Needi,jNeedi,j=Allocationi,j+Maxi,jMaxi,j=Availablei,j+Needi,jNeedi,j=Availablei,j+Max

2、i,j3下列進程調(diào)度算法中,（）可能會出現(xiàn)進程長期得不到調(diào)度的情況。非搶占式靜態(tài)優(yōu)先權(quán)法搶占式靜態(tài)優(yōu)先權(quán)法時間片輪轉(zhuǎn)調(diào)度算法非搶占式動態(tài)優(yōu)先權(quán)法TOC o 1-5 h z4在下列選項中,屬于預(yù)防死鎖的方法是（）。剝奪資源法B.資源分配圖簡化法C.資源隨意分配D.銀行家算法5在下列選項中,屬于檢測死鎖的方法是（）。銀行家算法B.消進程法C.資源靜態(tài)分配法D.資源分配圖簡化法6在下列選項中,屬于解除死鎖的方法是（）。剝奪資源法B.資源分配圖簡化法C.銀行家算法D.資源靜態(tài)分配法7為了照顧緊迫型作業(yè),應(yīng)采用（）。A.先來服務(wù)調(diào)度算法B.短作業(yè)優(yōu)先調(diào)度算法C.時間片輪轉(zhuǎn)調(diào)度算法D.優(yōu)先權(quán)調(diào)度算法8在采

3、用動態(tài)優(yōu)先權(quán)的優(yōu)先權(quán)調(diào)度算法中,如果所有進程都具有相同優(yōu)先權(quán)初值,則此時的優(yōu)先權(quán)調(diào)度算法實際上和（）相同。A.先來先服務(wù)調(diào)度算法B.短作業(yè)優(yōu)先調(diào)度算法C.時間片輪轉(zhuǎn)調(diào)度算法D.長作業(yè)優(yōu)先調(diào)度算法9作業(yè)從后備作業(yè)到被調(diào)度程序選中的時間稱為（）。A.周轉(zhuǎn)時間B.響應(yīng)時間C.等待調(diào)度時間D.運行時間10資源靜態(tài)分配法可以預(yù)防死鎖的發(fā)生，它們使死鎖四個條件中的（）不成立。A.互斥條件B.請求和保持條件C.不可剝奪條件D.環(huán)路等待條件4.3.2選擇所有正確答案1下列選項中，（）可能是非搶占方式進程調(diào)度中引起調(diào)度的原因。當前的運行進程調(diào)用阻塞原語而進入阻塞狀態(tài)當前的運行進程提出申請I/O而阻塞有更高優(yōu)先級

4、的進程到達而從執(zhí)行狀態(tài)變?yōu)榫途w狀態(tài)正在執(zhí)行的進程執(zhí)行了P原語操作，由于資源不足而阻塞2選擇排隊作業(yè)中等待時間最長的作業(yè)被優(yōu)先調(diào)度，該調(diào)度算法不可能是（）。A.先來先服務(wù)調(diào)度算法B.高響應(yīng)比優(yōu)先調(diào)度算法C.優(yōu)先權(quán)調(diào)度算法D.短作業(yè)優(yōu)先調(diào)度算法作業(yè)控制塊JCB連成一串而形成的一個排隊隊列，該隊列稱為（）。A掛起隊列B.阻塞隊列C.就緒隊列D.后備隊列4下列哪個選項描述的時間屬于響應(yīng)時間的一部分（）。處理機對請求信息進行處理的時間從鍵盤輸入的請求信息傳送到處理機的時間所形成的響應(yīng)回送到終端顯示器的時間用戶查看響應(yīng)回送到的信息5下列四個選項描述的時間組成了周轉(zhuǎn)時間，其中可能發(fā)生多次的是（）。等待I/O

5、操作完成的時間作業(yè)在外存后備隊列上等待作業(yè)調(diào)度的時間進程在CPU上的執(zhí)行時間進程在就緒隊列上等待進程調(diào)度的時間6下面列出的是選擇調(diào)度方式和算法的4個面向用戶的準則。其中，不完全適用于實時系統(tǒng)的準則是（）。A.優(yōu)先權(quán)準則C.截止時間的保證B.響應(yīng)時間快D.周轉(zhuǎn)時間短7下面列出了選擇調(diào)度方式和算法的4個準則。其中，對批處理、分時、實時系統(tǒng)都可以采用的是（）。A.周轉(zhuǎn)時間短B.響應(yīng)時間快C.截止時間的保證D.優(yōu)先權(quán)準則8.下列選項中，（）是分時系統(tǒng)中確定時間片大小需要考慮的因素A.各類資源的平衡利用B.就緒隊列中進程的數(shù)目C.系統(tǒng)的處理能力D.系統(tǒng)對響應(yīng)時間的要求9.下面列出的選項中屬于可剝奪性資源

6、的有（）。A.CPUB.內(nèi)存C.磁盤D.磁帶機10在多級隊列調(diào)度和多級反饋隊列調(diào)度的敘述中，正確的是（）。多級反饋隊列調(diào)度中就緒隊列的設(shè)置不是象多級隊列調(diào)度一樣按作業(yè)性質(zhì)劃分,而是按時間片的大小劃分多級隊列調(diào)度用到優(yōu)先權(quán)，而多級反饋隊列調(diào)度中沒有用到優(yōu)先權(quán)多級隊列調(diào)度中的進程固定在某一個隊列中，而多級反饋隊列調(diào)度中的進程不固定多級隊列調(diào)度中每個隊列按作業(yè)性質(zhì)不同而采用不同的調(diào)度算法，而多級反饋隊列調(diào)度中除了個別隊列外，均采用相同的調(diào)度算法4.3.3判斷正誤，簡要說明理由1作業(yè)調(diào)度能夠使作業(yè)獲得CPU。在多道程序系統(tǒng)中，系統(tǒng)的現(xiàn)有空閑可用資源能否滿足一個后備作業(yè)J的資源要求，是選擇作業(yè)J進入內(nèi)存

7、的必要條件。短作業(yè)（進程）優(yōu)先調(diào)度算法具有最短的平均周轉(zhuǎn)時間，因此這種算法是最好的算法。在優(yōu)先權(quán)調(diào)度算法中確定靜態(tài)優(yōu)先權(quán)時，一般說，計算進程的優(yōu)先權(quán)要高于磁盤I/O進程的優(yōu)先權(quán)。摒棄不可剝奪條件的方法可用于預(yù)防多個打印進程死鎖的發(fā)生。操作系統(tǒng)處理死鎖，只要采用預(yù)防、解除、檢測、避免之中的一種就足夠了。如果系統(tǒng)在所有進程運行前，一次性地將其在整個運行過程所需的全部資源分配給進程，即所謂“靜態(tài)分配”法，是可以預(yù)防死鎖發(fā)生的。多個進程競爭比進程數(shù)目少的資源時就可能產(chǎn)生死鎖，而當資源數(shù)目大于進程數(shù)目時就一定不會發(fā)生死鎖。在銀行家算法中，對某時刻的資源分配情況進行安全分析，如果該時刻狀態(tài)是安全的，則存在

8、一個安全序列，且這個安全序列是唯一的。進程調(diào)度算法各種各樣，但是如果選擇不當，就會造成死鎖。4.3.4簡答題1高級調(diào)度和低級調(diào)度的主要任務(wù)是什么？為什么要引入中級調(diào)度？2在作業(yè)調(diào)度中需作出哪些決定？3在剝奪調(diào)度中，有哪些剝奪原則？4在OS中引起進程調(diào)度的主要因素有哪些？5在選擇調(diào)度方式和調(diào)度算法時，應(yīng)遵循的原則是什么？6在批處理系統(tǒng)、分時系統(tǒng)和實時系統(tǒng)中，各采用哪幾個進程(作業(yè))調(diào)度算法？7為什么說多級反饋隊列能較好地滿足各種用戶的需要？8在多用戶分時系統(tǒng)中，時間片輪轉(zhuǎn)調(diào)度的算法在確定時間片的大小時，應(yīng)考慮哪些因素？9為實現(xiàn)實時調(diào)度，對實時系統(tǒng)提出了哪些要求？10目前常用的調(diào)度方式和算法，能否

9、應(yīng)用到實時系統(tǒng)中？11在多處理機系統(tǒng)中，比較有代表性的線程調(diào)度方式有哪幾種？12試比較自調(diào)度和成組調(diào)度？13在OS/2中采用哪種調(diào)度方式和調(diào)度算法？14何為死鎖？產(chǎn)生死鎖的原因和必要條件是什么？15在解決死鎖問題的幾個方法中，哪種方法最容易實現(xiàn)？哪種方法使資源的利用率最高？16請詳細說明可通過哪些途徑預(yù)防死鎖？17.在銀行家算法的例子中，如果P0發(fā)出的請求向量由Request0(0,2,0)改為RequestO(O,l,O),問系統(tǒng)可否將資源分配給它？4.4習題解答要點選擇最合適的答案B2.B3.B4.D5.D6.A7.D8.A9.C10.B選擇所有正確答案1.ABD2.BCD3.D4.ABC

10、5.ACD6.AD7.D8.BCD9.ABC10.ACD4.4.3判斷題1.錯誤作業(yè)調(diào)度是高級調(diào)度。它只能使某作業(yè)獲得使用CPU的資格。而只有進程調(diào)度或線程調(diào)度才能使作業(yè)真正獲得CPU。錯誤多道系統(tǒng)中的資源分配有兩種方法：靜態(tài)分配：作業(yè)調(diào)度的功能之一是審查系統(tǒng)能否滿足用戶作業(yè)的資源要求；之二是按照一定的算法選取作業(yè)。動態(tài)分配：進程所需的資源是在運行中分配的，作業(yè)調(diào)度并不考慮當前空閑的資源量，只是按照一定的算法選取作業(yè)。3.錯誤前半句話講的正確，但由此說短作業(yè)（進程）優(yōu)先調(diào)度算法是最好的，就不正確了。因為一個算法的好壞要看其是否適于系統(tǒng)的需要而判定。4.錯誤因為磁盤I/O進程屬于系統(tǒng)進程。而系統(tǒng)

11、在確定進程的靜態(tài)優(yōu)先權(quán)時遵循的原則是：系統(tǒng)進程的優(yōu)先權(quán)高于一般用戶進程的優(yōu)先權(quán)（除非用戶的進程特別緊迫或重要）5.錯誤因為摒棄不剝奪條件的方法可預(yù)防死鎖的發(fā)生。6.錯誤因為，操作系統(tǒng)要兼顧資源的使用效率和安全性兩個方面，常見的是，將預(yù)防、解除、檢測、避免四種處理混合起來使用。舉例來說，只有檢測死鎖而無解除死鎖，檢測出死鎖又有什么用呢？正確因為資源的“靜態(tài)分配”方法，可以摒棄“請求和保持”條件，是可以預(yù)防死鎖的。錯誤進程是否發(fā)生死鎖，需要考慮每個進程申請資源的數(shù)目、所申請資源的種類、進程推進情況等因素。不能簡單地比較進程數(shù)目和資源數(shù)目就來確定是否死鎖。9.錯誤系統(tǒng)在調(diào)用銀行家算法進行安全檢查時，

12、只要找到一個安全序列就可斷定系統(tǒng)是安全的。但安全序列可能不止一個，有的情況下可能是只有一個，有的情況下可能有2個或者更多。10.錯誤如果進程調(diào)度算法選擇不當，會造成某些進程的長期等待。我們將這種進程稱為“饑餓”進程（長期“饑餓”的極端情況是“餓死”）。“餓死”和“死鎖”具有完全不同的含義。4.4.4簡答題1高級調(diào)度和低級調(diào)度的主要任務(wù)以及引入中級調(diào)度原因如下：高級調(diào)度又稱為作業(yè)調(diào)度。它是批處理系統(tǒng)中使用的一種調(diào)度。其主要任務(wù)是，按照某種算法從外存的后備隊列上選擇一個或多個作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進程、分配必要的資源，然后再將創(chuàng)建的進程控制塊掛入就緒隊列上。低級調(diào)度又稱進程調(diào)度。它是距離硬件最

13、近的一級調(diào)度。其主要任務(wù)是，按照某種算法從就緒隊列上選擇一個（或多個）進程，使其獲得CPU。引入中級調(diào)度的目的是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。其功能是，讓那些暫時不能運行的進程不再占用寶貴的內(nèi)存資源，而是調(diào)出到外存上等待。此時的進程狀態(tài)為掛起狀態(tài)。當這些進程重新具備運行條件且內(nèi)存空閑時，由中級調(diào)度選擇一部分掛起狀態(tài)的進程調(diào)入內(nèi)存，將其狀態(tài)變?yōu)閮?nèi)存就緒狀態(tài)。2在作業(yè)調(diào)度中需作出的決定如下：作業(yè)調(diào)度需要按照多道程序度（即，最大道數(shù)）決定一次接納多少作業(yè)進入內(nèi)存。如果太少將導(dǎo)致系統(tǒng)資源利用率低，且系統(tǒng)吞吐量低；太多將導(dǎo)致內(nèi)存空間緊張，系統(tǒng)服務(wù)質(zhì)量下降，使作業(yè)運行周期過長。作業(yè)調(diào)度需要決定接納哪些作

14、業(yè)進入內(nèi)存。常用的算法是，先來先服務(wù)，短作業(yè)優(yōu)先，最高優(yōu)先級調(diào)度、響應(yīng)比高者優(yōu)先等。3在剝奪進程調(diào)度中，剝奪原則如下：時間片原則。在輪轉(zhuǎn)算法中，CPU輪流為諸多進程服務(wù)，每個進程運行完自己的時間片后，系統(tǒng)就將它的CPU剝奪過來，交給下一個進程使用。優(yōu)先級原則。為緊迫的作業(yè)賦予較高的優(yōu)先級，這種作業(yè)到達系統(tǒng)，或者由阻塞狀態(tài)被喚醒后，若其優(yōu)先級高于當前運行的進程的優(yōu)先級，可以剝奪其CPU。短作業(yè)（進程）優(yōu)先原則。若一個作業(yè)（進程）到達系統(tǒng)，其運行長度比當前運行的進程長度明顯的短，則剝奪它的CPU。4引起進程調(diào)度的主要因素主要有：一個進程運行完畢；一個正在運行的進程被阻塞；在搶占式調(diào)度中，一個高優(yōu)先

15、級的進程被創(chuàng)建；在搶占式調(diào)度中，一個高優(yōu)先級進程由阻塞被喚醒；在輪轉(zhuǎn)式調(diào)度中，正在運行的進程運行完一個時間片。5在選擇調(diào)度方式和調(diào)度算法時，應(yīng)遵循的原則如下：面向用戶準則。首先，對于用戶的緊迫性作業(yè)，系統(tǒng)能夠及時地處理，不至于運行延誤。其次，對于批處理系統(tǒng)，還應(yīng)追求作業(yè)的周轉(zhuǎn)時間短；分時系統(tǒng)中作業(yè)的響應(yīng)時間塊；實時系統(tǒng)中作業(yè)的截止時間有保證。面向系統(tǒng)準則。系統(tǒng)的吞吐量高，處理機的利用率高，各類系統(tǒng)資源能夠得到平衡利用。6批處理系統(tǒng)、分時系統(tǒng)和實時系統(tǒng)中的主要調(diào)度算法如下：批處理系統(tǒng)中的作業(yè)調(diào)度算法有先來先服務(wù)（FCFS）、短作業(yè)優(yōu)先（SJF）、優(yōu)先級調(diào)度（HPF）和高響應(yīng)比優(yōu)先（RF）。批處理

16、系統(tǒng)的進程調(diào)度算法有：先進先出（FIFO）、短進程優(yōu)先（SPF）、優(yōu)先級調(diào)度（PRI）和高響應(yīng)比優(yōu)先（RF）。分時系統(tǒng)中只設(shè)有進程調(diào)度（不設(shè)作業(yè)調(diào)度），其進程調(diào)度算法只有輪轉(zhuǎn)法（RR）種。實時系統(tǒng)中只設(shè)有進程調(diào)度(不設(shè)作業(yè)調(diào)度)，其進程調(diào)度算法有：輪轉(zhuǎn)法、優(yōu)先級調(diào)度算法。前者適用于時間要求不嚴格的實時系統(tǒng)；后者用于時間要求不嚴格的實時系統(tǒng)。后者又可細分為：非搶占式優(yōu)先級調(diào)度、搶占式優(yōu)先級調(diào)度、基于時鐘中斷的搶占式優(yōu)先級調(diào)度。注意，一個純粹的實時系統(tǒng)是針對特定應(yīng)用領(lǐng)域設(shè)計的專用系統(tǒng)。作業(yè)提交的數(shù)量不會超過系統(tǒng)規(guī)定的多道程序度，因而可全部進入內(nèi)存。若將實時系統(tǒng)與批處理系統(tǒng)結(jié)合的話，就可以讓作業(yè)量超

17、過多道程序度，使優(yōu)先級低的作業(yè)呆在外存的后備隊列上。7多級反饋隊列能較好地滿足各種用戶的需要的原因：終端用戶的作業(yè)一般比較短小精悍，大多數(shù)在進入多級隊列的第一級隊列中后運行一個時間片就可以完成，因而感到滿意。批處理作業(yè)用戶，其作業(yè)進入多級隊列的第一級隊列中后，若作業(yè)較短，運行一個時間片就可以完成。對于稍長一些的作業(yè)，只需在第二或第三隊列上各執(zhí)行一個時間片就可完成，因而感到滿意。對于長作業(yè)來說，它將依次在第1,2,，n個隊列上運行，不會因作業(yè)太長而長期得不到處理。8在多用戶分時時間片長度的選擇上，既要保證交互性，又要保證系統(tǒng)的效率。系統(tǒng)對響應(yīng)時間T的要求(一般應(yīng)小于等于23秒鐘)；就緒隊列中的進

18、程數(shù)目N(N與終端上的用戶數(shù)目有關(guān))；系統(tǒng)的處理能力，一個時間片的長度q應(yīng)能保證用戶的大部分常用命令可處理完；進程的轉(zhuǎn)換時間p；三者的關(guān)系可表示為：T=N(q+p)。9對實時系統(tǒng)提出了要求如下：任務(wù)要提供必要的調(diào)度信息：主要包括：開工的最后期限或完工的最后期限、處理時間長度、優(yōu)先級、就緒時間，以及資源需求。采用適當?shù)恼{(diào)度方式：如果實時任務(wù)的運行長度較長且時間要求嚴格，那么實時系統(tǒng)應(yīng)采用搶占式調(diào)度；如果所有的實時任務(wù)都比較小，且預(yù)知任務(wù)的開工最后期限，也可以采用非剝奪式調(diào)度。能夠快速響應(yīng)外部中斷：這要求，硬件上要有較高的中斷機制，軟件上要使“封中”的時間間隔盡量短，以免貽誤時機?？焖俚娜蝿?wù)分派能

19、力：盡量減少任務(wù)切換時間開銷，使得一個任務(wù)完成后可以較快地切換到下一個任務(wù)去。10.搶占方式和非搶占方式都可以用于實時系統(tǒng)中。能夠使用的算法有：輪轉(zhuǎn)算法(RR)和優(yōu)先級調(diào)度算法(HPF)；不可以使用的算法有:先進先出(FIFO)和短進程優(yōu)先算法(SPF)。11在多處理機系統(tǒng)中，有代表性的線程調(diào)度方式有：自調(diào)度方式：諸多CPU可以共享同一就緒隊列，從中獲取就緒線程運行。成組調(diào)度方式：由系統(tǒng)將若干相關(guān)的線程同時分配到多臺CPU上運行。線程與CPU一一對應(yīng)。專用處理機分配方式：將若干同屬于一個應(yīng)用程序的線程分配到一組CPU上。讓這組CPU專門處理它們。12調(diào)度方式的比較如下：自調(diào)度方式中，就緒隊列與

20、單機的相同，調(diào)度算法也與之相同。系統(tǒng)沒有集中調(diào)度機制，任何CPU都可調(diào)用系統(tǒng)的調(diào)度例程去選擇一個線程。只要就緒隊列不空，就不會有空閑的CPU。它存在的問題是，多CPU共享一個就緒隊列將產(chǎn)生瓶頸；各線程在其生命周期中可能要換好幾臺CPU，每次更換都要將CPU中的高速緩存（Cache）重新拷入現(xiàn)場數(shù)據(jù)，造成效率低下；由于合作的一組線程很難同時獲得CPU，一些運行的線程只好阻塞等待未獲得CPU的線程，所以線程切換頻繁。成組調(diào)度中，合作的各線程可以同時獲得CPU，減少因同步造成的阻塞，減少了切換次數(shù)。同時，也可減少調(diào)度的頻率。13多優(yōu)先級的搶占式調(diào)度，調(diào)度的基本單位是線程。優(yōu)先級分為3類：每一類共細分

21、32級，以31級為最高級。其中：時間緊迫類為最高類，對應(yīng)的是實時線程及通信管理等；常規(guī)類為中檔優(yōu)先類，對應(yīng)的是一般線程；空閑時間類為較低類，對應(yīng)的是緊迫度低的線程。調(diào)度算法：在同一類的同一優(yōu)先級中采用輪轉(zhuǎn)算法。每當運行完一個時間片就檢查是否有更高優(yōu)先級線程到來，若有便搶占CPU。14死鎖是指多個進程因競爭資源而造成的一種僵持狀態(tài)。若無外力作用，這些進程都將永遠處于阻塞狀態(tài)，不能再運行下去。產(chǎn)生死鎖的原因有：資源不足資源、進程推進次序不當。產(chǎn)生死鎖的必要條件有：互斥條件、請求和保持條件、不可剝奪條件、環(huán)路等待條件。15預(yù)防死鎖方法，主要是破壞產(chǎn)生死鎖的必要條件。該方法是最容易實現(xiàn)的，但系統(tǒng)資源利

22、用率較低。避免死鎖方法，比較實用的有銀行家算法（BankerAlgorithm）。該算法需要較多的數(shù)據(jù)結(jié)構(gòu)，實現(xiàn)起來比較困難，但資源利用率最高。（3）檢測死鎖方法是基于死鎖定理設(shè)計的，定期運行該算法對系統(tǒng)的狀態(tài)進行檢測，發(fā)現(xiàn)死鎖便予以解除。其中，需要比較一下各種死鎖解除方案的代價，找到代價最小的方案。該方法最難實現(xiàn)，資源利用率較高。16預(yù)防死鎖方法是破壞產(chǎn)生死鎖的必要條件，主要有：擯棄請求和保持條件。采用靜態(tài)分配方案，一次性地分配給進程所請求的全部資源。進程運行過程中不可再請求新資源。擯棄不剝奪條件。采用動態(tài)分配方案，進程運行中可以請求新資源。若進程請求資源不能滿足時，就應(yīng)使其釋放已占有的資源

23、。擯棄環(huán)路等待條件。采用動態(tài)分配方案，要求進程請求資源時，按資源序號遞增(或遞減)順序提出。17系統(tǒng)的資源數(shù)量為：(10,5,7)。經(jīng)過一段時間的分配后,資源分配與占用情況見下表所示。進程MAXABCAllocationABCNeedABCAvailableABCP0753010743P1322200122P2902302600332P3222211011P4433002431Request1(1,0,2)：P1請求滿足后的占用情況如下。進程MAXABCAllocationABCNeedABCAvailableABCP0753010743P1322302020P2902302600230P32

24、22211011P4433002431檢測系統(tǒng)此刻存在一條安全序列Pl,P3,P4,PO,P2。檢測過程為：資源可用量(230)，不能滿足P0，可滿足P1。資源可用量(532)，不能滿足P2,可滿足P3。資源可用量(743)，可滿足P4。資源可用量(745)，可滿足P0。資源可用量(755),可滿足P2。待其完成后使系統(tǒng)的資源可用量達到初始值(10,5,7)。Request4(3,3,0)：P4的請求超過系統(tǒng)當前的可用量(2,3,0),應(yīng)推遲分配。Request0(0,1,0)：P0請求滿足后的占用情況如下：檢測系統(tǒng)此刻存在安全序列Pl,P3,P4,PO,P2。資源可用量（220），不能滿足P

25、0,可滿足P1。資源可用量（522），不能滿足P2,可滿足P3。資源可用量（733），可滿足P4。資源可用量（735），可滿足P0。資源可用量（755）,可滿足P2。待其完成后使系統(tǒng)的資源可用量達到初始值（10,5,7）。FCFS運行時間等待時間周轉(zhuǎn)時間1：120012012：601001602.673：301401705.674：1816017810SJF運行時間等待時間周轉(zhuǎn)時間112001204187088330981282601482084.5考研試題精選及解析1.在銀行家算法中,若出現(xiàn)以下資源分配情況：（北京理工2002死鎖題）Processallocationclaimavailab

26、leABCABCABCP0010753322P1210322P2302902P3211222P4002433問：1該狀態(tài)是否安全?2若進程依次有以下資源請求：pl資源請求：Request(l,0,2)p4資源請求：Request(3,3,0)p0資源請求：Request(0,l,0)則系統(tǒng)如何分配資源可避免死鎖?答：(1)資源分配情況為：資源進程currentavilCki-Akiallocationcurrentavil+allocationpossibleABCABCABCABCP1322112210532TRUEP3532011211743TRUEP0743743010753TRUEP2

27、7536003021055TRUEP410554310021057TRUE可見存在一個安全序列P1,P3,P0,P2,P4,故為安全狀態(tài)。(2)只需考慮進程P1和P0的資源申請?，F(xiàn)在假定進程P1又要申請1個A類資源和2個C類資源，為了判別這個申請能否立即準許,按銀行家算法進行檢查：request1(1,0,2)WCk1-Ak1(1,1,2)request1(1,0,2)WAvailable(3,2,2)此時，系統(tǒng)可用資源向量為(2,2,0)。進程p0的資源請求為Request(0,1,0)，按銀行家算法進行檢查：request1(0,1,0)WCk1-Ak1(7,4,3)request1(0,

28、1,0)WAvailable(2,2,0)試分配并修改數(shù)據(jù)結(jié)構(gòu)，processallocationCki-AkiavailableABCABCABCP0020733210P1312010P2302600P3211011P4002431再用安全性算法檢查：資源進程currentavilCki-Akiallocationcurrentavil+allocationpossibleABCABCABCABCP1210010312522TRUEP3522011211733TRUEP0733733020753TRUEP27536003021055TRUEP410554310021057TRUE可見存在一個

29、安全序列Pl,P3,P0,P2,P4,故為安全狀態(tài)?？蓾M足進程P1,PO對資源的申請。2.一個操作系統(tǒng)有20個進程，競爭使用65個同類資源，申請方式是逐個進行的，一旦某進程獲得它所需要的全部資源,則立即歸還所有資源。每個進程最多使有3個資源。若僅考慮這類資源,該系統(tǒng)有可能產(chǎn)生死鎖,為什么？（北京大學(xué)1995年死鎖題）解：在本題中,若僅考慮這一類資源的分配,則不會產(chǎn)生死鎖。因為死鎖產(chǎn)生的原因有兩點：系統(tǒng)資源不足或進程推進順序不當。在本題介紹的系統(tǒng)中,進程所要的最大資源數(shù)為：20X3=60,而系統(tǒng)中共有該類資源65個，其資源數(shù)目已足夠系統(tǒng)內(nèi)的各地進程使用，因此絕不可能發(fā)生死鎖。3.一臺計算機有8臺

30、磁帶機。它們由N個進程競爭使用，每個進程可能需要3臺磁帶機。請問N為多少時，系統(tǒng)沒有死鎖危險，并說明原因。（上海交通大學(xué)1999年死鎖題）解：當N為1,2,3時，系統(tǒng)沒有產(chǎn)生死鎖的危險。因為，當系統(tǒng)中只有1個進程時，它最多需要3臺磁帶機，而系統(tǒng)有8臺磁帶機，其資源數(shù)目已足夠系統(tǒng)內(nèi)的1個進程使用，因此絕不可能發(fā)生死鎖；當系統(tǒng)中有2個進程時，最多需要6臺磁帶機，而系統(tǒng)有8臺磁帶機，其資源數(shù)目也足夠系統(tǒng)內(nèi)的2個進程使，因此也不可能發(fā)生死鎖；當系統(tǒng)中有3個進程時，在最壞情況下，每個進程都需要3個這樣的資源，且假定每個進程都已申請到了2個資源，那么系統(tǒng)中還剩下2個,無論系統(tǒng)為了滿足哪個進程的資源申請而將

31、資源分配給該進程，都會因為該進程已獲得了它所需要的全部資源而確保它運行完畢,從而可將它占有的3個資源歸還給系統(tǒng),這就保證了其余進程能順利運行完畢.由此可知當N為1，2，3時，該系統(tǒng)不會由于對這種資源的競爭而產(chǎn)生死鎖。4假定某計算機系統(tǒng)有R1和R2兩類可再使用資源（其中R1有兩個單位,R2有一個單位），它們被進程P1，P2所共享，且已知兩個進程均以下列順序使用兩類資源：-申請R1-申請R2-申請R1-釋放R1-釋放R2-釋放R1-試求出系統(tǒng)運行過程中可能到達的死鎖點，并畫出死鎖點的資源分配圖。（南開大學(xué)1994年死鎖題)解：在本題中，當兩個進程都執(zhí)行完第1步后，即進程P1和進程P2都申請到了一個

32、R1類資源時，系統(tǒng)進入不安全狀態(tài)。隨著兩個進程的向前推進，無論哪個進程執(zhí)行完第2步，系統(tǒng)都將進入死鎖狀態(tài)。可能到達的死鎖點是：進程P1占有一個單位的R1類資源及一個單位的R2類資源，進程P2占有一個單位的R1類資源，此時系統(tǒng)內(nèi)已無空閑資源，而兩個進程都在保持已占有資源不釋放的情況下繼續(xù)申請資源，從而造成死鎖；或進程P2占有單位的R1類資源及一個單位的R2類資源，進程P1占有一個單位的R1類資源，此時系統(tǒng)內(nèi)已無空閑資源，而兩個進程都在保持已占有資源不釋放的情況下繼續(xù)申請R1R2資源，從而造成死鎖。假定進程P1成功執(zhí)行了第2步，則死鎖點的資源分配圖如圖所示:圖4-55.某系統(tǒng)有同類資源m個，被并發(fā)

33、執(zhí)行的n個進程共享，若每個進程申請該類資源的最大量為x(1WxWm)，試給出保證系統(tǒng)不產(chǎn)生死鎖的n、x、m之間的關(guān)系式。解：當每個進程分得資源的最大量x-1個后，只要系統(tǒng)還擁有一個資源時，系統(tǒng)便不會產(chǎn)生死鎖，故可推出關(guān)系式：nX(x-1)+1Wm。其中，當mWn時，x=1。mn時，x=1+(m-1)/n其中，為取下界、即去掉小數(shù)點。6某系統(tǒng)有同類資源m個，被并發(fā)執(zhí)行的n個進程共享，若每個進程申請該類資源的最大量為x(1WxWm),試證明：當nX(x-1)+1Wm時，系統(tǒng)不產(chǎn)生死鎖。(西安理工2000死鎖題)解：當每個進程分得資源的最大量x-1個后，只要系統(tǒng)還擁有一個資源時，系統(tǒng)便不會產(chǎn)生死鎖，

34、故可推出關(guān)系式：nX(x-1)+1Wm。其中，當mWn時，x=1。mn時，x=1+(m-1)/n其中，為取下界、即去掉小數(shù)點。7假設(shè)系統(tǒng)由相同類型m個資源組成，系統(tǒng)有n個進程，每個進行至少請求一個資源。證明當n個進程最多需要的資源數(shù)之和小于m+n時，該系統(tǒng)沒有死鎖。(國防科大2001死鎖題)答：設(shè)max(i)表示第i個進程的最大資源需求量，need(i)表示第i個進程還需要的資源量，alloc(i)表示第i個進程已分配的資源量。由題中所給條件可知：max(1)+max(n)=(need(1)+-+need(n)+(alloc(1)+-+alloc(n)vm+n如果在這個系統(tǒng)中發(fā)生了死鎖，那么一

35、方面m個資源應(yīng)該全部分配出去，alloc(l)+alloc(n)=m另一方面所有進程將陷入無限等待狀態(tài)?？梢酝瞥鰊eed(1)+need(n)vn上式表示死鎖發(fā)生后，n個進程還需要的資源量之和小于n,這意味著此刻至少存在一個進程i,need(i)=O,即它已獲得了所需要的全部資源。既然該進程已獲得了它所需要的全部資源,那么它就能執(zhí)行完成并釋放它占有的資源，這與前面的假設(shè)矛盾，從而證明在這個系統(tǒng)中不可能發(fā)生死鎖。8某系統(tǒng)有同類獨占資源m個，被并發(fā)執(zhí)行的n個進程共享，若每個進程申請該類資源的最大量為w(1WwWm)，當m、w、n取下列值時，判斷下列哪些情形發(fā)生死鎖。(上交大1999死鎖題)(1)m

36、=2,n=2,w=1。(2)m=3,n=2,w=2。(3)m=3,n=2,w=3。(4)m=5,n=3,w=2。(5)m=6,n=3,w=3。解：用上題結(jié)論，當mWn時，w=1。mn時，w=1+(m-1)/n其中，口為取下界。(1)不會死鎖。(2)不會死鎖。(3)可能出現(xiàn)死鎖。(4)不會死鎖。(5)可能出現(xiàn)死鎖。N個進程共享M個資源，每個進程一次只能申請釋放一個資源，每個進程最多需要M個資源，所有進程總共的資源需求少于M+N個，證明該系統(tǒng)此時不會產(chǎn)生死鎖。(西北工大2000死鎖題)答1：設(shè)max(i)表示第i個進程的最大資源需求量，need(i)表示第i個進程還需要的資源量，alloc(i)表

37、示第i個進程已分配的資源量。由題中所給條件可知：max(1)+-“+max(n)=(need(1)+need(n)+(alloc(1)+-+alloc(n)vm+n如果在這個系統(tǒng)中發(fā)生了死鎖，那么一方面m個資源應(yīng)該全部分配出去，alloc(1)+alloc(n)=m另一方面所有進程將陷入無限等待狀態(tài)。可以推出need(1)+need(n)vn上式表示死鎖發(fā)生后，n個進程還需要的資源量之和小于n,這意味著此刻至少存在一個進程i,need(i)=0,即它已獲得了所需要的全部資源。既然該進程已獲得了它所需要的全部資源,那么，它就能執(zhí)行完成并釋放它占有的資源，這與前面的假設(shè)矛盾，從而證明在這個系統(tǒng)中不

38、可能發(fā)生死鎖。答2：設(shè)每個進程對共享資源的最大需求量為x(OvxWm),由于每個進程最多申請使用x個資源，在最壞情況下，每個進程都得到了(x-1)個資源，并且都需申請最后一個資源。這時系統(tǒng)剩余資源數(shù)為：m-n(x-1)。只要系統(tǒng)還有一個資源可用，就可使其中的一個進程獲得所需的全部資源，該進程運行結(jié)束后釋放出它所占用的資源，其他進程的資源需求也可得到全部滿足。因此，當m-n(x-l)21時，即xW(m+n-l)/n時系統(tǒng)不會發(fā)生死鎖。進而可得系統(tǒng)中所有進程最大需求量之和nxW(m+n-1)時系統(tǒng)不會發(fā)生死鎖。該題中，所有進程最大需求量之和小于m+n,所以，該系統(tǒng)是死鎖無關(guān)的。答3：由題意知道，n

39、Xmvm+n是成立的，等式變換nX(m-1)+nvn+m即nX(m-1)vm于是有nX(m-1)+16o(南京航空航天大學(xué)2002死鎖題)解：設(shè)3個進程各需x1,x2和x3個資源，根據(jù)題意，x=x1+x2+x3若發(fā)生了死鎖，那么，每個進程至還缺個資源，但系統(tǒng)己沒有空閑的可分配了、即有：(x1-1)+(x2-1)+(x3-1)三3x1+x2+x3-3=3故有x-3M3所以x6有一個具有兩道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法，進程調(diào)度采用以優(yōu)先數(shù)為基礎(chǔ)的搶占式調(diào)度算法，在下表所示的作業(yè)序列，作業(yè)優(yōu)先數(shù)即為進程優(yōu)先數(shù)，優(yōu)先數(shù)越小優(yōu)先級越高。(北京大學(xué)1995年進程調(diào)度題)作業(yè)名到達時

40、間估計運行時間優(yōu)先數(shù)A10：0040分5B10：2030分3C10：3050分4D10：5020分6列出所有作業(yè)進入內(nèi)存時間及結(jié)束時間。計算平均周轉(zhuǎn)時間。分析：每個作業(yè)的運行將經(jīng)歷兩級調(diào)度：作業(yè)調(diào)度和進程調(diào)度。作業(yè)調(diào)度采用短作業(yè)優(yōu)先調(diào)度算法進程調(diào)度采用基于優(yōu)先數(shù)的搶占式調(diào)度算法，高優(yōu)先級的進程可以搶占系統(tǒng)處理機。只有當作業(yè)調(diào)度程序?qū)⒆鳂I(yè)裝入內(nèi)存后，方能參與進程調(diào)度。本題中的批處理系統(tǒng)是兩道作業(yè)系統(tǒng)，因此每次只能有兩道作業(yè)進入系統(tǒng)內(nèi)存。本題中的作業(yè)和進程推進順序如下：10：00時，A作業(yè)到達。因系統(tǒng)的后備作業(yè)隊列中沒有其他作業(yè)，進程就緒隊列中也沒有進程，故作業(yè)調(diào)度程序?qū)⒆鳂I(yè)A調(diào)入內(nèi)存并將它排在就

41、緒隊列上，進程調(diào)度程序調(diào)度它運行。10：20時,B作業(yè)到達。因系統(tǒng)的后備作業(yè)隊列中沒有其他作業(yè)，故作業(yè)調(diào)度程序?qū)⒆鳂I(yè)B調(diào)入內(nèi)存并將它排在就緒隊列上。而作業(yè)B的優(yōu)先級高于作業(yè)A的優(yōu)先級，進程調(diào)度程序停止作業(yè)A的運行，將作業(yè)B放入就緒隊列，調(diào)度作業(yè)運行。此時，系統(tǒng)中已有兩道作業(yè)在內(nèi)存中運行，作業(yè)A已運行20分鐘，還需運行20分鐘才能完成。10：30時，C作業(yè)到達。因系統(tǒng)已有兩道作業(yè)在內(nèi)存中運行，故作業(yè)C只能在后備作業(yè)隊列中等待作業(yè)調(diào)度。此時，作業(yè)B已運行了10分鐘并將繼續(xù)運行，還需運行20分鐘才能完成；作業(yè)A已等待10分鐘并將繼續(xù)等待，還需運行20分鐘才能完成。10：50時，B作業(yè)運行30分鐘結(jié)束運行，D作業(yè)到達。因系統(tǒng)中只有作業(yè)A在內(nèi)存中運行，作業(yè)后備隊列中有C、D兩作業(yè)，按短作業(yè)優(yōu)先的作業(yè)調(diào)度策略，作業(yè)D被作業(yè)調(diào)度程序選中，裝入內(nèi)存運行，作業(yè)C仍在后備作業(yè)隊列中等待作業(yè)調(diào)度。在內(nèi)存中，作業(yè)A的優(yōu)先級高于作業(yè)D,進程調(diào)度程序調(diào)度作業(yè)A運行，作業(yè)D在就緒隊列中等待進程調(diào)度。此時，作業(yè)A已運行了20分鐘，在就緒隊列中等待了30分鐘，還需運行20分鐘才能完成；作業(yè)C已在后備隊列中等待了20分鐘并將繼續(xù)等待。11：10時，A作業(yè)運行40分鐘結(jié)束運行。因系統(tǒng)中只有作業(yè)D在內(nèi)存中運行，作業(yè)后備隊列中只