Algoritmo De Planificación Mediante Colas Multinivel

UNIVERSIDAD TECNICA PARTICULAR DE LOJA

La Universidad Católica de Loja

Escuela de Ciencias de la Computación

Titulación de Sistemas Informáticos y Computación

Algoritmo de planificación mediante colas multinivel

Integrantes:

Freddy Vera

Carlos Ojeda

Francisco Vargas

Cristian Lluay

Docentes: Fernanda Maricela Soto Guerrero

Fecha: 01/04/13

Período académico

Abril 2013 - Agosto 2013

INTRODUCCIÓN

Otra clase de algoritmos de planificación es la que se ha desarrollado para aquellas situaciones en las que los procesos pueden clasificarse fácilmente en grupos diferentes. Por ejemplo, una clasificación habitual consiste en diferenciar entre procesos de primer plano (interactivos) y procesos de segundo plano (por lotes). Estos dos tipos de procesos tienen requisitos diferentes de tiempo de respuesta y, por tanto, pueden tener distintas necesidades de planificación. Además, los procesos de primer plano pueden tener prioridad (definida externamente) sobre los procesos de segundo plano.

Un algoritmo de planificación mediante colas multinivel divide la cola de procesos preparados en varias colas distintas. Los procesos se asignan permanentemente a una cola, generalmente en función de alguna propiedad del proceso, como por ejemplo el tamaño memoria, la prioridad del proceso o el tipo de proceso. Cada cola tiene su propio algoritmo de planificación. Por ejemplo, pueden emplearse colas distintas para los procesos de primer plano y de segundo plano. La cola de primer plano puede planificarse mediante un algoritmo por turnos, mientras que para la cola de segundo plano puede emplearse un algoritmo FCFS.

Además , debe definirse una planificación entre las colas, la cual suele implementarse como una planificación apropiada y prioridad fija. Por ejemplo, la cola de procesos de primer plano puede tener velocidad absoluta sobre la cola de procesos de segundo plano.

Veamos un ejemplo de algoritmo de planificación mediante colas multinivel con las cinco colas que se enumeran a continuación, según su orden de prioridad:

1. Procesos del sistema.

2. Procesos interactivos.

3. Procesos de edición interactivos.

4. Procesos por lotes.

5. Procesos de estudiantes.

Cada cola tiene prioridad absoluta sobre las colas de prioridad más baja. Por ejemplo, ningún proceso de la cola por lotes podrá ejecutarse hasta que se hayan vaciado completamente las colas de los procesos del sistema, los procesos interactivos y los procesos de edición interactivos. Si un proceso de edición interactivo llega a la cola de procesos preparados mientras se está ejecutando un proceso por lotes, el proceso por lotes será desalojado.

Otra posibilidad consiste en repartir el tiempo entre las colas. En este caso, cada cola obtiene una cierta porción del tiempo de CPU, con la que puede entonces planificar sus distintos procesos Por ejemplo, en el caso de la colas de procesos de primer plano y segundo plano, la cola de primer plano puede disponer del 80 por ciento del tiempo de CPU para planificar por turnos sus procesos, mientras que la cola de procesos de segundo plano recibe el 20 por ciento del tiempo de CPU para gestionar sus procesos mediante el método FCFS.

Figura 01. Ilustración del algoritmo de planificación mediante colas multinivel.

EXPLICACIÓN DEL MODELO

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).

Las colas múltiples son una solución a la problemática que se presenta cuando en los sistemas operativos coexisten procesos con diferentes necesidades. Por ejemplo: pueden haber procesos interactivos, los cuales requieren una planificación de tiempo compartido adecuada, pero quizás haya que ejecutar también procesos de tiempo real, que no pueden estar sujetos a una expulsión por tiempo.

Por ello si fuera posible identificar en un sistema, clases diferenciadas de procesos (por ejemplo: tiempo real, interactivos, por lotes, …), se tendría interés en establecer una cola de listos para cada clase de procesos. La política de planificación se basa en algún esquema predeterminado, que da un tratamiento especial a los trabajos de cada cola.

Para este algoritmo se requieren dos niveles de planificación:

1. Planificación dentro de cada cola: Cada cola puede utilizar su propia política de planificación, de acuerdo a la clase de procesos que acoge, la cual puede ser usando diferentes algoritmos (FCFS, Round Robin, etc.).

2. Planificación entre colas:

o Se le asigna una prioridad (P) a cada cola.

o Se le asigna un Quantum de CPU a cada cola, que se reparte entre los procesos de cada cola.

El gráfico muestra las diferentes colas que pueden existir en "Colas Múltiples" (pueden haber menos colas o más colas), por ejemplo la cola para procesos del sistema tiene una prioridad (P) y un quantum de tiempo (Q) en la CPU diferente a las demás. Además las colas pueden estar implementadas con diferentes tipos de algoritmos ya sean con desalojo o sin desalojo. Es válido aclarar que las colas son atendidas en dependencia de su prioridad, por ejemplo:

Para la figura que se muestra, la primera cola en ser atendida es la cola de Procesos del Sistema, la cual tiene una prioridad (P) de 1, y solo después de haberse ejecutado todos los procesos de dicha cola, es que se atienden las próximas colas en dependencia de la prioridad, en caso de que lleguen nuevos procesos a la cola anteriormente atendida, esta vuelve a ser la de mayor prioridad y se deja de atender la cola presente para volver atender dicha cola.

PLANIFICACIÓN MLQ: COLAS MULTINIVEL.

Este algoritmo de planificación clasifica los procesos en diferentes grupos, de forma que podemos asignarlos a diferentes colas con distinta planificación para gestionarlos de la manera que realmente necesitan.

Los procesos se asignan permanentemente a una cola del sistema, generalmente en función de alguna propiedad del proceso, por ejemplo el tamaño de memoria, la prioridad

...