MODULE 3: PROCESS SYNCHRONIZATION AND DEADLOCK
1. What is the Critical Section Problem? Explain in detail the requirements
of a solution.
Answer:
In an operating system that supports multiprogramming and multiprocessing,
several processes may execute concurrently and share common system
resources such as memory locations, files, variables, or devices. When two or
more processes access shared data simultaneously, there is a possibility of data
inconsistency. To avoid this problem, the part of a program where shared data
is accessed must be executed in a controlled manner.
The portion of a program in which a process accesses shared resources is known
as the critical section. The critical section problem is the problem of
designing a mechanism that ensures cooperative execution of processes so that
shared data is accessed safely and correctly.
Each process is logically divided into the following sections:
Entry Section: Code that requests permission to enter the critical section.
Critical Section: Code segment where shared resources are accessed.
Exit Section: Code that releases permission after executing the critical
section.
Remainder Section: All other parts of the program.
Diagram:
Entry Section → Critical Section → Exit Section → Remainder Section
A correct solution to the critical section problem must satisfy the following
three requirements:
1. Mutual Exclusion:
Mutual exclusion ensures that at most one process can be executing in its
critical section at any given time. If one process is accessing shared data,
no other process should be allowed to enter its critical section
simultaneously.
2. Progress:
If no process is currently executing in the critical section and some
processes wish to enter it, the selection of the next process to enter the
critical section must be made without indefinite delay. Only the processes
that want to enter the critical section should participate in the decision-
making.
3. Bounded Waiting:
There must be a bound on the number of times other processes can enter
their critical sections after a process has made a request to enter its own
critical section. This condition ensures fairness and prevents starvation.
2. Explain Peterson’s Solution to the Critical Section Problem in detail.
Answer:
Peterson’s solution is a classical software-based solution to the critical section
problem that works for two processes. It provides a simple and elegant method
to achieve mutual exclusion using shared variables.
Shared Variables Used:
boolean flag[2]: Indicates whether a process is interested in entering the
critical section.
int turn: Indicates whose turn it is to enter the critical section.
Initially, flag[0] = flag[1] = false, indicating that neither process wants to enter
the critical section.
Working of the Algorithm:
When a process wants to enter the critical section, it sets its corresponding flag
to true and sets the turn variable to the other process, thereby giving priority to
the other process. The process then waits until either the other process is not
interested or it is its own turn.
If both processes attempt to enter the critical section simultaneously, both flags
become true. In this case, the turn variable decides which process enters first.
The other process waits until the first process exits the critical section and resets
its flag.
Diagram:
P0 P1
flag[0] = true flag[1] = true
turn = 1 turn = 0
while(flag[1] && turn==1); while(flag[0] && turn==0);
Critical Section Critical Section
Correctness of Peterson’s Solution:
Mutual Exclusion: Only one process can enter the critical section
because the turn variable can hold only one value at a time.
Progress: A waiting process is guaranteed to proceed once the other
process leaves the critical section.
Bounded Waiting: Each process waits for at most one turn of the other
process, ensuring fairness.
Although Peterson’s solution is theoretically important, it is rarely used in
modern systems due to issues with compiler reordering and modern CPU
architectures.
3. Explain Hardware Solutions to the Critical Section Problem.
Answer:
Hardware solutions to the critical section problem rely on special atomic
instructions provided by the processor. These instructions execute indivisibly,
meaning they cannot be interrupted during execution. Hardware-based solutions
are especially useful in multiprocessor systems.
(a) Test-and-Set Instruction:
The Test-and-Set instruction checks the value of a memory location and sets it
to true in a single atomic operation.
Diagram:
while(TestAndSet(lock))
;
Critical Section
lock = false
The first process to execute Test-and-Set finds the lock free and enters the
critical section. All other processes are forced to wait until the lock is released.
(b) Swap Instruction:
The Swap instruction atomically exchanges the values of two variables. It can
also be used to implement mutual exclusion.
Advantages and Limitations:
Simple and efficient
Suitable for low-level synchronization
Can cause busy waiting and CPU wastage
4. What is a Semaphore? Explain its role in process synchronization.
Answer:
A semaphore is a high-level synchronization tool used to control access to
shared resources in concurrent systems. It is an integer variable that can be
accessed only through two atomic operations: wait() and signal().
Semaphore Operations:
wait(S): Decrements the value of the semaphore. If the value becomes
negative, the process is blocked.
signal(S): Increments the value of the semaphore and wakes up a waiting
process, if any.
Diagram:
wait(S) → Critical Section → signal(S)
Types of Semaphores:
1. Binary Semaphore: Takes values 0 or 1 and provides mutual exclusion.
2. Counting Semaphore: Takes non-negative integer values and controls
access to multiple instances of a resource.
Semaphores eliminate race conditions and ensure proper synchronization among
processes.
5. Explain the Producer–Consumer (Bounded Buffer) Problem in detail.
Answer:
The producer–consumer problem is a classical synchronization problem where
two types of processes share a common buffer. The producer generates items
and places them into the buffer, while the consumer removes items from the
buffer for processing.
The buffer has a fixed size, which introduces two possible problems:
Buffer Overflow: Producer attempts to add an item when the buffer is
full.
Buffer Underflow: Consumer attempts to remove an item when the
buffer is empty.
Semaphores Used:
empty: Counts the number of empty slots in the buffer.
full: Counts the number of filled slots.
mutex: Ensures mutual exclusion while accessing the buffer.
Diagram:
Producer → [ Shared Buffer ] → Consumer
By properly using these semaphores, the producer waits when the buffer is full,
and the consumer waits when the buffer is empty, ensuring correct
synchronization.
6. Explain the Reader–Writer Problem in detail.
Answer:
The reader–writer problem models a situation where multiple processes access
shared data, such as a database. Readers only read the data, while writers
modify it.
Rules:
Multiple readers can read simultaneously.
Writers require exclusive access.
Semaphores are used to ensure that writers are not starved and data consistency
is maintained.
Diagram:
Readers → Shared Database ← Writer
7. Explain the Dining Philosophers Problem in detail.
Answer:
The dining philosophers problem illustrates synchronization issues when
multiple processes compete for limited resources. Five philosophers sit around a
table with five chopsticks. Each philosopher needs two chopsticks to eat.
Improper allocation may lead to deadlock or starvation. Semaphores associated
with each chopstick ensure that no two neighboring philosophers eat at the same
time.
Diagram:
P0—C0—P1—C1—P2—C2—P3—C3—P4—C4—P0
8. What is Deadlock? Explain the necessary conditions for deadlock in
detail.
Answer:
Deadlock is one of the most serious problems in an operating system related to
resource management. A deadlock is a situation in which a set of processes are
permanently blocked because each process is holding at least one resource and
is waiting for another resource that is held by some other process in the same
set. Since none of the processes can proceed, the system comes to a standstill
with respect to those processes.
Deadlocks usually occur in systems where multiple processes compete for
limited resources such as CPU, memory, I/O devices, files, and semaphores.
Once a deadlock occurs, none of the involved processes can make progress
unless the operating system intervenes.
For a deadlock to occur, all four of the following necessary conditions must
hold simultaneously:
1. Mutual Exclusion:
Mutual exclusion means that at least one resource must be non-shareable.
Only one process can use the resource at any given time. If another
process requests that resource, it must wait until the resource is released.
Resources like printers, tape drives, and critical data structures are
examples of mutually exclusive resources.
2. Hold and Wait:
Under this condition, a process is holding at least one resource and is
waiting to acquire additional resources that are currently being held by
other processes. The process does not release the resources it already
holds while waiting, which increases the possibility of deadlock.
3. No Pre-emption:
No pre-emption means that resources cannot be forcibly taken away from
a process. A resource can be released only voluntarily by the process
holding it, after the process has completed its task. The operating system
cannot pre-empt the resource, which contributes to deadlock.
4. Circular Wait:
Circular wait occurs when a set of processes are waiting for each other in
a circular chain. For example, process P1 is waiting for a resource held by
P2, P2 is waiting for a resource held by P3, and P3 is waiting for a
resource held by P1. This circular dependency ensures that none of the
processes can proceed.
Diagram:
P1 → R1 → P2 → R2 → P3 → R3 → P1
If any one of these conditions is prevented, deadlock cannot occur.
9. Explain different methods of handling deadlock in detail.
Answer:
Operating systems use different strategies to deal with deadlocks depending on
system requirements, frequency of deadlock occurrence, and overhead involved.
The four major methods of handling deadlock are as follows:
1. Deadlock Prevention:
Deadlock prevention is a proactive approach in which the system is
designed in such a way that at least one of the four necessary conditions
for deadlock never holds. By carefully controlling resource allocation
policies, deadlocks can be completely prevented. However, this approach
may lead to poor resource utilization and reduced system throughput.
2. Deadlock Avoidance:
Deadlock avoidance is a dynamic approach where the system checks each
resource request carefully before granting it. The system ensures that
allocating the resource will keep the system in a safe state, where
deadlock is not possible. Banker’s Algorithm is a well-known deadlock
avoidance technique. This approach requires prior knowledge of the
maximum resource needs of processes.
3. Deadlock Detection and Recovery:
In this approach, the system allows deadlocks to occur. It periodically
checks the system for deadlock using detection algorithms such as wait-
for graphs or resource allocation matrices. Once a deadlock is detected,
recovery techniques like process termination or resource pre-emption are
applied. This method is suitable for systems where deadlocks are rare.
4. Ostrich Approach:
The ostrich approach involves ignoring the deadlock problem entirely.
This approach is used when deadlocks occur very infrequently and the
cost of prevention or avoidance is higher than the cost of dealing with
deadlock manually. Many general-purpose operating systems follow this
approach.
10. Explain Deadlock Prevention in detail.
Answer:
Deadlock prevention is a technique that ensures the system never enters a
deadlocked state by eliminating at least one of the four necessary conditions
required for deadlock. The idea is to impose restrictions on how processes
request and use resources.
The methods to prevent deadlock by eliminating each condition are as follows:
1. Eliminating Mutual Exclusion:
This condition is difficult to eliminate because many resources are
inherently non-shareable. However, for some resources such as read-only
files, sharing can be allowed, thereby reducing the chances of deadlock.
2. Eliminating Hold and Wait:
This can be achieved by forcing processes to request all required
resources at once before execution begins. Alternatively, a process must
release all held resources before requesting new ones. Although this
prevents deadlock, it may result in poor resource utilization and
starvation.
3. Eliminating No Pre-emption:
The operating system can pre-empt resources from a process that is
waiting for additional resources. The pre-empted resources can be
allocated to other processes. Later, the original process can restart and
request resources again.
4. Eliminating Circular Wait:
Circular wait can be prevented by imposing a strict ordering on resource
types. Processes must request resources only in increasing order of the
assigned numbers. This prevents the formation of circular chains.
11. Explain Banker’s Algorithm in detail.
Answer:
Banker’s Algorithm is a well-known deadlock avoidance algorithm used in
operating systems to ensure that the system never enters a deadlocked state. It
works by carefully examining each resource request before granting it and
ensures that the system remains in a safe state after allocation. The name
“Banker’s Algorithm” comes from the analogy with a banking system, where
loans are sanctioned only if the bank can satisfy the maximum possible future
demands of all customers.
The fundamental assumption of Banker’s Algorithm is that every process must
declare in advance the maximum number of instances of each resource type
it may require during its execution. Based on this information, the operating
system decides whether granting a resource request is safe or unsafe.
Data Structures Used:
1. Available Vector:
It indicates the number of available instances for each resource type in the
system.
2. Max Matrix:
It specifies the maximum demand of each process for each resource type.
3. Allocation Matrix:
It shows the number of resources of each type currently allocated to each
process.
4. Need Matrix:
It represents the remaining resource needs of each process and is
calculated as:
Need = Max – Allocation
Working of Banker’s Algorithm:
When a process requests resources, the operating system performs the following
steps:
It checks whether the requested resources are less than or equal to the
process’s remaining need.
It verifies whether the requested resources are currently available.
The system temporarily allocates the resources and performs a safety
check to see if a safe sequence exists.
A safe sequence is an order of execution of processes such that each process
can obtain its required resources and complete execution without causing
deadlock. If at least one safe sequence exists, the system is said to be in a safe
state.
If the system remains in a safe state after the tentative allocation, the request is
granted permanently. Otherwise, the request is denied, and the process must
wait.
Diagram:
Resource Request → Safety Algorithm → Safe State → Grant Request
↓
Unsafe State → Deny Request
Advantages and Limitations:
Banker’s Algorithm completely avoids deadlock.
It ensures better system reliability.
However, it requires advance knowledge of maximum resource
requirements.
It involves significant overhead due to repeated safety checks.
12. Explain Deadlock Detection and Recovery in detail.
Answer:
Deadlock detection and recovery is a strategy in which the operating system
allows deadlocks to occur and then takes action to detect and recover from
them. This approach is suitable for systems where deadlocks are infrequent and
the cost of prevention or avoidance is too high.
Deadlock Detection:
Deadlock detection involves periodically examining the state of the system to
determine whether a deadlock has occurred. The method used depends on the
type of resources:
Single-instance resources: A wait-for graph is constructed by
converting the resource allocation graph. If a cycle is present in the wait-
for graph, a deadlock exists.
Multiple-instance resources: A detection algorithm similar to Banker’s
safety algorithm is used. It checks whether processes can finish with the
currently available resources.
Deadlock detection algorithms incur overhead because they must be executed
periodically, but they allow greater flexibility in resource allocation.
Deadlock Recovery:
Once a deadlock is detected, the operating system must recover from it to
restore normal system operation. Recovery methods include:
1. Process Termination:
o Abort all deadlocked processes, which is simple but leads to loss of
work.
o Abort one process at a time until the deadlock is resolved. The
selection may depend on priority, resources held, or execution
time.
2. Resource Pre-emption:
o Temporarily take resources from selected processes.
o Allocate them to other processes to break the deadlock.
o Roll back the pre-empted process to a safe state.
Although detection and recovery provide better resource utilization, they can be
complex to implement and may affect system performance.
13. Explain Deadlock Recovery Techniques in detail.
Answer:
Deadlock recovery techniques are the methods used by the operating system to
eliminate deadlock after it has been detected. The primary goal of recovery is to
break the circular wait condition with minimal impact on system stability and
performance.
Major Deadlock Recovery Techniques:
1. Process Termination:
In this method, one or more processes involved in the deadlock are
terminated.
o Terminating all deadlocked processes is simple but wastes all the
work done by those processes.
o Terminating one process at a time allows better control but requires
repeated deadlock detection.
2. Resource Pre-emption:
Resources are forcibly taken away from one or more deadlocked
processes and reassigned to other processes.
Important issues in resource pre-emption include:
o Selecting a victim process
o Rolling back the victim to a previous safe checkpoint
o Preventing starvation by ensuring fairness
3. Rollback Mechanism:
The system periodically saves the state of processes. When deadlock
occurs, processes are rolled back to an earlier safe state and restarted.
Limitations of Deadlock Recovery:
Recovery may cause loss of computation.
Rollback requires checkpointing support.
Choosing the right process to terminate is difficult.
Despite these challenges, deadlock recovery techniques are essential for
maintaining system stability when deadlock prevention or avoidance is not
feasible.