Hispanopedia WikiEn informática , una cola de retroalimentación multinivel es un algoritmo de planificación . Los algoritmos de planificación están diseñados para que siempre haya algún proceso en ejecución para mantener ocupada la unidad central de procesamiento (CPU). [ 1 ] La cola de retroalimentación multinivel extiende los algoritmos estándar con los siguientes requisitos de diseño:
- Separe los procesos en varias colas de procesos listos según su necesidad de procesador.
- Dar preferencia a los procesos con ráfagas cortas de CPU.
- Dar preferencia a los procesos con altas ráfagas de E/S . (Los procesos con uso intensivo de E/S permanecerán en la cola de espera para dar tiempo de CPU a otros procesos).
La cola de retroalimentación multinivel fue desarrollada por primera vez por Fernando J. Corbató (1962). [ 2 ] Por este logro, la Association for Computing Machinery otorgó a Corbató el Premio Turing . [ 3 ]
Programación de procesos
Mientras que el algoritmo de cola multinivel mantiene los procesos asignados permanentemente a sus asignaciones de cola iniciales, la cola de retroalimentación multinivel desplaza los procesos entre colas. [ 4 ] El desplazamiento depende de las ráfagas de CPU de segmentos de tiempo anteriores . [ 5 ]
- Si un proceso consume demasiado tiempo de CPU, se moverá a una cola de menor prioridad.
- Si un proceso está limitado por operaciones de entrada/salida o es un proceso interactivo, se moverá a una cola de mayor prioridad.
- Si un proceso espera demasiado tiempo en una cola de baja prioridad y se queda sin recursos , pasará a una cola de mayor prioridad.
Algoritmo
Se utilizan varias colas FIFO y el funcionamiento es el siguiente:
- Se inserta un nuevo proceso al final (cola) de la cola FIFO de nivel superior.
- En algún momento el proceso llega al principio de la cola y se le asigna la CPU .
- Si el proceso se completa dentro del intervalo de tiempo de la cola asignada, sale del sistema.
- Si el proceso cede voluntariamente el control de la CPU, abandona la red de colas y, cuando vuelve a estar listo, se inserta al final de la misma cola que cedió anteriormente.
- Si el proceso utiliza todo el tiempo cuántico, se interrumpe y se inserta al final de la siguiente cola de nivel inferior. Esta siguiente cola de nivel inferior tendrá un cuanto de tiempo mayor que el de la cola de nivel superior anterior.
- Este esquema continuará hasta que el proceso finalice o llegue a la cola de nivel base.
- En la cola de nivel base, los procesos circulan de forma rotativa hasta que finalizan y abandonan el sistema. Los procesos en la cola de nivel base también pueden programarse según el principio de primero en llegar, primero en ser atendido . [ 6 ]
- Opcionalmente, si un proceso se bloquea por una operación de entrada/salida, se le da prioridad un nivel y se coloca al final de la siguiente cola superior. Esto permite que el planificador dé prioridad a los procesos que se ven afectados por operaciones de entrada/salida y que otros procesos escapen de la cola de nivel base.
Para la planificación, el planificador siempre comienza a seleccionar procesos del inicio de la cola de nivel superior. Solo si la cola de nivel superior se vacía, el planificador seleccionará un proceso de la siguiente cola de nivel inferior. Se aplica la misma política para la selección en las colas de nivel inferior subsiguientes. Mientras tanto, si un proceso llega a cualquiera de las colas de nivel superior, interrumpirá a un proceso en la cola de nivel inferior.
Además, un nuevo proceso siempre se inserta al final de la cola de nivel superior, bajo el supuesto de que se completará en poco tiempo. Los procesos largos se desplazan automáticamente a colas de nivel inferior según su tiempo de procesamiento y nivel de interactividad. En la cola de retroalimentación multinivel, un proceso tiene una sola oportunidad de completarse en un nivel de cola determinado antes de ser desplazado a una cola de nivel inferior.
Parámetros de programación
En general, un planificador de cola de retroalimentación multinivel se define mediante los siguientes parámetros: [ 6 ]
- El número de colas.
- El algoritmo de planificación para cada cola puede ser diferente de FIFO.
- Método utilizado para determinar cuándo promover un proceso a una cola de mayor prioridad.
- Método utilizado para determinar cuándo degradar un proceso a una cola de menor prioridad.
- Método utilizado para determinar en qué cola entrará un proceso cuando necesite servicio.
Véase también
Referencias
- ↑ Silberschatz, Abraham (1994). Conceptos de sistemas operativos, cuarta edición . Addison-Wesley. pág. 131. ISBN 978-0-201-50480-4.
- ↑ Corbató, Fernando J.; Merwin-Daggett, Marjorie; Daley, Robert C. (1962). "Un sistema experimental de tiempo compartido". Actas de la conferencia conjunta de computación de primavera del 1 al 3 de mayo de 1962 - AIEE-IRE '62 (Primavera) . pág. 335. doi : 10.1145/1460833.1460871 . S2CID 14363753 .
- ↑ Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014). "Cola de retroalimentación multinivel". Sistemas operativos: tres piezas fáciles (PDF) . Libros de Arpaci-Dusseau.
- ↑ Silberschatz, Abraham (1994). Conceptos de sistemas operativos, cuarta edición . Addison-Wesley. pág. 147. ISBN 978-0-201-50480-4.
- ↑ Silberschatz, Abraham (1994). Conceptos de sistemas operativos, cuarta edición . Addison-Wesley. pág. 148. ISBN 978-0-201-50480-4.
- 1 2 Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2008). Conceptos de sistemas operativos (8.ª ed.). Hoboken, NJ: Wiley. pág. 198. ISBN 978-0470128725.
Enlaces externos
- Planificadores de cola de retroalimentación multinivel — Tiempo compartido de Solaris 2.6
- Modelos de colas con compartición de procesador de disciplinas de planificación mixtas para sistemas de tiempo compartido
- Algoritmos de planificación de procesadores
