El mecanismo de futex (abreviatura de "Fast userspace mutex") fue propuesto por Linux
colaboradores de IBM en 2002; Fue integrado en el núcleo a finales de 2003.
La idea principal es habilitar una forma más eficiente para que el código del espacio de usuario
sincronice varios subprocesos, con una participación mínima del kernel.
En esta publicación, deseo proporcionar una descripción básica de los futexes, cómo funcionan y
cómo se utilizan para implementar las primitivas de sincronización más familiares en
API e idiomas de nivel superior.
Un descargo de responsabilidad importante: los futexes son una característica de muy bajo nivel de Linux
kernel, adecuado para su uso en componentes de tiempo de ejecución fundamentales como C / C ++
bibliotecas estándar. Es extremadamente improbable que alguna vez necesites
úselos en el código de la aplicación.
Motivación
Antes de la introducción de futexes, se requerían llamadas al sistema para bloquear y
desbloqueo de recursos compartidos (por ejemplo semop ). Las llamadas al sistema son relativamente
caro, sin embargo, requiere un cambio de contexto del espacio de usuario al espacio de kernel;
a medida que los programas se volvieron cada vez más concurrentes, los bloqueos comenzaron a aparecer
Perfiles como un porcentaje significativo del tiempo de ejecución. Esto es muy desafortunado,
Dado que los bloqueos no realizan ningún trabajo real ("lógica de negocios") sino que solo están allí
para garantizar que el acceso a los recursos compartidos sea seguro.
La propuesta de futex se basa en una observación inteligente: en la mayoría de los casos, los bloqueos son
En realidad no se sostiene. Si un hilo entra en un bloqueo libre, bloquearlo
puede ser barato porque lo más probable es que ningún otro hilo esté intentando bloquearlo en el
exactamente el mismo tiempo . Así que podemos sobrevivir sin una llamada al sistema, intentando mucho más barato.
Operaciones atómicas primero. Hay una posibilidad muy alta de que el atómico
Sin embargo, en el improbable caso de que otra hebra intentara tomar el bloqueo en
Al mismo tiempo, el enfoque atómico puede fallar. En este caso hay dos opciones.
Podemos realizar un bucle de ocupado utilizando el atómico hasta que se borre el bloqueo; mientras que esto es 100%
espacio de usuario, también puede ser un gran desperdicio ya que los bucles pueden
ocupar un núcleo, y la cerradura se puede mantener durante mucho tiempo. La alternativa es
"dormir" hasta que la cerradura esté libre (o al menos hay una alta probabilidad de que sea
gratis); necesitamos el kernel para ayudar con eso, y aquí es donde entran los futex.
Uso de futex simple: espera y activación
El futex (2) sistema call
multiplexa una gran cantidad de funcionalidades sobre una única interfaz. no lo haré
discuta cualquiera de las opciones avanzadas aquí (algunas de ellas son tan esotéricas que son
ni siquiera documentado oficialmente) pero se centrará solo en FUTEX_WAIT y
FUTEX_WAKE . La descripción de la página de manual comienza con una buena introducción:
La llamada al sistema futex () proporciona un método para esperar hasta cierto momento.
la condición se hace realidad. Normalmente se utiliza como una construcción de bloqueo
en el contexto de la sincronización de memoria compartida. Cuando se usan futexes,
La mayoría de las operaciones de sincronización se realizan en usuario.
espacio. Un programa de espacio de usuario emplea la llamada al sistema futex ()
Cuando es probable que el programa tenga que bloquear por un tiempo más largo.
hasta que la condición se haga realidad. Otras operaciones futex () pueden ser
Se utiliza para activar cualquier proceso o subprocesos que esperan un determinado
En pocas palabras, un futex es una construcción del núcleo que ayuda al código de espacio de usuario
sincronizar en eventos compartidos. Algunos procesos del espacio de usuario (o hilos) pueden esperar
un evento ( FUTEX_WAIT ), mientras que otro proceso de espacio de usuario puede señalar el evento
( FUTEX_WAKE ) para notificar a los meseros. La espera es eficiente – los camareros son
suspendidos por el núcleo y solo se programan de nuevo cuando hay un despertar
señal
Asegúrese de leer la página de manual futex más allá de la introducción; entradas de blog
¡No son sustitutos de la documentación! Por lo menos leer sobre el
FUTEX_WAIT y FUTEX_WAKE llamadas, los argumentos que toman, su retorno
valores y posibles errores.
Estudiemos un ejemplo simple
Demostrando el uso básico de futexes para coordinar dos procesos. El principal
La función configura la maquinaria y lanza un proceso secundario que:
- Espera a que 0xA se escriba en una ranura de memoria compartida.
- Escribe 0xB en la misma ranura de memoria.
Mientras tanto, el padre:
- Escribe 0xA en la ranura de memoria compartida.
- Espera a que 0xB se escriba en la ranura.
Esta es una Apretón de manos simple entre dos procesos. Aquí está el código:
int main ( int argc char ** argv ) {[19659031] int shm_id = shmget ( IPC_PRIVATE [1965902233]] ] ].
if ( shm_id < 0 ) {
perror ( "shmget" ); 19659051] exit ( 1 );
}
int * shared_data shmat shmat 19659024] ] NULL 0 );
* shared_data = 0 ] [
int forkstatus ] forkstatus ] forkstatus forkstatus ] forkstatus forkstatus ] forkstatus ] = fork ();
if ( forkstatus < 0 ) {
perror "horquilla" );
salida ([19659057] 1 );
}
if ( forkstatus == 0 ) {
// Child process [19659106] printf ( "niño esperando A n " );
wait_on_futex_value ]] ]);
printf ( "niño escribiendo B n " );
// Escriba 0xB a los datos compartidos y despierte al padre. [19659125] * shared_data = 0xB ;
wake_futex_blocking ([19659036)] shared [datos] []
]
]
] // Proceso padre.
printf ( "padre escribiendo A n " );
// Escribe 0xA a los datos compartidos y despierta al niño.
* shared_data = 0xA ;
wake_futex_blocking [196590106] printf ] [196590226] printf 19659053] "padre esperando a B n " );
wait_on_futex_value ( shared_data [196590116] 0xB ]. / Espere a que el niño termine.
espere ( NULL );
shmdt ( shared_data );
}
return 0 ;
}
Tenga en cuenta que utilizamos las API de memoria compartida POSIX para crear una ubicación de memoria asignada
en ambos procesos. No podemos simplemente usar un puntero regular aquí, porque el
los espacios de direcciones de los dos procesos serán diferentes.
Tenga en cuenta que esto no es un uso canónico de futex que sería mejor
empleado para esperar hasta que un valor cambie de algo en lugar de a
alguna cosa. Solo está aquí para mostrar las diversas posibilidades en los valores de retorno.
desde futex . Más adelante en la publicación se demuestra un uso más canónico cuando
implementa un mutex
Aquí está wait_on_futex_value :
void wait_on_fut_exp.nu.p.p.pf.ccPccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccgggggggggggggg
19659024] val ) {
mientras que ( 1 ) {
int futex_rc fut futex futex ] ( futex_addr FUTEX_WAIT val NULL 0 ] ] ]
if ( futex_rc == - 1 ) {
if errno ! = EAGAIN ) {
perror ( "futex" );
exit 1 1; ]}
} else if ( futex_rc == 0 ] ] [ ] [ ] [ ] ] [ ] ] [ ] [ ] [ ] [ ] [* futex_addr == [19659024] val ) {
// Esta es una activación real.
return ;
}
} else {
abort ();
}
}
}
El valor agregado principal de esta función en la parte superior de la llamada del sistema futex está en bucle
Alrededor cuando el despertar es espurio. Esto puede suceder cuando val no es el
valor esperado (todavía) y también cuando otro proceso se despertó antes de este
(Realmente no puede suceder en este ejemplo de código, pero es una posibilidad real en otros
escenarios).
¡La semántica de Futex es complicada! FUTEX_WAIT regresará inmediatamente si el
el valor en la dirección futex no es igual a val . En nuestro caso esto puede suceder.
si el niño emitió una espera antes de que el padre escribiera 0xA por ejemplo. los
futex call devolverá un error con EAGAIN en este caso.
Aquí está wake_futexpañador 19659023] int * futex_addr ) {
while ( 1 ] [196590199] int futex_pc = futex ( futex_addr FUTEX_WAKE 1 NULL 19659038] 0 );
if ( futex_rc == - 1 ) per
perror [1919659053] "futex wake" );
exit ( 1 );
} else if futex_rc ]> 0 ) {
return ;
}
}
}
Es un envoltorio de bloqueo alrededor de FUTEX_WAKE que normalmente regresará
Rápidamente sin importar cuántos camareros se haya despertado. En nuestra muestra, este
esperar es parte del apretón de manos, pero en muchos casos no lo verá.
Los futexes son colas de kernel para el código de espacio de usuario
En pocas palabras, un futex es una cola que el kernel administra para mayor comodidad.
Permite que el código del espacio de usuario le pida al kernel que suspenda hasta que se cumpla una determinada condición
satisfecho, y permite que otros códigos de espacio de usuario señalicen esa condición y se activen
Procesos de espera. Anteriormente hemos mencionado el ciclo de ocupado como un enfoque para esperar
en el éxito de las operaciones atómicas; Una cola gestionada por el kernel es mucho más.
alternativa eficiente, que elimina el código del espacio de usuario de la necesidad de quemar miles de millones
Aquí hay un diagrama de LWN "Un resumen de futex y actualización" :
En el kernel de Linux, futexes se implementan en kernel / futex.c . El kernel
mantiene una tabla hash tecleada por la dirección para encontrar rápidamente los datos de cola adecuados
estructura y agrega el proceso de llamada a la cola de espera. Hay un poco de
complicación, por supuesto, debido al uso de un bloqueo de grano fino dentro del núcleo
y las diversas opciones avanzadas de futexes.
Bloqueo temporizado con FUTEX_WAIT
El futex llamada al sistema tiene un parámetro tiempo de espera parámetro que permite el código de usuario
implementar esperando con un tiempo de espera.
La muestra futex-wait-wait-timeout
Muestra esto en acción. Aquí está la parte relevante del proceso hijo que espera.
en un futex:
printf ( "niño esperando A n " );
struct timespec timeout = {. tv_sec = 0 . tv_nsec = 500000000 ] [1965903499]] 1 ) {
unsigned long long t1 = time_ns int
int futex_r = futex ( shared_data FUTEX_WAIT 0xA ] ] ] NULL 0 );
printf ( "niño despertó rc =% d errno =% s, transcurrido =% llu n [19659053] " futex_rc
futex_rc ? strerror ] [] ]] ]] ]] ]] ] , time_ns () - [1 9659024] t1 );
if ( futex_rc == 0 && ) {
break ;
}
}
Si la espera dura más de 500 ms, el proceso se repetirá y esperará nuevamente. los
La muestra le permite configurar el tiempo que el proceso padre mantiene al hijo
esperando y observe los efectos.
Usando un futex para implementar un mutex simple
En la sección de motivación que comenzó esta publicación, expliqué cómo ayudan los futexes
Implementar bloqueo eficiente en el caso común de baja contienda. Es hora de mostrar
Una implementación realista de un mutex utilizando futexes y atómicos. Esto se basa
sobre la segunda implementación en el documento " Futexes are Tricky " de Ulrich Drepper.
Para esta muestra, voy a cambiar a C ++, para usar sus métodos atómicos estandarizados (disponibles
desde C ++ 11). El código completo está aquí ;
Aquí está la parte importante:
clase Mutex {
public :
Mutex () : atom_ ( 0 ) {}
void bloqueo () {
int c = cmpxchg & atom_ 0 1 );
// Si el bloqueo se desbloqueó previamente, no hay nada más que podamos hacer.
/ / De lo contrario, probablemente tendremos que esperar.
if ( c ! = 0 ) {
do ] // Si el mutex está bloqueado, le indicamos que estamos esperando configurando el
// átomo en 2. Un atajo es que ya está en 2 y evita la operación atómica
// en este caso. [19659258] if ( c == 2 || cmpxchg ( & atom_ 1] 19659022] 2 [19659022]) ! = 0 ) {
// Aquí tenemos que dormir realmente, porque el mutex está en realidad
// bloqueado. Tenga en cuenta que no es necesario hacer un bucle alrededor de este syscall;
// una activación falsa no hará ningún daño ya que solo salimos del do ... mientras que
// bucle cuando atom_ es de hecho 0.
syscall [19659022] ( SYS_futex ( int * )) at ] FUTEX_WAIT ] 2 0 0 0 );
}
// Estamos aquí cuando:
/ / (a) el mutex estaba de hecho desbloqueado (por un hilo intermedio).
// (b) dormimos esperando el átomo y nos despertaron.
//
// Así que tratamos de bloquear El átomo de nuevo. Establecimos el estado 2 en 2 porque
// no podemos estar seguros de que no haya otro hilo en este punto exacto. Entonces
// preferimos errar en el lado seguro.
} mientras que (([ c = cmpxchg & ] atom_ 0 2 ))) ! = 0 );
}
}
void [19659024] desbloqueo () {
if ( átomo [. fetch_sub ] [) [1965903333]! = [19659038] 1 ) {
atom_ . store ( 0 ); SYS_futex SYS_fut SYS_futex ] ( int * ) & atom_ FUTEX_WAKE 1, 0 0 );
}
}
private :
// 0 significa desbloqueado
// 1 significa bloqueado, sin camareros
// 2 significa bloqueado, hay camareros en lock ()
std [1 9659027] :: atomic < int > atom_ ;
};
Donde cmpxhg es un simple contenedor para indicar La primitiva atómica de C ++ a la
interfaz esperada:
// Una envoltura atomic_compare_exchange con semántica esperada por el artículo
// mutex - devuelve el valor antiguo almacenado en el átomo.
int cmpxchg std [19659027] :: atómica < int > * átomo int esperado int int 19659022]) {
int * ep = & espera ; atomic_compare_exichic ] ( átomo ep deseado );
return * ep [196590179]}
}
El fragmento de código está muy comentado para explicar cómo funciona; leyendo Drepper's
Se recomienda el papel en cualquier caso, ya que se acumula para esta implementación por
Primero examinando uno más simple que es sutilmente incorrecto. Un poco no kosher
Lo que hace este código es acceder a la representación interna de std :: atomic por
enviar la dirección de atom_ a int * al pasarla al futex
syscall Esto se debe a que futex espera una dirección simple, mientras que C ++ Atómica
envolver sus datos reales en tipos opacos. Esto funciona en Linux en x64, pero no es
generalmente portátil. Para que std :: atomic juegue bien con futex en una
portátiles tendríamos que añadir una capa de portabilidad. Pero no es una necesidad lo que surge.
en la práctica, mezclar futex con C ++ 11 no es algo que todos deberían hacer -
¡Estos fragmentos son solo demostrativos!
Una observación interesante es sobre el significado del valor que se encuentra en el
miembro atom_ . Recuerde que el futex syscall no asigna ningún
lo que significa el valor: es responsabilidad del usuario hacer eso. La convención 0,1,2 es
útil para mutexes, y también el utilizado por la implementación glibc para
bloqueos de bajo nivel.
glibc mutex y bloqueo de bajo nivel
Esto nos lleva a la implementación de glibc de subprocesos POSIX, que tienen la
pthread_mutex_t tipo. Como he mencionado al principio del post,
Los futexes no son realmente para el código de usuario regular; más bien, son utilizados por bajo nivel
tiempos de ejecución y bibliotecas para implementar otras primitivas de nivel superior. En esto
En este contexto, es interesante ver cómo se implementa un mutex para NPTL . En el glibc
árbol de origen, este código está en nptl / pthread_mutex_lock.c
El código se complica significativamente por todos los diferentes tipos de exclusión mutua.
tiene que soportar, pero podemos descubrir algunos bloques de construcción familiares si cavamos
suficientemente profundo. Además del archivo mencionado anteriormente, otros archivos para ver
(para x86) son sysdeps / unix / sysv / linux / x86_64 / lowlevellock.h y
nptl / lowlevellock.c . El código es denso, pero la combinación de atómica.
Las operaciones de comparación e intercambio y las invocaciones futex son evidentes.
La maquinaria de bloqueo de bajo nivel ( lll_ o LLL_ prefijos) se usa en todo
el código glibc no solo en la implementación de subprocesos POSIX.
El comienzo del comentario en la parte superior de sysdeps / nptl / lowlevellock.h
ya debería estar familiarizado:
/ * Los bloqueos de bajo nivel utilizan una combinación de operaciones atómicas (para adquirir y
liberar la propiedad del bloqueo) y las operaciones de futex (para bloquear hasta que cambie el estado
de un bloqueo). Un bloqueo puede estar en uno de tres estados:
0: no adquirido,
1: adquirido sin camareros; no hay otros subprocesos bloqueados o a punto de bloquear
para cambios en el estado de bloqueo,
> 1: adquirido, posiblemente con camareros; puede haber otros subprocesos bloqueados o
a punto de bloquear para cambios en el estado de bloqueo.
Esperamos que el caso común sea un bloqueo no contendido, por lo que solo necesitamos
para cambiar el bloqueo entre los estados 0 y 1 ; la liberación de la cerradura
no necesita despertar ningún otro subproceso bloqueado. Si el bloqueo se sostiene
y un subproceso decide bloquearlo mediante una operación futex, entonces este subproceso
debe primero cambiar el estado a> 1; si se observa este estado durante la liberación de bloqueo
el subproceso de liberación despertará uno de los subprocesos potencialmente bloqueados
.
..
* /
Futexes in the Go runtime
The Go el tiempo de ejecución no utiliza libc, en la mayoría de los casos. Por lo tanto, no puede confiar en
La implementación de subprocesos POSIX en su propio código. Invoca los sistemas operativos subyacentes.
el sistema llama directamente en su lugar.
Eso lo convierte en un buen candidato alternativo para estudiar su uso de futexes.
Como no puede usar un pthread_mutex_t para su bloqueo, tiene que rodar
su propia cerradura Veamos cómo se hace esto, comenzando con el usuario visible.
sync.Mutex tipo (en src / sync / mutex.go ).
El método Lock sync.Mutex es bastante involucrado, como puedes imaginar.
Primero intenta usar un intercambio atómico para adquirir rápidamente un bloqueo. Si resulta
tiene que esperar, difiere a runtime_SemacquireMutex que a su vez llama
runtime.lock . Esa función se define en src / runtime / lock_futex.go ,
y define algunas constantes que parecerán familiares:
const (
mutex_unlocked = 0
mutex_locked
mutex_locked
] 19659038] 2
...
)
// Los posibles estados de bloqueo son mutex_unlocked, mutex_locked y mutex_sleeping.
// mutex_sleeping significa que probablemente hay al menos un hilo para dormir.
runtime.lock también intenta agarrar especulativamente una cerradura con un atómico; esta
La función se utiliza en un montón de lugares en el tiempo de ejecución de Go, por lo que tiene sentido,
pero me pregunto si no podrían haber optimizado los dos atómicos consecutivos que
ocurre cuando es llamado por Mutex.lock de alguna manera.
Si descubre que tiene que dormir, difiere a futexsleep que es
El sistema operativo es específico y vive en src / runtime / os_linux.go . Esta función llama
invoca la llamada al sistema futex directamente con FUTEX_WAIT_PRIVATE
(recuerde que esto es suficiente para un solo proceso, que el tiempo de ejecución Go)
cumple).
No comments:
Post a Comment