Uso de muchos bloqueos mutex

Question

Tengo una estructura de árbol grande en la que varios hilos están trabajando al mismo tiempo. Idealmente, me gustaría tener un bloqueo mutex individual para cada celda.

Miré la definición de pthread_mutex_t en bits/pthreadtypes.h y es bastante corta, por lo que el uso de la memoria no debería ser un problema en mi caso.

Sin embargo, ¿hay alguna penalización de rendimiento cuando se utilizan muchos (digamos unos pocos miles) pthread_mutex_t s diferentes para solo 8 hilos?

Answer 1

Si está bloqueando y desbloqueando con mucha frecuencia, puede haber una penalización, ya que la obtención y liberación de bloqueos lleva algo de tiempo, y puede llevar bastante tiempo si se disputan los bloqueos.

Cuando utilice muchos bloqueos en una estructura como esta, tendrá que ser muy específico sobre lo que bloquea cada bloqueo, y asegúrese de tener cuidado con los bloqueos AB-BA. Por ejemplo, si está cambiando la estructura del árbol durante una operación de bloqueo, deberá bloquear todos los nodos que se cambiarán, en un orden consistente, y asegurarse de que los hilos que trabajan en los descendientes no se confundan.

Si tiene un número muy grande de bloqueos distribuidos en la memoria, los problemas de almacenamiento en caché podrían causar problemas de rendimiento, según la arquitectura, ya que las operaciones de bloqueo generalmente invalidarán al menos parte de la caché.

Su mejor opción es probablemente implementar una estructura de bloqueo simple, luego perfilarla, y luego refinarla para mejorar el rendimiento, si es necesario. No estoy seguro de lo que está haciendo con el árbol, pero un buen lugar para comenzar podría ser un único bloqueo lector-escritor para todo el árbol, si espera leer mucho más de lo que actualiza.

"Deberíamos olvidarnos de pequeñas eficiencias, digamos aproximadamente el 97% del tiempo: la optimización prematura es la raíz de todo mal". - Donald Knuth

Answer 2

Debes indicar tus patrones de bloqueo/acceso para poder evaluar esto correctamente. Si cada subproceso solo tuviera uno o algunos bloqueos a la vez y la probabilidad de que dos o más subprocesos quisieran el mismo bloqueo al mismo tiempo es baja (un patrón de acceso aleatorio o 8 corredores en diferentes posiciones en una pista circular) corriendo aproximadamente a la misma velocidad u otras cosas más complicadas) entonces evitará en su mayoría el peor caso donde un hilo tiene que dormir para obtener un bloqueo (o en algunos casos tiene que involucrar al sistema operativo para decidir quién gana) porque usted tiene algunos hilos y tantos bloqueos.

Si cada hilo puede querer cientos o miles de bloqueos en un momento dado, las cosas comenzarán a cambiar.

No tocaré la prevención de interbloqueo porque no sé nada sobre el contenedor que está utilizando, pero debe ser consciente de la necesidad de evitarlos.