Skip to main content
Engineering LibreTexts

6.1: Concept and Principles of Deadlock

  • Page ID
    48015
  • Deadlock

    In concurrent computing, a deadlock is a state in which each member of a group waits for another member, including itself, to take action, such as sending a message or more commonly releasing a lock. Deadlocks are a common problem in multiprocessing systems, parallel computing, and distributed systems, where software and hardware locks are used to arbitrate shared resources and implement process synchronization.

    In an operating system, a deadlock occurs when a process or thread enters a waiting state because a requested system resource is held by another waiting process, which in turn is waiting for another resource held by another waiting process. If a process is unable to change its state indefinitely because the resources requested by it are being used by another waiting process, then the system is said to be in a deadlock.

    In a communications system, deadlocks occur mainly due to lost or corrupt signals rather than resource contention.

    Both processes need resources to continue execution. P1 requires additional resource R1 and is in possession of resource R2, P2 requires additional resource R2 and is in possession of R1; neither process can continue.
    Figure \(\PageIndex{1}\): Both processes need resources to continue execution. P1 requires additional resource R1 and is in possession of resource R2P2 requires additional resource R2 and is in possession of R1; neither process can continue. 
    ("Process deadlock" by Wikimedia Commons is licensed under CC BY-SA 4.0)

    The previous image show a simple instance of deadlock. Two resources are "stuck", because the other process has control of the resource that the process needs to continue to process. While this can occure quite easily, there is usually code in place to keep this from happening. As we discussed in the previous module there are various inter-process communication techniques that can actually keep processes from becoming deadlocked due to resource contention. So, often times when we hit a deadlock like this it is something to do with the IPC that is not handling this situation properly.

    Necessary conditions

    A deadlock situation on a resource can arise if and only if all of the following conditions hold simultaneously in a system:

    • Mutual exclusion: At least one resource must be held in a non-shareable mode. Otherwise, the processes would not be prevented from using the resource when necessary. Only one process can use the resource at any given instant of time.
    • Hold and wait or resource holding: a process is currently holding at least one resource and requesting additional resources which are being held by other processes.
    • No preemption: a resource can be released only voluntarily by the process holding it.
    • Circular wait: each process must be waiting for a resource which is being held by another process, which in turn is waiting for the first process to release the resource. In general, there is a set of waiting processes, P = {P1, P2, …, PN}, such that P1 is waiting for a resource held by P2, P2 is waiting for a resource held by P3 and so on until PN is waiting for a resource held by P1.

    These four conditions are known as the Coffman conditions from their first description in a 1971 article by Edward G. Coffman, Jr.

    While these conditions are sufficient to produce a deadlock on single-instance resource systems, they only indicate the possibility of deadlock on systems having multiple instances of resources.

    The following image shows 4 processes and a single resource. The image shows 2 processes contending for the single reource (the grey circl in the middle), the it shows 3 processes contending for that resource, then finally how it looks when 4 processes contend for the same resource. The image depicts the processes waiting to gain access to the resource - only one resource at a time can have access.

    Four processes (blue lines) compete for one resource (grey circle), following a right-before-left policy. A deadlock occurs when all processes lock the resource simultaneously (black lines). The deadlock can be resolved by breaking the symmetry.

    Figure \(\PageIndex{1}\): Four processes (blue lines) compete for one resource (grey circle), following a right-before-left policy. A deadlock occurs when all processes lock the resource simultaneously (black lines). The deadlock can be resolved by breaking the symmetry.
     ("Marble Machine" by Wikimedia Commons is licensed under CC BY-SA 4.0)

    Adapted from:
    "Deadlock" by Multiple ContributorsWikipedia is licensed under CC BY-SA 3.0

    • Was this article helpful?