Project 4b: xv6 Threads
Make sure to read the general instructions for the project here.
Changelog
Overview
In this project, you'll be adding real kernel threads to xv6. Sound
like fun? Well, it should. Because you are on your way to becoming a
real kernel hacker. And what could be more fun than that?
Specifically, you'll add four new system calls:
int clone(void *stack)
int lock(int *l)
int unlock(int *l)
int join()
You'll also add one user-space function that wraps clone() for convenience:
int thread_create(void (*fn) (void *), void *arg)
You'll also have to modify some existing system calls, such
as wait() .
Note: Start with a clean kernel; no need for your new fancy
address space with the stack at the bottom, for example.
Details
Each new function returns -1 on failure. The locking functions
(lock and unlock ) return 0 on success,
and the other three (clone , join , and
thread_create ) return a thread ID.
Getting clone working is the first step, and will
probably take the most time. This call should behave very much
like fork , except that instead of copying the address
space to a new page directory, clone initializes the new
process so that the new process and cloned process use the same page
directory. Thus, memory will be shared, and the two "processes" are
really actually threads.
Although the two threads will share the same address space, they
each need their own stack; the cloned process allocates space for
this, probably with malloc. Suppose thread T1 is making a clone of
itself, T2. T1 will first allocate a 1-page piece of page-aligned
memory and pass a pointer to that memory to the clone
system call. The
clone system call will then copy T1's stack to that
location, and update T2's stack and base registers to use the new
stack. It's admittedly a bit strange to allocate T2's stack in a heap
object allocated by T1 in this way, but the alternative would be to
integrate with p3b (relocated stacks), and that would require you to
do much more work.
The thread_create function wraps clone , and
takes a function pointer and thread argument as arguments. This call
should do the following:
- allocate page-aligned space for the new stack
- call
clone , returning the thread ID to the parent
- in the child,
thread_create should call the
function pointer, passing it the provided argument
- when the provided function returns,
thread_create
should free the stack and call exit
Note that functions passed to thread_create should not
quit by exiting; they should quit by returning.
Otherwise, thread_create will not have an opportunity to
free the space used for the stack.
Another new system call is int join(void) , which is
very similar to the already existing int wait(void) call;
join waits for a thread child to finish,
and wait waits for a process child to finish.
The lock and unlock calls should have the
normal behavior. Any code using these calls should initialize the lock
variable to 0. Internally, a thread waiting on lock
should go to sleep rather than spin.
To test your code, use the TAs tests, as usual! But of course you
should write your own little code snippets to test pieces as you
go.
Have fun!
Extra Credit
(1) When a thread is cloned, the new thread and old thread should have
identical file descriptors (this part is required). With some extra
work, you can make sure that when one thread opens a file descriptor,
the new file descriptor is visible to all the threads.
(2) The init program collects zombie processes when a parent exits
without calling wait . You may wish to modify init.c so
that it also collects zombie threads when a parent exits without
calling join . You may need to add an extra system call
to accomplish this.
Hints
For getpid , it is acceptable (but not required) for each
thread of a process to return a different pid. You may wish to use
pids as thread IDs to minimize the changes you must make.
You need to make sure you do not free the page table when a thread
exits if there are still other threads running. The elegant way to
handle this is with reference counting. The quick but hacky way is to
scan the process table looking for other references before freeing the
page table.
When implementing lock and unlock ,
the sleep and wakeup calls in proc.c may be
useful, perhaps in combination with a "guard" spinlock.
One thing you need to be careful with is when an address space is
grown by a thread in a multi-threaded 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.
It is difficult to write clone incrementally. Two
tricky cases you have to handle are (1) avoiding race conditions upon
address-space growth, and (2) not freeing a page table until all
threads are finished. We recommend starting with simple test code
that avoids these issues by never growing the address space and
never exiting, such as this.
The Code
The code can be found in
~cs537-2/public/xv6.tar.gz. Everything you need to build and run
and even debug the kernel is in there, as before.
As usual, it might be good to read the xv6 book a bit:
Here.
You may also find this book useful:
Programming from the Ground Up. Particular attention should be paid to the
first few chapters, including the calling convention (i.e., what's on the
stack when you make a function call, and how it all is manipulated).
|