Unit 2

Inter process Communication

Co-operative processes are processes which depend on other processes running in a
computer system. Simply, co-operative processes are processes that are sharing data.
That means those processes need to communicate with each other to know their
states. When processes communicate with each other, we call that Inter-
process communication(IPC).

Now we know that inter-process communication is two or more processes sharing

data. In a modern computer system, there are two models of doing this.

• Shared Memory
• Message Passing
•
In the shared memory model, processes using a shared portion of memory to
communicate data. One process can write to that memory and another process can
read from that memory.
In the message-passing model, the process is not using a shared memory portion.
Process directly sends data to other processes, which they need to communicate with.

Shared memory model

Interprocess communication — Shared memory model

Now we know that the shared memory model has a shared portion of memory to
communicate data between processes. Let us imagine there are two processes called
P1 and P2 and those processes need to communicate. Let’s say P1 needs to send some
data to P2. The following steps describe how this will happen.
Step 1: First P1 establish a shared memory region in P1’s address space.
Step 2: Now P2 should attach that shared memory region to its address space. Then
P1 writes data that needs to share with P2 in the shared memory region.
Step 3: P2 reads data from the shared memory region.

Now there are a few important points that we should keep in mind about the shared
memory model. As you see, always shared memory region initiate inside an address
space of one process. Literally, inside the address space of the process which needs to
initiate the communication. And then other processes need to attach that memory
space into its memory and we know that the operating system does not allow to
access the address space of a process by another process. So if a shared memory
system needs to be executed, then the operating system has to remove that restriction
of one process can’t access another processes address space.

We can see this model as a producer-consumer model. One process will produce the
data and another process will consume the data. We call buffer to this shared
memory region. When processes writing and reading using this buffer, those
processes need to be synchronized well, so that the consumer process will not try to
read data that the producer has not produced yet. The race condition may arise if
both the processes i.e. producer process and consumer process try to access the
shared data concurrently.

There are two types of buffers.

1.Bound Buffer
Bound buffer has a limit of size. With this type of buffer, the consumer has to wait if
the buffer is empty and the producer has to wait if the buffer is full.

2.Un-bound buffer
There is no limit of size in this type of buffer. In this case, the consumer has to wait if
the buffer is empty. But producers can always produce data since there is no
limitation of the size of the buffer.

There are both pros and cons in the shared memory model.
Message Passing Model

Inter-Process Communication — Message Passing Model

The message-passing model provides a mechanism to allow processes to
communicate and to synchronize their actions without sharing memory and this
model is particularly useful in distributed systems, where the communication process
resides on two computers connected by a network. Now let’s see how the message
passing model works inside.
In message-passing models, there are two main operations.
1. Send — sending a message to a process
2. Receive — receive a message from a process
According to the size of the message, there are two types of messages in a message-
passing system.
1. Fixed-size messages
2. Variable size messages

Fix Size Message — The message has a fixed size. System-level implementation of
this type is straight forward. But make the task of programming more difficult.
Imagine a process that has to send a message to another process, which is bigger than
the message size limit. Then the producer process has to break the message into parts
and send using mechanisms like serializing. Some systems, if the data that has to pass
with the message is too big, send the pointer of the data. This depends on the system
design.

Variable Size Message — There is no limit to the message size. System-level

implementation is a bit difficult. The system has to allow any size of the message. But
the programming task becomes much easier. A producer has not to worry about the
size of the message.
When two processes communicating using the message-passing model, there should
be a logical link between these two processes. There are various ways of creating this
link logically and physically. Here we are going to talk about only how logically
implement this link between processes.
Zoom image will be displayed

Logical link between two processes

Processes can execute send() and receive() operations via this logical link. As I
mentioned before there are various ways to implement this link
and send(), receive() operations.
• Direct or Indirect Communication
• Synchronous or Asynchronous Communication
• Automatic or Explicit Buffering
Also, there are few issues related to these implementations such as
• Naming issues
• Synchronization issues
• Buffering Issues

Direct and Indirect Communication

Direct Communication
Indirect communication model, each process must explicitly specify the sender or the
receiver. See the below example.
send(P, message)
receive(Q, message)
This process sends a message to process P and receives a message from process Q. It
has explicitly specified the sender and the receiver. The logical link created between
these types has few properties. The link is associated with exactly two processes and
there is only one link between two processes. Processes must know the producer
process and consumer process. We call this symmetry in addressing. Because both
the sender and the receiver have explicitly named.
There is another variety of this direct message passing.
send(P, message)
receive(pid, message)

In this case, specify only the receiver explicitly. This process sends a message to
process P and receives a message from any process. We call this asymmetric in
addressing.

There are some disadvantages to this direct communication model. This limits the
modularity of a program. If one process reference changed, all other processes which
depend on that process need to be changed.

In-direct communication

Indirect communication model using mailbox or ports to passing messages. The

mailbox is a sort of abstraction to a memory location that is used by processes to save
messages and retrieve messages. Each mailbox has a unique identification and two
processes can share messages if both have a shared mailbox. The mailbox may own
either by the process or the operating system. It will depend on the system
implementation. Refer to this example.

Send(A, message)
Receive(A, message)

Here is the mailbox. The process can send messages to mailbox A and processes can
receive a message from mailbox A. When using a mailbox more than two processes
can participate in a communication channel. Because of that, some issues can occur.
Refer to the below situation.
Zoom image will be displayed
Process A sends a message to the mailbox and Process B and Process C can receive
the message. Now the problem is who is going to receive the message among Process
B and Process C. There are a variety of workarounds to prevent this issue.
• Allow links to be associate with two processes at most so that only two
processes will communicate using the mailbox. So there will be only one
receiver process at once.
• Allow at most one process to execute receive() operation.
• Allow the system to select, which process will receive the message. The
system can use priority algorithms to select the process which will receive
the message.

Synchronous or Asynchronous Communication

We know that message passing between processes is happen

using send() and receive() primitives. There are different design options for
implementing each primitive. According to this design, message passing may be
either blocking or non-blocking. We can call this synchronous or asynchronous.
According to this blocking or non-blocking design, we can divide message passing
into 4 categories.
1. Blocking Send — The sending process is blocked until the receiving
process gets the message from the mailbox.
2. Non-blocking send — The sending process sends the message and
continues its operations. The sender doesn’t worry whether the receiver
gets the message from the mailbox or not.
3. Blocking Receive — Receiving process blocked, until a message is
available.
4. Non-blocking Receive — Receiving process receive either a message or
null. Receive the process not to wait until the message arrives.If the
message available then get the message. If the message is not available,
then receive the null and continues.
When a process is blocking we call that synchronous, and when a process is not
blocking we call asynchronous.

Buffering

Whether the communication is direct or indirect, messages reside in a temporary

message queue. We call that buffer. Such queues can be implemented in three ways.

1. Zero Capacity Buffer — In this queue maximum capacity is zero. Hence

messages can’t wait in the queue until a process receives the message. So
in this case, if the process wants to make sure that the receiver gets the
message, the sender has to wait until the receiver gets the message.

2. Bound Capacity Buffer — This queue has a limited capacity of n. So n

messages can wait in the queue until the receiving process retrieve the
message. So the sender has not to wait until the receiver gets the message.
 But since the queue has limited capacity, if the queue is full then the
sender has to wait or block until space available for the message in the
queue.

3. Unbounded Capacity Buffer — There is no limit in the queue. So an

infinite number of the message can wait in the queue. So the sender never
has to wait.

Process Synchronization

Process Synchronization is used in a computer system to ensure that multiple

processes or threads can run concurrently without interfering with each other.
The main objective of process synchronization is to ensure that multiple processes
access shared resources without interfering with each other and to prevent the
possibility of inconsistent data due to concurrent access. To achieve this, various
synchronization techniques such as semaphores, monitors and critical sections are
used.
In a multi-process system, synchronization is necessary to ensure data consistency
and integrity and to avoid the risk of deadlocks and other synchronization problems.
Process synchronization is an important aspect of modern operating systems and it
plays a crucial role in ensuring the correct and efficient functioning of multi-process
systems.
On the basis of synchronization, processes are categorized as one of the following
two types:
• Independent Process: The execution of one process does not affect the
execution of other processes.
• Cooperative Process: A process that can affect or be affected by other
processes executing in the system.
Process synchronization problem arises in the case of Cooperative processes also
because resources are shared in Cooperative processes.

Process Synchronization

Process Synchronization is the coordination of execution of multiple processes in a

multi-process system to ensure that they access shared resources in a controlled and
predictable manner. It aims to resolve the problem of race conditions and other
synchronization issues in a concurrent system.
Improper Synchronization in Inter Process Communication Environment leads to
following problems:
1. Inconsistency: When two or more processes access shared data at the
same time without proper synchronization. This can lead to conflicting
changes, where one process’s update is overwritten by another, causing
the data to become unreliable and incorrect.
2. Loss of Data: Loss of data occurs when multiple processes try to write or
modify the same shared resource without coordination. If one process
 overwrites the data before another process finishes, important
information can be lost, leading to incomplete or corrupted data.
3. Deadlock: Lack of proper Synchronization leads to Deadlock which
means that two or more processes get stuck, each waiting for the other to
release a resource. Because none of the processes can continue, the
system becomes unresponsive and none of the processes can complete
their tasks.
Types of Process Synchronization
The two primary type of process Synchronization in an Operating System are:
1. Competitive: Two or more processes are said to be in Competitive
Synchronization if and only if they compete for the accessibility of a
shared resource.
Lack of Proper Synchronization among Competing process may lead to
either Inconsistency or Data loss.
2. Cooperative: Two or more processes are said to be in Cooperative
Synchronization if and only if they get affected by each other i.e.
execution of one process affects the other process.
Lack of Proper Synchronization among Cooperating process may lead to
Deadlock.
Example:
Let consider a Linux code:
>>ps/grep "chrome"/wc
• ps command produces list of processes running in linux.
• grep command find/count the lines form the output of the ps command.
• wc command counts how many words are in the output.
Therefore, three processes are created which are ps, grep and wc. grep takes input
from ps and wc takes input from grep.
From this example, we can understand the concept of cooperative processes, where
some processes produce and others consume and thus work together. This type of
problem must be handled by the operating system, as it is the manager.
Conditions That Require Process Synchronization
1. Critical Section: It is that part of the program where shared resources are
accessed. Only one process can execute the critical section at a given
point of time. If there are no shared resources, then no need of
synchronization mechanisms.
2. Race Condition: It is a situation wherein processes are trying to access
the critical section and the final result depends on the order in which
they finish their update. Process Synchronization mechanism need to
ensure that instructions are being executed in a required order only.
3. Pre Emption: Preemption is when the operating system stops a running
process to give the CPU to another process. This allows the system to
make sure that important tasks get enough CPU time. This is important
as mainly issues arise when a process has not finished its job on shared
resource and got preempted. The other process might end up reading an
inconsistent value if process synchronization is not done.
What is Race Condition?
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. Race conditions in critical
sections can be avoided if the critical section is treated as an atomic instruction. Also,
proper thread synchronization using locks or atomic variables can prevent race
conditions.
Let us consider the following example.
• There is a shared variable balance with value 100.
• There are two processes deposit(10) and withdraw(10). The deposit
process does balance = balance + 10 and withdraw process does balance
= balance - 10.
• Suppose these processes run in an interleaved manner. The deposit()
fetches the balance as 100, then gets preempted.
• Now withdraw() get scheduled and makes balance 90.
• Finally deposit is rescheduled and makes the value as 110. This value is
not correct as the balance after both operations should be 100 only
We can not notice that the different segments of two processes running in different
order would give different values of balance.
Critical Section Problem
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. So the critical section problem means
designing a way for cooperative processes to access shared resources without
creating data inconsistencies.
In the above example, the operations that involve balance variable should be put in
critical sections of both deposit and withdraw.
In the entry section, the process requests for entry in the Critical Section.
Any solution to the critical section problem must satisfy three requirements:
• Mutual Exclusion: If a process is executing in its critical section, then no
other process is allowed to execute in the critical section.
• Progress: If no process is executing in the critical section and other
processes are waiting outside the critical section, then only those
processes that are not executing in their remainder section can
participate in deciding which will enter the critical section next and the
selection cannot be postponed indefinitely.
• Bounded Waiting: A bound must exist on the number of times that other
processes are allowed to enter their critical sections after a process has
made a request to enter its critical section and before that request is
granted.

Semaphores

What is Semaphores?
A semaphore is a synchronization tool used in concurrent programming to manage
access to shared resources. It is a lock-based mechanism designed to achieve process
synchronization, built on top of basic locking techniques.
Semaphores use a counter to control access, allowing synchronization for multiple
instances of a resource. Processes can attempt to access one instance, and if it is not
available, they can try other instances. Unlike basic locks, which allow only one
process to access one instance of a resource. Semaphores can handle more complex
synchronization scenarios, involving multiple processes or threads. It help prevent
problems like race conditions by controlling when and how processes access shared
data.
The process of using Semaphores provides two operations:
• wait (P): The wait operation decrements the value of the semaphore
• signal (V): The signal operation increments the value of the semaphore.
When the value of the semaphore is zero, any process that performs a wait
operation will be blocked until another process performs a signal operation.
When a process performs a wait operation on a semaphore, the operation checks
whether the value of the semaphore is >0. If so, it decrements the value of the
semaphore and lets the process continue its execution; otherwise, it blocks the
process on the semaphore. A signal operation on a semaphore activates a process
blocked on the semaphore if any, or increments the value of the semaphore by 1.
Due to these semantics, semaphores are also called counting semaphores. The initial
value of a semaphore determines how many processes can get past the wait
operation.
Semaphores are required for process synchronization to make sure that multiple
processes can safely share resources without interfering with each other. They help
control when a process can access a shared resource, preventing issues
like race conditions.
Types of Semaphores

Semaphores are of two Types:

• Binary Semaphore: This is also known as a mutex lock, as they are locks
that provide mutual exclusion. 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 problems with multiple processes and a single resource.
• Counting Semaphore: Counting semaphores can be used to control
access to a given resource consisting of a finite number of instances. The
semaphore is initialized to the number of resources available. Its value
can range over an unrestricted domain.

Working of Semaphore

A semaphore is a simple yet powerful synchronization tool used to manage access

to shared resources in a system with multiple processes. It 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.
There are two primary operations that a semaphore can perform:
1. Wait (P operation): This operation checks the semaphore's value. If the
value is greater than 0, the process is allowed to continue, and the
semaphore's value is decremented by 1. If the value is 0, the process is
blocked (waits) until the semaphore value becomes greater than 0.
2. Signal (V operation): After a process is done using the shared resource,
it performs the signal operation. This increments the semaphore's value
by 1, potentially unblocking other waiting processes and allowing them
to access the resource.

A critical section is surrounded by both operations to implement process

synchronization. The below image demonstrates the basic mechanism of how
semaphores are used to control access to a critical section in a multi-process
environment, ensuring that only one process can access the shared resource at a time

Now, let us see how it implements mutual exclusion. Let there be two processes P1
and P2 and a semaphore s is initialized as 1. Now if suppose P1 enters in its critical
section then the value of semaphore s becomes 0. Now if P2 wants to enter its critical
section then it will wait until s > 0, this can only happen when P1 finishes its critical
section and calls V operation on semaphore s.
This way mutual exclusion is achieved. Look at the below image for details which is
a Binary semaphore.

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

Classical Synchronization Problems using Semaphores Concept

These are the classical synchronization problem using the concept of semaphores.
Various classical Inter-Process Communication (IPC) problems include:
• Producer Consumer Problem
• Readers-Writers Problem
• Dining Philosophers Problem

Producer Consumer Problem Statement

We have a buffer of fixed size. A producer can produce an item and can place it in
the buffer. A consumer can pick items and 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, the buffer is the critical section.
To solve this problem, we need two counting semaphores - Full and Empty. "Full"
keeps track of some items in the buffer at any given time and "Empty" keeps track
of many 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 because the task of
producer has been completed and consumer can access the buffer.
Solution for Consumer
do{

wait(full);
wait(mutex);

// consume item from buffer

signal(mutex);
signal(empty);

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

Dining Philosopher Problem Using Semaphores

The Dining Philosopher Problem states that K philosophers are seated around a
circular table with one chopstick between each pair of philosophers. There is one
chopstick between each philosopher. A philosopher may eat if he can pick up the
two chopsticks adjacent to him. One chopstick may be picked up by any one of its
adjacent followers but not both.

The Dining Philosopher Problem is a classic synchronization problem in computer

science that involves multiple processes (philosophers) sharing a limited set of
resources (forks) in order to perform a task (eating). In order to avoid deadlock or
starvation, a solution must be implemented that ensures that each philosopher can
access the resources they need to perform their task without interference from other
philosophers.
One common solution to the Dining Philosopher Problem uses semaphores, a
synchronization mechanism that can be used to control access to shared resources.
In this solution, each fork is represented by a semaphore, and a philosopher must
acquire both the semaphore for the fork to their left and the semaphore for the fork
to their right before they can begin eating. If a philosopher cannot acquire both
semaphores, they must wait until they become available.

The steps for the Dining Philosopher Problem solution using semaphores are as
follows
1. Initialize the semaphores for each fork to 1 (indicating that they are available).
2. Initialize a binary semaphore (mutex) to 1 to ensure that only one philosopher can
attempt to pick up a fork at a time.
3. For each philosopher process, create a separate thread that executes the following
code:
• While true:
o Think for a random amount of time.
o Acquire the mutex semaphore to ensure that only one
philosopher can attempt to pick up a fork at a time.
o Attempt to acquire the semaphore for the fork to the left.
• If successful, attempt to acquire the semaphore for the fork to the right.
• If both forks are acquired successfully, eat for a random amount of time
and then release both semaphores.
• If not successful in acquiring both forks, release the semaphore for the
fork to the left (if acquired) and then release the mutex semaphore and
go back to thinking.
4. Run the philosopher threads concurrently.
By using semaphores to control access to the forks, the Dining Philosopher Problem
can be solved in a way that avoids deadlock and starvation. The use of the mutex
semaphore ensures that only one philosopher can attempt to pick up a fork at a time,
while the use of the fork semaphores ensures that a philosopher can only eat if both
forks are available.
Overall, the Dining Philosopher Problem solution using semaphores is a classic
example of how synchronization mechanisms can be used to solve complex
synchronization problems in concurrent programming.

Readers-Writers Problem
The readers-writer problem in operating systems is about managing access to shared
data. It allows multiple readers to read data at the same time without issues but
ensures that only one writer can write at a time, and no one can read while writing
is happening. This helps prevent data corruption and ensures smooth operation in
multi-user systems. Probably the most fundamental problem in concurrent
programming is to provide safe access to shared resources. A classic problem used
to illustrate this issue is Readers-Writers. It is a significant problem for showing how
data structures might be synchronized such that consistency is guaranteed and
efficiency is ensured. The Readers-Writers problem refers specifically to situations
where a number of processes or threads may possibly have access to some common
resource, like a database or a file. It also gives rise to the need for good
synchronization mechanisms so as not to bias the requirement of readers against that
of writers in access to the resource, considering the integrity of data.

What is The Readers-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:
• Readers: Multiple readers can access the shared data simultaneously
without causing any issues because they are only reading and not
modifying the data.
 • 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:
• Multiple Readers: A number of readers may access simultaneously if no
writer is presently writing.
• 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.
Focus on the solution Readers Preference in this paper. The purpose of the Readers
Preference solution is to give a higher priority to the readers to decrease the waiting
time of the readers and to make the access of resource more effective for readers.
Problem Parameters
• One set of data is shared among a number of processes
• Once a writer is ready, it performs its write. Only one writer may write at
a time
• If a process is writing, no other process can read it
• If at least one reader is reading, no other process can write
• Readers may not write and only read
Solution When Reader Has The Priority Over Writer
Here priority means, no reader should wait if the share is currently open for reading.
There are four types of cases that could happen here.
Case Process 1 Process 2 Allowed/Not Allowed

Case 1 Writing Writing Not Allowed

Case 2 Writing Reading Not Allowed

Case 3 Reading Writing Not Allowed

 Case Process 1 Process 2 Allowed/Not Allowed

Case 4 Reading Reading Allowed

Three variables are used: mutex, wrt, readcnt to implement a solution.

1. semaphore mutex, wrt; // semaphore mutex is used to ensure mutual
exclusion when readcnt is updated i.e. when any reader enters or exits
from the critical section, and semaphore wrt is used by both readers and
writers
2. int readcnt; //readcnt tells the number of processes performing read in
the critical section, initially 0
Functions for Semaphore
Semaphores are synchronization tools used in operating systems to manage access
to shared resources by multiple threads or processes. They use simple integer values
and two main operations to control access:
• wait() : decrements the semaphore value.
• signal() : increments the semaphore value.
Writer Process
• Writer requests the entry to critical section.
• If allowed i.e. wait() gives a true value, it enters and performs the write.
If not allowed, it keeps on waiting.
• It exits the critical section.
Reader Process
• Reader requests the entry to critical section.
• If allowed:

o it increments the count of number of readers inside the critical

section. If this reader is the first reader entering, it locks
the wrt semaphore to restrict the entry of writers if any reader
is inside.
o It then, signals mutex as any other reader is allowed to enter
while others are already reading.
o After performing reading, it exits the critical section. When
exiting, it checks if no more reader is inside, it signals the
semaphore "wrt" as now, writer can enter the critical section.
• If not allowed, it keeps on waiting.