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

Detección de deadlock

• La evitacíon de deadlock tiene un costo porque todos los estados inseguros no son estados de deadlock. Esto implica que hay tiempos cuando algunos procesos tienen que esperar y recursos están desocupados sin que es necesario.
• El sistema operativo puede chequear de vez en cuando si hay un deadlock. ¿Cuán frecuentemente debieramos chequear si hay deadlock?
  • El costo de algoritmo vs. el número de procesos en deadlock.
  • Saber quien creó el deadlock.
  • ¶ Cuando la utilización de la CPU es baja.
• Tenemos que eliminar los deadlocks que encontramos. Posibilidades:
  • Abortar todos los procesos en deadlock. ¡Esto es un método común!
  • Abortar procesos uno a la vez hasta que no haya deadlock.
  • Retroceder los procesos a algún punto y reiniciar. El deadlock puede reocurrir.
  • Expropiar recursos de procesos hasta que no haya deadlock. Retrocedemos los procesos expropiados.
• Tenemos que seleccionar un proceso para abortar o retroceder. Factores:
  • La prioridad
  • El tiempo que el proceso ha corrido
  • El número y tipo de los recursos adquiridos
  • La clase de proceso (batch o interactiva)
• La starvation es un problema.

Planificación de la CPU (Cap. 5)

• La idea central de multiprogramación es que los procesos se ejecutan hasta que tienen que esperar I/O. Así que la CPU es siempre ocupada, debieramos planificar su uso por procesos multiples.
• Recuerda los estados de un proceso (nuevo, listo, en ejecución, en espera, finalizado). Tenemos la posibilidad de planificar la CPU cuando
  • Un proceso cambia de en ejecución a en espera. ¶ Por ejemplo, después de una solicitud de I/O o una llamada a wait.
  • Un proceso cambia de en espera a listo. ¶ Por ejemplo, después de I/O o un signal.
  • Un proceso termina.
  • Un proceso cambia de en ejecución a listo (después de una interrupción).
  El caso final existe solamente en los sistemas con preemption (expropriación).

Criterios de planificación

• Utilización de la CPU. Queremos mantener la CPU tan ocupada como posible.
• Productividad. El número de los procesos que terminan por unidad de tiempo. Es un medida de trabajo que depende de la duración de los procesos.
• Tiempo de retorno. El tiempo para un proceso entre la entrada y la salida del sistema. Es la suma de los tiempos en espera, en ejecución, etc.
• Tiempo de espera. El tiempo un proceso pasa en la cola de procesos listos (no en espera de I/O).
• Tiempo de respuesta. El tiempo entre la presentación del proceso al sistema y su primera respuesta (output). ¶ ¿Por qué es interesante? Sistemas interactivos. ¿Debieramos minimizar el promedio del tiempo de respuesta, el mínimo, o el máximo? El máximo.

Planificación de first-come, first-served

• El algoritmo más sencillo es "servicio por orden de llegada" (first-come, first-served, o FCFS). No usa preemption.
• El proceso que primero solicita la CPU es el primero al que se asigna.
• ¶ Para la implementación podemos usar una cola FIFO de PCBs.
• Ejemplo: $P$₁ con 24 unidades de tiempo de CPU, $P$₂ con 3, y $P$₃ con 3. Con el orden $P$₁, $P$₂, $P$₃, el promedio del tiempo de espera es $(0+24+27)/3=17$. Pero con $P$₂, $P$₃, $P$₁, el promedio es $(0+3+6)/3=3$.
• El promedio de tiempo de espera en FCFS no es mínimo, en general.
• Efecto de convoy. ¶ ¿Qué pasa si tenemos un sistema con un proceso limitado por la CPU (CPU-bound) y muchos limitados por I/O (I/O-bound)? Los procesos I/O-bound tienen que esperar hasta que el proceso CPU-bound usa un depositivo de I/O. La utilización de los depositivos es más baja.