Inter-Process Communication

Interprocess Communication (IPC) is the mechanism provided by an operating system that

allows independent processes to communicate, share data, and synchronize their actions. In
modern computing, where systems run many tasks simultaneously (multitasking), IPC is
essential for building complex, modular, and high-performance applications.

Core IPC Models

There are two fundamental approaches to how processes "talk" to each other:

 Shared Memory: Processes agree to share a specific region of RAM.

o Pros: It is the fastest method because data isn't copied; processes read and write
directly.

o Cons: Requires careful synchronization (e.g., using semaphores) to prevent "race

conditions" where two processes try to change the same data at once.

 Message Passing: Processes exchange information by sending and receiving "packets" of

data through the OS kernel.

o Pros: Easier to implement and safer, as the kernel manages the communication.
It is ideal for distributed systems where processes are on different machines.

o Cons: Slower than shared memory due to the overhead of system calls and data
copying.

Common IPC Mechanisms

Beyond the two main models, various specific tools are used in different scenarios:

1. Pipes: Unidirectional data channels (like a water pipe). Data flows from a "write" end to
a "read" end.

1. Anonymous Pipes: Used between related processes (e.g., parent and child).

2. Named Pipes (FIFOs): Can connect unrelated processes and appear as special files on
the disk.

2. Message Queues: A linked list of messages stored in the kernel. Processes can leave
messages there for others to pick up later, allowing for asynchronous communication.

3. Sockets: The primary method for communication over a network. They act as endpoints
for sending or receiving data between processes on the same or different computers.
 4. Signals: Simple notifications sent by the OS or a process to another process to alert it of
an event (e.g., "stop" or "error").

5. Semaphores & Mutexes: Variables used to control access to shared resources, ensuring
only one process uses a critical section at a time.

Why Is IPC Necessary?

 Information Sharing: Multiple processes may need the same data (e.g., a shared file or
database).

 Computation Speedup: A large task can be split into smaller sub-tasks running in parallel,
which then communicate to combine results.

 Modularity: Complex systems (like a web browser) are broken into separate processes to
improve reliability; if one tab crashes, the whole browser doesn't have to.

 Convenience: Allows users to perform multiple tasks at once, like listening to music
while editing a document.

Critical Section
A critical section is a part of a program where shared resources (like memory, files, or variables)
are accessed by multiple processes or threads. To avoid problems such as race conditions and
data inconsistency, only one process/thread should execute the critical section at a time using
synchronization techniques. This ensures that operations on shared resources are performed
safely and predictably.

Structure of a Critical Section

1. Entry Section

 The process requests permission to enter the critical section.

 Synchronization tools (e.g., mutex, semaphore) are used to control access.

2. Critical Section: The actual code where shared resources are accessed or modified.

3. Exit Section: The process releases the lock or semaphore, allowing other processes to enter
the critical section.

4. Remainder Section: The rest of the program that does not involve shared resource access.
Critical Section Problem
Shared Resources and Race Conditions

 Shared resources include memory, global variables, files, and databases.

 A race condition occurs when two or more processes attempt to update shared data at
the same time, leading to unexpected results. Example: Two bank transactions
modifying the same account balance simultaneously without synchronization may lead
to incorrect final balance.

It could be visualized using the pseudo-code below

do{
flag=1;
while(flag); // (entry section)
// critical section
if (!flag)
// remainder section
} while(true);

Requirements of a Solution
A good critical section solution must ensure:

1. Correctness - Shared data should remain consistent.

2. Efficiency - Should minimize waiting and maximize CPU utilization.

3. Fairness - No process should be unfairly delayed or starved.

Requirements of Critical Section Solutions

1. Mutual Exclusion

 At most one process can be inside the critical section at a time.

 Prevents conflicts by ensuring no two processes update the shared resource

simultaneously.

2. Progress

 If no process is in the critical section, and some processes want to enter, the choice of
who enters next should not be postponed indefinitely.

 Ensures that the system continues to make progress rather than getting stuck.
3. Bounded Waiting

 There must be a limit on how long a process waits before it gets a chance to enter the
critical section.

 Prevents starvation, where one process is repeatedly bypassed while others get to
execute.

Example Use Case: Older operating systems or embedded systems where simplicity and
reliability outweigh responsiveness.

Solution to Critical Section Problem :

A simple solution to the critical section can be thought of as shown below,

acquireLock();
Process Critical Section
releaseLock();

A thread must acquire a lock prior to executing a critical section. The lock can be acquired by
only one thread. There are various ways to implement locks in the above pseudo-code.

Examples of critical sections in real-world applications

Banking System (ATM or Online Banking)

 Critical Section: Updating an account balance during a deposit or withdrawal.

 Issue if not handled: Two simultaneous withdrawals could result in an incorrect final
balance due to race conditions.

Ticket Booking System (Airlines, Movies, Trains)

 Critical Section: Reserving the last available seat.

 Issue if not handled: Two users may be shown the same available seat and both may
book it, leading to overbooking.

Print Spooler in a Networked Printer

 Critical Section: Sending print jobs to the printer queue.

 Issue if not handled: Print jobs may get mixed up or skipped if multiple users send jobs
simultaneously.

File Editing in Shared Documents (e.g., Google Docs, MS Word with shared access)
 Critical Section: Saving or writing to the shared document.

 Issue if not handled: Simultaneous edits could lead to conflicting versions or data loss.

A race condition occurs when two or more processes or threads access and modify the
same data at the same time, and the final result depends on the order in which they run.
Without proper coordination, this can lead to incorrect or unpredictable results. For
example, if two people update the same bank account simultaneously without checking
each other’s changes, the final balance may be wrong.

Key Concepts

 Shared Resource: A variable, file, memory location, or device accessed by multiple

processes.

 Concurrency: Multiple processes or threads executing simultaneously or overlapping in

execution.

 Non-Atomic Operations: Operations that can be interrupted, such as read-modify-write,

which can cause inconsistent states when multiple processes access the same data
concurrently.

Race Condition
A race condition occurs when two or more processes or threads access and modify the
same data at the same time, and the final result depends on the order in which they
run. Without proper coordination, this can lead to incorrect or unpredictable results.
For example, if two people update the same bank account simultaneously without
checking each other’s changes, the final balance may be wrong.

Key Concepts
 Shared Resource: A variable, file, memory location, or device accessed by multiple
processes.

 Concurrency: Multiple processes or threads executing simultaneously or overlapping

in execution.

 Non-Atomic Operations: Operations that can be interrupted, such as read-modify-

write, which can cause inconsistent states when multiple processes access the same
data concurrently.
 Causes of Race Conditions
 Simultaneous Access: when two or more processes try to read or write the same shared
resource at the same time.

 Non-Atomic Updates: Operations like increment or decrement are not indivisible.

 Lack of Synchronization: No mechanisms like locks, semaphores, or monitors are used

to control access.

 Improper Scheduling: OS scheduler interrupts processes at critical moments.

Example: Two Processes Updating a Shared Variable

Let’s take a shared variable balance = 100 and two processes P1 and P2:

 P1 wants to add 10 to balance.

 P2 wants to subtract 10 from balance.

Explanation:
 P1 reads balance = 100 and prepares to add 10.

 Before P1 updates the balance with the new value (110), it is interrupted by the process
P2.

 P2, unaware of P1’s action (of adding 10), reads the balance as 100 (incorrect) and
prepares to subtract 10.

 After subtracting, P2 updates the balance to 90 and then P1 resumes and writes the
balance as 110 which is incorrect now.

In many cases, the final balance may incorrectly be 110 or 90, instead of the expected
100. This is a classic race condition.

Effects of Race Conditions

 Data Corruption: Shared data may become inconsistent.

 Unpredictable Behavior: The output may vary every time the program runs.

 Security Risks: Race conditions can be exploited, e.g., in banking transactions or

authentication bypass.

 System Crashes: Critical system data may get corrupted, leading to failures.
 Prevention Techniques

1. Mutex (Mutual Exclusion): Ensure only one process can enter the critical section at a
time.

2. Semaphores: Counting or binary semaphores control access to resources.

3. Monitors: High-level synchronization constructs that manage shared resources.

4. Atomic Operations: Use hardware or software-supported atomic instructions.

5. Disable Interrupts (for kernel-level programming): Prevent context switches during

critical sections.

6. Proper Scheduling: Ensure the scheduler does not preempt critical section execution.

Mutual Exclusion
During concurrent execution of processes, processes need to enter the critical section (or
the section of the program shared across processes) at times for execution. It might
happen that because of the execution of multiple processes at once, the values stored in
the critical section become inconsistent. In other words, the values depend on the
sequence of execution of instructions - also known as a race condition. The primary task
of process synchronization is to get rid of race conditions while executing the critical
section .
What is Mutual Exclusion?
Mutual Exclusion is a property of process synchronization that states that "no two
processes can exist in the critical section at any given point of time". The term was first
coined by Dijkstra. Any process synchronization technique being used must satisfy the
property of mutual exclusion, without which it would not be possible to get rid of a race
condition.

The need for mutual exclusion comes with concurrency. There are several kinds of
concurrent execution:

 Interrupt handlers

 Interleaved, preemptively scheduled processes/threads

 Multiprocessor clusters, with shared memory

 Distributed systems

Mutual exclusion methods are used in concurrent programming to avoid the

simultaneous use of a common resource, such as a global variable, by pieces of
computer code called critical sections.

The requirement of mutual exclusion is that when process P1 is accessing a shared

resource R1, another process should not be able to access resource R1 until process P1
has finished its operation with resource R1.

Examples of such resources include files, I/O devices such as printers, and shared data
structures.

Conditions Required for Mutual Exclusion

According to the following four criteria, mutual exclusion is applicable:

 When using shared resources, it is important to ensure mutual exclusion between

various processes. There cannot be two processes running simultaneously in either of
their critical sections.

 It is not advisable to make assumptions about the relative speeds of the unstable
processes.

 For access to the critical section, a process that is outside of it must not obstruct another
process.

 Its critical section must be accessible by multiple processes in a finite amount of time;
multiple processes should never be kept waiting in an infinite loop.

Approaches To Implementing Mutual Exclusion

 Software Method: Leave the responsibility to the processes themselves. These methods
are usually highly error-prone and carry high overheads.

 Hardware Method: Special-purpose machine instructions are used for accessing shared
resources. This method is faster but cannot provide a complete solution. Hardware
solutions cannot give guarantee the absence of deadlock and starvation.

 Programming Language Method: Provide support through the operating system or

through the programming language.

Requirements of Mutual Exclusion

 At any time, only one process is allowed to enter its critical section.
 The solution is implemented purely in software on a machine.

 A process remains inside its critical section for a bounded time only.

 No assumption can be made about the relative speeds of asynchronous concurrent

processes.

 A process cannot prevent any other process from entering into a critical section.

 A process must not be indefinitely postponed from entering its critical section.

In order to understand mutual exclusion, let's take an example.

What is a Need of Mutual Exclusion?

An easy way to visualize the significance of mutual exclusion is to imagine a linked list of
several items, with the fourth and fifth items needing to be removed. By changing the
previous node's next reference to point to the succeeding node, the node that lies
between the other two nodes is deleted.

To put it simply, whenever node "i" wants to be removed, node "with - 1"'s subsequent
reference is changed to point to node "ith + 1" at that time. Two distinct nodes can be
removed by two threads at the same time when a shared linked list is being used by
many threads. This occurs when the first thread modifies node "ith - 1" next reference,
pointing towards the node "ith + 1," and the second thread modifies node "ith" next
reference, pointing towards the node "ith + 2." Although both nodes have been removed,
the linked list's required state has not yet been reached because node "i + 1" still exists
in the list because node "ith - 1" next reference still points to it.

Now, this situation is called a race condition. Race conditions can be prevented by
mutual exclusion so that updates at the same time cannot happen to the very bit about
the list.

Example:
In the clothes section of a supermarket, two people are shopping for clothes.
Boy, A decides upon some clothes to buy and heads to the changing room to try them
out. Now, while boy A is inside the changing room, there is an 'occupied' sign on it -
indicating that no one else can come in. Boy B has to use the changing room too, so she
has to wait till boy A is done using the changing room.
Once boy A comes out of the changing room, the sign on it changes from 'occupied' to
'vacant' - indicating that another person can use it. Hence, boy B proceeds to use the
changing room, while the sign displays 'occupied' again.

The changing room is nothing but the critical section, boy A and boy B are two different
processes, while the sign outside the changing room indicates the process
synchronization mechanism being used.
Conclusion
In conclusion, mutual exclusion is a key concept in synchronization that ensures only one
process accesses a shared resource at a time. This prevents conflicts and data corruption,
making sure that processes run smoothly and correctly. By using mutual exclusion
mechanisms, we can create stable and reliable systems that handle multiple processes
efficiently.

The Producer /consumer Problem

Producer-Consumer problem is a classical synchronization problem in the operating
system. With the presence of more than one process and limited resources in the system
the synchronization problem arises. If one resource is shared between more than one
process at the same time then it can lead to data inconsistency. In the producer-
consumer problem, the producer produces an item and the consumer consumes the
item produced by the producer.
 What is Producer Consumer Problem?
Before knowing what is Producer-Consumer Problem we have to know what are
Producer and Consumer.

 In operating System Producer is a process which is able to produce data/item.

 Consumer is a Process that is able to consume the data/item produced by the Producer.

 Both Producer and Consumer share a common memory buffer. This buffer is a space of a
certain size in the memory of the system which is used for storage. The producer
produces the data into the buffer and the consumer consumes the data from the buffer.

So, what are the Producer-Consumer Problems?

1. Producer Process should not produce any data when the shared buffer is full.

2. Consumer Process should not consume any data when the shared buffer is empty.

3. The access to the shared buffer should be mutually exclusive i.e at a time only one
process should be able to access the shared buffer and make changes to it.

For consistent data synchronization between Producer and Consumer, the above
problem should be resolved.

Solution For Producer Consumer Problem

To solve the Producer-Consumer problem three semaphores variable are used :

Semaphores are variables used to indicate the number of resources available in the
system at a particular time. semaphore variables are used to achieve `Process
Synchronization.

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.

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.

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 - 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

The code for Producer Process is as follows :

void Producer(){

while(true){

// producer produces an item/data

wait(Empty);

wait(mutex);

add();

signal(mutex);

signal(Full);

Let's understand the above Producer process code :

 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.

 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.

 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.

 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.

 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.

The code for the Consumer Process is as follows :

void Consumer() {

while(true){

// consumer consumes an item

wait(Full);

wait(mutex);

consume();

signal(mutex);

signal(Empty);

Let's understand the above Consumer process code :

 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.

 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.
 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.

 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.

 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 1.

Why can mutex solve the producer consumer Problem ?

Mutex is used to solve the producer-consumer problem as mutex helps in mutual
exclusion. It prevents more than one process to enter the critical section. As mutexes
have binary values i.e 0 and 1. So whenever any process tries to enter the critical section
code it first checks for the mutex value by using the wait operation.

wait(mutex);

wait(mutex) decreases the value of mutex by 1. so, suppose a process P1 tries to enter
the critical section when mutex value is 1. P1 executes wait(mutex) and decreases the
value of mutex. Now, the value of mutex becomes 0 when P1 enters the critical section
of the code.

Now, suppose Process P2 tries to enter the critical section then it will again try to
decrease the value of mutex. But the mutex value is already 0. So, wait(mutex) will not
execute, and P2 will now keep waiting for P1 to come out of the critical section.

Now, suppose if P2 comes out of the critical section by executing signal(mutex).

signal(mutex)

signal(mutex) increases the value of mutex by [Link] value again becomes 1. Now, the
process P2 which was in a busy-waiting state will be able to enter the critical section by
executing wait(mutex).

So, mutex helps in the mutual exclusion of the processes.

In the above section in both the Producer process code and consumer process code, we
have the wait and signal operation on mutex which helps in mutual exclusion and solves
the problem of the Producer consumer process.

Conclusion
 Producer Process produces data item and consumer process consumes data item.
 Both producer and consumer processes share a common memory buffer.

 Producer should not produce any item if the buffer is full.

 Consumer should not consume any item if the buffer is empty.

 Not more than one process should access the buffer at a time i.e mutual exclusion
should be there.

 Full, Empty and mutex semaphore help to solve Producer-consumer problem.

 Full semaphore checks for the number of filled space in the buffer by the producer
process

 Empty semaphore checks for the number of empty spaces in the buffer.

 mutex checks for the mutual exclusion.

Semaphores
A semaphore is a synchronization tool used in operating systems to manage access to
shared resources in a multi-process or multi-threaded environment. It is an integer
variable that controls process execution using atomic operations like wait() and signal().
Semaphores help prevent race conditions and ensure proper coordination between
processes.

 Controls entry into the critical section.

 Maintains a counter representing available resources.

 Ensures mutual exclusion among processes.

 Can block and wake up processes during execution.

 Widely used in concurrent programming.

How Semaphores Work

 A semaphore in OS uses two primary atomic operations:

1. wait(S)

Wait Operation

 Decrements the semaphore value.

 If the value is less than 0, the process waits until the resource is available.

 Used to acquire a resource.

2. signal(S)

Signal Operation

 Increments the semaphore value.

 If there are waiting processes, one is awakened.

 Used to release a resource.

Example: Let’s consider two processes P1 and P2 sharing a semaphore S, initialized to 1:

 State 1: Both processes are in their non-critical sections, and S = 1.

 State 2: P1 enters the critical section. It performs wait(S), so S = 0. P2 continues in the

non-critical section.

 State 3: If P2 now wants to enter, it cannot proceed since S = 0. It must wait until S > 0.

 State 4: When P1 finishes, it performs signal(S), making S = 1. Now P2 can enter its
critical section and again sets S = 0.

This mechanism guarantees mutual exclusion, ensuring that only one process can access
the shared resource at a time, see the image below for reference:

Features of Semaphores
 Mutual Exclusion: Semaphore ensures that only one process accesses a shared resource
at a time.

 Process Synchronization: Semaphore coordinates the execution order of multiple

processes.
 Resource Management: Limits access to a finite set of resources, like printers, devices,
etc.

 Reader-Writer Problem: Allows multiple readers but restricts the writers until no reader
is present.

 Avoiding Deadlocks: Prevents deadlocks by controlling the order of allocation of

resources.

Types of Semaphores
Semaphores are mainly of two Types:

1. Counting Semaphore

A counting semaphore can have values ranging from 0 to any positive integer. It is used
when multiple instances of a resource are available and need to be managed.

 Value ranges from 0 to n.

 Manages multiple resource instances.

 Controls access to limited resources.

 Example: Managing access to 5 printers or 3 database connections.

2. Binary Semaphore

A binary semaphore has only two possible values: 0 and 1. It is mainly used for mutual
exclusion, ensuring that only one process enters the critical section at a time.

 Value is either 0 or 1.

 Used for mutual exclusion.

 Similar to a mutex lock.

 Managing access to a single critical section

Limitations of Semaphores
 Priority Inversion: A low-priority process holding a semaphore can block a high-priority
one.

 Deadlock: Processes may wait on each other’s semaphores in a cycle, causing indefinite
blocking.
 Complex to Manage: The OS must carefully track wait and signal calls; misuse can cause
errors.

 Busy Waiting: In basic implementations, processes may keep checking the semaphore
value, wasting CPU time.

Event Counters
In operating systems, event counters are synchronization primitives used to manage the
sequencing and timing of processes. Think of them as a secure, "read-only" style of
counter that allows processes to wait for a specific state or event to occur without the
complexities (and potential pitfalls) of traditional locks.

They were famously introduced as a way to handle synchronization without the need
for mutual exclusion (where only one person can touch the variable at a time).

How Event Counters Work

An event counter is essentially a non-negative integer that starts at zero. Unlike a
standard variable, its value can only be changed or interacted with through three
specific operations:

 Read(E): Returns the current value of the event counter

 Advance(E): Increments the counter

by 1 (

). This signals that a specific event has occurred.

 Await(E, v): This is the "wait" command. The calling process is suspended until the value
of
 is greater than or equal to

Key Characteristics

Feature Description

Monotonicity The value only ever goes up. It never decreases or resets during a
cycle.

No Mutual Multiple processes can Read or Advance the counter

Exclusion simultaneously without traditional locking mechanisms.

Simplicity They focus on "when" something happens rather than "who" gets
to do it.

Event Counters vs. Semaphores

While both are used for synchronization, they behave differently:

1. Memory/History: A semaphore's value can go up and down. If a semaphore is "1" and

you decrement it, the "history" of that event is gone. An event counter keeps a
permanent record of how many times an event has happened.

2. Destructive vs. Non-destructive: A P() operation on a semaphore changes its value

(destructive). A Read() or Await() on an event counter does not change its value (non-
destructive).

3. The "Lost Wake-up" Problem: Event counters inherently solve the lost wake-up problem.
Since the counter always increases, a process checking Await(E, 5) will proceed even if
the Advance happened while the process was busy doing something else.

A Practical Example: Producer-Consumer

 Imagine a buffer where a Producer adds items and a Consumer removes them. We use
two event counters: In (items produced) and Out (items consumed).

 Producer Logic:

1. Read the current Out count.

2. Check if the buffer is full: Await(Out, sequence_number - buffer_size).

3. Place item in buffer.

4. Advance(In).

 Consumer Logic:

1. Await(In, sequence_number).

2. Take item from buffer.

3. Advance(Out).

Why use them?

Event counters are particularly useful in distributed systems or parallel
computing where you want to avoid the performance bottleneck of "locking" a variable.
Because Advance is the only operation that modifies the value, and it only moves in one
direction, it is much easier to implement in a way that avoids race conditions.

Monitors
Monitors are a high-level synchronization mechanism that simplify process and thread
synchronization. They are built on top of locks and are mostly used in multithreading
systems like Java.

Unlike semaphores, where the programmer must explicitly call wait() and signal(),
monitors combine shared data and the operations on that data inside a single structure,
making synchronization safer and easier to manage.

Key Points:
 A monitor is similar to a class/module that groups shared variables and the functions
that operate on them.
 Only one thread can execute inside a monitor at a time, ensuring automatic mutual
exclusion.

 In Java, monitors are implemented using classes and synchronized methods.

 There is no monitor keyword in Java – the functionality is achieved through synchronized.

How to Implement Monitors

 Monitors are implemented at the programming language level, not directly by the
operating system.

 In Java, monitor-like behavior is achieved using the synchronized keyword ensures that
only one thread can execute inside the monitor at a time.

 A monitor encapsulates both shared data (critical resource) and the operations that
access or modify it.

 Mutual exclusion is enforced automatically, unlike semaphores where programmers

must explicitly call wait() and signal().

 Synchronization can be applied through synchronized methods or synchronized blocks.

 Condition variables are used to control thread waiting and signaling.

 The methods wait(), notify(), and notifyAll() provide process coordination.

Structure of Monitor

Condition Variables in Monitors

A condition variable allows threads to wait until a certain condition becomes true. They
are always used inside a monitor. There are three main condition variables:

 wait(): temporarily releases the monitor lock and puts the thread to sleep until it is
signaled.

 signal(): wakes up one waiting thread (if any).

 broadcast() (in some languages): wakes up all waiting threads.

Message Passing
So message passing means how a message can be sent from one end to the other end.
Either it may be a client-server model or it may be from one node to another node. The
 formal model for distributed message passing has two timing models one is synchronous
and the other is asynchronous.

The fundamental points of message passing are:

1. In message-passing systems, processes communicate with one another by sending and
receiving messages over a communication channel. So how the arrangement should be
done?

2. The pattern of the connection provided by the channel is described by some topology
systems.

3. The collection of the channels are called a network.

4. So by the definition of distributed systems, we know that they are geographically set of
computers. So it is not possible for one computer to directly connect with some other
node.

5. So all channels in the Message-Passing Model are private.

6. The sender decides what data has to be sent over the network. An example is, making a
phone call.

7. The data is only fully communicated after the destination worker decides to receive the
data. Example when another person receives your call and starts to reply to you.

8. There is no time barrier. It is in the hand of a receiver after how many rings he receives
your call. He can make you wait forever by not picking up the call.

9. For successful network communication, it needs active participation from both sides.

Message Passing Model

 Algorithm:
1. Let us consider a network consisting of n nodes named p0, p1, p2........pn-1 which are
bidirectional point to point channels.

2. Each node might not know who is at another end. So in this way, the topology would be
arranged.

3. Whenever the communication is established and whenever the message passing is

started then only the processes know from where to where the message has to be sent.

Additional Information:
1. Security Measures: It is important to add security measures in message passing as the
data being sent is vulnerable to attacks. Hence, techniques such as encryption and
authentication should be used to ensure secure communication.

2. Types of Messages: The article could mention the types of messages that can be sent in
the message passing model, such as request messages, reply messages, broadcast
messages, and multicast messages.

3. Message Routing: It is essential to mention the message routing algorithm used in

message passing. The routing algorithm decides the path that the message should take
to reach the destination node.

4. Error Handling: The article can mention the error handling mechanism used in message
passing, as errors can occur during communication. Error handling ensures that the
system can continue its operation even in the presence of errors.

5. Communication Protocols: The article can also mention the various communication
protocols used in message passing, such as TCP/IP, UDP, and RDP.

6. Comparison with other models: It would be interesting to compare the message passing
model with other models, such as shared memory and Remote Procedure Call (RPC)
models. This will help readers understand the advantages and disadvantages of message
passing over other models.

Advantages of Message Passing Model :

1. Easier to implement.
2. Quite tolerant of high communication latencies.
3. Easier to build massively parallel hardware.
4. It is more tolerant of higher communication latencies.
5. Message passing libraries are faster and give high performance.

Disadvantages of Message Passing Model :

1. Programmer has to do everything.

2. Connection setup takes time that's why it is slower.

3. Data transfer usually requires cooperative operations which can be difficult to achieve.

4. It is difficult for programmers to develop portable applications using this model because
message-passing implementations commonly comprise a library of subroutines that are
embedded in source code. Here again, the programmer has to do everything on his own.

Classical IPC Problems

Inter-Process Communication (IPC) allows processes to share data and coordinate tasks.
However, when multiple processes interact, problems such as synchronization errors,
resource conflicts, and deadlocks can occur. These challenges are often studied through
the following classical IPC problems, which provide models for understanding and
solving real-world issues in operating systems.

1. Producer-Consumer Problem – managing shared buffers without overflow or underflow.

2. Readers-Writers Problem – balancing concurrent reads and exclusive writes.

3. Dining Philosophers Problem – preventing deadlock and starvation in shared resource

usage.

4. Sleeping Barber Problem – handling synchronization and fairness in service systems.

These problems highlight the need for proper synchronization techniques like
semaphores, mutexes, and monitors.

1. Producer-Consumer Problem
This problem involves two processes:

 Producer: generates data and adds it to a buffer.

 Consumer: removes data from the buffer for processing.

Challenges:
 Buffer Overflow – producer tries to add when the buffer is full.

 Buffer Underflow – consumer tries to remove when the buffer is empty.

Solution: Use synchronization tools like semaphores or mutexes to ensure controlled

access to the buffer.

2. Reader-Writer Problem
Here, multiple processes read and write to a shared resource.

 Readers: only read the data.

 Writers: modify the data.

Challenges:

 Allow many readers to access simultaneously.

 Ensure that only one writer writes at a time.

 Prevent readers from reading while a writer is writing.

Solutions:

 Readers Preference – give readers priority, making writers wait.

 Writers Preference – give writers priority, ensuring timely update.

3. Dining Philosophers Problem

This problem models philosophers seated around a table, each needing two chopsticks
to eat. Chopsticks are shared between neighbors, creating potential conflicts.

Challenges:

 Deadlock – if all philosophers pick up one chopstick and wait for the other.

 Starvation – some philosophers may never get to eat.

Solution: Use semaphores or monitors to coordinate chopstick use and avoid deadlock.

4. Sleeping Barber Problem

In a barber shop:

 If no customers are present, the barber sleeps.

 If customers arrive and seats are available, they wait.

 If all seats are full, new customers leave.

Challenges:

 Prevent deadlock where no one gets served.

 Ensure fairness so no customer starves waiting too long.

Solution: Semaphores can manage customer queues, chair availability, and barber
activity.

Deadlocks
A deadlock is a specific situation in computing and multitasking where a group of
processes is permanently blocked because each process is holding a resource and
waiting for another resource held by another process in the group.

Think of it like a four-way traffic jam where every car is waiting for the one in front of it
to move, but nobody can move because the intersection is blocked.

1. Necessary and Sufficient Conditions

For a deadlock to occur, the following four conditions (known as the Coffman Conditions)
must hold simultaneously. if any one of these is prevented, a deadlock cannot occur.

 Mutual Exclusion: At least one resource must be held in a non-shareable mode (only
one process can use it at a time).

 Hold and Wait: A process must be holding at least one resource and waiting to acquire
additional resources currently held by other processes.

 No Preemption: Resources cannot be forcibly taken from a process; they must be

released voluntarily.

 Circular Wait: A closed chain of processes exists such that each process holds at least
one resource needed by the next process in the chain.

2. Deadlock Prevention
 Prevention works by ensuring that at least one of the Coffman conditions never happens.
It is a proactive, "strict" approach.

 Eliminate Mutual Exclusion: Difficult for hardware (like printers), but easier for read-
only files.

 Eliminate Hold and Wait: Require processes to request all required resources at the
start. This leads to low resource utilization.

 Allow Preemption: If a process is denied a new request, it must release all its current
resources so others can use them.

 Prevent Circular Wait: Impose a strict ordering of resource types (e.g., Resource A must
always be requested before Resource B).

Deadlock Avoidance : Banker’s Algorithm

To understand Deadlock Avoidance, think of it as a "cautious manager." Unlike
prevention (which sets rigid rules), avoidance looks at every request and asks: "If I give
you this resource, do I still have a path to finish everyone else's work?"

The Banker's Algorithm is the most famous method for doing this.

1. Core Logic: The "Safe State"

The algorithm's primary goal is to keep the system in a Safe State.

 Safe State: There exists at least one sequence (a "Safe Sequence") where every process
can get its maximum resources, finish its job, and return the resources to the pool.

 Unsafe State: There is no guaranteed sequence to finish all processes. This does
not mean a deadlock has occurred yet, but the system can no longer guarantee one
won't happen.

2. The Data Structures

To make a decision, the Banker's Algorithm tracks four pieces of information:

Structure Description
 Available A vector representing how many units of each resource type are
currently free.

Max A matrix showing the maximum demand of each process for each
resource.

Allocation A matrix showing the resources currently assigned to each process.

Need A matrix (

) showing how much more each process might request.

3. How the Algorithm Works

When a process requests resources, the Banker performs a Resource-Request
Algorithm simulation:

1. Check Request: If the request is greater than the process's remaining Need or the
system's Available resources, the request is denied or delayed.

2. Pretend to Allocate: The Banker "pretends" to grant the resources by updating the state:

1.

2.

3.

3. Safety Check: The Banker runs a Safety Algorithm on this "pretend" state.

4. Decision:

1. If the state is Safe, the resources are actually granted.

2. If the state is Unsafe, the process is made to wait, and the "pretend" allocation is rolled
back.
 4. Example: A "Safe" vs. "Unsafe" Decision
Imagine a system with 10 Total Units of a resource (e.g., RAM blocks).

Current Snapshot:

Process Max Allocated Need

9 2 7

4 2 2

7 3 4

 Total Allocated:

 Available:

Scenario:

requests 1 more unit. Should we grant it?

1. Pretend: Give

the unit. Available becomes 2.

Allocation becomes 3, and its Need becomes 1.

2. Safety Test:

1. Can we finish

? Yes, it needs 1 and we have 2.

2. When

finishes, it releases all its resources (

). New Available =

3. Can we finish

? Yes, it needs 4 and we have 5.

4. When

finishes, it releases its 3 units. New Available =

5. Can we finish

? Yes, it needs 7 and we have 8.

3. Result: Since a sequence exists (

), the state is Safe. The request is Granted.

5. Limitations
While theoretically sound, the Banker's Algorithm is rarely used in general-purpose OSs
(like Windows or Linux) because:
 It requires processes to know their Maximum Need in advance, which is almost
impossible for modern software.

 The number of resources and processes must remain fixed.

 It is computationally expensive to run the safety check every time a resource is

requested.

Deadlock Detection and Recovery

If a system does not use prevention or avoidance, it must periodically check for
deadlocks and fix them.

Detection
The system maintains a Resource Allocation Graph (RAG).

 In systems with a single instance of each resource type, a cycle in the graph indicates a
deadlock.

 In systems with multiple instances, a more complex algorithm (similar to Banker's) is

used to see if any process can still finish.

Recovery
Once a deadlock is detected, the system must break it using one of two methods:

1. Process Termination:

 Abort all deadlocked processes (drastic).

 Abort one process at a time until the cycle is broken (based on priority or time spent).

2. Resource Preemption:

 Selecting a victim: Decide which process to take resources from based on cost.
 Rollback: Return the process to a previous "safe state" and restart it from there.
 Starvation: Ensure the same process isn't always picked as a victim.