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.
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!
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)
fn with the arguments arg1 and arg2, and use stack as its stack. The stack should be one page in size and page-aligned. As with fork(), the PID of the new thread is returned to the parent (for simplicity, threads each have their own process ID).int join(void **stack)
stack (which can then be free'd).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)
malloc to create a new user stack and uses clone to create a child thread and get it running. Returns the newly created PID to the parent and 0 to the child (if successful), -1 otherwise.int thread_join()
join, frees the user stack, and returns the joined thread's PID (if successful), -1 otherwise.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.
clone from forkTo 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
fork(void)
{
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){
kfree(np->kstack);
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.
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.