[Tuto] L'art de la sémaphorisation

Espace contenant des tutoriels divers concernant AutoIt.
Règles du forum
.

Tutoriel "La programmation avec Autoit" : https://openclassrooms.com/fr/courses/1 ... vec-autoit
Répondre
Avatar du membre
ZDS
Membre émérite
Membre émérite
Messages : 554
Enregistré le : jeu. 10 juin 2010 09:35
Localisation : 22300 Cul-d'chouette Langue-de-vache
Status : Hors ligne

[Tuto] L'art de la sémaphorisation

#1

Message par ZDS » jeu. 19 mai 2011 14:12

Bonjour à tous ! Depuis quelques temps je m'intéresse à un principe tout simple, faire communiquer plusieurs tout petits scripts entre eux pour faire le travail d'un programme plus grand : c'est ce qu'on appelle de l'algorithmique distribuée, très utile à l'heure où quasiment tout le monde utilise des ordinateurs multi-coeurs qui sont spécialisés pour cela. Mais en faisant ce genre d'architecture, on se heurte à des soucis de partage mémoire et d'accès concurrents, les scripts se marchant sur les pieds les uns les autres... D'où une "police" de non-interférence : la sémaphorisation !

Introduction :

Pour ceux qui ne savent pas ce qu'est la sémaphorisation, il faut d'abord se demander comment marche un ordinateur pour faire fonctionner deux programmes à la fois : en effet, il est tout à fait possible de lancer un Bloc-Notes et la Calculatrice en même temps, une vidéo et Firefox en parallèle, etc... pourtant quand on travaille sur un, les autres ne s'arrêtent pas de tourner pour autant. Cela est dû à ce qu'on appelle un tourniquet (cf tourniquet/noyau/gestion de processus) : Chaque programme a un processus, chaque processus est identifié par un PID (processus ID), et le tourniquet donne la parole à chaque processus à la suite en changeant toutes les millisecondes/microsecondes/nanosecondes par exemple; ainsi les processus semblent tourner ensemble en même temps, mais en réalité, ils effectuent un bout de chemin chacun leur tour.

Cela permet à l'ordinateur de faire plusieurs choses à la fois de notre point de vue alors que de base le processeur de l'ordinateur ne fait qu'une seule opération à la fois. Mais que se passe-t'il lorsque deux programmes tentent de faire la même chose au même moment? Pour voir ce qui peut poser problème, créez un fichier texte toto.txt, ouvrez le dans deux Bloc-Notes différents, écrivez quelque chose dans chaque fenêtre et sauvegardez : Seule la dernière sauvegarde sera prise en compte, la première sera perdue.

Catastrophe !

Cela peut être très problématique quand plusieurs scripts AutoIt sont en cours simultanément.
Voici un exemple : Je lance 10 scripts en même temps qui n'ont qu'une seule tache : lire une variable dans la base de registre et l'incrémenter 1000 fois. On s'attend donc que lorsque tous les processus ont fini leur travail, la clef dans la base de registre ait augmenté de 10 x 1000 = 10.000; logique, non?

Pour être sûr qu'ils se lancent en même temps, je lance tout d'abord un script de type "Père" qui lance lui même 10 scripts "Fils", qui attendent le signal du père pour faire leur travail :
► Afficher le texte10 processus en même temps
Et... Un message s'affiche disant que je n'ai pas 10.000 dans la variable, mais aux alentours de 8.000, ce qui veut dire que j'ai 20% des opérations qui se sont vautrées ! Comment cela se fait-il? Pourtant le code est bon...!
Cela est dû justement au tourniquet, qui met en pause un "fils" pour donner la main à un autre, c'est un peu aléatoire, c'est pour cela que tous les processus ne vont pas à la même vitesse. Et si cela se produit au mauvais moment, il peut se produire "un accès concurrent" à la variable. Exemple de situation :
► Afficher le texteSituation entre trois processeurs
Comment faire pour que cette situation ne se produise pas? Il faudrait pouvoir dire qu'il ne faut pas interrompre un processus entre la lecture d'une variable et l'écriture dans celle-ci. C'est ce qu'on appelle le principe d'atomicité (le fait qu'une opération ne doit pas être divisible). Il existe des garde-fous pour "encadrer" des lignes de codes, et dire aux autres processus qu'il faut attendre : Il s'agit des sémaphores.

Les sémaphores

Un sémaphore est un objet du noyau du système d'exploitation (ou kernel) qui met en attente un processus lorsque celui ci fait appel à lui et que certaines conditions ne sont pas remplies. Les sémaphores n'ont que trois opérations de base:
- Init : création du sémaphore avec un nombre de jetons.
- P : prise d'accès au sémaphore (Puis-je?)
- V : relâchement du sémaphore (Vas-y!)
Les sémaphores les plus simples à comprendre sont aussi ceux qui nous intéressent ici : les sémaphores Mutex (Exclusion mutuelle). Les mutex ont un nombre de jetons égal à 1 (cf Complément pour plus d'informations).

Le mutex est un sémaphore qui ne laisse la main qu'au premier qui demande avec la commande P (il passe en blocage), les suivants qui font un P sont mis en attente dans une file, et quand le premier le débloque (avec la commande V), il donne la main à celui qui est à la suite dans sa file d'attente, et ainsi de suite... Les processus sont des orateurs qui lèvent la main (P), la baisse quand ils ont fini leur discours (V), le mutex devient alors le micro pour parler.

Ainsi, l'exclusion mutuelle se met en place, empêchant deux processus d'accéder en même temps à une même variable. Reprenons l'exemple précédent des trois processus qui se disputent :
► Afficher le texteSituation entre trois processeurs AVEC mutex
Voici une situation où le mutex permet aux processus de ne pas écraser le travail des autres processus. En adaptant ce principe d'atomicité à notre script des 10 processus, on voit qu'il n'y a que de très légères modifications à effectuer :
- Créer un mutex => Func _Semaphore_MutexInit($nom) : $handle
- Avant de lire la clef de registre, demander l'accès au mutex => Func _Semaphore_P($handle) : void
- Après avoir écrit dans la clef de registre, redonner l'accès au mutex => Func _Semaphore_V($handle) : void

Voici ce que cela donne (le fichier Semaphore.au3 est en pièce jointe de ce message):
► Afficher le texte10 processus en même temps AVEC MUTEX
Et... Voila! 10 scripts comptant chacun jusque 1.000, et le résultat obtenu est bien de 10.000 !

Conclusion

Je me doute bien que ce souci n'arrive pas à tout le monde, mais ce genre de problème de partage se produit plus souvent qu'on ne le pense. J'espère ne pas en avoir trop fait à vouloir vulgariser ce phénomène ou ses implications/applications, et que vous aurez retenu quelque chose de ce pavé :)

Les sémaphores sont utiles pour faire fonctionner plusieurs scripts simultanément sur les même ressources, mais une mauvaise programmation peut entrainer des blocages. De plus, il n'existe pas que les mutex, et rien (au contraire !) n'empêche d'utiliser plusieurs sémaphores dans un même script/dans un même ensemble de scripts :) (rendez-vous de processus, pilotage et mise en pause, etc...) Mais cela fera partie d'un complément de ce tuto :)

Merci à tous, et à bientôt !

PJ: Mini-UDF de gestion des sémaphores (code source également disponible ci dessous) :
► Afficher le texteSemaphore.au3
NB: La fonction SemInit() permet de créer un sémaphore, où de récupérer son $handle si celui ci existe déjà.
PS: Pour plus d'informations sur les sémaphores : http://fr.wikipedia.org/wiki/Sémaphore_(informatique)
EDIT 23/05/2011 : Mise à jour du code pour correspondre aux UDFs avec documentation AutoIt.
Fichiers joints
Semaphore.au3
UDF de gestion des sémaphores
(6.34 Kio) Téléchargé 301 fois
Semaphore.au3
UDF de gestion des sémaphores
(6.34 Kio) Téléchargé 301 fois
Modifié en dernier par ZDS le lun. 23 mai 2011 16:18, modifié 4 fois.
ZDS : Chef de projet du nAiO (logiciel AutoIt gratuit sous licence CC 4.0 BY-NC-SA)
Tout problème a une solution, donc si il y a pas d'solution, c'est qu'il y a pas d'problème !

Avatar du membre
ZDS
Membre émérite
Membre émérite
Messages : 554
Enregistré le : jeu. 10 juin 2010 09:35
Localisation : 22300 Cul-d'chouette Langue-de-vache
Status : Hors ligne

Re: [Tuto] L'art de la sémaphorisation

#2

Message par ZDS » jeu. 19 mai 2011 14:12

[Complément de tutoriel en attente, ne pas effacer s'il vous plait]

Complément

Définition d'un sémaphore :

Me revoila à vous parler des sémaphores et de mutex, mais au fait, dans le cas le plus général, qu'est-ce-qu'un sémaphore exactement? Un sémaphore est un vigile d'entrée de boite de nuit, il connait à tout moment le nombre de personnes présentes à l'intérieur, il sait le nombre maximal de personnes que peut accueillir la boîte, il voit les personnes qui sortent de la boite (une place libre de plus), et il laisse entrer (une place de moins) ou met en attente les nouveaux arrivants. Avec cette analogie un mutex est un vigile d'entrée de photomaton, une seule place disponible à l'intérieur.

Un sémaphore est initialisé avec un compteur qui correspond aux places restantes (exemple 10), et une file d'attente vide.
  • Lorsqu'un processus P1 se présente au sémaphore en faisant une opération P (Puis-je?), deux cas se présentent :
    • Soit le compteur est supérieur à zéro : Le compteur est réduit de 1 et le sémaphore autorise P1 a continuer.
    • Soit le compteur est égal à zéro : Le sémaphore met P1 en pause et le place dans sa file d'attente.
  • Lorsqu'un processus P2 appelle le sémaphore avec une opération V (Vas-y!), le sémaphore se retrouve devant deux situations possibles :
    • Soit la file d'attente est vide : le compteur est augmenté de 1.
    • Soit la file d'attente n'est pas vide : le premier processus dans sa file est réveillé et reprend son traitement.
Il est donc très important qu'un processus qui a fait un P fasse un V par la suite (ou inversement) pour ne pas bloquer le système.

Il y a trois types de sémaphores : Les mutex (sémaphores avec un compteur initialisé à 1, utilisé pour les partages de ressources où un seul processus à la fois est autorisé), les bloquants (sémaphores avec un compteur initialisé à 0, utilisé dans les algorithmes pour la synchronisation entre processus), et les autres (sémaphores généraux dont le compteur représente le plus souvent le nombre d'instances autorisées en parallèle).

Exemples d'utilisation

Pour l'ensemble des exemples présentés, le père sert à lancer plusieurs exemplaires de ses fils, et contrôle le résultat obtenu.

1) Le partage de ressource :

Deux processus lisent une valeur chacun leur tour et se renvoient une balle (si valeur = "Ping", il renvoie "Pong" et inversement). Si il n'y a qu'un seul fils, il se renvoie lui même la balle.
► Afficher le texteExemple n°1 : Partage de ressource
Algorithme : créer un mutex M qui sera appelé à chaque fois que la ressource devra être travaillée (avec P(M) juste avant le travail, et avec V(M) juste après).

2) Le rendez-vous :

Deux processus font en boucle un travail d'une durée aléatoire, et doivent s'attendre pour recommencer (sleep(entre 1 et 5 secondes, puis attendre l'autre).
► Afficher le texteExemple n°2 : Rendez-vous (2 fils)
Algorithme : créer deux bloquants B1 et B2, et libérer l'un des sémaphores avant de demander l'accès à l'autre au moment du rendez vous (V(B1)...P(B2) pour le fils n°1, et V(B2)...P(B1) pour le fils n°2).

PS: Ceci est un exemple pour deux fils, il y a moyen de faire un rendez vous pour autant de fils que l'on souhaite. La méthode la plus simple est de créer autant de bloquants qu'il y a de processus (il y a N fils et N semaphores). Chaque fils X libère N-1 fois le sémaphore X et demande l'accès à tous les autres sémaphores (tous sauf le X).
► Afficher le texteExemple n°2b : Rendez-vous (10 fils)
3) Les limitations d'exécution :

Inconvénient
4) Les interblocages :

Dans l'exemple du rendez-vous, il est prévu de libérer un bloquant (avec V) avant de demander l'accès (avec P). Pourquoi? car l'utilisation des sémaphores peut entrainer des blocages où chacun des scripts attendrait (avec P) que l'autre libère un sémaphore (avec V). Une situation où chaque processus est en sommeil est appelé une situation d'interblocage.[En cours d'écriture]
Modifié en dernier par ZDS le mar. 24 mai 2011 15:59, modifié 3 fois.
ZDS : Chef de projet du nAiO (logiciel AutoIt gratuit sous licence CC 4.0 BY-NC-SA)
Tout problème a une solution, donc si il y a pas d'solution, c'est qu'il y a pas d'problème !

Avatar du membre
Yarillo
Niveau 5
Niveau 5
Messages : 109
Enregistré le : mer. 11 mai 2011 21:22
Status : Hors ligne

Re: [Tuto] L'art de la sémaphorisation

#3

Message par Yarillo » ven. 20 mai 2011 05:55

C'est vulgarisé à outrance, mais c'est pas désagréable non plus. Même en tant qu'aigri professionnel je peux comprendre que certains en aient besoin. :D

Avatar du membre
blacksoul305
Membre émérite
Membre émérite
Messages : 957
Enregistré le : ven. 18 mars 2011 11:49
Localisation : Au pays des programmeurs.
Status : Hors ligne

Re: [Tuto] L'art de la sémaphorisation

#4

Message par blacksoul305 » jeu. 03 mai 2012 17:46

Tutoriel complet et très intéressant, même si je pense ne pas les utiliser (du moins pas pour le moment).

Totalement HS, mais aujourd'hui j'ai pensé à toi et à ce tutoriel quand ma professeur d'Italien nous a appris que le feu tricolore pour organiser la circulation se disait : "Semaforo". Donc si les gens ne comprennent pas du premier coup, on peut imaginer un feu tricolore au milieu d'un carrefour, c'est lui qui s'occupe de laisser passer les voitures de chaque côté à un temps régulier !
Étudiant en 2ème année de Licence Informatique.

marlene99
Niveau 1
Niveau 1
Messages : 1
Enregistré le : mer. 05 mars 2014 09:27
Status : Hors ligne

Re: [Tuto] L'art de la sémaphorisation

#5

Message par marlene99 » mer. 05 mars 2014 16:31

Bonjour, merci pour ces explications claires qui m ont beaucoup aidé sur mon projet !
Modifié en dernier par Tlem le mer. 05 mars 2014 16:31, modifié 1 fois.
Raison : Suppression de la citation

Répondre