Chapter 5: Process Synchronization - Operating Systems
A. Process Synchronization
B. Critical Section Problem
C. Synchronization Hardware
D. Synchronization Problems
A. Process Synchronization
Cooperating Process:
One that can affect or be affected by other processes executing in the system. They can share both code and data or only
data. Concurrent(at the same time) access to shared data may result in data inconsistency. Process Synchronization are
mechanisms to ensure the orderly execution of cooperating processes so that data consistency is maintained.
How Processes are executed?
Processes can execute concurrently or in parallel.
Concurrently: The CPU Scheduler switches rapidly between processes to provide concurrent execution. One process may
only partially complete execution before another process is scheduled.
Parallel: Two processes execute simultaneoulsy on separate processing cores.
What is Race Condition? How it is prevented?
A situation where several processes access and manipulate the same data concurrently and the outcome of the execution
depends on the particular order in which access takes place.
Prevention:To prevent race condition, only one process at a time can be manipulating the shared data.
Example: Shared Counter
Suppose two processes share a variable:
int count = 5;
Both processes execute:
count = count + 1;
The operation is actually performed in three steps:
1. Read count from memory.
2. Add 1.
3. Write the result back to memory.
Possible Execution
Initial value:
count = 5
Step Process P1 Process P2
1 Read 5
2 Read 5
3 Compute 6
4 Compute 6
5 Write 6
6 Write 6
Final value:
count = 6
Expected Result
Since both processes incremented the counter, the expected value is:
count = 7
Actual Result
count = 6
One update is lost because both processes read the same old value before either wrote back the new value.
This is a race condition: the result depends on which process "wins the race" to access the shared variable.
B. Critical Section Problem
Consider a system consisting of n processes. Each process has a segment of code, called a critical section in which process
accesses or changes the shared data. Since this data is shared among processes, access to the critical section must be
carefully controlled. The critical-section problem is the problem of designing a method that allows processes to cooperate
BS Computer Science - Government Girls Degree Sardar Hasan Musa College, Quetta 1
Chapter 5: Process Synchronization - Operating Systems
safely while accessing shared [Link] entering the critical section, a process executes an entry section to request
access. After completing its work in the critical section, it executes an exit section. The rest of the process code is called
the remainder section.
do {
entry section
critical section
exit section
remainder section
}while(true);
General structure of typical process
What are the three requirements that any solution to Critical Section Problem must satisfy?
Any solution to critical section problem must satisfy three requirements:
1. Mutual Exclusion: At most one process can be in its critical section at a time.
2. Progress: If no process is currently in the critical section and some processes want to enter it, one of them must be allowed to
enter without unnecessary delay.
3. Bounded Waiting: Once a process requests access to the critical section, it should not have to wait forever. There must be a
limit on how many times other processes can enter before its request is granted
Peterson’s Solution
It is software based solution of critical section. It is restricted to two processes that alternate execution between their
critical section and remainder section. The processes share two variables,flag and turn. The variable turn indicate whose
turn it is to enter critical section and flag indicate if process want to enter critical section.
Atomic Operation
These are low level instructions provided by the hardware or the programming language to ensure that a specific
operation (e.g. read, write, compare and swap) is performed as a single, indivisible operation. They cannot be interrupted
by other threads or processes.
Busy Waiting
Busy waiting occurs when a process continuously checks a condition in a loop while waiting for a resource to become
available. Instead of sleeping or blocking, the process keeps using CPU time repeatedly checking the condition.
Disadvantage: It wastes CPU time because the process keeps running even while doing no useful work.
Spinlock
A spinlock is a type of lock that uses busy waiting. When a process tries to acquire a spinlock: If the lock is free, it enters
the critical section. If the lock is busy, it repeatedly “spins” in a loop checking the lock until it becomes available.
Advantages of Spinlocks: Simple and fast for very short waiting times. Avoids the overhead of blocking and waking up
processes.
Disadvantages: Wastes CPU cycles during waiting. Inefficient if the waiting time is long.
Relationship Between Busy Waiting and Spinlock
Busy waiting = the behavior of repeatedly checking.
Spinlock = a lock implementation that uses busy waiting.
So, a spinlock works by busy waiting.
C. Synchronization Hardware
All hardware-based synchronization solutions are based on the idea of locking, i.e., protecting critical sections using locks.
1. Test and Set Instruction (TSL)
TSL is a hardware atomic instruction used for synchronization. It checks the value of a lock and sets it to true in one
indivisible (atomic) step. If the lock is already true, the process keeps waiting (busy waiting). It ensures that only one
process enters the critical section at a time.
Example:
Suppose lock = false.
BS Computer Science - Government Girls Degree Sardar Hasan Musa College, Quetta 2
Chapter 5: Process Synchronization - Operating Systems
A process executes TSL(lock).
The instruction checks the lock and immediately sets it to true atomically.
Then process enters its critical section.
Other processes find lock = true and keep waiting until it becomes false.
2. Compare and Swap (CAS)
CAS is an atomic instruction that compares a memory value with an expected value. If both are equal, it replaces the value
with a new one. If they are different, no change is made.
3. Mutex Locks (Mutual Exclusion)
A mutex lock is used to protect a critical section by first calling acquire() on the lock and then release() after leaving the
critical section.
acquire(lock);
// Critical Section
release(lock);
The variable lock is boolean. The acquire() and release() operations must be atomic, usually implemented using hardware
atomic instructions such as TSL or CAS.
4. Semaphore
It controls access by allowing or blocking processes depending on the semaphore value.
There are two main types of semaphores:
4.1 Binary Semaphore
A binary semaphore has only two possible values: 0 and 1. 1 means the resource is available. 0 means the resource is
unavailable. If a process tries to access the resource when the semaphore value is 0, it blocks until the semaphore
becomes 1. When a process releases the resource, it changes the semaphore value back to 1.
semaphore S = 1;
wait(S);
/* Critical Section */
signal(S);
4.2 Counting Semaphore
A counting semaphore can have a range of integer values. It is used to control access to multiple instances of a resource.
The semaphore value represents the number of available resources. A process decreases (wait/down operation) the
semaphore when acquiring a resource. A process increases (signal/up operation) the semaphore when releasing a
resource. When the semaphore value becomes 0, any further attempt to decrease it causes the process to block until
another process increases the semaphore.
Example:
Initially:
printers = 3
Process P1 requests a printer:
wait(printers)
printers = 2
Process P2:
printers = 1
Process P3:
printers = 0
Now all printers are busy.
Process P4:
wait(printers)
Since:
printers = 0
P4 blocks and waits.
When P2 finishes:
signal(printers)
printers = 1
BS Computer Science - Government Girls Degree Sardar Hasan Musa College, Quetta 3
Chapter 5: Process Synchronization - Operating Systems
One printer becomes available and P4 can proceed.
5. Monitor
High Level Synchronization tool used in programming languages.
D. Synchronization Problems
Classical synchronization problems are standard problems in Operating Systems used to explain process synchronization,
mutual exclusion, deadlock, and coordination between processes/threads. Three main classical synchronization problems
are:
1. Producer–Consumer Problem (Bounded Buffer Problem)
This problem deals with synchronization between processes
that produce data and processes that consume data.
Producer adds items to a shared buffer. Consumer removes
items from the buffer. The buffer has limited size.
Problems:
Producer must not add data when the buffer is full.
Consumer must not remove data when the buffer is
empty.
Mutual exclusion is needed while accessing the buffer.
Solution: Semaphores, Mutex locks
Example: A printer queue where users submit print jobs and
the printer processes them.
2. Readers–Writers Problem
This problem manages access to shared data. Readers only read
data. Writers modify data.
Rules:
Multiple readers can access simultaneously.
Only one writer can access at a time.
No reader can access while a writer is writing.
Goal: Maintain data consistency while maximizing concurrency.
Example: A database system where many users read records
while administrators update them.
3. Dining Philosophers Problem
A famous synchronization and deadlock problem. Five
philosophers sit around a table. Each philosopher needs two
chopsticks/forks to eat. Each philosopher alternates between
thinking and eating.
Problems:
Deadlock
Starvation
Resource allocation conflicts
Goal: Design a method so philosophers can eat without deadlock.
Example: Processes competing for limited resources.
BS Computer Science - Government Girls Degree Sardar Hasan Musa College, Quetta 4