¿Cuál es el número de consenso para los semáforos?

Question

(Yo creo que el número de consenso para un mutex es 2.

¿Cuál es el número de consenso para los semáforos (como en pthread_sem_*)?

¿Cuál es el número de consenso para las variables de condición (como en pthread_cond_*)?

Answer 1

El número de consenso para un mutex sería 1. Está trivialmente claro que un mutex no espera para un solo hilo. Desde su definición, también está claro que un mutex ya no es libre de espera para dos hilos. El número de consenso, por lo tanto, es> = 1 y <2, por lo que debe ser 1.

Del mismo modo, otros mecanismos de sincronización que funcionan al detener un hilo a favor de otro también tienen el consenso número 1 y, por lo tanto, no pueden usarse para construir un objeto sin esperar compartido por 2 subprocesos.

Answer 2

La respuesta depende de las operaciones compatibles en el mutex o el semáforo. Si solo se admiten bloqueos de bloqueo, el número de consenso es 1. Si un hilo puede intentar bloquear el mutex sin esperar, el número de consenso es 2. es porque si hay dos hilos, ambos pueden intentar bloquear el mutex, ambos pueden De acuerdo cuál lo consiguió, por lo que hay consenso. Si el mutex puede determinar adicionalmente, para cualquier número de hilos, qué hilo lo ha bloqueado, entonces el número de consenso es infinito. Creo que la situación de los semáforos es similar. Los mutexes son equivalentes a los semáforos con el contador 1. No creo que se pueda alcanzar el consenso solo con contadores más grandes, todavía se reduce a las mismas operaciones. PTHreads admite cerraduras sin bloqueo pero no consultas, por lo que allí la respuesta sería 2.

La señalización de una variable de condición no hace nada si algún hilo no lo está esperando, por lo que tienen el consenso número 1.

Answer 3

Infinito, seguramente? Pero no esperan libres.

Quizás soy malentendido. Dices que un mutex tiene un número de consenso de 2, ¿cuál es tu fuente para eso? Está diseñado para permitir que cualquier número de hilos compartiera un recurso, con la compensación del bloqueo.

Atómico prueba tiene un número de consenso de 2, pero no bloquea.

---

Para aclarar: los semáforos, mutexes, etc. son primitivas que simplemente puede envolver un recurso compartido para que sea seguro (siempre que lo haga correctamente). Pueden bloquear, pero garantizarán que sus datos sean seguros.

El documento que cita se trata de las primitivas necesarias para proteger los datos sin bloquear, cual es difícil. Las mismas primitivas también pueden ser útiles para las cerraduras, pero eso es solo un buen extra.

Answer 4

Solo desde este artículo solo puede concluir que un semáforo debe tener un número de consenso menor o igual a 2. He aquí por qué:

En la tercera página del artículo, indican: "La operación Fetch & Add es bastante flexible: se puede usar para semáforos ...". Dado que sabemos que Fetch & Add tiene un número de consenso igual a 2, el teorema 1 de ese documento se puede usar para mostrar que un semáforo debe tener un número de consenso menor o igual a 2. La prueba es así:

Prueba

Suponga que existe una implementación gratuita de semáforos por Fetch & Add. Además, suponga que un semáforo tiene un número de consenso mayor a 2. Sabemos que Fetch & Add tiene un número de consenso de 2. Del Teorema 1 podemos concluir que no existe una implementación sin esperar una semáforo por Fetch & Add en un sistema de más de 2 procesos . Esto contradice la suposición de que existe una implementación de Fetch & Add. Por lo tanto, un semáforo debe tener un número de consenso menor o igual a 2.

Qed