c++ - semaforos - ¿Cómo funcionan los mutex realmente?

semaforos en c

Question

La idea detrás de mutexes es permitir solo un hilo de acceso a una sección de la memoria a la vez. 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 bloquearse, el mutex tiene que establecer un bit en algún lugar que diga que está bloqueado. Pero qué pasa si el segundo mutex está leyendo al mismo tiempo que el primero está escribiendo. Peor aún, ¿y si ambos bloquean el mutex al mismo tiempo? La exclusión mutua sucumbiría al mismo problema que se pretende evitar.

¿Cómo funcionan los mutex realmente?

Answer 1

Aquí hay una descripción general rápida de lo que necesita un mutex para trabajar, es una forma abreviada de mi artículo completo ¿Cómo funciona un mutex?

• Hay un entero en la memoria que representa el estado bloqueado, con un valor de 1 o 0.
• El mutex necesita una función atómica compare_and_swap que puede intentar modificar ese valor de forma atómica 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 el 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 controlará 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 estén completamente disponibles después del bloqueo.

Answer 2

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

Considere 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 por parte de la CPU y garantizan la coherencia entre los hilos en varios 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 fueran emitidas secuencialmente, en algún orden. Esto obviamente implica bloquear un poco.

Usted puede suponer con precisión que las operaciones atómicas pueden implementarse en términos de mutexes, o viceversa. Pero por lo general, las operaciones atómicas son proporcionadas por el hardware, y luego las 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 pueden operar lo que se conoce como "sin bloqueo", lo que significa simplemente usar operaciones atómicas para cierta coherencia entre subprocesos.

Answer 3

Todo lo que necesitas es hacerlo atómicamente. Puede ser proporcionado por hardware, como 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 se combinan ambos enfoques. Ver por ejemplo los futex de Linux.

Answer 4

Una implementación simple que se ha utilizado en el pasado es usar una instrucción atómica de "bloqueo e intercambio" a 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 subproceso podría adquirir dicho mutex al intentar intercambiar un valor de 1 en la ubicación de la memoria. Si el valor vuelve a ser 0, entonces el hilo asumirá que tiene el mutex y continuará. De lo contrario, si el valor devuelto es 1, el subproceso sabría que otro subproceso tiene actualmente el mutex. En ese caso esperaría hasta volver a intentarlo.

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