Le problème de la section critique

Cette page décrit une approche du problème de la section critique utilisant les Thymios.

Specification du problème de la section critique:

Sur la page précédente, nous avons observé des exemples où deux thymios agissaient en même temps. Dans le premier exemple, les Thymios changent de couleurs indépendamment et n'interférent pas l’un avec l’autre . Cependant, dans le deuxième exemple, les deux Thymios veulent traverser une intersection et, en l’absence de synchronisation, se heurtent.

Le problème des deux Thymios voulant traverser l’intersection peut se généraliser sous la forme du problème de la section critique. Dans ce problème, plusieurs processus exécutent leurs propres instructions, mais ont parfois besoin exécuter des instructions appartenant à la section critique. Le programme général doit alors répondre aux contraintes suivantes :

  • Exclusion mutuelle: un seul et unique processus peut accéder à sa section critique à la fois.
  • Pas d'interblocage: au moins un des processus doit pouvoir accéder à la section critique. Dans l’exemple, cela se traduirait par le fait qu’il ne soit pas possible qu’aucun Thymio ne puisse traverser l’intersection.
  • Pas de famine: un processus spécifique voulant entrer sa section critique y accédera éventuellement. Dans notre exemple, si un Des Thymios veut passer l’intersection, il pourra éventuellement le faire.

Le projet présenté sur le reste de cette page décrit comment plusieurs Thymios essayent de partager une seule place de parking (la section critique) entre eux. Cet projet fait une démonstration de ce qui arrive quand aucune synchronisation n’est implémentée, puis montre deux solutions pour la réaliser.

Implémentation avec les Thymios:

Plusieurs Thymios roulent en rond sur une route. Parfois, ils ont besoin d’aller faires des courses et cherchent une place de parking. A l'état initial, le robot doit être placé sur la route en dehors de la place de parking. Les Thymios doivent respecter les contraintes de la section critique dans leurs déplacement :

  • Seulement un Thymio à la fois peut accéder à la place de parking (exclusion mutuelle)
  • Un Thymio cherchant une place de parking finira par en trouver une (pas d'interblocage ou de famine)

Partie 1: Aucune synchronisation.

Nous laissons tout d’abord les thymios chercher une place de parking sans les synchroniser.

Ci-dessus, la machine d’état implementé par le programme pour chaque Thymio:
fr_state_car.png

Road: Dans cet état, le robot se déplace sur la route. Le robot effectue le suivi de ligne ainsi qu’un évitement d’obstacle basique.
Action : Cet état correspond à la prise de décision lorsque le robot arrive au virage du parking. Le Thymio effectue soit le suivi de ligne, soit la traversée de ligne.
Parking : Cet état correspond au moment où le Thymio est dans la place de parking.
Le robot reste garé pendant un temps aléatoire.

Le schéma suivant montre la carte, le virage, ainsi que la place de parking.

map_noprim.jpg

Le comportement des Thymios dans le programme est montré dans la vidéo suivante :

Que se passe t’il?

La solution n’est pas correcte car les deux Thymios rentrent dans le parking en même temps en violant la contrainte d’exclusion mutuelle. Tous les Thymios peuvent rentrer dans la place de parking sans vérifier avant si un autre robot n’y est pas déjà. Nous avons besoin d’un mécanisme de synchronisation pouvant détecter si un Thymio et déjà dans le parking, et empêcher les autres d’y accéder.
Les parties suivantes font la démonstrations de deux mécanismes de synchronisation.

Pour aller plus loin:

As-tu déjà rencontrer le problème de la situation critique dans la vie courante? Dans quelle situation? Comment était-il résolu?

Partie 2: Synchronisation avec un spinlock.

Un spinlock (ou verrou tournant) est un mécanisme de synchronisation qui régule l'accès à la section critique. Lorsqu’un processus veut accéder à sa section critique, il doit d’abord demander la permission au spinlock. Si la demande est rejetée, le processus continue de tourner en rond, demandant constamment permission, jusqu’à ce qu’elle lui soit accorée. Ce comportement est appelé attente active car le processus est encore en train d’être exécuté, sans rien faire d’utile.

Nous utilisons un Thymio supplémentaire pour implémenter le spinlock. Quant il accorde la permission à un Thymio d’enter dans le parking, il passe au rouge, et tous les Thymios qui demandant la permission doivent « perdre leur temps » dans une boucle séparée. Quand le Thymio quitte la place de parking, il libère le spinlock (qui passe au vert) et un des Thymios en attente dans la boucle peut rentrer dans le parking.

Ci dessous, la machine d’états correspondant au Thymio spinlock:

fr_state_lock.png

Free: Cet état correspond aux actions effectuées lorsque la place de parking est libre. Le spinlock transmet FREE
Occupied : Cet état correspond aux actions effectuées lorsque la place de parking est occupée. Le spinlock transmet OCCUPIED

Le diagramme d’état pour le Thymio se déplaçant change aussi car il doit maintenant demander la permission au spinlock avant d’entrer dans la place de parking.

fr_state_carlock.png

Road: Dans cet état, le robot se déplace sur la route.
Le robot effectue le suivi de ligne ainsi qu’un évitement d’obstacle basique. Il transmet Mon identité + hors du parking.
Action : Cet état correspond à la prise de décision lorsque le robot arrive au virage du parking.
Le Thymio effectue soit le suivi de ligne, soit la traversée de ligne. Il transmet Mon identité + hors du parking.
Parking : Cet état correspond au moment où le Thymio est dans la place de parking.
Le robot reste garé pendant un temps aléatoire et transmet Mon identité + dans le parking
Enter : Dans cet état, le Thymio doit décider si il peut entrer dans le parking.
Le Thymio effectue soit le suivi de ligne, soit la traversée de ligne. Il transmet Mon identité + hors du parking.
Busywait : Le Thymio tourne indéfiniment dans la boucle.
Le robot effectue le suivi de ligne. Il transmet Mon identité + hors du parking.

L’image suivante complète la dernière en montrant la boucle d’attente.

map_lock.jpg

Le comportement des Thymios dans le programme est montré dans la vidéo suivante :

Que se passe-t’il?

Cette solution est correcte puisqu’elle garantie l’exclusion mutuelle : plusieurs Thymios n’accèderont jamais à la place de parking en même temps.

Pour aller plus loin:

Cette solution est correcte, mais est elle efficace ?

Considérons maintenant la situation montrée dans la vidéo suivante. Attention à l’ordre d’arrivée des Thymios dans la boucle.


Que c’est il passé? Quel est le problème avec ce comportement?

Le mécanisme suivant apporte une solution à ces deux problèmes.

Partie 3: Synchronisation avec une sémaphore binaire.

Une sémaphore binaire est un mécanisme de synchronisation avec une file d’attente : la queue. Cela résout le problème du dépassement et permet de ne pas avoir de famine. Une sémaphore binaire bloque les processus dans la queue, ce qui résout aussi le problème de l’attente active.

Pour implémenter cette sémaphore, nous remplaçons le Thymio spinlock par un Thymio sémaphore. La sémaphore contient un tableau tab_queue dans lequel elle stocke les identités des Thymios présents dans la file d’attente, ainsi qu’une variable id_in pour l’identité du Thymio actuellement dans le parking. La sémaphore peut ajouter des Thymio dans la queue à la fois quand la place de parking et libre, ou occupée.

fr_state_sema.png

Free: Cet état correspond aux actions effectuées lorsque la place de parking est libre. La sémaphore transmet Identité du premier Thymio de la queue + FREE et gère tab_queue.
Occupied : Cet état correspond aux actions effectuées lorsque la place de parking est occupée. La sémaphore transmet Identité du premier Thymio de la queue + OCCUPIED et gère tab_queue.

Ci-dessous, le diagramme d’état du Thymio modifié pour la sémaphore :

fr_state_carsema.png

Road: Dans cet état, le robot se déplace sur la route.
Le robot effectue le suivi de ligne ainsi qu’un évitement d’obstacle basique. Il transmet Mon identité + hors du parking.
Action : Cet état correspond à la prise de décision lorsque le robot arrive au virage vers le parking.
Le Thymio effectue soit le suivi de ligne, soit la traversée de ligne. Il transmet Mon identité + hors du parking.
Parking : Cet état correspond au moment où le Thymio est dans la place de parking.
Le robot reste garé pendant un temps aléatoire et transmet Mon identité + dans le parking
Queue:Cet état correspond à l’attente dans la queue.
Le robot attend d’arriver en tête de file. Il transmet Mon identité + dans la queue

Le diagramme suivant complète le précédent pour montrer la queue:

map_sema.jpg

Le comportement des Thymios dans le programme est montré dans la vidéo suivante :

Que se passe t’il?

Ce programme est une solution correcte au problème de la section critique. Les Thymios attendent dans la queue pour le parking sans perdre d’énergie et le premier arrivé est le premier servi.

Pour aller plus loin:

Que se passe t’il si nous ajoutons plus de Thymios?

Que se passe t’il si un Thymio oublie de dire qu’il quitte le parking ?

Comment implémenter une solution pour deux places de parking?

Conclusion

Nous avons démontré comment résoudre le problème de la section critique, qui est le problème le plus fondamental en programmation concurrente. Deux méthodes de synchronisations ont été utilisées : le spinlock qui est sujet à l’attente active et au dépassement, et la sémaphore binaire qui utilise une file d’attente pour les éviter.

A faire soi-même

  • Pour imprimer les routes que suivent les Thymios, imprimez les fichiers PDF des segments de route contenus dans cette archive.
  • Le code source est disponible cette archive.
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License