Lab Thread: Kernel Threads

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:

$ git fetch origin
$ git checkout -b thread origin/main
$ make clean


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:

This xv6 kernel-level threads behave differently from typical kernel-level threads in several ways:

Our tests will focus on the following aspects:

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!

API Details

We describe the API here, including its input parameters, what it does, and its return value.

clone (system call)

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.

Input parameters:

Return value:

join (system call)

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.)

Input parameters:

Return value:

thread_create (user library function)

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.

Input parameters:

Return value:

thread_join (user library function)

int thread_join();

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

Return value:

Step by Step Hints

  1. You can first implement the glue. Implement the necessary parts for system calls - simply implement a clone and join that always return 0. Get them compiled without errors.
  2. Edit user/ulib.c and user/user.h to implement the thread_create and thread_join. Make sure that they can call clone and 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.
  3. Now focus on implementing clone first.
    1. 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.
    2. You also need to allocate a new thread control block for your clone. Fortunately, you can just use 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.
    3. Different from fork(), threads of the same process share the same address space, which means they use the same page table.
    4. The newly created thread will return to 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.
    5. Please refer to the RISC-V calling convention, and you will find a0 and 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)
    6. Important: each thread has its own 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 -
      1. uint64 kwalkaddr(pagetable_t, uint64); to find a free page in the page table
      2. 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 kernel/proc.c.
  4. With a correct 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 thread and 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.
  5. After fixing the exit issue, you can try to comment out all other tests and you should be able to pass test1 correctly now.
  6. Now focus on implementing join
    1. wait() already provides a template about how to wait for a process to terminate. Read wait() source code carefully.
    2. Similar as wait(), all you need to do for join() is to reap a proc that is for a thread and is already ZOMBIE.
    3. Additionally, you may need to copy the stack address back (to free it) in a similar way as the copyout for xstate
    4. You need to make corresponding changes to wait() to make sure it only captures child processes not threads.

Now you should be able to run clone() and join() correctly.

  1. However, the above is not enough for the kernel-level thread to be fully correct. One note is that all threads of the same process share the same address space. When the address space grows (e.g., 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).
  2. Besides, when a process (not a thread) calls 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 freeproc or kill to see how we can terminate a thread/proc.

Test and Submit

For test, python3

For submission, run make gradescope and submit the resulting file. If you have any errors, you can use make gradescope-all instead.