Process Synchronization
Deadlock Handling
Round Robin
Process Scheduling and Synchronization
Critical Section Problem
Process Synchronization is
a technique used to coordinate multiple processes so they can safely share
resources (like memory, files, variables) without causing errors or
inconsistencies.
Critical Section Problem (Operating
Systems)
The Critical Section Problem is about designing a
protocol so that multiple processes can safely access shared resources (like
variables, files, memory) without causing errors.
The Critical Section Problem is a fundamental concept
in Operating Systems that deals with how multiple processes can safely share
resources without causing errors.
What is a Critical Section?
A critical section is the part of a process where it
accesses shared data.
A critical section is the part of a program where a
process accesses shared data/resources (like variables, files, memory).
Structure of a Process:
while(true) {
Entry Section // request access
Critical Section // access shared resource
Exit Section // release resource
Remainder Section // other work
}
The Problem
When multiple processes enter their critical sections
at the same time, it can lead to:
Race Condition
Incorrect results
Data inconsistency
Example
Shared variable: count = 5
Process P1: count++
Process P2: count--
If both execute simultaneously, final value may be
wrong (not 5).
Requirements (Solution Conditions)
To solve the critical section problem, a
solution must satisfy:
1. Mutual Exclusion
Only one process at a time can execute in the critical
section
2. Progress
If no process is in the critical section,
One of the waiting processes should be allowed to
enter
Decision should not be delayed indefinitely
3. Bounded Waiting
A process should not wait forever
There must be a limit on how many times others can
enter before it
Solutions to Critical Section Problem
1. Software Solutions
Peterson’s Algorithm (for 2 processes)
Uses shared variables like flag and turn
Ensures mutual exclusion without hardware
2. Hardware Solutions
Test-and-Set instruction
Compare-and-Swap
These provide atomic operations.
3. High-Level Solutions
Mutex (Lock)
lock()
critical section
unlock()
Semaphore
wait(S)
critical section
signal(S)
Monitor
High-level construct (used in Java, etc.)
Automatically handles synchronization
Key Issues
Busy Waiting (wastes CPU time)
Deadlock (processes wait forever)
Starvation (some processes never get access)
Summary
Critical section problem ensures safe access to shared
resources
Prevents race conditions
Requires:
Mutual Exclusion
Progress
Bounded Waiting
Solved using algorithms, hardware instructions, and
synchronization tools
Critical Section Problem – Example 2
Let’s understand the Critical Section Problem
with a simple and clear example.
Example: Shared Bank Account 💰
Assume two processes are accessing the same bank
account balance.
Initial Balance = 1000
Process P1 (Deposit ₹500)
read balance (1000)
balance = balance + 500 → 1500
write balance (1500)
Process P2 (Withdraw ₹300)
read balance (1000)
balance = balance - 300 → 700
write balance (700)
What Goes Wrong? (Race Condition)
If both processes execute at the same time,
this may happen:
1.
P1 reads balance
= 1000
2.
P2 reads balance
= 1000
3.
P1 writes 1500
4.
P2 writes 700
Final Balance = 700 (WRONG ❌)
Correct answer should be 1200 (✔)
Where is the Critical Section?
The critical section is where the shared
variable (balance) is accessed:
read balance
modify balance
write balance
Both processes execute this part → conflict occurs.
Solution Using Mutual Exclusion
We ensure only one process at a time accesses
the balance.
Using Mutex Lock
lock()
read balance
modify balance
write balance
unlock()
Correct Execution (After Fix)
1.
P1 enters →
updates balance to 1500 → exits
2.
P2 enters →
updates balance to 1200 → exits
Final Balance = 1200 (Correct ✔)
Key Takeaways
- Critical section =
code accessing shared data
- Problem occurs due
to simultaneous access
- Leads to race
condition
- Solution: Mutual
Exclusion (locks, semaphores, etc.)
Another Quick Example (Counter)
count = 0
P1: count++
P2: count++
Expected result = 2
But due to race condition → result may be 1
Classical Synchronization Problems
Described by Dutch computer scientist Edsger W. Dijkstra in mid
1960.
(Producer-Consumer, Readers-Writers, Dining Philosophers)
Classical
Synchronization Problems are standard
problems used to understand how processes coordinate and share resources
safely without conflicts.
1.
Producer–Consumer Problem (Bounded Buffer Problem)
Concept
A producer creates data and puts it into a buffer
A consumer takes data from the buffer
Buffer has limited size
Problem
Producer should not add data if buffer is full
Consumer should not remove data if buffer is empty
Solution
Use
Semaphore: (we can use semaphores to keep track of the number of empty
and full slots in the buffer.)
Mutex
→ for mutual exclusion
Full
→ number of filled slots
Empty
→ number of empty slots
Mutual
Exclusion (Mutex) is a concept used
in operating systems to ensure that only one process or thread can access a
shared resource (critical section) at a time.
Mutual exclusion is a technique that prevents multiple
processes from entering the critical section simultaneously.
2. Dining Philosophers
Problem 1965
The Dining Philosopher
Problem is a classic synchronization problem introduced by Edsger Dijkstra in
1965. It illustrates the challenges of resource sharing in concurrent
programming, such as deadlock, starvation, and mutual exclusion.
Concept
6
Pphilosophers sit around a
circular table.
Each philosopher
alternates between thinking and eating.
There is one
chopstick between each philosopher (total K chopsticks).
A philosopher must
pick up two chopsticks (left and right) to eat.
Only one
philosopher can use a chopstick at a time.
The challenge: Design a synchronization mechanism so that philosophers
can eat without causing deadlock (all waiting
forever) or starvation (some never
get a chance to eat).
Issues in the Problem
If all pick one chopstick →
1.
Deadlock: If every philosopher picks up their left chopstick first,
no one can pick up the right one circular wait.
2.
Starvation: Some philosophers may never get a chance to eat if others
keep eating.
3.
Concurrency Control: Must ensure no two adjacent philosophers eat
simultaneously.
deadlock
occurs (A deadlock is a situation in which two or more processes are unable to
proceed because each is waiting for a resource held by another process.)
Solution
Resource hierarchy
Resource
Hierarchy is a technique used to prevent
deadlock by assigning an order (number) to resources and forcing processes
to request them in that order.
Idea
behind It
Each resource (chopstick) is given a unique
number
A philosopher must always pick the lower-numbered
chopstick first, then the higher-numbered one
this breaks circular wait, so deadlock cannot occur
Example (Dining
Philosophers)
Assume:
5
philosophers: P1, P2, P3, P4, P5
5
chopsticks numbered: C1, C2, C3, C4, C5
Arrangement:
P1
→ C1 & C2
P2
→ C2 & C3
P3
→ C3 & C4
P4
→ C4 & C5
P5
→ C5 & C1
Rule
Applied
Each
philosopher picks:
First lower-numbered chopstick, then higher-numbered
So:
P1
→ picks C1 then C2
P2
→ picks C2 then C3
P3
→ picks C3 then C4
P4
→ picks C4 then C5
P5
→ picks C1 then C5 (since C1 < C5)
Why
Deadlock is Avoided?
No
circular waiting chain is formed
At
least one philosopher can always eat
Circular wait condition is eliminated
Limit number of philosophers
Basic Idea
If
there are N philosophers, allow only N − 1 philosophers to sit (or pick
chopsticks) at a time
Example:
Total
philosophers = 5
Only
4 philosophers can try to eat at once
Why does it work?
At
least one philosopher will always be able to get both chopsticks
This
breaks circular wait condition so deadlock cannot occur
Example
- Philosophers: P1, P2, P3, P4, P5
- Only 4 allowed to pick chopsticks
Suppose:
- P1, P2, P3, P4 are trying to eat
- P5 is waiting
Since one philosopher is not competing:
One of the active philosophers will get both chopsticks and eat
Then resources are released → others proceed
Use semaphores or monitors
3. Readers–Writers
Problem
Concept
Multiple
processes:
Readers
→ only read data
Writers
→ modify data
Problem
Multiple
readers can access at same time
Ensure that only
one writer writes at a time.
Prevent readers
from reading while a writer is writing.
Writer
needs exclusive access
Solution
Readers Preference – give readers priority, making writers wait.
Writers Preference – give writers priority, ensuring timely updates.
Use read-write locks / semaphores (The reader-writer problem using semaphores manages concurrent access to a shared
resource, allowing multiple readers to read simultaneously but giving writers
exclusive access. (exclusive-not to be shared) It utilizes a mutex (for updating reader count, (
mutex - to prevent
multiple threads from accessing shared resources simultaneously)) and a wrt semaphore (for locking the resource) to prevent data
inconsistency, ensuring that while a writer is active, no reader or other
writer can enter)
Allow multiple readers
Block writers when readers active
Semaphores & Mutex
Both semaphores and mutex are used for process
synchronization and to control access to shared resources.
1.
Semaphore
What is a Semaphore?
A semaphore is a signaling mechanism used to control
access to multiple resources.
Types
Binary Semaphore (0 or 1)
Counting Semaphore (0, 1, 2, …)
Operations
wait (P) → decrease value
signal (V) → increase value
Example
wait(S);
// critical section
signal(S);
2. Mutex (Mutual Exclusion)
What
is a Mutex?
A mutex is a locking mechanism used to ensure that
only one process/thread accesses a resource at a time.
It is like a lock/unlock system
Example
lock(mutex);
// critical section
unlock(mutex);
Key
Differences
|
Feature
|
Semaphore
|
Mutex
|
|
Meaning
|
Signaling mechanism
|
Locking mechanism
|
|
Values
|
Integer (0,1,2,…)
|
Only 0 or 1
|
|
Usage
|
Multiple resources
|
Single resource
|
|
Ownership
|
No ownership
|
Has ownership
|
|
Operations
|
wait() / signal()
|
lock() / unlock()
|
Similarities
Used for synchronization
Prevent race conditions
Control access to critical section
Advantages
Efficient resource management
Ensures data consistency
Disadvantages
Can cause deadlock if misused
Difficult to implement correctly
Short
Answer (Exam Ready)
Semaphore is a signaling mechanism used to manage
multiple resources, while mutex is a locking mechanism used to allow only one
process to access a resource at a time.