Process Synchronization and Semaphore

 Synchronization
Synchronization is to use atomic operations to ensure co-operation between processes.

Requirements for Synchronization Mechanism:

  (i) Mutual Exclusion: A process mutually excludes itself from competition and agrees to wait whenever the resource is not always.
  (ii) Progress : 
        (a) Initially resource must be free so that first process can progress.
        (b) Release of locks should make one of the waiting process to access the resource.
   (iii) Bounded Waiting : Due to mutual exclusion waiting time of a process must be definite ( This is achieved by writing release of locks without for getting.)

Necessary Condition for Synchronization Problems :

   (i) Critical Section : That portion of the program text where shared resources are accessed.
   (ii) Race Condition : Processes must be racing concurrently to access the critical section.
   (iii) Preemption : Running process can be preempted after completion of few instructions only in user mode.

Lock of Synchronization leads to :
  (i) Inconsistency
  (ii) Loss of data
  (iii) Deadlock

Locking Mechanisms :
   (i) The test and set operation
   (ii) Busy waiting
   (iii) Spin Locks

Principle of Mutual Exclusion : It states that no two processes may be simultaneously present in the critical section ( i.e at the same time ).

Semaphore

   It is special variable whose value indicates information about lock.

  Type of Semaphore :
    (i) Counting Semaphore
    (ii) Binary Semaphore

Operations on Semaphore :
  (i) Wait ( P ) ( Down )
       (a) It is used before entering critical section.
       (b) It decrements semaphore value by 1.
       (c) If resource is not free block the process.
  (ii) Signal ( V ) ( Up ) :
        (a) It is used after critical section to release the acquired lock.
         (b) It increments semaphore value by 1.

 

Binary Semaphore :

  Semaphore b;

  initial value b = 1;

  wait ( b )                                             Signal ( b )

  {

                                                               {

      while ( b == 0 );                                  b ++;

       b - - ;

   }                                                             }

Limitations :

  (i) There is busy wait called spin locks in binary semaphore.

  (ii) Binary semaphore can work on a single instance of resource.

  (iii) Binary semaphore wait operation should complete for a single process only.

Counting Semaphore :

  Semaphore c;

  initial value c = Number of instances of type R

   wait ( c )                                                 Signal ( c )

    {                                                              {

      c - -;                                                        c + +;

     if ( c < 0 )                                                 if ( c <= 0)

    {                                                                {

     place current process                                 wake-up one waiting process on 'c';

      in waiting queue;                                      }

       }                                                               }

      }

Classical Problems on Synchronization using Semaphore

   1. Producer Consumer Problem.

   2. Reader Writer Problem :

         (i) N readers are allowed simultaneously

         (ii) If a reader is reading

             (a) New reader is allowed
             (b) New written is NOT allowed
         (iii) If a writer is writing
              (a) New reader    |
              (b) New writer    |

(iii) Dining Philosopher Problem : Number of philosopher N >= 2.
       Solution:

 Peterson Solution for Two Process and One Shared Resource
    # define B2
    # define TRUE 1
    # define FALSE 0
       int turn;
      int interested [N] = {FALSE};
   void entry-section (int process)
   {
     int other;
      other = 1- process;
      interested [process] = TRUE;
      turn = process;
      while (interested [other] = = TRUE && turn = = process );
   }
    Critical section
     void exit section ( int process )
        {
           interested [process] = FALSE;
         }
 Peterson solution can work for only two processes and one shared resource.
 Peterson solution has a drawback called busy wait or spinlock.
 Peterson solution needs operating system intervention so that only one waiting process enters into critical section
 It suffers from priority inversion problem.