¿Cómo funcionan realmente los mutexes?

Question

La idea detrás de los mutexes es permitir solo el acceso de un hilo a una sección de la memoria en cualquier momento. Si un hilo bloquea el mutex, cualquier otro intento de bloqueo se bloqueará hasta que el primero se desbloquee. Sin embargo, ¿cómo se implementa esto? Para bloquearlo, el mutex tiene que establecer un bit en algún lugar que diga que está bloqueado. Pero, ¿qué ocurre si el segundo mutex está leyendo al mismo tiempo que el primero está escribiendo? Peor aún, ¿qué pasa si ambos bloquean el mutex al mismo tiempo? El mutex sucumbiría al mismo problema que debe evitar.

¿Cómo funcionan realmente los mutexes?

Answer 1

operaciones atómicas de bajo nivel. Estos son esencialmente mutex implementados en hardware, excepto que solo puede realizar unas pocas operaciones de forma atómica.

Considérese el siguiente pseudocódigo equivalente:

mutex global_mutex; 
void InterlockedAdd(int& dest, int value) { 
    scoped_lock lock(mutex); 
    dest += value; 
} 
int InterlockedRead(int& src) { 
    scoped_lock lock(mutex); 
    return src; 
} 
void InterlockedWrite(int& dest, int value) { 
    scoped_lock lock(mutex); 
    dest = value; 
} 

Estas funciones se implementan como instrucciones de la CPU, y garantizar la coherencia entre los hilos en diversos grados. La semántica exacta depende de la CPU en cuestión. x86 ofrece consistencia secuencial. Esto significa que las operaciones actúan como si hubieran sido emitidas secuencialmente, en algún orden. Esto obviamente implica bloquear un poco.

Puede conjeturar con precisión que las operaciones atómicas se pueden implementar en términos de mutexes, o viceversa. Pero, por lo general, las operaciones atómicas son proporcionadas por el hardware, y luego mutexes y otras primitivas de sincronización implementadas sobre ellas por el sistema operativo. Esto se debe a que hay algunos algoritmos que no requieren un mutex completo y que pueden operar lo que se conoce como "sin bloqueo", lo que significa simplemente usar operaciones atómicas para lograr cierta coherencia entre hilos.

Answer 2

Una implementación simple que se ha utilizado en el pasado es utilizar una instrucción atómica de "bloqueo e intercambio" de nivel de CPU. Esta es una instrucción especial que intercambia atómicamente un valor dado con un valor en alguna ubicación de memoria.

Un hilo podría adquirir dicho mutex intentando intercambiar un valor 1 en la ubicación de la memoria. Si el valor vuelve a ser 0, entonces el hilo supondría que tiene el mutex y continuaría. De lo contrario, si el valor devuelto es 1, entonces el hilo sabrá que un otro hilo tiene actualmente el mutex. En ese caso, esperaría hasta volver a intentarlo.

Lo anterior es un esquema muy simplificado de lo que podría suceder en un sistema simple. Los sistemas operativos reales son mucho más complejos en estos días.

Answer 3

Todo lo que necesita es hacerlo atómicamente. Puede ser proporcionado por hardware, como las instrucciones atómicas de comparación e intercambio, o por el sistema operativo a través de llamadas al sistema. Una vez que está en el dominio del sistema operativo, es bastante fácil asegurarse de que solo un hilo esté intentando bloquear el mutex.

En la práctica, ambos enfoques se combinan. Ver por ejemplo los futexes de Linux.

Answer 4

Aquí está una descripción rápida de lo que un mutex tiene que trabajar, que es una forma abreviada de mi artículo completo How does a mutex work?

• No es un número entero en la memoria que representa el estado bloqueado, con un valor de 1 ó 0.
• El mutex necesita una función atómica compare_and_swap que pueda intentar atómicamente modificar ese valor e informar si tuvo éxito. Esto permite que un hilo compruebe y modifique el estado al mismo tiempo.
• El sistema operativo debe proporcionar una función para esperar en caso de que el mutex esté bloqueado. En Linux, la función de bajo nivel es futex. Esto colocará el hilo en una cola y también supervisará el número entero en la memoria.
• Las operaciones involucradas también incluyen vallas de datos, para evitar que las modificaciones en la memoria sean visibles antes del bloqueo, y estar completamente disponibles después del bloqueo.