📄 http:^^www.cs.wisc.edu^~cs537-1^deadlock.html
字号:
Date: Tue, 05 Nov 1996 00:27:39 GMTServer: NCSA/1.5Content-type: text/htmlLast-modified: Thu, 31 Oct 1996 21:38:53 GMTContent-length: 19822<html><head><title>CS 537 - Processes, Part II (Deadlock) </title></head><body bgcolor="#ffffff"><h1>CS 537<br>Lecture Notes<br>Processes and Synchronization, Part II<br>Deadlock</h1><hr><h2>Contents</h2><ul><li><!WA0><!WA0><!WA0><!WA0><a href="#terminology"> Terminology </a><li><!WA1><!WA1><!WA1><!WA1><a href="#detection"> Deadlock Detection </a><li><!WA2><!WA2><!WA2><!WA2><a href="#recovery"> Deadlock Recovery </a><li><!WA3><!WA3><!WA3><!WA3><a href="#prevention"> Deadlock Prevention </a><li><!WA4><!WA4><!WA4><!WA4><a href="#avoidance"> Deadlock Avoidance </a></ul><hr><a name="using"> <h2> Using Processes (Continued) </h2> </a><a name="using_deadlock"> <h3> Deadlock </h3> </a><a name="terminology"> <h4> Terminology </h4> </a>The Dining Philosophers problem isn't just a silly exercise.It is a scale-model example of a very important problem in operating systems:<b>resource allocation</b>.A ``resource'' can be defined as something that costs money.The philosophers represent processes, and the forks represent<b>resources</b>.<p>There are three kinds of resources:<ul><li><b>sharable</b><li><b>serially reusable</b><li><b>consumable</b></ul>Sharable resources can be used by more than one process at a time.A consumable resource can only be used by one process, and the resourcegets ``used up.''A serially reusable resource is in between.Only only process can use the resource at a time, but once it's done,it can give it back for use by another process.Examples are the CPU and memory.These are the most interesting type of resource.We won't say any more about the other kinds.<p>A process<b>requests</b> a (serially reusable) resource from the OS and<b>holds</b> it until it's done with it; then it<b>releases</b> the resource.The OS may delay responding to a request for a resource.The requesting process is <b>blocked</b> until the OS responds.Sometimes we say the process is ``blocked on the resource.''In actual systems, resources might be represented by semaphores,monitors, or condition variables in monitors--anything a process maywait for.<p>A resource might be<b>preemptable</b>,meaning that the resource can be ``borrowed'' from the process without harm.Sometimes a resource can be made preemptable by the OS, at some cost.For example, memory can be preempted from a process by suspending theprocess, and copying the contents of the memory to disk.Later, the data is copied back to the memory, and the process is allowedto continue.Essentially, this makes a serially reusable resource look sharable.<a name="detection"> <h4> Deadlock Detection </h4> </a><p>The formal definition of deadlock:<ol><em>A set of processes is <strong>deadlocked</strong> if each process in the set iswaiting for an event that only another process in the set can cause.</em></ol><p>We can show deadlock graphically by building the <em>waits-for</em>graph.Draw each process as a little circle, and draw an arrow from <em>P</em> to<em>Q</em> if <em>P</em> is waiting for <em>Q</em>.The picture is called a <em>graph</em>, the little circles are called<em>nodes</em>, and the arrows connecting them are called <em>arcs</em>.We can find out whether there is a deadlock as follows:<pre><font color="0f0fff"> for (;;) { find a node n with no arcs coming out of it; if (no such node can be found) break; erase n and all arcs coming into it; } if (any nodes are left) there is a deadlock;</font></pre>This algorithm simulates a best-case scenario:Every runnable process runs and causes all events that are expected from it,and no process waits for any new events.A node with no outgoing arcs represents a process that isn't waiting foranything, so is runnable.It causes all events other processes are waiting for (if any), therebyerasing all incoming arcs. Then, since it will never wait for anything,it cannot be part of a deadlock, and we can erase it.<p>Any processes that are left at the end of the algorithm are deadlocked, andwill wait forever.The graph that's left must contain a<em>cycle</em> (a path starting and ending at the same node and followingthe arcs).It may also contain processes that are not part of the cycle but are waitingfor processes in the cycle, or for processes waiting for them, etc.The algorithm will never erase any of the nodes in a cycle, since each onewill always have an outgoing arc pointing to the next node in the cycle.<p>The simplest cycle is an arc from a node to itself.This represents a process that is waiting for itself, and usually representsa simple programming bug:<pre><font color="0f0fff"> Semaphore s = 0; ... s.down(); s.up();</font></pre>If no other process can do <samp><font color="0f0fff">s.up()</font></samp>, this process is deadlockedwith itself.<p>Usually, processes block waiting for (serially reusable) resources.The ``events'' they are waiting for are release of resources.In this case, we can put some more detail into the graph.Add little boxes representing resources.Draw an arc from a process to a resource if the process is waiting forthe resource, and an arc from the resource to the process if the processholds the resource.The same algorithm as before will tell whether there is a deadlock.(Ignore the algorithm on page 248 of Tanenbaum. Not only is ithard to understand, it is much less efficient than the one presented here.)As before, deadlock is associated with cycles:If there is no cycle in the original graph, there is no deadlock, andthe algorithm will erase everything.If there is a cycle, the algorithm will never erase any part of it,and the final graph will contain only cycles and nodes that havepaths from them to cycles.<h5> Resource Types </h5><p>Often, a request from a process is not for a particular resource, butfor any resource of a given type.For example, a process may need a block of memory.It doesn't care which block of memory it gets.To model this, we will assume there there some number <em>m</em>of <em>resource types</em>, and some number <em>E[r]</em> of <em>units</em>of resource <em>r</em>, for each <em>r</em> between 1 and <em>m</em>.To be very general, we will allow a process to request multiple resourcesat once:Each request will tell now many units of each resource the process needsto continue.The graph gets pretty hard to draw, but essentially the same algorithmcan be used to determine whether there is a deadlock.We will need a few arrays for bookkeeping.<pre><font color="0f0fff"> E[r] = total number of units of resource r in the system C[p][r] = number of units of r currently allocated to process p A[r] = number of units of r that have not been allocated to any process R[p][r] = number of units of r requested by p but not yet allocated</font></pre>As before, the algorithm works by simulating a best-case scenario.We add an array of <samp><font color="0f0fff">boolean done[n]</font></samp> with one element for eachprocess, and initially set all elements to <samp><font color="0f0fff">false</font></samp>.<a name="deadlock_alg"><pre><font color="0f0fff"> for (;;) { find p such that !done[p] && for all r, R[p][r] <= A[r]; if (no such p can be found) break; for each r A[r] += C[p][r]; done[p] = true; } if (there is any p such that !done[p]) there is a deadlock;</font></pre></a>The algorithm looks for a process whose request can be satisfied immediately.If it finds one, it assumes that the process could be given all the resourcesit wants, would do what ever it wanted with them, and would eventually give them back, as well as all the resources it previously got.It can be proved that it doesn't matter what order we consider theprocesses;either we succeed in completing them, one at a time, or there is a deadlock.<a name="recovery"> <h4> Deadlock Recovery </h4> </a><p>Once you've discovered that there is a deadlock, what do you do about it?One thing to do is simply re-boot.A less drastic approach is to yank back a resource from a process to breaka cycle.As we saw, if there are no cycles, there is no deadlock.If the resource is not preemptable, snatching it back from a process maydo irreparable harm to the process.It may be necessary to kill the process, under the principle thatat least that's better than crashing the whole system.<p>Sometimes, we can do better.For example, if we <em>checkpoint</em> a process from time to time,we can roll it back to the latest checkpoint, hopefully to a time beforeit grabbed the resource in question.Database systems use checkpoints, as well as aa technique called <em>logging</em>, allowingthem to run processes ``backwards,'' undoing everything they have done.It works like this:Each time the process performs an action, it writes a <em>log record</em>containing enough information to undo the action.For example, if the action is to assign a value to a variable, thelog record contains the previous value of the record.When a database discovers a deadlock, it picks a victim and rolls it back.<p>Rolling back processes involved in deadlocks can lead to a form of⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -