Transcription
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasPlani cación de procesos: Algoritmos deplani caciónGunnar WolfFacultad de Ingeniería, UNAMInstituto de Investigaciones Económicas, UNAMGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades s de plani caciónEsquemas híbridos y prioridades externasGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasReferencia para esta secciónBuena parte del material de esta unidad toma por referencia alcapítulo 2 de An operating systems vade mecum (RaphaelFinkel, 1988), disponible para su descarga en el sitio Web delautor.Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasPrincipal decisión en un sistema multitareas¾Qué proceso es el siguiente a ejecutar?¾Qué eventos ocurrieron que hacen que cambien deestado?¾Qué procesos han ido terminando?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 plani cación.Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasPlani cador a largo plazoCual es el siguiente proceso a ser iniciadoPrincipalmente orientado a la operación en lotesPrincipalmente a los sistemas con spoolTambién presente en la multiprogramación tempranaDecide en base a los requisitos pre-declarados de losprocesos, y a los recursos disponibles al ejecutarsePeriodicidad: segundos a horasHoy en día no se empleanEl usuario indica expresamente qué procesos iniciarPodría verse a los programas comocron, at,o enWindows al Plani cador de procesos como cubriendo esterolAunque son procesosGunnar Wolfplenamente en espacio de usuarioPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasPlani cador a largo plazoFigure: Plani cador a largo plazoGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasPlani cador a mediano plazoCuáles procesos hay que bloquearPor escasez/saturación de algún recurso (p.ej.almacenamiento primario)Por haber iniciado una operación que no puedesatisfacerse aúnCuáles procesos hay que desbloquearA la espera de algún dispositivoFueron enviados a swap, pero ya requieren o merecenejecutarseFrecuentemente llamado agendador (scheduler)Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasPlani cador a mediano plazoFigure: Plani cador a mediano plazo, o agendadorGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasPlani cador a corto plazoCómo compartir momento a momento al CPU entretodos los procesosSe efectúa decenas de veces por segundoSe encarga de plani car los procesos listos para ejecuciónFrecuentemente llamado despachador (dispatcher)Debe ser simple, e ciente y rápidoEstados listo y ejecutandoGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasPlani cador a corto plazoFigure: Plani cador a corto plazo, o despachadorGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasTipo de plani cador según transición:Admitir:Ocurrió evento,Esperar evento:Activar ejecución,Tiempo terminadoLargo plazoMediano plazoCorto plazoFigure: Diagrama de transición entre losestados de un procesoGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasEl enfoque de esta unidadEn esta unidad hablaremos particularmente del plani cador acorto plazoCuando un proceso es suspendido (o bloqueado) yposteriormente reactivado, lo trataremos como un procesonuevo.Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasTipos de procesoDiversos procesos tienen distintas característicasAlternan entre ráfagas (bursts)CPU Trabajando con datos ya existentes en elsistemaE/S Mayormente esperando a eventos de E/SUn programa dado puede ser mayormente de un tipo uotro Dicho programa está limitado por CPU o limitadopor E/SCuando termina una ráfaga de CPU y se suspendeesperando E/S, deja de estar listo y sale de la vista deldespachadorEsto nos lleva a separar los procesos en.Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasTipos de procesoOjo: ½Un poco contraintuitivo!Largos Han estado listos o en ejecución por muchotiempoEsto es, están en una ráfaga de CPUCortos En este momento están en una ráfaga de E/SRequieren atención meramente ocasional delprocesadorTienden a estar bloqueados, esperando aeventosComo buena parte de los procesosinteractivosGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades s de plani caciónEsquemas híbridos y prioridades externasGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasUnidades a manejarPara hablar de plani cació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.En Linux (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 a 12 ticks (esto es, 20 a180ms).En Linux, 10 a 200 ticks (10 a 200ms)Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externas¾Qué es mejor?No hay un sólo criterio para de nir 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 tiempocorridoEn 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.¾O no?Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externas¾Qué es mejor?No hay un sólo criterio para de nir 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 tiempocorridoEn 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.¾O no?Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externas¾Qué métricas compararemos?Para un proceso p que requiere ejecutarse por tiempo t ,Tiempo de respuesta (T ) Tiempo total que toma el trabajo.Incluye el tiempo que pasó inactivo (pero listo).Tiempo en espera (E ) De T , cuánto tiempo está esperandoejecutar. (Tiempo perdido)E T t ; Idealmente, para p , Ep 0Proporción de penalización (P ) Fracción del tiempo derespuesta Tdurante la cual p estuvo en espera.P tProporción de respuesta (R ) Fracción del tiempo de respuestadurante la tcual p pudo ejecutarse.R T ;R P1Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasAdemás de los anteriores, para el sistema. . .Tiempo núcleo o kernel Tiempo que pasa el sistema enespacio de núcleoTiempo desocupado (idle) Tiempo en que la cola de procesoslistos está vacía y no puede realizarse ningúntrabajo.El sistema operativo aprovecha este tiempopara realizar tareas de mantenimientoUtilizació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%.Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasPor ejemplo. . .Los siguientes procesos forman la cola de procesos listos:Proceso Ticks LlegadaA70B32C126D420Toma 1 tick realizar un cambio de contexto; cada quantum esde 5 ticks, y tenemos un ordenamiento de ronda11 Quepronto describiremosGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasPrecisiones sobre el ejemploNuestro ejemplo no es realista½El cambio de contexto propuesto esdesproporcionadamente largo! (sólo para ejempli car)Consideraremos al tiempo núcleo como si fuera unproceso másMidiendo como si iniciara y terminara junto con losdemásNormalmente el tiempo núcleo no se cuenta, es tomadopor burocraciaGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasGra cando nuestro ejemploFigure: Ejecución de cuatro procesos con quantums de 5 ticks ycambios de contexto de 1 tickGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasResolviendo nuestro ejemploProcesotABCDPromedio útilNúcleoPromedio totalTiempo kernelTiempo desocupadoUtilización del CPUGunnar Wolf731246TEPRPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasResultado de nuestro ejemploProcesotTEPR7 18 11 2.57 0.3893 7 4 2.33 0.42912 26 14 2.17 0.4624 9 5 2.25 0.444Promedio útil 6.5 15 8.50 2.31 0.433Núcleo6 32 26 5.33 0.188Promedio total 6.4 18.4 12.00 2.88 0.348Tiempo kernel 14 ticksTiempo desocupado 0 ticksUtilización del CPU 26 ticksABCDGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasFrecuenciasRespecto 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 signi ca:ρ 0 Nunca llegan procesos nuevos; el sistema estarádesocupadoρ 1 Los procesos salen al mismo ritmo al que entranρ 1 Los procesos llegan más rápido de lo que puedeser atendidos. La cola de procesos listos tiende acrecer. R disminuye para todos.αβGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades s de plani caciónEsquemas híbridos y prioridades externasGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externas¾Cuándo se ejecuta el despachador?1Cuando un proceso:Pasa de ejecutando a en esperap.ej. por solicitar E/S, sincronización con otro proceso,Pasa de ejecutando a listoDeja de estar en espera para estar listoPasa de ejecutando a terminadoceder el paso (yield)2p.ej. al ocurrir una interrupción3p.ej. cuando naliza la operación E/S que solicitó4Cuando naliza su ejecuciónPara la multitarea cooperativa, podrían ser sólo 1 y 4.Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasNuestros procesos basePara presentar los diferentes algoritmos, usarmos la siguientetabla de procesos:Tiempo de TiempoProcesollegada requerido(t )A03B15C32D95E125Promedio4Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasPrimero llegado, primero servido (FCFS)First Come, First Serve.También referido como FIFO (First In, First Out)El esquema más simple de plani caciónApto para multitarea cooperativaCada proceso se ejecuta en órden de llegadaHasta que suelta el controlGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasPrimero llegado, primero servido (FCFS)Figure: Primero llegado, primero servido (FCFS)Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasPrimero llegado, primero servido (FCFS)Proceso Inicio Fin T E PA0 3 3 0 1B3 8 7 2 1.4C8 10 7 5 3.5D10 15 6 1 1.2E15 20 8 3 1.6Promedio6.2 2.2 1.74Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasPrimero llegado, primero servido (FCFS)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 procesosdisminuyeLos procesos cortos pueden esperardesproporcionadamente mucho tiempoLa demora aumenta fuertemente conforme creceTendencia a la inanición cuando ρ 1Gunnar WolfρPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasRonda (Round Robin)Busca dar buena respuesta tanto a procesos cortos comolargosRequiere multitarea preventivaEjecutamos cada proceso por un quantumSi no terminó su ejecución, se interrumpe y coloca devuelta al nal de la colaLos procesos nuevos se forman también al nal de estamisma colaGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasRonda (Round Robin)Figure: Ronda (Round Robin)Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasRonda (Round Robin)Proceso Inicio Fin T E PA0 6 6 3 2.0B1 11 10 5 2.0C4 8 5 3 2.5D9 18 9 4 1.8E12 20 8 3 1.6Promedio7.6 3.6 1.98Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasRonda (Round Robin)Alta frecuencia de cambios de contextoA pesar de que el algoritmo es simple, la sobrecargaadministrativa (burocracia) es altaPuede modi carse incrementando el quantumReduce la frecuencia de cambios de contextoPara valores grandes de q, tiende a convertirse en FCFSGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasRonda (Round Robin) con q 4Figure: Ronda (Round Robin), con qGunnar Wolf 4Plani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasRonda (Round Robin) con q 4Proceso Inicio Fin T E PA0 3 3 0 1.0B3 10 9 4 1.8C7 9 6 4 3.0D10 19 10 5 2.0E14 20 8 3 1.6Promedio7.2 3.2 1.88Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasEl 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 procesoNo por magia: Podemos estimar / predecir basados en suhistoriaRecuerden: Un proceso puedeentrar y salirdel ámbitodel despachadorSPN puede mantener la contabilidad de los procesosincluso tras entregarlos de vuelta al agendadorGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasEl 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 procesoNo por magia: Podemos estimar / predecir basados en suhistoriaRecuerden: Un proceso puedeentrar y salirdel ámbitodel despachadorSPN puede mantener la contabilidad de los procesosincluso tras entregarlos de vuelta al agendadorGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasSPN con tiempos declaradosHace años, podía esperarse que los usuarios proporcionaran unestimado de sus tiempos de ejecución:En un sistema que da alta prioridad a los procesos conestimación de tiempo corta, la política normal esterminar aquellos procesos que excedan sus límitesestimados; de otro modo, los usuarios pronto arruinaríanel esquema. En este caso, la mayoría de usuariospre eren hacer predicciones conservadoras. Morris (1967)encuentra que los usuarios sobre-estimaron sus requisitosde almacenamiento por 50%, y dice que las estimacionesen tiempo de procesamiento son mucho peores Per Brinch Hansen, 1973Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasEstimando para SPN: Promedio exponencialEs común emplear un promedio exponencial para estimar lasiguiente demanda de tiempo de p: Si en su última invocaciónempleó q quantums,ep fep (1 f )qDonde 0 f 1 es el factor atenuante, determinando quétan reactivo será el promedio a cada cambio.Es común que f 0.90Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasEstimando para SPN: Promedio exponencialFigure: Predicción de próxima solicitud de tiempo de un procesobasado en su historia.Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasEl proceso más corto a continuación (SPN)Figure: El proceso más corto a continuación (SPN)Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasEl proceso más corto a continuación (SPN)Proceso Inicio Fin T E PA0 3 3 0 1.0B5 10 9 4 1.8C3 5 2 0 1.0D10 15 6 1 1.2E15 20 8 3 1.6Promedio5.6 1.6 1.32Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasEl 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ónCon una cola de procesos listos chica, el resultado essimilar a FCFSPero vimos que una sóla permutación entre el órden deB y C redujo fuertemtente los factores de penalizaciónGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasVariaciones 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.Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasVariaciones sobre SPN: El más penalizado acontinuación (HPRN)Highest Penalty Ratio NextMultitarea cooperativaLas alternativas (FCFS y SPN) parecen injustas paramuchos proesosBusca otorgar un mejor balanceTodos los procesos incian con un valor de penalizaciónP 1Cada vez que un procesoes obligado a esperar un tiempow por otro, P w t t (acumulando w )Se elige el proceso cuyo valor de P sea mayor Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasEl 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 caroCuando hay muchos procesos en la cola, P tiene quecalcularse para todos ellos a cada invocación deldespachadorGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasMecanismos con múltiples colasHasta ahora, se evalúa cómo ordenar los procesos en lacola única de procesos listosDar trato diferenciado a procesos con per les distintos escomplicado. ¾Y si montamos distintas colas de procesos listos?Asignando determinado patrón de comportamiento a lamigración de una cola a otraDando un trato diferenciado a los procesos de distintascolasGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasMecanismos con múltiples colasFigure: Representación de un sistema con cinco colas de prioridad ysiete procesos listosGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasRetroalimentación multinivel (FB)Multilevel FeedbackMultitarea preventivaSe crea no una, sino varias colas de procesos listosPEl despachador toma el proceso al frente de la cola demás prioridadTras n ejecuciones, el proceso es degradado a CPFavorece a los procesos cortosCada cola con un distinto nivel de prioridad, C 1Terminan su trabajo sin ser marcados como de prioridadEl algoritmo es baratoinferiorSólo hay que actualizar a un proceso a cada ejecución, yevaluar un número limitado de colasGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasRetroalimentación multinivel (FB)Figure: Retroalimentación multinivel (FB) básica. En la líneasuperior al proceso se muestra la cola antes del quantum en que seejecuta.Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasRetroalimentación multinivel (FB)Fenómenos observados:Al tick 8, 10, 11, 13, 14, el despachador interrumpe al procesoactivo y lo vuelve a programarEn una implementación ingenua, esto causa un cambio decontexto¾Puede prevenirse esta interrupción?Burocracia innecesariaGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasRetroalimentación multinivel (FB)Proceso Inicio Fin T E PA0 7 7 4 1.7B1 18 17 12 3.4C3 6 3 1 1.5D9 19 10 5 2.0E12 20 8 3 1.6Promedio9 5 2.04Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasRetroalimentación multinivel (FB)½Pero todos los números apuntan a que es una peorestrategia que las anteriores!Los únicos bene ciados son los recién llegadosEntran a la cola de mayor prioridadUn proceso largo, a mayorρ,enfrenta inaniciónEl rendimiento del algoritmo puede ajustarse con dosvariables básicas:n Cuántas ejecuciones para ser degradado aCPQ Duración del quantum de las siguientes colasVeamos cómo se comporta cuando: 1Mantenemos nQ 2nq 1(donde q es la duración del quantum base)Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasRetroalimentación multinivel (FB)Figure: Retroalimentación multinivel (FB) con Q exponencialGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasRetroalimentación multinivel (FB)Fenómenos observados:Aunque FB favorece a los procesos recién llegados, al tick3, 9 y 10 los procesos que llegan son puestos en esperaLlegaron a la mitad del quantum largo de otro procesoGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasRetroalimentación multinivel (FB)Proceso Inicio Fin T E PA0 4 4 1 1.3B1 10 9 4 1.8C4 8 5 3 2.5D10 18 9 4 1.8E13 20 8 3 1.6Promedio7 3 1.8Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasRetroalimentación multinivel (FB)Con Q exponencial, los promedios resultan inclusomejores que rondaTípicamente los incrementos son más suaves Qo incluso q nq q log(n)Un proceso largo con Q exponencial puede causarinanición por largo tiempoPara evitar la inanición ante un ρ alto, puede considerarsela retroalimentación en sentido inversoSi un proceso largo es degradado a CP y pasa demasiadotiempo sin ejecutarse, promoverlo de vuelta a CP 1Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasRetroalimentación multinivel (FB)El mecanismo es muy exible, y permite muchas mejoríassimplesHoy en día es empleado por muchos de los principalessistemas operativosFreeBSD, Linux (pre-2.6), MacOS X, NetBSD, Solaris,Windows (2000 en adelante) (ref: Wikipedia Schedulingalgorithm )Con diferentes parámetros y prioridadesGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasRonda egoísta (SRR)Sel sh Round RobinMultitarea preventivaFavorece a los proesos que ya llevan tiempo ejecutandosobre los recién llegadosUn proeso nuevo se forma en la cola de procesos nuevos,el despachador avanza sólo sobre los procesos aceptadosParámetros ajustables:a Ritmo de incremento de prioridad deprocesos aceptadosb Ritmo de incremento de prioridad deprocesos nuevosCuando la prioridad de un proceso nuevo alcanza a la deuno aceptado, éste se acepta.Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasRonda egoísta (SRR)Figure: Ronda egoísta (SRR) con aGunnar Wolf 2y b 1Plani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasRonda egoísta (SRR)Proceso Inicio Fin T E PA0 4 4 1 1.3B2 10 9 4 1.8C6 9 6 4 3.0D10 15 6 1 1.2E15 20 8 3 1.6Promedio6.6 2.6 1.79Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasRonda egoísta (SRR)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 simpleSi 1, el proceso en ejecución terminará antes de quese acepteel nuevo Tiende a FCFSbSi a 0 (esto es, si b 0)b aLos procesos recién llegados son aceptadosSi 0inmediatamente ba Tiende a ronda1, la ronda es relativamente egoístaSe da entrada a procesos nuevosIncluso si hay procesos muy largos ejecutandoGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasClasi cando a los distintos esquemasLos siete algoritmos presentados pueden caracterizarse sobredos descriptores primariosTipo de multitarea si el esquema está planteado para operarbajo multitarea preventiva o cooperativaEmplea información intrínseca Si, para tomar cada decsión deplani cació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á plani cado a futuro.Gunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasClasi cando a los distintos esquemasTable: Caracterización de los mecanismos de plani cación a cortoplazoCooperativaPreventivaNo consideraConsideraintrínsecaintrínsecaPrimero llegadoprimero servido(FCFS)Ronda (RR)Gunnar WolfProceso máscorto (SPN),Proceso máspenalizado (HPRN)Proceso más cortopreventivo (PSPN),Retroalimentación (FB),Ronda egoísta (SRR)Plani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades s de plani caciónEsquemas híbridos y prioridades externasGunnar WolfPlani cación de procesos: Algoritmos de plani cación
IntroducciónMétricasAlgoritmos de plani caciónEsquemas híbridos y prioridades externasEsquemas híbridosLos esquemas de plani cación empleados normalmenteusan mezclas de los algoritmos presentadosPermite emplear el algoritmo que más ventajas presenteante una situación dadaY evitar algunas de sus de cienciasGunnar WolfPlani cación de procesos:
Principalmente a los sistemas con spool ambiénT presente en la multiprogramación temprana Decide en base a los requisitos pre-declarados de los procesos, y a los recursos disponibles al ejecutarse Periodicidad: segundos a horas Hoy en día no se emplean El usuario indica expresamente qué procesos iniciar
