Journal Les sémaphores

Posté par  . Licence CC By‑SA.
Étiquettes :
13
15
oct.
2012

Sommaire

Bonjour,

Je souhaitais écrire un document sur les sémaphores ici. J’ai même commencé une implémentation de FIFO. Mais le temps me manque pour le finaliser. Néanmoins, cette semaine j’ai réagi au fait que je trouve dommage qu’un démon ne rende pas la main, seulement une fois que l'ensemble des processus résidents sont prêts à répondre. On m’a dit que : « Tu forkes pas une fois ton programme en train de fonctionner, mais avant. » là Cette affirmation, est juste dans une certaine mesure, mais rien ne justifie, à mes yeux, qu’on ne fasse pas meilleure synchronisation. UNIX, dispose d’un nombre impressionnant de moyens de communiquer entre des processus qu’ils soient afiliés ou non (Mémoire partagée, tube, tube nommé, sémaphore, file de messages…). J’ai choisi de poursuivre mon exemple ici, de lui ajouter des démons, et une synchronisation par sémaphore. Je vais essayer d'être didactique.

Sémaphore

Les sémaphores sont une manière de gérer une ressource limitée. On pourrait imaginer un moyen de communication, de 100 ko/s divisé en 10 tranches de 10 ko. Pour communiquer, un processus demande une partie de la ressource, si disponible, alors la fonction P rend la main et le processus peut utiliser la ressource demandée. Lorsqu’il a fini, il doit rendre la ressource avec la fonction V pour qu’un autre puisse l’utiliser. En fonction de ces besoins, il peut demander 1, 2, 3… 10 tranches. Pour assurer la cohérence de l’ensemble, les opération P et V sont atomiques

Les sémaphores sont souvent utilisés avec une quantité de ressource à 1, de façon à créer des mutex (verrou d’exclusion mutuelle).

Dépôt git

J’ai fait un petit dépôt git, que j’ai compressé un tgz. Il se trouve ici. Il y a 3 tags : sans_ipc, synchro_1 et final.

  • sans_ipc contient le source de base écrit dans le journal précédent.
  • synchro_1 est la transformation avec des sémaphores.
  • final est la version finale sans bug.

Il y a une version entre sans_ipc et synchro_1, qui est la modification du squelette de programme.

Architecture du logiciel

Le programme est démarré depuis un shell, celui-ci démarre le fils, le fils change de session id et démarre le démon1, le démon2 et les démonsN. Chaque démon s’initialise pendant un temps certain, implémenté avec un magnifique sleep. Ensuite, chacun appelle la fonction synchro. Le rôle de cette dernière est de prévenir le fils que le démon est prêt.

Nous avons vu qu’un sémaphore compte des ressources. Quelles sont nos ressources et combien en avons nous ?
Nos ressources sont un droit de s’initialiser. Chaque démon en a une au départ. Lorsque son initialisation est finie, il rend la ressource. Puis attend une synchronisation. Cette dernière provient d’une particularité des sémaphores sysV, qui n’ont pas 2 mais 3 opérations possibles. La première est de prendre des ressources, opération strictement négative sur le stock. La deuxième est de rendre des ressources, opération strictement positive. La troisième concerne la valeur nulle de l’opération. Dans ce cas, on attend que la ressource (la valeur du sémaphore) soit à 0.
Pour résumer, le démon lors de la synchronisation va rendre sa ressource (son droit à s’initialiser) en effectuant une opération positive. Puis, il va attendre que le nombre de ressources repasse a 0.
Le fils, qui a démarré les processus, essaye de reprendre toutes les ressources d’initialisation. Comme il essaye de tout reprendre, il n’y arrivera que lorsque tous les démons auront rendu la leur. À ce moment, la ressource passera à 0 et tous les démons pourront quitter la synchro.
Le fils détruira le sémaphore et sortira proprement, ne rendant la main que lorsque tout est fini.
Cette implémentation est visible avec le label synchro_1.

shell --|
        V
      père
        |
        |------|
      wait     V
        :     fils
        :      |
        :     init
        :    sémaphore
        :      |-------……--|-----|
        :    P(-nb_res)    V     V
        :      :         Init  Init
        :      :           |     |
        :      :           |   V(+1)
        :      :         V(+1) S(=0)
        :      :         S(=0)   :   (dernier)
        :      |           |     |
        :    rm_sem        …     …   (travail de démon)
        |<-----
shell <--

Cette implémentation, si elle semble bonne sur le papier, a néanmoins un problème. Peut-être le verrez-vous à l’exécution, mais peut-être pas. En fonction du nombre de cœur du CPU, des options du noyau… ce n’est pas forcément visible. Je ne m’attendais à l’observer, pourtant je l’ai vu en faisant mes tests.
Le fils, reprend la main, dès que le dernier V(+1) est fait. Si, pour n’importe quelle raison, le S(=0) n’est pas immédiat (reschedule), l’effacement du sémaphore se fera avant et le S(=0) retournera une erreur car le sémaphore n’existe plus.

Pour résoudre ce problème, j’ai utilisé deux autres particularités des sémaphores sysV. La première, c’est que nous disposons non pas d’un sémaphore, mais d’un ensemble de sémaphores. Si lors de la création, j’ai demandé un ensemble de 1 élément, nous allons utiliser un ensemble de 2 éléments. La deuxième particularité, c’est qu’on peut réaliser plusieurs opérations sur un même ensemble de manière atomique.

En ajoutant un 2° élément à l’ensemble, on ajoute donc une ressource qui sera : « Je suis synchronisé ». Donc la synchronisation se fera de la sorte :

     V<0>(+1)   (Comme avant, pour rendre la ressource d’init)
     S<0>(=0),V<1>(+1)  (Ces deux opérations sont atomiques)

Le fils quant à lui, va refaire une opération P<1>(-nb). Cette opération ne sera effective que lorsque tous les démons auront quitté la fonction synchro.

On aurait pu simplifier et ne pas avoir de synchronisation de démarrage. C’est-à-dire, que chaque processus, une fois prêt font le V(+1) et commence son travail immédiatement.

  • # ouah..

    Posté par  . Évalué à 9.

    Dès le matin, ça pique un peu les yeux! je le relirai tout à l'heure pour voir si je fini par comprendre quelque chose à ce journal…

  • # Pourquoi ?

    Posté par  (site web personnel) . Évalué à 7.

    Ok, des sémaphores, on faisait ça en IUT mais:

    tu crois vraiment que les devs de services utilisant des sockets ne savent pas que cela existe ? Ou alors ils s'en foutent parce que tu essayes de résoudre un non problème.

    • [^] # Re: Pourquoi ?

      Posté par  . Évalué à 3.

      C'est tellement 90 les sémaphores :D

      • [^] # Re: Pourquoi ?

        Posté par  . Évalué à 8.

        Oui depuis les gens ne savent plus coder ni les concepts fondamentaux de l'informatique ;)

        • [^] # Re: Pourquoi ?

          Posté par  . Évalué à 3.

          Cela dit tu as tout à fait raison :-/

          Je faisais une petite boutade sur ça par rapport aux supers algos non-bloquants qu'on peut croiser aujourd'hui, mais pour la plupart des gens, ça se résume à "Cette implémentation de XXXX est thread-safe, tu peux y aller Bobby, la gestion des ressources c'est pour les vieux cons"

          ps : on accorde "super[s]" ?!

          • [^] # Re: Pourquoi ?

            Posté par  . Évalué à 3.

            on accorde "super" ?

            Ben oui, c'est un adjectif.
            Mais pas de bol, il y a des exceptions pour l'accord des adjectifs. Sinon c'est pas marrant.
            Et super fait partie des exceptions : c'est un adjectif invariable.

            Quels sont ces supers serpents qui sifflent sur votre supere tête ?

          • [^] # Re: Pourquoi ?

            Posté par  . Évalué à 1.

            Je faisais une petite boutade sur ça par rapport aux supers algos non-bloquants qu'on peut croiser aujourd'hui, mais pour la plupart des gens, ça se résume à "Cette implémentation de XXXX est thread-safe, tu peux y aller Bobby, la gestion des ressources c'est pour les vieux cons"

            Cette constatation me paraît tout à fait juste. J'ai l'impression qu'entre la vitesse de découverte de nouvelles techniques et celle sa mise en œuvre, ainsi que l'apprentissage, par les générations d'informaticiens « dans la vraie vie », c'est un gouffre qui se creuse de plus en plus. Une sorte d'accumulation des « nouveautés » qui fait que ça « bouche » le cerveau de ceux qui apprennent sans être à la pointe (tout le monde ne peut pas aller voir tout le temps les dernières technos sorties) qui fait que les techniques modernes mettent de plus en plus de temps à arriver chez les développeurs lambda.

    • [^] # Re: Pourquoi ?

      Posté par  . Évalué à 1.

      Ok, des sémaphores, on faisait ça en IUT

      Très bien, puisque tu maîtrises le sujet, ce journal ne t’est pas destiné.

    • [^] # Re: Pourquoi ?

      Posté par  . Évalué à 2.

      Tu crois vraiment que tous les lecteurs de Linuxfr sont passés par un IUT info? ou même des études d'info, quel que soit le niveau ou la portée?

      • [^] # Re: Pourquoi ?

        Posté par  . Évalué à 2.

        Non. Par contre soit tu écris toujours du code séquentiel, soit t'as intérêt à connaître les bases de chez base du sujet. On est en 2012, les machines parallèles et les systèmes asynchrones sont partout. Ces concepts doivent être maîtrisé par n'importe quel programmeur et non plus seulement système.

        Donc dans un sens il a raison. Si tu découvres ca par hasard dans un journal soit tu fais parti d'un public non technique qui n'aura jamais à s'en servir, soit ça fait des années que tu fais n'importe quoi et que tu n'as lu aucune bouquin ou aucune documentation traitant du sujet sur lequel tu travailles. Et si c'est pour éduquer la masse il existe moultes excellent bouquin/articles sur le sujet selon le domaine.

        • [^] # Re: Pourquoi ?

          Posté par  . Évalué à 1.

          Si j’ai bien compris ton propos, tu parles de programmation événementielle. La plupart des frameworks faisant de l’événementiel que je connais, genre win32, Qt, le web, sont par défaut mono-thread. Donc, oui, c’est événementiel, mais il n’y a pas de concurrence d’accès. C’est possible en Qt, mais il faut que la boucle d’événement soit dans le thread principale. Pour la communication inter-thread, Qt facilite les choses via les signaux, ce qui évite de se poser des questions. Sachant que même sans protection, de nombreux algorithme marche la plupart du temps, je ne ferais pas le même constat que toi.

          • [^] # Re: Pourquoi ?

            Posté par  . Évalué à 3.

            Sachant que même sans protection, de nombreux algorithme marche la plupart du temps, je ne ferais pas le même constat que toi.

            Même un développeur web a besoin de comprendre le principe d'asynchronisme quand il va écrire ses tests Selenium où il va lancer une ou des actions dont il va devoir attendre la fin avant de valider. Comme il n'y a pas de primitives de synchronisation efficaces possibles, tu voudrais une barrière, entre les deux parties il va se l'implémenter à la main avec un busy wait (cf. FluentWait). Si le mec n'a pas compris ca, il va faire de la merde avec des suites de tests totalement instables et non déterministes. Ce n'est qu'un exemple parmi des tas.

            Mais en même temps la programmation ca ne s'arrête pas à pisser du code frontend dans un framework. Autrement tu en arrives au syndrome du "codeur PHP". Et dès que tu sors de ce cadre tu as forcément des choix à faire en terme de design qui t'imposent de comprendre et la base de la base théorique et des technos avec lesquels tu travailles. Autrement tu passes ton temps a faire des trucs qui tombent en marche. Donc oui pour moi ce sont des concepts fondamentaux à notre époque.

  • # Manque de contexte

    Posté par  . Évalué à 7.

    Ton post est difficile a lire car tu n'explique pas bien le contexte.
    La question est: un script de démarrage lançant des démons doit-il rendre la main immédiatement(1) ou bien rendre la main quand tous les démons sont prêts à fonctionner(2) (par exemple en synchronisant les démons avec un sémaphore comme tu le fais)?

    Les deux systèmes ayant leurs avantages et inconvénients, je doute qu'il y ait une réponse qui convienne a tout le monde (1 est plus rapide, 2 est plus 'prévisible' mais pas toujours simple a implémenter).

    • [^] # Re: Manque de contexte

      Posté par  . Évalué à 5.

      Tu as raison. Je n’ai pas bien expliqué pourquoi je fais ce post.

      Ça fait quelques temps que je voulais écrire un petit journal sur les sémaphores, pour plusieurs raisons. 90% si ce n’est plus de l’usage d’un sémaphore se fait via des mutex, qui ne sont qu’un cas particulier. J’ai l’impression que certains confondent sémaphore et mutex. Donc je voulais faire un post dessus.
      Il y a un mois à peu près, quelqu’un a proposé une implémentation de fifo. Ça m’a donné l’idée de faire un journal en utilisant les ipc standard en utilisant un sémaphore comme compteur de place disponible. Mais le temps m’a manqué. Suite à la discussion sur le démarrage des démons, je me suis dis, que c’était un bon exemple de sémaphore non mutex.
      Mon journal est peut-être un peu rapide, mais le code est disponible, et est, je crois un bon exemple assez compréhensible. Je ne voulais pas poster tout le code sur le journal car ça l’aurait rendu long et indigeste.

      J’ai peut-être eu tort.

  • # Mauvais lien vers le code

    Posté par  . Évalué à 1.

    Il se trouve ici
    Ton lien pointe vers linuxfr.org/…

  • # Hum

    Posté par  (site web personnel) . Évalué à 3.

    Je souhaitais écrire un document sur les sémaphores ici.

    A mon avis, si c'est pour expliquer ce qu'est un sémaphore, l'exemple est trop lourd.

    En fonction de ces besoins, il peut demander 1, 2, 3… 10 tranches.

    S'il y a une quantité de ressources à allouer qui peut varier, alors ce n'est plus un sémaphore, c'est une variable de condition (ou encore un couple mutex/sémaphore[1])

    Les sémaphores sont souvent utilisés avec une quantité de ressource à 1, de façon à créer des mutex (verrou d’exclusion mutuelle).

    Si on a besoin d'un mutex, on utilise un mutex, pas un sémaphore. Un mutex assure l'acquisition/libération par le même processus d'une ressource unique.

    Un sémaphore au contraire cible des fonctionnements producteur / consommateur, où des processus génèrent des "jetons" et d'autres les consomment, le sémaphores permettant de compter les jetons et de mettre certains processus en attente de disponibilité.

    [1] implémentable avec sémaphore public / sémaphore privé - faudrais que je remette la main sur mon cours système du CNAM.

    Votez les 30 juin et 7 juillet, en connaissance de cause. http://www.pointal.net/VotesDeputesRN

    • [^] # Re: Hum

      Posté par  . Évalué à 2.

      S'il y a une quantité de ressources à allouer qui peut varier, alors ce n'est plus un sémaphore,

      Pourquoi ? Les opérations sur les sémaphores ne sont pas uniquement des +1, -1. Donc, pour une quantité de ressource je trouve ça adapté. Après, s’il s’agit d’allocation de slot… oui, ce n’est pas adapté.

      Si on a besoin d'un mutex, on utilise un mutex, pas un sémaphore.

      Mon propos est justement, qu’un mutex est un sémaphore, mais un sémaphore avec une seule ressource et donc un sous ensemble des possibilité d’usage d’un sémaphore. Le mutex est un peu comme un bâton de parole. Je le prends, je peux lire ou/et écrire une variable (ou un ensemble de variable), puis je le rend.

      Un mutex assure l'acquisition/libération par le même processus d'une ressource unique.

      Pas forcément dans un seul processus. On peut utiliser un mutex pour protéger une mémoire partagée entre deux processus.

      Un sémaphore au contraire cible des fonctionnements producteur / consommateur,

      On produit quoi et on consomme quoi ? Dans le cas de mon exemple, on produit une ressource qui est : « Je suis initialisé », et le chef d’orchestre, consomme ces ressources, pour être sûr que tout le monde à bien fini. Je ne vois pas en quoi ça ne respecte pas le principe ? Sauf, l’usage de l’opération de synchro qui est possible grâce aux sémaphores sysV.

      • [^] # Re: Hum

        Posté par  . Évalué à 3.

        Attention, sémaphore binaire et mutex ne sont pas exactement identiques, du moins sous POSIX.
        Un mutex ne peut être déverrouillé que par le thread qui l'a verrouillé, alors que n'importe quel process/thread peut faire un up sur une sémaphore. Ca permet par exemple d'implémenter simplement un rendez-vous point.
        Les locks Python sont des sémaphores binaires, pas des mutex.

        • [^] # Re: Hum

          Posté par  (site web personnel) . Évalué à 2.

          C'est le cas aussi sous Windows avec l'API Win32:

          The ReleaseMutex function fails if the calling thread does not own the mutex object.

          (source)

          Votez les 30 juin et 7 juillet, en connaissance de cause. http://www.pointal.net/VotesDeputesRN

      • [^] # Re: Hum

        Posté par  (site web personnel) . Évalué à 3.

        Mon propos est justement, qu’un mutex est un sémaphore, mais un sémaphore avec une seule ressource et donc un sous ensemble des possibilité d’usage d’un sémaphore.

        Sémantiquement et dans les API, un mutex n'est pas un sémaphore. Même si au niveau de l'implémentation il y a du code commun pour gérer les processus en attente.

        Un mutex assure l'acquisition/libération par le même processus d'une ressource unique.

        Pas forcément dans un seul processus. On peut utiliser un mutex pour protéger une mémoire partagée entre deux processus.

        Tout à fait. Quand je dis le même processus, c'est dans le sens que c'est le processus qui a alloué qui doit faire la libération, ce n'est pas une obligation avec un sémaphore.

        On produit quoi et on consomme quoi ?

        Un rajout là dessus, un (ou plusieurs) sémaphore peut aussi être utilisé conjointement à un mutex dans le cadre de synchronisations complexes, où on l'utilise pour gérer un nombre de processus en attente d'un état particulier.

        Votez les 30 juin et 7 juillet, en connaissance de cause. http://www.pointal.net/VotesDeputesRN

        • [^] # Re: Hum

          Posté par  . Évalué à 1.

          Un rajout là dessus, un (ou plusieurs) sémaphore peut aussi être utilisé conjointement à un mutex dans le cadre de synchronisations complexes, où on l'utilise pour gérer un nombre de processus en attente d'un état particulier.

          Les sémaphores sysV, rendent justement ce service. Il suffit de déclarer un seul ensemble de sémaphores, et on peut faire diverses opérations conjointes. L’avantage par rapport à une implémentation avec mutex, c’est de limité les cas d’inter blocage. Si on prend le cas des philosophes, en un seul appel à semop, je peux prendre les deux fourchettes, ou attendre que les deux soient disponibles. Là où, avec un mutex, il faut prendre le mutex, essayer de prendre les deux fourchettes :

          • cas 1 : on peut les prendre ;
          • cas 2 : on ne prend pas la première, donc on essaye pas de prendre la seconde ;
          • cas 3 : on prend la première, mais pas la seconde, il faut re-libérer la première ;

          Ensuite on rend le mutex. Si on est pas dans le cas 1, il faut réessayer de reprendre les fourchettes. Ce qui complique l’algorithme, mais et plus formateur pour un TP ;-).

          Réf : Dîner des philosophes.

          • [^] # Re: Hum

            Posté par  (site web personnel) . Évalué à 2.

            Je ne connaissais pas cette possibilité. Qu'est-ce qu'il y a comme prévention d'interblocage, une simple acquisition des sémaphores toujours dans le même ordre ou bien un algo de détection vis à vis d'autres ressources ?

            J'avais fait un texte sur les synchros complexes (de ce que j'avais compris du cours de C.Kaiser)… faudrait que je remettes la main dessus.

            Votez les 30 juin et 7 juillet, en connaissance de cause. http://www.pointal.net/VotesDeputesRN

            • [^] # Re: Hum

              Posté par  . Évalué à 1.

              Je ne sais pas comment c’est implémenté. Mais la lib, défini un comportement et garanti un certain nombre de choses.

              struct sembuf prendre_fourchettes[] =
{
   {
    .sem_num = 0,
    .sem_op  = -1,
    .sem_flg = SEM_UNDO
   },
   {
    .sem_num = 1,
    .sem_op  = -1,
    .sem_flg = SEM_UNDO
   }
};

              Ici on prend les fourchettes 0 et 1. semop garanti que ces deux opérations seront faites de manière atomique. Mais, il ne réserve pas. Si la fourchette 1 est prise mais pas la 0, il ne prend rien. Aucun risque d’interblocage ici. J’imagine qu’en interne il doit y avoir une file d’attente des opérations non résolu, et que à chaque libération, il vérifie si une opération est devenue possible, dans ce cas il la fait, et repasse le processus à READY.

  • # barrière

    Posté par  . Évalué à 4.

    Ce que tu implémentes ici, c'est ce qu'on appelle une barrière.
    C'est disponible pour les threads POSIX avec pthread_barrier_init()/pthread_barrier_wait(), mais pas pour les IPC.
    Sous Python, le module multiprocessing supporte les barrières inter-process, par exemple.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.