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

Round robin

• En FCFS el promedio del tiempo de espera puede ser muy alto si un proceso largo se ejecuta primero. ¿Cuál es otro problema? El efecto de convoy.
• En planificación circular (round robin) usamos preemption para reducir el tiempo de espera. Cada proceso se ejecuta por un cuanto, o porción, de tiempo. Después de que se ejecuta un cuanto, el proceso se coloca al fin de la cola de procesos listos.
• El rendimiento del algoritmo depende mucho del tamaño del cuanto. ¿Qué pasa con un cuanto muy largo? Tenemos FSCS otra vez. Con cuantos cortos, los procesos cortos terminan rápidamente.
• ¿Cuál es el costo de los cuantos cortos? El overhead de los cambios de contexto crece. Si el tiempo de cambio de contexto es 10% del cuanto, por casi 10% del tiempo la CPU estará cambiando contexto. El overhead aumenta el tiempo de retorno.
• En general, el cuanto debiera ser bastante grande para que la mayoria de los procesos corren dentro de un cuanto. Esto es particularamente importante en los sistemas interactivos.
• Podemos tener todavía el efecto de convoy. Los procesos limitados por I/O corren en general por menos que un cuanto antes de que se bloqearan. Los procesos limitados por CPU reciben más tiempo, los procesos limitados por I/O tienen que esperar en la cola lista, y los depositivos están desocupados.
• Una solución es que tenemos otra cola lista para los procesos volviendo de un espera de I/O. Planifacamos estes primero; cada corre por la porción del cuanto que quedó cuando se bloqueó.

"Próximo el proceso más corto"

• FCFS tiene una preferencia para los procesos largos.
• La estrategia nueva es que seleccionamos siempre el proceso que correrá por el tiempo más corto (shortest job first, o SJF).
• SJF produce el promedio mínimo de tiempo en espera.
• ¿Cuál es el problema? Tenemos que saber cuan largo va a correr un proceso.
• Podemos predecir el tiempo de ejecución usando estadísticas de ejecuciones anteriores. El promedio exponencial: $S$_n+1=a T_n + (1-a)S_n, donde $S$ es nuestra predicción y $T$ es el tiempo real.
• Podemos usar preemption. En este caso seleccionamos como el próximo el proceso que tenga el menor tiempo restante.
• ¿Cuál es el problema para los procesos largos? Hay la posibilidad de starvation.

"Próximo la razón de respuesta más alta"

• Queremos evitar la starvation de SJF. Definimos la razón de respuesta: $RR\; =\; (w+s)/s$, donde $w$ es el tiempo de espera y $s$ es el tiempo predecido de ejecución.
• ¿Qué pasa con los trabajos cortos? Tienen denominadores pequeños, así que se ejecutan primero.
• ¿Qué pasa con los trabajos largos? Envejecen, y $RR$ crece.

Feedback

• Con esta política no necesitamos predicciones de los tiempos de correr.
• Usamos la preemption con cuantos y prioridades dinámicas.
• Los procesos entran en el sistema en la cola de la prioridad más alta. Después de la preemption, un proceso se coloca en una cola de prioridad más baja.
• Hay peligro de starvation. Podemos dar un proceso en cola $i$ un cuanto de $2i$ y colocar arriba procesos en colas de prioridad baja si envejecen demasiado.