Les Sémaphores


Définition

Introduits par Dijkstra en 1965.

Les sémaphores sont un outil élémentaire de synchronisation qui évitent l'attente active.

Un sémaphore s =

Soit p le processus qui effectue P(s) ou V(s).

P(s)
e(s) = e(s) - 1;
si e(s) < 0 alors
. état(p) = bloqué;
. entrer(p, f(s));
V(s)
e(s) = e(s) + 1;
si e(s) <= 0 alors
. sortir(q, f(s));
. état(q) = éligible;
. entrer(q, f(éligibles));

Sémaphores d'Exclusion Mutuelle

But : protéger l'accès à une ressource unique (e.g. variable, imprimante, ...).

e(s) est initialisée à 1.

Utilisation :

P(s)
< Section Critique >
V(s)

Tous les processus doivent suivre la même règle.

Sémaphores de Synchronisation

But : un processus doit en attendre un autre pour continuer (ou commencer) son exécution.

e(s) est initialisée à 0.

Utilisation :

Processus 1Processus 2
1er travail
V(s) // réveil processus 2
P(s) // attente processus 1
2ème travail

Autres utilisations des sémaphores

Le rendez-vous (généralisation du problème précédent).

Un processus doit attendre que n autres processus soient parvenus à un endroit précis pour poursuivre son exécution.

On utilise :

Processus iProcessus RdV
...
P(mutex);
nb = nb + 1;
si nb = n alors V(Ssync); nb = 0;
V(mutex);
P(Sattend);
...
...
...
P(Ssync);
V(Sattend, n);
...
...
...

Interblocage

SemA et SemB sont deux sémaphores d'exclusion mutuelle.

Processus iProcessus j
...
P(semA);
P(semB);
< SC >
V(semB);
V(semA);
...
...
P(semB);
P(semA);
< SC >
V(semA);
V(semB);
...

Il existe deux remèdes différents pour s'affranchir des interblocages.

Prévention :

Détection--Guérison :
  1. construire le graphe des conflits (périodiquement) ;
  2. si un circuit interblocage ;
  3. tuer un processus effectuer les V() manquants.


Retour au sommaire.