Enhance StuBS with a 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, create a global instance of Scheduler in main.cc filled 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 Introduction to Assembler)
Understanding the procedure of thread switching
Distinguish between active and passive objects

Videos (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 requires special preparation. The first high-level (C++) function to be called in each thread 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). 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 performs the context switch and manages the life pointer of the currently active coroutine. In your test program the thread switch should now be performed by the Dispatcher.

Scheduler

Finally, the scheduler should be added (a Queue for the Scheduler is provided in the handout). Register the application and user threads to the scheduler in your test program. It is no longer necessary for threads to know each other, since the Scheduler selects the next thread from its queue.

Guarded Scheduler

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.

Since you have switched the synchronization of activities within StuBS to the prologue/epilogue model in the previous assignment, you can now solve this issue by using a coarse-grained locking strategy: executing the Scheduler on level ½. Introduce a system-call interface GuardedScheduler which encapsulates the calls to Scheduler in a Guarded environment.

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.