Interrupt handling in StuBS after Assignment 2 can not 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 acquisition can also add 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 therefore now be switched to the prologue/epilogue model. In this model, the interrupt service routines (prologues) are still not interruptable but 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).

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

Map of important classes for the third assignment

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. Normal execution can of course be interrupted by both.

Code running on level 1 (prologue) is never interrupted, but several processors can be on level 1 simultaneously.
Code running on level 0 (normal execution) can be interrupted and is also executed by several processors 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 ½.

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

Learning Objectives

Protection of critical sections using the prologue/epilogue model

Characteristics

The Prologue (Gate::prologue)

The prologue is called on external interrupts directly from 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 minimal prologues reduces the interrupt latency throughout the system.
Immediately after the prologue, the LAPIC is informed that the latency-critical ISR has finished.
If necessary, a prologue requests an epilogue.

The Epilogue (Gate::epilogue)

The epilogue is executed after the prologue and is its causal consequence. It may, however, need to be enqueued first and then be executed asynchronously later.
- 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.
- A Gate object can be enqueued in multiple core-local queues. To allow the Queue to be implemented without heap allocations, each Gate should have a queue_link field (per core), and the Gate needs to befriend the Queue to allow it to access that field.
At level ½, interrupts are active by default. Hence, prologues can occur.
The system synchronizes the execution of epilogues on level ½. This means that there is only one control flow at level ½ at any time (across CPUs).
Epilogues are executed greedily: If an epilogue can be executed, it will be executed. Level ½ will never be left if there are still epilogues left in the queue (per core).

Normal control flow can also enter level ½ at will for synchronization of shared data structures. In this case, the rules above apply as well.

The class Guard

The class Guard has three important methods:

Guard::enter() is called from normal execution (level 0) only. It brings the processor to level ½, where it ensures that no other epilogue-level code is running (on any core) before resuming.
Guard::relay() is called after a prologue requested the execution of its epilogue (so relay enters level ½ from level 1). It may only return (to level 1) when the epilogue queue is empty (and the requested epilogue has been executed).
Guard::leave() is called by (non-prologue) level ½ code only. It executes all queued epilogues and, once the queue is empty, drops back to level 0.

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

Excursus: In a program with heap allocation (that is, not in StuBS), a typical use of RAII are smart pointers, as implemented by the STL (C++ standard template library). Here, the existence of an object on the heap (which may hold any other resource) is bound to the existence of at least one (smart) pointer to it. Once the last pointer goes out of scope, is freed/deleted, or otherwise destroyed, the heap-object is deleted (and thus destroyed) as well. The resource therefore can't outlive the last reference to it, preventing resource leaks. (Cyclic references can be a problem, but that won't happen when only using the stack.)

void foobar() {
    // some calculations
    {
        Guarded _;  // Constructor enters level 1/2
 
        // can access shared data structure
 
        // ... for/do/while/if ... break/return(/throw)((/goto)) ...
        // in all cases: destructor is called implicitly and leaves level 1/2
    }
    // maybe more code
}

Handout

You don't have to write your own Queue, we are including a Queue implementation in the handouts. Each gate is extended to have Core::MAX pointers to the next Gate object in the queues. Remember, there is a queue for each processor core. The Queue object takes a parameter for an index into the array of next-pointers.

Implementation Notes

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 be guarded using only the prologue/epilogue model, hence making the Core::Interrupt::disable() and Core::Interrupt::enable() calls and the lock (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.