Assignment 5: Dispatching and Implementing Locks/CVs

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

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

Assignment 5 Overview Session: Thursday, March 2nd 2-2:50PM on Zoom (link on Canvas). Note that the session is recorded and will be posted to the course website shortly after it’s over. Slides here, code here (or make a copy of /usr/class/cs111/lecture-code/yeah5), video here.

In this project you will implement a threading mechanism in C++ similar to what's managed your own threads you've spawned in programs so far this quarter, and implement lock and condition variable types that utilize it. Normally, threads are implemented in the operating system, but for this project you will implement them inside a user-level application. This means that the operating system won't actually know about the threads (it thinks the program is using just one thread, the one spawned for the program itself), but they will have all the features of real threads (each has its own stack, they can be scheduled independently, and you will even implement locks and condition variables for them). 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 (and you may assume that all parts of this assignment are run on a single-core system).

Learning Goals

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

  • more fully understand thread dispatching and context switching
  • gain experience managing many running threads and scheduling threads
  • understand the internals of the mutex and condition_variable_any types that you've been using so far this quarter

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 instance variables, 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 instance variables, 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.

Note that test-soln is a fully-implemented sample solution; when in doubt about the expected behavior, you can run the sample solution to see what it does. Additionally, while you're debugging, you'll want to invoke the tests individually outside of sanity check. You can do this by running the program test with an argument specifying a particular test name. For example, type the command

./test enter

This will run the first test, which attempts to create a single thread and transfer control to that thread. Right now no output is generated, but that will change once you start implementing the Threads class. Each sanity check test displays the command it is running with the test executable.

When you're debugging, you'll also want 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, and that test is implemented by a function with a name such as enter_test. Open test.cc and find the function enter_test. 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_test; it prints an error message, then exits the test application. Right now, neither the Thread constructor nor the Thread::redispatch method do anything; this explains why the test generates no output.

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 the prior one in its 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. Check out this C++ guide/refresher to get up to speed!

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!

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. Here are the core operations that the Thread class provides - this is taken from the thread.hh file.


/* Thread constructor - initializes a new thread that will run
 * the specified function (which must take in no arguments and
 * return nothing).  This initializes all needed internal state,
 * and then adds the thread to the back of the ready queue.
 * If `main` returns, the thread is terminated just as if it had 
 * invoked `Thread::exit`.
 */
Thread(std::function<void()> main);

/* Schedules a thread to run when the CPU is available by adding
 * it to the back of the ready queue.  (The thread should be
 * ready, and not blocked, when this function is called.)
 */
void schedule();

/* Stop executing the current thread and switch to the next ready
 * thread. The caller must make sure that the current thread has
 * been scheduled or kept track of in some other way before calling
 * this; otherwise it will never run again.  Must be invoked 
 * with interrupts disabled.  If there are no more ready threads,
 * this method terminates the entire program by calling
 * std::exit(0).
 */
static void redispatch();

/* Schedules the current thread by calling schedule() on the 
 * current thread, and then switches to the next scheduled 
 * thread by calling redispatch(). The current thread remains 
 * ready, but other threads get a chance to execute.
 */
static void yield();

/* Returns a pointer to the currently-running thread, or 
 * nullptr if no thread is currently running.
 */
static Thread *current();

/* This terminates/deletes the current running thread and then
 * continues running the next ready thread (if any).  It never 
 * fully returns, because as part of its implementation it 
 * cleans up the current thread and then switch to another thread, 
 * which will never switch back to the current (deleted) one.
 */
[[noreturn]] static void exit();

/* Initializes preemptive threading.  If this function is called
 * once at the start of the program, it then preempts the
 * currently running thread every usec microseconds.  If this
 * method is not called, then your dispatcher should be 
 * non-preemptive (threads run until they either yield or exit).
 */
static void preempt_init(std::uint64_t usec = 100'000);

Note: an std::function<void()> is a variable type representing a function that takes no arguments and returns nothing.

Some of these methods are instance methods, like we've seen before, which you can call on a specific Thread, like this:

Thread myThread(...);
myThread.schedule();

Other methods are static methods; these are labeled static and aren't called on a specific Thread, but rather using the class, like this:

Thread myThread(...);
...
Thread::yield();  // yield to the next ready thread

See our C++ guide for more info on static methods.

Each thread will have its own stack, and we have created a class Stack to help you manage the stack 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 (from stack.hh):

/* Constructor: initializes the stack so that the first time you
 * switch to it, the function `start` will run from its beginning, 
 * and will be passed the specified thread as its parameter.  start
 * should take one parameter, which is a pointer to the 
 * running thread, and should never return.
 */
Stack(void(*start)(Thread *), Thread *t);

The Stack class also contains the code to do a context switch; the stack_switch function is just like the context_switch function from lecture, except that its parameters are pointers to Stacks instead of Thread references. Additionally, the first parameter can be nullptr - this is useful if we are switching to a thread and no current thread is running (more on this later).

/* This function performs a context switch.  It saves registers on the 
 * current stack, and saves the current stack pointer in current 
 * (only if current is not null). Then loads the stack pointer from 
 * next and restores registers from that stack. When this function 
 * returns, it will return from the last stack_switch call 
 * made on next.
 */
extern "C" void stack_switch(Stack *current, Stack *next);

We have designed the tests so that you can implement Thread in stages, testing each stage before going on to the next. The milestones we recommend are listed below.

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 try and 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)

Milestone 1

In this milestone we will create just enough functionality to create a thread and dispatch it, so that the thread's top-level function starts executing. To do this, we will need to implement the constructor, schedule and redispatch. Don't worry about any of the other methods right now, and don't worry about 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:

  • Spoiler - each thread should have its own stack. However, the stack needs to remain allocated even when the thread itself is deleted (you'll see why in a future milestone), and therefore the stack must be a pointer to a Stack allocated on the heap with new. Don't worry about freeing it for now. See our C++ guide for a refresher on heap allocation!
  • Spoiler #2 - if you need to save a thread's std::function as an instance variable, you can't initialize it using = in the constructor; you must initialize it using an initialization list. See our C++ guide for info on initialization lists.
  • 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, 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().
  • To implement schedule, you should use the provided ready queue called ready_ in the starter code. Use any 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, 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

In this milestone, we will implement functionality to rotate execution between several threads. To do this, we will need to implement the current and yield methods, and make updates to redispatch to switch from one thread to another.

  • To implement the current() method, the Thread class must keep track of the current running thread. Consider where this state should be updated or used in different methods. See our C++ guide for information on static variables!
  • yield should reschedule the current running thread and then context switch to the next ready thread.
  • We must revisit our redispatch implementation from milestone 1, since now in addition to switching from no thread to a thread, we are switching from one thread to another. Therefore, now the first parameter to stack_switch should be either nullptr if there is no current thread running, and otherwise it should be the current thread's stack. One other requirement is that redispatch should first check if the ready queue is empty, and if it is it should call std::exit(0) to terminate the entire 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 project.

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

Milestone 3

In this milestone, we will implement functionality for threads to exit/terminate. To do this, we will need to implement Thread::exit, which threads call to exit. We will also need to make a small change to thread_start.

  • So far, thread_start has just called the thread's main function. One way for that thread to terminate is if it itself calls Thread::exit(). However, another way a thread can exit is for its main function to return. When this happens, control will pass back to thread_start; make sure to call Thread::exit() to terminate the thread.
  • Thread::exit() should delete the current thread using delete, 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, this isn't safe, because Thread::exit() is actually running on the Thread's stack at that very moment! And it will continue to do so until it switches to another thread. So if we delete the current thread's stack now, then Thread::exit() won't be able to continue running. The solution is to delete the current thread, but not delete its stack until the next thread is deleted (at which point we know the old thread can't still be running). So when each thread exits, it deletes the Stack from the previous thread and saves its Stack for the next 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

So far, our dispatcher is non-preemptive; threads can run as long as they'd like, and switch between each other only by calling yield(). In this last milestone, we will add preemption to switch between threads using a round-robin scheduling mechanism with time slices.

To do this, we must implement preempt_init to initialize the timer, and ensure we properly handle interrupts throughout the Thread methods. (note: interrupts are initially enabled.)

The provided timer.hh file is the same timer as seen in lecture - specifically, we can initialize timer interrupts with the following function:

// Invoke handler (with interrupts disabled) every usec microseconds.
void timer_init(std::uint64_t usec, std::function<void()> handler);

Consider what function we should call every time slice - as a hint, if you need to pass in the name of one of the Thread methods, you must specify Thread:: before the method name.

We must also guard against interrupts throughout the other Thread methods. To do this, you can call intr_enable(bool on) to turn interrupts on (intr_enable(true)) or off (intr_enable(false)), but the preferred way where possible is to create an IntrGuard; this is a variable type just like unique_lock, but for interrupts. It turns interrupts off when it is created, and when it is destroyed it puts the interrupt state back to what it was before the interrupt guard was created (either on or off):

void myfunc() {
    // assume interrupts enabled initially
    IntrGuard guard; // interrupts disabled here
    ...
    return;
} // interrupts re-enabled

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.

Carefully review the intended behavior of each Thread method to decide when interrupts should be enabled and disabled. Here are a few hints:

  • interrupts can cause problems when we are modifying some state while another thread is modifying/accessing it. Consider what shared state we have in Thread.
  • Remember from lecture that interrupts must be re-enabled when a thread starts up for the first time.
  • redispatch must be called with interrupts disabled.

Once you've written this code, you should be able to pass the last test, preempt, though note that this test doesn't test for properly disabling interrupts; that's something that will require additional reasoning and checking in your code to ensure correctness.

Congratulations, you have a fully-functional thread dispatcher!

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. The following is taken from the sync.hh file:


// This is the constructor for `Mutex` objects. 
// It has no arguments.
Mutex();

/* Locks the `Mutex`. If the `Mutex` is currently locked, 
 * blocks the calling thread until the `Mutex` is unlocked. 
 * If there are multiple blocked threads, they return 
 * from `lock` in FIFO order (in other words, the first 
 * thread to block is the first thread to get the lock). 
 */
void lock();

/* If there are threads waiting to lock the `Mutex`, 
 * passes ownership of the `Mutex` to the first waiting 
 * thread and wakes it up. If there are no threads waiting, 
 * releases the lock.
 */
void unlock();

// Returns true if the lock is held by the current thread, 
// false otherwise
bool mine();

Your implementation should look similar to the single-core implementation discussed in lecture, with two main changes:

  • this implementation must keep track of its owner thread
  • the thread operations (blocking a thread, getting the current 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.

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 in sync.cc. 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 tests mutex_basic, mutex_many_threads and mutex_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; the following is taken from the sync.hh file:


// This is the constructor for `Condition` objects.  
// It takes no arguments.
Condition();

/* Releases the Mutex and blocks the thread until `notify_one` or
 * `notify_all` has been invoked, then reacquires the Mutex. The
 * caller must have locked `m` before calling this method.
 */
void wait(Mutex &m);

/* If any threads are blocked on the condition variable, wakes up 
 * the one that has been blocked the longest. If no threads are 
 * blocked, then this method does nothing. The caller must have 
 * locked the associated Mutex before calling this method.
 */
void notify_one();       

/* Wakes up all of the threads currently blocked on the condition 
 * variable. The caller must have locked the associated Mutex before 
 * calling this method.
 */
void notify_all();

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.

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 in sync.cc. 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 and Grading

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.

Your assignment will be graded using the tests we expose via sanitycheck (note that each test may not be weighted equally), plus manual review for the following:

  • ensuring your program has no race conditions and appropriately enables/disables interrupts
  • ensuring your Mutex and Condition classes are FIFO.
  • Code review for style