CHAPTER-3: Process Communication and Synchronization

 Principles of Concurrency
 Critical Region
 Race Condition
 Mutual Exclusion
 Semaphores and Mutex
 Message Passing
 Monitors
 Classical Problems of
Synchronization: ₋ Readers-
Writers Problem,
₋ Producer Consumer Problem,
₋ Dining Philosopher problem
-Sleeping Barber Problem

Principles of Concurrency
 The principle of concurrency refers to the execution of multiple processes during
the same time period.
 Since it is not practical to have a separate processor for every process, the operating
system manages the CPU by switching it from one process to another.
 Each process is allowed to execute for a small fixed amount of time called a time
slice (time quantum).
 After that time expires, the CPU is allocated to another process, giving the
appearance that multiple processes are executing simultaneously.

The multiple processes executing in the computer system using principle of

concurrency can be divided into two types:
• Independent process is a process that cannot affect or cannot be
affected by the execution of another process. The independent
process does not share any information or data with other processes.
They execute completely independently.
• Cooperating process is a process that can affect or can be affected
by the execution of another process. It shares data with other
 process. The cooperating processes require some mechanism to
exchange data or pass information to each other.
The cooperating processes have following benefits:

 Information Sharing:
Processes can share the same information when needed.
Example: Copying and pasting data between programs.
 Computation Speed:
A large task can be divided into smaller tasks and executed at the same time, which
increases the speed and performance of the system.
 Modularity:
The operating system can be divided into smaller parts called threads, making the
system easier to manage and improving performance.

Problems in Concurrency

1. Sharing Global Resources:

It is difficult to safely share global resources. If two processes change the same
variable at the same time, it may cause incorrect results.
2. Optimal Allocation of Resources:
It is hard for the operating system to allocate resources efficiently among many
processes.
3. Locating Programming Errors:
Errors (bugs) are difficult to find because the program may behave differently each
time it runs.
4. Locking Resources:
Locking shared resources for safety can slow down the system performance.

Inter process Communication:

• Inter-Process Communication (IPC) is a mechanism through which
processes can communicate and share data with each other. It helps
in synchronizing their actions and managing access to shared
resources to avoid conflicts.
• There are three issues here:
 Passing Information: How one process can send or share data with another process.
 Avoiding Conflicts: Making sure processes don’t interfere with each other.
Example: Two people trying to book the last seat on a flight at the same time.
  Process Dependencies: Some processes depend on others.
Example: One process creates data, and another prints it — printing must wait until
data is ready.
IPC allows the processes running on the single system to communicate with
other. Two basic communication model for providing IPC are:
₋ Shared Memory
₋ Message Passing

1. Shared Memory:
• In Inter process communication using shared memory, communicating
processes need to establish a region of shared memory.
• A process creates the shared-memory region in its own address space.
Other processes communicate by attaching the address space to their
own address space.
• Processes communicate by reading and writing data in the shared area.
Operating system does not have any control over data or location. It is
only determined by the processes.
 Way of Communication in Shared Memory
• Suppose P1 and P2 are executing simultaneously and they share some
resources or use some information from other process, P1 generate
information about certain computations or resources being used and
keeps it as a record in shared memory.
• When P2 need to use the shared information, it will check in the record
stored in shared memory and take note of the information generated
by P1 and act accordingly.
• Processes can use shared memory for extracting information as a
record from other process as well as for delivering any specific
information to other process.

2. Message passing:
 Message passing is a way for processes to communicate by sending and receiving
messages without sharing the same memory.
 It is useful in distributed systems, where processes may run on different computers
connected by a network.

• A message passing facility provides at least two operations:

(i) Send(message, destination) or send (message)
(ii) Receive(message, host) or receive (message)

Two can communicate with each other by sending and receiving

messages. This communication take place by establishing a
communication link these.
Shared Memory VS Message Passing
Shared Memory Message Passing
1. A region of memory is shared 1. Messages are shared among the
among the processes. processes.

2. Faster than message passing 2. Useful for exchanging small

systems amount of data.
3. Only requires to establish shared 3. Require more time consuming
memory regions. task of kernel intervention.

Race Condition
When multiple processes run simultaneously and try to change the same data, the result
may become incorrect or unpredictable.
Example:
• Consider two cooperating processes P1 and P2 that updates the balance
of account in a bank.
Process P1 Process P2
Read Balance Read Balance
Balance= Balance + 1000 Balance= Balance -400
Table: Code Segment for processes P1 and P2
• Suppose that the balance is initially 5000, then after the execution of
both P1 and P2, it should be 5600. The correct result is achieved if P1
and P2 execute one by one in any order either P1 is followed by P2 or
P2 followed by P1.
• However if the instructions of P1 and P2 are interleaved arbitrarily, the
balance may not be 5600 after the execution of both P1 and P2. One
possible interleaving sequence for the executions of instructions of P1
and P2 is given in below table.
Process P1 Process P2 Balance
Read balance 5000
Read balance 5000
Balance= Balance + 6000
1000
Balance = Balance - 4600
400
 • The above interleaved sequence results in an inconsistent balance that
is 4600. If the order of the last two instructions is interchanged, the
balance would be 6000 (again, inconsistent). A race condition happens
when several processes use the same data at the same time, and the final result
depends on the order in which they access the data.

Mutual Exclusion:
 To prevent race conditions, we use mutual exclusion.
 This means if one process (P1) is using shared data, no other process can use it until
P1 is done.
 Without mutual exclusion, shared data can become inconsistent or wrong.
• Mutual exclusion ensures that if one process is working on a critical
section (important part of code), no other process can work on it at the
same time.
• It is the responsibility of operating system to assure that no more than
one process is in its critical section simultaneously.

Critical Section
 A critical section (or critical region) is the part of a program where shared memory
or shared data is used.
 Only one process can run in its critical section at a time, and all other processes
must wait their turn.
 do {
 entry section
 critical section
 exit section
 remainder section
 } while (true);\

Basic structure:

 Mutual Exclusion:
Only one process can be in its critical section at a time.
 Progress:
 If no process is in the critical section, and some processes want to enter, one of
them must be allowed to enter.

 Bounded Waiting:
Every process must get a chance to enter its critical section after waiting for a
limited time.

Critical Section Problem:

 In programs where multiple tasks (or processes) run at the same time, they
sometimes need to share resources (like data or files).
 If two tasks try to use the same resource at once, things can break (e.g.,
corrupted data, crashes).

Three conditions to avoid critical region problem:

1. No two processes may be simultaneously inside their critical regions.
2. No process running outside its critical region may block other
processes.
3. No process have to wait forever to enter its critical region.

Example:
Here process A enters its critical region at time T1. A little later, at time
T2 process B attempts to enter its critical region but fails because another
process is already in its critical region and we allow only one at a time.
Consequently, B is temporarily suspended until time T3 when A leaves
its critical region, allowing B to enter immediately. Eventually B leaves
(at T4) and we are back to the original situation with no processes in their
critical regions.
Mutual Exclusion with Busy Waiting
• Mutual exclusion means to prevent simultaneous access of processes to
shared resources.
• When one process is busy updating shared memory in its critical region,
no other process will enter its critical region and cause trouble.

• Busy waiting is a process synchronization technique in which a

process/task waits and constantly checks for a condition to be satisfied
before proceeding with its execution.
• Busy looping is usually used to achieve mutual exclusion in operating
systems. Mutual exclusion prevents processes from accessing a shared
resource simultaneously.
1. Disabling Interrupts:
• An interrupt is an event that alters the sequence in which the processor
executes instructions.
• It is a hardware solution run on the kernel mode.
• On a single-processor system, the simplest solution is to have each
process disable all interrupts just after entering its critical region and
re-enable them just before leaving it.
• With interrupts is disabled, no clock interrupts can occur. So CPU will
not be able to switch to another process.
• Thus, once a process has disabled interrupts, it can examine and update
the shared memory without fear that any other process will intervene.
Problem:
• Suppose that one of the processes disable interrupt, and never turned
them on again, then this could be the end of the system.
2. Lock Variable:
• It is a software solution.
• Makes the use of single, shared (lock) variable, initially 0.
• Before entering into the critical section, a process checks a shared lock
variable lock’s value.
• If the value of the lock is 0 then set it to 1 before entering the critical
section and enters into the critical section and set it to 0 immediately
after leaving the critical section.
• If the value of the lock is 1 then wait until it becomes 0 by some other
process which is in critical section.
Problem:
• Suppose that one process reads the lock and sees that it is 0. Before it
can set the lock to 1, another process is scheduled, runs, and sets the
lock to 1. When the first process runs again, it will also set the lock to
1, and two processes will be in their critical regions at the same time.

[Link] Alteration(Turn variables):

• Two process Solution

 • The integer variable turn, initially 0, keeps track of whose turn it is to
enter the critical region and examine or update the shared memory.
• Initially, process 0 inspects turn, finds it to be 0, and enters its critical
region. Process 1 also finds it to be 0 and therefore sits in a tight loop
continually testing turn to see when it becomes 1.
• When process 0 leaves the critical region, it sets turn to 1, to allow
process 1 to enter its critical region.

Problem:
Progress is not guaranteed in this mechanism. If P0 doesn't want to get enter
into the critical section on its turn then P1 got blocked for infinite time. P1 has
to wait for so long for its turn since the turn variable will remain 0 until P0
assigns it to 1.
3. Peterson’s Solution:

• Before using the shared variables (i.e., before entering its critical
region), each process calls enter_region with its own process number,
0 or 1, as parameter.
• This call will make it wait until it's safe to enter. After it has finished with the
shared variables, the process calls leave_region to indicate that it is
done and to allow the other process to enter, if it so desires.
 • Since process 1 is not interested, enter region returns immediately.
If process 1 now makes a call to enter_region, it will hang there until
interested [0] goes to FALSE, an event that only happens when
process 0 calls leave_region to exit the critical region.

4. TSL Instruction:

• To use the TSL instruction, we will use a shared variable, lock, to

coordinate access to shared memory.
• When lock is 0, any process may set it to 1 using the TSL instruction
and then read or write the shared memory.
• When it is done, the process sets lock back to 0 using an ordinary
move instruction.

Semaphores
• Semaphore is a simply a variable. This variable is used to solve
critical section problem and to achieve process synchronization in
the multiprocessing environment.
• It was proposed by Edsger Dijkstra. It is a technique to manage
concurrent processes by using a simple integer value known as
semaphore.
• The two most common kinds of semaphores are counting
semaphores and binary semaphores. Counting semaphore can take
non-negative integer values and Binary semaphore can take a 0 and
1.
 • A semaphore can only be accessed using the following operations:
₋ wait () :- called when a process wants access to a resource
₋ signal ():- called when a process is done using a resource

Implementation of mutual-exclusion using binary semaphores:

do
{
wait(s);
// critical section
signal(s);
// remainder section
}
while(1);
Mutex:
• Mutex is the sort form for ‘mutual exclusion’.
• A mutex and the binary semaphore are essentially the same.
• Both mutex and the binary semaphore can take values: 0 or 1.

// Jump if Zero Equals

Monitor:
• When multiple process access to shared data simultaneously, it leads
to the problem of Race Condition.

• Monitor is programming language construct that controls access to

shared data.
• It is a collection of procedures, variables, and data structures that are
all grouped together in a special kind of module or package.
• Monitor is a module that encapsulates:
₋ Shared data structures.
 In Monitor when the process wants to access shared data, they cannot access directly.
Processes have to call procedure and those procedures in turn will allow access to
shared data. Only one process can enter into monitor at a time.

Example:

• Here when process P1 calls the procedure in order to access shared

data, at first it is checked if any other process is in monitor or not.
• If no other process is in the monitor then P1 acquires lock and enters
the monitor.
• When process P2 calls the procedure, then it gets block and will be
placed in the queue of monitor.
• In monitor Conditional variable provides the synchronization
between the processes.
• Three operations can be performed on conditional variables:
₋ Wait ()
₋ Signal ()
₋ Broadcast ()
• wait (): When a process call wait () operation, that process is placed
on a queue to enter to the monitor.
signal (): When a process wants to exit from monitor it calls signal
() operation.
• When a process calls a signal () operation, it causes one of the
waiting processes in the queue to enter monitor.
• broadcast (): It signals all the waiting processes in the queue to wait.
 Monitor Syntax:
Monitor Monitor_Name
{
Local_variables_declaration;
Procedure1 (...)
{
//statements;
}
Procedure2 (...)
{
//statements;
}
........
}

Monitors Semaphores

Condition variables are used only inside monitors. Condition variables are not used with semaphores.

Wait may or may not block, depending on the semaphore

Wait always blocks the process.
value.

A monitor includes shared variables and the A semaphore uses a value to represent the number of
procedures that access them. available resources.

Built-in support for condition variables. No support for condition variables.

Classical Problems of Synchronization

Producer Consumer Problem

• The Producer-Consumer problem is a classical problem. It is used
for multi-process synchronization, which means synchronization
between more than one processes.
• In this problem, we have one producer and one consumer. The
producer is the one who produces something, and the consumer is
the one who consumes something produced by the producer. The
producer and consumer both share the common memory buffer, and
the memory buffer is of fixed-size.
• Let us consider the producer-consumer problem where two
processes share a common, fixed-size buffer.
• One of them, the producer, puts information into the buffer, and the
other one, the consumer, takes it out.
• Trouble arises when the producer wants to put a new item in the
buffer, but it is already full. The solution is for the producer to go to
sleep, to be awakened when the consumer has removed one or more
items.
• Similarly, if the consumer wants to remove an item from the buffer
and sees that the buffer is empty, it goes to sleep until the producer
puts something in the buffer and wakes it up.
• To keep track of the number of items in the buffer, we will need a
variable, count. If the maximum number of items the buffer can hold
is N, then:
₋ The producer's code will first test to see if count is N. If it is, the
producer will go to sleep; if it is not, the producer will add an item
and increment count.
₋ Similarly, the consumer's code first test count to see if it is 0. If it
is, go to sleep; if it is nonzero, remove an item and decrement the
counter. Each of the processes also tests to see if the other should
be awakened, and if so, wakes it up.
Consumer Producer Problem

Void consumer(void)
Solving Consumer Producer Problem using Semaphore

Note: Empty(E)=N buffer size , Full(F)=0 buffer full empty

Dining Philosophers Problem

• In 1965, Dijkstra posed and solved a synchronization problem he
called the dining philosophers problem.
• The problem can be stated quite simply as follows:
₋ Five philosophers are seated around a circular table.
₋ Each philosopher has a plate of spaghetti.
₋ The spaghetti is so slippery that a philosopher needs two forks
to eat it. Between each pair of plates is one fork.
 • The life of a philosopher consists of alternate periods of eating and
thinking.
• When a philosopher gets hungry, she tries to acquire her left and
right forks, one at a time, in either order. If successful in acquiring
two forks, she eats for a while, then puts down the forks, and
continues to think.
Example:
#define N 5
void philosopher(int i)
{
while (TRUE)
{ think();
take_fork(i);
take_fork((i+1) % N);
eat();
put_fork(t);
put_fork((i+1) % N);
}
}
Solution Dining Philosophers Problem Using Semaphore
#define N 5 //no of philosophers
#define LEFT (i+N-1)%N // no of i’s left neighbor
#define RIGHT (i+1)%N // no of i’s right neighbor
#define THINKING 0 // philosopher is thinking
#define HUNGRY 1 // philosopher is trying to get forks
#define EATING 2 // philosopher is eating
typedef int semaphore; //semaphore is special kind of int
int state[N]; // array to keep track of everyone’s state
semaphore s = 1; //declaring mutex for achieving mutual exclusion in C.R
semaphore p[N]; // one semaphore for philosopher
void philosopher(int i)
{ //i: philosopher no from 0 to N-1
while (TRUE)
{
think(); //philosopher is thinking
take_forks(i); //acquire two forks or block
eat();
put_forks(i);
}
}
void take_forks(int i)
{
wait(s); state[i] = HUNGRY;
test(i); signal(s); wait(p[i]);
}
void put_forks(i)
{
wait(s);
State[i] = THINKING;
test(LEFT); test(RIGHT); signal(s);
}
void test(i)
{
if (state[i] = HUNGRY && state[LEFTJ != EATING && statefRIGHTl
!= EATING)
{
state[i] = EATING; signal(p[i]);
}}
Sleeping Barber Problem

• Dijkstra introduced the sleeping barber problem in 1965. This

problem is based on a hypothetical scenario where there is a
barbershop with one barber. The barbershop is divided into two
rooms, the waiting room, and the workroom. The waiting room has
n chairs for waiting customers, and the workroom only has a barber
chair.
• Now, if there is no customer, then the barber sleeps in his own
chair(barber chair). Whenever a customer arrives, he has to wake up
the barber to get his haircut. If there are multiple customers and the
barber is cutting a customer's hair, then the remaining customers
wait in the waiting room with "n" chairs(if there are empty chairs),
or they leave if there are no empty chairs in the waiting room.
• The sleeping barber problem may lead to a race condition. This
problem has occurred because of the actions of both barber and
customer.

Example to explain the problem:

• Suppose a customer arrives and notices that the barber is busy
cutting the hair of another customer, so he goes to the waiting room.
While he is on his way to the waiting room, the barber finishes his
job and sees the waiting room for other customers. But he (the
barber) finds no one in the waiting room (as the customer has yet not
arrived in the waiting room), so he sits down in his chair (barber
chair) and sleeps. Now the barber is waiting for new customers to
 wake him up, and the customer is waiting as he thinks the barber is
busy.
• Here, both of them are waiting for each other, which leads to race
conditions.

Solution of sleeping barber problem

The following solution uses three semaphores, one for customers (for
counts of waiting for customers), one for barber (a binary semaphore
denoting the state of the barber, i.e., 0 for idle and 1 for busy), and a
mutual exclusion semaphore, mutex for seats.
Solution of sleeping barber problem
The following solution uses three semaphores, one for customers (for counts of waiting for
customers), one for barber (a binary semaphore denoting the state of the barber, i.e., 0 for idle and
1 for busy), and a mutual exclusion semaphore, mutex for seats.

Semaphore Customers = 0; // semaphore for count of customers

Semaphore Barber = 0; // semaphore denoting the status of barber - 0 for idle and 1 for busy
Mutex Seats = 1; // a mutual exclusion semaphore
int FreeSeats = N; Barber { while(true) {
// waits for a customer (while barber is asleep).
down(Customers);
//mutex semaphore to protect the number of available seats.
down(Seats);
//a chair gets free.
FreeSeats++;
// this will bring customers for a haircut.
up(Barber);
// releasing the mutex(semaphore) on the chair.
up(Seats);
//now barber is cutting the hairs
}
}
Customer {
while(true) {
// protects seats so that only 1 customer tries to sit in a chair if that's the case.
down(Seats); //This line should not be here.
if(FreeSeats > 0) {
// sitting down
FreeSeats--;
// notifying the barber.
up(Customers);
// releasing the lock.
up(Seats);
// customer wait in the waiting room if the barber is busy.
down(Barber);
// customer is having hair cut
} else {
// releasing the lock .
up(Seats);
// now customer leaves
}
}