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í . 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 =)
Introducción al programador
La esencia del problema: cómo desarrollar una política de planificación
¿Cómo deberían diseñarse los marcos de políticas subyacentes del programador? ¿Cuáles deberían ser los supuestos clave? ¿Qué métricas son importantes? ¿Qué técnicas básicas se utilizaron en los primeros sistemas informáticos?
Supuestos de carga de trabajo
Antes de discutir posibles políticas, primero hagamos algunas digresiones simplificadoras sobre los procesos que se ejecutan en el sistema, que colectivamente se denominan carga de trabajo. Definir la carga de trabajo es una parte fundamental de la creación de políticas y cuanto más sepa sobre la carga de trabajo, mejor será la política que podrá redactar.
Hagamos las siguientes suposiciones sobre los procesos que se ejecutan en el sistema, a veces también llamados recibas nuevas vacantes en tu correo (tareas). Casi todos estos supuestos no son realistas, pero son necesarios para el desarrollo del pensamiento.
- Cada tarea se ejecuta durante la misma cantidad de tiempo,
- Todas las tareas se establecen simultáneamente,
- La tarea asignada trabaja hasta su finalización,
- Todas las tareas usan solo CPU,
- Se conoce el tiempo de ejecución de cada tarea.
Métricas del programador
Además de algunas suposiciones sobre la carga, se necesita otra herramienta para comparar diferentes políticas de programación: las métricas del programador. Una métrica es solo una medida de algo. Hay una serie de métricas que se pueden utilizar para comparar programadores.
Por ejemplo, usaremos una métrica llamada tiempo de respuesta (tiempo de respuesta). El tiempo de respuesta de la tarea se define como la diferencia entre el tiempo de finalización de la tarea y el tiempo de llegada de la tarea al sistema.
Tturnaround=Tcompleción-Tarrival
Como asumimos que todas las tareas llegaron al mismo tiempo, entonces Ta=0 y por tanto Tt=Tc. Este valor cambiará naturalmente cuando cambiemos los supuestos anteriores.
Otra métrica - justicia (justicia, honestidad). La productividad y la justicia son a menudo características opuestas en la planificación. Por ejemplo, el programador puede optimizar el rendimiento, pero a costa de esperar a que se ejecuten otras tareas, lo que reduce la equidad.
PRIMERO EN ENTRAR, PRIMERO EN SALIR (FIFO)
El algoritmo más básico que podemos implementar se llama FIFO o primero en llegar, primero en ser servido (salida). Este algoritmo tiene varias ventajas: es muy fácil de implementar, se ajusta a todas nuestras suposiciones y hace su trabajo bastante bien.
Veamos un ejemplo sencillo. Digamos que se establecieron 3 tareas simultáneamente. Pero supongamos que la tarea A llegó un poco antes que todas las demás, por lo que aparecerá en la lista de ejecución antes que las demás, al igual que B con respecto a C. Supongamos que cada una de ellas se ejecutará durante 10 segundos. ¿Cuál será el tiempo promedio para completar estas tareas en este caso?
Contando los valores: 10+20+30 y dividiéndolos por 3, obtenemos el tiempo promedio de ejecución del programa igual a 20 segundos.
Ahora intentemos cambiar nuestras suposiciones. En particular, el supuesto 1 y, por lo tanto, ya no asumiremos que cada tarea requiere la misma cantidad de tiempo para ejecutarse. ¿Cómo funcionará FIFO esta vez?
Resulta que los diferentes tiempos de ejecución de tareas tienen un impacto extremadamente negativo en la productividad del algoritmo FIFO. Supongamos que la tarea A tardará 100 segundos en completarse, mientras que B y C tardarán 10 segundos cada una.
Como puede verse en la figura, el tiempo promedio del sistema será (100+110+120)/3=110. Este efecto se llama efecto convoy, cuando algunos consumidores a corto plazo de un recurso hacen cola después de un gran consumidor. Es como la fila del supermercado cuando hay un cliente frente a ti con el carrito lleno. La mejor solución al problema es intentar cambiar la caja registradora o relajarse y respirar profundamente.
Trabajo más corto primero
¿Es posible resolver de alguna manera una situación similar con procesos pesados? Ciertamente. Otro tipo de planificación se llamaTrabajo más corto primero (SJF). Su algoritmo también es bastante primitivo: como su nombre indica, las tareas más cortas se ejecutarán primero, una tras otra.
En este ejemplo, el resultado de ejecutar los mismos procesos será una mejora en el tiempo promedio de respuesta del programa y será igual a 50 en lugar de 110, que es casi 2 veces mejor.
Por lo tanto, bajo el supuesto de que todas las tareas llegan al mismo tiempo, el algoritmo SJF parece ser el algoritmo más óptimo. Sin embargo, nuestras suposiciones todavía no parecen realistas. Esta vez cambiamos el supuesto 2 y esta vez imaginamos que las tareas pueden estar presentes en cualquier momento y no todas al mismo tiempo. ¿A qué problemas puede conducir esto?
Imaginemos que la tarea A (100c) llega primero y comienza a ejecutarse. En t=10 llegan las tareas B y C, cada una de las cuales tardará 10 segundos. Entonces, el tiempo promedio de ejecución es (100+(110-10)+(120-10))3 = 103. ¿Qué podría hacer el programador para mejorar esto?
Primero el tiempo de finalización más corto (STCF)
Para mejorar la situación, omitimos el supuesto 3 de que el programa se inicia y se ejecuta hasta su finalización. Además, necesitaremos soporte de hardware y, como puedes imaginar, usaremos temporizador para interrumpir una tarea en ejecución y cambio de contexto. Por lo tanto, el programador puede hacer algo en el momento en que llegan las tareas B, C: detener la ejecución de la tarea A y poner en procesamiento las tareas B y C y, una vez completadas, continuar ejecutando el proceso A. Dicho programador se llama STCFo Trabajo preventivo primero.
El resultado de este planificador será el siguiente resultado: ((120-0)+(20-10)+(30-10))/3=50. Por lo tanto, dicho programador se vuelve aún más óptimo para nuestras tareas.
Tiempo de respuesta métrico
Así, si conocemos el tiempo de ejecución de las tareas y que estas tareas sólo utilizan CPU, STCF será la mejor solución. Y una vez, en los primeros tiempos, estos algoritmos funcionaron bastante bien. Sin embargo, el usuario ahora pasa la mayor parte de su tiempo en la terminal y espera una experiencia interactiva productiva. Así nació una nueva métrica: tiempo de respuesta (respuesta).
El tiempo de respuesta se calcula de la siguiente manera:
Trespuesta = Tprimera ejecución − Tarrival
Así, para el ejemplo anterior, el tiempo de respuesta será: A=0, B=0, C=10 (abg=3,33).
Y resulta que el algoritmo STCF no es tan bueno en una situación en la que llegan 3 tareas al mismo tiempo: habrá que esperar hasta que las tareas pequeñas se completen por completo. Entonces, el algoritmo es bueno para la métrica del tiempo de respuesta, pero malo para la métrica de interactividad. Imagínese si estuviera sentado frente a una terminal intentando escribir caracteres en un editor y tuviera que esperar más de 10 segundos porque alguna otra tarea estaba consumiendo la CPU. No es muy agradable.
Entonces nos enfrentamos a otro problema: ¿cómo podemos crear un programador que sea sensible al tiempo de respuesta?
Round Robin
Se desarrolló un algoritmo para resolver este problema. Round Robin (RR). La idea básica es bastante simple: en lugar de ejecutar tareas hasta que se completen, ejecutaremos la tarea durante un cierto período de tiempo (llamado intervalo de tiempo) y luego cambiaremos a otra tarea de la cola. El algoritmo repite su trabajo hasta que se completan todas las tareas. En este caso, el tiempo de ejecución del programa debe ser múltiplo del tiempo después del cual el temporizador interrumpirá el proceso. Por ejemplo, si un temporizador interrumpe un proceso cada x=10 ms, entonces el tamaño de la ventana de ejecución del proceso debe ser múltiplo de 10 y ser 10,20 o x*10.
Veamos un ejemplo: las tareas ABC llegan simultáneamente al sistema y cada una de ellas quiere ejecutarse durante 5 segundos. El algoritmo SJF completará cada tarea antes de comenzar otra. Por el contrario, el algoritmo RR con una ventana de inicio = 1 s realizará las tareas de la siguiente manera (Fig. 4.3):
(SJF otra vez (malo para el tiempo de respuesta)
(Round Robin (bueno para el tiempo de respuesta)
El tiempo de respuesta promedio para el algoritmo RR es (0+1+2)/3=1, mientras que para el SJF (0+5+10)/3=5.
Es lógico suponer que la ventana de tiempo es un parámetro muy importante para RR; cuanto menor es, mayor es el tiempo de respuesta. Sin embargo, no debería hacerlo demasiado pequeño, ya que el tiempo de cambio de contexto también influirá en el rendimiento general. Por lo tanto, la elección del tiempo de la ventana de ejecución la establece el arquitecto del sistema operativo y depende de las tareas que se planean ejecutar en él. Cambiar de contexto no es la única operación de servicio que hace perder tiempo: el programa en ejecución funciona con muchas otras cosas, por ejemplo, varios cachés, y con cada cambio es necesario guardar y restaurar este entorno, lo que también puede requerir mucho tiempo. tiempo.
RR es un gran programador si habláramos solo de la métrica del tiempo de respuesta. Pero, ¿cómo se comportará la métrica del tiempo de respuesta de la tarea con este algoritmo? Considere el ejemplo anterior, cuando el tiempo de funcionamiento de A, B, C = 5 s y llegan al mismo tiempo. La tarea A finalizará a las 13, la B a las 14, la C a las 15 y el tiempo medio de respuesta será de 14 s. Por tanto, RR es el peor algoritmo para la métrica de rotación.
En términos más generales, cualquier algoritmo de tipo RR es justo: divide el tiempo de CPU por igual entre todos los procesos. Y, por tanto, estas métricas entran en conflicto constantemente entre sí.
Por lo tanto, tenemos varios algoritmos contrastantes y al mismo tiempo todavía quedan varias suposiciones: que se conoce el tiempo de la tarea y que la tarea solo utiliza la CPU.
Mezclando con E/S
En primer lugar, eliminemos el supuesto 4 de que el proceso solo utiliza la CPU; naturalmente, este no es el caso y los procesos pueden acceder a otros equipos.
En el momento en que cualquier proceso solicita una operación de E/S, el proceso entra en estado bloqueado, esperando a que se complete la E/S. Si la E/S se envía al disco duro, dicha operación puede tardar varios ms o más y el procesador estará inactivo en ese momento. Durante este tiempo, el planificador puede ocupar el procesador con cualquier otro proceso. La siguiente decisión que tendrá que tomar el planificador es cuándo el proceso completará su E/S. Cuando esto suceda, se producirá una interrupción y el sistema operativo pondrá el proceso que llamó a la E/S en estado listo.
Veamos un ejemplo de varias tareas. Cada uno de ellos requiere 50 ms de tiempo de CPU. Sin embargo, el primero accederá a E/S cada 10 ms (que también se ejecutará cada 10 ms). Y el proceso B simplemente usa un procesador de 50 ms sin E/S.
En este ejemplo usaremos el programador STCF. ¿Cómo se comportará el planificador si se inicia en él un proceso como A? Hará lo siguiente: primero resolverá completamente el proceso A y luego el proceso B.
El enfoque tradicional para resolver este problema es tratar cada subtarea de 10 ms del proceso A como una tarea separada. Por lo tanto, al comenzar con el algoritmo STJF, la elección entre una tarea de 50 ms y una tarea de 10 ms es obvia. Luego, cuando se complete la subtarea A, se iniciarán el proceso B y la E/S. Una vez completada la E/S, será habitual iniciar nuevamente el proceso A de 10 ms en lugar del proceso B. De esta manera, es posible implementar la superposición, donde otro proceso utiliza la CPU mientras el primero espera la finalización. E/S. Y como resultado, el sistema se utiliza mejor: en el momento en que los procesos interactivos esperan E/S, se pueden ejecutar otros procesos en el procesador.
El Oráculo ya no existe
Ahora intentemos deshacernos de la suposición de que se conoce el tiempo de ejecución de la tarea. Esta es generalmente la peor y más irreal suposición de toda la lista. De hecho, en el sistema operativo ordinario promedio, el sistema operativo en sí generalmente sabe muy poco sobre el tiempo de ejecución de las tareas, entonces, ¿cómo se puede crear un programador sin saber cuánto tiempo llevará ejecutar la tarea? ¿Quizás podríamos utilizar algunos principios de RR para resolver este problema?
Total
Analizamos las ideas básicas de la programación de tareas y analizamos 2 familias de programadores. El primero comienza primero la tarea más corta y, por lo tanto, aumenta el tiempo de respuesta, mientras que el segundo se divide entre todas las tareas por igual, lo que aumenta el tiempo de respuesta. Ambos algoritmos son malos mientras que los algoritmos de la otra familia son buenos. También analizamos cómo el uso paralelo de CPU y E/S puede mejorar el rendimiento, pero no resolvimos el problema con la clarividencia del sistema operativo. Y en la próxima lección veremos un planificador que mira el pasado inmediato e intenta predecir el futuro. Y se llama cola de retroalimentación multinivel.
Fuente: habr.com