UNIT 3:

PROCESS
SYNCHRONIZATION
PART-1

Prepared by:
Aysha Kazi
 INTRODUCTION

Cooperating Processes
A cooperating process is one that can affect or be affected by other processes executing
in the system. Cooperating processes can either:
1. Directly share a logical address space (i.e., both code and data), or
2. Share data only through shared memory or message passing.
Concurrent access to shared data may cause inconsiste ncy, so mechanisms are needed
to ensure orderly execution of cooperating processes and maintain data consistency.

Types of Process Execution

Processes may execute concurrently or in parallel:
• Concurrent execution: CPU switches rapidly between processes; a process may
be interrupted anytime.
• Parallel execution: Multiple processes execute simultaneously on separate cores.
Both may cause issues with shared data integrity.

Producer–Consumer Problem
The Producer–Consumer Problem is a classical synchronization problem in operating
systems. It highlights the challenges of coordinating multiple processes that share
limited resources.

Key Concepts
• Producer: Process that generates data/items and places them into a shared
buffer.
• Consumer: Process that removes data/ items from the shared buffer for use.
• Shared Buffer: A fixed-size memory area that both processes use to exchange
data.

Working of the Problem

• The Producer adds data/items to the buffer.
• The Consumer removes data/items from the buffer.
• The buffer is bounded (limited in size), so careful synchronization is required.

Constraints
1. The Producer must not add data if the buffer is full.
2. The Consumer must not remove data if the buffer is empty.
3. Mutual exclusion is required so that both processes don’t access the buffer
simultaneously.
Initial Solution Using Counter
To manage the buffer, a variable count is introduced:

• Initialized to 0.
• Incremented when an item is added to the buffer.
• Decremented when an item is removed from the buffer.

Producer Process Consumer Process

while (true) { while (true) {
/*produce an item in next_produced */ while (count == 0)
while (count == BUFFER_SIZE) ; /* do nothing */
; /* do nothing */ next_consumed = buffer[out];
buffer[in] = next_produced; out = (out + 1) % BUFFER_SIZE;
in = (in + 1) % BUFFER_SIZE; count--;
count++; /*consume the item in next_consumed */
} }

Problem of Concurrent Execution

Although the producer and consumer routines are correct when executed individually,
they may produce incorrect results when executed concurrently.

• Suppose count = 5.
• If the producer and consumer simultaneously execute the statements count++
and count--, the final value of count could be 4, 5, or 6.
• The only correct value should be 5, which is obtained if both processes run
separately.
• Shared variable manipulation without synchronization causes incorrect results.

Race Condition
A race condition occurs when multiple processes access and manipu late shared data
concurrently, and the result depends on the order of execution.
In the Producer–Consumer problem, both processes modify count at the same time,
causing incorrect results.

Solution: Ensure only one process at a time manipulates shared variables. This
requires process synchronization.

Synchronization
Synchronization is the coordination of processes to ensure that they operate correctly
when sharing resources or data, so that the outco me is predictable and consistent.
• When multiple processes or threads access shared resources concurrently, the
execution order can affect results.
• Without proper synchronization, race conditions and data inconsistency can
occur.
• Synchronization ensures tha t processes execute in a controlled manner,
particularly when entering critical sections (parts of code that access shared
resources).
Example:
Consider two processes updating a shared bank account balance:
• Process A deposits $100.
• Process B withdraws $50.
Without synchronization, both processes might read the old balance simultaneously
and write incorrect results, leading to inconsistency. Using synchronization
mechanisms like mutex locks, only one process can update the balance at a time,
ensuring the correct final balance.

Importance of Synchronization
• Prevents race conditions when multiple processes access shared resources.
• Ensures data consistency and correctness of operations.
• Provides mutual exclusion, allowing only one process in a critical section at
a time.
• Coordinates process execution in scenarios like Producer –Consumer and
Readers–Writers problems.
• Supports multithreaded applications in multicore systems, preventing
interference between threads.
• Enhances overall reliability and stability of the operating system.
 THE CRITICAL-SECTION PROBLEM
The critical -section problem arises in process synchronization when multiple processes
access shared resources.
• Consider a system with n processes: {P0, P1, …, Pn−1}.
• Each process has a critical section, where it may access and update shared
data.
• Key rule: Only one process can execute in its critical section at a time.
A protocol is needed to synchronize process activity so that shared data is safely
accessed.

Structure of a Process
A typical process consists of four sections:
• Entry Section - Code to request permission to enter the critical section.
• Critical Section - Code that accesses or modifies shared resources.
• Exit Section - Code to leave the critical section and allow others to enter.
• Remainder Section - All other code outside the critical section.

General Structure (Pseudo -code):

Requirements of a Solution
A correct solution to the critical -section problem must satisfy:
1. Mutual Exclusion: If a process is executing in its critical section, no other process
can enter its critical section.
2. Progress: If no process is in the critical section and some processes wish to enter,
the selection of the next process cannot be postponed indefinitely. Only
processes not in the remainder section can participate in deciding who enters
next.
3. Bounded Waiting: There must be a limit on the number of times other proces ses
can enter their critical sections after a process has requested entry and before it
is granted.

Assumptions

• Each process executes at a nonzero speed.

• No assumption is made about the relative speed of the processes.

Example of Race Condition- Process Creation

Using fork() to create child processes can lead to race conditions on variables like
next_available_pid if mutual exclusion is not enforced.
Both processes may receive the same process identifier if executed concurrently
without mutual exclusion.

Simple Solution to the Critical-Section Problem (Lock-Based)

acquireLock();
critical section
releaseLock();

• Only one process/thread can hold the lock at a time, ensuring safe access to
shared resources.
• Locks can be implemented using mutexes, semaphores, or monitors.

Single-Core vs Multi-Core Considerations:

• On single-core systems, disabling interrupts during critical section is feasible.
• On multi-core systems, disabling interrupts is inefficient; careful design using
synchronization primitives is required.
• Kernel Types:
o Preemptive Kernel: Allows a process to be preempted in kernel mode;
needs careful design to avoid race conditions. This is suitable for real -
time systems, as it is more responsive and allows high -priority processes
to preempt lower-priority ones.
o Nonpreemptive Kernel: Kernel process runs until exit, block, or voluntary
yield, i.e., only one kernel -mode process is active at a time, reducing race
conditions.

Real-World Examples of Critical Sections

1. Banking System (ATM/Online Banking): Critical Section: Updating account
balance during deposit/withdrawal.
Issue if not handled: Simultaneous withdrawals may produce incorrect balance.
2. Ticket Booking System: Critical Section: Reserving the last available seat. Issue
if not handled: Multiple users may book the same seat, causing overbooking.
3. Print Spooler (Networked Printer): Critical Section: Sending print jobs to the
printer queue. Issue if not handled: Jobs may get mixed up or skipped.
4. File Editing in Shared Documents (Google Docs/MS Word): Critical Section:
Saving or writing to a shared document.
Issue if not handled: Simultaneous edits can lead to data loss or conflicting
versions.
5.
 PETERSON’S SOLUTION
Peterson’s solution is a classic software -based approach to solving the critical -section
problem for two processes. It illustrates the concepts of mutual exclusion, progress,
and bounded waiting.

Process Scope
• Designed for two processes, P 0 and P 1 , that alternate between their critical
sections and remainder sections.
• When presenting process P i , P j denotes the other process (j = 1 − i).

Shared Data Items Required:

• int turn;
Indicates whose turn it is to enter the critical section.
• boolean flag[2];
Indicates whether a process is ready to enter its critical section (true if ready).

Structure of Process Pi

• flag[i] = true: Process P i indicates readiness to enter the critical section.

• turn = j: P i gives priority to the other process if it also wants to enter the critical
section.
• while (flag[j] && turn == j): Busy-wait until it is safe to enter.
• Critical Section: The code where shared resources are accessed.
• flag[i] = false: P i exits, allowing P j to enter.

Correctness of Peterson’s Solution

1. Mutual Exclusion

• Pi can enter the critical section only if either:

1. flag[j] == false (P j is not interested), or
2. turn == i (it is P i ’s turn).
• Both processes cannot execute the while loop successfully at the same time,
ensuring mutual exclusion.
2. Progress

• P i is prevented from entering only if it is stuck in while(flag[j] && turn == j).

• If P j is not ready (flag[j] == false), P i enters immediately.
• If P j is ready, the turn variable determines who enters first.
• Once P j exits, P i can enter without indefinite delay, ensuring progress.

3. Bounded Waiting

• A process will enter its critical section after at most one entry by the other
process.
• Prevents starvation, fulfilling the bounded-waiting requirement .

Limitations of Peterson’s Solution

• Modern processors and compilers may reorder instructions for performance.
• Instruction reordering can break mutual exclusion in multithreaded programs.

Example:
// Shared variables
boolean flag = false;
int x = 0;

// Thread 1
while (!flag);
print x;

// Thread 2
x = 100;
flag = true;

• Expected: Thread 1 prints 100.

• Possible with reordering: Thread 2 may set flag = true before x = 100, causing
Thread 1 to print 0.
• Similarly, Thread 1 may read x before reading flag, leading to incorrect output.

Effect on Peterson’s Solution:

• If flag[i] = true and turn = j are reordered, both processes may enter their
critical sections simultaneously.
• Proper synchronization tools are required to guarantee correctness on modern
architectures.
 HARDWARE SUPPORT FOR
SYNCHRONIZATION
Software-based solutions like Peterson’s solution rely only on programming logic to
control access to shared resources, without requiring special hardware or OS features.

Hardware support provides CPU instructions that perform operations atomically,

preventing conflicts when mult iple processes access shared resources. Thes e
instructions make synchronization more reliable, especially on modern systems where
processors may reorder instructions for efficiency.

Hardware instructions can be used directly for synchronization or as the f oundation for
higher-level tools like semaphores, mutexes, and atomic variables.

1. Memory Barriers
The memory model of a processor determines how memory modifications are made
visible to other processors:
• Strongly Ordered Memory: Modifications made by one processor are immediately
visible to all other processors.
• Weakly Ordered Memory : Modifications made by one processor may not be
immediately visible to other processors.
Because memory models differ by processor type, kernel developers cannot assume that
memory changes on one processor are instantly visible on others. To address this,
processors provide memory barrier instructions (also called memory fences).

Function of Memory Barriers:

• Ensure that all load and store operations before the barrier are completed before
any load or store after the barrier is executed.
• Prevent instruction reordering that could lead to inconsistent or incorrect data
states.
• Guarantee visibility of memory modifications to all other processors in a
multiprocessor system.

Example of Memory Barriers:

Consider two threads sharing variables x and flag :

Thread 1:
while (!flag)
memory_barrier();
print x;

Thread 2:
x = 100;
memory_barrier();
flag = true;

• The memory barrier in Thread 1 ensures that the value of flag is read before
reading x .
 • The memory barrier in Thread 2 ensures that the assignment to x occurs before
setting flag to true.

In Peterson’s solution, placing a memory barrier between the first two assignment
statements in the entry section prevents instruction reordering that could compromise
mutual exclusion.

2. Hardware Instructions
Modern computer systems provide special hardware instructions that allow atomic
operations on shared memory. These instructions can test and modify a memory
location or swap the contents of two me mory locations as one uninterruptible unit,
which can be used to solve the critical -section problem efficiently.
Two widely used instructions are test -and-set() and compare-and-swap() (CAS).

Test-and-Set Instruction
The test_and_set instruction is an atomic hardware operation that reads the value of
a boolean variable, sets it to true, and returns its original value.

boolean test_and_set(boolean *target) {

boolean rv = *target;
*target = true;

return rv;
}

Key Points:
• Executes atomically, meaning no interruption occurs during its execution.
• If two processes execute test -and-set simultaneously, the operations are
executed sequentially in some arbitrary order.
• Used to implement mutual exclusion.

Implementation for Critical Section:

do {
while (test_and_set(&lock))
; /* do nothing */

/* critical section */

lock = false;

/* remainder section */
} while (true);

• lock is a shared boolean variable initialized to false.

• Only one process can set lock to true at a time and enter the critical section.

Compare-and-Swap (CAS) Instruction

The compare_and_swap (CAS) instruction is an atomic operation that compares the
value of a variable to an expected value and, if they are equal, updates the varia ble to
a new value. It always returns the original value of the variable.
int compare_and_swap(int *value, int expected, int new_value) {
int temp = *value;

if (*value == expected)
*value = new_value;

return temp;
}

Key Points:

• Operates atomically on three operands: value, expected, and new_value.

• value is set to new_value only if *value == expected.
• Always returns the original value of value.
• If two CAS operations occur simultaneously, they are exe cuted sequentially in
some arbitrary order.

Implementation for Critical Section:

while (true) {
while (compare_and_swap(&lock, 0, 1) != 0)
; /* do nothing */

/* critical section */

lock = 0;

/* remainder section */
}

• lock is an integer variable initialized to 0.

• The first process to succeed in CAS sets lock to 1 and enters the critical section.
• On exiting, the process resets lock to 0, allowing another process to enter.

Bounded-Waiting with Compare -and-Swap

The standard CAS-based algorithm satisfies mutual exclusion but may not satisfy
bounded waiting. To enforce bounded waiting, a waiting array can be used:

while (true) {
waiting[i] = true;
key = 1;
while (waiting[i] && key == 1)
key = compare_and_swap(&lock, 0, 1);
waiting[i] = false;

/* critical section */

j = (i + 1) % n;
while ((j != i) && !waiting[j])
j = (j + 1) % n;
 if (j == i)
lock = 0;
else
waiting[j] = false;

/* remainder section */
}

Key Points:
• waiting[n] is a boolean array initialized to false.
• lock is initialized to 0.
• Mutual exclusion is ensured because only one process can acquire lock via CAS at
a time.
• Progress is guaranteed as processes leaving the critical section release the lock
or set waiting[j] = false.
• Bounded waiting is guaranteed because processes are selected in cyclic order,
ensuring any process will enter its c ritical section within n − 1 turns.

3. Atomic Variables
Atomic variables are a higher -level synchronization tool built using compare -and-swap
(CAS) or similar hardware instructions. They allow atomic operations on basic data
types, such as integers and boo leans, ensuring that operations like incrementing or
decrementing a value are performed without interruption, thereby preventing data
races on single variables.

Purpose
• Atomic variables are used to provide mutual exclusion for operations on single
variables.
• They are especially useful when a race condition may occur on a variable being
updated, such as a counter.

Implementation
• Most systems provide special atomic data types and functions for manipulating
atomic variables.
• These functions are often implement ed using the compare -and-swap (CAS)
instruction.

Example: Incrementing an atomic integer sequence

increment(&sequence);

CAS-based implementation of increment:

void increment(atomic_int *v) {
int temp;

do {
temp = *v;
} while (temp != compare_and_swap(v, temp, temp + 1));
}
The increment() function updates the atomic integer atomically, ensuring no two
processes modify the value simultaneously.

Limitation
Atomic variables do not fully prevent race conditions.
Example: In the bounded -buffer problem, using an atomic count ensures atomic
updates, but if two consumers are waiting while count == 0 and a producer adds one
item, both may try to consume it simultaneously.

Conclusion: Atomic variables alone are insufficient for complex synchronization

involving multiple dependent operations.

Applications

• Counters: Atomic variables are used to safely increment or decrement counters

without race conditions.
• Sequence Generators: They ensure unique sequence numbers are generated
correctly in concurrent environments.
• Single-Variable Updates: Atomic variables allow safe updates to individual
shared variables without requiring full locks.
 MUTEX LOCKS
Mutex locks are higher -level software tools designed to solve the critical -section
problem. The term mutex stands for mutual exclusion. Mutex locks protect critical
sections to prevent race conditions by ensuring that only one process can enter a critical
section at a time.

• A process must acquire the lock before entering a critical section and release it
after exiting.
• The acquire() function acquires the lock, and release() releases it.

Structure of a Mutex Lock

• A mutex lock typically has a boolean variable available , which indicates whether
the lock is free.
• If the lock is available, acquire() succeeds and the lock becomes unavailable.
• If the lock is unavailable, the process attempting to acquire it is blocked until the
lock is released.

Pseudo-code

acquire():
acquire() {
while (!available)
; /* busy wait */
available = false;
}

release():
release() {
available = true;
}

Calls to acquire() or release() must be performed atomically.

Lock Contention
• Contended lock: Occurs when a thread blocks while trying to acquire the lock.
• Uncontended lock: Occurs when the lock is free when a thread attempts to
acquire it.

Contention can be high (many threads competing) or low (few threads competing).
High contention can reduce s ystem performance.

Spinlocks
Spinlocks are mutex locks where a process spins (busy waits) while waiting for a lock.
They are preferred on multiprocessor systems when the lock will be held for a short
duration (less than the time of two context switches).

• Advantage: No context switch is required, which can save time on multicore

systems.
• Disadvantage: Busy waiting wastes CPU cycles in single -core systems.
 SEMAPHORES
Semaphores are more advanced synchronization tools than mutex locks. They provide
flexible ways for processes to synchronize and manage access to shared resources in
concurrent systems.

What is a Semaphore?
A semaphore is an integer variable used to control access to a shared resource by
multiple processes in a concurrent system, through two atomic operations: wait() and
signal(). It was introduced by Dutch computer scientist Edsger Dijkstra .

Semaphore Operations
• wait(S): wait() was originally called P (from Dutch proberen, “to test”). It
decreases the semaphore value. If the value becomes negative, the process is
blocked until the resource becomes available.

wait(S) {
while (S <= 0)
; // busy wait
S--;
}
Note: Both the testing of the value (S <= 0) and the decrement (S --) must be
executed without interruption.

• signal(S): signal() was originally called V (from Dutch verhogen, “to

increment”). It increases the semaphore value. If there are waitin g processes,
one of them gets unblocked.

signal(S) {
S++;
}

Types of Semaphores
Operating systems distinguish between two types of semaphores:

1. Counting Semaphore

• Can take values over an unrestricted range (0 to N).

• Used to control access to resources with multiple instances.
• Allows multiple processes to access a finite set of identical resources
simultaneously.
• Example: Managing access to a pool of 5 printers or 10 database connections.
• Wait() operation decrements the semaphore value; if the value becomes
negative, the process blocks.
• Signal() operation increments the semaphore value; if there are waiting
processes, one is unblocked.
• Can be used to implement resource pools efficiently.
• Helps in avoiding race conditions for multiple identical resources.
 • Can be combined with other synchronization mechanisms (like mutexes) for
complex resource management.

2. Binary Semaphore

• Can take only values 0 or 1.

• Behaves like a mutex lock, ensuring mutual exclusion for a single resource or
critical section.
• Example: Controlling access to a shared printer or a critical section in code.
• Wait() / P operation: If value is 1, the process acquires the lock (sets value to
0); if 0, the process blocks.
• Signal() / V operation: Releases the lock (sets value to 1) and wakes up a
waiting process, if any.
• Can be used to prevent simultaneous execution of critical section s.
• Suitable for binary decisions, e.g., indicating availability or unavailability of a
single resource.
• Often used to implement simple locks in operating systems and concurrent
applications.
• Can be combined with counting semaphores for hierarchical or laye red
synchronization.

Example: Process Synchronization USING SEMAPHORES

Suppose two processes, P 1 and P 2 , execute statements S 1 and S 2 , and we want S 2 to
execute only after S 1 .

Shared semaphore: synch initialized to 0.

In Process P1:
S1;
signal(synch);

In Process P2:
wait(synch);
S2;

Explanation: Since synch starts at 0, P 2 will block at wait(synch) until P1 executes

signal(synch) after completing S 1 . This ensures S 2 runs only after S 1 .
Semaphores thus provide a flexible mechanism for cont rolling the order of execution
and managing access to shared resources.

Semaphore Implementation-
• The classical definitions of wait() and signal() involve busy waiting, where a
process continuously loops while waiting for a semaphore.
• To avoid wasting CPU cycles, a process can suspend itself when the semaphore
is not available:
o The process is placed in a waiting queue associated with the semaphore.
o Its state is changed to waiting, and the CPU scheduler selects another
process to execute.
• When another process executes signal(), the suspended process is restarted
using wakeup(), changing its state to ready and placing it in the ready queue.
•
Semaphore Structure
A semaphore can be defined as:

typedef struct {
int value;
struct process *list;
} semaphore;

• value: current value of the semaphore.

• list: linked list of processes waiting on the semaphore.

Implementing wait()
wait(semaphore *S) {
S->value--;
if (S->value < 0) {
add this process to S->list;
sleep();
}
}

If value becomes negative, the process is added to the waiting list and suspended.

Implementing signal()
signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
remove a process P from S->list;
wakeup(P);
}
}

If there are waiting processes (value <= 0), one process is removed from the list and resumed.

Important Points
1. Atomicity: wait() and signal() must be executed atomically to prevent multiple processes from
modifying the same semaphore simultaneously.
o In single-processor systems, this can be achieved by disabling interrupts during these
operations.
o In multicore systems, atomicity requires special techniques like compare and swap() or
spinlocks.
2. Negative Semaphore Values: In this implementation, semaphore values can be negative. The
magnitude of a negative value represents the number of processes waiting on that semaphore.
3. Waiting Queue: Implemented via a linked list in each process control block (PCB). It can use
FIFO or other queuing strategies; correctness does not depend on the specific strategy.
4. Reduced Busy Waiting: Busy waiting is minimized and occurs only briefly within the wait() and
signal() operations (typically no more than about ten instructions). This is far more efficient
than busy waiting in the entire critical section.
5. Limitation: For application programs with long critical sections, busy waiting can still be
inefficient.

•
CLASSIC PROBLEMS OF SYNCHRONIZATION
In operating systems, many processes often run at the same time and need to share
resources (like memory, printers, or data in a buffer). To avoid conflicts and make sure
everything works smoothly, we use synchronization.

What are “Classical Problems of Synchronization”?

• These are well-known, standard problems that represent common situations
where processes must cooperate.
• They are called classical because they have been studied for a long time and are
used as models or examples for testing new synchronization methods.
• They are not just theory real operating systems face the same kinds of issues.

How are they solved?

• Traditionally, semaphores are used to write solutio ns for these problems.
• In practice, operating systems may also use mutex locks instead of binary
semaphores.

There are three main classical synchronization problems:

1. Bounded Buffer Problem (Producer –Consumer Problem)
2. Readers–Writers Problem
3. Dining Philosop hers Problem

The Bounded-Buffer Problem

The bounded -buffer problem (also called the producer -consumer problem) is a classic
example of process synchronization.

Definition:
It describes a situation where two types of processes , producers and consumers , share
a fixed-size buffer (bounded buffer).

• The producer generates data items and places them into the buffer.
• The consumer removes data items from the buffer and uses them.
• The buffer has a limited capacity (n slots), meaning it can hold only a fixed number
of items at any time.

Problem Description
• In this problem, the producer and consumer processes share the following data
structures:
int n;
semaphore mutex = 1;
semaphore empty = n;
semaphore full = 0;

• The pool consists of n buffers, each capable of holding one item.

• The mutex binary semaphore provides mutual exclusion for accesses to the buffer
pool and is initialized to 1.
• The empty semaphore counts the number of empty buffers and is initialized to n.
• The full semaphore counts the number of full buffers and is initialized to 0.
Producer Process
The structure of the producer process is as follows:

while (true) {
...
/* produce an item in next_produced */
...
wait(empty);
wait(mutex);
...
/* add next_produced to the buffer */
...
signal(mutex);
signal(full);
}

Consumer Process
The structure of the consumer process is as follows:

while (true) {
wait(full);
wait(mutex);
...
/* remove an item from buffer to next_consumed */
...
signal(mutex);
signal(empty);
...
/* consume the item in next_consumed */
...
}

Observations
• There is a symmetry between the producer and the consumer.
• The code can be interpreted in two ways:
1. The producer produces full buffers for the consumer.
2. The consumer produces empty buffers for the producer.
 THE READERS-WRITERS PROBLEM
The Readers–Writers Problem is a classic synchronization problem in operating systems.
It arises when a shared resource (such as a database or file) must be accessed
concurrently by multiple processes, some of which only read the data (readers), while
others update it (writers). The problem is to design a synchronization scheme that
allows multiple readers to access the resource simultaneously but ensures that writers
have exclusive access to prevent data inconsistency.

• Readers: Processes that only read the shared data. Since they do not modify the
data, multiple readers can safely access the resource at the same time.
• Writers: Processes that update (read and write) the shared data. To avoid
inconsistencies, only one writer can access the data at a time, and no readers are
allowed during this period.

Key Conditions to Satisfy

1. Multiple readers may access the shared resource simultaneously if no writer is
writing.
2. Writers must have exclusive access . No other writer or reader may access the
resource while a writer is writing.

Significance
• Ensures proper synchronization between con current processes.
• Prevents data corruption due to simultaneous writer and reader/writer
operations.
• Has been widely used to test new synchronization techniques and primitives.

Variations of the Readers –WRITERS PROBLEM

• First Readers –Writers Problem
o Readers are not kept waiting unless a writer has already obtained
permission to use the shared object.
o In other words, readers are allowed to start reading even if a writer is
waiting.
• Second Readers–Writers Problem
o Once a writer is waiting, that writer should get access as soon as possible.
o In this case, no new readers may start reading if a writer is waiting.

Starvation Issue
• In the first problem, writers may starve (if readers keep arriving continuously).
• In the second problem, readers may starv e (if writers keep arriving continuously).
• To address this, other variants (starvation -free solutions) have been proposed.

Solution to the First Readers–Writers Problem

Data Structures

• semaphore rw_mutex = 1;
o Provides mutual exclusion for writers.
o Shared between both readers and writers.
 • semaphore mutex = 1;
o Ensures mutual exclusion when updating read_count.
• int read_count = 0;
o Keeps track of how many readers are currently accessing the database.

Writer Process
while (true) {
wait(rw_mutex);
/* writing is performed */
signal(rw_mutex);

• Only one writer can access the database at a time.

• Writers require exclusive access.

Reader Process
while (true) {
wait(mutex);
read_count++;
if (read_count == 1)
wait(rw_mutex); // first reader locks writers out
signal(mutex);

/* reading is performed */

wait(mutex);
read_count --;
if (read_count == 0)
signal(rw_mutex); // last reader allows writers
signal(mutex);
}

• First reader blocks writers by acquiring rw_mutex.

• Last reader signals rw_mutex so writers may proceed.
• Multiple readers may read simultaneously, but writers get exclusive access.

Behavior of the Solution

• If a writer is in its critical section and n readers are waiting:

o One reader is queued on rw_mutex.
o Remaining n – 1 readers are queued on mutex.
• When signal(rw_mutex) is executed by a writer, either waiting readers or another
writer may resume execution. The scheduler decides who proceeds.

Reader–Writer Locks
The readers –writers problem has been generalized into reader –writer locks provided
by some systems. A reader –writer lock can be acquired in two modes:
• Read Mode: multiple processes may acquire simultaneously (shared access).
• Write Mode: only one process may acquire (exclusive access).
 THE DINING-PHILOSOPHERS PROBLEM
The Dining -Philosophers Problem is a classic synchronization problem that illustrates
the challenges of allocating multiple shared resources among competing processes.

It involves five philosophers sitting around a circular table. Each philosopher alternates
between thinking and eating. A bowl of rice is placed at the center of the table, and
five chopsticks are positioned, one between each pair of philosophers.

To eat, a philosopher requires two chopsticks (the one on her left and the one on her
right). A philosopher may pick up only one chopstick at a time, and a chopstick cannot
be shared simultaneously between two philosophers. After eating, the philosopher
puts down both chopsticks and returns to thinking.

The problem is to design a synchronization scheme that allows the philosophers to eat
and think without causing:
• Deadlock: a situat ion where all philosophers are waiting indefinitely for
chopsticks.
• Starvation: a situation where one or more philosophers never get a chance to
eat.

Problem Description
Philosophers spend their lives thinking and eating. When a philosopher thinks, she does
not interact with others. From time to time, a philosopher becomes hungry and tries to
pick up the two chopsticks closest to her. She may pick up only one chopstick at a time
and cannot pick up a chopstick that a neighbor is holding. Once a philosophe r has both
chopsticks, she eats, then puts them down and resumes thinking.

This problem is considered classic not for its practical importance, but because it
represents a large class of concurrency -control problems and the need to allocate
multiple resou rces among several processes in a deadlock -free and starvation-free
manner.
Semaphore Solution
• Represent each chopstick as a semaphore.
• A philosopher uses wait() to pick up a chopstick and signal() to put it down.
Shared Data: semaphore chopstick[5]; // each initialized to 1
Structure of Philosopher i:
while (true) {
wait(chopstick[i]);
wait(chopstick[(i+1) % 5]);
/* eat for a while */
signal(chopstick[i]);
signal(chopstick[(i+1) % 5]);
/* think for a while */
}

Problem with this Solution:

• Guarantees that no two neighbors eat at the same time.

• However, may lead to deadlock.
• Example: if all philosophers pick up their left chopstick simultaneously, each
holds one chopstick and waits forever for the other.

Possible Remedies for Deadlock:

1. Allow at most four philosophers at the table simultaneously.
2. Allow a philosopher to pick up her chop sticks only if both are available (done
inside a critical section).
3. Use an asymmetric solution:
o Odd-numbered philosophers pick up left then right.
o Even-numbered philosophers pick up right then left.

Monitor Solution
• Prevent deadlock by allowing a philosoph er to pick up chopsticks only if both
are available.
• Implemented using a monitor to control distribution of chopsticks.

Data Structures:
enum {THINKING, HUNGRY, EATING} state[5]; // state of each philosopher
condition self[5]; // condition variables for waiting

• A philosopher sets state[i] = EATING only if both neighbors are not eating:
• state[(i+4) % 5] != EATING && state[(i+1) % 5] != EATING

Operations:
1. pickup(i): Invoked when philosopher i wants to eat.
o If neighbors are eating, philosopher i waits (self[i].wait).
o Otherwise, philosopher i proceeds to eat.
2. putdown(i): Invoked when philosopher i finishes eating.
o Sets state[i] = THINKING.
o Signals neighbors if they are hungry and can now eat.
Usage Sequence:

[Link](i);
/* eat */
[Link](i);

Properties of Monitor Solution:

• Ensures that no two neighbors eat simultaneously.

• Ensures freedom from deadlock.
• However, starvation is still possible (a philosopher may wait indefinitely).