Algoritmos Planificador

Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relacionados

Planificacin de procesos: Algoritmos deplanificacin

Gunnar Wolf

Facultad de Ingeniera, UNAM

2013-02-27 2013-03-11


ndice

1 Introduccin

2 Mtricas

3 Algoritmos de planificacin

4 Esquemas hbridos y prioridades externas

5 Resumiendo y temas relacionados


Referencia para esta seccin

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

Finkel, 1988)

(Disponible en el sitio Web del curso)


Principal decisin 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 atencin delCPU?

Y por cunto tiempo?

Vemos que hay tres tipos muy distintos de planificacin.


Planificador a largo plazo

Cual es el siguiente proceso a ser iniciadoPrincipalmente orientado a la operacin en lotes

Principalmente a los sistemas con spoolTambin 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 da no se emplean

El usuario indica expresamente qu procesos iniciar


Planificador a largo plazo

Figura: Planificador a largo plazo


Planificador a mediano plazo

Cules procesos hay que bloquearPor escacez/saturacin de algn recurso (p.ej.almacenamiento primario)Por haber iniciado una operacin que no puedesatisfacerse an

Cules procesos hay que desbloquearA la espera de algn 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

Cmo compartir momento a momento al CPU entretodos los procesosSe efecta decenas de veces por segundo

Debe ser simple, eficiente y rpidoSe encarga de planificar los procesos listos para ejecucin

Estados listo y ejecutando

Frecuentemente llamado despachador (dispatcher)


Planificador a corto plazo

Figura: Planificador a corto plazo, o despachador


El enfoque de esta seccin

En esta seccin 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 caractersticasAlternan entre rfagas (bursts)

Limitado por CPULimitado por E/S

Cuando termina una rfaga 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 ejecucin por muchotiempo

Esto es, estn en una rfaga limitada porCPU

Cortos En este momento estn en una rfaga limitadapor E/S

Requieren atencin meramente ocasional delprocesadorTienden a estar bloqueados, esperando aeventos


ndice

1 Introduccin

2 Mtricas





Unidades a manejar

Para hablar de planificacin del procesador, no vamos amanejar tiempos estndar (s, ms, ns), sino que:

Tick Un tiempo mnimo 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 mnimo, expresado en ticks, que sepermitir a un proceso el uso del procesador.En Windows, 212 ticks (esto es, 20180ms).En Linux, 10200 ticks (10-200ms)


Qu es mejor?

No hay un slo criterio para definir qu es una mejorrespuestaEl patrn correcto vara segn el propsito del sistemaUn proceso interactivo sufre si el tiempo de respuestaincrementa, aunque pueda procesar por ms 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 mtricas 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 , cunto tiempo est esperandoejecutar. (Tiempo perdido)

E = T tEl proceso p desea que E 0

Proporcin de penalizacin (P) Fraccin del tiempo derespuesta durante la cual p estuvo en espera.

P = TtProporcin de respuesta (R) Fraccin del tiempo de respuesta

durante la cual p pudo ejecutarse.R = tT ; R =

1P


Adems de los anteriores, para el sistema. . .

Tiempo ncleo o kernel Tiempo que pasa el sistema enespacio de ncleo

Tiempo desocupado (idle) Tiempo en que la cola de procesoslistos est vaca y no puede realizarse ningntrabajo.

Utilizacin del CPU Porcentaje del tiempo en que el CPU estrealizando 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! (slo para ejemplificar)Consideraremos al tiempo ncleo como si fuera unproceso ms

Midiendo como si iniciara y terminara junto con losdemsNormalmente el tiempo ncleo no se cuenta, es tomadopor burocracia


Graficando nuestro ejemplo

Figura: Ejecucin 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.3383Ncleo 14 40 26 4.0 0.25Promedio total 8 23 13.8 2.875 0.347

Tiempo kernel 14 ticksTiempo desocupado 0 ticksUtilizacin del CPU 26 ticks


Frecuencias

Respecto al patrn de llegadas y salidas de procesos a la colade procesos listos:

Frecuencia de llegada promedio Tiempo de servicio requerido promedio Valor de saturacin, =

Esto significa:

= 0 Nunca llegan procesos nuevos; el sistema estardesocupado

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

> 1 Los procesos llegan ms rpido de lo que puedeser atendidos. La cola de procesos listos tiende acrecer. R se decrementa para todos.


ndice

1 Introduccin

2 Mtricas





Cundo se ejecuta el despachador?

Cuando un proceso:

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

2 Pasa de ejecutando a listop.ej. al ocurrir una interrupcin

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

4 Pasa de ejecutando a terminadoCuando finaliza su ejecucin

Para la multitarea cooperativa, pueden ser slo 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.Tambin referido como FIFO (First In, First Out)

El esquema ms simple de planificacinApto 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 mnimaEl algoritmo es extremadamente simple: una cola FIFOEfecta el mnimo posible de cambios de contextoNo requiere hardware de apoyo (temporizador /interrupciones) Principio de histresis (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 inanicin 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 ejecucin, se interrumpe y coloca devuelta al final de la colaLos procesos nuevos se forman tambin 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 ms corto a continuacin (SPN)

Shortest Process NextMultitarea cooperativaPero requerimos un algoritmo ms justo que FCFSSabemos cunto 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 comn emplear un promedio exponencial para estimar lasiguiente demanda de tiempo de p: Si en su ltima invocacin

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

Donde 0 f 1 es el factor atenuante, determinando qutan reactivo ser el promedio a cada cambio.

Es comn que f 0,9


Estimando para SPN: Promedio exponencial

Figura: Promedio exponencial (prediccin de prxima solicitud detiempo) de un proceso. (Silberschatz, p.183)



Figura: El proceso ms corto a continuacin (SPN)



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

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

Pero vimos que una sla permutacin entre el rden deB y C redujo fuertemtente los factores de penalizacin


Variaciones sobre SPN: SPN preventivo (PSPN)

Emplea la estrategia de SPN, pero interrumpe cadaquantumFinkel observa que la penalizacin a procesos largos no esmucho peor que la de la rondaMantiene mejores promedios, porque los procesos cortossalen ms temprano de la cola.


Variaciones sobre SPN: El ms penalizado acontinuacin (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 penalizacinP = 1Cada vez que un proceso es obligado a esperar un tiempow por otro, P = w+tt (acumulando w)Se elige el proceso cuyo valor de P sea mayor


El ms penalizado a continuacin (HPRN)

Mientras < 1, HPRN evita inanicin incluso en procesoslargosFinkel apunta que, ante la experimentacin, 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 invocacin deldespachador


Retroalimentacin multinivel (FB)

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

Cada cola con un distinto nivel de prioridad, CPEl despachador toma el proceso al frente de la cola dems prioridadTras n ejecuciones, el proceso es degradado a CP+1Favorece a los procesos cortos

Terminan su trabajo sin ser marcados como de prioridadinferior

El algoritmo es baratoSlo hay que actualizar a un proceso a cada ejecucin, yevaluar un nmero limitado de colas



Figura: Retroalimentacin multinivel (FB) bsica. En la lneasuperior al proceso se muestra la cola antes del quantum en que seejecuta.



Fenmenos observados:

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

En una implementacin ingenua, esto causa un cambio decontexto

Burocracia innecesaria

Puede prevenirse esta interrupcin?



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 nmeros apuntan a que es una peorestrategia que las anteriores!Los nicos beneficiados son los recin llegados

Entran a la cola de mayor prioridadUn proceso largo, a mayor , enfrenta inanicin

El rendimiento del algoritmo puede ajustarse con dosvariables bsicas:

n Cuntas ejecuciones para ser degradado aCP+1

Q Duracin del quantum de las siguientes colasVeamos cmo se comporta cuando:

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



Figura: Retroalimentacin multinivel (FB) con Q exponencial



Fenmenos observados:

Aunque FB favorece a los procesos recin 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

Tpicamente los incrementos son ms suaves Q = nqo incluso q = q log(n)Un proceso largo con Q exponencial puede causarinanicin por largo tiempo

Para evitar la inanicin ante un alto, puede considerarsela retroalimentacin en sentido inverso

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



El mecanismo es muy flexible, y permite muchas mejorassimplesHoy en da 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 parmetros y prioridades


Ronda egosta (SRR)

Selfish Round RobinMultitarea preventivaFavorece a los proesos que ya llevan tiempo ejecutandosobre los recin llegados

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

Parmetros 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.


Ronda egosta (SRR)

Figura: Ronda egosta (SRR) con a = 2 y b = 1


Ronda egosta (SRR)



Ronda egosta (SRR)

Mientras ba < 1:Los procesos nuevos sern aceptados eventualmenteSi el control va alternando entre dos procesos, suprioridad se mantendr igual, y sern despachados porronda simple

Si ba 1, el proceso en ejecucin terminar antes de quese acepte el nuevo

Tiende a FCFSSi ba = 0 (esto es, si b = 0)

Los procesos recin llegados son aceptadosinmediatamenteTiende a ronda

Si 0 < ba < 1, la ronda es relativamente egostaSe 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 informacin intrnseca Si, para tomar cada decsin deplanificacin, emplean informacin propia(intrnseca) a los procesos evaluados, o no Esto es, si el historial de ejecucin de un procesotiene impacto en cmo ser planificado a futuro.


Clasificando a los distintos esquemas

Cuadro: Caracterizacin de los mecanismos de planificacin a cortoplazo

No considera Consideraintrnseca intrnseca

Cooperativa Primero llegado Proceso msprimero servido corto (SPN),(FCFS) Proceso ms

penalizado (HPRN)Preventiva Ronda (RR), Proceso ms

Retroalimentacin (FB), corto preventivoRonda egosta (SRR) (PSPN)


ndice

1 Introduccin

2 Mtricas





Esquemas hbridos

Los esquemas de planificacin empleados normalmenteusan mezclas de los algoritmos presentadosPermite emplear el algoritmo que ms ventajas presenteante una situacin dada

Y evitar algunas de sus deficiencias


Esquemas hbridos: 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 ms 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 msgilmente posiblePero no obstaculizan a los procesos cortos que vanllegando


Esquemas hbridos: Dependientes del estado delsistema

Podemos considerar tambin informacin extrnseca paradespachar

Informacin externa al estado y ejecucin de cada uno delos procesosInformacin dependiente del estado del sistema, del tipode usuario, etc.

A continuacin, algunos ejemplos


FCFS/SPN o RR, dependiendo de

Si los procesos son en promedio cortos y < 1Mtodos con la mnima sobrecarga administrativa (FCFSo SPN)O un RR con quantum muy largo (evitando losproblemas de la multitarea cooperativa)

Si los procesos tienden a ser ms largos o si sube Cambiamos a RR con un quantum ms bajo o a PSPN


Ronda con quantum dependiente de procesospendientes

Esquema simple de rondaLa duracin de un quantum es ajustada peridicamenteCada quantum depende de la cantidad de procesos en eltotal de procesos listos, siguiendo Q = qnPocos procesos esperando

Mayor Q Menos cambios de contextoMuchos procesos esperando

Menor QNunca ms all de un minimo, para evitar sobrecargaburocrtica


Ronda + Prioridad externa

Usamos un esquema simple de ronda, con una sola colaLa duracin 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)

Generalizacin sobre HPRNNo slo se considera penalizacin 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 ejecucinDesventaja: Considerar demasiados factores (con distintospesos) impacta en el tiempo de ejecucin del algoritmo

Puede llamarse a WSN peridicamente para formar colasProceder con esquemas ms simples. . . Aunque esto reduce la velocidad de reaccin


Lindura (niceness)

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

Tpicamente slo hacia arriba Se porta ms 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 tamao de la colade procesos listos

Entre ms procesos pendientes, mayor el peso quemodifique a la prioridad


ndice

1 Introduccin

2 Mtricas





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)


Duracin mnima del quantum

Vimos que la penalizacin en la ronda puede evitarse conquantums mayores

Pero puede degenerar en multiprocesamiento cooperativo

Qu tan corto debe ser un quantum?


Duracin mnima del quantum

Duracin de cambio de contexto hoy en da: 0,01ms(Silberschatz p.187)

Con un quantum corto, 10ms, es 11000 la duracin deltiempo efectivo de procesamientoCon un quantum largo, 200ms, 120000

No es realmente significativo Ni debe serlo!Perder 1% del tiempo de cmputo en burocracia sera engeneral visto como excesivoOjo: El tiempo ncleo no slo es el tiempo del cambiode proceso!


Compartir el procesador

Estrategia empleada por Control Data (CDC6600, 1964,diseada por Seymour Cray): Multitarea gestionada enhardwareUn slo 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 ms lentos, cada uno de110 la velocidad del realMultitarea sin cambios de contexto


Compartir el procesador

Desventajas?Nivel de concurrencia fijoDifcil de adecuar a picos de ocupacinCosto muy elevado

Esquema comparable con el HyperThreading deprocesadores actuales

Aunque HyperThreading busca aprovechar las diferentesfases del pipeline, que no exista en 1964


Relacin entre hilos y procesos

Cmo 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 slo proceso

El tiempo se reparte dentro del proceso por mecanismosinternos

Cdigo ms portableNo se aprovecha realmente el paralelismoLlamadas bloqueantes Todos esperan


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 ms 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 LWPTambin hilos no unidos (unbound threads), donde uno oms 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 contencin

Recibe cada uno de los hilos la misma atencin que recibiraun proceso? Hay dos enfoques (categorizacin de hilos POSIX,

pthread):

mbito de contencin de sistema (System ContentionScope, SCS)mbito de contencion de proceso (Process ContentionScope, PCS)

El mbito de contencin se refiere a cul ser la estructuradentro de la cual coexisten los hilos, y dentro de la cual cada

hilo contender por el procesador.


mbitos de contencin

PTHREAD_SCOPE_SYSTEM

Todos los hilos sonatendidos en el tiempoque sera asignado a unslo procesoModelo muchos a uno, ascomo 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 implementacin pthreads puede ofrecer slouno de los modelos Tanto Linux como Windows manejan

slo PTHREAD_SCOPE_SYSTEM (SCS).


Otras caractersticas en pthreads

pthreads incluyen varios de los otros aspectosmencionados en esta unidadEl programador puede solicitar al ncleo la prioridad decada uno de los hilos por separado(pthread_setschedprio)Incluso solicitar el empleo de un algoritmo de planificacinen especfico (sched_setscheduler)Recordemos que pthreads permite, en muchos casos,responder al proceso Disculpa, no puedo hacer eso


Multiprocesamiento

Qu factores relativos a la planificacin tenemos queconsiderar cuando hablamos de un entorno multiprocesado?


Multiprocesamiento: Afinidad

Cuando un proceso se ejecut por cierto tiempo, dejporciones de su espacio de memoria en el cach delprocesador

Tanto segmentos de instrucciones como de datosCada procesador tiene usualmente un cachindependiente

Puede haber un cach comn a todo el sistema (L3);puede haber uno por chip multicore (L2), y puede haberuno especfico para cada ncleo (L1)

Despachar a un proceso en un procesador distinto del queya lo ejecut es un gasto intil

Invalidar el cach que empleRe-poblar el nuevo


Multiprocesamiento: Afinidad

Afinidad suave Un proceso que preferentemente serejecutado 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 asignacin dememoria considere dicha relacin)


Multiprocesamiento: Balanceo de cargas

La situacin ideal es que todos los procesadoresdespachen trabajos al 100% de su capacidad

Pero es un requisito demasiado rgido / 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 acta 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 ncleo revisa peridicamente 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 jaln

Balanceo de cargas: Por jaln (pull migration)

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

Los mecanismos no son mutuamente exclusivos, es comn queun SO emplee ambos.

Todo balanceo de cargas conllevar una penalizacin entrminos de afinidad al CPU.


Multiprocesamiento: Una cola o varias?

En un entorno multiprocesador, cmo encaramos losalgoritmos antes descritos?

Una cola globalParecera una decisin ms simpleSe ejecuta un slo despachador Ahorro de tiempoNo habra que preocuparse por balanceo de cargas Sera 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 relacin conlos hilos que abordamos

Pero s con el multiprocesamientoLa Ley de Moore no slo ha llevado a un paralelismoexpreso (multincleo)

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


Hilos hardware (hyperthreading): Pipelines

Un procesador simple/clsico (ejemplo: MIPS) puededividir la ejecucin de una instruccin en 5 etapas:

IF Recuperacin de la instruccin (InstructionFetch)

ID Decodificacin de la instruccin (InstructionDecode)

EX Ejecucin (Execution)MEM Acceso a datosWB Almacenamiento (Writeback)

Un procesador moderno presenta mucho ms etapas(Pentium 4: 20 etapas)



Figura: Descomposicin de una instruccin en sus cinco pasosclsicos para organizarse en un pipeline



Es comn que se presenten patrones de uso que requierenservicio de diferentes componentes del procesador

A veces con diferentes duracionesLleva a la insercin de demasiadas burbujas Prdidade tiempo

Para remediarlo, un slo procesador (un solo ncleo) sepresenta como compuesto de dos o ms hilos hardware

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



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



Puede profundizarse mucho ms en la planificacin dehilos hardware

Corresponde ms bien al estudio de construccin decompiladoresY de arquitecturas de sistemasConsideraciones de seguridad entre hilos

Presenta gran similitud (aunque no es lo mismo) con lacomparticin 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 garantasde tiempo

Para poder realizar su trabajo, tienen que recibirdeterminado tiempo de procesador antes de un tiempolmite

Estos procesos son conocidos como de tiempo real


Cundo nos enfrentamos con el tiempo real?

Controladores de dispositivosEntregan un determinado bloque de informacin 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 (reproduccin) o como un corte(recodificacin)

Procesadores de criptografaSi 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 cunto tiempo requerir

Puede ser una sola vez: Necesito 600ms en los prximos2sPuede ser peridico: Cada segundo necesito 30ms

El sistema operativo le asignar el tiempo solicitado, o lenotificar que no puede garantizrselo

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 garanta de que elproceso tendr el tiempo que reserv

Tiempo real suave El sistema intentar dar la prioridadrequerida al proceso, pero puede haber pequeasdemoras


Restricciones del tiempo real duro

El planificador debe saber con certeza cunto 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 ms alta ante el planificadorLos procesos de tiempo real pueden llevar a la inanicinde otros procesos

Es esperable y aceptable No debemos correr tantosprocesos de tiempo real! (rompera expectativas)


Retroalimentacin multinivel y tiempo real suave

Puede implementarse con una modificacin al esquema deretroalimentacin multinivel

La cola de tiempo real recibe prioridad sobre todas lasdems 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 dems procesos nunca llegan a subir alnivel de tiempo real por un proceso automtico

Aunque s puede hacerse por una llamada explcitaLa latencia de despacho debe ser mnima

Casi todos los sistemas operativos hoy en da presentanfacilidades bsicas 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 ncleoPrimer enfoque: Puntos de interrupcin

Marcar explcitamente puntos en que todas lasestructuras estn en un estado estable

No muy eficiente: Hay pocos puntos aptos para declararpuntos de interrupcin

Muy rgido, dificil estructurar para poner puntosadicionales


Ncleo completamente interrumpible

Otro enfoque: Proteger a todas las modificaciones aestructuras internas del ncleo con mecanismos desincronizacinEnfoque mucho ms flexibleHace que el sistema operativo completo sea ms lento(aunque ms seguro)

Ms operaciones a hacer por cada solicitud

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


Inversin 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 propsitos prcticos, degradado a laprioridad de A


Inversin de prioridades: Herencia de prioridades

Mecanismo introducido por Solaris 2Si A bloquea a B y PA < PBPA := PB hasta que B libere el recursoPasado el bloqueo, PA vuelve a su estado nativo

IntroduccinMtricasAlgoritmos de planificacinEsquemas hbridos y prioridades externasResumiendo y temas relacionados

Algoritmos Planificador

Documents

Transcript of Algoritmos Planificador