En informatique, les modèles de cohérence - en anglais : consistency models - sont utilisés dans les systèmes répartis comme les systèmes de mémoire partagée distribuée (DSM) ou les magasins de données distribuées (tels que les système de fichiers, les bases de données, les systèmes de réplication optimiste ou la mise en cache web). On dit que le système supporte un modèle donné si les opérations sur la mémoire suivent des règles spécifiques. Le modèle de cohérence des données spécifie un contrat entre le programmeur et le système, dans lequel le système garantit que si le programmeur suit les règles, la mémoire sera cohérente et les résultats de la lecture, de l'écriture ou de la mise à jour de la mémoire seront prévisibles. Ceci est différent de la cohérence (en anglais : coherence), qui se produit dans les systèmes avec ou sans cache, et qui est la cohérence des données (en anglais : consistency of data) par rapport à tous les processeurs. La cohérence consiste à maintenir un ordre global dans lequel les écritures dans un emplacement unique ou une variable unique sont vues par tous les processeurs. La cohérence concerne l'ordre des opérations sur plusieurs emplacements par rapport à tous les processeurs.
Les langages de programmation de haut niveau, tels que C++ et Java, maintiennent partiellement le contrat en traduisant les opérations de mémoire en opérations de bas niveau de manière à préserver la sémantique de la mémoire. Pour respecter le contrat, les compilateurs peuvent réorganiser certaines instructions de mémoire, et les appels de bibliothèque tels que pthread_mutex_lock() encapsulent la synchronisation requise.
La vérification de la cohérence séquentielle par vérification de modèles est indécidable en général, même pour les protocoles de cohérence de cache à état fini.
Les modèles de cohérence définissent des règles pour l'ordre apparent et la visibilité des mises à jour, et se situent sur un continuum avec des compromis.
Exemple Supposons que le cas suivant se produise :
La ligne X est répliquée sur les nœuds M et N Le client A écrit la ligne X au nœud M Après une période de temps t, le client B lit la ligne X du nœud N
Le modèle de cohérence doit déterminer si le client B voit l'écriture effectuée par le client A ou non.
Types Il existe deux méthodes pour définir et classer les modèles de cohérence : l'émission et la vue.
Émission : La méthode d'émission décrit les restrictions qui définissent comment un processus peut émettre des opérations. Vue La méthode de vue définit l'ordre des opérations visibles par les processus.
Par exemple, un modèle de cohérence peut définir qu'un processus n'est pas autorisé à émettre une opération tant que toutes les opérations émises précédemment ne sont pas terminées. Les différents modèles de cohérence appliquent des conditions différentes. Un modèle de cohérence peut être considéré comme plus fort qu'un autre s'il exige toutes les conditions de ce modèle et plus encore. En d'autres termes, un modèle comportant moins de contraintes est considéré comme un modèle de cohérence plus faible.
Ces modèles définissent la manière dont le matériel doit être disposé et, à un haut niveau, la manière dont le programmeur doit coder. Le modèle choisi affecte également la manière dont le compilateur peut réordonner les instructions. En général, si les dépendances de contrôle entre les instructions et si les écritures au même emplacement sont ordonnées, alors le compilateur peut réordonner selon les besoins. Cependant, avec les modèles décrits ci-dessous, certains peuvent permettre de réordonner les écritures avant les chargements, d'autres non.
Cohérence stricte La cohérence stricte est le modèle de cohérence le plus fort. Dans ce modèle, l'écriture d'une variable par n'importe quel processeur doit être vue instantanément par tous les processeurs.
Le diagramme de modèle strict et les diagrammes de modèle non strict décrivent la contrainte de temps - instantanée. Cela peut être mieux compris comme si une horloge globale était présente, dans laquelle chaque écriture doit être reflétée dans tous les caches du processeur avant la fin de cette période d'horloge. L'opération suivante ne doit se produire que dans la période d'horloge suivante. +SéquenceModèle strictModèle non-strictP1P2P1P21W(x)1W(x)12R(x)1R(x)03R(x)1 Il s'agit du modèle le plus rigide. Dans ce modèle, le résultat attendu par le programmeur sera reçu à chaque fois. Il est déterministe. Sa pertinence pratique est limitée à une expérience de pensée et à un formalisme, car l'échange instantané de messages est impossible. Il ne permet pas de répondre à la question de la résolution des conflits en cas d'écritures concurrentes sur le même élément de données, car il suppose que les écritures concurrentes sont impossibles.
Cohérence séquentielle Le modèle de cohérence séquentielle a été proposé par Lamport (1979). Il s'agit d'un modèle de mémoire plus faible que le modèle de cohérence stricte. L'écriture d'une variable ne doit pas nécessairement être vue instantanément, mais les écritures de variables par différents processeurs doivent être vues dans le même ordre par tous les processeurs. Comme défini par Lamport (1979), la cohérence séquentielle est satisfaite si "le résultat de toute exécution est le même que si les opérations de tous les processeurs étaient exécutées dans un certain ordre séquentiel, et que les opérations de chaque processeur individuel apparaissent dans cette séquence dans l'ordre spécifié par son programme."
L'ordre du programme au sein de chaque processeur et l'ordre séquentiel des opérations entre les processeurs doivent être maintenus. Afin de préserver l'ordre séquentiel d'exécution entre les processeurs, toutes les opérations doivent sembler s'exécuter instantanément ou atomiquement par rapport à chaque autre processeur. Ces opérations doivent seulement "sembler" s'exécuter car il est physiquement impossible d'envoyer des informations instantanément. Par exemple, dans un système utilisant un seul bus partagé globalement, une fois qu'une ligne de bus reçoit une information, il est garanti que tous les processeurs verront cette information au même moment. Ainsi, le passage de l'information sur la ligne de bus achève l'exécution par rapport à tous les processeurs et semble avoir été exécuté. Les architectures sans cache ou les architectures avec cache dont les réseaux d'interconnexion ne sont pas instantanés peuvent contenir un chemin lent entre les processeurs et les mémoires. Ces chemins lents peuvent entraîner une incohérence séquentielle, car certaines mémoires reçoivent les données diffusées plus rapidement que d'autres.
La cohérence séquentielle peut produire des résultats non déterministes. En effet, la séquence des opérations séquentielles entre les processeurs peut être différente au cours des différentes exécutions du programme. Toutes les opérations de mémoire doivent se produire dans l'ordre du programme.
La linéarisabilité (également connue sous le nom de cohérence atomique) peut être définie comme la cohérence séquentielle avec la contrainte de temps réel.
Cohérence causale La cohérence causale est un modèle d'affaiblissement de la cohérence séquentielle qui consiste à classer les événements en deux catégories : ceux qui sont liés par la causalité et ceux qui ne le sont pas.
Ce modèle relâche la cohérence séquentielle sur les écritures concurrentes d'un processeur et sur les écritures qui ne sont pas causalement liées. Deux écritures peuvent devenir causalement liées si une écriture sur une variable dépend d'une écriture précédente sur une variable quelconque et si le processeur qui effectue la seconde écriture vient de lire la première. Les deux écritures peuvent avoir été effectuées par le même processeur ou par des processeurs différents.
Comme dans la cohérence séquentielle, les lectures n'ont pas besoin de refléter les changements instantanément, mais elles doivent refléter tous les changements apportés à une variable de manière séquentielle. Séquence121W1(x)32W2(x)53R1(x)3 W1 n'est pas causalement lié à W2. R1 serait séquentiellement incohérent mais est causalement cohérent. Sequence12341W(x)1R(x)1R(x)1R(x)12W(x)23W(x)3R(x)3R(x)24R(x)2R(x)3 W(x)1 et W(x)2 sont liés par un lien de causalité en raison de la lecture effectuée par P2 sur x avant W(x)2.
Cohérence du processeur Afin de maintenir la cohérence des données et d'obtenir des systèmes de processeurs évolutifs où chaque processeur dispose de sa propre mémoire, le modèle de cohérence des processeurs a été élaboré. Tous les processeurs doivent être cohérents dans l'ordre dans lequel ils voient les écritures effectuées par un processeur et dans la façon dont ils voient les écritures effectuées par différents processeurs au même endroit (la cohérence est maintenue). Cependant, ils n'ont pas besoin d'être cohérents lorsque les écritures sont effectuées par différents processeurs à des emplacements différents.
Chaque opération d'écriture peut être divisée en plusieurs sous-écritures dans toutes les mémoires. La lecture d'une de ces mémoires peut avoir lieu avant que l'écriture dans cette mémoire ne soit terminée. Par conséquent, les données lues peuvent être périmées. Ainsi, un processeur sous PC peut exécuter un chargement plus récent lorsqu'un stockage plus ancien doit être bloqué. L'ordre de lecture avant écriture, lecture après lecture et écriture avant écriture est toujours préservé dans ce modèle.
Le modèle de cohérence du processeur est similaire au modèle de cohérence PRAM avec une condition plus forte qui définit que toutes les écritures sur le même emplacement mémoire doivent être vues dans le même ordre séquentiel par tous les autres processus. La cohérence du processeur est plus faible que la cohérence séquentielle mais plus forte que le modèle de cohérence PRAM.
Le système multiprocesseur DASH de Stanford met en œuvre une variante de la cohérence des processeurs qui est incomparable (ni plus faible ni plus forte) avec les définitions de Goodman.. Tous les processeurs doivent être cohérents dans l'ordre dans lequel ils voient les écritures d'un processeur et dans la façon dont ils voient les écritures de différents processeurs au même emplacement. Cependant, ils n'ont pas besoin d'être cohérents lorsque les écritures sont effectuées par différents processeurs à différents emplacements.
Cohérence de la RAM en pipeline, ou cohérence FIFO La cohérence de la RAM pipelinée (cohérence PRAM) a été présentée par Lipton et Sandberg en 1988 comme l'un des premiers modèles de cohérence décrits. En raison de sa définition informelle, il existe en fait au moins deux implémentations subtilement différentes, l'une par Ahamad et al. et l'autre par Mosberger.
Dans la cohérence PRAM, tous les processus voient les opérations d'un seul processus dans le même ordre qu'elles ont été émises par ce processus, tandis que les opérations émises par des processus différents peuvent être vues dans un ordre différent par des processus différents. La cohérence PRAM est plus faible que la cohérence du processeur. La PRAM relâche le besoin de maintenir la cohérence d'un emplacement à travers tous ses processeurs. Ici, les lectures de n'importe quelle variable peuvent être exécutées avant les écritures dans un processeur. L'ordre de lecture avant écriture, lecture après lecture et écriture avant écriture est toujours préservé dans ce modèle. Séquence12341W(x)12R(x)13W(x)24R(x)1R(x)25R(x)2R(x)1
Cohérence du cache La cohérence du cache exige que toutes les opérations d'écriture sur un même emplacement mémoire soient effectuées dans un certain ordre séquentiel. La cohérence du cache est plus faible que la cohérence du processeur et incomparable avec la cohérence de la PRAM.
Cohérence lente vignette|Mémoire lente