Classical Synchronization
Problems
Synchronization Problems
• Bounded Buffer (Producer-Consumer Problem)
• Readers-Writers Problem
• Dining-Philosophers Problem
• Sleeping Barber Problem
Bounded Buffer Producer-Consumer Problem
• The bounded buffer problem, which is also called
the producer-consumer problem, is one of the classic
problems of synchronization.
• There are two processes producer and consumer,
which are operating on the buffer.
• A producer tries to insert data into an empty slot of the
buffer. A consumer tries to remove data from a filled slot
in the buffer.
• Shared data
semaphore full, empty, mutex;
Initially:
full = 0, empty = n, mutex = 1.
Producer-Consumer Problem
▪ Looking at the above code for a producer, we can see that a producer first
waits until there is at least one empty slot.
▪ Then it decrements the empty semaphore because there will now be one less
empty slot since the producer is going to insert data in one of those slots.
▪ Then, it acquires a lock on the buffer, so that the consumer cannot access the
buffer until the producer completes its operation.
▪ After performing the insert operation, the lock is released and the value
of full is incremented because the producer has just filled a slot in the buffer.
The Consumer Operation
•The consumer waits until there is at least one full slot in the
buffer.
•Then it decrements the full semaphore because the number of
occupied slots will be decreased by one after the consumer
completes its operation.
•After that, the consumer acquires a lock on the buffer.
•Following that, the consumer completes the removal operation so
that the data from one of the full slots are removed.
•Then, the consumer releases the lock.
•Finally, the empty semaphore is incremented by 1, because the
consumer has just removed data from an occupied slot, thus
making it empty.
• The consumer waits until there is at least one full slot in the
buffer.
• Then it decrements the full semaphore because the number of
occupied slots will be decreased by one after the consumer
completes its operation.
• After that, the consumer acquires a lock on the buffer.
Readers-Writers Problem
• There are two types of processes in this context.
• They are reader and writer.
• Any number of reader can read from the shared
resource simultaneously, but only one writer can write to
the shared resource.
• When a writer is writing data to the resource, no other
process can access the resource.
• A writer cannot write to the resource if there are non-
zero readers accessing the resource at that time.
Readers-Writers
▪ problem statement, it is evident that readers have higher
priority than writer.
▪ If a writer wants to write to the resource, it must wait until
there are no readers currently accessing that resource.
▪ we use one mutex m, a semaphore w An integer
variable read_count is used to maintain the number of
readers currently accessing the resource.
▪ The variable read_count is initialized to 0.
▪ A value of 1 is given initially to m and w.
▪ Instead of having the process to acquire a lock on the shared resource, we use the
mutex m to make the process to acquire and release lock whenever it is updating the
read_count variable.
•As seen above in the code for the writer, the writer just waits on the w semaphore until it
gets a chance to write to the resource.
•After performing the write operation, it increments w so that the next writer can access the
resource.
•On the other hand, in the code for the reader, the lock is acquired whenever
the read_count is updated by a process.
•When a reader wants to access the resource, first it increments the read_count value, then
accesses the resource, and then decrements the read_count value.
•The semaphore w is used by the first reader which enters the critical section and the last
reader who exits the critical section.
•The reason for this is, when the first readers enter the critical section, the writer is blocked
from the resource. Only new readers can access the resource now.
•Similarly, when the last reader exits the critical section, it signals the writer using
the w semaphore because there are zero readers now and a writer can have the chance to
access the resource.
Dining Philosopher’s Problem
• Philosophers eat/think
• Eating needs two forks
• Pick one fork at a time
• How to avoid deadlock?
Example: multiple processes competing for limited resources
solution
Consider there are five philosophers sitting around a
circular dining table.
The dining table has five chopsticks and a bowl of rice in
the middle as shown in the below figure.
▪ At any instant, a philosopher is either eating or thinking.
▪ When a philosopher wants to eat, he uses two chopsticks — one from their
left and one from their right.
▪ When a philosopher wants to think, he keeps down both chopsticks at their
original place.
▪ From the problem statement, it is clear that a philosopher can think for
an indefinite amount of time.
▪ But when a philosopher starts eating, he has to stop at some point in
time.
▪ The philosopher is in an endless cycle of thinking and eating.
▪ An array of five semaphores, stick 5 for each of the five chopsticks.
▪ When a philosopher wants to eat the rice, he will wait for the
chopstick at his left and picks up that chopstick.
▪ Then he waits for the right chopstick to be available, and then
picks it too.
▪ After eating, he puts both the chopsticks down.
▪ But if all five philosophers are hungry simultaneously, and each of
them picks up one chopstick, then a deadlock situation occurs
because they will be waiting for another chopstick forever.
▪ The possible solutions for this are:
▪ There should be at most four philosophers on the table.
▪ An even philosopher should pick the right chopstick and then the
left chopstick while an odd philosopher should pick the left
chopstick and then the right chopstick.
▪ A philosopher should only be allowed to pick their chopstick if both
are available at the same time.
▪ Monitor in an operating system is one method for
achieving process synchronization.
▪ Programming languages help the monitor to accomplish
mutual exclusion between different activities in a system.
▪ wait() and notify() constructs are synchronization functions
that are available in the Java programming language.
