Project 2: Thread Dispatcher

In this project you will implement a simple threading library in C++. This package will use a single system thread to implement multiple application-level threads, in the same way that an operating system running on a single-core system would use that core to implement multiple system threads.

Basic APIs

You will create a C++ class Thread with the following methods. Note that all of the methods except schedule are static:

void Thread::create(std::function<void()> main, size_t stack_size)
Creates a new thread that will invoke main as its top-level function. The stack_size argument gives the desired size of the stack for the thread, in bytes, and defaults to 8192. The new thread will be added to the ready queue, so the dispatcher will eventually execute it. If main returns, the thread will exit. Storage for the new thread is owned by the Thread class and will be released when the thread exits. This is a static method.

void schedule()
Adds the thread to the back of the ready queue; the thread must not currently be on the ready queue.

void Thread::exit()
Terminate the current thread and destroy the Thread object. This is a static method.

void Thread::swtch()
Dispatches the next ready thread without rescheduling the current thread; the current thread will block unless schedule was invoked for it. Must be invoked with interrupts disabled. This is a static method. In case you are wondering, this method is called swtch because switch is a reserved word in C++.

void Thread::yield()
Invokes schedule() on the current thread, followed by swtch(): the current thread will remain ready, but other threads will get a chance to execute. This is a static method.

Thread(nullptr)
This is a private special-case constructor invoked during startup to create a Thread around the existing stack of the initial system thread in which ::main was invoked. There is no public constructor for Threads: applications will use Thread::create to create threads.

Stack Management

The starter repo provides you with two functions to help you manage stacks and context switching:

sp_t stack_init(void *stack, size_t bytes, void(*start)())
This function will initialize a stack so that the function start will be invoked the next time stack_switch is called to activate the stack. The stack consists of bytes bytes of memory starting at stack; the caller is responsible for allocating (and freeing) this memory. The return value is the initial stack pointer with which the thread should begin its execution; this value should eventually be passed to stack_switch. sp_t is an integer type that is the size of the stack pointer register.

void stack_switch(sp_t *prev_sp, sp_t *next_sp)
This function performs a context switch: it will save registers on the current stack, save the current stack pointer in the word given by prev_sp, switch to the stack pointer in the word indicated by next_sp, and restore the registers saved on that stack. When the function returns, it will be executing on the new stack. Note: it is fine for prev_sp and next_sp to point to the same location.

Both of these functions are pretty simple; if you’re curious, check out the code in stack_init.cc and stack_switch.cc in the starter repo.

Preemption and Interrupts

In addition to implementing the Thread methods above, which provide a non-preemptive dispatcher, you must also implement preemption (time slices) using timer interrupts and a simple round-robin scheduling discipline. You must implement the following static method:

Thread::preempt_init(std::uint64_t slice_usec)
This method will be invoked once, during initialization, if preemption is desired. The slice_usec argument indicates how long time slices should be, in microseconds.

Your implementation of preemption should use the following function, provided by the starter repo, to generate timer interrupts:

void timer_init(std::uint64_t usec, std::function<void()> handler)
This function will arrange for timer interrupts to occur every usec microseconds (unless interrupts are disabled as described below). During each timer interrupt, handler will be invoked.

The starter repo 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 repo also defines an IntrGuard class, analagous to std::lock_guard. When an IntrGuardobject is constructed, the current interrupt 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.

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.

Developing and Testing

To get started on this project, login to the myth cluster and clone the starter repo with this command:

git clone https://web.stanford.edu/class/cs111/starters/threads.git cs111_p2

This will create a new directory cs111_p2. Do your work for the project in this directory (you will also use this directory for Project 4, so it contains a few files that you won’t need for this project). The files thread.h and thread.cc contain a skeleton for all of the code you need to write. Add to the declarations in thread.h and fill in the bodies of the methods in thread.cc to implement the facilities described above.

The directory also contains a Makefile; if you type make, it will compile your code along with a test program, creating an executable test. You can then invoke

./run_tests thread_tests

which will run a simple set of tests on your code. You can also invoke test with an argument specifying a particular test name; this will run a single test and print out its results. For example,

./test yield

will run a simple test with two threads that yield back and forth a couple of times, printing information so you can see what’s happening; this is a good test to start with. Then try the block and preempt tests to test additional features. Invoke test with no arguments to print out all of the available test names. It will probably be useful to look at the code in test.cc so you can exactly what each test does.

We do not 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).

Miscellaneous Notes

Submitting Your Work

To submit your solution, cd to the directory containing your work and invoke the command

./submit

If you discover problems or improvements after you have submitted, you may resubmit; only the latest submit will be graded.