Busy. Please wait.
or

show password
Forgot Password?

Don't have an account?  Sign up 
or

Username is available taken
show password

why


Make sure to remember your password. If you forget it there is no way for StudyStack to send you a reset link. You would need to create a new account.
We do not share your email address with others. It is only used to allow you to reset your password. For details read our Privacy Policy and Terms of Service.


Already a StudyStack user? Log In

Reset Password
Enter the associated with your account, and we'll email you a link to reset your password.

Remove ads
Don't know
Know
remaining cards
Save
0:01
To flip the current card, click it or press the Spacebar key.  To move the current card to one of the three colored boxes, click on the box.  You may also press the UP ARROW key to move the card to the "Know" box, the DOWN ARROW key to move the card to the "Don't know" box, or the RIGHT ARROW key to move the card to the Remaining box.  You may also click on the card displayed in any of the three boxes to bring that card back to the center.

Pass complete!

"Know" box contains:
Time elapsed:
Retries:
restart all cards




share
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

6. Deadlocks

Operating Systems: Deadlocks (Ch. 6)

ProblemSolution
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