Trabajo optativo de sistemas operativos avanzados
Mirando hacia atrás sin ira: el planificador de Linux 2.4

Se trata de un ejercicio individual de carácter optativo que permite que el alumno que lo realice pueda obtener hasta 0,5 puntos adicionales en la nota de la asignatura, siempre que la tenga aprobada.

El objetivo de los trabajos optativos que se plantean en la asignatura es que el alumno sea capaz de buscar información sobre un determinado asunto, procesarla adecuadamente y emitir una valoración crítica sobre la misma. Se pretende, de esta forma, complementar el carácter puramente aplicado de las prácticas de la asignatura.

Descripción del trabajo

El planificador del procesador de Linux 2.4 supuso en su momento un importante avance en este componente de Linux, mejorando, entre otros aspectos, el soporte multiprocesador que daba este sistema operativo hasta entonces.

Con el paso del tiempo se ha visto superado por nuevas versiones del planificador (en orden cronológico, el planificador O(1) y el CFS) que han mejorado las diversas deficiencias de este algoritmo. Sin embargo, consideramos que el estudio de este antiguo esquema de planificación proporciona información muy valiosa para los interesados en este campo.

El trabajo consiste, por tanto, en estudiar este algoritmo y responder a las cuestiones que se plantean más adelante sobre el mismo. Nótese que nos vamos a centrar en la planificación de los procesos de la clase SCHED_OTHER puesto que la gestión de los procesos con perfil de tiempo real está definida por el estándar POSIX, no existiendo, por tanto, ninguna aportación específica de Linux.

Este trabajo, además de ofrecer información útil sobre el diseño de planificadores, tiene un objetivo adicional: familiarizarse con el código fuente de Linux y con las herramientas que permiten navegar por el mismo. Dado el gran volumen del código fuente de Linux, es difícil estudiar el mismo sin algún tipo de herramienta que permita navegar cómodamente entre los múltiples ficheros que componen este sistema operativo y que facilite encontrar la ubicación de la definición de los distintos símbolos (tipos de datos, variables, funciones, ...) usados en Linux así como de las referencias a los mismos (es decir, permiten obtener las referencias cruzadas de Linux). Algunas de estas herramientas están disponibles online permitiendo navegar por el código fuente de las distintas versiones de Linux:

Para responder a las preguntas que aparecen a continuación, tendrá que revisar el código fuente de una versión de Linux 2.4 como, por ejemplo, LXR free electrons (versión 2.4.37) (el planificador está básicamente incluido en el fichero kernel/sched.c: LXR free electrons). Como parte de TODA respuesta, tendrá que identificar un fragmento de código relacionado con la misma. Para ello, debe especificar usando una URL la línea de código inicial de ese fragmento.

Ilustrémoslo con el ejemplo de una pregunta hipotética:

Y la consiguiente respuesta: Aquí, finalmente, van las cuestiones sobre este planificador:
  1. ¿Qué estructuras de datos gestiona el planificador? ¿Es un esquema con una única cola de procesos listos en el sistema o una por procesador?
  2. ¿Qué información de planificación guarda en el BCP de cada proceso? ¿Y qué datos almacena por cada procesador?
  3. ¿Cómo selecciona qué proceso debe usar el procesador? ¿Qué orden de complejidad tiene ese proceso de selección?
  4. ¿Qué ocurre cuando todos los procesos han consumido su rodaja?
  5. ¿Cómo se favorece a los procesos con mucha entrada/salida? ¿Hay algún límite en el beneficio que se la da a este tipo de procesos?
  6. ¿Qué medidas se llevan a cabo para evitar que un programa pueda obtener mayor cuota de procesador usando este truco: cuando está a punto de agotar su rodaja, el proceso crea un hijo, que seguiría con el trabajo disponiendo de una rodaja completa, terminando el padre inmediatamente, y así repetidamente?
  7. Este esquema, a la hora de seleccionar el proceso a ejecutar a continuación, beneficia hasta cierto punto a aquellos procesos listos que usan el mismo mapa de memoria que el proceso que acaba de dejar el procesador. ¿Cómo implementa este beneficio? ¿Por qué es conveniente otorgarlo y cómo afecta a la implementación de los threads en Linux?
  8. ¿Cómo incorpora este esquema el concepto de afinidad natural al planificador? ¿Y el de afinidad estricta?
  9. Explique para el caso de un multiprocesador cómo se realiza la selección de en qué procesador ejecutará, en caso de que lo haga, un proceso que se acaba de desbloquear.
  10. Explique para el caso de un multiprocesador cómo se realiza la selección de qué proceso ejecutará en un determinado procesador cuando éste se queda libre (el proceso que estaba ejecutando en ese procesador se ha bloqueado o completado).
  11. En esta última pregunta es el lector el que tiene que diseñar: ¿cómo incluiría en este planificador la problemática específica de los multiprocesadores jerárquicos, no contemplada por el mismo?

El alumno deberá entregar una memoria respondiendo a estas cuestiones incluyendo las referencias bibliográficas (convencionales o web) usadas para la elaboración del mismo.

Entrega del trabajo

El plazo de entrega del trabajo es el viernes 5 de mayo de 2017.

La entrega se realiza en triqui ejecutando el mandato:

    entrega.soa planificador24.2017
Este mandato realizará la recolección del fichero memoria.pdf del directorio ~/DATSI/SOA/planificador24.2017.