Priority-Based RTOS Kernel

A preemptive real-time operating system kernel implemented in C for the ARM Cortex-M processor (LM3S9D92). Designed to demonstrate core OS concepts: process scheduling, context switching, memory management, and interrupt handling.

Overview

This project implements a fully functional RTOS with the following core features:

• Preemptive Round-Robin Scheduling with priority levels (0-3)
• Circular Doubly-Linked Queue data structure for O(1) process scheduling
• ARM Cortex-M Context Switching via SVC/PendSV exception handlers
• Tiered Fixed-Size Block Allocator for deterministic memory management
• Interrupt-Safe Operations with critical section protection
• Service Call Interface for process-kernel communication

Architecture

Process Scheduler

The kernel maintains four separate priority queues, each containing a circular doubly-linked list of Process Control Blocks (PCBs). The scheduler always executes the highest-priority ready process.

• Preemption: SysTick timer interrupt forces context switches at fixed intervals
• Round-Robin: Each process receives a fixed time quantum before yielding to the next process in its priority queue
• O(1) Switching: Context switching is constant-time—no searching required regardless of process count

Memory Allocator

A deterministic allocator designed for real-time constraints, eliminating heap fragmentation and unpredictable allocation latency.

• Five block size classes: 0x80, 0x100, 0x200, 0x400, 0x800 bytes
• SearchList lookup table: Maps requested size to smallest suitable block in O(1)
• Per-size free lists: Linked-list tracking of available blocks
• Total heap: 0x14000 bytes (80 KB) divided equally among size classes

Context Switching

Leverages ARM Cortex-M exception handlers to efficiently switch between processes.

• SVC (Supervisor Call): Software interrupt for service requests (print, get ID, terminate, etc.)
• PendSV (Pending Service Vector): Deferred exception handler that performs actual context switches
• Dual-stack architecture: Separate Main Stack Pointer (MSP) for kernel and Process Stack Pointer (PSP) for user processes
• Register preservation: Saves/restores 16 ARM registers per context switch

Key Design Decisions

Why Circular Doubly-Linked Queues?

• Circular: Eliminates NULL checks; last element points back to first
• Doubly-linked: Enables O(1) removal and reinsertion from any position
• Per-priority: Allows instant lookup of the highest-priority ready process

Why Fixed-Size Blocks?

• Determinism: O(1) allocation and deallocation, predictable timing
• No fragmentation: Each size class manages its own pool
• Real-time safety: Avoids unpredictable heap behavior critical for embedded systems
• Trade-off: Accepts internal fragmentation for guaranteed allocation latency

Project Structure

ccs/
├── src/
│   ├── main.c                           # Entry point & test harness
│   └── kernel/
│       ├── kernel_private.c             # Scheduler, PCB management, SVC handler
│       ├── kernel_public.c              # Public API for processes
│       ├── memory/memory.c              # Block allocator implementation
│       ├── queue/queue.c                # Circular queue for UART I/O
│       ├── pendsv/pendsv.c              # Context switch handler
│       ├── systick/systick.c            # Timer interrupt handler
│       └── uart0/uart0.c                # Serial I/O
├── hdr/                                  # Header files
│   ├── kernel_public.h
│   ├── kernel_private.h
│   ├── memory.h
│   └── ...
├── linker/                              # Linker configuration
└── targetConfigs/                       # CCS target settings

Building & Running

This project was built using Texas Instruments Code Composer Studio (CCS) targeting the LM3S9D92 ARM Cortex-M3 evaluation board.

Prerequisites:

• Code Composer Studio v6+
• ARM Cortex-M3 device support
• LM3S9D92 evaluation board (or simulator)

Build:

1. Open the project in CCS
2. Build → Build Project
3. Run → Debug to launch on target

Service Call API

Processes interact with the kernel through service calls:

• START: Initialize and begin scheduler
• GETID: Retrieve current process ID
• WRITE: Output to UART0 serial port
• NICE: Change process priority
• PASS: Yield CPU to next process
• TERMINATE: Exit current process

Testing

The project includes test cases in test/ demonstrating:

• Multi-priority process execution
• Context switching behavior
• Memory allocation/deallocation
• Service call invocation

Learning Outcomes

Building this kernel required deep understanding of:

• Concurrency & synchronization: Critical sections, interrupt safety
• Memory management: Heap allocation, fragmentation, determinism
• Hardware abstraction: ARM exception handlers, stack pointers, privileged modes
• Real-time constraints: Predictable latency, bounded execution time
• Systems design: Trade-offs between simplicity, efficiency, and determinism

Notes

This was coursework for ECED 4402 (Embedded Systems) at Dalhousie University (Nov 2016). The design emphasizes clarity and correctness over production optimizations. Key simplifications:

• No dynamic priority adjustment beyond NICE
• No inter-process synchronization primitives (mutex, semaphore)
• Single-core execution
• No power management

References

• ARM Cortex-M3 Devices Generic User Guide
• LM3S9D92 Datasheet (Texas Instruments)
• "Real-Time Operating Systems" design principles and best practices