Process Synchronization
Presented By
Mr. Ajay Maurya
Process Synchrnization
• Process Synchrnization is a technique used in an operating
system to Control the execution of multiple processes so that
they can safely shared data and resources without causing
errors.
• Shared Resources (Variable, Memory, Code, Resources(CPU,
Printer, Scanner.))
• It is mainly required in Concurrent(Co-operative)
Concurrent(Co Processes.
Why Synchronization Needed?
• When Two or More Processes access shared data at the same time, It
may cause:
• Data Inconsistency
• Race Condition
• Unexpected Result
Example
Process P1 Process P2
Int shared = 5
Int x = shared Int y = shared
x++ Y--
sleep(1) sleep(1)
shared = x shared = y
Result
• Final output will be based on execution order:
• If firstly Process P1 is running then output will be 4.
• If firstly Process P2 is running then output wiil be 6.
• This condition in known as Race Condition. Processes are doing race
in between to get the results based on execution order.
Code Segment(Problem)
Code Segment(Solution)
Problem in Concurrency
Race Condition : When two processes access shared data at
the same time and results depends on execution order.
Deadlock : Two or more processes are waiting for each other
to release resources.
Starvation : A process never CPU Time.
Critical Section : A critical section is the part of program
where a process accesses shared resource or shared data.
• Only one process at a time should execute the Critical Section to
avoid errors or data inconsistency.
inconsistency
Why Critical Section Needed?
• When multiple processes are running concurrently
and access shared resources, following problem may
occure:
• Race Condition
• Data Inconsistency
• Unexpected Result
• Therefore, the Operating System must control access
to the Critical Section.
Solutions/Requirement for Critical Section
A correct solution must satisfy three condition:
1. Mutual Exclusion
• Only one process can execute the critical section at a time.
2. Progress
• If no process in Critical Section, another process should be
allowed to enter.
3. Bound Waiting
• A process should not wait forever to enter critical section.
Critical Section
Structure of Critical Section Example of Critical Section
A typical process using a do{
critical section has 4-Parts Entry Section
1. Entry Section Critical Section
2. Critical Section
Exit Section
3. Exiti Section
Remainder Section
4. Remainder Section
}while(true)
Method to solve Critical Section Problem
Operating System use several Techniques:
• Lock Variable
• Peterson’s Solutions
• Semaphores
• Mutex
• Monitors
Producer Consumer Problem / Bounded Buffer
Problem
• The Producer Consumer Problem is a classical Process
Synchronization problem in an operating system.
• It occurs when:
• A Producer process produces data/items.
• A Consumer process consumes those data/items.
• Both are shared a common buffer(Shared Memory)
• The buffer has limited size, so proper coordination is
required.
Main issue in Producer Consumer Problem
Without synchronization, the following problems may occur :
• Buffer Overflow
• Producer tries to add an item when the buffer is full.
• Buffer Underflow
• Consumer tries to remove an item when the buffer is
empty.
• Race Condition
• Producer and Consumer access the buffer simultaneously,
causing incorrect data.
Pseudo Code for Producer Consumer Problem
Pseudo Code for Printer Spooler Problem
Spooler Directory
0
5
Critical Section Problem
• The Critical Section Problem occurs in a multitasking operating system
when multiple processes or threads share common resources (like
variable, files, files or memory) and try to access or modify them
simultaneously.
• What is Critical Section?
• A critical section is a part of program where shared resources are
accessed.
• “If two processes execute this at the same time, incorrect results
may occure due to race conditions.”
Why is it a Problem?
• If two or more processes enter their critical sections at the same time
and manipulated shared data, it may lead to:
• Race conditions
• Data Inconsistencey
• Unexpected results
Requirements for Good Solutions
Any solution to the critical section problem must satisfy four
conditions:
• Mutual Exclusion
Only one process can enter the critical section at a
Only
time.
• Progress
If no process is in the critical section, the decision of
If
who enters next cannot be postponed indefinitely.
Requirements for Good Solutions
• Bounded Waiting
AA process should not wait forever to enter the critical
section (no starvation)
• No assumption related to hardware speed
To achieve synchronization in Critical Section I have
To
given a solution and said that this solution will run on a
32 bit system, on Operating System, would not run on
64. This is not a condition, means there should not be
an assumption like this.
Method to solve Critical Section Problem
Operating System use several Techniques:
• Lock Variable
• Peterson’s Solutions
• Semaphores
• Mutex
• Monitors
Lock Variable
A Lock Variable is a simple method used to solve the critical section
problem in an Operating System. It ensures that only one process can
enter the critical section at a time.
time
• A lock variable is a shared variable used to control access to the
critical section.
• If lock = 0 → Cri cal sec on is free
• If lock = 1 → Cri cal sec on is busy (locked)
Working of Lock Variable
Steps:
• A process checks the value of lock.
• If lock = 0, the process sets lock = 1 and enters the critical section.
• After finishing, the process sets lock = 0 to release the resource.
Simple Example (Pseudo Code)
while(lock == 1); // wait until lock becomes 0
lock = 1; // acquire lock
/* Critical Section */
printf("Process is using shared resource");
lock = 0; // release lock
Problem with Lock Variable
• The lock variable solution is not perfect because it may fail in
multiprocessing environments.
environments
• Example problem:
• Two processes check lock at the same time when it is 0.
Both may set it to 1 simultaneously and enter the critical
section, causing a race condition.
condition
• So it does not guarantee mutual exclusion.
exclusion
Better Solutions
Because of the limitations of lock variables, better
mechanisms are used:
• Test and Set Instruction
• Peterson's Algorithm
• Semaphores
• Mutex locks
“A lock variable is a shared variable that indicates whether a
critical section is free or busy,, but it is not a reliable solution
for process synchronization.”
Test and Set Instruction
• Test-and-Set is a instruction used in process synchronization
to solve the critical section problem. It ensures that only
one process can enter the critical section at a time.
• Test-and-Set is an atomic (indivisible) instruction that:
1. Tests the value of a lock variable.
variable
2. Sets it to true (locked) in one single operation.
• Because it is atomic, no other process can interrupt it during
execution.
Working idea
A shared variable lock is used.
• lock = 0 → Cri cal sec on is free
• lock = 1 → Cri cal sec on is busy
When a process wants to enter the critical section:
• It executes Test-and-Set(lock)
Set(lock)
• If lock was 0, it becomes 1 and the process enters.
• If lock was 1,, the process keeps waiting.
Code Implementation
Simple Example (Real Life)
Imagine a single bathroom with a door lock.
lock
1. lock = 0 → Bathroom free
2. lock = 1 → Someone inside
Steps:
1. Person checks door and locks it (Test-and-Set).
(Test
2. If already locked → waits outside.
3. A er use → unlocks the door.
So only one person can use the bathroom at a time.
time
Turn Variable (Strict Alteration)
In Operating Systems, the Turn Variable is a shared variable
used in process synchronization to control which process is
allowed to enter the critical section.
section
• A turn variable is a shared integer variable that indicates
whose turn it is to enter the critical section.
section
• If turn = 0 → Process P0 can enter the critical section.
• If turn = 1 → Process P1 can enter the critical section.
• This technique is used in software solutions of the critical
section problem.
Basic Idea
Two processes P0 and P1 share a variable:
turn = 0
Process P0 Process P1
while(turn!=1);
while(turn!=0);
//Critical Section
//Critical Section
turn = 0
turn = 1
Simple Example (Real Life)
Imagine two students sharing one computer.
computer
• turn = 0 → Student P0 uses the computer.
• After finishing, P0 sets turn = 1.
• Now P1 can use the computer.
They alternate turns to use the resource.
Peterson’s Solutions
Peterson’s Solution is a classic algorithm used in Operating Systems to
solve the mutual exclusion (critical section) problem for two
processes.
• It uses two shared variables:
1. flag[2] → indicates whether a process wants to enter the critical
section.
2. turn → indicates whose turn it is to enter.
• So each process:
• Announces its intention to enter the critical section.
• Gives priority to the other process if both want to enter at the
same time.
Peterson’s Solutions
Properties of Peterson’s Solution
Peterson’s solution satisfies the three requirements of the critical
section problem:
1. Mutual Exclusion
Only one process enters the critical section.
2. Progress
If no process is in the critical section, one waiting process will
enter.
3. Bounded Waiting
A process will not wait forever.
Mutext
A Mutex is a locking mechanism that allows only one process/thread
to access a shared resource at a time. Other processes must wait until
the lock is released.
A mutex has two states:
1. Locked → Resource is being used
2. Unlocked → Resource is free
Steps:
1. Process requests the mutex lock.
lock
2. If the lock is free → process enters the critical section.
3. A er finishing → process releases the lock.
lock
Example
Imagine two processes sharing one printer.
printer
• Process P1 locks the mutex → uses printer.
• Process P2 tries to print → must wait.
• When P1 unlocks the mutex,, P2 can use the printer.
Thus only one process prints at a time.
time
• Advantages
✔ Prevents race conditions
✔ Ensures mutual exclusion
✔ Simple locking mechanism
Advantage & Disadvantage
• Advantages
✔ Prevents race conditions
✔ Ensures mutual exclusion
✔ Simple locking mechanism
• Disadvantages
❌ If not released properly → deadlock may occur
❌ Other processes may have to wait
Mutex (Code Implementation)
Semaphore
• A Semaphore is a synchronization mechanism used in an Operating
System to control access to shared resources when multiple
processes or threads are executing concurrently.
• It helps prevent race conditions and ensures proper process
synchronization.
• A semaphore is basically an integer variable that is accessed only
through two atomic operations:
• wait() (P operation) P() Down() Wait()
• signal() (V operation)
V() Up() Signal()
Operations on Semaphore
1. wait() Operation
Executed when a process want to use a resource.
wait(S)
{
S = S - 1;
if(S < 0)
wait until resource becomes available
}
Meaning :
• Decrease the semaphore value.
• If the value become negative, the process must wait.
Operations on Semaphore
2. signal() Operation
Executed when a process releases the resource.
signal(S)
{
S = S + 1;
if(S <= 0)
wake up one waiting process
}
Meaning:
• Increases the semaphore value.
• Wakes up one waiting process.
Types of Semaphore
There are two main types of semaphores.
semaphores
1. Binary Semaphore
• A Binary Semaphore can have only two values: 0 or 1.
• Used for mutual exclusion.
• Similar to a lock mechanism.
mechanism
Types of Semaphore
Example
Suppose one printer is shared by multiple processes.
Initial value:
S=1
Steps:
• Process P1 executes wait(S) → S = 0 → uses printer.
• Process P2 executes wait(S) → must wait.
• After printing, P1 executes signal(S) → S = 1.
• Now P2 can use the printer.
✔ Only one process uses the printer at a time.
time
Types of Semaphore
2. Counting Semaphore
• A Counting Semaphore can have multiple integer values
(0,1,2,3...).
• Used when multiple instances of a resource are available.
Types of Semaphore
Example
Suppose there are 3 printers in a lab.
Initial value:
S=3
Steps:
1. Three processes can execute wait(S) and use printers.
2. If a fourth process requests a printer → it must wait.
3. When any process finishes → it executes signal(S) → another
process can use the printer.
✔ Thus multiple resources can be managed efficiently.
efficiently
Difference Between Binary and Counting Semaphore
Feature Binary Semaphore Counting Semaphore
Values 0 or 1 0,1,2,3…
Resource Single resource Multiple resources
Purpose Mutual exclusion Resource management
Counting Semaphore
down(Semaphore s){ up(Semaphore s){
up
[Link] = [Link] – 1; [Link] = [Link] + 1;
If([Link] < 0){ If([Link] <= 0){
//put process in suspended
list //select a process from suspended
//sleep(); //list and wake up();
}else{ }
//Critical Section }
}
}
Binary Semaphore
down(Semaphore s){ up(Semaphore s){
up
If([Link] == 1){ If(suspended list is empty){
//cs
[Link] = 0; [Link] = 1;
}else{ }else{
//Block this process and //Select a proces from
place in suspended list, suspended list and wake up();
sleep();
} }
} }
Reader–Writer
Writer Problem
The Reader–Writer Problem is a classical synchronization problem in
Operating Systems. It deals with a situation where multiple processes
want to read and write shared data (such as a file or database).
The processes are divided into two types:
• Readers → Only read the data
• Writers → Modify (write) the data
Basic Rule
• Multiple readers can read the data at the same time.
• Only one writer can write at a time.
• When a writer is writing, no reader should read.
This ensures data consistency.
Example
• Suppose there is a database file.
file
• Many users are reading the file → Allowed simultaneously.
• If one user wants to update the file → No other reader or writer
should access it until writing finishes.
Example
Reader1 → Reading database
Reader2 → Reading database
Reader3 → Reading database
Writer1 → Must wait
When all readers finish:
Writer1 → Starts wri ng
During writing:
Reader1, Reader2 → Must wait
Solution Using Semaphores
We use:
• mutex → Protects reader count variable
• wrt → Controls access to shared data
Variable:
• readcount → Number of readers currently reading
Reader – Writer Problem
Int rc = 0;
Binary Semaphore mutex =
Down(mutex); Void writer(){
Rc = rc – 1;
1
If(rc == 0){
While(true){
Binary Semaphore db = 1
Void reader(){
Up(db) Down(db)
}
While(true){ Db // CS
Up(mutex)
Down(mutex);
Process_data; Up(db)
Rc = rc +1
If(rc == 1) then down(db);
} }
}
Up(mutex) }
Db // CS
How It Works
1. First reader locks writer access.
2. Other readers can read simultaneously.
simultaneously
3. Writer must wait until all readers finish.
finish
4. A er the last reader exits → writer gets access.
access
Real-Life Example
Think of a library 📚 :
• Many students can read books at the same time.
time
• If a librarian wants to update the book record,
record nobody can read
until the update finishes.
Sleeping Barber Problem
• The Sleeping Barber Problem is a classical synchronization
problem in Operating Systems that demonstrates how
processes coordinate using shared resources. It was
introduced by Edsger W. Dijkstra.
Dijkstra
• The problem models a barber shop where a barber serves
customers, and synchronization is needed between the
barber process and customer processes.
Problem Description
Consider a barber shop with:
• 1 Barber
• 1 Barber chair
• N waiting chairs for customers
The challenge is to synchronized the barber and customer so that-
that
• The barber does not sleep when there are customer waiting.
• Customer do not leave unnecessarily.
• No two person occupy the barber chair at same time.
• Customer are served in FIFO order.
Rules
1. If no customers are present,, the barber sleeps.
2. When a customer arrives:
• If the barber is sleeping → the customer wakes the barber.
• If the barber is busy → the customer sits in a waiting chair.
3. If all waiting chairs are full,, the customer leaves the shop.
4. When the barber finishes a haircut:
• If there are customers wai ng → he takes the next customer.
• If no customers are wai ng → he goes to sleep again.
Goal of the Problem
The goal is to avoid:
• Race conditions
• Deadlock
• Busy waiting
and ensure proper process synchronization between barber and
customers.
Sleeping Barber Solution using Semaphore
We use three semaphores:
• customers → number of customers wai ng
• barbers → number of barbers available
• mutex → protects access to wai ng chairs
Also a variable:
• waiting → number of wai ng customers
Pseudocode
Barber Process Customer Process
while(true){ wait(mutex);
if(waiting < N){
wait(customers); // sleep if no waiting = waiting + 1;
customers
signal(customers); // notify barber
wait(mutex); // enter critical signal(mutex);
section
wait(barbers); // wait until barber ready
waiting = waiting - 1; get_haircut();
signal(barbers); // barber ready }
signal(mutex); // leave critical else{
section signal(mutex);
cut_hair(); leave_shop();
} }
Simple Working Example
Suppose:
• Waiting chairs = 3
Scenario
1. No customers → barber sleeps.
sleeps
2. Customer1 arrives → wakes barber → haircut starts.
3. Customer2 and Customer3 arrive → sit in wai ng chairs.
4. Customer4 arrives → waits if chair available.
5. If all chairs are full → customer leaves.
leaves
Diagram (Concept)
Customers → Wai ng Chairs → Barber Chair → Barber
If no customer → Barber Sleeps
If chairs full → Customer Leaves
Key Concepts Demonstrated
• Mutual Exclusion
• Process Synchronization
• Semaphore usage
• Resource sharing