Module a5_time_slice

BSB - A5: Time Slice Scheduling

We already have a Prologue-Epilogue model for interrupt handling and a cooperative thread-switching mechanism and policy. In this assignment, we will apply the coarse-grained locking strategy provided by the Prologue-Epilogue model to the threading system. Threads will be scheduled in a round-robin manner and preempted with the help of a timer interrupt. We need the APIC timer for that.

This assignment requires changes at:

• LApic and idt to handle the timer interrupt.
• Scheduler to implement the round-robin scheduling policy.
• Epilogues for killing running threads.

Learning Objectives

• Configure and program hardware timers
• Implementation of preemptive scheduling

1. LApic Timer

Preemptive scheduling requires a periodic interrupt that interrupts the running thread and gives control of the CPU to the operating system. It then can execute the scheduling logic and perform the thread switch. We will use the LApic timer for this interrupt.

Each CPU-local APIC has a timer. The timer uses a clock generator that produces a periodic signal of a fixed frequency. Usually, quartz crystals are used for this, as they vibrate at a constant frequency when a voltage is applied. The clock signal is then divided by a programmable divider, which allows for the frequency to be reduced. The APIC supports a few divider values, which are powers of two.

           +----+   +----+     +---------------+
        1--|T  Q|   |    |<----| Current Count |
--|[]|-----|>   |---|> -1|---->|               |
 quartz    +----+   +----+     +---------------+
 clock    divider  decrement         ^   |
                                     |   | == 0
                   Initial Count ----+   +---> Interrupt

The resulting frequency is then used to decrement a 32-bit counter. When the counter reaches zero, the APIC sends an interrupt to the CPU. The programmable initial count register sets the counter’s initial value. The timer can be configured to be either one-shot or periodic.

Unfortunately, the frequency of the timer depends on the exact hardware. Consequently, we cannot simply configure it to wait 5ms, for example. Instead, we have to use another standardized timer (e.g., the PIT) first to measure the frequency of our APIC timer. The PIT can be used to wait a specific time, and we can count the number of APIC timer ticks that have passed. These ticks can be used to calculate the correct divider and initial count values for any given number of microseconds. The LApic contains the necessary methods to configure the timer. Also, measure the timer once on the boot core and reuse the result for all other cores.

When implementing the timer, first generate and catch the timer interrupt. Use a test output in the interrupt handler to showcase that sending and catching the timer interrupt works reliably. Ensure 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 50ms.

2. Preemption

With a periodic timer interrupt, we can now implement the preemption logic. Luckily, we already have a cooperative thread-switching mechanism in place, and we can reuse the Scheduler::resume() function.

Implement a new Epilogue that calls Scheduler::resume() if a thread is running. This epilogue is to be enqueued when a timer interrupt occurs.

Guard::enter() now must temporarily disable interrupts while checking the local active flag. Otherwise, the thread might be rescheduled to another CPU during this check.

3. Killing Threads

If a thread is killed (Scheduler::kill()), it should be stopped immediately. This includes removing it from the scheduler ready list or stopping it if it is currently running. The first is relatively straightforward, but the second requires inter-processor communication. The LApic::send() provides a way to send an Inter-Processor Interrupt (IPI) to another CPU. When receiving this Assassin IPI, the other CPU should stop the thread and continue with the next one.