cs241: deadlocks

What is a deadlock?

A set of processes is in a deadlock when each process is waiting for an event that can only be caused by another process in the set.

What kind of events cause deadlock?

Acquisition or release of resources like mutex locks, semaphores, CPU, file, or I/O devices.

in normal mode of operation, aprocess may utilise a resource in only the following sequence

1. the process requests the resource. if the requrst cannot be granted immeditately then the requesting process must wait until it can acquire the resource.

2. the process can use the resource and release the resource

What are the four necessary conditions for deadlock?

Mutual exclusion, Hold and wait, No preemption, Circular wait. must occur simulataneously

What does mutual exclusion mean in the context of deadlocks?

Only one process can use a resource instance at a time.

What is the 'hold and wait' condition?

A process is holding some resources while waiting for additional ones.

What is 'no preemption' in deadlocks?

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

What is circular wait?

A set of waiting processes {P0, …, Pn} must exist such that P0 is waiting for a resiurce held by p1, p1 is waiting for p2, …, pn is waiting for p0.

What is a Resource Allocation Graph?

A directed graph showing processes and resources with request and assignment edges. (represent the allocation and request of resources by processes). It is a directed graph G = (V, E) where:

• V (vertices) = P ∪ R

  • P = set of active processes

  • R = set of resource types

• E (edges) = represent relationships between processes and resources

What does a cycle in a resource allocation graph indicate?

Potential deadlock, but not necessarily a deadlock unless multiple instances are involved of the resources.( if each resource has one instance a cycle this is deadlock)

What does it mean if the resource allocation graph has no cycles?

There is no deadlock.

What is the purpose of a deadlock detection algorithm?

To identify if deadlocks exist in the current state.

How can deadlocks be handled?

Through prevention:provides a set of methods to ensure that at least one of the necessary conditions cannot hold

, avoidance: requires the OS to be given additional information in advance concerning which resources a process will request and use during its lifetime

the OS can decide for each request whether or not the process should wait

, or detection and recovery needed or else the system stays deadlocked.

Why ignore the possibility of deadlocks ?

it is cheaper since they occur infrequently

cons of deadlock prevention

• restrictive system

• harmless requests can be denied

cons of deadlock avoidance

• Low device utilization

• Reduced system throughput

how can mutual exclusion be prevented?

Cannot be prevented for non-sharable resources

How is deadlock prevented by avoiding 'hold and wait'?

must guarantee that whenever a process requests a resource, it does not hold any other resource. Ensure processes request all their required resources at once or release held ones before requesting new ones.

How can 'no preemption' be enforced to prevent deadlock?

Resources are forcibly released if a process cannot get all it needs. if a process, holding some resources, requests additional resources that cannot be immediately allocated to it, then all resources currently being held by the process are released

How can circular wait be avoided?

Assign a numerical order to resources and ensure each process requests them in increasing order. Process holding resource n cannot request a resource with a number less than n

What does deadlock avoidance aim to do?

Prevents deadlocks by limiting how requests can be made so that at least one necessary condition for deadlock cannot occur.

What is required in the simplest deadlock avoidance models?

Each process must declare the maximum number of resources of each type it may need.

How do deadlock avoidance algorithms work?

They dynamically examine the resource-allocation state to ensure circular-wait conditions can never exist.

What is the resource-allocation state?

It is defined by the number of available and allocated resources and the maximum demands of the processes.

What is a safe state?

A state where the system can allocate resources in a way that avoids deadlocks. A system can only be in safe state if there’s a safe sequence

what is safe sequence?

A sequence of processes <P₁, ..., Pₙ> is a safe sequence for the current allocation state if for each Pᵢ, the resource requests that Pᵢ can still make can be satisfied by the currently available resources plus the resources held by all Pⱼ with j < i.
Pᵢ waits for P₁ to Pⱼ to finish and gets their resources.

When is a system unsafe?

If no safe sequence exists , then the system is unsafe.A safe state is not a deadlocked state.A deadlocked state is an unsafe state. Not all unsafe states are deadlocks. An unsafe state may lead to deadlocks

What algorithm is used to check if a state is safe?

Banker’s algorithm.

What information does the Banker’s algorithm require?

Maximum number of each resource type for each resource type.

What does the Resource Request Algorithm do?

Pretends to grant a request and uses Banker’s algorithm to check if the system remains in a safe state.

When can a resource request be granted immediately?

If after granting, the system remains in a safe state.

What is the result of the Banker’s safety algorithm if a safe sequence exists?

The system is in a safe state.

What is the final conclusion if all processes can finish in Banker’s algorithm?

The starting state is safe.

What must a process do when it enters the system (Banker's Algorithm)?

It must declare the maximum number of instances of each resource type it may need.

What happens when a process requests resources (Banker's Algorithm)?

The system checks whether granting the request keeps the system in a safe state.

When are resources allocated in the Banker's Algorithm?

If the system remains in a safe state after the allocation.

What happens if granting a request would lead to an unsafe state?

The process must wait until another process releases enough resources.

What is Available[m]?

An array showing the number of available instances of each resource type.

What does Available[j] = k mean?

There are k instances of resource Rj available.

What is Max[n][m]?

Matrix showing the maximum demand of each process for each resource type.

What does Max[i][j] = k mean?

Process Pi may request up to k instances of resource Rj.

What is Allocation[n][m]?

Matrix showing how many resources are currently allocated to each process.

What does Allocation[i][j] = k mean?

Process Pi is currently allocated k instances of resource Rj.

What is Need[n][m]?

Matrix showing the remaining resource needs of each process.

How is Need[i][j] calculated?

Need[i][j] = Max[i][j] - Allocation[i][j]

What does Need[i][j] = k mean?

Process Pi may still need k more instances of Rj to finish.

When is vector X less than or equal to vector Y?

X ≤ Y iff for all i, X[i] ≤ Y[i] and X ≠ Y.

What is the purpose of the Safety Algorithm?

To determine whether the system is in a safe state.

how does safety algorithm work?

1. Let Work[m] = Available and Finish[i] = false for i = 0, ..., n-1

2. Find an index i such that both:

   • Finish[i] == false → Pi is not finished

   • Need[i] ≤ Work → Needs at most the number of available resources
     If no such i exists, go to step 4.

3. Work = Work + Allocation[i] → Release resources
   Finish[i] = true → Finish Pi
   Go to step 2.

4. If Finish[i] == true for all i, then the system is in a safe state.

What is the time complexity of the Safety Algorithm?

It may require m × n² operations, where m = resource types and n = processes.

What is the basic idea of resource-request?

• Let Requestᵢ be the request vector for process Pᵢ.

• If Requestᵢ[j] = k, then Pᵢ wants k instances of resource Rⱼ.

How does resource-request algorithm work?

When a request for resources is made by Pᵢ, the following actions are taken:

1. If Requestᵢ ≤ Needᵢ, go to step 2.
   Otherwise, raise an error since Pᵢ has exceeded its max claim.

2. If Requestᵢ ≤ Available, go to step 3.
   Otherwise, Pᵢ must wait since the resources are not available.

3. Have the system pretend to have allocated the requested resources to Pᵢ by modifying the state as follows:

   Available = Available - Requestᵢ

   Allocationᵢ = Allocationᵢ + Requestᵢ

   Needᵢ = Needᵢ - Requestᵢ

If the system is still in a safe state after these actions, complete transaction. Otherwise, revert the allocation and Pᵢ must wait and old state is restored.

What data structures are needed for deadlock algorithms?

• Available[m] → Number of available resources of each type

• Allocation[n][m] → Number of each resource type currently allocated to each process

• Request[n][m] → Current request of each process

  • Request[i][j] = k → Process Pᵢ is requesting k more instances of resource Rⱼ

How does deadlock detection algorithm

1. Initialize Work[m] = Available, and set Finish[n]:

   • For i = 0, ..., n-1, if Allocation[i] ≠ 0, then Finish[i] = false, else Finish[i] = true

2. Find an index i such that:

   • a. Finish[i] == false (Process is not finished), and

   • b. Request[i] ≤ Work (Process's request can be satisfied)

   If no such i exists, go to step 4.

3. Simulate resource release:

   • Work = Work + Allocation[i] → Process finishes and releases resources

   • Finish[i] = true

   • Go to step 2

4. Final check:

   • If any Finish[i] == false, then the system is in a deadlocked state

   • Each such Pᵢ is deadlocked

When should deadlock detection algorithm be used?

should be invoked frequently if deadlocks occur frequently.

In extreme cases, it should be used every time a resource request cannot be granted immediately.