Project 3: Threads

Note: It might be useful to print out this project description page for easy reference.

Project Overview

In this project you will implement threads in xv6.  This project may be completed individually or in groups of two people.

Project (100 points)
This project requires you to create two new syscalls to implement threads in xv6.  The syscalls are clone and join.  The clone syscall creates a new thread.  The join syscall waits for a child thread to finish.  You will also have to make some changes to a few other places in the code to get everything working properly.

Extra credit (20 points)
For extra credit, you can implement a user library of thread-related functions.  See below for more details.

Educational Objectives

This project aims to achieve several educational objectives:

The Code

You should start from a fresh copy of the xv6 code.  The simplest option is to clone another copy of the repository:

$ git clone

Or you can pull my latest changes to your existing repository and switch to my last commit:

$ git fetch origin
$ git checkout bcb94c0
$ git checkout -b project3

Project Description and Requirements

100 points

You will implement threads as lightweight processes which share the same address space as their parent process.  This approach is how LinuxThreads was implemented on earlier versions of the Linux kernel, although it has since been superseded in newer versions.

We will explain the project by going over the syscalls that you need to create in detail.

1) clone

The clone syscall creates a new thread of execution by creating a clone of the current process with the same address space.  You MUST use this function signature:

int clone(void(*fcn)(void*), void* arg, void* stack)

The first argument, fcn, is a function pointer.  It points to a function where the new thread will begin execution.  For now, let's refer to this function as DoThreadWork.

The second argument, arg, is a pointer to some data that will be passed as an argument to the DoThreadWork function.

The third argument, stack, is a pointer to a page in user space that the new thread will use as its call stack.

Overall, clone is very similar to fork.  It creates a new entry in the process table and copies over the parent process's information into the new entry.  However, clone does not create a new copy of the memory associated with the parent process.  Instead, the new thread will use the same address space as the parent process.  Another difference between clone and fork is that in fork, both the parent and the child return from fork to the same place, namely the next instruction after the call to fork.  However, in clone, the new thread begins execution in the function that is designated by the function pointer fcn.

Here is an example of a simple user program that makes use of the clone syscall:

#include "types.h"
#include "user.h"

#define PGSIZE (4096)

volatile int global = 1;

void DoThreadWork(void* arg_ptr); // function signature for our DoThreadFunction

main(int argc, char* argv[])
void* stack = malloc(PGSIZE*2); // allocate 2 pages of space
if((uint)stack % PGSIZE) {
// make sure that stack is page-aligned
stack = stack + (PGSIZE - (uint)stack % PGSIZE);

void* arg = NULL; // our DoThreadWork function is simple and doesn't need an arg
int clone_pid = clone(DoThreadWork, arg, stack);
// the main thread of execution (aka parent process) continues executing here
while(global != 5) {
; // wait for child thread to finish
printf(1, "global: %d\n", global); // prints "global: 5"

DoThreadWork(void* arg_ptr) {
// clone creates a new thread, which begins execution here
global = 5;

Requirements (and hints)

Here is a list of specific requirements related to the clone syscall:


2) join

As you have seen, clone is sort of like fork, except for threads.  Well, join is sort of like wait(), except for threads.  It waits for a thread to complete.  Here is the function signature:

int join(int pid)

The argument, pid, is the pid of the thread to wait for.

Here is an example of a simple user program that makes use of the join syscall.

#include "types.h"
#include "user.h"

#define PGSIZE (4096)

int global = 1;

void DoThreadWork(void* arg_ptr);

main(int argc, char* argv[])

void* stack = malloc(PGSIZE*2); // as before, allocate 2 pages
if((uint)stack % PGSIZE){
stack = stack + (PGSIZE - (uint)stack % PGSIZE); // make sure the stack is page aligned

int arg = 42;
int clone_pid = clone(worker, &arg, stack);
// main thread continues executing...
int join_pid = join(clone_pid); // ...but waits for the new thread to complete
// note that join_pid should equal clone_pid
printf(1, "global: %d\n", global); // prints "global: 43"

DoThreadWork(void *arg_ptr) {
int arg = *(int*)arg_ptr;
global = global + arg;

Requirements (and hints)

Here is a list of specific requirements related to the join syscall:


3) side effects

Now that we have implemented threads as lightweight processes.  The wait syscall must change slightly.

Requirements (and hints)

Here is a list of specific requirements related to the wait syscall:



Make sure you do a final testing on Murphy because Murphy will be the machine used for grading. 

We are providing some basic tests to help you get started.  The purpose of these tests is:
1) to give you a testing framework,
2) to help you understand how a user program might invoke your syscalls, and
3) to make it easy to add your own tests.

The provided tests are intentionally not comprehensive and we strongly recommend that you add your own tests.  If you are having trouble thinking of your own tests, see the list of Requirements.  Typically, each requirement can be translated into at least one test.  Sometimes you can write many many many tests for a single requirement.

One final recommendation.  Modern software engineering principles emphasize writing your tests before writing your code.  This is taught at Northwestern in EECS 111 as part of the Design Recipe.  In industry, you may hear it described as test-driven development.  The point is, we recommend writing tests first, in order to force yourself to define the desired outcome of your code.  Then after you've written your code, you can run your tests to get immediate feedback on whether your code is correct or not.

Without further ado, here is how to use the provided tests.  Download the .tar.gz below, copy it to a lab machine, and extract it.  Inside, you will find a README with instructions on how to run the provided tests as well as how to add your own tests.  If anything is unclear or doesn't work, please post to Piazza.


Extra Credit Description and Requirements

20 points

Note: Unlike Project 2, attempting this extra credit should not require modifying the basic functionality above.  Therefore, for this project you can just make one submission.  We will run the extra credit tests on all submissions.

We believe that the project requirements above are fairly manageable and so we hope that many of you will attempt the extra credit.

For extra credit, you will implement a user library that would allow a developer to make good use of your operating system's threads.  This user library will include wrapper functions for creating and joining threads.  It also includes synchronization-related functions which will make it easier to write thread-safe programs.

The functions below should be placed in a new file: user/uthreadlib.c

  1. Thread wrappers
    1. thread_create
      int thread_create(void (*start_routine)(void*), void* arg)
      Creates a new thread by first allocating a page-aligned user stack, then calling the clone syscall.  Returns the pid of the new thread.
    2. thread_join
      int thread_join(int pid)
      Calls join to wait for the thread specified by pid to complete.  Cleans up the completed thread's user stack.

  2. Locks
    Hint: See how spinlock is implemented in the kernel.  You will want to use the atomic exchange function, xchg.
    1. lock_acquire
      void lock_acquire(lock_t* lock)
      Acquires the lock pointed to by lock.  If the lock is already held, spin until it becomes available.
    2. lock_release
      void lock_release(lock_t* lock)
      Release the lock pointed to by lock.
    3. lock_init
      void lock_init(lock_t* lock)
      Initialize the lock pointed to by lock.

  3. Condition variables
    Hint: In order to implement these user functions, you will have to implement new syscalls.
    1. cv_wait
      void cv_wait(cond_t* conditionVariable, lock_t* lock)
      Release the lock pointed to by lock and put the caller to sleep.  Assumes that lock is held when this is called.  When signaled, the thread awakens and reacquires the lock.
    2. cv_signal
      void cv_signal(cond_t* conditionVariable)
      Wake all threads that are waiting on conditionVariable. (This is actually like the broadcast() function in pthreads).

Submission instructions


To submit, make sure your xv6 directory contains a file called team.txt, which contains all the netids of the members of your group on separate lines.  

You should first commit all your changes to git and create a patch file for submission.  If you created new files for your solution then you will have to tell git to add these files to the project.  Run "git status" and look for untracked files.  Then run "git add <my_new_file>" to add that file to the project.  For example, you will have to run "git add team.txt".  Review your changes with "git diff" and finally run "git commit -a" to commit your changes.  Now create a patch file for submission as follows:

$ git diff --binary --cached 5e6f6aac > project3_solution.patch

If you look at the "project3_solution.patch" file, you should see all of the code that you have written for this project.  If you do not see all your code, then you probably forgot to "git add" something.  You must upload the .patch file on the assignment page on Canvas.

Please test your patch file by cloning a fresh copy of xv6 to another folder, then running:

$ git apply --whitespace=nowarn <path-to-your-patch-file>