3.3 Operating Systems

Deadlock

as a situation in which every process in a set of processes is waiting for an event that can be caused only by another process in the set.

Mutual exclusion:

Hold and wait:

No preemption

Four conditions that can make the deadlock arise

Mutual exclusion

only one process at a time can use a resource

Hold and wait

a process holding at least one resource is waiting to acquire additional resources held by other processes

No preemption

resource can be released only voluntarily by the process holding it after that process has completed its task

Circular wait

here exists a set {P0, P1, …, Pn} of waiting for processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2, …, Pn–1 is waiting for a resource that is held by Pn, and Pn is waiting for a resource that is held by P0.

Mutual Exclusion

Hold and Wait

No Preemption

Circular Wait

Deadlocks can be prevented by four conditions

Mutual Exclusion

not required for sharable resources (e.g., read-only files); must hold for non-sharable resources

Hold and Wait

must guarantee that whenever a process requests a resource, it does not hold any other resources

No Preemption

a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released

Circular Wait

• Impose a total ordering of all resource types, and require that each process requests resources in increasing order of enumeration