~/posts $ cat 9.md · 2022-05-02 · 7 min read

uKernel DevLog #1

I'm currently enrolled in a class about embedded and real-time systems. For this class's final project, I'm developing a real-time kernel for Arduino UNO. I'll try to document the development in a series of posts. This is part #1.

Today (as of writing) was the exam's day: the final exam was in the middle of the semester. As such, the rest of lectures are reserved for the development of the project. My team (me and 2 friends) decided to develop a micro-kernel (uKernel) for the Arduino UNO. The Arduino wasn't chosen for any reason in particular (besides being available at the school's lab).

The basics

Around 2 weeks ago, we had a guided workshop to develop a small Kernel for the Arduino (in C). It was a tick-based preemptive kernel supporting a fixed task-set of periodic tasks with fixed priorities. This kernel had both a scheduler and a dispatcher, so we had what's called on-line scheduling. The tasks' deadlines are equal to their periods.

Explaining concepts

Preemption example diagram

Source code

1#define NT 20 // the max number of tasks in the system
2
3typedef struct
4{
5    unsigned int period;
6    unsigned int delay;
7    void (*func)(void);
8    unsigned int exec;
9} Task;
10
11Task tasks[NT];
12unsigned int curr_task = NT + 1;
13
14/*
15 * Registers a task in the system. The delay controls the initial offset of the task.
16 * A task with 0 period is only run once (one-shot task).
17 */
18int Sched_Add(unsigned int period, unsigned int delay, void (*func)(void), unsigned prio) {
19    if (!tasks[prio].func) {
20            tasks[prio] = {
21                period,
22                delay,
23                func,
24                (delay == 0)
25            };
26            return prio;
27    }
28    return -1;
29}
30
31/* Ticks all tasks: updates the current time till ativation, and sets tasks ready */
32void Sched_Schedule() {
33    for (int i = 0; i < NT; ++i ) {
34        if (!tasks[i].func || tasks[i].exec)
35            continue;
36
37        if (tasks[i].delay == 0) {
38            tasks[i].exec = 1;
39            tasks[i].delay = tasks[i].period + 1;
40        }
41        --tasks[i].delay;
42    }
43}
44
45/* Runs the highest priority ready task */
46void Sched_Dispatch() {
47    int prev_task = curr_task;
48
49    for (int i = 0; i < prev_task; ++i) {
50        if (tasks[i].func && tasks[i].exec) {
51            tasks[i].exec = 0;
52
53            // run task
54            curr_task = i;
55            interrupts();
56            tasks[i].func();
57            noInterrupts();
58            curr_task = prev_task;
59
60            // delete one-shot tasks (tasks that only run once)
61            if (tasks[i].period == 0) {
62                tasks[i].func = 0;
63            }
64        }
65    }
66}
67
68// Timer1 interrupt handler
69ISR(TIMER1_COMPA_vect) {
70    Sched_Schedule();
71    Sched_Dispatch();
72}
73
74void setup(){
75  Sched_Add(10, 5, FuncX, 0);
76  Sched_Add(4,  0, FuncY, 1);
77  Sched_Add(1,  0, FuncZ, 2);
78
79  // Setup timer interrupts on timer1
80}
81
82void loop(){
83  // do nothing
84}

In the code above, I've omitted some details like the implementation of the tasks function (FuncX, FuncY, FuncZ just toggle their respective LED) and how to set up timer interrupts, for simplicity’s sake.

Code analysis

Given how scary "implementing a micro-kernel" sounds, the code above is fairly simple. In my opinion, the most elegant part is how preemption is handled:

Another cool property is how task overruns are handled. A task overrun is when a task runs for longer than the maximum time (worst-case) it said it would run for. In the case of this micro-kernel, the task's deadlines are equal to the periods (Di = Ti). If a task runs for longer than its period, it can't prempt itself. The cool thing about this is that the effect of these overruns is deterministic: they only affect tasks of lower priority (they get delayed).

But there are some problems with this implementation:

Improving the kernel

Task schedulability

When we have a real-time system, we're interested in determining if the task set can be scheduled in a way that no deadlines are missed before deploying the system.

In the case of this kernel (considering fixed priorities and Di = Ti), there are 2 alternative methods for priority assignment:

Let's the following task set with RM priorities:

priorityTC
120.5
230.5
362

The lower the priority, the higher the period (T). C is the amount of CPU time the task needs to complete execution (worst-case).

To verify the schedulability of this task-set, we perform a CPU utilization test using Liu & Layland's Least Upper Bound (LUB):

The image below shows this test being applied to the task-set above.

LUB test

As the image displays, the task-set is schedulable.

Harmonic periods – special case

If the periods of all tasks are harmonic (all multiples of each other), we compare the CPU utilization to 100% (instead of the LUB): U(n) <= 1.

It should be noted that, if the periods aren't harmonic, we can't grantee 100% CPU utilization with fixed priority systems.

Example of harmonic periods

In the image above, we have 2 systems with 2 tasks each:

To solve the problem above, we can use dynamic priority systems: a task's priority is only known/calculated at run-time by the scheduler.

Blocking situations

Blocking happens there are dependencies/sequences between tasks.
For example, 2 tasks share a mutex for a given critical region. Task 1 (higher priority), tries to preempt task 2, but can't execute, because the mutex is locked in task 2's critical region. In this kind of situation, task 1 can run for a while before reaching the critical region, but when it reaches the region, it will have to return control to task 2 before proceeding.

When this happens, we're going back on our chain of tasks. This means that when the control returns to the lower priority task, it can override that higher priority's stack data (for example, by calling a function).

Block stack corruption example

In the image above, we see how a function call from the lower priority task (after blocking the higher priority one) can corrupt the stack.

To deal with this, we'll implement mechanisms to manage the access to shared resources, and their protection mechanisms. Most of these solutions require us to implement multiple stacks: one for each task.

Shared resource access

There are several solutions available to us here depending on which techniques of shared resource access control we want to implement. These techniques divide themselves into 2 main groups:

The local methods are more efficient, but they can introduce some other problems, namely: undetermined blocking, chained blocking, and deadlocks. The protection mechanisms intend to mitigate one or more of these. We'll explore these in the future (when we're implementing them).

Conclusion

I tried to explain most of what I find the fundamental concepts of Real-time systems, so next posts can be easier to follow. I hope it wasn't too much.

In the next chapter, we'll explore how we can implement multiple stacks: one for each task. Spoiler: there's assembly involved. We'll also start using C++ where we can, so we can clean up the code by using classes.

Stay safe :P