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 Thread
s: 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 IntrGuard
object 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
- It is not safe to use the
main
argument to theThread
constructor as thestart
argument tostack_init
: if you did this andmain
returned, it would run off the top of the thread’s stack without invokingThread::exit
. In addition,main
is a function object that might contain additional state for starting the thread, whilestart
is a simple C function with no arguments. - When
Thread::exit
is invoked, it is not safe to delete the thread’s stack, becauseThread::exit
is currently using that stack. You must delay freeing the stack until some later time when you can be certain that the stack is no longer in use. - The
Thread
class does not have a public destructor: the only way to delete a thread is for it to invokeThread::exit
. - You may assume that your code will only run on single-core systems, so disabling interrupts ensures that no other thread will run.
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.