Module rstubs::assignments::a3_int_sync

BSB - A3: Interrupt Synchronization using Prologue/Epilogue

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 handling other interrupts. Therefore, interrupt service routines should be as short as possible. In the multicore case, lock acquisition 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 block interrupts manually, making it error-prone.

The synchronization of activities within StuBS should now be changed 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.

By introducing the epilogues, we add a third level (level ½) between level 1 (prologue) and level 0 (normal execution). 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.

                           interrupt  relay()      iret
Level 1:                           X====x      +====|
Parallel                           .    |      |    .
----------------------------------------|------|------------
                        leave()    .    |      |    .
Level ½:            +------+       .    +------+    .
Sequential          |      |       .        leave() .
--------------------|------|--------------------------------
                    |      |       .                .
Level 0:  App ======+      +=======|................|=======
Parallel          enter()

• 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 sequentially (not parallel) and must wait until the previous one finishes. The Guard needs to busy-wait to serialize execution on level ½.

It might still be necessary to disable interrupts (hard synchronization) for a few instructions when accessing shared data structures (like the epilogue queues).

The Guard

The prologue is executed directly in the interrupt service routine, and the Epilogue is deferred and executed by the Guard. Do not forget to notify the LApic and activate interrupts before deferring Epilogues.

The Guard implements the following functions:

• Guard::enter(): enter the critical section (level ½).
• Guard::leave(): execute the remaining Epilogues from the local list and leave the critical section (level ½).
• Guard::relay(): register the given epilogue to be either executed directly or enqueued for later execution.

The Guard is a singleton that is stored in GUARD. It contains a single global lock, for which you can use the Ticket lock from the previous assignment.

Each core has its own Epilogue list, together with a flag indicating whether the Guard is already locked by this CPU. In this case, Guard::relay() should enqueue the epilogue into the local list. If the current CPU does not lock the Guard, it can enter it (by taking the global lock) and execute the Epilogue directly.

For critical sections, level 0 can enter the guard. Like locks, the guard is unlocked when it goes out of scope. Critical sections are serialized and can be interrupted by level 1 but not by level 0.

use crate::interrupts::guard::GUARD;
{
    let guarded = GUARD.lock();
    // critical section
    // ...
} // <- guard is unlocked

In the following assignments, we will protect different kernel objects with the Guard, by putting them into Guarded. They can then only be accessed while the Guard is locked.

• Your test application should be pretty similar to the one from assignment 2: Again, it should output the value of its increasing counters on the main window, while keyboard Epilogue has a separate line for keystrokes.
• The critical section should only be guarded by the prologue/epilogue model, making the int::enable() calls and the Spinlock superfluous – remove them.
• Since interrupts are automatically disabled in interrupt_handler(), they must be enabled manually at a suitable point (before processing epilogues).
• We recommend using a Ticketlock to synchronize the cores. Due to the memory model, some cores might starve when using Spinlock.