PDF de programación - Colas multinivel con Retroalimentación

UNIVERSIDAD TECNOLÓGICA ECOTEC

FACULTAD DE INGENIERÍA DE SISTEMAS

COMPUTACIONALES Y
TELECOMUNICACIONES



COLAS MULTINIVEL CON

RETROLIMENTACIÓN



SISTEMAS OPERATIVOS I



CÉSAR ZÚÑIGA SAN LUCAS



PROFESOR:

INGENIERA SARA NORIEGA



FECHA DE ENTREGA
04 MAYO DEL 2012







INDICE



INTRODUCCIÓN .................................................................................... 3

Desarrollo .......................................................................................... 4

Colas de Retroalimentación de Múltiples Niveles .............................................. 4







INTRODUCCIÓN

Existen algunas colas de procesos en una CPU, por lo que a continuación veremos el
funcionamiento de uno de ellos llamado Colas de Retroalimentación Múltiples.



Desarrollo

La planificación mediante colas multinivel es un algoritmo de planificación de procesos en
un sistema operativo. Su objetivo es diferenciar entre distintos tipos de trabajos, para ello
dividen la cola de procesos preparados en varias colas, una por cada tipo de trabajo, y no
permiten el movimiento de los procesos entre las distintas colas.
Los algoritmos de colas multinivel realimentadas se basan en los algoritmos de colas
multinivel, pero permiten el movimiento de los trabajos de unas colas a otras.
Las siglas MLQ y MLFQ son los acrónimos ingleses de multi level queues (colas multinivel)
y multi level feedback queues (colas multinivel realimentadas).



Colas de Retroalimentación de Múltiples Niveles

Cuando un proceso obtiene la CPU, sobre todo cuando todavía no ha tenido oportunidad
de establecer un patrón de comportamiento, el planificador no tiene idea de la cantidad
de tiempo de CPU que necesitará el proceso.
Los procesos limitados por la E/S normalmente usan la CPU sólo un momento antes de
generar una solicitud de E/S; los procesos limitados por la CPU pueden usar el procesador
durante horas si está disponible en forma no apropiativa.
Un mecanismo de planificación debe:
• Favorecer a los trabajos cortos.
• Favorecer a los trabajos limitados por la E/S para lograr un mejor aprovechamiento

de los dispositivos de E/S.

• Determinar la naturaleza de un trabajo lo más pronto posible y planificarlo de

acuerdo con su naturaleza.



Las colas de retroalimentación de niveles múltiples ofrecen una estructura que cumple
con estos objetivos.
Un proceso nuevo entra en la red de colas al final de la primera cola. Se desplaza en esa
cola mediante Round Robin hasta que obtiene la CPU. Si el trabajo termina o cede la CPU
para esperar la terminación de una operación de E/S o de algún evento, el trabajo
abandona
la red de colas. Si el cuanto expira antes de que el proceso ceda
voluntariamente la CPU, el proceso se colocará al final de la cola del siguiente nivel. El
proceso será atendido otra vez cuando llegue a la cabeza de esa cola si está vacía la
primera. Mientras el proceso utilice todo el cuanto proporcionado en cada nivel,
continuará desplazándose al final de la siguiente cola inferior. Por lo general, existe una
cola en el nivel más bajo en la cual el proceso circula por turno rotatorio hasta que
termina.
En muchos esquemas de retroalimentación de múltiples niveles, el cuanto asignado a un
proceso cuando pasa a una cola de nivel inferior alcanza un valor mayor. De esta forma,
cuanto más tiempo se encuentre un proceso en la red de colas más grande será el cuanto
asignado cada vez que obtenga la CPU, pero tal vez no obtenga la CPU muy a menudo,
porque los procesos de las colas de nivel superior tienen mayor prioridad. Un proceso
situado en una cola no puede ejecutarse a menos que estén vacías las colas de nivel
superior. Un proceso en ejecución será desposeído por un proceso que llegue a una cola
superior.

Considérese ahora cómo responde un mecanismo de este tipo a diferentes tipos de
procesos. El mecanismo debe favorecer a los procesos limitados por la E/S para lograr un
buen aprovechamiento de los dispositivos y una respuesta buena para los usuarios
interactivos; y de hecho lo hace porque los procesos limitados por la E/S entrarán en la
red con prioridad alta y se les asignará rápidamente la CPU. El tamaño del cuanto de la
primera cola se elegirá lo suficientemente grande para que la gran mayoría de los trabajos
limitados por la E/S generen una petición de E/S antes de que expire el primer cuanto.
Cuando el proceso solicita E/S, abandona la red y ha obtenido un tratamiento favorable,
tal como se deseaba.

Ahora considérese una tarea limitada por la CPU que necesita mucho tiempo de
procesador. Esa tarea entra en la cola más alta de la red con prioridad alta. Recibe
rápidamente su primera asignación de la CPU, pero su cuanto expira y el proceso se coloca
en la cola del siguiente nivel inferior. En ese momento, el proceso tiene una prioridad
menor que la de los procesos que llegan al sistema, en particular los trabajos limitados por
la E/S, que obtienen primero la CPU. El proceso limitado por la CPU acaba recibiendo ésta,
obtiene un cuanto mayor que en la cola más alta y vuelve a utilizar la totalidad de su
cuanto. Luego es situado al final de la siguiente cola inferior. El proceso sigue
desplazándose a colas inferiores, espera más entre divisiones de tiempo y utiliza todo su
cuanto cada vez que obtiene la CPU ( a menos que sea arrebatada por un proceso
entrante). En algún momento, el proceso limitado por la CPU llega a la cola de nivel
inferior, en donde entrará en una planificación por turno hasta terminar.

Las colas de retroalimentación de niveles múltiples son ideales para separar procesos en
categorías basadas en su necesidad de la CPU. En un sistema de tiempo compartido, cada

vez que un proceso abandona la red de colas puede "marcarse" con la identidad de la
última cola en donde estuvo, y cuando el proceso entra de nuevo en la red de colas,
puede enviarse directamente a la cola en la cual terminó su operación por última vez. En
este caso, el planificador está usando un razonamiento heurístico, según el cual el
comportamiento anterior del proceso es un buen indicador de su comportamiento en un
futuro inmediato. De esta forma, un proceso limitado por la CPU que regresa a la red de
colas no se coloca en las colas de nivel alto donde interferiría con el servicio a los procesos
cortos de prioridad alta o con los limitados por la E/S.

Si los procesos se colocan siempre dentro de la red en la cola que ocuparon la última vez,
será imposible que el sistema responda a cambios de un proceso, por ejemplo, de estar
limitado por la CPU, a estar limitado por la E/S. El problema puede resolverse marcando al
proceso también con su duración dentro de la red la última vez que estuvo en ella. Así,
cuando el proceso entra de nuevo en la red puede colocarse en la cola correcta. Entonces,
si el proceso entra en una fase nueva en la cual deja de estar limitado por la CPU y
empieza a estar limitado por la E/S, el proceso experimentará en principio un tratamiento
lento mientras el sistema determina que la naturaleza del proceso está cambiando. Pero
el mecanismo de planificación responderá con rapidez a este cambio. Otra forma de hacer
que el sistema responda a los cambios de comportamiento de los procesos es permitir
que un proceso ascienda un nivel en la red de colas cada vez que abandona
voluntariamente la CPU antes de que expire su cuanto.

El mecanismo de colas de retroalimentación de niveles múltiples es un buen ejemplo de
mecanismo adaptativo, que responde a los cambios en el comportamiento del sistema
que controla. Los mecanismos adaptativos implican, en general, una carga extra mayor
que los no adaptativos, pero la sensibilidad ante los cambios en el sistema da como
resultado una mejor capacidad de respuesta, y justifica el aumento en el gasto extra.
Una variante común del mecanismo de colas de retroalimentación de múltiples niveles
consiste en hacer que un proceso circule por turno varias veces en cada cola antes de
pasar a la siguiente cola inferior. El número de ciclos en cada cola crece por lo regular
cuando el proceso pasa a la siguiente cola inferior.