Deadlock - Necessary and Sufficient Condition

Necessary and Sufficient Condition

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

  1. Mutual Exclusion: At least one resource must be non-shareable. Only one process can use the resource at any given instant of time.
  2. 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.
  3. No Preemption: The operating system must not de-allocate resources once they have been allocated; they must be released by the holding process voluntarily.
  4. Circular Wait: A 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 till 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. Unfulfillment of any of these conditions is enough to preclude a deadlock from occurring.

Read more about this topic:  Deadlock

Famous quotes containing the words sufficient and/or condition:

    “... most Southerners of my parents’ era were raised to feel that it wasn’t respectable to be rich. We felt that all patriotic Southerners had lost everything in defense of the South, and sufficient time hadn’t elapsed for respectable rebuilding of financial security in a war- impoverished region.”
    —Sarah Patton Boyle, U.S. civil rights activist and author. The Desegregated Heart, part 1, ch. 1 (1962)

    “...Negroes must concern themselves with every single means of struggle: legal, illegal, passive, active, violent and non- violent.... They must harass, debate, petition, boycott, sing hymns, pray on steps—and shoot from their windows when the racists come cruising through their communities.... The acceptance of our condition is the only form of extremism which discredits us before our children [ellipses in source].”
    —Lorraine Hansberry (1930–1965)