計算機操作系統(tǒng)(第四版)課后習(xí)題答案第三章.docVIP

第三章 處理機調(diào)度與死鎖1，高級調(diào)度與低級調(diào)度的主要任務(wù)是什么？為什么要引入中級調(diào)度？ 【解】 （1）高級調(diào)度主要任務(wù)是用于決定把外存上處于后備隊列中的那些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進程，分配必要的資源，然后再將新創(chuàng)建的進程排在就緒隊列上，準備執(zhí)行。 （2）低級調(diào)度主要任務(wù)是決定就緒隊列中的哪個進程將獲得處理機，然后由分派程序執(zhí)行把處理機分配給該進程的操作。 （3）引入中級調(diào)度的主要目的是為了提高內(nèi)存的利用率和系統(tǒng)吞吐量。為此，應(yīng)使那些暫時不能運行的進程不再占用寶貴的內(nèi)存空間，而將它們調(diào)至外存上去等待，稱此時的進程狀態(tài)為就緒駐外存狀態(tài)或掛起狀態(tài)。當這些進程重又具備運行條件，且內(nèi)存又稍有空閑時，由中級調(diào)度決定，將外存上的那些重又具備運行條件的就緒進程重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊列上，等待進程調(diào)度。 3、何謂作業(yè)、作業(yè)步和作業(yè)流？ 【解】作業(yè)包含通常的程序和數(shù)據(jù)，還配有作業(yè)說明書。系統(tǒng)根據(jù)該說明書對程序的運行進行控制。批處理系統(tǒng)中是以作業(yè)為基本單位從外存調(diào)入內(nèi)存。作業(yè)步是指每個作業(yè)運行期間都必須經(jīng)過若干個相對獨立相互關(guān)聯(lián)的順序加工的步驟。作業(yè)流是指若干個作業(yè)進入系統(tǒng)后依次存放在外存上形成的輸入作業(yè)流；在操作系統(tǒng)的控制下，逐個作業(yè)進程處理，于是形成了處理作業(yè)流。4、在什么情冴下需要使用作業(yè)控制塊JCB？其中包含了哪些內(nèi)容？【解】每當作業(yè)進入系統(tǒng)時，系統(tǒng)便為每個作業(yè)建立一個作業(yè)控制塊JCB，根據(jù)作業(yè)類型將它插入到相應(yīng)的后備隊列中。JCB 包含的內(nèi)容通常有：1) 作業(yè)標識2)用戶名稱3)用戶賬戶4)作業(yè)類型（CPU繁忙型、I/O芳名型、批量型、終端型）5)作業(yè)狀態(tài)6)調(diào)度信息（優(yōu)先級、作業(yè)已運行）7)資源要求8)進入系統(tǒng)時間9) 開始處理時間10) 作業(yè)完成時間11) 作業(yè)退出時間12) 資源使用情況等5在作業(yè)調(diào)度中應(yīng)如何確定接納多少個作業(yè)和接納哪些作業(yè)？【解】作業(yè)調(diào)度每次接納進入內(nèi)存的作業(yè)數(shù)，取決于多道程序度。應(yīng)將哪些作業(yè)從外存調(diào)入內(nèi)存，取決于采用的調(diào)度算法。最簡單的是先來服務(wù)調(diào)度算法，較常用的是短作業(yè)優(yōu)先調(diào)度算法和基于作業(yè)優(yōu)先級的調(diào)度算法。7試說明低級調(diào)度的主要功能。【解】（1）保存處理機的現(xiàn)場信息（2）按某種算法選取進程（3）把處理機分配給進程。8、在搶占調(diào)度方式中，搶占的原則是什么？ 【解】剝奪原則有： （1）時間片原則 各進程按時間片運行，當一個時間片用完后，便停止該進程的執(zhí)行而重新進行調(diào)度。這種原則適用于分時系統(tǒng)、大多數(shù)實時系統(tǒng)，以及要求較高的批處理系統(tǒng)。 （2）優(yōu)先權(quán)原則 通常是對一些重要的和緊急的作業(yè)賦予較高的優(yōu)先權(quán)。當這種作業(yè)到達時，如果其優(yōu)先權(quán)比正在執(zhí)行進程的優(yōu)先權(quán)高，便停止正在執(zhí)行的進程，將處理機分配給優(yōu)先權(quán)高的進程，使之執(zhí)行。 （3）短作業(yè)（進程）優(yōu)先原則 當新到達的作業(yè)（進程）比正在執(zhí)行的作業(yè)（進程）明顯地短時，將剝奪長作業(yè)（進程）的執(zhí)行，將處理機分配給短作業(yè)（進程），使之優(yōu)先執(zhí)行。 9、選擇調(diào)度方式和調(diào)度算法時，應(yīng)遵循的準則是什么？ 【解】應(yīng)遵循的準則有 （1）面向用戶的準則：周轉(zhuǎn)時間短，響應(yīng)時間快，截止時間的保證，優(yōu)先權(quán)準則。 （2）面向系統(tǒng)的準則：系統(tǒng)吞吐量高，處理機利用率好，各類資源的平衡利用。 10、在批處理系統(tǒng)、分時系統(tǒng)和實時系統(tǒng)中，各采用哪幾種進程（作業(yè)）調(diào)度算法？ 【解】 l 批處理系統(tǒng)：FCFS算法、最小優(yōu)先數(shù)優(yōu)先算法、搶占式最小優(yōu)先數(shù)優(yōu)先算法 2 l 分時系統(tǒng)：可剝奪調(diào)度、輪轉(zhuǎn)調(diào)度 l 實時系統(tǒng)：時間片輪轉(zhuǎn)調(diào)度算法、非搶占優(yōu)先權(quán)調(diào)度算法、基于時鐘中斷搶 占的優(yōu)先權(quán)調(diào)度算法、立即搶占的優(yōu)先權(quán)調(diào)度。11、何謂靜態(tài)和動態(tài)優(yōu)先權(quán)？確定靜態(tài)優(yōu)先權(quán)的依據(jù)是什么？ 【解】靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進程時確定的，且在進程的整個運行期間保持不變。動態(tài)優(yōu)先權(quán)是指，在創(chuàng)建進程時所賦予的優(yōu)先權(quán)，是可以隨進程的推進或隨其等待時間的增加而改變的，以便獲得更好的調(diào)度性能。 確定靜態(tài)優(yōu)先權(quán)的依據(jù)是： （1）進程類型，通常系統(tǒng)進程的優(yōu)先權(quán)高于一般用戶進程的優(yōu)先權(quán)。 （2）進程對資源的需要。 （3）用戶要求，用戶進程的緊迫程度及用戶所付費用的多少來確定優(yōu)先權(quán)的。 12、試比較FCFS和SPF兩種進程調(diào)度算法。 【解】FCFS算法按照作業(yè)提交或進程變?yōu)榫途w狀態(tài)的先后次序，分派CPU。當前作業(yè)或進程占有CPU，直到執(zhí)行完或阻塞，才讓出CPU。在作業(yè)或進程喚醒后，并不立即恢復(fù)執(zhí)行，通常等到當前作業(yè)或進程讓出CPU。FCFS比較有利于長作業(yè)，而不利于短作業(yè)；有利于CPU繁忙的作業(yè)，而不利于I/O繁忙的作業(yè)。 SPF有利于短進程調(diào)度，是從就緒隊列中選出一估計運行時間最短的進程，將處理機分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機時，再重新調(diào)度。比FCFS改善了平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間，縮短了作業(yè)的等待時間，提高了系統(tǒng)的吞吐量。但SPF有其不容忽視的缺點：該算法對長作業(yè)不利；完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)（進程）會被及時處理；用戶可能會有意無意地干擾作業(yè)的運行時間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。 13、在時間片輪轉(zhuǎn)法中，應(yīng)如何確定時間片的大小？ 【解】時間片應(yīng)略大于一次典型的交互需要的時間。一般應(yīng)考慮三個因素：系統(tǒng)對相應(yīng)時間的要求、就緒隊列中進程的數(shù)目和系統(tǒng)的處理能力。14、通過一個例子來說明通常的優(yōu)先級調(diào)度算法不能適用于實時系統(tǒng)？ 【解】實時系統(tǒng)的調(diào)度算法很多，主要是基于任務(wù)的開始截止時間和任務(wù)緊急/松弛程度的任務(wù)優(yōu)先級調(diào)度算法，通常的優(yōu)先級調(diào)度算法不能滿足實時系統(tǒng)的調(diào)度實時性要求而不適用。15、為什么說多級反饋隊列調(diào)度算法能較好地滿足各方面用戶的需要？ 【解】（1）對于終端型用戶來說，他們提交的大多屬于較小的交互型作業(yè)，系統(tǒng)只要能使這些作業(yè)（進程）在第一隊列所規(guī)定的時間片內(nèi)完成，便可使終端型作業(yè)用戶都感到滿意。 （2）對短批處理作業(yè)用戶來說，在第一隊列中執(zhí)行一個時間片或至多只需在第二隊列和第三隊列中各執(zhí)行一個時間片即可完成。 （3）對長批處理作業(yè)用戶來說，只要將作業(yè)依次在第1，2，n個隊列中運行，然后再按輪轉(zhuǎn)方式運行，用戶不必擔心其作業(yè)長期得不到處理。 16、 19、為什么在實時系統(tǒng)中，要求系統(tǒng)（尤其是CPU）具有較強的處理能力？ 【解】在實時系統(tǒng)中都存在著若干個實時進程或任務(wù)，它們用來反應(yīng)或控制某個（些）外部事件，往往帶有某種程度的緊迫性，因而對實時系統(tǒng)中的調(diào)度提出了某些特殊要求。 若處理機的處理能力不夠強，則有可能因處理機忙不過來而使某些實時任務(wù)不能得到及時處理，從而導(dǎo)致發(fā)生難以預(yù)料的后果。 20、按調(diào)度方式可將實時調(diào)度算法分為哪幾種？ 【解】按調(diào)度方式可將實時調(diào)度算法分為兩大類四小類： （1）非搶占式調(diào)度算法：非搶占式輪轉(zhuǎn)調(diào)度算法；非搶占式優(yōu)先調(diào)度算法； （2）搶占式調(diào)度算法：基于時鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法；立即搶占的優(yōu)先權(quán)調(diào)度算法。 21、什么是最早截止時間優(yōu)先調(diào)度算法？舉例說明之。【解】在系統(tǒng)中保持一個實時任務(wù)就緒隊列，該隊列按各任務(wù)截止時間的早晚排序，截止時間愈早的優(yōu)先級愈高，在隊列中排列愈靠前，調(diào)度程序在選擇任務(wù)時，總是選擇就緒隊列中的第一個任務(wù)，為之分配處理機，使之投入運行。 例：四個非周期任務(wù)，它們先后到達。系統(tǒng)首先調(diào)度任務(wù)1執(zhí)行，在任務(wù)1執(zhí)行期間，任務(wù)2、3又先后到達。由于任務(wù)3的開始截止時間早于任務(wù)2，系統(tǒng)在任務(wù)1后將調(diào)度任務(wù)3執(zhí)行。在此期間又到達作業(yè)4，其開始截止時間仍是早于任務(wù)2的，在任務(wù)3執(zhí)行完后，系統(tǒng)又調(diào)度任務(wù)4的執(zhí)行，最后才調(diào)度任務(wù)2執(zhí)行。 22、什么是最低松弛度優(yōu)先調(diào)度算法？舉例說明之?！窘狻?該算法是根據(jù)任務(wù)緊急(或松弛)的程度，來確定任務(wù)的優(yōu)先級。任務(wù)的緊急程度愈高，為該任務(wù)所賦予的優(yōu)先級就愈高，以使之優(yōu)先執(zhí)行。例如，一個任務(wù)在200 ms 時必須完成，而它本身所需的運行時間就有100 ms，因此，調(diào)度程序必須在100 ms 之前調(diào)度執(zhí)行，該任務(wù)的緊急程度(松弛程度)為100 ms。又如，另一任務(wù)在400 ms 時必須完成，它本身需要運行 150 ms，則其松弛程度為 250 ms。 27、何謂死鎖？產(chǎn)生死鎖的原因和必要條件是什么？ 【解】 所謂死鎖，是指多個進程因競爭資源而造成的一種僵局，若無外力作用，這些進程都將永遠不能再向前推進。 產(chǎn)生死鎖的原因： （1） 競爭資源，當系統(tǒng)中供多個進程所共享的資源，不足以同時滿足它們的 需要時，引起它們對資源的競爭而產(chǎn)生死鎖； （2） 進程推進順序非法，進程在運行過程中，請求和釋放資源的順序不當， 導(dǎo)致進程死鎖。 產(chǎn)生死鎖的必要條件： （1） 互斥條件 進程對所分配到的資源進行排他性使用。如果此時還有其他進程請求該資源，請求者只能阻塞，直到占有該資源的進程釋放該資源。 （2） 請求和保持條件 進程已經(jīng)保持了至少一個資源，但又提出了新的資源要求，而該資源又已被其他進程占有，此時請求進程阻塞，但請求進程又對已經(jīng)獲得的其他資源保持不放。 （3） 不剝奪條件 進程已獲得的資源，在未使用完之前，不能被剝奪，只能在使用完后由自己釋放。 （4） 環(huán)路等待條件 在發(fā)生死鎖時，必然存在一個進程資源的環(huán)形鏈。29、請詳細說明可通過哪些途徑預(yù)防死鎖？ 【解】可以通過： （1） 摒棄“請求和保持”條件，系統(tǒng)要求所有進程要一次性地申請 在整個運行過程所需的全部資源。如系統(tǒng)有足夠的資源分配給進程，便一次性的把其所需要的所有資源分配給該進程。這樣，該進程在整個運行期間，便不會再提出資源要求，從而摒棄了請求條件。但在分配時，只要有一種資源要求得不到滿足，則即使是已有的其他資源，也全部不分配給該進程，而讓該進程等待。這樣，由于等待期間的進程未占有任何資源，因而也摒棄了保持條件，從而可以避免發(fā)生死鎖。 （2） 摒棄“不剝奪”條件，進程是在需要資源時才提出請求，這樣， 一個已經(jīng)保持了某些資源的進程，當它在提出新的資源要求而不能立即得到滿足時，必須釋放它已經(jīng)保持的所有資源，待以后需要時再重新申請。這意味著進程已經(jīng)占有的資源，在運行過程中可能會暫時釋放，也可認為是被剝奪了，從而摒棄了“不剝奪條件”。 （3） 摒棄“環(huán)路等待”條件，系統(tǒng)將所有資源按類型進行線性排隊， 并賦予不同的序號。所有進程對資源的請求必須嚴格按資源序號遞增的次序提出，這樣，在所形成的資源分配圖中，不可能再出現(xiàn)環(huán)路，從而摒棄了“環(huán)路等待”條件。 30、在銀行家算法的例子中，如果P0發(fā)出的請求向量由Request(0,2,0)）改為Request(0,1,0)，問系統(tǒng)可否將資源分配給它？ 【解】能。 request0(0,1,0)need0(7,4,3);request0(0,1,0)available(2,3,0); 系統(tǒng)暫時先假定可為P0分配資源，并修改有關(guān)數(shù)據(jù)，如下所示： allocation need available A B C A B C A B C P0 0 2 0 7 3 3 2 2 0 P1 3 0 2 0 2 0 P2 3 0 2 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1 存在一個安全序列P1,P3,P0,P2,P4，故系統(tǒng)是安全的，可以分配資源。31、在銀行家算法中，若出現(xiàn)下述資源分配情況： Process Allocation Need Available P0 0 0 3 2 0 0 1 2 1 6 2 2 P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6 P3 0 3 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6 試問： （1）該狀態(tài)是否安全？ （2）若進程P2提出請求Request（1，2，2，2）后，系統(tǒng)能否將資源分配給它？ 【解】（1）利用安全性算法對上面的狀態(tài)進行分析（見下表），找到了一個安全序列P0,P3,P4,P1,P2，故系統(tǒng)是安全的。 Work Need Allocation Work+Allocation Finish P0 1 6 2 2 0 0 1 2 0 0 3 2 1 6 5 4 trueP3 1 6 5 4 0 6 5 2 0 3 3 2 1 9 8 6 true P4 1 9 8 6 0 6 5 6 0 0 1 4 1 9 9 10 true P1 1 9 9 10 1 7 5 0 1 0 0 0 2 9 9 10 true P2 2 9 9 10 2 3 5 6 1 3 5 4 3 12 14 14 true （2）P2發(fā)出請求向量Request(1,2,2,2),系統(tǒng)按銀行家算法進行檢查： Request2(1,2,2,2)=Need2(