Lab Thread: Kernel Threads

In this project, you will implement a simplified version of kernel thread to have a taste of how thread works. This xv6 kernel thread behaves differently from a typical kernel thread. We will describe the difference in overview section. However, to implement a simplified version of kernel thread will already let you have a deep understanding of threads and practice your system-level engineering skills. That is super interesting and please have fun with it!

Before you start

We update the xv6 base repo to provide some helper functions for your kernel thread lab, please re-pull the course repo from main branch (git pull origin main) and then create your own branch as you did for alarm and util labs.


The essential of kernel thread is to let a process have several execution flows simultaneously. This requires each thread keeps its own contexts. For example, threads of the same process can have their own program counters and stacks, and kernel needs to keep track of these for threads. However, all threads of the same process will share the same virtual memory address space, and hence, the same page table.

To implement kernel threads and let application developers to use them, you basically need to do the following things

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

Specifically, to make sure you implement the simplified xv6 kernel thread correctly, we test -

Notice - our tests won’t cover file descriptors (to reduce your workload) and you don’t need to worry about file descriptor tables in this lab. If you already get 100, feel free to make them work in a proper 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 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, return immediately. Otherwise, keeps waiting until there is one child thread terminated. It reap the terminated thread and free the terminated thread’s resources, and return the child thread’s PID. Notice, 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 the clone() to create a new thread for process.

Input parameters:

Return values:

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 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 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, make gradescope and submit the file. Please delete file before you create a new one. Besides, refer to the Ed pinned post if you have zip: command not found error.