Lab 11.1: Round-Robin Scheduler with Context-Switch Measurement

Total points: 25
Estimated time: 4 hours
Prerequisites: Lab 10.1 complete; CLINT wired to CPU; trap handler from Lab 2 extended

Overview

This lab implements a preemptive round-robin scheduler in Virtus OS v2. Two user-mode tasks run concurrently. A CLINT timer interrupt fires every 10 ms and switches between them. You will measure the context-switch cycle cost and verify both tasks advance independently.

Part A: CLINT timer interrupt (8 pts)

A1: Wire CLINT to CPU interrupt inputs (3 pts)

The reference implementation's clint.v module exposes irq_mtip (machine-timer interrupt pending) and irq_msip (machine-software interrupt pending) per hart. Wire these to the CPU:

wire irq_mtip, irq_msip;

clint #(.NUM_HARTS(1)) u_clint (
    .clk(clk),
    .reset_n(reset_n),
    .mtime_lo(mtime_lo),    // expose for kernel reads
    .mtime_hi(mtime_hi),
    .mtimecmp_lo(mtimecmp_lo),  // kernel-writable via MMIO
    .mtimecmp_hi(mtimecmp_hi),
    .irq_mtip(irq_mtip),
    .irq_msip(irq_msip),
    // ... MMIO bus connections ...
);

Map the CLINT registers to the physical address range 0x02000000-0x0200BFFF in your memory decoder.

A2: Timer interrupt delivery in the CPU (3 pts)

In the CPU's execute stage, add interrupt delivery logic:

// After every instruction, check for pending interrupts
if (mstatus.MIE && mip.MTIP && mie.MTIE) begin
    // deliver timer interrupt: same trap mechanism as ECALL
    // but cause = 0x80000007 (interrupt bit set, cause 7)
    trap_cause <= 32'h80000007;
    mepc <= pc_current;         // save current PC (NOT pc+4)
    mstatus.MPIE <= mstatus.MIE;
    mstatus.MIE <= 0;
    mstatus.MPP <= priv;
    priv <= M_MODE;
    pc <= mtvec;                // jump to trap vector
end

Unlike ECALL, the interrupted instruction's PC is saved to mepc (not mepc+4); when MRET returns from the interrupt, it resumes at the interrupted instruction.

A3: Kernel timer setup (2 pts)

In the kernel boot code, after setting up the trap handler:

# enable machine-timer interrupts
li      t0, (1 << 7)           # MTIE bit
csrs    mie, t0
# set first timer deadline: now + 500000 cycles (10ms @ 50MHz)
li      t0, 500000
li      t1, -1
sw      t1, CLINT_MTIMECMP_LO  # push deadline far future
sw      x0, CLINT_MTIMECMP_HI  # clear hi
sw      t0, CLINT_MTIMECMP_LO  # set actual deadline
# enable global interrupts
li      t0, (1 << 3)           # MIE bit in mstatus
csrs    mstatus, t0

Verify: the timer fires after 500,000 cycles. Add a counter in the trap handler that increments on each timer interrupt; verify it increments at roughly 100 Hz (10 ms interval).

Part B: Process control block and context switch (10 pts)

B1: Define the PCB structure (2 pts)

#define MAX_PROCS 4
#define PCB_SIZE  (32*4 + 4 + 4 + 4 + 4 + 4 + 4 + 4)  // regs + pc + satp + mstatus + state + pid + stk_base + stk_size

typedef struct {
    uint32_t regs[32];     // x0-x31
    uint32_t pc;
    uint32_t satp;
    uint32_t mstatus;
    uint32_t state;        // 0=EMPTY, 1=READY, 2=RUNNING, 3=BLOCKED
    uint32_t pid;
    uint32_t stack_base;
    uint32_t stack_size;
} pcb_t;

pcb_t process_table[MAX_PROCS];
uint32_t current_pid = 0;

B2: Context switch in timer interrupt handler (5 pts)

Extend the trap handler (from Lab 2) to handle mcause = 0x80000007 (timer interrupt):

void trap_dispatch(uint32_t cause, uint32_t trap_frame_addr) {
    if (cause == 11 || cause == 8) {
        // ECALL: existing handler
        handle_ecall(trap_frame_addr);
    } else if (cause == 0x80000007) {
        // timer interrupt: context switch
        
        // 1. save current process
        pcb_t* cur = &process_table[current_pid];
        memcpy(cur->regs, (void*)trap_frame_addr, 128);
        cur->pc = read_mepc();
        cur->satp = read_satp();
        if (cur->state == 2) cur->state = 1;  // RUNNING -> READY
        
        // 2. run scheduler
        uint32_t next_pid = schedule_next();
        current_pid = next_pid;
        
        // 3. restore next process
        pcb_t* next = &process_table[next_pid];
        next->state = 2;  // READY -> RUNNING
        memcpy((void*)trap_frame_addr, next->regs, 128);
        write_mepc(next->pc);
        write_satp(next->satp);
        
        // 4. reprogram timer
        reprogram_timer(500000);  // 10 ms
    }
    // (page faults, PMP faults, etc. handled elsewhere)
}

B3: spawn_process() (3 pts)

Add SYS_SPAWN (a7=101): the kernel creates a new process in the process table with a fresh stack (allocated from the kernel heap) and an entry point at the address in a0. The new process is set to READY state and will run on the next context switch.

uint32_t sys_spawn(uint32_t entry_point) {
    // find an empty PCB slot
    for (int i = 1; i < MAX_PROCS; i++) {
        if (process_table[i].state == 0) {
            // allocate a 4 KiB stack for the new process
            uint32_t stack = alloc_page();
            process_table[i].regs[2] = stack + 4096;  // sp = stack top
            process_table[i].pc = entry_point;
            process_table[i].satp = read_satp();        // share parent's page table
            process_table[i].mstatus = 0x00000080;      // MPIE=1, MPP=0 (U-mode)
            process_table[i].state = 1;                 // READY
            process_table[i].pid = i;
            process_table[i].stack_base = stack;
            process_table[i].stack_size = 4096;
            return i;
        }
    }
    return -1;  // no empty slot
}

Part C: Two-task demonstration and measurement (7 pts)

C1: Two concurrently running tasks (4 pts)

Write two user-mode tasks:

Task A:

void task_a(void) {
    uint32_t counter = 0;
    while (1) {
        counter++;
        if (counter % 100 == 0) {
            // SYS_WRITE to OLED line 0: "TASK A: <counter>"
            char buf[20];
            itoa(counter, buf, 10);
            oled_write(0, 0, "TASK A: ");
            oled_write(0, 8, buf);
        }
    }
}

Task B: Same structure, writes "TASK B: " to OLED line 1.

In the kernel boot: spawn Task A (PID 1) and Task B (PID 2). Both should advance simultaneously. Capture a 5-second video of the OLED: both lines must advance (Task B does not freeze while Task A runs).

C2: Context-switch cycle cost (3 pts)

Add csrr mcycle instrumentation around the context-switch handler:

# at timer interrupt entry:
csrr    t0, mcycle
sw      t0, context_switch_start

# at mret before returning to next process:
csrr    t1, mcycle
lw      t0, context_switch_start
sub     t1, t1, t0
sw      t1, context_switch_cycles

After 100 context switches, read context_switch_cycles / 100 to get the average. Record this value.

Fill in:

The incremental cost should be ~70-100 cycles (the PCB memcpy cost).

Grading