UNIT 2 Chapter 3
PROCESS SYNCHRONIZATION
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, destination) or send(message)
– receive(message, host) or receive(message)
The message size can be of fixed size or of variable size. A standard message can have two parts: header
and body.
The critical section problem:
Consider a system , assume that it consisting of n processes. Each process having a segment of code. This
segment of code is said to be critical section.
E.G: Railway Reservation System.
Two persons from different stations want to reserve their tickets, the train number,destination is
common, the two persons try to get the reservation at the same [Link], the available berths
are only one; both are trying for that [Link] is also called the critical section problem. Solution is when
one process is executing in its critical section, no other process is to be allowed to execute in
its critical section.
The critical section problem is to design a protocol that the processes can use to
cooperate. Each process must request permission to enter its critical section. The section of code
implementing this request is the entry section. The critical section may be followed by an exit section. The
remaining code is the remainder section.
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
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.
Semaphores in Process Synchronization
In multiprogramming systems, multiple processes may need to access shared resources like files,
printers, or memory. To handle this, operating systems use synchronization mechanisms. One of
the most widely used mechanisms is the Semaphore.
A Semaphore is simply a variable (integer) used to control access to a shared resource by
multiple processes in a concurrent system. It ensures that only the allowed number of processes
can use a resource at a given time.
A semaphore works using two fundamental operations:
1. Wait (P operation / down)
Decreases the semaphore value.
If the value becomes negative, the process is blocked until the resource becomes available.
2. Signal (V operation / up)
Increases the semaphore value.
If there are waiting processes, one of them gets unblocked.
Types of Semaphores
Semaphores are mainly of two Types:
1. Counting Semaphore
Used when multiple instances of a resource exist.
The semaphore value can range over an unrestricted domain (0 to N).
Example: Managing access to a pool of 5 printers.
2. Binary Semaphore
Special case of counting semaphore with only two values: 0 and 1.
Works like a lock: either the resource is free (1) or busy (0).
Example: Managing access to a single critical section.
Working of Semaphore
A semaphore works by maintaining a counter that controls access to a specific resource,
ensuring that no more than the allowed number of processes access the resource at the same
time.
To achieve synchronization, every critical section of code is surrounded by two operations-
Wait (P operation) and Signal (V operation) that are discussed above.
Example: Let’s consider two processes P1 and P2 sharing a semaphore S, initialised to 1:
State 1: Both processes are in their non-critical sections, and S = 1.
State 2: P1 enters the critical section. It performs wait(S), so S = 0. P2 continues in the non-
critical section.
State 3: If P2 now wants to enter, it cannot proceed since S = 0. It must wait until S > 0.
State 4: When P1 finishes, it performs signal(S), making S = 1. Now P2 can enter its critical
section and again sets S = 0.
This mechanism guarantees mutual exclusion, ensuring that only one process can access the
shared resource at a time
Peterson’s Algorithm
Peterson’s Algorithm is a classic software-based solution for the critical section
problem in operating systems. It ensures mutual exclusion between two processes,
meaning only one process can access a shared resource at a time, thus preventing
race conditions.
The algorithm uses two shared variables:
flag[i]: shows whether process i wants to enter the critical section.
turn: indicates whose turn it is to enter if both processes want to access the
critical section at the same time.
The Algorithm
For process Pi:
do {
flag[i] = true; // Pi wants to enter
turn = j; // Give turn to Pj
while (flag[j] && turn == j); // Wait if Pj also wants to enter
// Critical Section
flag[i] = false; // Pi leaves critical section
// Remainder Section
} while (true);
For process Pj:
do {
flag[j] = true;
turn = i;
while (flag[i] && turn == i);
// Critical Section
flag[j] = false;
// Remainder Section
} while (true);
Step-by-Step Explanation
1. Intent to Enter: A process sets its flag to true when it wants to enter the
critical section.
2. Turn Assignment: It sets the turn variable to the other process, giving the
other process the chance to enter first if it also wants to.
3. Waiting Condition: A process waits if the other process also wants to enter
and it is the other’s turn.
4. Critical Section: Once the condition is false, the process enters the critical
section safely.
5. Exit: On leaving, the process resets its flag to false, allowing the other process
to proceed.
This guarantees:
Mutual Exclusion: Only one process enters CS.
Progress: A process will eventually enter CS if no other is inside.
Bounded Waiting; No process waits indefinitely.
Classic problems of synchronization
1) Bounded-buffer problem
Two processes share a common ,fixed –size buffer.
Producer puts information into the buffer, consumer takes it [Link] problem arise when the
producer wants to put a new item in the buffer,but it is already full. The solution is for the
producer has to wait until the consumer has consumed atleast one buffer. similarly if the consumer
wants to remove an item from the buffer and sees that the buffer is empty,it goes to sleep until the
producer puts something in the buffer and wakes it up.
2) The readers-writers problem
The readers-writers problem is related to an object(such as a file or a database) that is shared by
numerous [Link] of these processes are readers, meaning they only want to read data
from the object, while others are writers, meaning they want to write data into the object. The
Readers-Writers Problem is a classic synchronization and concurrency problem in computer
science and operating system design. It arises when there is a shared resource that can be read by
multiple processes (readers) but only written by one process (writer) at a time. The problem is to
ensure that multiple readers can access the resource simultaneously as long as no writer is
currently modifying it. However, only one writer can access or modify the resource at a particular
time while allowing any number of readers to read it simultaneously. To solve this problem,
various synchronization mechanisms like semaphores, mutexes, or condition variables are
employed to coordinate access. The primary goal is to strike a balance between allowing readers
to read in parallel for efficiency while maintaining exclusive access for writers to prevent data
corruption.
Reader process
1. The reader requests entry to the critical section
2. If permitted, it increments the number of readers within the critical section. If this reader is
the first to enter, the wrt semaphore is locked, preventing writers from entering if any other
reader is present it then signals mutex, indicating that any new reader may enter while others
are currently reading it leaves the critical section after reading. When departing, it checks to
see whether there are any more readers within, and if there are, it signals the semaphore
"wrt," indicating that the writer can now enter the critical region
3. If it is not permitted, it will continue to wait
do {
// The reader requests entry to the critical section
wait(mutex);
//Now,the number of readers has incremented by 1
readCount++;
// there is minimum one reader in the critical section
// this ensures that no writer can enter if there is even one reader
// hence readers are given preference here
if (readCount==1)
wait(wrt);
// other readers can enter while the current reader is inside the critical section
signal(mutex);
// current reader performs reading
wait(mutex); // a reader wants to exit
readCount--;
// i.e., no reader is left in the critical section,
if (readCount == 0)
signal(wrt); // writers can enter now
signal(mutex); // reader exits
} while(true);
As a result, the semaphore 'wrt' is queued on both readers and writers, with readers being
prioritized if writers are also present.
Writer process
1. The writer requests entry to the critical section
2. If permitted, i.e., wait() returns a true value, it enters and performs the write
3. If it is not allowed, it will continue to wait
4. It gets out of the critical section
do {
// the writer requests entry to the critical section
wait(wrt);
// performs the write
// exits the critical section
signal(wrt);
} while(true);
3) Dining Philosophers problem
Five philosophers are seated on 5 chairs across a table. Each philosopher has a plate full of noodles. Each
philosopher needs a pair of forks to eat it. There are only 5 forks available all together. There is only one
fork between any two plates of [Link] order to eat, a philosopher lifts two forks, one to his left and
the other to his right. if he is successful in obtaining two forks, he starts eating after some time, he stops
eating and keeps both the forks down.
What if all the 5 philosophers decide to eat at the same time ?
All the 5 philosophers would attempt to pick up two forks at the same time. So,none of them
succeed.
One simple solution is to represent each fork with a semaphore.a philosopher tries to grab a fork
by executing wait() operation on that [Link] releases his forks by executing the signal()
[Link] solution guarantees that no two neighbours are eating [Link] all 5
philosophers become hungry simultaneously and each grabs his left fork,he will be delayed
forever.
Several remedies:
1) Allow at most 4 philosophers to be sitting simultaneously at the table.
2) Allow a philosopher to pickup his fork only if both forks are available.
3) An odd philosopher picks up first his left fork and then right fork. an even philosopher picks up
his right fork and then his left fork.