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.
To start the lab, update your repository and create a new branch for your solution:
$ git fetch origin
$ git checkout -b uthread origin/xv6-19auIt’s important to understand a bit of RISC-V assembly.
There is a file user/call.c in the repo; make fs.img
builds a user program call and a readable assembly a version of the
program in the file user/call.asm.
Read through user/call.asm and understand it. Refer to the
RISC-V instruction manual if needed.
Below are some questions to help you understand RISC-V. You don’t need to submit answers to the questions in this lab. Do answer them for yourself though!
Which registers contain arguments to functions?
For example, which register holds 13 in main’s call to printf?
Where is the function call to f from main? Where is the call to g?
(Hint: the compiler may inline functions.)
At what address is the function printf located?
What value is in the register ra just after the jalr to printf in main?
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 should complete thread_create to create a properly initialized
thread so that when the scheduler switches to that thread for the
first time, thread_switch returns to the function func, running on
the thread’s stack. You will have to decide where to save/restore
registers. Several solutions are possible. You are allowed to modify
struct thread. 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 the
next_thread.
Some hints:
thread_switch needs to save/restore only the callee-save registers. Why?
You can add fields to struct thread into which to save registers.
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:60This 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_threadWith “x”, you can examine the content of a memory location:
(gdb) x/x next_thread->stackYou can single step assembly instructions using:
(gdb) siRefer to the on-line documentation for gdb if needed.
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.