Arbiter – Real-Time Scheduling Framework

Overview

Arbiter is an RTOS-style scheduling project that demonstrates deterministic task execution, synchronization, and kernel–user space interaction on Linux. The project models real-time systems by coordinating periodic and aperiodic tasks with strict timing constraints, while preventing unsafe preemption using semaphore-based protocols.

The system consists of:

• A user-space real-time application implementing periodic and event-driven tasks
• A custom Linux kernel module (character device driver) used for controlled logging and verification

Arbiter focuses on how real-time systems behave, not just how threads are created.

---

System Design

graph TD
    subgraph "User Space (arbiter.c)"
        MainThread([Main Thread])
        PCP_Mutex>"PCP Mutex (PTHREAD_PRIO_PROTECT)"]
        CondVar>"Condition Variable (cond_task_4)"]

        subgraph "Periodic Tasks (SCHED_FIFO)"
            Task1([Task 1 - High Prio])
            Task2([Task 2 - Med Prio])
            Task3([Task 3 - Low Prio])
        end

        Task4([Task 4 - Aperiodic])

        MainThread -- "Initialize & Create Threads" --> Task1 & Task2 & Task3 & Task4

        Task1 -- "Periodically Wake Up" --> T1_Cycle
        subgraph T1_Cycle ["Task 1 Cycle"]
            T1_Lock["Lock PCP Mutex"] -- "Boosts Priority" --> T1_WriteStart["write(fd, ' 1[ ')"]
            T1_WriteStart --> T1_Work["Simulate Work"]
            T1_WriteEnd["write(fd, ' ]1 ')"] --> T1_Unlock["Unlock PCP Mutex"]
        end
        T1_Lock -.-> PCP_Mutex
        T1_Unlock -.-> PCP_Mutex

        Task2 -- "Periodically Wake Up" --> T2_Cycle
        subgraph T2_Cycle ["Task 2 Cycle"]
            T2_Lock["Lock PCP Mutex"] -- "Boosts Priority" --> T2_WriteStart["write(fd, ' 2[ ')"]
            T2_WriteStart --> T2_Work["Simulate Work (Random Trigger)"]
            T2_Work -- "If Triggered" --> T2_Signal["Signal Condition"]
            T2_Work --> T2_WriteEnd["write(fd, ' ]2 ')"]
            T2_WriteEnd --> T2_Unlock["Unlock PCP Mutex"]
        end
        T2_Lock -.-> PCP_Mutex
        T2_Unlock -.-> PCP_Mutex
        T2_Signal -.-> CondVar

        Task3 -- "Periodically Wake Up" --> T3_Cycle
        subgraph T3_Cycle ["Task 3 Cycle"]
            T3_Lock["Lock PCP Mutex"] -- "Boosts Priority" --> T3_WriteStart["write(fd, ' 3[ ')"]
            T3_WriteStart --> T3_Work["Simulate Work"]
            T3_WriteEnd["write(fd, ' ]3 ')"] --> T3_Unlock["Unlock PCP Mutex"]
        end
        T3_Lock -.-> PCP_Mutex
        T3_Unlock -.-> PCP_Mutex

        Task4 -- "Wait for Signal" --> CondVar
        CondVar -- "Wakes Up" --> T4_Cycle
        subgraph T4_Cycle ["Task 4 Cycle"]
            T4_Lock["Lock PCP Mutex"] -- "Boosts Priority" --> T4_WriteStart["write(fd, ' 4[ ')"]
            T4_WriteStart --> T4_Work["Simulate Work"]
            T4_WriteEnd["write(fd, ' ]4 ')"] --> T4_Unlock["Unlock PCP Mutex"]
        end
        T4_Lock -.-> PCP_Mutex
        T4_Unlock -.-> PCP_Mutex

        T1_WriteStart & T1_WriteEnd & T2_WriteStart & T2_WriteEnd & T3_WriteStart & T3_WriteEnd & T4_WriteStart & T4_WriteEnd -- "write() syscall" --> KernelDriver
    end

    subgraph "Kernel Space (simple.c)"
        KernelDriver{{simple_write function}}
        KernelSem>"Kernel Semaphore (down_interruptible/up)"]
        KernelLog[Kernel Ring Buffer dmesg]

        KernelDriver --> SemLock["Acquire Semaphore"]
        SemLock -.-> KernelSem
        SemLock --> CopyData["copy_from_user()"]
        CopyData --> PrintK["printk(KERN_INFO, ...)"]
        PrintK --> SemUnlock["Release Semaphore"]
        SemUnlock -.-> KernelSem
        PrintK -- "Logs data" --> KernelLog
    end

Loading

Task Model

The application spawns four real-time tasks:

Task	Type	Period / Trigger
J1	Periodic	300 ms
J2	Periodic	500 ms
J3	Periodic	800 ms
J4	Aperiodic	Triggered by J2

• Periodic tasks (J1–J3) execute repeatedly at fixed intervals.
• Aperiodic task (J4) executes only when explicitly triggered, modeling interrupt- or event-driven workloads.

Each task performs CPU-intensive operations to simulate execution time and expose scheduling behavior.

---

Synchronization & Preemption Control

All tasks interact with a shared kernel driver and therefore require strict synchronization.

• Semaphores are used to protect critical sections

• A Priority Ceiling Protocol (PCP) is implemented to:

  • Prevent priority inversion
  • Guarantee bounded blocking
  • Ensure deterministic execution

This design prevents tasks from being preempted while executing critical sections that involve kernel interaction.

---

Kernel Module (Driver)

The kernel component is a character device driver implementing the following system calls:

• open() – Establishes access to the device
• write() – Logs task activity to the kernel log
• close() – Releases the device

Each task:

1. Opens the device file
2. Writes its task identifier with an opening bracket (e.g., [1, [2)
3. Closes the device
4. Performs time-consuming computation
5. Repeats the process with a closing bracket (e.g., 1], 2])

This bracket-based logging allows visual inspection of task interleaving and preemption via dmesg.

Example kernel log output:

[11][2[11]2][3[11]3][4]

Such output clearly illustrates scheduling behavior and the effect of synchronization.

---

Key Concepts Demonstrated

• Real-time task modeling (periodic vs aperiodic)
• Linux thread scheduling behavior
• Semaphore-based synchronization
• Priority Ceiling Protocol
• Kernel ↔ user-space interaction
• Timing verification via kernel logs

This project mirrors design patterns used in embedded systems, RTOS kernels, and safety-critical software.

---

Build & Run Instructions

⚠️ Requires Linux (recommended: Ubuntu 20.04+). Kernel modules cannot be loaded on macOS/Windows natively.

1. Gain Superuser Access

sudo su

2. Build the Kernel Module

make

3. Load the Kernel Module

insmod my_module.ko

4. Verify Module Installation

lsmod | grep simple

5. Identify Major Device Number

cat /proc/devices

6. Create the Device File

Replace <major_number> with the value from the previous step:

mknod /dev/simple c <major_number> 0

7. Compile the User-Space Application

gcc arbiter.c -lpthread -o arbiter

8. Run the Scheduler

./arbiter

9. Inspect Kernel Logs

dmesg | tail

---

Expected Output

• Deterministic execution of periodic tasks at their defined periods
• Event-driven activation of the aperiodic task
• Ordered, non-overlapping kernel logs when semaphore protection is enabled

Any deviation in ordering indicates incorrect synchronization or preemption behavior.

---

Educational Value

Arbiter provides hands-on exposure to:

• RTOS design principles
• Concurrency hazards and solutions
• Kernel programming fundamentals
• Real-time scheduling analysis

This project goes beyond basic multithreading and reflects real-world OS and embedded systems engineering practices.

---

Future Extensions

• Deadline miss detection
• Rate Monotonic vs EDF comparison
• High-resolution timers
• Tracing with ftrace or perf
• Migration to PREEMPT_RT kernel

---