Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Planificacin de procesos: Algoritmos de
planificacin
Gunnar Wolf
Facultad de Ingeniera, UNAM
2013-02-27 2013-03-11
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
ndice
Introduccin
Mtricas
Algoritmos de planificacin
Esquemas hbridos y prioridades externas
Resumiendo y temas relacionados
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Referencia para esta seccin
Buena parte del material de esta unidad toma por referencia al
captulo 2 de An operating systems vade mecum (Raphael
Finkel, 1988)
(Disponible en el sitio Web del curso)
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
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 de
estado?
Solicitudes (y respuestas) de E/S
Swap de/a disco
Cual es el siguiente proceso al que le toca atencin del
CPU?
Y por cunto tiempo?
Vemos que hay tres tipos muy distintos de planificacin.
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Planificador a largo plazo
Cual es el siguiente proceso a ser iniciado
Principalmente orientado a la operacin en lotes
Principalmente a los sistemas con spool
Tambin presente en la multiprogramacin 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 da no se emplean
El usuario indica expresamente qu procesos iniciar
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Planificador a largo plazo
Figura: Planificador a largo plazo
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Planificador a mediano plazo
Cules procesos hay que bloquear
Por escacez/saturacin de algn recurso (p.ej.
almacenamiento primario)
Por haber iniciado una operacin que no puede
satisfacerse an
Cules procesos hay que desbloquear
A la espera de algn dispositivo
Fueron enviados a swap, pero ya requieren o merecen
ejecutarse
Frecuentemente llamado agendador (scheduler)
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Planificador a mediano plazo
Figura: Planificador a mediano plazo, o agendador
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Planificador a corto plazo
Cmo compartir momento a momento al CPU entre
todos los procesos
Se efecta decenas de veces por segundo
Debe ser simple, eficiente y rpido
Se encarga de planificar los procesos listos para ejecucin
Estados listo y ejecutando
Frecuentemente llamado despachador (dispatcher)
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Planificador a corto plazo
Figura: Planificador a corto plazo, o despachador
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
El enfoque de esta seccin
En esta seccin hablaremos particularmente del planificador a
corto plazo
Cuando un proceso es suspendido (o bloqueado) y
posteriormente reactivado, lo trataremos como un proceso
nuevo.
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Tipos de proceso
Diversos procesos tienen distintas caractersticas
Alternan entre rfagas (bursts)
Limitado por CPU
Limitado por E/S
Cuando termina una rfaga limitada por CPU y se
suspende esperando E/S, deja de estar listo y sale de la
vista del despachador
Esto nos lleva a separar los procesos en. . .
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Tipos de proceso
Largos Han estado listos o en ejecucin por mucho
tiempo
Esto es, estn en una rfaga limitada por
CPU
Cortos En este momento estn en una rfaga limitada
por E/S
Requieren atencin meramente ocasional del
procesador
Tienden a estar bloqueados, esperando a
eventos
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
ndice
Introduccin
Mtricas
Algoritmos de planificacin
Esquemas hbridos y prioridades externas
Resumiendo y temas relacionados
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Unidades a manejar
Para hablar de planificacin del procesador, no vamos a
manejar tiempos estndar (s, ms, ns), sino que:
Tick Un tiempo mnimo dado durante el cual se puede
realizar trabajo til. Medida caprichosa y
arbitraria.
En Windows, un tick dura entre 10 y 15 ms. En
Linux (2.6.8 en adelante), dura 1 ms.
Quantum Tiempo mnimo, expresado en ticks, que se
permitir a un proceso el uso del procesador.
En Windows, 212 ticks (esto es, 20180ms).
En Linux, 10200 ticks (10-200ms)
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Qu es mejor?
No hay un slo criterio para definir qu es una mejor
respuesta
El patrn correcto vara segn el propsito del sistema
Un proceso interactivo sufre si el tiempo de respuesta
incrementa, aunque pueda procesar por ms tiempo
corrido
En caso de sufrir demoras, debemos intentar que sean
consistentes, aunque el tiempo promedio resulte
deteriorado
Es mejor saber que el sistema siempre tardar 0.5s en
responder a mis necesidades a que unas veces responda
de inmediato y otras tarde 3s.
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Qu mtricas compararemos?
Para un proceso p que requiere ejecutarse por tiempo t,
Tiempo de respuesta (T ) Tiempo total que toma el trabajo
Incluye el tiempo inactivo (pero listo).
Tiempo en espera (E ) De T , cunto tiempo est esperando
ejecutar. (Tiempo perdido)
E =T t
El proceso p desea que E 0
Proporcin de penalizacin (P) Fraccin del tiempo de
respuesta durante la cual p estuvo en espera.
P = Tt
Proporcin de respuesta (R) Fraccin del tiempo de respuesta
durante la cual p pudo ejecutarse.
R = Tt ; R = P1
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Adems de los anteriores, para el sistema. . .
Tiempo ncleo o kernel Tiempo que pasa el sistema en
espacio de ncleo
Tiempo desocupado (idle) Tiempo en que la cola de procesos
listos est vaca y no puede realizarse ningn
trabajo.
Utilizacin 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 %.
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Por ejemplo. . .
Los siguientes procesos forman la cola de procesos listos:
Proceso
A
B
C
D
Ticks
7
3
12
4
Llegada
0
2
6
20
Toma 2 ticks realizar un cambio de contexto; cada quantum es
de 5 ticks, y tenemos un ordenamiento de ronda1
Que pronto describiremos
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Precisiones sobre el ejemplo
Nuestro ejemplo no es realista
El cambio de contexto propuesto es
desproporcionadamente largo! (slo para ejemplificar)
Consideraremos al tiempo ncleo como si fuera un
proceso ms
Midiendo como si iniciara y terminara junto con los
dems
Normalmente el tiempo ncleo no se cuenta, es tomado
por burocracia
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Graficando nuestro ejemplo
Figura: Ejecucin de cuatro procesos con quantums de 5 ticks y
cambios de contexto de 2 ticks
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Resultado de nuestro ejemplo
Proceso
A
B
C
D
Promedio til
Ncleo
Promedio total
t
T
E
P
R
7
21
14
3.0
0.33
3
8
5 2.66
0.37
12
32
14 2.66
0.37
4
14
10
3.5
0.28
6.5 18.75 10.75 2.958 0.3383
14
40
26
4.0
0.25
8
23 13.8 2.875 0.347
Tiempo kernel 14 ticks
Tiempo desocupado 0 ticks
Utilizacin del CPU 26 ticks
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Frecuencias
Respecto al patrn de llegadas y salidas de procesos a la cola
de procesos listos:
Frecuencia de llegada promedio
Tiempo de servicio requerido promedio
Valor de saturacin, =
Esto significa:
= 0 Nunca llegan procesos nuevos; el sistema estar
desocupado
= 1 Los procesos van saliendo al mismo ritmo al que
van entrando
> 1 Los procesos llegan ms rpido de lo que puede
ser atendidos. La cola de procesos listos tiende a
crecer. R se decrementa para todos.
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
ndice
Introduccin
Mtricas
Algoritmos de planificacin
Esquemas hbridos y prioridades externas
Resumiendo y temas relacionados
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Cundo se ejecuta el despachador?
Cuando un proceso:
1
Pasa de ejecutando a en espera
p.ej. por solicitar E/S, sincronizacin con otro proceso,
ceder el paso (yield)
Pasa de ejecutando a listo
p.ej. al ocurrir una interrupcin
Deja de estar en espera para estar listo
p.ej. cuando finaliza la operacin E/S que solicit
Pasa de ejecutando a terminado
Cuando finaliza su ejecucin
Para la multitarea cooperativa, pueden ser slo 1 y 4.
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Nuestros procesos base
Para presentar los diferentes algoritmos, usarmos la siguiente
tabla de procesos:
Proceso
A
B
C
D
E
Promedio
Tiempo de
llegada
Tiempo
requerido
(t)
0
3
1
5
3
2
9
5
12
5
4
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Primero llegado, primero servido (FCFS)
First Come, First Serve.
Tambin referido como FIFO (First In, First Out)
El esquema ms simple de planificacin
Apto para multitarea cooperativa
Cada proceso se ejecuta en rden de llegada
Hasta que suelta el control
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Primero llegado, primero servido (FCFS)
Figura: Primero llegado, primero servido (FCFS)
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Primero llegado, primero servido (FCFS)
Proceso
Inicio Fin
T
A
0
3
3
B
3
8
7
C
8 10
7
D
10 15
6
E
15 20
8
Promedio
6.2
E
P
0
1
2 1.4
5 3.5
1 1.2
3 1.6
2.2 1.74
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Primero llegado, primero servido (FCFS)
La sobrecarga administrativa es mnima
El algoritmo es extremadamente simple: una cola FIFO
Efecta el mnimo posible de cambios de contexto
No requiere hardware de apoyo (temporizador /
interrupciones)
Principio de histresis (Finkel): Hay que resistirse al
cambio
El rendimiento percibido por los ltimos procesos
disminuye
Los procesos cortos pueden esperar
desproporcionadamente mucho tiempo
La demora aumenta fuertemente conforme crece
Tendencia a la inanicin cuando 1
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Ronda (Round Robin)
Busca dar buena respuesta tanto a procesos cortos como
largos
Requiere multitarea preventiva
Ejecutamos cada proceso por un quantum
Si no termin su ejecucin, se interrumpe y coloca de
vuelta al final de la cola
Los procesos nuevos se forman tambin al final de esta
misma cola
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Ronda (Round Robin)
Figura: Ronda (Round Robin)
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Ronda (Round Robin)
Proceso
Inicio Fin
A
0
6
B
1 11
C
4
8
D
9 18
E
12 20
Promedio
T
E
P
6
3 2.0
10
5 2.0
5
3 2.5
9
4 1.8
8
3 1.6
7.6 3.6 1.98
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Ronda (Round Robin)
Alta frecuencia de cambios de contexto
A pesar de que el algoritmo es simple, la sobrecarga
administrativa (burocracia) es alta
Puede modificarse incrementando el quantum
Reduce la frecuencia de cambios de contexto
Para valores grandes de q, tiende a convertirse en FCFS
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Ronda (Round Robin) con q = 4
Figura: Ronda (Round Robin), con q = 4
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Ronda (Round Robin) con q = 4
Proceso
Inicio Fin
T
E
P
A
0
3
3
0 1.0
B
3 10
9
4 1.8
C
7
9
6
4 3.0
D
10 19 10
5 2.0
E
14 20
8
3 1.6
Promedio
7.2 3.2 1.88
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
El proceso ms corto a continuacin (SPN)
Shortest Process Next
Multitarea cooperativa
Pero requerimos un algoritmo ms justo que FCFS
Sabemos cunto tiempo va a requerir cada proceso
No por magia: Podemos estimar / predecir basados en su
historia
SPN puede mantener la contabilidad de los procesos
incluso tras entregarlos de vuelta al agendador
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Estimando para SPN: Promedio exponencial
Es comn emplear un promedio exponencial para estimar la
siguiente demanda de tiempo de p: Si en su ltima invocacin
emple q quantums,
ep0 = fep + (1 f )q
Donde 0 f 1 es el factor atenuante, determinando qu
tan reactivo ser el promedio a cada cambio.
Es comn que f 0,9
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Estimando para SPN: Promedio exponencial
Figura: Promedio exponencial (prediccin de prxima solicitud de
tiempo) de un proceso. (Silberschatz, p.183)
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
El proceso ms corto a continuacin (SPN)
Figura: El proceso ms corto a continuacin (SPN)
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
El proceso ms corto a continuacin (SPN)
Proceso
Inicio Fin
T
E
P
A
0
3
3
0 1.0
B
5 10
9
4 1.8
C
3
5
2
0 1.0
D
10 15
6
1 1.2
E
15 20
8
3 1.6
Promedio
5.6 1.6 1.32
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
El proceso ms corto a continuacin (SPN)
Obviamente, SPN favorece a los procesos cortos
Un proceso largo puede esperar mucho tiempo antes de
ser atendido
Con alto, los procesos largos sufren inanicin
Con una cola de procesos listos chica, el resultado es
similar a FCFS
Pero vimos que una sla permutacin entre el rden de
B y C redujo fuertemtente los factores de penalizacin
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Variaciones sobre SPN: SPN preventivo (PSPN)
Emplea la estrategia de SPN, pero interrumpe cada
quantum
Finkel observa que la penalizacin a procesos largos no es
mucho peor que la de la ronda
Mantiene mejores promedios, porque los procesos cortos
salen ms temprano de la cola.
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Variaciones sobre SPN: El ms penalizado a
continuacin (HPRN)
Highest Penalty Ratio Next
Multitarea cooperativa
Las alternativas (FCFS y SPN) parecen injustas para
muchos proesos
Busca otorgar un mejor balance
Todos los procesos incian con un valor de penalizacin
P =1
Cada vez que un proceso es obligado a esperar un tiempo
w por otro, P = w t+t (acumulando w )
Se elige el proceso cuyo valor de P sea mayor
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
El ms penalizado a continuacin (HPRN)
Mientras < 1, HPRN evita inanicin incluso en procesos
largos
Finkel apunta que, ante la experimentacin, HPRN se
ubica siempre entre FCFS y SPN
Principal desventaja: Es un algoritmo caro
Cuando hay muchos procesos en la cola, P tiene que
calcularse para todos ellos a cada invocacin del
despachador
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Retroalimentacin multinivel (FB)
Multilevel Feedback
Multitarea preventiva
Se 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 de
ms prioridad
Tras n ejecuciones, el proceso es degradado a CP+1
Favorece a los procesos cortos
Terminan su trabajo sin ser marcados como de prioridad
inferior
El algoritmo es barato
Slo hay que actualizar a un proceso a cada ejecucin, y
evaluar un nmero limitado de colas
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Retroalimentacin multinivel (FB)
Figura: Retroalimentacin multinivel (FB) bsica. En la lnea
superior al proceso se muestra la cola antes del quantum en que se
ejecuta.
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Retroalimentacin multinivel (FB)
Fenmenos observados:
Al tick 8, 10, 11, 13, 14, el despachador interrumpe al proceso
activo y lo vuelve a programar
En una implementacin ingenua, esto causa un cambio de
contexto
Burocracia innecesaria
Puede prevenirse esta interrupcin?
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Retroalimentacin multinivel (FB)
Proceso
Inicio Fin T E
A
0
7 7 3
B
1 18 17 12
C
3
6 3 1
D
9 19 10 5
E
12 20 8 3
Promedio
9 5
P
2.3
3.4
1.5
2.0
1.6
2.16
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Retroalimentacin multinivel (FB)
Pero todos los nmeros apuntan a que es una peor
estrategia que las anteriores!
Los nicos beneficiados son los recin llegados
Entran a la cola de mayor prioridad
Un proceso largo, a mayor , enfrenta inanicin
El rendimiento del algoritmo puede ajustarse con dos
variables bsicas:
n Cuntas ejecuciones para ser degradado a
CP+1
Q Duracin del quantum de las siguientes colas
Veamos cmo se comporta cuando:
Mantenemos n = 1
Q = 2nq (donde q es la duracin del quantum base)
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Retroalimentacin multinivel (FB)
Figura: Retroalimentacin multinivel (FB) con Q exponencial
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Retroalimentacin multinivel (FB)
Fenmenos observados:
Aunque FB favorece a los procesos recin llegados, al tick
3, 9 y 10 los procesos que llegan son puestos en espera
Llegaron a la mitad del quantum largo de otro proceso
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Retroalimentacin multinivel (FB)
Proceso
Inicio Fin T E
P
A
0
4 4 1 1.3
B
1 10 9 4 1.8
C
4
8 5 3 2.5
D
10 18 9 4 1.8
E
13 20 8 3 1.6
Promedio
7 3 1.8
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Retroalimentacin multinivel (FB)
Con Q exponencial, los promedios resultan incluso
mejores que ronda
Tpicamente los incrementos son ms suaves Q = nq
o incluso q = q log(n)
Un proceso largo con Q exponencial puede causar
inanicin por largo tiempo
Para evitar la inanicin ante un alto, puede considerarse
la retroalimentacin en sentido inverso
Si un proceso largo es degradado a CP y pasa demasiado
tiempo sin ejecutarse, promoverlo de vuelta a CP1
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Retroalimentacin multinivel (FB)
El mecanismo es muy flexible, y permite muchas mejoras
simples
Hoy en da es empleado por muchos de los principales
sistemas operativos
FreeBSD, Linux (pre-2.6), MacOS X, NetBSD, Solaris,
Windows (2000 en adelante) (ref: Wikipedia Scheduling
algorithm)
Con diferentes parmetros y prioridades
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Ronda egosta (SRR)
Selfish Round Robin
Multitarea preventiva
Favorece a los proesos que ya llevan tiempo ejecutando
sobre 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 de
procesos aceptados
b Ritmo de incremento de prioridad de
procesos nuevos
Cuando la prioridad de un proceso nuevo alcanza a la de
uno aceptado, ste se acepta.
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Ronda egosta (SRR)
Figura: Ronda egosta (SRR) con a = 2 y b = 1
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Ronda egosta (SRR)
Proceso
Inicio Fin
T
E
P
A
0
4
4
1 1.3
B
2 10
9
4 1.8
C
6
9
6
4 3.0
D
10 15
6
1 1.2
E
15 20
8
3 1.6
Promedio
6.6 2.6 1.79
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Ronda egosta (SRR)
Mientras
b
a
< 1:
Los procesos nuevos sern aceptados eventualmente
Si el control va alternando entre dos procesos, su
prioridad se mantendr igual, y sern despachados por
ronda simple
Si ba 1, el proceso en ejecucin terminar antes de que
se acepte el nuevo
Tiende a FCFS
Si
b
a
= 0 (esto es, si b = 0)
Los procesos recin llegados son aceptados
inmediatamente
Tiende a ronda
Si 0 <
b
a
< 1, la ronda es relativamente egosta
Se da entrada a procesos nuevos
Incluso si hay procesos muy largos ejecutando
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Clasificando a los distintos esquemas
Los siete algoritmos presentados pueden caracterizarse sobre
dos descriptores primarios
Tipo de multitarea si el esquema est planteado para operar
bajo multitarea preventiva o cooperativa
Emplea informacin intrnseca Si, para tomar cada decsin de
planificacin, emplean informacin propia
(intrnseca) a los procesos evaluados, o no
Esto es, si el historial de ejecucin de un proceso
tiene impacto en cmo ser planificado a futuro.
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Clasificando a los distintos esquemas
Cuadro: Caracterizacin de los mecanismos de planificacin a corto
plazo
Cooperativa
Preventiva
No considera
intrnseca
Primero llegado
primero servido
(FCFS)
Considera
intrnseca
Proceso ms
corto (SPN),
Proceso ms
penalizado (HPRN)
Ronda (RR),
Proceso ms
Retroalimentacin (FB), corto preventivo
Ronda egosta (SRR)
(PSPN)
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
ndice
Introduccin
Mtricas
Algoritmos de planificacin
Esquemas hbridos y prioridades externas
Resumiendo y temas relacionados
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Esquemas hbridos
Los esquemas de planificacin empleados normalmente
usan mezclas de los algoritmos presentados
Permite emplear el algoritmo que ms ventajas presente
ante una situacin dada
Y evitar algunas de sus deficiencias
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Esquemas hbridos: Algoritmo por cola en FB
Manejamos varias colas en un esquema FB
Cada cola usa internamente un algoritmo distinto para
elegir el proceso que est a la cabeza. Algunas ideas como
ejemplo:
Una cola bajo PSPN: Empuja a los procesos ms largos
hacia colas que sean interrumpidas con menor frecuencia
Emplear SRR para las colas de menor prioridad
Sus procesos ya esperaron mucho para tener respuesta;
cuando obtienen el procesador, avanzan lo ms
gilmente posible
Pero no obstaculizan a los procesos cortos que van
llegando
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Esquemas hbridos: Dependientes del estado del
sistema
Podemos considerar tambin informacin extrnseca para
despachar
Informacin externa al estado y ejecucin de cada uno de
los procesos
Informacin dependiente del estado del sistema, del tipo
de usuario, etc.
A continuacin, algunos ejemplos
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
FCFS/SPN o RR, dependiendo de
Si los procesos son en promedio cortos y < 1
Mtodos con la mnima sobrecarga administrativa (FCFS
o SPN)
O un RR con quantum muy largo (evitando los
problemas 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
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Ronda con quantum dependiente de procesos
pendientes
Esquema simple de ronda
La duracin de un quantum es ajustada peridicamente
Cada quantum depende de la cantidad de procesos en el
total de procesos listos, siguiendo Q = qn
Pocos procesos esperando
Mayor Q Menos cambios de contexto
Muchos procesos esperando
Menor Q
Nunca ms all de un minimo, para evitar sobrecarga
burocrtica
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Ronda + Prioridad externa
Usamos un esquema simple de ronda, con una sola cola
La duracin del quantum depender de la prioridad
externa
Fijada por el usuario o por el sistema por factores ajenos
al despachador
Un proceso de mayor prioridad ejecutar por mayor
tiempo
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Peor servicio a continuacion (WSN)
Generalizacin sobre HPRN
No slo se considera penalizacin el tiempo esperado en
la cola de procesos listos
Veces que ha sido interrumpido por el temporizador
Prioridad externa
Espera por E/S u otros recursos
El proceso que ha sufrido peor servicio es seleccionado
para su ejecucin
Desventaja: Considerar demasiados factores (con distintos
pesos) impacta en el tiempo de ejecucin del algoritmo
Puede llamarse a WSN peridicamente para formar colas
Proceder con esquemas ms simples
. . . Aunque esto reduce la velocidad de reaccin
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Lindura (niceness)
Empleado por varios Unixes histricos
El usuario inicia (nice) o modifica (renice) la
prioridad de su proceso
Tpicamente slo hacia arriba Se porta ms lindo.
Esta prioridad externa y el tiempo consumido
recientemente por el proceso constituyen una prioridad
interna
La prioridad interna aumenta cuando el proceso espera
Por el despachador, por E/S, o cualquier otra causa
La prioridad interna es matizada por el tamao de la cola
de procesos listos
Entre ms procesos pendientes, mayor el peso que
modifique a la prioridad
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
ndice
Introduccin
Mtricas
Algoritmos de planificacin
Esquemas hbridos y prioridades externas
Resumiendo y temas relacionados
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Sobrecarga administrativa
Figura: Sobrecarga administrativa de los planificadores de corto
plazo (Finkel, p.33)
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Tiempo perdido por sobrecarga adm.
Figura: Tiempo perdido por sobrecarga administrativa por
planificador de corto plazo (Finkel, p.34)
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Duracin mnima del quantum
Vimos que la penalizacin en la ronda puede evitarse con
quantums mayores
Pero puede degenerar en multiprocesamiento cooperativo
Qu tan corto debe ser un quantum?
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Duracin mnima del quantum
Duracin de cambio de contexto hoy en da: 0,01ms
(Silberschatz p.187)
1
la duracin del
Con un quantum corto, 10ms, es 1000
tiempo efectivo de procesamiento
1
Con un quantum largo, 200ms, 20000
No es realmente significativo Ni debe serlo!
Perder 1 % del tiempo de cmputo en burocracia sera en
general visto como excesivo
Ojo: El tiempo ncleo no slo es el tiempo del cambio
de proceso!
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Compartir el procesador
Estrategia empleada por Control Data (CDC6600, 1964,
diseada por Seymour Cray): Multitarea gestionada en
hardware
Un slo procesador, pero con 10 juegos de registros
Procesador superescalar
A cada paso de reloj, avanzaba el juego de registros
Quantum efectivo igual a la velocidad del reloj
Apariencia de 10 procesadores ms lentos, cada uno de
1
10 la velocidad del real
Multitarea sin cambios de contexto
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Compartir el procesador
Desventajas?
Nivel de concurrencia fijo
Difcil de adecuar a picos de ocupacin
Costo muy elevado
Esquema comparable con el HyperThreading de
procesadores actuales
Aunque HyperThreading busca aprovechar las diferentes
fases del pipeline, que no exista en 1964
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Relacin entre hilos y procesos
Cmo entiende el despachador a los hilos?
Tres modelos principales de mapeo:
Muchos a uno
Uno a uno
Muchos a muchos
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
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 mecanismos
internos
Cdigo ms portable
No se aprovecha realmente el paralelismo
Llamadas bloqueantes Todos esperan
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
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 proceso
Comparte memoria, descriptores, estructuras
Aprovecha tanto el paralelismo como lo permita el
hardware
Cada hilo puede correr en un procesador distinto, si los
hay
El SO debe poder manejar LWP
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Muchos a muchos
Figura: Mapeo de hilos muchos a muchos (imagen: Beth Plale)
Existen hilos unidos (bound threads), que corresponden
cada uno a un LWP
Tambin hilos no unidos (unbound threads), donde uno o
ms corresponden a cada LWP
Brindan la flexibilidad de ambos modelos
Si el SO no maneja LWP, pueden caer en el modelo uno
a muchos como modo degradado
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
El mbito de contencin
Recibe cada uno de los hilos la misma atencin que recibira
un proceso? Hay dos enfoques (categorizacin de hilos POSIX,
pthread):
mbito de contencin de sistema (System Contention
Scope, SCS)
mbito de contencion de proceso (Process Contention
Scope, PCS)
El mbito de contencin se refiere a cul ser la estructura
dentro de la cual coexisten los hilos, y dentro de la cual cada
hilo contender por el procesador.
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
mbitos de contencin
PTHREAD_SCOPE_SYSTEM
PTHREAD_SCOPE_PROCESS
Todos los hilos son
atendidos en el tiempo
Cada hilo es visto por el
que sera asignado a un
planificador como un
slo proceso
proceso independiente
Modelo muchos a uno, as
Modelo uno a uno y los
como los hilos no unidos
hilos unidos en muchos a
multiplexados en muchos
muchos
a muchos
. . . Pero una implementacin pthreads puede ofrecer slo
uno de los modelos Tanto Linux como Windows manejan
slo PTHREAD_SCOPE_SYSTEM (SCS).
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Otras caractersticas en pthreads
pthreads incluyen varios de los otros aspectos
mencionados en esta unidad
El programador puede solicitar al ncleo la prioridad de
cada uno de los hilos por separado
(pthread_setschedprio)
Incluso solicitar el empleo de un algoritmo de planificacin
en especfico (sched_setscheduler)
Recordemos que pthreads permite, en muchos casos,
responder al proceso Disculpa, no puedo hacer eso
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Multiprocesamiento
Qu factores relativos a la planificacin tenemos que
considerar cuando hablamos de un entorno multiprocesado?
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Multiprocesamiento: Afinidad
Cuando un proceso se ejecut por cierto tiempo, dej
porciones de su espacio de memoria en el cach del
procesador
Tanto segmentos de instrucciones como de datos
Cada procesador tiene usualmente un cach
independiente
Puede haber un cach comn a todo el sistema (L3);
puede haber uno por chip multicore (L2), y puede haber
uno especfico para cada ncleo (L1)
Despachar a un proceso en un procesador distinto del que
ya lo ejecut es un gasto intil
Invalidar el cach que emple
Re-poblar el nuevo
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Multiprocesamiento: Afinidad
Afinidad suave Un proceso que preferentemente ser
ejecutado en un determinado procesador
Ciertos patrones de carga pueden llevar a que el
despachador decida migrarlo a otro procesador
Afinidad dura Se garantiza que un proceso ser ejecutado
siempre en un procesador (o conjunto de
procesadores)
Ejemplo: En un entorno NUMA, buscamos que los procesos
tengan afinidad dura (y que el algoritmo de asignacin de
memoria considere dicha relacin)
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Multiprocesamiento: Balanceo de cargas
La situacin ideal es que todos los procesadores
despachen 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 encolados
y en espera
. . . O ambas situaciones
Para mantener la divergencia lo menor posible, se emplea
el balanceo de cargas
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Multiprocesamiento: Balanceo de cargas
El balanceo de cargas acta en sentido contrario de la
afinidad al procesador
Algoritmos que analizan el estado de las colas y
transfieran procesos entre ellas para homogeneizarlas
Puede reubicar procesos con afinidad suave
Debe preferir reubicar procesos sin afinidad declarada
No debe reubicar procesos con afinidad dura
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Estrategias de balanceo de cargas: Por empuje
Balanceo de cargas por empuje (push migration)
El ncleo revisa peridicamente el estado de los
procesadores
Si el desbalance sobrepasa cierto umbral, empuja a
algunos procesos de una cola a otra.
Linux ejecuta esto cada 200ms.
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
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 ejecutar
tareas del ncleo
Puede averiguar si hay procesos en espera con otro
procesador, y jalarlos al actual.
Los mecanismos no son mutuamente exclusivos, es comn que
un SO emplee ambos.
Todo balanceo de cargas conllevar una penalizacin en
trminos de afinidad al CPU.
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Multiprocesamiento: Una cola o varias?
En un entorno multiprocesador, cmo encaramos los
algoritmos antes descritos?
Una cola global
Parecera una decisin ms simple
Se ejecuta un slo despachador Ahorro de tiempo
No habra que preocuparse por balanceo de cargas
Sera natural
Una cola por procesador
Necesaria si queremos soportar manejo de afinidad al
CPU
Todos los sistemas en uso amplo implementan una cola
por procesador
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Hilos hardware (hyperthreading)
Hilos es una palabra que sufre abuso en nuestro campo.
Hilos hardware (hyperthreading): No tienen relacin con
los hilos que abordamos
Pero s con el multiprocesamiento
La Ley de Moore no slo ha llevado a un paralelismo
expreso (multincleo)
El pipeline de los procesadores hace que cada unidad
funcional del CPU pueda estar atendiendo a una
instruccin distinta
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Hilos hardware (hyperthreading): Pipelines
Un procesador simple/clsico (ejemplo: MIPS) puede
dividir la ejecucin de una instruccin en 5 etapas:
IF Recuperacin de la instruccin (Instruction
Fetch)
ID Decodificacin de la instruccin (Instruction
Decode)
EX Ejecucin (Execution)
MEM Acceso a datos
WB Almacenamiento (Writeback)
Un procesador moderno presenta mucho ms etapas
(Pentium 4: 20 etapas)
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Hilos hardware (hyperthreading): Pipelines
Figura: Descomposicin de una instruccin en sus cinco pasos
clsicos para organizarse en un pipeline
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Hilos hardware (hyperthreading): Pipelines
Es comn que se presenten patrones de uso que requieren
servicio de diferentes componentes del procesador
A veces con diferentes duraciones
Lleva a la insercin de demasiadas burbujas Prdida
de tiempo
Para remediarlo, un slo procesador (un solo ncleo) se
presenta como compuesto de dos o ms hilos hardware
Conocidos en el mercado como hyper-threads
Puede aumentar el paralelismo aunque es muy
improbable que sea en 2x!
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Hilos hardware (hyperthreading): Pipelines
Figura: Alternando ciclos de cmputo y espera por memoria, un
procesador que implementa hilos hardware (hyperthreaded) se
presenta como dos procesadores
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Hilos hardware (hyperthreading): Pipelines
Puede profundizarse mucho ms en la planificacin de
hilos hardware
Corresponde ms bien al estudio de construccin de
compiladores
Y de arquitecturas de sistemas
Consideraciones de seguridad entre hilos
Presenta gran similitud (aunque no es lo mismo) con la
comparticin de procesador
No ahondaremos en el tema en este curso
Se presenta para aclarar el concepto
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Tiempo real
Nos hemos enfocado a repartir el tiempo disponible entre
varios procesos
No hemos tocado a los procesos que requieren garantas
de tiempo
Para poder realizar su trabajo, tienen que recibir
determinado tiempo de procesador antes de un tiempo
lmite
Estos procesos son conocidos como de tiempo real
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Cundo nos enfrentamos con el tiempo real?
Controladores de dispositivos
Entregan un determinado bloque de informacin cada
tanto tiempo
Si ese bloque no es procesado completo, se sobreescribe
por el siguiente
Reproductores o recodificadores de audio y video
Si un cuadro se pierde, el resultado puede escucharse
Sea como una demora (reproduccin) o como un corte
(recodificacin)
Procesadores de criptografa
Si un bloque se pierde, el documento completo de ese
punto en adelante puede quedar corrupto
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Reserva de recursos
Para poder manejarse como de tiempo real, un proceso
debe declarar de inicio cunto tiempo requerir
Puede ser una sola vez: Necesito 600ms en los prximos
2s
Puede ser peridico: Cada segundo necesito 30ms
El sistema operativo le asignar el tiempo solicitado, o le
notificar que no puede garantizrselo
Mensaje de error El proceso puede intentar continuar
de todos modos sin prioridad especial
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Tiempo real duro y suave
Tiempo real duro El sistema puede dar garanta de que el
proceso tendr el tiempo que reserv
Tiempo real suave El sistema intentar dar la prioridad
requerida al proceso, pero puede haber pequeas
demoras
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Restricciones del tiempo real duro
El planificador debe saber con certeza cunto tiempo
toman todas las tareas de sistema que ejecutar en el
periodo
Algunos dispositivos introducen demoras con demasiada
varianza
Almacenamiento en disco
Memoria virtual
Imposibilitan que un sistema que los maneje implemente
tiempo real duro
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Tiempo real suave: Prioridad del planificador
Los procesos de tiempo real simplemente reciben una
prioridad mucho ms alta ante el planificador
Los procesos de tiempo real pueden llevar a la inanicin
de otros procesos
Es esperable y aceptable No debemos correr tantos
procesos de tiempo real! (rompera expectativas)
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Retroalimentacin multinivel y tiempo real suave
Puede implementarse con una modificacin al esquema de
retroalimentacin multinivel
La cola de tiempo real recibe prioridad sobre todas las
dems colas
La prioridad de un proceso de tiempo real no se degrada
conforme se ejecuta repetidamente
Aunque puede indicar que ya termin con su trabajo
sensible a tiempo
La prioridad de los dems procesos nunca llegan a subir al
nivel de tiempo real por un proceso automtico
Aunque s puede hacerse por una llamada explcita
La latencia de despacho debe ser mnima
Casi todos los sistemas operativos hoy en da presentan
facilidades bsicas de tiempo real suave.
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Sistema operativo interrumpible (prevenible)
Hay llamadas al sistema que toman demasiado tiempo
Para poder ofrecer tiempo real suave con buenas
expectativas, hay que poder interrumpir al propio ncleo
Primer enfoque: Puntos de interrupcin
Marcar explcitamente puntos en que todas las
estructuras estn en un estado estable
No muy eficiente: Hay pocos puntos aptos para declarar
puntos de interrupcin
Muy rgido, dificil estructurar para poner puntos
adicionales
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Ncleo completamente interrumpible
Otro enfoque: Proteger a todas las modificaciones a
estructuras internas del ncleo con mecanismos de
sincronizacin
Enfoque mucho ms flexible
Hace 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 hilos
concurrentes en los distintos procesadores
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Inversin de prioridades
Un proceso A de baja prioridad hace una llamada al
sistema
Es interrumpido a la mitad de la llamada
Un proceso B de prioridad tiempo real hace una segunda
llamada al sistema
Requiriendo de la misma estructura que la que tiene
bloqueada A
B quedar esperando hasta que A vuelva a ser agendado
Esto es, B fue, para propsitos prcticos, degradado a la
prioridad de A
Introduccin Mtricas Algoritmos de planificacin Esquemas hbridos y prioridades externas Resumiendo y temas relac
Inversin de prioridades: Herencia de prioridades
Mecanismo introducido por Solaris 2
Si A bloquea a B y PA < PB
PA := PB hasta que B libere el recurso
Pasado el bloqueo, PA vuelve a su estado nativo
