mutex - sincronización - Problema de exclusión mutua

interbloqueo

Question

Por favor, eche un vistazo al siguiente pseudo-código:

boolean blocked[2];
int turn;
void P(int id) {
while(true) {
blocked[id] = true;
while(turn != id) {
while(blocked[1-id])
/* do nothing */;
turn = id;
}
/* critical section */
blocked[id] = false;
/* remainder */
}
}
void main() {
blocked[0] = false;
blocked[1] = false;
turn = 0;
parbegin(P(0), P(1)); //RUN P0 and P1 parallel
}

Pensé que podría implementar una solución de exclusión mutua simple usando el código anterior. Pero no está funcionando. ¿Alguien tiene una idea de por qué?

¡Cualquier ayuda realmente sería apreciada!

Answer 1

¿Es esta tarea o alguna plataforma incrustada? ¿Hay alguna razón por la que no pueda usar las primitivas de sincronización pthreads o Win32 (según corresponda)?

Answer 2

El compilador podría haber optimizado el ciclo while "vacío". Declarar las variables como volátiles podría ayudar, pero no se garantiza que sea suficiente en los sistemas multiprocesador.

Answer 3

La concurrencia no se puede implementar de esta manera, especialmente en un entorno de multiprocesador (o multi-núcleo): diferentes núcleos / procesadores tienen cachés diferentes. Esos cachés pueden no ser coherentes. El pseudo-código a continuación podría ejecutarse en el orden mostrado, con los resultados que se muestran:

get blocked[0] -> false // cpu 0
set blocked[0] = true // cpu 1 (stored in CPU 1''s L1 cache)
get blocked[0] -> false // cpu 0 (retrieved from CPU 0''s L1 cache)
get glocked[0] -> false // cpu 2 (retrieved from main memory)

Necesita conocimiento de hardware para implementar concurrencia.

Answer 4

Tal vez necesites declarar bloqueado y convertirlo en volátil, pero sin especificar el lenguaje de programación no hay forma de saberlo.

Answer 5

La exclusión mutua no está garantizada en este ejemplo debido a lo siguiente:

Comenzamos con la siguiente situación:

blocked = {false, false};
turn = 0;

P1 ahora se ejecuta y omite

 blocked[id] = false; // Not yet executed.

La situación es ahora:

blocked {false, true}
turn = 0;

Ahora P0 se ejecuta. Pasa el segundo ciclo while, listo para ejecutar la sección crítica. Y cuando P1 se ejecuta, establece turn to 1, y también está listo para ejecutar la sección crítica.

Por cierto, este método fue inventado originalmente por Hyman. Lo envió a Communications of the Acm en 1966

Answer 6

La exclusión mutua no está garantizada en este ejemplo debido a lo siguiente:

Comenzamos con la siguiente situación:

turn= 1;
blocked = {false, false};

La ejecución se ejecuta de la siguiente manera:

P0: while (true) {
P0: blocked[0] = true;
P0: while (turn != 0) {
P0: while (blocked[1]) {
P0: }
P1: while (true) {
P1: blocked[1] = true;
P1: while (turn != 1) {
P1: }
P1: criticalSection(P1);
P0: turn = 0;
P0: while (turn != 0)
P0: }
P0: critcalSection(P0);