Allocateurs de mémoire sans verrouillage dynamique

Question

Une des difficultés dans l'écriture d'algorithmes ou de structures de données qui garantissent la progression sans verrouillage est l'allocation de mémoire dynamique : appeler quelque chose comme malloc ou new n'est pas garanti d'être sans verrou de manière portable. Cependant, de nombreuses implémentations sans verrouillage de malloc ou new existent, et il existe également divers allocateurs de mémoire sans verrou pouvant être utilisés pour implémenter des algorithmes/structures de données sans verrou.

Cependant, je ne comprends toujours pas comment cela peut réellement satisfaire complètement les garanties de progression sans verrou, à moins que vous ne limitiez spécifiquement votre structure de données ou algorithme à un pool de mémoire statique pré-alloué. Mais si vous avez besoin d'une allocation de mémoire dynamique, je ne comprends pas comment un éventuel allocateur de mémoire sans verrou peut jamais être vraiment sans verrou à long terme. Le problème est que, peu importe à quel point incroyable peut être votre malloc ou new sans verrou, vous finirez par manquer de mémoire, moment où vous devrez demander au système d'exploitation plus de mémoire. Cela signifie qu'au final, vous devrez appeler brk() ou mmap() ou autre équivalent de bas niveau pour réellement obtenir accès à plus de mémoire. Et il n'y a tout simplement aucune garantie que aucun de ces appels de bas niveau ne soit implémenté de manière sans verrou.

Il n'y a tout simplement pas de solution à cela (à moins d'utiliser un ancien système d'exploitation comme MS-DOS qui ne fournit pas de protection de mémoire, ou d'écrire votre propre système d'exploitation entièrement sans verrou - deux scénarios qui ne sont pas pratiques ou probables.) Alors, comment un quelconque allocateur de mémoire dynamique peut-il vraiment être sans verrou?

Answer 1

Comme vous l'avez découvert par vous-même, l'allocateur OS fondamental n'est probablement pas lock-free, car il doit gérer plusieurs processus et toutes sortes de choses intéressantes qui le rendent vraiment difficile à ne pas introduire une sorte de verrou.

Cependant, dans certains cas, la "allocation de mémoire sans verrou" ne signifie pas "ne verrouille jamais", mais "verrouille statistiquement si rarement que cela n'a pas vraiment d'importance". Ce qui est bien pour tout sauf les systèmes de temps réel les plus stricts. Si vous n'avez pas une forte contention sur votre verrou, alors verrouiller ou non n'a pas vraiment d'importance - le but du lock-free n'est pas vraiment le surcoût du verrou lui-même, mais la facilité avec laquelle il devient un goulot d'étranglement où chaque thread ou processus dans le système doit passer par ce seul endroit pour faire quelque chose d'utile, et ce faisant, il doit attendre en file d'attente [ce n'est peut-être pas une vraie file d'attente non plus, cela peut être "qui se réveille en premier" ou un autre mécanisme qui décide qui sort ensuite, après l'appelant actuel].

Il existe quelques options différentes pour résoudre cela:

• Si vous avez un pool de mémoire avec une taille finie, vous pouvez demander à l'OS toute cette mémoire en une seule fois, au démarrage du logiciel. Et après que la mémoire ait été distribuée par l'OS, elle peut être utilisée comme un pool sans verrou. L'inconvénient évident est qu'il y a une limite à la quantité de mémoire qui peut être allouée. Vous devez alors arrêter l'allocation (échouer l'application complètement, ou échouer cette opération particulière).

  Bien sûr, dans un système comme Linux ou Windows, il n'y a toujours aucune garantie que l'allocation de mémoire, dans un scénario sans verrou, signifie "accès instantané à la mémoire allouée", puisque le système peut et allouera de la mémoire sans mémoire physique réelle la soutenant, et ce n'est qu'une fois que la mémoire est réellement utilisée que la page mémoire physique lui est assignée. Cela peut impliquer à la fois des verrous et par exemple des E/S disque pour remplacer une autre page en mémoire virtuelle.

• Pour de tels systèmes temps réel stricts que le temps d'un seul appel système qui pourrait être en concurrence pour un verrou est "trop long", la solution est bien sûr d'utiliser un OS dédié, un qui a un allocateu...

• Une autre solution qui peut fonctionner est d'avoir des "pools par thread". Cela peut devenir un peu compliqué si vous passez des données entre les threads, mais si vous acceptez que "la mémoire libérée pour être réutilisée puisse finir dans un thread différent" (ce qui bien sûr conduit à des problèmes le long des lignes de "toute la mémoire se retrouve maintenant dans ce seul thread qui collecte et libère les informations de nombreux autres threads, et tous les autres threads sont à court de mémoire")