Process Communication and

Synchronization
Chapter 3
Objective
3.1 Principles of concurrency, race condition, critical region
3.2 Mutual exclusion, semaphores, and mutex
3.3 Message passing and monitors
3.4 Classical problems of synchronization: Readers-writers problem, producer-
consumer problem, dining philosopher problem
3.5 Deadlock: Prevention, ignorance, avoidance, detection and recovery
Concurrency
Concurrency in operating systems refers to the capability of an OS to handle
more than one task or process at the same time, thereby enhancing efficiency
and responsiveness.
Concurrency can be achieved through multithreading or multi-processing
whereby more than one process or threads are executed simultaneously or in
an interleaved fashion.
The running process threads always communicate with each other through
shared memory or message passing.
Concurrency results in sharing of resources resulting in problems like
deadlocks and resources starvation.
Benefit of Concurrency
Resource Sharing and Performance
In concurrency, multiple programs run simultaneously while sharing system
resources such as the CPU and memory.

This optimizes system performance, reduces idle time, and enhances

application responsiveness, especially in multitasking environments.

Concurrency helps in techniques like coordinating execution of processes,

memory allocation and execution scheduling for maximizing throughput.
Continued
1. Physical resource Sharing: Multiuser environment since hardware
resources are limited
2. Logical resource Sharing: Shared file (same piece of information)
3. Computation Speedup: Parallel execution
4. Modularity: Divide system functions into separation processes
Importance and Management
Proper handling of concurrency is essential to avoid issues like deadlocks
and race conditions.
It ensures smooth execution of tasks by coordinating
● process execution,
● memory allocation, and
● scheduling,
ultimately maximizing system throughput.
Independent Process vs Cooperating Process
Independent Processes Cooperating Processes

1. Its state is not shared with any 1. Its state is shared along other
other process. processes.
2. The result of execution depends 2. The result of the execution depends
only on the input state. on relative execution sequence and
3. The result of the execution will cannot be predicted in
always be the same for the same advanced(Non-deterministic).
input. 3. The result of the execution will not
4. The termination of the always be the same for the same
independent process will not input.
terminate any other. 4. The termination of the cooperating
process may affect other process.
Process Operation
Process Creation Process Termination

A parent process and then children of A child process can be terminated in the
that process can be created. following ways:
When more than one process is created A parent may terminate the execution of
several possible implementations exist. one of its children for a following reasons:
● Parent and child can execute ● The child has exceeded its allocation
concurrently. resource usage.
● The Parents waits until all of its ● The task assigned to its child is no
children have terminated. longer required.
● The parent and children share all ● If a parent has terminated than its
resources in common. children must be terminated.
● The children share only a subset of
their parent's resources.
Principles of Concurrency
Concurrency means multiple processes are in progress during the same time
period. Processes can execute concurrently in one of two ways:

1. Interleaved execution → On a single CPU (time sharing)

2. Overlapped execution → On multiple CPUs (true parallelism)
Interleaved Processes vs Overlapping Process
Interleaving occurs when multiple processes execute one Overlapping occurs when multiple
after another in small time slices, but not truly at the processes execute truly at the same time.
same time.
● Happens in single-CPU systems. Happens in multi-core or multiprocessor
● The CPU switches rapidly between processes. systems.
● Creates the illusion of simultaneous execution. Different CPUs/cores execute different
How it Works: Process A executes for a short time → processes simultaneously.
CPU switches to Process B →
Example
Then back to Process A → and so on.
Example 1. Core 1 runs Process A
In a single-core system: 2. Core 2 runs Process B
● While typing in Word, Both run at the exact same time
● Music is playing, Key Point
● Browser is downloading.
They appear simultaneous, but the CPU is switching
More than one process is physically
between them. executing at the same moment.
Do these process interact?
When multiple processes run concurrently, do they interact or not?
Both interleaved and overlapped processes can be
viewed as examples of concurrent processes, they
both present the same problems.
The relative speed of execution cannot be
predicted. It depends on the following:

● The activities of other processes

● The way operating system handles
interrupts
● The scheduling policies of the operating
system
Problems in Concurrency
● Sharing global resources: Sharing of global resources safely is difficult. If two processes both
make use of a global variable and both perform read and write on that variable, then the order
in which various read and write are executed is critical.
● Optimal allocation of resources: It is difficult for the operating system to manage the
allocation of resources optimally.
● Locating programming errors: It is very difficult to locate a programming error because
reports are usually not reproducible.
● Locking the channel: It may be inefficient for the operating system to simply lock the channel
and prevents its use by other processes.
Advantages of Concurrency
● Running of multiple applications: It enable to run multiple applications at the same time.
● Better resource utilization: It enables that the resources that are unused by one application
can be used for other applications.
● Better average response time: Without concurrency, each application has to be run to
completion before the next one can be run.
● Better performance: It enables the better performance by the operating system. When one
application uses only the processor and another application uses only the disk drive then the
time to run both applications concurrently to completion will be shorter than the time to run
each application consecutively.
Drawbacks of Concurrency
● It is required to protect multiple applications from one another.
● It is required to coordinate multiple applications through additional mechanisms.
● Additional performance overheads and complexities in operating systems are required for
switching among applications.
● Sometimes running too many applications concurrently leads to severely degraded
performance.
Issues of Concurrency
● Non-atomic: Operations that are non-atomic but interruptible by multiple
processes can cause problems.
● Race conditions: A race condition occurs of the outcome depends on which of
several processes gets to a point first.
● Blocking: Processes can block waiting for resources. A process could be blocked for
long period of time waiting for input from a terminal. If the process is required to
periodically update some data, this would be very undesirable.
● Starvation: Starvation occurs when a process does not obtain service to progress.
● Deadlock: Deadlock occurs when two processes are blocked and hence neither can
proceed to execute.
Race Condition
A critical section is a code segment that can be accessed by only one process at a time. The
critical section contains shared variables that need to be synchronized to maintain the
consistency of data variables.

A race condition is a situation that may occur inside a critical section. This happens when
the result of multiple process/thread execution in the critical section differs according to
the order in which the threads execute.
Two threads are incrementing the
same shared variable.

Because count++ is not atomic: It actually performs:

1. Read value
2. Add 1
3. Write back

If two threads execute this at the same time, they may

overwrite each other’s update. This is called a Race
Condition —When multiple threads access shared
data and the final result depends on execution
timing.
Critical Section
A critical section is a segment of code in an operating system that
accesses shared resources (memory, files, variables) and must be
executed by only one process/thread at a time to prevent data
inconsistency.

Proper synchronization, such as mutual exclusion via mutexes

or semaphores, is required to prevent race conditions.
Requirements for Solution to Critical Section Problem
A critical section is code that accesses shared resources (variables, files, etc.). The critical section problem
requires a solution to synchronize different processes. The solution must satisfy:

1. Mutual Exclusion: Mutual exclusion means only one process can be inside the critical section at a time. If
other processes require the critical section, they must wait until it is free.

If Pi is executing in its critical section, no other processes can execute in their critical sections: The
resources involved are [Link] least one resource must be held in a non-shareable
mode i.e, only one process at a time claims exclusive control of the resource. If another process
requests that resource, it must be delayed until the resource is released.

2. Progress: Progress means that if a process is not using the critical section, it should not prevent other
processes from accessing it. In other words, any process can enter the critical section if it is free.
If the critical section is empty but processes are waiting to use it, only the processes that are actually
ready and waiting can compete for it. This group must choose one of them to go next without stalling or
waiting forever.

3. Bounded Waiting: Bounded waiting means that each process must have a limited waiting time and
should not wait endlessly to access the critical section. There exists a limit on the number of times
that order processes are allowed to enter critical section after a process has requested entry and before
that request is granted.
Solution to Critical Section Problem
A critical section is a code segment where a process accesses the section and then exits it, releasing the resources.

Synchronization Mechanisms

To ensure that only one process executes the critical section at a time, process synchronization mechanisms such as
semaphores are used. A semaphore is a variable that determines whether a resource is available and provides mutual
exclusion to shared resources.

Entry Protocol

When a process enters the critical section, it must first request access to the semaphore or mutex associated with the
section. If the resource is available, then the process can proceed to execute the critical section. If the resource is not
available, then the process must wait until it is released by the process currently executing the critical section.

Exit Protocol

When a process finishes executing the critical section, it releases the semaphore or mutex, allowing another process to enter
the critical section if needed.
Mutual Exclusion
Mutual exclusion ensures that only one process at a time can enter its critical section and access shared
resources.

● When more than one process wants to access or update a shared resource—meaning they want to enter their
critical sections—if they execute simultaneously, a race condition may occur, leading to inconsistent results. In
order to avoid race conditions, the process synchronization technique should satisfy the mutual exclusion
criteria.

In the critical section, if the executing process is interrupted by another process that updates the shared
resource in a different way, a race condition occurs and the value of the shared resource becomes invalid.

The Solution: Synchronization Mechanisms

● Synchronization mechanisms are techniques that ensure processes are executed in such a manner that
the state of the system and common data structures remain consistent at all times.
● In order to avoid race conditions, synchronization techniques make sure that the instructions of the
operations in the critical section are executed as a single unit—in other words, in an atomic manner.
● Atomicity is guaranteed through mutual exclusion, through which only one process can execute in the
critical section at a particular time.
Requirements for Mutual Exclusion
For mutual exclusion to work properly, it must satisfy these four conditions:

1. Only one process can enter its critical section at a particular time.
2. A process is permitted to execute in its critical section only for a bounded
time.
3. No process that is not in its critical section can prevent another process from
entering its critical section.
4. No process must wait indefinitely to enter its critical section.
Techniques for Achieving Mutual Exclusion
Locks and Mutex

● Synchronization primitives called locks or mutex (short for mutual exclusion) are implemented to maintain
consistency of the value or status of shared resources.
● There are two possible states for a lock: locked and unlocked.
● An operating system or process must obtain the lock before being able to utilize the shared resource.
● The requesting process will be restricted as long as the lock has been released if it has already been locked by a
different thread.

Semaphores

A semaphore is an advanced synchronization tool that uses two atomic operations: wait() and signal(). The wait() instruction
is used in the entry section to gain access to the critical section, while the signal() operation is used to release control of the shared
resource.

Semaphores can be of two types:

1. Binary semaphores
2. Counting semaphores
In a counting semaphore, when a thread needs to enter the critical area, semaphores keep track of a counter and decrease it.
The running thread becomes immobilized if the counter decreases, signifying that the critical portion has become in use.
Contd..
Atomic Operations
Without using locks or semaphores, certain processors offer atomic operations that may be employed to
guarantee mutual exclusion. Atomic operations are advantageous for modifying shared parameters
because they are unbreakable and can't be stopped. A property of a variable may only be altered using
atomic compare-and-swap (CAS) procedures—for instance, if the value of the variable coincides with the value
that is anticipated.

Software-Based Techniques
Mutual exclusion can be achieved using a variety of software-based algorithms and strategies, including:
● Peterson's algorithm
● Dekker's algorithm
● Lamport's bakery algorithm
These techniques guarantee that only a single thread at one point is able to utilize the critical section by
combining factors, flags, and busy-waiting.
2. Lock
- Locks ensure that only one process at a time can enter the critical section.
- A process must “acquire” the lock before entering, and “release” it after exiting.
- If another process tries to enter while the lock is held, it must wait.

Locks can be implemented in two ways:

a. Software-Based Locks
b. Hardware-Based Locks
Software-Based Locks
Software-based locks are implemented using algorithms that rely on shared variables (like flags, turn
variables, or ticket numbers) to coordinate access to the critical section. These solutions try to ensure
mutual exclusion without depending on hardware instructions.

Some well-known algorithms are:

● Peterson’s Algorithm: works well for exactly two processes.

● Dekker’s Algorithm: One of the earliest algorithms for mutual exclusion. Works for exactly two
processes using flags and a turn variable.
● Bakery Algorithm: works for multiple processes, inspired by “take-a-number” systems in
shops.
Problems of Software Locks:
a. Require busy waiting: the CPU wastes cycles looping while checking conditions.
b. Peterson’s Algorithm is elegant, but only practical for two processes. Extending it to many
processes (like Bakery Algorithm) makes the code complex.
c. Not suitable for modern multiprocessor systems, where hardware-level atomicity is
required.

Because of these inefficiencies, hardware support for locks was introduced.

Hardware-Based Locks
● Modern CPUs provide special atomic instructions that make lock implementation easier and
faster.
● It works in multiprocessor systems, because the atomic instruction is enforced by the CPU’s
memory system.

What does "atomic" mean here?

● Atomic means indivisible operation.

● Once an atomic instruction starts, it finishes completely before anything else (like another
process or interrupt) can occur.
● This ensures that no two processes can modify the same lock at the same time.
Importance of Atomic Operations
Without atomic operations, two processes could:

● Check the lock at the same time,

● Both see it as “free”,
● Both enter the critical section leading to a race condition.

How CPUs solve this:

CPUs include hardware-level instructions such as:

● Test-and-Set (TSL): Tests the lock’s old value and sets it to “locked” in one unbreakable step.
● Compare-and-Swap (CAS): Compares a memory value with an expected value and, if equal, swaps it with a new
value atomically.
● Spinlocks: Built using TSL or CAS; processes “spin” (busy wait) until the lock becomes free. Very fast for short
waits but wastes CPU cycles for long waits.
Limitations (why OS-based solutions are still needed):

● Processes may still use busy waiting, which wastes CPU cycles.
● No fairness guarantee one process might keep winning while others starve.
● Only solves basic mutual exclusion, not higher-level needs like sleeping, waking, or scheduling.
2.1 Mutex (Mutual Exclusion Lock)

Only one process is allowed to use a resource. It has a lock. If a process enters the shared resource, lock is
acquired and after finishing the task, the lock is release.
Components used in Mutex Locks
1. Mutex variable - which holds the state of a lock(If lock is available or not)
2. Lock Acquisition: Every process or thread will be requesting for a lock to utilize the shared resources. If lock is
available, the lock is granted else the process/thread will be in waiting state until the lock is released.
3. Lock Release: After completion of utilizing shared resource, then lock will be released.
A mutex is a higher-level lock abstraction often built on top of hardware primitives like spinlocks.
A spinlock is a synchronization mechanism in which a thread repeatedly checks for a lock in a loop until it
becomes available, instead of being blocked or put to [Link] and are widely used in thread libraries (e.g.,
Pthreads) and operating systems.
3. Semaphores and Monitors
Locks (software or hardware) solve the basic problem of mutual exclusion, but they still
have limitations:
● They rely on busy waiting, wasting CPU cycles.
● They don’t provide higher-level management like blocking, waking up, or handling
multiple conditions.

To address this, Operating Systems introduced more powerful synchronization tools:

● Semaphores and
● Monitors.

These are built on top of lock-based mechanisms but provide extra control, safety and ease of use.
Semaphore
Semaphores proposed by Edsger Dijkstra, is a technique to manage concurrent processes by using a simple integer value, which is known as semaphore.

Semaphore is simply a variable which is non-negative and shared between threads. This variable is used to solve the critical section problem and to achieve process synchronization in the
multiprocessing environment.

A semaphore is an integer variable that, apart from initialization, is accessed only through two standard atomic operations:

● wait() (decrement, block if < 0 - to test),

● signal() (increment, wake one waiting process - to increment)

Removes busy waiting by blocking processes when resources are unavailable.

A semaphore is a variable used to control access to shared resources.

● Can allow more than one process to access the resource simultaneously (counting semaphore).
● Can be binary (0 or 1), similar to a mutex.
 P - denotes wait - test if there is any other process in the critical
section.
wait(): S - semaphor that is share resource, it is integer variable
when S is less than equal to 0, there is semicolon right after while,
no operation, but as long as condition is true, control will be inside
P(Semaphore S){ the while loop and not break the operation as long as the condition
does not become false.
while(S <= 0)
If S is greater than 0 - come out of while loop - decrement value of S.
; //no
operation ● This code signifies - S is shared. When one process wants to
enter critical section, S will take care of who should access the
S - -;
resource.
} ● If S is less than 0 - some process is already in critical section, no
other process is allowed in critical section. If
● S is greater than 0 then process will come out of loop,
decrement value of S and enter the critical section. Decrement
is necessary to let other process know, the condition will either
be true or false for that process.
signal()
V(Semaphore S){

S++;

}
Counting Semaphore
A semaphore that can hold any non-negative integer value, not just 0 and 1.
Counting Semaphore Example
Initially: S = 3

P1 calls wait(S) → S = 2 // P1 gets printer, 2 left

P2 calls wait(S) → S = 1 // P2 gets printer, 1 left
P3 calls wait(S) → S = 0 // P3 gets printer, 0 left
P4 calls wait(S) → S = -1 // no printer left, P4 BLOCKS
P5 calls wait(S) → S = -2 // no printer left, P5 BLOCKS
P6 calls wait(S) → S = -3 // no printer left, P6 BLOCKS
// P1 finishes printing
P1 calls signal(S) → S = -2 // S <= 0, so wake up P4
P4 gets printer and prints

// P2 finishes printing
P2 calls signal(S) → S = -1 // S <= 0, so wake up P5
P5 gets printer and prints

// P3 finishes printing
P3 calls signal(S) → S = 0 // S <= 0, so wake up P6
P6 gets printer and prints

// All done
S = 3 again after all signal()
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
Used when multiple instances of a resource exist.
The semaphore value can range over an unrestricted domain (0 to N).
Example: Managing access to a pool of 5 printers.

2. Binary Semaphore
Special case of counting semaphore with only two values: 0 and 1.
Works like a lock: either the resource is free (1) or busy (0).
Example: Managing access to a single critical section.
Mutex lock
Working of Semaphore
A semaphore works by maintaining a counter that controls access to a specific resource, ensuring
that no more than the allowed number of processes access the resource at the same time.

To achieve synchronization, every critical section of code is surrounded by two operations- Wait (P
operation) and Signal (V operation) that are discussed above.

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:
Counting Semaphore
The semaphore value can range over an unrestricted domain (0 to N). A counting semaphore is a
synchronization tool that uses a counter to manage access to a shared resource. Unlike binary semaphores,
which only have two states (0 and 1), counting semaphores can have a range of values that represent the
number of available resources.

The Counter Mechanism

Counting semaphores use an integer counter that keeps track of available resources. The value of the counter
indicates:
● If the counter is greater than 0, resources are available for use.
● If the counter is 0, all resources are currently in use.
● If the counter is negative, it may indicate the number of processes waiting for the resource (depending on
implementation).

The Operations
A counting semaphore uses two atomic operations:
wait() or P() - Decreases the counter when a process needs to acquire the resource
signal() or V() - Increases the counter when a process releases the resource
The Process Flow
When a thread needs to enter the critical area, the counting semaphore does
the following:
● Checks the counter - It looks at the current value of the counter
● Decreases the counter - It reduces the counter value by one
● Evaluates the result - If the counter decreases to a value that indicates
all resources are in use, the running thread becomes immobilized
● When Resources Are Unavailable: If the counter decreases and reaches
zero (or becomes negative), this signifies that the critical portion or
resource has become fully occupied. In this case:
■ The requesting thread is blocked and put into a waiting state
■ The thread is added to a queue of waiting processes
■ The thread will remain blocked until another thread releases the resource
Disadvantages of Semaphores
While semaphores are powerful synchronization tools, they come with several significant disadvantages that can make them challenging to use correctly and safely in
concurrent programming environments.

1. Busy Waiting (Spinlock)

What is Busy Waiting?

When a process cannot enter its critical section because the semaphore is not available, it continuously loops and checks the semaphore value without performing
any useful work.

The Problem

Wastes CPU cycles - The processor keeps executing empty checks

Reduces system performance - Other processes could be using those CPU cycles productively
Causes unnecessary power consumption - Especially problematic in mobile and embedded systems
Example

c
while (semaphore <= 0) {
// Continuously checking, doing nothing useful
2. Deadlock
Deadlock occurs when two or more processes are waiting indefinitely for each other to release resources that
they need. Each process holds a resource and waits for another resource held by another process.

The Problem
Complete system halt - Affected processes stop making progress
Difficult to detect - Deadlocks may not be immediately obvious
Requires external intervention - Often needs system restart or manual killing of processes

Example of Deadlock
Process A: wait(S) → wait(Q) → critical section → signal(Q) → signal(S)
Process B: wait(Q) → wait(S) → critical section → signal(S) → signal(Q)

If Process A executes wait(S) and Process B executes wait(Q) simultaneously:

- Process A holds S, waiting for Q
- Process B holds Q, waiting for S
- Both wait forever → DEADLOCK
Starvation
Starvation happens when a process waits indefinitely to enter its critical section while other
processes continuously get access.

The Problem
● Unfair resource allocation - Some processes never get to execute
● Priority inversion - Lower priority processes might get access while higher priority ones
wait
● Difficult to guarantee - No built-in mechanism in basic semaphores to ensure fairness
● Causes Improper queue management
● Processes with higher priority continuously acquiring the semaphore
● Poorly designed signaling mechanisms
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.

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.
class
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
It refers to means of communication between
- Different thread with in a process .
- Different processes running on same node.
- Different processes running on different node.

In this a sender or a source process send a message to a non receiver or destination process.
Message has a predefined structure and message passing uses two system call: Send and Receive

send(name of destination process, message);

In this calls, the
receive(name of source process, message); sender and
receiver
processes
address each
other by names.
Mode of Communication
Mode of communication between two process can take place through two
methods

1) Direct Addressing
2) Indirect Addressing
Direct Addressing
In this type that two processes need to name other to communicate. This become
easy if they have the same parent.
Example
If process A sends a message to process B, then
send(B, message);
Receive(A, message);
By message passing ,a link is established between A and B. Here the receiver knows
the Identity of sender message destination. This type of arrangement in direct
communication is known as Symmetric Addressing.
Contd..
Another type of addressing known as asymmetric addressing where receiver
does not know the ID of the sending process in advance.
Indirect Addressing
In this message send and receive from a mailbox. A mailbox can be abstractly viewed as an object into which
messages may be placed and from which messages may be removed by processes. The sender and receiver
processes should share a mailbox to communicate.

The following types of communication link are possible through mailbox.

- One to One link: one sender wants to communicate with one receiver. Then single link is established.

- Many to Many link: Multiple Sender want to communicate with single [Link] in client server
system, there are many crying processes and one server process. The mailbox is here known as PORT.

- One to Many link: One sender wants to communicate with multiple receiver, that is to broadcast message.

- Many to many: Multiple sender want to communicate with multiple receivers.

Classic Problems of Synchronization
1. Readers-writers problem
2. Producer-consumer problem
3. Dining philosopher problem
Producers Consumers Problem
The problem describe two processes, User and Consumer, who share a
common fixed size buffer.
Producer consumer problem also known as the "Bounded Buffer Problem"
is a multi-process synchronization problem.

Producer: The producer's job is to generate a bit of data, put it into the
buffer and start again.

Consumer: The consumer is consuming the data(i.e remaining it from the

buffer) one piece at a time.

● If the buffer is empty, then a consumer should not try to access the
data item from it.

● Similarly, a producer should not produce any data item if the buffer is
full.
Bounded Buffer Problem — Three Semaphore Solution
Producer Consumer
do{ do{
produce(item) wait(full) // block if buffer empty, if full>0
wait(mutex) // acquire lock
wait(empty) // block if buffer full, if empty > 0 there
are empty slots, empty = 0 no slots
wait(mutex) // acquire lock
item = buffer[out]
out = (out + 1) % N
buffer[in] = item
in = (in + 1) % N signal(mutex) // release lock
//here empty is decremented signal(empty) // notify producer
signal(mutex) // release lock
signal(full) // notify consumer, here full is //INCREMENT EMPTY SINCE WE TOOK AN ITEM
incremented }while (true)
}while (true)
Dining Philosophers Problem
The Dining Philosophers problem is a classic synchronization problem that
involves a certain number of philosophers sitting at a round table.

Each philosopher does only two things:

• Thinks
• Eats (by using a fork)

There are a number of forks placed between the philosophers.

For a philosopher to eat, they need two forks, one from the left and one
from the right.
The problem involves designing a solution that avoids deadlock and ensures
that no philosopher is starved (i.e., no philosopher should be prevented from
eating indefinitely)
 Dining Philosophers Problem:
When a philosopher gets hungry he tries to pick up the two forks
that are closest to him(left & right).

A philosopher may pick up only one fork at a time. One

cannot pick up a fork that is already in the hand of a
neighbour.

When a philosopher thinks, he does not interact with his

colleagues..

When a hungry philosopher has both his forks at the same time, he eats without releasing his forks. When he has
finished eating, he puts down both of his forks and starts thinking again.

Key challenges:
Deadlock: A situation where all philosophers hold one fork and wait for the other, causing a deadlock.

Starvation: A philosopher could potentially never get both forks and never eat
Dining Philosophers Problem:

Solutions:
• Resource hierarchy: Philosophers pick up forks in a specific order
(e.g., pick the lower-numbered fork first).

• Using semaphores or mutexes to control access to the forks.

Using semaphores
• Step 1: We initialize semaphores for each fork, where each fork is
available initially.
• Step 2: We initialize a mutex semaphore to control mutual exclusion
when philosophers pick up and put down forks.
• Step 3:Philosophers repeatedly think, then attempt to pick up their
left and right forks.
Once they acquire both forks, they eat, and then release the forks
afterward.
• Step 4: This process continues infinitely for each philosopher.
 Although this solution guarantees that no
do: two neighbors are eating simultaneously, it
think() // philosopher is thinking
could still create a deadlock.
wait(fork[i]) // pick up LEFT fork
wait(fork[(i+1) % 5]) // pick up RIGHT fork Suppose that all five philosophers become
hungry and each grabs their left fork. All
eat() // eating (has both forks) the elements of chopstick will now be
equal to 0.
signal(fork[i]) // put down LEFT fork
signal(fork[(i+1) % 5]) // put down RIGHT fork
When each philosopher tries to grab his
while (true) right chopstick, he will be delayed forever.
Using semaphores
1. Initialize an array of semaphores `forks[0...n-1]` where each semaphore is
initialized to 1, indicating the fork is available.
2. Initialize a semaphore `mutex` to 1, for mutual exclusion.
3. For each philosopher `i`: - Repeat forever:
a. Think (indicates the philosopher is not using any resources).
b. Acquire the left fork `forks[i]`.
c. Acquire the right fork `forks[(i + 1) % n]`.
d. Eat (indicates the philosopher is using both forks).
e. Release the left fork `forks[i]`.
f. Release the right fork `forks[(i + 1) % n]`.
4. The process repeats until the simulation ends.
Possible remedies to avoid deadlocks
1 — Allow at most four philosophers to be sitting
simultaneously at the table.
2 - Allow a philosopher to pick up his forks only if both
forks are available(to do this he must pick them up in a
critical section)
3 - Use an asymmetric solution; that is, an odd philosopher
picks up first his left chopstick and then his right fork,
whereas an even philosopher picks up his right fork and
then his right fork.
[Link]-Writers Problem:
The Readers-Writers Problem is a classic synchronization issue in operating systems
that involves managing access to shared data by multiple threads or processes. The
problem addresses the scenario where:
1. Readers: Multiple readers can access the shared data simultaneously without
causing any issues because they are only reading and not modifying the data.
2. Writers: Only one writer can access the shared data at a time to ensure data
integrity, as writers modify the data, and concurrent modifications could lead to
data corruption or inconsistencies.
Challenges of the Reader-Writer Problem
The challenge now becomes how to create a synchronization scheme such that the
following is supported:
1. Multiple Readers: A number of readers may access simultaneously if no writer is
presently writing.
2. Exclusion for Writers: If one writer is writing, no other reader or writer may
access the common resource.
Solution of the Reader-Writer Problem
There are two fundamental solutions to the Readers-Writers problem:
• Readers Preference: In this solution, readers are given preference
over writers. That means that till readers are reading, writers will
have to wait. The Writers can access the resource only when no
reader is accessing it.
• Writer’s Preference: Preference is given to the writers. It simply
means that, after arrival, the writers can go ahead with their
operations; though perhaps there are readers currently accessing the
resource.
 Solution of Readers-Writers Problem (Using
Semaphore)

Writer Process

Do{
/*writer request for critical section*/

wait(wrt) // block if any reader or writer active

write(data) // exclusive access to shared resource

signal(wrt) // release, allow readers or next writer

}while (true)
 Solution for Readers:
do{
wait(mutex) // lock to safely update read_count, so that no two processes will update the read
//count at the same time.
read_count++
if read_count == 1: //at least one reader trying to read database

wait(wrt) // first reader blocks all writers, it will acquire write semaphore

signal(mutex) // unlock read_count

/*current reader performs reading here*/

read(data) // multiple readers can be here at once

wait(mutex) // lock to safely update read_count

read_count--

if read_count == 0:
signal(wrt) // last reader releases writers
signal(mutex) // unlock read_count
}while (true)