Skip to content

12. Scheduler - Preemptive Multitasking

In the previous article, we implemented Cooperative Multitasking where tasks voluntarily yield the CPU. But what if a task misbehaves and never yields? The system would hang.

The solution is Preemptive Multitasking: The OS forcibly switches tasks at regular intervals using interrupts.

How Timer Interrupts Work on Raspberry Pi 4

Before implementing the scheduler, we need to understand how interrupts are delivered to the CPU.

The GICv2 Interrupt Controller

Raspberry Pi 4 uses ARM Generic Interrupt Controller version 2 (GICv2), which is significantly different from earlier Pi models.

The GICv2 has two main components:

1. Distributor (GICD) - Receives interrupt signals from peripherals and timers - Filters, prioritizes, and routes interrupts - Routes to the appropriate CPU Interface

2. CPU Interface (GICC) - One per CPU core - Receives routed interrupts from Distributor - Delivers interrupts to the processor - Provides interrupt acknowledgment and EOI (End of Interrupt)

Memory-Mapped Addresses

On Raspberry Pi 4: - Distributor Base: 0xff841000 - CPU Interface Base: 0xff842000

Initializing the Timer Interrupt

To receive timer interrupts, we must configure:

  1. Distributor (GICD):

    • Enable PPI 27 (ARM Virtual Timer) with GICD_ISENABLER
    • Set priority with GICD_PRIORITYR
    • Set interrupt group (secure/non-secure) with GICD_IGROUPR
    • Enable Distributor with GICD_CTLR

  2. CPU Interface (GICC):

    • Set interrupt priority mask with GICC_PMR
    • Enable CPU Interface with GICC_CTLR

  3. Processor:

    • Enable IRQ in DAIF register
    • Set up exception vector table

Note: ITARGETSR (target processor) is only needed for SPI (Shared Peripheral Interrupts). PPI 27 is a private timer, automatically routed to the local CPU core.

PPI 27: The Virtual Timer

We use PPI 27 (Private Peripheral Interrupt 27), which is the ARM Generic Timer virtual counter. This timer: - Is per-CPU (each core has its own) - Can be programmed to fire at specific intervals - Fires even while CPU is in deep sleep

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
/* Read timer frequency (ticks per second) */
uint64_t freq;
asm volatile("mrs %0, cntfrq_el0" : "=r"(freq));

/* Read current timer value */
uint64_t current;
asm volatile("mrs %0, cntvct_el0" : "=r"(current));

/* Set compare register to trigger in N seconds */
uint64_t compare = current + freq;  // 1 second
asm volatile("msr cntv_cval_el0, %0" ::"r"(compare));

/* Enable the timer */
uint32_t ctrl = 0x1;  // ENABLE bit
asm volatile("msr cntv_ctl_el0, %0" ::"r"(ctrl));

Handling Interrupts

When an interrupt fires:

  1. IRQ Vector (in vectors.S) saves all registers to a pt_regs structure
  2. IRQ Handler reads GICC_IAR to get the interrupt ID
  3. Dispatch based on ID (PPI 27 = timer, etc.)
  4. Context Switch modifies pt_regs to switch to next task
  5. EOI write interrupt ID to GICC_EOIR to acknowledge
  6. Restore loads registers from pt_regs and eret returns to new task

IRQ Context Switching

You cannot call a normal schedule() function from an IRQ handler. The IRQ handler has its own stack and saved registers. To switch tasks from an IRQ, you must:

  1. Save all registers (not just callee-saved) to pt_regs
  2. Copy pt_regs to the current task's PCB
  3. Copy the next task's saved pt_regs back
  4. Return via eret which restores PC and PSTATE
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/* Full context saved during IRQ */
struct pt_regs {
    uint64_t regs[31];  /* x0-x30 */
    uint64_t sp;
    uint64_t pc;        /* elr_el1 - return address */
    uint64_t pstate;    /* spsr_el1 - processor state */
};

void irq_handler_with_regs(struct pt_regs *regs) {
    uint32_t iar = *GICC_IAR;
    uint32_t irq_id = iar & 0x3FF;

    if (irq_id == 27) {
        /* Handle timer interrupt */
        timer_tick_count++;

        /* Reschedule timer for next tick */
        uint64_t freq, current;
        asm volatile("mrs %0, cntfrq_el0" : "=r"(freq));
        asm volatile("mrs %0, cntvct_el0" : "=r"(current));
        asm volatile("msr cntv_cval_el0, %0" :: "r"(current + freq));

        *GICC_EOIR = iar;  /* EOI before context switch */

        /* Switch tasks by modifying pt_regs */
        schedule_from_irq(regs);
    } else {
        *GICC_EOIR = iar;
    }
}

The Concept of Preemption

Preemption means the OS can interrupt a running task and switch to another, even if the task doesn't want to yield.

This is achieved by: 1. Timer Interrupt: Fires at regular intervals (e.g., every second). 2. Scheduler Hook: The interrupt handler calls schedule(). 3. Context Switch: The scheduler saves the current task's state and loads another.

Implementation

1. The pt_regs Structure

First, we need a structure to hold the complete CPU state during an interrupt:

1
2
3
4
5
6
struct pt_regs {
    uint64_t regs[31];  /* x0-x30 */
    uint64_t sp;
    uint64_t pc;        /* elr_el1 */
    uint64_t pstate;    /* spsr_el1 */
};

Each process stores this in its PCB:

1
2
3
4
5
6
struct process {
    struct cpu_context context;     /* For cooperative switching */
    struct pt_regs saved_regs;      /* For preemptive switching */
    int has_irq_context;            /* 1 if saved_regs is valid */
    /* ... */
};

2. IRQ Handler Assembly

The IRQ handler must build pt_regs on the stack and pass it to C:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
irq_el1_handler:
    sub sp, sp, #272            // sizeof(pt_regs)

    // Save x0-x30
    stp x0, x1, [sp, #0]
    stp x2, x3, [sp, #16]
    // ... save all registers ...

    // Save SP, ELR_EL1, SPSR_EL1
    add x21, sp, #272
    str x21, [sp, #248]         // sp
    mrs x21, elr_el1
    str x21, [sp, #256]         // pc
    mrs x21, spsr_el1
    str x21, [sp, #264]         // pstate

    // Call C handler with pt_regs pointer
    mov x0, sp
    bl irq_handler_with_regs

    // Restore SPSR and ELR (may have changed!)
    ldr x21, [sp, #264]
    msr spsr_el1, x21
    ldr x21, [sp, #256]
    msr elr_el1, x21

    // Restore all registers
    ldp x0, x1, [sp, #0]
    // ...

    add sp, sp, #272
    eret  // Return to (possibly different) task

3. schedule_from_irq

This is the key function that switches tasks by modifying pt_regs:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
void schedule_from_irq(struct pt_regs *regs) {
    if (current_process->preempt_count > 0) {
        return;  /* Preemption disabled */
    }

    int next_pid = (current_process->pid + 1) % num_processes;
    if (next_pid == current_process->pid) {
        return;  /* Only one task */
    }

    struct process* prev = current_process;
    struct process* next = &procs[next_pid];

    /* Save current task's context */
    for (int i = 0; i < 31; i++) {
        prev->saved_regs.regs[i] = regs->regs[i];
    }
    prev->saved_regs.sp = regs->sp;
    prev->saved_regs.pc = regs->pc;
    prev->saved_regs.pstate = regs->pstate;
    prev->has_irq_context = 1;

    /* Load next task's context */
    if (next->has_irq_context) {
        /* Resume interrupted task */
        for (int i = 0; i < 31; i++) {
            regs->regs[i] = next->saved_regs.regs[i];
        }
        regs->sp = next->saved_regs.sp;
        regs->pc = next->saved_regs.pc;
        regs->pstate = next->saved_regs.pstate;
    } else {
        /* First time running this task */
        for (int i = 0; i < 31; i++) {
            regs->regs[i] = 0;
        }
        regs->sp = next->context.sp;
        regs->pc = next->context.pc;
        regs->pstate = 0x345;  /* EL1h, IRQ enabled! */
    }

    current_process = next;
}

Critical: pstate Value

When starting a new task, pstate must be 0x345 (not 0x3C5):

  • 0x3C5 = EL1h + IRQ masked → Task runs but no more interrupts!
  • 0x345 = EL1h + IRQ enabled → Timer keeps firing, preemption works

The difference is bit 7 (I bit): 0 = IRQ enabled, 1 = IRQ masked.

4. Preemption Control

But there's a problem: What if the scheduler itself gets interrupted while switching tasks? This would corrupt the process state.

We need a way to disable preemption during critical sections:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
void preempt_disable(void) {
    current_process->preempt_count++;
}

void preempt_enable(void) {
    current_process->preempt_count--;
}

void schedule(void) {
    /* Check if preemption is disabled */
    if (current_process->preempt_count > 0) {
        return;  // Don't switch
    }

    // ... do context switch ...
}

5. The Demo

In examples/12_scheduler_demo.c, we create tasks that never call schedule():

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void task_a(void) {
    while (1) {
        kprint("A");
        for (volatile int i = 0; i < 1000000; i++);
    }
}

void kernel_main(void) {
    /* Initialize subsystems */
    memory_init();
    process_init();
    interrupt_init();

    /* Create tasks */
    create_process(task_a);
    create_process(task_b);
    create_process(task_c);

    /* Start timer and enable interrupts */
    timer_interrupt_init();
    timer_interrupt_enable();
    enable_irq();

    /* Idle loop - timer will switch to tasks */
    while (1) {
        asm volatile("wfi");  /* Wait For Interrupt */
    }
}

Building and Testing

1. Build

1
2
3
cd os-rasp/build
cmake -DBUILD_EXAMPLES=ON ..
make

2. Deploy

Copy scheduler_demo.img to SD card (rename to kernel8.img).

3. Expected Output

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Scheduler Demo
==============
Memory initialized. Heap start: OK
Process subsystem initialized.
[GIC] Initialization complete - ready for timer interrupts
[IRQ] Vector table installed
Creating tasks (A, B, C)...
Enabling Timer Interrupt (1 Hz)...
[Timer] Frequency = 54000000 Hz
Starting preemptive multitasking...
Tasks will be switched by timer interrupt.

Idle task running, waiting for timer interrupt...
[IRQ] Handler called! IAR=27
[TICK] 1
AAA[IRQ] Handler called! IAR=27
[TICK] 2
BBB[IRQ] Handler called! IAR=27
[TICK] 3
CCC[IRQ] Handler called! IAR=27
[TICK] 4
[IRQ] Handler called! IAR=27
[TICK] 5
AAA...

Tasks switch every second automatically - true preemptive multitasking!

Time Slicing

Currently, our timer fires at 1 Hz (once per second), which is very slow. In a real OS, you'd want 100 Hz or 1000 Hz for smooth multitasking.

To change the frequency, modify timer_interrupt_init() in kernel/interrupts.c:

1
uint64_t compare = current + (freq / 100);  // 100 Hz = 10ms time slice

What's Next?

We now have a true time-sharing operating system! Multiple tasks run concurrently, and the OS ensures fair CPU time.

The next logical steps are: - Synchronization Primitives (Mutexes, Semaphores) to coordinate between tasks. - System Calls to allow user programs to request OS services. - File Systems to persist data.

At this stage, the kernel can schedule processes using timer interrupts. Test task switching and the failure cases described above before adding more kernel features.

Donate