Modèle de cohérence

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.

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.

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)[4], 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.

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.

W1 n'est pas causalement lié à W2. R1 serait séquentiellement incohérent mais est causalement cohérent.[5]

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[5].

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é[5]. 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[6] 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[7] 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.

La cohérence de la RAM pipelinée (cohérence PRAM) a été présentée par Lipton et Sandberg en 1988[8] 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[7], 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.

La cohérence du cache[6] - [9] 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.

Mémoire lente

En cohérence lente[9], si un processus lit une valeur précédemment écrite dans un emplacement mémoire, il ne peut pas lire ultérieurement une valeur antérieure de cet emplacement. Les écritures effectuées par un processus sont immédiatement visibles pour ce processus. La cohérence lente est un modèle plus faible que la cohérence de la PRAM et du cache.

Exemple :

Le diagramme de la mémoire lente décrit un exemple de cohérence lente. Le premier processus écrit 1 à l'emplacement mémoire X puis écrit 1 à l'emplacement mémoire Y. Le second processus lit 1 à partir de Y puis lit 0 à partir de X même si X a été écrit avant Y.

Hutto, Phillip W., et Mustaque Ahamad (1990)[10] illustrent qu'avec une programmation appropriée, la mémoire lente (cohérence) peut être expressive et efficace. Ils mentionnent que la mémoire lente possède deux propriétés précieuses : la localité et le support de la réduction de la mémoire atomique. Ils proposent deux algorithmes pour présenter l'expressivité de la mémoire lente.

Les modèles suivants nécessitent une synchronisation spécifique par les programmeurs.

L'ordre et l'atomicité du programme sont maintenus uniquement sur un groupe d'opérations et non sur toutes les lectures et écritures. Cela découle de la compréhension du fait que certaines opérations de mémoire - telles que celles effectuées dans une section critique - ne doivent pas être vues par tous les processeurs - jusqu'à ce que toutes les opérations de la section critique soient terminées, par exemple. Il exploite également le fait que les programmes écrits pour être exécutés sur un système multiprocesseur contiennent la synchronisation nécessaire pour s'assurer que les courses de données ne se produisent pas et que les résultats SC sont toujours produits. Ainsi, dans l'ordonnancement faible, les opérations autres que les opérations de synchronisation peuvent être classées comme des opérations de données[11].

X = 1;
''barrière''
xready = 1;

''barrière''
while (!xready) {}; 
''barrière''
y = 2;

Les opérations de synchronisation signalent au processeur qu'il doit s'assurer qu'il a terminé et vu toutes les opérations précédentes effectuées par tous les processeurs. Afin de maintenir un ordre faible, les opérations d'écriture précédant une opération de synchronisation doivent être globalement effectuées avant l'opération de synchronisation. Les opérations présentes après une opération de synchronisation doivent également être effectuées uniquement après la fin de l'opération de synchronisation. Par conséquent, l'accès aux variables de synchronisation est séquentiellement cohérent et toute lecture ou écriture ne doit être effectuée qu'après la fin des opérations de synchronisation précédentes. La cohérence n'est pas relâchée dans ce modèle. Une fois ces exigences satisfaites, toutes les autres opérations de "données" peuvent être réorganisées.

Il y a une forte dépendance à la synchronisation explicite dans le programme. Pour les modèles d'ordonnancement faibles, le programmeur doit utiliser des instructions de verrouillage atomique telles que test-and-set, fetch-and-op, store conditional, load linked ou doit étiqueter des variables de synchronisation ou utiliser des barrières.

Le modèle de cohérence de libération relaxe le modèle de cohérence faible en distinguant l'opération de synchronisation d'entrée de l'opération de synchronisation de sortie. Dans le modèle de cohérence faible, lorsqu'une opération de synchronisation doit être vue, toutes les opérations de tous les processeurs doivent être visibles avant que l'opération de synchronisation ne soit effectuée et que le processeur ne procède. Cependant, dans le cadre du modèle de cohérence de libération, lors de l'entrée dans une section critique, appelée "acquisition", toutes les opérations relatives aux variables de la mémoire locale doivent être terminées. Lors de la sortie, appelée "release", toutes les modifications effectuées par le processeur local doivent être propagées à tous les autres processeurs. La cohérence est toujours maintenue.

L'opération d'acquisition est un chargement/lecture qui est effectué pour accéder à la section critique. Une opération de libération est un stockage/écriture effectué pour permettre aux autres processeurs d'utiliser les variables partagées.

Parmi les variables de synchronisation, il est possible de maintenir la cohérence séquentielle ou la cohérence du processeur. Avec SC, toutes les variables de synchronisation concurrentes doivent être traitées dans l'ordre. En revanche, avec PC, une paire de variables concurrentes ne doit suivre que cet ordre. On peut permettre à des acquisitions plus jeunes de se produire avant des versions plus anciennes[12].

Il s'agit d'une variante du modèle de cohérence de libération. Il nécessite également l'utilisation d'instructions d'acquisition et de libération pour indiquer explicitement une entrée ou une sortie dans une section critique. Toutefois, dans le cadre de la cohérence de saisie, chaque variable partagée se voit attribuer une variable de synchronisation qui lui est propre. De cette façon, ce n'est que lorsque l'acquisition concerne la variable x que toutes les opérations liées à x doivent être achevées par rapport à ce processeur. Cela permet d'effectuer des opérations concurrentes sur différentes sections critiques de différentes variables partagées. La simultanéité ne peut pas être vue pour les opérations critiques sur la même variable partagée. Un tel modèle de cohérence sera utile lorsque différents éléments de la matrice peuvent être traités en même temps.

Dans le cadre de la cohérence générale[13], toutes les copies d'un emplacement mémoire sont finalement identiques une fois que les écritures de tous les processus sont terminées.

En cohérence locale[9], chaque processus effectue ses propres opérations dans l'ordre défini par son programme. Il n'y a aucune contrainte sur l'ordre dans lequel les opérations d'écriture des autres processus semblent être effectuées. La cohérence locale est le modèle de cohérence le plus faible dans les systèmes de mémoire partagée.

Voici d'autres modèles de cohérence :

• Cohérence causale+[14] - [15]
• Cohérence delta
• Cohérence éventuelle
• Cohérence de la fourche
• Sérialisation en une seule copie
• Sérialisation
• Cohérence des champs vectoriels
• Cohérence faible
• Cohérence forte

Plusieurs autres modèles de cohérence ont été conçus pour exprimer des restrictions concernant l'ordre ou la visibilité des opérations, ou pour traiter des hypothèses de défaillance spécifiques[16].

Les modèles suivants sont quelques modèles de cohérence relaxée :

Une approche permettant d'améliorer les performances au niveau matériel consiste à relâcher l'OP d'une écriture suivie d'une lecture, ce qui permet de masquer efficacement la latence des opérations d'écriture. L'optimisation sur laquelle repose ce type de relaxation est qu'elle permet aux lectures suivantes d'être dans un ordre détendu par rapport aux écritures précédentes du processeur. À cause de cette relaxation, certains programmes peuvent ne pas donner de résultats SC. D'autres en revanche devraient toujours donner des résultats cohérents en raison de l'application des autres contraintes d'ordre du programme.

Trois modèles entrent dans cette catégorie. Le modèle IBM 370 est le modèle le plus strict. Une lecture peut être terminée avant une écriture antérieure à une adresse différente, mais il lui est interdit de retourner la valeur de l'écriture à moins que tous les processeurs aient vu l'écriture. Le modèle SPARC V8 total store ordering (TSO) assouplit partiellement le modèle IBM 370, il permet à une lecture de renvoyer la valeur de l'écriture de son propre processeur par rapport aux autres écritures au même emplacement, c'est-à-dire qu'elle renvoie la valeur de sa propre écriture avant que les autres ne la voient. Comme le modèle précédent, il ne peut pas renvoyer la valeur de l'écriture si tous les processeurs n'ont pas vu l'écriture. Le modèle de cohérence du processeur (PC) est le plus détendu des trois modèles et relâche les deux contraintes de telle sorte qu'une lecture peut se terminer avant une écriture antérieure, même avant que celle-ci ne soit rendue visible par les autres processeurs.

Dans l'exemple A, le résultat n'est possible que dans l'IBM 370 parce que la lecture (A) n'est pas émise avant que l'écriture (A) dans ce processeur soit terminée. Par contre, ce résultat est possible dans TSO et PC car ils permettent la lecture des drapeaux avant l'écriture des drapeaux dans un seul processeur.

Dans l'exemple B, le résultat n'est possible qu'avec le PC car il permet à P2 de renvoyer la valeur d'une écriture avant même qu'elle ne soit visible par P3. Cela ne sera pas possible dans les deux autres modèles.

Pour assurer la cohérence séquentielle dans les modèles ci-dessus, des filets de sécurité ou des barrières sont utilisés pour faire respecter manuellement la contrainte. Le modèle IBM370 comporte certaines instructions de sérialisation spécialisées qui sont placées manuellement entre les opérations. Ces instructions peuvent être des instructions mémoire ou des instructions non mémoire telles que des branches. D'autre part, les modèles TSO et PC ne fournissent pas de filets de sécurité, mais les programmeurs peuvent toujours utiliser des opérations de lecture-modification-écriture pour faire croire que l'ordre du programme est toujours maintenu entre une écriture et une lecture suivante. Dans le cas de TSO, le PO semble être maintenu si le R ou le W qui fait déjà partie d'un R-modify-W est remplacé par un R-modify-W, ce qui nécessite que le W dans le R-modify-W soit un 'factice' qui renvoie la valeur lue. De même, pour PC, PO semble être maintenu si la lecture est remplacée par une écriture ou fait déjà partie de R-modifié-W.

Cependant, les optimisations du compilateur ne peuvent pas être effectuées après avoir exercé cette seule relaxation. Les optimisations du compilateur requièrent la flexibilité totale de pouvoir réordonner n'importe quelles des deux opérations dans l'OP, donc la possibilité de réordonner une écriture par rapport à une lecture n'est pas suffisamment utile dans ce cas.

Certains modèles relaxent encore plus l'ordre du programme en relaxant même les contraintes d'ordre entre les écritures à différents emplacements. Le modèle PSO (partial store ordering) de SPARC V8 est le seul exemple d'un tel modèle. La capacité de canaliser et de chevaucher les écritures à différents emplacements à partir du même processeur est la principale optimisation matérielle permise par PSO. PSO est similaire à TSO en termes d'exigences d'atomicité, en ce sens qu'il permet à un processeur de lire la valeur de sa propre écriture et empêche les autres processeurs de lire l'écriture d'un autre processeur avant que l'écriture ne soit visible par tous les autres processeurs. L'ordre du programme entre deux écritures est maintenu par PSO en utilisant une instruction STBAR explicite. L'instruction STBAR est insérée dans un tampon d'écriture dans les implémentations avec des tampons d'écriture FIFO. Un compteur est utilisé pour déterminer quand toutes les écritures avant l'instruction STBAR ont été effectuées, ce qui déclenche une écriture dans le système de mémoire pour incrémenter le compteur. Un accusé de réception d'écriture décrémente le compteur, et lorsque le compteur devient 0, cela signifie que toutes les écritures précédentes sont terminées.

Dans les exemples A et B, PSO permet ces deux résultats non séquentiellement cohérents. Le filet de sécurité que fournit PSO est similaire à celui de TSO, il impose l'ordre du programme d'une écriture vers une lecture et fait respecter l'atomicité de l'écriture.

Comme pour les modèles précédents, les relaxations permises par PSO ne sont pas suffisamment flexibles pour être utiles à l'optimisation des compilateurs, qui nécessite une optimisation beaucoup plus souple.

Dans certains modèles, toutes les opérations sur des emplacements différents sont relaxées. Une lecture ou une écriture peut être réordonnée par rapport à une autre lecture ou écriture dans un autre emplacement. L'ordonnancement faible peut être classé dans cette catégorie et deux types de modèles de cohérence de libération (RCsc et RCpc) relèvent également de ce modèle. Trois architectures commerciales sont également proposées dans cette catégorie de relaxation : les modèles Digital Alpha, SPARC V9 relaxed memory order (RMO) et IBM PowerPC. Tous ces modèles permettent de réordonner les lectures au même emplacement, sauf le Digital Alpha. Ces modèles violent l'ordre séquentiel dans les exemples A et B. Une relaxation supplémentaire autorisée dans ces modèles, absente des modèles précédents, est que les opérations de mémoire suivant une opération de lecture peuvent être superposées et réordonnées par rapport à la lecture. Tous ces modèles, à l'exception du RCpc et du PowerPC, permettent à une lecture de retourner la valeur de l'écriture précoce d'un autre processeur. Du point de vue du programmeur, tous ces modèles doivent maintenir l'illusion de l'atomicité de l'écriture même s'ils permettent au processeur de lire sa propre écriture en avance.

Ces modèles peuvent être classés en deux catégories en fonction du type de filet de sécurité fourni. On voit ici la nécessité de programmes soigneusement écrits. La nature de la synchronisation aide à catégoriser les modèles d'ordre faible, RCsc et RCpc. Les modèles Alpha, RMO et PowerPC fournissent des instructions de clôture afin que l'ordre du programme puisse être imposé entre différentes opérations de mémoire.

Un exemple de modèle qui relâche la plupart des contraintes ci-dessus (à l'exception de la lecture anticipée de l'écriture d'autrui) est l'ordonnancement faible. Il classe les opérations de mémoire en deux catégories : les opérations de données et les opérations de synchronisation. Pour faire respecter l'ordre du programme, un programmeur doit trouver au moins une opération de synchronisation dans un programme. L'hypothèse selon laquelle cela fonctionne est que la réorganisation des opérations de mémoire dans les régions de données entre les opérations de synchronisation n'affecte pas le résultat du programme. Elles agissent simplement comme un filet de sécurité pour faire respecter l'ordre du programme. La façon dont cela fonctionne est qu'un compteur suit le nombre d'opérations de données et tant que ce compteur ne devient pas nul, l'opération de synchronisation n'est pas émise. De plus, aucune autre opération de données n'est émise tant que toutes les synchronisations précédentes ne sont pas terminées. Les opérations de mémoire entre deux variables de synchronisation peuvent être superposées et réordonnées sans affecter la correction du programme. Ce modèle garantit que l'atomicité de l'écriture est toujours maintenue, par conséquent, aucun filet de sécurité supplémentaire n'est nécessaire pour l'ordonnancement faible.

Il existe deux types de cohérence de validation, la cohérence de validation avec la cohérence séquentielle (RCsc) et la cohérence de validation avec la cohérence du processeur (RCpc). Ce dernier type indique quel type de cohérence est appliqué aux opérations désignées ci-dessous comme spéciales.

Il existe des opérations mémoire spéciales (cf. ordinaires), elles-mêmes composées de deux classes d'opérations : les opérations sync ou nsync. Ces dernières sont des opérations qui ne sont pas utilisées pour la synchronisation ; les premières le sont, et consistent en des opérations d'acquisition et de libération. Une acquisition est effectivement une opération de lecture de la mémoire utilisée pour obtenir l'accès à un certain ensemble d'emplacements partagés. La libération, quant à elle, est une opération d'écriture effectuée pour accorder la permission d'accéder aux emplacements partagés.

Pour la cohérence séquentielle (RCsc), les contraintes sont :

• acquérir → tous,
• tous → validation,
• spécial → spécial.

Pour la cohérence du processeur (RCpc), l'ordre des programmes d'écriture et de lecture est relâché, avec des contraintes :

• acquérir → tous,
• tous → validation,
• spécial → spécial (sauf lorsque l'écriture spéciale est suivie d'une lecture spéciale).

Remarque : la notation ci-dessus A → B, implique que si l'opération A précède B dans l'ordre du programme, alors l'ordre du programme est respecté.

Ces trois architectures commerciales présentent des instructions de clôture explicites comme leurs filets de sécurité. Le modèle Alpha fournit deux types d'instructions de clôture, la barrière mémoire (MB) et la barrière mémoire en écriture (WMB). L'opération MB peut être utilisée pour maintenir l'ordre du programme de toute opération mémoire avant la MB avec une opération mémoire après la barrière. De même, la WMB maintient l'ordre du programme uniquement entre les écritures. Le modèle RMO SPARC V9 fournit une instruction MEMBAR qui peut être personnalisée pour ordonner les lectures et écritures précédentes par rapport aux opérations de lecture et d'écriture futures. Il n'est pas nécessaire d'utiliser des lectures-modifications-écritures pour obtenir cet ordre car l'instruction MEMBAR peut être utilisée pour ordonner une écriture par rapport à une lecture suivante. Le modèle PowerPC utilise une seule instruction de clôture appelée instruction SYNC. Elle est similaire à l'instruction MB, mais à la petite exception que les lectures peuvent se produire hors de l'ordre du programme même si un SYNC est placé entre deux lectures au même endroit. Ce modèle diffère également d'Alpha et de RMO en termes d'atomicité. Il permet à une écriture d'être vue avant l'achèvement d'une lecture. Une combinaison d'opérations d'écriture modifiant la lecture peut être nécessaire pour donner l'illusion de l'atomicité de l'écriture.

Tanenbaum et al., 2007[19] définit le modèle de cohérence comme un contrat entre le logiciel (processus) et l'implémentation de la mémoire (magasin de données). Ce modèle garantit que si le logiciel suit certaines règles, la mémoire fonctionne correctement. Puisque, dans un système sans horloge globale, il est difficile de définir la dernière opération parmi les écritures, certaines restrictions peuvent être appliquées sur les valeurs qui peuvent être retournées par une opération de lecture.

Certains modèles de cohérence, tels que les modèles de cohérence séquentielle ou causale, traitent de l'ordre des opérations sur les données répliquées partagées afin d'assurer la cohérence. Dans ces modèles, toutes les répliques doivent convenir d'un ordre global cohérent des mises à jour.

L'objectif des modèles de cohérence centrés sur les données est de fournir une vue cohérente sur un magasin de données où les processus peuvent effectuer des mises à jour simultanées. Un important modèle de cohérence centré sur les données est la cohérence séquentielle définie par Lamport (1979)[4]. Tanenbaum et al., 2007[19] définit la cohérence séquentielle sous la condition suivante :

Le résultat de toute exécution est le même que si les opérations (lecture et écriture) effectuées par tous les processus sur le magasin de données étaient exécutées dans un certain ordre séquentiel et que les opérations de chaque processus individuel apparaissaient dans cette séquence dans l'ordre spécifié par son programme[19].

Adve et Gharachorloo, 1996[18] définissent deux exigences pour mettre en œuvre la cohérence séquentielle : l'ordre du programme et l'atomicité de l'écriture.

• Ordre des programmes : L'ordre des programmes garantit que chaque processus émet une demande de mémoire ordonnée par son programme.
• Atomicité d'écriture : L'atomicité d'écriture définit le fait que les demandes de mémoire sont traitées en fonction de l'ordre d'une seule file d'attente FIFO.

Dans la cohérence séquentielle, il n'y a pas de notion de temps ou d'opérations d'écriture les plus récentes. Il y a un entrelacement des opérations qui est le même pour tous les processus. Un processus peut voir les opérations d'écriture de tous les processus mais il ne peut voir que ses propres opérations de lecture.

La linéarisabilité[20] (mémoire atomique)[17] peut être définie comme une cohérence séquentielle avec une contrainte de temps réel en considérant un temps de début et un temps de fin pour chaque opération. Une exécution est linéarisable si chaque opération se déroule dans un ordre linéarisable en plaçant un point entre son heure de début et son heure de fin et garantit la cohérence séquentielle.

La cohérence causale[19] définie par Hutto et Ahamad, 1990[10] est un modèle de cohérence plus faible que la cohérence séquentielle en faisant la distinction entre les opérations causalement liées et celles qui ne le sont pas. Par exemple, si un événement b prend effet à partir d'un événement a antérieur, la cohérence causale garantit que tous les processus voient l'événement b après l'événement a.

Tanenbaum et al., 2007[19] définit qu'un magasin de données est considéré comme cohérent du point de vue causal dans la condition suivante :

Les écritures qui sont potentiellement liées de manière causale doivent être vues par tous les processus dans le même ordre. Les écritures concurrentes peuvent être vues dans un ordre différent sur différentes machines[19].

Une cohérence éventuelle[19] est un modèle de cohérence faible dans le système avec l'absence de mises à jour simultanées. Il définit que si aucune mise à jour ne prend un temps très long, toutes les répliques finissent par devenir cohérentes.

La plupart des bases de données décentralisées partagées ont un modèle de cohérence éventuelle, soit BASE : fondamentalement disponible ; état mou ; éventuellement cohérent, soit une combinaison d'ACID et de BASE parfois appelée SALT : séquentielle ; convenue ; jalonnée ; inviolable, et également symétrique ; sans administration ; jalonnée ; et consensuelle dans le temps[21] - [22] - [23].

En opération de regroupement, les accès aux variables de synchronisation sont séquentiellement cohérents. Un processus est autorisé à accéder à une variable de synchronisation que toutes les écritures précédentes ont été complétées. En d'autres termes, les accès aux variables de synchronisation ne sont pas autorisés tant que toutes les opérations sur les variables de synchronisation ne sont pas complètement effectuées[19].

La cohérence continue est définie plus loin dans la section sur le protocole de cohérence.

Dans les systèmes distribués, il est essentiel de maintenir la cohérence séquentielle afin de contrôler les opérations simultanées. Dans certains magasins de données spéciaux sans mises à jour simultanées, les modèles de cohérence centrés sur le client peuvent traiter les incohérences d'une manière moins coûteuse. Les modèles suivants sont des modèles de cohérence centrés sur le client[19] :

Tanenbaum et al., 2007[19] définit la cohérence monotone de la lecture comme suit :

"Si un processus lit la valeur d'une donnée x, toute opération de lecture successive sur x par ce processus retournera toujours cette même valeur ou une valeur plus récente."[19]

La cohérence monotone de la lecture garantit qu'après qu'un processus a lu une valeur de l'élément de données x à l'instant t, il ne verra jamais l'ancienne valeur de cet élément de données.

La condition de cohérence d'écriture monotone est définie par Tanenbaum et al., 2007[19] comme suit :

"Une opération d'écriture par un processus sur une donnée X est terminée avant toute opération d'écriture successive sur X par le même processus."[19]

Une valeur écrite par un processus sur un élément de données X sera toujours disponible pour une opération de lecture successive effectuée par le même processus sur l'élément de données X[19].

Dans le cas de la cohérence écriture-lecture, les mises à jour sont propagées après l'exécution des opérations de lecture précédentes. Tanenbaum et al., 2007[19] définit la condition suivante pour la cohérence écriture-lecture :

"Une opération d'écriture par un processus sur une donnée x à la suite d'une opération de lecture précédente sur x par le même processus est garantie d'avoir lieu sur la même valeur ou une valeur plus récente de x qui a été lue."[19]

La mise en œuvre d'un modèle de cohérence est définie par un protocole de cohérence. Tanenbaum et al., 2007[19] illustre certains protocoles de cohérence pour les modèles centrés sur les données.

La cohérence continue a été introduite par Yu et Vahdat (2000)[24]. Dans ce modèle, la sémantique de cohérence d'une application est décrite en utilisant des unités de cohérence dans l'application. Étant donné que les exigences en matière de cohérence peuvent différer en fonction de la sémantique de l'application, Yu et Vahdat (2000) estiment qu'un modèle de cohérence uniforme prédéfini n'est peut-être pas une approche appropriée. L'application doit spécifier les exigences de cohérence qui satisfont la sémantique de l'application. Dans ce modèle, une application spécifie chaque exigence de cohérence sous forme d'unités de cohérence. Une unité de cohérence peut être une cohérence physique ou logique et est utilisée pour mesurer la cohérence. Tanenbaum et al, 2007[19] décrit la notion d'unité de cohérence en donnant un exemple.

Il existe trois incohérences qui peuvent être tolérées par les applications.

Écart dans les valeurs numériques

L'écart numérique limite la différence entre la valeur de l'unité de cohérence et la valeur relative de la dernière mise à jour. Un poids peut être attribué aux écritures, ce qui définit l'importance des écritures dans une application spécifique. Le poids total des écritures non vues pour une unité de cohérence peut être défini comme un écart numérique dans une application. Il existe deux types d'écart numérique : l'écart numérique absolu et l'écart numérique relatif[24].

Écart dans la commande

L'écart d'ordonnancement est la divergence entre l'ordre local des écritures dans une réplique et leur ordre relatif dans l'image finale éventuelle[24].

Écart de vétusté entre les répliques

L'écart de vétusté définit la validité de l'écriture la plus ancienne en bornant la différence entre l'heure actuelle et l'heure de l'écriture la plus ancienne sur une unité de cohérence non vue localement. Chaque serveur a une file d'attente locale d'écritures incertaines qui sont nécessaires pour qu'un ordre réel soit déterminé et appliqué sur une unité de cohérence. La longueur maximale de la file d'attente des écritures incertaines est la limite de la déviation de l'ordre. Lorsque le nombre d'écritures dépasse la limite, au lieu d'accepter de nouvelles écritures soumises, le serveur tentera de valider les écritures incertaines en communiquant avec d'autres serveurs en fonction de l'ordre dans lequel les écritures doivent être exécutées[24].

Si les trois limites d'écart sont fixées à zéro, le modèle de cohérence continue est la cohérence forte.

Protocole de sauvegarde primaire

Protocole de sauvegarde primaire (écriture locale)

Les protocoles basés sur les primaires[19] peuvent être considérés comme une classe de protocoles de cohérence plus simples à mettre en œuvre. Par exemple, l'ordonnancement séquentiel est un modèle de cohérence populaire lorsque l'on considère l'ordonnancement cohérent des opérations. L'ordonnancement séquentiel peut être déterminé comme un protocole basé sur les primaires. Dans ces protocoles, il y a un primaire associé à chaque élément de données dans un magasin de données pour coordonner les opérations d'écriture sur cet élément de données.

Dans le protocole le plus simple basé sur le primaire et prenant en charge la réplication, également appelé protocole primaire de sauvegarde, les opérations d'écriture sont transmises à un seul serveur et les opérations de lecture peuvent être effectuées localement.

Exemple : Tanenbaum et al., 2007[19] donne un exemple de protocole de sauvegarde primaire. Le diagramme du protocole de sauvegarde primaire montre un exemple de ce protocole. Lorsqu'un client demande une écriture, la demande d'écriture est transmise à un serveur primaire. Le serveur primaire envoie une demande aux sauvegardes pour effectuer la mise à jour. Le serveur reçoit ensuite l'accusé de réception de la mise à jour de toutes les sauvegardes et envoie l'accusé de réception de l'achèvement des écritures au client. Tout client peut lire localement la dernière mise à jour disponible. La contrepartie de ce protocole est qu'un client qui envoie une demande de mise à jour peut devoir attendre longtemps avant de recevoir l'accusé de réception pour pouvoir continuer. Ce problème peut être résolu en effectuant les mises à jour localement, puis en demandant aux autres sauvegardes d'effectuer leurs mises à jour. Le protocole de sauvegarde primaire non bloquant ne garantit pas la cohérence des mises à jour sur tous les serveurs de sauvegarde. Cependant, il améliore les performances. Dans le protocole de sauvegarde primaire, tous les processus verront le même ordre d'opérations d'écriture puisque ce protocole ordonne toutes les écritures entrantes sur la base d'un temps unique au niveau mondial. Les protocoles de blocage garantissent que les processus voient le résultat de la dernière opération d'écriture.

Dans les protocoles d'écriture locale basés sur le primaire[19], la copie primaire se déplace entre les processus désireux d'effectuer une mise à jour. Pour mettre à jour un élément de données, un processus le déplace d'abord à son emplacement. Par conséquent, dans cette approche, les opérations d'écriture successives peuvent être effectuées localement tandis que chaque processus peut lire sa copie locale des éléments de données. Une fois que le primaire a terminé sa mise à jour, celle-ci est transmise aux autres répliques et toutes effectuent la mise à jour localement. Cette approche non bloquante peut conduire à une amélioration. Le diagramme du protocole local d'écriture décrit l'approche locale d'écriture dans les protocoles basés sur les primaires. Un processus demande une opération d'écriture dans un élément de données x. Le serveur actuel est considéré comme le nouveau primaire pour un élément de données x. L'opération d'écriture est effectuée et lorsque la demande est terminée, le primaire envoie une demande de mise à jour aux autres serveurs de sauvegarde. Chaque sauvegarde envoie un accusé de réception au primaire après avoir terminé l'opération de mise à jour.

Dans les protocoles de copie écrite[19], contrairement au protocole basé sur le primaire, toutes les mises à jour sont effectuées sur toutes les copies.

Dans la reproduction active[19], il y a un processus associé à chaque réplique pour effectuer l'opération d'écriture. En d'autres termes, les mises à jour sont envoyées à chaque réplique sous la forme d'une opération afin d'être exécutées. Toutes les mises à jour doivent être exécutées dans le même ordre dans toutes les répliques. Par conséquent, un mécanisme de multidiffusion totalement ordonné est nécessaire. La mise en œuvre d'un tel mécanisme de multidiffusion dans les grands systèmes distribués pose un problème d'évolutivité. Il existe une autre approche dans laquelle chaque opération est envoyée à un coordinateur central (séquenceur). Le coordinateur attribue d'abord un numéro de séquence à chaque opération, puis transmet l'opération à toutes les répliques. Cette deuxième approche ne peut pas non plus résoudre le problème d'évolutivité.

Le vote peut être une autre approche dans les protocoles de copie écrite. Dans cette approche, un client demande et reçoit la permission de plusieurs serveurs afin de lire et d'écrire des données répliquées. Par exemple, supposons que dans un système de fichiers distribué, un fichier est répliqué sur N serveurs. Pour mettre à jour un fichier, un client doit envoyer une demande à au moins N/2 + 1 afin d'obtenir leur accord pour effectuer une mise à jour. Après l'accord, les modifications sont appliquées sur le fichier et un nouveau numéro de version est attribué au fichier mis à jour. De même, pour lire un fichier répliqué, un client envoie une demande à N/2 + 1 serveurs afin de recevoir le numéro de version associé de ces serveurs. L'opération de lecture est terminée si tous les numéros de version reçus sont la version la plus récente[19].

Dans un système de fichiers répliqué, un protocole de cohérence du cache[19] assure la cohérence du cache tandis que les caches sont généralement contrôlés par les clients. Dans de nombreuses approches, la cohérence du cache est assurée par le matériel sous-jacent. D'autres approches dans les systèmes distribués basés sur des intergiciels appliquent des solutions logicielles pour assurer la cohérence du cache.

Les modèles de cohérence des caches peuvent différer par leurs stratégies de détection de la cohérence qui définissent quand les incohérences se produisent. Il existe deux approches pour détecter l'incohérence : les solutions statiques et dynamiques. Dans la solution statique, un compilateur détermine quelles variables peuvent causer l'incohérence du cache. Ainsi, le compilateur impose une instruction afin d'éviter le problème d'incohérence. Dans la solution dynamique, le serveur vérifie les incohérences au moment de l'exécution pour contrôler la cohérence des données mises en cache qui ont changé après leur mise en cache.

La stratégie d'application de la cohérence est un autre protocole de cohérence du cache. Elle définit comment assurer la cohérence des caches en utilisant les copies situées sur le serveur. Une façon de maintenir la cohérence des données est de ne jamais mettre en cache les données partagées. Un serveur peut conserver les données et appliquer un protocole de cohérence tel que les protocoles basés sur les primaires pour assurer la cohérence des données partagées. Dans cette solution, seules les données privées peuvent être mises en cache par les clients. Dans le cas où les données partagées sont mises en cache, il existe deux approches pour faire respecter la cohérence du cache.

Dans la première approche, lorsqu'une donnée partagée est mise à jour, le serveur transmet l'invalidation à tous les caches. Dans la deuxième approche, une mise à jour est propagée. La plupart des systèmes de mise en cache appliquent ces deux approches ou choisissent dynamiquement entre elles.