Chapter Seven Notes Flashcards

1
Q

Bounded Buffer Problem

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Readers-writers problems

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Readers writers problem solution (both)

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Dining-Philosophers Problem

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What does Dining Philosophers Algorithm look like (code)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Dining Philosophers Algorithm Problems

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Remedies to philosophers deadlock

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly