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

• Erika tendrá la tarea el viernes por la tarde.
• Las cuentas deben ser disponibles un dia después tu solicitud.
• Será una sala de terminales abierta 24 horas por día.

Bloqueos mutuos y bloques indefinidos

• Procesos $P$₀ y $P$₁ con semáforos $S$ y $T$ iniciado a 1:

  (* P0 *)                (* P1 *)
  wait(S);                wait(T);
  wait(T);                wait(S);
  ...                     ...
  signal(S);              signal(T);
  signal(T);              signal(S);
  

• ¶ ¿Cuál es el problema? Suponga que ambos ejecutan el primer enunciado. Tenemos el bloqueo mutuo (deadlock).
• ¶ Si cambiamos la orden de las llamadas a wait in $P$₀, ¿es la solución correcta? Sí. La orden de las llamadas a signal no importa.
• Podemos tener el bloqueo indefinido (starvation) si un proceso no es sacado nunca de la cola de un semáforo que usa, por ejemplo, una lista LIFO.

Productor-consumidor con buffer limitado

• El código sin sincronización:

  (* P *)                 (* C *)              
  producir nextp          sacar nextc de buffer 
  poner nextp en buffer   consumir nextc       
  

• ¶ El consumidor debiera esperar hasta que hay algo en el buffer. Recuerde la interrogación. El semáforo lleno tiene un valor inicial de 0.

  (* P *)                 (* C *)              
  producir nextp          wait(lleno);          
  poner nextp en buffer   sacar nextc de buffer
  signal(lleno);          consumir nextc       
  

• ¶ ¿Y el productor? El semáforo vacio tiene un valor inicial de $n$.

  (* P *)                 (* C *)              
  producir nextp          wait(lleno);          
  wait(vacio);            sacar nextc de buffer
  poner nextp en buffer   signal(vacio);       
  signal(lleno);          consumir nextc       
  

• ¶ ¡Pero ambos pueden modificar el buffer al mismo tiempo!

  (* P *)                 (* C *)
  producir nextp          wait(lleno);          
  wait(vacio);            wait(mutex);         
  wait(mutex);            sacar nextc de buffer
  poner nextp en buffer   signal(mutex);       
  signal(mutex);          signal(vacio);       
  signal(lleno);          consumir nextc       
  

  ¶ mutex tiene un valor inicial de 1.
• ¶ ¿Qué pasa si tenemos más de un productor o consumidor? La solución es todavía correcta.

Lectores y escritores

• Tenemos procesos que quieren leer o escribir un recurso compartido. Más de un lector puede leerlo al mismo tiempo, pero un escritor necesita el acceso exclusivo.
• Usamos un semáforo dde (con valor inicial de 1) para el derecho de escribir. El escritor es entonces

  wait(dde);
  ...escribir...
  signal(dde);
  

• ¶ Los lectores tienen que asir el derecho de escribir, también con wait(dde). Pero no podemos usar lo mismo código como los escritores. ¿Por qué? Porque entonces solamente un lector puede leer a la vez.
• El lector:

          wait(mutex);
  readcount := readcount + 1;
  if readcount = 1 then wait(dde)
          signal(mutex);
  ...leer...
          wait(mutex);
  readcount := readcount - 1;
  if readcount = 0 then signal(dde)
          signal(mutex);
  

  ¶ Tenemos que controlar los accesos al readcount con un semáforo mutex.

  ¶ ¿Es la solución justa? No. Los escritores pueden esperar sin límite.

Los filósofos comensales

• Cinco filósofos con cinco palillos chinos y una fuente de arroz en el centro de la mesa.
• Los filósofos piensan y comer. Un filósofo hambremiento tiene que coger dos palillos (uno a la vez).
• Una solución es que un filósofo coge el palillo a la izquierda y después el palillo a la derecha.

  ¶ Problema: deadlock.

• Otra solución: Un filósofo puede coger sus palillos solamente si ambos están disponibles.

  ¶ Problema: inanición.

Claves

• Una clave (lock) es un semáforo binario (como mutex). Puede tener solamentes los valores 0 y 1.
• acquire

  acquire(s)
    if s.value = 1 then s.value = 0
    else begin
      poner el proceso en s.queue
      bloquear
    end
  

• release

  release(s)
    if s.queue es vacio then s.value = 1
    else begin
      sacar un proceso P de s.queue
      despertar P
    end
  

• Podemos implementar los semáforos de contar con las claves.