Semaphore (informatique)

Semaphore (informatique)

Sémaphore (informatique)

Page d'aide sur l'homonymie Pour les articles homonymes, voir 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 (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.

Le sémaphore SEM, sa liste L et son compteur K, SEM est accessible aux opérations :
  • INIT(SEM, VAL)
  • P(SEM)
  • V(SEM)

Sommaire

Opérations prises en charge par les sémaphores

Les trois opérations prises en charge sont Init, P et V. P et V signifient en néerlandais Proberen, tester, et Verhogen, 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)

//intialisation d'une sémaphore

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

Opération P(sem)

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

Opération V(sem)

function V(semaphore sem)
{
disable_interrupt;
sem.K=sem.K+1;
if (sem.K <= 0) 
 {
   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 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. Les sémaphores peuvent être utilisés pour la synchronisation des entrées/sorties.

Les sémaphores aujourd'hui

Les sémaphores sont toujours utilisés dans les langages de programmation qui n'implémentent pas intrinsè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

Sémaphores bloquants

Outre les sémaphores à compteur interne, il existe également les sémaphores bloquants. 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 effectue 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. Cette utilisation des sémaphores permet de réaliser des barrières de synchronisation.

Exclusion mutuelle

Article détaillé : Exclusion mutuelle.

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

Résolution du problème des lecteurs/rédacteurs

Un problème classique pouvant être résolu à l'aide des sémaphores est le problème des lecteurs/rédacteurs. Ce problème traite de l'accès concurrent en lecture et en écriture à une ressource. Plusieurs processus légers (thread) peuvent lire en même temps la ressource, mais il ne peut y avoir qu'un et un seul thread en écriture.

Résolution du problème des producteurs/consommateurs

Lorsque des processus légers souhaitent communiquer entre eux, ils peuvent le faire par l'intermédiaire d'une file. Il faut définir le comportement à avoir lorsqu'un thread souhaite lire depuis la file lorsque celle-ci est vide et lorsqu'un thread souhaite écrire dans la file mais que celle-ci est pleine. Voir l'article sur le problème des producteurs et consommateurs.

Problèmes pouvant être induits par l'utilisation des sémaphores

Les sémaphores servant notamment à effectuer de la synchronisation, ils peuvent conduire à des situations indésirables, par exemple

Les méthodes de synchronisation

Barrière de synchronisation - Futex - Moniteur

Mutex - Sémaphore - Spinlock

Problèmes classiques des
méthodes de synchronisation

Couplage fort - Famine

Interblocage - Inversion de priorité

  • Portail de la programmation informatique Portail de la programmation informatique
Ce document provient de « S%C3%A9maphore (informatique) ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Semaphore (informatique) de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Sémaphore (informatique) — Pour les articles homonymes, voir sémaphore. 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… …   Wikipédia en Français

  • sémaphore — ● n. m. ou adj. ● 1. ►SYSTM Si sem op est différent de 0, et si sem flg & IPC NOWAIT est faux, sem op incrémente sem zcnt et suspend le processus appelant jusqu à ce que ce soit sem val qui devienne nul, auquel cas sem zcnt est décrémenté, ou… …   Dictionnaire d'informatique francophone

  • Semaphore — Sémaphore Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom …   Wikipédia en Français

  • Sémaphore à héritage de priorité — Le sémaphore à héritage de priorité est une variable utilisée en informatique destinée à éviter l inversion de priorité. Protocole de fonctionnement Soient trois tâches : Th : tâche avec une haute priorité Tm : tâche avec une… …   Wikipédia en Français

  • Sémaphore — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Sémaphore », sur le Wiktionnaire (dictionnaire universel) Le sémaphore est un moyen de communication… …   Wikipédia en Français

  • réseau sémaphore — ● loc. m. ►NET Voir sémaphore …   Dictionnaire d'informatique francophone

  • Parallélisme (informatique) — Pour les articles homonymes, voir parallèle. Blue Gene L cabinet., un des ordinateurs massivement parallèle les plus rapides des années 2000 En informatiqu …   Wikipédia en Français

  • Tube (informatique) — Pour les articles homonymes, voir Tube. En génie logiciel, un tube ou une pipeline est un mécanisme de communication inter processus sous la forme d une série de données, octets ou bits, accessibles en FIFO. Le patron de conception qui correspond …   Wikipédia en Français

  • Interface en informatique — Interface (informatique) ██████████ …   Wikipédia en Français

  • Specification (informatique) — Spécification (informatique) En génie informatique, la spécification est un ensemble de documents qui par des textes et des diagrammes décrit de manière formelle et exhaustive le produit informatique à réaliser. La rédaction de la spécification… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”