Planificador y cambios de contexto

Dos flujos de ejecución sólo pueden ser concurrentes en una misma CPU si existe la posibilidad de realizar un cambio de contexto entre ellos.

Qué procedimiento seguir viene dictado por las características de los flujos en ejecución; por ejemplo, para dos procesos cada uno con su propio espacio de direcciones, el cambio de contexto —en x86— deberá actualizar el registro CR3. Por el contrario, no sería necesario si se salta entre dos hilos de un mismo proceso.1

Otra diferencia surge cuando los flujos de ejecución pertenecen a distintos niveles de privilegio (ring 0 vs ring 3, por ejemplo). Sin embargo, la diferencia de privilegio no implica necesariamente un cambio de espacio de direcciones, lo cual quedará al arbitrio de la implementación.

En definitiva, la expresión “flujos de ejecución” intenta subrayar esta idea: hay tantas modalidades de cambio de contexto como modelos de ejecución: proceso vs userspace thread vs kernel thread, etc.

Índice

Todo el código base del lab se puede leer online aquí, y clonar mediante:

1
2

$ git clone \
  https://gist.github.com/e3a5a8fc5ef68b080ace77043c4449f2 sched

Un context switch simple

El código que se presenta a continuación estudia en detalle uno de los casos más sencillos de context switching:

  • ejecución sin memoria virtual
  • en un mismo nivel de privilegio
  • sin interrupciones habilitadas

En otras palabras, el kernel ejecuta concurrentemente varios flujos de ejecución de su propio código. Al no haber interrupciones (ni siquiera de un reloj), el planificador es necesariamente cooperativo: sólo se cambia de tarea cuando la tarea en ejecución decide ceder el control.

Por usar terminología distinta, el código usa Task para referirse a los flujos de ejecución en este caso de estudio. Esta es la función principal de este kernel:

1
2
3
4
5
6
7
8
9
10
11

int main(void) {
    task_init();

    task_spawn(contador1);
    task_spawn(contador2);
    task_spawn(contador3);

    while (1) {
        sched();  // Become the idle task.
    }
}

Código de las tareas: un contador

El kernel se limita a lanzar tres tareas que mantienen un contador en el buffer VGA:

1
2
3

static void contador1(void) ...  // Verde, rápido.
static void contador2(void) ...  // Naranja, lento.
static void contador3(void) ...  // Rojo, muy lento.

Contadores

El archivo contador.c contiene la implementación:

1
2
3
4

// Imprime en una línea VGA un contador que se auto-incrementa.
// Para moderar la velocidad, hace (TICKS << delay) iteraciones
// por incremento.
void contador(uchar linea, char color, uchar delay) ...

Definición y creación de tareas

De manera similar a JOS, las tareas se almacenan en un arreglo global de tareas:

1
2
3
4
5

// task.c
#define MAX_TASK 128

static struct Task *current;
static struct Task Tasks[MAX_TASK];

La primera decisión es dónde guardar el estado de cada tarea. Como no hay niveles de privilegio distinto, el diseño más simple consiste en usar el stack propio de cada tarea:2

1
2
3
4

struct Task {
    unsigned *stack;
    enum TaskStatus status;
};

Como ninguna de las tareas va a dormir, solo hay tres posibles estados de cada tarea:

1
2
3
4
5

enum TaskStatus {
    FREE = 0,
    READY,
    RUNNING,
};

Al arrancar el kernel, se asigna el primer elemento del arreglo como tarea actual:

1
2
3
4
5
6

// Asigna a main() el índice 0, y lo marca como RUNNING.
// main() se convierte después en la “idle task” del sistema.
void task_init(void) {
    current = &Tasks[0];
    current->status = RUNNING;
}

Finalmente, arrancar una tarea es similar a usar clone() o pthread_init(), ya que el código ya está cargado en memoria. Los pasos son:

  1. encontrar una posición libre en el arreglo global Tasks
  2. reservar espacio para su stack (4 KiB)
  3. preparar el stack para su ejecución via swtch()

Los pasos 1 y 2 son, simplemente:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

// Crea una nueva tarea, marcándola como READY. No se ejecutará
// hasta que se llame a sched().
void task_spawn(void (*entry)(void)) {
    unsigned i = 0;

    // (1) Encontrar la siguiente posición libre.
    while (i < MAX_TASK && Tasks[i].status != FREE)
        i++;

    // (2) Reservar y asignar el stack
    void *stack = stack_alloc(STACK_SIZE) ...
    Tasks[i].stack = stack;
    Tasks[i].status = READY;

    // (3) Preparar el stack conforme a lo que espera swtch().
    ...

Funciones swtch() y sched()

La función sched() simplemente encuentra una tarea en estado READY, e invoca a swtch() para que realice el cambio de contexto. swtch() es realmente quien realiza el trabajo.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void sched() {
    int i;
    struct Task *old = current;

    for (i = 0; i < MAX_TASK; i++)
        if (Tasks[i].status == READY)
            break;

    if (i < MAX_TASK) {
        old->status = READY;
        current = &Tasks[i];
        current->status = RUNNING;
        swtch(&old->stack, &current->stack);
    }
}

A sched() la llama:

  • main(), cada vez que alguien le cede el turno, para cambiar a cualquier otra tarea
  • contador(), tras cada incremento, para ceder el turno a otros contadores

La función swtch() (no implementada) recibe dos punteros a stack como argumentos: el de la tarea anterior (la que recién había llamado a sched()), y la siguiente tarea. Su labor se divide en dos mitades simétricas:

  1. Primero, almacena en el stack de la tarea antigua todo su estado, incluyendo los registros (pusha) y EFLAGS (pushfl).

    IMPORTANTE: Una vez hecho eso, actualiza el puntero con la nueva ubicación del stack (ya que, al hacer varios push, quedó modificada).

    Ese es el único registro que queda en las estructuras del scheduler de dónde quedó guardado el estado de la tarea suspendida.

  2. A continuación, se fija en el segundo stack, que ha surgido de dos lugares posibles:

    • si la tarea ya estuvo en ejecución anteriormente, el stack proviene de una llamada previa a swtch(); en ese caso, tan solo debe hacer el trabajo inverso al paso 1.

    • si la tarea se ejecuta por primera vez, su stack fue configurado desde task_spawn()—quien debería dejarla en un formato 100% compatible con el paso 1 de swtch().

    En otras palabras, swtch() no llega a saber si la tarea se ejecuta por primera vez, o ya cambió de contexto previamente.

Ejercicios

El código proporcionado tiene un número de omisiones y deficiencias. Los siguientes ejercicios componen una guía para subsanarlas. El código debe entregarse: bien como diff respecto al repositorio original; bien impreso, marcando claramente las partes cambiadas.

En este lab, en particular, las respuestas en prosa a las preguntas de cada ejercicio son tanto o más importantes que el código: se debe explicar qué deficiencia se arregla, por qué sucedía, y cómo ayuda el nuevo código. En caso de no poder solucionar un ejercicio, es suficiente con explicar el razonamiento seguido, y hasta dónde funcionó y no funcionó.

swtch

Al arrancar el código base con ‘make qemu’3, no ocurre nada: las tareas están preparadas, pero no llegan ejecutarse. Falta la implementación de swtch() para que la idle task pueda cambiar a alguno de los contadores.

  1. Explicar el propósito de la siguiente línea de código en task_spawn():

    1

     void *stack = stack_alloc(STACK_SIZE) - sizeof(struct TaskData);

  2. Implementar la funcion swtch() en el archivo swtch.S. A esta función se la llama con las direcciones de los punteros a stack como parámetros:

  3. Responder: ¿Cómo se debería cambiar la implementación de swtch() si se eliminara de TaskData el elemento reg_ebp?

sched

Al ejecutarse los contadores ¿cuántos aparecen? ¿Cuáles? Si no aparecen tres, explicar qué está sucediendo, y aplicar una solución en la función correspondiente.

ticks

¿Cómo está configurado el delay de los timers? ¿Se están respetando las velocidades?

Si las velocidades son incorrectas, explicar por qué está sucediendo, y cómo se podría arreglar en esta implementación (scheduling cooperativo) frente a otras implementaciones (scheduling con desalojo).

Implementar una solución, simulando la noción de quantum (ARP §7.7) de un scheduler round-robin. (Como quantum, se puede usar la constante TICKS.)

exit

Cambiar el ciclo de la función contador() para que ejecute un número constante de iteraciones (por ejemplo 500). ¿Qué ocurre según van terminando las tareas?

Implementar la función task_exit() e invocarla en contador() tras finalizar el ciclo principal. ¿Es suficiente para arreglar el problema? Si no: ¿qué más se debió arreglar?

term

Eliminar la llamada a task_exit() del contador. Explicar cómo se podría invocar automáticamente al terminarse la tarea, y mostrar una implementación (probablemente modificando task_spawn() y el struct TaskData).

halt

¿Cuánta CPU consume QEMU una vez terminan todas las tareas? Si la idle task quisiera invocar la instrucción hlt cuando no hay más tareas activas ¿dónde y cómo se debería hacer? Implementar.

idle

Evitar que la tarea idle se ejecute mientras haya otras tareas en el sistema. ¿Qué ocurre en este caso cuando termina la última tarea?

  1. Ya que comparten un mismo espacio de direcciones. ↩︎

  2. Tanto JOS como xv6 usan el stack del kernel para guardar esta información. Como el proceso de usuario puede cambiar %esp con libertad, usar ese stack directamente sería un alto vector de ataque. ↩︎

  3. El Makefile también incluye reglas para gdb y qemu-gdb. ↩︎