DEADLOCK
1) Define a deadlock.
A process requests resources; if the resources are not available at that
time, the process enters a waiting state. Sometimes, a waiting process
will not able to change state, because the resources it has requested
are held by other waiting processes. This situation is called a
deadlock.
A process may utilize a resource in only the following sequence:
1. Request. The process requests the resource. If the request cannot be
granted immediately (for example, if the resource is being used by
another process), then the requesting process must wait until it can
acquire the resource.
2. Use. The process can operate on the resource (for example, if the
resource is a printer, the process can print on the printer).
3. Release. The process releases the resource.
----------------------------------------------------------------------------------------------------------------------
DEADLOCK CHARACTERIZATION :
How is deadlock characterised?
Deadlocks are characterised by:
1. Necessary condition
2. Resource allocation graph
------------------------------------------------------------------------------------------------
2) Explain necessary conditions for deadlock.
Necessary Condition :
A. Mutual exclusion. At least one resource must be held in a non-sharable
mode; that is, only one process at a time can use the resource. If another
, process requests that resource, the requesting process must be delayed
until the resource has been released.
B. Hold and wait. A process must be holding at least one resource and
waiting to acquire additional resources that are currently being held by
other processes.
C. No preemption. Resources cannot be preempted; that is, a resource can
be released only voluntarily by the process holding it, after that process
has completed its task.
D. Circular wait. A set {P0, P1, ..., Pn} of waiting processes must exist
such that P0 is waiting for a resource held by P1, P1 is waiting for a
resource held by P2, ..., Pn−1 is waiting for a resource held by Pn, and
Pn is waitingfor a resource held by P0.
-------------------------------------------------------------------------------------------------------------------------
3) Explain resource allocation graph with and without deadlock
Deadlocks can be described more precisely in terms of a directed graph called
a system resource-allocation graph.
This graph consists of a set of
A set of vertices V
A set of edges E
The set of vertices V is partitioned into two different types of nodes :
1) A set of processes, P = {P1, P2, ..., Pn}
2) A set of Resources, R = {R1, R2, ..., Rm}
A directed edge Pi → Rj is called a request edge.
A directed edge Rj → Pi is called an assignment edge.
Pictorially, we represent each process Pi as a circle and each resource type Rj as
a rectangle.
Since resource type Rj may have more than one instance, we
represent each such instance as a dot within the rectangle.
1) Define a deadlock.
A process requests resources; if the resources are not available at that
time, the process enters a waiting state. Sometimes, a waiting process
will not able to change state, because the resources it has requested
are held by other waiting processes. This situation is called a
deadlock.
A process may utilize a resource in only the following sequence:
1. Request. The process requests the resource. If the request cannot be
granted immediately (for example, if the resource is being used by
another process), then the requesting process must wait until it can
acquire the resource.
2. Use. The process can operate on the resource (for example, if the
resource is a printer, the process can print on the printer).
3. Release. The process releases the resource.
----------------------------------------------------------------------------------------------------------------------
DEADLOCK CHARACTERIZATION :
How is deadlock characterised?
Deadlocks are characterised by:
1. Necessary condition
2. Resource allocation graph
------------------------------------------------------------------------------------------------
2) Explain necessary conditions for deadlock.
Necessary Condition :
A. Mutual exclusion. At least one resource must be held in a non-sharable
mode; that is, only one process at a time can use the resource. If another
, process requests that resource, the requesting process must be delayed
until the resource has been released.
B. Hold and wait. A process must be holding at least one resource and
waiting to acquire additional resources that are currently being held by
other processes.
C. No preemption. Resources cannot be preempted; that is, a resource can
be released only voluntarily by the process holding it, after that process
has completed its task.
D. Circular wait. A set {P0, P1, ..., Pn} of waiting processes must exist
such that P0 is waiting for a resource held by P1, P1 is waiting for a
resource held by P2, ..., Pn−1 is waiting for a resource held by Pn, and
Pn is waitingfor a resource held by P0.
-------------------------------------------------------------------------------------------------------------------------
3) Explain resource allocation graph with and without deadlock
Deadlocks can be described more precisely in terms of a directed graph called
a system resource-allocation graph.
This graph consists of a set of
A set of vertices V
A set of edges E
The set of vertices V is partitioned into two different types of nodes :
1) A set of processes, P = {P1, P2, ..., Pn}
2) A set of Resources, R = {R1, R2, ..., Rm}
A directed edge Pi → Rj is called a request edge.
A directed edge Rj → Pi is called an assignment edge.
Pictorially, we represent each process Pi as a circle and each resource type Rj as
a rectangle.
Since resource type Rj may have more than one instance, we
represent each such instance as a dot within the rectangle.
