Semaphores

• Protected variable, which can only be accessed and modified by P and V operations, plus some initialisation code
• Binary semaphores (values 0 or 1) and general or counting semaphores (assume ONLY non-negative integer values)
• P and V are indivisible (cannot be interrupted)
• If several processes attempt P simultaneously, only one will be allowed to proceed
• Implementation of P and V ensure that none suffer indefinite postponement

P(s) ::= if s>0
 then s := s-1
 else -- suspend process on s ;

V(s) ::= if (process waiting on s)
 then -- resume one of these processes
 else s := s+1;

• Binary Semaphore : like a lock
• General semaphore : like a counter (items in a buffer)
• Initial value = number of processes in critical section simultaneously
• For mutual exclusion : initial value = 1 (only 1 process in critical section)

• Synchronisation is dispersed in processes
• Difficult to use, understand and verify (rather unstructured)
• Mistakes are disastrous
• No explicit textual association between semaphore and the date item to which it is synchronising access
• Main synchronisation primitive used in unix

  
Figure:

Producer - Consumer relation

Producer puts things into a buffer, consumer takes them out - need synchronisation for coordination
the Unix pipe :

 ls | sort | uniq

• Producer and Consumer operating at different rates - hence the user of an intermediate buffer
• Coke Machine : Producer is delivery person, consumer are staff and students