操作系统概念第七版答案(含编程代码)

programming for a process that wishes obtain a number of resources: while (decrease count(count) == -1);

Rewrite the resource-manager code segment using a monitor and con- dition variables so that the decrease count() function suspends the process until sufficient resources are available. This will allow a process to invoke decrease count() by simply calling decrease_count(count);

The process will only return from this function call when sufficient resources are available.

Answer:

monitor resources

{ int available_resources; condition resources_avail; int decrease_count(int count)

{ while (available_resources < count) resources_avail.wait(); available_resources -= count; }

int increase_count(int count) { available_resources += count; resources_avail.signal(); } }

Chapter 7

7.1 Consider the traffic deadlock depicted in Figure 7.1.

word文档 可自由复制编辑

a. Show that the four necessary conditions for deadlock indeed hold in this example. b. State a simple rule for avoiding deadlocks in this system.

Figure 7.1 Traffic deadlock for Exercise 7.1.

Answer:

a. The four necessary conditions for a deadlock are (1) mutual exclu- sion;(2) hold-and-wait; (3) no preemption; and (4) circular wait. The mutual exclusion condition holds as only one car can occupy a space in the roadway. Hold-and-wait occurs where a car holds onto their place in the roadway while they wait to advance in the roadway. A car cannot be removed (i.e. preempted) from its position in the roadway. Lastly, there is indeed a circular wait as each car is waiting for a subsequent car to advance. The circular wait condition is also easily observed from the graphic.

b. A simple rule that would avoid this traffic deadlock is that a car may not advance into an intersection if it is clear they will not be able to immediately clear the intersection.

7.2 Consider the deadlock situation that could occur in the dining-philosophers problem when the philosophers obtain the chopsticks one at a time. Discuss how the four necessary conditions for deadlock indeed hold in this setting. Discuss how deadlocks could be avoided by eliminating any one of the four conditions.

Answer: Deadlock is possible because the four necessary conditions hold in the following manner: 1) mutual exclusion is required for chop- sticks, 2) the philosophers tend to hold onto the chopstick in hand while they wait for the other chopstick, 3) there is no preemption of chopsticks in the sense that a chopstick allocated to a philosopher cannot be forcibly taken away, and 4) there is a possibility of circular wait. Deadlocks could be avoided by overcoming the conditions in the following manner: 1) allow simultaneous sharing of chopsticks, 2) have the philosophers relin- quish the first chopstick if they are unable to obtain the other chopstick, 3) allow for chopsticks to be forcibly taken away if a

word文档 可自由复制编辑

philosopher has had a chopstick for a long period of time, and 4) enforce a numbering of the chopsticks and always obtain the lower numbered chopstick before obtaining the higher numbered one.

7.3 A possible solution for preventing deadlocks is to have a single, higher-order resource that must be requested before any other resource. For example, if multiple threads attempt to access the synchronization objects A… E , deadlock is possible. (Such synchronization objects may include mutexes, semaphores, condition variables, etc.) We can prevent the deadlock by adding a sixth object F . Whenever a thread wants to acquire the synchronization lock for any object A…E , it must first acquire the lock for object F . This solution is known as containment: The locks for objects A … E are contained within the lock for object F . Compare this scheme with the circular-wait scheme of Section 7.4.4.

Answer: This is probably not a good solution because it yields too large a scope. It is better to define a locking policy with as narrow a scope as possible.

7.4 Compare the circular-wait scheme with the deadlock-avoidance schemes (like the banker ’s algorithm) with respect to the following issues: a. Runtime overheads b. System throughput

Answer: A deadlock-avoidance scheme tends to increase the runtime overheads due to the cost of keep track of the current resource allocation. However, a deadlock-avoidance scheme allows for more concurrent use of resources than schemes that statically prevent the formation of dead- lock. In that sense, a deadlock-avoidance scheme could increase system throughput.

7.5 In a real computer system, neither the resources available nor the de- mands of processes for resources are consistent over long periods (months). Resources break or are replaced, new processes come and go, new re- sources are bought and added to the system. If deadlock is controlled by the banker ’s algorithm, which of the following changes can be made safely (without introducing the possibility of deadlock), and under what circumstances? a. Increase Available (new resources added).

b. Decrease Available (resource permanently removed from system)

c. Increase Max for one process (the process needs more resources than allowed, it may want more)

d. Decrease Max for one process (the process decides it does not need that many resources)

e. Increase the number of processes. f. Decrease the number of processes.

Answer:

a. Increase Available (new resources added) - This could safely be changed without

word文档 可自由复制编辑

any problems.

b. Decrease Available (resource permanently removed from system) - This could have an effect on the system and introduce the possibility of deadlock as the safety of the system assumed there were a certain number of available resources.

c. Increase Max for one process (the process needs more resources than allowed, it may want more) - This could have an effect on the system and introduce the possibility of deadlock.

d. Decrease Max for one process (the process decides it does not need that many resources) - This could safely be changed without any problems. e. Increase the number of processes - This could be allowed assum- ing that resources were allocated to the new process(es) such that the system does not enter an unsafe state.

f. Decrease the number of processes - This could safely be changed without any problems.

7.6 Consider a system consisting of four resources of the same type that are shared by three processes, each of which needs at most two resources.Show that the system is deadlock-free.

Answer: Suppose the system is deadlocked. This implies that each process is holding one resource and is waiting for one more. Since there are three processes and four resources, one process must be able to obtain two resources. This process requires no more resources and, therefore it will return its resources when done.

7.7 Consider a system consisting of m resources of the same type, being shared by n processes. Resources can be requested and released by processes only one at a time. Show that the system is deadlock free if the following two conditions hold:

a. The maximum need of each process is between 1 and m resources b. The sum of all maximum needs is less than m + n

Answer: Using the terminology of Section 7.6.2, we have:

nMax?m?n a. ?i?1ib. Maxi≥1 for all i

Proof: Needi = Maxi-Allocationi

If there exists a deadlock state then: c.

?ni?1Allocationi?m

Use a. to get: ∑Needi + ∑Allocationi = ∑Maxi < m+n Use c. to get: ∑Needi + m < m+n

nNeed?n Rewrite to get: ?i?1iThis implies that there exists a process Pi such that Needi=0. Since Maxi≥1 it

word文档 可自由复制编辑