Aufgabe 5: Zeitscheiben

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.

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

Videos (WS21, in German)

• Zeitgeber (8 min)
• Aufgabe 5 (12 min)

Implementation Notes

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

1. Set-up the LAPIC timer and catch its interrupts
2. Change to preemptive scheduling
3. Scheduler::kill as Inter-Processor Interrupt (IPI) in MPStuBS
4. Optional timers

Further Reading

• Overview of files and classes
• List of mandatory and voluntary tasks

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

Further Reading

• APIC-Timer Information

Additional Timer (voluntary)

Time Stamp Counter (TSC)

The TSC allows accurate time measurements using an efficient read instruction (rdtsc) and is hence quite popular for benchmarking purposes. However, it has no fixed frequency either – in fact, on older processors like the Pentium 4 it can even vary during runtime depending on the processor's current power state. Modern processors not only have a constant frequency, but also synchronize the values across cores. You can use CPUID (encapsulating the instruction cpuid) to check if your processor supports those features. On some Intel processors, you can even calculate the frequency. However, you have to extend TSC::ticks() with an alternative option for calibration (similar to the LAPIC Timer) to support other processors as well.

This allows you to implement a precise time-based active waiting in TSC::delay() and a conversion of a time delta given in ticks into SI units in TSC::nanoseconds().

Real-Time Clock (RTC)

Do you know what time it is? Your PC does. Not only the time, but the date as well are stored in CMOS registers (non-volatile BIOS memory, usually powered by a battery) since the IBM Personal Computer AT (introduced almost 40 years ago). Consequently, it has been through a lot (like the turn of the millennium – with only two digits for the year), which has left its marks: The values in the registers may be encoded as binary-coded decimal (BCD) or binary values, the time format can be 12h or 24h, you might be able to change it or not, additional fields like the century may be available or not.

Try to deal with all possible formats when implementing RTC, and use DateTime to store those values (which not only offers a formatted output but also a conversion to Unix epoch time).

Note

You have to query several CMOS registers to read date and time – which is quite expensive and, moreover, an update of those registers can happen at exactly this moment. Your solution should be able to detect such a case and keep track of the current time using the Clock device in conjunction with the update interrupt!

High-Precision Event Timers (HPET)

As we have learnt from the previous sections, both the PIT and and RTC are rather old devices. Over the last decades, operating systems grew more complex and their demands regarding measuring time accurately grew with them. Additionally, as you might have experienced yourself while implementing their drivers, both the PIT and the RTC have rather cumbersome interfaces. This is why Intel and Microsoft decided at the beginning of the twenty-first century that it might be a good idea to create a completely new timer suitable for modern needs. The result of their joint work were the High-Precision Event Timers. They are intended to succeed the PIT as well as RTC some time in the future.

If you are interested in how the interaction with the HPET works, you can implement your own HPET driver for StuBS. We recommence to first implement a delay function (to ensure correct handling of the information from ACPI tables) before focusing on the comparators triggering interrupts. For further information take a look at the IA-PC HPET (High Precision Event Timers) Specification.

The example device Ticker increases every 0.1s using HPET interrupts, hence, measuring the uptime of your operating system.