操作系統(tǒng)第七章翻譯

1、 第七章 翻譯 第七組 黃常君 周妮7.1 List three examples of deadlocks that are not related to a computer systemenvironment. 列出三個(gè)與一個(gè)計(jì)算機(jī)系統(tǒng)環(huán)境不相關(guān)的死鎖的例子。Answer: Two cars crossing a single-lane bridge from opposite directions. 兩輛車從相反的方向跨越單線橋. A person going down a ladder while another person is climbing upthe ladder. 當(dāng)一

2、個(gè)人下梯子時(shí)另一個(gè)人在爬上梯子。 Two trains traveling toward each other on the same track. 兩列火車朝向?qū)Ψ酵瑯拥馁惖礼倎怼?Two carpenters who must pound nails. There is a single hammerand a single bucket of nails. Deadlock occurs if one carpenter hasthe hammer and the other carpenter has the nails. 有兩位木匠必須釘釘子?，F(xiàn)在有一個(gè)單一的錘子和一桶釘子。如果一個(gè)

3、木匠只分得一把錘子,而另一個(gè)木匠只能得釘子。那么就發(fā)生了死鎖。7.2 Suppose that a system is in an unsafe state. Show that it is possible forthe processes to complete their execution without entering a deadlockstate. 假設(shè)一個(gè)系統(tǒng)是在一個(gè)不安全的狀態(tài)。說明這可能是一個(gè)進(jìn)程完成地執(zhí)行而沒有進(jìn)入一個(gè)死鎖狀態(tài)。Answer: An unsafe state may not necessarily lead to deadlock, it justmea

4、ns that we cannot guarantee that deadlock will not occur. Thus, itis possible that a system in an unsafe state may still allow all processesto complete without deadlock occurring. Consider the situation wherea system has 12 resources allocated among processes P0, P1, and P2. Theresources are allocat

5、ed according to the following policy: 答案： 一個(gè)不安全的狀態(tài)不一定導(dǎo)致死鎖,它僅僅意味著我們不能保證死鎖不會(huì)再次發(fā)生。因此,可能是一個(gè)系統(tǒng)在一個(gè)不安全的狀態(tài)還可以讓所有的進(jìn)程完成而沒有死鎖發(fā)生?？紤]到這樣的情況，一個(gè)系統(tǒng)有12個(gè)資源要分配給進(jìn)程P0，P1和P2。資源按照以下政策分配:Max Current Need當(dāng)前的最大的需求P0 10 5 5P1 4 2 2P2 9 3 622 Chapter 7 Deadlocks 第七章 死鎖for (int i = 0; i n; i+) / first find a thread that can fini

6、shfor (int j = 0; j n; j+) if (!finishj) boolean temp = true;for (int k = 0; k workk)temp = false;if (temp) / if this thread can finishfinishj = true;for (int x = 0; x m; x+)workx += workjx;Figure 7.1 Bankers algorithm safety algorithm. 銀行家算法的安全算法Currently there are two resources available. This sys

7、tem is in an unsafestate as process P1 could complete, thereby freeing a total of fourresources. But we cannot guarantee that processes P0 and P2 can complete.However, it is possible that a process may release resources beforerequesting any further. For example, process P2 could release a resource,t

8、hereby increasing the total number of resources to five. This allows processP0 to complete, which would free a total of nine resources, therebyallowing process P2 to complete as well. 目前有兩種資源。該系統(tǒng)是在一個(gè)不安全的狀態(tài)，從而進(jìn)程P1會(huì)完成然后釋放一共有四個(gè)資源。但我們不能保證進(jìn)程P0和P2可以完成。然而一個(gè)進(jìn)程可能可以釋放資源在其他進(jìn)程請求更多資源之前。例如, 進(jìn)程P2可能釋放一個(gè)資源,從而增加資源的總數(shù)

9、量到五個(gè)。這允許進(jìn)程P0完成,并將釋放資源共計(jì)9項(xiàng),從而允許P2也可以完成7.3 Prove that the safety algorithm presented in Section 7.5.3 requires anorder of m n2 operation. 在7.5.3部分，證明安全算法，要求用一個(gè)米n2的順序操作Answer:Figure 7.1 provides Java code that implement the safety algorithm ofthe bankers algorithm (the complete implementation of the ba

10、nkersalgorithm is available with the source code download).As can be seen, the nested outer loopsboth of which loop through ntimesprovide the n2 performance. Within these outer loops are twosequential inner loops which loop m times. The big-oh of this algorithmis therefore O(m n2). 答案： 圖7.1提供Java代碼的

11、安全算法,實(shí)現(xiàn)的銀行家的算法(銀行的完全實(shí)現(xiàn)算法可提供源代碼下載)?？梢钥闯?嵌套的外部loops-both循環(huán)n 次提高n2的性能。在這些外環(huán)是兩個(gè)內(nèi)部循環(huán),連續(xù)循環(huán)m次。這種算法是big-oh的，因此,O(mn2)。7.4 Consider a computer system that runs 5,000 jobs per month with nodeadlock-prevention or deadlock-avoidance scheme. Deadlocks occurabout twice per a month, and the operator must terminate

12、 and rerun about10 jobs per deadlock. Each job is worth about $2 (in CPU time), and thejobs terminated tend to be about half-done when they are aborted.A systems programmer has estimated that a deadlock-avoidancealgorithm (like the bankers algorithm) could be installed in the systemwith an increase

13、in the average execution time per job of about 10 percent.Since the machine currently has 30-percent idle time, all 5,000 jobs permonth could still be run, although turnaround time would increase byabout 20 percent on average. 考慮一個(gè)電腦系統(tǒng)運(yùn)行5000個(gè)作業(yè),每月沒有死鎖預(yù)防或死鎖避免方案。死鎖每月就會(huì)發(fā)生兩次,操作人員一定要終止和重新運(yùn)行10作業(yè)的死鎖。每個(gè)作業(yè)值約

14、$ 2(CPU時(shí)間)，當(dāng)運(yùn)行到一半失敗時(shí)作業(yè)往往會(huì)終止。一個(gè)系統(tǒng)程序員估計(jì),有一個(gè)死鎖避免算法(如銀行家的算法)可以在系統(tǒng)上安裝，增加平均每工作執(zhí)行時(shí)間的10%左右。由于這臺(tái)機(jī)器目前有30%的空閑時(shí)間,全部的5000個(gè)作業(yè)每個(gè)月仍然可以運(yùn)行,盡管轉(zhuǎn)機(jī)時(shí)間將會(huì)增加大約20%的平均水平。Practice Exercises 23 練習(xí)活動(dòng)23a. What are the arguments for installing安裝 the deadlock-avoidancealgorithm? a. 安裝死鎖避免算法的理由是什么?b. What are the arguments against in

15、stalling the deadlock-avoidancealgorithm? b. 有什么理由反對安裝死鎖避免算法?Answer: An argument for installing deadlock avoidance in the systemis that we could ensure deadlock would never occur. In addition, despitethe increase in turnaround time, all 5,000 jobs could still run. An argument against installing dead

16、lock avoidance software is that deadlocks occur infrequently and they cost little when they do occur. 答案： 一個(gè)觀點(diǎn),針對該系統(tǒng)安裝的死鎖是,我們可以確保死鎖不會(huì)發(fā)生。此外,盡管周轉(zhuǎn)時(shí)間增加,但所有的5000個(gè)作業(yè)仍能運(yùn)行。安裝死鎖避免軟件的理由是,避免死鎖發(fā)生頻繁,和消耗的資源會(huì)少些。7.5 Can a system detect that some of its processes are starving? If you answer“yes,” explain how it can.

17、 If you answer “no,” explain how the systemcan deal with the starvation problem.Answer: Starvation is a difficult topic to define as it may mean differentthings for different systems. For the purposes of this question, we willdefine starvation as the situation whereby a process must wait beyonda rea

18、sonable period of timeperhaps indefinitelybefore receiving arequested resource. One way of detecting starvation would be to firstidentify a period of timeTthat is considered unreasonable. When aprocess requests a resource, a timer is started. If the elapsed time exceedsT, then the process is conside

19、red to be starved. One strategy for dealing with starvation would be to adopt a policy where resources are assigned only to the process that has been waiting the longest. For example, if process Pa has been waiting longer for resource X than process Pb , the request from process Pb would be deferred

20、until process Pa s request has been satisfied. Another strategy would be less strict than what was just mentioned. In this scenario, a resource might be granted to a process that has waited less than another process, providing that the other process is not starving. However, if another process is co

21、nsidered to be starving, its requestwould be satisfied first. 一個(gè)系統(tǒng)能檢測到某些進(jìn)程正處于饑餓狀態(tài)嗎?如果你回答“是的,”解釋它如何檢測。如果你回答“沒有”,說明該系統(tǒng)能處理這個(gè)饑餓問題。答:饑餓是一個(gè)很難定義的主題,因?yàn)樗诓煌南到y(tǒng)可能意味著不同的事情。為了更好的理解這個(gè)問題,我們將規(guī)定饑餓的不同情況,確定進(jìn)程必須等待超越假設(shè)時(shí)間假設(shè)無限期，在合理期限內(nèi)收到請求的資源之前。饑餓的一種方式是第一次檢測確定一段時(shí)間T，那是被認(rèn)為不合理的。當(dāng)一個(gè)進(jìn)程要求資源,有一個(gè)開始。如果總共用時(shí)超過T,然后進(jìn)程被認(rèn)為是忍饑挨餓。一個(gè)戰(zhàn)略處理饑餓

22、會(huì)采取的政策在資源分配的過程中,只是一直在等待最長的時(shí)間。例如,如果Pa進(jìn)程一直在等待資源X的時(shí)間比進(jìn)程Pb的長,請求進(jìn)程Pb會(huì)被延遲。直到Pa進(jìn)程要求已經(jīng)得到滿足。另一個(gè)策略就會(huì)比剛才提到的少一些嚴(yán)格的要求。在這種情況下,一個(gè)資源可能授予一個(gè)進(jìn)程,之后如等待時(shí)間少于另一個(gè)進(jìn)程,則提供給其他并不餓的進(jìn)程。然而,如果另一個(gè)進(jìn)程被認(rèn)為是饑餓,其要求第一次就滿足了。7.6 Consider the following resource-allocation policy. Requests and releasesfor resources are allowed at any time. If a

23、 request for resources cannotbe satisfied because the resources are not available, then we check anyprocesses that are blocked, waiting for resources. If they have the desiredresources, then these resources are taken away from them and are givento the requesting process. The vector of resources for

24、which the processis waiting is increased to include the resources that were taken away.For example, consider a system with three resource types and thevector Available initialized to (4,2,2). If process P0 asks for (2,2,1), it getsthem. If P1 asks for (1,0,1), it gets them. Then, if P0 asks for (0,0

25、,1), itis blocked (resource not available). If P2 now asks for (2,0,0), it gets theavailable one (1,0,0) and one that was allocated to P0 (since P0 is blocked).P0s Allocation vector goes down to (1,2,1) and its Need vector goes up to(1,0,1). 考慮以下的資源分配的政策。允許在任何時(shí)間對資源進(jìn)行請求和釋放。如果一個(gè)請求資源不能感到滿足那是因?yàn)橘Y源是無效的,那么

26、,我們要檢查有沒有進(jìn)程被堵塞,等待資源。如果他們有理想的資源,那么這些資源可以離開他們,給要求的進(jìn)程。矢量的資源的進(jìn)程正在增加,包括資源被帶走。例如,考慮系統(tǒng)類型和三種資源初始化向量可用來(4、2、2)。如果進(jìn)程P0要求(2、2、1),它得到他們的機(jī)會(huì)。如果P1要求(1,0,1),它得到他們。然后,如果P0要求(0,0,1),它被堵塞(資源不能提供)。如果P2現(xiàn)在要求(2 0,0),獲得了可用(1 - 0),并被分配給P0 (因?yàn)镻0堵住了)。P0的配置向量(1、2、1)以及其所需矢量上升（1,0,1)。a. Can deadlock occur? If you answer “yes”, g

27、ive an example. If youanswer “no,” specify which necessary condition cannot occur. a. 死鎖會(huì)發(fā)生?如果你回答“是”,舉個(gè)例子吧。如果你回答“沒有”,指定不能發(fā)生有哪些必要條件。b. Can indefinite blocking occur? Explain your answer. b. 阻塞可以無限期發(fā)生?請解釋你的答案。24 Chapter 7 Deadlocks第七章 鎖Answer:a. Deadlock cannot occur because preemption exists. a. 死鎖不能

28、發(fā)生因?yàn)閾屨即嬖凇. Yes. A process may never acquire all the resources it needs if theyare continuously preempted by a series of requests such as those of process C. b. 是的。如果他們通過一系列的要求與C等過程不斷地?fù)屨?，那么一個(gè)進(jìn)程可能永遠(yuǎn)也不會(huì)獲得它需要的所有資源。7.7 Suppose that you have coded the deadlock-avoidance safety algorithmand now have been asked to implement the deadlock-detection algorithm.Can you do so by simply using the safety algorithm code andred