Instead of cooperative scheduling, the Scheduler in StuBS should be able to preempt threads – triggered by a timer interrupt.

There are several different timers available on the x86 platform, Programmable Interval Timer (PIT), "Real Time Clock (RTC)", "Time Stamp Counter (TSC)" and "High-Precision Event Timer (HPET)" to name just a few, but the LAPIC::Timer (located on each core) is suited best for our approach.

Map of important classes for the fifth assignment

The Watch device will be triggered on every LAPIC timer interrupt, and instructs the Scheduler to switch threads. The Scheduler will be wrapped into a GuardedScheduler, which is the system call interface used by the application threads when they need to interact with the scheduler. Remember to set a proper state of the Guard during OS initialization. The Assassin (in MPStuBS) is used to kill threads running on a different CPU.

Learning Objectives

Configure and program timers via a low-level interface
Implementation of preemptive scheduling by timer interrupts

Implementation

First of all, ensure your Guard::enter() and Guard::leave() functions use a assert() upon function entry. This way your OS stops execution if your epilogue lock is alreadys taken (Guard::enter()), or already released (Guard::leave()).

We recommend the following order to allow good separate testing of the individual parts:

Set-up the LAPIC timer (Use debug outputs to verify your calibration) in Watch::windup(), and call it upon OS init.

Enable, and catch LAPIC timer interrupts. You could use the following snippet in Watch::prologue():

static int direction = 0;
static char handle[4] = {'/', '-', '\\', '|'};
static int tick = 0;

// Every 250 ticks turn the clock hand (in the upper right corner) a little further.
// With an interrupt frequency of 1000 Hertz (1ms) it moves half a turn every second (i.e. same character).
tick = (tick + 1) % 250;
if (tick == 1) {
        direction = (direction + 1) % 4;
        TextWindow::show(-1, 0, handle[direction], TextWindow::Attribute(TextWindow::RED));
}

Switch to preemptive scheduling
Scheduler::kill as Inter-Processor Interrupt (IPI) in MPStuBS

Preemptive Scheduling

For implementing preemptive context switching, we'll need a periodic interrupt that interrupts the currently running thread and gives the control of the corresponding Core to the Operating System. It will then reschedule and switch to a different thread.

LAPIC Timer

This timer is located in each core and has the ability to trigger interrupts. Implement LAPIC::Timer::set() to configure the timer. All LAPIC timers run at the (same) APIC bus frequency. However, we do not know the actual value of the frequency. It can vary from platform to platform. Therefore, you have to calibrate it using the PIT (which runs on a well defined frequency) in LAPIC::Timer::ticks() – try to be as precise as possible!

First, generate and catch the timer interrupt. Be as precise as possible when setting the frequency of the interrupt. You can use a test output in the interrupt handler to verify that sending and catching the timer interrupt works reliably. Make sure that your code will work with high timer intervals (e.g., 5 seconds), but demonstrate your implementation with several threads and a (re-scheduling) interval of 10ms. (You can try an interval of 1ms.)

Preemption

With a periodic interrupt from the timer, the scheduling system can be switched over to a preemptive one. From now on, you'll need to think twice when to use the normal Scheduler object and when the Guarded (GuardedScheduler) version needs to be used.

Explicit synchronization in MPStuBS in the Scheduler needs to be removed, because it's now guarded by the GuardedScheduler.

The Watch is the device driver implementation for the timer. Here, you should take care of rescheduling threads on each interrupt.

MPStuBS

If a thread gets terminated using Scheduler::kill(), it should stop immediately instead of waiting for its time slice to end like we did in assignment 4. With enabled interrupts, this requires special treatment on MPStuBS. If the respective thread is currently running on another core, its execution has to be interrupted by an Inter-Processor Interrupt (IPI). The method LAPIC::IPI::send() enables you to send such interrupts to other cores with the help of the LAPIC, either direct or as broadcast. The Assassin implements the handling of this Kill-IPI.