CSS 430 Book Notes Chapter 8 Deadlocks

8.1 System Model

When a waiting thread can never change state because a resource it requested is held by other waiting threads, the situation is called a deadlock.

Info

deadlock: The state in which two processes or threads are stuck waiting for an event that can only be caused by one of the processes or threads.

A system consists of a finite number of resources to be distributed among a number of competing threads.

The resources may be partitioned into several types, for instance, if a system has four CPUs, then the resource type CPU has four instances.

If a thread requests an instance of a resource type, the allocation of any instance of the type should satisfy the request. If it does not, then the instances are not identical, and the resource type classes have not been defined properly.
A thread must request a resource before using it and must release the resource after using it. A thread may request as many resources as it requires to carry out its designated task. Obviously, the number of resources requested may not exceed the total number of resources available in the system. In other words, a thread cannot request two network interfaces if the system has only one.

Under the normal mode of operation, a thread may utilize a resource in only the following sequence:

Request. The thread requests the resource. If the request cannot be granted immediately (for example, if a mutex lock is currently held by another thread), then the requesting thread must wait until it can acquire the resource.
Use. The thread can operate on the resource (for example, if the resource is a mutex lock, the thread can access its critical section).
Release. The thread releases the resource.
Developers of multithreaded applications must remain aware of the possibility of deadlocks. The locking tools presented in the chapter Synchronization Tools are designed to avoid race conditions. However, in using these tools, developers must pay careful attention to how locks are acquired and released. Otherwise, deadlock can occur, as described next.

8.2 Deadlock in multithreaded applications

Here we illustrate an example of deadlock using Pthreads

Two mutex locks are initialized

pthread_mutex_t first_mutex;
pthread_mutex_t second_mutex;
 
pthread_mutex_init(&first_mutex,NULL);
pthread_mutex_init(&second_mutex,NULL);

Next, two threads, thread_one and thread_two are created and both these have access to both mutex locks. thred_one and thread_two run in the functions do_work_one() and do_work_two()

/* thread_one runs in this function */
void *do_work_one(void *param)
{
   pthread_mutex_lock(&first_mutex);
   pthread_mutex_lock(&second_mutex);
   /**
     * Do some work
     */
   pthread_mutex_unlock(&second_mutex);
   pthread_mutex_unlock(&first_mutex);
 
   pthread_exit(0);
}
 
/* thread_two runs in this function */
void *do_work_two(void *param)
{
   pthread_mutex_lock(&second_mutex);
   pthread_mutex_lock(&first_mutex);
   /**
    * Do some work
    */
   pthread_mutex_unlock(&first_mutex);
   pthread_mutex_unlock(&second_mutex);
 
   pthread_exit(0);
}

Here, thread_one attempts to acquire first_mutex and then second_mutex while thread_two attempts to acquire second_mutex then first_mutex. If thread_one acquires first_mutex and thread_two acquires second mutex, deadlock can occur

Livelock

livelock is similar to deadlock in that it prevents two or more threads from proceeding. Livelock occurs when a thread continuously attempts an action that fails. (think people trying to pass where they keep moving to the same side.)

/* thread_one runs in this function */
void *do_work_one(void *param)
{
   int done = 0;
 
   while (!done) {
      pthread_mutex_lock(&first_mutex);
      if (pthread_mutex_trylock(&second_mutex)) {
         /**
          * Do some work
          */
         pthread_mutex_unlock(&second_mutex);
         pthread_mutex_unlock(&first_mutex);
         done = 1;
     }
     else
         pthread_mutex_unlock(&first_mutex);
   }
   pthread_exit(0);
}
 
/* thread_two runs in this function */
void *do_work_two(void *param)
{
   int done = 0;
 
   while (!done) {
     pthread_mutex_lock(&second_mutex);
     if (pthread_mutex_trylock(&first_mutex)) {
         /**
          * Do some work
          */
         pthread_mutex_unlock(&first_mutex);
         pthread_mutex_unlock(&second_mutex);
         done = 1;
     }
     else
         pthread_mutex_unlock(&second_mutex);
   }
 
   pthread_exit(0);
}

8.3 Deadlock Characterization

Necessary Conditions

A deadlock situation can arise if the following four conditions hold simultaneously in a system:

Mutual Exclusion: At least one resource must be held in a nonsharable mode; that is, only one thread at a time can use the resource. If another thread requests that resource, the requesting thread must be delayed until the resource has been released.
Hold and Wait: A thread must be holding at least one resource and waiting to acquire additional resources that are currently being held by other threads.
No preemption: Resources cannot be preempted. IE, a resource can be released only voluntarily by the thread holding it after the thread completes its task
Circular Wait: A set { $T_{0}$ , $T_{1}$ ,... $T_{N}$ } of waiting threads must exist such that $T_{0}$ is waiting for a resource held by $T_{1}$ , $T_{1}$ is waiting for a resource held by $T_{2}$ , …, $T_{N - 1}$ is waiting for a resource held by $T_{N}$ , and $T_{N}$ is waiting for a resource held by $T_{0}$ .

In order for dead lock to occur, all four of the above must be true.

Resource Allocation Graph

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 $V$ vertices and a set of edges $E$ . The set of vertices $V$ is partitioned into two different types of nodes, $T = T_{1}, T_{2}, . . . T_{N}$ , the set consisting of all active threads in the system, and $R = R_{1}, R_{2}, . . . R_{M}$ , the set of all resource types in the system.

A directed edge from thread $T_{i}$ to resource type $R_{i}$ is denoted by $T_{i} \to R_{J}$ . it signifies that thread $T_{i}$ has requested an instance of resource type $R_{j}$ and is currently waiting for that resource. A directed edge of from resource $R_{j}$ to thread $T_{i}$ is denoted by $R_{j} \to T_{i}$ . It signifies that an instance of resource type $R_{j}$ has been allocated to thread $T_{i}$ . A directed edge $T_{i} \to R_{j}$ is called a request edge and a directed edge $R_{j} \to T_{i}$ is called an assignment edge.

Generally we represent each thread $T_{i}$ as a circle and each resource type $R_{j}$ as a rectangle

Since resource $R_{j}$ may have more than one instance, we represent each instance as a dot within the rectangle. A request edge only points to the rectangle, however, an assignment edge points from one of the dots(resources) in the rectangle.
Pasted image 20230213192632.png

thread_one acquires first_mutex.
thread_two acquires second_mutex.
thread_one wants second_mutex, which could be freed up by thread_two.
thread_two wants first_mutex, and as it is still holding second_mutex which thread_one is waiting for, there is a cycle in the graph: first_mutex → T1 → second_mutex → T2 → first_mutex.

When thread $T_{i}$ requests an instance of resource type $R_{j}$ , a request edge is inserted in the resource allocation graph. When this request can be fulfilled, the request edge is instantaneously transformed to an assignment edge.
Once a thread finishes with a resource, the assignment edge is deleted.

Example

The sets $T$ , $R$ , $E$ :

$T = T_{1}, T_{2}, T_{3}$
$R = R_{1}, R_{2}, R_{3}, R_{4}$
$E = T_{1} \to R_{1}, T_{2} \to R_{3}, R_{1} \to T_{2}, R_{2} \to T_{2}, R_{2} \to T_{1}, R_{3} \to T_{3}$

Resource Instances:
- One instance of resource type $R_{1}$
- Two instances of resource type $R_{2}$
- One instance of resource type $R_{3}$
- Three instances of resource type $R_{4}$

Thread States:

Thread $T_{1}$ is holding an instance of resource type $R_{2}$ and is waiting for an instance of resource type $R_{1}$ .
Thread $T_{2}$ is holding an instance of $R_{1}$ and an instance of $R_{2}$ and is waiting for an instance of $R_{3}$ .
Thread $T_{3}$ is holding an instance of $R_{3}$

if the graph contains no cycles, then no thread in the system is deadlocked. If the graph does contain a cycle, then a deadlock may exist.

If each resource type has exactly one instance, then a cycle implies that a deadlock has occurred. If the cycle involves only a set of resource types, each of which has only a single instance, then a deadlock has occurred. Each thread involved in the cycle is deadlocked. In this case, a cycle in the graph is both a necessary and a sufficient condition for the existence of deadlock.

If we take the above graph, and add an instance where $T_{3}$ requests an instance of type $R_{2}$ , we will add edge $T_{3} \to R_{2}$ . This creates two possible cycles in the graph

T1 → R1 → T2 → R3 → T3 → R2 → T1
T2 → R3 → T3 → R2 → T2

Threads $T_{1}$ , $T_{2}$ , and $T_{3}$ are deadlocked. $T_{2}$ is waiting for $R_{3}$ , which is held by $T_{3}$ . $T_{3}$ is waiting for $T_{1}$ or $T_{2}$ to release resource $R_{2}$ . Additionally, $T_{1}$ is waiting for $T_{2}$ to release $R_{1}$
Pasted image 20230213194400.png

In the following however, there is no deadlock. There is a cycle, however $T_{4}$ may release its instance of resource $R_{2}$ which can then be allocated to $T_{3}$ .

Methods for handling deadlocks

We can deal with deadlocks in one of three ways:

We can ignore the problem altogether and pretend that deadlocks never occur in the system.
We can use a protocol to prevent or avoid deadlocks, ensuring that the system will never enter a deadlocked state.
We can allow the system to enter a deadlocked state, detect it, and recover.
Most operating systems (including Windows and Linux) use option 1.

Deadlock prevention provides a set of methods to ensure that at least one of the necessary conditions (Section Necessary conditions) cannot hold. These methods prevent deadlocks by constraining how requests for resources can be made.

Deadlock avoidance requires that the operating system be given additional information in advance concerning which resources a thread will request and use during its lifetime. With this additional knowledge, the operating system can decide for each request whether or not the thread should wait.

8.5 Deadlock Prevention

If we prevent one of the four necessary conditions for deadlocks(mutual exclusion, hold and wait, no preemption, and circular wait), we can prevent deadlock from occurring.

Mutual exclusion

In general, we cannot prevent deadlocks by denying the mutual-exclusion condition, because some resources are intrinsically nonsharable. For example, a mutex lock cannot be simultaneously shared by several threads.

Hold and Wait

To ensure that the hold-and-wait condition never occurs in the system, we must guarantee that, whenever a thread requests a resource, it does not hold any other resources.
One way we can do this is require that each thread be allocated all its resources before it begins execution, however this is difficult to implement

Another method is allowing a thread to request resources only when it has none. A thread can request some resources, uses them, but must release them before it requests more.
Both these protocols have two main disadvantages. First, resource utilization may be low, since resources may be allocated but unused for a long period. For example, a thread may be allocated a mutex lock for its entire execution, yet only require it for a short duration. Second, starvation is possible. A thread that needs several popular resources may have to wait indefinitely, because at least one of the resources that it needs is always allocated to some other thread.

No preemption

If a thread is holding some resources and requests another resource that cannot be immediately allocated to it (that is, the thread must wait), then all resources the thread is currently holding are preempted. In other words, these resources are implicitly released. The preempted resources are added to the list of resources for which the thread is waiting. The thread will be restarted only when it can regain its old resources, as well as the new ones that it is requesting.
Alternatively, if a thread requests some resources, we first check whether they are available. If they are, we allocate them. If they are not, we check whether they are allocated to some other thread that is waiting for additional resources. If so, we preempt the desired resources from the waiting thread and allocate them to the requesting thread. If the resources are neither available nor held by a waiting thread, the requesting thread must wait. While it is waiting, some of its resources may be preempted, but only if another thread requests them. A thread can be restarted only when it is allocated the new resources it is requesting and recovers any resources that were preempted while it was waiting.

Circular Wait

Consider the set $R = R_{1}, R_{2}, . . . R_{M}$ as the set of resource types. We assign each resource type a unique integer number. This allows us to compare two resources and determine which one precedes another in our ordering. We define a one-to-one function $F : R \to N$ where $N$ is the set of natural numbers.

We can accomplish this scheme in an application program by developing an ordering among all synchronization objects in the system. For example, the lock ordering in the Pthread program shown below could be:

F(first_mutex)=1;
F(second_mutex)=1;

We now can use the following protocol to prevent a deadlock. Each thread can request resources only in an increasing order of enumeration. Or, a thread can initially request an instance of a resource, say $R_{i}$ . After that, the thread can request an instance of $R_{j}$ if and only if $F (R_{j}) > F (R_{i})$

Using the function defined above, a thread which wants to use both first_mutex and second_mutex at the same time must first request first_mutex and then second_mutex.

We can also require thread requesting an instance of $R_{j}$ must have released any resources $R_{i}$ such that $F (R_{i}) \geq F (R_{j})$ . If several instances of the same resource type are needed, a single request for them must be issued.

If these two protocols are used, circular-wait cannot hold. This can be demonstrated by assuming that a circular wait exists. If the set of threads involved in the circular wait are $T_{1}, T_{2}, . . . T_{N}$ where $T_{i}$ is waiting for a resource $R_{i}$ which is held by thread (modulo arithmetic is used on the indexes so that $T_{N}$ is waiting for resource $R_{N}$ held by $T_{0}$ ) $T_{i + 1}$ , then since $T_{i + 1}$ is holding resource $R_{i}$ while requesting resource $R_{i + 1}$ , we must have $F (R_{i}) < F (R_{i + 1}$ for all $i$ . This condition means that $F (R_{0}) < F (R_{1}) < . . . < F (R_{N}) < F (R_{0})$ . Since $F (R_{0})$ cannot be less than $F (R_{0})$ we know this circular wait cannot hold true.

It is also important to note that imposing a lock ordering does not guarantee deadlock prevention if locks can be acquired dynamically. For example, assume we have a function that transfers funds between two accounts. To prevent a race condition, each account has an associated mutex lock that is obtained from a get_lock() function such as that shown below. Deadlock is possible if two threads simultaneously invoke the transaction() function, transposing different accounts. That is, one thread might invoke

Deadlock with lock ordering

void transaction(Account from, Account to, double amount)
{
  mutex lock1, lock2;
  lock1 = get_lock(from);
  lock2 = get_lock(to);
 
  acquire(lock1);
    acquire(lock2);
 
      withdraw(from, amount);
      deposit(to, amount);
 
    release(lock2);
  release(lock1);
}

8.6 Deadlock Avoidance

An alternative method for preventing deadlocks is to require additional info about how resources are to be requested. For example, in a system with resources $R_{1}$ and $R_{2}$ , the system might need to know that thread $P$ will request first $R_{1}$ $ and then $R_{2}$ before releasing both resources, whereas thread $Q$ will request $R_{2}$ and then $R_{1}$ .

With this knowledge of the complete sequence of requests and releases for each thread, the system can decide for each request whether or not the thread should wait in order to avoid a possible future deadlock. Each request requires that in making this decision the system consider the resources currently available, the resources currently allocated to each thread, and the future requests and releases of each thread.

The simplest and most useful model requires that each thread declare the maximum number of resources of each type that it may need. Given this, it's possible to create an algorithm that ensures that the system will never enter a deadlocked state.

Deadlock avoidance algorithms dynamically examines the resource allocation state to ensure that a circular-wait condition can never exist. The resource allocation state is defined by the number of available and allocated resources and the maximum demands of the threads

Safe State

A state is safe if the system can allocate resources to each thread (up to its maximum) in some order and still avoid a deadlock.

A system is in a safe state only if there exists a safe sequence. A sequence such as $< T_{1}, T_{2}, . . . T_{N} >$ is safe for the current allocation state if for eacht $T_{i}$ the resource requests that $T_{i}$ can still make can be satisfied by the currently available resources plus the resources held by all $T_{j}$ with $j < i$ . If the resources that $T_{i}$ needs are not immediately available, then $T_{i}$ can wait until all $T_{j}$ have finished. When they're done, $T_{i}$ can obtain all of its needed resources, do critical work, then terminate. When $T_{i}$ terminates, $T_{i + 1}$ can obtain its needed resources and so on.

An unsafe state may lead to a deadlock, but doesn't necessarily do so.

Safe, Unsafe, and Deadlocked State Spaces

Pasted image 20230214145832.png

For example, lets say you have 12 resources and three threads, $< T_{0}, T_{1}, a n d T_{2} >$ . Thread $T_{0}$ requires a maximum of 10 resources, $T_{1}$ a maximum of four, and $T_{2}$ a max of 9. Suppose that at time $t_{0}$ , thread $T_{0}$ is holding 5 resources, $T_{1}$ is holding 2, and $T_{2}$ is holding 2, leaving us with 3 free resources ( $5 + 2 + 2 = 9$ ).

	Maximum Needs	Current Needs
$T_{0}$	10	5
$T_{1}$	4	2
$T_{2}$	9	2

at time $t_{0}$ the system is in a safe state. The sequence $< T_{0}, T_{1}, T_{2} >$ satisfies the safety condition. Thread $T_{1}$ can be allocated 2 resources, complete it's task at which point there will be 5 available resources. thread $T_{0}$ can then get it's necessary 5 resources, complete it's task, and return them which would give us 10 available resources. Finally $T_{2}$ can acquire its needed resources and return them giving the system all 12 resources back.

A system can go from safe to unsafe pretty easily. For instance, if at time $t_{1}$ thread $T_{2}$ is allocated one more resource, there will not be enough resources to complete task $T_{0}$ after $T_{1}$ completes
Additionally, If thread $T_{2}$ had requested and been allocated 6 resources, we would have had to wait, which would have resulted in deadlock. Therefore the mistake is in granting additional resources to thread $T_{2}$ . Instead we should have made it wait.

Resource-allocation-graph-algorithm.

If we have a resource-allocation system with only one instance of each resource type, we can use a variant of the resource-allocation graph for deadlock avoidance. In addition to the request and assignment edges already described, we can introduce a new type of edge, called a claim edge. A claim edge $T_{i} \to R_{j}$ indicates a thread $T_{i}$ may request resource $R_{j}$ at some time in the future. This edge resembles a request edge in direction but is represented in the graph by a dashed line. When thread $T_{i}$ requests resource $R_{j}$ the claim edge $T_{i} \to R_{j}$ is converted to a request edge. Similarly, when resource $R_{j}$ is released by $T_{i}$ the assignment edge $R_{j} \to T_{i}$ is reconverted to a claim edge $T_{i} \to R_{j}$ .

The resources must be claimed a priori in the system, or before thread $T_{i}$ starts executing, all its claim edges must already appear in the resource allocation graph. We can relax this condition by allowing claim edge $T_{i} \to R_{j}$ to be added to the graph only if all the edges associated with thread $T_{i}$ are claim edges.

Suppose that thread $T_{i}$ requests $R_{j}$ , the request can be granted only if converting the edge $T_{i} \to R_{j}$ to an assignment edge $R_{j} \to T_{i}$ does not result in the formation of a cycle in the resource-allocation graph.We check for safety by using a cycle-detection algorithm. An algorithm for detecting a cycle requires an order of $n^{2}$ operations where $n$ is the number of threads in the system.

If no cycle exists, the allocation of resources will leave the system in a safe state. If a cycle is found, the allocation will put the system in an unsafe state. in that case, thread $T_{i}$ will have to wait for its request to be satisfied

Example:

Pasted image 20230214152919.png
Suppose that $T_{2}$ requests $R_{2}$ . Although $R_{2}$ is currently free, we cannot allocate it to $T_{2}$ since this action will create a cycle in the graph. A cycle indicates that the system is in an unsafe state. If $T_{1}$ requests $R_{2}$ and $T_{2}$ requests $R_{1}$ then a deadlock will occur

An unsafe state in the resource-allocation graph

Pasted image 20230214153408.png

Banker's Algorithm

The resource-allocation-graph algorithm is not applicable to a resource-allocation system with multiple instances of each resource type. The deadlock-avoidance algorithm that we describe next is applicable to such a system but is less efficient than the resource-allocation graph scheme. This algorithm is commonly known as the banker's algorithm.
When a new thread enters the system, it must declare the maximum number of instances of each resource type that it may need. This number may not exceed the total number of resources in the system. When a user requests a set of resources, the system must determine whether the allocation of these resources will leave the system in a safe state. If it will, the resources are allocated; otherwise, the thread must wait until some other thread releases enough resources.

To implement the banker's algorithm, we need to use several data structures. These data structures encode the state of the resource allocation system. In the following data structures, $n$ is the number of threads in the system and $m$ is the number of resources.

Available: A vector of length $m$ indicates the number of available resources of each type. if Available[ $j$ ] equals $k$ , $k$ instances of resource type $R_{j}$ are available.
Max: A $n \times m$ matrix defines the maximum demand of each thread. If Max[ $i$ ][j] equals $k$ , thread $T_{i}$ may request at most $k$ instances of resource type $R_{j}$
Allocation: An $n \times m$ matrix defines the number of resources of each type currently allocated to each thread. If Allocation[ $i$ ][j] equals $k$ , thread $T_{i}$ is currently allocated $k$ instances of resource type $R_{j}$
Need: An $n \times m$ matrix indicates the remaining resources need of each thread. if Need[ $i$ ][j] equals $k$ , then thread $T_{i}$ may need $k$ more instances of resource type $R_{j}$ to complete it's task. Note that Need[ $i$ ][j] = Max[ $i$ ][j] - Allocation[ $i$ ][j]

To simplify the presentation of the banker's algorithm, we can establish some notation. Let $X$ and $Y$ be vectors of length $n$ . We say that $X \leq Y$ if and only if $X [i] \leq Y [i]$ for all $i = 1, 2, . . . n$ . For example, if $X = (1, 7, 3, 2)$ and $Y = (0, 3, 2, 1$ then $Y \leq X$ . In addition, $Y < X$ if $Y \leq X$ and $Y \neq X$

We can treat each row in the matrices Allocation and Need as vextors and refer to them as $A l l o c a t i o n_{i}$ and $N e e d_{i}$ The vector $A l l o c a t i o n_{i}$ specifies the resources currently allocated to $T_{i}$ . The vector $N e e d_{i}$ specifies the additional resources that the thread T_i may still request to complete its task.

Safety Algorithm

We can now present the algorithm for finding out whether or not a system is in a safe state. This algorithm can be described as follows:

Let Work and Finish be vectors of length $m$ and $n$ , respectively. Initialize Work = Available and Finish[ $i$ ] = false for $i$ = 0, 1, …, $n$ − 1.
Find an index $i$ such that both
1. Finish[ $i$ ] == false
2. $N e e d_{i}$ ≤ Work
  If no such $i$ exists, go to step 4.
Work = Work + Allocationi Finish[ $i$ ] = true Go to step 2.
If Finish[ $i$ ] == true for all $i$ , then the system is in a safe state.

This algorithm may require an order of $m \times n^{2}$ operations to determine whether a state is safe.

Resource Request Algorithm

Next, we describe the algorithm for determining whether requests can be safely granted. Let $R e q u e s t_{i}$ be the request vector for thread $T_{i}$ . If $R e q u e s t_{i} [j]$ == $k$ , then thread $T_{i}$ wants $k$ instances of resource type $R_{j}$ . When a request for resources is made by thread $T_{i}$ , the following actions are taken:

If $R e q u e s t_{i} \leq N e e d_{i}$ go to step 2. Otherwise, raise an error condition since the thread has exceeded its maximum claim.
If $R e q u e s t_{i} \leq A v a i l a b l e$ go to step 3, Otherwise $T_{i}$ must wait since the resources are not available.
Have the system pretend to have allocates the requested resources to thread $T_{i}$ by modifying the state as follows

Available = Available-Requesti
Allocationi = Allocationi + Requesti
Need = Needi-Requesti

If the resulting resource allocation state is safe, the transaction is completed and the thread $T_{i}$ is allocated its resources. However, if the new state is unsafe, then $T_{i}$ must wait for $R e q u e s t_{i}$ and the old resource allocation state is restored.

Example:

To illustrate the use of the banker's algorithm, consider a system with five threads, $T_{0}$ through $T_{4}$ , and three resource types, $A, B,$ and $C$ . Resource type $A$ has ten instances, resource type $B$ has five instances, and resource type $C$ has seven instances. The following snapshot represents the state of the system.

	Allocation	Max	Available
	ABC	ABC	ABC
$T_{0}$	010	753	332
$T_{1}$	200	322
$T_{2}$	302	902
$T_{3}$	211	222
$T_{4}$	002	433

The content of the matrix Need is defined to be Max-Allocationand is as follows:

	Need
	ABC
$T_{0}$	743
$T_{1}$	122
$T_{2}$	600
$T_{3}$	011
$T_{4}$	431

We claim that the system is currently in a safe state. Indeed, the sequence $< T_{1}, T_{3}, T_{4}, T_{2}, T_{0} >$ satisfies the safety criteria. Suppose now that thread $T_{1}$ requests one additional instance of resource type $A$ and two instances of resource type $C$ , so $R e q u e s t_{i} = (1, 0, 2)$ . To decide whether this request can immediately be granted, we first check that $R e q u e s t_{i} \leq A v a i l a b l e$ , that is that $(1, 0, 2) \leq (3, 3, 2)$ which is true. We then pretend that this request has been fulfilled, and we arrive at the following new state:

	Allocation	Need	Available
	ABC	ABC	ABC
$T_{0}$	010	743	230
$T_{1}$	200	020
$T_{2}$	302	600
$T_{3}$	211	011
$T_{4}$	002	431

We must determine whether this new system state is safe. To do so, we execute our safety algorithm and find that the sequence $< T_{1}, T_{3}, T_{4}, T_{2}, T_{0} >$ satisfies the safety requirement, Hence we can immediately grant the request of threat $T_{1}$ .

However, we can see, that when the system is in this state, a request for (3,3,0) by $T_{4}$ cannot be granted since the resources are not available. Furthermore, a request for (0,2,0) by $T_{0}$ cannot be granted, even though the resources are available since the resulting state is unsafe.

8.7 Deadlock Detection

If a system does not employ either a deadlock-prevention or deadlock avoidance algorithm, then a deadlock situation may occur. To solve for this, the operating system may provide:

An algorithm that examines the state of the system to determine whether a deadlock has occurred
An algorithm to recover from the deadlock

Single instance of each resource type

If all resources have only a single instance, we can define a deadlock detection algorithm that uses a variant of the resource allocation graph called a wait-for graph. We obtain this graph from the resource allocation graph by removing the resource nodes and collapsing the appropriate edges.

An edge from $T_{i}$ to $T_{j}$ in a wait for graph implies that thread $T_{i}$ is waiting for thread $T_{j}$ to release a resource that $T_{i} n e e d s$ . An edge, $T_{i} \to T_{j}$ exists in a wait-for graph if and only if the corresponding resource allocation graph contains two edges, $T_{i} \to R_{q}$ and $R_{q} \to T_{j}$ for some resource $R_{q}$

Resource allocation graph(a) and corresponding wait-for graph(b)

Pasted image 20230215204544.png

A deadlock exists in the system if and only if the wait-for graph contains a cycle. To detect deadlocks, the system needs to maintain the wait-for graph and periodically invoke an algorithm that searches for a cycle in the graph. this is an $O (n^{2})$ operation where $n$ is the number of vertices in the graph.

Several instances of a resource type

The wait-for graph scheme is not applicable to a resource-allocation system with multiple instances of each resource type, however we can use an algorithm similar to the banker's algorithm to deal with this

Available. A vector of length $m$ indicates the number of available resources of each type.
Allocation. An $n \times m$ matrix defines the number of resources of each type currently allocated to each thread.
Request. An $n \times m$ matrix indicates the current request of each thread. If Request[j][ j] equals k, then thread $T_{i}$ is requesting $k$ more instances of resource type $R_{j}$ .
We treat the rows in the matrices Allocation and Request as vectors and refer to them as $A l l o c a t i o n_{i}$ and $R e q u e s t_{i}$ . The detection algorithm investigates every possible allocation sequence for the threads that remain to be completed.

Let Work and Finish be vectors of length $m$ and $n$ respectively. Initialize $W o r k = A v a i l a b l e$ . For $i = 0, 1, . . . n$ if $A l l o c a t i o n \neq 0$ , $F i n i s h [i] = f a l s e$ otherwise $F i n i s h [i] = t r u e$
Find an index $i$ such that both
- $F i n i s h [i] == f a l s e$
- $R e q u e s t_{i} \leq W o r k$
  if no such $i$ exists, go to step 4
$W o r k = W o r k + A l l o c a t i o n_{i}, F i n i s h [i] = t r u e$ go to step 2
If $F i n i s h [i] == f a l s e$ for some $i$ , $0 \leq i < n$ then the system is in a deadlocked state. If $F i n i s h [i] == f a l s e$ , then thread $T_{i}$ is deadlocked.

This algorithm requires $m \times n^{2}$ operations to detect whether the system is in a deadlocked state.

Recovery From Deadlock

There are two options for breaking a deadlock. One is simply to abort one or more threads to break the circular wait. The other is to preempt some resources from one or more of the deadlocked threads.

Process and thread termination

Elimination by abortion can use one of two methods. In both methods, the system reclaims all resources allocated to the terminated processes.

Abort all deadlocked processes. This method clearly will break the deadlock cycle, but at great expense. The deadlocked processes may have computed for a long time, and the results of these partial computations must be discarded and probably will have to be recomputed later.
Abort one process at a time until the deadlock cycle is eliminated. This method incurs considerable overhead, since after each process is aborted, a deadlock-detection algorithm must be invoked to determine whether any processes are still deadlocked.

Aborting a process may have repercussions. If the process was, say, updating a file, it may leave the file in an incorrect state. Additionally, if a process was holding a mutex, the system must restore the status of the mutex as being available.

If aborting one process at a time, the system must determine which process or processes should be terminated. Ideally, the system should abort the process whose termination will incur the minimum cost, unfortunatley many factors play into what may constitute minimum cost.

What the priority of the process is
How long the process has computed and how much longer the process will compute before completing its designated task
How many and what types of resources the process has used (for example, whether the resources are simple to preempt)
How many more resources the process needs in order to complete
How many processes will need to be terminated

Resource Preemption

To eliminate deadlocks using resource preemption, we successively preempt some resources from processes and give these resources to other processes until the deadlock cycle is broken.

If preemption is required to deal with deadlocks, then three issues need to be addressed:

Selecting a victim. Which resources and which processes are to be preempted? As in process termination, we must determine the order of preemption to minimize cost. Cost factors may include such parameters as the number of resources a deadlocked process is holding and the amount of time the process has thus far consumed.
Rollback.
If we preempt a resource from a process, what should be done with that process? Clearly, it cannot continue with its normal execution; it is missing some needed resource. We must roll back the process to some safe state and restart it from that state.
Since, in general, it is difficult to determine what a safe state is, the simplest solution is a total rollback: abort the process and then restart it. Although it is more effective to roll back the process only as far as necessary to break the deadlock, this method requires the system to keep more information about the state of all running processes.
Starvation.
How do we ensure that starvation will not occur? That is, how can we guarantee that resources will not always be preempted from the same process?
In a system where victim selection is based primarily on cost factors, it may happen that the same process is always picked as a victim. As a result, this process never completes its designated task, a starvation situation any practical system must address. Clearly, we must ensure that a process can be picked as a victim only a (small) finite number of times. The most common solution is to include the number of rollbacks in the cost factor.