Aufgabe 4: Kontextwechsel

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 a test program with several user threads to demonstrate the functionality of your approach. For this purpose, fill Scheduler in main.cc with the user threads, which, similar to previous test programs, each output a counter value on their own screen position. Don't forget to test Scheduler::exit() and Scheduler::kill().

Note: 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 assembler)
Understanding the procedure of thread switching
Distinguish between active and passive objects

Videos (WS21, in German)

Aufrufkonvention (8 min)
Kontextwechsel (11 min)
Aufgabe 4 (12 min)

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.

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() routine in assembly.

Starting the first Thread on the core after boot-up (Thread::go) (i.e., leaving the boot-up code (main) of our operating system) requires special preparation – making it impossible to return back to main.

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.

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

Dispatcher

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.

Scheduler

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). 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.