| Il arrive que l'on souhaite accroître le débit de programmes concurrents, et que pour ce faire nous choisissions de nous compliquer quelque peu l'existence. Il faut toutefois que nos algorithmes progressent vers leur résolution. Il existe trois grandes variantes de modèles de progression d'algorithmes concurrents, soit les algorithmes Wait-Free, les algorithmes Lock-Free et les algorithmes Obstruction-Free. Il existe des définitions formelles dans chaque cas; j'ai choisi ici d'exposer les versions plus informelles (mais plus lisibles, à mon avis) proposées par Herb Sutter. Le résumé à droite est une traduction libre de celles données par Anthony Williams. |
Résumé terminologique De la garantie la plus faible à la garantie la plus forte :
|
L'article séminal sur la question est Wait-Free Synchronization de Maurice P. Herlihy, en 1991
Un algorithme est Wait-Free si un thread n'est jamais bloqué, jamais en attente du résultat des autres. Formellement, dans un algorithme Wait-Free, toute opération se complètera dans un nombre maximal connu a priori d'étapes. Un algorithme susceptible de réessayer une même opération un nombre potentiellement infini de fois dû à l'action d'autres threads n'est pas Wait-Free. C'est dans les systèmes temps réel que ces algorithmes sont particulièrement recherchés, surtout dans le cas de threads à haute priorité.
Des trois contraintes présentées ici, c'est la plus forte. Dans un algorithmes Wait-Free, un thread ne souffre jamais de famine, et un débit systémique satisfaisant est essentiellement garanti.
Un exemple d'algorithme Wait-Free serait celui-ci :
//
// supposons que ptr_partage<T> implémente une sémantique de partage du pointé,
// que cpt_ soit un atomic<long long>* et que p_ soit un T*. cpt_ et p_ sont
// présumés non-nuls par construction (pour alléger le code)
//
template <class T>
void ptr_partage<T>::add_client() {
++(*cpt_);
}
template <class T>
void ptr_partage<T>::remove_client() {
if ((*cpt_)-- == 1) {
delete cpt_;
delete p_;
}
}Informellement, Lock-Free signifie « sans recours à un mutex ».
Un algorithme est Lock-Free si chaque étape franchie fait progresser le système dans son ensemble. Ceci ne dit rien sur les garanties de threads de ce système pris individuellement : dans un tel algorithme, un ou plusieurs threads peuvent souffrir de famine, dans la mesure où le système dans son ensemble progresse vers la réalisation de sa tâche.
Un algorithme Wait-Free est aussi Lock-Free, mais l'inverse n'est pas nécessairement vrai.
Un exemple d'algorithme Lock-Free serait celui-ci :
//
// Dans cet exemple, tete est un atomic<noeud>*, et noeud est un struct contenant une valeur, de
// type T, et un successeur nommé succ, de type noeud*
//
template <class T>
void stack<T>::push(const T &val) {
auto p = new noeud{ val };
p->succ = tete.load();
while (!tete.compare_exchange_weak(p->succ, p, std::memory_order_relaxed)) // brrrr...
;
}Dans cet algorithme, en effet, le temps requis pour compléter le push() est fortement influencé par la contention sur la tête de la pile, mais si la contention est faible sur cet objet, alors cet algorithme sera typiquement plus rapide qu'un équivalent reposant sur un mutex.
Un algorithme est Obstruction-Free dans le cas où, en tout temps, un thread progressera vers la complétion de sa tâche si les threads susceptibles de le bloquer n'interviennent pas.
Des trois contraintes présentées ici, c'est la plus faible. Par définition, un thread ne peut être bloqué par l'échec ou le ralentissement d'un autre thread. Toujours par définition, les deadlocks y sont impossibles, mais il peut y avoir des cas de livelocks. Il y a peu d'exemples de tels algorithmes en pratique, bien que http://cs.brown.edu/%7Emph/HerlihyLM03/main.pdf en soit un.
Un algorithme Lock-Free est aussi Obstruction-Free, mais l'inverse n'est pas nécessairement vrai.
Pour les textes officiels, plus précis mais peut-être moins « mâchés », voir http://wg21.link/p0299 et http://wg21.link/p0296
Grâce en particulier aux travaux de Torvald Riegel, le standard C++ 17 offrira des garanties de progression pour appuyer ses algorithmes standards parallèles. Ces garanties détaillent ce sur quoi il est possible de compter lors de la rédaction de nos programmes à l'aide de ces outils.
Voici comment procède le raisonnement derrière ce que supporte désormais le langage. Notez que l'« implémentation » réfère ici à ce qu'offrira un compilateur C++ 17 conforme. Notez aussi que thread signifie ici un fil d'exécution, pas une instance de std::thread. Enfin, notez que ce qui suit présume un programme correctement écrit (outils de synchronisation correctement utilisés, pas de boucle infinie, pas d'interblocage) :
Une implémentation peut supposer que tout thread fera éventuellement au moins l'une des choses suivantes (ce sont des étapes d'exécution) :
Certaines exécutions de fonctions sur des objets atomiques sont Lock-Free et documentées comme telles. Si un seul thread s'exécute, n'est pas bloqué par une fonction de la bibliothèque standard, alors une exécution Lock-Free dans ce thread se complétera.
Si plusieurs exécutions Lock-Free s'exécutent concurremment, alors au moins une se complétera.
Techniquement, une opération d'entrée/ sortie de la bibliothèque standard est considérée active même si elle est bloquante (on peut imaginer qu'elle boucle de manière non-bloquante en vérifiant la disponibilité de données). Ceci facilite le raisonnement.
Un thread progresse lorsqu'une étape d'exécution se produit (il y a des nuances sur le blocage d'un thread devant une exécution Lock-Free dans la bibliothèque standard qui s'ajoutent à ce portrait). L'implémentation s'assurera qu'un thread offrant la garantie concurrent forward progress progresse jusqu'à ce que son exécution se soit complétée. Il est à noter que main() et les fils d'exécution créés par std::thread n'ont pas l'obligation d'offrir la garantie concurrent forward progress, mais que ce comportement est encouragé par le standard.
Puisque la bibliothèque standard offre des algorithmes parallèles, elle offre aussi des garanties de progression. Ces garanties de progression offertes sont, en ordre décroissant de force : concurrent forward progress, parallel forward progress, et weakly parallel forward progress :
Les spécifications de garantie de progression sont rattachées aux politiques d'exécution (parallèle ou autre) des algorithmes standards, et sont donc représentées par des objets du langage. Ces objets sont passés en paramètre aux algorithmes, et l'absence d'une spécification explicite équivaut au choix d'un algorithme séquentiel :
| Politique | Effet |
|---|---|
|
Les appels de fonctions accédant aux éléments parcourus en parallèle avec cette politique peuvent être faits dans le désordre, que ce soit par le thread ayant lancé l'exécution de l'algorithme ou par l'un autres threads participant à cette exécution parallèle. Si les threads impliqués offrent la garantie de progression concurrent forward progress, alors les threads implicitement créés par la bibliothèque standard offriront la garantie parallel forward progress; sinon, les garanties de progression offertes dépendent de l'implémentation. Les appels s'exécutant sur un thread donné ne sont pas séquencés (ils sont indeterminately sequenced) les uns pas rapport aux autre. C'est à l'appelant de l'algorithme de s'assurer du fait que le code soit correct, ne créant ni Data Race, ni interblocage. |
|
Les appels de fonctions accédant aux éléments parcourus en parallèle avec cette politique peuvent être faits dans le désordre, que ce soit par le thread ayant lancé l'exécution de l'algorithme ou par l'un autres threads participant à cette exécution parallèle. Ces threads seront soit le thread ayant lancé l'exécution de l'algorithme, soit l'un de ceux implicitement lancés par la bibliothèque standard (dans quel cas les threads offriront la garantie weakly parallel forward progress). Avec cette politique, plusieurs appels de fonctions peuvent être entrelacés sur un même thread. C'est l'une des rares exceptions aux règles usuelles du langage C++ qui ne permettent pas l'entrelacement d'appels de fonctions sur un même thread. Pour cette raison, avec cette politique d'exécution, la synchronisation bloquante, incluant le recours à des mutex, peut provoquer un interblocage. Conséquemment, la synchronisation avec cette politique d'exécution est soumise à certaines contraintes :
|
Quelques liens suivent pour enrichir le propos.
