Introducción a los Sistemas Operativos

¡Hola, Habr! Me gustaría llamar su atención sobre una serie de artículos, traducciones de una literatura interesante en mi opinión: OSTEP. Este material analiza con bastante profundidad el trabajo de los sistemas operativos similares a Unix, es decir, el trabajo con procesos, varios programadores, memoria y otros componentes similares que conforman un sistema operativo moderno. Puedes ver el original de todos los materiales aquí aquí. Tenga en cuenta que la traducción se hizo de manera poco profesional (con bastante libertad), pero espero haber conservado el significado general.

El trabajo de laboratorio sobre este tema se puede encontrar aquí:

Otras partes:

También puedes ver mi canal en telegrama =)

Planificación: cola de comentarios de varios niveles

En esta conferencia hablaremos sobre los problemas de desarrollar uno de los enfoques más famosos para
planificación, que se llama Cola de comentarios de varios niveles (MLFQ). El planificador MLFQ fue descrito por primera vez en 1962 por Fernando J. Corbató en un sistema llamado
Sistema de tiempo compartido compatible (CTSS). Estos trabajos (incluidos trabajos posteriores sobre
Multics) fueron posteriormente nominados al Premio Turing. El planificador fue
Posteriormente mejoró y adquirió la apariencia que ya se puede encontrar en
algunos sistemas modernos.

El algoritmo MLFQ intenta resolver dos problemas fundamentales superpuestos.
Primero, intenta optimizar el tiempo de respuesta, que, como comentamos en la lección anterior, se optimiza mediante el método de comenzar más al principio de la cola.
tareas cortas. Sin embargo, el sistema operativo no sabe cuánto tiempo se ejecutará un proceso en particular, y esto
Conocimientos necesarios para el funcionamiento de los algoritmos SJF, STCF. En segundo lugar, MLFQ está intentando
hacer que el sistema responda a los usuarios (por ejemplo, a aquellos que se sientan y
mirar fijamente la pantalla esperando a que se complete la tarea) y así minimizar el tiempo
respuesta. Desafortunadamente, algoritmos como RR mejoran el tiempo de respuesta, pero son extremadamente
tener un impacto negativo en la métrica del tiempo de respuesta. De ahí nuestro problema: ¿Cómo diseñar?
un planificador que cumplirá con nuestros requisitos sin saber nada sobre
¿La naturaleza del proceso en general? ¿Cómo puede el programador aprender las características de las tareas?
que lanza y así tomar mejores decisiones de planificación?

La esencia del problema: ¿Cómo planificar el establecimiento de tareas sin un conocimiento perfecto?
Cómo diseñar un planificador que minimice simultáneamente el tiempo de respuesta
para tareas interactivas y al mismo tiempo minimiza el tiempo de respuesta sin saber
¿Conocimiento del tiempo de ejecución de la tarea?

Nota: aprendemos de eventos anteriores

La cola MLFQ es un excelente ejemplo de un sistema que aprende de
acontecimientos pasados para predecir el futuro. A menudo se utilizan enfoques similares
encontrado en OS (y muchas otras ramas de la informática, incluidas ramas
predicciones de hardware y algoritmos de almacenamiento en caché). Viajes similares
Se activan cuando las tareas tienen fases de comportamiento y, por lo tanto, son predecibles.
Sin embargo, debes tener cuidado con esta técnica porque las predicciones son muy fáciles.
puede resultar incorrecto y llevar al sistema a tomar peores decisiones que las
estaría sin conocimiento alguno.

MLFQ: reglas básicas

Veamos las reglas básicas del algoritmo MLFQ. Y aunque las implementaciones de este algoritmo
Hay varios, los enfoques básicos son similares.
En la implementación que veremos, MLFQ tendrá varios
colas separadas, cada una de las cuales tendrá una prioridad diferente. En cualquier momento,
una tarea lista para su ejecución está en una cola. MLFQ utiliza prioridades,
para decidir qué tarea ejecutar para su ejecución, es decir tarea con mayor
La prioridad (la tarea de la cola con la mayor prioridad) se iniciará primero.
giro.
Por supuesto, puede haber más de una tarea en una cola determinada, por lo que
por lo que tendrán la misma prioridad. En este caso se utilizará el mecanismo
RR para programar una ejecución entre estas tareas.
Así llegamos a dos reglas básicas para MLFQ:

Regla 1: si prioridad (A) > Prioridad (B), se iniciará la tarea A (B no)
Regla 2: Si prioridad (A) = Prioridad (B), A y B se inician usando RR

Con base en lo anterior, los elementos clave para la planificación del MLFQ
son prioridades. En lugar de dar una prioridad fija a cada uno
tarea, MLFQ cambia su prioridad dependiendo del comportamiento observado.
Por ejemplo, si una tarea genera trabajo constantemente en la CPU mientras espera la entrada del teclado,
MLFQ mantendrá alta la prioridad del proceso porque así es como
un proceso interactivo debería funcionar. Si, por el contrario, la tarea es constante y
utiliza mucho la CPU durante un período prolongado, MLFQ la reducirá
una prioridad. Así, MLFQ estudiará el comportamiento de los procesos mientras se ejecutan.
y utilizar comportamientos.
Dibujemos un ejemplo de cómo podrían verse las colas en algún momento.
tiempo y luego obtienes algo como esto:

En este esquema, 2 procesos A y B están en la cola de mayor prioridad. Proceso
C está en algún punto intermedio y el proceso D está al final de la cola. Según lo anterior
Según las descripciones del algoritmo MLFQ, el programador ejecutará tareas solo con el nivel más alto
prioridad según RR, y las tareas C, D quedarán sin trabajo.
Naturalmente, una instantánea estática no dará una imagen completa de cómo funciona MLFQ.
Es importante comprender exactamente cómo cambia la imagen con el tiempo.

Intento 1: Cómo cambiar la prioridad

En este punto, debe decidir cómo MLFQ cambiará el nivel de prioridad.
tareas (y por lo tanto la posición de la tarea en la cola) a medida que avanza a lo largo de su ciclo de vida. Para
esto es necesario tener en cuenta el flujo de trabajo: una cierta cantidad
Tareas interactivas con tiempos de ejecución cortos (y, por lo tanto, lanzamientos frecuentes).
CPU) y varias tareas de larga duración que utilizan la CPU todo su tiempo de trabajo, mientras
El tiempo de respuesta no es importante para este tipo de tareas. Y de esta manera podrás hacer tu primer intento.
Implemente el algoritmo MLFQ con las siguientes reglas:

Regla 3: Cuando una tarea ingresa al sistema, se coloca en la cola con la mayor
prioridad.
Regla 4a: Si una tarea utiliza toda la ventana de tiempo que se le ha asignado, entonces
La prioridad se reduce.
Regla 4b: si una tarea libera la CPU antes de que expire su ventana de tiempo, entonces
sigue teniendo la misma prioridad.

Ejemplo 1: tarea única de larga duración

Como se puede ver en este ejemplo, la tarea de admisión se establece con el nivel más alto
prioridad. Después de una ventana de tiempo de 10 ms, la prioridad del proceso se degrada
planificador. Después de la siguiente ventana de tiempo, la tarea finalmente se degrada a
prioridad más baja en el sistema, donde permanece.

Ejemplo 2: entregó una tarea breve

Ahora veamos un ejemplo de cómo MLFQ intentará acercarse a SJF. En eso
Por ejemplo, dos tareas: A, que es una tarea de larga duración que se ejecuta constantemente.
ocupando CPU y B, que es una tarea interactiva corta. Suponer
que A ya había estado trabajando durante algún tiempo cuando llegó la tarea B.

Este gráfico muestra los resultados del escenario. La tarea A, como cualquier tarea,
El uso de la CPU estaba en el nivel más bajo. La tarea B llegará en el momento T=100 y
colocado en la cola de mayor prioridad. Dado que su tiempo de funcionamiento es corto, entonces
se completará antes de llegar a la última cola.

A partir de este ejemplo, se debe entender el objetivo principal del algoritmo: dado que el algoritmo no
sabe si una tarea es larga o corta, primero que nada asume que la tarea
breve y le da la máxima prioridad. Si esta es una tarea realmente corta, entonces
se completará rápidamente; de lo contrario, si es una tarea larga, avanzará lentamente
prioridad y pronto demostrará que, de hecho, es una tarea larga que no
requiere una respuesta.

Ejemplo 3: ¿Qué pasa con las E/S?

Ahora veamos un ejemplo de E/S. Como se establece en la regla 4b,
si un proceso libera el procesador sin utilizar todo su tiempo de procesador,
entonces permanece en el mismo nivel de prioridad. La intención de esta regla es bastante simple.
- si el trabajo interactivo realiza muchas operaciones de E/S, por ejemplo, espera
desde la tecla del usuario o las pulsaciones del mouse, dicha tarea liberará el procesador
antes de la ventana asignada. No quisiéramos rebajar la prioridad de tal tarea,
y así se mantendrá en el mismo nivel.

Este ejemplo muestra cómo funcionará el algoritmo con dichos procesos: trabajo interactivo B, que solo necesita CPU durante 1 ms antes de su ejecución.
Proceso de E/S y Trabajo A de larga duración, que pasa todo su tiempo utilizando la CPU.
MLFQ mantiene el proceso B en la máxima prioridad porque continúa
liberar la CPU. Si B es una tarea interactiva, entonces el algoritmo ha logrado
Su objetivo es ejecutar tareas interactivas rápidamente.

Problemas con el algoritmo MLFQ actual

En los ejemplos anteriores construimos una versión básica de MLFQ. Y parece que el
hace su trabajo bien y honestamente, distribuyendo el tiempo de CPU de manera justa entre
Tareas largas y permitir tareas cortas o de gran volumen.
trabajar en E/S rápidamente. Desafortunadamente, este enfoque contiene varios
problemas serios.
Primero, el problema del hambre: si el sistema tiene muchos interactivos
tareas, entonces consumirán todo el tiempo de la CPU y, por lo tanto, ni una sola durante mucho tiempo
la tarea no podrá ejecutarse (se mueren de hambre).

En segundo lugar, los usuarios inteligentes podrían escribir sus programas de modo que
engañar al planificador. El engaño consiste en hacer algo para forzar
El programador le da al proceso más tiempo de CPU. Algoritmo que
descrito anteriormente es bastante vulnerable a ataques similares: antes de que la ventana de tiempo sea prácticamente
finalizado, necesita realizar una operación de E/S (a algunos, sin importar qué archivo)
y así liberar la CPU. Tal comportamiento le permitirá permanecer en el mismo
la cola misma y nuevamente obtener un mayor porcentaje de tiempo de CPU. Si lo haces
esto es correcto (por ejemplo, ejecutar el 99% del tiempo de la ventana antes de liberar la CPU),
tal tarea puede simplemente monopolizar el procesador.

Finalmente, un programa puede cambiar su comportamiento con el tiempo. esas tareas
que utiliza la CPU puede volverse interactivo. En nuestro ejemplo, similar
Las tareas no recibirán el tratamiento que merecen por parte del programador como lo harían otras.
Tareas interactivas (iniciales).

Pregunta para el público: ¿qué ataques al planificador podrían llevarse a cabo en el mundo moderno?

Intento 2: aumentar la prioridad

Intentemos cambiar las reglas y ver si podemos evitar problemas con
ayuno. ¿Qué podemos hacer para garantizar que los relacionados
Las tareas de la CPU tendrán su tiempo (aunque no mucho).
Como solución sencilla al problema, puedes sugerir periódicamente.
aumentar la prioridad de todas estas tareas en el sistema. Hay muchas maneras
Para lograr esto, intentemos implementar algo simple como ejemplo: traducir
a todas las tareas se les da inmediatamente la máxima prioridad, de ahí la nueva regla:

Regla5: Después de un cierto período S, mueve todas las tareas del sistema a la cola más alta.

Nuestra nueva regla resuelve dos problemas a la vez. Primero, los procesos
tienen la garantía de no morir de hambre: las tareas que tienen la máxima prioridad se dividirán
Tiempo de CPU según el algoritmo RR y así todos los procesos recibirán
Tiempo de CPU. En segundo lugar, si algún proceso que se utilizaba anteriormente
Sólo el procesador se vuelve interactivo, permanecerá en la cola con el mayor
prioridad después de recibir un aumento único de prioridad al más alto.
Veamos un ejemplo. En este escenario, considere un proceso usando

CPU y dos procesos cortos e interactivos. A la izquierda de la figura, se muestra el comportamiento sin promoción prioritaria y, por lo tanto, la tarea de larga duración comienza a morir de hambre después de que llegan dos tareas interactivas al sistema. En la figura de la derecha, se realiza un aumento de prioridad cada 50 ms y, por lo tanto, se garantiza que todos los procesos recibirán tiempo de CPU y se iniciarán periódicamente. En este caso se toma como ejemplo 50 ms; en realidad, este número es ligeramente mayor.
Obviamente, sumando el tiempo de incremento periódico S se obtiene
una pregunta lógica: ¿qué valor se debe establecer? uno de los homenajeados
Los ingenieros de sistemas John Ousterhout llamaron a tales cantidades en los sistemas como vudú.
constante, ya que de alguna manera requerían magia negra para la correcta
exhibiendo. Y, desafortunadamente, S tiene ese olor. Si estableces el valor también
grandes: las tareas largas comenzarán a morir de hambre. Y si establece el valor demasiado bajo,
Las tareas interactivas no recibirán el tiempo de CPU adecuado.

Intento 3: Mejor contabilidad

Ahora tenemos otro problema que resolver: ¿cómo no
¿Permitir que engañen a nuestro planificador? Los culpables de esta posibilidad son
reglas 4a, 4b, que permiten que un trabajo conserve la prioridad, liberando el procesador
antes de que expire el tiempo asignado. Como lidiar con esto?
La solución en este caso puede considerarse una mejor contabilidad del tiempo de CPU en cada
Nivel MLFQ. En lugar de olvidar el tiempo que utilizó el programa
procesador durante el período asignado, debe tenerse en cuenta y guardarse. Después
el proceso ha agotado su tiempo asignado, debe pasar al siguiente
nivel de prioridad. Ahora no importa cómo utilizará su tiempo el proceso: cómo
Computando constantemente en el procesador o como una serie de llamadas. De este modo,
La regla 4 debe reescribirse a la siguiente forma:

Regla4: Después de que una tarea ha agotado su tiempo asignado en la cola actual (sin importar cuántas veces liberó la CPU), la prioridad de esa tarea disminuye (desciende en la cola).

Veamos un ejemplo:
»

La figura muestra lo que sucede si intentas engañar al planificador, como
si fuera con las reglas anteriores 4a, 4b se obtendría el resultado de la izquierda. Feliz nuevo
la regla es el resultado de la derecha. Antes de la protección, cualquier proceso podría llamar a E/S antes de completarse y
por lo tanto dominan la CPU, después de habilitar la protección, independientemente del comportamiento
E/S, seguirá descendiendo en la cola y, por lo tanto, no podrá realizar operaciones deshonestas.
hacerse cargo de los recursos de la CPU.

Mejorar MLFQ y otros problemas

Con las mejoras anteriores surgen nuevos problemas: uno de los principales
Preguntas: ¿cómo parametrizar dicho programador? Aquellos. cuanto deberia ser
colas? ¿Cuál debería ser el tamaño de la ventana del programa dentro de la cola? Cómo
A menudo se debe aumentar la prioridad del programa para evitar el hambre y
¿Tener en cuenta el cambio en el comportamiento del programa? No hay una respuesta sencilla a estas preguntas.
respuesta y solo experimentos con cargas y configuración posterior
El planificador puede conducir a un equilibrio satisfactorio.

Por ejemplo, la mayoría de las implementaciones de MLFQ le permiten asignar diferentes
intervalos de tiempo para diferentes colas. Las colas de alta prioridad generalmente
Se prescriben intervalos cortos. Estas colas constan de tareas interactivas,
cambiar entre los cuales es bastante sensible y debería tomar 10 o menos
EM. Por el contrario, las colas de baja prioridad consisten en tareas de larga duración que utilizan
UPC. Y en este caso, los intervalos de tiempo largos encajan muy bien (100 ms).

En este ejemplo hay 2 tareas que funcionaron en la cola 20 de alta prioridad
ms, dividido en ventanas de 10 ms. 40 ms en la cola intermedia (ventana de 20 ms) y en la prioridad baja
La ventana de tiempo de cola pasó a ser de 40 ms cuando las tareas completaron su trabajo.

La implementación de MLFQ en el sistema operativo Solaris es una clase de programadores de tiempo compartido.
El planificador proporcionará un conjunto de tablas que definen exactamente como debe
La prioridad del proceso cambia a lo largo de su vida, ¿cuál debería ser el tamaño?
ventana asignada y con qué frecuencia necesita aumentar las prioridades de las tareas. Administrador
Los sistemas pueden interactuar con esta tabla y hacer que el planificador se comporte
diferentemente. Por defecto, esta tabla tiene 60 colas con un aumento gradual.
tamaño de ventana de 20 ms (prioridad alta) a varios cientos de ms (prioridad baja), y
también con un impulso de todas las tareas una vez por segundo.

Otros planificadores de MLFQ no utilizan una tabla ni ningún método específico.
reglas que se describen en esta conferencia, por el contrario, calculan prioridades usando
fórmulas matemáticas. Por ejemplo, el programador de FreeBSD utiliza una fórmula para
calcular la prioridad actual de una tarea en función de la duración del proceso
procesador usado. Además, el uso de la CPU disminuye con el tiempo, por lo que
Por tanto, el aumento de la prioridad se produce de forma algo diferente a la descrita anteriormente. Esto es cierto
llamados algoritmos de decaimiento. Desde la versión 7.1, FreeBSD ha utilizado el programador ULE.

Finalmente, muchos programadores tienen otras características. Por ejemplo, algunos
Los programadores reservan los niveles más altos para el funcionamiento del sistema operativo y, por lo tanto,
Por lo tanto, ningún proceso de usuario puede recibir la máxima prioridad en
sistema. Algunos sistemas te permiten dar consejos para ayudar.
el planificador puede establecer prioridades correctamente. Por ejemplo, usando el comando agradable
puede aumentar o disminuir la prioridad de una tarea y así aumentar o disminuir
reducir las posibilidades del programa de utilizar tiempo de CPU.

MLFQ: Resumen

Hemos descrito un enfoque de planificación llamado MLFQ. Su nombre
incluido en el principio de funcionamiento: tiene varias colas y utiliza retroalimentación
para determinar la prioridad de la tarea.
La forma final de las reglas será la siguiente:

Regla1: Si prioridad (A) > Prioridad (B), se iniciará la tarea A (B no)
Regla2: Si prioridad (A) = Prioridad (B), A y B se inician usando RR
Regla3: Cuando una tarea ingresa al sistema, se coloca en la cola de mayor prioridad.
Regla4: Después de que una tarea ha agotado su tiempo asignado en la cola actual (sin importar cuántas veces liberó la CPU), la prioridad de esa tarea disminuye (desciende en la cola).
Regla5: Después de un cierto período S, mueve todas las tareas del sistema a la cola más alta.

MLFQ es interesante por la siguiente razón: en lugar de requerir conocimientos sobre
naturaleza de la tarea de antemano, el algoritmo estudia el comportamiento pasado de la tarea y establece
prioridades en consecuencia. Por lo tanto, intenta sentarse en dos sillas a la vez, para lograr productividad en tareas pequeñas (SJF, STCF) y, honestamente, trabajar durante mucho tiempo.
Trabajos de carga de CPU. Por lo tanto, muchos sistemas, incluido BSD y sus derivados,
Solaris, Windows y Mac utilizan algún tipo de algoritmo como programador
MLFQ como punto de referencia.

Materiales adicionales:

Fuente: habr.com

Sistemas operativos: tres piezas sencillas. Parte 5: Planificación: cola de comentarios de varios niveles (traducción)