Les bases de Futex

Futex (futex - abréviation de "Fast userspace mutex") est un mécanisme proposé par les développeurs Linux d'IBM en 2002 et entré dans le noyau fin 2003. L'idée principale était de fournir un moyen plus efficace de synchroniser les threads utilisateur avec un nombre minimum d'appels au noyau du système d'exploitation.

Dans cet article, nous allons passer en revue les futex, essayer de comprendre les principes de leur travail et les utiliser également comme briques pour construire des objets de synchronisation de niveau supérieur (et qui nous sont familiers).

Un point important: les futexes sont un outil de bas niveau; il vaut la peine de l'utiliser directement uniquement lors du développement de bibliothèques fondamentales, comme la bibliothèque standard C / C ++. Il est très peu probable que vous ayez besoin d'utiliser des futex dans une application régulière.

La motivation

Avant l'avènement des futex, il était nécessaire de faire des appels système (en utilisant, par exemple, semop ) à chaque fois pour contrôler l'accès aux ressources partagées à partir de plusieurs threads, ce qui, comme vous le savez, est gourmand en ressources, car chaque appel nécessite de basculer le contexte du mode utilisateur vers le mode noyau. Avec l'augmentation du nombre de cœurs dans les processeurs modernes et l'augmentation du nombre de threads dans les logiciels d'application, cela est devenu un problème important. C'est encore plus «offensant», étant donné que tous ces appels ne portent aucune fonction appliquée, ne mettent en œuvre aucune logique métier, mais garantissent uniquement le bon fonctionnement du reste du code.

La proposition d'ajouter un nouveau concept de «futex» au système d'exploitation reposait sur une simple observation: dans la plupart des cas, une tentative de capture d'un objet de synchronisation réussit la première fois. Les programmeurs écrivent le logiciel de manière à ce que le plus de temps possible passe du verrouillage au déverrouillage, ce qui signifie qu'il y a de très grandes chances qu'une tentative de capture d'un autre thread ne rencontre pas d'obstacles. Lorsqu'un flux atteint un tel objet de synchronisation «gratuit», nous pouvons le capturer sans effectuer d'appel système en utilisant des opérations atomiques relativement bon marché. Et il y a de très grandes chances que l'opération atomique réussisse.

Dans ce cas rare, lorsque nous essayons toujours d'accéder à une ressource bloquée par un autre thread, une opération atomique renvoie une erreur. Dans ce cas, nous avons deux options. Nous pouvons soit tourner dans un spin-lock du mode utilisateur, en attendant la libération de la ressource (qui va manger les ressources CPU), soit demander au noyau de nous mettre en mode veille, en attendant la libération de la ressource. C'est là que les futex entrent en scène.

Utilisation simple des futex - attente et éveil

L'appel système futex combine une grande variété de fonctionnalités. Nous ne considérerons pas ici les options complexes (certaines d'entre elles sont si élaborées qu'elles ne sont même pas décrites dans la documentation officielle), mais nous nous concentrerons sur les opérations FUTEX_WAIT et FUTEX_WAKE. La description dans la documentation officielle servira de bonne base:

L'appel système futex () fournit aux programmes une méthode pour attendre qu'une certaine condition devienne vraie. En règle générale, cet appel système utilise une construction de blocage dans le contexte de la synchronisation de la mémoire partagée. Lors de l'utilisation de futex, les principales opérations de synchronisation sont effectuées dans l'espace utilisateur. Les programmes de l'espace utilisateur exécutent l'appel système futex () uniquement lorsqu'il est nécessaire que le programme passe en mode veille pendant une longue période jusqu'à ce que la condition devienne vraie. En outre, futex () peut être utilisé pour réveiller des processus ou des threads qui attendent une condition spécifique.

Autrement dit, un futex est une construction de noyau qui aide le code utilisateur à synchroniser les threads en cas de problème. Certains processus (ou threads) peuvent attendre des événements dans un appel FUTEX_WAIT, tandis que d'autres peuvent appeler ces événements avec FUTEX_WAKE. L'attente fonctionne efficacement - les threads en attente sont suspendus par le noyau et n'utilisent pas les ressources du processeur jusqu'à ce qu'ils soient réveillés lorsqu'un événement attendu se produit.

Prenez le temps de lire la documentation dans son intégralité. Eh bien, ou du moins lisez les sections sur FUTEX_WAIT et FUTEX_WAKE.

Regardons un exemple simple qui montre l'utilisation de base des futex pour coordonner le travail de deux processus.

Processus enfant:

1. Attend 0xA dans l'emplacement de mémoire général
2. Écrit la valeur 0xB dans cet emplacement

Processus parent à ce moment:

1. Écrit une valeur 0xA dans un emplacement de mémoire partagée
2. Attend que 0xB y apparaisse

Une telle «poignée de main» entre deux processus. Voici le code:

int main(int argc, char** argv) { int shm_id = shmget(IPC_PRIVATE, 4096, IPC_CREAT | 0666); if (shm_id < 0) { perror("shmget"); exit(1); } int* shared_data = shmat(shm_id, NULL, 0); *shared_data = 0; int forkstatus = fork(); if (forkstatus < 0) { perror("fork"); exit(1); } if (forkstatus == 0) { //   printf("child waiting for A\n"); wait_on_futex_value(shared_data, 0xA); printf("child writing B\n"); //  0xB         *shared_data = 0xB; wake_futex_blocking(shared_data); } else { //   printf("parent writing A\n"); //  0xA         *shared_data = 0xA; wake_futex_blocking(shared_data); printf("parent waiting for B\n"); wait_on_futex_value(shared_data, 0xB); // Wait for the child to terminate. wait(NULL); shmdt(shared_data); } return 0; } 

Faites attention aux appels POSIX pour allouer la mémoire partagée entre les processus. Nous ne pouvions pas utiliser l'allocation de mémoire habituelle ici, car même la même adresse de pointeurs dans différents processus pointerait en fait vers des blocs de mémoire différents (uniques à chaque processus).

Il convient de noter que cet exemple s'écarte quelque peu des canons, car le futex a été créé à l'origine pour attendre un changement dans une certaine signification «de quelque chose de spécifique à n'importe quoi», et non «de quelque chose à quelque chose de spécifique». J'ai donné cet exemple afin de démontrer une telle possibilité, et ci-dessous nous considérerons la version de base (sur elle nous implémentons le mutex).

Et voici le code de la fonction wait_on_futex_value:

 void wait_on_futex_value(int* futex_addr, int val) { while (1) { int futex_rc = futex(futex_addr, FUTEX_WAIT, val, NULL, NULL, 0); if (futex_rc == -1) { if (errno != EAGAIN) { perror("futex"); exit(1); } } else if (futex_rc == 0) { if (*futex_addr == val) { //    return; } } else { abort(); } } } 

La tâche principale de cette fonction (en plus, en fait, l'appel système futex) est un cycle dans lequel nous nous exécutons lorsque nous nous réveillons faux (ne nous intéressant pas). Cela peut se produire lorsqu'une nouvelle valeur, mais non attendue par nous, est installée dans l'emplacement de mémoire partagée. Eh bien, ou dans le cas où un autre processus a été réveillé plus tôt que le nôtre (cela ne peut pas arriver dans notre cas particulier, mais d'une manière plus générale c'est possible).

La sémantique de Futex est assez compliquée! L'appel FUTEX_WAIT retournera immédiatement si la valeur à l'adresse futex n'est pas égale à l'argument passé val. Dans notre cas, cela peut se produire si le processus enfant attendait avant que le parent n'écrive la valeur 0xA dans l'emplacement. Dans ce cas, le futex renvoie la valeur EAGAIN.

Et voici le code de la fonction wake_futex_blocking:

 void wake_futex_blocking(int* futex_addr) { while (1) { int futex_rc = futex(futex_addr, FUTEX_WAKE, 1, NULL, NULL, 0); if (futex_rc == -1) { perror("futex wake"); exit(1); } else if (futex_rc > 0) { return; } } } 

Il s'agit d'un wrapper de blocage sur FUTEX_WAKE qui fonctionnera rapidement et renverra une valeur, quel que soit le nombre d'auditeurs qui l'attendent. Dans notre exemple, cela est utilisé dans le cadre d'une «poignée de main», mais d'autres utilisations sont possibles.

Les Futex sont des files d'attente du noyau pour du code personnalisé.

Autrement dit, un futex est une file d'attente gérée par le noyau pour résoudre des tâches de code personnalisées. Il permet au code utilisateur de demander au noyau de suspendre l'exécution de son thread jusqu'à ce qu'un événement se produise, et à l'autre thread en même temps de signaler cet événement et de réveiller tous les threads qui l'attendent. Plus tôt, nous avons mentionné la possibilité d'organiser un verrou tournant en mode utilisateur, en attendant que certaines conditions soient remplies. Cependant, la file d'attente dans le noyau est une bien meilleure alternative, car elle nous évite des milliards d'instructions de processeur gaspillées exécutées dans une boucle d'attente.

Voici le schéma de l'article «Un aperçu et une mise à jour du futex » sur LWN:



Dans le code du noyau Linux, les futex sont implémentés dans le fichier kernel / futex.c. Le noyau stocke une table de hachage où les clés sont des adresses - pour trouver rapidement la file d'attente souhaitée et y ajouter le processus d'appel. Bien sûr, tout n'est pas si simple - après tout, le noyau lui-même doit synchroniser l'accès aux données à l'intérieur, et prendre en charge toutes sortes d'options supplémentaires pour futeksov.

Attente limitée dans le temps avec FUTEX_WAIT

L'appel système futex a un paramètre de délai d'attente qui permet à l'utilisateur de spécifier combien de temps il est prêt à attendre. Voici un exemple complet où cela est mis en œuvre, mais voici la partie clé:

 printf("child waiting for A\n"); struct timespec timeout = {.tv_sec = 0, .tv_nsec = 500000000}; while (1) { unsigned long long t1 = time_ns(); int futex_rc = futex(shared_data, FUTEX_WAIT, 0xA, &timeout, NULL, 0); printf("child woken up rc=%d errno=%s, elapsed=%llu\n", futex_rc, futex_rc ? strerror(errno) : "", time_ns() - t1); if (futex_rc == 0 && *shared_data == 0xA) { break; } } 

Si l'attente est retardée de 500 ms, la fonction futex se terminera et à la prochaine itération de la boucle, nous pourrons en quelque sorte réagir à cela (afficher quelque chose à l'écran, écrire dans le journal, continuer l'attente ou arrêter).

Utiliser un futex pour implémenter un mutex

Nous avons commencé cet article avec le fait que les futex sont d'une utilité pratique dans l'implémentation d'objets de synchronisation de niveau supérieur. Essayons de les utiliser (ainsi que atomiques) pour implémenter le mutex classique. L'implémentation ci-dessous est basée sur le code de l'article «Futexes are Tricky» écrit par Ulrich Drepper.

Pour cet exemple, j'utilise C ++, principalement pour la capacité à utiliser atomics de la norme C ++ 11. Vous pouvez trouver le code complet ici , mais la partie la plus importante est:

 class Mutex { public: Mutex() : atom_(0) {} void lock() { int c = cmpxchg(&atom_, 0, 1); // If the lock was previously unlocked, there's nothing else for us to do. // Otherwise, we'll probably have to wait. if (c != 0) { do { // If the mutex is locked, we signal that we're waiting by setting the // atom to 2. A shortcut checks is it's 2 already and avoids the atomic // operation in this case. if (c == 2 || cmpxchg(&atom_, 1, 2) != 0) { // Here we have to actually sleep, because the mutex is actually // locked. Note that it's not necessary to loop around this syscall; // a spurious wakeup will do no harm since we only exit the do...while // loop when atom_ is indeed 0. syscall(SYS_futex, (int*)&atom_, FUTEX_WAIT, 2, 0, 0, 0); } // We're here when either: // (a) the mutex was in fact unlocked (by an intervening thread). // (b) we slept waiting for the atom and were awoken. // // So we try to lock the atom again. We set teh state to 2 because we // can't be certain there's no other thread at this exact point. So we // prefer to err on the safe side. } while ((c = cmpxchg(&atom_, 0, 2)) != 0); } } void unlock() { if (atom_.fetch_sub(1) != 1) { atom_.store(0); syscall(SYS_futex, (int*)&atom_, FUTEX_WAKE, 1, 0, 0, 0); } } private: // 0 means unlocked // 1 means locked, no waiters // 2 means locked, there are waiters in lock() std::atomic<int> atom_; }; 

Dans ce code, la fonction cmpxhg est un simple wrapper pour une utilisation plus pratique des atomes:

 // An atomic_compare_exchange wrapper with semantics expected by the paper's // mutex - return the old value stored in the atom. int cmpxchg(std::atomic<int>* atom, int expected, int desired) { int* ep = &expected; std::atomic_compare_exchange_strong(atom, ep, desired); return *ep; } 

Cet exemple de code contient de nombreux commentaires expliquant la logique de son fonctionnement. Cela ne fera pas de mal, car il existe un risque important que vous souhaitiez en écrire une version légèrement plus simple, mais complètement incorrecte. Quant à ce code - il n'est pas non plus parfait en tout. Par exemple, il essaie de faire une hypothèse sur un périphérique interne de type std :: atomic, en castant son contenu en int * pour le passer à l'appel futex. Ce n'est généralement pas le cas. Le code se compile et s'exécute sur Linux x64, mais nous n'avons aucune garantie de compatibilité avec d'autres plates-formes. Pour l'obtenir, nous devons ajouter une couche de dépendance de plate-forme pour les atomes. Comme ce n'est pas le sujet de cet article (et aussi parce qu'il est très peu probable que vous mélangiez des futex dans un module C ++), nous omettons cette implémentation. Ce n'est qu'une démonstration!

Mutibes Glibc et verrous de bas niveau

Nous sommes donc arrivés au point où la glibc implémente les threads POSIX, dont une partie est le type pthread_mutex_t. Comme je l'ai dit au début de cet article, les futex ne sont pas tout à fait ce dont un développeur ordinaire aura besoin. Ils sont utilisés par les bibliothèques d'exécution ou quelque chose de très spécialisé pour implémenter des primitives de synchronisation de niveau supérieur. Dans ce contexte, il est intéressant d'examiner la mise en œuvre du mutex pour NPTL . Dans le code glibc, il s'agit du fichier nptl / pthread_mutex_lock.c.

Le code est assez compliqué en raison de la nécessité de prendre en charge différents types de mutex, mais nous pouvons trouver des blocs assez familiers si vous le souhaitez. Vous pouvez également consulter les fichiers sysdeps / unix / sysv / linux / x86_64 / lowlevellock.h et nptl / lowlevellock.c. Le code est quelque peu déroutant, mais la combinaison d'appels de comparaison et d'échange et de futex est toujours facile.

Le commentaire initial du fichier systeds / nptl / lowlevellock.h doit déjà être bien compris par vous:

 /* Low-level locks use a combination of atomic operations (to acquire and release lock ownership) and futex operations (to block until the state of a lock changes). A lock can be in one of three states: 0: not acquired, 1: acquired with no waiters; no other threads are blocked or about to block for changes to the lock state, >1: acquired, possibly with waiters; there may be other threads blocked or about to block for changes to the lock state. We expect that the common case is an uncontended lock, so we just need to transition the lock between states 0 and 1; releasing the lock does not need to wake any other blocked threads. If the lock is contended and a thread decides to block using a futex operation, then this thread needs to first change the state to >1; if this state is observed during lock release, the releasing thread will wake one of the potentially blocked threads. .. */ 

Go Futexes d'exécution

Rantime Go n'utilise pas libc (dans la plupart des cas). Ainsi, il ne peut pas s'appuyer sur l'implémentation de threads POSIX. Au lieu de cela, il appelle directement les appels système de niveau inférieur. Cela en fait un bon exemple d'utilisation des futex. Puisqu'il n'y a aucun moyen d'appeler pthread_mutex_t, vous devez écrire votre propre remplacement. Voyons comment cela se fait, commençons par le type sync.Mutex visible par l'utilisateur (dans src / sync / mutex.go).

La méthode Lock de ce type tente d'utiliser l'opération de permutation atomique pour capturer rapidement le verrou. S'il s'avère que vous devez attendre, il appelle runtime_SemacquireMutex, qui appelle runtime.lock. Cette fonction est définie dans src / runtime / lock_futex.go et elle déclare plusieurs constantes qui peuvent vous sembler familières:

 const ( mutex_unlocked = 0 mutex_locked = 1 mutex_sleeping = 2 ... ) // Possible lock states are mutex_unlocked, mutex_locked and mutex_sleeping. // mutex_sleeping means that there is presumably at least one sleeping thread. 

runtime.lock tente également de capturer le verrou à l'aide d'une fonction atomique. Cela a du sens, car runtime.lock est appelé à de nombreux endroits de l'exécution Go, mais il me semble qu'il serait possible d'optimiser le code en supprimant deux appels consécutifs de la fonction atomique lors de l'appel de runtime.lock à Mutex.lock.

S'il s'avère que vous devez attendre, la fonction dépendante de la plate-forme futexsleep est appelée, qui est définie pour Linux dans le fichier src / runtime / os_linux.go. Cette fonction effectue un appel système futex avec le code FUTEX_WAIT_PRIVATE (dans ce cas, cela convient, car le runtime Go vit dans un processus).