SYNCHRONIZATION
1. Introduction
In a multiprogramming or multitasking environment, multiple processes or
threads execute concurrently. Often, these processes need to share resources
such as memory, files, or variables.
Synchronization is the mechanism used to control the access of multiple
processes to shared resources in a coordinated manner.
Why Synchronization is Important
Without synchronization, processes may interfere with each other, leading to
Incorrect results and Data inconsistency.
Race Condition:
A race condition occurs when:
The outcome of a process depends on the sequence or timing of execution of
other processes.
Example:
Consider a shared variable:
int x = 5;
Two processes execute:
P1: x = x + 1
P2: x = x + 1
Expected result: x = 7
Possible wrong result: x = 6
*This happens because both processes read the same value simultaneously.
Key Requirements of a Good Synchronization Solution
1. Mutual Exclusion – Only one process accesses shared resource at a time
2. Progress – Waiting processes should not be delayed unnecessarily
3. Bounded Waiting – No process should wait forever
2. CRITICAL SECTION
A critical section is a part of a program where shared resources (variables,
memory, files) are accessed.
Example
do {
// Entry Section
// Critical Section
// Exit Section
// Remainder Section
} while(true);
Explanation of Sections
1. Entry Section
Code where a process requests permission to enter the critical section.
2. Critical Section
The part where shared data is accessed.
3. Exit Section
Code that releases the resource.
4. Remainder Section
Rest of the program.
Critical Section Problem:
Design a system such that no two processes execute their critical sections at
the same time.
3. Hardware Solution to Synchronization:
Modern computer systems provide hardware-level support to implement
synchronization efficiently.
1. Test-and-Set (TAS)
We can stop interrupts to occur during modification of a shared variable so that
the instruction an be executed without pre-emption.
Many machines provide hardware instruction to test and modify a word and
swap the contents of words atomically without any interruption. The Test-And-
Set instruction is executed atomically
2. Semaphores:
A semaphore is just an integer variable that controls how many processes can
access a resource.
A semaphore works by allowing processes to wait (decrement) and signal
(increment) on a shared variable to manage access to critical sections. It
ensures that only a limited number of processes can access a resource at a
time, preventing race conditions. Semaphores are commonly used to achieve
process synchronization.
Example:
1. wait() (also called P operation)
wait(S){
S = S - 1;
if(S < 0){
// process goes to waiting queue
}
}
2. signal() (also called V operation)
signal(S){
S = S + 1;
if(S <= 0){
// wake up one waiting process
}
}
4. Problems of Synchronization:
(I) Producer-Consumer Problem (Bounded Buffer)
Suppose there are producer and consumer processes. Producer produces
objects, which consumer uses for something. There is one Buffer object used to
pass objects from producers to consumers. A Buffer is used to store production
of producer.
The problem is to allow producers and consumers to access the Buffer while
ensuring the following:
1. The shared buffer should not be accessed by these processes
simultaneously
2. Consumers do not try to remove objects from Buffer when it is empty
3. producers do not try to add objects to the buffer when it is full
(II) Readers–Writers Problem
The Readers-Writers problem is a classical synchronization problem where
multiple processes access shared data. There are two types of processes:
readers, who only read the data, and writers, who modify it. The main
challenge is to allow multiple readers to access the data simultaneously while
ensuring that writers get exclusive access (no reader or other writer is allowed
during writing). If a writer updates data while readers are reading, it can cause
inconsistency.
Solutions:
• Reader-Priority Solution: Readers are given preference, so writers may
wait for a long time (possible starvation of writers).
• Writer-Priority Solution: Writers are given priority, so readers must wait
if a writer is waiting (prevents writer starvation).
• Fair (No-Starvation) Solution: Both readers and writers are treated
equally, ensuring no process waits indefinitely.
(III) Dining Philosophers Problem
The Dining Philosophers problem is a classical synchronization problem that
illustrates issues like deadlock and starvation in concurrent systems. In this
problem, five philosophers sit around a table with five forks, and each
philosopher needs two forks (left and right) to eat. A philosopher alternates
between thinking and eating, but can only eat if both forks are available. If all
philosophers pick up one fork at the same time, none can pick the second fork,
leading to a deadlock where everyone waits indefinitely. The problem
highlights the need for proper resource allocation and synchronization
techniques.
Waiter (Arbitrator) Solution:
In this solution, a central authority called a waiter controls access to forks. A
philosopher must ask the waiter before picking up any forks, and the waiter
only allows permission if both forks are available. This prevents two
neighboring philosophers from picking up forks at the same time, thereby
avoiding deadlock and starvation. Semaphore-Based Solution
used to understand process coordination and resource sharing in operating
systems.