Semaphore

In sharing a resource, it is necessary to ensure "mutual exclusion".  That is, during a period of one process using that resource, other process that also want that resource must wait.  Dijkstra invented "semaphore" (1965) to achieve this mutual exclusion ("mutex") behaviour.   A semaphore is a variable (can be binary, 0/1 or an integer) associated with a resource, indicates availability of the resource to the process that requested it.  Two operations are defined on a semaphore: wait, signal  (originally Dijkstra called it P, V).  Associated with each semaphore is a waiting list of the process that wait on this semaphore.  They are defined as follows:

Wait sem
   value = value - 1
   if value < 0

      block this process, set it to WAIT
      put this process to the waiting list

Signal sem
   value = value + 1 (only when value < 1) *** see note
   if value <= 0   

      remove a waiting process from the waiting list      
      wakeup that process

These two operations must be atomic, that is, they must run to completion without interruption.  (can not task switch in between).  The initial value of a semaphore is 1.  (Note:  when signal(sem) is called before wait(sem), we will not increment its value, so the negative value shows the number of process that are waiting on this semaphore.  The value will never grow more than 1).

How to use a semaphore

For resource sharing, we can let only one process to acquire it, all other processes that request that resource will be waiting in the waiting list.   The code where this mutual exclusion is required is said to be "critical section".  A semaphore is used to protect this section.  Start with sem = 1

....
// critical section
wait sem
... code to access shared resource
signal sem

The first process that enters the critical section will "close the door".  After it exits this section, it "open the door" to let other process in.   A semaphore is the basis that other mechanism can be built such as process synchronisation or process communication. 

Process synchronisation

When two processes want to "synchronise" at some point,  two semaphores can be used to achieve it.  Let two processes be A, B.  Assume A arrives to the synchronise point before B.  Then A must wait for B and vice versa if B arrives before A.

process A            process B

wait sem1            wait sem2
signal sem2          signal sem1

Example

Two processes, one process print 1...5, the other print 11...15.  We want them to synchronise so that they print the numbers alternately.  So, the output should be   1, 11, 2, 12, 3, 13 ....   
process1()                     process2()
   for i = 1..5                   for i = 11..15
      wait sem1                      wait sem2
      signal sem2                    signal sem1
      print i                        print i

Implementation

I code three primitives into trap instructions:   newsem(), wait(), signal().   A semaphore is a block of memory.  The first slot is its value, initially is 1; the rest is the waiting list.  The list is just a list of pointer to the process, the list is terminated by 0.  The length of this list is easily found because the number of the waiting process is exactly the negative number of the semaphore value.
trap 20        newsem()         return pointer to a semaphore in r27
trap 21        wait(sem)       input sem in r1
trap 22        signal(sem)   input sem in r1

newsem()
  a = alloc(16)
  a[0] = 1
  a[1] = 0
  return a

wait(sem)
  sem[0]--
  if( sem[0] < 0 )
     put current process to the list
     block current process

signal(sem)
  if( sem[0] < 1 ) sem[0]++  
  if( sem[0] <= 0 )
     dequeue the first process from the list
     wake it up


MOS with semaphore

The package  s21mos3.zip  contains MOS with semaphore.  I change nextp() (in s2 assembly) so that the process queue is compacted when there is a process terminated (otherwise the queue continues to grow when wait() and signal() moves a process in/out of the queue).  Here is its pseudo code:
 nextp()
   if( nump == 0 ) return 0
   if( Q[qindex] == 1 )
      compact Q from qindex to qend
      qend--
   else
      qindex++
   if( Q[qindex] == 0 ) qindex = 0
   return Q[qindex]

 The first example mos5.txt  shows two processes share a variable (cnt).  Both processes share the same code.

initialisation


    st r0 cnt          ;; cnt = 0
    trap newsem
    st retval sem      ;; sem = newsem()
    mv r1 #count       ;; create process1
    jal link createp
    mv r1 #count       ;; create process2
    jal link createp


code (pseudo)


count()
   i = 0
   while i < 20
      wait(sem)
      cnt = cnt + 1     // protected shared variable
      print cnt
      signal(sem)
      i++

Here is the screen output from the run with the interrupt interval set to 100.
C:\s21i\test>as21i mos5.txt
C:\s21i\test>sim21i mos5.obj
load program, last address 123
>g
interrupt
nump 2; Q idx 0: 2100 2116 0
[1] [2] [3] [4] [5] [6] [7] interrupt
nump 2; Q idx 1: 2100 2116 0
interrupt
nump 1; Q idx 0: 1 2116 0
[8] interrupt
nump 1; Q idx 0: 1 2100 0
<9> interrupt
nump 1; Q idx 0: 1 2116 0
[10] interrupt
nump 1; Q idx 0: 1 2100 0
<11> interrupt
nump 1; Q idx 0: 1 2116 0
[12] interrupt
nump 1; Q idx 0: 1 2100 0
. . .
<19> interrupt
nump 1; Q idx 0: 1 2116 0
[20] interrupt
nump 1; Q idx 0: 1 2100 0
<21> interrupt
nump 1; Q idx 0: 1 2116 0
[22] interrupt
nump 0; Q idx 0: 1 0
stop, execute 1142 instructions
>q

Two processes increment the shared variable cnt.  They do not access cnt at the same time because it is protected by semaphore sem.  Because they are not synchronised so one process races ahead initially before the task switched.  (I made the trap print3 instruction so that it prints from process1 and process2 differently).

[1] [2] [3] [4] [5] [6] [7] interrupt

Then the two processes synchronised on wait(sem) and they increment cnt alternately. Please observe the state of the process queue that shows "1" as terminated process, "2100" process1, "2116" process2, the end of queue is "0" and nump is the number of process in the process queue.

[8] interrupt
nump 1; Q idx 0: 1 2100 0
<9> interrupt
nump 1; Q idx 0: 1 2116 0
[10] interrupt
nump 1; Q idx 0: 1 2100 0
<11> interrupt
nump 1; Q idx 0: 1 2116 0

Please also observe that the process did not stop when the count reach 20 because the other process has increment it "after" this process has checked the stopping condition.

<21> interrupt
nump 1; Q idx 0: 1 2116 0
[22] interrupt
nump 0; Q idx 0: 1 0
stop, execute 1142 instructions
>q

The second example (mos-sync.txt) shows two processes synchronised using a pair of semaphores. They do not share any variable.  Both print their own numbers.  The output is 0, 10, 1, 11, 2, 12, ...

C:\s21i\test>sim21i mos-sync.obj
load program, last address 137
>g
interrupt
nump 2; Q idx 0: 2100 2116 0
[10] interrupt
nump 1; Q idx 1: 2100 1 0
<0> interrupt
nump 1; Q idx 0: 1 2116 0
[11] interrupt
nump 1; Q idx 0: 1 2100 0
<1> interrupt
nump 1; Q idx 0: 1 2116 0
[12] interrupt
nump 1; Q idx 0: 1 2100 0
<2> interrupt
nump 1; Q idx 0: 1 2116 0
[13] interrupt
nump 1; Q idx 0: 1 2100 0
<3> interrupt
nump 1; Q idx 0: 1 2116 0
[14] interrupt
nump 1; Q idx 0: 1 2100 0
<4> interrupt
nump 1; Q idx 0: 1 2116 0
interrupt
nump 1; Q idx 0: 1 2100 0
interrupt
nump 0; Q idx 0: 1 0
stop, execute 804 instructions
>q

Important note

Because wait() and signal() is implemented as "trap" instructions, they are "atomic", that is, they are not interruptable.  When you want to implement them in assembly language you have to be careful to preserve this "atomic" property.

last update 15 Apr 2016