Le sémaphore est un outil de synchronisation proposé par E. W.
Dijkstra [C-Dij68]. Il est encore utilisé dans un grand nombre de
systèmes.
Comme le verrou, il
permet de résoudre des problèmes d'exclusion
mutuelle. Mais il est de plus un outil de synchronisation
permettant de résoudre des problèmes complexes.
C'est un outil de bas niveau dont l'utilisation est hasardeuse.
C'est pourquoi l'accent est mis sur une méthode quasi
systématique pour résoudre des problèmes de synchronisation en
utilisant les sémaphores. Cette méthode est basée sur la notion
de condition de synchronisation.
Un sémaphore est un objet que l'on doit initialiser à sa création
(valeur par défaut 1), et sur lequel on peut appliquer deux
opérateurs (P et V) :
l'opérateur P : il peut entraîner le blocage du
processus
qui appelle cet opérateur,
l'opérateur V : il peut permettre le déblocage d'un
processus
bloqué sur le sémaphore.
Un sémaphore peut être vu comme un chapeau contenant des billes.
A la construction, on indique quel est le nombre de billes dans
le chapeau (on fournit donc une valeur entière positive ou nulle
à la déclaration d'un objet Semaphore).
Un processus
appelle la primitive P (Passeren) pour prendre une bille.
S'il n'y en a pas, le processus se
met en attente qu'une bille soit déposé. Il s'agit donc d'une
primitive permettant de programmer le blocage d'un processus.
Un processus qui
appelle la primitive V (Vrijmaken) met une bille dans le
chapeau. Celle-ci peut être prise "instantanément" par un
processus qui
était bloqué en attente de billes. L'appel de la primitive
V permet donc de débloquer un processus.
On peut donc associer à un sémaphore une valeur:
Positive ou nulle, cette valeur représente le nombre de
billes dans le chapeau.
Négative, elle représente le nombre de processus
en attente d'une bille.
Une ressource est partagée entre plusieurs processus
(par exemple une imprimante). Un seul processus à
la fois peut utiliser la ressource.
#include "Semaphore.h"
class Gestion_imprimante
{
public:
Gestion_imprimante() ; // appel du constructeur du
Semaphore
// avec 1 comme valeur pour mutex
void imprimer (...);
...
protected:
Semaphore mutex;
};
Rappelons que c'est une mauvaise solution (chap. sur l'exclusioon
mutuelle), même si elle marche. Mieux vaut déléguer à un processus
spooler que d'attendre, même si l'attente est bloquée.
Du fait que le sémaphore est initialisé à 1, le premier appel
mutex.p() n'est pas bloquant. Un mutex.p() effectué
alors que la ressource est utilisée est bloquant.
Le sémaphore mutex est un sémaphore un peu particulier :
sa valeur (nombre de billes) ne peut pas excéder 1 (s.e <=1).
Ce type de sémaphore est parfois appelé sémaphore booléen.
Les sémaphores peuvent tout d'abord être utilisés comme simple
outil de signalisation d'événement. A chaque processus
qui, en un point donné de son programme, doit attendre l'arrivée
d'un ou plusieurs signaux en provenance d'autres processus, on
associe un sémaphore privé sur lequel il peut seul
exécuter la primitive P. Le processus
effectuera autant d'appels à la primitive P que de signaux qu'il
attend. Les processus qui
émettent les signaux effectuent autant d'opération V qu'il y a de
processus
attendant le signal.
Bien que l'ouvrage CROCUS [S-Cro75] préconise une méthode de
résolution de problèmes de synchronisation à base de sémaphores
privés, nous préférons la méthode basée sur l'expression de
conditions d'attente, méthode que nous avons commencé à esquisser
dans ce chapitre.
Notre méthode adaptée aux sémaphores
Les déclarations nécessaires
Un sémaphore d'exclusion
mutuelle (initialisé à 1) pour protéger l'accès aux
variables partagées,
Un sémaphore, dit de blocage, pour chaque cause différente
d'attente [1] (ces sémaphores sont initialisés à 0). On ne
fait un V sur un sémaphore de blocage que si on est assuré
(utilisation des compteurs de processus
en attente) qu'un processus
est bloqué sur le sémaphore ou viendra faire un P (voir le
point c ci-dessous).
Pour chaque condition différente d'attente, d'une variable
contenant le nombre de processus
en attente. Cette variable est une variable partagée entre tous
les processus
et doit donc être protégée par le sémaphore d'exclusion
mutuelle.
Le schéma de blocage est quasiment toujours le même quelque soit
le problème de synchronisation. Il utilise :
Une condition d'attente exprimée par l'expression booléenne:
attente,
Le sémaphore de blocage correspondant initialisé à 0
(sema_attente),
nb_attente:= nb_attente+1;
mutex.v(); //le processus
doit libérer
//la section
critique avant de se bloquer
sema_attente.p();
}
Un seul schéma de blocage pour les sémaphores
Sur ce schéma d'attente, on peut faire trois remarques :
L'exclusion
mutuelle est nécessaire pour pouvoir tester la condition
d'attente et incrémenter le compteur,
L'exclusion
mutuelle doit être relâchée (mutex.v() ) avant
l'opération P sur le sémaphore de blocage. Sinon, un
second processus
ne pourrait pas venir modifier les variables partagées et
débloquer ce processus.
La programmation doit tenir compte du fait que le processus
peut mettre un temps très long (non connu a priori) pour passer
de l'instruction mutex.v() à l'instruction
semattente.p(). D'autres processus
peuvent s'intercaler. La solution doit fonctionner quelque soit
la vitesse respective des processus[2] .
Les déblocages doivent être programmés de telle façon qu'à l'issu
d'une phase de déblocage les invariants de sécurité et de
vivacité soient vérifiés. Avant un V sur un sémaphore de blocage,
Is doit être vérifié. Avant un V de mutex, Is et Iv doivent être
vérifiés.
{Is} sema_attente. v ( ) ;
{Is & Iv} mutex. v ( ) ;
Les deux schémas de blocage
Le schéma : un
processus
débloque plusieurs. Un processus A
qui vient de modifier l'état des variables partagées,
modification rendant possible le déblocage d'un certain nombre
de processus,
débloque tous ces processus
un par un. Le processus A
doit modifier les compteurs de processus
en attente. Une fois tous les déblocages effectués, le processus A
libère (mutex.v()) la section
critique. Le processus A
possède l'exclusion
mutuelle pendant toute la phase de déblocage, ce qui
interdit tout accès aux variables partagées par les processus
débloqués
Le schéma : un
processus
en débloque au plus un. Le processus A
débloque éventuellement un premier processus.
Celui-ci en débloque éventuellement un second, ainsi de suite
jusqu'à ce qu'il n'y ait plus de processus à
débloquer. C'est le dernier processus
débloqué qui libère la section
critique. L'exclusion
mutuelle est "passé" d'un processus à
l'autre. C'est au processus
débloqué qu'incombe la tâche de répercuter sur les variables
partagées le fait qu'il a été débloqué. Un processus
qui en débloque un autre n'a plus le droit d'accéder aux
variables partagées.
La solution dérivée de cette méthode n'est en général pas la plus
courte et la plus efficace en temps d'exécution machine. Mais le
programmeur est presque assuré d'obtenir une solution qui marche.
A chaque condition d'attente, on associe un sémaphore de blocage
initialisé à 0. Nous utiliserons des tableaux de sémaphores
indicés par les numéros de tronçon:
Nous allons donner la programmation de la procédure
entre_echange dans le cas des deux schémas de déblocage.
Nous laisserons le soin au lecteur d'écrire les procédure
entre_carrefour, entre_interne et sort_carrefour.
Nous donnons la programmation de deux procédures
libere_interne (appelée quand une voiture quitte un
tronçon interne) et libere_echange (appelée quand une voiture
quitte un tronçon d'échange).
Le processus qui
entre dans le tronçon d'échange sans attente effectue un appel
initial à libère interne. Nous utilisons une programmation
récursive plutôt qu'itérative.
void libere_interne (num_courant)
{
//Je viens de quitter le
tronçon interne num_courant, maintenant
//je dois regarder si une voiture n'était pas bloquée
//à cause de moi dans le tronçon d'échange précédent. Si
oui,
//je la débloque et j'appelle libere_echange
if
(nb_attente_dans_echange[num_courant] >0)
{
nb_attente_dans_echange[num_courant]--;
nb_echange[num_courant]--;
nb_interne[num_courant]++;
sem_entre_interne[num_courant].v(); // Iv
libere_echange(num_courant); // récursivité
}
}
void libere_echange (num_courant)
{
//Une voiture vient de
quitter le tronçon d'échange num_courant,
//maintenant je dois regarder si une voiture n'était pas
bloquée
//à cause de moi dans le tronçon interne précédent. Si
oui,
//je la débloque et j'appelle libere_interne. Sinon je
regarde
//si une voiture n'est pas bloquée à l'entrée du carrefour,
et
//si le tronçon interne précédent est libre, alors je
débloque
//cette voiture.
else if
((nb_attente_carrefour[num_courant] > 0)
&&
(! doit_attendre_carrefour [num_courant]))
{
nb_attente_carrefour[num_courant]--;
nb_echange[num_courant]++;
sem_carrefour[num_courant].v(); // Iv
}
}
void Carrefour::entre_echange (int
num_courant) { // Is et
Iv
mutex.p(); if
(doit_attendre_entree_echange(num_courant))
{
//je dois me
bloquer nb_attente_dans_interne[(num_courant-1)%
nombre_troncons]++; // Is et Iv
mutex.v(); // le processus
doit libérer la section
critique
// avant de se bloquer
sem_entre_echange[(num_courant-1)%
nombre_troncons].p(); //après je ne fais plus rien, c'est le processus qui
va me
//libérer qui s'occupera de tout.
} else{
nb_interne[(num_courant-1)%
nombre_troncons]--;
nb_echange[num_courant]++; // maintenant je dois éventuellement débloquer des
voitures
// puisque j'ai libéré une place dans le tronçon
interne
// précédent libere_interne((num_courant-1) %
nombre_troncons); // Is et Iv
mutex.v();
}
}
Sémaphores, le schéma : un processus en
débloque plusieurs
//Je viens de quitter le
tronçon interne num_courant, maintenant
//je dois regarder si une voiture n'était pas bloquée
//à cause de moi dans le tronçon d'échange précédent. Si
oui,
//je la débloque, sinon je rends l'exclusion
mutuelle.
if
(nb_attente_dans_echange[num_courant] >0)
sem_entre_interne[num_courant].v();
else // Is et Iv
mutex.v();
}
void
Carrefour::entre_echange (int num_courant)
{ // Is et Iv
mutex.p(); if
(doit_attendre_entree_echange(num_courant))
{
//je dois me bloquer
nb_attente_dans_interne[(num_courant-1)%
nombre_troncons]++; // Is et Iv
mutex.v(); // le processus
doit libérer la section
critique // avant de se bloquer
sem_entre_echange[(num_courant-1)%
nombre_troncons].p(); // le processus
débloqué possède l'exclusion
mutuelle
nb_attente_dans_interne[(num_courant-1)%
nombre_troncons]--;
// maintenant je dois éventuellement débloquer des
voitures
// puisque j'ai libéré une place dans le tronçon
interne
// précédent
libere_interne((num_courant-1) % nombre_troncons);
}
Sémaphores, le schéma : un processus en
débloque au plus 1
Pourquoi des compteurs d'attente?
Il est possible de rajouter une primitive supplémentaire aux
sémaphores permettant de connaître le nombre de processus en
attente sur un sémaphore, mais il serait incorrect d'écrire :
void libere_interne (num_courant)
{
if
(sem_entre_interne[(num_courant-1)%
nombre_troncons].nb_processus_en_attente()
> 0) {
On ne peut pas se passer des compteurs de
processus en
attente
La raison est que dans la phase de blocage, un processus
doit libérer l'exclusion
mutuelle avant de se bloquer sur un sémaphore de blocage.
Entre le mutex.v() et le mutex.p() sur le sémaphore
de blocage, d'autres processus
peuvent s'intercaler. En utilisant la fonction au lieu des
compteurs, la décision pourrait être prise d'arrêter de débloquer
des processus. On
peut alors se trouver dans la situation où un processus se
bloque alors que sa condition de passage est satisfaite.
La présence des compteurs d'attente est donc bien obligatoire
(contrairement au moniteurs paragraphe 4.5) dans le cas des deux
schémas de déblocage.
L'utilisateur n'a pas accès à la représentation interne du
sémaphore. Il n'a pas accès directement aux champs e et
liste_attente des sémaphores. Il ne peut agir sur un
sémaphore qu'à l'aide des primitives p et v et init.
Participants
