Enhance StuBS with simple thread management, where user threads voluntarily yield control of the core according to the coroutine concept.

You have to implement the Thread class, low level functions for handling the Context Switch of a thread, and the Scheduler and Dispatcher classes, which provide the scheduling policy and the dispatching mechanism, respectively.

It's recommended to split the task in three parts:

First implement the low level context switching mechanism,
then implement Dispatcher as an abstraction layer and interface,
lastly implement Scheduler, which realizes the policy by which threads are selected to run.

It is strongly recommended to test each step thoroughly and only begin the next step when the previous one is working as expected. Disable interrupts for the time being, and ignore synchronization between interrupt service routines and the normal control flow.

Map of important classes for the fourth assignment

Learning Objectives

Refreshing your assembler knowledge (see also Introduction to Assembler)
Understanding the procedure of thread switching
Distinguishing between active and passive objects

Cooperative Context Switch

The general procedure of a context switch is shown below.

A running Thread 1 can call Scheduler::resume. The scheduler chooses the next thread and calls Dispatcher::dispatch, which in turn calls Thread::resume, finally calling context_switch. (The intermediate calls have been omitted in the figure for clarity.)

The context_switch function changes the context of the thread so that it returns into the next thread (Thread 2). Which again returns from Thread::resume, Dispatcher::dispatch, and Scheduler::resume and continues execution. From the processors perspective, the execution thus returns to a different location that that of the last call.

In this assignment, we start with the most basic function: context_switch.

(1) Low-level Context Switch

We want to achieve that context_switch, called by the current thread, returns to the next thread. Consequently, it has two parameters: the CPU execution Context for the current and the next threads. However, not all registers have to be saved, why? One of the registers that needs to be saved is the stack pointer (RSP), which contains a return address that is jumped to when context_switch returns. So, if you change the RSP, you also change the return address to one of the next thread, and the compiler will restore any callee-saved registers automatically.

To implement context_switch, you need a bit of inline assembly to save and restore the CPU state of a thread. However, you only need mov and ret instructions for this.

There are different types of mov:

Direct: mov rax, rsp: rax = rsp;

Indirect: mov rax, [rsp]: rax = *rsp;, Dereferences pointer in RSP

Direct: mov rax, [rsp+4]: rax = *(rsp + 4);, Add and dereference

Also, implement the context_launch function. It only loads the new context (without saving the current one) and is called when the scheduling starts. As this is very similar to context_switch, you could do a small trick and reuse (not copy) the same assembly code.

Initial Kickoff

Switching to a new thread for the first time requires some preparation. The switch function operates by modifying CPU registers, including the stack pointer (RSP), and then returns. This return pops the return address from the (now changed) stack and jumps to it. This also has to work for new newly created threads. Here, we ultimately need to jump to Thread::kickoff, which will call the thread's action function. To accomplish this, we "fake" (prepareContext) the stack of new threads, placing the address of Thread::kickoff as the return address on the stack.

However, there's a complication: the kickoff function requires arguments in specific registers (RDI, RSI, RDX, etc.) according to the System V ABI. To handle this, we recommend storing these arguments in the Context registers first. When the thread starts, these registers will be loaded by context_switch or context_launch. To ensure the arguments are placed (mov) in the correct registers, implement the fake_systemv_abi function. This function should execute first for a new thread and then return into Thread::kickoff. Thus, we additionally need to put the address of Thread::kickoff into the stack (in prepareContext).

For testing purposes, create several threads, which all call context_switch after a few lines of code to switch to the next thread. Hardcode the successor threads for these tests and turn off interrupts for debugging. With breakpoints (or stepping), you can observe how the context switch works.

(2) Thread / Dispatcher

Next, implement the remainder of the Thread class, which combines a thread's CPU context with some other application execution state, and the Dispatcher, which is responsible for dispatching threads. For this, the dispatcher needs to remember the currently active thread, on which it calls Thread::go / Thread::resume, which in turn call context_launch or context_switch.

In your test program, the thread switch should now be performed by calling the Dispatcher, still with known successor.

(3) Scheduler

Finally, the scheduler should be added. It is responsible for deciding who gets dispatched next. A simple First-Come-First-Served (FCFS) strategy, implemented with a Queue of Threads ready to be executed, is sufficient. Consequently, the application code no longer needs to know the thread to resume to.

The Scheduler::resume function is the heart of the scheduler. It is called by a thread to yield control and resume the next thread (Scheduler::getNext). Additionally, it has to decide whether to reschedule (Scheduler::ready) the current thread. This depends on the ready argument. If false, the thread will not be enqueued again. Similarly, if a thread has exited, it also should not be added to the ready list.

Thread creation is done by statically initializing threads as global variables, and then adding them (Scheduler::ready) to the scheduler, placing them into the ready list. The thread stacks should also be statically allocated from the system image (e.g. a large global array). This is possible because we have a fixed limit of supported threads which you have to define. Keep in mind that you need at least one active thread per core (idling is part of a future assignment).

The initial start of the scheduler is done with the Scheduler::schedule function on each CPU core. This function does not return to the caller, but instead calls the first thread's action function (see Initial Kickoff).

Synchronization (MPStuBS)

On multicore systems, different cores may access the data structures of the scheduler at the same time. Therefore, calls to the Scheduler need to be synchronized in MPStuBS, even in the case of cooperative scheduling. In particular, you must ensure that a thread running on the current core will not be made available for execution prematurely on another core. Therefore, we put the scheduler into the Vault, which is designed to protect kernel objects.

Now, before calling resume, an app has to enter the guard and leave afterward. But what about the first start of an app? During the context switch, the scheduler was locked (either by the previous thread or the main function that starts the scheduler). Consequently, the new thread has to leave the guard when it starts execution. A good point for that would be the Thread::kickoff function, which could Guard::leave before calling Thread::action.

Notes

In assignment 4, we always assume that there are enough threads in the system, ready to be executed, so the ready-list should never run empty. Make sure that this assumption holds in your test system! Test your code intensively with a variable number of threads. In MPStuBS we recommend testing your code on a single core at first, and if that works, switch on scheduling on the others as well.