Lab uthread: User-level threads

This lab will familiarize you with how state is saved and restored in context switches. You will implement switching between threads in a user-level threads package.

Scheduling in the xv6 book

Before writing code, you should make sure you have read §7, Scheduling from the xv6 book and studied the corresponding code.

To start the lab, update your repository and create a new branch for your solution:

$ git fetch origin
$ git checkout -b uthread origin/xv6-21au
$ make clean

Uthread

In this exercise you will design the context switch mechanism for a user-level threading system, and then implement it. To get you started, your xv6 has two files user/uthread.c and user/uthread_switch.S, and a rule in the Makefile to build a uthread program. uthread.c contains most of a user-level threading package, and code for three simple test threads. The threading package is missing code to create a thread and to switch between threads.

Your job is to come up with a plan to create threads and save/restore registers to switch between threads, and implement that plan.

Once you’ve finished, you should see the following output when you run uthread on xv6 (the three threads might start in a different order):

$ make qemu
...
$ uthread
thread_a started
thread_b started
thread_c started
thread_c 0
thread_a 0
thread_b 0
thread_c 1
thread_a 1
thread_b 1
...
thread_c 99
thread_a 99
thread_b 99
thread_c: exit after 100
thread_a: exit after 100
thread_b: exit after 100
thread_schedule: no runnable threads
$

This output comes from the three test threads, each of which has a loop that prints a line and then yields the CPU to the other thread.

At this point, however, with no context switch code, you’ll see no output.

You will need to add code to thread_create() and thread_schedule() in user/uthread.c, and thread_switch in user/uthread_switch.S. One goal is ensure that when thread_schedule() runs a given thread for the first time, the thread executes the function passed to thread_create(), on its own stack. Another goal is to ensure that thread_switch saves the registers of the thread being switched away from, restores the registers of the thread being switched to, and returns to the point in the latter thread’s instructions where it last left off. You will have to decide where to save/restore registers; modifying struct thread to hold registers is a good plan. You’ll need to add a call to thread_switch in thread_schedule; you can pass whatever arguments you need to thread_switch, but the intent is to switch from thread t to next_thread.

Some hints:

thread_switch needs to save/restore only the callee-save registers. Why?
You can see the assembly code for uthread in user/uthread.asm, which may be handy for debugging.
To test your code it might be helpful to single step through your thread_switch using riscv64-unknown-elf-gdb (or riscv64-linux-gnu-gdb). You can get started in this way:

(gdb) file user/_uthread
Reading symbols from user/_uthread...
(gdb) b thread.c:60

This sets a breakpoint at a specified line in thread.c. The breakpoint may (or may not) be triggered before you even run uthread. How could that happen?

Once your xv6 shell runs, type uthread, and gdb will break at line thread_switch. Now you can type commands like the following to inspect the state of uthread:

(gdb) p/x *next_thread

With “x”, you can examine the content of a memory location:

(gdb) x/x next_thread->stack

You can skip to the start of thread_switch thus:

(gdb) b thread_switch
(gdb) c

You can single step assembly instructions using:

(gdb) si

Refer to the on-line documentation for gdb if needed.

Optional challenges

The user-level thread package interacts badly with the operating system in several ways. For example, if one user-level thread blocks in a system call, another user-level thread won’t run, because the user-level threads scheduler doesn’t know that one of its threads has been descheduled by the xv6 scheduler. As another example, two user-level threads will not run concurrently on different cores, because the xv6 scheduler isn’t aware that there are multiple threads that could run in parallel. Note that if two user-level threads were to run truly in parallel, this implementation won’t work because of several races (e.g., two threads on different processors could call thread_schedule concurrently, select the same runnable thread, and both run it on different processors.)

There are several ways of addressing these problems. One is using scheduler activations and another is to use one kernel thread per user-level thread (as the Linux kernel does). Implement one of these ways in xv6. This is not easy to get right; for example, you will need to implement TLB shootdown when updating a page table for a multithreaded user process.

Add locks, condition variables, barriers, etc. to your thread package.

This completes the lab. In the lab directory, commit your changes, type make tarball, and submit the tarball through Canvas.