¿Qué tan eficiente es bloquear un mutex desbloqueado? ¿Cuál es el costo de un mutex?

En un lenguaje de bajo nivel (C, C ++ o lo que sea): tengo la opción de elegir entre tener un montón de mutexes (como lo que me da pthread o lo que proporcione la biblioteca del sistema nativo) o uno solo para un objeto.

¿Qué tan eficiente es bloquear un mutex? Es decir, ¿cuántas instrucciones de ensamblador existen y cuánto tiempo toman (en caso de que el mutex esté desbloqueado)?

¿Cuánto cuesta un mutex? ¿Es un problema tener realmente muchos mutexes? ¿O puedo simplemente arrojar tantas variables mutex en mi código como tengo intvariables y realmente no importa?

(No estoy seguro de cuántas diferencias hay entre hardware diferente. Si las hay, también me gustaría saber sobre ellas. Pero sobre todo, estoy interesado en hardware común).

El punto es que, al usar muchos mutex que cubren solo una parte del objeto en lugar de un solo mutex para todo el objeto, podría proteger muchos bloques. Y me pregunto qué tan lejos debería llegar sobre esto. Es decir, ¿debería tratar de proteger cualquier posible bloqueo realmente en la medida de lo posible, sin importar cuánto más complicado y cuántos mutexes más esto significa?

La publicación de blog de WebKits (2016) sobre el bloqueo está muy relacionada con esta pregunta y explica las diferencias entre un spinlock, un bloqueo adaptativo, futex, etc.

Tengo la opción entre tener un montón de mutexes o uno solo para un objeto.

Si tiene muchos hilos y el acceso al objeto ocurre con frecuencia, entonces los bloqueos múltiples aumentarían el paralelismo. A costa de la mantenibilidad, ya que más bloqueo significa más depuración del bloqueo.

¿Qué tan eficiente es bloquear un mutex? Es decir, ¿cuántas instrucciones de ensamblador hay y cuánto tiempo toman (en caso de que el mutex esté desbloqueado)?

Las instrucciones precisas del ensamblador son la menor sobrecarga de un mutex : las garantías de coherencia de memoria / caché son la sobrecarga principal. Y con menos frecuencia se toma una cerradura particular, mejor.

Mutex se compone de dos partes principales (simplificación excesiva): (1) un indicador que indica si el mutex está bloqueado o no y (2) espera en cola.

El cambio de bandera es solo unas pocas instrucciones y normalmente se realiza sin una llamada al sistema. Si mutex está bloqueado, syscall agregará el hilo de llamada a la cola de espera y comenzará la espera. El desbloqueo, si la cola de espera está vacía, es barato, pero necesita una llamada al sistema para activar uno de los procesos de espera. (En algunos sistemas, se utilizan syscalls baratos / rápidos para implementar los mutexes, se convierten en llamadas lentas (normales) del sistema solo en caso de contención).

Bloquear mutex desbloqueado es realmente barato. Desbloquear mutex sin contención también es barato.

¿Cuánto cuesta un mutex? ¿Es un problema tener realmente muchos mutexes? ¿O puedo simplemente arrojar tantas variables mutex en mi código como tengo variables int y realmente no importa?

Puede incluir tantas variables mutex en su código como desee. Solo está limitado por la cantidad de memoria que su aplicación puede asignar.

Resumen. Los bloqueos de espacio de usuario (y los mutexes en particular) son baratos y no están sujetos a ningún límite del sistema. Pero demasiados de ellos significan pesadilla para la depuración. Tabla simple:

1. Menos bloqueos significa más contenciones (llamadas de sistema lentas, paradas de CPU) y menor paralelismo
2. Menos bloqueos significa menos problemas para depurar problemas de subprocesos múltiples.
3. Más bloqueos significa menos contenciones y mayor paralelismo
4. Más bloqueos significa más posibilidades de toparse con callejones sin salida.

Se debe encontrar y mantener un esquema de bloqueo equilibrado para la aplicación, generalmente equilibrando el # 2 y el # 3.

(*) El problema con mutexes bloqueados con menos frecuencia es que si tiene demasiado bloqueo en su aplicación, hace que gran parte del tráfico entre CPU / núcleo elimine la memoria mutex del caché de datos de otras CPU para garantizar coherencia de caché. Los enjuagues de caché son como interrupciones ligeras y manejados por CPU de manera transparente, pero introducen los denominados bloqueos (busque "bloqueo").

Y las paradas son las que hacen que el código de bloqueo se ejecute lentamente, a menudo sin ninguna indicación aparente de por qué la aplicación es lenta. (Algunos archivos proporcionan las estadísticas de tráfico entre CPU / núcleo, otros no).

Para evitar el problema, las personas generalmente recurren a un gran número de bloqueos para disminuir la probabilidad de contenciones de bloqueos y evitar el bloqueo. Esa es la razón por la cual existe el bloqueo de espacio de usuario barato, no sujeto a los límites del sistema.

Quería saber lo mismo, así que lo medí. En mi caja (procesador AMD FX (tm) -8150 de ocho núcleos a 3.612361 GHz), bloquear y desbloquear un mutex desbloqueado que está en su propia línea de caché y ya está en caché, toma 47 relojes (13 ns).

Debido a la sincronización entre dos núcleos (utilicé CPU # 0 y # 1), solo pude llamar a un par de bloqueo / desbloqueo una vez cada 102 ns en dos subprocesos, por lo que una vez cada 51 ns, de lo que se puede concluir que toma aproximadamente 38 ns para recuperarse después de que un hilo se desbloquea antes de que el siguiente hilo pueda bloquearlo nuevamente.

El programa que utilicé para investigar esto se puede encontrar aquí: https://github.com/CarloWood/ai-statefultask-testsuite/blob/b69b112e2e91d35b56a39f41809d3e3de2f9e4b8/src/mutex_test.cxx

Tenga en cuenta que tiene algunos valores codificados específicamente para mi cuadro (xrange, yrange y rdtsc de arriba), por lo que probablemente tenga que experimentar con él antes de que funcione para usted.

El gráfico que produce en ese estado es:

Esto muestra el resultado de las ejecuciones de referencia en el siguiente código:

uint64_t do_Ndec(int thread, int loop_count)
{
  uint64_t start;
  uint64_t end;
  int __d0;

  asm volatile ("rdtsc\n\tshl $32, %%rdx\n\tor %%rdx, %0" : "=a" (start) : : "%rdx");
  mutex.lock();
  mutex.unlock();
  asm volatile ("rdtsc\n\tshl $32, %%rdx\n\tor %%rdx, %0" : "=a" (end) : : "%rdx");
  asm volatile ("\n1:\n\tdecl %%ecx\n\tjnz 1b" : "=c" (__d0) : "c" (loop_count - thread) : "cc");
  return end - start;
}

Las dos llamadas rdtsc miden la cantidad de relojes necesarios para bloquear y desbloquear 'mutex' (con una sobrecarga de 39 relojes para las llamadas rdtsc en mi casilla). El tercer asm es un bucle de retraso. El tamaño del bucle de retardo es 1 recuento menor para el subproceso 1 que para el subproceso 0, por lo que el subproceso 1 es ligeramente más rápido.

La función anterior se llama en un ciclo cerrado de tamaño 100,000. A pesar de que la función es ligeramente más rápida para el subproceso 1, ambos bucles se sincronizan debido a la llamada al mutex. Esto es visible en el gráfico por el hecho de que el número de relojes medidos para el par de bloqueo / desbloqueo es ligeramente mayor para el hilo 1, para tener en cuenta el retraso más corto en el bucle debajo de él.

En el gráfico anterior, el punto inferior derecho es una medición con un retraso loop_count de 150, y luego, siguiendo los puntos en la parte inferior, hacia la izquierda, el loop_count se reduce en uno en cada medición. Cuando se convierte en 77, la función se llama cada 102 ns en ambos hilos. Si posteriormente loop_count se reduce aún más, ya no es posible sincronizar los subprocesos y el mutex comienza a bloquearse la mayor parte del tiempo, lo que resulta en una mayor cantidad de relojes que se necesitan para bloquear / desbloquear. Además, el tiempo promedio de la llamada a la función aumenta debido a esto; entonces los puntos de la trama ahora suben y vuelven a la derecha nuevamente.

De esto podemos concluir que bloquear y desbloquear un mutex cada 50 ns no es un problema en mi caja.

En general, mi conclusión es que la respuesta a la pregunta de OP es que agregar más mutexes es mejor siempre que eso resulte en menos contención.

Intente bloquear mutexes lo más corto posible. La única razón para colocarlos, digamos, fuera de un bucle sería si ese bucle se repite más rápido que una vez cada 100 ns (o más bien, el número de subprocesos que desean ejecutar ese bucle al mismo tiempo multiplicado por 50 ns) o cuando 13 ns veces el tamaño del bucle es más demorado que el retraso que se obtiene por contención

EDITAR: ahora tengo mucho más conocimiento sobre el tema y empiezo a dudar de la conclusión que presenté aquí. En primer lugar, las CPU 0 y 1 son hiperprocesadas; A pesar de que AMD afirma tener 8 núcleos reales, ciertamente hay algo muy sospechoso porque los retrasos entre otros dos núcleos son mucho mayores (es decir, 0 y 1 forman un par, al igual que 2 y 3, 4 y 5, y 6 y 7 ) En segundo lugar, el std :: mutex se implementa de manera que hace girar los bloqueos por un momento antes de realizar llamadas al sistema cuando no puede obtener el bloqueo de inmediato en un mutex (que sin duda será extremadamente lento). Entonces, lo que he medido aquí es la situación más ideal y, en la práctica, el bloqueo y desbloqueo puede tomar drásticamente más tiempo por bloqueo / desbloqueo.

En pocas palabras, un mutex se implementa con atómicos. Para sincronizar atómicas entre núcleos, debe bloquearse un bus interno que congela la línea de caché correspondiente durante varios cientos de ciclos de reloj. En el caso de que no se pueda obtener un bloqueo, se debe realizar una llamada al sistema para poner el hilo en suspensión; eso es obviamente extremadamente lento (las llamadas al sistema son del orden de 10 mircosecondos). Normalmente eso no es realmente un problema porque ese hilo tiene que dormir de todos modos, pero podría ser un problema con una alta contención donde un hilo no puede obtener el bloqueo por el tiempo que normalmente gira y también lo hace el sistema, pero PUEDE toma la cerradura poco después. Por ejemplo, si varios subprocesos bloquean y desbloquean un mutex en un bucle cerrado y cada uno mantiene el bloqueo durante 1 microsegundo más o menos, entonces podrían ser ralentizados enormemente por el hecho de que son constantemente dormidos y despertados nuevamente. Además, una vez que un subproceso duerme y otro subproceso tiene que despertarlo, ese subproceso debe realizar una llamada al sistema y se retrasa ~ 10 microsegundos; esta demora ocurre mientras se desbloquea un mutex cuando otro hilo está esperando ese mutex en el kernel (después de que el giro tomó demasiado tiempo).

Esto depende de lo que realmente llama "mutex", modo OS, etc.

Como mínimo , es un costo de una operación de memoria enclavada. Es una operación relativamente pesada (en comparación con otros comandos de ensamblador primitivos).

Sin embargo, eso puede ser mucho más alto. Si lo que llama "mutex" es un objeto kernel (es decir, un objeto administrado por el sistema operativo) y se ejecuta en modo usuario, cada operación lleva a una transacción en modo kernel, que es muy pesada.

Por ejemplo, en el procesador Intel Core Duo, Windows XP. Operación enclavada: toma alrededor de 40 ciclos de CPU. Llamada en modo kernel (es decir, llamada al sistema): aproximadamente 2000 ciclos de CPU.

Si este es el caso, puede considerar el uso de secciones críticas. Es un híbrido de un mutex del núcleo y acceso de memoria enclavado.

El costo variará dependiendo de la implementación, pero debe tener en cuenta dos cosas:

• Lo más probable es que el costo sea mínimo, ya que es una operación bastante primitiva y se optimizará tanto como sea posible debido a su patrón de uso (se usa mucho ).
• no importa lo caro que sea, ya que debe usarlo si desea una operación segura de subprocesos múltiples. Si lo necesitas, entonces lo necesitas.

En los sistemas de procesador único, generalmente puede deshabilitar las interrupciones el tiempo suficiente para cambiar los datos atómicamente. Los sistemas multiprocesador pueden usar una estrategia de prueba y configuración .

En ambos casos, las instrucciones son relativamente eficientes.

En cuanto a si debe proporcionar un único mutex para una estructura de datos masiva, o tener muchos mutexes, uno para cada sección, es un acto de equilibrio.

Al tener un único mutex, tiene un mayor riesgo de contención entre múltiples hilos. Puede reducir este riesgo al tener un mutex por sección, pero no desea entrar en una situación en la que un hilo tenga que bloquear 180 mutexes para hacer su trabajo :-)

Soy completamente nuevo en pthreads y mutex, pero puedo confirmar por experimentación que el costo de bloquear / desbloquear un mutex es casi cero cuando no hay contención, pero cuando hay contención, el costo de bloqueo es extremadamente alto. Ejecuté un código simple con un grupo de subprocesos en el que la tarea era solo calcular una suma en una variable global protegida por un bloqueo mutex:

y = exp(-j*0.0001);
pthread_mutex_lock(&lock);
x += y ;
pthread_mutex_unlock(&lock);

Con un hilo, el programa suma 10,000,000 valores virtualmente instantáneamente (menos de un segundo); con dos hilos (en una MacBook con 4 núcleos), el mismo programa tarda 39 segundos.