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.
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.
Adds the thread to the back of the ready queue; the thread must not currently be on the ready queue.
Terminate the current thread and destroy the Thread object. This is a static method.
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
switch is a reserved word in C++.
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.
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.
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
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
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_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:
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:
If the argument is false, defers all interrupts. If the argument is true, enables interrupts and immediately dispatches any deferred interrupts.
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.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
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,
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
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).
- It is not safe to use the
mainargument to the
Threadconstructor as the
stack_init: if you did this and
mainreturned, it would run off the top of the thread’s stack without invoking
Thread::exit. In addition,
mainis a function object that might contain additional state for starting the thread, while
startis a simple C function with no arguments.
Thread::exitis invoked, it is not safe to delete the thread’s stack, because
Thread::exitis 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.
Threadclass does not have a public destructor: the only way to delete a thread is for it to invoke
- 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
If you discover problems or improvements after you have submitted, you may resubmit; only the latest submit will be graded.