Planificador del kernel Linux.

Gabriel Núñez Núñez-Lagos - Juan Antonio Rodríguez Vela

1 Introducción.

Linux es un núcleo (kernel) de sistema operativo. Habitualmente se distribuye junto con una serie de aplicaciones desarrolladas por el proyecto GNU para formar un sistema operativo completo llamado GNU/Linux. Es software libre, lo que quiere decir, fundamentalmente, que se puede leer o modificar el código, distribuir (original o modificado), copiar y utilizar libremente. No se permite plagiarlo, ni distribuirlo sin dar acceso al código fuente, ni cambiarle la licencia.

Linux debe su nombre a su desarrollador original, Linus Torvalds, que era estudiante de Informática en una universidad de Helsinki (Finlandia) cuando en 1991 se decidió a hacer un núcleo de sistema operativo que funcionara como MINIX (un derivado de UNIX). Es muy compatible con UNIX, pero no es un UNIX en el sentido de que por dentro funciona como han querido Linus y los cientos de desarrolladores que trabajan en él por Internet desde su creación.

Desde hace unos meses se encuentra en su versión 2.6 (la 2.6.5 era la última el 20 de Abril de 2004). La versión de producción anterior, la 2.4 (2.4.26 era la última el 23 de Abril de 2004), se sigue utilizando mucho. Las versiones con segunda cifra por la izquierda impar son de desarrollo.

El planificador (scheduler) es la parte del sistema operativo que permite la multiprogramación y el multiproceso mediante la asignación de procesos a las CPUs del sistema y el intercambio de procesos en ejecución. Ha cambiado completamente de una versión a otra, se mantienen las principales estructuras de datos, pero se ha cambiado el algoritmo para hacerlo O(1) y con ello, más escalable¹. La versión más documentada es la 2.4, así que hablaremos fundamentalmente de ella.

2 Características generales.

• Linux es un kernel monolítico, como la mayoría de *NIX. Eso quiere decir que el núcleo hace todo (proporciona todos los servicios del sistema operativo) y todas las capas del núcleo tienen acceso a todas las estructuras de datos, rutinas y componentes del sistema.

• Es capaz de linkar módulos en tiempo de ejecución. Los módulos contienen funcionalidades particulares que son cargadas dentro del Kernel cada vez que se requiere y no están permanentemente alojados dentro del Kernel en sí, ni dentro de la memoria. Además de la reducción en el uso de memoria, los módulos tienen la ventaja de ser actualizables. Al compilar el núcleo se da con cada módulo la opción de incorporarlo estáticamente al binario del kernel o bien compilarlo aparte para que luego se pueda cargar según demanda.
• No está diseñado a partir de hilos de núcleo. El kernel no está implementado como un conjunto de hilos, al contrario que otros *NIX modernos. Aunque realmente los admite: utiliza unos pocos para realizar tareas repetitivas² y no tienen permitido ejecutar programas de usuario.
• Tiene un diseño reentrante de modo que pueden existir varios procesos en modo núcleo 'ejecutándose' a la vez (en monoprocesadores, todos menos uno estarían en la cola de listos).
• Tiene soporte para aplicaciones de usuario multihilo. Antes del kernel 2.0 los hilos en aplicaciones de ususario se gestionaban desde librerías en modo usuario.
• Compatible con estándares: POSIX, las APIs del UNIX SysV y los sockets BSD, sistemas de archivos para todos los gustos, ...
• Admite multiproceso simétrico (SMP).
• No expropiativo (Non-preemptiveness). Quiere decir que un proceso en modo núcleo no puede ser arbitrariamente interrumpido. Realmente sólo tiene interés³ en monoprocesadores, porque si tenemos más de una CPU, un nuevo proceso en modo núcleo podrá ejecutarse, en principio, en una CPU que esté libre sin estorbar a los procesos en modo núcleo que se estén ejecutando en otras CPUs. Era una característica del núcleo 2.4 que ha cambiado en el 2.6: en este último el kernel puede interrumpirse a sí mismo para atender a ciertas interrupciones.

3 Gestión de procesos en linux.

En todo sistema operativo un proceso está representado por una estructura de datos donde se guarda toda la información relevante de éste, el PCB (Process Control Block), bloque de control del proceso o descriptor del proceso.En Linux, el PCB es la estructura struct task_struct. En esta estructura aparece todo tipo de información sobre un proceso.Cada proceso del sistema tiene una estructura del tipo struct task_struct asociada. Dicha estructura forma parte de una estructura del tipo union task_union que contiene el PCB (struct task_struct) y la pila del núcleo de dicho proceso (para cuando el proceso se ejecuta en modo núcleo). Esta estructura, en la que la pila y el PCB comparten la memoria ocupa 8KB.Con esta estructura, el núcleo es capaz de determinar el puntero al PCB de un proceso a partir de su puntero de la pila de núcleo (se hace con la macro current que ejecuta tres instrucciones de ensamblador).

union task_union struct task_struct task;
unsignedlong stack[INIT_TASK_SIZE/sizeof(long)];

El conjunto de procesos en el sistema Linux está representado como una colección de estructuras struct task_struct, las cuales están enlazadas de dos formas principalmente: Como una tabla hash, ordenados por el pid y como una lista circular doblemente enlazada usando los punteros p-next_task y p-prev_task.

• La tabla hash es usada para encontrar rápidamente una tarea por su pid usando find_task_pid().
• La lista circular doblemente enlazada que usa p-next_task/ prev_task es mantenida para poder ir fácilmente a través de todas las tareas del sistema.

static inline struct task_struct *find_task_by_pid(int pid)
$\lbrace$

struct task_struct *p, **htable = pidhash[pid_hashfn(pid)];
/* Se recorren los elementos cuyo
valor dado por la función hash es
el mismo. Son las llamadas colisiones */
for(p = *htable; p p-pid != pid; p = p-pidhash_next);
return p;

$\rbrace$

En caso de colisión en la tabla hash, se usa encadenamiento. Las tareas en cada lista ordenada (esto es, ordenadas por el mismo valor dado por la función hash) son enlazadas por p->pidhash_next/pidhash_pprev el cual es usado por hash_pid() y unhash_pid() para insertar y quitar un proceso dado en la tabla hash. Esto es realizado bajo la protección de un spinlock ⁴ read/write ya que un acceso no controlado a la tabla hash podría traer consecuencias desatrosas.Nótese que el uso de semáforos no sería suficiente para proporcionar protección en caso de múltiples cpu´s.

3.1 Análisis del descriptor de proceso
(struct task_struct)

El principal tipo de dato que se utiliza para gestionar los procesos en el núcleo es task_struct, el descriptor de proceso. Una instancia de este tipo de dato puede ocupar normalmente hasta cerca de 1000 bytes. Está muy bien aprovechada: todas las estructuras y tablas que trabajan con procesos están implementadas de tal forma que una misma de estas task_struct puede formar parte de muchas tablas o listas a la vez. ¿EL truco? Lo que solemos usar como nodo en una lista enlazada (los punteros anterior y siguiente), por ejemplo, no es más que una subestructura incrustada dentro del descriptor del proceso, así es: un puntero al anterior y al siguiente están incrustados dentro de nuestra task_struct.

Muchas partes del S.O. hacen uso de esta estructura de datos, por lo que es necesario conocer los campos más importantes de task_struct.

Algunos de estos campos son:

• volatile long state: contiene el estado del proceso. Que la variable esté declarada como volatile le indica al compilador que su valor puede cambiarse de forma asíncrona (Por ejemplo desde una rutina de tratamiento de interrupción).

  volatile long state;/*-1 no ejecutable, 0 ejecutable, 0 parado*/
  volatile long state; /* -1 no ejecutable, 0 ejecutable, 0 parado */
  
  #define TASK_RUNNING 0 /* Listo, ejecución */
  #define TASK_INTERRUPTIBLE 1 /* Dormido (bloqueado). Admite señales */
  #define TASK_UNINTERRUPTIBLE 2 /* Bloqueado pero sólo responde a la señal o interrupción que espera. */
  #define TASK_ZOMBIE 4 /* Esperando un wait() */
  #define TASK_STOPPED 8 /* SIGSTOP, SIGTSMP, SIGTTIN, SIGTTOU. Depuración*/
  #define TASK_EXCLUSIVE 32
  

• int sigpending: un valor distinto de cero (típicamente 1) indica si el proceso tiene señales pendientes. Se reacciona a estas señales al volver de una llamada al sistema, o de un bloqueo o suspensión.

• mm_segment_taddr_limit: indica el tamaño máximo del espacio de direcciones de dicho proceso. El valor típico es de 3GB para procesos de usuario y 4GB para los hilos de ejecución del núcleo.

• volatile long need_resched: con su valor a 1 indica que este proceso, posiblemente, debe abandonar la CPU y por lo tanto se deberá invocar al planificador en el momento adecuado (en vez de llamar a schedule() directamente).

Otros campos que contienen información general del proceso son:

• int exit_code, exit_signal: contiene el valor de terminación de un proceso, en caso de que haya finalizado mediante la llamada al sistema exit(2). Si termina por una señal, contendrá el número de señal que lo mató.

• struct task_struct*p_opptr, *p_pptr, *p_cptr, *p_ysptr, *p_osptr: Punteros para acceder a toda la familia de procesos: op(Original Parent),p(Parent),c(Youngest Child),ys (Younger Sibling, tu hermano inmediatamente más joven), os (Older Sibling, hermano directamente más viejo).

• long start_time: Indica el instante de creación de este proceso.

• uid_tuid, euid, suid, fsuid; Usuario propietario de este proceso, tanto real (uid), como efectivo (euid), y atributos más específicos.

• gid_tgid, egid, sgid, fsgid: Grupo propietario de este proceso, tanto real (gid), como efectivo (egid), y atributos más específicos.

• unsigned long blocked: Contiene un mapa de bits con las señales que están temporalmente bloqueadas.

• struct sigpending pending: Contiene la información sobre las señales que este proceso tiene pendientes.

Aunque la mayor parte del estado de un proceso se ha salvado en la pila del núcleo con la macro SAVE_ALL, existen algunos registros adicionales que se almacenan en la estructura task_struct y que son utilizados sobre todo en el cambio de contexto.

El campo que contiene esta información es struct thread_struct thread. Algunos de sus campos son:

• unsigned long esp0; Puntero de pila del núcleo.
• unsigned long eip, esp, fs, gs; Puntero de instrucción y de pila del proceso y otros registros de segmento del i386.
• unsigned long debugreg [ 8 ] ; Registros de depuración.

4 Descripción del algoritmo de planificación de procesos.

Los tipos de algoritmos de planificación usados en este núcleo están definidos en las extensiones de tiempo real del estándar POSIX (POSIX.1b, antes llamado POSIX.4). El algoritmo de planificación es bastante parecido a un Round Robin con prioridades. Puede haber a la vez en el sistema procesos con distinta política de planificación establecida. En realidad cada proceso se puede planificar de varias maneras, las políticas de planificación de un proceso se pueden cambiar en tiempo de ejecución y son:

• SCHED_OTHER : Es la planificación clásica de UNIX. No es aplicable a tiempo real. Examina las prioridades dinámicas (calculadas como combinación de las especificadas por el usuario y las calculadas por el sistema). Los procesos que llevan más tiempo en el sistema van perdiendo prioridad.
• SCHED_FIFO : El sistema FIFO o FCFS (First to Come is First Served). Los procesos esperan en cola y se ejecutan secuencialmente. Se sigue calculando un cuanto de tiempo para el proceso, aunque normalmente no se use porque con esta planificación no se fuerza al proceso a abandonar la CPU. Se usa en procesos de tiempo real.
• SCHED_RR : Round Robin o turno rotatorio. Funciona como el FIFO pero ahora cuando un proceso acaba su cuanto de tiempo (time slice) se le desaloja. El siguiente proceso se escoge de la lista de procesos con SCHED_RR o de la lista SCHED_FIFO. Son procesos en tiempo real.
• SCHED_YIELD : No es una política de planificación, sino un modificador que afecta a las tres políticas anteriores. El proceso cede la CPU a cualquier otro que esté listo. Se activa con una llamada al sistema (sched_yield()) sólo para el siguiente ciclo de planificación.

4.1 El algoritmo del kernel 2.4.

La prioridad de un proceso se calcula sumando. Por una parte se usa una función goodness que mide lo deseable (entre -1000, nada deseable y +1000, tiempo real, ejecutar ya) de ejecutar un proceso evaluando la prioridad. Si el proceso no es de tiempo real, se parte del tiempo restante de CPU (prioridad dinámica guardada en counter) de forma que tienen más prioridad aquellos a los que les quede más tiempo de CPU, se aumenta ligeramente la prioridad de los hilos del mismo proceso, se favorece a los procesos que se hayan estado ejecutando en la misma CPU (si se usa SMP) y se añade el valor de nice que especificó el usuario. Si no, los procesos en tiempo real tienen un campo extra de prioridad que se suma a 1000 para el cálculo de goodness. Por otra parte, existe una función sys_nice o sys_setpriority que se usa para aumentar la prioridad estática del proceso. La prioridad estática se guarda en un campo priority del descriptor de proceso y se usa para inicializar el valor de nice además de marcar el valor inicial del cuanto de tiempo.

La función schedule realiza el ciclo de planificación. Se la puede llamar explícitamente o la puede llamar el sistema operativo: a la vuelta de una llamada al sistema, después de poner el proceso actual en la cola de espera o por temporizador.

En primer lugar se definen los punteros a la tabla de procesos prev y next, que apuntarán al proceso que estaba en ejecución y al proceso que se va a pasar a ejecutar, luego si la política del proceso ya ejecutado es RR se comprueba su cuanto de tiempo y si ha acabado,el proceso es enviado al final de la cola de listos. Si el proceso actual no está en TASK_RUNNING se quita de la cola de preparados,y si está en estado TASK_INTERRUPTIBLE se le enia una señal si hay que despertarlo, en caso contrario se eleimina de la cola. Más tarde se elimina la marca que indica la necesidad de planificación.

Existe una única cola de procesos que empieza en INIT, y que se va recorriendo en busca del mayor valor devuelto por goodness. Si no encuentra ningún proceso con cuanto por ejecutar se restablece el cuanto de cada de las tareas. Se divide por dos el tiempo de CPU (valor de counter que marca el tiempo restante) y se le suma la prioridad estática para obtener el nuevo valor del contador. Lo normal es que el valor del contador anterior sea 0 por lo tanto estariamos inicializando el contador a la prioridad estática. Podría no ser 0 si se hubiera llamado a goodness() con el bit SCHED_YIELD activo. Estos cálculos se hacen con la función recalculate que en este kernel resultaba poco eficiente.

4.2 Diferencias en el kernel 2.6.

El nuevo planificador ejecuta un hilo de núcleo en cada CPU. Este hilo se encarga de planificar los procesos de la cola de ejecución de la CPU en la que se ejecuta. Se llama a este hilo por temporizador, por llamada del sistema o cuando se ha acabado la cola de ejecución para equilibrar la carga con otras CPUs. Además, se lleva la cuenta del comportamiento del proceso, si se dedica a entrada/salida o tiene carga de CPU, pudiendo cambiar dinámicamente la política de planificación y la prioridad del proceso.

Tal como indicaba Ingo Molnar cuando anunció el nuevo planificador en enero de 2002 (kernel 2.5.2-pre6) se pretendía mantener las cosas buenas del planificador antiguo y añadir 'algunas pocas':

• O(1): Se eliminan unos bucles que recalculaban datos para las rutinas wakeup(), schedule() y la interrupción por tiempo. Ahora se hacen con algoritmos que tardan un tiempo constante, independientemente de las circunstancias que rodean la ejecución.
• Escalabilidad con multiproceso simétrico. Dos procesos en dos CPUs distintas se ejecutan de forma totalemente independiente. Antes se usaba una sola cola para todos y un semáforo runqueue_lock para todos los procesos de todas las CPUs.
• Mayor afinidad por el procesador. Un proceso tiende a ejecutarse en el mismo procesador después de un bloqueo o suspensión. No se le cambia de procesador sin motivo. Los intervalos de tiempo se distribuyen en cada CPU por separado.
• Planificación por lotes. Se ha añadido SCHED_BATCH a los posibles valores de la política de planificación. Los procesos por lotes utilizan la CPU cuando no hay otros procesos listos: tienen menos prioridad que cualquier otro proceso pero sus cuantos de tiempo son mucho mayores.
• Capacidad para manejar grandes cargas sin colapsar la planificación.
• Para la planificación en tiempo real (RT) , que usaba cola FIFO, el algoritmo también es O(1).
• Ejecutar los hijos antes que el proceso padre. Mejora la eficiencia.

5 Apéndice: Hilos y procesos.

Linux usa la misma estructura de datos (task_struct) para representar un proceso y para representar un hilo. Esto supone una ventaja importante para la planificación: se planifica cada hilo como si fuera un proceso. A veces a esto se le llama proceso ligero (LWP- Light Weight Process). La peculiaridad es que esta estructura tiene unos campos que son punteros al espacio de direcciones de un proceso.

¿En qué se diferencia un proceso hijo de un hilo? Al crear un proceso hijo lo que se hace es copiar la memoria del padre en otra dirección y hacer que estos punteros señalen a la nueva; al crear un hilo lo que se hace es copiar los punteros, de forma que todos los hilos de un mismo proceso comparten exactamente el mismo espacio de direcciones. La sincronización y exclusión mutua del acceso concurrente de los hilos a la memoria del proceso es responsabilidad del programador que los usa ;-) .

6 Apéndice2: Spinlocks.

Desde los primeros días del soporte Linux los desarrolladores se encararon con el clásico problema de acceder a datos compartidos entre los diferentes tipos de contexto (procesos de usuario vs interrupciones) y diferentes instancias del mismo contexto para múltiples cpus.

Si la región crítica del código puede ser ejecutada por el contexto de los procesos y el contexto de las interrupciones, entonces la forma de protegerlo usando las instrucciones cli/sti en UP es:

save_flags(flags);
cli();
/* código crítico */
restore_flags(flags);

Mientras que esto está bien en UP, obviamente no lo está usándolo en SMP porque la misma secuencia de código quizás sea ejecutada simultáneamente en otra cpu, y mientras cli() suministra protección contra las carreras con el contexto de interrupciones en cada CPU individualmente, no suministra protección contra todas las carreras entre los contextos funcionando en diferentes CPUs. Ocurriría lo mismo si usasemos semáforos Es aquí donde los spinlocks son útiles.

Ejemplo de uso:

spin_lock(lock);
/* sección crítica */
spin_unlock(lock);

7 Bibliografía

• http://ftp.kernel.org/pub/linux/kernel/people/davej/misc/post-halloween-2.6.txt
• http://www.hpl.hp.com/research/linux/kernel/o1.php
• http://www.escomposlinux.org/wwol26/wwol26.html
• http://nulies.hispalinux.es/
• http://safari.iki.fi/O%281%29-scheduler.txt
• http://es.tldp.org/Manuales-LuCAS/DENTRO-NUCLEO-LINUX/dentro-nucleo-linux-html/dentro-nucleo-linux.html#toc2
• http://www.kernelnewbies.org
• Understanding The Linux Kernel. Daniel P. Bovet, Marco Cesati. 2ª Edición. Sebastopol, Clifornia Ed. O'Really 2003.
• http://sopa.dis.ulpgc.es/ii-dso/leclinux/procesos/planificador/LEC6_CHEDULER.pdf
• http://www.arstechnica.com/etc/linux/index.html
• http://www.kernel.org/pub/linux/kernel/v2.6/linux-2.6.5.tar.bz2
• http://www.kernel.org/pub/linux/kernel/v2.4/linux-2.4.26.tar.bz2

8 Condiciones de copia y distribución.

Copyright 2004 Juan Antonio Rodríguez Vela, Gabriel Núñez Núñez-Lagos (gabriel.nnl@estudiante.uam.es).

Este documento es software libre. Se puede copiar, distribuir usar y modificar según los términos de la Licencia Pública General de GNU (GPL- GNU General Public License). Tiene una copia de esta licencia en http://www.gnu.org/licenses/gpl.txt

Se considerará como código fuente el código HTML.

Sobre este documento...

Copyright (C) 2004 Juan Antonio Rodriguez & Gabriel Nunez
charla-kernelv1-0-html.html :: descargado de la sección de documentación de la Asociación para el Fomento del Software Libre: http://afsl.adi.uam.es

Notas al pie

... escalable¹

La habilidad de manejar con eficiencia distintas cantidades de recursos y CPUs, desde pequeños procesadores empotrados hasta sistemas multiprocesador se conoce como escalabilidad.

... repetitivas²

Esos hilos son: proceso0, proceso1, keventd, kapm, kswapd, kflush (bdflush), kupdated, ksoftirqd. En el 2.6 hay además un hilo en cada CPU que se encarga de balancear la carga entre procesadores.

... interés³

El interés recaía en que se facilitaba el diseño del kernel si se consideraba que las estructuras de datos no podían ser modificadas por otros procesos durante la ejecución de un proceso en modo núcleo.

...spinlock ⁴

Los spinlocks son una de las formas de controlar la concurrencia en el kernel. Hablaremos de ellos en el apéndice segundo.