Process Synchronization
Process Synchronization is a mechanism in operating systems used to
manage the execution of multiple processes that access shared resources.
Its main purpose is to ensure data consistency, prevent race conditions and
avoid deadlocks in a multi-process environment.
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 is the coordination of multiple cooperating processes
in a system to ensure controlled access to shared resources, thereby
preventing race conditions and other synchronization problems.
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.
Required conditions for Process Synchronization
1. Critical Section: 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.
2. 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.
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.
Critical Section in Synchronization
A critical section is a part of a program where shared resources (like
memory, files, or variables) are accessed by multiple processes or threads.
To avoid problems such as race conditions and data inconsistency, only one
process/thread should execute the critical section at a time using
synchronization techniques.
Structure of a Critical Section
A critical section is a key concept in operating systems that ensures safe and
controlled access to shared resources when multiple processes or threads are
executing simultaneously. It helps prevent issues like race conditions and data
inconsistency by allowing only one process or thread to access the shared
resource at a time, using synchronization techniques for proper coordination.
1. Entry Section
The process requests permission to enter the critical section.
Synchronization tools (e.g., mutex, semaphore) are used to control access.
2. Critical Section: The actual code where shared resources are accessed or
modified.
3. Exit Section: The process releases the lock or semaphore, allowing other
processes to enter the critical section.
4. Remainder Section: The rest of the program that does not involve shared
resource access.
Critical Section Problem
Shared Resources and Race Conditions
Shared resources include memory, global variables, files, and databases.
A race condition occurs when two or more processes attempt to update
shared data at the same time, leading to unexpected
results. Example: Two bank transactions modifying the same account
balance simultaneously without synchronization may lead to incorrect final
balance.
It could be visualized using the pseudo-code below
do{
flag=1;
while(flag); // (entry section)
// critical section
if (!flag)
// remainder section
} while(true);
Requirements of Critical Section Solutions
1. Mutual Exclusion
At most one process can be inside the critical section at a time.
Prevents conflicts by ensuring no two processes update the shared
resource simultaneously.
2. Progress
If no process is in the critical section, and some processes want to enter,
the choice of who enters next should not be postponed indefinitely.
Ensures that the system continues to make progress rather than getting
stuck.
3. Bounded Waiting
There must be a limit on how long a process waits before it gets a chance
to enter the critical section.
Prevents starvation, where one process is repeatedly bypassed while
others get to execute.
olution to Critical Section Problem :
A simple solution to the critical section can be thought of as shown below,
acquireLock();
Process Critical Section
releaseLock();
A thread must acquire a lock prior to executing a critical section. The lock can
be acquired by only one thread. There are various ways to implement locks in
the above pseudo-code.
Examples of critical sections in real-world applications
Banking System (ATM or Online Banking)
Critical Section: Updating an account balance during a deposit or
withdrawal.
Issue if not handled: Two simultaneous withdrawals could result in an
incorrect final balance due to race conditions.
Ticket Booking System (Airlines, Movies, Trains)
Critical Section: Reserving the last available seat.
Issue if not handled: Two users may be shown the same available seat
and both may book it, leading to overbooking.
Print Spooler in a Networked Printer
Critical Section: Sending print jobs to the printer queue.
Issue if not handled: Print jobs may get mixed up or skipped if multiple
users send jobs simultaneously.
File Editing in Shared Documents (e.g., Google Docs, MS Word with
shared access)
Critical Section: Saving or writing to the shared document.
Issue if not handled: Simultaneous edits could lead to conflicting versions
or data loss.
Race Condition
A race condition occurs when two or more processes or threads access and
modify the same data at the same time, and the final result depends on the
order in which they run. Without proper coordination, this can lead to incorrect
or unpredictable results.
For example: If two people update the same bank account simultaneously
without checking each other’s changes, the final balance may be wrong.
Shared Resource: A variable, file, memory location, or device accessed
by multiple processes.
Concurrency: Multiple processes or threads executing simultaneously or
overlapping in execution.
Non-Atomic Operations: Operations that can be interrupted, such as
read-modify-write, which can cause inconsistent states when multiple
processes access the same data concurrently.
Causes of Race Conditions
Simultaneous Access: When two or more processes try to read or write
the same shared resource at the same time.
Non-Atomic Updates: Operations like increment or decrement are not
indivisible.
Lack of Synchronization: No mechanisms like locks, semaphores, or
monitors are used to control access.
Improper Scheduling: OS scheduler interrupts processes at critical
moments.
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.
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 results in an incorrect final value.
In many cases, the final balance may incorrectly be 110 or 90, instead of the
expected 100. This is a classic race condition.
Effects of Race Conditions
Data Corruption: Shared data may become inconsistent.
Unpredictable Behavior: The output may vary every time the program
runs.
Security Risks: Race conditions can be exploited, e.g., in banking
transactions or authentication bypass.
System Crashes: Critical system data may get corrupted, leading to
failures.
Prevention Techniques
1. Mutex (Mutual Exclusion): Ensure only one process can enter the critical
section at a time.
2. Semaphores: Counting or binary semaphores control access to resources.
3. Monitors: High-level synchronization constructs that manage shared
resources.
4. Atomic Operations: Use hardware or software-supported atomic
instructions.
5. Disable Interrupts (for kernel-level programming): Prevent context
switches during critical sections.
6. Proper Scheduling: Ensure the scheduler does not preempt critical
section execution.
What is Mutual Exclusion?
Mutual Exclusion is a property of process synchronization that 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:
Interrupt handlers
Interleaved, preemptively scheduled processes/threads
Multiprocessor clusters, with shared memory
Distributed systems
Conditions Required for Mutual Exclusion
According to the following four criteria, mutual exclusion is applicable:
When using shared resources, it is important to ensure mutual exclusion
between various processes. There cannot be two processes running
simultaneously in either of their critical sections.
It is not advisable to make assumptions about the relative speeds of the
unstable processes.
For access to the critical section, a process that is outside of it must not
obstruct another process.
Its critical section must be accessible by multiple processes in a finite
amount of time; multiple processes should never be kept waiting in an
infinite loop.
Approaches To Implementing Mutual Exclusion
Software Method: Leave the responsibility to the processes themselves.
These methods are usually highly error-prone and carry high overheads.
Hardware Method: Special-purpose machine instructions are used for
accessing shared resources. This method is faster but cannot provide a
complete solution. Hardware solutions cannot give guarantee the absence
of deadlock and starvation.
Programming Language Method: Provide support through the operating
system or through the programming language.
Requirements of Mutual Exclusion
At any time, only one process is allowed to enter its critical section.
The solution is implemented purely in software on a machine.
A process remains inside its critical section for a bounded time only.
No assumption can be made about the relative speeds of asynchronous
concurrent processes.
A process cannot prevent any other process from entering into a critical
section.
A process must not be indefinitely postponed from entering its critical
section.
Peterson's Algorithm in Process
Synchronization
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.
Example Use Cases
Peterson’s Algorithm can be used (theoretically) in:
Accessing a shared printer: Peterson's solution ensures that only one
process can access the printer at a time when two processes are trying to
print documents.
Reading and writing to a shared file: It can be used when two processes
need to read from and write to the same file, preventing concurrent access
issues.
Competing for a shared resource: When two processes are competing
for a limited resource, such as a network connection or critical hardware,
Peterson’s solution ensures mutual exclusion to avoid conflicts.
Hardware Synchronization Algorithms :
Unlock and Lock, Test and Set, Swap
Process Synchronization problems occur when two processes running
concurrently share the same data or same variable. The value of that variable
may not be updated correctly before its being used by a second process.
Such a condition is known as Race Around Condition. There are a software as
well as hardware solutions to this problem. In this article, we will talk about the
most efficient hardware solution to process synchronization problems and its
implementation.
There are three algorithms in the hardware approach of solving Process
Synchronization problem:
1. Test and Set
2. Swap
3. Unlock and Lock
Hardware instructions in many operating systems help in the effective solution
of critical section problems.
1. Test and Set:
Here, the shared variable is lock which is initialized to false. TestAndSet(lock)
algorithm works in this way – it always returns whatever value is sent to it and
sets lock to true. The first process will enter the critical section at once as
TestAndSet(lock) will return false and it’ll break out of the while loop. The
other processes cannot enter now as lock is set to true and so the while loop
continues to be true. Mutual exclusion is ensured. Once the first process gets
out of the critical section, lock is changed to false. So, now the other
processes can enter one by one. Progress is also ensured. However, after the
first process, any process can go in. There is no queue maintained, so any
new process that finds the lock to be false again can enter. So bounded
waiting is not ensured.
Test and Set Pseudocode -
//Shared variable lock initialized to false
boolean lock;
boolean TestAndSet (boolean &target){
boolean rv = target;
target = true;
return rv;
}
while(1){
while (TestAndSet(lock));
critical section
lock = false;
remainder section
}
2. Swap:
Swap algorithm is a lot like the TestAndSet algorithm. Instead of directly
setting lock to true in the swap function, key is set to true and then swapped
with lock. First process will be executed, and in while(key), since key=true ,
swap will take place and hence lock=true and key=false. Again next iteration
takes place while(key) but key=false , so while loop breaks and first process
will enter in critical section. Now another process will try to enter in Critical
section, so again key=true and hence while(key) loop will run and swap takes
place so, lock=true and key=true (since lock=true in first process). Again on
next iteration while(key) is true so this will keep on executing and another
process will not be able to enter in critical section. Therefore Mutual exclusion
is ensured. Again, out of the critical section, lock is changed to false, so any
process finding it gets t enter the critical section. Progress is ensured.
However, again bounded waiting is not ensured for the very same reason.
Swap Pseudocode -
// Shared variable lock initialized to false
// and individual key initialized to false;
boolean lock;
Individual key;
void swap(boolean &a, boolean &b){
boolean temp = a;
a = b;
b = temp;
}
while (1){
key = true;
while(key)
swap(lock,key);
critical section
lock = false;
remainder section
}
3. Unlock and Lock :
Unlock and Lock Algorithm uses TestAndSet to regulate the value of lock but
it adds another value, waiting[i], for each process which checks whether or not
a process has been waiting. A ready queue is maintained with respect to the
process in the critical section. All the processes coming in next are added to
the ready queue with respect to their process number, not necessarily
sequentially. Once the ith process gets out of the critical section, it does not
turn lock to false so that any process can avail the critical section now, which
was the problem with the previous algorithms. Instead, it checks if there is any
process waiting in the queue. The queue is taken to be a circular queue. j is
considered to be the next process in line and the while loop checks from jth
process to the last process and again from 0 to (i-1)th process if there is any
process waiting to access the critical section. If there is no process waiting
then the lock value is changed to false and any process which comes next
can enter the critical section. If there is, then that process’ waiting value is
turned to false, so that the first while loop becomes false and it can enter the
critical section. This ensures bounded waiting. So the problem of process
synchronization can be solved through this algorithm.
Unlock and Lock Pseudocode -
// Shared variable lock initialized to false
// and individual key initialized to false
boolean lock;
Individual key;
Individual waiting[i];
while(1){
waiting[i] = true;
key = true;
while(waiting[i] && key)
key = TestAndSet(lock);
waiting[i] = false;
critical section
j = (i+1) % n;
while(j != i && !waiting[j])
j = (j+1) % n;
if(j == i)
lock = false;
else
waiting[j] = false;
remainder section
}
Hardware-based solutions
Hardware-based solutions to the critical section problem use special
instructions like Test-and-Set and Swap. These instructions help manage
access to shared resources by allowing only one process to enter the critical
section at a time. They are fast and efficient, making them ideal for systems
with advanced hardware support.
Various hardware solutions to the Critical Section Problem are:
Test and Set
Swap
1. Test and Set
TAS is an atomic instruction that reads a variable’s old value and sets it to
true in a single indivisible step.
boolean lock = false; // Shared lock variable
boolean TestAndSet(boolean &target) {
boolean rv = target; // Step 1: Read old value
target = true; // Step 2: Set lock (mark busy)
return rv; // Step 3: Return old value
}
while (1) {
while (TestAndSet(lock)); // Entry Section → Busy wait until lock is free
// ---- Critical Section ----
lock = false; // Exit Section → Release lock
// ---- Remainder Section ----
}
Explanation of Pseudocode:
Mutual Exclusion
Only one process can enter the critical section at a time because
TestAndSet is atomic.
If one process sets lock = true, all others will keep spinning in the inner
while.
Critical Section Protection
A process enters only if TestAndSet(lock) returns false (lock was free).
If it returns true, the process keeps waiting.
Exit Section
After finishing, the process releases the lock by setting lock = false.
2. Swap (and CAS Enhancement)
The Swap instruction is a hardware-based synchronization mechanism similar
to Test-and-Set. Instead of directly setting the lock, it swaps the values of a
shared lock variable and a local key variable. This ensures mutual exclusion
because only one process can set its key to false and enter the critical
section, while others keep spinning.
boolean lock = false; // Shared variable
boolean key; // Local per-process variable
void swap(boolean &a, boolean &b) {
boolean temp = a;
a = b;
b = temp;
}
while (1) {
key = true; // Process wants to enter
while (key) // Entry Section
swap(lock, key); // Keep swapping until lock becomes true & key false
// ---- Critical Section ----
lock = false; // Exit Section → Release lock
}
Explanation of Pseudocode
1. Initialization
lock = false means no process is inside the critical section.
Each process has a local key variable (initially false).
2. Entry Section
A process sets key = true (wants to enter).
It then calls swap(lock, key):
If lock was false, swap makes key = false and lock = true, so the process
enters.
If lock was already true, key remains true, and the process spins in the
loop.
3. Critical Section: Only the process that successfully swapped and got key =
false enters.
4. Exit Section: When the process leaves, it sets lock = false, allowing other
waiting processes to try again.
5. Remainder Section: The process executes other code before attempting
entry again.
The Swap instruction ensures mutual exclusion and progress, but like Test-
and-Set, it suffers from busy waiting and no bounded waiting guarantee.
Compare-and-Swap (CAS) Enhancement
Modern CPUs often use CAS (Compare-and-Swap), which improves
efficiency compared to Swap. CAS atomically compares a variable to an
expected value and updates it only if they match.
int lock = 0; // 0 = free, 1 = busy
boolean CompareAndSwap(int &target, int expected, int new_val) {
int old = target;
if (target == expected)
target = new_val;
return old == expected; // true if swap succeeded
}
while (1) {
while (!CompareAndSwap(lock, 0, 1)); // Try to acquire lock
// ---- Critical Section ----
lock = 0; // Exit Section → Release lock
}
Key Points
Mutual Exclusion: Only one process at a time can succeed in swapping
values.
Progress: If the lock is free, a process will eventually enter.
Drawbacks: Both Swap and CAS suffer from busy waiting and no bounded
waiting guarantee as some processes may starve.
3. Spinlock
A Spinlock is a higher-level abstraction built using Test-and-Set or CAS.
A process repeatedly checks if the lock is free (spins) instead of sleeping.
Useful when waiting times are short (e.g., in kernel or multiprocessor
systems).
Example with Test-and-Set:
int lock = 0; // 0 = free, 1 = busy
void acquire() {
while (TestAndSet(lock)); // Busy wait
}
void release() {
lock = 0;
}
while (1) {
acquire();
// ---- Critical Section ----
release();
// ---- Remainder Section ----
}
Pros:
Very fast on multiprocessor systems (no context switching overhead).
Simple to implement with atomic instructions.
Cons:
Causes busy waiting → wastes CPU cycles.
Not suitable for long critical sections.
Comparison of Hardware-Based Solutions
Method Mechanism Pros Cons
Test-and-Set Atomically sets lock Simple, widely Busy waiting,
Method Mechanism Pros Cons
variable supported starvation possible
Swap shared & local Ensures mutual Busy waiting, less
Swap
variables exclusion efficient than CAS
CAS Compare-and-swap Efficient, lock- Still spins under
(enhanced) atomic update free possible contention
Lock abstraction (built Very fast for
Spinlock CPU wasting, not f
on TAS/CAS) short waits