Semaphores for Multi-threading
|
A Cross-plateform Implementation of DIJKSTRA Semaphores for Multi-threading |
|
|
SUMMARY Introduction
 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 1 - 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 :
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.
2- 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 */
3 – 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 ] *----------* | 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. 4 – 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 */
...
5 – 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 :
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' */
6 - 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 */
7 - 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 */
1 - Examples See HH&S Semaphore C sample C program See HH&S Semaphore C Header C file  Author: Henri Henault Senior System Programer Author of XSM, ACMU, HSPO, EVMPR, ... and many other tools. |
| Contact | Company Info | Site map | Trademarks | Design Stéphane HENAULT © HH&S 1994-2008 |  |