OS (Process Synchronization)

★★Process Synchronization

Process Synchronization was introduced to handle problems that arose while multiple process
executions.

Process is categorized into two types on the basis of synchronization and these are given below:

 Independent Process

 Cooperative Process

Independent Processes: Two processes are said to be independent if the execution of one process
does not affect the execution of another process.

Cooperative Processes: Two processes are said to be cooperative if the execution of one process
affects the execution of another process. These processes need to be synchronized so that the order
of execution can be guaranteed.

☆☆Process Synchronization

It is the task phenomenon of coordinating the execution of processes in such a way that no two
processes can have access to the same shared data and resources.

 It is a procedure that is involved in order to preserve the appropriate order of execution of

cooperative processes.

 In order to synchronize the processes, there are various synchronization mechanisms.

 Process Synchronization is mainly needed in a multi-process system when multiple processes

are running together and more than one process try to gain access to the same shared
resource or any data at the same time.

☆☆Race Condition

At the time when more than one process is either executing the same code or accessing the same
memory or any shared variable; In that condition, there is a possibility that the output or the value
of the shared variable is wrong so for that purpose all the processes are doing the race to say that
my output is correct. This condition is commonly known as a race condition. As several processes
access and process the manipulations on the same data in a concurrent manner and due to which
the outcome depends on the particular order in which the access of data takes place.

Mainly this condition is a situation that may occur inside the critical section. Race condition in the
critical section happens when the result of multiple thread execution differs according to the order
in which the threads execute. But this condition is critical sections can be avoided if the critical

Md. Zahidur Rahman, Lecturer, Dept. of CSE, Comilla University Page 1

section is treated as an atomic instruction. Proper thread synchronization using locks or atomic
variables can also prevent race conditions.

★★Critical Section Problem

A Critical Section is a part of a Program (or code segment), where shared resources (like memory,
files, or variables) are accessed by multiple processes. Critical Section and has to be executed as an
atomic action. It means that in a group of cooperating processes, at a given point of time, To avoid
problems such as race conditions and data inconsistency, only one process must be executing the
critical section at a time using synchronization techniques. If any other process also wants to execute
the critical section, it must wait until the first one finishes.

The entry to the critical section is mainly handled by wait() function while the exit from the critical
section is controlled by the signal() function.

Entry Section: In this section mainly the process requests for its entry in the critical section.

Exit Section: This section is followed by the critical section.

☆☆The solution to the Critical Section Problem

A solution to the critical section problem must satisfy the following three conditions:

1. Mutual Exclusion: Out of a group of cooperating processes, only one process can be in its critical
section at a given point of time.

2. Progress: If no process is in its critical section, and if one or more threads want to execute their
critical section then any one of these threads must be allowed to get into its critical section.

3. Bounded Waiting: After a process makes a request for getting into its critical section, there is a
limit for how many other processes can get into their critical section, before this process's request is
granted. So after the limit is reached, the system must grant the process permission to get into its
critical section.

Md. Zahidur Rahman, Lecturer, Dept. of CSE, Comilla University Page 2

★★Semaphore (General Sense)

In General Sense: A system of sending message by holding the arms/flags in certain positions.

Example: Earlier used in guiding train. In modern age, it is like “traffic-lights”.

★★Semaphore (In OS)

 Semaphore (S) is a variable used to control access to a common resource by multiple processes
in multitasking operating system.

 It is used to solve the critical section problem by using two atomic operations, wait and signal
that are used for process synchronization.

The definitions of wait and signal are as follows −

 Wait: The wait operation decrements the value of its argument S, if it is positive. If S is
negative or zero, then no operation is performed. This Operation mainly helps to control the
entry of a task into the critical section. In the case of the negative or zero value, no
operation is executed.

wait(S)
{
while (S>=0);
S--;
}

 Signal: Increments the value of its argument S, as there is no more process blocked on the
queue. This Operation is mainly used to control the exit of a task from the critical section.

signal(S)
{
S++;
}

Md. Zahidur Rahman, Lecturer, Dept. of CSE, Comilla University Page 3

☆☆Types of Semaphores

There are two main types of semaphores i.e. counting semaphores and binary semaphores. Details
about these are given as follows −

 Counting Semaphores: These are integer value semaphores and have an unrestricted value
domain. These semaphores are used to coordinate the resource access, where the
semaphore count is the number of available resources. If the resources are added,
semaphore count automatically incremented and if the resources are removed, the count is
decremented.

 Binary Semaphores

The binary semaphores are like counting semaphores but their value is restricted to 0 and 1. The
wait operation only works when the semaphore is 1 and the signal operation succeeds when
semaphore is 0. It is sometimes easier to implement binary semaphores than counting semaphores.

☆☆Advantages of Semaphores

Some of the advantages of semaphores are as follows −

 Semaphores allow only one process into the critical section. They follow the mutual
exclusion principle strictly and are much more efficient than some other methods of
synchronization.

 There is no resource wastage because of busy waiting in semaphores as processor time is

not wasted unnecessarily to check if a condition is fulfilled to allow a process to access the
critical section.

 Semaphores are implemented in the machine independent code of the microkernel. So they
are machine independent.

☆☆Disadvantages of Semaphores

Some of the disadvantages of semaphores are as follows −

 Semaphores are complicated so the wait and signal operations must be implemented in the
correct order to prevent deadlocks.

 Semaphores are impractical for last scale use as their use leads to loss of modularity. This
happens because the wait and signal operations prevent the creation of a structured layout
for the system.

 Semaphores may lead to a priority inversion where low priority processes may access the
critical section first and high priority processes later.

Md. Zahidur Rahman, Lecturer, Dept. of CSE, Comilla University Page 4

★★Classical Problems of Synchronization

In this section, we present some of the classical synchronization problems. These problems are
used for testing nearly every newly proposed synchronization scheme.

We will discuss the following three problems:

1. Bounded Buffer (Producer-Consumer) Problem

2. The Readers Writers Problem

3. Dining Philosophers Problem

☆☆Bounded Buffer Problem

Because the buffer pool has a maximum size, this problem is often called the Bounded buffer
problem.

 This problem is generalized in terms of the Producer Consumer problem, where a finite
buffer pool is used to exchange messages between producer and consumer processes.

 Solution to this problem is, creating two counting semaphores "full" and "empty" to keep
track of the current number of full and empty buffers respectively.

 In this method, Producers mainly produces a product and consumers consume the product,
but both can use of one of the containers each time.

 The main complexity of this problem is that we must have to maintain the count for both
empty and full containers that are available.

☆☆The Readers Writers Problem

 In this problem there are some processes(called readers) that only read the shared data, and
never change it, and there are other processes(called writers) who may change the data in
addition to reading, or instead of reading it.

 There are various type of readers-writers problem, most centered on relative priorities of
readers and writers.

 The main complexity with this problem occurs from allowing more than one reader to access
the data at the same time.

Md. Zahidur Rahman, Lecturer, Dept. of CSE, Comilla University Page 5

☆☆Dining Philosophers Problem

 The dining philosopher's problem involves the allocation of limited resources to a group of
processes in a deadlock-free and starvation-free manner.

 There are five philosophers sitting around a table, in which there are five chopsticks/forks
kept beside them and a bowl of rice in the center, when a philosopher wants to eat, he uses
two chopsticks - one from their left and one from their right. When a philosopher wants to
think, he keeps down both chopsticks at their original place.

The possible solutions for this are:

 A philosopher must be allowed to pick up the chopsticks only if both the left and right
chopsticks are available.

 Allow only four philosophers to sit at the table. That way, if all the four philosophers pick up
four chopsticks, there will be one chopstick left on the table. So, one philosopher can start
eating and eventually, two chopsticks will be available. In this way, deadlocks can be
avoided.

Md. Zahidur Rahman, Lecturer, Dept. of CSE, Comilla University Page 6

★★Monitor in OS

Monitor in OS (operating system) is a synchronization construct that enables multiple processes or

threads to coordinate actions and ensures that they are not interfering with each other or producing
unexpected results. Also, it ensures that only one thread is executed at a critical code section.

☆☆Why are Monitors Used?

Monitors in operating systems are used to manage access to shared resources, like files or data,
among multiple processes. They ensure that only one process can use a resource simultaneously,
preventing conflicts and data corruption. Monitors simplify synchronization and protect data
integrity, making it easier for programmers to create reliable software.

They serve as "guards" for critical code sections, ensuring that no two processes can enter them
simultaneously. Monitors are like traffic lights that control access to resources, preventing crashes
and ensuring a smooth flow of data and tasks in an operating system.

☆☆Syntax and Pseudo-code of Monitor in OS

Below is the pseudo-code of the monitor in OS:

monitor monitor_name{

//declaring shared variables

variables_declaration;
condition_variables;

procedure p1(...) {
...
};

procedure p2(...){
...
};
...
procedure pn(...){
..
};

{
Initailisation Code();
}

Md. Zahidur Rahman, Lecturer, Dept. of CSE, Comilla University Page 7

In the above pseudo code, monitor_name is the name of the monitor, and p1, p2, pn are the
procedures that provide access to shared data and variables enclosed in monitors. They help ensure
that only one thread is accessed at a time for using the shared resource. This help prevents race
condition and synchronization problems.

☆☆Advantages of Monitors in OS

There are various advantages of a monitor in OS, some of which are mentioned below:

 Mutual Exclusion: It is automatic in monitors. It ensures that at a time, only one thread can
access the shared resource.

 Modularity: Monitors are helpful for encapsulating individual modules of an extensive

system, which helps in maintenance.

 Parallel programming: Monitors help in making parallel programming easy.

 Less error-prone: Monitors are less prone to errors as compared to semaphores. A

semaphore can be defined as an integer variable. It is shared among various processes.

☆☆Disadvantages of Monitors in OS

While monitors can be helpful in some situations, it also has some disadvantages. Some are listed
below:

 Difficult debugging: Debugging programs that use monitors can be tedious.

 Single process limitation: Monitors are implemented within a thread or single process. This
also means that synchronization access to shared resources is not possible across multiple
threads.

Md. Zahidur Rahman, Lecturer, Dept. of CSE, Comilla University Page 8

 OS (Deadlock)

★★System Model

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

processes. The resources are partitioned into several types, each of which consists of some number
of identical instances. Memory space, CPU cycles, files, and I/O devices (such as printers and
tape drives) are examples of resource types.

A process must request a resource before using it, and must release the resource after using it. A
process may request as many resources as it requires to carry out its designated task.

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

(Sequence of events required to use a resource)

1. Request: Process must request for a resource. If the request cannot be immediately granted
(for example, 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 line printer, the
process can print on the printer).

3. Release: The process releases the resource.

★★Resources

A resource can be hardware device (e.g., a tape drive memory) or a piece of information (e.g., a
locked record in a database). A computer will normally have many different resources that can be
acquired. Resources come in the following types:

 Preemptible Resources: Resources the OS can remove from a process (before it is

completed) and give to another process.

 Non-preemptible Resources: Resources a process must hold from when they are
allocated to when they are released.

 Shared Resource: A resource which may be used by many processes simultaneously.

 Dedicated Resource: A resource that belongs to one process only.

Md. Zahidur Rahman, Lecturer, Dept. of CSE, Comilla University Page 1

★★Deadlock Definition

A set of process is in a deadlock state when every process in the set is waiting for an event that can
be caused by another process in the set. Example: A deadlock occurs when two people start crossing
the river from opposite sides and meet in the middle.

In other words deadlock is a state where one or more processes are blocked, all waiting on
some event that will never occur.

★★Deadlock Modeling [Resource-Allocation Graph]

Deadlocks can be described more precisely in terms of a directed graph called a system
resource allocation graph. This consists of a pair G = (V, E), where V is a set of vertices and E is a set
of edges. The set of vertices is partitioned into two types P = {p1, p2, ..., pn}, the set consisting of all
the processes in the system, and R = {r1, r2, ..., rm}, the set consisting of all resource types in the
system.

An edge (pi, rj) is called a request edge, while an edge (rj, pi) is called and assignment edge.
Pictorially, we represent each process, pi as a circle and each resource type, rj as a square.
Since resource type rj may have more than one instance, we represent each such instance as a dot
within the square. The resource allocation graph in Fig. 4.3 depicts the following situation.

Md. Zahidur Rahman, Lecturer, Dept. of CSE, Comilla University Page 2

●The sets P, R and E:

 P = {p1, p2, p3}

 R = {r1, r2, r3, r4}
 E = {p1, r1), (p2, r3), (r1, p2), (r2, p2), (r2, p1), r3, p3)}

●Resource instances:

 One instance of resource type r1.

 Two instances of resource type r2.
 One instances of resource type r3.
 Two instances of resources type r4.

●Process states:

 Process p1 is holding an instance of resource type r2 and is waiting for an instance of

resource type r1.
 Process p2 is holding an instance of r1 and r2 and is waiting for an instance of
resource type r3.
 Process p3 is holding an instance of r3.

A cycle in the graph is both a necessary and sufficient condition for the existence of deadlock.
To illustrate this concept, let us return to the resource allocation graph depicted in (Fig. 4.3).
Suppose that process p3 requests an instance of resource type r2. Since no resource instance is
available, a request edge (p3, r2) is added to the graph (Fig. 4.4). At this point two minimal cycles
exist in the system.

So, Processes, p1, p2 and p3 are deadlocked. Process p2 is waiting for the resource r3, which is held
by process p3. Process p3 is waiting for either process p1 or p2 to release r2. Meanwhile,
process p2 waiting on process p3. In is Process p1 is waiting for process p2 to release resource r1.

Md. Zahidur Rahman, Lecturer, Dept. of CSE, Comilla University Page 3

★★Necessary Conditions for Deadlock [Deadlock Characterization]

Before we discuss the various methods for dealing with the deadlock problem, we shall
describe features that characterize deadlocks. Coffman (1971) showed that a deadlock situation
can arise if and only if the following four conditions hold simultaneously in a system.

1. Mutual Exclusion Condition: There exist shared resources that are used in a mutually exclusive
manner. 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.

2. Hold and Wait Condition: Processes hold onto resources they already have while waiting for the
allocation of other resources.

3. No preemption condition: Resources cannot be removed from a process until that process
releases.

4. Circular wait: A circular chain of processes exists in which each process holds resources
wanted by the next process in the chain.

★★Methods for Handling Deadlocks

Principally, we can deal with the deadlock problem in one of three ways:

1. We can use a protocol to prevent or avoid deadlocks, ensuring that the system will
never enter a deadlock state.

2. We can allow the system to enter a deadlock state, detect it, and recover.

3. We can ignore the problem altogether, and pretend that deadlocks never occur in the
system. This solution is used by most operating systems, including UNIX.

To ensure that deadlocks never occur, the system can use either a deadlock prevention or a
deadlock avoidance scheme. Deadlock prevention is a set of methods for ensuring that at least one
of the necessary conditions (*previous section) cannot hold.

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

We will discuss these schemes in further sections.

Md. Zahidur Rahman, Lecturer, Dept. of CSE, Comilla University Page 4

★★Deadlock Prevention

We know that for the occurrence of a deadlock, each of the four necessary conditions must
hold. By preventing on of the 4 necessary conditions, we can prevent the occurrence of a
deadlock.

1. Mutual Exclusion Condition: A process never needs to wait for a sharable resource. So, it is
not possible to prevent deadlocks by denying the mutual-exclusion condition.

2. Hold and Wait Condition: If we can prevent processes that hold resources from waiting for more
resources we can eliminate deadlock. One way to achieve this goal is to require all
processes to request all their resources before staring execution. If everything is available,
the process will be allocated whatever it needs and can run to completion. If one or
more resources are busy, nothing will be allocated and the process would just wait.
Advantage: It is easy to code.

3. No Preemption Condition: If we can ensure that, no preemption does not hold, we can
eliminate deadlocks.

4. Circular wait Conditions: By preventing the circular wait from occurring, we can eliminate
deadlock. For this, resources are uniquely numbered and processes can only request
resources in linear ascending order.

★★Deadlock Avoidance

Deadlock-prevention algorithms, prevent deadlocks by restraining how requests can be made. The
restraints ensure that at least one of the necessary conditions for deadlock cannot occur, and,
hence, that deadlocks cannot hold. Possible side effects of preventing deadlocks by this method,
however, are low device utilization and reduced system throughput.

An alternative method for avoiding deadlocks is to require additional information about how
resources are to be requested. This approach defines the deadlock-avoidance approach. A deadlock-
avoidance algorithm dynamically examines the resource-allocation state to ensure that a
deadlock condition can never exist. We discuss Banker’s Algorithm to avoid Deadlock.

Md. Zahidur Rahman, Lecturer, Dept. of CSE, Comilla University Page 5

☆☆Safe State and Unsafe State

A safe state is one in which it can be determined that the system can allocate resources to
each process (up to its maximum) in some order (for all pending requests) and still avoid
deadlock. A safe state is not a deadlock state. A deadlock state is an unsafe state. Not all unsafe
states are deadlocks but an unsafe state may lead to a deadlock.

The difference between a safe state and an unsafe state is that from a safe state the system can
guarantee that all processes will finish, whereas from an unsafe state, no such guarantee can be
given.

It will be more clear to illustrate safe state and unsafe state by an example.

To illustrate, we consider a system with 12 magnetic tape drives and 3 processes: P0, P1, and
P2. Process P0 requires 10 tape drives, process P1 may need as many as 4, and process P2 may
need up to 9 tape drives.

Suppose that, at time t0, process P0 is holding 5 tape drives, process P1 is holding 2, and process P3
is holding 2 tape drives. (Thus, there are 3 free tape drives.)

At time t0, the system is in a safe state. The sequence <P1, P0, P2> satisfies the safety condition,
since process P1 can immediately be allocated all its tape drives and then return them (the system
will then have 5 available tape drives), then process P0 can get all its tape drives and return them
(the system will then have 10 available tape drives), and finally process P2 could get all its tape
drives and return them (the system will then have all 12 tape drives available).

A system may go from a safe state to an unsafe state. Suppose that, at time t1, process P2 requests
and is allocated 1 more tape drive. The system is no longer in a safe state, as there are 3 free drives
and all are blocked.

Our mistake was in granting the request from process P2 for 1 more tape drive. If we had made P2
wait until either of the other processes had finished and released its resources, then we could have
avoided the deadlock.

Md. Zahidur Rahman, Lecturer, Dept. of CSE, Comilla University Page 6

★★ Banker’s Algorithm in Operating System [Deadlock Avoidance Algorithm]

The scheduling algorithm for avoiding deadlock is known as Dijkstra's banker's algorithm. It is
named so because this algorithm is used in banking systems to determine whether a loan can be
granted or not.

● Data Structures used to implement the Banker’s Algorithm

Some data structures that are used to implement the banker's algorithm are:

1. Available: It is an array of length m. It represents the number of available resources of each type.
If Available[j] = k, then there are k instances available, of resource type Rj.

2. Max: It is an n x m matrix which represents the maximum number of instances of each resource
that a process can request. If Max[i][j] = k, then the process Pi can request atmost k instances of
resource type Rj.

3. Allocation: It is an n x m matrix which represents the number of resources of each type currently
allocated to each process. If Allocation[i][j] = k, then process Pi is currently allocated k instances of
resource type Rj.

4. Need: It is a two-dimensional array. It is an n x m matrix which indicates the remaining resource

needs of each process. If Need[i][j] = k, then process Pi may need k more instances of resource type
Rj to complete its task.

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

Banker’s algorithm comprises of two algorithms:

1. Safety algorithm

2. Resource request algorithm

Md. Zahidur Rahman, Lecturer, Dept. of CSE, Comilla University Page 7

☆☆Safety Algorithm

A safety algorithm is an algorithm used to find whether or not a system is in its safe state. The
algorithm is as follows:

(1) Let Work and Finish be vectors of length m and n, respectively. Initially,

Work = Available

Finish[i] =false for i = 0, 1, ... , n - 1.

This means, initially, no process has finished and the number of available resources is represented by
the Available array.

(2) Find an index i such that both

Finish[i] ==false

Needi <= Work

If there is no such i present, then proceed to step 4.

It means, we need to find an unfinished process whose needs can be satisfied by the available
resources. If no such process exists, just go to step 4.

(3) Perform the following:

Work = Work + Allocationi

Finish[i] = true

Go to step 2.

When an unfinished process is found, then the resources are allocated and the process is marked
finished. And then, the loop is repeated to check the same for all other processes.

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

That means if all processes are finished, then the system is in safe state.

This algorithm may require an order of mxn² operations in order to determine whether a state is safe
or not.

Md. Zahidur Rahman, Lecturer, Dept. of CSE, Comilla University Page 8

☆☆Resource Request Algorithm

Now the next algorithm is a resource-request algorithm and it is mainly used to determine whether
requests can be safely granted or not.

Let Requesti be the request vector for the process Pi. If Requesti[j] == k, then process Pi wants k
instance of Resource type Rj. When a request for resources is made by the process Pi, the following
are the actions that will be taken:

1. If Requesti <= Needi, then go to step 2; else raise an error condition, since the process has
exceeded its maximum claim.

2. If Requesti <= Availablei then go to step 3; else Pi must have to wait as resources are not available.

3. Now we will assume that resources are assigned to process Pi and thus perform the following
steps:

Available = Available - Requesti;

Allocationi = Allocationi +Requesti;

Needi = Needi - Requesti;

If the resulting resource allocation state comes out to be safe, then the transaction is completed
and, process Pi is allocated its resources. But in this case, if the new state is unsafe, then Pi waits for
Requesti, and the old resource-allocation state is restored.

Reference: [Link]

Md. Zahidur Rahman, Lecturer, Dept. of CSE, Comilla University Page 9

☆☆An Illustrative Example

The content of the matrix Need is defined to be Max − Allocation and is as follows:

We claim that the system is currently in a safe state. Indeed, the sequence <P1, P3, P4, P2, P0>
satisfies the safety criteria.

Suppose now that process P1 requests one additional instance of resource type A and two instances
of resource type C, so Request1 = (1,0,2). To decide whether this request can be immediately
granted, we first check that Request1 ≤ Available—that is, that (1,0,2) ≤ (3,3,2), which is true. We
then pretend that this request has been fulfilled, and we arrive at the following new state:

We must determine whether this new system state is safe. To do so, we execute our safety
algorithm and find that the sequence <P1, P3, P4, P0, P2> satisfies the safety requirement. Hence,
we can immediately grant the request of process P1.

Extra - [You should be able to see, however, that when the system is in this state, a request for
(3,3,0) by P4 cannot be granted, since the resources are not available. Furthermore, a request for
(0,2,0) by P0 cannot be granted, even though the resources are available, since the resulting state is
unsafe.]

Md. Zahidur Rahman, Lecturer, Dept. of CSE, Comilla University Page 10

☆☆Another Example: Suppose that a system is in an unsafe state. Show that it is possible for the
processes to complete their execution without entering a deadlock state.

An unsafe state may not necessarily lead to deadlock, it just means that we cannot guarantee that
deadlock will not occur. Thus, it is possible that a system in an unsafe state may still allow all
processes to complete without deadlock occurring. Consider the situation where a system has 12
resources allocated among processes P0, P1, and P2. The resources are allocated according to the
following policy:

Currently there are two resources available. This system is in an unsafe state as process P1 could
complete, thereby freeing a total of four resources. But we cannot guarantee that processes P0 and
P2 can complete.

However, it is possible that a process may release resources before requesting any further. For
example, process P2 could release a resource, thereby increasing the total number of resources to
five. This allows process P0 to complete, which would free a total of nine resources, thereby allowing
process P2 to complete as well.

Md. Zahidur Rahman, Lecturer, Dept. of CSE, Comilla University Page 11

★★ Deadlock Detection Algorithm in Operating System

If a system does not employ either a deadlock-prevention or deadlock-avoidance algorithm, then

there are chances of occurrence of a deadlock.

In this case, the system may provide two things:

 An algorithm is used to examine the state of the system in order to determine whether a
deadlock has occurred. (Deadlock Detection)

 An algorithm that is used to recover from the deadlock. (Deadlock Recovery)

☆☆Deadlock Detection Algorithm

*** In most websites, it says that Bankers Algorithm can act as Deadlock Detection Algorithm, see
[Link]
detection-algorithm

*** As Alternative, we can prefer following discussion

1. If resources have a single instance – In this case for Deadlock detection, we can run an algorithm
to check for the cycle in the Resource Allocation Graph. The presence of a cycle in the graph is a
sufficient condition for deadlock.

In the above diagram, resource 1 and resource 2 have single instances. There is a cycle R1 → P1 → R2 → P2.
So, Deadlock is confirmed.

2. If there are multiple instances of resources – Detection of the cycle is necessary but not sufficient
condition for deadlock detection, in this case, the system may or may not be in deadlock varies
according to different situations.

Reference: [Link]

Md. Zahidur Rahman, Lecturer, Dept. of CSE, Comilla University Page 12

☆☆Deadlock Recovery

Detection is only one part of the solution of deadlock problem. After detecting deadlock with
the help of detection algorithm, what should be done next. There should be some way in
the system needed to recover from deadlock and get the system going again. There are two
ways for breaking a deadlock:

(1) Recovery through killing process.

(2) Recover through resource preemption.

(1) Recovery through killing process

For eliminating the deadlock by killing a process the following two methods can be used:

 Kill all Deadlock Processes: By killing all deadlocked processes will break the deadlock
cycle.
 Kill one process at a time until the deadlock cycle is eliminated: After each process is
killed, the other processes will be able to continue and a deadlock detection algorithm
must be involved to determine whether any processes are still deadlocked.

(2) Recover through resource preemption

The following issues are related to preemption: Selection of a Victim and Rollback

Selection of a Victim

We have to determine the resources and processes to be preempted and determine the order of
preemption cost.

Case 1: A has a higher priority than B. So, B will have to back up.

Case 2: A needs only 2 more stepping stones to cross the river (i.e. A has already used 98
stepping stones). So, B have to back up.

Case 3: A and B deadlock in the middle of the river. There are ten people behind A. So it would be
more reasonable to require B have to back up. Otherwise, eleven people will have to back up.

Rollback

The solution of a rollback is to abort the process and then restart it. Let us go through river
crossing example. If we preempt a resource from a process, it cannot continue with its normal
execution; it is missing some needed resource. So, We have to roll the process back to some
safe state and restart it from that state.

An effective solution of rollback is to place several additional stepping stones in the river, so that
one of the people involved in the deadlock may step aside to break the deadlock.

Md. Zahidur Rahman, Lecturer, Dept. of CSE, Comilla University Page 13