Classical Problems of Synchronization

Classical Problems of Synchronization
Google Drive link - classical problems of synchronization

1.    Bounded-Buffer Problem ( in producer – consumer program)

The code for producer process

While(true)

    {

   // produce an item in //nextProduced

while(counter==BUFFER_SIZE)

         ; //do-nothing

Buffer[in]=nextProduced;

In=(in+1)%BUFFER_SIZE;

Counter++;

}

Structure of Producer Process

Do{

.  .  .

//produce an item in nextP

.  .  .

Wait(empty);

Wait(mutex);

.  .  .

//add nextP to buffer

.  .  .

Signal(mutex);

Signal(full);

}while(TRUE);

The code for Consumer Process

While(true)

      {

      While(counter==0)

       ; // do- nothing

    nextConsumed=buffer[out];

out=(out+1)%BUFFER_SIZE;

counter--;

//consume the item in //nextConsumed

       }

Structure of Consumer Process

Do

   {

     Wait(full);

     Wait(mutex);

     .   .   .

//remove an item from buffer to nextC

.   .   .

Signal(mutex);

Signal(empty);

.   .   .

//consume the item nextC

.   .   .

}while(TRUE);

Note:-

·        Pool of ‘n’ buffers, each capable of holding one item.

·        “mutex” semaphore provides MUTUAL EXCLUSION.

·        “empty” & “full” semaphores – count number of empty and full buffers.

·        Initialization

o   Empty=n

o   Full=0

2.    Readers – Writers Problem

·        Database is to be shared among several concurrent processes.

·        Readers – read the database

·        Writers – write to database

·        No problem – when multiple Readers tries to simultaneously access shared data.

·        Chaos – When a writer and some other process (Reader/Writer) access the database simultaneously.

·        Writers require exclusive access to database while writing to database. This synchronization problem is referred as “Readers – Writers Problem”.

·        Several variations

o   First Readers – Writers Problem ( Simplest)

o   Second Readers – Writers Problem

·        First Readers – Writers Problem

o   No reader be kept waiting unless a writer has already obtained permission to use the shared object.

(or)

No Reader should wait for other readers to finish simply because a writer is waiting.

o   Solution to this problem may result starvation (Writer).

·        Second Readers – Writers Problem

o   Once a Writer is Ready, that Writer perform its write operation as soon as possible.

(or)

If a Writer is waiting to access the object, no new readers may start reading.

o   Solution to this problem may result starvation (Reader).

·        Solution to the First Readers – Writers Problem

o   Reader process Data Structures

§  Semaphore mutex, wrt;//initialized to 1

int readcount;//initialized to 0

§  ‘wrt’ Semaphore

·        Common to both Reader & Writer Processes.

·        Functions as mutual-exclusion semaphore for Writers.

·        Used by first or last Reader that enters or exits the critical section.

·        Not used by Readers while entering or exiting the critical-section.

§  Mutex Semaphore

·        Used to ensure Mutual-Exclusion when ‘readcount’ is updated.

§  ‘Readcount’ – counts no. of processes currently reading the object.

·        Structure of Writers Process

Do{

       Wait(wrt);

          .   .   .

        //writing is performed

        .    .    .

        Signal(wrt);

      }while(TRUE);

·     Structure of Readers Process

Do{

Wait(mutex);

Readcount++;

If(readcount==1)

          Wait(wrt);

Signal(mutex);

.   .   .

//reading is performed

.   .   .

Wait(mutex);

Readcount--;

If(readcount==0)

     Signal(wrt);

Signal(mutex);

}while(TRUE);

·        If a Writer is in critical section and ‘n’ readers are waiting, then one reader is queued on ‘wrt’, and (n-1) readers are queued on ‘mutex’.

·        When a Writer executes ‘signal(wrt)’, then we may resume the execution of either waiting readers or single waiting writer.(Scheduler will select)

·        Generalized Form

o   Reader – Writer Lock is maintained.

o   In order to acquire the lock, mode of access is to be mentioned i.e., read mode / write mode.

o   Multiple processes can obtain READ MODE at once, but only one process to get WRITE MODE .

o   These LOCKs are useful when

§  We identify processes that read shared data and processes that write data.

§  In applications which has more Readers than Writers.

        

3.    Dining Philosopher’s Problem

·        Philosophers spend their lives thinking and eating

·        They do not interact with their neighbors, occasionally try to pick up 2 chopsticks (one at a time, on either side) to eat from bowl

§  Need both chopsticks to eat  

§  Cannot pick up a chopstick that is already in the hand of neighbor.

§  Put back in their place both chopsticks when done eating

·        Shared data for 5 philosophers

o   Bowl of rice (data set)

o   Semaphore chopstick[5] initialized to 1    

·        One simple solution – Represent each chopstick with a semaphore

·        Wait() – To grab a chopstick by a philosopher

·        Signal() – To release chopstick

·        The structure of Philosopher i :

do  {

          wait(chopstick[i]);

          wait(chopstick[(i+1)%5]);

          //  eat

          signal(chopstick[i]);

          signal(chopstick[(i+1)%5]);

          //  think

} while (TRUE);

·        Deadlock – when all philosophers want to eat at once by picking their right side chopstick.

·        Several Possible remedies to deadlock problem

o   Allow atmost 4 philosophers to sit simultaneously

o   Allow to pick both only when both are available

o   Odd philosophers – first right & then left

Even Philosopher – first left & then right

·        Satisfactory Solution – stop possibility of one philosopher starvation

·        Deadlock-free solution may not necessarily eliminate starvation.