|
L'exactitude d'un programme concurrent est nettement plus complexe que celle d'un programme séquentiel en raison des dimensions supplémentaires de synchronisation, d'entrelacement et de ressources partagées. Un programme concurrent est considéré comme correct s'il satisfait à sa spécification *indépendamment de la planification de ses threads ou processus simultanés*. Cela signifie que le programme produit le résultat attendu et présente le comportement souhaité dans tous les entrelacements d'exécution possibles.
Plusieurs aspects contribuent à la définition de l’exactitude dans un programme concurrent :
* Sécurité : Le programme n'entre jamais dans un état invalide. Cela inclut d’éviter des problèmes tels que :
* Courses de données : Plusieurs threads accèdent et modifient le même emplacement de mémoire partagée sans synchronisation appropriée, conduisant à des résultats imprévisibles.
* Interblocages : Deux ou plusieurs threads sont bloqués indéfiniment, attendant que l'autre libère des ressources.
* Livelocks : Les threads changent continuellement d'état en réponse les uns aux autres, mais aucun ne progresse.
* Mamine : Un ou plusieurs threads se voient perpétuellement refuser l’accès à une ressource partagée.
* Conditions de course : Le résultat dépend de l’ordre imprévisible dans lequel les threads s’exécutent.
* Vivacité : Le programme finit par progresser et se termine s'il est censé le faire. Cela implique de s’assurer que :
* Les threads finissent par acquérir les ressources nécessaires.
* Le programme atteint finalement un état de fin.
* Fonctionnalité : Le programme produit le résultat correct et atteint son objectif. Ceci est similaire aux programmes séquentiels, mais compliqué par la nature simultanée de l'exécution. Le résultat final doit être cohérent dans tous les scénarios d’exécution possibles.
Par conséquent, prouver l’exactitude d’un programme concurrent implique généralement de démontrer que :
1. Tous les entrelacements possibles d'exécutions de threads conduisent à un état final valide. C’est incroyablement difficile et souvent peu pratique à réaliser de manière exhaustive.
2. Le programme est exempt de violations de sécurité (impasses, courses aux données, etc.). Ce problème est souvent résolu grâce à une conception soignée et à l'utilisation de mécanismes de synchronisation (mutex, sémaphores, moniteurs, etc.).
3. Le programme satisfait à ses propriétés de vivacité. Cela signifie démontrer que le programme finira par terminer ses tâches et ne restera pas coincé dans une boucle infinie ou une impasse.
En résumé, l'exactitude de la programmation simultanée signifie garantir un comportement prévisible et fiable sur tous les calendriers d'exécution possibles. Cela nécessite une attention méticuleuse à la synchronisation, à la gestion des ressources et à des techniques de test et de vérification rigoureuses. Des méthodes formelles peuvent être utilisées pour une vérification rigoureuse, mais elles sont souvent coûteuses en termes de calcul et ne s'appliquent qu'à des programmes plus petits. Par conséquent, une combinaison de conception minutieuse, de tests et éventuellement de vérification formelle est généralement nécessaire pour garantir l’exactitude d’un programme concurrent.
|
