![]() ![]() Adopt a policy of not letting a process wait for one resource while holding another, either by requiring each process to hold only one resource at a time, or to request all of the resources it needs simultaneously. ![]() Sometimes resources can be partitioned to avoid mutual exclusion (memory partitioning, window systems). This doesn't work for resources that can't reasonably be shared by two processes at the same time (most writable data structures, the CPU, CD-ROM burners, the keyboard). This is the best solution when it can be arranged, particularly when resources (read-only files, lock-free data structures) can be shared. If there's no need for mutual exclusion, there's no deadlock. To prevent deadlock, we just have to violate one of the Coffman conditions. When these extra instances become available, P 1 stops waiting and the cycle clears up. For example, if P 1 holds R 1 and waits for R 2 while P 2 holds R 2 and waits for R 1, then we have a cycle in the resource-allocation graph, but there is no deadlock if R 2 has multiple instances some of which are held by other processes not involved in the cycle. The converse is generally not true (although it holds if there is only one instance of each resource). It follows that deadlock can occur only if there is a cycle in the resource-allocation graph. Circular waiting strings these length-2 paths together into a cycle. The situation where P 1 waits for a resource R held by P 2 corresponds to a path of length 2 in the resource-allocation graph. (See SGG §7.2 for many pictures of resource-allocation graphs.) A directed edge is drawn from process P to resource R if P is waiting for R, and from R to P if P holds R. Each node in the graph represents either a process or a resource. (Note that this implies hold-and-wait.)Ī resource-allocation graph depicts which processes are waiting for or holding each resource. , P n such that each process P i is waiting for a resource held by the next process in the cycle. There must be some cycle of waiting processes P 1, P 2. Only the process holding a resource can release it.Ĭircular wait. Some process must be holding one resource while waiting for another. There must be some resource that can't be shared between processes. Shoshani, System Deadlocks, ACM Computing Surveys, 3(2):67–78, 1971 coffman_deadlocks.pdf). These are known as Coffman's conditions from a 1971 survey paper of which Coffman was the first author in alphabetical order (Coffman, E.G., M.J. There are four conditions which must hold for deadlock to occur as classically defined. It is typically assumed that each resource may have multiple instances, where a process is indifferent to which instance it gets and nobody blocks unless the processes collectively request more instances than the resource can provide. Processes may or may not correspond to full-blown processes as used elsewhere. Nobody makes any progress from this point on-we have a deadlock.ĭeadlocks are described in terms of processes (things that can block) and resources (things processes can wait for). This causes P to fill up its output buffer and block. If P's input to Q is large enough and Q produces output comparable in size to its input, then Q fills up its outgoing buffer and blocks before P is done writing. We'll imagine each process puts its outgoing data in a buffer guarded by a semaphore, and blocks when the buffer fills up. Let's imagine a simple circular pipeline where process P (say some user program) sends data to process Q (say tr) and then reads the result. ![]() Python's os.popen2 function) bury them in obscure libraries. Even scripting languages that provide such tools (e.g. Curiously, there is no built-in mechanism in most shells to create a circular pipeline, where two programs A and B each produce as output the input to the other, even though it may be reasonable in some circumstances for one program to use another as a subroutine, providing its input and consuming its output. In a pipeline, each program feeds its output to the next program. sort | uniq | wc to count unique lines in a file. If process P grabs the keyboard while process Q grabs the display, both may be stuck waiting for the other resource.Ī common design pattern in Unix-derived operating systems is the pipeline, e.g. Two interactive processes on a primitive handheld device with no window system each want to control the keyboard (so the user can type at them) and the display (so they can respond). Neither process can make progress until the other gives up some of its memory. The operating system kindly gives each 1 Gb exactly. Two processes each demand 1.5 Gb of memory on a machine with only 2 Gb (and no virtual memory). For more details see SilberschatzGalvinGagne Chapter 7.ĭeadlock is when two or more tasks never make progress because each is waiting for some resource held by another process. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |