Planificador de Linux (Scheduler)

Profesor Gilberto Díazgilberto@ula.ve

Universidad de Los AndesFacultad 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ónLa planificación es el método mediante el cual los hilos, los procesos o losflujos de datos tienen acceso a los recursos, por ejemplo, tiempo deprocesador, 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

PlanificadorEs el componente del sistema operativo encargado de la planificación. Lanecesidad de algoritmos de planificación surgió con la aparición de sistemasoperativos multi tareas.

Completely Fair Scheduler (CFS)

Desde la versión 2.6.23 el planificador tradicional de Linux fue remplazadopor el CFS. El 80% del diseño de CFS fundamentalmente modela unProcesador 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 procesadorque se asignan a los procesos. Cada proceso debe recibir un tiempoequitativo.Cuando un proceso esta “fuera de balance”, se le asigna tiempo deejecución en el procesador.Para determinar el balance, CFS mantiene la cantidad de tiempo quese 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 Scheduler

Completely Fair SchedulerCFS utiliza una colas basadas en el tiempo.El proceso con menor “Virtual Runtime” es el más próximo a serejecutado.

G. Díaz (ULA) Planificador de Linux (Scheduler) Mérida, 2013 5 / 21

Necesidad

Arquitectura CFS

Arquitectura CFSCFS 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 CFSUn árbol RB está balanceadoEl 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 CFSEl nodo más a la izquierda tiene la clave más pequeña. Eso quieredecir que es el nodo con el menor “virtual runtime”. Es decir, es elnodo que representa al proceso que más necesita ejecutarseEl nodo de más a la derecha tiene la clave más grande (mayor virtualruntime). Es el proceso que menos necesita ejecución.Entonces, CFS selecciona el nodo más a la izquierda para serdespachado.El nodo se elimina del árbol. Si no ha terminado, se inserta de nuevocon 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 CFSdelta_exec Cantidad de tiempo de ejecución.NICE_0_LOAD Valor de la unidad de peso.

G. Díaz (ULA) Planificador de Linux (Scheduler) Mérida, 2013 9 / 21

Necesidad

Arquitectura CFS

Arquitectura CFSLos arboles “rojo-negro” son auto-balanceables. Ningún camino es, a losumo, 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 en el árbol ocurren en tiempo O(log(n)), donde n esel número de nodos del árbol. De esta manera se pueden ejecutar lasoperaciones de inserción y eliminación de procesos de manera rápida yeficiente.

G. Díaz (ULA) Planificador de Linux (Scheduler) Mérida, 2013 11 / 21

Necesidad

Políticas de Planificación

Políticas de PlanificaciónUtiliza una técnica de tiempo compartido.

A cada proceso se le asigna un quantum de tiempo para ejecutarse enel procesador.

La planificación se ejecuta acorde a un ranking de prioridad.Utiliza prioridades dinámicas que son ajustadas a través del tiempo.Los procesos que no han sido ejecutados por ele procesador en unperiodo largo de tiempo, aumentan su prioridad. Los que han sidoejecutados por mayor tiempo, reducen su prioridad.

G. Díaz (ULA) Planificador de Linux (Scheduler) Mérida, 2013 12 / 21

Necesidad

Políticas de Planificación

Políticas de PlanificaciónSe utiliza la expropiación de procesos. Un proceso se expropia cuando:

Se acaba su quantum de tiempo.Entra un nuevo proceso con mayor prioridad que se ejecutaactualmente.

G. Díaz (ULA) Planificador de Linux (Scheduler) Mérida, 2013 13 / 21

Necesidad

Políticas de Planificación

Políticas de PlanificaciónUn proceso puede tener 2 tipos de prioridades:

Estática:Dinámica:

G. Díaz (ULA) Planificador de Linux (Scheduler) Mérida, 2013 14 / 21

Necesidad

Prioridad Estática

Prioridad EstáticaEstática: Es asignada cuando el proceso es creado. Los procesos detiempo real también tienen prioridad estática (de 0 a 99). Estosprocesos tienen prioridad mayor a los procesos comunes y no puede sercambiada por el planificador. Estos utilizan 2 tipos de políticas:

SCHED_FIFOSCHED_RR

Los procesos normales utilizan la política SCHED_OTHER.

G. Díaz (ULA) Planificador de Linux (Scheduler) Mérida, 2013 15 / 21

Necesidad

Políticas de Planificación

Políticas de PlanificaciónUn proceso puede tener 2 tipos de prioridades:

Estática: Es asignada cuando el proceso es creado. Los procesos detiempo real también tienen prioridad estática (de 0 a 99). Estosprocesos tienen prioridad mayor a los procesos comunes y no puede sercambiada por el planificador. Estos utilizan 2 tipos de políticas:

G. Díaz (ULA) Planificador de Linux (Scheduler) Mérida, 2013 16 / 21

Necesidad

Políticas de Planificación

Políticas de PlanificaciónSe pueden clasificar los procesos mediante dos esquemas:

CPU-bound y I/O-boundInteractive, Batch y Real-Time

El planificador asigna mayor prioridad a procesos en tiempo real. Estosnunca pueden ser bloqueados por procesos de menor prioridad.Los procesos “Batch” son penalizados por el planificador, ya que noson responsivos y corren generalmente en segundo plano.Los procesos “Real Time” necesitan mayor tiempo de ejecución.

G. Díaz (ULA) Planificador de Linux (Scheduler) Mérida, 2013 17 / 21

Necesidad

Funcionamiento

FuncionamientoEl planificador de Linux ejecuta varios métodos para cumplir su función,entre los principales están:

scheduler_tick()try_to_wake_up()recalc_task_prio()load_balance()schedule()

G. Díaz (ULA) Planificador de Linux (Scheduler) Mérida, 2013 18 / 21

Necesidad

Funcionamiento

Rutina schedule()

Es el método más importante del planificador. Este método es elresponsable de elegir el próximo proceso a ser ejecutado.Es ejecutado cuando:

Un proceso cede voluntariamente el CPU.Un proceso espera por una señal para dormir.Un proceso agota su tiempo de ejecución.Otros casos.

G. Díaz (ULA) Planificador de Linux (Scheduler) Mérida, 2013 19 / 21

Necesidad

Kernel de Linux

G. Díaz (ULA) Planificador de Linux (Scheduler) Mérida, 2013 20 / 21

Necesidad

Kernel de Linux

Kernel de LinuxSe encuentra en el directorio de los códigos fuentes del kernel, en eldirectorio /usr/src/linux/kernel/sched/. Algunos de los archivos principalesson:

sched.c : Contiene el código del planificador genérico. Las políticas degestión están implementadas en otros archivos.sched_fair.c : Contiene el código del planificador CFS y provee laspoliticas de planificación para los procesos “Interactive” y “Batch”.sched_rt.c : Provee las políticas usadas para los procesos “RealTime”.

G. Díaz (ULA) Planificador de Linux (Scheduler) Mérida, 2013 21 / 21