Sémaphore (informatique)

Cet article traite de l'application informatique de l'exclusion mutuelle. Pour les autres définitions, voir la page générale de sémaphore.

Un sémaphore est une variable protégée (ou un type de donnée abstrait) et constitue la méthode utilisée couramment pour restreindre l'accès à des ressources partagées (ex: espace de stockage) dans un environnement de programmation concurrente. Le sémaphore a été inventé par Edsger Dijkstra et utilisé pour la première fois dans le système d'exploitation THEOS.

Les sémaphores fournissent la solution la plus courante pour le fameux problème du "dîner des philosophes", bien qu'ils ne permettent pas d'éviter tous les interblocages (ou deadlocks).

Les sémaphores ne peuvent être accédés que par les opérations suivantes :

P(Semaphore s)
 {
   await s > 0 then s = s-1; /* doit être atomique une fois que s > 0 est détecté */
 }
 

V(Semaphore s)
 {
   s = s+1;   /* doit être atomique */
 }
 

Init(Semaphore s, Integer v)
 {
   s = v;
 }
 

Il est à noter que l'incrémentation de la variable s ne doit pas être interrompue, et que l'opération P ne doit pas être interrompue après que s soit différent de 0. Ceci peut être fait par une instruction spéciale ou en ignorant les interruptions afin d'empêcher d'autres processus de devenir actifs.

P et V signifient en néerlandais "Probeer", décrémenter, et "Verhoog", incrémenter. La valeur d'un sémaphore est le nombre d'unités de ressource libres. (S'il n'y a qu'une ressource, un sémaphore à système numérique binaire avec les valeurs 0 ou 1 est utilisé). L'opération P est en attente jusqu'à ce qu'une ressource soit disponible, ressource qui sera immédiatement allouée au processus courant. V est l'opération inverse; elle rend simplement une ressource disponible à nouveau après que le processus a terminé de l'utiliser. Init est seulement utilisé pour initialiser le sémaphore après une requête quelconque. Les opérations P et V doivent être indivisibles, ce qui signifie que chacune des deux opérations ne peuvent pas être exécutées plusieurs fois de manière concurrente. Un processus qui désire exécuter une opération qui est déjà en cours d'exécution par un autre processus doit attendre que le premier termine.

Dans les livres en anglais, les opérations V et P sont quelques fois appelées respectivement up et down. En conception logicielle, elles sont appelées signal et wait ou release et take.

Pour éviter l'attente, un sémaphore peut avoir une file de processus associée (généralement une file du type FIFO). Si un processus exécute l'opération P sur un sémaphore qui a la valeur zéro, le processus est ajouté à la file du sémaphore. Quand un autre processus incrémente le sémaphore en exécutant l'opération V, et qu'il y a des processus dans la file, l'un d'eux est retiré de la file et reprend la suite de son exécution.

Les sémaphores aujourd'hui

Les sémaphores sont toujours utilisés dans les langages de programmation qui n'implantent pas intrasèquement d'autres formes de synchronisation. Ils sont le mécanisme primitif de synchronisation de beaucoup de systèmes d'exploitation. La tendance dans le développement des langages de programmation est de s'orienter vers des formes plus structurées de synchronisation comme les moniteurs. Outre les problèmes d'interblocages qu'ils peuvent provoquer, les sémaphores ne protègent pas les programmeurs de l'erreur courante qui est de bloquer un sémaphore par un processus qui est déjà bloqué par ce même processus, et d'oublier de libérer un sémaphore qui a été bloqué. Hoare, Hansen, Andrews, Wirth, et même Dijkstra ont jugé le sémaphore obsolète.

Exemple d'usage du sémaphore

Outre les sémaphores à compteur interne, il existe également les sémaphores bloquant. Un sémaphore bloquant est un sémaphore qui est initialisé avec la valeur 0. Ceci a pour effet de bloquer n'importe quel thread qui fait un P(S) tant qu'un autre thread n'aura pas fait un V(S). Ce type d'utilisation est très utile lorsque l'on a besoin de contrôler l'ordre d'exécution entre threads.

Il existe également le sémaphore binaire qui est une exclusion mutuelle (mutex). Il est toujours initialisé avec la valeur 1.

See also: Sémaphore (informatique), Dijkstra, Edsger Dijkstra, FIFO, Néerlandais, Sémaphore, Thread