La plus importante contribution au problème de la synchronisation entre processus fut l'introduction par Dijkstra, en 1965, du concept des Sémaphores.
Conceptuellement, un sémaphore joue le rôle d'un distributeur de tickets, qui, initialement dispose d'un certain nombre de tickets, éventuellement nul.
Un processus utilisateur du sémaphore demande un ticket en invoquant une opération particulière appelée P : si au moins un ticket est disponible, le processus appelant le prend et poursuit son exécution ; dans le cas contraire, le demandeur est enregistré dans une file d'attente et est bloqué dans l'attente de l'obtention d'un ticket. Autrement dit, l'opération P n'est exécutable par le processus appelant que s'il existe un ticket libre, elle peut se retrouver bloquante dans le cas contraire.
Grâce à une opération inverse, appelée V, un processus dépose son ticket dans le distributeur. Si des processus sont en attente dans la file du sémaphore, le premier d'entre eux est débloqué et obtient son ticket.
Plus précisément, un sémaphore est une variable entière non négative à laquelle, sauf pour l'initialisation, on accède seulement à travers deux opérations standards atomiques (non interruptibles) : P et V.
Algorithme de P :
TQ sémaphore < = 0 Faire
rien (nop ...)
FTQ
Décrémenter sémaphore
Algorithme de V :
Incrémenter sémaphore
Nous verrons plus tard, dans la partie Détails du fonctionnement à la page 15, comment fonctionne plus précisément les sémaphores et comment sont réalisées les opérations P et V.
Ce mécanisme permet donc de limiter l'exécution d'une portion de code (et donc l'accès à une ressource quelconque), encadrée par des appels respectifs à P et à V, à un nombre fixé de processus. Nous allons voir par la suite, que cela permet de réaliser l'exclusion mutuelle nécessaire à la prévention des conflits d'accès aux données non partageables.
Pour adapter le concept des sémaphores à certains problèmes spécifiques et, en particulier, pour répondre aux exigences du temps réel, plusieurs variantes ont été proposées :
Un sémaphore est privé à un processus dit propriétaire, si seul ce processus peut effectuer une opération P sur ce sémaphore. Il ne peut donc y avoir qu'au plus un processus en attente derrière un sémaphore privé, le processus propriétaire, et il n'est pas nécessaire alors d'avoir une file d'attente associée à un sémaphore privé. Tout processus, y compris le propriétaire, peut, par contre, exécuter une opération V sur le sémaphore privé.
voir Utilisation d'un sémaphore privé pour bloquer un processus, à la page 24
Un sémaphore binaire est une variante du mécanisme de sémaphore général. Le compteur associé au sémaphore est simplement remplacé par un booléen, qui ne peut donc prendre que les valeurs Vrai ou Faux.
L'opération P immédiate permet à un processus de demander des tickets, en lui évitant d'être bloqué si la demande ne peut pas être honorée : il sera seulement averti de l'échec de sa demande.
prototype : bool pImmediate(sem s) {...}
Grâce à l'opération P temporisée, un processus précise le temps maximum pendant lequel il accepte d'attendre que sa requête soit satisfaite : ce délai écoulé, le processus est débloqué et prévenu de l'échec.
prototype : bool ptemporise(sem s, int delai) {...}
L'opération P avec priorité range les demandes dans la file d'attente en fonction d'une priorité, ce qui permet à chaque fois de servir en premier le processus réalisant le traitement le plus urgent.
prototype : void pPriorite(sem s, int priorite) { }
Le problème de l'exclusion mutuelle peut être simplement résolu à l'aide d'un sémaphore dont la valeur initiale est fixée à 1. Un tel sémaphore est couramment appelé sémaphore d'exclusion mutuelle (mutex).
Ainsi pour garantir le respect de la section critique, il suffit de l'encadrer entre deux appels à respectivement P et V sur ce sémaphore.
Le premier processus désirant entrer en section critique (on suppose que celle-ci est libre), effectue un appel à P, et prend donc le seul ticket disponible. La valeur du sémaphore passe à 0.
Dès lors, tout autre processus désirant entrer en section critique, se voit mis en attente sur le sémaphore (lors de son appel à P), car la valeur de ce dernier est nul.
Enfin, lorsque l'exécution de la section critique est terminée, le processus l'ayant occupé effectue son appel à V afin de rendre son ticket : la valeur du sémaphore redevient positive, en l'occurrence égale à 1, et le (ou les) processus éventuellement bloqués peuvent accéder, à tour de rôle et selon la méthode précédemment décrite, à la section critique.
La section critique étant protégée par un sémaphore ne disposant que d'un ticket : un seul processus peut exécuter l'opération P avant celle-ci ne devienne bloquante, et seul l'opération V exécutée après la fin de la section critique autorise à nouveau l'exécution de P. Donc l'exclusion mutuelle est donc bien assuré.
Précision : pour un fonctionnement correct, il doit être garanti, comme dans la définitions sémantique, que les opérations P et V soient indivisibles, c'est à dire non interruptibles au profit d'un autre processus.
Nous verrons par la suite, dans la partie Utilisation d'un sémaphore privé pour bloquer un processus, à la page 24, que même si l'utilisation des sémaphores afin de restreindre l'accès à une ressource est le plus courant, il n'est pas le seul usage que l'on peut en faire.
De même que pour l'exclusion mutuelle, où l'on limitait l'exécution d'une portion de code à un seul et unique processus, en assignant la valeur 1 au sémaphore, on peut restreindre le fonctionnement d'une séquence d'instruction à un nombre fixé 'N' de processus en affectant cette valeur au sémaphore.
Cette possibilité peut être très utile pour limiter le nombre maximum de processus utilisant simultanément une ressource système, et ainsi empêcher un phénomène de saturation ou d'interblocage (dead-lock).
Nous avons vu dans la partie 2.1, à la page 12, la spécification du mécanisme des sémaphore. Nous examinerons ici, les solutions possibles pour implanter ce mécanisme dans un contexte centralisé.
Un sémaphore peut donc être représenté par un compteur, et une file d'attente de processus. La file d'attente enregistre les processus demandeurs bloqués, et le compteur représente :
Structure de données d'un sémaphore :
typedef struct
{
int valeur;
processus *ptrTeteListe;
} semaphore;
typedef struct
{
int pid;
processus *ptrSuivante;
} processus;
NB : on remarquera que le compteur interne associé à la représentation du sémaphore peut devenir négatif. Ceci est en contradiction apparente avec la spécification de la sémantique d'un sémaphore donnée précédemment. En réalité, pour l'usager du sémaphore, tout se passe comme si le compteur (logique) de tickets restait bien toujours positif ou nul. Il ne s'agit ici que d'une technique particulière qui ne contredit en rien la sémantique externe du sémaphore, et qui permet de connaître, en prenant la valeur absolue du compteur négatif, le nombre de processus bloqué dans la file d'attente.
Le principal désavantage de la définition simpliste de P, est que tout processus bloqué, essayant d'entrer en section critique, doit itérer continuellement, on appelle cela l'attente active.
Rappel : algorithme simpliste de P :
Début
TQ sémaphore < = 0 Faire
rien (nop ...)
FTQ
Décrémenter sémaphore
Fin
Cette attente gaspille des cycles du processeur, que d'autres processus pourraient utiliser de façon productive. Pour surmonter cet inconvénient, le processus peut se bloquer lui-même, en s'endormant, et en devenant donc inactif.
Implémentation de P :
Début
semaphore.valeur = semaphore.valeur - 1
Si semaphore.valeur < 0 Alors
ajouter le processus dans la liste des processus bloqués
mettre en sommeil le processus
FSi
Fin
En se mettant en sommeil, le processus devient inactif au niveau du système, et ne consomme donc plus de temps du processeur.
Le processus redevient actif, lorsque qu'un autre processus exécute V en rendant son ticket.
Implémentation de V :
Début
semaphore.valeur = semaphore.valeur + 1
Si semaphore.valeur < = 0 Alors
retirer un processus de la liste des processus bloqués
réveiller ce processus
FSi
Fin
Sauf pour le cas des sémaphores disposant de listes d'attente avec ordre de priorité (voir Quelques variantes à la page 13), en principe, le réveil des processus se fait suivant la logique des piles FIFO : le plus vieux processus endormi est réveillé.
La gestion des sémaphores sous Unix, est prise en compte par des primitives systèmes (system calls) étant donné leur principe de fonctionnement très bas niveau et la nécessité d'avoir les opérations P et V qui ne soient pas interruptibles. Les sémaphores sont donc gérés par le noyau, ils appartiennent à la classe des objets IPC.
La technique IPC Unix système V, propose un ensemble de mécanismes purement mémoires, qui permettent dans des limites de droits, à n'importe quels couples de processus d'échanger des informations et/ou de se synchroniser. Les objets IPC sont composés en :
Les processus ont le loisir de créer une file d'attente, de la supprimer, d'y ajouter ou d'en retirer un message. Ces files gérées directement dans l'espace noyau recevront des messages de différents types et tailles.
Les mémoires partagées sont des segments de mémoire qui peuvent, comme leur nom l'indique être partagé par plusieurs processus, avec les problèmes d'exclusion mutuelle que peut impliquer.
Sémaphores que l'on ne présente plus...
Le point commun des objets IPC, et qui nous intéresse plus particulièrement en ce qui concerne les sémaphores, est qu'ils forment des ressources maintenues par le noyau dans son espace personnel ; ils sont donc indépendants d'un processus particulier. Chaque processus ne fait que requérir auprès du noyau l'obtention et l'utilisation de ceux-ci.
A cette double fin (centralisation et partage), Unix maintient pour type d'objet IPC, une table personnelle identifiant chacune des instances crées. Ceci explique pourquoi, les files de messages, les mémoires partagées et les sémaphores sont tous identifiés sous la forme d'un entier (type int) souvent appelé xxxid (ou xxx est soit msg pour les files, shm pour les mémoires ou sem pour les sémaphores).
L'IPC sémaphore d'Unix possède deux généralisations qui en enrichissent encore la puissance.
Pour créer, ou acquérir un sémaphore, on dispose de la primitive suivante :
Cette fonction crée le sémaphore si celui-ci n'existe pas, ou renvoie un identificateur sur ce dernier s'il a déjà été créé par un autre processus.
Description des paramètres :
En retour, la fonction renvoie soit -1 si une erreur c'est produite, ou alors l'identificateur (semid) du sémaphore.
Ex. pour créer un sémaphore simple :
Pour affecter une valeur initiale à un sémaphore, on utilise la primitive semctl(), qui permet aussi entre autre, comme nous le verrons plus tard, de libérer un sémaphore.
Description des paramètres :
En retour, la fonction renvoie soit -1 si une erreur s'est produite.
Ex. pour initialiser un sémaphore simple à 1 (identifié par semid) :
En ce qui concerne les opérations P et V, elles peuvent être réalisées par des appels directs à la primitive système semop(), de la manière suivante :
void p(int semid)
{
int rep;
struct sembuf pd={0,-1,0};
rep=semop(semid, &pd, 1);
return(rep);
}
void v(int semid)
{
int rep;
struct sembuf pd={0,1,0};
rep=semop(semid, &pd, 1);
return(rep);
}
NB : il est très important pour le bon fonctionnement de ces deux opérations, que leur code ne comportent uniquement que des appels à semop() et rien de plus, car seul le déroulement de cette primitive est garanti comme n'étant pas interruptible par le noyau ! Cette précaution est nécessaire pour préserver le caractère atomique de ces deux opérations.
La primitive semop() permet d'augmenter ou de diminuer la valeur d'un sémaphore, et comme nous l'avons vu précédemment, elle peut le faire avec un nombre d'une valeur quelconque et sur un sémaphore qui peut éventuellement être décomposé en un sous-ensemble de sémaphore.
Description des paramètres :
Dans le cas présent, un seul sémaphore (non décomposable) nous suffit, donc la plupart de ces paramètres sont à zéro.
L'action réelle de semop()dépend de la valeur du paramètre sem_op :
Ainsi, dans les définitions précédentes de P et de V, on peut remarquer que le paramètre sem_op prend respectivement la valeur -1 (pour décrémenter le sémaphore) et la valeur 1 (pour l'incrémenter).
Remarque:
La libération d'un sémaphore est faite par un appel à semctl(), a qui l'on transmet l'identificateur du sémaphore, ainsi que la commande IPC_RMID.
Description des paramètres :
En retour, la fonction renvoie soit -1 si une erreur s'est produite.
Ex. pour libérer un sémaphore (identifié par semid) :
Bien que les sémaphores fournissent des mécanismes pratiques et efficaces (en temps machine) pour la synchronisation de processus, leur utilisation incorrecte peut encore provoquer de nombreuses erreurs de synchronisation difficiles à détecter, puisque ces erreurs surviennent seulement si certaines séquences d'exécution particulières ont lieu. Une difficulté supplémentaire et pernicieuse étant le fait que ces séquences erronées ne se produisent pas toujours.
Afin d'illustrer comment, étudions à nouveau la solution au problème de la section critique avec des sémaphores. Tous les processus partagent une variable sémaphore : mutex, initialisée à 1. Chaque processus doit exécuter un P(mutex) avant de rentrer dans la section critique, et un V(mutex) après. Si l'on ne respecte pas cette séquence, les deux processus peuvent se trouver dans leur sections critiques simultanément, ou en arriver à un situation de blocage, ou d'interblocage.
Supposons qu'un processus permute l'ordre d'exécution des opérateurs P et V sur le sémaphore d'exclusion mutuelle, ce qui provoque l'exécution suivante :
V(mutex)
...
section critique
...
P(mutex)
Dans cette situation, plusieurs processus peuvent s'exécuter simultanément dans leur sections critiques, violant ainsi le besoin de l'exclusion mutuelle. On peut aussi découvrir cette erreur si plusieurs processus sont actifs en même temps dans leur sections critiques, mais cette situation peut ne pas toujours se reproduire !
Supposons maintenant, qu'un processus remplace un appel à V (remise du ticket) par un appel à P (prise du ticket), c'est à dire qu'il exécute deux fois P :
P(mutex)
...
section critique
...
P(mutex)
Dans ce cas, il se produira irrémédiablement un blocage sur le second P.
Supposons enfin, qu'un processus omette l'appel à V ou à P, ou les deux. Dans ce cas, soit on viole l'exclusion mutuelle, soit il se produira un blocage du processus par lui-même, comme nous venons de le voir précédemment, soit les processus se bloque les uns les autres (interblocage).
Ces exemples montrent que plusieurs types d'erreurs peuvent se générer facilement quand les sémaphores sont utilisés incorrectement pour résoudre, entre autre, le problème de la section critique.
Ces cas peuvent sembler évident et facile à déceler lorsqu'ils sont isolés comme ici, mais dans l'hypothèse d'un projet volumineux, employant éventuellement plusieurs sémaphores simultanément, et se déroulant de manière assez difficile à prévoir, ils peuvent facilement se glisser dans des séquences d'instructions et être très complexe à déceler.
De plus, si un programmeur ne s'aperçoit pas qu'une structure de données particulière doit être partagée entre différents processus, il omettra d'encadrer les sections critiques par des opérateurs P et V, et cette structure sera exposée aux risques de corruption exposés dans la section 1.2.
Une des solutions introduites, pour remédier à ces inconvénients, fut l'apparition d'une autre structure de synchronisation de plus haut niveau : les Moniteurs, que nous examinerons par la suite, dans la section 4 à la page 26.
retour au Sommaire