CS 202: Advanced Operating Systems
University of California, Riverside
Lab #3: xv6 Threads
Due: 12/02/2022, Friday, 11:59 p.m. (Pacific time)
Overview
In this project, you will be adding kernel-level thread support to xv6. First, you will implement a new
system call to create a kernel-level thread, called clone(). Then, using the clone() system call, you will
build a simple user-level library consisting of thread_create(), lock_acquire() and
lock_release() for thread management. Finally, you will show these things work by using a user-level
multi-threaded test program.
Before your start:
1. In Makefile, set the number of CPUs to 3 (CPUS := 3). You may debug your code using one
CPU, your demo and submission should have CPUS := 3.
2. Replace kernel/trampoline.S with the one provided at the end of this document. This new
trampoline.S is also available to download from eLearn.
Background: xv6 virtual address space memory layout
In xv6, every process has its own page table that defines a virtual address space used in the user mode.
When a process enters the kernel mode, the address space is switched to the kernel’s virtual address space.
Because of this, each process has separate stacks for the kernel and user spaces (aka. user stack and kernel
stack). Also, in xv6, each PCB maintains separate objects to store process’s register values:
struct proc {
 …
struct trapframe *trapframe; // data page for trampoline.S
struct context context; // swtch() here to run process
trapframe stores registers used in the user space when entering the kernel mode. context is for registers
in the kernel space when context-switched to another process.
Below figure illustrates the layout of a process’s virtual address space in xv6-riscv.
2
In the virtual address space, user text, data, and user stack are mapped at the bottom. At top, you can see
two special pages are mapped: trampoline and trapframe, each has the size of PGSIZE (= 4096 bytes).
The trampoline page maps the code to transition in and out of the kernel. The trapframe page maps
the PCB’s trapframe object so that it is accessible by a trap handler while in the user space (see Chapter
4 of the xv6 book for more details).
The mapping of those pages to process’s address space is done when a process is created. In fork(), it
calls proc_pagetable() which allocates a new address space and then performs mappings of
trampoline and trapframe pages. For example, in proc_pagetable()
if(mappages(pagetable, TRAPFRAME, PGSIZE,
(uint64)(p->trapframe), PTE_R | PTE_W) < 0){ ...
This means mapping the kernel object p->trapframe to the user address space defined by pagetable
at the memory location of TRAPFRAME.
Part 1: Clone() system call
In this part, the goal is to add a new system call to create a child thread. It should look like:
int clone(void *stack);
clone() does more or less what fork() does, except for the following major differences:
• Address space: Instead of creating a new address space, it should use the parent's address space.
This means a single address space (and thus the corresponding page table) is shared between the
parent and all of its children. Do not create a separate page table for a child.
• stack argument: This pointer argument specifies the starting address of the user-level stack
used by the child. The stack area must have been allocated by the caller (parent) before the call to
clone is made. Thus, inside clone(), you should make sure that, when this syscall is returned, a
child thread runs on this stack, instead of the stack of the parent. Some basic sanity check is required
for input parameters of clone(), e.g., stack is not null.
3
Similar to fork(), the clone() call returns the PID of the child to the parent, and 0 to the newly-created
child thread. And of course, the child thread created by clone() must have its own PCB. The number of
child threads per process is assumed to be at most 20.
To manage threads, add an integer type thread_id variable to PCB. The value of thread_id is 0 for the
parent process and greater than 0 (e.g., 1, 2, …) for its child threads created using clone().
There are also some modifications required for the wait() syscall.
• wait(): The parent process uses wait() to wait for a child process to exit and returns the child’s
PID. Also, wait() frees up the child’s resources such as PCB, memory space, page table, etc. This
becomes tricky for child threads created by clone() because some resources are now shared
among all the threads of the same process. Therefore, if the child is a thread, wait() must
deallocate only the thread local resources, e.g., clearing PCB and freeing & unmapping its own
trapframe, and must not deallocate the shared page table.
For simplicity, we will assume that only parent process calls clone() – a thread created by clone()
does not call clone() to create another child thread. Also, assume that a process does not call clone()
more than 20 times (i.e., up to 20 child threads). It is fine to assume that only the parent uses wait() and
the parent is the last one to exit (i.e., after all of its child threads have exited). In addition, parent and child
do not need to share file descriptors. These assumptions will make the implementation a lot easier.
Tips:
• The best way to start would be creating clone() by duplicating fork(). fork() uses
allocproc() to allocate PCB, trapframe, pagetable, etc. However, clone() must not allocate a
separate page table because the parent and child threads should share the same page table. But each
thread still needs a separate trapframe. So, modify allocproc() or create a new function (e.g.,
allocproc_thread) for clone().
• In clone(), you need to specify the child’s user stack’s starting address (hint: trapframe->sp).
• In clone(), you should map each thread's
trapframe page to a certain user space with
no overlap. One simple way would be to map
it below the parent's trapframe location. For
example, see the figure on the right. If your
child thread has a thread ID (> 0), map it to
TRAPFRAME - PGSIZE * (thread ID).
So your first child thread's trapframe is
mapped at TRAPFRAME - PGSIZE, second
one at TRAPFRAME - PGSIZE * 2, and so
on. This can easily avoid overlap.
TRAPFRAME
trapframe
trapframe …
TRAPFRAME - PGSIZE
TRAPFRAME – 2*PGSIZE
Parent’s
Child thread 1
Child thread 2 …
…
4
• You also need to tell the kernel explicitly the new trapframe locations for your child threads.
Update kernel/trampoline.S as explained earlier. Then, at the end of usertrapret() in
kernel/trap.c, change
 ((void (*)(uint64))trampoline_userret)(satp);
to
 ((void (*)(uint64,uint64))trampoline_userret)(TRAPFRAME - PGSIZE * p->thread_id, satp);
for child threads. Normal processes (or thread ID == 0) should continue to use the default
TRAPFRAME address as follows:
 ((void (*)(uint64,uint64))trampoline_userret)(TRAPFRAME, satp);
• Trampoline (not trapframe) is already mapped by the parent and it can be shared with childs. So
you must not map it again to the page table when creating child threads (doing so will crash).
Only map the trapframe of each child (see mappages() function in the background).
• wait() uses freeproc() to deallocate child’s resources, so you will need to make appropriate
changes to freeproc().
Part 2: User-level thread library
You need to implement a user-level thread library in user/thread.c and user/thread.h. How to
create a library? Once you write user/thread.c, find the line starting with ULIB in Makefile and
modify as follows:
ULIB = $U/ulib.o $U/usys.o $U/printf.o $U/umalloc.o $U/thread.o
This will compile user/thread.c as a library and make it usable by other user-level programs that
include user/thread.h.
The first thread library routine to create is thread_create():
int thread_create(void *(start_routine)(void*), void *arg);
You can think of it as a wrapper function of clone(). Specifically, this routine must allocate a user stack
of PGSIZE bytes, and call clone() to create a child thread. Then, for the parent, this routine returns 0 on
success and -1 on failure. For the child, it calls start_routine() to start thread execution with the input
argument arg. When start_routine() returns, it should terminate the child thread by exit().
Your thread library should also implement simple user-level spin lock routines. There should be a type
struct lock_t that one uses to declare a lock, and two routines lock_acquire() and
lock_release(), which acquire and release the lock. The spin lock should use the atomic test-and-set
operation to build the spin lock (see the xv6 kernel to find an example; you can use GCC’s built-in atomic
operations like __sync_lock_test_and_set). One last routine, lock_init(), is used to initialize the lock
as need be. In summary, you need to implement:
struct lock_t {
uint locked;
};
5
int thread_create(void *(start_routine)(void*), void *arg);
void lock_init(struct lock_t* lock);
void lock_acquire(struct lock_t* lock);
void lock_release(struct lock_t* lock);
These library routines need be declared in user/thread.h and implemented in user/thread.c. Other
user programs should be able to use this library by including the header "user/thread.h".
Tips: In RISC-V, the stack grows downwards, as in most other architectures. So you need to give the
correct stack starting address to clone() for the allocated stack space.
How to test:
We will be using a simple program that uses thread_create() to create some number of threads. The
threads will simulate a game of frisbee, where each thread passes the frisbee (token) to the next thread. The
location of the frisbee is updated in a critical section protected by a lock. Each thread spins to check the
value of the lock. If it is its turn, then it prints a message, and releases the lock. Below shows the program
code. This program should run as-is. Do not modify. Add this program as user/lab3_test.c
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
#include "user/thread.h"
lock_t lock;
int n_threads, n_passes, cur_turn, cur_pass;
void* thread_fn(void *arg)
{
int thread_id = (uint64)arg;
int done = 0;
while (!done) {
lock_acquire(&lock);
 if (cur_pass >= n_passes) done = 1;
 else if (cur_turn == thread_id) {
 cur_turn = (cur_turn + 1) % n_threads;
printf("Round %d: thread %d is passing the token to thread %d\n",
 ++cur_pass, thread_id, cur_turn);
 }
 lock_release(&lock);
 sleep(0);
}
return 0;
}
int main(int argc, char *argv[])
{
if (argc < 3) {
printf("Usage: %s [N_PASSES] [N_THREADS]\n", argv[0]);
 exit(-1);
}
6
n_passes = atoi(argv[1]);
n_threads = atoi(argv[2]);
cur_turn = 0;
cur_pass = 0;
lock_init(&lock);
for (int i = 0; i < n_threads; i++) {
thread_create(thread_fn, (void*)(uint64)i);
}
for (int i = 0; i < n_threads; i++) {
wait(0);
}
printf("Frisbee simulation has finished, %d rounds played in total\n", n_passes);
exit(0);
}
It takes two arguments, the first is the number of rounds (passes) and the second is the number of threads
to create. For example, for 6 rounds with 4 threads:
$ lab3_test 6 4
Round 1: thread 0 is passing the token to thread 1
Round 2: thread 1 is passing the token to thread 2
Round 3: thread 2 is passing the token to thread 3
Round 4: thread 3 is passing the token to thread 0
Round 5: thread 0 is passing the token to thread 1
Round 6: thread 1 is passing the token to thread 2
Frisbee simulation has finished, 6 rounds played in total!
$
Test your implementation with up to 20 threads on 3 emulated CPUs.
The Code and Reference Materials
Download a fresh copy of xv6 from the course repository and add the above-mentioned functionalities.
This Lab may take additional readings and through understanding of the concepts discussed in the
handout. Especially, Chapters 2 and 4 of the xv6 book discusses the essential background for this Lab.
What to submit:
Your submission should include:
(1) XV6 source code with your modifications (‘make clean’ to reduce the size before submission)
(2) Writeup (in PDF). Give a detailed explanation on the changes you have made (Part 1 & 2). Add
the screenshots of the frisbee program results for “lab3_test 10 3” and “lab3_test 21 20”. Also, a
brief summary of the contributions of each member.
(3) Demo video showing that all the functionalities you implemented can work as expected, as if you
were demonstrating your work in person. Demonstrate the results of “lab3_test 10 3” and
“lab3_test 21 20” on three CPUs. Your video should show that xv6 is running with three CPUs
(e.g., ‘hart 1 starting’ and ‘hart 2 starting’ messages when booting up).
7
Grades breakdown:
• Part I: clone() system call: 45 pts
o clone() implementation
o modifications to wait()
o other related kernel changes
• Part II: user-level thread library: 25 pts
o thread_create() routine
o spinlock routines
• Writeup and demo: 30 pts
Total: 100 pts
8
Appendix: kernel/trampoline.S
# # code to switch between user and kernel space. # # this code is mapped at the same virtual address # (TRAMPOLINE) in user and kernel space so that # it continues to work when it switches page tables.
#
# kernel.ld causes this to be aligned # to a page boundary. #
.section trampsec
.globl trampoline
trampoline:
.align 4
.globl uservec
uservec: # # trap.c sets stvec to point here, so # traps from user space start here, # in supervisor mode, but with a # user page table. # # sscratch points to where the process's p->trapframe is # mapped into user space, at TRAPFRAME. # # swap a0 and sscratch # so that a0 is TRAPFRAME csrrw a0, sscratch, a0
 # save the user registers in TRAPFRAME sd ra, 40(a0) sd sp, 48(a0) sd gp, 56(a0) sd tp, 64(a0) sd t0, 72(a0) sd t1, 80(a0) sd t2, 88(a0) sd s0, 96(a0) sd s1, 104(a0) sd a1, 120(a0) sd a2, 128(a0) sd a3, 136(a0) sd a4, 144(a0) sd a5, 152(a0) sd a6, 160(a0) sd a7, 168(a0) sd s2, 176(a0) sd s3, 184(a0) sd s4, 192(a0) sd s5, 200(a0) sd s6, 208(a0) sd s7, 216(a0) sd s8, 224(a0) sd s9, 2**(a0) sd s10, 240(a0) sd s11, 248(a0) sd t3, 256(a0) sd t4, 264(a0) sd t5, 272(a0) sd t6, 280(a0)
# save the user a0 in p->trapframe->a0 csrr t0, sscratch sd t0, 112(a0)
 # restore kernel stack pointer from p->trapframe->kernel_sp ld sp, 8(a0)
 # make tp hold the current hartid, from p->trapframe->kernel_hartid ld tp, **(a0)
 # load the address of usertrap(), p->trapframe->kernel_trap
9
 ld t0, 16(a0)
 # restore kernel page table from p->trapframe->kernel_satp ld t1, 0(a0) csrw satp, t1 sfence.vma zero, zero
 # a0 is no longer valid, since the kernel page # table does not specially map p->tf.
 # jump to usertrap(), which does not return jr t0
.globl userret
userret:
 # userret(TRAPFRAME, pagetable) # switch from kernel to user. # usertrapret() calls here. # a0: TRAPFRAME, in user page table. # a1: user page table, for satp.
 # switch to the user page table. csrw satp, a1 sfence.vma zero, zero
 # put the saved user a0 in sscratch, so we # can swap it with our a0 (TRAPFRAME) in the last step. ld t0, 112(a0) csrw sscratch, t0
 # restore all but a0 from TRAPFRAME ld ra, 40(a0) ld sp, 48(a0) ld gp, 56(a0) ld tp, 64(a0) ld t0, 72(a0) ld t1, 80(a0) ld t2, 88(a0) ld s0, 96(a0) ld s1, 104(a0) ld a1, 120(a0) ld a2, 128(a0) ld a3, 136(a0) ld a4, 144(a0) ld a5, 152(a0) ld a6, 160(a0) ld a7, 168(a0) ld s2, 176(a0) ld s3, 184(a0) ld s4, 192(a0) ld s5, 200(a0) ld s6, 208(a0) ld s7, 216(a0) ld s8, 224(a0) ld s9, 2**(a0) ld s10, 240(a0) ld s11, 248(a0) ld t3, 256(a0) ld t4, 264(a0) ld t5, 272(a0) ld t6, 280(a0)
# restore user a0, and save TRAPFRAME in sscratch csrrw a0, sscratch, a0
 # return to user mode and user pc. # usertrapret() set up sstatus and sepc. Sret
請(qǐng)加QQ：99515681 或郵箱：99515681@qq.com   WX：codehelp