PDF de programación - Planificación de procesos: Temas relacionados

Afinando al despachador
El despachador y los hilos
El despachador y el multiprocesamiento
Planificación de tiempo real

Planificación de procesos: Temas relacionados

Gunnar Wolf

Gunnar Wolf

Planificación de procesos: Temas relacionados

Afinando al despachador
El despachador y los hilos
El despachador y el multiprocesamiento
Planificación de tiempo real

Índice

1 Afinando al despachador

2 El despachador y los hilos

3 El despachador y el multiprocesamiento

4 Planificación de tiempo real

Gunnar Wolf

Planificación de procesos: Temas relacionados

Afinando al despachador
El despachador y los hilos
El despachador y el multiprocesamiento
Planificación de tiempo real

Comparando los distintos algoritmos

Los ejemplos que presentamos son sólo con una distribución
arbitraria de procesos

Diferentes distribuciones llevarán necesariamente a distintos
resultados

Para comparar de forma significativa los distintos mecanismos,
habría que analizar con muy distintas cargas
Raphael Finkel compara en An operating systems vade mecum
(1988) lo observado en distintos conjuntos de procesos, bajo
los diferentes mecanismos

Gunnar Wolf

Planificación de procesos: Temas relacionados

Afinando al despachador
El despachador y los hilos
El despachador y el multiprocesamiento
Planificación de tiempo real

Midiendo la respuesta de distintos algoritmos

Parámetros de los procesos:

Generados de forma aleatoria, obedeciendo a distribución
exponencial
Simulación de 50,000 procesos
α = 0,8, β = 1,0 → ρ = 0,8

Finkel apunta a que una verdadera comparación debería ser
tridimensional (variando ρ)

Pero presentan ya un acercamiento útil acerca de su
comportamiento general

Gunnar Wolf

Planificación de procesos: Temas relacionados

Afinando al despachador
El despachador y los hilos
El despachador y el multiprocesamiento
Planificación de tiempo real

Proporción de penalización (P)

Figura: Proporción de penalización contra porcentaje de tiempo
requerido en despachadores (Finkel, p.33)

Gunnar Wolf

Planificación de procesos: Temas relacionados

Afinando al despachador
El despachador y los hilos
El despachador y el multiprocesamiento
Planificación de tiempo real

Tiempo perdido (E)

Figura: Tiempo perdido contra porcentaje de tiempo requerido en
despachadores (Finkel, p.34)

Gunnar Wolf

Planificación de procesos: Temas relacionados

Afinando al despachador
El despachador y los hilos
El despachador y el multiprocesamiento
Planificación de tiempo real

Duración mínima del quantum

Vimos que la penalización en la ronda puede evitarse con
quantums mayores

Pero puede degenerar en multiprocesamiento cooperativo

¿Qué tan corto debe ser un quantum?

Gunnar Wolf

Planificación de procesos: Temas relacionados

Afinando al despachador
El despachador y los hilos
El despachador y el multiprocesamiento
Planificación de tiempo real

Duración mínima del quantum

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

Con un quantum corto, 10ms, es
efectivo de procesamiento
Con un quantum largo, 200ms,

1
1000 la duración del tiempo

No es realmente significativo — ¡Ni debe serlo!

1

20000

Perder 1 % del tiempo de cómputo en burocracia sería en
general visto como excesivo
Ojo: ¡El tiempo núcleo no sólo es el tiempo del cambio de
proceso!

Gunnar Wolf

Planificación de procesos: Temas relacionados

Afinando al despachador
El despachador y los hilos
El despachador y el multiprocesamiento
Planificación de tiempo real

¿Puede acelerarse más el cambio de contexto?

En breve vamos a ver una posible solución (que ha caído en el

olvido):

Compartir o multiplexar el procesador a nivel hardware

. . . Recordemos este punto al llegar allá.

Gunnar Wolf

Planificación de procesos: Temas relacionados

Afinando al despachador
El despachador y los hilos
El despachador y el multiprocesamiento
Planificación de tiempo real

Índice

1 Afinando al despachador

2 El despachador y los hilos

3 El despachador y el multiprocesamiento

4 Planificación de tiempo real

Gunnar Wolf

Planificación de procesos: Temas relacionados

Afinando al despachador
El despachador y los hilos
El despachador y el multiprocesamiento
Planificación de tiempo real

Relación entre hilos y procesos

¿Cómo entiende el despachador a los hilos?

Tres modelos principales de mapeo:

Muchos a uno
Uno a uno
Muchos a muchos

Gunnar Wolf

Planificación de procesos: Temas relacionados

Afinando al despachador
El despachador y los hilos
El despachador y el multiprocesamiento
Planificación de tiempo real

Muchos a uno

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

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

El tiempo se reparte dentro del proceso por mecanismos
internos

Código más portable
No se aprovecha realmente el paralelismo
Llamadas bloqueantes → Todos esperan

Gunnar Wolf

Planificación de procesos: Temas relacionados

Afinando al despachador
El despachador y los hilos
El despachador y el multiprocesamiento
Planificación de tiempo real

Uno a uno

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

Cada hilo es un proceso ligero (lightweight process, LWP)
Un LWP es mucho más ligero de levantar que un 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

Gunnar Wolf

Planificación de procesos: Temas relacionados

Afinando al despachador
El despachador y los hilos
El despachador y el multiprocesamiento
Planificación de tiempo real

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
También hilos no unidos (unbound threads), donde uno o más
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

Gunnar Wolf

Planificación de procesos: Temas relacionados

Afinando al despachador
El despachador y los hilos
El despachador y el multiprocesamiento
Planificación de tiempo real

El ámbito de contención

¿Recibe cada uno de los hilos la misma atención que recibiría un

proceso? Hay dos enfoques (categorización de hilos POSIX,

pthread):

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

El ámbito de contención se refiere a cuál será la estructura dentro

de la cual coexisten los hilos, y dentro de la cual cada hilo

contenderá (competirá) por el procesador.

Gunnar Wolf

Planificación de procesos: Temas relacionados

Afinando al despachador
El despachador y los hilos
El despachador y el multiprocesamiento
Planificación de tiempo real

Ámbitos de contención

PTHREAD_SCOPE_SYSTEM

Todos los hilos son atendidos
en el tiempo que sería
asignado a un sólo proceso
Modelo muchos a uno, así
como los hilos no unidos
multiplexados en muchos a
muchos

PTHREAD_SCOPE_PROCESS

Cada hilo es visto por el
planificador como un proceso
independiente
Modelo uno a uno y los hilos
unidos en muchos a muchos

. . . Pero una implementación pthreads puede ofrecer sólo uno de

los modelos → Tanto Linux como Windows manejan sólo

PTHREAD_SCOPE_SYSTEM (SCS).

Gunnar Wolf

Planificación de procesos: Temas relacionados

Afinando al despachador
El despachador y los hilos
El despachador y el multiprocesamiento
Planificación de tiempo real

Otras características en pthreads

pthreads incluyen varios de los otros aspectos mencionados
en esta unidad
El programador puede solicitar al núcleo la prioridad de cada
uno de los hilos por separado (pthread_setschedprio)
Incluso solicitar el empleo de un algoritmo de planificación en
específico (sched_setscheduler)
. . . Pero recordemos que pthreads permite, en muchos
casos, responder al proceso «Disculpa, no puedo hacer eso»

Gunnar Wolf

Planificación de procesos: Temas relacionados

Afinando al despachador
El despachador y los hilos
El despachador y el multiprocesamiento
Planificación de tiempo real

Índice

1 Afinando al despachador

2 El despachador y los hilos

3 El despachador y el multiprocesamiento

4 Planificación de tiempo real

Gunnar Wolf

Planificación de procesos: Temas relacionados

Afinando al despachador
El despachador y los hilos
El despachador y el multiprocesamiento
Planificación de tiempo real

Compartir el procesador

Estrategia empleada por Control Data (CDC6600, 1964,
diseñada por Seymour Cray): Multitarea gestionada en
hardware
Un sólo 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 más lentos, cada uno de 1
velocidad del real
Multitarea sin cambios de contexto

10 la

Gunnar Wolf

Planificación de procesos: Temas relacionados

Afinando al despachador
El despachador y los hilos
El despachador y el multiprocesamiento
Planificación de tiempo real

Compartir el procesador

¿Desventajas?

Nivel de concurrencia fijo
Difícil de adecuar a picos de ocupación
Costo muy elevado

Esquema comparable con el HyperThreading de procesadores
actuales

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

Hoy en día. . . Mera curiosidad histórica.

Gunnar Wolf

Planificación de procesos: Temas relacionados

Afinando al despachador
El despachador y los hilos
El despachador y el multiprocesamiento
Planificación de tiempo real

Multiprocesamiento

¿Qué factores relativos a la planificación tenemos que considerar

cuando hablamos de un entorno multiprocesado?

Gunnar Wolf

Planificación de procesos: Temas relacionados

Afinando al despachador
El despachador y los hilos
El despachador y el multiprocesamiento
Planificación de tiempo real

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é común a tod