Ad

Thursday, August 27, 2015

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.







No comments:

Post a Comment