[Tuto] L'art de la sémaphorisation
Posté : jeu. 19 mai 2011 15: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 :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 :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 :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):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) :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.
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
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
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
- 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
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
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.