Race Condition
• 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 the access takes place,
is called a race condition.
• To guard against the race condition above, we need to ensure
that only one process at a time can be manipulating the
variable.
• To make such a guarantee, we require that the processes be
synchronized in some way.
Critical Section
Consider a system consisting of n processes {P0, P1, ..., Pn−1}.
Each process has a segment of code, called a critical section, in
which the process may be accessing — and updating — data that is
shared with at least one other process.
Structure of a typical process
Structure of a typical process
• Each process must request permission to enter its critical
section. The section of code implementing this request is
the entry section.
• The critical section may be followed by an exit section.
• The remaining code is the remainder section.
Critical Section Problem
The critical-section problem is to design a protocol
that the processes can use to synchronize their
activity so as to cooperatively share data.
Requirements of Critical Section Problem’s
Solution
• Mutual exclusion: If process Pi is executing in its critical section, then no
other processes can be executing in their critical sections.
• Progress: If no process is executing in its critical section and some pro- cesses
wish to enter their critical sections, then only those processes that are not
executing in their remainder sections can participate in deciding which will
enter its critical section next, and this selection cannot be postponed
indefinitely.
• 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.
Peterson’s Solution
int turn;
boolean flag[2];
while (true) {
flag[i] = true;
turn = j;
while (flag[j] && turn == j) ;
/* critical section */
flag[i] = false;
/*remainder section */
}
Semaphores
A Semaphore is an integer variable that is used to control
access to shared resources among multiple processes.
Semaphores Operations
It can only be accessed via two atomic operations:
• wait(S) or P(S) → decreases semaphore value by 1
• signal(S) or V(S) → increases semaphore value by
1
Types of
Semaphore
Binary Counting
Semaphore Semaphore
Classical Problems of
The Bounded-Buffer Problem
Synchronization
The Readers-Writers Problem
The Dining-Philosophers Problem
The Bounded-Buffer Problem
Bounded-Buffer Problem
The producer and consumer processes share the following data
structures:
int n;
semaphore mutex = 1; // to ensure mutual exclusion
semaphore empty = n; //count of empty slots
semaphore full = 0; //count of full slots
PRODUCER CONSUMER
/* produce an item in next wait(full);
produced */ wait(mutex);
wait(empty); /* remove an item from buffer to
wait(mutex); next consumed */
/* add next produced to the buffer signal(mutex);
*/
signal(empty);
signal(mutex);
signal(full);
The Readers-Writers Problem
The Readers-Writers Problem
Some of these processes may want only to read the
database, whereas others may want to update (that is,
read and write) the database.
We distinguish between these two types of processes by
referring to the former as readers and to the latter as
writers.
The Readers-Writers Problem
Variations of Readers-Writers Problem
First Readers-Writers Problem:
Give Priority to Readers. Writers may starve.
Second Readers-Writers Problem:
Give Priority to Writers. Readers may starve.
The Readers-Writers Problem
The reader processes share the following data structures:
semaphore rw_mutex = 1; //mutual exclusion for writers
semaphore mutex = 1; // ensure mutual exclusion
int read_count = 0; //how many processes are reading the data
wait(rw_mutex);
Writer Process /* writing is performed */
signal(rw_mutex);
wait(mutex);
read_count++;
if (read_count == 1)
wait(rw mutex);
Reader signal(mutex);
Process /* reading is performed */
wait(mutex);
read_count--;
if (read count == 0)
signal(rw mutex);
signal(mutex);
The Dining Philosophers Problem
The Dining Philosophers Problem
To eat, a philosopher needs both the chopsticks adjacent to
her — one on the left and one on the right.
A philosopher cannot pick up a chopstick that is already in
use by a neighbour.
The Dining Philosophers Problem
No two neighboring philosophers should eat at the same time
because they share a chopstick between them.
The system must ensure progress — that is, philosophers
continue alternating between thinking and eating — and
resources are allocated fairly.
The Dining Philosophers Problem
semaphore chopstick[5];
wait(chopstick[i]);
wait(chopstick[(i+1) % 5]);
...
/* eat for a while */
...
signal(chopstick[i]);
signal(chopstick[(i+1) % 5]);
Deadlock in Dining Philosophers Problem
Suppose that all five philosophers become hungry at the same time
and each grabs her left chopstick.
All the elements of chopstick will now be equal to 0.
When each philosopher tries to grab her right chopstick, she will be
delayed forever.
Solution to Deadlock in Dining Philosophers
Problem
• Allow at most four philosophers to be sitting simultaneously at the
table.
• Allow a philosopher to pick up her chopsticks only if both chopsticks
are available.
• Use an asymmetric solution—that is, an odd-numbered philosopher
picks up first her left chopstick and then her right chopstick, whereas
an even- numbered philosopher picks up her right chopstick and then
her left chopstick.
The Dining Philosophers Problem – using
Monitors