P2 — Planificador por lotería en xv6-riscv

Publicación: semana 5 · Entrega: semana 8 · Reglas generales de entrega y revisión: projects/README.md.

En este proyecto van a reemplazar el planificador (scheduler) de xv6 por un planificador por lotería (lottery scheduling). La idea viene del capítulo 9 de OSTEP: cada proceso tiene un número de tickets y, en cada quantum, se sortea un ticket ganador; el owner de ese ticket es el que corre. Un proceso con el doble de tickets que otro debería recibir, en promedio, el doble de CPU.

El enunciado es una adaptación a xv6-riscv del proyecto scheduling-xv6-lottery de OSTEP, que fue escrito para la versión x86 de xv6. Las ideas son las mismas; cambian los nombres de algunos archivos y funciones.

Objetivos

• Leer y entender un planificador real: scheduler(), sched(), yield() y el cambio de contexto (context switch) en xv6-riscv.
• Agregar llamadas al sistema (system calls) que reciben y devuelven datos entre el espacio de usuario y el kernel de forma segura.
• Cambiar la política del planificador respetando la disciplina de locks del kernel.
• Comprobar con un experimento y un gráfico que la CPU se reparte en proporción a los tickets.

Versión de xv6

Todos trabajan sobre la misma versión de xv6-riscv, dentro del contenedor del curso (env/run.sh):

git clone https://github.com/mit-pdos/xv6-riscv
cd xv6-riscv
git checkout -b p2 e93dabeb98431235c6e1a101cb96c73c923fdbc4
git config user.name "Nombre Apellido"     # una sola vez por repositorio
git config user.email "correo@uni.pe"
make qemu                      # salir con Ctrl-a x

El contenedor se borra al salir, así que no guarda una configuración global de git; git config sin --global la guarda dentro del repositorio (.git/config), que sí persiste.

En esta versión algunas funciones del kernel tienen nombres distintos a los de libros y tutoriales antiguos: kfork(), kexit() y kwait() (en vez de fork(), exit() y wait() dentro del kernel), printk() para imprimir desde el kernel y pause(n) como la llamada de usuario que duerme n ticks (antes sleep).

Contexto: cómo planifica xv6-riscv

Procesos

Cada proceso es una struct proc (kernel/proc.h). Los campos que más importan aquí:

• state: UNUSED, USED, SLEEPING, RUNNABLE, RUNNING o ZOMBIE.
• pid, name, trapframe (registros de usuario guardados) y context (registros del kernel que guarda swtch()).
• lock: un spinlock por proceso. Hay que tenerlo tomado para leer o escribir state y los demás campos marcados en el comentario de struct proc.

La tabla de procesos es el arreglo proc[NPROC] en kernel/proc.c (NPROC = 64, en kernel/param.h). allocproc() busca una entrada UNUSED y la inicializa; freeproc() la libera. kfork() crea el hijo con allocproc() (que devuelve la entrada con su lock tomado), copia la memoria y los registros del padre y lo deja RUNNABLE.

El planificador

Cada CPU, al terminar de arrancar, entra a scheduler() (kernel/proc.c) y nunca sale. La versión original es round-robin: recorre la tabla, y para cada proceso RUNNABLE toma su lock, lo marca RUNNING y llama a swtch(&c->context, &p->context). El proceso corre hasta que vuelve al planificador mediante sched(), que hace el swtch inverso. Noten que el lock del proceso sigue tomado a través del swtch: lo suelta el propio proceso (en forkret() o al volver de sched()), y lo vuelve a tomar antes de regresar al planificador.

Interrupciones del temporizador

La CPU vuelve al planificador por dos motivos: el proceso se bloquea (por ejemplo en sleep() esperando un disco o un pipe) o llega una interrupción (interrupt) del temporizador.

• timerinit() en kernel/start.c pide la primera interrupción.
• Cada interrupción llega a devintr() en kernel/trap.c, que llama a clockintr(). Esta incrementa el contador global ticks (solo la CPU 0) y programa la siguiente interrupción 1000000 ciclos después: en QEMU eso es un tick cada 0.1 s aproximadamente.
• devintr() devuelve 2 para el temporizador, y entonces usertrap() (si el proceso estaba en modo usuario) o kerneltrap() (si estaba en el kernel) llaman a yield(). yield() marca al proceso RUNNABLE y llama a sched().

Es decir: el quantum de xv6 es un tick. Un proceso que solo usa CPU vuelve al planificador una vez por tick, y en ese momento se sortea quién corre después.

Cómo se agrega una llamada al sistema

Ya lo practicaron en la semana 4 con getreadcount(). El recorrido de una llamada es:

1. El programa llama, por ejemplo, a settickets(10). El stub generado por user/usys.pl pone el número de la llamada en el registro a7 y ejecuta ecall.
2. El hardware salta a uservec (kernel/trampoline.S), que guarda los registros en p->trapframe y llama a usertrap() (kernel/trap.c).
3. usertrap() ve que la causa es una llamada al sistema y llama a syscall() (kernel/syscall.c), que lee p->trapframe->a7, busca la función en el arreglo syscalls[] y guarda el valor de retorno en p->trapframe->a0.

Para una llamada nueva hay que tocar:

Los argumentos se leen con argint() y argaddr() (kernel/syscall.c). Para escribir en memoria de usuario se usa siempre copyout() (kernel/vm.c), que verifica que la dirección pertenezca al proceso y sea escribible; nunca se escribe directamente en un puntero que viene de usuario.

Requisitos

1. int settickets(int number)

Fija el número de tickets del proceso que la llama.

• Devuelve 0 si tuvo éxito.
• Si number < 1, devuelve -1 y no cambia los tickets.
• No se exige un máximo. Los tests usan hasta 1000 tickets por proceso.

2. int getpinfo(struct pstat *ps)

Llena *ps con información de todas las entradas de la tabla de procesos.

• Devuelve 0 si tuvo éxito, y -1 si el puntero es nulo o inválido (fuera de la memoria del proceso, o en una página de solo lectura).
• La entrada i de cada arreglo corresponde a proc[i].

La estructura se define en kernel/pstat.h. Usen exactamente el archivo provisto (pstat.h): los tests dependen de su forma y el script de pruebas lo sobrescribe con esta versión.

struct pstat {
  int inuse[NPROC];   // 1 si esa entrada de la tabla de procesos está en uso, 0 si no
  int tickets[NPROC]; // número de tickets del proceso
  int pid[NPROC];     // PID del proceso
  int ticks[NPROC];   // veces que el planificador eligió al proceso
};

• inuse[i] es 1 si proc[i].state != UNUSED.
• ticks[i] cuenta cuántas veces el planificador eligió a ese proceso para correr (se incrementa en scheduler() justo al elegirlo). Para un proceso que solo usa CPU, esto coincide con los ticks del reloj que estuvo corriendo.
• En user/user.h basta una declaración adelantada: struct pstat; y el prototipo int getpinfo(struct pstat *);. Los programas de usuario incluyen kernel/types.h, kernel/param.h, kernel/pstat.h y user/user.h, en ese orden.

3. Tickets por defecto y herencia

• Todo proceso empieza con 1 ticket y 0 ticks. Esto incluye al primer proceso (userinit()), así que init y sh tienen 1 ticket.
• Con fork(), el hijo hereda los tickets del padre (si el padre tiene 10, el hijo nace con 10). Sus ticks empiezan en 0.

4. Planificador por lotería

Reemplacen el recorrido round-robin de scheduler() por un sorteo:

1. Sumar los tickets de todos los procesos RUNNABLE.
2. Si la suma es 0, no hay nada que correr: hacer lo mismo que el código original (wfi) y volver a empezar.
3. Elegir un número ganador al azar entre 0 y total - 1.
4. Recorrer la tabla acumulando los tickets de los procesos RUNNABLE; el primero en el que la suma acumulada supere a ganador es el elegido.
5. Correrlo igual que el código original (RUNNING, c->proc, swtch) e incrementar su contador de ticks.
6. Cuando el proceso devuelva la CPU, volver a sortear desde el paso 1. No sigan recorriendo la tabla desde donde estaban: eso vuelve a ser round-robin.

Disciplina de locks. El planificador corre a la vez en todas las CPUs, y mientras suma tickets otros procesos pueden despertar, terminar o ser elegidos por otra CPU.

• Lean p->state y p->tickets solo con p->lock tomado, y suéltenlo antes de pasar al siguiente proceso. No intenten tomar los 64 locks a la vez.
• Al elegido, mantengan el lock tomado a través del swtch, como el original.
• Entre el paso 1 y el paso 4 la tabla puede cambiar. Si al recorrerla ningún proceso alcanza al ganador, simplemente vuelvan a empezar. Usen un uint64 para la suma de tickets.
• En getpinfo(), copien primero los datos a una struct pstat local (en la pila del kernel; ocupa 1 KB) tomando y soltando el lock de cada proceso, y recién al final llamen a copyout(), sin ningún spinlock tomado.
• settickets() modifica el proceso actual; tomen p->lock al escribir p->tickets, porque el planificador de otra CPU puede estar leyéndolo.

5. Números aleatorios en el kernel

xv6 no trae un generador de números aleatorios. Basta uno pseudoaleatorio sencillo, por ejemplo xorshift32:

static uint32 rand_state = 2463534242; // cualquier semilla distinta de 0

static uint32
rand(void)
{
  uint32 x = rand_state;
  x ^= x << 13;
  x ^= x >> 17;
  x ^= x << 5;
  rand_state = x;
  return x;
}

Otra opción es un generador lineal congruencial (LCG): state = state * 1103515245 + 12345, usando los bits altos del resultado.

El estado rand_state es compartido por todas las CPUs. Protéjanlo con un spinlock propio (inicializado con initlock() en procinit()), o usen un estado por CPU dentro de struct cpu. rand() % total tiene un sesgo mínimo que aquí no importa.

6. Varias CPUs

El código debe funcionar sin errores con cualquier número de CPUs (make qemu usa 3 por defecto). Pero la proporción 3:2:1 solo se ve con una CPU: con tres CPUs y tres procesos ocupados, cada uno tiene una CPU para él solo. Por eso las mediciones se hacen con make qemu CPUS=1.

Archivos provistos

En esta carpeta:

Para agregar los programas a xv6, desde la raíz de su árbol de xv6-riscv (CURSO es la carpeta de este repositorio):

cp CURSO/projects/p2-lottery/pstat.h kernel/pstat.h
cp CURSO/projects/p2-lottery/tickettest.c CURSO/projects/p2-lottery/lotterytest.c user/

y en el Makefile, dentro de la lista UPROGS, agreguen dos líneas:

UPROGS=\
	$U/_cat\
	...
	$U/_sync\
	$U/_tickettest\
	$U/_lotterytest\

Luego make qemu CPUS=1 y, en la shell de xv6:

$ tickettest
tickettest: getpinfo devuelve 0: ok
...
tickettest: OK
tickettest: done
$ lotterytest
lotterytest: ventana 300 ticks, tickets 30:20:10
lotterytest: serie 20 12 6 2
lotterytest: serie 40 22 13 5
...
lotterytest: serie 300 157 103 41
lotterytest: tickets 30 ticks 157
lotterytest: tickets 20 ticks 103
lotterytest: tickets 10 ticks 41
lotterytest: total 301
lotterytest: esperado (por mil) 500 333 166
lotterytest: obtenido (por mil) 521 342 136
lotterytest: done

lotterytest tarda unos 30 segundos. Acepta dos argumentos opcionales: lotterytest [ventana] [paso], la duración de la medición en ticks (300 por defecto) y cada cuántos ticks imprimir una línea serie (20 por defecto). Cada línea serie t a b c dice cuántas veces fue elegido cada hijo desde el inicio de la medición hasta el tick t. Con esas líneas hacen el gráfico.

Cómo se evalúa

Pruebas públicas

CURSO/projects/p2-lottery/test-p2.sh ruta/a/su/xv6-riscv

Se puede correr desde la computadora (si no encuentra QEMU, se vuelve a lanzar solo dentro del contenedor sistemas-operativos) o desde dentro del contenedor. Trabaja sobre una copia temporal, así que no modifica su árbol. El script:

1. Copia pstat.h, tickettest.c y lotterytest.c, y los agrega a UPROGS si hace falta.
2. Compila. El Makefile de xv6 usa -Werror: cualquier warning es un error.
3. Arranca xv6 sin interfaz gráfica con CPUS=1 y corre tickettest. Cada línea ok o FAIL cuenta como una prueba.
4. Corre lotterytest 300 y verifica que:
   • los hijos acumulen al menos 150 ticks en total;
   • la fracción de CPU de cada hijo esté a ±0.100 de lo esperado (0.500, 0.333 y 0.167);
   • el de 30 tickets reciba más CPU que el de 20, y este más que el de 10.

Con 300 ticks, un planificador correcto falla la prueba de proporción por mala suerte en menos de 2 de cada 1000 corridas. Si les falla por poco, vuelvan a correrla; si falla siempre, hay un error.

Con USERTESTS=1 el script además corre usertests -q, que tarda unos minutos. Su planificador no debe romper ninguna prueba de xv6.

Pruebas privadas y revisión

Habrá pruebas privadas: otras proporciones de tickets, más procesos, procesos que duermen y despiertan, y usertests -q con varias CPUs. Además se revisa el código (en especial el manejo de locks y de punteros de usuario), el README.md y el gráfico. Puede haber una defensa oral breve en el laboratorio.

Qué entregar

En la semana 8 se entregan:

1. El código. Hagan commits en su rama p2 y generen el parche contra la versión base:

   git add -A
   git commit -m "Planificador por loteria"
   git diff e93dabeb98431235c6e1a101cb96c73c923fdbc4 HEAD > p2.patch

   El parche debe aplicarse limpio con git apply sobre esa versión y debe incluir kernel/pstat.h, los dos programas de prueba y los cambios en el Makefile.

2. README.md: integrantes, qué funciona y qué no, y una explicación corta de su diseño: dónde guardan los tickets, cómo hacen el sorteo y qué locks toman en scheduler(), settickets() y getpinfo().

3. El gráfico (PNG o PDF): ticks acumulados de cada uno de los tres hijos en función del tiempo, a partir de las líneas serie de lotterytest, con dos o tres líneas de interpretación. Pueden hacerlo con Python, una hoja de cálculo o gnuplot fuera de xv6.

Calentamiento con gdb

Antes de tocar el planificador, sigan una llamada al sistema con gdb. Dentro del contenedor abran dos terminales; lo más simple es tmux (Ctrl-b % divide la pantalla, Ctrl-b o cambia de panel).

Terminal 1:

make qemu-gdb CPUS=1

QEMU se queda detenido esperando al depurador. Terminal 2, en la misma carpeta:

gdb-multiarch

El archivo .gdbinit que genera el Makefile conecta gdb a QEMU y carga los símbolos de kernel/kernel. Luego:

(gdb) break syscall
(gdb) continue
(gdb) bt
(gdb) next
(gdb) next
(gdb) next
(gdb) p num
(gdb) p p->trapframe->a7
(gdb) p p->name
(gdb) p p->pid

• bt muestra que syscall() fue llamada por usertrap().
• La primera llamada al sistema la hace init (pid 1), y es la número 15 (SYS_open en kernel/syscall.h): init abre la consola.
• El kernel se compila con -O, así que en la primera línea de syscall() gdb puede decir <optimized out> para p o num. Avancen con next hasta pasar num = p->trapframe->a7;, o usen p myproc()->trapframe->a7, que funciona en cualquier momento.

Para detenerse solo en su llamada nueva (usen el número que le asignaron a SYS_settickets):

(gdb) delete
(gdb) break syscall if myproc()->trapframe->a7 == 23
(gdb) continue

y en la terminal 1 ejecuten tickettest. Con finish vuelven a usertrap() y con p myproc()->trapframe->a0 ven el valor que recibirá el programa.

Preguntas para el calentamiento (no se entregan, pero pueden salir en la defensa oral):

1. ¿Qué otras llamadas al sistema hace init antes de lanzar la shell, y en qué orden?
2. ¿Por qué syscall() puede leer los argumentos desde p->trapframe y no de los registros de la CPU?
3. Pongan un breakpoint en yield y continúen: ¿desde dónde se llama cuando ningún programa hace llamadas al sistema?