Fundamentos de Futex

Futex (futex - abreviatura de "Fast userpace mutex") es un mecanismo propuesto por los desarrolladores de Linux de IBM en 2002 y entró en el núcleo a finales de 2003. La idea principal era proporcionar una forma más eficiente de sincronizar hilos de usuario con un número mínimo de llamadas al núcleo del sistema operativo.

En este artículo, revisaremos los futexes, trataremos de comprender los principios de su trabajo y también los utilizaremos como ladrillos para construir objetos de sincronización de nivel superior (y que nos son familiares).

Un punto importante: futexes es una herramienta de bajo nivel, vale la pena usarla directamente solo al desarrollar bibliotecas fundamentales, como la biblioteca estándar C / C ++. Es muy poco probable que necesite usar futexes en una aplicación normal.

Motivación

Antes del advenimiento de los futexes, era necesario hacer llamadas al sistema (usando, por ejemplo, semop ) cada vez para controlar el acceso a los recursos compartidos desde varios subprocesos, lo que, como saben, requiere muchos recursos, ya que cada llamada requiere cambiar el contexto del modo de usuario al modo kernel. Con el aumento en el número de núcleos en los procesadores modernos y el aumento en el número de hilos en el software de aplicación, esto se ha convertido en un problema importante. Es aún más "ofensivo", dado que todas estas llamadas no tienen ninguna función aplicada, no implementan ninguna lógica de negocios, sino que solo garantizan el correcto funcionamiento del resto del código.

La propuesta de agregar un nuevo concepto de "futex" al sistema operativo se basó en una simple observación: en la mayoría de los casos, un intento de capturar un objeto de sincronización es exitoso la primera vez. Los programadores escriben software de tal manera que pase el menor tiempo posible desde bloquear un bloqueo hasta desbloquearlo, lo que significa que hay muchas posibilidades de que un intento de capturar otro hilo no encuentre obstáculos. Cuando un flujo alcanza un objeto de sincronización "libre", podemos capturarlo sin hacer una llamada al sistema utilizando operaciones atómicas relativamente baratas. Y existe una gran posibilidad de que la operación atómica funcione con éxito.

En ese raro caso, cuando aún intentamos acceder a un recurso bloqueado por otro hilo, una operación atómica devolverá un error. En este caso, tenemos dos opciones. Podemos girar en algún bloqueo de giro del modo de usuario, esperando la liberación del recurso (que consumirá los recursos de la CPU), o pedirle al núcleo que nos ponga en modo de suspensión, esperando la liberación del recurso. Aquí es donde los futexes entran en escena.

Uso simple de futexes: expectativa y despertar

La llamada al sistema futex combina una gran variedad de funcionalidades. Aquí no consideraremos opciones complejas (algunas de ellas son tan elaboradas que ni siquiera se describen en la documentación oficial), sino que nos centraremos en las operaciones FUTEX_WAIT y FUTEX_WAKE. La descripción en la documentación oficial servirá como una buena base:

La llamada al sistema futex () proporciona a los programas un método para esperar a que se cumpla una determinada condición. Normalmente, esta llamada al sistema utiliza una construcción de bloqueo en el contexto de la sincronización de memoria compartida. Cuando se usan futexes, las operaciones de sincronización principales se realizan en el espacio del usuario. Los programas de espacio de usuario ejecutan la llamada al sistema futex () solo cuando es necesario que el programa entre en modo de espera durante un largo tiempo hasta que la condición se vuelva verdadera. Además, futex () se puede usar para activar procesos o subprocesos que esperan una condición específica.

En pocas palabras, un futex es una construcción del núcleo que ayuda al código del usuario a sincronizar hilos cuando sucede algo. Algunos procesos (o subprocesos) pueden esperar eventos en una llamada FUTEX_WAIT, mientras que otros pueden llamar a estos eventos con FUTEX_WAKE. La espera funciona de manera eficiente: el kernel suspende los subprocesos de espera y no utiliza los recursos del procesador hasta que se despiertan cuando ocurre un evento esperado.

Tómese el tiempo para leer la documentación en su totalidad. Bueno, o al menos lea las secciones sobre FUTEX_WAIT y FUTEX_WAKE.

Veamos un ejemplo simple que demuestra el uso básico de los futexes para coordinar el trabajo de dos procesos.

Proceso hijo:

1. Espera 0xA en la ranura de memoria general
2. Escribe el valor 0xB en este espacio

Proceso principal en este momento:

1. Escribe un valor 0xA en una ranura de memoria compartida
2. Espera a que aparezca 0xB en él

Tal "apretón de manos" entre dos procesos. Aquí está el código:

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; } 

Preste atención a las llamadas POSIX para asignar memoria compartida entre procesos. No podríamos usar la asignación de memoria habitual aquí, ya que incluso la misma dirección de punteros en diferentes procesos apuntaría realmente a diferentes bloques de memoria (únicos para cada proceso).

Cabe señalar que este ejemplo se desvía un poco de los cánones, porque el futex se creó originalmente para esperar un cambio en un cierto significado "de algo específico a cualquier cosa", y no "de algo a algo específico". Di este ejemplo para demostrar tal posibilidad, y a continuación consideraremos la versión básica (en ella implementamos el mutex).

Y aquí está el código de función 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 tarea principal de esta función (además, en realidad, la llamada al sistema futex) es un ciclo en el que corremos cuando nos despertamos en falso (no nos interesa). Esto puede suceder cuando se instala un nuevo valor, pero no esperado por nosotros, en la ranura de memoria compartida. Bueno, o en el caso de que otro proceso se haya despertado antes que el nuestro (esto no puede suceder en nuestro caso particular, pero de una manera más general es posible).

¡La semántica de Futex es bastante complicada! La llamada FUTEX_WAIT volverá inmediatamente si el valor en la dirección futex no es igual al argumento val valido. En nuestro caso, esto puede suceder si el proceso secundario fue a esperar antes de que el padre escribiera el valor 0xA en la ranura. El futex en este caso devuelve el valor EAGAIN.

Y aquí está el código de la función 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; } } } 

Este es un contenedor de bloqueo sobre FUTEX_WAKE que funcionará rápidamente y devolverá un valor, sin importar cuántos oyentes lo esperen. En nuestro ejemplo, esto se usa como parte de un "apretón de manos", pero son posibles otros usos.

Los futexes son colas de kernel para código personalizado.

En pocas palabras, un futex es una cola impulsada por el núcleo para resolver tareas de código personalizado. Permite que el código de usuario solicite al núcleo que suspenda la ejecución de su subproceso hasta que se produzca un evento, y al otro subproceso al mismo tiempo para señalar este evento y activar todos los subprocesos que lo esperan. Anteriormente mencionamos la capacidad de organizar un bloqueo de giro en modo de usuario, esperando que se cumpla alguna condición. Sin embargo, la cola en el núcleo es una alternativa mucho mejor, ya que nos salva de miles de millones de instrucciones de procesador desperdiciadas ejecutadas en un ciclo de espera.

Aquí está el diagrama del artículo "Descripción general y actualización de futex" en LWN:



En el código del kernel de Linux, los futexes se implementan en el archivo kernel / futex.c. El kernel almacena una tabla hash donde las claves son direcciones, para encontrar rápidamente la cola deseada y agregarle el proceso de llamada. Todo, por supuesto, no es tan simple: después de todo, el núcleo mismo necesita sincronizar el acceso a los datos internos, además de admitir todo tipo de opciones adicionales para futeksov.

Espera por tiempo limitado con FUTEX_WAIT

La llamada al sistema futex tiene un parámetro de tiempo de espera que permite al usuario especificar cuánto tiempo están listos para esperar. Aquí hay un ejemplo completo donde se implementa esto, pero aquí está la parte clave:

 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 la espera se retrasa 500 ms, entonces la función futex finalizará, y en la próxima iteración del ciclo podemos reaccionar de alguna manera a esto (mostrar algo en la pantalla, escribir en el registro, continuar la espera o detener).

Usando un futex para implementar un mutex

Comenzamos este artículo con el hecho de que los futexes son de uso práctico en la implementación de objetos de sincronización de nivel superior. Intentemos usarlos (así como los atómicos) para implementar el mutex clásico. La implementación a continuación se basa en el código del artículo "Futexes are Tricky" escrito por Ulrich Drepper.

Para este ejemplo, uso C ++, principalmente por la capacidad de usar atómicos del estándar C ++ 11. Puede encontrar el código completo aquí , pero la parte más importante es:

 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_; }; 

En este código, la función cmpxhg es un contenedor simple para un uso más conveniente de los átomos:

 // 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; } 

Este ejemplo de código contiene muchos comentarios que explican la lógica de su funcionamiento. Esto no afectará, porque existe un riesgo significativo de que desee escribir una versión un poco más simple pero completamente incorrecta. En cuanto a este código, tampoco es perfecto en todo. Por ejemplo, intenta hacer una suposición sobre un dispositivo interno del tipo std :: atomic, enviando su contenido a int * para pasar a la llamada futex. Este generalmente no es el caso. El código se compila y se ejecuta en Linux x64, pero no tenemos garantía de compatibilidad con otras plataformas. Para obtenerlo, necesitamos agregar una capa de dependencia de plataforma para los átomos. Como este no es el tema de este artículo (y también porque es muy poco probable que mezcle futexes en el mismo módulo C ++), omitiremos esta implementación. ¡Esto es solo una demostración!

Mutexes Glibc y cerraduras de bajo nivel

Entonces llegamos al punto donde glibc implementa hilos POSIX, parte del cual es el tipo pthread_mutex_t. Como dije al comienzo de este artículo, los futexes no son lo que un desarrollador ordinario necesitará. Los utilizan las bibliotecas de tiempo de ejecución o algo muy especializado para implementar primitivas de sincronización de nivel superior. En este contexto, es interesante observar la implementación del mutex para NPTL . En el código glibc, este es el archivo nptl / pthread_mutex_lock.c.

El código es bastante complicado debido a la necesidad de admitir varios tipos de mutexes, pero podemos encontrar bloques bastante familiares si lo desea. También puede echar un vistazo a los archivos sysdeps / unix / sysv / linux / x86_64 / lowlevellock.h y nptl / lowlevellock.c. El código es algo confuso, pero aún así la combinación de comparar e intercambiar y llamadas futex es fácil.

El comentario inicial del archivo systeds / nptl / lowlevellock.h ya debe ser bien entendido por usted:

 /* 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. .. */ 

Ir en tiempo de ejecución futexes

Rantime Go no usa libc (en la mayoría de los casos). Por lo tanto, no puede confiar en la implementación de hilos POSIX. En cambio, llama directamente a las llamadas del sistema de nivel inferior. Esto lo convierte en un buen ejemplo de uso de futexes. Como no hay forma de llamar a pthread_mutex_t, debe escribir su propio reemplazo. Veamos cómo se hace esto, comencemos con el tipo sync.Mutex visible para el usuario (en src / sync / mutex.go).

El método de bloqueo de este tipo intenta utilizar la operación de intercambio atómico para capturar rápidamente el bloqueo. Si resulta que necesita esperar, llama a runtime_SemacquireMutex, que llama a runtime.lock. Esta función se define en src / runtime / lock_futex.go y declara varias constantes que pueden resultarle familiares:

 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 también está tratando de capturar el bloqueo usando una función atómica. Esto tiene sentido, ya que runtime.lock se llama en muchos lugares del tiempo de ejecución Go, pero me parece que sería posible optimizar de alguna manera el código eliminando dos llamadas consecutivas de la función atómica al llamar a runtime.lock desde Mutex.lock.

Si resulta que necesita esperar, se llama a la función dependiente de la plataforma futexsleep, que se define para Linux en el archivo src / runtime / os_linux.go. Esta función realiza una llamada al sistema futex con el código FUTEX_WAIT_PRIVATE (en este caso, esto es adecuado, ya que el tiempo de ejecución Go vive en un proceso).