Scribd
Upload
322 views

Classical Problems of Synchronization

The document describes three classical synchronization problems: 1) The bounded buffer problem involves a producer inserting data into a fixed size buffer and a consumer removing data, with conditions to prevent overflow or underflow. 2) The readers-writers problem allows multiple readers to access shared data simultaneously but only one writer at a time using semaphores. 3) In the dining philosophers problem, philosophers take turns thinking and eating with shared chopsticks, requiring synchronization to prevent deadlock.

Uploaded by

veeramat
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
322 views

Classical Problems of Synchronization

The document describes three classical synchronization problems: 1) The bounded buffer problem involves a producer inserting data into a fixed size buffer and a consumer removing data, with conditions to prevent overflow or underflow. 2) The readers-writers problem allows multiple readers to access shared data simultaneously but only one writer at a time using semaphores. 3) In the dining philosophers problem, philosophers take turns thinking and eating with shared chopsticks, requiring synchronization to prevent deadlock.

Uploaded by

veeramat
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 10

Classical Problems of Synchronization

1. Bounded-Buffer Problem
2. Readers and Writers Problem
3. Dining-Philosophers Problem
Bounded-Buffer Problem
Bounded-Buffer Problem
Two Process: Fixed Size Buffer

1. Producer
2. Consumer

Producer: Insert one unit of data into the buffer


Consumer: Remove one unit of data from the buffer
Condition:
The producer must not insert data into the buffer when it is full

The Consumer must not remove the data when the buffer is empty
Producer:
do { wait(S) {
while (S <= 0); // busy wait
wait(empty); //Decrease the Empty S--;
wait(mutex); //Acquire the lock }
...
//Insert Data into the Buffer
... signal(S) {
S++;
signal(mutex); //Release the lock }
signal(full); // Increase the Full
} while (true);

Consumer
do {
wait(full); // Decrease the full
wait(mutex); //Acquire the lock
...
/* Remove an item from the buffer
...
signal(mutex); // Release the lock
signal(empty); // Increase the empty
...
} while (true);
Readers and Writers Problem
Readers and Writers Problem
• A data set is shared among a number of concurrent processes
• Readers – only read the data set; they do not perform any updates
• Writers – can both read and write

• Problem – allow multiple readers to read at the same time


• Only one single writer can access the shared data at the same time

• Several variations of how readers and writers are considered – all involve some form of priorities

• Shared Data
• Data set
• Semaphore rw_mutex initialized to 1
• Semaphore mutex initialized to 1
• Integer read_count initialized to 0
Readers and Writers Problem
signal(S) {
S++;
}

Reader:
wait(S) {
do { while (S <= 0); // busy
wait(mutex); wait
read_count++; S--;
if (read_count == 1) }
wait(rw_mutex);
signal(mutex);
... Writer Process:
/* reading is performed */ do {
... wait(rw_mutex);
wait(mutex); ...
read count--; /* writing is performed */
if (read_count == 0) ...
signal(rw_mutex); signal(rw_mutex);
signal(mutex); } while (true);
} while (true);
Dining-Philosophers Problem

• Philosophers spend their lives alternating thinking and eating


• Don’t interact with their neighbors, occasionally try to pick up 2 chopsticks
(one at a time) to eat from bowl
• Need both to eat, then release both when done
• In the case of 5 philosophers
• Shared data
• Bowl of rice (data set)
• Semaphore chopstick [5] initialized to 1

12/28/2023 21CSC202J Operating Systems UNIT 2 8


Dining-Philosophers Problem Algorithm
• The structure of Philosopher i:
do {
wait (chopstick[i] );
wait (chopStick[ (i + 1) % 5] );

// eat

signal (chopstick[i] );
signal (chopstick[ (i + 1) % 5] );

// think

} while (TRUE);

• What is the problem with this algorithm?

12/28/2023 21CSC202J Operating Systems UNIT 2 9


Dining-Philosophers Problem Algorithm (Cont.)

• Deadlock handling
• Allow at most 4 philosophers to be sitting
simultaneously at the table.
• Allow a philosopher to pick up the forks only if both
are available (picking must be done in a critical section.
• Use an asymmetric solution -- an odd-numbered
philosopher picks up first the left chopstick and then
the right chopstick. Even-numbered philosopher picks
up first the right chopstick and then the left chopstick.

12/28/2023 21CSC202J Operating Systems UNIT 2 10

You might also like