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

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

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

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

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

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

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

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

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

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

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

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

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

13、，1）后再申請（0，0，1）被阻塞。此后，進程C又剝奪了進程A的一個資源，使得進程A擁有的資源變?yōu)椋?，2，1），其需求向量為（1，0，1）。之后，若再創(chuàng)建的進程總是只申請第1和第3類資源，總是占有系統(tǒng)所剩下的第1和第3類資源的全部且不阻塞，那么進程A將會無限期地等待。4.一臺計算機有8臺磁帶機。它們由N個進程競爭使用，每個進程可能需要3臺磁帶機。請問N為多少時，系統(tǒng)沒有死鎖危險，并說明原因。解：當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個進程時，最

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

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

16、資源需求量Need，Need最大資源需求量分配資源數(shù)量：資源需求量ABCP1347P2134P3006P4221P5110 利用銀行家算法對此時刻的資源分配情況進行分析，可得此時刻的安全性分析情況：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從上述情況分析中可以看出，此時存在一個安

17、全序列P5，P4，P3，P2，P1，故該狀態(tài)是安全的。 在T0時刻若進程P2請求資源（0，3，4），因請求資源數(shù)（0，3，4）剩余資源數(shù)（2，2，3），所以不能分配。 在的基礎上，若進程P4請求資源（2，0，1），按銀行家算法進行檢查： P4請求資源（2，0，1） P4資源需求量（2，2，1） P4請求資源（2，0，1） 剩余資源數(shù)（2，3，3）試分配并修改相應數(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、全，可得此時刻的安全性分析情況：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從上述情況分析中可以看出，此時存在一個安全序列P4，P5，P3，P2，P1，故該狀態(tài)是安全的，可以立即將P4所申請的資源分配給它。 在的基礎上，若進程P1請求資源（0，2，0），按銀行家算法進行檢查： P1請求資源（0

19、，2，0） P1資源需求量（3，4，7） P1請求資源（0，2，0） 剩余資源數(shù)（0，3，2） 試分配并修改相應數(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）已不能滿足任何進程的資源需求，故系統(tǒng)進入不安全狀態(tài)，此時系統(tǒng)不能將資源分配給P1。6. 若在后備作業(yè)隊列中等待運行的同時有三個作業(yè)1、2、3，已知它們各自的運行時間為a、b、c，且滿足關系abc，試證明采用短

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