planificación de procesos: algoritmos de...

Introducción Métricas Algoritmos de planificación Esquemas híbridos y prioridades externas Resumiendo y temas relacionados

Planificación de procesos: Algoritmos deplanificación

Gunnar Wolf

Facultad de Ingeniería, UNAM

2013-02-27 — 2013-03-11


Índice

1 Introducción

2 Métricas

3 Algoritmos de planificación

4 Esquemas híbridos y prioridades externas

5 Resumiendo y temas relacionados


Referencia para esta sección

Buena parte del material de esta unidad toma por referencia alcapítulo 2 de An operating systems vade mecum (Raphael

Finkel, 1988)

(Disponible en el sitio Web del curso)

http://sistop.gwolf.org/html/biblio/An_operating_system_vade_mecum_-_Raphael_Finkel.pdf


Principal decisión en un sistema multitareas

¿Qué proceso es el siguiente a ejecutar?¿Qué procesos han ido terminando?

¿Qué eventos ocurrieron que hacen que cambien deestado?

Solicitudes (y respuestas) de E/SSwap de/a disco

¿Cual es el siguiente proceso al que le toca atención delCPU?

¿Y por cuánto tiempo?

Vemos que hay tres tipos muy distintos de planificación.


Planificador a largo plazo

Cual es el siguiente proceso a ser iniciadoPrincipalmente orientado a la operación en lotes

Principalmente a los sistemas con spoolTambién presente en la multiprogramacin temprana

Decide en base a los requisitos pre-declarados de losprocesos, y a los recursos disponibles al ejecutarsePeriodicidad: segundos a horasHoy en día no se emplean

El usuario indica expresamente qué procesos iniciar


Planificador a largo plazo

Figura: Planificador a largo plazo


Planificador a mediano plazo

Cuáles procesos hay que bloquearPor escacez/saturación de algún recurso (p.ej.almacenamiento primario)Por haber iniciado una operación que no puedesatisfacerse aún

Cuáles procesos hay que desbloquearA la espera de algún dispositivoFueron enviados a swap, pero ya requieren o merecenejecutarse

Frecuentemente llamado agendador (scheduler)


Planificador a mediano plazo

Figura: Planificador a mediano plazo, o agendador


Planificador a corto plazo

Cómo compartir momento a momento al CPU entretodos los procesosSe efectúa decenas de veces por segundo

Debe ser simple, eficiente y rápidoSe encarga de planificar los procesos listos para ejecución

Estados listo y ejecutando

Frecuentemente llamado despachador (dispatcher)


Planificador a corto plazo

Figura: Planificador a corto plazo, o despachador


El enfoque de esta sección

En esta sección hablaremos particularmente del planificador acorto plazo

Cuando un proceso es suspendido (o bloqueado) yposteriormente reactivado, lo trataremos como un proceso

nuevo.


Tipos de proceso

Diversos procesos tienen distintas característicasAlternan entre ráfagas (bursts)

Limitado por CPULimitado por E/S

Cuando termina una ráfaga limitada por CPU y sesuspende esperando E/S, deja de estar listo y sale de lavista del despachadorEsto nos lleva a separar los procesos en. . .


Tipos de proceso

Largos Han estado listos o en ejecución por muchotiempo

Esto es, están en una ráfaga limitada porCPU

Cortos En este momento están en una ráfaga limitadapor E/S

Requieren atención meramente ocasional delprocesadorTienden a estar bloqueados, esperando aeventos


Índice

1 Introducción

2 Métricas





Unidades a manejar

Para hablar de planificación del procesador, no vamos amanejar tiempos estándar (s, ms, ns), sino que:

Tick Un tiempo mínimo dado durante el cual se puederealizar trabajo útil. Medida caprichosa yarbitraria.En Windows, un tick dura entre 10 y 15 ms. EnLinux (2.6.8 en adelante), dura 1 ms.

Quantum Tiempo mínimo, expresado en ticks, que sepermitirá a un proceso el uso del procesador.En Windows, 2—12 ticks (esto es, 20—180ms).En Linux, 10—200 ticks (10-200ms)


¿Qué es mejor?

No hay un sólo criterio para definir qué es una mejorrespuestaEl patrón correcto varía según el propósito del sistemaUn proceso interactivo sufre si el tiempo de respuestaincrementa, aunque pueda procesar por más tiempocorrido

En caso de sufrir demoras, debemos intentar que seanconsistentes, aunque el tiempo promedio resultedeterioradoEs mejor saber que el sistema siempre tardará 0.5s enresponder a mis necesidades a que unas veces respondade inmediato y otras tarde 3s.


¿Qué métricas compararemos?

Para un proceso p que requiere ejecutarse por tiempo t,

Tiempo de respuesta (T ) Tiempo total que toma el trabajoIncluye el tiempo inactivo (pero listo).

Tiempo en espera (E ) De T , cuánto tiempo está esperandoejecutar. (Tiempo perdido)

E = T − tEl proceso p desea que E → 0

Proporción de penalización (P) Fracción del tiempo derespuesta durante la cual p estuvo en espera.

P = Tt

Proporción de respuesta (R) Fracción del tiempo de respuestadurante la cual p pudo ejecutarse.

R = tT ; R = 1

P


Además de los anteriores, para el sistema. . .

Tiempo núcleo o kernel Tiempo que pasa el sistema enespacio de núcleo

Tiempo desocupado (idle) Tiempo en que la cola de procesoslistos está vacía y no puede realizarse ningúntrabajo.

Utilización del CPU Porcentaje del tiempo en que el CPU estárealizando trabajo útil.

Conceptualmente, entre 0 y 100%En realidad, en un rango entre 40 y el 90%.


Por ejemplo. . .

Los siguientes procesos forman la cola de procesos listos:

Proceso Ticks LlegadaA 7 0B 3 2C 12 6D 4 20

Toma 2 ticks realizar un cambio de contexto; cada quantum esde 5 ticks, y tenemos un ordenamiento de ronda1

1Que pronto describiremos


Precisiones sobre el ejemplo

Nuestro ejemplo no es realista

¡El cambio de contexto propuesto esdesproporcionadamente largo! (sólo para ejemplificar)Consideraremos al tiempo núcleo como si fuera unproceso más

Midiendo como si iniciara y terminara junto con losdemásNormalmente el tiempo núcleo no se cuenta, es tomadopor burocracia


Graficando nuestro ejemplo

Figura: Ejecución de cuatro procesos con quantums de 5 ticks ycambios de contexto de 2 ticks


Resultado de nuestro ejemplo

Proceso t T E P RA 7 21 14 3.0 0.33B 3 8 5 2.66 0.37C 12 32 14 2.66 0.37D 4 14 10 3.5 0.28Promedio útil 6.5 18.75 10.75 2.958 0.3383Núcleo 14 40 26 4.0 0.25Promedio total 8 23 13.8 2.875 0.347

Tiempo kernel 14 ticksTiempo desocupado 0 ticksUtilización del CPU 26 ticks


Frecuencias

Respecto al patrón de llegadas y salidas de procesos a la colade procesos listos:

α Frecuencia de llegada promedioβ Tiempo de servicio requerido promedioρ Valor de saturación, ρ = α

β

Esto significa:

ρ = 0 Nunca llegan procesos nuevos; el sistema estarádesocupado

ρ = 1 Los procesos van saliendo al mismo ritmo al quevan entrando

ρ > 1 Los procesos llegan más rápido de lo que puedeser atendidos. La cola de procesos listos tiende acrecer. R se decrementa para todos.


Índice

1 Introducción

2 Métricas





¿Cuándo se ejecuta el despachador?

Cuando un proceso:

1 Pasa de ejecutando a en esperap.ej. por solicitar E/S, sincronización con otro proceso,ceder el paso (yield)

2 Pasa de ejecutando a listop.ej. al ocurrir una interrupción

3 Deja de estar en espera para estar listop.ej. cuando finaliza la operación E/S que solicitó

4 Pasa de ejecutando a terminadoCuando finaliza su ejecución

Para la multitarea cooperativa, pueden ser sólo 1 y 4.


Nuestros procesos base

Para presentar los diferentes algoritmos, usarmos la siguientetabla de procesos:

Tiempo de TiempoProceso llegada requerido

(t)A 0 3B 1 5C 3 2D 9 5E 12 5Promedio 4


Primero llegado, primero servido (FCFS)

First Come, First Serve.También referido como FIFO (First In, First Out)

El esquema más simple de planificaciónApto para multitarea cooperativaCada proceso se ejecuta en órden de llegadaHasta que suelta el control



Figura: Primero llegado, primero servido (FCFS)



Proceso Inicio Fin T E PA 0 3 3 0 1B 3 8 7 2 1.4C 8 10 7 5 3.5D 10 15 6 1 1.2E 15 20 8 3 1.6Promedio 6.2 2.2 1.74



La sobrecarga administrativa es mínimaEl algoritmo es extremadamente simple: una cola FIFOEfectúa el mínimo posible de cambios de contextoNo requiere hardware de apoyo (temporizador /interrupciones)→ Principio de histéresis (Finkel): “Hay que resistirse alcambio”

El rendimiento percibido por los últimos procesosdisminuye

Los procesos cortos pueden esperardesproporcionadamente mucho tiempoLa demora aumenta fuertemente conforme crece ρ

Tendencia a la inanición cuando ρ ≥ 1


Ronda (Round Robin)

Busca dar buena respuesta tanto a procesos cortos comolargosRequiere multitarea preventivaEjecutamos cada proceso por un quantum

Si no terminó su ejecución, se interrumpe y coloca devuelta al final de la colaLos procesos nuevos se forman también al final de estamisma cola


Ronda (Round Robin)

Figura: Ronda (Round Robin)


Ronda (Round Robin)

Proceso Inicio Fin T E PA 0 6 6 3 2.0B 1 11 10 5 2.0C 4 8 5 3 2.5D 9 18 9 4 1.8E 12 20 8 3 1.6Promedio 7.6 3.6 1.98


Ronda (Round Robin)

Alta frecuencia de cambios de contextoA pesar de que el algoritmo es simple, la sobrecargaadministrativa (burocracia) es alta

Puede modificarse incrementando el quantumReduce la frecuencia de cambios de contextoPara valores grandes de q, tiende a convertirse en FCFS


Ronda (Round Robin) con q = 4

Figura: Ronda (Round Robin), con q = 4


Ronda (Round Robin) con q = 4



El proceso más corto a continuación (SPN)

Shortest Process NextMultitarea cooperativaPero requerimos un algoritmo más justo que FCFSSabemos cuánto tiempo va a requerir cada proceso

No por magia: Podemos estimar / predecir basados en suhistoriaSPN puede mantener la contabilidad de los procesosincluso tras entregarlos de vuelta al agendador


Estimando para SPN: Promedio exponencial

Es común emplear un promedio exponencial para estimar lasiguiente demanda de tiempo de p: Si en su última invocación

empleó q quantums,e ′p = fep + (1− f )q

Donde 0 ≤ f ≤ 1 es el factor atenuante, determinando quétan reactivo será el promedio a cada cambio.

Es común que f ≈ 0,9


Estimando para SPN: Promedio exponencial

Figura: Promedio exponencial (predicción de próxima solicitud detiempo) de un proceso. (Silberschatz, p.183)



Figura: El proceso más corto a continuación (SPN)



Obviamente, SPN favorece a los procesos cortosUn proceso largo puede esperar mucho tiempo antes deser atendidoCon ρ alto, los procesos largos sufren inanición

Con una cola de procesos listos chica, el resultado essimilar a FCFS

Pero vimos que una sóla permutación entre el órden deB y C redujo fuertemtente los factores de penalización


Variaciones sobre SPN: SPN preventivo (PSPN)

Emplea la estrategia de SPN, pero interrumpe cadaquantumFinkel observa que la penalización a procesos largos no esmucho peor que la de la rondaMantiene mejores promedios, porque los procesos cortossalen más temprano de la cola.


Variaciones sobre SPN: El más penalizado acontinuación (HPRN)

Highest Penalty Ratio NextMultitarea cooperativa

Las alternativas (FCFS y SPN) parecen injustas paramuchos proesosBusca otorgar un mejor balance

Todos los procesos incian con un valor de penalizaciónP = 1Cada vez que un proceso es obligado a esperar un tiempow por otro, P = w+t

t (acumulando w)Se elige el proceso cuyo valor de P sea mayor


El más penalizado a continuación (HPRN)

Mientras ρ < 1, HPRN evita inanición incluso en procesoslargosFinkel apunta que, ante la experimentación, HPRN seubica siempre entre FCFS y SPNPrincipal desventaja: Es un algoritmo caro

Cuando hay muchos procesos en la cola, P tiene quecalcularse para todos ellos a cada invocación deldespachador


Retroalimentación multinivel (FB)

Multilevel FeedbackMultitarea preventivaSe crea no una, sino varias colas de procesos listos

Cada cola con un distinto nivel de prioridad, CP

El despachador toma el proceso al frente de la cola demás prioridadTras n ejecuciones, el proceso es degradado a CP+1

Favorece a los procesos cortosTerminan su trabajo sin ser marcados como de prioridadinferior

El algoritmo es baratoSólo hay que actualizar a un proceso a cada ejecución, yevaluar un número limitado de colas



Figura: Retroalimentación multinivel (FB) básica. En la líneasuperior al proceso se muestra la cola antes del quantum en que seejecuta.



Fenómenos observados:

Al tick 8, 10, 11, 13, 14, el despachador interrumpe al procesoactivo y lo vuelve a programar

En una implementación ingenua, esto causa un cambio decontexto

Burocracia innecesaria

¿Puede prevenirse esta interrupción?



Proceso Inicio Fin T E PA 0 7 7 3 2.3B 1 18 17 12 3.4C 3 6 3 1 1.5D 9 19 10 5 2.0E 12 20 8 3 1.6Promedio 9 5 2.16



¡Pero todos los números apuntan a que es una peorestrategia que las anteriores!Los únicos beneficiados son los recién llegados

Entran a la cola de mayor prioridadUn proceso largo, a mayor ρ, enfrenta inanición

El rendimiento del algoritmo puede ajustarse con dosvariables básicas:

n Cuántas ejecuciones para ser degradado aCP+1

Q Duración del quantum de las siguientes colasVeamos cómo se comporta cuando:

Mantenemos n = 1Q = 2nq (donde q es la duración del quantum base)



Figura: Retroalimentación multinivel (FB) con Q exponencial



Fenómenos observados:

Aunque FB favorece a los procesos recién llegados, al tick3, 9 y 10 los procesos que llegan son puestos en espera

Llegaron a la mitad del quantum largo de otro proceso



Proceso Inicio Fin T E PA 0 4 4 1 1.3B 1 10 9 4 1.8C 4 8 5 3 2.5D 10 18 9 4 1.8E 13 20 8 3 1.6Promedio 7 3 1.8



Con Q exponencial, los promedios resultan inclusomejores que ronda

Típicamente los incrementos son más suaves — Q = nqo incluso q = q log(n)Un proceso largo con Q exponencial puede causarinanición por largo tiempo

Para evitar la inanición ante un ρ alto, puede considerarsela retroalimentación en sentido inverso

Si un proceso largo es degradado a CP y pasa demasiadotiempo sin ejecutarse, promoverlo de vuelta a CP−1



El mecanismo es muy flexible, y permite muchas mejoríassimplesHoy en día es empleado por muchos de los principalessistemas operativos

FreeBSD, Linux (pre-2.6), MacOS X, NetBSD, Solaris,Windows (2000 en adelante) (ref: Wikipedia “Schedulingalgorithm”)Con diferentes parámetros y prioridades


Ronda egoísta (SRR)

Selfish Round RobinMultitarea preventivaFavorece a los proesos que ya llevan tiempo ejecutandosobre los recién llegados

Un proeso nuevo se forma en la cola de procesos nuevos,el despachador avanza sólo sobre los procesos aceptados

Parámetros ajustables:a Ritmo de incremento de prioridad deprocesos aceptados

b Ritmo de incremento de prioridad deprocesos nuevos

Cuando la prioridad de un proceso nuevo alcanza a la deuno aceptado, éste se acepta.



Figura: Ronda egoísta (SRR) con a = 2 y b = 1



Mientras ba < 1:

Los procesos nuevos serán aceptados eventualmenteSi el control va alternando entre dos procesos, suprioridad se mantendrá igual, y serán despachados porronda simple

Si ba ≥ 1, el proceso en ejecución terminará antes de que

se acepte el nuevoTiende a FCFS

Si ba = 0 (esto es, si b = 0)Los procesos recién llegados son aceptadosinmediatamenteTiende a ronda

Si 0 < ba < 1, la ronda es relativamente egoísta

Se da entrada a procesos nuevosIncluso si hay procesos muy largos ejecutando


Clasificando a los distintos esquemas

Los siete algoritmos presentados pueden caracterizarse sobredos descriptores primarios

Tipo de multitarea si el esquema está planteado para operarbajo multitarea preventiva o cooperativa

Emplea información intrínseca Si, para tomar cada decsión deplanificación, emplean información propia(intrínseca) a los procesos evaluados, o no —Esto es, si el historial de ejecución de un procesotiene impacto en cómo será planificado a futuro.


Clasificando a los distintos esquemas

Cuadro: Caracterización de los mecanismos de planificación a cortoplazo

No considera Consideraintrínseca intrínseca

Cooperativa Primero llegado Proceso másprimero servido corto (SPN),(FCFS) Proceso más

penalizado (HPRN)Preventiva Ronda (RR), Proceso más

Retroalimentación (FB), corto preventivoRonda egoísta (SRR) (PSPN)


Índice

1 Introducción

2 Métricas





Esquemas híbridos

Los esquemas de planificación empleados normalmenteusan mezclas de los algoritmos presentadosPermite emplear el algoritmo que más ventajas presenteante una situación dada

Y evitar algunas de sus deficiencias


Esquemas híbridos: Algoritmo por cola en FB

Manejamos varias colas en un esquema FBCada cola usa internamente un algoritmo distinto paraelegir el proceso que está a la cabeza. Algunas ideas comoejemplo:

Una cola bajo PSPN: Empuja a los procesos más largoshacia colas que sean interrumpidas con menor frecuenciaEmplear SRR para las colas de menor prioridad

Sus procesos ya esperaron mucho para tener respuesta;cuando obtienen el procesador, avanzan lo máságilmente posiblePero no obstaculizan a los procesos cortos que vanllegando


Esquemas híbridos: Dependientes del estado delsistema

Podemos considerar también información extrínseca paradespachar

Información externa al estado y ejecución de cada uno delos procesosInformación dependiente del estado del sistema, del tipode usuario, etc.

A continuación, algunos ejemplos


FCFS/SPN o RR, dependiendo de ρ

Si los procesos son en promedio cortos y ρ < 1Métodos con la mínima sobrecarga administrativa (FCFSo SPN)O un RR con quantum muy largo (evitando losproblemas de la multitarea cooperativa)

Si los procesos tienden a ser más largos o si sube ρCambiamos a RR con un quantum más bajo o a PSPN


Ronda con quantum dependiente de procesospendientes

Esquema simple de rondaLa duración de un quantum es ajustada periódicamenteCada quantum depende de la cantidad de procesos en eltotal de procesos listos, siguiendo Q = q

n

Pocos procesos esperandoMayor Q → Menos cambios de contexto

Muchos procesos esperandoMenor QNunca más allá de un minimo, para evitar sobrecargaburocrática


Ronda + Prioridad externa

Usamos un esquema simple de ronda, con una sola colaLa duración del quantum dependerá de la prioridadexterna

Fijada por el usuario o por el sistema por factores ajenosal despachador

Un proceso de mayor prioridad ejecutará por mayortiempo


Peor servicio a continuacion (WSN)

Generalización sobre HPRNNo sólo se considera penalización el tiempo esperado enla cola de procesos listos

Veces que ha sido interrumpido por el temporizadorPrioridad externaEspera por E/S u otros recursos

El proceso que ha sufrido peor servicio es seleccionadopara su ejecuciónDesventaja: Considerar demasiados factores (con distintospesos) impacta en el tiempo de ejecución del algoritmo

Puede llamarse a WSN periódicamente para formar colasProceder con esquemas más simples. . . Aunque esto reduce la velocidad de reacción


Lindura (niceness)

Empleado por varios Unixes históricosEl usuario inicia (nice) o modifica (renice) laprioridad de su proceso

Típicamente sólo hacia arriba — Se porta más lindo.

Esta prioridad externa y el tiempo consumidorecientemente por el proceso constituyen una prioridadinternaLa prioridad interna aumenta cuando el proceso espera

Por el despachador, por E/S, o cualquier otra causaLa prioridad interna es matizada por el tamaño de la colade procesos listos

Entre más procesos pendientes, mayor el peso quemodifique a la prioridad


Índice

1 Introducción

2 Métricas





Sobrecarga administrativa

Figura: Sobrecarga administrativa de los planificadores de cortoplazo (Finkel, p.33)


Tiempo perdido por sobrecarga adm.

Figura: Tiempo perdido por sobrecarga administrativa porplanificador de corto plazo (Finkel, p.34)


Duración mínima del quantum

Vimos que la penalización en la ronda puede evitarse conquantums mayores

Pero puede degenerar en multiprocesamiento cooperativo

¿Qué tan corto debe ser un quantum?


Duración mínima del quantum

Duración de cambio de contexto hoy en día: ≈ 0,01ms(Silberschatz p.187)

Con un quantum corto, 10ms, es 11000 la duración del

tiempo efectivo de procesamientoCon un quantum largo, 200ms, 1

20000

No es realmente significativo — ¡Ni debe serlo!Perder 1% del tiempo de cómputo en burocracia sería engeneral visto como excesivoOjo: ¡El tiempo núcleo no sólo es el tiempo del cambiode proceso!


Compartir el procesador

Estrategia empleada por Control Data (CDC6600, 1964,diseñada por Seymour Cray): Multitarea gestionada enhardwareUn sólo procesador, pero con 10 juegos de registros

Procesador superescalarA cada paso de reloj, avanzaba el juego de registros

Quantum efectivo igual a la velocidad del relojApariencia de 10 procesadores más lentos, cada uno de110 la velocidad del realMultitarea sin cambios de contexto


Compartir el procesador

¿Desventajas?Nivel de concurrencia fijoDifícil de adecuar a picos de ocupaciónCosto muy elevado

Esquema comparable con el HyperThreading deprocesadores actuales

Aunque HyperThreading busca aprovechar las diferentesfases del pipeline, que no existía en 1964


Relación entre hilos y procesos

¿Cómo entiende el despachador a los hilos?Tres modelos principales de mapeo:

Muchos a unoUno a unoMuchos a muchos


Muchos a uno

Figura: Mapeo de hilos muchos a uno (imagen: Beth Plale)

Hilos verdes (o de usuario)El SO ve un sólo proceso

El tiempo se reparte dentro del proceso por mecanismosinternos

Código más portableNo se aprovecha realmente el paralelismoLlamadas bloqueantes → Todos esperan

http://www.cs.indiana.edu/classes/b534-plal/ClassNotes/sched-synch-details4.pdf


Uno a uno

Figura: Mapeo de hilos uno a uno (imagen: Beth Plale)

Cada hilo es un proceso ligero (lightweight process, LWP)Un LWP es mucho más ligero de levantar que un procesoComparte memoria, descriptores, estructuras

Aprovecha tanto el paralelismo como lo permita elhardware

Cada hilo puede correr en un procesador distinto, si loshay

El SO debe poder manejar LWP



Muchos a muchos

Figura: Mapeo de hilos muchos a muchos (imagen: Beth Plale)

Existen hilos unidos (bound threads), que correspondencada uno a un LWPTambién hilos no unidos (unbound threads), donde uno omás corresponden a cada LWPBrindan la flexibilidad de ambos modelos

Si el SO no maneja LWP, pueden caer en el modelo unoa muchos como modo degradado



El ámbito de contención

¿Recibe cada uno de los hilos la misma atención que recibiríaun proceso? Hay dos enfoques (categorización de hilos POSIX,

pthread):

Ámbito de contención de sistema (System ContentionScope, SCS)Ámbito de contencion de proceso (Process ContentionScope, PCS)

El ámbito de contención se refiere a cuál será la estructuradentro de la cual coexisten los hilos, y dentro de la cual cada

hilo contenderá por el procesador.


Ámbitos de contención

PTHREAD_SCOPE_SYSTEM

Todos los hilos sonatendidos en el tiempoque sería asignado a unsólo procesoModelo muchos a uno, asícomo los hilos no unidosmultiplexados en muchosa muchos

PTHREAD_SCOPE_PROCESS

Cada hilo es visto por elplanificador como unproceso independienteModelo uno a uno y loshilos unidos en muchos amuchos

. . . Pero una implementación pthreads puede ofrecer sólouno de los modelos → Tanto Linux como Windows manejan

sólo PTHREAD_SCOPE_SYSTEM (SCS).


Otras características en pthreads

pthreads incluyen varios de los otros aspectosmencionados en esta unidadEl programador puede solicitar al núcleo la prioridad decada uno de los hilos por separado(pthread_setschedprio)Incluso solicitar el empleo de un algoritmo de planificaciónen específico (sched_setscheduler)Recordemos que pthreads permite, en muchos casos,responder al proceso «Disculpa, no puedo hacer eso»


Multiprocesamiento

¿Qué factores relativos a la planificación tenemos queconsiderar cuando hablamos de un entorno multiprocesado?


Multiprocesamiento: Afinidad

Cuando un proceso se ejecutó por cierto tiempo, dejóporciones de su espacio de memoria en el caché delprocesador

Tanto segmentos de instrucciones como de datosCada procesador tiene usualmente un cachéindependiente

Puede haber un caché común a todo el sistema (L3);puede haber uno por chip multicore (L2), y puede haberuno específico para cada núcleo (L1)

Despachar a un proceso en un procesador distinto del queya lo ejecutó es un gasto inútil

Invalidar el caché que empleóRe-poblar el nuevo


Multiprocesamiento: Afinidad

Afinidad suave Un proceso que preferentemente seráejecutado en un determinado procesadorCiertos patrones de carga pueden llevar a que eldespachador decida migrarlo a otro procesador

Afinidad dura Se garantiza que un proceso será ejecutadosiempre en un procesador (o conjunto deprocesadores)

Ejemplo: En un entorno NUMA, buscamos que los procesostengan afinidad dura (y que el algoritmo de asignación dememoria considere dicha relación)


Multiprocesamiento: Balanceo de cargas

La situación ideal es que todos los procesadoresdespachen trabajos al 100% de su capacidad

Pero es un requisito demasiado rígido / irreal(casi) siempre habrá un procesador con tiempo libre(casi) siempre habrá procesadores con procesos encoladosy en espera. . . O ambas situaciones

Para mantener la divergencia lo menor posible, se empleael balanceo de cargas


Multiprocesamiento: Balanceo de cargas

El balanceo de cargas actúa en sentido contrario de laafinidad al procesador

Algoritmos que analizan el estado de las colas ytransfieran procesos entre ellas para homogeneizarlas

Puede reubicar procesos con afinidad suaveDebe preferir reubicar procesos sin afinidad declaradaNo debe reubicar procesos con afinidad dura


Estrategias de balanceo de cargas: Por empuje

Balanceo de cargas por empuje (push migration)

El núcleo revisa periódicamente el estado de losprocesadoresSi el desbalance sobrepasa cierto umbral, empuja aalgunos procesos de una cola a otra.Linux ejecuta esto cada 200ms.


Estrategias de balanceo de cargas: Por jalón

Balanceo de cargas: Por jalón (pull migration)

Cuando un procesador queda sin tareas pendientes,ejecuta el proceso especial desocupado (idle)Desocupado no significa no hacer nada: Puede ejecutartareas del núcleoPuede averiguar si hay procesos en espera con otroprocesador, y jalarlos al actual.

Los mecanismos no son mutuamente exclusivos, es común queun SO emplee ambos.

Todo balanceo de cargas conllevará una penalización entérminos de afinidad al CPU.


Multiprocesamiento: ¿Una cola o varias?

En un entorno multiprocesador, ¿cómo encaramos losalgoritmos antes descritos?

Una cola globalParecería una decisión más simpleSe ejecuta un sólo despachador → Ahorro de tiempoNo habría que preocuparse por balanceo de cargas —Sería natural

Una cola por procesadorNecesaria si queremos soportar manejo de afinidad alCPUTodos los sistemas en uso amplo implementan una colapor procesador


Hilos hardware (hyperthreading)

Hilos es una palabra que sufre abuso en nuestro campo.Hilos hardware (hyperthreading): No tienen relación conlos hilos que abordamos

Pero sí con el multiprocesamientoLa Ley de Moore no sólo ha llevado a un paralelismoexpreso (multinúcleo)

El pipeline de los procesadores hace que cada unidadfuncional del CPU pueda estar atendiendo a unainstrucción distinta


Hilos hardware (hyperthreading): Pipelines

Un procesador simple/clásico (ejemplo: MIPS) puededividir la ejecución de una instrucción en 5 etapas:

IF Recuperación de la instrucción (InstructionFetch)

ID Decodificación de la instrucción (InstructionDecode)

EX Ejecución (Execution)MEM Acceso a datosWB Almacenamiento (Writeback)

Un procesador moderno presenta mucho más etapas(Pentium 4: 20 etapas)



Figura: Descomposición de una instrucción en sus cinco pasosclásicos para organizarse en un pipeline



Es común que se presenten patrones de uso que requierenservicio de diferentes componentes del procesador

A veces con diferentes duracionesLleva a la inserción de demasiadas burbujas → Pérdidade tiempo

Para remediarlo, un sólo procesador (un solo núcleo) sepresenta como compuesto de dos o más hilos hardware

Conocidos en el mercado como hyper-threadsPuede aumentar el paralelismo — ¡aunque es muyimprobable que sea en 2x!



Figura: Alternando ciclos de cómputo y espera por memoria, unprocesador que implementa hilos hardware (hyperthreaded) sepresenta como dos procesadores



Puede profundizarse mucho más en la planificación dehilos hardware

Corresponde más bien al estudio de construcción decompiladoresY de arquitecturas de sistemasConsideraciones de seguridad entre hilos

Presenta gran similitud (aunque no es lo mismo) con lacompartición de procesadorNo ahondaremos en el tema en este curso

Se presenta para aclarar el concepto


Tiempo real

Nos hemos enfocado a repartir el tiempo disponible entrevarios procesosNo hemos tocado a los procesos que requieren garantíasde tiempo

Para poder realizar su trabajo, tienen que recibirdeterminado tiempo de procesador antes de un tiempolímite

Estos procesos son conocidos como de tiempo real


¿Cuándo nos enfrentamos con el tiempo real?

Controladores de dispositivosEntregan un determinado bloque de información cadatanto tiempoSi ese bloque no es procesado completo, se sobreescribepor el siguiente

Reproductores o recodificadores de audio y videoSi un cuadro se pierde, el resultado puede escucharseSea como una demora (reproducción) o como un corte(recodificación)

Procesadores de criptografíaSi un bloque se pierde, el documento completo de esepunto en adelante puede quedar corrupto


Reserva de recursos

Para poder manejarse como de tiempo real, un procesodebe declarar de inicio cuánto tiempo requerirá

Puede ser una sola vez: Necesito 600ms en los próximos2sPuede ser periódico: Cada segundo necesito 30ms

El sistema operativo le asignará el tiempo solicitado, o lenotificará que no puede garantizárselo

Mensaje de error → El proceso puede intentar continuarde todos modos sin prioridad especial


Tiempo real duro y suave

Tiempo real duro El sistema puede dar garantía de que elproceso tendrá el tiempo que reservó

Tiempo real suave El sistema intentará dar la prioridadrequerida al proceso, pero puede haber pequeñasdemoras


Restricciones del tiempo real duro

El planificador debe saber con certeza cuánto tiempotoman todas las tareas de sistema que ejecutará en elperiodoAlgunos dispositivos introducen demoras con demasiadavarianza

Almacenamiento en discoMemoria virtual

Imposibilitan que un sistema que los maneje implementetiempo real duro


Tiempo real suave: Prioridad del planificador

Los procesos de tiempo real simplemente reciben unaprioridad mucho más alta ante el planificadorLos procesos de tiempo real pueden llevar a la inaniciónde otros procesos

Es esperable y aceptable — ¡No debemos correr tantosprocesos de tiempo real! (rompería expectativas)


Retroalimentación multinivel y tiempo real suave

Puede implementarse con una modificación al esquema deretroalimentación multinivel

La cola de tiempo real recibe prioridad sobre todas lasdemás colasLa prioridad de un proceso de tiempo real no se degradaconforme se ejecuta repetidamente

Aunque puede indicar que ya terminó con su trabajosensible a tiempo

La prioridad de los demás procesos nunca llegan a subir alnivel de tiempo real por un proceso automático

Aunque sí puede hacerse por una llamada explícitaLa latencia de despacho debe ser mínima

Casi todos los sistemas operativos hoy en día presentanfacilidades básicas de tiempo real suave.


Sistema operativo interrumpible (prevenible)

Hay llamadas al sistema que toman demasiado tiempoPara poder ofrecer tiempo real suave con buenasexpectativas, hay que poder interrumpir al propio núcleoPrimer enfoque: Puntos de interrupción

Marcar explícitamente puntos en que todas lasestructuras están en un estado estable

No muy eficiente: Hay pocos puntos aptos para declararpuntos de interrupción

Muy rígido, dificil estructurar para poner puntosadicionales


Núcleo completamente interrumpible

Otro enfoque: Proteger a todas las modificaciones aestructuras internas del núcleo con mecanismos desincronizaciónEnfoque mucho más flexibleHace que el sistema operativo completo sea más lento(aunque más seguro)

Más operaciones a hacer por cada solicitud

Permiten que funciones del SO puedan correr como hilosconcurrentes en los distintos procesadores


Inversión de prioridades

Un proceso A de baja prioridad hace una llamada alsistema

Es interrumpido a la mitad de la llamadaUn proceso B de prioridad tiempo real hace una segundallamada al sistema

Requiriendo de la misma estructura que la que tienebloqueada A

B quedará esperando hasta que A vuelva a ser agendado

Esto es, B fue, para propósitos prácticos, degradado a laprioridad de A


Inversión de prioridades: Herencia de prioridades

Mecanismo introducido por Solaris 2Si A bloquea a B y PA < PB

PA := PB hasta que B libere el recursoPasado el bloqueo, PA vuelve a su estado nativo

planificación de procesos: algoritmos de...

Documents