# uKernel DevLog #1

URL: https://joaocosta.dev/blog/9
Published: 2022-05-02 · 7 min read

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](https://www.arduino.cc/en/Main/arduinoBoardUno). 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

- **Task** - A set of instructions that has to be run according to some time
  constraints;
- **Periodic task** - A task that takes _C_ time units to complete and needs to
  be run every _T_ time units;
  - Note that this doesn't mean that a task (C=2ms, T=10ms) executes for 2ms and
    then executes again, that 10ms later. It means that every 10ms, 2ms will be
    taken to execute the task.
- **Period (_T_)** - The time between task activations.
- **Fixed priorities** - A static attribute assigned to each task:
  - Higher numbers mean higher priority;
  - Used by the **scheduler** to choose which task to run at a given instant.
- **Tick-based** - A **tick-based** kernel (like the name implies) uses timer
  interrupts to schedule and dispatch tasks;
- **Preemptive** - When a kernel supports preemption, it means that tasks can be
  paused

---

![Preemption example diagram](../_resources/d07b520cb26663312dea7f2ff8f1aaae.png)

### Source code

```c
#define NT 20 // the max number of tasks in the system

typedef struct
{
    unsigned int period;
    unsigned int delay;
    void (*func)(void);
    unsigned int exec;
} Task;

Task tasks[NT];
unsigned int curr_task = NT + 1;

/*
 * Registers a task in the system. The delay controls the initial offset of the task.
 * A task with 0 period is only run once (one-shot task).
 */
int Sched_Add(unsigned int period, unsigned int delay, void (*func)(void), unsigned prio) {
    if (!tasks[prio].func) {
            tasks[prio] = {
                period,
                delay,
                func,
                (delay == 0)
            };
            return prio;
    }
    return -1;
}

/* Ticks all tasks: updates the current time till ativation, and sets tasks ready */
void Sched_Schedule() {
    for (int i = 0; i < NT; ++i ) {
        if (!tasks[i].func || tasks[i].exec)
            continue;

        if (tasks[i].delay == 0) {
            tasks[i].exec = 1;
            tasks[i].delay = tasks[i].period + 1;
        }
        --tasks[i].delay;
    }
}

/* Runs the highest priority ready task */
void Sched_Dispatch() {
    int prev_task = curr_task;

    for (int i = 0; i < prev_task; ++i) {
        if (tasks[i].func && tasks[i].exec) {
            tasks[i].exec = 0;

            // run task
            curr_task = i;
            interrupts();
            tasks[i].func();
            noInterrupts();
            curr_task = prev_task;

            // delete one-shot tasks (tasks that only run once)
            if (tasks[i].period == 0) {
                tasks[i].func = 0;
            }
        }
    }
}

// Timer1 interrupt handler
ISR(TIMER1_COMPA_vect) {
    Sched_Schedule();
    Sched_Dispatch();
}

void setup(){
  Sched_Add(10, 5, FuncX, 0);
  Sched_Add(4,  0, FuncY, 1);
  Sched_Add(1,  0, FuncZ, 2);

  // Setup timer interrupts on timer1
}

void loop(){
  // do nothing
}
```

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:

- When handling an interrupt, interrupts are automatically disabled (and
  re-enabled on return from the interrupt handler);
- Before running the task's code, we re-enable interrupts (and disable them
  afterwards);
- If the task is long enough for another timer interrupt to happen, the _ISR_
  can start executing another task;
- When a task returns, and the _ISR_ exits, the previous task's execution will
  be resumed.

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:

- The kernel uses fixed priorities, but they aren't sorted in any particular
  order. This makes **schedulability testing** unfeasible;
- We can't configure a task to have **deadlines** smaller than its **period**
  (`Di < Ti`);
- The tasks are assumed independent, so there aren't **priority inversion**
  (**blocking**) problems with the kernel;
- For the same reason, **task synchronization (semaphores)**/**mutual exclusion
  (mutexes)** mechanisms aren't available.

## 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_:

- **Rate Monotonic (RM)** - The priorities are inversely proportional to the
  **period**. This means that the lower the **period**, the higher the
  **priority**. Only works for `Di = Ti`;
- **Deadline Monotonic (DM)** - The priorities are inversely proportional to the
  **deadline**. This means that the lower the **deadline**, the higher the
  **priority**. Works for `Di <= Ti`.

Let's the following task set with RM priorities:

| priority | T   | C   |
| -------- | --- | --- |
| 1        | 2   | 0.5 |
| 2        | 3   | 0.5 |
| 3        | 6   | 2   |

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)**:

- **CPU utilization - U(n)** - Is the sum of all tasks utilization: `Ci/Ti`;
- **LUB** - `n * (2^(1/n) - 1)`, where `n` is the number of tasks in the system.
- `U(n) > 1` => non schedulable set (overload);
- `U(n) <= LUB` => schedulable set;
- `1 >= U(n) >= LUB` => undetermined case. The test doesn't always work/grantee
  if the system is schedulable/unschedulable.

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

![LUB test](../_resources/141d8b59089e7d099a33d585a9557aaa.png)

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](../_resources/c9d5597207431601059a0d289b2881ea.png)

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

- In the first system, the periods are harmonic. The tasks use 100% of the CPU,
  and the task-set is schedulable;
- In the second system, the periods aren't harmonic. In fact, there is less
  "load" in the system as the second task has more _slack_ (doesn't run as
  often). Still, we aren't using 100% of the CPU and if we reduce the period of
  any of the tasks for any amount (make them more frequent), the task-set won't
  be schedulable.

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](../_resources/aac46ddffd2050da1d801902bb2f210b.png)

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:

- Global - Interrupt disabling and/or preemption disabling. These are only
  feasible for extremely small critical regions as they block the whole system.
  We won't really deal with this in our implementation.
- Local - **Mutexes** and **semaphores**.

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