Project 4: A Preemptive, Priority-Based Scheduler

Add preemption and priorities so the highest-priority READY task always runs, using SysTick + PendSV on Cortex-M.

Quick Reference

Attribute Value
Difficulty Advanced
Time Estimate 2-3 weeks
Main Programming Language C with ARM assembly
Alternative Programming Languages Rust, Ada
Coolness Level Very High
Business Potential High
Prerequisites Projects 1-3, SysTick, context switching
Key Topics Preemption, PendSV, priority scheduling, critical sections, task states

1. Learning Objectives

By completing this project, you will:

  1. Trigger context switches from SysTick to enforce preemption.
  2. Implement priority-based task selection.
  3. Protect scheduler data structures with critical sections.
  4. Demonstrate preemption with measurable GPIO behavior.

2. All Theory Needed (Per-Concept Breakdown)

2.1 Preemption and PendSV-Based Context Switching

Fundamentals

Preemption allows the kernel to interrupt a running task and switch to a more important one. On Cortex-M, PendSV is designed for this purpose because it can be set to the lowest priority and triggered from SysTick or other interrupts. The SysTick ISR marks the need for a reschedule and sets the PendSV pending bit. When the CPU exits the ISR and no higher-priority interrupts are active, PendSV runs and performs the context switch. This separation keeps SysTick fast while making context switching deterministic.

Additional fundamentals: Preemption is about enforcing deadlines, not just fairness. The kernel must be able to interrupt lower-priority work immediately when a higher-priority task becomes READY. This is why PendSV exists and why the scheduler must be carefully integrated with SysTick and interrupt priorities.

Deep Dive into the concept

Preemptive scheduling on Cortex-M depends on the interrupt architecture. SysTick runs at a configurable priority and is a regular exception. It should not do heavy work; instead, it sets SCB->ICSR |= SCB_ICSR_PENDSVSET_Msk. PendSV is then pending and will execute when no higher-priority interrupts remain active. This ensures that the CPU does not switch contexts in the middle of a higher-priority ISR, preserving interrupt latency. PendSV itself performs the save/restore of R4-R11 and swaps the PSP to the next task. If you use MSP for kernel work and PSP for tasks, PendSV runs on MSP and manipulates PSP for the outgoing/incoming task, which keeps kernel stacks isolated.

The priority configuration is critical. If PendSV is not the lowest priority, it can preempt other interrupts, which may violate timing guarantees or introduce unbounded latency. If SysTick is too low, it may be delayed, causing jitter in scheduling. A common configuration is: high-priority peripheral ISRs at high priority, SysTick at medium priority, PendSV at the lowest. This ensures that timing-critical peripherals run when needed, SysTick maintains the timebase, and context switching happens only when safe.

Another subtlety is the interrupt tail-chaining behavior. If SysTick triggers while another interrupt is running, the CPU may tail-chain directly into PendSV when the ISR finishes, avoiding a full restore/stack sequence. This improves efficiency and reduces jitter. However, if you call a scheduler from within the SysTick ISR, you can accidentally extend ISR time and increase worst-case latency. The rule of thumb: SysTick should be minimal, PendSV should handle context switching, and the scheduler should be carefully bounded.

Preemption introduces concurrency problems that cooperative scheduling avoids. Since a task can be interrupted at almost any time, any shared scheduler data structures (like READY lists) must be protected. This introduces the need for critical sections and atomic operations, which are explored in the next concept. The key insight is that preemption is not just a feature; it changes the entire correctness model of your kernel.

Additional depth: Preemption depends on careful control of exception priorities and the concept of interrupt priority grouping. The NVIC allows you to split priority bits into preempt priority and subpriority. If you misconfigure the grouping, two interrupts that you expect to preempt each other might not. In a small RTOS, you can use the default grouping, but you should still be aware of how many priority levels are actually available on your MCU. Many Cortex-M parts only implement the upper bits of the priority field, so writing arbitrary values can lead to unexpected priority ordering. A disciplined approach is to define a small set of priorities (for example, 0 for highest, 3 for lowest) and use those consistently across SysTick, PendSV, and peripheral ISRs.

Another subtlety is how preemption interacts with critical sections and scheduler data structures. When a higher-priority task becomes READY, you want to preempt as soon as possible, but not in the middle of updating a list. This is why you set PendSV rather than switching immediately in the ISR. PendSV runs when it is safe to switch, and you can ensure that scheduler data is consistent. If you attempt to switch directly in SysTick, you risk switching while interrupts are still masked or while the scheduler is in a partially updated state. This can lead to corrupted lists or lost tasks.

Preemption also raises the issue of stack usage under nested interrupts. If you allow nested interrupts, multiple exception frames can be stacked, which increases stack usage. If you keep ISR stack on MSP, you must size it to handle the worst-case nesting. Many systems choose to keep high-priority ISRs short and avoid deep nesting to simplify sizing. This is another place where preemption changes the engineering tradeoffs: you gain responsiveness but must manage more complex worst-case analysis.

Finally, preemption changes how you think about timing. In a cooperative system, a task is in control of when it yields. In a preemptive system, a task can be interrupted at any time. This means any shared data must be protected and any timing assumptions must account for interruptions. This project is the bridge between those two worlds, and its success is a reliable, repeatable preemption demo that proves your kernel can enforce priorities correctly.

How this fit on projects

You will implement the SysTick -> PendSV handoff in Sec. 3.2 and Sec. 4.1, and validate preemption with a GPIO demo in Sec. 3.7.2.

Definitions & key terms

  • Preemption: Forced context switch from a running task to another.
  • PendSV: Low-priority exception used for context switches.
  • ICSR: Interrupt Control and State Register; used to set PendSV.
  • Tail-chaining: CPU optimization for back-to-back ISRs.

Mental model diagram (ASCII)

SysTick ISR
   |
   | set PendSV pending
   v
PendSV ISR -> save context -> select next -> restore context

How it works (step-by-step, with invariants and failure modes)

  1. SysTick interrupt fires and increments tick.
  2. SysTick sets PendSV pending bit.
  3. CPU exits SysTick; PendSV runs when safe.
  4. PendSV saves R4-R11, swaps PSP, restores next task.
  5. Failure mode: PendSV priority too high -> ISR latency increases.

Minimal concrete example

void SysTick_Handler(void) {
    tick++;
    SCB->ICSR = SCB_ICSR_PENDSVSET_Msk;
}

Common misconceptions

  • “SysTick should do the full context switch” -> it should only request it.
  • “PendSV priority does not matter” -> it must be lowest.
  • “Preemption is just cooperative plus interrupts” -> it introduces new race risks.

Check-your-understanding questions

  1. Why is PendSV assigned the lowest priority?
  2. What does tail-chaining optimize?
  3. How does preemption change correctness assumptions?

Check-your-understanding answers

  1. To avoid preempting other interrupts and increasing latency.
  2. It avoids redundant stacking when switching ISRs.
  3. Shared data can be accessed concurrently, requiring protection.

Real-world applications

  • Hard real-time control loops that must preempt background work.
  • RTOS kernels in automotive and aerospace systems.

Where you’ll apply it

  • This project: Sec. 3.2, Sec. 3.7.2, Sec. 5.10 Phase 2.
  • Also used in: Project 5 and Project 6.

References

  • ARM Cortex-M exception and PendSV documentation.
  • “Real-Time Concepts for Embedded Systems” by Qing Li, Ch. 5.

Key insights

PendSV is the safe, deterministic place for context switching in a preemptive RTOS.

Summary

Preemption relies on SysTick to request a switch and PendSV to perform it safely at the lowest priority.

Homework/Exercises to practice the concept

  1. Measure the cycle cost of PendSV context switching.
  2. Change PendSV priority and observe impact on a UART ISR.
  3. Implement a manual context switch and compare stability.

Solutions to the homework/exercises

  1. Use DWT cycle counter around PendSV entry/exit.
  2. Higher PendSV priority increases UART ISR latency.
  3. Manual switch works but is harder to reason about under nested interrupts.

2.2 Priority Scheduling and Critical Sections

Fundamentals

Priority scheduling ensures that the highest-priority READY task always runs. When a higher-priority task becomes READY, it should preempt the currently running lower-priority task. Implementing this requires a data structure that can quickly find the highest-priority READY task and a mechanism to protect that data structure from concurrent access. Critical sections are used to prevent interrupts from modifying scheduler state while it is being updated. This is essential because preemption means your scheduler can be interrupted at almost any time.

Additional fundamentals: Priority scheduling only works if the scheduler’s data structures are consistent. Any race condition in READY lists can cause the wrong task to run, which is effectively a real-time bug. Critical sections are the minimum tool to guarantee correctness under preemption.

Deep Dive into the concept

Priority scheduling can be implemented in many ways: a simple linear scan of TCBs, multiple ready lists (one per priority), or a bitmap-based ready set. The simplest for this project is a linear scan over tasks to find the highest READY priority. Although O(n), it is sufficient for a small task count. The key is correctness: when a task changes state (READY, BLOCKED, RUNNING), the scheduler must update the ready list atomically. If an ISR makes a task READY while the scheduler is scanning, you could end up missing the newly ready task or corrupting its state. This is why critical sections are mandatory.

Critical sections on Cortex-M are typically implemented by disabling interrupts (globally with PRIMASK) or by raising BASEPRI to mask lower-priority interrupts. Using PRIMASK is simpler but blocks all interrupts, increasing worst-case latency. BASEPRI is more nuanced: it allows high-priority interrupts to continue while masking lower-priority ones. In RTOS design, BASEPRI is preferred because it balances safety and responsiveness. You must choose the appropriate method depending on your latency requirements. For this project, a simple PRIMASK lock is acceptable, but understanding BASEPRI prepares you for production kernels.

Priority scheduling also introduces edge cases. What happens if two tasks have the same priority? You must define a tie-breaker (round-robin within a priority). What happens if all tasks are BLOCKED? You need an idle task to run. What if a task’s priority changes at runtime? Then you must reinsert it into the ready structure and possibly reschedule. While dynamic priority changes are not required here, your data structures should not make them impossible.

The interaction between priorities and interrupts also matters. An ISR might unblocks a high-priority task; the kernel should notice immediately and preempt the current task. This is typically done by setting PendSV in the ISR after unblocking. The scheduler must then run with interrupts masked to prevent a race between selecting a task and a new READY event. All these mechanics come together to enforce deterministic response for high-priority work.

Additional depth: Priority scheduling can be implemented in many increasingly sophisticated ways. A linear scan over tasks is simple but scales poorly with large numbers of tasks. A ready bitmap is a common improvement: each bit represents whether a priority level has any READY tasks, and you can use a count-leading-zeros instruction to find the highest priority in constant time. For this learning RTOS, the linear scan is fine, but understanding the bitmap option prepares you for more advanced implementations. If you do implement a bitmap later, you will also need per-priority queues to preserve round-robin fairness within the same priority.

Critical sections are also more nuanced than a simple disable/enable. If you use PRIMASK, you disable all interrupts, which can increase worst-case latency for high-priority ISRs. BASEPRI allows you to mask only lower-priority interrupts, so you can keep critical ISRs responsive. However, BASEPRI requires you to carefully define a kernel interrupt priority threshold. Many RTOSes define a constant like MAX_SYSCALL_INTERRUPT_PRIORITY and ensure that any ISR that calls kernel services runs at or below that priority. This ensures the kernel can safely mask those ISRs during critical sections while still allowing higher-priority interrupts to run. Understanding this convention early will make your kernel more robust.

Another subtle issue is priority inversion and starvation. Even with preemption, a low-priority task can hold a resource needed by a high-priority task, causing inversion. The scheduler alone cannot solve this; you need mutex protocols like priority inheritance (Project 6). Similarly, if you have a stream of high-priority work, lower-priority tasks may starve. Some RTOSes implement time slicing within equal priorities or implement aging to prevent starvation. You should at least be aware of these behaviors when you design your ready list selection.

Finally, priority scheduling requires careful testing. Use GPIO traces to observe preemption and verify that the highest-priority task always runs immediately when READY. This is not just a functional test; it is a proof that your kernel enforces deadlines. A deterministic, reproducible preemption demo is the hallmark of a correctly implemented priority scheduler.

How this fit on projects

You will implement priority selection in Sec. 3.2 and guard scheduler data in Sec. 4.2 and Sec. 5.11. These decisions will influence priority inversion behavior in Project 6.

Definitions & key terms

  • Priority: Rank indicating which task should run first.
  • Ready list: Set of tasks that are READY to run.
  • Critical section: Code region protected from concurrent access.
  • BASEPRI/PRIMASK: Cortex-M registers controlling interrupt masking.

Mental model diagram (ASCII)

READY tasks -> select highest priority -> run
       ^             |
       |             v
    ISR makes task READY

How it works (step-by-step, with invariants and failure modes)

  1. ISR or task marks another task READY.
  2. Enter critical section to update ready structures.
  3. Scheduler selects highest priority READY task.
  4. If different from current, PendSV triggers switch.
  5. Failure mode: missing critical section -> corrupted state.

Minimal concrete example

uint32_t enter_critical(void) {
    uint32_t primask = __get_PRIMASK();
    __disable_irq();
    return primask;
}

void exit_critical(uint32_t state) {
    if (!state) __enable_irq();
}

Common misconceptions

  • “Priority alone solves timing” -> shared resource blocking can still break deadlines.
  • “Disabling interrupts is always safe” -> it increases latency.
  • “Round-robin is incompatible with priority” -> it can be used within a priority level.

Check-your-understanding questions

  1. Why must scheduler state updates be atomic?
  2. What is the difference between PRIMASK and BASEPRI?
  3. How would you handle two tasks with equal priority?

Check-your-understanding answers

  1. Preemption can occur at any time and corrupt the data otherwise.
  2. PRIMASK disables all interrupts; BASEPRI masks only lower-priority ones.
  3. Use round-robin within that priority level.

Real-world applications

  • Flight control systems where priority ensures sensor loops run on time.
  • Audio processing pipelines where high-priority tasks handle real-time streams.

Where you’ll apply it

  • This project: Sec. 3.2, Sec. 4.2, Sec. 5.11.
  • Also used in: Project 6.

References

  • ARM Cortex-M PRIMASK and BASEPRI documentation.
  • “Real-Time Concepts for Embedded Systems” by Qing Li, Ch. 4-6.

Key insights

Priority scheduling only works if ready lists are updated atomically.

Summary

Priority scheduling enforces deterministic response but requires careful critical section design to be correct.

Homework/Exercises to practice the concept

  1. Implement a simple priority scan scheduler.
  2. Add round-robin within equal priorities.
  3. Replace PRIMASK with BASEPRI and compare latency impact.

Solutions to the homework/exercises

  1. Scan TCB array and choose highest READY.
  2. Track last-run index per priority.
  3. Expect higher ISR responsiveness when using BASEPRI.

3. Project Specification

3.1 What You Will Build

A preemptive, priority-based scheduler where SysTick triggers PendSV, and the highest-priority READY task always runs. The system includes an idle task and supports task state transitions under interrupt load.

3.2 Functional Requirements

  1. Preemption: SysTick triggers PendSV for context switching.
  2. Priority Selection: Highest priority READY task runs immediately.
  3. Critical Sections: Scheduler data updates are protected.

3.3 Non-Functional Requirements

  • Performance: Context switch < 30 us on target.
  • Reliability: No corrupted task states after 10,000 switches.
  • Usability: Preemption behavior observable via GPIO.

3.4 Example Usage / Output

  • High-priority task toggles LED at 100 ms.
  • Low-priority task toggles another LED, but is interrupted by high-priority toggles.

3.5 Data Formats / Schemas / Protocols

  • TCB contains priority, state, and stack pointer.

3.6 Edge Cases

  • Two tasks READY at same priority.
  • All tasks BLOCKED -> idle must run.
  • Scheduler updates interrupted by ISR.

3.7 Real World Outcome

A higher-priority task visibly preempts a lower-priority task, and GPIO traces show deterministic preemption on each tick.

3.7.1 How to Run (Copy/Paste)

make clean all
make flash

Exit codes:

  • make: 0 success, 2 build failure.
  • openocd: 0 flash success, 1 connection failure.

3.7.2 Golden Path Demo (Deterministic)

  1. Task High toggles LED1 every 50 ms.
  2. Task Low toggles LED2 in a longer loop.
  3. Observe LED1 interrupting LED2’s pattern consistently.

3.7.3 Failure Demo (Deterministic)

  1. Set PendSV priority higher than SysTick.
  2. Observe ISR latency spikes and inconsistent toggling.
  3. Restore PendSV to lowest priority and verify stability.

4. Solution Architecture

4.1 High-Level Design

SysTick -> set PendSV -> scheduler -> context switch -> highest READY task

4.2 Key Components

Component Responsibility Key Decisions
sched.c Priority selection Linear scan vs ready lists
context.S PendSV context switching Save/restore R4-R11
critical.c Interrupt masking utilities PRIMASK vs BASEPRI

4.4 Data Structures (No Full Code)

typedef struct {
    uint32_t *sp;
    uint8_t priority;
    uint8_t state;
} tcb_t;

4.4 Algorithm Overview

Key Algorithm: Priority Select

  1. Enter critical section.
  2. Scan READY tasks for highest priority.
  3. If different from current, set next.
  4. Exit critical section; PendSV switches.

Complexity Analysis:

  • Time: O(n) scan per scheduling decision.
  • Space: O(n) TCBs.

5. Implementation Guide

5.1 Development Environment Setup

brew install arm-none-eabi-gcc openocd

5.2 Project Structure

rtos-p04/
|-- src/
|   |-- sched.c
|   |-- critical.c
|   `-- main.c
|-- asm/
|   `-- context.S
`-- Makefile

5.3 The Core Question You’re Answering

“How do I guarantee that the most important task runs immediately, every time?”

5.4 Concepts You Must Understand First

  1. PendSV-based context switching.
  2. Priority scheduling and critical sections.

5.5 Questions to Guide Your Design

  1. Which priority should SysTick and PendSV use?
  2. How will you avoid race conditions in READY lists?
  3. What should the idle task do when nothing is READY?

5.6 Thinking Exercise

Draw a timeline where a high-priority task becomes READY in the middle of a low-priority task’s loop.

5.7 The Interview Questions They’ll Ask

  1. “Why is PendSV the lowest priority?”
  2. “How do critical sections affect interrupt latency?”
  3. “What is the difference between preemptive and cooperative scheduling?”

5.8 Hints in Layers

Hint 1: Keep SysTick short Only set PendSV and update time.

Hint 2: Protect ready lists Disable interrupts around list updates.

Hint 3: Verify priorities Read NVIC priority registers in GDB.

5.9 Books That Will Help

Topic Book Chapter
Preemptive scheduling “Real-Time Concepts for Embedded Systems” Ch. 4-5
Cortex-M exceptions “The Definitive Guide to ARM Cortex-M” Ch. 7

5.10 Implementation Phases

Phase 1: Priority Scheduler (4-6 days)

Goals: Implement priority scan and READY list. Tasks: Add priority to TCB, update scheduler selection. Checkpoint: Highest priority task always runs.

Phase 2: Preemption Hook (4-6 days)

Goals: Integrate SysTick -> PendSV. Tasks: Set PendSV pending in SysTick, implement context switch. Checkpoint: Preemption visible in LED patterns.

Phase 3: Critical Section Hardening (3-4 days)

Goals: Avoid race conditions. Tasks: Wrap ready list updates with PRIMASK or BASEPRI. Checkpoint: No corruption under stress.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
Ready list structure Linear scan vs bitmap Linear scan Simpler for small task counts
Interrupt masking PRIMASK vs BASEPRI PRIMASK (start) Simpler, then upgrade later

6. Testing Strategy

6.1 Test Categories

| Category | Purpose | Examples | |——————|———————————-|————————————| | Unit Tests | Scheduler selection correctness | Highest priority chosen | | Integration Tests | Preemption behavior | LED pattern interruption | | Edge Case Tests | All tasks blocked | Idle task runs |

6.2 Critical Test Cases

  1. High-priority task preempts low task immediately when READY.
  2. Ready list updates remain consistent under ISR load.
  3. Idle task runs when all tasks are blocked.

6.3 Test Data

Priority range: 0 (lowest) to 3 (highest)
Expected preemption latency: < 1 tick

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

| Pitfall | Symptom | Solution | |—————————|——————————-|————————————| | PendSV priority too high | ISR latency spikes | Set PendSV to lowest priority | | Missing critical section | READY list corruption | Use PRIMASK/BASEPRI | | No idle task | CPU executes invalid pointer | Add idle task |

7.2 Debugging Strategies

  • Toggle GPIO at PendSV entry to measure context switch frequency.
  • Verify NVIC priorities with GDB.

7.3 Performance Traps

  • Excessive context switching can reduce CPU time for real work.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add round-robin within equal priorities.
  • Add a statistics counter for context switches.

8.2 Intermediate Extensions

  • Implement BASEPRI-based critical sections.
  • Add a ready bitmap to speed selection.

8.3 Advanced Extensions

  • Implement time slicing within same priority.
  • Add dynamic priority changes at runtime.

9. Real-World Connections

9.1 Industry Applications

  • Hard real-time control and safety systems.
  • Priority scheduling in avionics RTOS kernels.
  • FreeRTOS: PendSV-based context switch.
  • ThreadX: Priority scheduling with preemption.

9.3 Interview Relevance

  • Preemption, PendSV, and priority scheduling are core embedded interview topics.

10. Resources

10.1 Essential Reading

  • ARM Cortex-M exception documentation.
  • “Real-Time Concepts for Embedded Systems” by Qing Li.

10.2 Video Resources

  • RTOS scheduling demos and PendSV explanations.

10.3 Tools & Documentation

  • GDB for inspecting NVIC and SCB registers.

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain why PendSV is low priority.
  • I can describe how preemption changes task safety.

11.2 Implementation

  • High-priority tasks preempt low-priority tasks reliably.
  • Scheduler data is protected with critical sections.

11.3 Growth

  • I can explain the tradeoff between responsiveness and latency.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • SysTick triggers PendSV and preemption is observable.
  • Highest priority READY task always runs.

Full Completion:

  • Critical sections prevent race conditions under load.
  • Idle task runs correctly when no tasks are READY.

Excellence (Going Above & Beyond):

  • Ready bitmap implemented with O(1) selection.
  • BASEPRI-based critical sections measured for latency.