A Cross-platform implementation of DIJKSTRA's semaphores for multi-threading

SUMMARY

  1. Introduction
  2. Definitions
  3. MultiTasking - MultiThreading
  4. The Dijkstra Semaphores
  5. The 'Mutual Exclusion' model
  6. The 'one producer - one consumer' model
  7. The 'one producer - many consumers' model
  8. The 'one consumer - many producers' model
  9. Examples: Detail of the HH&S implementation of the Dijkstra semaphores
  10. The Author



1. Introduction


Multitasking appeared in the sixties, as a way to better use the computers CPU's, and as an early solution to share the same programs between several users, when 'screens' were spreading as users 'WorkStations' : handling of the same data by several workstations, using the same program (OS/MVT, IBM 1970)

But, due to hardness of programming, leak of CPU power, and lack of hardware/sofware synchronization features, Multitasking was replaced by Transaction Processing subsystems such as CICS (IBM) and TUXEDO (BEA), or home-made applications using Inter Process facilities such as UNIX IPCS (Inter Process Communication System).

Therefore, most of the Multitasking knowledge had been forgotten.

Since middle 90's, MicroComputers' CPUs where dramatically growing in power, the Multitasking came back in the Operating Systems (LINUX 1995, AIX 4, Windows/NT), and is known today as 'Multi threading'.

There is always a lack of powefull Hardware/Software synchronization features. Existing features are mostly Software only, and are different from one Operating System to another.

But everybody will afford soonly a cheap machine, with more than one CPU, and may be it's time to remember the basis of 'Multitasking'.


In this paper, we expose how to implement and use the Dijkstra semaphores, as a powerfull synchronization tool, in a unified way, on UNIX / Windows platforms.


E.W.DIJKSTRA (1930-2002) : Dutch Computer Scientist, Professor at the University of Austin (Texas).
Introcuded the concept of semaphores for multitasking programming in the mid-sixties.
further links



2. Definitions


Program :

Static description of a set of actions to be executed.

Process :

Action of running a program, with its own CPU registers, its own stack, and its own memory image, which is non-accessible from the other processes.

Multiprogramming ( 'Multiprocessing') :

Action of running several processes, each one with its own memory image :


      main process                   process    process ... process
          //                        .          .            .
          //                        .          .            .
          //                        .          .            .
         fork() --------------------------------------------//
          //                        .          .            //
          //                        .          .            //
         fork() -------------------------------//           //
          //                        .          //           //
          //                        .          //           //
          //                        .          //           //
          //                        .          //          exit()
         fork() --------------------//         //
          //                        //         //
          //                       exit()      //
          //                                   //
          //                                  exit()
          //


Status Vector ('Program Status Word' ...) :

Set of informations describing the running point of a process or task :
  • instruction counter or pointer (IP),
  • last condition code (CC),
  • CPU registers,
  • etc ...

Interrupt :

Immediate stop of a running process or task by the system, including a backup of its status vector, and replacement by another process, by restoring another status vector.

Re-entrancy :

A routine is said 're-entrant' if it can be interrupted at any running point, and replaced by another instance of itself, at the same or any other running point.
A routine running in several instances, which manipulate the same set of data outside of their own stack, without synchronization, is not re-entrant.



3. Multitasking


Subtask ('Thread') :

Action of running a routine ('function') in the CPU, concurently with the process who launched it ('Main task'), with its own registers and its own stack, but sharing the same memory image with the 'Main Task'.

Multitasking ('multithreading') :

Action of running several tasks, sharing the same memory image.


 
      Main_Task                  thread     thread   ...     thread
          //
          //
          //        
   start_task() ----------------------------------------------//
          //                                                  //
          //                                                  //
   start_task() -------------------------------//             //
          //                                   //             //
          //                                   //             //
          //                                   //             //
          //                                   //             //
          //                                   //          end_task()
   start_task() -------------------//          //
          //                       //          //
          //                       //          //           
          //                    end_task()     //
          //                                   //
          //                                   //           
          //                                end_task()
          //                             
         ... 
 



HH&S Implementation for running, ending, and waiting for tasks :

TSKID_t is a common data type for subtasks identification.

TSKID_t void strtsk(void * f, void * args)
Type   : macro
Purpose    : launch a substask, based on the code of the function ' f(args)'
Returns     : System subtask identification.


void exitsk(int rc)
Type    : macro
Purpose     : end of a substak, with a return code equal to 'rc'
Returns    : none.


TSKID_t waitsk(int cid, int rc)
Type    : macro
Purpose    : wait for the ending of the subtask identified by 'cid'
Result    : the subtask's return code in 'rc'
Returns    : Its first argument, the subtask identification (= 'cid')       


TSKID_t waitany(int rc)
Type    : macro
Purpose    : wait for the ending of any of the running subtasks.
Returns    : Identication of the next subtask that ended
Result    : the subtask's return code in 'rc'


int waitall(void)
Type    : macro
Purpose    : wait for the ending of all running subtasks.
Returns    : number of all substasks  having ended..    


TSKID_t taskid(void)
Type    : macro
Returns    : gives the System Identification of the running (calling) subtask.
  

Example of running, ending, and waiting for subtasks :


  
     #include "semhh.h"
      
     static void f(void * a);   /* declares the subtask code, = function 'f' */
      ...
      
      /*----------------------------------------------------------------*/
      /*   main :  the main task                                        */
      /*----------------------------------------------------------------*/
      main(...) {
      
         ...
      
         TASKID_t cid;           /* will hold the subtask's id .             */
         int rc;                 /* will hold the subtask's return code.     */
         char args[...];         /* or any kind of pointer for args to 'f'   */
      
         ...
      
         /*-- launches a subtask, based on the 'f' function                            --*/
         cid  = startsk(f, thearg); 
         /*-- subtask 'f' is running, its id is stored in  'cid' ...                   --*/
      
         ...
      
         /*-- wait for the end of the subtask identified by 'cid'                      --*/
         waitsk(cid, rc);
         /*-- the subtask  'cid' is over, its retcode is stored in 'rc' ...            --*/
      
      
         /*-- or :  wait for the end of any substask                                   --*/
         cid = waitany(rc);
         /* a subtask has ended, its reticde is stored in 'rc', and its Id in 'cid'    --*/
      
         ...
      
         /*-- or :  wait for the end of all subtasks that were launched                --*/
         n = waitall();
         /*-- there were 'n' subtasks running, they have all ended                     --*/ 
      
      
      }  /* end main */
      
      
      /*----------------------------------------------------------------*/
      /*   function 'f' : the subtask                                   */
      /*----------------------------------------------------------------*/
      static void f(void * a) {   /* subtask c ode f */
          int rc;
      
           ... 
      
          /* the subtask did its job, it ends with retcode = 'rc'                     --*/
          exitsk(rc);                   
         
      } /* end f */
  



4. The DIJKSTRA Semaphores


Semaphore :

Synchronisation feature, 'hardware', or 'microcoded', or simulated by the Operating System, and having non interruptible operators.
Processed as a variable in the programs, therefore to be declared, et initialized;

DIJKSTRA Semaphore :

Semaphore including a counter and a wait queue, and having 3 operators :
  • The Create / Initialize operator
  • The P operator
  • The V operator

Create operator     :     seminit(Semaphore_nameinitial_counter_value)
             The semaphore is created with counter = value, and an empty tasks queue.
             This operation must be done once for all, before any use of the semaphore.


P  operator     :   P( Semaphore_name )     [  non interruptible operation ]

  
                                  *----------*
                                  | ctr - 1  |
                                  *----------*
                                        |
                         < 0       *--------*
                   *--------------* ctr :: 0 *
                   |               *--------*
          *------------------*          |
          | calling task is  |          |  >= 0
          | stopped and added|          
          | to the wait queue|          |
          *------------------*          |
                                 [ calling task continues ]
  



V operator      :   V( Semaphore_name )   [  non interruptible operation ]

  
                                  *----------*
                                  | ctr + 1  |
                                  *----------*
                                        |
                       >= 0        *--------*
                   *--------------* ctr :: 0 *
                   |               *--------*
          *-------------------*         |
          | if queue is not   |         | < 0
          | empty, then a task|         |
          | is extracted from |         |
          | the wait queue    |         |
          *-------------------*         |
                   |                    |
                   * -------------------*
                   |                    |
                   |                    |
    [ other task continues ]      [ calling task continues  ]
  



HH&S Implementation of the semaphore operations :

void seminit(HHSEM sem, int val)
Type    : macro
Purpose    : create and initialize a semaphore, with an empty wait queue, and couter=' val'
Return    : none

void semp(HHSEM sem)
Type    : macro
Purpose    : 'P'  Operation on the 'sem' semaphore';
its counter is decremented;
if counter < 0, then the calling task is moved to the wait queue.
Returns    : none

void semv(HHSEM sem)
Type    : macro
Purpose    : 'V'  Operation on the 'sem' semaphore';
its counter is incremented;
if counter >= 0 and the wait queue is not empty,
then one of the waiting tasks is extracted to continue running.
Returns    : none


Exemples of using the 3 semaphores Operations  :

  
#include "semhh.h"
  
...
   
static HHSEM  s;          /* declares a semaphore variable named 's' */
                         
...
      
main() {
      
      int v = ...
        ...
      seminit(s, v);      /* initializes the 's' semaphore, initial value = 'v' */
        ...               /*     once, and mandatory.                           */
      
...
      
      
      semp(s);            /* P Operation    */
        ...
      semv(s);            /* V Operation    */
        ...
      

Once a semaphore is initialized, its counter and its task queue are  'Highly Confidential':
They look like unaccessible microcode objects.



5. The 'Mutual Exclusive'Model


Purpose  :

Provides re-entrancy in protecting a set of global ressources or a portion of code ('Critical Section') used by several tasks, by the way of a 'Mutual Exclusion'.


Mechanic :

A semaphore ("Mutual Exclusive", 'Mutex'), initial value  = 1;
The counter, when negative, holds the number of subtasks waiting until counter >= 0.


HHNS Implementation :


  
      #include "semhh.h"
      
      static HHSEM  s;           /* declares semaphore 's' */
      
      static int ctr=0;          /* resource to protect    */
        ...
      
      seminit(s, 1);      /* initialization semaphore 's', initial value = '1' */
      
        ...
      
      /*---- for each use of the 'ctr' variable (set/get) : ----*/
      
      semp(s); 
      ctr = ctr + 1; 
      semv(s);   /* the 'ctr' variable is protected against concurrent access */
      
        ... 
  




6. The One producer - One consumer' Model


Purpose :

Provides synchronisation between two tasks : the 'producer', which produces jobs (data or requests), and the 'consumer', which processes the jobs.


Mechanic :

A pair of semaphores ("Free/Full"), initialized to (1 / 0)

The producer :
  • waits until the consumer is 'Free' : P(Free) operation;
  • stores the job (data or request) into a 'well known' common storage location,
  • signals to the consumer that some data or request were produced : V(Full) operation;

The consumer :
  • waits until something produced : P(Full) operation
  • processes the job from the 'well known' common storage location ,
  • signals to the producer that the job is done : V(Free) operation.

HHNS Implementation :

		      
       #include "semhh.h"
      
    HHSEM  sem_free;       /* declares a semaphore variable 'sem_free'    */
    HHSEM  sem_full;       /* declares a semaphore variable 'sem_full'    */
      
        ...
      
      seminit(sem_free, 1); /* creates the semaphore 'sem_free',initial value = 1 */
      seminit(sem_full, 0); /* creates the semaphore 'sem_full',initial value = 0 */
      
        ...
      
      /*--- the producer subtasks  : ------------------*/
      semp(sem_free);      /* waits until consumer free        */
        ...                /* stores the job somewhere         */
      semv(sem_full);      /* signals 'there is a job ready'   */
      
      
      /*--- the consumer subtask ------------------*/
      semp(sem_full);      /* waits for a job                     */
        ...                /* processes the job                   */
      semv(sem_free);      /* signals 'I, consumer, am ready for next job'  */                




7. The One producer - N consumers' Model


Purpose :

Provides synchronisation between several tasks : one 'producer', which produces jobs (data or requests), and several 'consumers', which process the jobs.


Mechanic :

Basically same model as above, except that N consumer subtasks are launched.
Since there is only one slot for storing the incoming jobs, the 'free' semaphore is still initialzed to 1.
Each consumer will extract the last job stored by the producer, and will signal as soon a possible than the slot is free.


HHNS Implementation :


#include "semhh.h"
      
      HHSEM  sem_free;       /* declares a semaphore variable 'sem_free'    */
      HHSEM  sem_full;       /* declares a semaphore variable 'sem_full'    */
      HHSEM  sem_job;        /* mutual exclusive, for the 'job' area        */
      #define N 5            /* NUMBER OF PRODUCERS                         */
              ...
      
      static void consumer(void *);
      static void producer(void *);
      static char job[80];         /* job description location */
      
       
      main() { 
            int i;
      
            seminit(sem_free, 1); /* creates the semaphore 'sem_free',initial value = 1 */
            seminit(sem_full, 0); /* creates the semaphore 'sem_full',initial value = 0 */
            seminit(sem_job,  1); /* creates the semaphore 'sem_job' ,initial value = 1 */
              ...
      /* main :  starts N producers and 1 consumer  ...  */
      for (i=0; i < N; ++i) 
             strtsk(producer, NULL);
      strtsk(consumer, NULL);
      
      /* main : waits for end of all subtasks */
      waitall();
      
      }  /* end of main */
      
      
            /*--- the producer subtask  : ------------------*/
      static void producer(void *)  {
      
      for(;;) {
           ...               /* produces a job                    */
            semp(sem_free);      /* waits until consumer free         */
            semp(sem_job);       /* protection against concurrent acces to the job area */
            strcpy(job, ...);    /* fills the 'job' string            */
            semv(sem_job);       /* unprotects the 'job' string'      */
            semv(sem_full);      /* signals 'there is a job ready'    */
          }
            } /* end producer code */
      
            /*--- the N consumers subtasks : ---------------*/
      static void consumer(void *)  {
      
           for (;;) {
            semp(sem_full);      /* waits for a job                                */
            semp(sem_job);       /* protection against concurrent acces to the job area */                    
            strcpy(..., job);    /* extract the job string                         */
            semv(sem_job);       /* unprotects the 'job' string'                   */
            semv(sem_free);      /* signals 'I, consumer, am ready for next job'   */
             ...                 /* do the job                                     */
          }  
      } /* end consumer code */ 

      


8. The One consumer - N producers' Model


Purpose :

Provides synchronisation between several tasks : one 'consumer', which processes jobs (data or requests), and several 'producers', which produce jobs.


Mechanic :

Basically same as above.
As several jobs may be produced concurrently, we provide a 'job buffers table', and a pair of indexes : one for storing a job, one for extracting a job, those three job elements beeing protected by a 'mutex' semaphore.
Therefore, we can initialize the 'free' semaphore with N.


HHNS Implementation :


#include "semhh.h"
      
      HHSEM  sem_free;       /* declares a semaphore variable 'sem_free'    */
      HHSEM  sem_full;       /* declares a semaphore variable 'sem_full'    */
      HHSEM  sem_job;        /* mutual exclusive, for the 'jobs' data       */
      #define N 5            /* NUMBER OF CONSUMERS                         */
              ...
      
      static void consumer(void *);
      static void producer(void *);

      /* the jobs data : N slots, one index for filling one index for extracting  */
      static char job[N*80];       /* job description slots table    */
      static int  job_out = 0,     /* index of next job slot ready to be extracted (=full) */
                  job_in  = 0;     /* index of next job slot ready to be filled (=free)    */
       
      main() { 
            int i;
      
            seminit(sem_free, N); /* creates the semaphore 'sem_free',initial value = N */
            seminit(sem_full, 0); /* creates the semaphore 'sem_full',initial value = 0 */
            seminit(sem_job,  1); /* creates the semaphore 'sem_job' ,initial value = 1 */
              ...
            /* main :  starts N consumers and 1 producer  ...  */
            for (i=0; i < N; ++i)
                 strtsk(consumer, NULL);
            strtsk(producer, NULL);
      
            /* main : waits for end of all subtasks */
            waitall();
      
      }  /* end of main */
      
      
            /*--- the producer subtask  : ------------------*/
      static void producer(void *)  {

          for(;;) {
               ...                       /* produce a job                          */
               semp(sem_free);           /* waits until consumer free         */
               semp(sem_job);            /* protection against concurrent acces to the jobs data */
               i = job_in ++ % N;        /* i : next free slot in the job table, 0 <= i <= N-1   */
               strcpy(job + i*80, ...);  /* fills the 'job' string                 */
               semv(sem_job);            /* unprotects the jobs data               */
               semv(sem_full);           /* signals 'there is a job ready'    */
          }
      } /* end producer code */
      
            /*--- the N consumers subtasks : ---------------*/
      static void consumer(void *)  {
      
           for (;;) {
               semp(sem_full);           /* waits for a job                                */
               semp(sem_job);            /* protection against concurrent acces to the jobs data */
               i = job_out++ % N;        /* i : next full slot in the job table, 0 <= i <= N-1   */
               strcpy(..., job + i*80);  /* extract the job string                         */
               semv(sem_job);            /* unprotects the jobs data                       */
               ...                       /* process the job                                */
               semv(sem_free);           /* signals 'I, consumer, am ready for next job'   */
          }
      } /* end consumer code */ 

      



9. Examples

See HH&S Semaphore C sample C program
See HH&S Semaphore C Header C file

10. The Author


 Henri Henault
 Senior System Programer
 Author of XSM,  ACMU,  HSPO,  EVMPR softwares,  ... and many other tools.