In this project, you will implement a simplified version of kernel-level threads to have a taste of how threading is supported by an operating system kernel. To simplify things, the xv6 kernel-level threads will behave slightly differently compared to typical kernel-level threads (e.g., on Linux), and we will describe the differences in Overview section. However, even implementing a simplified version will already give you have a deep understanding of threads and a chance to practice your system engineering/programming skills.
To start the lab, update your repository and create a new branch for your solution by running:
Kernel-level threads enable a process to have several different execution contexts simultaneously, as each thread is responsible for its own context (e.g., register state, stack). However, threads are not concerned with resource management or protection, which are instead concerns for the process. Therefore, all threads belonging to the same process share the virtual memory address space (page table), file descriptor table, and more.
To implement kernel-level threads and let user programs benefit from them, you essentially need to do the following:
clone to create a new kernel-level thread.
join to wait for a kernel-level thread to terminate.
thread_join for applications to invoke.
kernel/proc.c to make your kernel-level threads work properly. This will include (but is not limited to) modifying
This xv6 kernel-level threads behave differently from typical kernel-level threads in several ways:
clone) and our tests will not invoke any file operations. Therefore, you don’t need to take file descriptors into consideration for this lab.
exit, this will terminate the entire process (including all other threads belonging to that process). However, the
exit in this lab has different semantics. If the main thread of the process (i.e., the one created via
exit, then the entire process should be terminated (including all of the created threads via
clone). However, if any other thread of the process (i.e., ones created via
exit, then only that thread itself should terminate (with all other threads unaffected).
struct proc as the TCB for simplicity, as creating a separate
struct thread would involve significant refactoring. Note that you will need to modify
struct proc to store thread information as necessary.
Our tests will focus on the following aspects:
join() are implemented correctly.
sbrk), all other threads should see the same thing (i.e.,
growproc() is implemented correctly).
freeproc() are implemented correctly).
wait() are implemented correctly).
Again, our tests won’t cover file descriptors (to reduce your workload). If you already got a score of 100, feel free to make them work in the traditional way and test it yourself!
We describe the API here, including its input parameters, what it does, and its return value.
int clone(void(*fcn)(void*, void*), void *arg1, void *arg2, void *stack);
This call creates a new kernel-level thread which shares the calling process’s address space.
fcn - the new thread will starts to execute
fcn, which is similar to the signal handler in alarm lab.
arg2 - additionally, we allow the calling process to pass two arguments (
arg2) to the thread. So that the thread can use these two arguments in its routine (i.e.,
stack - each thread should have its own userspace stack, we require the calling process to provide a page of memory (
stack) when creating this thread. This
stack should point to a valid userspace memory with at least 1 page as its size, and it should also be page aligned.
int join(void **stack);
This call waits for a child thread of this calling process to terminate. If there is no child thread, it returns immediately. Otherwise, it keeps waiting until there is one child thread terminates. It reaps the terminated thread, freeing the underlying thread resources resources, and returns the child thread’s PID. (Note: It is possible that there is already a terminated thread when
join is called.)
stack is the address of a
void * variable (e.g.,
void *ptr). When a thread exits, the address of this thread’s user stack will be copied into the
ptr, which can subsequently be freed.
int thread_create(void (*start_routine)(void *, void *), void *arg1, void *arg2);
This is a wrapper library function for
clone(). Inside this function, you need to allocate a suitable block of memory for the newly created thread to use (remember the
stack parameter for
clone()) and then call
clone() to create a new thread for the process.
start_routine - the function that the newly created thread will execute
arg2 - the parameters the calling process want to pass to the thread’s routine
This is a wrapper for the
join() system call. Inside this function, you need to call
join() to wait for a thread to terminate. You need to free the allocated memory (for thread’s stack) inside to avoid a memory leak.
Input parameters: N/A
join that always
return 0. Get them compiled without errors.
user/user.h to implement the
thread_join. Make sure that they can call
join in a correct way. Additionally, make sure they can be called by
threadtest.c in a correct way. Now, edit your
Makefile to include
threadtest. Your code now should be able to compiled correctly and … fail as expected.
fork() already provides a template about how to create a new process control block (
struct proc) and assign them with correct values. Read
fork() source code carefully.
struct proc as a TCB here. Therefore, you need to allocate a new
struct proc for your thread. Take a look at how
fork() does this, and you will find the answer.
fork(), threads of the same process share the same address space, which means they use the same page table.
usertrapret and return to the userspace after it gets scheduled. It will then restore its context from its trapframe. Recall what we’ve done in the alarm lab, you need to modify some values of its trapframe to make it correct, including the program counter, two arguments, and the stack pointer.
a1 stores the arguments. For the stack pointer, you need to make it points to the top of the stack, and you also want to make it aligned. (Hint:
a & (~(8-1)) is a way to align a with 8)
proc, and hence its own
trapframe. However, since all threads share the same process’s address space, their trapframes may be mapped to the same address and will interfere each other. You therefore need to map each thread’s trapframe to a unique address. We provide you several APIs in
kernel/vm.c to do so -
uint64 kwalkaddr(pagetable_t, uint64); to find a free page in the page table
int mappages(pagetable_t, uint64, uint64, uint64, int); to map into the page
You can refer to how
TRAPFRAME is mapped to properly use the above APIs in
clone, you should be able to run the test and see
TEST1 passed followed by some kernel errors. Please use
gdb as instructed on course website and xv6 command line to back trace the panic. If you see some weird page fault errors, you may want to take a look at
exit : the reason why the page fault are caused by
exit is that when thread calls
exit(0), they will free their resources, including freeing their page tables and physical memory. However, all threads share the same memory address space. If one thread exits and free everything, the other threads of the same process will suffer from invalid page table and have no physical memory. To address this issue, you need to go into
exit and differentiate
process. Make sure
thread exits without destroying the entire process. Notice: thread’s unique resource (the page table entry for the trapframe) should be freed properly here, because other threads of the same process have no visibility of that.
exit issue, you can try to comment out all other tests and you should be able to pass test1 correctly now.
wait() already provides a template about how to wait for a process to terminate. Read
wait() source code carefully.
wait(), all you need to do for
join() is to reap a
proc that is for a thread and is already
stack address back (to free it) in a similar way as the
wait() to make sure it only captures child processes not threads.
Now you should be able to run
growproc()), it currently only updates its own
sz while the
pagetable is visible to all threads. You need to ensure that all threads of the same process have the same visibility of the
sz, so that they won’t update
pagetable wrongly (e.g., remap).
exit, all threads of this process should be exit. You need to do something similar to
reparent. The difference is that
reparent changes the parent of all children to be the
init process while for a process’s
exit you need to make all threads (not child process) of the same process exit correctly. You may refer to
kill to see how we can terminate a thread/proc.
For submission, run
make gradescope and submit the resulting
submission.zip file. If you have any errors, you can use
make gradescope-all instead.