Introduction to

Synchronization: Critical-Section Problem,

Hardware, Semaphores, Classical Problems, and
Monitors
The Critical-Section Problem:
1. Definition:
o The critical-section problem involves
ensuring that multiple processes or
threads can access shared resources or
critical sections of code in a way that
prevents conflicts and inconsistencies.
2. Solution Requirements:
o Mutual Exclusion: Only one process or
thread can be in the critical section at any
time.
o Progress: If no process is in the critical
section and multiple processes are waiting
to enter, then the selection of the next
process to enter should be based on some
 criterion (e.g., a process waiting the
longest).
o Bounded Waiting: There should be a limit
on the number of times other processes
are allowed to enter their critical sections
after a process has requested entry to its
critical section and before it is granted
access.
Synchronization Hardware:
1. Mechanisms for Synchronization:
o Test-and-Set Instruction: An atomic
instruction that tests a value and sets it if
it is clear. Often used to implement locks.
o Compare-and-Swap (CAS) Instruction: An
atomic operation that compares the
current value of a variable with a given
value and, if they match, updates the
variable with a new value. Used for
implementing various synchronization
primitives.
o Interrupt Disabling: Disabling interrupts
to prevent context switches during critical
 sections, although this approach can
affect system responsiveness.
Semaphores:
1. Definition:
o A semaphore is a synchronization
primitive used to control access to shared
resources by multiple processes or
threads. It is essentially an integer
variable that is accessed and modified
atomically.
2. Operations:
o P (Proberen) or Wait Operation:
Decreases the semaphore value. If the
value is negative, the process is blocked
until the semaphore value becomes non-
negative.
o V (Verhogen) or Signal Operation:
Increases the semaphore value. If there
are processes waiting (blocked) on the
semaphore, one of them is unblocked.
3. Implementation:
 o Semaphores are implemented using
atomic operations to ensure that
operations on the semaphore are
performed without interference from
other processes. They can be used to
manage resource allocation, ensure
mutual exclusion, and coordinate
processes.
Classical Problems of Synchronization:
1. Producer-Consumer Problem:
o Description: Involves two types of
processes, producers and consumers,
sharing a common buffer. Producers
generate data and place it into the buffer,
while consumers take data from the
buffer. The problem is to ensure that the
buffer is managed properly to prevent
overflows and underflows.
o Solution Requirements: Synchronization
mechanisms are required to ensure
mutual exclusion when accessing the
buffer, proper handling of buffer
 full/empty conditions, and coordination
between producers and consumers.
2. Readers-Writers Problem:
o Description: Involves processes that read
from and write to a shared database.
Readers can read simultaneously, but
writers require exclusive access. The
challenge is to manage access to ensure
that readers and writers do not interfere
with each other.
o Solution Requirements: Ensure that no
writer is writing while readers are reading,
and no reader is reading while a writer is
writing. Solutions must also handle the
fairness of access to avoid starvation.
3. Dining Philosophers Problem:
o Description: Involves philosophers sitting
at a table with a fork between each pair.
They must alternately think and eat, but
need two forks to eat. The problem is to
prevent deadlock (where all philosophers
hold one fork and wait for the other) and
 ensure that each philosopher gets a
chance to eat.
o Solution Requirements: Ensure mutual
exclusion for fork access, prevent
deadlock, and avoid starvation (where a
philosopher is unable to eat due to others'
actions).
Monitors:
1. Definition:
o A monitor is a high-level synchronization
construct that provides a convenient way
to achieve mutual exclusion and condition
synchronization. It encapsulates shared
data and the procedures that operate on
that data within a single module.
2. High-Level Synchronization Construct:
o Encapsulation: The monitor encapsulates
shared data and synchronization
mechanisms, providing an abstraction
that simplifies synchronization.
o Condition Variables: Monitors use
condition variables to allow processes to
 wait for certain conditions to become true
and to signal when those conditions
change. Condition variables support wait()
and signal() operations.
o Mutual Exclusion: Only one process can
execute a monitor procedure at a time,
ensuring mutual exclusion.