Planificación mediante colas multinivel
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.[1]
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.[1]
Las siglas MLQ y MLFQ son los acrónimos ingleses de multi level queues (colas multinivel) y multi level feedback queues (colas multinivel realimentadas).
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.[2][3][4]
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 del proceso o el tipo de proceso.[4]
Por ejemplo, tenemos el grupo de procesos foreground (interactivos) y background (batch), que necesitan diferentes tiempos de respuesta.[2] Cada uno de ellos estará gestionado en una cola distinta con un algoritmo de planificación distinto, por ejemplo la cola de procesos foreground con Round Robin, y la de procesos background con FCFS.[2][3][4]
Además debe existir un criterio de planificación entre las colas. Puede ser de prioridad fija con requisa o sin requisa, o de prioridad variable con requisa o sin requisa.
En los algoritmos FCFS, SJF y aquellos que utilizan prioridades, un proceso puede permanecer en el procesador hasta que realice una entrada/salida o hasta que termine. Si no termina o no realiza ninguna entrada/salida, el proceso podría llegar a monopolizar la CPU. Para evitar este monopolio, el mecanismo de requisa permite que un proceso pueda ser expulsado del procesador.[1]
El criterio de planificación suele implementarse como prioridad fija con expropiación[2][4]que consiste en que no se puede ejecutar un proceso si hay algún otro en una cola más prioritaria. Y si un proceso se está ejecutando y llega otro proceso más prioritario que él, abandonará el procesador y se lo cederá al proceso con mayor prioridad.
Las características de esta política de planificación son:[2]
- Es apropiativa, es decir si llega un proceso con mayor prioridad que el que se está ejecutando podrá expulsarle y apropiarse del procesador.
- Cada cola tendrá una prioridad interna, de acuerdo a su algoritmo de planificación. Y cuando un proceso entre en la cola, automáticamente se calculará su prioridad interna. Esto no afectará al funcionamiento global de las colas múltiples.
- El proceso que se ejecutará será el de mayor prioridad. Y si hubiera varios, se elegirá el mayor según las normas de las políticas de gestión correspondientes.
Si aplicamos la planificación apropiativa de prioridad fija al ejemplo anterior, la cola de procesos foreground será más prioritaria que la de procesos background.[2] Mientras haya procesos en la cola de foreground, los de la cola de background no se podrán ejecutar.
Otra posibilidad sería realizar la expulsión con intervalos periódicos o quantum, repartiendo el tiempo entre las colas.[3][4][5]
En resumen, este algoritmo se puede definir por los siguientes parámetros:
- El número de colas.
- El algoritmo de planificación de cada cola.
- El algoritmo de planificación entre las distintas colas.
- El método usado para determinar en qué cola se introducirá un proceso cuando haya que darle servicio.
Planificación MLFQ: colas multinivel con realimentación.
El algoritmo de colas multinivel presenta baja carga de planificación pero es poco flexible.[4]
Mediante la planificación con colas multinivel realimentadas, un proceso se puede mover de una cola a otra dependiendo de su comportamiento en tiempo de ejecución.[6][3][4]
En las colas multinivel realimentadas se separan los procesos en grupos pero dependiendo de las características de su ráfaga de CPU. Los procesos con ráfagas cortas irán a una cola más prioritaria de procesos preparados que los procesos con ráfagas largas.[4]
El funcionamiento de este algoritmo consiste en ejecutar los procesos de la cola de prioridad más alta, a continuación se pasan a ejecutar los procesos de la siguiente cola y así sucesivamente. Con esta distribución, los procesos con ráfagas cortas se ejecutarán de forma rápida sin necesidad de llegar muy lejos en la jerarquía de colas de listos. Mientras que los procesos con ráfagas largas irán degradándose gradualmente.[5][6]
Para gestionar a los procesos de la forma más justa, es necesario conocer su longitud, si están limitados por entrada/salida o por el procesador, la memoria que van a necesitar, etc.[2]
La forma óptima de atenderlos es:
- Establecer una preferencia para los trabajos más cortos y penalizar a los que se han estado ejecutando durante más tiempo.[5]
- Favorecer a los trabajos limitados por entrada/salida, para mantener los recursos ocupados y dejar el procesador libre el mayor tiempo posible.[2]
En general, a un proceso se le concede un tiempo T de permanencia en una cola, cuando lo supera, pasará a la cola inmediatamente inferior con menor prioridad, es decir, se disminuirá su prioridad en una unidad.[2] La elección del valor que se le dará al tiempo T varía mucho de un sistema a otro, depende del número de procesos existentes, del tipo de procesos y del número de colas.
Se pueden usar mecanismos de envejecimiento para evitar el bloqueo indefinido de un proceso, estos mecanismos consisten en incrementar la prioridad de los procesos que estén demasiado tiempo esperando en una cola de prioridad baja, para pasarlos a una cola de prioridad más alta y que se puedan ejecutar antes.[4]
En resumen, este algoritmo se puede definir por los siguientes parámetros:[4][3][2][1]
- El número de colas.
- El algoritmo de planificación de cada cola.
- El algoritmo de planificación entre las distintas colas.
- El método usado para determinar cuándo pasar un proceso a una cola de prioridad más alta.
- El método usado para determinar cuándo pasar un proceso a una cola de prioridad más baja.
- El método usado para determinar en qué cola se introducirá un proceso cuando haya que darle servicio.
Referencias
- ↑ Sánchez, Sebastián A. (2005). Sistemas Operativos. Alcalá de Henares: Servicio de Publicaciones de UAH.
- ↑ Pérez-Campanero, Juan A.; Morena, Juan M. (2002). Conceptos De Sistemas Operativos. Madrid: Universidad Pontificia de Comillas.
- ↑ Aranda, Joaquin; Canto, Mª Antonia; De La Cruz, Jesus Manuel; Dormido, Sebastian; Mañoso, Carolina (2002). Sistemas Operativos, Teoría y problemas. Madrid: Sanz y Torres.
- ↑ Silberschatz, Abraham; Galvin, Peter.B.; Gagne, Greg (2006). Fundamentos de Sistemas Operativos (7ª edición). Madrid: McGraw Hill.
- ↑ Stallings, William (2005). Sistemas Operativos, Aspectos internos y principios de diseño (5ª edición). Madrid: Prentice Hall.
- ↑ Milenkovic, Milan (1989). Sistemas Operativos, conceptos y diseño (2ª edición). Madrid: McGraw-Hill.
Bibliografía complementaria
Tanenbaum, Andrew (1998). Sistemas Operativos, Diseño e Implementación (2ª edición). México: Prentice Hall.