Ces notes ne sont pas de moi et ont été trouvés sur le Discord

Introduction

Sûreté : rien de mal n’arrive
vivacité / liveness : un jour quelque chose de bien se passera

Exclusion mutuelle : Sûreté assure que deux Threads n’interagirons pas en même temps avec une ressource. Ou en tout cas en même temps de telle sorte à modifier le comportement pour l’autre Thread.

Absence de Deadlock :
Si une ressource devient indisponible (par exemple verrou jamais relâché) les individus doivent faire avec Garantie l’avancée globale du système même si des individus sont en famine.

vivacité/liveness

Absence de famine :
Si quelqu’un veut une ressource un jour, il l’aura, dans au pire x temps. Garantie que les individus finiront par avancer dans le temps.

vivacité/liveness

Absence d’attente :
Tout appel de méthode d’un objet se termine en un nombre fini de pas.

vivacité/liveness

Absence de verrou

Loi de Amdahl
Permet de calculer le gain de vitesse par la parallélisation du code \frac{1}{1-p+\frac{p}{n}} avec :

volatile: mot clé java
Qui signale au compilateur

ThreadLocal<T> : Permet de spécifier des variables qui sont locales à un Thread.

Section critique

linéarisable

Point de linéarisation : évènement “fictif” dans certaines fonctions où l’on peut considérer dans une histoire concurrentielle que toute l’exécution à lieue instantanément. Au dit point permet de raisonner sûr et de démontrer la sûreté d’évènement concurrent, voir linéarisation.

lock free

n-consensus

Cours exclusion mutuelle 12 janvier

évènement :
repère dans le temps d’exécution d’un Thread, instantané et ne peut pas se superposer (se produire en même temps que) d’autres évènements dans un même Thread.

Entrelacement/interleaving:
Se dit lorsque deux ou plus Thread possèdent des évènements qui, sur une frise temporelle globale, (et non plus locale à un Thread) sont entremêlés et/ou se chevauchent. Qu’ils s’entremêlent signifie qu’on a un/plusieurs évènements d’un Thread puis un/des évènements d’un autre Thread puis à nouveau un/des évènements du premier Thread.

Un intervalle de temps est un doublet d’évènement dans un Thread.

Deux intervalles de temps peuvent ou non se chevaucher. (entrelacement entre les évènements des 2 intervalles)

Un intervalle A précède un intervalle B et est noté A \ra B si les 2 évènements du doublet A se produisent avant les 2 évènements du doublet B.

Il est possible que A\ra B soit faux et B\ra A soit faux par exemple si deux intervalles de temps se chevauchent.

Un évènement que l’on note ici a_0 peut avoir lieu plusieurs fois dans le temps, on note (a_0)^k la k-ème occurrence de l’évènement.

Il en va de même pour un intervalle de temps noté A_0: la k-ème occurrence sera (A_0)^k

L’interface Lock de Java permet de mettre en place ses propres algorithmes de verrouillage

Algorithme de la boulangerie : court, élégant, équitable mais “impossible” à pratiquer : voir prochain cours

fin cours exclusion mutuelle 26 janvier

Problème pour appliquer l’algorithme de la boulangerie, il faut lire n variables distinctes si on a n Thread.

Cours linéarisabilité début 26 janvier

Spécification d’un objet concurrent : montrer la correction du comportement de l’objet

Une spécification séquentielle (donc pas concurrente) s’exprime sous la forme :

Si précondition
Sur l'état initial

Alors postcondition 
la valeur retournée

Et postcondition
Effet de bord sur l'objet

Une spécification concurrentielle s’exprime sous la forme

Une spécification concurrente garantit : sûreté/liveness l’accent est mis sur comment se comporte un objet face à des appels concurrent, car un appel de méthode n’est pas un évènement, mais un intervalle délimité par son appel et son retour. Il peut se passer d’autres choses durant cet intervalle.

Première option de spécification concurrente, si l’objet est en exclusion mutuelle avec des verrous On essaie de linéariser le tout (montrer que séquentiellement tout marche bien, car les sections critiques sont protégées).

Cours registre 26 janvier

Un registre est dit sûr si en cas de concurrence, il garantit qu’une valeur légale sera toujours lue par qui que ce soit.

Un registre est régulier si en cas de concurrence, il garantit qu’uniquement une ancienne valeur ou la valeur actuelle
sera toujours lue par qui que ce soit.

Un registre est dit atomique si en cas de concurrence, il garantit qu’une fois une mise à jour faite, la nouvelle valeur
sera systématiquement lue par qui que ce soit.

Cours linéarisabilité fin 2 février

éléments de Notation :

Thread A
objet obj
méthode fun
argument x
résultat y

Appel de méthode :

A obj.fun(x)
et sa réponse:
A obj: y

Histoire :
Suite d’appels de méthode/ de leur réponse par des Threads sur des objets. Ordonné dans le temps.

Projection d’une histoire en fonction de quelque chose :
Sous-histoire qui comporte seulement les appels de méthode / leur réponse en fonction de :

Histoire séquentielle : Pas d’entrelacement entre les appels de méthodes et leurs réponses;
chaque appel de méthode est suivi de sa réponse, autorisation pour dernier appel d’être pendant.

Histoire Complète : Toutes les invocations de méthodes dans l’histoire trouvent leur réponse.
(Aucune invocation n’est pendante, sans réponse).

Histoire bien formée : Toutes les invocations ont reçu une réponse pour tous les Threads. (Tous les Threads ont une histoire complète).

Histoire équivalente : Deux histoires sont équivalentes si elles ont les mêmes processus et que pour chaque processus pris à part, et son symétrique dans l’autre histoire ; les évènements et leur ordre est identique.

Histoire légale : Pour tout objet de l’histoire la projection de l’histoire par l’objet respecte la spécification séquentielle dudit objet.

Précédence : Tout comme pour les intervalles, un appel de méthode A en précède un autre B si l’appel + la réponse de A a lieu avant l’appel de B. (pas d’entrelacement)

Linéarisabilité : Une histoire est dite linéarisable si elle peut être étendue à une histoire légale séquentielle en ajoutant des réponses à des invocations pendantes ou en les ignorant.

Équivalent : Une histoire est aussi linéarisable si pour chaque objet de l’histoire, l’histoire projetée par l’objet est linéarisable et légale.

“Sous structure valide” : la linéarisabilité est alors une propriété locale à l’objet, pour chaque objet.

Cette définition nous autorise à mettre les invocations / réponse dans n’importe quel Thread pourvu qu’on respecte la précédence séquentielle Si une histoire est linéarisable, elle n’a pas besoin de verrous, elle peut être non bloquante sans aucun soucis !

Alternative moins forte à la linéarisation, la consistance séquentielle

Une histoire est dite consistante séquentiellement si elle peut être étendue à une histoire légale séquentielle
pour chaque Thread en ajoutant des réponses à des invocations pendantes ou en les ignorant.

C’est moins fort que la linéarisation, car dans la linéarisation, c’est l’objet le centre de l’histoire, peu importe où le Thread qui appel ou fait on ne sait quoi sur l’objet il n’y aura pas de problème, car la spéc séquentielle de l’objet est garantie.
La consistance séquentielle nous dit “si on considère ce qui se passe dans chaque Thread seul tout va bien” reste à gérer correctement la communication inter-Thread et voilà le verrou qui pointe le bout de son nez. Cette définition nous autorise à réordonner les Thread, mais nous interdit de réordonner à l’intérieur des Threads.

Cours Atomic Snapshot du 9 février 2023

…

Cours consensus 23 février 2023

…

Cours liste 9 mars 2023 et 15 mars 2023

Synchronisation à gros grain

L’utilisation systématique de verrous sur l’objet tout entier.
Le plus facile, le moins facilement mis à l’échelle aussi.

Synchronisation à grain fin

Utilisation de verrou uniquement sur le morceau de l’objet que l’on souhaite utiliser, les autres morceaux sont laissés à autrui.
Potentiellement mieux la Synchronisation à gros grain, Risque potentiel de Deadlock.
On doit potentiellement prendre beaucoup de verrou “par sécurité” qui ne sont pas utiles à l’opération !

Synchronisation optimiste

Préparer le changement sans prendre le verrou, poser le verrou juste avant le changement et vérifier que les prémisses acquises sans verrou sont toujours vraies une fois qu’on a le verrou.
Si ce n’est plus le cas, c’est un cas d’erreur, il faut recommencer : couteux.
On ne prend que les verrous strictement nécessaires!

Synchronisation paresseuse

Faire le maximum de travail de manière “symbolique” et laisser le travail difficile avec verrou à autrui / pour plus tard.