[IOS] Ch6 Synchronization #2

Ch6.6 Classic Problems of Synchronization

• The Bounded-Buffer Problem
• The Readers-Writers Problem
• The Dining-Philosophers Problem

6.6.1. The Bounded-Buffer Problem

bounded-buffer producer process sample code:

do  {
    ...
    // produce an item in nextp
    wait(empty);
    wait(mutex);
    ...
    // add nextp to buffer
    ...
    signal(mutex);
    signal(full);
    } while (true);

bounded-buffer consumer process sample code:

do  {
    wait(full);
    wait(mutex);
    ...
    // remove an item from buffer to nextc
    ...
    // consume the item in nextc
    ...
    } while (true);

• Assume that the pool consists of n buffers
  
  • Each capable of holding one item.
• The mutex semaphore provides mutual exclusion for accesses to the buffer pool and is initialized to the value 1.
• The empty and full semaphores count the number of empty and full buffers.
  
  • empty initialized to the value n; full is initialized to the value 0.

6.6.2 The Readers-Writers Problem

Writer process:

do  {
    wait(wrt);
    ...
    // writing is performed
    ...
    signal(wrt);
    } while (true);

Reader Process:

do {
    wait(mutex);
    readcount++;
    if (readcount == 1) wait(wrt);
    signal(mutex);
    ...
    // readint is performed
    ...
    wait(mutex);
    readcount--;
    if (readcount == 0) signal(wrt);
    signal(mutex);
    } while (true);

• No reader be kept waiting unless a writer has already obtained permission to use the shared object.
  
  • writers may starve
• If a writer is waiting to access the object, no new readers may start reading.
  
  • readers may starve
• solution:
  
  • The reader processes share the following data structures:

        semaphore mutex, wrt; // initial to 1
        int readcount; // initial to 0

6.6.3 The Dining-Philosophers Problem

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

• shared data:

    semaphore chopstick[5]; // initialized to 1

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

Reference:  
Operating System Concepts 8th, by Silberschatz, Galvin, Gagne
Wikipedia