lOMoAR cPSD| 21591425

OS-UNIT 2 Notes - operating system unit 2

Operating Systems (Dr. A.P.J. Abdul Kalam Technical University)

 lOMoAR cPSD| 21591425

Unit-2
Concurrent Processes
1. Process concept

2.
 lOMoAR cPSD| 21591425

3. Principle of concurrency :
Concurrency in operating systems refers to the ability of an operating system to handle
multiple tasks or processes at the same time. With the increasing demand for high
performance computing, concurrency has become a critical aspect of modern computing
systems. Operating systems that support concurrency can execute multiple tasks
simultaneously, leading to better resource utilization, improved responsiveness, and enhanced
user experience.
lOMoAR cPSD| 21591425
 lOMoAR cPSD| 21591425

4. Producer/Consumer Problem:

Producer-Consumer problem is a classical synchronization problem in the operating system.

With the presence of more than one process and limited resources in the system the
synchronization problem arises. If one resource is shared between more than one process at the
same time then it can lead to data inconsistency. In the producer-consumer problem, the
producer produces an item and the consumer consumes the item produced by the producer.

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

• Consumer is a Process that is able to consume the data/item produced by the
Producer.
• Both Producer and Consumer share a common memory buffer. This buffer is a space
of a certain size in the memory of the system which is used for storage. The producer
produces the data into the buffer and the consumer consumes the data from the buffer.

1. Producer Process should not produce any data when the shared buffer is full.
2. Consumer Process should not consume any data when the shared buffer is empty.
 lOMoAR cPSD| 21591425

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

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

Solution For Producer Consumer Problem

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

Semaphores are variables used to indicate the number of resources available in the system at
a particular time. semaphore variables are used to achieve `Process Synchronization.
Full
The full variable is used to track the space filled in the buffer by the Producer process. It is
initialized to 0 initially as initially no space is filled by the Producer process.
Empty
The Empty variable is used to track the empty space in the buffer. The Empty variable is
initially initialized to the BUFFER-SIZE as initially, the whole buffer is empty.
Mutex
Mutex is used to achieve mutual exclusion. mutex ensures that at any particular time only the
producer or the consumer is accessing the buffer.
Mutex - mutex is a binary semaphore variable that has a value of 0 or 1.
We will use the Signal() and wait() operation in the above-mentioned semaphores to arrive at
a solution to the Producer-Consumer problem.
Signal() - The signal function increases the semaphore value by 1. Wait() - The wait
operation decreases the semaphore value by 1.
Let's look at the code of Producer-Consumer Process
The code for Producer Process is as follows :

• wait(Empty) - Before producing items, the producer process checks for the empty
space in the buffer. If the buffer is full producer process waits for the consumer process
to consume items from the buffer. so, the producer process executes wait(Empty) before
producing any item.
• wait(mutex) - Only one process can access the buffer at a time. So, once the producer
process enters into the critical section of the code it decreases the value of mutex by
executing wait(mutex) so that no other process can access the buffer at the same time.
• add() - This method adds the item to the buffer produced by the Producer process. once
the Producer process reaches add function in the code, it is guaranteed that no other
process will be able to access the shared buffer concurrently which helps in data
consistency.
 lOMoAR cPSD| 21591425

• signal(mutex) - Now, once the Producer process added the item into the buffer it
increases the mutex value by 1 so that other processes which were in a busy-waiting
state can access the critical section.
• signal(Full) - when the producer process adds an item into the buffer spaces is filled
by one item so it increases the Full semaphore so that it indicates the filled spaces in
the buffer correctly.

The code for the Consumer Process is as follows :

• wait(Full) - Before the consumer process starts consuming any item from the buffer it
checks if the buffer is empty or has some item in it. So, the consumer process creates
one more empty space in the buffer and this is indicated by the full variable. The value
of the full variable decreases by one when the wait(Full) is executed. If the Full variable
is already zero i.e the buffer is empty then the consumer process cannot consume any
item from the buffer and it goes in the busy-waiting state.
• wait(mutex) - It does the same as explained in the producer process. It decreases the
mutex by 1 and restricts another process to enter the critical section until the consumer
process increases the value of mutex by 1.
• consume() - This function consumes an item from the buffer. when code reaches the
consuming () function it will not allow any other process to access the critical section
which maintains the data consistency.
• signal(mutex) - After consuming the item it increases the mutex value by 1 so that
other processes which are in a busy-waiting state can access the critical section now.
• signal(Empty) - when a consumer process consumes an item it increases the value of
the Empty variable indicating that the empty space in the buffer is increased by 1.
• Mutex is used to solve the producer-consumer problem as mutex helps in mutual
exclusion. It prevents more than one process to enter the critical section. As mutexes
have binary values i.e 0 and 1. So whenever any process tries to enter the critical section
code it first checks for the mutex value by using the wait operation.
• wait(mutex);
• wait(mutex) decreases the value of mutex by 1. so, suppose a process P1 tries to enter
the critical section when mutex value is 1. P1 executes wait(mutex) and decreases the
value of mutex. Now, the value of mutex becomes 0 when P1 enters the critical section
of the code.
• Now, suppose Process P2 tries to enter the critical section then it will again try to
decrease the value of mutex. But the mutex value is already 0. So, wait(mutex) will not
execute, and P2 will now keep waiting for P1 to come out of the critical section.
• Now, suppose if P2 comes out of the critical section by executing signal(mutex).
 lOMoAR cPSD| 21591425

• signal(mutex)
• signal(mutex) increases the value of mutex by 1.mutex value again becomes 1. Now,
the process P2 which was in a busy-waiting state will be able to enter the critical section
by executing wait(mutex).
• So, mutex helps in the mutual exclusion of the processes.
• In the above section in both the Producer process code and consumer process code, we
have the wait and signal operation on mutex which helps in mutual exclusion and solves
the problem of the Producer consumer process.

4. 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.
The need for mutual exclusion comes with concurrency. There are several kinds of concurrent
execution:
1. Interrupt handlers
2. Interleaved preemptively scheduled processes/threads
3. Multiprocessor clusters, with shared memory
4. Distributed systems
• Mutual exclusion methods are used in concurrent programming to avoid the
simultaneous use of a common resource, such as a global variable, by pieces of
computer code called critical sections • Requirement of mutual exclusion is that,
when process P1 is accessing a shared resource R1 then on other process should
be able to access resource R1 until process P1 has finished its operation with
resource R1.
• Examples of such resources include files, I/O devices such as printers and shared
data structures.
• Approaches to implementing mutual exclusion:
1. Software method: Leave the responsibility with the processes themselves. These methods
are usually highly error-prone and carry high overheads.
2. Hardware method: Special-purpose machine instructions are used for accessing shared
resources. This method is faster but cannot provide complete solution. Hardware solution
cannot give guarantee the absence of deadlock and starvation.
3. Programming language method: Provide support through the operating system or
through the programming language.
Requirements of mutual exclusion:
1. At any time, only one process is allowed to enter in its critical section.
2. Solution is implemented purely in software on a machine.
3. A process remains inside its critical section for a bounded time only.
4. No assumption can be made about relative speeds of asynchronous concurrent
processes.
5. A process cannot prevent any other process for entering into critical section.
6. A process must not be indefinitely postponed from entering its critical section.
In order to understand mutual exclusion, let’s take an example.
 lOMoAR cPSD| 21591425

Boy A decides upon some clothes to buy and heads to the changing room to try them out.
Now, while boy A is inside the changing room, there is an ‘occupied’ sign on it – indicating
that no one else can come in. Girl B has to use the changing room too, so she has to wait till
boy A is done using the changing room.

Once boy A comes out of the changing room, the sign on it changes from ‘occupied’ to
‘vacant’ – indicating that another person can use it. Hence, girl B proceeds to use the changing
room, while the sign displays ‘occupied’ again.

5. Critical Section Problem:

Critical Section is the part of a program which tries to access shared resources. That resource
may be any resource in a computer like a memory location, Data structure, CPU or any IO
device.
 lOMoAR cPSD| 21591425

The critical section cannot be executed by more than one process at the same time; operating
system faces the difficulties in allowing and disallowing the processes from entering the critical
section.

The critical section problem is used to design a set of protocols which can ensure that the Race
condition among the processes will never arise.

In order to synchronize the cooperative processes, our main task is to solve the critical section
problem. We need to provide a solution in such a way that the following conditions can be
satisfied.

Solution to the Critical Section Problem

The critical section problem needs a solution to synchronize the different processes. The
solution to the critical section problem must satisfy the following conditions −

• Mutual Exclusion
Mutual exclusion implies that only one process can be inside the critical section
at any time. If any other processes require the critical section, they must wait
until it is free.
• Progress
 lOMoAR cPSD| 21591425

Progress means that if a process is not using the critical section, then it should
not stop any other process from accessing it. In other words, any process can
enter a critical section if it is free.
• Bounded Waiting
Bounded waiting means that each process must have a limited waiting time. Itt
should not wait endlessly to access the critical section.

6. Dekker’s Solution
Dekker’s algorithm was the first probably-correct solution to the critical section problem. It
allows two threads to share a single-use resource without conflict, using only shared memory
for communication. It avoids the strict alternation of a naïve turn-taking algorithm, and was
one of the first mutual exclusion algorithms to be invented.
First Version of Dekker’s Solution – The idea is to use a common or shared thread number
between processes and stop the other process from entering its critical section if the shared
thread indicates the former one already running.
Second Version of Dekker’s Solution – To remove lockstep synchronization, it uses two
flags to indicate its current status and updates them accordingly at the entry and exit section.
Third Version of Dekker’s Solution – To re-ensure mutual exclusion, it sets the flags before
the entry section itself.
Fourth Version of Dekker’s Solution – Uses small time interval to recheck the condition,
eliminates deadlock, and ensures mutual exclusion as well.
Final and completed Solution – -Idea is to use favoured thread notion to determine entry to
the critical section. Favoured thread alternates between the thread providing mutual exclusion
and avoiding deadlock, indefinite postponement, or lockstep synchronization.
 lOMoAR cPSD| 21591425

7. Peterson’s Solution:
 lOMoAR cPSD| 21591425

8. Semaphores:
lOMoAR cPSD| 21591425
 lOMoAR cPSD| 21591425

9. Test and Set Operation:

10. Classical Problem in concurrency:

The classical problems of synchronization are as follows:
1. Bound-Buffer problem
2. Sleeping barber problem
 lOMoAR cPSD| 21591425

3. Dining Philosophers problem

4. Readers and writers problem

Bound-Buffer problem(Producer-consumer problem)

Also known as the Producer-Consumer problem. In this problem, there is a buffer of
n slots, and each buffer is capable of storing one unit of data. There are two processes
that are operating on the buffer – Producer and Consumer. The producer tries to insert
data and the consumer tries to remove data. If the processes are run simultaneously they
will not yield the expected output.cThe solution to this problem is creating two
semaphores, one full and the other empty to keep a track of the concurrent processes.
Dining Philosopher’s problem
This problem states that there are K number of philosophers sitting around a circular
table with one chopstick placed between each pair of philosophers. The philosopher will
be able to eat if he can pick up two chopsticks that are adjacent to the philosopher.

Sleeping barber Problem

This problem is based on a hypothetical barbershop with one barber. When there are no
customers the barber sleeps in his chair. If any customer enters he will wake up the
barber and sit in the customer chair. If there are no chairs empty they wait in the waiting
queue.

Readers and Writers Problem

This problem occurs when many threads of execution try to access the same shared
resources at a time. Some threads may read, and some may write. In this scenario, we
may get faulty outputs.

Readers-Writers Problem:
 lOMoAR cPSD| 21591425

Dining Philosopher Problem:

 lOMoAR cPSD| 21591425

Sleeping Barber Problem

The Sleeping Barber problem is a classic problem in process synchronization that is used to
illustrate synchronization issues that can arise in a concurrent system. The problem is as
follows:
There is a barber shop with one barber and a number of chairs for waiting customers.
Customers arrive at random times and if there is an available chair, they take a seat and wait
for the barber to become available. If there are no chairs available, the customer leaves. When
the barber finishes with a customer, he checks if there are any waiting customers. If there are,
he begins cutting the hair of the next customer in the queue. If there are no customers waiting,
he goes to sleep.
The problem is to write a program that coordinates the actions of the customers and the barber
in a way that avoids synchronization problems, such as deadlock or starvation.
One solution to the Sleeping Barber problem is to use semaphores to coordinate access to the
waiting chairs and the barber chair. The solution involves the following steps:
Initialize two semaphores: one for the number of waiting chairs and one for the barber chair.
The waiting chairs semaphore is initialized to the number of chairs, and the barber chair
semaphore is initialized to zero.
Customers should acquire the waiting chairs semaphore before taking a seat in the waiting
room. If there are no available chairs, they should leave.
 lOMoAR cPSD| 21591425

When the barber finishes cutting a customer’s hair, he releases the barber chair semaphore
and checks if there are any waiting customers. If there are, he acquires the barber chair
semaphore and begins cutting the hair of the next customer in the queue.
The barber should wait on the barber chair semaphore if there are no customers waiting.
The solution ensures that the barber never cuts the hair of more than one customer at a time,
and that customers wait if the barber is busy. It also ensures that the barber goes to sleep if
there are no customers waiting.
However, there are variations of the problem that can require more complex synchronization
mechanisms to avoid synchronization issues. For example, if multiple barbers are employed,
a more complex mechanism may be needed to ensure that they do not interfere with each
other.
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
 lOMoAR cPSD| 21591425

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
 lOMoAR cPSD| 21591425

11. Inter process communication models and schemes: 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 utilized for increasing
computational speed, convenience, and modularity. Inter-process communication (IPC) is a
mechanism that 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
Figure 1 below shows a basic structure of communication between processes via the shared
memory method and via the message passing method.

i) Shared Memory Method

Ex: Producer-Consumer problem
There are two processes: Producer and Consumer. The producer produces some items and
the Consumer consumes that item. The two processes share a common space or memory
location known as a buffer where the item produced by the 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 the unbounded buffer problem in which the 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 the 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 the producer will start producing items. If the total produced item is equal to the size
of the buffer, the producer will wait to get it consumed by the Consumer. Similarly, the
 lOMoAR cPSD| 21591425

consumer will first check for the availability of the item. If no item is available, the
Consumer will wait for the Producer to produce it. If there are items available, Consumer
will consume them. The pseudo-code to demonstrate is provided below:
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, destination) or send(message)
– receive(message, host) or receive(message)