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

Soluciones de hardware

• Es posible tener soluciones más sencillas al problema de la sección crítica con apoyo de hardware.
• Una solución es el apagar interrupciones. Desventajas:
  • Difícil para implementar en los multiprocesadores
  • ¶ El proceso puede quedar demasiado largo en la SC. Esto no es un problema para bibliotecas de threads a nivel de usuario.
• Las máquinas modernas tienen instrucciones atómicas que se pueden usar para el problema de SC.
• Test-and-Set.

  function Test-and-Set (var target: boolean): boolean;
    begin
      Test-and-Set := target;
      target := true
    end;
  

• Swap.

  procedure Swap (var a,b: boolean);
    var temp: boolean;
    begin
      temp := a;
      a := b;
      b := temp;
    end;
  

• ¶ Exclusión mutua. [Interrogación]

  (* lock iniciado a falso *)
  while Test-and-Set(lock) do no-op;
  <SC>
  lock := false;
  

  No soluciona la espera limitada. Para ésa necesitamos usar un array para todos los procesos que esperan y chequearlo durante la salida de la SC.

Semaphores (Semáforos)

• Las soluciones anteriores al problema de la sección crítica no son fáciles de usar para problemas más generales.
• Una herramienta clásica (de 1965) es el semaphore. Un semaphore es una variable de enteros que se puede accesar solamente a través de dos operaciones:
  • wait, o P

    wait(S): while S <= 0 do no-op;
             S := S - 1;
    

  • signal, o V

    signal(S): S := S + 1;
    

  Las modificaciones y la prueba (en wait) de S deben ser atómicas.
• ¶ Una solución para el problema de la sección crítica de $n$ procesos:

  (* mutex iniciado a 1 *)
  wait(mutex);
  <SC>
  signal(mutex);
  

• Sincronización de dos procesos. Enunciado $S$₁ de proceso $P$₁ debe ser ejecutado antes de $S$₂ de $P$₂

  (* P1 *)                        (* P2 *)
  S1;                             wait(synch);
  signal(synch);                  S2;
  

  ¶ ¿A qué valor se debiera iniciar synch? 0.

Implementación de semaphores

• Todas nuestras soluciones usan lo siguiente para esperar:

  while ... do no-op;
  

  ¶ ¿Cuál es una desventaja de estos loops? Usan la CPU mientras que esperan (espera activa, o busy waiting).
• Cuando implementamos semaphores como parte del sistema operativo, podemos eliminar busy waiting. Un proceso que tiene que esperar puede bloquearse.
• Cada semaphore tiene una cola de procesos bloqueado. La llamada a signal pone un proceso esperando en la cola lista del sistema.
• ¶ La implementación nueva:

  type semaphore = record value: integer;
                          L: list of process;
                   end;
  
  wait(S): 
    S.value := S.value - 1;
    if S.value < 0 then
      begin
        poner este proceso en S.L
        bloquear
      end
  
  signal(S):
    S.value := S.value + 1;
    if S.value <= 0 then
      begin
        sacar un proceso P de S.L
        despertar P
      end
  

  El S.O. provee las rutinas de bloquear y despertar. Podemos poner los procesos en las colas a través de un campo especial en el PCB.
• ¶ Para las secciones críticas de wait y signal (¿Dónde estan?) podemos inhibir las interrupciones o usar una solución de busy waiting. Ya que las SS.CC. son cortas, las esperas lo son también.