Inter Process Communication (IPC)

A process can be of two types:

Independent process.
Co-operating process.
An independent process is not affected by the execution of other processes while a co-
operating process can be affected by other executing processes. Though one can think that
those processes, which are running independently, will execute very efficiently, in reality,
there are many situations when co-operative nature can be utilised for increasing
computational speed, convenience and modularity. Inter process communication (IPC) is a
mechanism which allows processes to communicate with each other and synchronize their
actions. The communication between these processes can be seen as a method of co-
operation between them. Processes can communicate with each other through both:
1. Shared Memory
2. Message passing
The Figure 1 below shows a basic structure of communication between processes via the
shared memory method and via the message passing method.
An operating system can implement both method of communication. First, we will discuss
the shared memory methods of communication and then message passing. Communication
between processes using shared memory requires processes to share some variable and it
completely depends on how programmer will implement it. One way of communication
using shared memory can be imagined like this: Suppose process1 and process2 are
executing simultaneously and they share some resources or use some information from
another process. Process1 generate information about certain computations or resources
being used and keeps it as a record in shared memory. When process2 needs to use the
shared information, it will check in the record stored in shared memory and take note of the
information generated by process1 and act accordingly. Processes can use shared memory
for extracting information as a record from another process as well as for delivering any
specific information to other processes.
Let’s discuss an example of communication between processes using shared memory
method.
i) Shared Memory Method
Ex: Producer-Consumer problem
There are two processes: Producer and Consumer. Producer produces some item and
Consumer consumes that item. The two processes share a common space or memory
location known as a buffer where the item produced by Producer is stored and from which
the Consumer consumes the item, if needed. There are two versions of this problem: the
first one is known as unbounded buffer problem in which Producer can keep on producing
items and there is no limit on the size of the buffer, the second one is known as the
bounded buffer problem in which Producer can produce up to a certain number of items
before it starts waiting for Consumer to consume it. We will discuss the bounded buffer
problem. First, the Producer and the Consumer will share some common memory, then
producer will start producing items. If the total produced item is equal to the size of buffer,
producer will wait to get it consumed by the Consumer. Similarly, the consumer will first
check for the availability of the item. If no item is available, Consumer will wait for Producer
to produce it. If there are items available, Consumer will consume it.
ii) Messaging Passing Method
Now, We will start our discussion of the communication between processes via message
passing. In this method, processes communicate with each other without using any kind of
shared memory. If two processes p1 and p2 want to communicate with each other, they
proceed as follows:
Establish a communication link (if a link already exists, no need to establish it again.)
 Start exchanging messages using basic primitives.
We need at least two primitives:
– send(message, destinaion) or send(message)
– receive(message, host) or receive(message)

The message size can be of fixed size or of variable size. If it is of fixed size, it is easy for an
OS designer but complicated for a programmer and if it is of variable size then it is easy for a
programmer but complicated for the OS designer. A standard message can have two
parts: header and body.
The header part is used for storing message type, destination id, source id, message length,
and control information. The control information contains information like what to do if
runs out of buffer space, sequence number, priority. Generally, message is sent using FIFO
style.

Message Passing through Communication Link.

Direct and Indirect Communication link
Now, We will start our discussion about the methods of implementing communication link.
While implementing the link, there are some questions which need to be kept in mind like :
1. How are links established?

2. Can a link be associated with more than two processes?

3. How many links can there be between every pair of communicating processes?
 4. What is the capacity of a link? Is the size of a message that the link can
accommodate fixed or variable?
5. Is a link unidirectional or bi-directional?
A link has some capacity that determines the number of messages that can reside in it
temporarily for which every link has a queue associated with it which can be of zero
capacity, bounded capacity, or unbounded capacity. In zero capacity, the sender waits until
the receiver informs the sender that it has received the message. In non-zero capacity cases,
a process does not know whether a message has been received or not after the send
operation. For this, the sender must communicate with the receiver explicitly.
Implementation of the link depends on the situation, it can be either a direct
communication link or an in-directed communication link.
Direct Communication links are implemented when the processes uses a specific process
identifier for the communication, but it is hard to identify the sender ahead of time.
For example: the print server.

In-direct Communication is done via a shared mailbox (port), which consists of a queue of
messages. The sender keeps the message in mailbox and the receiver picks them up.

Message Passing through Exchanging the Messages.

Synchronous and Asynchronous Message Passing:
A process that is blocked is one that is waiting for some event, such as a resource becoming
available or the completion of an I/O operation. IPC is possible between the processes on
same computer as well as on the processes running on different computer i.e. in
networked/distributed system. In both cases, the process may or may not be blocked while
sending a message or attempting to receive a message so message passing may be blocking
or non-blocking. Blocking is considered synchronous and blocking send means the sender
will be blocked until the message is received by receiver. Similarly, blocking receive has the
receiver block until a message is available. Non-blocking is considered asynchronous and
Non-blocking send has the sender sends the message and continue. Similarly, Non-blocking
receive has the receiver receive a valid message or null. After a careful analysis, we can
come to a conclusion that for a sender it is more natural to be non-blocking after message
passing as there may be a need to send the message to different processes. However, the
sender expects acknowledgement from the receiver in case the send fails. Similarly, it is
more natural for a receiver to be blocking after issuing the receive as the information from
the received message may be used for further execution. At the same time, if the message
send keep on failing, the receiver will have to wait indefinitely. That is why we also consider
the other possibility of message passing. There are basically three preferred combinations:
Blocking send and blocking receive
Non-blocking send and Non-blocking receive
Non-blocking send and Blocking receive (Mostly used)
In Direct message passing, The process which want to communicate must explicitly name
the recipient or sender of communication.
e.g. send(p1, message) means send the message to p1.
similarly, receive(p2, message) means receive the message from p2.
In this method of communication, the communication link gets established automatically,
which can be either unidirectional or bidirectional, but one link can be used between one
pair of the sender and receiver and one pair of sender and receiver should not possess more
than one pair of links. Symmetry and asymmetry between sending and receiving can also be
implemented i.e. either both process will name each other for sending and receiving the
messages or only the sender will name receiver for sending the message and there is no
need for receiver for naming the sender for receiving the message. The problem with this
method of communication is that if the name of one process changes, this method will not
work.

In Indirect message passing, processes use mailboxes (also referred to as ports) for sending
and receiving messages. Each mailbox has a unique id and processes can communicate only
if they share a mailbox. Link established only if processes share a common mailbox and a
single link can be associated with many processes. Each pair of processes can share several
communication links and these links may be unidirectional or bi-directional. Suppose two
process want to communicate though Indirect message passing, the required operations
are: create a mail box, use this mail box for sending and receiving messages, then destroy
the mail box. The standard primitives used are: send(A, message) which means send the
message to mailbox A. The primitive for the receiving the message also works in the same
way e.g. received (A, message). There is a problem in this mailbox implementation. Suppose
there are more than two processes sharing the same mailbox and suppose the process p1
sends a message to the mailbox, which process will be the receiver? This can be solved by
either enforcing that only two processes can share a single mailbox or enforcing that only
one process is allowed to execute the receive at a given time or select any process randomly
and notify the sender about the receiver. A mailbox can be made private to a single
sender/receiver pair and can also be shared between multiple sender/receiver pairs. Port is
an implementation of such mailbox which can have multiple sender and single receiver. It is
used in client/server applications (in this case the server is the receiver). The port is owned
by the receiving process and created by OS on the request of the receiver process and can
be destroyed either on request of the same receiver process or when the receiver
terminates itself. Enforcing that only one process is allowed to execute the receive can be
done using the concept of mutual exclusion. Mutex mailbox is create which is shared by n
process. Sender is non-blocking and sends the message. The first process which executes
the receive will enter in the critical section and all other processes will be blocking and will
wait.

Now, lets discuss the Producer-Consumer problem using message passing concept. The
producer places items (inside messages) in the mailbox and the consumer can consume an
item when at least one message present in the mailbox.
Examples of IPC systems
1. Posix : uses shared memory method.
2. Mach : uses message passing

3. Windows XP : uses message passing using local procedural calls

Communication in client/server Architecture:
There are various mechanism:
Pipe
Socket

Remote Procedural calls (RPCs)

The above three methods will be discussed in later articles as all of them are quite
conceptual and deserve their own separate articles.
Concurrent Processes
Concurrent processing is a computing model in which multiple processors execute
instructions simultaneously for better performance. Concurrent means, which occurs when
something else happens. The tasks are broken into sub-types, which are then assigned to
different processors to perform simultaneously, sequentially instead, as they would have to
be performed by one processor. Concurrent processing is sometimes synonymous with
parallel processing.
The term real and virtual concurrency in concurrent processing:
1. Multiprogramming Environment :
In multiprogramming environment, there are multiple tasks shared by one
processor. while a virtual concert can be achieved by the operating system, if the
processor is allocated for each individual task, so that the virtual concept is visible if
each task has a dedicated processor. The multilayer environment shown in figure.

2. Multiprocessing Environment :
In multiprocessing environment two or more processors are used with shared
memory. Only one virtual address space is used, which is common for all processors.
All tasks reside in shared memory. In this environment, concurrency is supported in
the form of concurrently executing processors. The tasks executed on different
processors are performed with each other through shared memory. The
multiprocessing environment is shown in figure.
3. Distributed Processing Environment :
In a distributed processing environment, two or more computers are connected to
each other by a communication network or high speed bus. There is no shared
memory between the processors and each computer has its own local memory.
Hence a distributed application consisting of concurrent tasks, which are distributed
over network communication via messages. The distributed processing environment
is shown in figure.
Dead lock:

In concurrent computing, a deadlock is a state in which each member of a group

waits for another member, including itself, to take action, such as sending a message or
more commonly releasing a lock.[1] Deadlocks are a common problem in multiprocessing
systems, parallel computing, and distributed systems, where software and hardware locks
are used to arbitrate shared resources and implement process synchronization.

Both processes need resources to continue execution. P1 requires additional resource R1

and is in possession of resource R2, P2 requires additional resource R2 and is in possession
of R1; neither process can continue.

Four processes (blue lines) compete for one resource (grey circle), following a right-before-
left policy. A deadlock occurs when all processes lock the resource simultaneously (black
lines). The deadlock can be resolved by breaking the symmetry.
In an operating system, a deadlock occurs when a process or thread enters a waiting state
because a requested system resource is held by another waiting process, which in turn is
waiting for another resource held by another waiting process. If a process is unable to
change its state indefinitely because the resources requested by it are being used by
another waiting process, then the system is said to be in a deadlock.
In a communications system, deadlocks occur mainly due to lost or corrupt signals rather
than resource contention.

Two processes competing for two resources in opposite order.

1) A single process goes through.
2) The later process has to wait.
3) A deadlock occurs when the first process locks the first resource at the same time
as the second process locks the second resource.

4) The deadlock can be resolved by cancelling and restarting the first process.

Deadlock is a situation that occurs in OS when any process enters a waiting state because
another waiting process is holding the demanded resource. Deadlock is a common problem
in multi-processing where several processes share a specific type of mutually exclusive
resource known as a soft lock or software.

Race condition:
A race condition is an undesirable situation that occurs when a device or system attempts to
perform two or more operations at the same time, but because of the nature of the device
or system, the operations must be done in the proper sequence to be done correctly.

Mutual exclusion, sleep and awake, mutex, semaphores…are solutions to this.

A simple example of a race condition is a light switch. In some homes there are multiple
light switches connected to a common ceiling light. When these types of circuits are used,
the switch position becomes irrelevant. If the light is on, moving either switch from its
current position turns the light off. Similarly, if the light is off, then moving either switch
from its current position turns the light on. With that in mind, imagine what might happen if
two people tried to turn on the light using two different switches at exactly the same time.
One instruction might cancel the other or the two actions might trip the circuit breaker.

A deadlock is when two (or more) threads are blocking each other. Usually this has
something to do with threads trying to acquire shared resources. ... Race conditions occur
when two threads interact in a negatve (buggy) way depending on the exact order that their
different instructions are executed.
Critical Section:
When more than one processes access a same code segment that segment is known
as critical section. Critical section contains shared variables or resources which are needed
to be synchronized to maintain consistency of data variable.
In simple terms a critical section is group of instructions/statements or region of code that
need to be executed atomically, such as accessing a resource (file, input or output port,
global data, etc.).
In concurrent programming, if one thread tries to change the value of shared data at the
same time as another thread tries to read the value (i.e. data race across threads), the result
is unpredictable.
The access to such shared variable (shared memory, shared files, shared port, etc…) to be
synchronized. Few programming languages have built-in support for synchronization.
It is critical to understand the importance of race condition while writing kernel mode
programming (a device driver, kernel thread, etc.). since the programmer can directly access
and modifying kernel data structures.

A simple solution to the critical section can be thought 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.
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 so 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.
This is primarily achieved through mutual exclusion.
Mutual exclusion is a property of process synchronization which 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.

(Ex) 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 person A is inside the changing room, there is an ‘occupied’ sign on it –
indicating that no one else can come in. person B has to use the changing room too, so
he/she has to wait till person A is done using the changing room.
Once person A comes out of the changing room, the sign on it changes from ‘occupied’ to
‘vacant’ – indicating that another person can use it. Hence, person B proceeds to use the
changing room, while the sign displays ‘occupied’ again.
The changing room is nothing but the critical section, person A and person B are two
different processes, while the sign outside the changing room indicates the process
synchronization mechanism being used.
SLEEP &WAKEUP

Sleep-wake solution is better between these two solution techniques , because in busy
waiting solution , process remains executing the while loop untill it enters the critical
section , whereas in sleep-wake solution process sleeps (goes to wait state) untill other
process exits from the critical section.

Let's examine the basic model that is sleep and wake. Assume that we have two system calls
as sleep and wake. The process which calls sleep will get blocked while the process which
calls will get waked up.
There is a popular example called producer consumer problem which is the most popular
problem simulating sleep and wake mechanism.
The concept of sleep and wake is very simple. If the critical section is not empty then the
process will go and sleep. It will be waked up by the other process which is currently
executing inside the critical section so that the process can get inside the critical section.

In producer consumer problem, let us say there are two processes, one process writes
something while the other process reads that. The process which is writing something is
called producer while the process which is reading is called consumer.
In order to read and write, both of them are usinga buffer. The code that simulates the
sleep and wake mechanism in terms of providing the solution to producer consumer
problem is shown below.

#define N 100 //maximum slots in buffer

· #define count=0 //items in the buffer
· void producer (void)
· {

· int item;
· while(True)
· {
· item = produce_item(); //producer produces an item
· if(count == N) //if the buffer is full then the producer will sleep
· Sleep();

· insert_item (item); //the item is inserted into buffer

· countcount=count+1;
· if(count==1) //The producer will wake up the
· //consumer if there is at least 1 item in the buffer
· wake-up(consumer);

· }
· }
·
· void consumer (void)
· {

· int item;
· while(True)
· {
· {
· if(count == 0) //The consumer will sleep if the buffer is empty.

· sleep();
· item = remove_item();
· countcount = count - 1;
· if(count == N-1) //if there is at least one slot available in the buffer
· //then the consumer will wake up producer

· wake-up(producer);
· consume_item(item); //the item is read by consumer.
· }
· }
· }
The producer produces the item and inserts it into the buffer. The value of the global
variable count got increased at each insertion. If the buffer is filled completely and no slot is
available then the producer will sleep, otherwise it keep inserting.
On the consumer's end, the value of count got decreased by 1 at each consumption. If the
buffer is empty at any point of time then the consumer will sleep otherwise, it keeps
consuming the items and decreasing the value of count by 1.
The consumer will be waked up by the producer if there is at least 1 item available in the
buffer which is to be consumed. The producer will be waked up by the consumer if there is
at least one slot available in the buffer so that the producer can write that.
Well, the problem arises in the case when the consumer got preempted just before it was
about to sleep. Now the consumer is neither sleeping nor consuming. Since the producer is
not aware of the fact that consumer is not actually sleeping therefore it keep waking the
consumer while the consumer is not responding since it is not sleeping.
SEMAPHORES

Semaphores are integer variables that are used to solve the critical section problem by using
two atomic operations, wait and signal that are used for process synchronization.
The definitions of wait and signal are as follows −

Wait
The wait operation decrements the value of its argument S, if it is positive. If S is negative or
zero, then no operation is performed.

wait(S)
{
while (S<=0);

S--;
}

Signal
The signal operation increments the value of its argument S.
signal(S)
{
S++;

}
Types of Semaphores
There are two main types of semaphores i.e. counting semaphores and binary semaphores.
Details about these are given as follows −
Counting Semaphores
These are integer value semaphores and have an unrestricted value domain. These
semaphores are used to coordinate the resource access, where the semaphore count is the
number of available resources. If the resources are added, semaphore count automatically
incremented and if the resources are removed, the count is decremented.
Binary Semaphores
The binary semaphores are like counting semaphores but their value is restricted to 0 and 1.
The wait operation only works when the semaphore is 1 and the signal operation succeeds
when semaphore is 0. It is sometimes easier to implement binary semaphores than counting
semaphores.
Advantages of Semaphores
Some of the advantages of semaphores are as follows −
Semaphores allow only one process into the critical section. They follow the mutual
exclusion principle strictly and are much more efficient than some other methods of
synchronization.
There is no resource wastage because of busy waiting in semaphores as processor
time is not wasted unnecessarily to check if a condition is fulfilled to allow a process
to access the critical section.
Semaphores are implemented in the machine independent code of the microkernel.
So they are machine independent.
Disadvantages of Semaphores
Some of the disadvantages of semaphores are as follows −
Semaphores are complicated so the wait and signal operations must be
implemented in the correct order to prevent deadlocks.
Semaphores are impractical for last scale use as their use leads to loss of modularity.
This happens because the wait and signal operations prevent the creation of a
structured layout for the system.
Semaphores may lead to a priority inversion where low priority processes may
access the critical section first and high priority processes later.
Mutex in Operating System
Mutex lock is essentially a variable that is binary nature that provides code wise
functionality for mutual exclusion. At times, there maybe multiple threads that may be
trying to access same resource like memory or I/O etc. To make sure that there is no
overriding. Mutex provides a locking mechanism.
Only one thread at a time can take the ownership of a mutex and apply the lock. Once it
done utilising the resource and it may release the mutex lock.

Mutex is very different from Semaphores, please read Semaphores here and then read
the difference between mutex and semaphores here.
1. Mutex is Binary in nature
2. Operations like Lock and Release are possible
3. Mutex is for Threads, while Semaphores are for processes.
4. Mutex works in user-space and Semaphore for kernel
5. Mutex provides locking mechanism
6. A thread may acquire more than one mutex
7. Binary Semaphore and mutex are different
Message Passing
Process communication is the mechanism provided by the operating system that allows
processes to communicate with each other. This communication could involve a process
letting another process know that some event has occurred or transferring of data from one
process to another. One of the models of process communication is the message passing
model.
Message passing model allows multiple processes to read and write data to the message
queue without being connected to each other. Messages are stored on the queue until their
recipient retrieves them. Message queues are quite useful for interprocess communication
and are used by most operating systems.
A diagram that demonstrates message passing model of process communication is given as
follows −

In the above diagram, both the processes P1 and P2 can access the message queue and
store and retrieve data.
Advantages of Message Passing Model
Some of the advantages of message passing model are given as follows −
The message passing model is much easier to implement than the shared memory
model.
It is easier to build parallel hardware using message passing model as it is quite
tolerant of higher communication latencies.
Disadvantage of Message Passing Model
The message passing model has slower communication than the shared memory model
because the connection setup takes time.
DINING PHILOSOPHERS PROBLEM
The dining philosopher’s problem states that there are 5 philosophers sharing a circular
table and they eat and think alternatively. There is a bowl of rice for each of the
philosophers and 5 chopsticks. A philosopher needs both their right and left chopstick to
eat. A hungry philosopher may only eat if there are both chopsticks available. Otherwise a
philosopher puts down their chopstick and begin thinking again.
The dining philosopher is a classic synchronization problem as it demonstrates a large class
of concurrency control problems.
Solution of Dining Philosophers Problem
A solution of the Dining Philosophers Problem is to use a semaphore to represent a
chopstick. A chopstick can be picked up by executing a wait operation on the semaphore
and released by executing a signal semaphore.
The structure of the chopstick is shown below semaphore chopstick.
Initially the elements of the chopstick are initialized to 1 as the chopsticks are on the table
and not picked up by a philosopher.

The structure of a random philosopher i is given as follows −

do {
wait( chopstick[i] );
wait( chopstick[ (i+1) % 5] );
..
. EATING THE RICE
.
signal( chopstick[i] );
signal( chopstick[ (i+1) % 5] );
.

. THINKING
.
} while(1);
In the above structure, first wait operation is performed on chopstick[i] and chopstick[ (i+1)
% 5]. This means that the philosopher i has picked up the chopsticks on his sides. Then the
eating function is performed.
After that, signal operation is performed on chopstick[i] and chopstick[ (i+1) % 5]. This
means that the philosopher i has eaten and put down the chopsticks on his sides. Then the
philosopher goes back to thinking.
Difficulty with the solution
The above solution makes sure that no two neighbouring philosophers can eat at the same
time. But this solution can lead to a deadlock. This may happen if all the philosophers pick
their left chopstick simultaneously. Then none of them can eat and deadlock occurs.
Some of the ways to avoid deadlock are as follows −

There should be at most four philosophers on the table.

An even philosopher should pick the right chopstick and then the left chopstick while
an odd philosopher should pick the left chopstick and then the right chopstick.

A philosopher should only be allowed to pick their chopstick if both are available at
the same time.

READERS AND WRITERS PROBLEM

The readers-writers problem relates to an object such as a file that is shared between
multiple processes. Some of these processes are readers i.e. they only want to read the data
from the object and some of the processes are writers i.e. they want to write into the
object.
The readers-writers problem is used to manage synchronization so that there are no
problems with the object data. For example - If two readers access the object at the same
time there is no problem. However if two writers or a reader and writer access the object at
the same time, there may be problems.
To solve this situation, a writer should get exclusive access to an object i.e. when a writer is
accessing the object, no reader or writer may access it. However, multiple readers can
access the object at the same time.
This can be implemented using semaphores. The codes for the reader and writer process in
the reader-writer problem are given as follows −
Reader Process

The code that defines the reader process is given below −

wait (mutex);
rc ++;
if (rc == 1)
wait (wrt);
signal(mutex);
.
. READ THE OBJECT
.

wait(mutex);
rc --;
if (rc == 0)
signal (wrt);
signal(mutex);
In the above code, mutex and wrt are semaphores that are initialized to 1. Also, rc is a
variable that is initialized to 0. The mutex semaphore ensures mutual exclusion and wrt
handles the writing mechanism and is common to the reader and writer process code.
The variable rc denotes the number of readers accessing the object. As soon as rc becomes
1, wait operation is used on wrt. This means that a writer cannot access the object anymore.
After the read operation is done, rc is decremented. When re becomes 0, signal operation is
used on wrt. So a writer can access the object now.
Writer Process

The code that defines the writer process is given below:

wait(wrt);
.
. WRITE INTO THE OBJECT
.

signal(wrt);
If a writer wants to access the object, wait operation is performed on wrt. After that no
other writer can access the object. When a writer is done writing into the object, signal
operation is performed on wrt.
Sleeping Barber problem in Process Synchronization
Prerequisite – Inter Process Communication
Problem : The analogy is based upon a hypothetical barber shop with one barber. There

is a barber shop which has one barber, one barber chair, and n chairs for waiting for
customers if there are any to sit on the chair.
If there is no customer, then the barber sleeps in his own chair.
When a customer arrives, he has to wake up the barber.
If there are many customers and the barber is cutting a customer’s hair, then the

remaining customers either wait if there are empty chairs in the waiting room or they
leave if no chairs are empty.
Solution : The solution to this problem includes three semaphores.First is for the
customer which counts the number of customers present in the waiting room (customer
in the barber chair is not included because he is not waiting). Second, the barber 0 or 1

is used to tell whether the barber is idle or is working, And the third mutex is used to
provide the mutual exclusion which is required for the process to execute. In the
solution, the customer has the record of the number of customers waiting in the waiting
room if the number of customers is equal to the number of chairs in the waiting room
then the upcoming customer leaves the barbershop.

When the barber shows up in the morning, he executes the procedure barber, causing
him to block on the semaphore customers because it is initially 0. Then the barber goes
to sleep until the first customer comes up.
When a customer arrives, he executes customer procedure the customer acquires the
mutex for entering the critical region, if another customer enters thereafter, the second

one will not be able to anything until the first one has released the mutex. The customer
then checks the chairs in the waiting room if waiting customers are less then the
number of chairs then he sits otherwise he leaves and releases the mutex.
If the chair is available then customer sits in the waiting room and increments the
variable waiting value and also increases the customer’s semaphore this wakes up the
barber if he is sleeping.
At this point, customer and barber are both awake and the barber is ready to give that
person a haircut. When the haircut is over, the customer exits the procedure and if there
are no customers in waiting room barber sleeps.

Algorithm for Sleeping Barber problem:

Semaphore Customers = 0;
Semaphore Barber = 0;
Mutex Seats = 1;
int FreeSeats = N;

Barber {
while(true) {
/* waits for a customer (sleeps). */
down(Customers);
/* mutex to protect the number of available seats.*/

down(Seats);
/* a chair gets free.*/
FreeSeats++;
/* bring customer for haircut.*/
up(Barber);

/* release the mutex on the chair.*/

up(Seats);
/* barber is cutting hair.*/
}
}

Customer {
while(true) {
/* protects seats so 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--;
/* notify the barber. */

up(Customers);
/* release the lock */
up(Seats);
/* wait in the waiting room if barber is busy. */
down(Barber);

// customer is having hair cut

} else {
/* release the lock */
up(Seats);
// customer leaves

}
}
}
Attention reader! Don’t stop learning now. Get hold of all the important CS Theory
concepts for SDE interviews with the CS Theory Course at a student-friendly price and

become industry ready.

Producer Consumer Problem using Semaphores
Prerequisite – Semaphores in operating system, Inter Process Communication
Producer consumer problem is a classical synchronization problem. We can solve this

problem by using semaphores.

A semaphore S is an integer variable that can be accessed only through two standard
operations : wait() and signal().
The wait() operation reduces the value of semaphore by 1 and the signal() operation
increases its value by 1.

wait(S){
while(S<=0); // busy waiting
S--;
}
signal(S){

S++;
}
Semaphores are of two types:
Binary Semaphore – This is similar to mutex lock but not the same thing. It can have
only two values – 0 and 1. Its value is initialized to 1. It is used to implement the

solution of critical section problem with multiple processes.

Counting Semaphore – Its value can range over an unrestricted domain. It is used to
control access to a resource that has multiple instances.
Problem Statement – We have a buffer of fixed size. A producer can produce an item and
can place in the buffer. A consumer can pick items and can consume them. We need to

ensure that when a producer is placing an item in the buffer, then at the same time
consumer should not consume any item. In this problem, buffer is the critical section.
To solve this problem, we need two counting semaphores – Full and Empty. “Full” keeps
track of number of items in the buffer at any given time and “Empty” keeps track of
number of unoccupied slots.
Initialization of semaphores –
mutex = 1
Full = 0 // Initially, all slots are empty. Thus full slots are 0
Empty = n // All slots are empty initially

Solution for Producer –

do{
//produce an item
wait(empty);
wait(mutex);

//place in buffer
signal(mutex);
signal(full);
}while(true)
When producer produces an item then the value of “empty” is reduced by 1 because one

slot will be filled now. The value of mutex is also reduced to prevent consumer to access
the buffer. Now, the producer has placed the item and thus the value of “full” is
increased by 1. The value of mutex is also increased by 1 beacuse the task of producer
has been completed and consumer can access the buffer.
Solution for Consumer –

do{
wait(full);
wait(mutex);
// remove item from buffer
signal(mutex);

signal(empty);
// consumes item
}while(true)
As the consumer is removing an item from buffer, therefore the value of “full” is reduced
by 1 and the value is mutex is also reduced so that the producer cannot access the buffer
at this moment. Now, the consumer has consumed the item, thus increasing the value of
“empty” by 1. The value of mutex is also increased so that producer can access the
buffer now.
Deadlock Prevention And Avoidance
Deadlock Characteristics
As discussed in the previous post, deadlock has following characteristics.
1. Mutual Exclusion
2. Hold and Wait

3. No preemption
4. Circular wait

Deadlock Prevention
We can prevent Deadlock by eliminating any of the above four conditions.
Eliminate Mutual Exclusion
It is not possible to dis-satisfy the mutual exclusion because some resources, such as the
tape drive and printer, are inherently non-shareable.

Eliminate Hold and wait

1. Allocate all required resources to the process before the start of its execution, this
way hold and wait condition is eliminated but it will lead to low device utilization. for
example, if a process requires printer at a later time and we have allocated printer
before the start of its execution printer will remain blocked till it has completed its
execution.
2. The process will make a new request for resources after releasing the current set of
resources. This solution may lead to starvation.

Eliminate No Preemption
Preempt resources from the process when resources required by other high priority
processes.
Eliminate Circular Wait
Each resource will be assigned with a numerical number. A process can request the
resources increasing/decreasing. order of numbering.
For Example, if P1 process is allocated R5 resources, now next time if P1 ask for R4, R3 lesser
than R5 such request will not be granted, only request for resources more than R5 will be
granted.

Deadlock Avoidance
Deadlock avoidance can be done with Banker’s Algorithm.
Banker’s Algorithm
Bankers’s Algorithm is resource allocation and deadlock avoidance algorithm which test all
the request made by processes for resources, it checks for the safe state, if after granting
request system remains in the safe state it allows the request and if there is no safe state it
doesn’t allow the request made by the process.
Inputs to Banker’s Algorithm:

1. Max need of resources by each process.

2. Currently allocated resources by each process.
3. Max free available resources in the system.
The request will only be granted under the below condition:
1. If the request made by the process is less than equal to max need to that process.
2. If the request made by the process is less than equal to the freely available resource
in the system.

Example:
Total resources in system:
ABCD
6576
Available system resources are:

ABCD
3112
Processes (currently allocated resources):
ABCD
P1 1 2 2 1
P2 1 0 3 3
P3 1 2 1 0

Processes (maximum resources):

ABCD
P1 3 3 2 2
P2 1 2 3 4
P3 1 3 5 0

Need = maximum resources - currently allocated resources.

Processes (need resources):
ABCD
P1 2 1 0 1
P2 0 2 0 1

P3 0 1 4 0
Deadlock Detection And Recovery
In the previous post, we have discussed Deadlock Prevention and Avoidance. In this post,
Deadlock Detection and Recovery technique to handle deadlock is discussed.
Deadlock Detection
1. If resources have single instance:
In this case for Deadlock detection we can run an algorithm to check for cycle in the
Resource Allocation Graph. Presence of cycle in the graph is the sufficient condition
for deadlock.

In the above diagram, resource 1 and resource 2 have single instances. There is a cycle R1 →
P1 → R2 → P2. So, Deadlock is Confirmed.
2. If there are multiple instances of resources:
Detection of the cycle is necessary but not sufficient condition for deadlock
detection, in this case, the system may or may not be in deadlock varies according to
different situations.
Deadlock Recovery
A traditional operating system such as Windows doesn’t deal with deadlock recovery as it is
time and space consuming process. Real-time operating systems use Deadlock recovery.
Recovery method
1. Killing the process: killing all the process involved in the deadlock. Killing process
one by one. After killing each process check for deadlock again keep repeating the
process till system recover from deadlock.
2. Resource Preemption: Resources are preempted from the processes involved in the
deadlock, preempted resources are allocated to other processes so that there is a
possibility of recovering the system from deadlock. In this case, the system goes into
starvation.