Ce tutoriel a pour but de présenter les principaux aspects de la gestion de sémaphores et de mutex sous Delphi
et Java. Il n'est pas indispensable, mais tout de même fortement recommandé, de maîtriser les principaux concepts
de la programmation multi-thread en Delphi ou en Java. Vous pouvez à ce sujet consulter les excellents tutoriels
pour Delphi et pour
Java.
Je tiens à remercier toutes les personnes qui ont contribué à l'élaboration de ce tutoriel, notamment Laurent Dardenne
pour ses nombreuses interventions et ses relectures attentives.
Introduction
L’apparition des systèmes d’exploitation multi-tâches sur PC au début des années 90 a mis en évidence plusieurs problèmes de partage de ressources
dans l’environnement informatique. Ainsi, comment par exemple, utiliser le disque dur, lorsque plusieurs programmes demandent à écrire
ou lire dessus ? Comment imprimer deux documents sans qu’il n’y ait aucune interférence ? Ces différents problèmes ont été en partie réglés
par l’utilisation des sémaphores et des mutex, dont nous allons voir ici le fonctionnement théorique.
Un sémaphore intervient donc dans le mécanisme de partage des ressources disponibles, qu'elles soient uniques ou non, dans un environnement donné
(nous parlerons ici, en priorité, d’un environnement informatique géré par un système d’exploitation). On trouve cependant des sémaphores dans tous
les domaines de la vie courante, où les ressources doivent être partagées.
1.2. Un exemple concret
Prenons d’ores et déjà un exemple concret, afin d’illustrer le fonctionnement des sémaphores. Cet exemple est destiné à schématiser la situation :
Vous décidez d’aller dans le restaurant le plus huppé de la ville (on admet, pour l’exemple, que vous pouvez aisément vous le payer !).
Lorsque vous arrivez, vous constatez que toutes les tables sont prises, et n’ayant pas réservé, vous êtes dans l’obligation d’attendre qu’une table se libère.
Cette situation peut être gérée par un sémaphore : ici le type de ressource à se partager est la table, le nombre de ressources est connu
(par exemple 20 tables dans ce restaurant), et toutes les ressources sont malheureusement prises et aucune n’est disponible pour vous.
Vous attendez donc qu’une ressource se libère pour la prendre, vous attendez une table pour enfin pouvoir dîner !
1.3. Un exemple informatique
Ce mécanisme est similaire au sein du système d’exploitation : prenons un exemple simple avec le disque dur.
Deux ou plusieurs programmes différents tentent d’accéder au disque dur pour y faire plusieurs opérations d’écriture et de lecture.
Ici aussi, un sémaphore gère la situation : le premier des programmes accédant à la ressource (qui est unique dans ce cas, car il n’y a qu’un seul
disque dur qui intéresse les programmes) bloque les autres programmes qui attendent la libération de la ressource, le disque dur dans notre cas.
1.4. Principe des mutex
Dans ce dernier cas, on parle de mutex, car la ressource disponible est unique. Le mot mutex est une contraction de «Mutual Exclusion»,
en français «Exclusion Mutuelle», ce qui se comprend aisément : la ressource étant unique, le premier programme y accédant bloque l’accès à
tous les autres, qui attendent tous que la ressource se libère. Un mutex se comporte donc comme un sémaphore, sauf qu’il possède la particularité
de gérer une ressource unique.
2. Principe de fonctionnement
2.1. Programmes, processus et threads
Tout d’abord, faisons un résumé sur le vocabulaire que l’on peut rencontrer. Un sémaphore, comme nous l’avons vu, gère le partage de ressources
entre plusieurs programmes. Mais ceci n’est pas tout à fait vrai, si on se réfère au strict sens des termes… Un programme est avant tout composé d'un processus,
au niveau du système d’exploitation, et un processus a pour but d’exécuter des instructions. De cette façon, un processus est créé à chaque exécution
d'un programme exécutable, ou tout autre module contenant du code machine, tel qu’une DLL ou un pilote de matériel. Mais ce n’est pas tout car
un processus est composé de «threads» (en français «fil», à comprendre au sens figuré), dont le nombre peut être variable. Un thread peut être assimilé à une subdivision du
processus car chaque thread est capable
d'exécuter des instructions et donc d'accéder aux ressources de l'environnement. Tout processus contient un thread principal (le «main thread» dans la littérature informatique),
et peut contenir un ou plusieurs threads secondaires. C’est à ce niveau que les distinctions doivent être faites : puisque chaque thread peut accéder aux ressources,
c’est donc non pas entre processus mais entre threads que les sémaphores gèrent les accès.
Ainsi un sémaphore peut très bien gérer une ressource
au sein d’un même processus, entre, par exemple, le thread principal et un thread secondaire. De la même façon, deux threads n’appartenant pas au
même processus obéiront aux mêmes restrictions.
2.2. Le mécanisme des sémaphores
Observons à présent le fonctionnement général d’un sémaphore. D’un point de vue conceptuel, un sémaphore agit comme une porte d’accès,
un point d’entrée. Reprenons notre exemple du début, pour le restaurant : vous vous présentez à la réception et demandez une table,
le maître d'hôtel vous dit alors qu’il n’y a aucune table de libre et vous demande de patienter. Si l’on devait modéliser la situation
dans un système informatique, un sémaphore ferait parfaitement l’affaire pour remplacer le maître d'hôtel, et vous ne seriez
qu’un thread parmi tant d’autres ! Ici le maître d'hôtel refuse ou non votre accès à une ressource qu’est une table, il joue un rôle de régulateur,
en contrôlant le nombre de tables disponibles. Ce comportement est le même pour un sémaphore : chaque sémaphore contrôlant un type de ressource
connaît à chaque instant le nombre de ressources de ce type disponibles et autorise ou refuse l’accès d’un thread à une de ces ressources.
2.3. L'approche Objet
Si l’on approfondit le sujet, on constate qu’un sémaphore est au final un mécanisme simple. Dans un souci de compatibilité avec la majorité
des langages modernes, nous utiliserons la conception par objet pour modéliser des sémaphores et des mutex. Ainsi, un sémaphore est un objet possédant
deux attributs :
l’un de ces deux attributs doit permettre de comptabiliser le nombre de ressources disponibles à un instant donné;
l’autre attribut doit contenir le nombre maximal de ressources.
Si on reprend encore une fois l’exemple du restaurant, le sémaphore représentant le réceptionniste
aura un de ses deux attributs à 20 (le nombre maximal de tables dans le restaurant) et l’autre à 0 (le nombre de tables disponibles, c’est-à-dire aucune).
Afin de communiquer avec le sémaphore, on dispose de deux procédures, que l’on appelle communément P et V. Ces deux procédures servent pour
l’accès aux ressources : P permet ainsi de demander une ressource et V permet de libérer une ressource. Un moyen mnémotechnique pour s’en rappeler
est d’associer P à «Prendre une ressource» et V à «Valider une ressource» ! Ces deux procédures peuvent être évidemment nommées selon votre gré,
mais ces deux appellations sont les plus rencontrées dans la programmation système. Dans notre approche objet, ces deux procédures seront incluses en tant que méthodes
dans notre objet Sémaphore.
3. Programmation sous Delphi
3.1. Définition de la classe TSemaphore
Afin d’illustrer les mécanismes des sémaphores, nous implémenterons une classe sous Delphi. Cette classe représentera donc un sémaphore, avec
ses deux attributs :
«valeur», pour le nombre de ressources disponibles;
«limite», pour le nombre maximal de ressources.
Nous ajouterons également les deux procédures P et V, sans oublier une fonction qui, pour notre confort, retournera le nombre actuel de ressources disponibles.
Programmation orientée objet oblige, un constructeur sera défini pour cette classe. Enfin, la classe TSemaphore aura un attribut privé supplémentaire,
permettant de stocker le Handle retourné par la fonction CreateSemaphore de l'API Windows. En effet, Windows possède un support pour les sémaphores
et les mutex, ce support étant composé, pour chaque type, de trois fonctions.
On remarque l’utilisation de la fonction CreateSemaphore de l’API de Windows. Cette fonction permet de créer un sémaphore que Windows
pourra gérer. En effet, les mécanismes de gestion de threads étant internes à Windows, il est impossible de se passer des fonctions
dédiées pour gérer un sémaphore. La fonction CreateSemaphore renvoie un Handle vers le sémaphore qui a été créé. On ne se souciera pas
dans notre cas du paramètre de sécurité (le premier paramètre de la fonction), en acceptant d’utiliser le niveau de sécurité par défaut,
qui est suffisant dans la plupart des cas. De même, on évitera ici d'utiliser le quatrième paramètre qui permet de donner un nom au sémaphore,
étant donné que le nommage du sémaphore n’est utile que dans très peu de cas. Le nommage d'un sémaphore n'aura d'intérêt que si l'on décide de
de créer plusieurs instances d'un même sémaphore, au sein du système d'exploitation, ce qui est fait à l'aide de la fonction OpenSemaphore de l'API Windows.
Les fonctions de l'API de Windows assurent donc une gestion minimale des ressources, mais cette gestion ne remplit pas toutes nos exigences de programmeur.
Il est en effet impossible de connaître le nombre de ressources disponible à un moment donné. Ceci est comblé par l'ajout d'attribut dans la classe TSemaphore,
que nous avons programmée.
Regardons la définition de la méthode Free :
destructor TSemaphore.Destroy;
begin
CloseHandle(FHSemaphore);
inherited Destroy;
end;
Cette fonction utilise la fonction CloseHandle afin de libérer le sémaphore au sein du système d’exploitation, lorsque l’on en a plus besoin.
Cet appel est nécessaire afin de quitter proprement l’environnement d’exécution du programme !
3.3. Les principales méthodes
Arrêtons nous un instant sur les principales méthodes de l’objet TSemaphore :
procedure TSemaphore.P;
beginwhile FValeur < 1 dobegin
WaitForSingleObject(FHSemaphore, INFINITE);
end;
FValeur := FValeur - 1;
end;
procedure TSemaphore.V;
begin
FValeur := FValeur + 1;
ReleaseSemaphore(FHSemaphore, 1, nil);
end;
function TSemaphore.GetValeur: Integer;
begin
Result := FValeur;
end;
Analysons tout d’abord la méthode P : pour rappel, cette méthode sert à prendre une ressource si il y en a au moins une de disponible.
On remarque l’utilisation de la fonction WaitForSingleObject : cette fonction a pour but d’attendre que le sémaphore lui signale qu’une ressource
est libre d’accès. On passe alors le handle du sémaphore en paramètre de cette fonction. Si l’on décortique le déroulement de cette méthode P, on
observe que l'on exécute la boucle tant qu'il n'y a pas de ressource disponible. Dans ce cas-ci, la boucle s'exécute, et l'appel à la fonction WaitForSingleObject
fige le thread appelant. Ce thread continuera son exécution lorsque'il recevra un message de la part du sémaphore, l'informant qu'une ressource vient de se libérer.
L'exécution de la boucle s'achève donc, et si un autre thread n’a pas été plus «rapide», le thread appelant prend la ressource, en décrémentant la valeur de 1. Si un
autre thread a précédé ce thread, la boucle est à nouveau exécutée car à nouveau aucune ressource n'est disponible.
Regardons la méthode V, qui sert à libérer une ressource. Là aussi, nous faisons appel à une fonction de l’API de Windows, ReleaseSemaphore.
Cette fonction sert à signaler aux threads restés figés qu’une ressource vient de se libérer. L’incrémentation de la valeur du sémaphore permet de
garder le nombre de ressources disponibles à jour. Enfin la fonction getValeur est un accesseur en lecture sur l’attribut valeur, elle permet de connaître
le nombre de ressources disponibles à un moment précis.
3.4. La synchronisation sous Delphi
La synchronisation sous Delphi est faite grâce aux sections critiques. Les sections critiques permettent, dans une application possédant plusieurs threads, de contrôler
l'accès à des données ou du code précis. Une section critique agît donc comme un commutateur, au niveau du code : ainsi, un bloc de code protégé par une section critique
ne pourra être exécuté que par un seul thread à la fois. Ceci implique donc que si deux ou plusieurs threads différents tentent d'exécuter ce bloc de code, un ordre
d'exécution sera mis en place afin que chaque thread exécute le bloc de code tour à tour. Les sections critiques sont représentées à travers la classe TCriticalSection,
située dans l'unité SyncObjs. Cette classe possède deux méthodes qui permettent de délimiter le bloc de code qui sera exécuté en section critique. La première méthode,
Acquire, également appelée Enter, permet de définir le point de départ de la section critique. La seconde méthode, appelée Release ou Leave,
définit le point d'arrêt de la section critique. Voici un exemple d'utilisation des sections critiques, cet exemple étant issu de la déclaration de la méthode Depose de
la classe TBal, que nous étudierons plus tard :
procedure TBal.Depose(X: Integer);
begin
FSectionCritique.Acquire;
try
FTable[FIndiceDepot] := X;
FIndiceDepot := (FIndiceDepot + 1) mod 10;
finally
FSectionCritique.Release;
end;
end;
Ainsi tout le code situé entre ces deux méthodes s'exécutera en section critique. Une conséquence de ce concept est que
les données manipulées dans ce bloc de code protégé ne peuvent être modifiées que par un seul thread à la fois, si évidemment elles ne sont pas modifiées
hors de la section critique par tout autre thread. Dans notre cas, nous avons souhaité protéger les attributs privés de la classe TBal, qui sont FIndiceDepot et FIndiceRetrait,
car leur modification par deux ou plusieurs threads simultanément auraient pu conduire à des effets de bords désagréables, pouvant perturber le déroulement normal du programme.
4. Programmation sous Java
4.1. La classe Semaphore
Contrairement à Delphi, le langage Java prévoit un mécanisme pour gérer les sémaphores, mais il est cependant nécessaire d’utiliser le compteur
de valeur et la limite de ressources. Les deux attributs valeur et limite sont donc toujours présents dans l’implémentation sous Java.
Nous retrouvons également les deux procédures P() et V() pour la gestion des ressources et la fonction getValeur() qui retourne le nombre de
ressources disponibles.
Nous retrouvons donc les mêmes principes que pour la programmation sous Delphi, à savoir que la procédure P met en attente le thread l’appelant
avec l’instruction wait(). De la même façon, la procédure V libère une ressource et signale aux threads en attente qu’une ressource s’est libérée,
grâce à l’instruction notify(). Ces deux méthodes sont déclarées avec la directive synchronized, ce qui leur confère un traitement spécial au niveau
de la machine virtuelle : en effet, le mot clé synchronized est utilisé pour signifier que les fonctions affectées ne peuvent pas accéder en même temps
aux objets situés dans l’environnement d’exécution. Ces fonctions s’exécuteront donc l’une après l’autre si leur appel est simultané. Ceci évite ainsi
qu’un objet soit modifié par deux threads simultanément, ce qui pourrait conduire à des effets de bords indésirables.
4.3. Apparition dans Java 1.5
Depuis la version 1.5 du JRE de Java, une nouvelle classe a été introduite afin de fournir un support plus complet pour les sémaphores.
Cette classe Semaphore est située dans le package java.util.concurrent : vous pouvez obtenir les spécifications de cette classe sur le
site de Sun.
Cette nouvelle classe permet donc de créer et de manipuler des sémaphores, sans se préoccuper véritablement des compteurs de ressources disponibles,
le tout étant gérer au sein de la machine virtuelle. Un article concernant les nouveautés de Java 1.5 est également disponible.
5. Un exemple concret de Producteurs - Consommateurs
5.1. Principe général
Le principe des Producteurs - Consommateurs est bien connu des programmeurs système, car il revient très souvent au niveau
d’un système informatique. Le principe est simple, car il repose sur les relations entre plusieurs threads et un objet commun, cet objet subissant des
modifications de la part des threads. Dans cet exemple, nous prendrons le cas d’une BAL, une boîte Aux Lettres, partagée par cinq threads.
Nous stockerons dans cette boîte aux lettres des nombres entiers. Nous utiliserons également deux types de threads : trois threads seront producteurs
de valeurs, leur but sera de remplir la boîte aux lettres, et deux threads seront consommateurs, car il devront lire les valeurs situées dans la boîte.
5.2. La Boîte Aux Lettres
Afin de mieux comprend le mécanisme de gestion de la BAL, regardons les définitions de la classe TBal en Delphi et de la classe BAL Java :
type
TBal = class(TObject)
private
FTable: array[0..9] of Integer;
FIndiceDepot: Integer;
FIndiceRetrait: Integer;
FSemaphoreDepot: TSemaphore;
FSemaphoreRetrait: TSemaphore;
FMemo: TMemo;
FSectionCritique: TCriticalSection;
publicconstructor Create(Memo: TMemo);
procedure DeposeP();
procedure DeposeV();
procedure RetireP();
procedure RetireV();
procedure Depose(X: Integer);
function Retire: Integer;
procedure Affiche;
procedure Free;
end;
constructor TBal.Create(Memo: TMemo);
begininherited Create;
FMemo := Memo;
FIndiceDepot := 0;
FIndiceRetrait := 0;
FSemaphoreDepot := TSemaphore.Create(10, 10);
FSemaphoreRetrait := TSemaphore.Create(0, 10);
FSectionCritique := TCriticalSection.Create;
end;
procedure TBal.DeposeP();
begin
FSemaphoreDepot.P;
end;
procedure TBal.DeposeV();
begin
FSemaphoreDepot.V;
end;
procedure TBal.RetireP();
begin
FSemaphoreRetrait.P;
end;
procedure TBal.RetireV();
begin
FSemaphoreRetrait.V;
end;
procedure TBal.Depose(X: Integer);
begin
FSectionCritique.Acquire;
try
FTable[FIndiceDepot] := X;
FIndiceDepot := (FIndiceDepot + 1) mod 10;
finally
FSectionCritique.Release;
end;
end;
function TBal.Retire;
begin
FSectionCritique.Acquire;
try
Result := FTable[FIndiceRetrait];
FTable[FIndiceRetrait] := 0;
FIndiceRetrait := (FIndiceRetrait + 1) mod 10;
finally
FSectionCritique.Release;
end;
end;
procedure TBal.Affiche;
var Valeur: string;
var I: Integer;
begin
Valeur := '';
for I := 0 to 9 do Valeur := Valeur + IntToStr(FTable[I]);
Valeur := Valeur + Format(' %d %d', [FSemaphoreDepot.GetValeur, FSemaphoreRetrait.GetValeur]);
FMemo.Lines.Append(Valeur);
end;
procedure TBal.Free;
begin
FSemaphoreDepot.Free;
FSemaphoreRetrait.Free;
FSectionCritique.Free;
inherited Free;
end;
Afin de garder une certaine uniformité, les deux codes se ressemblent fortement, tout en respectant les contraintes de chaque langage.
On peut ainsi voir que les classes TBal en Delphi et BAL en Java se composent deux cinq attributs :
un tableau de 10 cases;
un indice de dépôt;
un indice de retrait;
un sémaphore pour le retrait;
un sémaphore pour le dépôt.
On trouve également six méthodes importantes : quatre servent à «dialoguer» avec les sémaphores,
et les deux autres servent à déposer ou retirer une valeur de la boîte. Une autre classification serait de dire que trois méthodes concernent le dépôt
et les trois autres sont utilisées pour le retrait.
5.3. Les Producteurs et les Consommateurs
Analysons maintenant les définitions des producteurs et des consommateurs :
Ces deux objets sont des descendants des classes threads disponibles pour les deux langages (nous admettrons que vous connaissez un minimum
la programmation des threads pour le langage qui vous intéresse). Intéressons nous tout d’abord aux producteurs : la méthode principale du thread
(Execute en Delphi et Run en java) contient trois appels de méthodes de la BAL. La première méthode appelée est deposeP : son but est de prendre
une ressource de dépôt si il y en a au moins une de disponible, ou de mettre en attente le thread appelant. La méthode suivante, depose, permet de
déposer une valeur générée au hasard dans la BAL, et enfin la troisième méthode retireV libère une ressource de retrait. De façon similaire,
la boucle principale des consommateurs fait appel à trois méthodes de la BAL : retireP qui doit prendre une ressource de retrait, retire qui retire
une valeur de la BAL et deposeV qui libère une ressource de dépôt. C’est encore obscur ? Ne vous inquiétez pas, nous allons analyser
tout ceci en détail !
5.4. Initialisation du mécanisme
Tout d’abord, revenons à l’objet BAL et à son initialisation (il est important de garder toujours en tête le nombre de ressources disponibles pour bien
saisir le déroulement du programme). Il existe 10 cases dans la BAL, chacune de ses cases pouvant contenir un nombre entier. Le nombre maximal de
ressources pour les sémaphores de dépôt et de retrait est donc de 10 : dans les deux cas, on ne pourra au maximum déposer que 10 valeurs et on ne
pourra en lire que 10 ! Seulement au début de l’exécution, si on admet que la BAL est vide, il y a 10 cases pour écrire mais 0 pour lire, car il n’y a rien
à lire.
C’est à ce niveau que l’initialisation correcte des sémaphores joue un rôle important : en effet, pour le sémaphore de dépôt, il y a donc
10 ressources maximales et 10 ressources disponibles, car on peut écrire dans les 10 cases du tableau, mais pour le sémaphore de retrait, il y a bien
10 ressources maximales mais 0 ressource disponible car il n’y a rien à lire.
Dans les différents codes ci-dessus, on constate que les sémaphores ont été initialisés ainsi.
5.5. Déroulement du programme
Nous pouvons débuter l’exécution du programme : les threads sont créés et lancés automatiquement, tous «en même temps». Comme nous l’avons vu
précédemment, tous les threads commencent par essayer de prendre une ressource, soit une ressource de dépôt, soit une ressource de retrait, en interrogeant le sémaphore correspondant
sur le nombre de ressource disponible. En réalité, chaque thread fait un appel à la méthode P du sémaphore concerné, il demande donc, quoi qu'il arrive, une ressource, mais si il n'y
a pas de ressource disponible, le sémaphore le met en attente. Il n'est pas évident que tous les threads obtiennent effectivement une ressource, et dans ce cas, les threads concernés se verront temporairement figés par le système.
Observons le comportement d’un thread consommateur : sa première action est d’appeler retireP, qui permet de prendre une ressource de retrait.
Seulement au tout début de l’exécution, aucun ressource de retrait n’est disponible car personne n’a encore écrit dans la BAL.
La conséquence de cet appel est donc une mise en attente du thread consommateur appelant : ainsi au début de l’exécution, les deux threads consommateurs attendent
qu’une valeur soit écrite dans la BAL.
Pour un thread producteur, le déroulement est inverse : comme la BAL est vide, 10 ressources sont disponibles,
donc le thread appelant deposeP obtient l’autorisation de déposer une valeur dans la BAL. Après le dépôt d’une valeur, l’appel à retireV permet
de signifier aux threads consommateurs qu’une ressource de retrait est disponible.
Ainsi un des deux threads consommateurs, qui avaient précédemment été figés, continue son exécution et retire une valeur de la BAL.
Après avoir retiré cette valeur, il signifie aux threads producteurs
qu’une case vient de se libérer et qu’elle est de nouveau disponible pour une écriture. Ce déroulement se prolonge jusqu’à ce que tous les threads
producteurs aient écrit leurs valeurs dans la BAL et que tous les threads consommateurs aient lu les valeurs stockées (dans notre cas, le nombre total
de valeur est de 12, un thread producteur écrivant 4 valeurs chacun et un thread consommateur en lisant 6).
A la fin de l'exécution, les producteurs et les consommateurs ayant fait tout leur travail, la BAL est à nouveau vide.
5.6. Programmes d'exemple
Les programmes disponibles en téléchargements, pour Delphi et Java, illustrent ce phénomène : pour la bonne compréhension du système, nous
avons employés des temporisateurs afin que l’exécution ne soit pas trop rapide. Les temporisateurs modifient légèrement le comportement des
sémaphores, car on perd sensiblement la notion de synchronisation, mais cette utilisation est nécessaire pour montrer le mécanisme de gestion
des sémaphores. Lors de l'exécution de ces programmes, vous pourrez constater que l'état de la BAL, ainsi que la valeur de chaque sémaphore, est affichée
soit dans une fenêtre dédiée sous Delphi, soit dans la console sous Java (la version Delphi a été compilée avec Delphi 7, et la version Java a été testé
avec succès sous Eclipse, avec un JRE version 1.4.2).
Vous avez donc toutes les cartes en main pour maîtriser la synchronisation de thread sous Delphi et Java. Pour en savoir plus
sur les threads sous Delphi, vous pouvez consulter ce tutoriel.
Il existe également un tutoriel sous Delphi pour l'exécution de tâches périodiques en arrière plan.
Pour Java, vous pouvez consulter ce cours.
Pour tous commentaires, suggestions, idées ou critiques, vous pouvez me contacter par MP ou sur les forums de developpez.com.
