Chapter Seven Notes

Question 1

Bounded Buffer Problem

Answer 1

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.

Question 2

Readers-writers problems

Answer 2

• 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.

Question 3

Readers writers problem solution (both)

Answer 3

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.

Question 4

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);

Answer 4

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);

Question 5

Dining-Philosophers Problem

Answer 5

• 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.

Question 6

What does Dining Philosophers Algorithm look like (code)

Answer 6

do {
* wait (chopstick[i] );
* wait (chopStick[ (i + 1) % 5] );
* // eat
* signal (chopstick[i] );
* signal (chopstick[ (i + 1) % 5] );
* // think
* } while (TRUE);

Question 7

Dining Philosophers Algorithm Problems

Answer 7

• 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.

Question 8

Remedies to philosophers deadlock

Answer 8

• 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.