02_Planificador

Planificador de Linux (Scheduler)
Profesor Gilberto Díaz
gilberto@ula.ve

Universidad de Los Andes
Facultad de Ingeniería
Departamento de Computación

G. Díaz (ULA)

Planificador de Linux (Scheduler)

Mérida, 2013

1 / 21

Necesidad

Planificador de Linux
Definición
La planificación es el método mediante el cual los hilos, los procesos o los
flujos de datos tienen acceso a los recursos, porejemplo, tiempo de
procesador, ancho de banda en la comunicación, entre otros.

G. Díaz (ULA)

Planificador de Linux (Scheduler)

Mérida, 2013

2 / 21

Necesidad

Planificador de Linux

Planificador
Es el componente del sistema operativo encargado de la planificación. La
necesidad de algoritmos de planificación surgió con la aparición de sistemas
operativos multi tareas.
Completely Fair Scheduler(CFS)
Desde la versión 2.6.23 el planificador tradicional de Linux fue remplazado
por el CFS. El 80 % del diseño de CFS fundamentalmente modela un
Procesador multi tarea “ideal”.

G. Díaz (ULA)

Planificador de Linux (Scheduler)

Mérida, 2013

3 / 21

Necesidad

Completely Fair Scheduler

Completely Fair Scheduler
CFS busca mantener el balance (equidad) en el tiempo de procesador
que se asignan alos procesos. Cada proceso debe recibir un tiempo
equitativo.
Cuando un proceso esta “fuera de balance”, se le asigna tiempo de
ejecución en el procesador.
Para determinar el balance, CFS mantiene la cantidad de tiempo que
se le ha asignado a un proceso en lo que llaman “Virtual Runtime”.

G. Díaz (ULA)

Planificador de Linux (Scheduler)

Mérida, 2013

4 / 21

Necesidad

Completely Fair SchedulerCompletely Fair Scheduler
CFS utiliza una colas basadas en el tiempo.
El proceso con menor “Virtual Runtime” es el más próximo a ser
ejecutado.

G. Díaz (ULA)

Planificador de Linux (Scheduler)

Mérida, 2013

5 / 21

Necesidad

Arquitectura CFS
Arquitectura CFS
CFS mantiene un árbol “rojo-negro” ordenado por tiempo.

G. Díaz (ULA)

Planificador de Linux (Scheduler)

Mérida, 2013

6 / 21Necesidad

Arquitectura CFS

Arquitectura CFS
Un árbol RB está balanceado
El sub árbol con claves menores a n se encuentra a la izquierda.
El sub árbol con claves mayores a n se encuentra a la derecha.
La profundidad de 2 nodos cualquiera no difiere en más de 1.
Los sub árboles son balanceados también.
La búsqueda es O(log n)

G. Díaz (ULA)

Planificador de Linux (Scheduler)

Mérida, 2013

7 / 21Necesidad

Arquitectura CFS

Arquitectura CFS
El nodo más a la izquierda tiene la clave más pequeña. Eso quiere
decir que es el nodo con el menor “virtual runtime”. Es decir, es el
nodo que representa al proceso que más necesita ejecutarse
El nodo de más a la derecha tiene la clave más grande (mayor virtual
runtime). Es el proceso que menos necesita ejecución.
Entonces, CFS selecciona el nodo más a laizquierda para ser
despachado.
El nodo se elimina del árbol. Si no ha terminado, se inserta de nuevo
con un nuevo valor de virtual runtime.

G. Díaz (ULA)

Planificador de Linux (Scheduler)

Mérida, 2013

8 / 21

Necesidad

Arquitectura CFS

Arquitectura CFS
virtualruntime+ =

(delta_exec)(NICE _0_LOAD)
se(load.weight)

Arquitectura CFS
delta_exec Cantidad de tiempo de ejecución.
NICE _0_LOADValor de la unidad de peso.

G. Díaz (ULA)

Planificador de Linux (Scheduler)

Mérida, 2013

9 / 21

Necesidad

Arquitectura CFS
Arquitectura CFS
Los arboles “rojo-negro” son auto-balanceables. Ningún camino es, a lo
sumo, el doble en tamaño que cualquier otro.

G. Díaz (ULA)

Planificador de Linux (Scheduler)

Mérida, 2013

10 / 21

Necesidad

Arquitectura CFS
Arquitectura CFS
Las operaciones enel árbol ocurren en tiempo O(log (n)), donde n es
el número de nodos del árbol. De esta manera se pueden ejecutar las
operaciones de inserción y eliminación de procesos de manera rápida y
eficiente.

G. Díaz (ULA)

Planificador de Linux (Scheduler)

Mérida, 2013

11 / 21

Necesidad

Políticas de Planificación

Políticas de Planificación
Utiliza una técnica de tiempo compartido.
A cada proceso se...