Implémentez l’Algorithme de Peterson en Python pour la Synchronisation des Processus
Introduction
Dans le domaine de la programmation concurrente, la synchronisation des processus est essentielle pour éviter les comportements indésirables comme les conditions de course, où deux processus simultanés manipulent des données partagées de manière non coordonnée. La synchronisation assure que plusieurs processus ou threads s’exécutant en parallèle ne produisent pas d’effets indésirables lorsqu’ils accèdent à des ressources partagées.
L’algorithme de Peterson est une solution software classique pour la synchronisation entre deux processus. Développé par Gary L. Peterson en 1981, cet algorithme est utilisé pour garantir l’exclusion mutuelle en permettant à deux processus d’alterner leur accès à une section critique.
Comprendre l’Algorithme de Peterson
Contexte de l’algorithme
L’algorithme de Peterson s’applique aux environnements où l’on doit gérer la concurrence entre deux processus accédant à des ressources partagées. Ce qui rend cet algorithme particulièrement utile, c’est sa capacité à assurer l’exclusion mutuelle avec seulement deux variables: un tableau de drapeaux indiquant l’intention d’accéder à la section critique, et une variable indiquant le tour du processus.
Mécanisme de l’algorithme
L’algorithme utilise deux variables principales :
– flag
: un tableau où chaque élément indique si un processus veut entrer dans la section critique.
– turn
: une variable qui indique quel processus a la priorité pour entrer dans la section critique.
Les trois conditions que l’algorithme de Peterson vise à garantir sont :
– Exclusion mutuelle : un seul processus à la fois peut être dans la section critique.
– Progrès : des processus en dehors de la section critique ne peuvent pas empêcher un autre d’entrer dans la section critique.
– Attente bornée : chaque processus finit par avoir accès à la section critique dans un délai raisonnable.
Implémentation de l’Algorithme de Peterson en Python
Pré-requis et préparation de l’environnement
Assurez-vous d’avoir une installation de Python configurée sur votre système. Installez le module threading
, qui fait partie de la bibliothèque standard de Python et nous aidera à simuler un environnement multitâches.
Code de base de l’algorithme
Voici comment on peut implémenter l’algorithme de Peterson en Python :
import threading class PetersonLock: def __init__(self): self.flag = [False, False] self.turn = 0 def lock(self, process_id): other = 1 - process_id self.flag[process_id] = True self.turn = other while self.flag[other] and self.turn == other: pass # Attente active def unlock(self, process_id): self.flag[process_id] = False
Explication ligne par ligne
self.flag = [False, False]
: Initialise le tableauflag
pour deux processus.self.turn = 0
: Initialise la variableturn
au processus 0.lock(self, process_id)
: Indique l’intention d’un processus d’entrer en section critique et définit le tour à l’autre processus.unlock(self, process_id)
: Libère la section critique pour le processus en mettant à jour le drapeau.
Exécution et Évaluation de l’Implémentation
Création de processus en Python
Pour démontrer l’efficacité de l’algorithme, créons deux threads simuler deux processus :
def critical_section(process_id, lock): for _ in range(5): lock.lock(process_id) print(f"Processus {process_id} est dans la section critique") lock.unlock(process_id) lock = PetersonLock() thread_0 = threading.Thread(target=critical_section, args=(0, lock)) thread_1 = threading.Thread(target=critical_section, args=(1, lock)) thread_0.start() thread_1.start() thread_0.join() thread_1.join()
Test de l’algorithme
Testez ces threads pour vérifier que l’exclusion mutuelle est respectée. Les tests doivent vérifier que jamais les deux processus ne se trouvent dans la section critique simultanément.
Démonstration avec des résultats de tests
L’exécution de ce code doit montrer que les sorties des threads sont séquentielles par rapport à la section critique, illustrant le fonctionnement correct de l’algorithme de Peterson.
Applications Pratiques et Limites
Cas d’utilisation réels
L’algorithme de Peterson est idéal pour les systèmes embarqués où les ressources sont limitées, et où un verrou hardware peut être trop coûteux ou impossible à implémenter.
Limites de l’algorithme
Cependant, cet algorithme est limité à deux processus. Pour plus de deux processus, des méthodes plus sophistiquées comme les sémaphores ou les moniteurs sont nécessaires. Comparé à d’autres solutions, l’algorithme de Peterson peut également souffrir de l’attente active.
Conclusion
Récapitulatif des points abordés
L’algorithme de Peterson est un outil puissant dans l’arsenal des techniques de synchronisation, offrant certaines garanties avec une implémentation simple et efficace. Cependant, ses limitations doivent être prises en compte dans des systèmes plus complexes.
Réflexion finale
Pour la programmation concurrente, comprendre et appliquer des techniques appropriées comme l’algorithme de Peterson reste crucial pour assurer la précision et la robustesse de l’exécution du programme.
Appendice
Références supplémentaires
- » Operating Systems: Design and Implementation » par Andrew S. Tanenbaum
- Wikipédia sur l’algorithme de Peterson
Code source complet en annexe
Voici le code complet implémentant l’algorithme de Peterson en Python, utilisable pour des tests et des démonstrations supplémentaires.
Glossaire
- Condition de course : Un défaut dans un programme où le résultat dépend de l’ordre ou du moment d’exécution des threads ou des processus.
- Exclusion mutuelle : Garantie qu’une seule section critique s’exécute à un moment donné pour un ensemble de threads.
- Attente active : Technique où un processus vérifie continuellement l’accessibilité d’une ressource, consommant du CPU.