Import Settings: 
Base Settings: Brownstone Default
Highest Answer Letter: D
Multiple Keywords in Same Paragraph: No

Chapter: Chapter 7

Multiple Choice

1.  A deadlocked state occurs whenever ____.
A)  a process is waiting for I/O to a device that does not exist
B)  the system has no available free resources
C)  every process in a set is waiting for an event that can only be caused by another process in the set
D)  a process is unable to release its request for a resource after use

Ans:  C
Feedback: 7.1
Difficulty: Medium

2.  One necessary condition for deadlock is ____, which states that at least one resource must be held in a nonsharable mode.
A)  hold and wait
B)  mutual exclusion
C)  circular wait
D)  no preemption

Ans:  B
Feedback: 7.2.1
Difficulty: Medium

3. One necessary condition for deadlock is ______, which states that a process must be holding one resource and waiting to acquire additional resources.
A)  hold and wait
B)  mutual exclusion
C)  circular wait
D)  no preemption

Ans:  A
Feedback: 7.2.1
Difficulty: Easy

4. One necessary condition for deadlock is ______, which states that a resource can be released only voluntarily by the process holding the resource.
A)  hold and wait
B)  mutual exclusion
C)  circular wait
D)  no preemption

Ans:  D
Feedback: 7.2.1
Difficulty: Easy

5. One necessary condition for deadlock is ______, which states that there is a chain of waiting processes whereby P0 is waiting for a resource held by P1, P1 is waiting for a resource held by P2, and Pn is waiting for a resource held by P0.
A)  hold and wait
B)  mutual exclusion
C)  circular wait
D)  no preemption

Ans:  C
Feedback: 7.2.1
Difficulty: Easy

6.  The witness software product is a ____.
A)  lock-order verifier that uses mutual-exclusion locks to protect critical sections 
B)  modeler to develop resource allocation graphs 
C)  driver that can be used to prevent mutual exclusion for nonsharable resources
D)  implementation of the banker's algorithm available for most operating systems

Ans:  A
Feedback: 7.4.4
Difficulty: Medium

7.  In a system resource-allocation graph, ____.
A)  a directed edge from a process to a resource is called an assignment edge
B)  a directed edge from a resource to a process is called a request edge
C)  a directed edge from a process to a resource is called a request edge
D)  None of the above

Ans:  C
Feedback: 7.2.2
Difficulty: Medium

8.  A cycle in a resource-allocation graph is ____.
A)  a necessary and sufficient condition for deadlock in the case that each resource has more than one instance
B)  a necessary and sufficient condition for a deadlock in the case that each resource has exactly one instance
C)  a sufficient condition for a deadlock in the case that each resource has more than once instance
D)  is neither necessary nor sufficient for indicating deadlock in the case that each resource has exactly one instance

Ans:  B
Feedback: 7.2.2
Difficulty: Difficult

9.  To handle deadlocks, operating systems most often _____.
A)  pretend that deadlocks never occur
B)  use protocols to prevent or avoid deadlocks
C)  detect and recover from deadlocks
D)  None of the above

Ans:  A
Feedback: 7.3
Difficulty: Medium

10.  Which of the following statements is true?
A)  A safe state is a deadlocked state.
B)  A safe state may lead to a deadlocked state.
C)  An unsafe state is necessarily, and by definition, always a deadlocked state.
D)  An unsafe state may lead to a deadlocked state.

Ans:  D
Feedback: 7.5.1
Difficulty: Medium

11.  Suppose that there are ten resources available to three processes. At time 0, the following data is collected. The table indicates the process, the maximum number of resources needed by the process, and the number of resources currently owned by each process. Which of the following correctly characterizes this state?

Process	Maximum Needs	Currently Owned
	P0	10	4
	P1	3	1
	P2	6	4
A)  It is safe.
B)  It is not safe.
C)  The state cannot be determined.
D)  It is an impossible state.

Ans:  B
Feedback: 7.5.1
Difficulty: Difficult

12.  Suppose that there are 12 resources available to three processes. At time 0, the following data is collected. The table indicates the process, the maximum number of resources needed by the process, and the number of resources currently owned by each process. Which of the following correctly characterizes this state?

Process	Maximum Needs	Currently Owned
	P0	10	4
	P1	3	2
	P2	7	4
A)  It is safe.
B)  It is not safe.
C)  The state cannot be determined.
D)  It is an impossible state.

Ans:  A
Feedback: 7.5.1
Difficulty: Difficult

13.  Which of the following data structures in the banker's algorithm is a vector of length m, where m is the number of resource types?
A)  Need
B)  Allocation
C)  Max
D)  Available

Ans:  D
Feedback: 7.5.3
Difficulty: Easy

14.  Assume there are three resources, R1, R2, and R3, that are each assigned unique integer values 15, 10, and 25, respectively. What is a resource ordering which prevents a circular wait?
A)  R1, R2, R3
B)  R3, R2, R1
C)  R3, R1, R2
D)  R2, R1, R3

Ans:  D
Feedback: 7.4.4
Difficulty: Medium

15. A _____ could be preempted from a process.
A) mutex lock
B) CPU
C) semaphore
D) file lock

Ans: B
Feedback: 7.4.3
Difficulty: Medium

Essay

16.  Explain what has to happen for a set of processes to achieve a deadlocked state.

Ans:  For a set of processes to exist in a deadlocked state, every process in the set must be waiting for an event that can be caused only be another process in the set. Thus, the processes cannot ever exit this state without manual intervention. 
Feedback: 7.1
Difficulty: Medium

17.  Describe the four conditions that must hold simultaneously in a system if a deadlock is to occur.

Ans:  For a set of processes to be deadlocked: at least one resource must remain in a nonsharable mode, a process must hold at least one resource and be waiting to acquire additional resources held by other processes, resources in the system cannot be preempted, and a circular wait has to exist between processes.
Feedback: 7.2.1
Difficulty: Medium

18.  What are the three general ways that a deadlock can be handled?

Ans:  A deadlock can be prevented by using protocols to ensure that a deadlock will never occur. A system may allow a deadlock to occur, detect it, and recover from it. Lastly, an operating system may just ignore the problem and pretend that deadlocks can never occur.
Feedback: 7.3
Difficulty: Medium

19.  What is the difference between deadlock prevention and deadlock avoidance?

Ans:  Deadlock prevention is a set of methods for ensuring that at least one of the necessary conditions for deadlock cannot hold. Deadlock avoidance requires that the operating system be given, in advance, additional information concerning which resources a process will request and use during its lifetime.
Feedback: 7.4
Difficulty: Medium

20.  Describe two protocols to ensure that the hold-and-wait condition never occurs in a system.

Ans:  One protocol requires each process to request and be allocated all its resources before it begins execution. We can implement this provision by requiring that system calls requesting resources for a process precede all other system calls. An alternative protocol allows a process to request resources only when it has none. A process may request some resources and use them. Before it can request any additional resources, however, it must release all the resources that it is currently allocated.  
Feedback: 7.4.2
Difficulty: Medium

21.  What is one way to ensure that a circular-wait condition does not occur?

Ans:  One way to ensure that this condition never holds is to impose a total ordering of all resource types, and to require that each process requests resources in an increasing order of enumeration. This can be accomplished by assigning each resource type a unique integer number to determine whether one precedes another in the ordering.
Feedback: 7.4.4
Difficulty: Medium

22.  What does a claim edge signify in a resource-allocation graph?

Ans:  A claim edge indicates that a process may request a resource at some time in the future. This edge resembles a request edge in direction, but is represented in the graph by a dashed line.
Feedback: 7.5.2
Difficulty: Medium

23.  Describe a wait-for graph and how it detects deadlock.

Ans:  If all resources have only a single instance, then we can define a deadlock-detection algorithm that uses a variant of the resource-allocation graph, called a wait-for graph. We obtain this graph from the resource-allocation graph by removing the resource nodes and collapsing the appropriate edges. To detect deadlocks, the system needs to maintain the wait-for graph and periodically invoke an algorithm that searches for a cycle in the graph.
Feedback: 7.6.1
Difficulty: Medium

24.  What factors influence the decision of when to invoke a detection algorithm? 

Ans:  The first factor is how often a deadlock is likely to occur; if deadlocks occur frequently, the detection algorithm should be invoked frequently. The second factor is how many processes will be affected by deadlock when it happens; if the deadlock-detection algorithm is invoked for every resource request, a considerable overhead in computation time will be incurred.
Feedback: 7.6.3
Difficulty: Medium

25.  Describe two methods for eliminating processes by aborting a process.

Ans:  The first method is to abort all deadlocked processes. Aborting all deadlocked processes will clearly break the deadlock cycle; however, the deadlocked processes may have to be computed for a long time, and results of these partial computations must be discarded and will probably have to be recomputed later. The second method is to abort one process at a time until the deadlock cycle is eliminated. Aborting one process at a time incurs considerable overhead, since, after each process is aborted, a deadlock-detection algorithm must be invoked to determine whether any processes are still deadlocked.
Feedback: 7.7.1
Difficulty: Medium

26.  Name three issues that need to be addressed if a preemption is required to deal with deadlocks.

Ans:  First, the order of resources and processes that need to be preempted must be determined to minimize cost. Second, if a resource is preempted from a process, the process must be rolled back to some safe state and restarted from that state. The simplest solution is a total rollback. Finally, we must ensure that starvation does not occur from always preempting resources from the same process.
Feedback: 7.7.2
Difficulty: Medium

27. Describe how a safe state ensures deadlock will be avoided. 

Ans: A safe state ensures that there is a sequence of processes to finish their program execution. Deadlock is not possible while the system is in a safe state. However, if a system goes from a safe state to an unsafe state, deadlock is possible. One technique for avoiding deadlock is to ensure that the system always stays in a safe state. This can be done by only assigning a resource as long as it maintains the system in a safe state.
Feedback: 7.5.1
Difficulty: Medium

True/False

28.  The circular-wait condition for a deadlock implies the hold-and-wait condition. 

Ans:  True
Feedback: 7.2
Difficulty: Medium

29.  If a resource-allocation graph has a cycle, the system must be in a deadlocked state.

Ans:  False
Feedback: 7.2.2
Difficulty: Medium

30.  Protocols to prevent hold-and-wait conditions typically also prevent starvation.

Ans:  False
Feedback: 7.4.2
Difficulty: Medium

31.  The wait-for graph scheme is not applicable to a resource allocation system with multiple instances of each resource type.

Ans:  True
Feedback: 7.6.1
Difficulty: Medium

32. Ordering resources and requiring the resources to be acquired in order prevents the circular wait from occurring and therefore prevents deadlock from occurring.

Ans: False
Feedback: 7.4.4
Difficulty: Medium

33. The banker's algorithm is useful in a system with multiple instances of each resource type.

Ans: True
Feedback: 7.5.3
Difficulty: Easy

34. A system in an unsafe state will ultimately deadlock.

Ans: False
Feedback: 7.5.1
Difficulty: Medium

35. Deadlock prevention and deadlock avoidance are essentially the same approaches for handling deadlock.

Ans: False
Feedback: 7.5
Difficulty: Medium