Programación de CPU
Referencias
- Abraham Silberschatz, Greg Gagne y Peter Baer Galvin, “Conceptos del sistema operativo, octava edición”, Capítulo 5
5.1 Conceptos básicos
- ¿Qué es el algoritmo de Wagner y Fischer y cuál es su código de muestra en C ++?
- ¿Qué calcula este algoritmo? ¿Cuál es su funcionamiento básico? ¿Cuántas veces se ejecuta la operación básica? ¿Cuál es la clase de eficiencia de este algoritmo?
- ¿Debería usar la función de clasificación () incorporada de C ++ para problemas en la programación competitiva, o debería implementar el algoritmo por mi cuenta?
- Cómo implementar la implementación de la pila y la cola en las estructuras de datos
- ¿Qué es un algoritmo explicado para que las personas normales puedan entender y también cómo se hacen?
- Casi todos los programas tienen un ciclo alterno de procesamiento de números de CPU y esperan algún tipo de E / S. (Incluso una simple recuperación de la memoria lleva mucho tiempo en relación con las velocidades de la CPU).
- En un sistema simple que ejecuta un solo proceso, se desperdicia el tiempo de espera de E / S y esos ciclos de CPU se pierden para siempre.
- Un sistema de programación permite que un proceso use la CPU mientras otro está esperando E / S, haciendo uso completo de los ciclos de CPU que de otro modo se perderían.
- El desafío es hacer que el sistema general sea lo más “eficiente” y “justo” posible, sujeto a condiciones variables ya menudo dinámicas, y donde “eficiente” y “justo” son términos algo subjetivos, a menudo sujetos a políticas prioritarias cambiantes.
5.1.1 Ciclo de ráfaga de E / S de CPU
- Casi todos los procesos alternan entre dos estados en un ciclo continuo, como se muestra en la Figura 5.1 a continuación : Una ráfaga de CPU de realizar cálculos y una ráfaga de E / S, esperando la transferencia de datos dentro o fuera del sistema.
- Las ráfagas de CPU varían de un proceso a otro y de un programa a otro, pero un extenso estudio muestra patrones de frecuencia similares a los que se muestran en la Figura 5.2:
5.1.2 Programador de CPU
- Cada vez que la CPU queda inactiva, el trabajo del Programador de la CPU (también conocido como el programador a corto plazo) es seleccionar otro proceso de la cola lista para ejecutarse a continuación.
- La estructura de almacenamiento para la cola lista y el algoritmo utilizado para seleccionar el siguiente proceso no son necesariamente una cola FIFO. Hay varias alternativas para elegir, así como numerosos parámetros ajustables para cada algoritmo, que es el tema básico de todo este capítulo.
5.1.3. Programación preventiva
- Las decisiones de programación de la CPU tienen lugar en una de cuatro condiciones: cuando un proceso cambia del estado de ejecución al estado de espera, como una solicitud de E / S o la invocación de la llamada al sistema wait (). Cuando un proceso cambia del estado de ejecución al estado listo, por ejemplo, en respuesta a una interrupción. Cuando un proceso cambia del estado de espera al estado listo, digamos al finalizar la E / S o al regresar de wait (). Cuando un proceso finaliza.
- Para las condiciones 1 y 4 no hay elección: se debe seleccionar un nuevo proceso.
- Para las condiciones 2 y 3 hay una opción: continuar ejecutando el proceso actual o seleccionar uno diferente.
- Si la programación se lleva a cabo solo en las condiciones 1 y 4, se dice que el sistema no es preventivo o cooperativo . En estas condiciones, una vez que un proceso comienza a ejecutarse, continúa ejecutándose, hasta que se bloquea voluntariamente o hasta que finaliza. De lo contrario, se dice que el sistema es preventivo.
- Windows usó la programación no preventiva hasta Windows 3.xy comenzó a usar la programación preventiva con Win95. Macs usaba no preventivo antes de OSX, y preventivo desde entonces. Tenga en cuenta que la programación preventiva solo es posible en hardware que admite una interrupción del temporizador.
- Tenga en cuenta que la programación preventiva puede causar problemas cuando dos procesos comparten datos, porque un proceso puede interrumpirse en medio de la actualización de las estructuras de datos compartidos. El Capítulo 6 examinará este tema con mayor detalle.
- La aprobación previa también puede ser un problema si el kernel está ocupado implementando una llamada al sistema (por ejemplo, actualizando las estructuras críticas de datos del kernel) cuando ocurre la preferencia. La mayoría de los UNIX modernos abordan este problema haciendo que el proceso espere hasta que la llamada del sistema se haya completado o bloqueado antes de permitir la prevención. Desafortunadamente, esta solución es problemática para los sistemas en tiempo real, ya que la respuesta en tiempo real ya no puede garantizarse.
- Algunas secciones críticas del código se protegen de los problemas de concurrencia al deshabilitar las interrupciones antes de ingresar a la sección crítica y volver a habilitar las interrupciones al salir de la sección. No es necesario decir que esto solo debe hacerse en situaciones poco frecuentes y solo en fragmentos de código muy cortos que terminarán rápidamente (generalmente, solo unas pocas instrucciones de la máquina).
5.1.4 Despachador
- El despachador es el módulo que da el control de la CPU al proceso seleccionado por el planificador. Esta función implica: Cambiar el contexto, Cambiar al modo de usuario, Saltar a la ubicación adecuada en el programa recién cargado.
- El despachador debe ser lo más rápido posible, ya que se ejecuta en cada cambio de contexto. El tiempo que consume el despachador se conoce como latencia de despacho.
5.2 Criterios de programación
- Hay varios criterios diferentes a tener en cuenta al intentar seleccionar el “mejor” algoritmo de programación para una situación y entorno particulares, que incluyen: Utilización de la CPU : idealmente, la CPU estaría ocupada el 100% del tiempo, para perder 0 ciclos de la CPU. En un sistema real, el uso de la CPU debe variar del 40% (con poca carga) al 90% (con mucha carga). Rendimiento : número de procesos completados por unidad de tiempo. Puede variar de 10 / segundo a 1 / hora dependiendo de los procesos específicos. Tiempo de respuesta : tiempo requerido para que se complete un proceso en particular, desde el tiempo de envío hasta la finalización. (Tiempo de reloj de pared.) Tiempo de espera : cuánto tiempo pasan los procesos en la cola de espera esperando su turno para subir a la CPU. ( Promedio de carga : el número promedio de procesos en la cola de espera esperando su turno para ingresar a la CPU. Informado en promedios de 1 minuto, 5 minutos y 15 minutos por “tiempo de actividad” y “quién”.) Tiempo de respuesta : el tiempo empleado en un programa interactivo desde la emisión de un comando hasta el comienzo de una respuesta a ese comando .
- En general, uno quiere optimizar el valor promedio de un criterio (Maximizar la utilización y el rendimiento de la CPU, y minimizar todos los demás). Sin embargo, algunas veces uno quiere hacer algo diferente, como minimizar el tiempo máximo de respuesta.
- A veces es más deseable minimizar la varianza de un criterio que el valor real. Es decir, los usuarios aceptan más un sistema predecible consistente que uno inconsistente, incluso si es un poco más lento.
5.3 Algoritmos de programación
Las siguientes subsecciones explicarán varias estrategias de programación comunes, observando solo una ráfaga de CPU cada una para un pequeño número de procesos. Obviamente, los sistemas reales tienen que lidiar con muchos más procesos simultáneos ejecutando sus ciclos de ráfaga de CPU-I / O.
5.3.1 Programación por orden de llegada, FCFS
- FCFS es muy simple: solo una cola FIFO, como los clientes que hacen cola en el banco o en la oficina de correos o en una copiadora.
- Desafortunadamente, sin embargo, el FCFS puede generar tiempos de espera promedio muy largos, particularmente si el primer proceso para llegar allí lleva mucho tiempo. Por ejemplo, considere los siguientes tres procesos:
Proceso
Tiempo quemado
P1
24
P2
3
P3
3
- En el primer diagrama de Gantt a continuación, el proceso P1 llega primero. El tiempo de espera promedio para los tres procesos es (0 + 24 + 27) / 3 = 17.0 ms.
- En el segundo diagrama de Gantt a continuación, los mismos tres procesos tienen un tiempo de espera promedio de (0 + 3 + 6) / 3 = 3.0 ms. El tiempo de ejecución total para las tres ráfagas es el mismo, pero en el segundo caso dos de las tres terminan mucho más rápido, y el otro proceso solo se retrasa por una pequeña cantidad.
- FCFS también puede bloquear el sistema en un sistema dinámico ocupado de otra manera, conocido como el efecto convoy . Cuando un proceso intensivo de CPU bloquea la CPU, varios procesos intensivos de E / S pueden respaldarse, dejando los dispositivos de E / S inactivos. Cuando el procesador de CPU finalmente abandona la CPU, los procesos de E / S pasan a través de la CPU rápidamente, dejando la CPU inactiva mientras todos hacen cola para E / S, y luego el ciclo se repite cuando el proceso intensivo de CPU vuelve a estar listo cola.
5.3.2 Programación de trabajo más corto primero, SJF
- La idea detrás del algoritmo SJF es elegir el pequeño trabajo más rápido y rápido que se necesita hacer, sacarlo del camino primero y luego elegir el siguiente trabajo más pequeño y más rápido para hacer a continuación.
- (Técnicamente, este algoritmo selecciona un proceso basado en la siguiente ráfaga de CPU más corta, no en el tiempo total del proceso).
- Por ejemplo, el siguiente diagrama de Gantt se basa en los siguientes tiempos de ráfaga de CPU (y en el supuesto de que todos los trabajos llegan al mismo tiempo).
Proceso
Tiempo quemado
P1
6 6
P2
8
P3
7 7
P4
3
- En el caso anterior, el tiempo de espera promedio es (0 + 3 + 9 + 16) / 4 = 7.0 ms (en oposición a 10.25 ms para FCFS para los mismos procesos).
- Se puede demostrar que SJF es el algoritmo de programación más rápido, pero tiene un problema importante: ¿cómo sabe cuánto tiempo durará la próxima ráfaga de CPU? Para los trabajos por lotes a largo plazo, esto se puede hacer en función de los límites que los usuarios establecidos para sus trabajos cuando los envían, lo que los alienta a establecer límites bajos, pero se arriesga a tener que volver a enviar el trabajo si establecen el límite demasiado bajo. Sin embargo, eso no funciona para la programación de CPU a corto plazo en un sistema interactivo. Otra opción sería medir estadísticamente las características de tiempo de ejecución de los trabajos, particularmente si las mismas tareas se ejecutan de forma repetida y previsible. Pero una vez más, eso realmente no es una opción viable para la programación de CPU a corto plazo en el mundo real. Un enfoque más práctico es predecir la duración de la próxima ráfaga, en función de algunas mediciones históricas de los últimos tiempos de ráfaga para este proceso. Un método simple, rápido y relativamente preciso es el promedio exponencial , que se puede definir de la siguiente manera. (El libro usa tau y t para sus variables, pero son difíciles de distinguir entre sí y no funcionan bien en HTML.) Estimar [i + 1] = alpha * burst [i] + (1.0 – alpha) * estimación [i] En este esquema, la estimación anterior contiene el historial de todos los tiempos anteriores, y alfa sirve como factor de ponderación para la importancia relativa de los datos recientes versus el historial pasado. Si alfa es 1.0, se ignora el historial pasado y suponemos que la próxima ráfaga tendrá la misma longitud que la última ráfaga. Si alfa es 0.0, entonces todos los tiempos de ráfaga medidos se ignoran, y simplemente asumimos un tiempo de ráfaga constante. Lo más comúnmente alfa se establece en 0.5, como se ilustra en la Figura 5.3:
- SJF puede ser preventivo o no preventivo. La anticipación ocurre cuando un nuevo proceso llega a la cola de espera que tiene un tiempo de ráfaga predicho más corto que el tiempo restante en el proceso cuya ráfaga está actualmente en la CPU. La SJF preventiva a veces se conoce como la primera programación del tiempo restante más corto.
- Por ejemplo, el siguiente diagrama de Gantt se basa en los siguientes datos:
Proceso
Hora de llegada
Tiempo quemado
P1
0 0
8
P2
1
4 4
P3
2
9
p4
3
5 5
- El tiempo de espera promedio en este caso es ((5 – 3) + (10 – 1) + (17 – 2)) / 4 = 26/4 = 6.5 ms. (A diferencia de 7.75 ms para SJF no preventivo u 8.75 para FCFS).
5.3.3 Programación prioritaria
- La programación de prioridades es un caso más general de SJF, en el que se asigna una prioridad a cada trabajo y el trabajo con la prioridad más alta se programa primero. (SJF utiliza el inverso del siguiente tiempo de ráfaga esperado como prioridad: cuanto menor sea la ráfaga esperada, mayor será la prioridad).
- Tenga en cuenta que, en la práctica, las prioridades se implementan utilizando números enteros dentro de un rango fijo, pero no existe una convención acordada sobre si las prioridades “altas” usan números grandes o números pequeños. Este libro usa un número bajo para prioridades altas, siendo 0 la prioridad más alta posible.
- Por ejemplo, el siguiente diagrama de Gantt se basa en estos tiempos y prioridades de ráfaga de proceso, y produce un tiempo de espera promedio de 8.2 ms:
Proceso
Tiempo quemado
Prioridad
P1
10
3
P2
1
1
P3
2
4 4
P4
1
5 5
P5
5 5
2
- Las prioridades se pueden asignar internamente o externamente. El sistema operativo asigna prioridades internas utilizando criterios como el tiempo de ráfaga promedio, la relación de la actividad CPU / E / S, el uso de recursos del sistema y otros factores disponibles para el núcleo. Los usuarios asignan prioridades externas, en función de la importancia del trabajo, los honorarios pagados, la política, etc.
- La programación de prioridad puede ser preventiva o no preventiva.
- La programación prioritaria puede sufrir un problema importante conocido como bloqueo indefinido o inanición , en el que una tarea de baja prioridad puede esperar para siempre porque siempre hay otros trabajos que tienen mayor prioridad. Si se permite que ocurra este problema, entonces los procesos ocurrirán o se ejecuta eventualmente cuando la carga del sistema se aligera (por ejemplo, a las 2:00 a.m.), o eventualmente se perderá cuando el sistema se apague o falle. (Hay rumores de empleos que se han estancado durante años). Una solución común a este problema es el envejecimiento , en el que las prioridades de los empleos aumentan cuanto más esperan. Bajo este esquema, un trabajo de baja prioridad eventualmente aumentará su prioridad lo suficiente como para que se ejecute.
5.3.4 Programación Round Robin
- La programación de round robin es similar a la programación de FCFS, excepto que las ráfagas de CPU se asignan con límites llamados tiempo cuántico .
- Cuando se da un proceso a la CPU, se establece un temporizador para cualquier valor que se haya establecido para un tiempo cuántico. Si el proceso finaliza su ráfaga antes de que expire el temporizador cuántico de tiempo, se cambia de la CPU al igual que el algoritmo FCFS normal Si el temporizador se apaga primero, el proceso se cambia de la CPU y se mueve al final de la lista de espera.
- La cola lista se mantiene como una cola circular, por lo que cuando todos los procesos han tenido un turno, el programador le da al primer proceso otro turno, y así sucesivamente.
- La programación RR puede dar el efecto de que todos los procesadores compartan la CPU por igual, aunque el tiempo de espera promedio puede ser más largo que con otros algoritmos de programación. En el siguiente ejemplo, el tiempo de espera promedio es de 5.66 ms.
Proceso
Tiempo quemado
P1
24
P2
3
P3
3
- El rendimiento de RR es sensible al tiempo cuántico seleccionado. Si el cuanto es lo suficientemente grande, entonces RR se reduce al algoritmo FCFS; Si es muy pequeño, entonces cada proceso obtiene una décima parte del tiempo del procesador y comparte la CPU por igual.
- PERO , un sistema real invoca gastos generales para cada cambio de contexto, y cuanto menor es el tiempo cuántico, más cambios de contexto hay. (Consulte la Figura 5.4 a continuación.) La mayoría de los sistemas modernos usan un tiempo cuántico entre 10 y 100 milisegundos, y tiempos de cambio de contexto del orden de 10 microsegundos, por lo que la sobrecarga es pequeña en relación con el tiempo cuántico.
- El tiempo de respuesta también varía con el tiempo cuántico, de una manera no aparente. Considere, por ejemplo, los procesos que se muestran en la Figura 5.5:
- En general, el tiempo de respuesta se minimiza si la mayoría de los procesos finalizan su próxima ráfaga de CPU en un tiempo cuántico. Por ejemplo, con tres procesos de ráfagas de 10 ms cada uno, el tiempo de respuesta promedio para 1 ms cuántico es 29, y para 10 ms cuántico se reduce a 20. Sin embargo, si se hace demasiado grande, entonces RR degenera en FCFS. Una regla general es que el 80% de las ráfagas de CPU deberían ser más pequeñas que el tiempo cuántico.
5.3.5 Programación de cola multinivel
- Cuando los procesos se pueden clasificar fácilmente, se pueden establecer múltiples colas separadas, cada una implementando el algoritmo de programación que sea más apropiado para ese tipo de trabajo, y / o con diferentes ajustes paramétricos.
- La programación también debe realizarse entre colas, es decir, programar una cola para obtener tiempo en relación con otras colas. Dos opciones comunes son la prioridad estricta (ningún trabajo en una cola de menor prioridad se ejecuta hasta que todas las colas de mayor prioridad estén vacías) y la operación por turnos (cada cola obtiene un intervalo de tiempo, posiblemente de diferentes tamaños).
- Tenga en cuenta que, según este algoritmo, los trabajos no pueden cambiar de cola a cola: una vez que se les asigna una cola, esa es su cola hasta que terminan.
5.3.6 Programación de cola de retroalimentación multinivel
- La programación de colas de retroalimentación multinivel es similar a la programación de colas multinivel ordinaria descrita anteriormente, excepto que los trabajos se pueden mover de una cola a otra por una variedad de razones: si las características de un trabajo cambian entre uso intensivo de CPU e I / O, entonces puede ser apropiado para cambiar un trabajo de una cola a otra. También se puede incorporar el envejecimiento, de modo que un trabajo que ha esperado durante mucho tiempo puede pasar a una cola de mayor prioridad durante un tiempo.
- La programación de la cola de retroalimentación multinivel es la más flexible, ya que se puede ajustar para cualquier situación. Pero también es el más complejo de implementar debido a todos los parámetros ajustables. Algunos de los parámetros que definen uno de estos sistemas incluyen: El número de colas. El algoritmo de programación para cada cola. Los métodos utilizados para actualizar o degradar procesos de una cola a otra. (Que puede ser diferente). El método utilizado para determinar en qué cola ingresa un proceso inicialmente.
5.4 Programación de hilos
- El planificador de procesos programa solo los hilos del núcleo.
- La biblioteca de subprocesos asigna los subprocesos de usuario a los subprocesos del núcleo: el sistema operativo (y en particular el planificador) no los conoce.
5.4.1 Alcance de contención
- El alcance de contención se refiere al alcance en el que los hilos compiten por el uso de CPU físicas.
- En los sistemas que implementan subprocesos muchos a uno y muchos a muchos , se produce Process Contention Scope, PCS , porque se produce competencia entre los subprocesos que forman parte del mismo proceso. (Esta es la gestión / programación de múltiples subprocesos de usuario en un solo subproceso del núcleo, y es administrada por la biblioteca de subprocesos).
- System Contention Scope, SCS, implica que el planificador del sistema programe subprocesos del núcleo para que se ejecuten en una o más CPU. Los sistemas que implementan subprocesos uno a uno (XP, Solaris 9, Linux) usan solo SCS.
- La programación de PCS generalmente se realiza con prioridad, donde el programador puede establecer y / o cambiar la prioridad de los hilos creados por sus programas. Incluso el corte de tiempo no está garantizado entre hilos de igual prioridad.
5.4.2 Programación de subprocesos
- La biblioteca Pthread proporciona la especificación de la contención del alcance: PTHREAD_SCOPE_PROCESS programa subprocesos utilizando PCS, programando subprocesos de usuario en los LWP disponibles utilizando el modelo de varios a muchos. modelo uno a uno.
- Los métodos getscope y setscope permiten determinar y establecer la contención del alcance respectivamente:
Figura 5.8
5.5 Programación de múltiples procesadores
- Cuando hay varios procesadores disponibles, la programación se vuelve más complicada, porque ahora hay más de una CPU que debe mantenerse ocupada y en uso efectivo en todo momento.
- El reparto de carga gira en torno al equilibrio de la carga entre múltiples procesadores.
- Los sistemas multiprocesador pueden ser heterogéneos (diferentes tipos de CPU) u homogéneos (todos del mismo tipo de CPU). Incluso en este último caso puede haber restricciones de programación especiales, como dispositivos que están conectados a través de un bus privado a solo una de las CPU. Este libro restringirá su discusión a sistemas homogéneos.
5.5.1 Enfoques para la programación de múltiples procesadores
- Un enfoque para la programación multiprocesador es el multiprocesamiento asimétrico, en el que un procesador es el maestro, controla todas las actividades y ejecuta todo el código del núcleo, mientras que el otro solo ejecuta el código del usuario. Este enfoque es relativamente simple, ya que no es necesario compartir datos críticos del sistema.
- Otro enfoque es el multiprocesamiento simétrico, SMP, donde cada procesador programa sus propios trabajos, ya sea desde una cola preparada común o desde colas preparadas separadas para cada procesador.
- Prácticamente todos los sistemas operativos modernos son compatibles con SMP, incluidos XP, Win 2000, Solaris, Linux y Mac OSX.
5.5.2 Afinidad del procesador
- Los procesadores contienen memoria caché, que acelera los accesos repetidos a las mismas ubicaciones de memoria.
- Si un proceso cambiara de un procesador a otro cada vez que tuviera un intervalo de tiempo, los datos en el caché (para ese proceso) tendrían que ser invalidados y recargados desde la memoria principal, evitando así el beneficio del caché.
- Por lo tanto, los sistemas SMP intentan mantener los procesos en el mismo procesador, a través de la afinidad del procesador. La afinidad suave ocurre cuando el sistema intenta mantener los procesos en el mismo procesador pero no ofrece garantías. Linux y algunos otros sistemas operativos admiten una afinidad dura, en la que un proceso especifica que no se debe mover entre procesadores.
- La arquitectura de la memoria principal también puede afectar la afinidad del proceso, si determinadas CPU tienen acceso más rápido a la memoria en el mismo chip o placa que a otra memoria cargada en otro lugar. (Acceso no uniforme a la memoria, NUMA). Como se muestra a continuación, si un proceso tiene una afinidad por una CPU en particular, se le debe asignar preferentemente almacenamiento de memoria en áreas de acceso rápido “locales”.
5.5.3 Equilibrio de carga
- Obviamente, un objetivo importante en un sistema multiprocesador es equilibrar la carga entre los procesadores, de modo que un procesador no esté inactivo mientras otro está sobrecargado.
- Los sistemas que usan una cola lista común son naturalmente autoequilibrantes y no necesitan ningún manejo especial. Sin embargo, la mayoría de los sistemas mantienen colas preparadas separadas para cada procesador.
- El equilibrio se puede lograr a través de la migración push o la migración pull: la migración push implica un proceso separado que se ejecuta periódicamente (por ejemplo, cada 200 milisegundos), y mueve los procesos de procesadores muy cargados a los menos cargados. La migración de extracción involucra procesadores inactivos que toman procesos de las colas listas de otros procesadores. La migración de extracción y extracción no son mutuamente excluyentes.
- Tenga en cuenta que mover los procesos de procesador a procesador para lograr el equilibrio de carga funciona en contra del principio de afinidad del procesador y, si no se gestiona con cuidado, los ahorros obtenidos al equilibrar el sistema pueden perderse en la reconstrucción de cachés. Una opción es permitir solo la migración cuando el desequilibrio supera un umbral determinado.
5.5.4 Procesadores multinúcleo
- SMP tradicional requería múltiples chips de CPU para ejecutar múltiples hilos de kernel al mismo tiempo.
- Las tendencias recientes son colocar múltiples CPU (núcleos) en un solo chip, que aparecen en el sistema como procesadores múltiples.
- Los ciclos de cálculo se pueden bloquear por el tiempo necesario para acceder a la memoria, siempre que los datos necesarios no estén presentes en la memoria caché. (La memoria caché falla.) En la Figura 5.10, hasta la mitad de los ciclos de la CPU se pierden en la pérdida de memoria.
- Al asignar múltiples hilos de kernel a un solo procesador, se puede evitar (o reducir) la pérdida de memoria ejecutando un hilo en el procesador mientras el otro hilo espera memoria.
- Un sistema de doble núcleo y doble subproceso tiene cuatro procesadores lógicos disponibles para el sistema operativo. La CPU UltraSPARC T1 tiene 8 núcleos por chip y 4 hilos de hardware por núcleo, para un total de 32 procesadores lógicos por chip.
- Hay dos formas de multiprocesar un procesador: los subprocesos múltiples de grano grueso cambian entre subprocesos solo cuando un subproceso se bloquea, por ejemplo, en una lectura de memoria. El cambio de contexto es similar al cambio de proceso, con una sobrecarga considerable. El subprocesamiento múltiple de grano fino ocurre en intervalos regulares más pequeños, por ejemplo, en el límite de los ciclos de instrucción. Sin embargo, la arquitectura está diseñada para admitir la conmutación de subprocesos, por lo que la sobrecarga es relativamente menor.
- Tenga en cuenta que para un sistema multi-hilo multi-núcleo, hay dos niveles de programación, a nivel del núcleo: el sistema operativo programa qué hilo (s) del núcleo asignar a qué procesadores lógicos, y cuándo hacer cambios de contexto usando algoritmos como se describe arriba. En un nivel inferior, el hardware programa procesadores lógicos en cada núcleo físico utilizando algún otro algoritmo. El UltraSPARC T1 utiliza un método simple de operación por turnos para programar los 4 procesadores lógicos (hilos del núcleo) en cada núcleo físico. Intel Itanium es un chip de doble núcleo que utiliza un esquema de prioridad de 7 niveles (urgencia) para determinar qué hilo programar cuando ocurre uno de los 5 eventos diferentes.
5.5.5 Virtualización y programación
- La virtualización agrega otra capa de complejidad y programación.
- Normalmente, hay un sistema operativo host que opera en procesadores “reales” y varios sistemas operativos invitados que operan en procesadores virtuales.
- El sistema operativo host crea una cantidad de procesadores virtuales y los presenta a los sistemas operativos invitados como si fueran procesadores reales.
- Los sistemas operativos invitados no se dan cuenta de que sus procesadores son virtuales, y toman decisiones de programación asumiendo procesadores reales.
- Como resultado, el rendimiento interactivo y especialmente en tiempo real puede verse gravemente comprometido en los sistemas invitados. El reloj de la hora del día también estará frecuentemente apagado.
5.6 Ejemplos de sistema operativo
5.6.1 Ejemplo: programación de Solaris
- Programación de hilos de kernel basada en prioridades.
- Cuatro clases (tiempo real, sistema, interactivo y tiempo compartido), y múltiples colas / algoritmos dentro de cada clase.
- El valor predeterminado es tiempo compartido. Las prioridades de proceso y los segmentos de tiempo se ajustan dinámicamente en un sistema de cola de prioridad de retroalimentación multinivel. Los segmentos de tiempo son inversamente proporcionales a la prioridad: los trabajos de mayor prioridad obtienen segmentos de tiempo más pequeños. Los trabajos interactivos tienen mayor prioridad que los vinculados a la CPU. Consulte la tabla a continuación para conocer algunos de los 60 niveles de prioridad y cómo cambian. “Tiempo cuántico expirado” y “regreso del sueño” indican la nueva prioridad cuando se producen esos eventos. (Los números más grandes son una prioridad más alta, es decir, mejor).
Figura 5.12
- Solaris 9 introdujo dos nuevas clases de programación: Prioridad fija y reparto equitativo. La prioridad fija es similar al tiempo compartido, pero no se ajusta dinámicamente. El reparto equitativo utiliza el tiempo de CPU en lugar de las prioridades para programar trabajos. Una parte del tiempo de CPU disponible se asigna a un proyecto, que es un conjunto de procesos.
- La clase del sistema está reservada para el uso del núcleo. (Los programas de usuario que se ejecutan en modo kernel NO se consideran en la clase de programación del sistema).
5.6.2 Ejemplo: Programación de Windows XP
- Windows XP utiliza un algoritmo de programación preventivo basado en prioridades.
- El despachador utiliza un esquema de prioridad de 32 niveles para determinar el orden de ejecución del subproceso, dividido en dos clases: clase variable de 1 a 15 y clase de tiempo real de 16 a 31 (más un subproceso con prioridad 0 que administra la memoria).
- También hay un subproceso inactivo especial que se programa cuando no hay otros subprocesos listos.
- Win XP identifica 7 clases de prioridad (filas en la tabla a continuación) y 6 prioridades relativas dentro de cada clase (columnas).
- A los procesos también se les asigna una prioridad básica dentro de su clase de prioridad. Cuando los procesos de clase variable consumen sus cuantos de tiempo completos, su prioridad se reduce, pero no por debajo de su prioridad base.
- Los procesos en primer plano (ventana activa) tienen sus cuantos de programación multiplicados por 3, para dar una mejor respuesta a los procesos interactivos en primer plano.
Figura 5.14
5.6.3 Ejemplo: programación de Linux
- La programación moderna de Linux proporciona un soporte mejorado para los sistemas SMP y un algoritmo de programación que se ejecuta en tiempo O (1) a medida que aumenta el número de procesos.
- El planificador de Linux es un algoritmo preventivo basado en prioridades con dos rangos de prioridad: tiempo real de 0 a 99 y un rango agradable de 100 a 140.
- A diferencia de Solaris o XP, Linux asigna cantidades de tiempo más largas a tareas de mayor prioridad.
Figura 5.15
- Una tarea ejecutable se considera elegible para la ejecución siempre que no haya consumido todo el tiempo disponible en su segmento de tiempo. Esas tareas se almacenan en una matriz activa , indexadas según la prioridad.
- Cuando un proceso consume su segmento de tiempo, se mueve a una matriz caducada. La prioridad de las tareas puede reasignarse como parte de la transferencia.
- Cuando la matriz activa se vacía, las dos matrices se intercambian.
- Estas matrices se almacenan en estructuras runqueue . En máquinas multiprocesador, cada procesador tiene su propio programador con su propia secuencia de ejecución.
Figura 5.16
5.7 Evaluación de algoritmos
- El primer paso para determinar qué algoritmo (y qué configuraciones de parámetros dentro de ese algoritmo) es óptimo para un entorno operativo particular es determinar qué criterios se utilizarán, qué objetivos se deben apuntar y qué restricciones, si es necesario, se deben aplicar. Por ejemplo, uno podría querer “maximizar la utilización de la CPU, sujeto a un tiempo de respuesta máximo de 1 segundo”.
- Una vez que se han establecido los criterios, se pueden analizar diferentes algoritmos y determinar la “mejor opción”. Las siguientes secciones describen algunos métodos diferentes para determinar la “mejor opción”.
5.7.1 Modelado determinista
- Si se conoce una carga de trabajo específica, los valores exactos para los criterios principales se pueden calcular con bastante facilidad y se puede determinar el “mejor”. Por ejemplo, considere la siguiente carga de trabajo (con todos los procesos llegando al tiempo 0), y las programaciones resultantes determinadas por tres algoritmos diferentes:
Proceso
Tiempo quemado
P1
10
P2
29
P3
3
P4
7 7
P5
12
- Los tiempos de espera promedio para FCFS, SJF y RR son 28 ms, 13 ms y 23 ms respectivamente.
- El modelado determinista es rápido y fácil, pero requiere una entrada específica conocida, y los resultados solo se aplican a ese conjunto particular de entrada. Sin embargo, al examinar múltiples casos similares, se pueden observar ciertas tendencias. (Como el hecho de que para los procesos que llegan al mismo tiempo, SJF siempre generará el tiempo de espera promedio más corto).
5.7.2 Modelos de colas
- Los datos de procesos específicos a menudo no están disponibles, particularmente para tiempos futuros. Sin embargo, un estudio del rendimiento histórico a menudo puede producir descripciones estadísticas de ciertos parámetros importantes, como la velocidad a la que llegan los nuevos procesos, la relación entre las ráfagas de CPU y los tiempos de E / S, la distribución de los tiempos de ráfaga de la CPU y los tiempos de ráfaga de E / S, etc.
- Armado con esas distribuciones de probabilidad y algunas fórmulas matemáticas, es posible calcular ciertas características de rendimiento de las colas de espera individuales. Por ejemplo, Little’s Formula dice que para una longitud de cola promedio de N, con un tiempo de espera promedio en la cola de W y una llegada promedio de nuevos trabajos en la cola de Lambda, estos tres términos pueden estar relacionados por:
N = Lambda * W
- Los modelos de colas tratan la computadora como una red de colas interconectadas, cada una de las cuales se describe por sus estadísticas de distribución de probabilidad y fórmulas como la fórmula de Little. Desafortunadamente, los sistemas reales y los algoritmos de programación modernos son tan complejos que hacen que las matemáticas sean intratables en muchos casos con sistemas reales.
5.7.3 Simulaciones
- Otro enfoque es ejecutar simulaciones por computadora de los diferentes algoritmos propuestos (y parámetros de ajuste) bajo diferentes condiciones de carga, y analizar los resultados para determinar la “mejor” opción de operación para un patrón de carga particular.
- Las condiciones de operación para las simulaciones a menudo se generan aleatoriamente utilizando funciones de distribución similares a las descritas anteriormente.
- Una alternativa mejor cuando sea posible es generar cintas de rastreo , monitoreando y registrando el rendimiento de un sistema real bajo las cargas de trabajo típicas esperadas. Estos son mejores porque proporcionan una imagen más precisa de las cargas del sistema y también porque permiten ejecutar múltiples simulaciones con la carga de proceso idéntica, y no solo cargas estadísticamente equivalentes. Un compromiso es determinar aleatoriamente las cargas del sistema y luego guardar los resultados en un archivo, de modo que todas las simulaciones puedan ejecutarse contra cargas del sistema idénticas determinadas aleatoriamente.
- Aunque las cintas de rastreo proporcionan información de entrada más precisa, pueden ser difíciles y costosas de recopilar y almacenar, y su uso aumenta significativamente la complejidad de las simulaciones. También hay dudas sobre si el rendimiento futuro del nuevo sistema realmente coincidirá con el rendimiento anterior del sistema anterior. (Si el sistema funciona más rápido, los usuarios pueden tomar menos pausas para el café y enviar más procesos por hora que en el sistema anterior. Por el contrario, si el tiempo de respuesta para los trabajos es más largo, los usuarios inteligentes pueden pensar más detenidamente sobre los trabajos que envían en lugar de al azar enviando trabajos y esperando que uno de ellos funcione).
Figura 5.17
5.7.4 Implementación
- La única forma real de determinar cómo funcionará un algoritmo de programación propuesto es implementarlo en un sistema real.
- Para algoritmos experimentales y aquellos en desarrollo, esto puede causar dificultades y resistencia entre los usuarios que no se preocupan por desarrollar sistemas operativos y solo están tratando de hacer su trabajo diario.
- Incluso en este caso, los resultados medidos pueden no ser definitivos, al menos por dos razones principales: (1) Las cargas de trabajo del sistema no son estáticas, sino que cambian con el tiempo a medida que se instalan nuevos programas, se agregan nuevos usuarios al sistema, nuevo hardware está disponible, comienzan nuevos proyectos de trabajo e incluso cambios sociales. (Por ejemplo, la explosión de Internet ha cambiado drásticamente la cantidad de tráfico de red que ve un sistema y la importancia de manejarlo con tiempos de respuesta rápidos). (2) Como se mencionó anteriormente, cambiar el sistema de programación puede tener un impacto en el trabajo carga y las formas en que los usuarios usan el sistema. (El libro da un ejemplo de un programador que modificó su código para escribir un carácter arbitrario en la pantalla a intervalos regulares, solo para que su trabajo se clasifique como interactivo y se coloque en una cola de mayor prioridad).
- La mayoría de los sistemas modernos proporcionan cierta capacidad para que el administrador del sistema ajuste los parámetros de programación, ya sea sobre la marcha o como resultado de un reinicio o una reconstrucción del núcleo.
5.8 Resumen
Material omitido de la octava edición:
Era 5.4.4 Subprocesamiento simétrico (omitido desde la 8ª edición)
- Una estrategia alternativa a SMP es SMT, Symmetric Multi-Threading, en la que se utilizan múltiples CPU virtuales (lógicas) en lugar de (o en combinación con) múltiples CPU físicas.
- SMT debe ser compatible con el hardware, ya que cada CPU lógica tiene sus propios registros y maneja sus propias interrupciones. (Intel se refiere a SMT como tecnología hyperthreading).
- Hasta cierto punto, el sistema operativo no necesita saber si los procesadores que administra son reales o virtuales. Por otro lado, algunas decisiones de programación pueden optimizarse si el planificador conoce la asignación de procesadores virtuales a CPU reales. (Considere la programación de dos procesos intensivos en CPU en la arquitectura que se muestra a continuación).
Si eres más nuevo en el mundo de las computadoras, mira este video hasta el final
