CS 450: Operating Systems

Machine Problem 2: Kernel Threads

Objectives

For this machine problem you will be adding more system calls to xv6 that:

  1. Support kernel-level threading, so that concurrency within a single user-level process is possible.
  2. Provide a basic synchronization mechanism -- the mutex lock -- for said threads to use.

Threading API

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

int thread_create(void (*tmain)(void *), void *stack, void *arg);

  • This creates a new thread that starts execution at the function tmain, which is called with the argument arg. The caller is responsible for allocating (using malloc, given in the file "umalloc.c") a new user stack before calling thread_create and passing the address of the top of this memory region in as the stack argument. Returns the thread ID (which is really just a process ID) of the new thread to the parent and 0 to the child (similar to fork()).

  • Its implementation will closely mimic that of fork, except that the newly created process will share the address space of its parent and will therefore have automatic access to all of its parent's code and data segments.

int thread_join(void **stack);

  • This will cause the caller to block until a child thread has terminated, upon which its ID will be returned and a pointer to its stack placed in stack (so that the latter can be freed). If the caller does not have any child threads, it will return immediately with -1.

  • While this is similar to the wait system call, note that it only operates on children that share the same address space. wait, in turn, will need to be updated so that it only synchronizes on processes created by the caller that do not share the same address space.

  • The main thread (i.e., the "original" thread) of a given process can call thread_join as many times as it invoked thread_create, so to ensure it exits last.

Mutex

To allow your newly minted threads to coordinate critical sections and safely share data, you will implement the following system calls that expose a mutex lock. The lock will be implemented internally using a spinlock. Your lock should use the x86 atomic exchange.

int mtx_create(int locked);

  • Creates a mutex lock and returns an opaque ID (you might wish to typedef a separate type for the lock ID, though it isn't strictly necessary). The lock starts out in the locked state (binary: true or false).

int mtx_lock(int lock_id);

  • Blocks until the lock has been acquired.

int mtx_unlock(int lock_id);

  • Releases the lock, potentially unblocking a waiting thread.

Note that you can build arbitrarily more sophisticated synchronization mechanisms (e.g., semaphores) in userspace by leveraging this mutex lock.


Hints

Remember, your objective is to implement threading at the kernel level, which means that of course the methods which you are to implement will be done in the kernel. As you have already done this in the first MP, this process shouldn't be confusing to you at all.

 

Recall that one of the major differences between threads and processes is that threads have access to the data which belongs to the parent process. Of course, as you've seen, xv6 supports creating new processes, but these are sandboxed from each other such that direct data access is impossible. In this assignment, we seek to alleviate that constraint by allowing for the creation of threads.

 

Therefore, your implementation will very closely resemble that of the fork() system call, except for the major difference that instead of making a new address space for the child process, the address space will be in that of the parent (which is thus shared between the parent and the child). Looking at the function you are to implement for thread creation, you will see that one of the arguments is indeed this address space (which of course must be allocated before the call to create the thread. Thus, you should make sure that when you return, you are running on this stack, instead of the stack of the parent.

 

Your thread creation function will have two parts: first, it will perform the necessary logic to "clone" the parent with the all important distinction(s) discussed above; second, it will call the function passed in by tmain with the arguments passed in by arg.

 

Your locking implementation will be similar to what is currently implemented in the xv6 kernel, look at some of the more sensitive functions for an example of this. Note: your implementation will be similar, NOT identical!


Testing

To test your code, you should write a program that implements the producer/consumer problem by sharing a bounded buffer between a parent and child (or sibling) threads, using the mutex as a primitive for implementing synchronization.

Add this program to your codebase and the Makefile (see how getcount was added for reference), and be sure to commit and push it as part of your submission.


Submission

As before, submit your work with the command git push origin master, after committing and testing all your changes.