Implémentez l’Algorithme de Peterson en Python pour la Synchronisation des Processus

Implémentez l'Algorithme de Peterson en Python pour la Synchronisation des Processus

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 tableau flag pour deux processus.
  • self.turn = 0 : Initialise la variable turn 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.

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.