EnglishA Cross-platform implementation of DIJKSTRA's semaphores for multi-threading
SUMMARY
- Introduction
- Definitions
- MultiTasking - MultiThreading
- The Dijkstra Semaphores
- The 'Mutual Exclusion' model
- The 'one producer - one consumer' model
- The 'one producer - many consumers' model
- The 'one consumer - many producers' model
- Examples: Detail of the HH&S implementation of the Dijkstra semaphores
- 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 :
Create operator : seminit(Semaphore_name, initial_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 ]
- The Create / Initialize operator
- The P operator
- The V operator
Create operator : seminit(Semaphore_name, initial_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.
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 :
The consumer :
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.
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.
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 programSee 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.
