multithreading - lock - mutex en c ejemplos

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

Question

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

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

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

(No estoy seguro de la cantidad de diferencias que existen entre diferentes hardware. 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 único mutex para todo el objeto, podría proteger muchos bloques. Y me pregunto qué tan lejos debo ir sobre esto. Es decir, ¿debería tratar de proteger cualquier bloqueo posible en la medida de lo posible, sin importar cuánto más complicado y cuánto más mutex significa esto?

Answer 1

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 a menudo, entonces múltiples bloqueos aumentarían el paralelismo. A costa de la capacidad de mantenimiento, dado que más bloqueo significa más depuración del bloqueo.

¿Qué tan eficiente es bloquear un mutex? Es decir, ¿cuántas instrucciones del ensamblador existen y cuánto tiempo toman (en el 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 un bloqueo particular, mejor.

Mutex está compuesto por dos partes principales (simplificación excesiva): (1) una bandera que indica si el mutex está bloqueado o no y (2) espera la cola.

El cambio de la bandera es solo unas pocas instrucciones y normalmente se realiza sin una llamada al sistema. Si mutex está bloqueado, syscall pasará a agregar el hilo que llama a la cola de espera e iniciará la espera. Desbloquear, si la cola de espera está vacía, es barata, pero de lo contrario necesita un syscall para activar uno de los procesos de espera. (En algunos sistemas, las llamadas de sistema económicas / rápidas se usan para implementar las exclusiones mutuas, se convierten en llamadas de sistema lentas (normales) solo en caso de conflicto).

Bloquear mutex desbloqueado es realmente barato. Desbloquear el mutex sin conflicto también es barato.

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

Puede lanzar 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 mutex en particular) son baratos y no están sujetos a ningún límite del sistema. Pero muchos de ellos encierran una pesadilla para la depuración. Tabla simple:

1. Menos bloqueos significa más contenciones (llamadas de sys lenta, puestos de CPU) y menor paralelismo
2. Menos bloqueos significa menos problemas de depuración de 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 puntos muertos no ejecutables.

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

(*) El problema con mutexes menos bloqueados es que si tiene demasiado bloqueo en su aplicación, hace que gran parte del tráfico entre CPU / núcleo limpie la memoria mutex de la memoria caché de datos de otras CPU para garantizar el coherencia de caché. Los vaciados de caché son como interrupciones livianas y son manejados por CPU de forma transparente, pero introducen los llamados stalls (búsqueda de "puesto").

Y los puestos son los que hacen que el código de bloqueo funcione 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 una gran cantidad de bloqueos para disminuir la probabilidad de contenciones de bloqueo y evitar el bloqueo. Esa es la razón por la que existe un bloqueo de espacio de usuario barato, no sujeto a los límites del sistema.

Answer 2

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

• el costo será 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 qué tan costoso sea, ya que debe usarlo si desea una operación segura de múltiples hilos. Si lo necesitas, entonces lo necesitas.

En los sistemas de un solo procesador, generalmente puede desactivar las interrupciones el tiempo suficiente para cambiar los datos de forma atómica. Los sistemas multiprocesador pueden usar una estrategia de test-and-set .

En ambos casos, las instrucciones son relativamente eficientes.

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

Al tener un solo 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 donde un hilo tiene que bloquear 180 mutexes para hacer su trabajo :-)

Answer 3

Esto depende de lo que realmente se llame "mutex", modo de sistema operativo, etc.

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

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 el modo de usuario, cada operación en él conduce 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 núcleo mutex y acceso de memoria interbloqueado.

Answer 4

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 la memoria caché, toma 47 relojes (13 ns).

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

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 unos pocos valores codificados específicos para mi cuadro (xrange, yrange y rdtsc overhead), 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 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 el número de relojes que se necesitan para bloquear y desbloquear `mutex ''(con una sobrecarga de 39 relojes para las llamadas rdtsc en mi caja). El tercer asm es un bucle de retardo. El tamaño del bucle de retardo es 1 más pequeño para el hilo 1 que para el hilo 0, por lo que el hilo 1 es ligeramente más rápido.

La función anterior se llama en un bucle estrecho 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 circuito debajo de él.

En el gráfico de arriba, el punto inferior derecho es una medición con un retardo loop_count de 150, y luego siguiendo los puntos en la parte inferior, hacia la izquierda, loop_count se reduce en una medida. Cuando se convierte en 77, la función se llama cada 102 ns en ambos hilos. Si subsecuentemente loop_count se reduce aún más, ya no es posible sincronizar los hilos y el mutex comienza a bloquearse la mayor parte del tiempo, lo que da como resultado una mayor cantidad de relojes que se requieren para realizar el bloqueo / desbloqueo. También el tiempo promedio de la llamada de función aumenta debido a esto; entonces los puntos de la trama ahora suben y hacia la derecha otra vez.

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 ponerlos -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 ciclo al mismo tiempo por 50 ns) o cuando 13 ns veces el tamaño del bucle es más demorado que el retraso que obtienes por contención.