TP2: Scheduling, interrupciones y threads

Índice

• Introducción
• Esqueleto
  • Integración
  • Compilación
  • Ejecución
  • Depurado
    • Depurado de una triple fault
• Uso de IA
• Implementación
  • Parte 1: Cambio de contexto
    • De modo kernel a modo usuario
    • De modo usuario a modo kernel
  • Parte 2: Scheduler round robin preemptivo con timer
    • El timer como mecanismo de preemption
    • Round robin
    • Syscall sys_sleep
    • Estadísticas
  • Parte 3: Scheduler con prioridades y aging
    • Motivación
    • Prioridades en el struct Env
    • Política de scheduling
    • Syscalls de prioridad
    • Prioridad inicial y herencia en fork
    • Estadísticas
  • Parte 4: Threads en espacio de usuario
    • Procesos vs threads
    • Modelo de implementación
    • Syscall sys_thread_create
    • Librería de usuario
    • Consideraciones
• Bibliografía útil

Introducción

AVISO: antes de comenzar, verificar que se tiene instalado el software necesario.

En este trabajo se extenderá un sistema operativo preexistente para explorar tres grandes áreas del diseño de un sistema operativo moderno: el mecanismo de cambio de contexto, el scheduling (i.e. planificación) dirigido por hardware, y el soporte para múltiples hilos de ejecución (threads). El kernel a utilizar será una modificación de JOS, un exokernel educativo con licencia libre del grupo de Sistemas Operativos Distribuidos del MIT.

JOS está diseñado para correr en la arquitectura Intel x86, y para poder ejecutarlo utilizaremos QEMU que emula dicha arquitectura.

AVISO: las diapositivas están en sched

Esqueleto

AVISO: El esqueleto se encuentra disponible en fisop/sched.

IMPORTANTE: leer el archivo sched/README.md que se encuentra en la raíz del proyecto. Contiene información sobre cómo realizar la compilación de los archivos, y cómo ejecutar el formateo de código.

Integración

Suponiendo que ya se clonó el repositorio privado en algún directorio:

1
2
git clone git@github.com:fiubatps/sisop_<año_cuatrimestre>_g1 tps
cd tps

Para integrar el esqueleto de la cátedra, hacer:

• asegurarse de estar en la rama main

  1
  git checkout main
  

• agregar remoto de la cátedra

  1
  git remote add sched git@github.com:fisop/sched.git
  

• creación de la rama base

  1
  2
  git checkout -b base_sched
  git push -u origin base_sched
  

• merge del esqueleto

  1
  2
  3
  git fetch --all
  git merge sched/main --allow-unrelated-histories
  git push origin base_sched
  

• creación de la rama entrega

  1
  2
  git checkout -b entrega_sched
  git push -u origin entrega_sched
  

IMPORTANTE: asegurarse de siempre commitear en la rama entrega_sched.

Compilación

La compilación se realiza mediante make. En el directorio obj/kern se puede encontrar:

• kernel — el binario ELF con el kernel
• kernel.asm — assembler asociado al binario

La política de scheduling se elige al compilar:

• USE_RR=1 — scheduler round robin (Partes 1 y 2)
• USE_PR=1 — scheduler con prioridades (Parte 3)

Por ejemplo:

1
2
make qemu USE_RR=1
make qemu USE_PR=1

Ejecución

Para correr JOS, se puede usar make qemu o make qemu-nox.

Para ejecutar un proceso de usuario en particular dentro del kernel, se puede usar make run-<proceso> o make run-<proceso>-nox. Como ejemplo, make run-hello-nox correrá el proceso de usuario user/hello.c.

Los programas de usuario que se ejecutan al arrancar el kernel se eligen con ENV_CREATE(user_<nombre>, ENV_TYPE_USER) en kern/init.c. Cualquier programa nuevo en user/ tiene que agregarse además a KERN_BINFILES en kern/Makefrag para que se compile y quede embebido en el kernel. Los tests user/sleeptest.c, user/priotest.c y user/threadtest.c ya están declarados ahí.

Las pruebas automáticas se corren con:

1
2
make grade USE_RR=1
make grade USE_PR=1

El entorno de desarrollo se puede levantar con Docker:

1
2
./dock build   # construir la imagen
./dock run     # entrar al container, con el repo montado en /sched

Depurado

El Makefile de JOS incluye dos reglas para correr QEMU junto con GDB.

En una terminal ejecutar:

1
2
3
4
5
$ make qemu-gdb USE_RR=1
***
*** Now run 'make gdb'.
***
qemu-system-i386 ...

y en otra distinta:

1
2
3
4
5
6
$ make gdb
gdb -q -ex 'target remote ...' -n -x .gdbinit
Reading symbols from obj/kern/kernel...done.
Remote debugging using 127.0.0.1:...
0x0000fff0 in ?? ()
(gdb)

Depurado de una triple fault

En la arquitectura x86, el sistema se reinicia automáticamente cuando ocurre una “triple falla” (triple fault). QEMU, por omisión, obedece esta especificación.

Sin embargo, durante el desarrollo de sistemas operativos en modo protegido de x86, las triple fault ocurren casi exclusivamente por un bug en el kernel. Por esto, es más deseable que QEMU detenga la ejecución en lugar de reiniciarse constantemente.

QEMU no ofrece soporte directo para detectar fallas triples y detener la ejecución, pero existen un set de opciones que se acercan bastante a ese propósito.

Por tanto, si en una determinada versión del desarrollo ocurre que QEMU se reinicia constantemente, se recomienda probar lo siguiente:

• correr QEMU con las opciones: -no-reboot -no-shutdown -d cpu_reset (estas opciones pueden añadirse en la variable QEMUOPTS en el archivo GNUmakefile)

• si el error realmente fue un Triple fault, se mostrará ese error en la última línea del archivo qemu.log, y se podrá consultar el estado de los registros mediante el monitor de QEMU (Ctrl-A C → info registers)

Uso de IA

IMPORTANTE: es requisito mencionar cómo utilizaron herramientas de IA en la implementación. Dicha mención no debe estar realizada con IA.

Implementación

La implementación del TP se dividirá en cuatro partes, de dificultad creciente.

1. Implementación del cambio de contexto ¹
2. Implementación de un scheduler round robin preemptive con timer.
3. Implementación de un scheduler con prioridades y aging.
4. Implementación de threads en espacio de usuario.

IMPORTANTE: las partes 1 y 2 deben completarse en ese orden antes de seguir con 3 y 4.

Parte 1: Cambio de contexto

JOS mantiene un arreglo en memoria como PCB (Process Control Block), aunque llama environment a los procesos. De aquí en más se usarán las palabras proceso y environment como sinónimos siempre que hablemos en el contexto de JOS.

Las funciones que se encargan de alocar espacio para un proceso nuevo, crear su espacio de direcciones virtuales y cargar el código en memoria ya se encuentran implementadas, como se puede ver en el archivo kern/env.c.

Entre tales funciones se encuentran:

• env_alloc: que reserva el espacio en el PCB para un proceso nuevo, y le inicializa algunos parámetros
• env_setup_vm: que inicializa el espacio de direcciones virtuales (i.e. el page directory) del proceso
• load_icode: que carga el código del proceso a partir del binario compilado
• env_destroy y env_free: para eliminar a un proceso una vez que termina

No las modificaremos en esta parte, pero es importante entender dónde y cómo son llamadas para comprender el flujo de vida de un proceso en JOS. En la Parte 3 se pedirán cambios puntuales en env_alloc y en la Parte 4 en env_free.

La definición de un environment puede encontrarse en inc/env.h y contiene, entre otras cosas, los campos necesarios para realizar el cambio de contexto. A continuación algunos de los campos del mismo struct.

1
2
3
4
5
6
7
8
9
10
11
12
struct Env {
	struct Trapframe env_tf;	// Saved registers
	struct Env *env_link;		// Next free Env
	envid_t env_id;			// Unique environment identifier
	envid_t env_parent_id;		// env_id of this env's parent
	enum EnvType env_type;		// Indicates special system environments
	unsigned env_status;		// Status of the environment
	uint32_t env_runs;		// Number of times environment has run
	int env_cpunum;			// The CPU that the env is running on
	pde_t *env_pgdir;		// Kernel virtual address of page dir
  [...]
}

Los más importantes del struct son: env_id, que identifica al environment; env_pgdir, que contiene su page directory (i.e. su espacio de direcciones virtuales a través de la tabla de paginación inicial) y env_tf, que mantiene el estado de todos los registros para ese environment.

De modo kernel a modo usuario

A partir de esa información, el kernel podrá ejecutar cualquier proceso. La función que se encarga de tomar un proceso y ejecutarlo es env_run, en kern/env.c. Como parámetro, esta función acepta un struct Env * y deberá realizar lo siguiente:

1. Actualizar la variable global curenv del kernel, con el nuevo proceso a ser ejecutado
2. Modificar el estado del environment env_status para indicar que está siendo ejecutado. La lista de estados puede verse en un enum dentro de inc/env.h.
3. Realizar el cambio de contexto.
   1. Cargar la tabla de paginación del environment con env_load_pgdir (función ya implementada)
   2. Llamar a la función context_switch para restaurar el estado de CPU

Será la función context_switch (en kern/switch.S) la que restaure completamente el estado del environment a correr, y que realice el cambio de contexto a modo usuario. Es decir, esta función no hace return jamás, y como resultado de la misma la CPU pasará a ejecutar código de usuario en ring 3.

Para ello, se utilizará la ayuda del hardware, mediante la instrucción iret (“interrupt return”). Dicha instrucción permite modificar conjuntamente los registros cs, eip y esp de forma atómica, tomando valores desde el stack. El formato que requiere del stack para ser invocada es específico a la arquitectura x86.

Cabe notar que el resto de los registros definidos en struct Trapframe deben ser restaurados previamente, dado que iret no los modifica.

De modo usuario a modo kernel

El cambio de contexto descrito anteriormente nos permite realizar el pasaje de modo kernel a modo usuario (es decir, de ring 0 a ring 3). Sin embargo, dicho mecanismo no puede utilizarse para volver a modo kernel, dado que requiere de la instrucción privilegiada iret.

Para volver al modo kernel, se utilizan interrupciones. Las interrupciones son eventos generados por hardware que interrumpen al CPU en su ciclo de instrucciones y trasladan la ejecución de una forma controlada a otro contexto, permitiendo cambiar registros importantes (eip, cs, esp, etc.) a valores fijos definidos previamente.

El kernel configura las interrupciones en kern/trap.c, mediante la función trap_init. Ahí se genera la tabla de interrupciones (la IDT) con referencias a los handlers de cada tipo de interrupción.

Un tipo de interrupción común es la syscall. Todas las syscalls pasarán por esta única interrupción, y desembocarán en la función syscall del lado del kernel que se encargará de determinar qué syscall se necesita ejecutar y llamar a la función sys_* adecuada. En kern/syscall.c.

Así, un handler para la interrupción de las syscalls se define de la siguiente forma:

1
SETGATE(idt[T_SYSCALL], 0, GD_KT, &trap48, 3);

Los detalles de la macro SETGATE no son importantes, pero mediante los parámetros se está indicando al CPU que siempre que se genere la interrupción número 48 (la que corresponde a las syscalls, dado que T_SYSCALL=48), esperamos que se llame a la función trap48, que se corresponde al handler de la interrupción de ese número.

Mediante el resto de los parámetros, específicamente GD_KT (Global Descriptor, Kernel Text) se está indicando al CPU que siempre que se llame a ese handler, se deberá hacerlo en el ring 0. La función trap48 está definida, de forma auto-generada vía macros, en kern/trapentry.S.

Como es el kernel quien define la tabla de interrupciones, y se coloca a si mismo como punto de entrada luego de cualquier interrupción, dicha entrada al kernel está controlada y el paso de ring 3 a ring 0 es seguro.

Observando kern/trapentry.S todos los handlers están generados usando las macros TRAPHANDLER y TRAPHANDLER_NOEC, y todos desembocan en la función _alltraps, que está incompleta y deberán implementar.

Con ambas tareas implementadas, la ejecución de cualquier proceso debería poder llegar a su fin. Sin embargo, solo podemos ejecutar un proceso a la vez dado que no hay scheduler implementado.

Parte 2: Scheduler round robin preemptivo con timer

Ejecutar: make qemu USE_RR=1 para compilar y correr, y make grade USE_RR=1 para correr las pruebas

Los tests automáticos validan el scheduler base: que los procesos alternen, no se pisen y terminen. El resto de esta parte (sys_sleep y las estadísticas) se valida a mano con user/sleeptest.c y con la salida del kernel.

El timer como mecanismo de preemption

En la Parte 1, el kernel solo recupera el control cuando el proceso hace una syscall voluntariamente. Un scheduler real también debe poder interrumpir un proceso que no cede la CPU.

JOS ya tiene configurado el LAPIC timer para generar interrupciones periódicas (IRQ_TIMER). Al producirse, trap_dispatch en kern/trap.c llama a lapic_eoi() para confirmar la interrupción y luego a sched_yield(). Con ésto, el scheduler puede reemplazar al proceso actual aunque éste no haya llamado a sys_yield.

Existe un contador global ticks, definido en kern/trap.c y declarado en kern/trap.h, que debe incrementarse en cada interrupción de timer. Este contador permite medir el tiempo transcurrido desde el arranque del kernel.

Round robin

El esqueleto tiene preparado ya todo lo necesario para el scheduler, en kern/sched.c. La función sched_yield es la que se invoca cada vez que se necesita elegir el próximo proceso a ejecutar, y es aquí donde la política de scheduling deberá ser implementada.

Notar que sched_yield tiene dos posibles salidas: se elige y ejecuta un proceso llamando a env_run, o bien no hay más procesos que ejecutar y se desemboca en sched_halt, donde efectivamente el kernel queda en estado idle.

Con round robin:

• Se recorre la lista de environments de forma completa, empezando justo después del último proceso ejecutado.
• Se elige el primero que esté listo para ejecutarse.
• Si no hay ninguno y el proceso que se estaba ejecutando sigue en ejecución, se lo puede volver a elegir.
• Si no hay nada que ejecutar, el kernel queda en estado idle.

Syscall sys_sleep

Implementar la syscall SYS_sleep (stub en kern/syscall.c). El wrapper de usuario en lib/syscall.c y su prototipo en inc/lib.h ya están provistos.

1
int sys_sleep(uint32_t n);

La syscall:

• marca al proceso para que no sea ejecutable
• guarda el momento a partir del cual tiene que despertar
• debe retornar un valor

Considerar que en cada interrupción del timer se debe actualizar el contador global y revisar si hay procesos que deban ser despertados.

NOTA: tener en cuenta que la syscall en sí no retorna, pero igualmente debe devolver un valor de retorno.

IMPORTANTE: atención al efecto que tiene sleep sobre el final de la ejecución. Un proceso dormido no es ejecutable: ¿qué ocurre si todos los procesos duermen al mismo tiempo? ¿Cómo se distingue “no hay nada que ejecutar por ahora, pero el timer va a despertar a alguien” de “ya no queda ningún proceso vivo”?

Estadísticas

Al finalizar todos los procesos (en sched_halt), imprimir al menos:

• Número total de llamadas al scheduler.
• Número de veces que cada proceso fue ejecutado.
• Tiempo total de ejecución en ticks.

Parte 3: Scheduler con prioridades y aging

Ejecutar: make qemu USE_PR=1 para compilar y correr, y make grade USE_PR=1 para correr las pruebas

Los tests automáticos validan que el scheduler siga siendo correcto con la política de prioridades activa; el comportamiento propio de las prioridades se valida con user/priotest.c y con los tests propios que se pidan más abajo.

Motivación

La política de scheduling round robin es la más sencilla y simple de implementar; y aunque es justa (le da a todos los procesos la misma proporción del CPU) puede no ser suficiente para situaciones más reales. Usualmente los procesos son distintos entre sí en cuanto a importancia y carga para el sistema. Un scheduler con prioridades permite reflejar eso.

Sin embargo, un scheduler puramente basado en prioridades puede causar starvation: los procesos de baja prioridad nunca obtienen CPU si siempre hay procesos de mayor prioridad disponibles. El mecanismo de aging mitiga esto aumentando gradualmente la prioridad efectiva de los procesos que llevan mucho tiempo esperando.

Prioridades en el struct Env

El struct Env ya tiene los campos:

1
2
uint32_t env_priority;   // prioridad del environment
uint32_t env_wait_ticks; // ticks acumulados esperando (para aging)

Política de scheduling

En lugar de recorrer los procesos en orden circular, el scheduler debe elegir el proceso listo con mayor prioridad efectiva, entendida como la prioridad base del proceso más un bonus que crece con el tiempo que lleva esperando su turno:

1
prioridad_efectiva = env_priority + aging_bonus(espera acumulada)

Syscalls de prioridad

Implementar:

1
2
int sys_getpriority(envid_t envid);
int sys_setpriority(envid_t envid, uint32_t priority);

Reglas de seguridad:

• Un proceso no puede aumentar su propia prioridad.
• Un proceso puede reducir su propia prioridad.
• Un proceso puede modificar la prioridad de sus hijos directos (con cualquier valor).
• sys_setpriority con envid == 0 refiere al proceso actual.

Como sys_getpriority usa su valor de retorno tanto para la prioridad como para los códigos de error (negativos), el rango de prioridades válidas debe ser acotado y no negativo. Definir ese rango y documentarlo en el informe; también hace falta para la estadística de distribución de CPU por prioridad.

Prioridad inicial y herencia en fork

• Todo proceso nuevo debe recibir una prioridad por defecto al crearse (modificar env_alloc o env_create).
• Cuando un proceso hace fork, el hijo hereda la prioridad del padre (o una fracción de ella, a criterio del equipo — justificar en el informe).

Estadísticas

Además de las de la Parte 2, agregar:

• Historial de los últimos N procesos ejecutados (proceso + tick de inicio).
• Distribución de CPU por prioridad (cuántos ticks acumuló cada nivel de prioridad).

PISTA: env_priority es la prioridad base y el aging no la modifica: el bonus vive en la prioridad efectiva, que se recalcula en cada decisión. Unas estadísticas que sólo muestren env_priority se ven idénticas en una corrida donde el aging fue decisivo y en una donde nunca actuó.

Al terminar esta parte, con USE_PR=1:

• El scheduler elige por prioridad efectiva, existen sys_getpriority y sys_setpriority con las reglas de seguridad de arriba, todo proceso arranca con una prioridad por defecto y uno creado usando fork hereda la del padre.
• Las estadísticas incluyen el historial de decisiones y la distribución de CPU por prioridad.
• user/priotest.c corre y muestra que la política favorece a los procesos de alta prioridad (dejar un único ENV_CREATE(user_priotest, ENV_TYPE_USER); el binario ya está declarado). Cuidado con la expectativa: con prioridades el proceso de mayor prioridad acapara la CPU hasta terminar, así que lo que corresponde ver es a los hijos terminando en orden descendente de prioridad, y no cuatro series de líneas intercaladas de forma pareja. Correr el mismo test con USE_RR=1 da el contraste.
• Un test propio demuestra que el aging evita starvation. El escenario son dos procesos CPU-bound con prioridades distintas que nunca cedan la CPU por su cuenta (así lo único que puede sacársela es la interrupción del timer). Hay que mostrar que el proceso postergado obtiene CPU antes de que el otro termine. Los programas de usuario nuevos van en user/ y hay que agregarlos a KERN_BINFILES en kern/Makefrag.
• El mismo test, anulando el bonus de aging, muestra la starvation contra la que se compara.

Parte 4: Threads en espacio de usuario

Ejecutar: make qemu USE_RR=1 o make qemu USE_PR=1: los threads son independientes de la política de scheduling, y deben funcionar con ambas.

Procesos vs threads

Hasta ahora, cada struct Env tiene su propio page directory (env_pgdir): su espacio de direcciones es completamente separado del de otros procesos. Para comunicarse, los procesos deben usar IPC.

Un thread es una unidad de ejecución que comparte el espacio de direcciones de su proceso padre. Múltiples threads dentro del mismo proceso ven la misma memoria, lo que permite comunicación directa a través de variables compartidas. Ésto requiere coordinación (sincronización) para evitar condiciones de carrera.

Modelo de implementación

En JOS, un thread se representa como un struct Env con env_type = ENV_TYPE_THREAD cuyo env_pgdir apunta al mismo page directory que su proceso padre. El scheduler lo trata exactamente igual que a un proceso normal: tiene su propio env_tf (registros), su propia pila, y puede estar en cualquier estado (ENV_RUNNABLE, ENV_NOT_RUNNABLE, etc.).

La diferencia clave entre las syscalls que crean procesos y threads es:

• sys_exofork crea un environment con un page directory propio.
• sys_thread_create comparte el page directory del proceso creador, sin crear uno nuevo.

Syscall sys_thread_create

1
envid_t sys_thread_create(void *entry, void *ustack_top);

• Crea un nuevo struct Env con env_type = ENV_TYPE_THREAD.
• Copia env_pgdir del proceso actual al nuevo env (sin duplicar las páginas).
• Inicializa env_tf del thread para que comience a ejecutar en entry con el stack en ustack_top.
• El thread hereda el env_parent_id del proceso creador.
• Retorna el envid del nuevo thread.

Cuando el proceso padre es destruido (env_free), todos sus threads deben ser destruidos también. Modificar env_free para contemplar esto.

IMPORTANTE: antes de tocar env_free, leerla con atención: tal como está, desmapea todo el espacio de usuario del environment y libera su page directory. Aplicada sobre un thread, que comparte el env_pgdir con su proceso, destruiría la memoria del proceso y del resto de los threads. Revisar también el refcount de la página del page directory (pp_ref, ver cómo lo maneja env_setup_vm) al compartirlo entre varios environments.

Librería de usuario

El archivo lib/thread.c contiene el stub de thread_create:

1
envid_t thread_create(void (*func)(void *), void *arg);

Esta función debe:

1. Alocar páginas para el stack del nuevo thread con sys_page_alloc.
2. Preparar el stack de modo que al retornar de func se llame a exit().
3. Llamar a sys_thread_create(func, stack_top).

Se debe decidir la dirección donde alocar el stack y documentar el criterio. Tener en cuenta que la página [USTACKTOP - PGSIZE, USTACKTOP) ya está ocupada por el stack del thread principal (ver load_icode en kern/env.c), y que los stacks de los threads no deben solaparse entre sí.

Consideraciones

• ¿Qué ocurre si dos threads modifican la misma variable simultáneamente? Mostrar un ejemplo concreto de condición de carrera en el informe (aunque no es necesario implementar sincronización).
• ¿Qué pasa con el page directory cuando un thread termina pero el padre sigue vivo? ¿Y al revés?
• ¿Puede un thread hacer fork? ¿Qué heredaría el hijo?
• La variable global thisenv la inicializa libmain (y la corrige fork) para el proceso, pero un thread arranca directamente en entry y comparte esa variable con el resto del proceso. ¿Qué implica eso para un thread que quiera conocer su propio env_id? ¿Cómo lo resolvería un sistema real?

Bibliografía útil

A continuación se presentan algunos enlaces y bibliografía útiles como referencia.

• OSTEP
  • Capítulo 7: Scheduling: Introduction (PDF)
  • Capítulo 8: Scheduling: The Multi-Level Feedback Queue (PDF)
  • Capítulo 9: Scheduling: Proportional Share (PDF)
  • Capítulo 26: Concurrency: An Introduction (PDF)
• Manuales de Intel: Intel® 64 and IA-32 Architectures Software Developer’s Manual (PDF)
  • Volumen 1: Basic Architecture
    • Chapter 6 - Procedure calls, Interrupts and Exceptions (6.2, 6.4, 6.5)
    • Chapter 7 - Programming with general-purpose instructions (7.3)
  • Volumen 2: Instruction Set Reference
    • Chapter 4: Instruction Set Reference, M-U (4.3)
  • Volume 3: System Programming Guide
    • Chapter 5: Paging (5.2, 5.5, 5.7, 5.12)
    • Chapter 7: Interrupt and Exception Handling (7.1, 7.2, 7.3, 7.4, 7.10, 7.11, 7.12)