Planificacion por Turno Rotatorio(ROUND-ROBIN)
Por: Carlos Gabriel Hurtado Castillo
Funcionamiento
Este es uno de los
algoritmos más antiguos, sencillos y equitativos en el reparto de la CPU entre
los procesos, muy válido para entornos de tiempo compartido. Cada proceso tiene
asignado un intervalo de tiempo de ejecución, llamado cuantum o cuanto. Si el
proceso agota su cuantum de tiempo, se elige a otro proceso para ocupar la CPU.
Si el proceso se bloquea o termina antes de agotar su cuantum también se
alterna el uso de la CPU. El round robín es muy fácil de implementar. Todo lo
que necesita el planificador es mantener una lista de los procesos listos.
Tamaño del Cuanto
La determinación del tamaño
del cuanto es vital para la operación efectiva de un sistema de cómputo. Si el cuanto
de tiempo es muy grande, cada proceso tendrá el tiempo necesario para terminar,
de manera que el esquema de planificación por turno degenera en uno de
primero-en-entrar-primero-en-salir. Si el cuanto es muy pequeño, el gasto extra
por cambio de proceso se convierte en el factor dominante y el rendimiento del
sistema se degradará hasta el punto en que la mayor parte del tiempo se
invierte en la conmutación del procesador, con muy poco o ningún tiempo para
ejecutar los programas de los usuarios.
El tamaño del cuanto debe
fijarse en el tamaño lo bastante grande como para que la mayoría de las
peticiones interactivas requieran menos tiempo que la duración del cuanto.
Por ejemplo, supongamos que
el cambio de proceso tarda 5 mseg., y la duración del cuantum es de 20 mseg. Con
estos parámetros, se utiliza un mínimo del 20% del tiempo de la CPU en la
ejecución del sistema operativo. Para incrementar la utilización de la CPU por
parte de los procesos de usuario podríamos establecer un cuantum de 500 mseg.,
el tiempo desperdiciado con este parámetro sería del 1%.
Pero consideremos lo que
ocurriría si diez usuarios interactivos oprimieran la tecla enter casi al mismo
tiempo. Diez procesos se colocarían en la lista de procesos listos. Si la CPU
está inactiva, el primero de los procesos comenzaría de inmediato, el segundo
comenzaría medio segundo después, etc. Partiendo de la hipótesis de que todos
los procesos agoten su cuantum, el último proceso deberá de esperar 4’5 seg.
para poder ejecutarse. Esperar 4’5 seg. para la ejecución de una orden sencilla
como dir parece excesivo.
En conclusión, un cuantum
corto disminuye el rendimiento de la CPU, mientras que un cuantum muy largo empobrece
los tiempos de respuesta y degenera en el algoritmo FIFO. La solución es
adoptar un término medio como 100 mseg.
Este algoritmo presupone la
existencia de un reloj en el sistema.
Un reloj es un dispositivo que genera periódicamente interrupciones. Esto es
muy importante, pues garantiza que el sistema operativo (en concreto la rutina
de servicio de interrupción del reloj) coge el mando de la CPU periódicamente.
El cuantum
de un proceso equivale a un número fijo de pulsos o ciclos de reloj. Al ocurrir
una interrupción de reloj que coincide con la agotación del cuantum se llama al dispatcher.
Caracteristica
- Periódicamente, se genera una interrupción de reloj.
- Cuando se genera la interrupción, el proceso
que está en ejecución se sitúa en la cola de Listos y se selecciona el
siguiente trabajo (apropiativo)
- Se conoce también como fracciones de ti
-
Esta diseñado específicamente para sistemas
de tiempo compartido. Se asigna un cuanto de tiempo (10-100ms.) de igual duración
a todos los procesos listos para ser ejecutados. Entre ellos, la selección se
realiza mediante una cola FIFO.
3 comentarios:
Algoritmos de Planificación estáticos y dinámicos
Los algoritmos de planificación pueden ser clasificados en estáticos y dinámicos La planificación estática hace un cálculo previo del plan del sistema, requiere de conocimiento a-priori de las características de las tareas y tiene la ventaja de que se ejecuta con poca sobrecarga. La planificación dinámica, por otra parte, determina el plan en tiempo de ejecución permitiendo la implementación de sistemas más flexibles que cuando se utiliza la planificación estática. La sobrecarga atribuible a la planificación dinámica es mayor pero consiguen una mayor utilización del procesador.
En un planificador estático todas las decisiones de planificación se llevan a cabo previo a la ejecución del sistema. Una tabla es generada con las decisiones de planificación que serán utilizadas durante la ejecución. Esta tabla contiene el plan estático que indica el instante de tiempo en que cada tarea debe ser ejecutada, de tal manera que el planificador sólo debe seguir las indicaciones de la tabla. Tan sólo es necesario almacenar las actividades del hiperperiodo del conjunto de tareas ya que estas se repetirán durante la ejecución del sistema. Como puede verse esta clase de algoritmos dependen del conocimiento a priori de las características y comportamiento de las tareas
. La verificación de la planificabilidad utilizando planificación estática debe llevarse a cabo durante la construcción del plan. Por otra parte, este esquema funciona si todas las tareas son periódicas, por lo que no puede utilizarse para sistemas conformados con tareas esporádicas o aperiódicas.
El tamaño de la tabla es un inconveniente adicional ya que pudiera ser excesivamente grande. Además, están la escasa flexibilidad y el que el problema deconstruir el plan estático sea NP-completo [46], lo que hace que la planificación estática muestre muchas desventajas a pesar de que algunos autores la consideren ventajosa.
Un planificador dinámico toma las decisiones durante la ejecución del sistema tomando en consideración las características de las tareas y el estado del sistema. Los planificadores dinámicos más utilizados son los basados en prioridades, mientras que las prioridades de las tareas a su vez pueden ser asignadas de manera fija o dinámica. En la planificación dinámica se elige para ejecución a la tarea con función de prioridad mayor de entre las que estén activas. Cuando la prioridad es fija, su valor se mantendrá igual con respecto al resto de tareas durante la vida del sistema. En el caso de las prioridades dinámica, el valor de la función de prioridad
Podrá variar en relación con el resto de tareas dependiendo de la carga del sistema en un instante determinado. La planificación dinámica ofrece muchas ventajas sobre la estática ya que es flexible y permite la implementación de sistemas más complejos.
En el ámbito de la planificación dinámica con prioridades fijas dos algoritmos tienen particular relevancia: prioridad a la tarea más frecuente (RM) y prioridad a la tarea más urgente (DM). El algoritmo RM asigna a cada tarea una prioridad inversamente proporcional a su periodo y asume que los plazos de las tareas son iguales a sus periodos. Para ejemplificar el funcionamiento del algoritmo RM.se muestra el cronograma de ejecución de un sistema formado por tres tareas, utilizando el algoritmo de prioridad a la tarea más frecuente (RM). Las tareas tienen los siguientes parámetros:T1= (3, 1), T2= (5, 2) y T3= (8,1), en donde el primer parámetro de las tareas representa su periodo y el segúndo su tiempo de cómputo. Se supone que los plazos son iguales a los periodos y que todas las tareas son liberadas en el instante creo. De acuerdo a la política de planificación RM la tarea T1es la más prioritaria mientras que T3es la menos prioritaria. En el instante 5 es liberada la segunda instancia de T2 y al no existir alguna otra tarea activa en el sistema inicia su ejecución. Sin embargo, en el instante 6 la tarea T 1 es liberada y al tener una prioridad mayor que T 2 expulsa a esta del procesador T1 inicia su ejecución. Una vez que T1 concluye, T2 continúa su ejecución en el punto en la que fue suspendida.
Publicar un comentario