Problema de exclusión mutua

StackOverflow https://stackoverflow.com/questions/411499

  •  03-07-2019
  •  | 
  •  

Pregunta

Por favor, eche un vistazo al siguiente pseudocó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 sería realmente apreciada!

¿Fue útil?

Solución

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 salta 

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

La situación es ahora: 

blocked {false, true}
turn = 0;

Ahora se ejecuta P0. Pasa el segundo bucle while, listo para ejecutar la sección crítica. Y cuando P1 se ejecuta, establece el turno a 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 Comunicaciones de la Cámara en 1966

Otros consejos

La exclusión mutua en este ejemplo no está garantizada 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);

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

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

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

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)

Usted necesita conocimientos de hardware para implementar la concurrencia.

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

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top