StuBS
Assignment 5: Time Slice Scheduling

We already have a Prologue-Epilogue model for interrupt handlung and a cooperative thread-switching mechanism and policy with interrupts disabled. Now the coarse grained locking-strategy provided by the Prologue-Epilogue model is to be applied to the threading system and a system call interface is to be defined. Threads will be scheduled in a round-robin manner and preempted with the help of a Timer-Interrupt. We'll use the APIC timer for that.

dot_a5.png
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. The Assassin (in MPStuBS) is used to kill thread, running on a different CPU.

One can split this assignment into 3 parts:

  • Set-up the APIC timer and catch its interrupts
  • Change to preemptive Scheduling
  • Scheduler::kill as Inter-Processor-Interrupt (IPI)

Learning Objectives

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

Preemptive Scheduling

(1) LAPIC Timer

For implementing preemptive context switching, we'll need a periodic interrupt, which interrupts the currently running thread and gives the control of the CPU to the Operating System. We'll use the APIC timer to send periodic timer interrupts. The interrupt enforces that the currently running thread is preempted from the core and the OS regans control. It will then reschedule and switch to a different thread.

First, generate and catch the timer interrupt. Be as precise as possible when setting the frequency of the interrupt. Use a test-output in the interrupt handler for showcasing 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.

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

(3) Killing Threads (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 local APIC, either direct or as broadcast. The Assassin implements the handling of this IPI.

Further Reading