Chapter Seven Notes Flashcards
Bounded Buffer Problem
Classic example of a multi-process synchronization problem. The problem describes two processes, the producer and the consumer, who share a common, fixed-size buffer used as a queue.
Readers-writers problems
- First readers–writers problem is that
no reader should wait for other readers
to finish simply because a writer is
waiting - The second readers–writers problem is if a writer is waiting to
access the object, no new readers may
start reading.
A solution to either problem may result
in starvation. In the first case, writers
may starve; in the second case, readers
may starve.
Readers writers problem solution (both)
Reader processes share data structures:
The reader processes share the following data structures:
semaphore rw_mutex = 1;
semaphore mutex = 1;
int read_count = 0;
- Semaphore rw_mutex initialized to 1: it is common to both reader and writer
processes. It functions as a mutual exclusion semaphore for the writers. It is also used by
the first or last reader that enters or exits the critical section. It is not used by readers
that enter or exit while other readers are in their critical sections.
- Semaphore mutex initialized to 1: It is used to ensure mutual exclusion when the
variable read_count is updated.
- Integer read_count initialized to 0: it is keeps track of how many processes are
currently reading the object.
This a functioning solution to readers-writers problem (T/F):
semaphore rw_mutex = 0;
semaphore mutex = 1;
int read_count = 1;
writer process:
do {
wait(rw_mutex);
…
/* writing is performed */
…
signal(rw_mutex);
} while (true);
reader process:
do {
wait(mutex);
read_count++;
if (read_count == 1)
wait(rw_mutex);
signal(mutex);
…
/* reading is
performed */
…
wait(mutex);
read count–;
if (read_count == 0)
signal(rw_mutex);
signal(mutex);
} while (true);
False, semaphore rw_mutex is initialized to 1, and read_count is initialized to 0.
This is the correct solution:
semaphore rw_mutex = 0;
semaphore mutex = 1;
int read_count = 1;
writer process:
do {
wait(rw_mutex);
…
/* writing is performed */
…
signal(rw_mutex);
} while (true);
reader process:
do {
wait(mutex);
read_count++;
if (read_count == 1)
wait(rw_mutex);
signal(mutex);
…
/* reading is
performed */
…
wait(mutex);
read count–;
if (read_count == 0)
signal(rw_mutex);
signal(mutex);
} while (true);
Dining-Philosophers Problem
- This problem is considered a classic
synchronization problem because it is
an example of a large class of
concurrency-control problems. - It is a simple representation of the
need to allocate several resources
among several processes in a
deadlock-free and starvation-free
manner.
What does Dining Philosophers Algorithm look like (code)
do {
* wait (chopstick[i] );
* wait (chopStick[ (i + 1) % 5] );
* // eat
* signal (chopstick[i] );
* signal (chopstick[ (i + 1) % 5] );
* // think
* } while (TRUE);
Dining Philosophers Algorithm Problems
- Although this solution guarantees
that no two neighbors are eating
simultaneously, it nevertheless must
be rejected because it could create a
deadlock. - 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.
Remedies to philosophers deadlock
- 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 (to do this, she must
pick them up in a critical section). - 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.