0

NotesNeo

Unit 2 : Inter-Process Communication and Deadlocks

Syllabus :
Inter-process Communication: Critical Section, Race Conditions, Mutual Exclusion,,
Semaphores, Event Counters, Monitors, Message Passing, Classical IPC Problems: The
Producer Consumer Problem, Reader Writer Problem, Dining Philosopher Problem etc.
Deadlocks: Definition, Necessary and sufficient conditions for Deadlock, Deadlock
Prevention, and Deadlock Avoidance: Banker’s algorithm, Deadlock detection and
Recovery.

Section 1 : Inter-Process Communication (IPC)

1.1 Process Synchronization in OS

Definition
Process synchronization in an operating system refers to the coordination of multiple
processes to ensure orderly execution and prevent conflicts when accessing shared
resources. It involves implementing mechanisms that allow processes to cooperate and
communicate effectively.

Importance
1.​ Data consistency: Synchronization ensures that shared data accessed by multiple
processes remain consistent and coherent.
2.​ Avoidance of race conditions: Race conditions occur when the outcome of a
program depends on the sequence or timing of concurrent process execution.
Synchronization mechanisms prevent race conditions by enforcing orderly access
to shared resources.
3.​ Deadlock and starvation prevention: Synchronization techniques help prevent
deadlock situations where processes are unable to proceed due to resource
contention. They also mitigate starvation, ensuring fair access to resources for all
processes.
4.​ Performance optimization: Efficient synchronization can improve system
performance by minimizing overhead and maximizing resource utilization.

Types of Processes: Independent and Cooperative Processes

1.​ Independent Processes:

●​ Independent processes operate autonomously and do not interact with each
other during execution.
1
 NotesNeo
●​ They do not share resources or communicate directly, and their execution
does not depend on other processes.
●​ Examples include standalone applications or background system tasks that
run independently of each other.
2.​ Cooperative Processes:
●​ Cooperative processes interact with each other and may share resources or
communicate to accomplish a common goal.
●​ Their execution may be influenced by the actions of other processes,
requiring synchronization to maintain order and consistency.
●​ Examples include concurrent threads within an application, client-server
interactions, or parallel processing tasks.

Need for Synchronization in Cooperative Processes

Cooperative processes often need to synchronize their actions to avoid conflicts and
ensure correct behavior. Some reasons for synchronization include:

1. Shared resources:
●​ When multiple processes access shared resources such as memory, files, or
hardware devices concurrently, synchronization is necessary to prevent data
corruption and maintain integrity.
●​ Example:
Consider a banking application with multiple concurrent transactions. If two
processes try to update the same account balance simultaneously without
synchronization, it could result in inconsistencies or incorrect balances.
Synchronization mechanisms ensure that only one process accesses the account
balance at a time, preventing such issues.

2. Communication and coordination:

●​ Cooperative processes may need to communicate and coordinate their activities to
achieve a common objective. Synchronization ensures that messages are
exchanged in the correct order and that processes wait for necessary data before
proceeding.
●​ Example:
In a distributed system, multiple processes collaborate to perform a task, such as a
group of servers handling client requests. Synchronization mechanisms ensure that
requests are processed in the order they are received and that servers coordinate
their actions to maintain system consistency and responsiveness.

3. Mutual exclusion:
●​ In scenarios where only one process should access a critical section of code or a
shared resource at a time, mutual exclusion ensures that conflicting accesses do
not occur concurrently.
●​ Example:
Consider a printer shared by multiple processes. To avoid printing conflicts, only
one process should be allowed to access the printer at any given time.
Synchronization mechanisms such as mutex locks or semaphores enforce mutual
2
 NotesNeo
exclusion, ensuring that only one process prints at a time while others wait their
turn.

1.2 Critical Section

Definition
●​ A critical section refers to the part of program where shared resources are
accessed by various cooperative processes. It is a part of the code that must be
executed atomically, meaning without interruption, to maintain data consistency
and integrity.
●​ Only one process should be allowed to execute within the critical section at any
given time to avoid inconsistencies or race conditions.
●​ Example: Consider multiple processes accessing a shared printer. The critical
section here would be the code that sends a print job to the printer. Only one
process should be allowed to access this critical section at any given time to avoid
conflicts.

Purpose
●​ The purpose of a critical section is to protect shared resources from concurrent
access by multiple processes or threads. By restricting access to the critical section
to only one entity at a time, the integrity of shared data is maintained, and race
conditions are prevented.
●​ Critical sections are essential for ensuring data consistency and avoiding conflicts
in concurrent programming environments.

Characteristics of a Critical Section

1.​ Mutual Exclusion: Only one process or thread can execute the critical section at any
given time. This ensures that conflicting accesses to shared resources do not occur
simultaneously.
2.​ Atomicity: The critical section is executed atomically, meaning it is indivisible and
uninterruptible. Once a process enters the critical section, it must complete its
execution before other processes can enter.
3.​ Limited Execution Time: The execution time of the critical section should be
relatively short to minimize the waiting time for other processes attempting to
access it. Long-running critical sections can lead to performance degradation and
potential deadlock situations.

3
 NotesNeo
4.​ Shared Resources: Critical sections typically involve accessing shared variables,
data structures, or hardware devices that are shared among multiple processes or
threads.

Critical Section Problem

The critical section problem arises when multiple processes or threads attempt to execute
critical sections concurrently, leading to potential conflicts and data inconsistencies. The
main challenges associated with the critical section problem include:
1.​ Mutual Exclusion: Ensuring that only one process can enter the critical section at a
time to prevent race conditions and data corruption.
2.​ Progress: Guaranteeing that processes do not remain indefinitely blocked from
entering the critical section, thus avoiding deadlock situations.
3.​ Bounded Waiting: Ensuring that processes waiting to enter the critical section are
not indefinitely postponed, preventing starvation and ensuring fair access to
shared resources.

1.3 Race Conditions

●​ A race condition occurs in concurrent systems when multiple processes or threads
racing to access and modify the same shared data or resources simultaneously.
●​ Since the process scheduling algorithm can swap between processes at any time,
we don’t know the order in which they’ll access the data. As a result, the outcome
depends on the process scheduling, and both processes are essentially “racing” to
modify the data.

Causes of Race Conditions:

1.​ Shared Resources: When multiple processes or threads access shared resources
such as variables, files, or memory locations concurrently, conflicts may arise.
2.​ Non-Atomic Operations: Operations that appear to be a single operation but are
implemented as multiple smaller operations can introduce race conditions. If these
operations are interleaved with operations from other processes, unexpected
results may occur.
3.​ Interrupts and Signals: In systems where asynchronous events such as interrupts
or signals can occur, they may interrupt the execution of a process at critical
points, leading to race conditions.
4.​ Thread Scheduling: The order in which threads are scheduled to execute by the
operating system scheduler can impact the outcome of concurrent execution,
potentially leading to race conditions.

Examples of Race Conditions:

1.​ Increment a Shared Variable: Multiple threads attempt to increment a shared
counter. If the increment operation is not atomic, two or more threads may read
the current value of the counter simultaneously, resulting in a lost update.
2.​ File Access: Multiple processes attempt to read from or write to the same file
concurrently. If proper synchronization mechanisms are not in place, data
corruption or inconsistencies may occur.

4
 NotesNeo
3.​ Resource Allocation: Multiple threads request access to a finite pool of resources.
Without proper locking mechanisms, two or more threads may be allocated the
same resource simultaneously, leading to resource contention or deadlock.

Impact on Program Execution:

Race conditions can have several adverse effects on program execution, including:
1.​ Data Corruption: Inconsistent or incorrect data may be produced due to conflicting
updates by concurrent processes. This can lead to data corruption, integrity
violations, or unexpected program behavior.
2.​ Deadlocks: Race conditions can sometimes result in deadlock situations where
processes become stuck waiting for resources that are held by other processes.
Deadlocks can halt program execution indefinitely and require intervention to
resolve.
3.​ Performance Degradation: Race conditions may introduce overhead and
contention as processes contend for access to shared resources. This can lead to
reduced performance and scalability, especially in multi-threaded or concurrent
systems.

Detecting Race Conditions:

1.​ Testing and Debugging: Race conditions are often detected through testing and
debugging techniques such as stress testing, code inspection, and the use of
debugging tools that can identify concurrency issues.
2.​ Static Analysis: Static analysis tools can analyze source code to detect potential
race conditions by identifying shared resources and operations that are not
properly synchronized.
3.​ Code Review: Peer code reviews can help identify race conditions by examining
code for potential concurrency issues and ensuring that proper synchronization
mechanisms are implemented.

Preventing Race Conditions:

1.​ Synchronization: Proper synchronization mechanisms such as locks, semaphores, or
mutexes can be used to ensure that only one thread or process accesses a shared
resource at a time.
2.​ Atomic Operations: Atomic operations ensure that operations on shared variables
are performed as a single, indivisible unit, preventing race conditions.
3.​ Thread Safety: Designing code to be thread-safe by minimizing shared state,
encapsulating shared resources, and using thread-safe data structures can help
prevent race conditions.
4.​ Avoiding Shared State: Reducing the reliance on shared state by using message
passing or immutable data structures can eliminate many potential race
conditions.

5
 NotesNeo

1.4 Mutual Exclusion

●​ Mutual exclusion is a synchronization technique used in concurrent programming to
ensure that only one process or thread can access a critical section of code or a
shared resource at any given time.
●​ Mutual exclusion helps prevent race conditions by ensuring that only one process
can enter the critical section at a time.
●​ Example: Mutex locks or semaphores are commonly used to achieve mutual
exclusion. When a process enters a critical section, it acquires the lock. Other
processes attempting to enter the critical section will be blocked until the lock is
released.

Requirements for Mutual Exclusion:

To achieve mutual exclusion, the following conditions must be met:
●​ No two processes can run simultaneously within their critical sections.
●​ We cannot assume anything about the relative speeds of processes.
●​ A process outside the critical section must not block another process from
accessing it.
●​ The critical section should be accessible by multiple processes within a finite
amount of time.

Approaches to Implementing Mutual Exclusion:

●​ Software Method: Processes manage mutual exclusion themselves (e.g., using flags
or semaphores). However, this approach is error-prone and has high overhead.
●​ Hardware Method: Special machine instructions (e.g., test-and-set,
compare-and-swap) provide faster mutual exclusion. But they don’t guarantee
absence of deadlock or starvation.
●​ Programming Language Method: Operating systems or programming languages
provide synchronization primitives (e.g., locks, semaphores) to enforce mutual
exclusion.

Advantages of Mutual Exclusion:

●​ Data Integrity: By preventing concurrent access to shared resources, mutual
exclusion ensures that data integrity and consistency are maintained.
●​ Synchronization: Mutual exclusion facilitates synchronization between concurrent
entities, allowing them to coordinate their actions and interactions effectively.
●​ Prevention of Deadlocks: it can also be used in conjunction with other
synchronization mechanisms to prevent deadlocks, where processes or threads are
indefinitely blocked due to circular dependencies.

1.5 Synchronization Mechanisms

Synchronization mechanisms are essential in concurrent programming to ensure that
multiple threads or processes coordinate their actions correctly.

6
 NotesNeo

1.​ Locks and Mutexes:

●​ Locks (short for “mutual exclusion”) are used to protect shared resources
from concurrent access. A thread acquires a lock before accessing a critical
section and releases it afterward.
●​ Mutexes (short for “mutual exclusion objects”) are similar to locks but can be
system-wide or named, allowing synchronization across processes.
2.​ Semaphores:
●​ Semaphores are integer variables used to control access to shared
resources. They maintain a count and allow a specified number of threads to
access a resource concurrently.
●​ Binary semaphores (with values 0 or 1) act as locks, while counting
semaphores allow a specific number of threads to access a resource
simultaneously.
3.​ Condition Variables:
●​ Condition variables allow threads to wait for a specific condition to be met
before proceeding. They are often used with locks to implement
producer-consumer patterns or other synchronization scenarios.
●​ Common operations include wait, signal, and broadcast.
4.​ Barriers:
●​ Barriers synchronize a group of threads by ensuring that they all reach a
specific point before continuing. They are useful for parallelizing tasks with
dependencies.
●​ Examples include cyclic barriers and countdown latches.
5.​ Read-Write Locks:
●​ Read-write locks allow multiple threads to read a shared resource
simultaneously but ensure exclusive access during writes.
●​ They improve performance by allowing concurrent reads while maintaining
data consistency.
6.​ Atomic Operations:
●​ Atomic operations (e.g., compare-and-swap, fetch-and-add) provide
low-level synchronization without explicit locks.
●​ They guarantee that certain operations occur atomically, preventing race
conditions.
7.​ Monitors:
●​ Monitors are a higher-level synchronization construct that encapsulates
shared data and the operations that can be performed on it.
●​ Monitors provide mutual exclusion automatically, ensuring that only one
thread can execute within the monitor at a time. They also typically include
condition variables for thread signaling within the monitor.

1.6 Semaphores
●​ Semaphore is a synchronization primitive variable that controls access to a shared
resource and coordinate the execution of multiple processes or threads.
●​ It was introduced by Edsger Dijkstra in the 1960s and is widely used in operating
systems and multi-threaded applications.

7
 NotesNeo
●​ It acts as a hardware solution to the critical section problem, which involves
ensuring that only one process can enter a critical section at a time. The critical
section problem arises when multiple processes share variables and need to access
them in a coordinated manner.

Operations:
●​ Semaphores maintain an integer value that can be modified by two fundamental
operations: wait (also known as P or down operation) and signal (also known as V
or up operation).
1.​ Wait (P) Operation: This operation decrements the semaphore value. If the
semaphore value becomes negative, the process waits until it becomes
positive.
2.​ Signal (V) Operation: This operation increments the semaphore value. If
there are waiting processes, one of them is allowed to proceed.

Types of Semaphores:
1.​ Binary Semaphore: Can take only two values (0 or 1). Used for mutual exclusion
(e.g., ensuring only one process accesses a resource at a time).
2.​ Counting Semaphore: Can take any non-negative integer value. Used for
scenarios where multiple processes can access a resource up to a certain limit.

Advantages:
1.​ Synchronization: Semaphores ensure orderly access to shared resources,
preventing conflicts.
2.​ Deadlock Prevention: Properly designed semaphores can prevent deadlocks.
3.​ Process Coordination: Semaphores allow processes to coordinate their actions.

1. Binary Semaphores:
●​ Also known as mutex (mutual exclusion) or simply a lock, a binary semaphore can
take on only two values: 0 and 1. It is typically used to control access to a single
resource, allowing only one thread or process to access it at a time.
●​ Binary semaphores are often used to implement critical sections and ensure mutual
exclusion.

2. Counting Semaphores:
●​ Unlike binary semaphores, counting semaphores can take on multiple non-negative
integer values. They are used to control access to a finite number of identical
resources.
●​ Counting semaphores are commonly employed to limit the number of concurrent
accesses to a shared resource, such as a fixed-size buffer or a pool of worker
threads.

1.7 Event Counters

●​ An event counter is a synchronization primitive used in concurrent programming to
track the occurrence of events or the availability of resources. It maintains an

8
 NotesNeo
integer value representing the count of events or the number of available
resources. It is used to coordinate synchronization among processes, especially in
scenarios where a fixed number of resources are available.
●​ Example: Suppose a system has a limited number of network connections. An event
counter keeps track of the available connections. Processes requesting a
connection decrement the counter, and when the counter reaches zero, further
requests are blocked until connections are released.

Purpose and Functionality

The primary purpose of an event counter is to provide a mechanism for coordinating the
execution of processes or threads and managing access to shared resources. Event
counters serve several key functions:
1.​ Counting Events: Event counters keep track of the number of events that have
occurred in a system. Events can include signals, notifications, or other significant
occurrences that processes or threads need to react to.
2.​ Managing Resources: Event counters can also be used to manage the availability of
resources in a system. The counter's value indicates the number of resources that
are currently available for use by processes or threads.
3.​ Synchronization: Event counters provide a means of synchronizing the execution of
processes or threads based on the occurrence of events or the availability of
resources. Processes or threads can wait for events to occur or for resources to
become available by monitoring the value of the event counter.
4.​ Blocking and Unblocking: Processes or threads can block (suspend their execution)
or unblock (resume their execution) based on the state of the event counter. When
the counter's value reaches a certain threshold or condition, processes or threads
waiting for the event can be unblocked and allowed to proceed.

Use Cases and Examples

Event counters are commonly used in various scenarios and applications where
event-driven or resource-based synchronization is required. Some use cases and examples
include:
1.​ Concurrency Control: Event counters can be used to manage access to a finite pool
of resources, such as network connections, database connections, or memory
buffers. Processes or threads can acquire resources by decrementing the counter
and release them by incrementing the counter when finished.
2.​ Task Synchronization: Event counters are used to coordinate the execution of tasks
or processes in systems with multiple concurrent activities. Processes or threads
can wait for specific events or conditions to occur before proceeding with their
execution.
3.​ Message Passing: Event counters are often used in message passing systems to
signal the arrival of messages or events. Processes or threads can wait for
messages to be received by monitoring the value of the event counter associated
with the message queue.
4.​ Parallel Computing: In parallel computing environments, event counters are used to
synchronize the execution of parallel tasks or threads. Processes or threads can

9
 NotesNeo
wait for all tasks to complete by monitoring the value of the event counter
representing the number of tasks remaining.

1.8 Monitors
●​ A monitor is a high-level synchronization construct used in concurrent
programming to encapsulate shared data and the operations performed on that
data within a single programming language construct.
●​ The concept of monitors was introduced by Per Brinch Hansen in the 1970s.

Purpose:
Monitors manage access to shared resources (such as files or data) among multiple
processes. They ensure that only one process can use a resource at a time, preventing
conflicts and data corruption.

Implementation:
Monitors are typically implemented as programming language constructs, often in
object-oriented languages. They encapsulate a shared resource and provide access
through a set of procedures. These procedures ensure that only one process accesses the
resource simultaneously, while others wait until it becomes available.

Features:
1.​ Mutual Exclusion: Monitors enforce mutual exclusion, allowing only one process
inside the monitor at any given time.
2.​ Condition Variables: Monitors include condition variables and procedures.
Processes can wait on condition variables (using wait()) and signal other processes
(using signal()) when a condition is met.
3.​ Data Encapsulation: Monitors encapsulate shared resources and relevant
procedures, making synchronization easier to reason about.
4.​ Abstraction: Monitors hide low-level synchronization details, such as semaphores or
locks, simplifying concurrent program implementation.

Limitations:
1.​ Monitors may be less efficient than lower-level primitives due to their higher-level
abstraction.
2.​ Not suitable for all synchronization problems; sometimes lower-level primitives are
needed for optimal performance.

1.9 Inter-Process Communication (IPC)

●​ Inter-Process Communication (IPC) refers to the mechanisms provided by the
operating system to facilitate communication and synchronization between
different processes in a multi-process environment.
●​ IPC is crucial for enabling cooperation and coordination among processes running
concurrently on a computer system.

10
 NotesNeo
●​ Inter-process communication involves exchanging information between multiple
threads within one or more processes or programs.

Importance
IPC is crucial for enabling cooperation and coordination among processes running
concurrently on a computer system. Some key reasons why IPC is important include:
1.​ Cooperation: IPC enables processes to work together towards common goals by
exchanging information, coordinating actions, and synchronizing their activities.
This cooperation is essential for implementing complex systems and distributed
applications.
2.​ Resource Sharing: IPC allows processes to share resources such as data, files,
memory, and hardware devices. This enables efficient resource utilization and
improves system scalability.
3.​ Concurrency: IPC facilitates communication and synchronization between
concurrent processes or threads, allowing them to interact without interfering with
each other's execution. This is particularly important in multi-threaded and
multi-core systems where concurrency is prevalent.
4.​ Fault Isolation: IPC provides mechanisms for isolating and containing faults within
individual processes. By separating processes and enforcing boundaries between
them, IPC helps prevent errors and failures from spreading to other parts of the
system.

Types of IPC Mechanisms

There are several IPC mechanisms provided by operating systems to facilitate
communication and synchronization between processes. Some common types of IPC
mechanisms include:
1.​ Pipes: Pipes are unidirectional data channels used for communication between
processes. They allow data to be transmitted from one process to another in a
sequential manner. Pipes can be used for both input and output operations and are
commonly used in POSIX and Windows systems.
2.​ Shared Memory: Shared memory is a memory region that can be accessed by
multiple processes simultaneously. It enables efficient communication and data
exchange between processes by allowing them to read and write to shared
memory locations. Shared memory is widely used in both POSIX and Windows
operating systems.
3.​ Message Queues: Message queues allow multiple processes to send and receive
messages asynchronously. Messages remain in the queue until they are retrieved
by their recipients, allowing processes to communicate in a loosely coupled manner.
Message queues are utilized by all operating systems for IPC.
4.​ Sockets: Sockets provide a bidirectional communication channel between
processes over a network. They allow processes running on different computers to
exchange data and messages, enabling distributed communication and
collaboration.

11
 NotesNeo
Relationship with Process Synchronization
Process synchronization and IPC are closely related concepts that address different
aspects of concurrent programming.
●​ Process synchronization focuses on coordinating the execution of concurrent
processes or threads within a single system, ensuring that they access shared
resources in a mutually exclusive and orderly manner. IPC, on the other hand, deals
with communication and data exchange between processes, enabling them to
cooperate and coordinate their activities.
●​ While process synchronization mechanisms such as locks, semaphores, and
monitors ensure orderly access to shared resources, IPC mechanisms such as pipes,
shared memory, and message queues facilitate communication and data exchange
between processes. Together, process synchronization and IPC enable the
development of robust, scalable, and efficient concurrent systems and applications.

1.10 Message Passing

●​ Message passing is a mechanism of inter-process communication (IPC) where
processes communicate and synchronize their actions by sending and receiving
messages.
●​ In message passing systems, processes interact by exchanging messages rather
than directly accessing shared memory or resources.
●​ The purpose of message passing is to facilitate communication, synchronization,
and coordination between processes running concurrently on a computer system.
●​ Example: In a distributed system, processes communicate over a network by
sending and receiving messages. Each process can send messages to other
processes, enabling communication and coordination.

How it works:
●​ Processes send and receive messages to coordinate activities and exchange data.
●​ Communication Channels are established between processes, which can be either
direct or indirect.
●​ Synchronous Message Passing: The sender process waits until the receiver has
received the message. This ensures a tight coupling between processes but can
lead to delays if the receiver is slow or unavailable.
●​ Asynchronous Message Passing: The sender continues its execution without waiting
for the message to be received. This allows for concurrent execution and is more
flexible but requires mechanisms to handle message queues and potential
communication delays.

Key aspects of message passing include:

1.​ Asynchronous Communication: Message passing allows processes to communicate
asynchronously, meaning that processes can send and receive messages
independently of each other's execution. This asynchronous communication
enables decoupling between sender and receiver processes, allowing them to
operate independently and asynchronously.

12
 NotesNeo
2.​ Isolation and Encapsulation: Message passing promotes encapsulation and data
hiding by providing a mechanism for processes to communicate in a modular and
isolated manner. Processes communicate through well-defined interfaces (message
formats), which helps maintain modularity and encapsulation in the system.
3.​ Concurrency and Parallelism: Message passing supports concurrency and
parallelism by enabling processes to communicate and synchronize their actions in
a distributed or parallel computing environment. Processes can communicate and
exchange messages concurrently, allowing for efficient utilization of resources and
scalability.

Implementation and Usage

Message passing can be implemented using various techniques and mechanisms,
depending on the underlying operating system, programming language, and
communication model. Some common implementations of message passing include:
1.​ Direct Message Passing: In direct message passing, processes communicate
directly with each other using explicit message send and receive operations. This
can be implemented using system calls or language-specific constructs for
inter-process communication.
2.​ Indirect Message Passing: In indirect message passing, processes communicate
through intermediary entities such as message queues, mailboxes, or
communication channels. Processes send messages to a shared communication
channel or mailbox, from which they are retrieved by the recipient processes.
3.​ Remote Procedure Calls (RPC): RPC is a form of message passing where processes
invoke procedures or functions on remote processes located on different
computers or network nodes. RPC hides the details of message passing and
communication protocols, allowing processes to interact as if they were local.

Examples of Message Passing Systems

Some examples of message passing systems and frameworks include:
1.​ MPI (Message Passing Interface): MPI is a standardized and widely used message
passing library for parallel computing. It provides a set of functions and routines
for sending and receiving messages between processes in distributed memory
systems.
2.​ ZeroMQ: ZeroMQ is a lightweight and high-performance messaging library that
provides sockets-based message passing for distributed and concurrent
applications. It supports various messaging patterns, including request-reply,
publish-subscribe, and pipeline.
3.​ Java Message Service (JMS): JMS is a Java-based messaging API that provides a
standardized way for Java applications to send and receive messages
asynchronously. It supports both point-to-point and publish-subscribe messaging
models and is commonly used in enterprise messaging systems.
4.​ AMQP (Advanced Message Queuing Protocol): AMQP is an open standard for
message-oriented middleware that defines a protocol for message passing
between applications. It is widely used in distributed systems and cloud-based
messaging architectures.

13
 NotesNeo

Section 2 : Classical IPC Problems

Inter-Process Communication (IPC) problems refer to a set of challenges that arise in
concurrent programming when multiple processes or threads need to communicate,
coordinate, and synchronize their actions to achieve a common goal.
In computer science, several classical Inter-Process Communication (IPC) problems serve
as fundamental examples to illustrate synchronization challenges and solutions in
concurrent programming. Three well-known IPC problems are:
1.​ The Producer-Consumer Problem
2.​ The Reader-Writer Problem
3.​ The Dining Philosophers Problem

1. The Producer-Consumer Problem

●​ The Producer-Consumer Problem is a classical synchronization problem in
concurrent programming. It involves two types of processes, known as producers
and consumers sharing a common fixed-size buffer or queue. Producers generate
data items and add (produce) them to the buffer, while consumers retrieve and
process (consume) these items.
●​ The challenge is to ensure proper synchronization between producers and
consumers to prevent issues such as buffer overflow or underflow. The producers
should not produce items if the buffer is full and the consumers should not consume
items if the buffer is empty.

Description of the Problem:

1.​ Roles of Producers and Consumers:
●​ Producers: Generate data items and add them to the buffer.
●​ Consumers: Retrieve data items from the buffer and process them.
2.​ Shared Buffer/Queue:
●​ Acts as a shared resource between producers and consumers.
●​ Typically, it has a fixed size and is implemented as a bounded buffer.
3.​ Assumptions:
●​ Multiple producers and consumers operate concurrently.
●​ Producers generate data items at varying rates, and consumers process
items at their own pace.
●​ The buffer has limited capacity.
●​ Producers must wait if the buffer is full, and consumers must wait if the
buffer is empty.
●​ Access to the buffer needs to be exclusive to prevent data corruption.

14
 NotesNeo
Key Challenges:
1.​ Buffer Synchronization: Ensuring proper management of the shared buffer to
prevent issues such as buffer overflow or underflow.
2.​ Mutual Exclusion: Ensuring that only one process (producer or consumer) accesses
the buffer at a time to prevent data corruption.

Solution Approaches

1.​ Using Semaphores:

●​ Employ binary semaphores to control access to the buffer and track the
number of available slots.
●​ Use two semaphores: one for tracking empty slots and another for tracking
filled slots.
●​ Producers increment the empty semaphore when adding items and
decrement the filled semaphore.
●​ Consumers increment the filled semaphore when removing items and
decrement the empty semaphore.
2.​ Using Monitors:
●​ Encapsulate the buffer and synchronization logic within a monitor.
●​ Define monitor procedures for adding and removing items from the buffer.
●​ Ensure mutual exclusion by allowing only one producer or consumer to
access the buffer at a time.
3.​ Using Condition Variables:
●​ Employ condition variables to signal when the buffer is full or empty.
●​ Producers wait on the condition variable for empty slots if the buffer is full.
●​ Consumers wait on the condition variable for filled slots if the buffer is
empty.

Solution/Implementation using Semaphores

To solve the Producer-Consumer problem three semaphores variable are used :
1.​ Full: The full variable is used to track the space filled in the buffer by the Producer
process. It is initialized to 0 initially as initially no space is filled by the Producer
process.
2.​ Empty: The Empty variable is used to track the empty space in the buffer. The
Empty variable is initially initialized to the BUFFER-SIZE as initially, the whole
buffer is empty.
3.​ Mutex: Mutex is used to achieve mutual exclusion. Mutex ensures that at any
particular time only the producer or the consumer is accessing the buffer. Mutex is
a binary semaphore variable that has a value of 0 or 1.

We will use the Signal() and wait() operation in the above-mentioned semaphores to
arrive at a solution to the Producer-Consumer problem.
Signal() - The signal function increases the semaphore value by 1.
Wait() - The wait operation decreases the semaphore value by 1.

Let's look at the code of Producer-Consumer Process

15
 NotesNeo
Producer Process:
void Producer(){
while(true){
// producer produces an item/data
wait(Empty); // Waits for space in the buffer
wait(mutex); // Enters critical section
add(); // Adds item to the buffer
signal(mutex); // Exits critical section
signal(Full); // Indicates buffer is no longer empty
}
}

Let's understand the above Producer process code :

1.​ wait(Empty) - Before producing items, the producer process checks for the empty
space in the buffer. If the buffer is full producer process waits for the consumer
process to consume items from the buffer. so, the producer process executes
wait(Empty) before producing any item.
2.​ wait(mutex) - Only one process can access the buffer at a time. So, once the
producer process enters into the critical section of the code it decreases the value
of mutex by executing wait(mutex) so that no other process can access the buffer
at the same time.
3.​ add() - This method adds the item to the buffer produced by the Producer process.
once the Producer process reaches add function in the code, it is guaranteed that
no other process will be able to access the shared buffer concurrently which helps
in data consistency.
4.​ signal(mutex) - Now, once the Producer process added the item into the buffer it
increases the mutex value by 1 so that other processes which were in a
busy-waiting state can access the critical section.
5.​ signal(Full) - when the producer process adds an item into the buffer spaces is filled
by one item so it increases the Full semaphore so that it indicates the filled spaces
in the buffer correctly.

Consumer Process:
void Consumer() {
while(true){
// consumer consumes an item
wait(Full); // Waits for an item in the buffer
wait(mutex); // Enters critical section
consume(); // Consumes item from the buffer
signal(mutex);// Exits critical section
signal(Empty);// Indicates buffer is no longer full
}
}

Let's understand the above Consumer process code :

16
 NotesNeo
1.​ wait(Full) - Before the consumer process starts consuming any item from the buffer
it checks if the buffer is empty or has some item in it. So, the consumer process
creates one more empty space in the buffer and this is indicated by the full
variable. The value of the full variable decreases by one when the wait(Full) is
executed. If the Full variable is already zero i.e the buffer is empty then the
consumer process cannot consume any item from the buffer and it goes in the
busy-waiting state.
2.​ wait(mutex) - It does the same as explained in the producer process. It decreases
the mutex by 1 and restricts another process to enter the critical section until the
consumer process increases the value of mutex by 1.
3.​ consume() - This function consumes an item from the buffer. when code reaches the
consuming () function it will not allow any other process to access the critical
section which maintains the data consistency.
4.​ signal(mutex) - After consuming the item it increases the mutex value by 1 so that
other processes which are in a busy-waiting state can access the critical section
now.
5.​ signal(Empty) - when a consumer process consumes an item it increases the value
of the Empty variable indicating that the empty space in the buffer is increased by

This solution ensures mutual exclusion to prevent multiple processes from accessing the
buffer simultaneously, and it also ensures that producers wait if the buffer is full and
consumers wait if the buffer is empty, achieving synchronization between the two
processes.

2. The Reader-Writer Problem

●​ The Reader-Writer Problem is a classic synchronization problem in operating
systems and concurrent programming. In this problem, there are two types of
processes: readers and writers. Multiple readers can read simultaneously from a
shared resource (such as a file or database), but only one writer can write to the
resource at a time.
●​ The goal of solving the readers-writers problem is to design a synchronization
mechanism that allows multiple readers to access the data set simultaneously.
However, when a writer is accessing the data set for writing, no other reader or
writer should be allowed to access it simultaneously.

17
 NotesNeo

Description of the Problem:

1.​ Readers and Writers:
●​ Readers: Readers can only read from the data set. They do not perform
updates.
●​ Writers: Writers can both read and write to the data set. They have the
potential to modify the shared resource.
2.​ Shared Resource:
●​ Represents the data structure or resource that readers and writers access.
●​ Examples include files, databases, or any shared data structure.
3.​ Assumptions:
●​ Readers can access the resource simultaneously for reading.
●​ Writers need exclusive access to the resource for writing.
●​ Readers and writers may arrive at different times and frequencies.
●​ Data integrity must be maintained, and readers should not see partially
written data.

Key Challenges:
1.​ Read Access vs. Write Access:
●​ Readers can access the resource concurrently, but writers need exclusive
access to prevent data corruption.
●​ Readers should not be allowed to access the resource while a writer is
writing.
2.​ Data Consistency:
●​ Ensuring that readers see consistent data even if writers are actively writing
to the resource.
●​ Preventing issues such as data corruption or inconsistencies.:

Example:
Consider a scenario where multiple readers and writers want to access a shared file
simultaneously. We can analyze different cases to determine whether access should be
allowed or not:

18
 NotesNeo

Case Process 1 Process 2 Allowed / Not Allowed

Case 1 Writing Writing Not Allowed

Case 2 Reading Writing Not Allowed

Case 3 Writing Reading Not Allowed

Case 4 Reading Reading Allowed

Explanation of Cases:
1.​ Case 1 (Writing-Writing): If two or more writers attempt to access the file
simultaneously, only one is allowed while others are blocked.
2.​ Case 2 (Reading-Writing): When a writer is writing, readers are blocked to maintain
data consistency.
3.​ Case 3 (Writing-Reading): Similarly, when a writer is writing, other readers are
blocked to prevent inconsistencies.
4.​ Case 4 (Reading-Reading): Multiple readers are allowed to access the file
simultaneously as long as no writer is writing.

Solution Approaches

1.​ Using Semaphores:

●​ Employ semaphores to control access to the shared resource.
●​ Maintain separate semaphores for readers and writers to track their access.
●​ Allow multiple readers to acquire the semaphore for reading while blocking
writers.
●​ Allow only one writer to acquire the semaphore for writing, blocking all other
readers and writers.
2.​ Using Monitors:
●​ Encapsulate the shared resource and synchronization logic within a monitor.
●​ Define monitor procedures for readers to read and writers to write.
●​ Ensure mutual exclusion between readers and writers to prevent concurrent
access.
●​ Allow readers to enter the monitor concurrently but block writers while
readers are active.
3.​ Using Readers-Writers (RW) Locks:
●​ Implement specialized locks, such as readers-writers locks, designed for this
problem.
●​ Readers-writers locks allow multiple readers to acquire the lock
simultaneously.
●​ Writers acquire an exclusive lock, blocking all other readers and writers until
the write operation completes.

19
 NotesNeo
Solution/Implementation using Semaphores
The readers-writers problem involves managing access to a shared resource, such as a
file, by multiple processes concurrently. To solve this problem, binary semaphores can be
employed. Binary semaphores are synchronization primitives that allow only two possible
values: 0 and 1.
Binary Semaphore Operations:
1.​ wait(S): If the value of semaphore S is 0, the process executing this operation will
wait until it becomes 1. If the value is already 1, the operation decrements the
value of S by 1.
2.​ signal(S): This operation increments the value of semaphore S by 1.

Reader Process:
●​ Initialize a semaphore mutex and a variable readcount to manage access.
●​ Upon entering the critical section:
●​ Wait on the mutex semaphore to ensure mutual exclusion.
●​ Increment readcount to indicate a reader is accessing the resource.
●​ If readcount is 1 (i.e., the first reader), wait on the write semaphore to
prevent writers from accessing.
●​ Release the mutex semaphore.
●​ Perform reading operations.
●​ Upon exiting the critical section:
●​ Wait on the mutex semaphore.
●​ Decrement readcount.
●​ If readcount becomes 0 (i.e., no readers), signal the write semaphore to
allow writers to access.
●​ Release the mutex semaphore.

Reader Process Code:

static int readcount = 0;

wait(mutex);
readcount++; // Increment readcount on entry
if (readcount == 1) {
wait(write); // Lock write if first reader
}
signal(mutex);

// --Read the file

wait(mutex);
readcount--; // Decrement readcount on exit
if (readcount == 0) {
signal(write); // Unlock write if last reader
}
signal(mutex);

20
 NotesNeo
Writer Process:
●​ Wait on the write semaphore to ensure mutual exclusion for writing operations.
●​ Perform writing operations on the shared resource.
●​ Signal the write semaphore to release access to the resource.

Writer Process Code:

wait(write); // Lock write for writing
// --Write into the file
signal(write); // Unlock write after writing

Proof of Each Case:

1.​ Case 1 Proof: If one writer is writing, no other writer is allowed due to the binary
semaphore write.
2.​ Case 2 Proof: When a reader is reading, the write semaphore prevents writers from
accessing the file.
3.​ Case 3 Proof: When a writer is writing, the write semaphore blocks readers from
accessing the file.
4.​ Case 4 Proof: Multiple readers are allowed to access the file simultaneously as the
write semaphore is not decremented by readers.

CASE 1: WRITING - WRITING (Not Allowed)

●​ Initial State: Semaphore write is set to 1.
●​ Suppose two processes, P0 and P1, both attempt to write simultaneously.
●​ P0 enters the writer code first and decrements write to 0.
●​ When P1 attempts to write, it enters an infinite loop because write is already 0.
●​ Thus, only one writer can write at a time.

CASE 2: READING - WRITING (Not Allowed)

●​ Initial State: Semaphore mutex is set to 1 and readcount is 0.
●​ Suppose processes P0 (reader) and P1 (writer) are present.
●​ When P0 starts reading, it locks mutex and increments readcount.
●​ As readcount is 1, P0 locks write, preventing P1 from writing.
●​ P1, attempting to write, enters an infinite loop because write is already 0.
●​ Thus, reading and writing are mutually exclusive.

CASE 3: WRITING - READING (Not Allowed)

●​ Initial State: Semaphore write is set to 1.
●​ Suppose processes P0 (writer) and P1 (reader) are present.
●​ When P0 starts writing, it locks write and prevents P1 from reading.
●​ P1, attempting to read, is unable to proceed as write is already 0.
●​ Thus, writing prevents reading.

CASE 4: READING - READING (Allowed)

●​ Initial State: Semaphore mutex is set to 1 and readcount is 0.
●​ Suppose processes P0, P1, and P2 are readers.

21
 NotesNeo
●​ Each reader, upon entry, increments readcount.
●​ All readers can concurrently read as mutex allows access.
●​ When a writer arrives, it blocks all readers by setting write to 0.
●​ Upon completion of reading, readers decrement readcount.
●​ When readcount becomes 0, the writer is allowed to write.

3. The Dining-Philosophers Problem

●​ The Dining Philosophers Problem is a classic synchronization problem in concurrent
programming, first introduced by Edsger Dijkstra in 1965.
●​ In this problem, there are several philosophers seated around a dining table. Each
philosopher alternates between thinking and eating.
●​ Each philosopher requires two chopsticks to eat — one for the left hand and one for
the right hand, and the chopsticks must be shared among adjacent philosophers.
●​ The challenge is to prevent deadlock, where each philosopher holds one fork and
waits indefinitely for the other fork, unable to proceed.

Five Philosophers sitting around the table

●​ Five philosophers (P0, P1, P2, P3, and P4) seated around a circular table.
●​ A bowl of noodles is placed at the center.
●​ Each philosopher has two chopsticks (C0, C1, C2, C3, C4), one to their left and one
to their right.

22
 NotesNeo

Description of the Problem:

1.​ Philosophers and Chopsticks:
●​ Philosophers: Represent individual processes or threads.
●​ Chopsticks: Resources needed by philosophers to eat. Each philosopher
requires two chopsticks, one on their left and one on their right.
2.​ Shared Resources:
●​ Chopsticks: Shared among adjacent philosophers.
●​ Bowl of Noodles: Represent the shared resource that philosophers need
access to in order to eat.
3.​ Rules:
●​ A philosopher may only eat if they can acquire both the left and right
chopsticks.
●​ If a philosopher cannot acquire both chopsticks, they must continue
thinking.
●​ Chopsticks can only be held by one philosopher at a time.
4.​ Assumptions:
●​ Each philosopher spends time thinking and time eating, alternating between
the two activities.
●​ A philosopher requires both chopsticks to eat but does not require any
chopsticks to think.
●​ Chopsticks must be shared among adjacent philosophers and cannot be
used simultaneously by multiple philosophers.
●​ Philosophers must avoid deadlock (where each philosopher holds one
chopstick and waits indefinitely for the other) and starvation (where a
philosopher never gets a chance to eat).

Key Challenges:
1.​ Deadlock Prevention:

23
 NotesNeo
●​ Ensure that the philosophers cannot reach a state where each philosopher
holds one chopstick and waits indefinitely for the other.
2.​ Starvation Avoidance:
●​ Design a solution that prevents any philosopher from being indefinitely
prevented from accessing the shared resource (bowl of noodles).

Solution Approaches

1. Using Semaphores:
●​ Employ binary semaphores to represent the availability of each chopstick.
●​ Each chopstick is associated with a semaphore, and philosophers must acquire
both semaphores (chopsticks) to eat.
●​ Implement logic to handle the potential for deadlock, such as enforcing a
maximum number of philosophers allowed to pick up chopsticks simultaneously.

2. Using Monitors:
●​ Encapsulate the dining table and chopsticks within a monitor.
●​ Define monitor procedures for picking up and releasing chopsticks, ensuring
mutual exclusion.
●​ Implement a mechanism to detect and prevent deadlocks, such as allowing
philosophers to pick up both chopsticks only if both are available simultaneously.

3 Using Resource Allocation Strategies:

●​ Implement resource allocation algorithms to manage the allocation of chopsticks
to philosophers.
●​ Use techniques such as banker's algorithm or resource hierarchy to prevent
deadlock and ensure fair access to chopsticks.
●​ Monitor the state of each philosopher and chopstick to dynamically adjust resource
allocation and avoid deadlocks.

Implementation/Solution using Semaphores

// Define semaphores
Semaphore chopstick[5] = {1, 1, 1, 1, 1}; // One semaphore per chopstick,
initialized to 1

// Philosopher process
void philosopher(int id) {
while (true) {
think(); // Philosopher is thinking
take_chopsticks(id); // Philosopher tries to pick up chopsticks
eat(); // Philosopher is eating
put_chopsticks(id); // Philosopher puts down chopsticks
}
}

// Function to pick up chopsticks

24
 NotesNeo
void take_chopsticks(int id) {
wait(chopstick[id]); // Wait for left chopstick
wait(chopstick[(id + 1) % 5]); // Wait for right chopstick
}

// Function to put down chopsticks

void put_chopsticks(int id) {
signal(chopstick[id]); // Put down left chopstick
signal(chopstick[(id + 1) % 5]); // Put down right chopstick
}

Explanation:
●​ Each philosopher is represented by a process, and there are five philosophers (0 to
4).
●​ The philosopher function represents the main behavior of a philosopher, where they
alternate between thinking, picking up chopsticks, eating, and putting down
chopsticks.
●​ think() represents the philosopher's thinking state.
●​ take_chopsticks(id) and put_chopsticks(id) represent the actions of picking up and
putting down chopsticks, respectively.
●​ In take_chopsticks(id), a philosopher tries to acquire both the left and right
chopsticks by waiting on the corresponding semaphores. The modulo operation (id
+ 1) % 5 ensures that the philosopher wraps around the table to pick up the right
chopstick for philosopher 4.
●​ In put_chopsticks(id), the philosopher releases both chopsticks by signaling the
corresponding semaphores.
●​ Each chopstick is represented by a semaphore initialized to 1, indicating
availability. When a philosopher picks up a chopstick, the semaphore value is
decremented (wait operation), and when they put down a chopstick, the
semaphore value is incremented (signal operation).

This implementation ensures that philosophers follow the rules of picking up and putting
down chopsticks in a coordinated manner, preventing deadlock and ensuring mutual
exclusion.

Section 2 : Deadlocks

2.1 Definition:
●​ A deadlock is a state where two or more processes are unable to proceed because
each is waiting for the other to release resources. Essentially, the processes are
stuck in a circular dependency, where each process holds a resource that another
process needs to continue execution.

25
 NotesNeo
Scenario of Deadlocks:
●​ Imagine three processes, P1, P2, and P3, each holding a resource (R1, R2, R3) and
waiting for another resource held by a different process.
●​ For example, P1 may be waiting for R2 held by P2, P2 may be waiting for R3 held by
P3, and P3 may be waiting for R1 held by P1.
●​ This creates a cycle of dependencies where no process can proceed, causing the
system to become unresponsive.

Deadlocks can occur in various scenarios, such as:

●​ Resource Allocation: When processes request resources and hold them while
waiting for additional resources that are currently held by other processes,
deadlock can occur.
●​ Memory Management: Deadlocks can occur in memory allocation scenarios, where
processes request memory blocks and hold them while waiting for additional
memory blocks.
●​ File Access: Deadlocks can occur when processes request exclusive access to files
or file systems and hold the access while waiting for other files or resources.

Difference between Starvation and Deadlock:

●​ Deadlock:
1.​ All processes are blocked indefinitely, waiting for resources held by other
processes.
2.​ It leads to an infinite waiting situation.
3.​ It occurs due to conditions like mutual exclusion, hold and wait, no
preemption, and circular wait happening simultaneously.
●​ Starvation:
1.​ Low priority processes are unable to proceed while high priority processes
continue execution.
2.​ It may lead to long waiting but is not infinite.
3.​ It can occur due to uncontrolled priority and resource management, where
resources are continuously used by higher priority processes.

Relationship between Starvation and Deadlock:

●​ Every deadlock situation also involves starvation, as processes are indefinitely
blocked.

26
 NotesNeo
●​ However, not every case of starvation leads to deadlock.
●​ Deadlock specifically refers to the scenario where processes are stuck in a cyclic
dependency, while starvation refers to the situation where certain processes are
unable to proceed due to resource allocation policies.

2.2 Necessary and Sufficient Conditions for Deadlock:

Necessary Conditions:
1.​ Mutual Exclusion: Each resource can be assigned to only one process or thread at
a time.
2.​ Hold and Wait: A process holds at least one resource and is waiting to acquire
additional resources held by other processes.
3.​ No Preemption: Resources cannot be forcibly taken from a process; they must be
released voluntarily.
4.​ Circular Wait: There must be a circular chain of two or more processes, each
waiting for a resource held by the next process in the chain.

Sufficient Conditions:
●​ All the necessary conditions must hold simultaneously for a deadlock to occur.

2.3 Strategies for Handling Deadlock:

These strategies for handling deadlock provide various approaches to address the issue:

1.​ Deadlock Ignorance (Ostrich Method):

●​ This approach is the most widely used to handle deadlock and commonly
used in many operating systems, especially those focused on end-user
usage like Windows and Linux.
●​ The OS assumes that deadlock never occurs and simply ignores it.
●​ It is suitable for systems where deadlock is rare and the impact of
occasional deadlock situations is minimal.
●​ Users may need to manually restart the system if deadlock occurs.
2.​ Deadlock Prevention:
●​ Focuses on breaking one or more of the necessary conditions for deadlock
(Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait).
●​ If any of these conditions can be violated at any time, deadlock can be
prevented from occurring.
●​ Implementation can be challenging, and there may be trade-offs in terms of
system efficiency and resource utilization.
3.​ Deadlock Avoidance (Bankers Algorithm):
●​ Involves dynamically analyzing the system's state to determine if an
allocation would potentially lead to deadlock.
●​ The OS checks if the system is in a safe state before allocating resources to
processes.
●​ If a potential deadlock is detected, the allocation is delayed or denied to
prevent deadlock.

27
 NotesNeo
●​ Requires careful resource allocation and scheduling to ensure deadlock-free
execution.
4.​ Deadlock Detection and Recovery:
●​ Allows processes to potentially enter deadlock, but periodically checks the
system to detect if deadlock has occurred.
●​ If deadlock is detected, the system applies recovery methods to resolve the
deadlock.
●​ Recovery methods may include killing one or more processes involved in the
deadlock, preempting resources, rolling back processes, or restarting
affected processes.
●​ This approach involves overhead in terms of system monitoring and
recovery mechanisms but ensures that deadlocks are resolved once
detected.

2.4 Deadlock Prevention:

Deadlock prevention strategies aim to ensure that the necessary conditions for deadlock
are never satisfied.

Approaches for Deadlock Prevention:

1.​ No Mutual Exclusion:

●​ Deadlock occurs when processes require exclusive access to resources. To
prevent this, resources can be designed to allow multiple processes to use
them simultaneously.
●​ Spooling is one technique where a resource, like a printer, has associated
memory that stores jobs from each process. The printer then processes these
jobs in a first-come, first-served manner, allowing processes to continue
without waiting for the printer. However, spooling may not be applicable to
all resources and can introduce issues like race conditions.
●​ Spooling stands for Simultaneous Peripheral Operation Online. It’s a
technique used in operating systems to manage input/output (I/O)
operations.

28
 NotesNeo
2.​ No Hold and Wait:
●​ Deadlock arises when processes hold resources while waiting for others,
creating a circular dependency. To prevent this, processes should request
and hold all necessary resources before execution starts.
●​ This approach is not practical in many cases because processes often
cannot determine all required resources beforehand. Additionally, it can
increase the risk of starvation if processes hold resources for long durations.
3.​ Preemption:
●​ Deadlock occurs because processes cannot be forcibly stopped once they
acquire resources. Preemption involves forcibly taking resources from
processes to break deadlocks.
●​ However, preempting resources can lead to inconsistent states and
performance inefficiencies. For example, preempting a printer resource from
a process midway through printing could lead to incomplete or inconsistent
output.
4.​ No Circular Wait:
●​ Deadlock arises when processes wait for resources held by other processes
in a circular chain. To prevent this, assign a priority to each resource and
ensure that processes can only request resources of equal or higher priority.
●​ By enforcing priority-based resource requests, processes cannot form
circular chains of dependencies, thereby preventing deadlock.
​

Among these methods, preventing circular wait is the most practical and commonly
implemented approach. It ensures that processes cannot enter into circular dependencies,
thereby eliminating the possibility of deadlock.

2.5 Deadlock Avoidance - Banker's Algorithm:

The Banker's Algorithm is a deadlock avoidance algorithm used in operating systems to
allocate resources safely to processes and prevent deadlock situations. It simulates a
banking system where resources are allocated based on the need and availability of
resources.
This algorithm was developed by Edsger Dijkstra.

29
 NotesNeo
It is also known as deadlock avoidance or deadlock detection algorithm in the
operating system.

Here's how it works:

1.​ Resource Allocation: The Banker's Algorithm allocates resources to processes based
on their maximum resource requirements and the available resources. It checks
whether granting a resource request will leave the system in a safe state, meaning
that no deadlock will occur.
2.​ Deadlock Avoidance: By analyzing the resource allocation state and future
resource requests, the Banker's Algorithm prevents deadlock situations. It ensures
that resources are allocated in a way that allows processes to progress without
getting stuck in a deadlock.

Real-World Analogy:
●​ Imagine a scenario in a bank where the number of account holders represents
processes, and the total money in the bank represents available system resources.
●​ When an account holder applies for a loan, the bank subtracts the loan amount
from its total cash and ensures that the remaining cash is still sufficient to meet
future loan requests or withdrawals.
●​ Similarly, in an operating system, when a new process is created, it provides
information about its resource requirements to the OS.
●​ The OS, acting like a banker, evaluates these requests and ensures that allocating
resources to processes won't lead to resource starvation or deadlock.

Advantages:
1.​ Ensures deadlock avoidance by carefully allocating resources.
2.​ Helps in managing and controlling resource requests efficiently.
3.​ Allows sharing of resources among processes in a controlled manner.
4.​ Provides a systematic approach to resource allocation, reducing the risk of
deadlocks.

Disadvantages:
1.​ Requires processes to specify their maximum resource requirements in advance.
2.​ Assumes a fixed number of processes, limiting scalability.
3.​ May lead to underutilization of resources if processes overestimate their
requirements.
4.​ Requires careful implementation to avoid inefficiencies and race conditions.

Implementation:
In the Banker's Algorithm, several data structures are used to manage resource allocation
and ensure deadlock avoidance. These data structures include:
1.​ Available: A vector of length m (number of resource types) indicating the number
of available instances of each resource type.
2.​ Max: An n x m matrix defining the maximum demand of each process. Max[i][j] is
the maximum number of instances of resource type j that process i may request.

30
 NotesNeo
3.​ Allocation: An n x m matrix defining the number of instances of each resource type
currently allocated to each process. Allocation[i][j] is the number of instances of
resource type j currently allocated to process i.
4.​ Need: An n x m matrix indicating the remaining resource need of each process.
Need[i][j] = Max[i][j] - Allocation[i][j].
Also, Available[i][j] >= Need[i][j] for safe sequence to occur where deadlock
doesn’t occur.

The Banker's Algorithm is the combination of the safety algorithm and the resource
request algorithm :

Safety Algorithm:
The safety algorithm checks if the system is in a safe state:
1.​ Initialize Work = Available and Finish[i] = false for all processes i.
2.​ Find an index i such that:
●​ Finish[i] == false
●​ Need[i] <= Work
●​ If no such i exists, go to step 4.
3.​ Set Work = Work + Allocation[i] and Finish[i] = true. Go to step 2.
4.​ If Finish[i] == true for all i, the system is in a safe state.

Resource Request Algorithm:

This algorithm checks if a resource request can be safely granted:
1.​ Let Request[i] be the request vector for process i. If Request[i][j] = k, process i
wants k instances of resource type j.
2.​ If Request[i] <= Need[i], go to step 3. Otherwise, raise an error (process has
exceeded its maximum claim).
3.​ If Request[i] <= Available, go to step 4. Otherwise, the process must wait (resources
not available).
4.​ Temporarily allocate the requested resources:
●​ Available = Available - Request[i]
●​ Allocation[i] = Allocation[i] + Request[i]
●​ Need[i] = Need[i] - Request[i]
5.​ Use the Safety Algorithm to check if the new state is safe:
●​ If the new state is safe, allocate the resources to process i.
●​ If the new state is unsafe, restore the previous state and process i must wait.

Example:
Consider a system with five processes {P1, P2, P3, P4, P5} and three resources {A, B, C}.
Resource type A has 10 instances, B has 5 instances and type C has 7 instances.
Total Available Resources: 3, 3, 2 initially.

Process Allocation Max Available Need

A B C A B C A B C A B C

31
 NotesNeo

P1 0 1 0 7 5 3 3 3 2 7 4 3

P2 2 0 0 3 2 2 5 3 2 1 2 2

P3 3 0 2 9 0 2 7 4 3 6 0 0

P4 2 1 1 2 2 2 7 4 5 0 1 1

P5 0 0 2 5 3 3 7 5 5 5 3 1

Explanation and Steps

1.​ Need Matrix Calculation:
●​ P1: Need = Max - Allocation = (7, 5, 3) - (0, 1, 0) = (7, 4, 3)
●​ P2: Need = Max - Allocation = (3, 2, 2) - (2, 0, 0) = (1, 2, 2)
●​ P3: Need = Max - Allocation = (9, 0, 2) - (3, 0, 2) = (6, 0, 0)
●​ P4: Need = Max - Allocation = (2, 2, 2) - (2, 1, 1) = (0, 1, 1)
●​ P5: Need = Max - Allocation = (5, 3, 3) - (0, 0, 2) = (5, 3, 1)
2.​ Safety Algorithm:
●​ Initial Available Resources: [3, 3, 2]
●​ Check each process to see if it can be completed with the current available
resources.
3.​ Steps to check if the system is in a safe state:
●​ Step 1: For Process P1:
●​ Need: (7, 4, 3)
●​ Available: (3, 3, 2)
●​ Since (7, 4, 3) > (3, 3, 2), P1 cannot proceed.
●​ Step 2: For Process P2:
●​ Need: (1, 2, 2)
●​ Available: (3, 3, 2)
●​ Since (1, 2, 2) <= (3, 3, 2), P2 can proceed.
●​ New Available after P2 finishes: (3, 3, 2) + (2, 0, 0) = (5, 3, 2)
●​ Step 3: For Process P3:
●​ Need: (6, 0, 0)
●​ Available: (5, 3, 2)
●​ Since (6, 0, 0) > (5, 3, 2), P3 cannot proceed.
●​ Step 4: For Process P4:
●​ Need: (0, 1, 1)
●​ Available: (5, 3, 2)
●​ Since (0, 1, 1) <= (5, 3, 2), P4 can proceed.
●​ New Available after P4 finishes: (5, 3, 2) + (2, 1, 1) = (7, 4, 3)
●​ Step 5: For Process P5:
●​ Need: (5, 3, 1)
●​ Available: (7, 4, 3)
●​ Since (5, 3, 1) <= (7, 4, 3), P5 can proceed.
●​ New Available after P5 finishes: (7, 4, 3) + (0, 0, 2) = (7, 4, 5)
●​ Step 6: For Process P1:

32
 NotesNeo
●​ Need: (7, 4, 3)
●​ Available: (7, 4, 5)
●​ Since (7, 4, 3) <= (7, 4, 5), P1 can proceed.
●​ New Available after P1 finishes: (7, 4, 5) + (0, 1, 0) = (7, 5, 5)
●​ Step 7: For Process P3:
●​ Need: (6, 0, 0)
●​ Available: (7, 5, 5)
●​ Since (6, 0, 0) <= (7, 5, 5), P3 can proceed.
●​ New Available after P3 finishes: (7, 5, 5) + (3, 0, 2) = (10, 5, 7)

Safe Sequence:
Based on the above steps, the safe sequence is: P2 -> P4 -> P5 -> P1 -> P3.

2.6 Deadlock Detection Using RAG

Resource Allocation Graph (RAG):

The Resource Allocation Graph (RAG) is a visual representation used in deadlock detection
algorithms to illustrate the allocation of resources to processes. Here's a breakdown of its
components:

Vertices:
1.​ Process (Circle): Each process in the system is represented by a circle.
2.​ Resource (Rectangle): Resources in the system, such as printers or memory units,
are depicted by rectangles.

Instances:
●​ Each resource rectangle may contain one or more dots inside, representing the
instances of that resource.

Edges:
1.​ Assignment Edge: An arrow from a resource to the process currently holding it.
2.​ Request Edge: An arrow from a process to a resource it wants.

33
 NotesNeo

Example:
Consider a scenario with three processes (P1, P2, P3) and two types of resources (R1, R2),
each with one instance.

●​ The graph is deadlock free since no cycle is being formed in the graph.

Deadlock Detection Using RAG:

●​ A deadlock occurs if a cycle is detected in the resource allocation graph.
●​ If there are no cycles in the graph, then the system is considered deadlock-free.
●​ Deadlock detection algorithms use the resource allocation graph to identify
potential deadlocks and take appropriate actions to resolve them.

A cycle in RAG indicates the potential for deadlock:

●​ If all resources have a single instance, a cycle in RAG implies deadlock.
●​ With multiple instances of resources, a cycle is necessary but not sufficient for
deadlock.

Example:
●​ Consider a system with three processes (P1, P2, P3) and three resources (R1, R2,
R3), each having a single instance. The RAG shows the current allocation and
requests.

34
 NotesNeo

●​ The system has deadlock because cycle is being formed in the graph.

RAG Analysis:
The RAG forms a cycle involving all processes and resources, indicating that the system
satisfies the four conditions of deadlock:
1.​ Mutual Exclusion: Each resource is assigned to exactly one process.
2.​ Hold and Wait: Processes holding resources are waiting for other resources.
3.​ No Preemption: Resources cannot be forcibly taken from processes.
4.​ Circular Wait: There exists a cycle in the graph.

Allocation and Request Matrices

To analyze deadlock using matrices, we convert the RAG information into Allocation and
Request matrices.

Allocation Matrix- Indicates the current resource allocation to processes.

Process R1 R2 R3

P1 0 0 1

P2 1 0 0

P3 0 1 0

Request Matrix- Indicates the current resource requests by processes.

Process R1 R2 R3

P1 1 0 0

P2 0 1 0

P3 0 0 1

Available Vector- Indicates the currently available resources.

Available=(0,0,0)

35
 NotesNeo
Deadlock Detection Algorithm
1.​ Initialization:
■​ Work = Available (0, 0, 0)
■​ Finish[i] = False for all i
2.​ Find a Process:
■​ Find a process Pi such that both:
○​ Finish[i] = False
○​ Request[i] <= Work
■​ If no such process exists, go to step 4.
3.​ Resource Allocation:
■​ If such a process is found:
○​ Work = Work + Allocation[i]
○​ Finish[i] = True
○​ Go to step 2.
4.​ Check for Deadlock:
■​ If Finish[i] = False for any i, the system is in deadlock.

Application to the Example

●​ Initialization:
■​ Work=(0,0,0)
■​ Finish=[False, False, False]
■​ Finish=[False, False, False]
●​ Finding Process:
■​ For P1: Request (1, 0, 0) > Work (0, 0, 0) - cannot proceed.
■​ For P2: Request (0, 1, 0) > Work (0, 0, 0) - cannot proceed.
■​ For P3: Request (0, 0, 1) > Work (0, 0, 0) - cannot proceed.
Since no process can proceed, we detect a deadlock.

2.7 Deadlock Detection and Recovery:

Deadlock Detection:

1.​ Periodic checks: The operating system periodically checks the system for deadlock
conditions.

36
 NotesNeo
2.​ Resource allocation graph (RAG): The OS may use a resource allocation graph to
detect deadlocks. If a cycle is present in the graph, it indicates a potential
deadlock.
3.​ Matrix representations: In systems with multiple instances of resources, deadlock
detection may involve converting the resource allocation graph into allocation and
request matrices. The system checks for unsafe states where processes cannot
proceed without leading to deadlock.

Deadlock Recovery:
Once deadlock is detected, the OS can choose from several recovery techniques to resolve
the deadlock:

1.​ Preempt the resource: The OS can forcibly reclaim resources from one or more
processes and allocate them to others. This is done with the hope that the affected
processes can continue execution and release resources to resolve the deadlock.
2.​ Rollback to a safe state: The OS may rollback the system to a previously known
safe state. This involves reverting resource allocations to a point where deadlock
did not exist. Checkpoints are used to mark safe states in the system's execution.
3.​ Kill a process: The OS may terminate one or more processes to break the
deadlock. Typically, the process chosen for termination is the one that has done the
least amount of work, minimizing the impact on overall system functionality.
4.​ Kill all processes: As a last resort, the OS may choose to terminate all processes in
the system. This approach is highly disruptive and inefficient, as it requires all
processes to restart from the beginning.

MDU PYQs (Short)

July 2022
1.​ What is critical section problem ?

37
 NotesNeo

Others
2.​ Is it possible to have a deadlock involving only one process? Explain your answer.
3.​ Explain semaphores.
4.​ Write a short note on Critical section.
5.​ What are buffering and spooling?

MDU PYQs (Long)

May 2023
1.​ (a) What is deadlock? Explain various methods for detecting, prevention and
recovery of deadlocks.
(b) Explain Banker’s algorithm briefly.
2.​ (a) What is Inter Process Communication (IPC) ? Explain Dining Philosopher IPC
problem in detail.
(b) What is semaphore? Explain counting and binary semaphore in detail.

July 2022
3.​ What is semaphores? Implement readers writers problem using semaphores.
4.​ What is deadlock? What are the conditions to prevent deadlock in a system?

July 2021
5.​ What is critical section problem? Explain IPC (Inter Process Communication) Dining
Philosophers problem with implementation using semaphore.
6.​ What is deadlock? What are the necessary conditions for a deadlock? Explain the
mechanism for a deadlock recovery.

Others
7.​ What are the algorithms for deadlock prevention?

38