Assignment 4: Context Switch

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 abstraction Thread for coroutines (e.g., Application), functions for initializing a Thread's StackPointer, a Dispatcher and Scheduler to manage them, and the low-level functions to start and switch the Context Switch.

In order to be able to address the thread switching everywhere in StuBS, first create a global instance of the Dispatcher for testing purposes. Later on, this is replaced by a global Scheduler instance.

Map of important classes for the fourth assignment

Create several "test programs" (a.k.a. Application) to demonstrate the functionality of your approach. For this purpose, create several instances of Application, and announce them to the Scheduler in using Scheduler::ready(). Similar to previous test programs, each instance shall output a counter value on their own screen position. (You can use a thread's id for this purpose.) Don't forget to test Scheduler::exit() and Scheduler::kill().

You only have 4 KiB of Stack (per core), so try to avoid creating objects on the stack.

Learning Objectives

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

Implementation Notes

For testing, we strongly recommend to work in the following order: Implement Dispatcher and Scheduler only after you have successfully implemented and extensively tested the previous steps (e.g., context_switch). You may disable interrupts for this assignment. This means that only your user threads are running on the core(s) and you don't have to worry about synchronization between thread control flow and the interrupt handler. We will enable Interrupts in in the next assignment.

Further Reading

Low-level Context Switch

During this sub-task, the switch from one thread to another is realized. Start by implementing the context preparation (initialization of the StackPointer) and the Thread, then the context_switch(), context_go(), and trampoline_go() routine in assembly.

Starting the first Thread on the boot core after boot-up (via Thread::go). An application must now contain an endless loop in its Application::action() method. Leaving the boot-up code (main) of our operating system requires special preparation – making it impossible to return back to main. Keep this in mind when writing prepareContext().

When starting a new thread, the first high-level (C++) function to be called should be Thread::kickoff(), with a pointer to the Thread itself as parameter. It leaves level ½ and calls the action method (since this is done in C++, the compiler will generate the code for the vtable lookup).

Make sure to prepare the stack and the context of your new threads correctly. Each instance of Thread must have its own stack Thread::STACK_SIZE of size. You can ensure a proper aligned using alignas(16), or manually adjust the stack pointer in prepareContext().

Create several threads via the Application to test your solution, each of which manually yields the processor to the next thread after a few instructions:



Next, implement the Dispatcher, which provides a nicer interface to the context switching mechanism, and manages the life pointer of the currently active thread. In your test program the thread switch should now be performed by calling the Dispatcher, still with known successor.


Finally, the scheduler should be added, a simple First-Come-First-Served (FCFS) strategy is sufficient here. Threads are enqueued in a Queue (provided in the handout), and the next thread to be scheduled is always the one at the head of the queue. For realizing its policy, the Scheduler uses the mechanism provided by the Dispatcher. Threads now have to be known to the Scheduler (Scheduler::ready) only – it is no longer necessary for threads to be aware of each other when switching cooperatively between threads (Scheduler::resume) since the Scheduler will select the next thread from its queue.

Multicore scheduling

Threads are managed in a single ready list in both OOStuBS and MPStuBS. However, on multicore systems it is possible that different cores access the data structure of the scheduler at the same time. Hence, calls to the Scheduler need to be synchronized in MPStuBS even in the case of cooperative scheduling. In particular, you have to ensure that a thread running on the current core will not be made available for execution prematurely on another core.

Additional Notes for MPStuBS

In principle, it makes sense for MPStuBS to carry out the implementation step-by-step as described above. However, at the beginning it might be a good idea to start scheduling on only one core (the bootstrap processor). You could, for example, comment out ApplicationProcessor::boot() to prevent the system from starting the application processors. After you've verified that this works properly you can also enable scheduling on the remaining application processors. This will greatly simplify debugging.

For this assignment, you should make sure that there always will be enough threads to keep all cores busy. We will take care of coping with idle cores during one of the next assignments. Additionally, you should test the thread switch intensively with different numbers of threads.