IIC 2332 -- Sistemas Operativos
Apuntes 04
1er Semestre 1996

Sincronización (Cap. 6)

• Usar todos las $n$ posiciones del buffer entre el productor y el consumidor.

  (* P *)
  producir nextp;
  while counter = n do no-op;
  buffer[in] := nextp;
  in := (in+1) mod n;
  counter := counter + 1;
  
  (* C *)
  while counter = 0 do no-op;
  nextc := buffer[out];
  out := (out+1) mod n;
  counter := counter - 1;
  consumir nextc;
  

• ¶ ¿Cuál es el problema con esta solución? El contador puede ser modificado por ambos hilos simultáneamente, produciendo un valor incorrecto.

  Las instrucciones se intercalan:

  load counter, r1            load counter, r2 
  add r1, 1, r1               sub r2, 1, r2    
  store r1, counter           store r2, counter
  

  Eso es una condicion de carrera (race condition).

Secciones críticas

• En el ejemplo de productores-consumidores, la modificación del contador es una acción clave que solamente un hilo debe llevar a cabo al mismo tiempo. Esa acción de código es una sección crítica.
• Una sección crítica es un segmento de código donde un proceso manipula o usa un recurso común. Ejemplos: trenes y un túnel.
• ¶ Para usar secciones críticas con $n$ procesos, se tienen que satisfacer las condiciones siguientes:

  Exclusión mutua.

  Si $P$_i está en su sección crítica, ningún otro está en la suya.

  Progreso.

  Si ningún proceso está en su sección crítica, y hay procesos que desean entrar en las suyas, debe ser posible que un proceso entre en su sección crítica en un tiempo limitado.

  Espera limitada.

  Debe haber un límite en el número de veces que los procesos puedan entrar en sus secciones críticas mientras que un proceso espera entrar en la suya.

Soluciones de Dos Procesos

• Suponemos que las instrucciones de cargar y almacenar son atómicas (no se pueden interrumpir).
• Procesos/Threads $P$_i y $P$_j

  while turn <> i do no-op;
  <SC>
  turn := j;
  

• ¶ ¿Soluciona el problema de sección crítica? No. No tenemos la condición de progreso; los procesos tienen que alternarse.
• Segunda solución:

  var flag: array [0..1] of boolean;
  
  flag[i] := true;
  while flag[j] do no-op;
  <SC>
  flag[i] := false;
  

• ¶ No solucionado. No tenemos la espera limitada porque ambos procesos se pueden atorar en el loop. Esta solución depende de la sincronización.
• Tercera solución:

  flag[i] := true;
  turn := j;
  while (flag[j] and turn=j) do no-op;
  <SC>
  flag[i] := false
  

• ¶ Solucionado (Algoritmo de Peterson, 1981).

  Exclusión mutua.

  • Si ambos están en la SC, ambos flags son verdaderos.
  • Podemos entrar en la SC solamente si flag[j] es falso o turn = i.
  • turn no puede tener dos valores al mismo tiempo.
  • Así ambos procesos no pueden salir del loop al mismo tiempo.
  • Entonces uno salió mientras que otro (digamos $P$_i) tuvo más que hacer; por lo menos, chequear turn = j.
  • Pero ya turn = j (de otro modo $P$_j no pudo entrar), así $P$_i tiene que esperar.
  Propiedades otros.
  • Si $P$_i no puede entrar en su sección crítica, tiene que estar en su loop.
  • Si $P$_j no desea entrar en su SC, su flag será falso y $P$_i puede entrar.
  • Si $P$_j ha establecido flag[j] = true y está en el loop while, turn puede ser i o j.
  • Si j, $P$_j entrará en la SC.
  • Después de dejar la SC, $P$_j establece flag[j] = true.
  • $P$_i puede entrar ahora en su SC.
  • $P$_j no puede entrar otra vez antes de $P$_i porque antes el loop tiene que establecer turn = i, y $P$_i no cambiará flag o turn hasta termina con la SC.
• Soluciones para más de dos procesos: Ver al alogitmo de panadería (bakery algorithm) en la página 171.