-
Notifications
You must be signed in to change notification settings - Fork 13
3.3 atomic_ring: Un template pour un anneau à verrou minimum
Un anneau est un conteneur particulier dans lequel des éléments peuvent être rajoutés en tête ou en queue dans un temps comparable. La structure est circulaire, ce qui signifie que lorsque l'on atteint l'extrémité de l'anneau, l'élément suivant recommence au début de la structure.
La version que je propose ici est conçu pour s'exécuter dans des threads avec une utilisation minimale des locks.
Je me suis inspiré de la programmation "sans verrou" (lock-free en anglais) pour construire ce conteneur. Le terme est plutôt trompeur car lorsque le besoin d'étendre la mémoire pour accueillir de nouveaux éléments se fait sentir, il est parfois nécessaire de verrouiller les accès mémoire. Malgré tout, si l'on veut implémenter un conteneur propre à survivre en milieu multithreadé, il faut implanter les deux contraintes suivantes a minima:
-
Première contrainte: l'augmentation de la mémoire doit se faire par page, sans que les pages déjà allouées ne soient détruites. De cette façon, on se protège contre le risque d'un accès à une zone mémoire détruite, comme c'est parfois le cas avec les conteneurs standards en C++.
-
Seconde contrainte: cette structure en anneau peut nous servir à stocker des pointeurs, ce qui introduit des problèmes de concurrence particulièrement épineux. En effet, si deux threads remplacent le même pointeur par un autre, il faut que les opérations soient correctement séquencées pour éviter qu'un objet ne soit détruit deux fois ou pire jamais détruit, au risque sinon de crashes intempestifs ou de dérapage mémoire.
Cet anneau a été implémenté sous la forme d'un template C++ avec quelques contraintes que l'on peut d'ailleurs modifier si besoin est. En particulier, il ne peut comprendre que 65535 éléments. De plus, certains choix pour assurer une programmation "lock-free" donnent un ratio taille mémoire/occupation assez mauvais dans le pire des cas. Il faut quand même préciser qu'un anneau sert à placer des objets en tête ou en queue, rarement à les positionner à un endroit précis. De ce point de vue, cette structure assure un temps équivalent d'ajout en tête ou en queue de nouveaux éléments. De plus, lorsque les opérations s'se résument à des "push_front" ou des "push_back", l'occupation mémoire est généralement optimale.
Nous avons précisé plus haut qu'une des solutions pour implémenter un conteneur "lock-free" est de gérer la mémoire sous la forme de page. Dans le cas présent, cette pagination se base sur une table de taille fixe de 256 éléments. Chaque élément est lui-même une table de 256 éléments. A l'initial, cette table de base est vide à l'exception du premier élément et du dernier élément.
template <class Z> class atomic_ring {
public:
atomic_ring_element<Z>* head[256];
std::atomic<unsigned short> first;
std::atomic<unsigned short> last;
std::recursive_mutex _lock;
atomic_ring() {
for (long i = 0; i < 256; i++)
head[i] = NULL;
head[0] = new atomic_ring_element<Z>(NULL);
head[255] = new atomic_ring_element<Z>(NULL);
last = 0;
first = 0;
} Comme on peut le voir sur l'exemple ci-dessus, ce template est en réalité très simple. La table initiale de 256 éléments contient des éléments de type atomic_ring_element sur lesquels nous reviendrons plus loin.
A la première initialisation, la table est vide à l'exception du premier et du dernier élément pour lesquels on crée un atomic_ring_element.
Notons d'abord que "first" et "last" sont des "unsigned short" dont la valeur maximale est 65535. Ce choix a pour effet que si "last" vaut 65535, alors "last+1" vaudra 0, d'où l'effet d'anneau ainsi obtenu.
Notons de plus qu'ils sont implémentés comme des variables atomiques. Ainsi on s'assure que leurs valeurs pourront être modifiés sans verrou.
Le seul cas où le lock peut se révéler utile est lorsque l'on cherche à placer un élément dans une case de head qui est NULL.
Ce cas est géré par la méthode suivante:
inline void addnewelement(unsigned char nb) {
if (head[nb] == NULL) {
_lock.lock();
if (head[nb] == NULL)
head[nb] = new atomic_ring_element<Z>(zero);
_lock.unlock();
}
}Remarquons le double test sur head[nb]. En effet, un seul thread à la fois peut accéder à la section critique. Une fois l'élément créé, le second test permettra aux threads en attente de sauter cette section.
La position du dernier élément ajouté en tête est enregistrée par first tandis que celle du dernier élément ajouté en queue est enregistrée par last. Quand on rajoute en tête, on décrémente first, quand on rajoute en queue on incrémente last. Ainsi, l'ajout d'un nouvel élément en tête ou en queue est totalement parallèle.
Voici par exemple la version: push_front qui rajoute un élément en tête:
Z push_front(Z val) {
unsigned short pos = --first;
uchar nb = pos >> 8;
uchar i = pos - (nb << 8);
addnewelement(nb);
return head[nb]->replace(val,i);
}Le calcul pour savoir où ranger l'élément est très simple. On divise par 256 pour savoir dans quelle case de head est située notre sous-table. Puis on calcule le reste pour connaitre la position dans cette sous-table. addnewelement vérifiera si la case pointée par nb nécessite ou non la création d'un nouvel élément atomic_ring_element.
Le fait que first est atomique permet de s'assurer que chaque thread aura accès à sa propre valeur de first.
La version inverse: push_back ne fait qu'appliquer la même chose sur last, à la différence que last est incrémenté.
...
unsigned short pos = last++;
...Remarquons aussi l'appel à replace en fin de méthode, qui effectue en échange entre la valeur stockée dans la sous-table et val. Nous reviendrons sur le choix de cette méthode.
On peut aussi bien retirer un élément en tête qu'en queue: remove_back et remove_front. Ces méthodes non seulement retirent un élément en tête ou en queue, mais elles renvoient aussi la valeur de celui-ci. En effet, s'il s'agit d'un pointeur sur un objet, il peut être nécessaire de le détruire.
Z remove_back() {
unsigned short pos = --last;
uchar nb = pos >> 8;
uchar i = pos - (nb << 8);
return head[nb]->replace(NULL, i);
}Remarquons l'appel de la méthode replace. replace renvoie la valeur pointé par i et remplace celle-ci par NULL. Cette méthode est fondamentale car c'est grace à elle que l'on résout les problèmes d'accès concurrent.
Examinons maintenant atomic_ring_element pour comprendre pourquoi.
Comme nous l'avons mentionné plus haut, atomic_ring_element est aussi une table de 256 éléments: 256x256 = 65536, mais avec un zeste de surprise:
template <class Z> class atomic_ring_element {
public:
std::atomic<Z> vecteur[256];
... En effet, la table vecteur contient des éléments atomiques. Ce type permet de gérer des accès concurrents à la condition d'utiliser une méthode particulière: exchange. Cette méthode permet d'enregistrer une nouvelle valeur tout en renvoyant comme résultat l'ancienne valeur. Etant atomique, cette opération nous garantit que les appels depuis des threads différents se feront les uns derrière les autres.
Voici à quoi ressemble la fameuse méthode replace:
Z replace(Z v, unsigned char i) {
return vecteur[i].exchange(v);
}Cette méthode replace que nous avons vu plus haut dans remove_back nous permet de garantir qu'aucun élément ne sera perdu.
L'accès à la tête ou à la queue est là aussi très simple:
Z back() {
unsigned short pos = last-1;
uchar nb = pos >> 8;
uchar i = pos - (nb << 8);
return head[nb]->vecteur[i];
}Il suffit de se placer avant ou après le pointeur courant.
Voici un exemple d'utilisation de ce template:
//Le paramètre NULL est la valeur par défaut rangée dans les sous-tables
//Vous pouvez choisir ce que vous voulez
atomic_ring<char*> test(NULL);
char* c = new char[10];
strcpy(c,"test");
char* r = test.push_back(c);
if (r != NULL) //Si une valeur a été échangée avec une déjà existante
delete[] r; //on la détruit. NULL est la valeur par défaut fournie ci-dessusLa description de ce template montre comment on peut implémenter une structure aussi riche qu'un anneau de façon très simple en limitant le plus possible l'utilisation des locks.
Dans notre anneau, nous n'avons pas besoin de lock pour accéder à un élément ou pour le retirer. Dans le cas d'un ajout, le lock n'est utilisé finalement que toutes les 256 opérations, et encore une fois la table principale pleine, les locks deviennent inutiles. Evidemment, comparé à un vector, cette structure est légèrement moins efficace et un peu plus gourmande en ressource. En revanche, sa très faible utilisation des locks la rend remarquablement efficace dans un contexte multithreadé.
L'implémentation est disponible ici: atomic_ring