Process Synchronization
In a multitasking operating system, Process Synchronization is a mechanism used to
coordinate the execution of processes that share a common address space or resources. It
ensures that concurrent processes access shared data in a specific order to maintain data
consistency.
Without synchronization, if two processes access and modify shared data simultaneously,
the final value depends on the order of execution. This chaotic situation is known as a Race
Condition.
Categories of Processes
To understand synchronization, we first categorize processes based on how they interact
with others:
• Independent Processes: These processes do not share any data or state with other
processes. The execution of one does not affect the others.
• Cooperating Processes: These processes can affect or be affected by other
processes. They share data, variables, or resources, making synchronization essential
to prevent data corruption.
What is Race Condition?
A race condition is a problem that occurs in an operating system (OS) where two or more
processes or threads are executing concurrently. The outcome of their execution depends
on the order in which they are executed. In a race condition, the exact timing of events is
unpredictable, and the outcome of the execution may vary based on the timing. This can
result in unexpected or incorrect behaviour of the system.
Example: Two Processes Updating a Shared Variable
Let’s take a shared variable balance = 100 and two processes P1 and P2:
• P1 wants to add 10 to balance.
• P2 wants to subtract 10 from balance.
Scenario without synchronization:
1
Explanation:
• P1 reads balance = 100 and prepares to add 10.
• Before P1 updates the balance with the new value (110), it is interrupted by the process
P2.
• P2, unaware of P1’s action (of adding 10), reads the balance as 100 (incorrect) and
prepares to subtract 10.
• After subtracting, P2 updates the balance to 90 and then P1 resumes and writes the
balance as 110 which is incorrect now.
In many cases, the final balance may incorrectly be 110 or 90, instead of the expected 100.
This is a classic race condition.
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.
• Entry Section: Code that requests permission to enter the critical section (e.g., locking).
• Critical Section: The segment accessing shared data.
• Exit Section: Code that releases access permissions (e.g., unlocking).
• Remainder Section: The remaining code in the process.
Solution to the Critical Section Problem
1. Mutual Exclusion
Only one process can enter the critical section at a time.
No two processes execute in the critical section simultaneously.
2
2. Progress
If no process is in the critical section, then the selection of the next process must not be
delayed indefinitely.
Only the processes that wish to enter can participate in the decision.
3. Bounded Waiting
A process must not wait forever to enter the critical section.
There must be a limit on the number of times other processes can enter before a waiting
process gets its turn.
Using Lock Variable-
• Lock variable is a synchronization mechanism.
• It uses a lock variable to provide the synchronization among the processes executing
concurrently.
• However, it completely fails to provide the synchronization.
It is implemented as-
Initially, lock value is set to 0.
• Lock value = 0 means the critical section is currently vacant and no process is present
inside it.
• Lock value = 1 means the critical section is currently occupied and a process is present
inside it.
Working-
This synchronization mechanism is supposed to work as explained in the following scenes-
Scene-01:
• Process P0 arrives.
3
• It executes the lock!=0 instruction.
• Since lock value is set to 0, so it returns value 0 to the while loop.
• The while loop condition breaks.
• It sets the lock value to 1 and enters the critical section.
• Now, even if process P0 gets pre-empted in the middle, no other process can enter the
critical section.
• Any other process can enter only after process P0 completes and sets the lock value to 0.
Scene-02:
• Another process P1 arrives.
• It executes the lock!=0 instruction.
• Since lock value is set to 1, so it returns value 1 to the while loop.
• The returned value 1 does not break the while loop condition.
• The process P1 is trapped inside an infinite while loop.
• The while loop keeps the process P1 busy until the lock value becomes 0 and its condition
breaks.
Scene-03:
• Process P0 comes out of the critical section and sets the lock value to 0.
• The while loop condition of process P1 breaks.
• It sets the lock value to 1 and enters the critical section.
• Now, even if process P1 gets pre-empted in the middle, no other process can enter the
critical section.
• Any other process can enter only after process P1 completes and sets the lock value to 0.
Failure of the Mechanism-
• The mechanism completely fails to provide the synchronization among the processes.
• It can not even guarantee to meet the basic criterion of mutual exclusion.
Explanation-
The occurrence of the following scenes may lead to two processes present inside the critical
section at the same time-
4
Scene-01:
• Process P0 arrives.
• It executes the lock!=0 instruction.
• Since lock value is set to 0, so it returns value 0 to the while loop.
• The while loop condition breaks.
• Now, process P0 gets pre-empted before it sets the lock value to 1.
Scene-02:
• Another process P1 arrives.
• It executes the lock!=0 instruction.
• Since lock value is still 0, so it returns value 0 to the while loop.
• The while loop condition breaks.
• It sets the lock value to 1 and enters the critical section.
• Now, process P1 gets pre-empted in the middle of the critical section.
Scene-03:
• Process P0 gets scheduled again.
• It resumes its execution.
• Before pre-emption, it had already failed the while loop condition.
• Now, it begins execution from the next instruction.
• It sets the lock value to 1 (which is already 1) and enters the critical section.
Thus, both the processes get to present inside the critical section at the same time.
Similarly,
• If there are n processes, then all of them may be present inside the critical section at the
same time.
• This happens when each process gets pre-empted immediately after breaking the while
loop condition.
Characteristics-
The characteristics of this synchronization mechanism are-
• It can be used for any number of processes.
5
• It is a software mechanism implemented in user mode.
• There is no support required from the operating system.
• It is a busy waiting solution which keeps the CPU busy when the process is actually
waiting.
• It does not fulfil any criteria of synchronization mechanism. The lock variable
synchronization
mechanism is a complete
failure.
Thus, it is never used.
Using Turn Variable-
• Turn variable is a synchronization mechanism that provides synchronization among two
processes.
• It uses a turn variable to provide the synchronization.
It is implemented as-
Scene-01:
• Process P0 arrives.
• It executes the turn!=0 instruction.
• Since turn value is set to 0, so it returns value 0 to the while loop.
• The while loop condition breaks.
• Process P0 enters the critical section and executes.
• Now, even if process P0 gets preempted in the middle, process P1 can not enter the
critical section.
• Process P1 can not enter unless process P0 completes and sets the turn value to 1.
6
Scene-02:
• Process P1 arrives.
• It executes the turn!=1 instruction.
• Since turn value is set to 0, so it returns value 1 to the while loop.
• The returned value 1 does not break the while loop condition.
• The process P1 is trapped inside an infinite while loop.
• The while loop keeps the process P1 busy until the turn value becomes 1 and its condition
breaks.
Scene-03:
• Process P0 comes out of the critical section and sets the turn value to 1.
• The while loop condition of process P1 breaks.
• Now, the process P1 waiting for the critical section enters the critical section and execute.
• Now, even if process P1 gets preempted in the middle, process P0 can not enter the
critical section.
• Process P0 can not enter unless process P1 completes and sets the turn value to 0.
Strict Alteration Approach
Characteristics- Process have to compulsorily enter
the critical section alternately
The characteristics of this synchronization mechanism are-
whether they want it or not.
• It ensures mutual exclusion. This is because if one process does
• It follows the strict alternation approach. not enter the critical section, then
other process will never get a
chance to execute again.
• It does not guarantee progress since it follows strict alternation approach.
• It ensures bounded waiting since processes are executed turn wise one by one and each
process is guaranteed to get a chance.
• It ensures processes does not starve for the CPU.
• It is architectural neutral since it does not require any support from the operating system.
• It is deadlock free.
• It is a busy waiting solution which keeps the CPU busy when the process is actually
waiting.
Peterson’s Solution
Peterson's approach to critical section problems is extensively utilized. It is a classical
software-based solution.
7
The solution is based on the idea that when a process is executing in a critical section, then
the other process executes the rest of the code and vice-versa is also possible, i.e., this
solution makes sure that only one process executes the critical section at any point in time.
In Peterson's solution, we have two shared variables that are used by the processes.
A boolean Flag[]: A boolean array Flag which is initialized to FALSE. This Flag array
represents which process is which process wants to enter into the critical solution.
int Turn: An integer variable Turn indicates the process number that is ready to enter into
the critical section.
do{
//A process Pi wants to enter into the critical section
//The ith index of flag is set
Flag[i] = True;
Turn = i;
while(Flag[i] && Turn == i);
{ Critical Section };
Flag[i] = False;
// another process can go to Critical Section
Turn = j;
Remainder Section
8
} while ( True);
Advantages
• Ensures mutual exclusion
• Ensures progress
• Ensures bounded waiting
Disadvantages
• Applicable only for two processes
• Uses busy waiting
• Not suitable for modern systems
Synchronization Hardware
Test and Set:
Test and set algorithm uses a boolean variable 'lock' which is initially initialized to false. This
lock variable determines the entry of the process inside the critical section of the code. Let's
first see the algorithm and then try to understand what the algorithm is doing.
boolean lock = false;
boolean TestAndSet(boolean &target){
boolean returnValue = target;
target = true;
return returnValue;
}
while(1){
while(TestAndSet(lock));
CRITICAL SECTION CODE;
lock = false;
REMAINDER SECTION CODE;
the TestAndSet() function takes a boolean value and returns the same value. TestAndSet()
function sets the lock variable to true.
When lock varibale is initially false the TestAndSet(lock) condition checks for
TestAndSet(false). As TestAndSet function returns the same value as its argument,
TestAndSet(false) returns false. Now, while loop while(TestAndSet(lock)) breaks and the
process enters the critical section.
9
As one process is inside the critical section and lock value is now 'true', if any other process
tries to enter the critical section then the new process checks for while(TestAndSet(true))
which will return true inside while loop and as a result the other process keeps executing
the while loop.
while(true); // this keeps executing until lock becomes false.
As no queue is maintained for the processes stuck in the while loop, bounded waiting is not
ensured. If a process waits for a set amount of time before entering the critical section, it is
said to be a bounded waiting condition.
In test and set algorithm the incoming process trying to enter the critical section does not
wait in a queue so any process may get the chance to enter the critical section as soon as
the process finds the lock variable to be false. It may be possible that a particular process
never gets the chance to enter the critical section and that process waits indefinitely.
Semaphores
1. 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.
1. wait(S)
2. {
3. while (S<=0);
4. S--;
5. }
2. Signal for the process synchronization: The signal operation increments the value of its
argument S.
1. signal(S)
2. {
3. S++;
4. }
A semaphore either allows or reject access to the resource, depending on how it is set up.
Use of Semaphore
In the case of a single buffer, we can separate the 4 KB buffer into four buffers of 1 KB.
Semaphore can be associated with these four buffers, allowing users and producers to work
on different buffers simultaneously.
Types of Semaphores
The two common kinds of semaphores are
• Counting semaphores
• Binary semaphores.
10
Counting Semaphores
The semaphore S value is initialized to the number of resources present in the system.
Whenever a process wants to access the resource, it performs the wait()operation on the
semaphore and decrements the semaphore value by one. When it releases the resource, it
performs the signal() operation on the semaphore and increments the semaphore value by
one.
When the semaphore count goes to 0, it means the processes occupy all resources. A process
needs to use a resource when the semaphore count is 0. It executes the wait() operation and
gets blocked until the semaphore value becomes greater than 0.
Binary Semaphores
The value of a semaphore ranges between 0and 1. It is similar to mutex lock, but mutex is a
locking mechanism, whereas the semaphore is a signalling mechanism. In binary
semaphore, if a process wants to access the resource, it performs the wait() operation on
the semaphore and decrements the value of the semaphore from 1 to 0. When it releases
the resource, it performs a signal() operation on the semaphore and increments its value to
1. Suppose the value of the semaphore is 0 and a process wants to access the resource. In
that case, it performs wait() operation and block itself till the current process utilizing the
resources releases the resource.
11
Example of Semaphore
The below-given program is a step by step implementation, which involves usage and
declaration of semaphore.
Shared var mutex: semaphore = 1;
Process i
begin
.
.
P(mutex);
execute CS;
V(mutex);
.
.
End;
Counting Semaphore vs. Binary Semaphore
Here, are some major differences between counting and binary semaphore:
Counting Semaphore Binary Semaphore
No mutual exclusion Mutual exclusion
Any integer value Value only 0 and 1
More than one slot Only one slot
Provide a set of Processes It has a mutual exclusion mechanism.
Advantages of Semaphores
Here, are pros/benefits of using Semaphore:
• It allows more than one thread to access the critical section
• Semaphores are machine-independent.
• Semaphores are implemented in the machine-independent code of the microkernel.
• They do not allow multiple processes to enter the critical section.
• As there is busy waiting in semaphore, there is never a wastage of process time and
resources.
12
• They are machine-independent, which should be run in the machine-independent
code of the microkernel.
• They allow flexible management of resources.
Disadvantage of semaphores
Here, are cons/drawback of semaphore
• One of the biggest limitations of a semaphore is priority inversion.
• The operating system has to keep track of all calls to wait and signal semaphore.
• Their use is never enforced, but it is by convention only.
• In order to avoid deadlocks in semaphore, the Wait and Signal operations require to
be executed in the correct order.
• Semaphore programming is a complicated, so there are chances of not achieving
mutual exclusion.
• It is also not a practical method for large scale use as their use leads to loss of
modularity.
• Semaphore is more prone to programmer error.
• It may cause deadlock or violation of mutual exclusion due to programmer error.
What is Mutex?
Mutex is a mutual exclusion object that synchronizes access to a resource. It is created with
a unique name at the start of a program. The mutex locking mechanism ensures only one
thread can acquire the mutex and enter the critical section. This thread only releases the
mutex when it exits in the critical section.
It is a special type of binary semaphore used for controlling access to the shared resource. It
includes a priority inheritance mechanism to avoid extended priority inversion problems. It
allows current higher priority tasks to be kept in the blocked state for the shortest time
possible. However, priority inheritance does not correct priority inversion but only minimizes
its effect.
This is shown with the help of the following example,
1. wait (mutex);
2. .....
3. Critical Section
4. .....
13
5. signal (mutex);
Advantages of Mutex
Here are the following advantages of the mutex, such as:
• Mutex is just simple locks obtained before entering its critical section and then
releasing it.
• Since only one thread is in its critical section at any given time, there are no race
conditions, and data always remain consistent.
Disadvantages of Mutex
Mutex also has some disadvantages, such as:
• If a thread obtains a lock and goes to sleep or is pre-empted, then the other thread
may not move forward. This may lead to starvation.
• It can't be locked or unlocked from a different context than the one that acquired it.
• Only one thread should be allowed in the critical section at a time.
Terms Mutex Semaphore
The mutex is a locking
Semaphore is a signalling mechanism
mechanism, as to acquire a
as wait() and signal() operations
resource, a process needs to lock
Definition performed on the semaphore variable
the mutex object, and while
indicate whether a process is
releasing a resource process has
acquiring or releasing the resource.
to unlock the mutex object.
Existence A mutex is an object. Semaphore is an integer variable.
Mutex allows multiple program Semaphore allows multiple program
Function threads to access a single threads to access a finite instance of
resource but not simultaneously. resources.
Semaphore value can be changed by
Mutex object lock is released only
any process acquiring or releasing the
Ownership by the process that has acquired
resource by performing wait() and
the lock on the mutex object.
signal() operation.
The semaphore can be categorized
Categorize Mutex is not categorized further. into counting semaphore and binary
semaphore.
The mutex object is locked or
Semaphore value is modified using
unlocked by the process of
Operation wait() and signal() operation apart
requesting or releasing the
from initialization.
resource.
14
Suppose the process acquires all the
If a mutex object is already
resources, and no resource is free. In
locked, then the process desiring
that case, the process desiring to
Resources to acquire resource waits and get
acquire resource performs wait()
Occupied queued by the system till the
operation on semaphore variable and
resource is released and the
blocks itself till the count of
mutex object gets unlocked.
semaphore become greater than 0.
Classical Problems of Synchronization
1. The Producer–Consumer Problem
The Producer–Consumer Problem (also known as the Bounded-Buffer Problem) is a classic
multi-process synchronization challenge. It describes two processes—the Producer and the
Consumer—who share a common, fixed-size buffer used as a queue.
• The Producer: Generates data and puts it into the buffer.
• The Consumer: Takes data out of the buffer one piece at a time.
• The Constraint: * The Producer must not add data if the buffer is full.
o The Consumer must not remove data if the buffer is empty.
o Both must not access the buffer at the same time (Mutual Exclusion) to
prevent data corruption.
The Solution using Semaphores
To solve this efficiently and avoid "busy waiting," we use three semaphores:
1. Mutex (m): A binary semaphore (initialized to 1) used to ensure mutual exclusion
when accessing the buffer.
2. Empty (e): A counting semaphore (initialized to $N$, the buffer size) to track empty
slots.
3. Full (f): A counting semaphore (initialized to 0) to track filled slots.
Implementation Logic
The Producer Process
while (true) {
// Produce an item
wait(empty); // Decrement empty count (block if 0)
15
wait(mutex); // Lock the buffer
// Add item to buffer
signal(mutex); // Unlock the buffer
signal(full); // Increment full count
The Consumer Process
while (true) {
wait(full); // Decrement full count (block if 0)
wait(mutex); // Lock the buffer
// Remove item from buffer
signal(mutex); // Unlock the buffer
signal(empty); // Increment empty count
• Mutual Exclusion: Only one process can modify the buffer pointers at a time. If the
producer is writing, the consumer must wait, and vice versa.
• Synchronization: The producer and consumer must stay in sync. If the producer is
much faster, it must wait for the consumer to create space.
• Avoidance of Deadlock: The order of wait() operations is crucial. If a process locks
the mutex before checking if the buffer is empty or full, it could lead to a deadlock
where everyone is waiting and nobody can move.
• Avoidance of Starvation: The system must ensure that both the producer and
consumer eventually get a turn to access the buffer.
16
Applications:
This problem isn't just theoretical; it’s fundamental to:
• Print Spoolers: Your document (Producer) goes to a buffer, and the Printer
(Consumer) takes it when ready.
• Compilers: The lexical analyzer produces tokens for the syntax analyzer to consume.
• Web Servers: Incoming requests are buffered before being handled by worker
threads.
2. The Dining Philosophers Problem
The Dining Philosophers Problem is a classic synchronization problem proposed by Edsger
Dijkstra in 1965. It is used to illustrate the challenges of resource allocation and deadlock in
a multi-process system.
Imagine five philosophers sitting around a circular table. They spend their lives alternating
between two states: thinking and eating.
• In the center of the table is a large bowl of rice.
• There are five chopsticks (or forks) placed between each pair of philosophers.
• To eat, a philosopher must pick up two chopsticks—one from their left and one from
their right.
• When finished eating, they put down both chopsticks and start thinking again.
The chopsticks represent shared resources. Since there are only five chopsticks for five
philosophers, not everyone can eat at the same time. The problem arises when multiple
philosophers try to eat simultaneously, leading to:
• Deadlock: If every philosopher picks up their left chopstick at the same time, they
will all be waiting forever for their right chopstick to become available. None can eat,
and none will release their resource.
• Starvation: A philosopher might never get to eat because their neighbours are
constantly alternating between eating and thinking, keeping the chopsticks
occupied.
Solution using Semaphores
We represent each chopstick as a semaphore. An array of semaphores chopstick[5] is
initialized to 1.
17
Implementation Logic
while (true) {
wait(chopstick[i]); // Pick up left chopstick
wait(chopstick[(i + 1) % 5]); // Pick up right chopstick
// EATING...
signal(chopstick[i]); // Put down left chopstick
signal(chopstick[(i + 1) % 5]); // Put down right chopstick
// THINKING...
}
How to Prevent Deadlock
The basic semaphore solution above can still lead to deadlock. To fix this, we can apply one
of the following rules:
1. Limit Attendance: Allow only four philosophers to sit at the table simultaneously,
ensuring at least one philosopher can always pick up two chopsticks.
2. Asymmetric Solution: Odd-numbered philosophers pick up their left chopstick first,
while even-numbered philosophers pick up their right chopstick first.
3. Wait for Both: A philosopher is allowed to pick up chopsticks only if both the left and
right ones are available at the same time (usually implemented using a Monitor or
state-checking).
This problem is a metaphor for:
18
• Process Synchronization: How multiple processes share limited hardware resources
(like CPUs or I/O devices).
• Resource Management: Developing algorithms that ensure the system remains
"liveness" (no deadlock) and "fair" (no starvation).
3. The Readers-Writers Problem
The Readers-Writers Problem is a classic synchronization challenge that deals with multiple
processes accessing a shared data area (like a database or a file). It focuses on managing
access when some processes only need to read data while others need to update it.
The situation involves two types of processes:
• Readers: These processes only read the data. Multiple readers can read the shared
data simultaneously without any issues.
• Writers: These processes update or modify the data. When a writer is accessing the
data, no other process (reader or writer) should be allowed to access it.
The Constraints:
1. Multiple Readers: Many readers can read at once.
2. Exclusive Writer: Only one writer can write at a time.
3. No Interruption: If a writer is writing, no reader can start reading.
4. Mutual Exclusion: If a reader is reading, no writer can start writing.
The Solution using Semaphores:
To solve this, we typically use two semaphores and an integer variable:
1. rw_mutex (Semaphore): Initialized to 1. It ensures mutual exclusion for the writers.
It is also used by the first/last reader to "lock" the data from writers.
2. mutex (Semaphore): Initialized to 1. It ensures mutual exclusion when updating the
read_count variable.
3. read_count (Integer): Initialized to 0. It keeps track of how many readers are
currently accessing the data.
Implementation Logic
The Writer Process
The writer simply waits for the rw_mutex to be free, performs the write, and then releases
it.
19
while (true) {
wait(rw_mutex); // Lock access for writers and readers
// WRITING IS PERFORMED...
signal(rw_mutex); // Release access
}
The Reader Process
The logic for readers is slightly more complex because only the first reader needs to lock the
writer out, and only the last reader needs to signal that writers can enter again.
while (true) {
wait(mutex); // Lock read_count update
read_count++;
if (read_count == 1) {
wait(rw_mutex); // First reader locks the writer
}
signal(mutex); // Unlock read_count update
// READING IS PERFORMED...
wait(mutex); // Lock read_count update
read_count--;
if (read_count == 0) {
signal(rw_mutex); // Last reader unlocks the writer
}
signal(mutex); // Unlock read_count update
}
Analysis :
• Starvation: In the standard solution (Reader Preference), if a steady stream of
readers arrives, a writer might wait indefinitely. This is a major drawback.
• Concurrency: This problem highlights the difference between Mutual Exclusion
(necessary for writers) and Concurrency (allowable for readers).
• Real-World Example: Consider an online flight booking system. Thousands of people
can view (read) the seat availability at once, but only one process can successfully
book (write/update) a specific seat to avoid double-booking.
20