Aufgabe 3: Pro-/Epilog

Interrupt handling in StuBS after Assignment 2 cannot be interrupted by other interrupts. If an interrupt service routine takes a while, it can lead to latency for the handling of other interrupts. Therefore interrupt service routines should be as short as possible. In the multicore case, lock aquisition also adds to the latency, as a core waiting for a lock of another core cannot make any progress. Access to shared data structures between the interrupt handler and normal execution is also problematic, as the programmer needs to manually block interrupts when necessary, making it error prone.

The synchronization of activities within StuBS should now be switched to the prologue/epilogue model. In this model, the interrupt service routines (prologues) are not interruptable and are as short as possible, whereas the deferred longer epilogue can be interrupted by new prologues. Modify your operating system in such a way that synchronization is no longer based solely on disabling interrupts (hard synchronization).

The synchronization of activities within StuBS should be switched to the prologue/epilogue model. Modify your operating system in such a way that synchronization is no longer based solely on interrupt locks (hard synchronization).

For this purpose, you have to implement the Guard (and its wrapper Guarded) which implements level ½. The interrupt_handler and Gate also need to be modified or extended.

Map of important classes for the third assignment

Of course, you also have to adapt your devices (e.g., Keyboard) and application accordingly, using the functions provided by Guard to protect all critical sections in the later case.

In MPStuBS, the Guard not only protects against interrupts, but also locks out other cores using a Ticketlock and thus prevents them from entering the critical section. Locked out cores have to wait actively until its their turn to enter the critical section, hence serializing the processing of critical sections.

Note: It might still be necessary to disable interrupts (hard synchronization) for a few instructions, e.g., when accessing GateQueue (a lock-free queue is not required nor recommended).

Learning Objectives

Protection of critical sections using the prologue/epilogue model

Videos (WS21, in German)

Interruptsynchronisation (6 min)
Aufgabe 3 (5 min)

Characteristics

By introducing the epilogues, a third level (level ½) between level 1 (prologue) and level 0 (normal execution) is added. The prologue handles interrupts with the devices, level ½ handles synchronization with the rest of the system and can be interrupted by level 1, and normal execution can of course be interrupted by both.

Code running on level 0 (normal execution) can be interrupted and is executed by several processors simultaneously.
Code running on level 1 (prologue) is never interrupted, but in MPStuBS several processors can be on level 1 simultaneously.
Code running on level ½ (epilogue and other critical sections) can be interrupted by level 1 and can interrupt level 0.
Epilogues are always executed in a serial fashion. Epilogues are never executed simultaneously on several CPUs and have to wait until the previous one finishes. Guard needs to busy-wait to serialize execution on level ½.

The Prologue

The prologue is called on external interrupts via the interrupt_handler().
The prologue should be as short as possible and only perform the most necessary tasks to handle the hardware which caused the interrupt. It should only share a minimal state with the rest of the system.
Using a prologue reduces interrupt latency throughout the system.
If necessary, a prologue requests an epilogue.

The Epilogue

The epilogue is executed after the prologue and is its causal consequence.
The system synchronizes the execution of epilogues on level ½. This means that there is only one control flow at level ½ at any time.
At level ½, interrupts are always active. Hence, prologues can occur.
Greedy execution of epilogues: If an epilogue can be executed, it will be executed. The level ½ will never be left if there are still epilogues left in the queue.
In MPStuBS, an epilogue is executed on the core where the corresponding prologue has taken place. Hence, each core will have its own epilogue queue. Additionally, in MPStuBS a Gate object can be enqueued in multiple core-local epilogue queues. For this, each Gate has a queue link field for every core.

Normal control flow can also enter level ½ at will for synchronization of shared data structures. For this case, the same assumptions hold.

The class Guard

The class Guard has three important methods:

Guard::enter() is called from normal execution (level 0) only and brings the processor to level ½ if possible or waits until the epilogue-level is free (in MPStuBS only).
Guard::leave() executes all queued epilogues and drops back to level 0 afterwards.
Guard::relay() is called when a prologue requests the execution of the epilogue (so this method enters level ½ from level 1).

The class Guarded and RAII (Resource Acquisition is Initialization)

The Guarded class is a wrapper around the methods of Guard. When the level 0 needs to enter level ½ it can create a new Guarded object on the stack, which is deleted when the scope is left. Using the constructor and destructor of the Guarded class, clever scoping of code to be run on level ½ is possible. This is called RAII (Resource Acquisition is Initialization), where requesting a resource is coupled to the life time of a stack-local object.

int foobar() {
    // some calculations
    {
        Guarded _;  // Constructor enters level 1/2
 
        // accessing a shared data structure
        ...
 
        // destructor is called implicitly and leaves level 1/2
    }
 
    return 0;
}

Implementation Notes

Your GateQueue implementation should be based on a kind of linked list (in MPStuBS, its methods must first determine the proper list, depending on the core it is executed on).
Your test application should be quite similar to the one from assignment 2: Again, it should output the value of its increasing counter (for MPStuBS on each core at different positions) on the main window, while Keyboard::epilogue has a separate line for keystrokes.
The critical section should only be guarded using the prologue/epilogue model, hence making the Core::Interrupt::disable() and Core::Interrupt::enable() calls and the Spinlock (in MPStuBS) superfluous – remove them.
Since interrupts are automatically disabled in interrupt_handler(), they have to be manually enabled at a suitable point (before epilogues are processed).
It's recommended to use a Ticketlock in MPStuBS to synchronize the cores and ensure a fair sequencing – due to the memory model, it is possible that some cores might starve when using Spinlock.

Extend serial interface (optional)

You can also switch the Serial interface to interrupt mode – in this case you should limit yourself to the receive interrupt. This allows you to receive inputs from keyboard and console at the same time, without having to implement non-blocking queries. Furthermore, this allows you to connect to the GDB_Stub anytime during runtime, interrupt the system at will (by pressing Ctrl-c in GDB) and, for example, read out the memory.