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

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 witht 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 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 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.
After the prologue, the LAPIC is informed that the latency-critical ISR has finished.

The Epilogue (Gate::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.
A Gate object can be enqueued in multiple core-local queues. For this, each Gate has a link field for every CPU.

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 (multi-core only). Guard::leave() executes all queues epilogues and if the queue is empty drop back to level 0. Guard::relay() is called when a prologue requests the execution of the epilogue (so relay enteres 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 cleverly 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.

This could used on a normal operating system for requesting a block of memory in the constructor of an object, which is only needed for the duration of a scope of code. When the scope is left or the function returns, the RAII-object is also freed, the destructor is executed, which frees the requested block of memory. Typical uses in the STL are the Smart-Pointers which couple the life time of the referenced objects to their own using RAII.

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;
}

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