Due: Thu Mar 7 11:59 pm
Late submissions accepted until Sat Mar 9 11:59 pm

Assignment by David Mazières and John Ousterhout, with modifications by Nick Troccoli.

In this assignment you will implement a simple threading mechanism in C++ and use that to implement your own version of locks and condition variables. Normally, threads are implemented in the operating system, but for this assignment you will implement them inside a user-level application. Your thread dispatcher will run in a single system thread, which is what you get when a new process starts or when you create a std::thread object. Your dispatcher will use that system thread to create and run any number of user-level threads. These user-level threads will have all the features of system threads (each has its own stack, they can be scheduled independently, and you will implement locks and condition variables for them), but the operating system doesn't know about them: it only knows about the one system thread. Your code to implement user-level threads will be very similar to the code that implements system threads in an operating system running on a single core.

Learning Goals

The goal of this project is for you to get experience managing thread dispatching, scheduling and synchronization. This assignment will help you:

• Learn how dispatching works and what code is required to create, execute, and delete threads.
• Learn how timer interrupts can be used to implement a round-robin scheduler.
• Learn how locks and condition variables can be implemented in a singe-core system.

Getting Started

To get started on the assignment, clone the starter project using the command

    git clone /afs/ir/class/cs111/repos/assign5/$USER assign5

This line creates a new folder called assign5 in your current working directory containing a copy of the starter code.

Here are the relevant files for your work on the assignment:

• thread.hh/cc: the implementation of the Thread class for part 1 of the assignment that represents a single thread, and also dispatches/schedules threads to run. You will edit the header file to add necessary state, and edit the cc file to implement the provided methods.
• stack.hh: a provided implementation of a Stack variable type that represents a thread stack and manages the stack memory, the saved stack pointer, and what function to initially run.
• timer.hh: a provided implementation of a timer that can call a specified handler function at a specified time interval.
• sync.hh/cc: the implementation of the Mutex and Condition class for parts 2 and 3 of the assignment that represents mutex and condition variable types. You will edit the header file to add necessary state, and edit the cc file to implement the provided methods.
• test.cc: a test file containing various tests that spawn Threads and use mutexes and condition variables in different ways.
• samples: a symbolic link to the shared directory for this assignment. It contains:
  • test_soln: a provided sample test solution executable that uses a fully-implemented Thread/Mutex/Condition class.

The testing framework for this assignment is similar to what you have used in other assignments. When you invoke make, it will compile your code along with the file test.cc to form an executable program test. test.cc contains various tests that invoke your code to exercise features of the Thread class. The sanity checker will invoke test with different parameters to run a series of tests, and it will compare the output of those tests with the output produced by our sample solution, which is in samples/test_soln. The sanity checker prints out the command that it runs for each test, so if a test fails, you can invoke test or samples/test_soln with the same parameter in order to see the output/expected output. You can also run test under the gdb debugger to study its behavior in more detail.

When you're debugging, it may be useful to look at the actual test code so you can see exactly what it's trying to do. All of the test code is in the file test.cc. Each test has a name such as enter, which is included on the command line to run the test, and the test is implemented by a function with the same name. Open test.cc and find the function enter, which is the first test that the sanity checker will run. As you can see, it is trying to create a new thread with enter_thread as the top-level method; then it invokes the dispatcher so the thread will run. You can find the code for enter_thread just above the code for enter; it prints a message and then exits the test application.

Note: we don't guarantee that the tests we have provided are exhaustive, so passing all of the tests is not necessarily sufficient to ensure a perfect score (CAs may discover other problems in reading through your code).

This project consists of three parts - implementing Thread, implementing Mutex, and implementing Condition. Each part builds on the previous one (Mutex relies on Thread methods, and Condition relies on Mutexes and Thread methods), so make sure to thoroughly test each part before moving on to the next.

Additionally, this project builds on our use of C++ classes, methods and instance variables, and uses some additional C++ features, some of which you may have used before, and others that might be new. The resources in our C/C++ guide, including the C++ classes review video, may be helpful in reviewing details of classes in C++. Also check out this C++ guide/refresher to get up to speed on static!

Open assign5 C++ Guide

Important note: one of the new C++ features mentioned in the guide above is static class variables. When deciding whether to make something static, carefully consider how many copies of that field you need; do you need one per object, or one shared across all objects? Making something static when it shouldn't be can be the source of many a gnarly bug, since it will subtly share one copy instead of keeping separate copies!

Additionally, make sure to distinguish between using this and using Thread::current(). this refers to the current object in a non-static method; e.g. within Mutex::lock, it will refer to the current Mutex.

Assignment Overview Video

We've created a short video that provides an overview of the assignment. It's not required to watch to complete the assignment, but rather just provides a walkthrough of some of the information included in this spec, plus tips/hints/tricks for different parts. We hope you find it helpful! (You can also view the video on Canvas, in the same place as the lecture videos). Slides here, code here (or make a copy of /usr/class/cs111/lecture-code/assign5).

1. Thread

First, you'll implement a C++ class Thread that represents a single thread. This is an expanded version of the struct Thread used in lecture and section with more features. Specifically, in addition to managing internal state (such as its stack), the Thread class also manages dispatching/scheduling of threads. Specifically, it can context switch between threads, it keeps track of a ready list of ready threads to run, and it keeps track of the current running thread.

Check out thread.hh for the list of public methods on the Thread class that you will implement - the documentation in the header file provides more information about each method's behavior.

Stack Management

Each thread will have its own stack, and we have created a class Stack to help you manage stacks and context switching. A Stack object contains enough space for a moderate size call stack, plus a place to store the stack pointer register when the stack is not active. The constructor for the class looks like this:

Stack(void(*start)(Thread *), Thread *t);

This constructor will initialize the object so that the function start will be invoked the first time stack_switch is called to activate the stack, and will be passed the specified thread as its parameter.

void stack_switch(Stack *current, Stack *next)

This function performs a context switch by switching executing from one stack to another. This is just like the context_switch function from lecture, except that its parameters are pointers to Stacks instead of Thread references. current is the Stack object that is active (the stack pointer register points somewhere in this object), and next is the stack to switch to. The function will save registers on the current stack, save the current stack pointer in current, switch to the stack pointer stored in next, and restore the registers saved on that stack. When the function returns, it will be executing on the new stack. The first time that stack_switch switches into a stack, it will start executing code at the start function for that stack; after that switching into a stack will cause execution to resume where it left off (returning from the stack_switch call that switched out of that stack). Note: it is fine for current and next to be the same. As a special case, it is also OK for current to be nullptr; when this happens, the current stack pointer register is not saved (you'll see later why this is needed). You will invoke this function in your implementation of Thread::redispatch.

The code that implements Stack is interesting to read through - if you're curious, check out the code in stack.hh and stack.cc in the starter code.

Miscellaneous Notes

• You may assume that your code will only run on single-core systems, so disabling interrupts is sufficient to ensure that no other thread will run.
• Don't worry about Valgrind errors (stack switching can cause false positives). Just make sure your code frees things it allocates.
• Your code may (and is encouraged to, where appropriate) call existing Thread methods as needed instead of re-implementing logic.
• Our full implementation is roughly 30 lines (excluding comments, and only including lines in the .cc file)

Initial Milestones

We have designed the tests so that you can implement this assignment in stages, testing each stage before going on to the next. Here are the first milestones to implement:

Milestone 1: The First Thread

Before writing any code, take a few minutes to think about what information will need to be stored in each Thread object in order to implement the required methods (hint: it's not much!).

In this milestone you will create just enough functionality to create a thread and dispatch it, so that the thread's top-level function starts executing. To pass this milestone, you'll need to implement the following features:

• The Thread constructor.
• The schedule method (so the constructor can schedule the new thread).
• The redispatch static method, which the first test will invoke to context switch into the new thread.
• The thread_start wrapper method, discussed below.

Don't worry about any of the other methods right now, and don't worry about disabling interrupts.

The constructor must initialize the thread's instance variables as needed, and schedule the thread so it can run. There are a few nuanced parts to initialize a thread's state:

• You'll see why in a future milestone, but a thread's stack needs to remain allocated even when the thread itself is deleted. For this reason, the stack must be allocated on the heap. Don't worry about freeing it for now. See our C++ guide for info on heap allocation.
• When you initialize a stack, you must specify the initial function it should run. We might think this can just be the function specified by the main argument, but later on we will need to do additional prep and cleanup in addition to running main, so we can't just pass in main itself. For that reason, we've provided a wrapper function called thread_start in the starter code - this is the function that every stack should initially run, and is passed the running thread as a parameter (so you can access its instance variables). Right now, that wrapper function should just execute the thread's main function (though you will also need to leave the while (1) {} line as the last line for now, because ultimately thread_start must not return), but later we will add additional code to this wrapper function (e.g. when handling interrupts). Note: if you have a variable func of type std::function, you can run it like this: func().
• When using the provided ready queue called ready_ in the starter code, check out a handy C++ reference to learn more about the C++ queue type (common gotchas; front() does NOT remove the element from the queue, and pop() does NOT return the popped element).
• To implement redispatch, you should perform a context switch to the next ready thread using stack_switch. When the program starts up, no Thread is currently running (we do not count the real system thread as a Thread). Therefore, the first time we call redispatch, we will be switching from no thread to a thread, and then subsequent context switches will switch from one thread to another. For this milestone (we'll update this later), assume that only one thread is ever scheduled - in other words, when you call stack_switch, the first parameter should always be nullptr (which indicates that stack_switch should not save the existing stack pointer). What this means is, once your Threads start executing, you'll abandon the system thread's stack and just use the Stacks you created for each Thread.

Once you've written this code, you should be able to pass the enter test to dispatch your first thread!

Milestone 2: Multiple Threads

In this milestone you will add functionality to switch between threads. To do this, you will implement the yield method and current method. In addition, you will need to fix the stack_switch simplification from Milestone 1, where you always passed nullptr as the prev argument. From now on, you should pass in nullptr only if there is no current thread running, and otherwise it should be the current thread's stack.

Note: if at any point the redispatch method finds that there are no threads left to schedule, then it should invoke std::exit(0) to terminate the program. Exiting the program makes sense because once there are no runnable threads, there is no way for a thread ever to become runnable (even if there are blocked threads, some other thread would have to run in order to unblock them). In a real operating system, device interrupts could cause blocked threads to become runnable, but there are no devices in this assignment.

Once you've written this code, you should be able to pass the ping_pong, round_robin and block tests!

Milestone 3: Thread Exit

In this milestone you will implement enough functionality for threads to exit cleanly. A thread can exit either by calling Thread::exit or by returning from its top-level function back into your wrapper (as of this milestone, there should be no more need for the while (1) {} line in your wrapper).

Thread::exit() should delete the current thread, update the state to reflect there is currently no thread running, and then switch to the next ready thread to run. As part of this, we might think that deleting the current thread should also mean deleting its stack. However, that isn't safe, because Thread::exit() is actually running on the Thread's stack and will continue to do so until Thread::redispatch changes to a different Thread. Thus, the stack cannot be freed immediately. However, it must eventually be freed, once you can be sure it's no longer in use. There are several ways to do this, but one simple way is to delay freeing a Thread's Stack until the next Thread is destroyed (at which point we know the old thread can't still be running). When each Thread exits, it deletes the Stack from the previous thread and saves its Stack for the next exiting thread to delete. This means there will always be one Stack that hasn't yet been deleted, but that's OK. The only tricky aspect of this milestone is figuring out how to implement this deferred Stack deletion (hint: you'll probably want to use a static variable).

Once you've written this code, you should be able to pass the exit and stack tests!

Milestone 4: Preemption

So far, your dispatcher is non-preemptive: a thread can run as long as it likes. In the final milestone for this assignment you will add preemption to switch between threads using a round-robin scheduling mechanism with time slices. You'll use timer interrupts to do this, and you'll implement two methods: Thread::preempt_init, which initializes preemption - see thread.hh information about this method and what it should do. A timer interrupt handler. We'll also need to ensure we properly handle interrupts throughout the Thread methods.

Your implementation of preemption should use the following function, provided by the starter code in timer.cc (the same timer as seen in lecture), to generate timer interrupts:

void timer_init(std::uint64_t usec, std::function<void()> handler);

Once you have invoked this function, timer interrupts will occur every usec microseconds (unless interrupts are disabled as described below). During each timer interrupt, handler will be invoked.

You must decide what the handler should do/be, and specify its name as the handler parameter (prefix it with Thread:: if you specify a thread method).

The starter code also provides the following functions to disable and reenable interrupts:

intr_enable(bool on)

If the argument is false, defers all interrupts. If the argument is true, enables interrupts and immediately dispatches any deferred interrupts.

intr_enabled()

Returns true if interrupts are currently enabled, false otherwise. Interrupts are initially enabled.

The starter code also defines an IntrGuard class, analagous to std::unique_lock. When an IntrGuardobject is constructed, the current interrupt-enabled state is saved and interrupts will be disabled; when an IntrGuard object is destroyed, the interrupt-enabled state will be restored to the value saved by the constructor. You should prefer using IntrGuard objects instead of calling intr_enable whenever possible to guarantee proper enabling/disabling. Note: the interrupt handling code that invokes handler will create an IntrGuard (see the timer_interrupt function in timer.cc), so interrupts will be disabled as long as your handler is executing. Before returning from an interrupt the IntrGuard will be destroyed, which reenables interrupts.

If the timer fires at a time when interrupts have been disabled, this occurrence will be remembered and an interrupt will occur as soon as interrupts are re-enabled.

To complete this milestone, implement the preempt_init method and the timer handler function. You will also need to add code throughout the Thread class to disable and enable interrupts when appropriate. Carefully review the expected behavior of each Thread method to decide when interrupts should be enabled and disabled. Here are a few hints:

• Interrupts can cause problems when you are modifying state that is shared between threads. Consider which pieces of state are shared and which are private to a thread.
• Interrupts must be disabled whenever redispatch is invoked
• When a thread starts up for the first time in your wrapper function, it receives control from the dispatcher just as if it had invoked redispatch, so interrupts will be disabled; your code will need to reenable interrupts.

Once you have made these changes, the preempt sanity test should pass. At this point, if you invoke tools/sanitycheck all the tests should pass. Note: the sanity tests do not test for properly disabling and reenabling interrupts in all situations; that's something that will require additional reasoning and checking in your code to ensure correctness.

Congratulations, you have a fully-functional thread dispatcher/scheduler!

2. Mutex

Your next task is to implement something you're familiar with as a client - but now you have the tools (specifically your dispatcher from part 1!) to build one yourself. The Mutex class is extremely similar to the standard C++ mutex, with the addition of a mine method. Check out sync.hh for the list of public methods on the Mutex class that you will implement - the documentation in the header file provides more information about each method's behavior.

Complete the declaration of the Mutex class in sync.hh, and fill in the bodies of the Mutex constructor and the methods lock, unlock, and mine.

You may assume that your code will only run on single-core systems, so disabling interrupts ensures that no other thread will run. Your solution should look similar to the uniprocessor implementation described in lecture, but must also keep track of its owner thread.

As part of this assignment, you will need to use the public methods you implemented in the Thread class. For example, a thread can block itself by calling Thread::redispatch (with interrupts disabled, of course). Later on, some other thread can wake it up by invoking the schedule method on the blocked thread. Carefully consider how some of those methods will come in handy to perform the thread operations you want to perform.

Make sure to properly enable and disable interrupts as needed to avoid race conditions.

At this point the tests mutex_basic, many_threads and mine should pass!

3. Condition

Your final task is to implement something else you're familiar with as a client - a condition variable. Now that you have both a dispatcher and a mutex implementation, you have the tools to build one yourself. The Condition class is extremely similar to the standard C++ condition_variable_any. Check out sync.hh for the list of public methods on the Condition class that you will implement - the documentation in the header file provides more information about each method's behavior.

Before you start coding, think a bit about what sort of information you'll need to keep in Condition structures. There are some similarities with the Mutex implementation to consider.

Like with Mutex, the thread operations (blocking a thread, etc.) will require using the public methods from your Thread dispatcher. Carefully consider how some of those methods will come in handy to perform the thread operations you want to perform. Your implementation will also use the public methods of your Mutex class. There should be no need for any of the Condition methods to access the private fields of a Mutex object, or vice versa.

Complete the declaration of the Condition class in sync.hh, and fill in the bodies of the Condition constructor and the methods wait, notify_one, and notify_all. You may assume that your code will only run on single-core systems, so disabling interrupts is sufficient to ensure that no other thread will run.

Make sure to properly enable and disable interrupts as needed to avoid race conditions.

At this point the remaining tests (cond_basic, two_conds, notify_all, and lock_vs_notify) should pass!

Submitting

Once you are finished working and have saved all your changes, submit by running the submit tool in the tools folder: ./tools/submit. We recommend you do a trial submit in advance of the deadline to allow time to work through any snags. You may submit as many times as you would like; we will grade the latest submission. Submitting a stable but unpolished/unfinished is like an insurance policy. If the unexpected happens and you miss the deadline to submit your final version, this previous submit will earn points. Without a submission, we cannot grade your work. You can confirm the timestamp of your latest submission in your course gradebook.

Grading

Here is a recap of the work that will be graded on this assignment:

• thread.hh and thread.cc: flesh out the Thread class; it should work in both preemptive and non-preemptive modes.
• sync.hh and sync.cc: implement Mutex and Condition
• Code review for style.

We will grade your code using the provided sanity check tests and possible additional autograder tests. We will also review your code for other possible errors and for style. Check out our course style guide for tips and guidelines for writing code with good style!