Deadlock Summ

DEADLOCK
Principles of Deadlock (Stallings, 2018)
Amiel
Deadlocks - permanent blocking of a set of processes that either compete for
system resources or communicate with each other.
- A set of processes is deadlocked when each process in the set is
blocked waiting for an event, typically freeing up some requested resource that
can only be triggered by another blocked process in the set.
- Note that all deadlocks involve conflicting needs for resources by two
(2) or more processes.
General Resource Categories:
1. Reusable resources – These resources can be used by only one process at a time
and are not depleted by usage.
Example: Consider two (2) programs that compete for exclusive access to
a disk file D and a tape drive T. Deadlock occurs if each process holds one (1)
resource and requests the other.
2. Consumable resources – These are resources that can be created (produced)

and destroyed (consumed).
- An unblocked producing process may create any number of
resources. Then, when a resource is acquired by a consuming process, the
Christopher
resource ceases to exist.
Example: Consider a pair of processes in which each process attempts to
receive a message from the other process, then sends a message to the other.
Deadlock occurs if the receiving process is blocked until the message is received.
Resource allocation graph
- Introduced by Richard Holt
- A useful tool in characterizing the allocation of resources to processes.
- It is a directed graph that depicts the state of system resource processes,
wherein processes and resources are represented by nodes
connected by edges.
A resource allocation graph can be described as follows:

⚫ An edge directed from a process to a resource indicates a resource that has
been requested by the process but not yet granted.
⚫ A dot within the resource node represents an instance of a resource.
⚫ An edge directed from a reusable resource node dot to a process indicates a
request that has been granted, and one (1) unit of the resource has been
Nathaniel
assigned to the process.
⚫ An edge directed from a consumable resource node dot to a process
indicates the process is the procedure of that resource.
Deadlock Prevention, Avoidance, and Detection
The following conditions must be present for a deadlock to occur (Silberschatz,

Kenneth
Galvin & Gagne, 2018):
1. Mutual exclusion:
- At least one resource must be held in a non-shareable mode. This means
that only one (1) thread at a time can use the resource.
- If another thread requests that specific resource, the requesting thread must
be delayed until the resource has been released.
2. Hold and wait:
- A thread must be holding at least one (1) resource and waiting to acquire
additional resources that are currently being held by other threads.
3. No preemption:
- Resources cannot be preempted. This means that a resource can only be
released voluntarily by the thread holding it after that thread has completed its
task.
Kenneth
4. Circular wait:
- A closed chain of threads exists, such that each thread holds at least one
resource needed by the next thread in the chain.
Note:
- The first three (3) conditions are necessary, but not sufficient, for a
deadlock to occur.
- The fourth condition is required for a deadlock to actually take place.
Technically, the fourth condition is the potential consequence of the first three
conditions.
- Deadlock can also be described as an unresolved circular wait.
Deadlock Prevention: Disallows one of the four conditions for deadlock

occurrence:
- This strategy of involves the designing of a system in such a way that the
possibility of deadlock is excluded (Stallings, 2018).
A. Indirect method of deadlock prevention (preventing the first three conditions)

a) Mutual exclusion: In general, this condition cannot be disallowed. If access
to a resource requires mutual execution, then mutual exclusion must be
supported by the operating system.
b) Hold and wait: This condition can be prevented by requiring a process to Mark Ian
request all of its required resources at once and blocking the process until
all resources can be granted simultaneously.
c) No preemption: This condition can be prevented through the following
ways:
i. If a process is denied of further request, that process must release the
resources that it is currently holding;
ii. If necessary, request the process again with the additional resources;
and
iii. Let go of other resources in order to proceed with other process
execution.
B. Direct method of deadlock prevention (preventing the occurrence of the fourth
condition)
a) Circular wait: This condition can be prevented by defining a linear ordering
of resource types.
Deadlock Avoidance: Do not grant a resource request if the allocation might lead
to a deadlock condition:
- This strategy allows the three necessary conditions but makes judicious
Christopher
choices to assure that the deadlock point is never reached. Thus, allowing more
concurrency.
- With deadlock avoidance, decisions are made dynamically. Hence,
knowledge of future process resource requests must be known.
Two (2) approaches of deadlock avoidance are as follows (Stallings, 2018):
A. Process initiation denial: Do not start a process if its demands might lead to a
deadlock; and
B. Resource allocation denial: Do not grant an incremental resource request to a
process if this allocation might lead to a deadlock.
Below are some restrictions in implementing the deadlock avoidance strategy:
Nathaniel
⚫ The maximum resource requirement for each process must be stated in
advance;
⚫ The processes under consideration must be unconstrained by any
synchronization requirements;
⚫ There must be a fixed number of resources to allocate; and
⚫ No process may exit while holding resources.
Deadlock Detection: Grant resource requests, when possible, but periodically

check for deadlock and act to recover:
– This strategy does not limit resource access or restricts process executions.
Amiel
1. Requested resources are granted to processes whenever possible.
2. Then, the operating system periodically executes an algorithm that detects the
presence of a circular wait condition.
3. Once the deadlock has been detected, any of the following recovery methods
can be performed, whichever is more appropriate for the program (Stallings, 2018):
Recovery Methods:
A. Aborting all deadlock processes is the most common solution in operating

systems.
B. Back up each deadlocked process to some previously defined checkpoint, and
restart all processes. This requires that the rollback and restart mechanisms are
built into the system. However, the original deadlock may recur.
Kian Geoff
C. Successively abort deadlocked processes until deadlock no longer exists. After
each abortion, the detection algorithm must be re-invoked to see whether a
deadlock still exists.
D. Successively preempt resources until deadlock no longer exists. A process that
encompasses preempted resource must be rolled back to the point prior to its
resource acquisition.
The selection criteria in successively aborting deadlocked processes or preempt

resources could be one of the following:
•Process with the least amount of processor time consumed so far

• Process with least amount of output produced so far
• Process with the most estimated remaining time
• Process with the least total of resources allocated so far
• Process with the lowest priority

Deadlock Summ

Uploaded by

Copyright:

Available Formats

Deadlock Summ

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Deadlock Summ

Uploaded by

Copyright:

Available Formats

DEADLOCK

Principles of Deadlock (Stallings, 2018)

General Resource Categories:

2. Consumable resources – These are resources that can be created (produced)

A resource allocation graph can be described as follows:

Deadlock Prevention, Avoidance, and Detection

The following conditions must be present for a deadlock to occur (Silberschatz,

Galvin & Gagne, 2018):

Deadlock Prevention: Disallows one of the four conditions for deadlock

A. Indirect method of deadlock prevention (preventing the first three conditions)

Two (2) approaches of deadlock avoidance are as follows (Stallings, 2018):

Below are some restrictions in implementing the deadlock avoidance strategy:

Deadlock Detection: Grant resource requests, when possible, but periodically

presence of a circular wait condition.

A. Aborting all deadlock processes is the most common solution in operating

The selection criteria in successively aborting deadlocked processes or preempt

•Process with the least amount of processor time consumed so far

You might also like