1、第三章 處理機(jī)的調(diào)度與死鎖1高級(jí)調(diào)度與低級(jí)調(diào)度的主要任務(wù)是什么？為什么要引入中級(jí)調(diào)度？答：高級(jí)調(diào)度的主要任務(wù)是根據(jù)某種算法，把外存上處于后備隊(duì)列中的那些作業(yè)調(diào)入內(nèi) 存。低級(jí)調(diào)度是保存處理機(jī)的現(xiàn)場(chǎng)信息，按某種算法先取進(jìn)程，再把處理器分配給進(jìn)程。引 入中級(jí)調(diào)度的主要目的是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。使那些暫時(shí)不能運(yùn)行的進(jìn)程不 再占用內(nèi)存資源，將它們調(diào)至外存等待，把進(jìn)程狀態(tài)改為就緒駐外存狀態(tài)或掛起狀態(tài)。2何謂作業(yè)、作業(yè)步和作業(yè)流？ 答：作業(yè)包含通常的程序和數(shù)據(jù)，還配有作業(yè)說(shuō)明書(shū)。系統(tǒng)根據(jù)該說(shuō)明書(shū)對(duì)程序的運(yùn)行 進(jìn)行控制。批處理系統(tǒng)中是以作業(yè)為基本單位從外存調(diào)入內(nèi)存。作業(yè)步是指每個(gè)作業(yè)運(yùn)行期間都必須

2、經(jīng)過(guò)若干個(gè)相對(duì)獨(dú)立相互關(guān)聯(lián)的順序加工的步驟。 作業(yè)流是指若干個(gè)作業(yè)進(jìn)入系統(tǒng)后依次存放在外存上形成的輸入作業(yè)流；在操作系統(tǒng)的控制 下，逐個(gè)作業(yè)進(jìn)程處理，于是形成了處理作業(yè)流。3.在什么情況下需要使用作業(yè)控制塊 JCB?其中包含了哪些內(nèi)容？答：每當(dāng)作業(yè)進(jìn)入系統(tǒng)時(shí)，系統(tǒng)便為每個(gè)作業(yè)建立一個(gè)作業(yè)控制塊JCB,根據(jù)作業(yè)類型將它插入到相應(yīng)的后備隊(duì)列中。 JCB 包含的內(nèi)容通常有：1）作業(yè)標(biāo)識(shí)2）用戶名稱3）用戶賬戶4）作業(yè)類型（CPU繁忙型、I/O 芳名型、批量型、終端型）5）作業(yè)狀態(tài)6）調(diào)度信息（優(yōu)先級(jí)、作業(yè)已運(yùn)行）7）資源要求8）進(jìn)入系統(tǒng)時(shí)間9）開(kāi)始處理時(shí)間10）作業(yè)完成時(shí)間11）作業(yè)退出時(shí)間12）資

3、源使用情況等4在作業(yè)調(diào)度中應(yīng)如何確定接納多少個(gè)作業(yè)和接納哪些作業(yè)？ 答:作業(yè)調(diào)度每次接納進(jìn)入內(nèi)存的作業(yè)數(shù)，取決于多道程序度。應(yīng)將哪些作業(yè)從外存調(diào)入 內(nèi)存，取決于采用的調(diào)度算法。最簡(jiǎn)單的是先來(lái)服務(wù)調(diào)度算法，較常用的是短作業(yè)優(yōu)先調(diào)度 算法和基于作業(yè)優(yōu)先級(jí)的調(diào)度算法 。5試說(shuō)明低級(jí)調(diào)度的主要功能。答：（1）保存處理機(jī)的現(xiàn)場(chǎng)信息（2）按某種算法選取進(jìn)程（3）把處理機(jī)分配給進(jìn)程。6在搶占調(diào)度方式中，搶占的原則是什么？答：搶占的原則有：時(shí)間片原則、優(yōu)先權(quán)原則、短作業(yè)優(yōu)先權(quán)原則等。7在選擇調(diào)度方式和調(diào)度算法時(shí)，應(yīng)遵循的準(zhǔn)則是什么？答： 1）面向用戶的準(zhǔn)則：周轉(zhuǎn)時(shí)間短、響應(yīng)時(shí)間快、截止時(shí)間的保證、優(yōu)先權(quán)準(zhǔn)則。

4、2）面向系統(tǒng)的準(zhǔn)則：系統(tǒng)吞吐量高、處理機(jī)利用率好、各類資源的平衡利用。8在批處理系統(tǒng)、分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)中，各采用哪幾種進(jìn)程（作業(yè)）調(diào)度算法？ 答：批處理系統(tǒng)的調(diào)度算法：短作業(yè)優(yōu)先、優(yōu)先權(quán)、高響應(yīng)比優(yōu)先、多級(jí)反饋隊(duì)列調(diào)度 算法。分時(shí)系統(tǒng)的調(diào)度算法： 時(shí)間片輪轉(zhuǎn)法。實(shí)時(shí)系統(tǒng)的調(diào)度算法： 最早截止時(shí)間優(yōu)先即 EDF 、 最低松弛度優(yōu)先即 LLF 算法。9何謂靜態(tài)和動(dòng)態(tài)優(yōu)先級(jí)？確定靜態(tài)優(yōu)先級(jí)的依據(jù)是什么？答：靜態(tài)優(yōu)先級(jí)是指在創(chuàng)建進(jìn)程時(shí)確定且在進(jìn)程的整個(gè)運(yùn)行期間保持不變的優(yōu)先級(jí)。動(dòng) 態(tài)優(yōu)先級(jí)是指在創(chuàng)建進(jìn)程時(shí)賦予的優(yōu)先權(quán)，可以隨進(jìn)程推進(jìn)或隨其等待時(shí)間增加而改變的優(yōu) 先級(jí)，可以獲得更好的調(diào)度性能。確定進(jìn)程

5、優(yōu)先級(jí)的依據(jù)：進(jìn)程類型、進(jìn)程對(duì)資源的需求和 用戶要求。10. 試比較FCFS和SPF兩種進(jìn)程調(diào)度算法。答：相同點(diǎn)：兩種調(diào)度算法都可以用于作業(yè)調(diào)度和進(jìn)程調(diào)度。不同點(diǎn)：FCFS調(diào)度算法每次都從后備隊(duì)列中選擇一個(gè)或多個(gè)最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存、分配資源、創(chuàng)建進(jìn)程、插入到就緒隊(duì)列。該算法有利于長(zhǎng)作業(yè) / 進(jìn)程，不利于 短作業(yè) /進(jìn)程。 SPF 算法每次調(diào)度都從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作 業(yè)，調(diào)入內(nèi)存中運(yùn)行。該算法有利于短作業(yè) /進(jìn)程，不利于長(zhǎng)作業(yè) / 進(jìn)程。11. 在時(shí)間片輪轉(zhuǎn)法中，應(yīng)如何確定時(shí)間片的大小？ 答：時(shí)間片應(yīng)略大于一次典型的交互需要的時(shí)間。一般應(yīng)考慮三個(gè)因素

6、：系統(tǒng)對(duì)相應(yīng)時(shí)間的要求、就緒隊(duì)列中進(jìn)程的數(shù)目和系統(tǒng)的處理能力。12. 通過(guò)一個(gè)例子來(lái)說(shuō)明通常的優(yōu)先級(jí)調(diào)度算法不能適用于實(shí)時(shí)系統(tǒng)？ 答：實(shí)時(shí)系統(tǒng)的調(diào)度算法很多， 主要是基于任務(wù)的開(kāi)始截止時(shí)間和任務(wù)緊急 / 松弛程度的任務(wù)優(yōu)先級(jí)調(diào)度算法， 通常的優(yōu)先級(jí)調(diào)度算法不能滿足實(shí)時(shí)系統(tǒng)的調(diào)度實(shí)時(shí)性要求而不適用。13. 為什么說(shuō)多級(jí)反饋隊(duì)列調(diào)度算法能較好地滿足各方面用戶的需求？ 答：（1）終端型作業(yè)用戶提交的作業(yè)大多屬于較小的交互型作業(yè)，系統(tǒng)只要使這些作業(yè)在第一隊(duì)列規(guī)定的時(shí)間片內(nèi)完成，終端作業(yè)用戶就會(huì)感到滿足。（2）短批處理作業(yè)用戶，開(kāi)始時(shí)像終端型作業(yè)一樣，如果在第一隊(duì)列中執(zhí)行一個(gè)時(shí)間片 段即可完成，便可獲得

7、與終端作業(yè)一樣的響應(yīng)時(shí)間。對(duì)于稍長(zhǎng)作業(yè)，通常只需在第二和第三 隊(duì)列各執(zhí)行一時(shí)間片即可完成，其周轉(zhuǎn)時(shí)間仍然較短。（3）長(zhǎng)批處理作業(yè)，它將依次在第1, 2, n個(gè)隊(duì)列中運(yùn)行，然后再按輪轉(zhuǎn)方式運(yùn)行， 用戶不必?fù)?dān)心其作業(yè)長(zhǎng)期得不到處理。所以，多級(jí)反饋隊(duì)列調(diào)度算法能滿足多用戶需求14. 為什么在實(shí)時(shí)系統(tǒng)中，要求系統(tǒng)（尤其是 CPU）具有較強(qiáng)的處理能力？答：實(shí)時(shí)系統(tǒng)中通常有著多個(gè)實(shí)時(shí)任務(wù)。若處理機(jī)的處理能力不夠強(qiáng)，有可能因?yàn)樘幚?機(jī)忙不過(guò)來(lái)而使某些實(shí)時(shí)任務(wù)得不到及時(shí)處理，導(dǎo)致發(fā)生難以預(yù)料的后果。15按照調(diào)度方式可將實(shí)時(shí)調(diào)度算法分為哪幾種？答：可分為非搶占式和搶占式兩種算法。而非搶占式算法又分為非搶占式輪轉(zhuǎn)

8、和優(yōu)先調(diào) 度算法；搶占式調(diào)度算法又分為基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)和立即搶占式優(yōu)先權(quán)調(diào)度算法。16.什么是最早截止時(shí)間優(yōu)先調(diào)度算法？舉例說(shuō)明。答：根據(jù)任務(wù)的開(kāi)始截止時(shí)間確定的任務(wù)優(yōu)先級(jí)調(diào)度算法。截止時(shí)間越早則優(yōu)先級(jí)越高 該算法要求在系統(tǒng)中保持一個(gè)實(shí)時(shí)任務(wù)就緒隊(duì)列，該隊(duì)列按各任務(wù)截止時(shí)間的先后排序。舉 例：非搶占式調(diào)度方式用于非周期實(shí)時(shí)任務(wù)。圖3-9是將該算法用于非搶占調(diào)度方式之例。該例中具有四個(gè)非周期任務(wù)，它們先后到達(dá)。系統(tǒng)首先調(diào)度任務(wù) 1執(zhí)行，在任務(wù)1執(zhí)行期間, 任務(wù)2、3又先后到達(dá)。由于任務(wù)3的開(kāi)始截止時(shí)間早于任務(wù)2，故系統(tǒng)在任務(wù)1后將調(diào)度任 務(wù)3執(zhí)行。在此期間又到達(dá)作業(yè)4,其開(kāi)始截止時(shí)間仍

9、是早于任務(wù) 2的，故在任務(wù)3執(zhí)行完后,系統(tǒng)又調(diào)度任務(wù)4執(zhí)行，最后才調(diào)度任務(wù)2執(zhí)行。圖3-9 EDF算法用于非搶占調(diào)度的調(diào)度方式17.什么是最低松弛度優(yōu)先調(diào)度算法？舉例說(shuō)明之。答：該算法是根據(jù)任務(wù)緊急（或松弛）的程度，來(lái)確定任務(wù)的優(yōu)先級(jí)。任務(wù)的緊急程度愈高, 為該任務(wù)所賦予的優(yōu)先級(jí)就愈咼，以使之優(yōu)先執(zhí)行。例如，一個(gè)任務(wù)在 200 ms時(shí)必須完成， 而它本身所需的運(yùn)行時(shí)間就有100 ms因此，調(diào)度程序必須在100 ms之前調(diào)度執(zhí)行，該任務(wù) 的緊急程度（松弛程度）為100 ms。又如，另一任務(wù)在400 ms時(shí)必須完成，它本身需要運(yùn)行150 ms，則其松弛程度為250 ms18何謂死鎖？產(chǎn)生死鎖的原因

10、和必要條件是什么?答：死鎖是指多個(gè)進(jìn)程在運(yùn)行過(guò)程中因爭(zhēng)奪資源而造成的一種僵局，當(dāng)進(jìn)程處于這種僵 持狀態(tài)時(shí)，若無(wú)外力作用，它們都將無(wú)法再向前推進(jìn)。產(chǎn)生死鎖的原因?yàn)楦?jìng)爭(zhēng)資源和進(jìn)程間推進(jìn)順序非法。其必要條件是：互斥條件、請(qǐng)求和 保持條件、不剝奪條件、環(huán)路等待條件。19. 在解決死鎖問(wèn)題的幾個(gè)方法中，哪種方法最易于實(shí)現(xiàn)？哪種方法使資源利用率最高？答：解決死鎖的四種方法即預(yù)防、避免、檢測(cè)和解除死鎖中，預(yù)防死鎖最容易實(shí)現(xiàn)；避 免死鎖使資源的利用率最高。20. 請(qǐng)?jiān)敿?xì)說(shuō)明可通過(guò)哪些途徑預(yù)防死鎖。答：(1)擯棄“請(qǐng)求和保持”條件，就是如果系統(tǒng)有足夠資源，便一次性把進(jìn)程需要的 所有資源分配給它；(2) 擯棄“不

11、剝奪”條件，就是已經(jīng)擁有資源的進(jìn)程，當(dāng)它提出新資源請(qǐng)求而不能立即 滿足時(shí)，必須釋放它已保持的所有資源，待以后需要時(shí)再重新申請(qǐng)；(3) 擯棄“環(huán)路等待”條件，就是將所有資源按類型排序標(biāo)號(hào)，所有進(jìn)程對(duì)資源的請(qǐng)求 必須嚴(yán)格按序號(hào)遞增的次序提出。21. 在銀行家算法的例子中，如果 Po發(fā)出請(qǐng)求向量由ReqUeSt(0,2,(改為ReqUeSt(0,1,Q) 問(wèn)系統(tǒng)可否將資源分配給它？答：(1)可以。銀行家算法各種資源數(shù)量分別為10、5、7,在T0時(shí)刻的資源分配如圖所示：情況進(jìn)程MflXAllOCatiOnNeedAVailabIeABCABCABCABCPO/53O10/43332PI32220A 0

12、122P39023O2600P3222211011P4433002431(2)具體分析如下： RequSto(0,1,0)V=Needo(7,4,3); ReqUSt0(0,1,0)V=AVailable(3,3,2);系統(tǒng)先假定可為P0分配資源，并修改AVaiIabIeQ AllOCatiOn0和Need0向量，由此形成的資源變化情況如下圖所示：情況進(jìn)程MaXAiIQCatiQnNeedAVaiIabIeABCABCABCABCP。763O10743322Pl3222OO122P3gO23O26O0P3222211O11P4433OO2431(3)P0請(qǐng)求資源：P0發(fā)出請(qǐng)求向量ReqUSt0

13、(0,1,0系統(tǒng)按銀行家算法進(jìn)行檢查: ReqUSt0(0,1,0)V=Need0(7,4,3); ReqUSt0(0,1,0)V=AVailable(2,3,0); 系統(tǒng)暫時(shí)先假定可為P0分配資源，并修改 關(guān)數(shù)據(jù)，如下圖所示W(wǎng)OrkNeedAlIOcatiOnWork÷ AlIOCatiOnABCAB CABCABCFmiShPo32273o20342TUTePl342122200542THre巳5426OO302844TUTePJ844O112111055TUTeP*10 554310021057TLLre綜上所述系統(tǒng)可以將資源分配給它22銀行家算法中出現(xiàn)以下資源分配，試問(wèn)(1)

14、該狀態(tài)是否安全？ ( 2)若進(jìn)程P2提出ReqUeSt(1,2,2,后 ,系統(tǒng)能否將資源分配給它?PrOCeSSAllOCatiOnNeedAVailabIePO00 3 200 12162 2PLIOOO17 5 0P213 5 423 56Pa0 3 3 206 52P400 140 6 5 6試問(wèn)：（1）該狀態(tài)是否安全?（2）若進(jìn)程P2提出請(qǐng)求ReqUeSt（1,2,2,2后，系統(tǒng)能否將資源分配給它？（參考答案有 錯(cuò)）答：（1）安全，因?yàn)榇嬖诎踩蛄蠵0,P3,P4,P1,P2（2）系統(tǒng)能分配資源，分析如下。 ReqUeSt（1,2,2,2） V= Need2（2,3,5,6）; ReqUeSt（1,2,2,2） V= AVaiIabIe2（1,6,2；） 系統(tǒng)先假定可為P2分配資源，并修改 AVaiIable2, Allocation2和Need2向量，由此形成的資源變化情況如下圖所示:PrOCeSSAIIOCatianNeedAVaiIabIePo00 3 20 0 120 4 0 0PL100017 50P32 5 7 62 3 56P30 3 320 6 5 2P400 140 6 56再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。如下圖PrOCeSSWorkAIloCatiOnN