PROCESS SYNCHRONIZATION

12/5/2024
 Process Synchronization
• Background
• Race condition
• The Critical-Section Problem
• Peterson’s solution
• Mutex locks
• Semaphores
• Classical Problems of Synchronization

12/5/2024
 Background
• Cooperating processes can either directly share a logical
address space (that is, both code and data) or be
allowed to share data only through files or messages.
• Concurrent access to shared data may result in data
inconsistency.
• In this chapter, we will discuss various mechanisms to
ensure the orderly execution of cooperating processes
that share a logical address space, so that data
consistency is maintained.
Producer consumer problem
Shared-memory solution to bounded-buffer problem allows at most n – 1 items
in buffer at the same time. A solution, where all N buffers are used is not simple.
 Background
• Shared-memory solution to bounded-buffer
problem allows at most n – 1 items in buffer at
the same time. A solution, where all N buffers
are used is not simple.
– Suppose that we modify the producer-consumer
code by adding a variable counter, initialized to 0
and incremented each time a new item is added to
the buffer

12/5/2024
 Bounded-Buffer
#define BUFFER_SIZE 10
typedef struct {
...
} item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
int counter = 0;
12/5/2024
 Bounded-Buffer
• Producer process

item nextProduced;

while (1) {
while (counter == BUFFER_SIZE)
; /* do nothing */
buffer[in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
counter++;
}
12/5/2024
 Bounded-Buffer
• Consumer process

item nextConsumed;
while (1) {
while (counter == 0)
; /* do nothing */
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
counter--;
}

12/5/2024
 Bounded Buffer
• The statements

counter++;
counter--;

must be performed atomically.

• Atomic operation means an operation that

completes in its entirety without interruption.

12/5/2024
 Bounded Buffer
• The statement “count++” may be implemented in
machine language as:
register1 = counter
register1 = register1 + 1
counter = register1

• The statement “count—” may be implemented as:

register2 = counter
register2 = register2 – 1
counter = register2

12/5/2024
 Bounded Buffer
• If both the producer and consumer attempt to
update the buffer concurrently, the assembly
language statements may get interleaved.

• Interleaving depends upon how the producer

and consumer processes are scheduled.

12/5/2024
 Bounded Buffer
• Assume counter is initially 5. One interleaving of
statements is:
producer: register1 = counter (register1 = 5)
producer: register1 = register1 + 1 (register1 = 6)
consumer: register2 = counter (register2 = 5)
consumer: register2 = register2 – 1 (register2 = 4)
producer: counter = register1 (counter = 6)
consumer: counter = register2 (counter = 4)

• The value of count may be either 4 or 6, where the

correct result should be 5.

12/5/2024
 Race condition
• A race condition occurs in a multi-threaded or multi-process
system when the outcome of a computation depends on the
non-deterministic ordering or timing of thread or process
execution.
• This can result in unintended or unpredictable behavior,
especially when two or more threads access shared resources
concurrently and at least one of them modifies the shared
data.
• To prevent race conditions, concurrent
processes must be synchronized.
 Race Condition
• Race condition: The situation where several
processes access – and manipulate shared data
concurrently. The final value of the shared data
depends upon which process finishes last.

12/5/2024
 The Critical-Section Problem
• 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.

12/5/2024
 Initial Attempts to Solve Problem
• Each process must request permission to enter its critical
section.
• Section of the code implementing this request is the entry
section.
• Critical section may be followed by the exit section.
• The remaining code is the remainder section
 Solution to Critical-Section Problem
A solution to the critical-section problem must satisfy the following
three requirements:
[Link] Exclusion: If process Pi is executing in its critical section, then
no other processes can be executing in their critical sections.
2. Progress. If no process is executing in its critical section and there
exist some processes that wish to enter their critical section, then
the selection of the processes that will enter the critical section
next cannot be postponed indefinitely.
3. Bounded waiting: There exists a bound, or limit, on the number of
times that other processes are allowed to enter their critical
sections after a process has made a request to enter its critical
section and before that request is granted

12/5/2024
 Peterson’s Solution
• Peterson’s solution is a classic software-based
algorithm for achieving mutual exclusion in
concurrent programming.
• It is specifically designed for two processes and is
widely studied as a foundation for understanding
synchronization concepts.
 Peterson’s Solution
• Peterson’s solution is restricted to two
processes that alternate execution between
their critical sections and remainder sections.
• The processes are numbered P0 and P1.
• For convenience, when presenting Pi , we use
Pj to denote the other process; that is, j equals
1 − i.
 Peterson's solution
Peterson's solution uses two shared variables:
1. Boolean flag[]:
 An array of boolean values indicating whether a process is
ready to enter its critical section.
 flag[0] = true means Process 0 wants to enter.
 flag[1] = true means Process 1 wants to enter.

2. Int turn:
 An integer variable indicating whose turn it is to
enter the critical section.
 turn = 0 allows Process 0 to enter.
 turn = 1 allows Process 1 to enter.
Algorithm:
For two processes, Process 0 and Process 1:
do {
flag[i] = true;
turn = j;
while (flag[j] && turn == j);
critical section
Flag[i] = false;
remainder section
} while (true);
The structure of process Pi in Peterson’s solution.

Where:
•i is the current process (0 or 1).
•j is the other process (1 - i).
 Explanation of Peterson’s Solution
Setting Intentions
• When a process wants to enter its critical section, it sets its
flag[i] to true and sets turn to the other process (j). This
signals its intention but gives the other process priority.
• Mutual Exclusion: A process enters its critical section only if:
The other process does not want to enter (flag[j] == false), or
It is its turn (turn != j).
• Exiting the Critical Section: After completing its critical
section, the process sets flag[i] = false to indicate it no longer
needs the critical section.
• Waiting: A process waits (spins) in the while loop if the other
process wants to enter and it is not its turn.
Advantages:
• Simple and easy to implement for two processes.
• Satisfies the critical-section requirements:
--Mutual Exclusion: Only one process can be in the critical
section at a time.
– Progress: Processes alternate their turns.
– Bounded Waiting: No indefinite waiting since turn
alternates between the processes.
Limitations
Two Processes Only:
Peterson’s solution is specifically designed for two processes.
Extending it to multiple processes is complex and less
efficient.
 Mutex Locks
• A mutex (mutual exclusion) lock is a synchronization
mechanism used in operating systems to prevent
concurrent processes or threads from accessing a
critical section simultaneously.
• It ensures mutual exclusion, allowing only one thread
or process to execute the critical section at a time
and thus prevent race conditions.
• A process must acquire the lock before entering a
critical section; it releases the lock when it exits the
critical section.
 Mutex Locks
• The acquire()function acquires the lock, and the
release() function releases the lock.
Working:
• A mutex lock has a boolean variable available whose
value indicates if the lock is available or not.
• If the lock is available, a call to acquire() succeeds, and
the lock is then considered unavailable.
• A process that attempts to acquire an unavailable lock
is blocked until the lock is released.
 Key Concepts of Mutex Locks
1. Critical Section: A section of code where shared resources are
accessed, requiring synchronization to prevent data
inconsistency.
2. Mutex Lock:
1. A binary lock (locked or unlocked) used to protect the
critical section.
2. Only one thread or process can acquire the lock at a time.
3. Other threads/processes attempting to acquire the lock
must wait until it is released.
3. Operations:
1. Lock (acquire): If the mutex is available, a thread/process
acquires it and enters the critical section.
2. Unlock (release): Once the critical section is exited, the
thread/process releases the mutex, allowing others to
acquire it.
 The definition of acquire() is as
follows:
acquire()
{
while (!available)
; /* busy wait */
available = false;
}
 Solution to the critical-section problem using mutex locks.

do {
acquire lock
critical section
release lock
remainder section
} while(true)
The definition of release() is as follows:
release()
{
available = true;
}
• Working of a Mutex Lock
1. Initially: Mutex is unlocked.
2. Thread A: Acquires the mutex and locks it. Enters the critical
section.
3. Thread B: Attempts to acquire the lock but must wait until
Thread A releases it.
4. Thread A: Completes its execution in the critical section and
unlocks the mutex.
5. Thread B: Acquires the lock and enters the critical section.
 Advantages of Mutex Locks

[Link] Exclusion: Ensures only one

thread/process accesses the critical section at
a time.
[Link] to Use: Well-supported by most
programming languages and operating
systems.
[Link] Safety: Helps avoid race conditions.
 Disadvantages of Mutex Locks

[Link]:
[Link] occur if multiple threads hold locks and wait
indefinitely for others.
[Link]:
[Link] acquisition and release involve some
computational cost.
[Link] Inversion:
1.A high-priority thread might be waiting for a low-
priority thread holding the lock, causing delays.
 Semaphore
• A semaphore in Operating Systems is a synchronization tool
used to manage access to shared resources in concurrent
programming.
• It helps prevent race conditions and ensures safe access to
critical sections by multiple processes or threads.
Types of Semaphores:
Binary Semaphore: Can have only two values (0 or 1). It is similar
to a mutex (mutual exclusion lock) and is used for exclusive
resource access.
Counting Semaphore: Can have any non-negative integer value.
It is used to manage access to a resource with multiple units,
such as a pool of threads or database connections.
 Working of a Semaphore
A semaphore is associated with:
A counter (integer value): Represents the
number of available resources.
A queue: Holds processes waiting for the
semaphore to become available.
Key Operations:
• Wait (P)
• Signal (V)
Wait (P):
• Decreases the semaphore value.
• If the value is negative, the process is blocked and added to the semaphore's
waiting queue.
Pseudo Code:
wait(S):
S=S-1
if S < 0:
block the process
Signal (V):
• Increases the semaphore value.
• If the value becomes 0 or positive, it unblocks one waiting process.
Pseudo code:
signal(S):
S=S+1
if S <= 0:
unblock a process
 Generic representation of semaphore
struct semaphore
{
int value; // Counter for resources
Struct process *L; // Queue for blocked processes
};
Purpose of value:
• Represents the current state of the semaphore.
• Tracks the availability of resources.
Behavior:
•Positive Values: The semaphore is available, and its value indicates how many resources are free.
•Zero: All resources are in use, but no processes are waiting yet.
•Negative Values: The semaphore is unavailable, and its magnitude (absolute value) represents the
number of processes blocked in the queue waiting for resources.
Struct process *L:
•Purpose:
Maintains a list (queue) of processes that are waiting for the semaphore to become available.
•Behavior:
•When the semaphore’s value is less than or equal to zero, processes requesting
•access are blocked and added to this queue.
•When the signal operation is performed, one process is removed from the queue
(in FIFO order) and unblocked.
 Implementation of semaphore

struct semaphore { void signal(struct semaphore *S) {

int value; // Semaphore S->value++; // Increment the
counter counter
struct process *wait_queue; // Pointer to if (S->value <= 0) {
the waiting process queue struct process *next =
}; remove_from_queue(S->wait_queue);
unblock(next); // Unblock a
void wait(struct semaphore *S) { waiting process
S->value--; // Decrement the counter }
if (S->value < 0) { }
add_to_queue(S->wait_queue,
current_process); // Block current process
block(current_process);
}
}
 Advantages of Semaphores
1. Efficient Resource Management:
• semaphores are useful for managing access to a limited number of resources
(e.g., printers, memory buffers).
• Counting semaphores can handle multiple instances of resources, unlike simple locks.
2. Process Synchronization:
Semaphores help synchronize processes or threads by ensuring that only the allowed number of
them can access a critical section or resource at a time.

[Link] of Race Conditions:

Semaphores prevent race conditions by controlling access to shared resources, ensuring
consistency and correctness.

[Link] Busy Waiting (in blocking semaphores):

Processes waiting on a semaphore are placed in a queue and put to sleep, avoiding CPU time
wastage due to spinning.
 Disadvantage of semaphore
Deadlocks:
Deadlocks occur when multiple processes hold semaphores and wait
for resources held by each other, creating a circular dependency.

Starvation:
If processes in the queue are not treated fairly (e.g., in priority-based
systems), some may wait indefinitely for the semaphore to be released.

Priority Inversion:
High-priority processes may be blocked by lower-priority processes
holding the semaphore, leading to inefficient scheduling unless additional
mechanisms (like priority inheritance) are implemented.
 Deadlock and Starvation
Deadlock – two or more processes are waiting indefinitely for an event
that can be caused by only one of the waiting processes.
• Let S and Q be two semaphores initialized to 1
P0 P1
wait(S); wait(Q);
wait(Q); wait(S);
 
signal(S); signal(Q);
signal(Q) signal(S);
• Starvation – indefinite blocking. A process may never be removed
from the semaphore queue in which it is suspended

12/5/2024
 Priority Inversion
• Priority Inversion is a phenomenon in concurrent systems where a higher-
priority task is waiting for a lower-priority task to release a resource, but
the lower-priority task cannot make progress because it is preempted by a
medium-priority task.
• This leads to a situation where the higher-priority task is effectively
"inverted" in the priority queue.
Example:
Steps in Priority Inversion
1. Initial Condition:
1. A high-priority task (HP) requires a resource (e.g., a lock or semaphore)
currently held by a low-priority task (LP).
2. Inversion Occurs:
1. Before LP can complete and release the resource, a medium-priority task (MP)
preempts LP because MP has a higher priority than LP.
3. Result:
1. The high-priority task (HP) is forced to wait indefinitely until MP finishes, even
though HP has a higher priority than MP.
 Classical Problems of Synchronization
• Bounded-Buffer Problem

• Readers and Writers Problem

• Dining-Philosophers Problem

12/5/2024
 The Producer-Consumer Problem
Description:
• A producer generates items and places them in a shared
buffer, while a consumer removes items from the buffer for
processing.
• The buffer has limited capacity, so synchronization is required
to prevent the producer from overfilling the buffer or the
consumer from consuming from an empty buffer.
Key Issues:
• The producer must wait if the buffer is full.
• The consumer must wait if the buffer is empty.
 The Producer-Consumer Problem
Solution:
Use semaphores:
• A counting semaphore to track the number of
filled buffer slots (full).
• A counting semaphore to track the number of
empty slots (empty).
• A binary semaphore (mutex) to ensure mutual
exclusion during buffer access.
 Bounded-Buffer Problem
• Shared data

semaphore full, empty, mutex;

Initially:

full = 0, empty = n, mutex = 1

12/5/2024
 Bounded-Buffer Problem Producer
Process
do {
…
produce an item in nextp
…
wait(empty);
wait(mutex);
…
add nextp to buffer
…
signal(mutex);
signal(full);
} while (1);
12/5/2024
 Bounded-Buffer Problem Consumer
Process
do {
wait(full)
wait(mutex);
…
remove an item from buffer to nextc
…
signal(mutex);
signal(empty);
…
consume the item in nextc
…
} while (1);

12/5/2024
 The Readers-Writers Problem
Description:
• A shared database allows multiple readers to read
simultaneously but requires exclusive access for writers to
prevent data inconsistency.
Key Issues:
• If a writer is writing, no other readers or writers should access
the resource.
• If readers are reading, no writer should modify the resource.
 The Readers-Writers Problem
A shared database can be accessed by:
[Link]: Multiple readers can read the data
simultaneously.
[Link]: Only one writer can modify the data,
and while writing, no reader or other writer is
allowed access.
 The Readers-Writers Problem
variations:
First Readers-Writers Problem:
• Ensures no reader is kept waiting unless a writer has already
gained access.
• This may cause starvation for writers.

Second Readers-Writers Problem:

• Gives priority to writers, preventing readers from gaining
access once a writer is waiting.
• This may cause starvation for readers.
Solution for reader-writer problem
Solution Using Semaphores:
synchronization primitives:
mutex: A binary semaphore for mutual
exclusion when modifying the reader count.
rw_mutex: A binary semaphore that ensures
mutual exclusion for the shared resource (used
by writers or readers collectively).
reader_count: An integer variable to track the
number of active readers
 How It Works
Readers:
• Use the mutex semaphore to increment or decrement the reader_count.
• The first reader locks the shared resource (rw_mutex) to prevent writers
from accessing it.
• The last reader unlocks the shared resource (rw_mutex) once done.
Writers:
Writers directly acquire the rw_mutex semaphore, ensuring
exclusive access to the shared resource.
Concurrency:
Multiple readers can access the shared resource simultaneously.
Only one writer can access the resource at a time.
// Initialize semaphores and variables // Reading the shared resource
semaphore mutex = 1; // For modifying printf("Reader is reading the data.\n");
reader_count sleep(1); // Simulate reading time
semaphore rw_mutex = 1; // For wait(mutex); // Lock to modify
accessing the shared resource reader_count
int reader_count = 0; // Number of reader_count--; // Decrement
active readers number of readers
if (reader_count == 0) // If this is the
last reader
// Reader process signal(rw_mutex); // Unlock the
void reader() { shared resource
wait(mutex); // Lock to modify signal(mutex); // Release lock on
reader_count reader_count
reader_count++; // Increment number }
of readers
if (reader_count == 1) // If this is the first
reader
wait(rw_mutex); // Lock the shared
resource
signal(mutex); // Release lock on
reader_count
// Writer process
void writer() {
wait(rw_mutex); // Lock the shared resource

// Writing to the shared resource

printf("Writer is writing the data.\n");
sleep(2); // Simulate writing time

signal(rw_mutex); // Unlock the shared resource

}
 The Dining Philosophers Problem
• Consider five philosophers who spend their lives thinking and eating.
• The philosophers share a circular table surrounded by five chairs, each belonging to one
philosopher.
• In the center of the table is a bowl of rice, and the table is laid with five single chopsticks.
• When a philosopher thinks, she does not interact with her colleagues.
• From time to time, a philosopher gets hungry and tries to pick up the two chopsticks that
are closest to her (the chopsticks that are between her and her left and right neighbors).
• A philosopher may pick up only one chopstick at a time. Obviously, she cannot pick up a
chopstick that is already in the hand of a neighbor.
• When a hungry philosopher has both her chopsticks at the same time, she eats without
releasing the chopsticks.
• When she is finished eating, she puts down both chopsticks and starts thinking again.
 The Dining Philosophers Problem
• The dining-philosophers problem is considered a classic synchronization
Problem because it is an example of a large class of concurrency-control
problems.
• It is a simple representation of the need to allocate several resources
among several processes in a deadlock-free and starvation-free manner.
 Dining-Philosophers Problem
• One simple solution is to represent each chopstick with a semaphore.
• A philosopher tries to grab a chopstick by executing a wait() operation on
that semaphore.
• She releases her chopsticks by executing the signal() operation on the
appropriate semaphores.

Shared data
semaphore chopstick[5];
Initially all values are 1
12/5/2024
 Dining-Philosophers Problem
• Philosopher i:
do {
wait(chopstick[i])
wait(chopstick[(i+1) % 5])
…
eat
…
signal(chopstick[i]);
signal(chopstick[(i+1) % 5]);
…
think
…
} while (1);

12/5/2024