Cola de retroalimentación de varios niveles

Algoritmo de programación de procesamiento

En informática , una cola de retroalimentación multinivel es un algoritmo de programación . Los algoritmos de programación están diseñados para que algún proceso se ejecute en todo momento para mantener ocupada la unidad central de procesamiento (CPU). ^[1] La cola de retroalimentación multinivel amplía los algoritmos estándar con los siguientes requisitos de diseño:

1. Separe los procesos en múltiples colas listas según su necesidad del procesador.
2. Dar preferencia a los procesos con ráfagas cortas de CPU.
3. Dar preferencia a los procesos con altas ráfagas de E/S . (Los procesos limitados por E/S dormirán en la cola de espera para darle 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 le 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 cambia los procesos entre colas. ^[4] El cambio depende de las ráfagas de CPU de los intervalos de tiempo anteriores . ^[5]

• Si un proceso utiliza demasiado tiempo de CPU, se moverá a una cola de menor prioridad.
• Si un proceso está limitado por E/S 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 múltiples colas FIFO y el funcionamiento es el siguiente:

1. Se inserta un nuevo proceso al final (cola) de la cola FIFO de nivel superior .
2. En algún momento, el proceso llega al principio de la cola y se le asigna la CPU .
3. Si el proceso se completa dentro del intervalo de tiempo de la cola dada, abandona el sistema.
4. Si el proceso renuncia voluntariamente al control de la CPU, abandona la red de colas y, cuando vuelve a estar listo, se inserta al final de la misma cola que abandonó anteriormente.
5. Si el proceso utiliza todo el tiempo cuántico, se lo reemplaza y se lo inserta al final de la siguiente cola de nivel inferior. Esta siguiente cola de nivel inferior tendrá un tiempo cuántico mayor que el de la cola de nivel superior anterior.
6. Este esquema continuará hasta que el proceso se complete o llegue a la cola de nivel base.

• En la cola de nivel básico, los procesos circulan en forma circular hasta que se completan y abandonan el sistema. Los procesos en la cola de nivel básico también pueden programarse por orden de llegada . ^[6]
• De manera opcional, si un proceso se bloquea por E/S, se lo promueve a un nivel superior y se lo ubica al final de la cola inmediatamente superior. Esto permite que el programador favorezca a los procesos limitados por E/S y permite que los procesos escapen de la cola de nivel base.

Para la programación, el programador siempre comienza a seleccionar procesos desde la cabecera de la cola de nivel más alto. Solo si la cola de nivel más alto se ha vaciado, el programador seleccionará un proceso de la cola de nivel inferior. La misma política se implementa para la selección en las colas de nivel inferior posteriores. Mientras tanto, si un proceso llega a cualquiera de las colas de nivel superior, reemplazará a un proceso en la cola de nivel inferior.

Además, siempre se inserta un nuevo proceso al final de la cola de nivel superior con la suposición de que se completará en un corto período de tiempo. Los procesos largos se desplazarán automáticamente a las colas de nivel inferior en función de su consumo de tiempo y su nivel de interactividad. En la cola de retroalimentación de varios niveles, a un proceso se le da solo una oportunidad de completarse en un nivel de cola determinado antes de que se lo obligue a pasar a una cola de nivel inferior.

Parámetros de programación

En general, un programador de cola de retroalimentación multinivel se define mediante los siguientes parámetros: ^[6]

• El número de colas.
• El algoritmo de programación para cada cola, que puede ser diferente de FIFO.
• El método utilizado para determinar cuándo promover un proceso a una cola de mayor prioridad.
• El método utilizado para determinar cuándo degradar un proceso a una cola de menor prioridad.
• El método utilizado para determinar a qué cola entrará un proceso cuando ese proceso necesite servicio.

Enlaces externos

• Programadores de colas de retroalimentación de varios niveles: tiempo compartido de Solaris 2.6
• Modelos de colas de uso compartido de procesadores de disciplinas de programación mixtas para sistemas de tiempo compartido

Véase también

• Programación de loterías
• Programación de reparto equitativo
• Programación por turnos

Referencias

1. Silberschatz, Abraham (1994). Conceptos de sistemas operativos, cuarta edición . Addison-Wesley. pág. 131. ISBN 978-0-201-50480-4.
2. Corbató, Fernando J.; Merwin-Daggett, Marjorie; Daley, Robert C. (1962). "Un sistema experimental de tiempo compartido". Actas de la conferencia conjunta de informática de primavera del 1 al 3 de mayo de 1962 sobre - AIEE-IRE '62 (primavera) . pág. 335. doi :10.1145/1460833.1460871. S2CID  14363753.
3. Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014). "Cola de retroalimentación multinivel". Sistemas operativos: tres piezas sencillas (PDF) . Libros de Arpaci-Dusseau.
4. Silberschatz, Abraham (1994). Conceptos de sistemas operativos, cuarta edición . Addison-Wesley. pág. 147. ISBN 978-0-201-50480-4.
5. Silberschatz, Abraham (1994). Conceptos de sistemas operativos, cuarta edición . Addison-Wesley. pág. 148. ISBN 978-0-201-50480-4.
6. Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (2008). Conceptos de sistemas operativos (8.ª ed.). Hoboken, NJ: Wiley. pág. 198. ISBN 978-0470128725.