Recent Post

Process Synchronization and Semaphore

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


   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.

 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.

No comments