Lors de la conférence CppCon 2014, Herb Sutter a fait une présentation portant sur la programmation sans lock en C++ (1ère partie, 2ème partie). Il en a rappelé les concepts fondamentaux et a présenté trois algorithmes illustrant des techniques "lock-free". Voici un résumé des points essentiels de la présentation.
Herb commence par traiter les bénéfices de la programmation sans lock :
- Celle-ci permet d’améliorer le degré de concurrence et la scalabilité en réduisant les attentes et les blocages.
- Celle-ci permet de se débarrasser des problématiques potentielles telles que les "race conditions", les "deadlocks" et les limites de composabilité.
La programmation sans lock n’est pas la panacée cependant, puisque les algorithmes sont généralement plus complexes à concevoir et que certains problèmes pouvant affecter sévèrement la performance, comme de la contention, peuvent être rencontrés. De ce constat, Herb tire ses premières préconisations :
- N’appliquez les techniques "lock-free" qu’après avoir établi des mesures de votre programme et constaté des problèmes de performance ou de scalabilité.
- Après avoir implémenté un algorithme "lock-free", mesurez à nouveau pour vérifier qu’il y a eu effectivement une amélioration.
Fondamentaux
Voici quelques bases de réflexion à appliquer aux algorithmes "lock-free" :
- Cohérence : toute portion de code devrait être considérée comme une transaction portant le système d’un état cohérent vers un autre état cohérent.
- Isolation : deux transactions ne doivent jamais opérer sur les mêmes données.
- Durabilité : une transaction commitée n’est jamais écrasée par une autre avant que cette dernière n’ait "vu" les résultats de la première.
La technique fondamentale pour réaliser cela consiste à :
- Calculer tous les changements dans une zone privée.
- Utiliser une écriture atomique unique avec une fonction compare/exchange spécifique pour les rendre publics.
En C++11, ceci se traduit par l’utilisation d’atomic<T> qui offre deux gros avantages :
- Vous pouvez considérer toutes les opérations de lecture et d’écriture comme atomiques, sans lock requis.
- Il est garanti que les lectures et les écritures ne seront pas réordonnées.
Voici quelques autres points importants au sujet d’atomic :
- Pour les "petits" types,
atomicest généralement implémenté avec des opérations spécifiques à la plate-forme. - Les objets atomic doivent toujours être initialisés (autrement, ils contiendront des données incorrectes).
- Il est garanti que deux opérations atomiques le sont de façon individuelle, mais le statut des objets peut changer entre temps.
Exemple : Double-checked Locking
Le premier exemple présenté par Herb montre comment assurer la construction unique d’objet global. L’idée clé est la suivante : protéger l’opération d’écriture atomique avec un lock, tout en laissant l’écriture atomique se faire sans lock. Un blocage ne peut ainsi se produire qu’entre les threads en concurrence pour initialiser le singleton. L’algorithme porte ce nom car l’instance du pointeur est vérifiée deux fois, avant et après avoir acquis le lock :
atomic<Widget*> Widget::pInstance{ nullptr };
Widget* Widget::Instance() {
if (pInstance == nullptr) {
lock_guard<mutex> lock { mutW };
if (pInstance == nullptr) {
pInstance = new Widget();
}
}
}
Exemple : producteur - consommateurs
Le deuxième exemple décrit par Herb est un algorithme de producteur consommateurs classique. Il commence par décrire une solution traditionnelle utilisant des locks où :
- Le producteur acquiert un lock sur la queue partagée et y pousse quelques objets. Pour chaque objet, une variable est notifiée, ce qui a pour effet d’informer les consommateurs.
- Les consommateurs essaient d’acquérir un lock sur la queue. Lorsque l’un d’entre eux y arrive, il regarde s’il y a un objet à consommer et, si c’est le cas, l’objet est récupéré et traité après avoir relâché le mutex.
Il est possible d’imaginer une première variante de cet algorithme utilisant une technique sans lock, où l’on accède à la liste à travers une variable atomic. Cela permet au producteur de créer tous ses éléments d’un seul coup et de les publier au consommateur en positionnant de façon atomique la tête de la queue. Les consommateurs restent inchangés.
On peut ensuite passer à une implémentation complètement "lock-free" : dans ce cas, l’algorithme s’appuie sur l’idée que le producteur doit remplir un certain nombre d’emplacements. Quand celui-ci a une nouvelle tâche à effectuer, il vérifie s’il y a un emplacement vide et y stocke la tâche. Dans le code suivant, l’emplacement est une variable atomique :
curr = 0;
// Phase 1: build and distribute tasks
while (ThereAreMoreTasks()) {
task = AllocateAndBuildNewTask();
while (slot[curr] != null)
curr = (curr+1)%K;
slot[curr] = task;
sem[curr].signal();
}
// Phase 2: Stuff the mailbox with done
numNotified = 0;
while (numNotified < K) {
while (slot[curr] != null)
curr = (curr+1)%K;
slot[curr] = done;
sem[curr].signal();
++numNotified;
}
Concernant les consommateurs, le code est plus simple :
myTask = null;
while (myTask != done) {
while (myTask = slot[mySlot]) == null)
sem[mySlot].wait();
if (myTask != done) {
slot[mySlot] = null;
DoWork(myTask);
}
}
Un consommateur attend via le signal d’un sémaphore qu’une tâche soit dans un emplacement. Lorsqu’une tâche arrive, le consommateur la récupère et vide l’emplacement. Après avoir fait cela, le consommateur commence à traiter ses données. Ceci reprend l’idée précédente d’effectuer le travail en dehors de la section critique. Mais si le consommateur est plus lent que le producteur, alors cela pourrait être opportun d’effectuer le travail avant de relâcher le lock, afin que le producteur ne remplisse pas le même emplacement alors que le consommateur est occupé mais préfère remplir un autre emplacement vide. Ceci illustre comment peuvent être prises différentes décisions qui affectent de façon subtile le débit/la scalabilité contre la répartition de charge.
Exemple : Liste chaînée simple
Une liste chaînée simple est une des structures de données parmi les plus simples, qui supporte ici seulement quatre opérations : construct, destroy, find, push_front. L’implémentation sans lock proposée par Herb utilise un atomic<Node*> head{ nullptr }; pour accéder à la tête de slist. La seule méthode qui présente des problèmes de concurrence est push_front qui dans une version à thread unique pourrait ressembler à ceci :
template
void slist<T>::push_front(T t) {
auto p = new Node;
p->t = t;
p->next = head;
head = p;
}
Ce code présente des problèmes car il ouvre la possibilité de races lorsque la nouvelle valeur de head est positionnée. Ce problème peut être résolu en utilisant compare_exchange lors de l’écriture de head, comme le montre le code ci-dessous :
template
void slist<T>::push_front(T t) {
auto p = new Node;
p->t = t;
p->next = head;
while (!head.compare_exchange_weak(p->next, p))
{}
}
Ici, on essaie d’échanger head et p jusqu’à réussite. L’utilisation de compare_exchange_weak est classique dans un code "lock-free". Celui-ci est principalement utilisé avec des boucles, alors que compare_exchange_strong est utilisé en dehors des boucles.
Des problèmes supplémentaires apparaissent lorsque l’on essaie d’implémenter une opération pop, qui supprime le premier élément de la liste. Dans ce cas, une source principale de la complexité est qu’il est possible de retourner un pointeur vers un objet qui peut être supprimé par un autre thread peu après. Herb détaille comment ce problème, bien connu dans la littérature sous le nom de problème ABA, peut se produire dans le contexte de son scénario. C++11 propose une solution élégante à ce problème, en permettant de remplacer l’utilisation des pointeurs purs par des shared_ptr. L’implémentation en pseudo-code devient :
template
struct Node { T t; shared_ptr<Node> next; };
atomic<shared_ptr<Node>> head;
public:
slist() =default;
~slist() =default;
class reference {
shared_ptr<Node> p;
public:
reference(shared_ptr<Node> p_) : p{_p} {}
T& operator*() { return p->t; }
T* operator->() { return &p->t; }
};
auto find(T t) const {
auto p = head.load();
while (p && p->t != t)
p = p->next;
return reference{move(p)};
void push_front(T t) {
auto p = make_shared<Node>();
p->t = t;
p->next = head;
while (head.compare_exchange_weak(p->next, p))
{}
}
void pop_front() {
auto p = head.load();
while (p && !head.compare_exchange_weak(p, p->next))
{}
}
};
Ici, l’astuce est que le pointeur est retourné dans un shared_ptr, on est donc prémuni des soucis de suppression. Cette implémentation présente une caractéristique intéressante connue sous le nom de linéarisabilité, qui fait qu’une série d’opérations qui se chevauchent peut être pensée comme si ces opérations étaient exécutées en séquence.
La dernière partie de la présentation est dédiée à l’exemple d’un programme mesuré pour déterminer son comportement et identifier quels seraient les bénéfices d’en avoir une version sans lock.