操作系統(tǒng)第3章習(xí)題－答案

1、第3章 調(diào)度與死鎖一、單項(xiàng)選擇題1. 在為多道程序所提供的可共享的系統(tǒng)資源不足時(shí)，可能出現(xiàn)死鎖。但是，不適當(dāng)?shù)腳也可能產(chǎn)生死鎖。A. 進(jìn)程優(yōu)先權(quán)B. 資源的線性分配 =C. 進(jìn)程推進(jìn)順序D. 分配隊(duì)列優(yōu)先權(quán)2. 采用資源剝奪法可解除死鎖，還可以采用_方法解除死鎖。A. 執(zhí)行并行操作=B. 撤消進(jìn)程 C. 拒絕分配新資源D. 修改信號(hào)量3. 產(chǎn)生死鎖的四個(gè)必要條件是：互斥、_、循環(huán)等待和不剝奪。A. 請(qǐng)求與阻塞=B. 請(qǐng)求與保持 C. 請(qǐng)求與釋放D. 釋放與阻塞4. 發(fā)生死鎖的必要條件有四個(gè)，要防止死鎖的發(fā)生，可以破壞這四個(gè)必要條件，但破壞_條件是不太實(shí)際的。=A. 互斥 B. 不可搶占 C.

2、部分分配D. 循環(huán)等待5. 在分時(shí)操作系統(tǒng)中，進(jìn)程調(diào)度經(jīng)常采用_算法。A. 先來先服務(wù)B. 最高優(yōu)先權(quán) =C. 時(shí)間片輪轉(zhuǎn)D. 隨機(jī)6. 資源的按序分配策略可以破壞_條件。A. 互斥使用資源B. 占有且等待資源 C. 非搶奪資源=D. 環(huán)路等待資源7. 銀行家算法是一種_算法。A. 死鎖解除B. 死鎖避免 C. 死鎖預(yù)防D. 死鎖檢測8. _優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時(shí)確定的，確定之后在整個(gè)進(jìn)程運(yùn)行期間不再改變。A. 先來先服務(wù) =B. 靜態(tài) C. 動(dòng)態(tài)D. 短作業(yè)9. 某系統(tǒng)中有3個(gè)并發(fā)進(jìn)程，都需要同類資源4個(gè)，試問該系統(tǒng)不會(huì)發(fā)生死鎖的最少資源數(shù)是_。A. 9B. 10C. 11D. 1210. 以

3、優(yōu)先級(jí)為基礎(chǔ)的進(jìn)程調(diào)度算法可以保證在任何時(shí)候正在運(yùn)行的進(jìn)程總是諸就緒進(jìn)程中優(yōu)先級(jí)最高的進(jìn)程。上述描述是_。A. 正確的B. 錯(cuò)誤的11. 當(dāng)檢測出發(fā)生死鎖時(shí)，可以通過撤消一個(gè)進(jìn)程解除死鎖。上述描述是_。A. 正確的B. 錯(cuò)誤的12. 在下列解決死鎖的方法中，屬于死鎖預(yù)防策略的是_。A. 銀行家算法=B. 資源有序分配法 C. 死鎖檢測法 D. 資源分配圖化簡法13. _是作業(yè)存在的惟一標(biāo)志。A. 作業(yè)名B. 進(jìn)程控制塊 =C. 作業(yè)控制塊D. 程序名143個(gè)進(jìn)程A、B、C對(duì)某類資源的需求分別是7個(gè)、8個(gè)、3個(gè)。且目前已分別得到了3個(gè)、3個(gè)和2個(gè)資源，若系統(tǒng)還至少能提供_個(gè)資源，則系統(tǒng)是安全的。

4、 A. 1B. 2C. 5D. 1015系統(tǒng)中有某類資源12個(gè)供若干進(jìn)程共享，若每個(gè)進(jìn)程申請(qǐng)的資源量不超過4個(gè)，則最多允許_個(gè)進(jìn)程共享資源就可以保證系統(tǒng)是安全的。A. 3B. 4 C. 5D. 1216. 在各種作業(yè)調(diào)度算法中，若所有作業(yè)同時(shí)到達(dá)，則平均等待時(shí)間最短的算法是_。A. 先來先服務(wù) B. 優(yōu)先數(shù) C. 最高響應(yīng)比優(yōu)先=D. 短作業(yè)優(yōu)先17. 既考慮作業(yè)等待時(shí)間，又考慮作業(yè)執(zhí)行時(shí)間的調(diào)度算法是_。=A. 響應(yīng)比高者優(yōu)先B. 短作業(yè)優(yōu)先 C. 優(yōu)先級(jí)調(diào)度D. 先來先服務(wù)18. _是指從作業(yè)提交給系統(tǒng)到作業(yè)完成的時(shí)間間隔。=A. 周轉(zhuǎn)時(shí)間B. 響應(yīng)時(shí)間 C. 等待時(shí)間D. 運(yùn)行時(shí)間19.

5、 下述作業(yè)調(diào)度算法中，_調(diào)度算法與作業(yè)的估計(jì)運(yùn)行時(shí)間有關(guān)。A. 先來先服務(wù)=B. 短作業(yè)優(yōu)先 C. 均衡D. 時(shí)間片輪轉(zhuǎn)二、填空題1. 作業(yè)調(diào)度又稱 高級(jí)調(diào)度，長調(diào)度 。其主要功能是 接納作業(yè)，并為作業(yè)做好運(yùn)行前的準(zhǔn)備工作和作業(yè)完成后的善后處理工作。2. 低級(jí)調(diào)度也稱為_進(jìn)程_調(diào)度，常采用非搶占_和_搶占_兩種調(diào)度方式。3. 引入中級(jí)調(diào)度的目的是提高內(nèi)存利用率和 系統(tǒng)吞吐量 。4. 設(shè)有一組作業(yè)，它們的提交時(shí)間及運(yùn)行時(shí)間如下：作業(yè)號(hào)提交時(shí)間運(yùn)行時(shí)間（分鐘）19:007029:403039:5010410:105在單道方式下，采用短作業(yè)優(yōu)先調(diào)度算法，作業(yè)的執(zhí)行順序是_1。4。3。2_。5. 搶占

6、方式調(diào)度的搶占原則是（優(yōu)先權(quán)）、（短作業(yè)）和（時(shí)間片 ）。6. 死鎖是指在系統(tǒng)中的多個(gè)_進(jìn)程_無限期地等待永遠(yuǎn)不會(huì)發(fā)生的條件。7. 多處理機(jī)系統(tǒng)中，根據(jù)系統(tǒng)中所用的處理器是否相同可分（對(duì)稱多處理機(jī)系統(tǒng) ）和（非對(duì)稱多處理機(jī)系統(tǒng) ）兩類。8. 在_FCFS_調(diào)度算法中，按照進(jìn)程進(jìn)入就緒隊(duì)列的先后次序來分配處理機(jī)。9. 進(jìn)程調(diào)度算法采用時(shí)間片輪轉(zhuǎn)法時(shí)，時(shí)間片過大，就會(huì)使輪轉(zhuǎn)法變化為（先來先服務(wù)）調(diào)度算法。10. 如果要求所有進(jìn)程一次性申請(qǐng)它所需要的全部資源。若系統(tǒng)有足夠的資源分配給進(jìn)程，便一次把所有的資源分配給該進(jìn)程。但在分配時(shí)只要有一種資源要求不能滿足，則資源全不分配，進(jìn)程等待。這種死鎖預(yù)防方法

7、破壞了死鎖產(chǎn)生必要條件中的_請(qǐng)求和保持_條件。11. 對(duì)待死鎖，一般應(yīng)考慮死鎖的預(yù)防、避免、檢測和解除四個(gè)問題。典型的銀行家算法是屬于 避免 ，破壞環(huán)路等待條件是屬于 預(yù)防 ，而剝奪資源是 解除 的基本方法。12銀行家算法中，當(dāng)一個(gè)進(jìn)程提出的資源請(qǐng)求將導(dǎo)致系統(tǒng)從 安全狀態(tài) 進(jìn)入 不安全狀態(tài) 時(shí)，系統(tǒng)就拒絕它的資源請(qǐng)求。13采用有序分配策略可以防止死鎖，但是實(shí)現(xiàn)該策略時(shí)最大的困難是(如何確定資源的編號(hào))14操作系統(tǒng)中解決死鎖問題的方法有3種，即死鎖預(yù)防，死鎖避免和死鎖解除。15對(duì)于內(nèi)存和處理機(jī)兩種資源可以采用搶奪式分配。16.若要使當(dāng)前運(yùn)行進(jìn)程總是優(yōu)先級(jí)最高的進(jìn)程，應(yīng)選擇可剝奪最高優(yōu)先級(jí)優(yōu)先進(jìn)程

8、調(diào)度算法17.最高優(yōu)先權(quán)優(yōu)先調(diào)度算法，優(yōu)先權(quán)的確定基于靜態(tài)特性和動(dòng)態(tài)特性18.在有m個(gè)進(jìn)程的系統(tǒng)中出現(xiàn)死鎖時(shí)，死鎖進(jìn)程的個(gè)數(shù)應(yīng)該滿足的條件是 2km三 、 問答題1、 比較Fcfs和Spf 兩種進(jìn)程調(diào)度算法。2、 為什么多級(jí)反饋隊(duì)列調(diào)度算法能較好地滿足各方面用戶的需求？3、 何謂死鎖？死鎖產(chǎn)生的原因和必要條件是什么？4、 有人認(rèn)為“只要實(shí)現(xiàn)了共享資源的互斥使用，系統(tǒng)就不會(huì)死鎖”，這種觀點(diǎn)對(duì)嗎？5、 為什么銀行家算法能夠避免死鎖的發(fā)生？四、分析題1. 為什么說采用有序資源分配法不會(huì)產(chǎn)生死鎖？解：為了便于說明，不妨設(shè)系統(tǒng)中有m類資源，n個(gè)進(jìn)程，分別用R1，R2，Rm（1，2，m可看作資源編號(hào)）和P

9、1，P2， Pn表示。根據(jù)有序資源分配法可知，進(jìn)程申請(qǐng)資源時(shí)必須按照資源編號(hào)的升序進(jìn)行，即任何進(jìn)程在占有了Ri類資源后，再申請(qǐng)的資源Rj的編號(hào)j一定大于i。因此在任一時(shí)刻，系統(tǒng)中至少存在一個(gè)進(jìn)程Pk，它占有了較高編號(hào)的資源Rh，且它繼續(xù)請(qǐng)求的資源必然是空閑的，因而Pk可以一直向前推進(jìn)直至完成，當(dāng)Pk運(yùn)行完成后即會(huì)釋放它占有的所有資源；在Pk完成之后，剩下的進(jìn)程集合中同樣會(huì)存在一個(gè)進(jìn)程，它占有了較高編號(hào)的資源，且它繼續(xù)請(qǐng)求的資源必然是空閑的，因而它可以一直向前推進(jìn)直至完成；以此類推，所有進(jìn)程均可運(yùn)行完成，故不會(huì)發(fā)生死鎖。2. 有相同類型的5個(gè)資源被4個(gè)進(jìn)程所共享，且每個(gè)進(jìn)程最多需要2個(gè)這樣的資源

10、就可以運(yùn)行完畢。試問該系統(tǒng)是否會(huì)由于對(duì)這種資源的競爭而產(chǎn)生死鎖。解：該系統(tǒng)不會(huì)由于對(duì)這種資源的競爭而產(chǎn)生死鎖。因?yàn)樵谧顗那闆r下，每個(gè)進(jìn)程都需要2個(gè)這樣的資源，且每個(gè)進(jìn)程都已申請(qǐng)到了1個(gè)資源，那么系統(tǒng)中還剩下1個(gè)可用資源。無論系統(tǒng)為了滿足哪個(gè)進(jìn)程的資源申請(qǐng)而將資源分配給該進(jìn)程，都會(huì)因?yàn)樵撨M(jìn)程已獲得了它所需要的全部資源而確保它運(yùn)行完畢，從而可將它占有的2個(gè)資源歸還給系統(tǒng)，這就保證了其余三個(gè)進(jìn)程能順利運(yùn)行。由此可知，該系統(tǒng)不會(huì)由于對(duì)這種資源的競爭而產(chǎn)生死鎖。3.考慮下列資源分配策略：對(duì)資源的申請(qǐng)和釋放可以在任何時(shí)候進(jìn)行。如果一個(gè)進(jìn)程提出資源請(qǐng)求時(shí)得不到滿足，若此時(shí)無 由于等待資源而被阻塞的進(jìn)程，則自

11、己就被阻塞；若此時(shí)已有等待資源而被阻塞的進(jìn)程，則檢查所有由于等待資源而被阻塞的進(jìn)程。如果它們有申請(qǐng)進(jìn)程所需要的資源，則將這些資源取出分配給申請(qǐng)進(jìn)程。例如，考慮一個(gè)有3類資源的系統(tǒng)，系統(tǒng)所有可用資源為（4，2，2），進(jìn)程A申請(qǐng)（2，2，1），可滿足；進(jìn)程B申請(qǐng)（1，0，1），可滿足；若A再申請(qǐng)（0，0，1），則被阻塞。此時(shí)，若C請(qǐng)求（2，0，0），它可以分到剩余資源（1，0，0），并從A已分到的資源中獲得一個(gè)資源，于是進(jìn)程A的分配向量變成（1，2，1）而需求向量變成（1，0，1）。 這種分配策略會(huì)導(dǎo)致死鎖嗎？如果會(huì)，請(qǐng)舉一個(gè)例子；如果不會(huì)，請(qǐng)說明產(chǎn)生死鎖的哪一個(gè)必要條件不成立？ 這種分配方式會(huì)導(dǎo)

12、致某些進(jìn)程的無限等待嗎？為什么？解：本題所給的資源分配策略不會(huì)產(chǎn)生死鎖。因?yàn)楸绢}給出的分配策略規(guī)定若一進(jìn)程的資源得不到滿足，則檢查所有由于等待資源而被阻塞的進(jìn)程，如果它們有申請(qǐng)進(jìn)程所需要的資源，則將這些資源取出分配給申請(qǐng)進(jìn)程。從而破壞了產(chǎn)生死鎖必要條件中的不剝奪條件，這樣系統(tǒng)就不會(huì)產(chǎn)生死鎖。這種方法會(huì)導(dǎo)致某些進(jìn)程無限期的等待。因?yàn)楸蛔枞M(jìn)程的資源可以被剝奪，所以被阻塞進(jìn)程所擁有的資源數(shù)量在其被喚醒之前只可能減少。若系統(tǒng)中不斷出現(xiàn)其他進(jìn)程申請(qǐng)資源，這些進(jìn)程申請(qǐng)的資源與被阻塞進(jìn)程申請(qǐng)或擁有的資源類型相同且不被阻塞，則系統(tǒng)無法保證被阻塞進(jìn)程一定能獲得所需要的全部資源。例如，本題中的進(jìn)程A申請(qǐng)（2，2

13、，1）后再申請(qǐng)（0，0，1）被阻塞。此后，進(jìn)程C又剝奪了進(jìn)程A的一個(gè)資源，使得進(jìn)程A擁有的資源變?yōu)椋?，2，1），其需求向量為（1，0，1）。之后，若再創(chuàng)建的進(jìn)程總是只申請(qǐng)第1和第3類資源，總是占有系統(tǒng)所剩下的第1和第3類資源的全部且不阻塞，那么進(jìn)程A將會(huì)無限期地等待。4.一臺(tái)計(jì)算機(jī)有8臺(tái)磁帶機(jī)。它們由N個(gè)進(jìn)程競爭使用，每個(gè)進(jìn)程可能需要3臺(tái)磁帶機(jī)。請(qǐng)問N為多少時(shí)，系統(tǒng)沒有死鎖危險(xiǎn)，并說明原因。解：當(dāng)N為1，2，3時(shí)，系統(tǒng)沒有產(chǎn)生死鎖的危險(xiǎn)。因?yàn)?，?dāng)系統(tǒng)中只有1個(gè)進(jìn)程時(shí)，它最多需要3臺(tái)磁帶機(jī)，而系統(tǒng)有8臺(tái)磁帶機(jī)，其資源數(shù)目已足夠系統(tǒng)內(nèi)的1個(gè)進(jìn)程使用，因此絕不可能發(fā)生死鎖；當(dāng)系統(tǒng)中有2個(gè)進(jìn)程時(shí)，最

14、多需要6臺(tái)磁帶機(jī)，而系統(tǒng)有8臺(tái)磁帶機(jī)，其資源數(shù)目也足夠系統(tǒng)內(nèi)的2個(gè)進(jìn)程使用，因此也不可能發(fā)生死鎖；當(dāng)系統(tǒng)中有3個(gè)進(jìn)程時(shí)，在最壞情況下，每個(gè)進(jìn)程都需要3個(gè)這樣的資源，且假定每個(gè)進(jìn)程都已申請(qǐng)到了2個(gè)資源，那么系統(tǒng)中還剩下2個(gè)可用資源，無論系統(tǒng)為了滿足哪個(gè)進(jìn)程的資源申請(qǐng)而將資源分配給該進(jìn)程，都會(huì)因?yàn)樵撨M(jìn)程已獲得了它所需要的全部資源而確保它運(yùn)行完畢，從而可將它占有的3個(gè)資源歸還給系統(tǒng)，這就保證了其余進(jìn)程能順利運(yùn)行完畢。由此可知，當(dāng)N為1，2，3時(shí)，該系統(tǒng)不會(huì)由于對(duì)這種資源的競爭而產(chǎn)生死鎖。5.設(shè)系統(tǒng)中有3種類型的資源（A，B，C）和5個(gè)進(jìn)程P1、P2、P3、P4、P5，A資源的數(shù)量為17，B資源的數(shù)量

15、為5，C資源的數(shù)量為20。在T0時(shí)刻系統(tǒng)狀態(tài)見下表所示。系統(tǒng)采用銀行家算法實(shí)施死鎖避免策略。T0時(shí)刻系統(tǒng)狀態(tài)最大資源需求量已分配資源數(shù)量ABCABCP1559212P2536402P34011405P4425204P5424314剩余資源ABC233 T0時(shí)刻是否為安全狀態(tài)？若是，請(qǐng)給出安全序列。 在T0時(shí)刻若進(jìn)程P2請(qǐng)求資源（0，3，4），是否能實(shí)施資源分配？為什么？ 在的基礎(chǔ)上，若進(jìn)程P4請(qǐng)求資源（2，0，1），是否能實(shí)施資源分配？為什么？ 在的基礎(chǔ)上，若進(jìn)程P1請(qǐng)求資源（0，2，0），是否能實(shí)施資源分配？為什么？解：由題目所給出的最大資源需求量和已分配資源數(shù)量，可以計(jì)算出T0時(shí)刻各進(jìn)程的

16、資源需求量Need，Need最大資源需求量分配資源數(shù)量：資源需求量ABCP1347P2134P3006P4221P5110 利用銀行家算法對(duì)此時(shí)刻的資源分配情況進(jìn)行分析，可得此時(shí)刻的安全性分析情況：WorkNeedAllocationWork+AllocationFinishP52 3 31 1 03 1 45 4 7trueP45 4 72 2 12 0 47 4 11trueP37 4 110 0 64 0 511 4 16trueP211 4 161 3 44 0 215 4 18trueP115 4 183 4 72 1 217 5 20true從上述情況分析中可以看出，此時(shí)存在一個(gè)安

17、全序列P5，P4，P3，P2，P1，故該狀態(tài)是安全的。 在T0時(shí)刻若進(jìn)程P2請(qǐng)求資源（0，3，4），因請(qǐng)求資源數(shù)（0，3，4）剩余資源數(shù)（2，2，3），所以不能分配。 在的基礎(chǔ)上，若進(jìn)程P4請(qǐng)求資源（2，0，1），按銀行家算法進(jìn)行檢查： P4請(qǐng)求資源（2，0，1） P4資源需求量（2，2，1） P4請(qǐng)求資源（2，0，1） 剩余資源數(shù)（2，3，3）試分配并修改相應(yīng)數(shù)據(jù)結(jié)構(gòu)，資源分配情況如下：AllocationNeedAvailableP12 1 23 4 70 3 2P24 0 21 3 4P34 0 50 0 6P44 0 50 2 0 P53 1 41 1 0再利用安全性算法檢查系統(tǒng)是否安

18、全，可得此時(shí)刻的安全性分析情況：WorkNeedAllocationWork+AlloFinishP40 3 20 2 04 0 54 3 7trueP54 3 71 1 03 1 47 4 11trueP37 4 110 0 64 0 511 4 16trueP211 4 161 3 44 0 215 4 18trueP115 4 183 4 72 1 217 5 20true從上述情況分析中可以看出，此時(shí)存在一個(gè)安全序列P4，P5，P3，P2，P1，故該狀態(tài)是安全的，可以立即將P4所申請(qǐng)的資源分配給它。 在的基礎(chǔ)上，若進(jìn)程P1請(qǐng)求資源（0，2，0），按銀行家算法進(jìn)行檢查： P1請(qǐng)求資源（0

19、，2，0） P1資源需求量（3，4，7） P1請(qǐng)求資源（0，2，0） 剩余資源數(shù)（0，3，2） 試分配并修改相應(yīng)數(shù)據(jù)結(jié)構(gòu)，資源分配情況如下：AllocationNeedAvailableP12 3 23 2 70 1 2P24 0 21 3 4P34 0 50 0 6P44 0 50 2 0 P53 1 41 1 0再利用安全性算法檢查系統(tǒng)是否安全，可用資源Available（0，1，2）已不能滿足任何進(jìn)程的資源需求，故系統(tǒng)進(jìn)入不安全狀態(tài)，此時(shí)系統(tǒng)不能將資源分配給P1。6. 若在后備作業(yè)隊(duì)列中等待運(yùn)行的同時(shí)有三個(gè)作業(yè)1、2、3，已知它們各自的運(yùn)行時(shí)間為a、b、c，且滿足關(guān)系abc，試證明采用短

20、作業(yè)優(yōu)先調(diào)度算法能獲得最小平均周轉(zhuǎn)時(shí)間。解：由于短作業(yè)優(yōu)先調(diào)度算法總是在后備作業(yè)隊(duì)列中選擇運(yùn)行時(shí)間最短的作業(yè)作為調(diào)度對(duì)象，因此對(duì)短作業(yè)優(yōu)先調(diào)度算法而言，這三個(gè)作業(yè)的總周轉(zhuǎn)時(shí)間為T1=a(ab)(abc)=3a2bc 若不按短作業(yè)優(yōu)先調(diào)度算法來調(diào)度這三個(gè)作業(yè)，不失一般性，假定調(diào)度順序?yàn)?、1、3，則其總周轉(zhuǎn)時(shí)間為T2=b(ba)(bac)=3b2ac 式得：T2T1=ba0由此可見，短作業(yè)優(yōu)先調(diào)度算法能獲得最小平均周轉(zhuǎn)時(shí)間。7. 設(shè)有4道作業(yè)，它們的提交時(shí)間及執(zhí)行時(shí)間如下：作業(yè)號(hào)提交時(shí)間執(zhí)行時(shí)間110.02.0210.21.0310.40.5410.50.3試計(jì)算在單道程序環(huán)境下，采用先來先服務(wù)調(diào)度算法和最短作業(yè)優(yōu)先調(diào)度算法時(shí)的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間，并指出它們的調(diào)度順序。（時(shí)間單位：小時(shí)，以十進(jìn)制進(jìn)行計(jì)算。）解：若采用先來先服務(wù)調(diào)度算法，則其調(diào)度順序?yàn)?、2、3、4。作業(yè)號(hào)提交時(shí)間執(zhí)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間110.02.010.012.02.01.0210.21.012.0