Chapter 8: Deadlocks in Operating Systems

What are the four necessary conditions that characterize deadlock?

1. Mutual exclusion: only one thread can use a resource at a time. 2. Hold and wait: a thread holding resources is waiting for more. 3. No preemption: resources can only be released voluntarily. 4. Circular wait: a set of threads is waiting in a circular chain.

What is the system model in the context of deadlocks?

The system consists of resources, including types like CPU cycles, memory space, and I/O devices, with each resource type having multiple instances.

How do threads utilize resources in a system?

Threads utilize resources by requesting, using, and releasing them.

What is a semaphore, and how is it used in deadlock scenarios?

A semaphore is a synchronization tool initialized to a value (e.g., 1) that controls access to resources. In deadlock scenarios, two threads may wait on each other's semaphores, leading to a deadlock.

What is a resource-allocation graph?

A resource-allocation graph consists of vertices representing threads and resource types, with edges indicating requests and assignments.

What does a request edge in a resource-allocation graph represent?

A request edge is a directed edge from a thread to a resource, indicating that the thread is requesting that resource.

What does an assignment edge in a resource-allocation graph represent?

An assignment edge is a directed edge from a resource to a thread, indicating that the resource is currently allocated to that thread.

What is the significance of cycles in a resource-allocation graph?

If the graph contains no cycles, there is no deadlock. If it contains a cycle, deadlock may occur if there is only one instance per resource type.

What is deadlock prevention?

Deadlock prevention involves ensuring that the system will never enter a deadlock state through specific strategies.

What is deadlock avoidance?

Deadlock avoidance is a method that allows the system to enter a deadlock state but takes measures to ensure it does not occur.

What is deadlock detection?

Deadlock detection involves identifying when a deadlock has occurred in the system.

What are the approaches for recovering from deadlock?

Recovery approaches may include terminating processes, rolling back processes to safe states, or preempting resources.

What is the banker's algorithm?

The banker's algorithm is a deadlock avoidance algorithm that allocates resources based on current needs and future requests to ensure safe states.

What is the role of mutex locks in deadlocks?

Mutex locks can lead to deadlocks when multiple threads hold locks and wait for each other to release them.

What is the difference between deadlock prevention and deadlock avoidance?

Deadlock prevention aims to ensure that the system never enters a deadlock state, while deadlock avoidance allows for the possibility of deadlocks but prevents them from occurring.

What happens if a resource-allocation graph contains multiple instances of a resource type?

If a graph contains a cycle but multiple instances of a resource type, there is a possibility of deadlock, but it is not guaranteed.

How can you identify a deadlock situation in a resource allocation graph?

A deadlock situation can be identified if there is a cycle in the graph where threads are waiting for resources held by each other.

What is the importance of the 'no preemption' condition in deadlock characterization?

The 'no preemption' condition means that once a resource is allocated to a thread, it cannot be forcibly taken away, which can lead to deadlock.

What does 'hold and wait' imply in the context of deadlocks?

'Hold and wait' implies that a thread holding one or more resources is waiting to acquire additional resources held by other threads.

What is the implication of having a cycle in a resource allocation graph?

A cycle in a resource allocation graph indicates a potential deadlock situation, especially if there is only one instance of each resource type.

What are the basic facts regarding cycles in resource-allocation graphs?

If the graph contains no cycles, there is no deadlock. If it contains a cycle, deadlock may occur depending on the number of resource instances.

What are the four necessary conditions for deadlock?

1. Mutual Exclusion 2. Hold and Wait 3. No Preemption 4. Circular Wait

What is the mutual exclusion condition in the context of deadlock?

Mutual Exclusion is not required for sharable resources (e.g., read-only files) but must hold for non-sharable resources.

How can the hold and wait condition be invalidated?

By guaranteeing that whenever a thread requests a resource, it does not hold any other resources, or by requiring threads to request all resources before execution or only when they have none allocated.

What are the potential downsides of invalidating the hold and wait condition?

Low resource utilization and possible starvation.

What does the no preemption condition entail in deadlock prevention?

If a process holding resources requests another resource that cannot be allocated, all held resources are released, and the thread is restarted only when it can regain its old and new requested resources.

How can circular wait be prevented?

By imposing a total ordering of all resource types and requiring that each thread requests resources in an increasing order of enumeration.

What is the purpose of deadlock avoidance?

To ensure that the system never enters a circular-wait condition by using a priori information about resource needs.

What is the simplest model for deadlock avoidance?

Each thread declares the maximum number of resources of each type that it may need.

What is a safe state in the context of resource allocation?

A system is in a safe state if there exists a sequence of threads such that each thread can be satisfied with currently available resources plus resources held by previously finished threads.

What happens if a system is in a safe state?

If a system is in a safe state, there are no deadlocks.

What does it mean if a system is in an unsafe state?

If a system is in an unsafe state, there is a possibility of deadlock.

What is the relationship between avoidance and unsafe states?

Avoidance ensures that a system will never enter an unsafe state.

How does the system determine if it can allocate a resource to a thread?

The system must decide if immediate allocation leaves the system in a safe state.

What is the definition of the resource-allocation state?

The resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes.

What is the implication of a thread's resource needs not being immediately available?

The thread can wait until all previously finished threads have completed.

What occurs when a thread terminates in a safe state?

When a thread terminates, the next thread in the sequence can obtain its needed resources.

What is the significance of assigning unique numbers to resources?

It helps to impose an order in which resources must be acquired, preventing circular wait.

What is the consequence of a thread requesting resources in a non-increasing order?

It can lead to a circular wait condition, which is a necessary condition for deadlock.

What is starvation in the context of resource allocation?

Starvation occurs when a thread is perpetually denied the resources it needs to proceed.

What does it mean for a resource to be sharable?

Sharable resources can be accessed by multiple threads simultaneously without causing deadlock.

What is the importance of the maximum demand declaration by threads?

It allows the deadlock-avoidance algorithm to dynamically examine the resource-allocation state.

What are the two types of states in resource allocation?

Safe and Unsafe states.

What is the purpose of a resource-allocation graph?

To manage resource allocation between processes and prevent deadlocks.

What does a claim edge in a resource-allocation graph indicate?

It indicates that a process may request a resource.

What happens to a claim edge when a thread requests a resource?

It converts to a request edge.

What is the Banker's Algorithm used for?

To manage resource allocation when multiple instances of a resource type are available.

What must each thread do before requesting resources in the Banker's Algorithm?

Each thread must claim its maximum resource usage a priori.

What is the condition for granting a resource request in the resource-allocation graph?

The request can be granted only if it does not form a cycle in the graph.

What are the four data structures used in the Banker's Algorithm?

Available vector, Max matrix, Allocation matrix, Need matrix.

How is the Need matrix calculated in the Banker's Algorithm?

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

What is the first step in the Safety Algorithm?

Initialize Work to Available and Finish[i] to false for all processes.

What does the Safety Algorithm check for?

It checks if the system is in a safe state by ensuring all processes can finish.

What does the Resource-Request Algorithm determine?

It determines if a process can be granted its requested resources without exceeding limits.

What must be true for a request to be valid in the Resource-Request Algorithm?

Request must be less than or equal to Need and Available.

What happens if a process's request exceeds its maximum claim?

An error condition is raised.

What is the significance of the Finish vector in the Safety Algorithm?

It indicates whether a process has completed its execution.

What is the role of the Work vector in the Safety Algorithm?

It keeps track of the currently available resources.

What occurs in step 2 of the Safety Algorithm?

Find a process that can finish based on current Work and Need.

What is the outcome if no process can finish in the Safety Algorithm?

The algorithm concludes that the system is in an unsafe state.

What does the term 'unsafe state' imply in resource allocation?

It implies that there is a potential for deadlock.

What is the maximum claim of a process in the context of resource allocation?

The maximum number of instances of each resource type that a process may request.

What does the assignment edge represent in a resource-allocation graph?

It represents that a resource has been allocated to a thread.

What happens to the assignment edge when a resource is released?

It reconverts to a claim edge.

What is the first step in the resource allocation process for thread Ti in the Banker's Algorithm?

Modify the state by reducing Available by Requesti, increasing Allocationi by Requesti, and decreasing Needi by Requesti.

What happens if the system is in a safe state after a resource allocation?

The resources are allocated to thread Ti.

What happens if the system is in an unsafe state after a resource allocation?

Thread Ti must wait, and the old resource-allocation state is restored.

In the example of the Banker's Algorithm, how many resource types are there?

Three resource types: A, B, and C.

What is the total number of instances for resource type A in the example?

10 instances.

What is the total number of instances for resource type B in the example?

5 instances.

What is the total number of instances for resource type C in the example?

7 instances.

How is the Need matrix defined in the context of the Banker's Algorithm?

Need is defined as Max - Allocation.

What is the sequence that satisfies the safety criteria in the example provided?

< T1, T3, T4, T2, T0 >.

What is the first check performed when a thread requests resources in the example?

Check that Request ≤ Available.

What is the result of executing the safety algorithm for the request (1,0,2) by P1?

The sequence < T1, T3, T4, T0, T2 > satisfies the safety requirement.

What is the purpose of a deadlock detection algorithm?

To allow the system to enter a deadlock state and then detect it.

What is the wait-for graph used for in deadlock detection?

To represent threads as nodes and indicate which thread is waiting for which.

What does a cycle in the wait-for graph indicate?

The presence of a deadlock.

What is the time complexity of the algorithm to detect a cycle in a wait-for graph?

O(n^2) operations, where n is the number of vertices.

What does the detection algorithm initialize Work and Finish vectors to?

Work is initialized to Available, and Finish is initialized based on Allocation.

What does the detection algorithm check for in step 2?

Find an index i such that Finish[i] is false and Requesti ≤ Work.

What happens if no such index i exists in the detection algorithm?

Proceed to step 4.

What does the detection algorithm conclude if Finish[i] is false for some i?

The system is in a deadlock state.

What factors influence when to invoke the deadlock detection algorithm?

How often a deadlock is likely to occur and how many processes need to be rolled back.

What is one method of recovering from deadlock?

Abort all deadlocked threads or abort one process at a time until the deadlock cycle is eliminated.

What criteria can be used to decide which thread to abort in a deadlock recovery scenario?

Priority of the thread, computation time, resources used, resources needed, number of threads to terminate, and whether the thread is interactive or batch.

What is resource preemption in the context of deadlock recovery?

Selecting a victim to minimize cost and rolling back to a safe state.

What is a potential issue with resource preemption?

Starvation, where the same thread may always be picked as a victim.