CMSC 412

NOTE 9

March 16, 1999

Semaphores

1. Overview

Test-and-set and swap are low-level read-modify-write constructs, usually provided as machine instructions. A semaphore is a higher-level construct, usually provided as an OS system call. It has two properties:
  1. It can be efficiently implemented on many architectures.
  2. It is powerful enough to allow most ipc and synchronization problems to be easily solved.
As with any programming construct, it is important to distinguish the definition of a semaphore from its various implementations. The definition says what properties you can assume about a semaphore when you use it to solve synchronization problems. An implementation describes one way to achieve the properties given an architecture.

2. What is a semaphore

Definition. A semaphore S has the following properties: End definition

When several processes are stuck at P(S) and a V(S) is executed, any of the waiting processes may be allowed to get past P(S). We cannot assume that processes are woken up in some order, e.g., the longest waiting process.

Sometimes we may explicitly state that a semaphore S is not starvation-free. In this case, a waiting process can wait forever at P(S) even while the sempahore is repeatedly signalled because other processes keep executing P(S).

3. Using Semaphores

Solving Mutual Exclusion

Semaphores allow a simple solution to the N-process mutual exclusion problem: 
 // shared 
 Semaphore mutex := 1 ;  // process in CS iff mutex=0

 entry(i) {
    P(mutex)
 }

 exit(i) {
    V(mutex)
 }
Note that this satisfies both safety and progress.

Imposing execution order across processes

Suppose we want process 1 to execute a statement S only after process 2 executes a statement T. This can be solved by

3. Semaphore implementations

Implementing a semaphore S means providing Ensuring that P(S) and V(S) are atomic means ensuring that the code for P(S) and the code for V(S) are executed mutually exclusively. For this we need to make use of a solution to the CS problem. Any the previous solutions will do, and we assume we have one called X, consisting of 
     Xvars       // shared variables of X
     Xentry(i)   // entry code executed by process i
     Xexit(i)    // exit code executed by process i

3.1.  Attempted semaphore implementation using busy-waiting and CS solution X

Semaphore construct
Implementation
Semaphore S initially K record S { 
    integer val initially K, 
    Xvars appropriately initialized 
}
P(S) P(S) { 
     S.Xentry(i)    // process id i if needed in Xentry() 
  L: if S.val = 0 
       then { S.Xexit(i); go to L } 
       else { S.val := S.val - 1; S.Xexit(i) } 
}
V(S) V(S) { 
     S.Xentry(i) 
     S.val = S.val + 1; 
     S.Xexit(i) 
}
NOTE:


3.1.  Attempted semaphore implementation using blocked waiting, process queues, and CS solution X

Semaphore construct
Implementation
Semaphore S initially K record S { 
    integer val initially K, 
        queue_of_pcb wait, 
    Xvars appropriately initialized 
}
P(S) P(S) { 
     S.Xentry(i)    // process id i if needed in Xentry() 
     if S.val = 0 
       then { S.Xexit(i); 
              WaitIn( S.wait ); // syscall defined below 
       } 
       else { S.val := S.val - 1; S.Xexit(i) } 
} 

where 
  Syscall WaitIn( queue_of_pcb x ) { 
              UpdateRunQPCB(); 
              move RunQ pcb to x; 
              Scheduler(); 
  } 
 
V(S) V(S) { 
     S.Xentry(i); 
     if S.wait is not empty 
        then { move S.wait.head pcb to readyQ } 
        else { S.val = S.val + 1 }; 
     S.Xexit(i) 
}

NOTE: