Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.

Normal Size Small Size show me how

Normal Size Small Size show me how

# 6. Deadlocks

### Operating Systems: Deadlocks (Ch. 6)

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. |

Created by:
JJFresh814