Sémaphore (informatique) - Définition

Introduction

Un sémaphore permet de protéger une variable (ou un type de donnée abstrait) et constitue la méthode utilisée couramment pour restreindre l'accès à des ressources partagées (par exemple un 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 THE Operating system.

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). Pour pouvoir exister sous forme logicielle, ils nécessitent une implémentation matérielle (au niveau du microprocesseur), permettant de tester et modifier la variable protégée au cours d'un cycle insécable.

Opérations prises en charge par les sémaphores

Les trois opérations prises en charge sont Init, P et V.

P et V du néerlandais Proberen et Verhogen signifient tester et incrémenter (en français "Puis-je?" et "Vas-y!"). La valeur d'un sémaphore est le nombre d'unités de ressource (exemple : imprimantes...) 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. Cette opération ne doit être utilisée qu'une seule et unique fois.

Les opérations P et V doivent être indivisibles, ce qui signifie que les différentes 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.

Opération Init(sem, val)

Initialisation d'un sémaphore :

      function Init(semaphore sem, int val)      {         disable_interrupt;       sem.K:= val;       enable_interrupt;      }      

Opération P(sem)

      function P(semaphore sem)      {      disable_interrupt;       if (sem.K == 0)       {         L.suivant = processus_courant;         processus_courant.state= bloque;         reordonnancement = vrai;       }       sem.K=sem.K-1;       enable_interrupt;      }      

Opération V(sem)

      function V(semaphore sem)      {      disable_interrupt;      sem.K=sem.K+1;      if (not L.vide)        {         processus_reveille= L.tete;         processus_reveille.state = prêt;         reordonnancement = vrai;       }      enable_interrupt;       }      

L'incrémentation de la variable s ne doit pas être interrompue, et 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. Les sémaphores peuvent être utilisés pour la synchronisation des entrées/sorties.