xv6 MP4: Kernel threads


In this machine problem, you'll be adding support for kernel-level threads to xv6. You will also write a small user-space threading library that allows you to create and synchronize threads via locks.

Obtaining the repository

Claim your private repository using the GitHub invitation link found in the assignment list on the course homepage. Accept the invitation and clone your repository on the computer where you'll be doing your work.

Next, edit the "AUTHOR" file in your repository -- in it you will find an honor pledge that you should sign with your information and today's date. Do this NOW so you don't forget!

Implementation details

Your kernel thread API will consist of two system calls: the first, called clone, will create a kernel thread, and the second, called join, will allow you to wait for a thread.

You will implement the following system calls to support thread creation and management:

int clone(void(*fn)(void*, void *), void *arg1, void *arg2, void *stack)

int join(void **stack)

You also need to think about the semantics of existing system calls. For example, wait should wait for a child process that does not share the address space with this process. It should also free the address space if this is last reference to it. Also, exit should work as before but for both processes and threads; little change is required here.

Your user-space thread library will be built on top of the system calls described above, and consist of the following thread management functions:

int thread_create(void (*start_routine)(void *, void *), void *arg1, void *arg2)

int thread_join()

Your thread library should also provide a simple locking API (built on top of a ticket lock, discussed in class and covered in this OSTEP chapter). You should define the lock_t type used for declaring locks, and the following functions:

void lock_init(lock_t *)

void lock_acquire(lock_t *)

void lock_release(lock_t *)

Your lock implementation should use x86's atomic add instruction to build the lock -- see this wikipedia page for a way to create an atomic fetch-and-add routine using xaddl.

The thread library should be available as part of every program that runs in xv6. Thus, you should add prototypes to user/user.h and the actual code to implement the library routines in user/ulib.c.

One thing you need to be careful with is when an address space is grown by a thread in a multi-threaded process (for example, when malloc() is called, it may call sbrk to grow the address space of the process). Trace this code path carefully and see where a new lock is needed and what else needs to be updated to grow an address space in a multi-threaded process correctly.

Building clone from fork

To implement clone, you should study (and mostly copy) the fork system call. The fork system call will serve as a template for clone, with some modifications. For example, in kernel/proc.c, we see the beginning of the fork implementation:

  int i, pid;
  struct proc *np;

  // Allocate process.
  if((np = allocproc()) == 0)
    return -1;

  // Copy process state from p.
  if((np->pgdir = copyuvm(proc->pgdir, proc->sz)) == 0){
    np->kstack = 0;
    np->state = UNUSED;
    return -1;
  np->sz = proc->sz;
  np->parent = proc;
  *np->tf = *proc->tf;

This code does some work you need to have done for clone, for example, calling allocproc to allocate a slot in the process table, creating a kernel stack for the new thread, etc.

However, as you can see, the next thing fork does is copy the address space and point the page directory (np->pgdir) to a new page table for that address space. When creating a thread (as clone does), you'll want the new child thread to be in the same address space as the parent; thus, there is no need to create a copy of the address space, and the new thread's np->pgdir should be the same as the parent's -- they now share the address space, and thus have the same page table.

Once that part is complete, there is a little more effort you'll have to apply inside clone to make it work. Specifically, you'll have to set up the kernel stack so that when clone returns in the child (i.e., in the newly created thread), it runs on the user stack passed into clone (stack), that the function fn is the starting point of the child thread, and that the arguments arg1 and arg2 are available to that function.

Testing and Scoring

As with the previous machine problem, we include a test suite which you can run with the command make test-mp4. The test source files (which you should not alter --- we'll be using our own pristine copies in any case) can be found in the "tests/mp4/ctests" directory if you're interested.

If a test fails, it'll stop immediately with an error report. If you want to continue running all tests even after hitting a failure, do make test-mp4-cont instead.


Make sure that you edited the "AUTHOR" file in your repository and signed the honor pledge with your student information. If you don't do this we won't be able to associate your submission with you!

To submit your work, simply commit all your changes (adding new files as needed) and push your work to your GitHub repository.