Problem | Solution |
Fig. 6-3 shows the concept of a resource graph. Do illegal graphs exist, that is, graphs that structurally violate the model we have used of resource usage? If so, give an example of one. | Yes illegal graphs exist; any graph in which multiple arcs leave a square and end in different circles violates the rules |
Consider Figure 6-4. Suppose that in step (o) C requested S instead of requesting R. Would this lead to deadlock? Suppose that it requested both S and R. | Neither change leads to deadlock. There is no circular wait in either case. |
All the trajectories in Figure 6-8 are horizontal or vertical. Is is possible for a trajectory to be a diagonal. | If the system had two or more CPUs, two or more processes could run in parallel, leading to diagonal trajectories. |
Can the resource trajectory scheme of Fig. 6-8 also be used to illustrate the problem of deadlocks with three processes and three resources? If so, how can this be done? If not, why not? | Yes. Do the whole thing in three dimensions. The z-axis measures the number of instructions executed by the third process. |
In theory, resource trajectory graphs could be used to avoid deadlocks. By clever scheduling, the operating system could avoid unsafe regions. Is there a practical way of actually doing this? | The method can only be used to guide the scheduling if the exact instant at which a resource is going to be claimed is known in advance. In practice, this is rarely the case. |
Take a careful look at Fig. 6-11(b). If D asks for one more unit, does this lead to a safe state or an unsafe one? What if the request came from C instead of D? | Satisfying a request from D is unsafe, but satisfying one from C is safe. |
BANKER'S ALGORITHM PROBLEM | BANKER'S ALGORITHM PROBLEM |
A system has four processes and five allocatable resources. The current allocation and maximum needs are as follows: [Fig. P. 467 #26]. What is the smallest value of x for which this is a safe state? | If x is 2, only D complete. This time, after D runs/returns resources, available vector is 1 1 3 2 1 and C can run. After it finishes/returns resources the available vector is 2 2 3 3 1, allows B, A to run/complete. Therefore, the smallest value is 2. |
A mailbox system has 2 IPC primitives, send & receive. Latter specifies process to receive, blocks if no message available, even if messages may be waiting from processes. No shared resources, but processes need to communicate. Is deadlock possible? | Yes. Suppose all the mailboxes are empty. Now A sends to B and waits for a reply, B sends to C and waits for a reply, and C sends to A and waits for a reply. All the conditions for deadlock are now fulfilled. |
Couple divorcing. Each sends letter requesting item. If same item requested, request cancelled. Separation between pets and houses are invalid, requiring do-over. Both want item. CPUs still negotiating. Why? Is deadlock possible? Is starvation possible? | If both programs ask for Woofer first, the computers will livelock; if one of them asks for the doghouse and the other asks for the dog, we have a deadlock. Regardless, either livelock or deadlock occurs. |