Introduction to Real-Time Operating Systems Part 1

Introduction

In previous articles I have talked about microprocessors, what they are, what they do and looked at a case study of designing one from scratch based on the RISC-V ISA specifications. I recommend reading these first, if you are unfamiliar with processor design and RISC-V. Assuming we’ve done all that, and have a processor in our hands (and some of my mentees have done just such a thing), what can we do with it now?

Well, a processor by itself can’t even run without some additional hardware. At the very least it will need some sort of memory to house a program and have RAM for reading and writing data values.?More likely though, a whole other set of hardware will make up the environment in which the processor, or processors, sit. A System-on-Chip (SoC) is a typical embedded environment in which processors might find themselves. These will vary in design from one implementation to the next, depending on the particular needs, but they all share a set of characteristics. The diagram below shows a simplified generic SoC block diagram based around a RISC-V core:

Here we have a core connected to some sort of memory mapped bus infrastructure. It has a memory sub-system, with caches, memory protection unit or memory management unit, a DDR memory controller, and might have other features for FLASH, ROM or tightly coupled memory—you get the idea. A processor can be interrupted, so there is an interrupt controller for gathering and prioritizing?interrupts, and a timer which can also be a source of interrupts, as might any other present peripherals. An SoC is not much good if it can’t interact with the outside world to sample, measure, control and communicate, and so a set of peripherals would be present to implement this functionality. Which sets are present would be based on what the function of the system is meant to achieve. This could be quite limited and specific if required to control a particular scenario, to quite broad in scope as a single-board computer, such as the Raspberry Pi. What is common to most systems is that they have one or more processors, a bus system, memory, sources of interrupts (which could be the peripherals) and a set of peripheral functions to interact with the outside world. So, we’ve designed our processor core and we have our hardware environment. Is this all we need?

In the same set of articles on processor design, I finished off by looking at the RISC-V assembly language so that code could be constructed and run on the core. In other words, we started looking at software. Software is the key to a processor based system, as the whole point of the processor is to execute programs. With the hardware environment we have constructed, the software will have the task of configuring and using the peripherals to affect some overall system function. We could write a single program, as a single thread of code, to do all of this. We could even do all of this in assembly language. This might be a good approach for a very small system, such as one monitoring a signal and raising an alarm on some state of that signal. More generally, though, multiple peripherals will need to be running in parallel with each other, with the software taking care of all of them. This still might be done as a single program, written specifically for the function, but it is likely that each peripheral (or a sub-set group) will need to be treated independently, and so we would need a multi-tasking software environment via a multi-tasking operating system (OS), so that individual tasks can be assigned to each peripheral or sub-group, running independently from each other (though they might still interact).

In embedded systems, the interaction with the real world would normally need to have a sense of actual time passing. For example, with the signal monitoring I mentioned earlier, it may need to sample this at a certain rate to ensure that the latency from a ‘dangerous’ value to the alarm being raised meets a certain minimum requirement. This system would then said to be a ‘real-time’ system and the operating system running on it would be a real-time operating system (RTOS). The timer in the SoC diagram would ‘tick’ at some constant known real-time rate and be configurable to interrupt when some set time has passed.

In the rest of this article, I want to look at the basics of a real-time operating system, what it is and how it is used. We will be looking at the FreeRTOS operating system as an example, which is an open-source RTOS maintained by Amazon Web Services (AWS). This was chosen as it is lightweight, fairly simple to use and contains just the functionality required to have a useful RTOS in an embedded environment. In this first part, some groundwork will be covered and then we will look at ‘tasks’, in relation to a multi-tasking OS. In the next part we will look at how tasks communicate and synchronise, how they work across multiple processor cores, and then look at how FreeRTOS was ported to the rv32 RISC-V instruction set simulator (ISS). This last has been done so that the RTOS can be explored without the need for any additional and specific hardware. The configuration and porting requirements are also documented as an introduction and example for migrating to other potential target systems.

The aim of the articles is to give the reader some insights into the basic common features of an RTOS and how they might be used, as well as exploring a real-world example in FreeRTOS, ported to a RISC-V based virtual system so you can start exploring it right away.

Fundamentals

On top of the hardware layer, then, we need a software layer that will consist of the operating system, along with driver software to configure and use the peripherals. In addition to this, in order to run a ‘main’ program, we need a C run-time program (CRT). This initialises state and gets things ready before calling the user’s main program and we will look at our CRT program in detail, when discussing port FreeRTOS to the ISS, in a later article.

On top of these things, we can run an application, with a main program and any tasks that are created from this to manage the individual independent operations. This stack of hardware and software now looks something like the diagram below:

Here we have the hardware as the bottom layer—assume it looks like the first diagram, with all the other peripherals. The FreeRTOS operating system sits on top of this as a ‘bare-metal’ program. That is, there is no other software layer between it and running on the processor. Any driver code sits at this same level, as it will be peeking and poking registers of the peripherals that they drive in the memory mapped space without going through the OS necessarily. I’ve also placed the CRT program (crt0.S) at this same level for similar reasons, with it setting things up before any call to FreeRTOS is made. The application software sits on top of these, with a main program that creates a number of tasks and then starts the OS scheduler to manage the running of these tasks.

Some common features of real-time operating systems can be summarised as listed below:

• Tasks/co-routines: Creation, deletion/abortion, suspending/resuming
• Task communications: Notifications/events, messages/streams, queues
• Synchronisation: Semaphores, mutexes
• Timing: Delays, software timers

There will be many other features not listed above that can be found in various RTOS’s, but those listed are fairly fundamental and constitute the main features of the FreeRTOS kernel, and so we will concentrate on these in our discussions.

FreeRTOS is written largely in C. Certainly the code that is common to all the platforms on which it can run (the bulk of the code) is written in C. It also has platform and processor specific portions that differ from each other, and these can be a mixture of C and assembly programs. We will, of course, stick to the RISC-V specific code for this discussion, and the demonstration programs will be written in C. The application code can be written in C++, if desired, with C linkage for the OS’s API, and for any user provided functions, called by the OS. For simplicity, we will stick to C for this exercise.

The FreeRTOS kernel common code can be found in its repository under FreeRTOS/Source, with headers found in the include sub-directory in that location. A portable sub-directory is where the processor and platform specific code can be found. For our purposes, this is portable/GCC/RISC-V. For those that are curious, have a look in these directories. We will be alluding to this code in the discussions to follow.

Tasks

Since running tasks is the most obvious feature of a multi-tasking RTOS, we will start with this functionality. In the list above the first item mentions both tasks and coroutines. So, what’s the difference?

In general, a co-routine is just like a function but can be suspended to run other code and then resumed from where it left off. This would normally be because the co-routine ‘yielded’ control to some other routine (the caller, for example) to be ‘resumed’ at a later point. This is known as ‘co-operative scheduling’. A task runs freely and can be suspended at any point by an external routine (in kernel code), usually because of some ‘event’, such as an interrupt. This is known as pre-emptive scheduling.

In FreeRTOS, there are facilities for co-routines and cooperative scheduling, where co-routines cannot be suspended by other co-routines (but yield themselves), although they can be pre-empted by tasks. To keep things simple, we will stick to the most commonly used method, which is pre-emptive scheduling and tasks. The FreeRTOS website has more information about co-routines for those wishing to delve deeper.

Each task will have its own space within memory to store its local data state (its ‘context’), which is how it can pick up from where it was suspended. When switching between tasks the processor register state will need saving to the suspended task’s memory space, on a ‘stack’, and then the processor register state is updated with the saved state of the resuming task, which will also include updating registers pointing to the memory area for that task’s local data, via the stack pointer (sp) and, for global data, global pointer (gp) registers for RISC-V. Thus, the new task can start running from where it left off, with the register state and the local memory state returned to the values where it was suspended. It is often the case that when a user task is suspended, a kernel task is the one to be resumed. When the kernel task has completed its operation, it can then suspend and resume a user task—possibly a different one from that which was originally suspended.

Time Slicing

Having discussed in general terms how tasks can be suspended and resumed, the question is when does this happen? Given that this is an article on pre-emptive real-time operating systems, the most common reason for swapping out a task for another is due to a timing event. In a multi-tasking operating system, a set of running tasks will ‘share’ the processor run-time so that each makes progress. We briefly mentioned co-operative scheduling, but our main focus is on pre-emptive scheduling.

In an RTOS, this involves having a real-time clock that can be configured to generate an interrupt at regular intervals. For RISC-V this involves the mtime and mtimecmp memory mapped registers (see the “Timer Registers” section in part 2 of my article on processor design). We will talk about priorities shortly, but let’s assume, for now, that all the user tasks are the same priority and need to have similar access to the processor execution time. The timer will be set up to interrupt at some regular interval that is long enough to allow a task to progress more than just a few instructions, but short enough so that a task is active enough to respond to real-world events with a sufficiently low latency (this being dependent on the needs of the required function of the system). Usually this might be in the millisecond range—say from 1ms to 100ms. Each time the timer interrupts, the running user task will be suspended, and a new task resumed. It will cycle through each active task, giving each a proportion of the processor run time. This is known as ‘time-slicing’ and the tasks are said to be running ‘concurrently’. In this context, concurrently is different from running in parallel. The latter would be the case if the tasks were running on separate processors (which we will discuss later), but when running on a shared processor they are executing concurrently. From an external point of view, it looks like each task is running in parallel, but this is an illusion, though with a very similar result.

Priority

In the above discussion I made the assumption that all the tasks are running at the same priority and thus get an equal share of the processor time. However, a feature of an RTOS is that tasks can have different priorities. This is useful to distinguish between tasks that have to respond to events quickly, or capture data that is removed in a short time over tasks that need only respond more slowly, such as updating a display.

When a set of tasks are running with different priorities, at each time slice, the active task with the highest priority will always be selected—even if it is the task that is already running. Of course, if there is more than one task at this high priority, the processor time will be shared out between those tasks. The lower priority task, though, will not be run. Won’t this lock out the lower priority tasks forever?

Well, yes, if things are not set up correctly. We have discussed tasks, up until now, as if they are always active—i.e., they have something to do and are running code. This can only be the case if all the tasks are the same priority, and the time-slicing will sort out a fair share of run time. In a real-time system, however, tasks do not have things to do all the time. For example, a task might be responsible for capturing an analogue-to-digital’s measurement and storing it away for processing. This may happen infrequently, but the capture may have a small time window for when the data needs to be read and stored away, and so this task has high priority. When it is waiting for the next ADC reading, it can ‘sleep’. This mechanism could be that, when it calls to a function to read an ADC function, the code suspends the tasks, making it inactive. It could also setup an interrupt from the ADC when the next value is available, and this interrupt causes the kernel to make the task active once more. The task, now the highest priority, will be resumed and can capture the value before going to sleep again.

Tasks can also voluntarily suspend for a period of time. Calls to delay functions will suspend a task, to be resumed after some delay, or at some specific future time. The task will be inactive during that period and so will not be scheduled until that time has passed, where it will be put back on the list of active tasks. This use of delays is somewhat like cooperative scheduling where a task yields execution, but not quite. A coroutine specifically yields execution, but it does not know when it will be resumed. With tasks, calls to blocking functions that ultimately suspend the task have some criteria for resumption—a delay, or some result being available etc.

Interrupt service routines, though not tasks (and more like coroutines), have priorities even higher than for tasks. That is, if an unmasked interrupt occurs, the relevant interrupt service routine will be called, regardless of what the priority of active tasks are. Because of this, ISRs would normally be as short as possible so as not to lock out high priority tasks.

The diagram below shows a simple scenario with three tasks, timer interrupts and an external interrupt:

In this example there are three tasks: t0, t1 and t2. The t0 and t1 tasks both have the same priority, whilst the t2 task has a higher priority. In addition to these user tasks, the kernel has an idle task which will be automatically started. If no user task is active, the processor must still do ‘something’, and so it runs the idle task, which basically loops on a no-operation (nop). If the processor supports it, it can go into a low powered state. For example, the RISC-V processor can implement a wait-for-interrupt (wfi) instruction which puts the processor I low powered mode and will only power back up if an interrupt is received.

In the diagram, when the timer first generates an interrupt, the timer ISR is executed, and t0 is scheduled and run. It is assumed that t2, a higher priority task is suspended. For this example, we will say it is initially blocked waiting on an external interrupt. At some point t0 blocks, waiting on a 2 tick delay. Because t1, of the same priority, is ready to go t0 is no longer ready, it is run. It eventually blocks waiting on a single tick delay. The flow then returns to the idle task. At the next tick, t1 is resumed as it was waiting on the next tick, rather than the two ticks of t0. Before it blocks, an external interrupt event happens, running its ISR, and t2 now gets run, suspending t1. When t2 blocks again, t1 is the resumed…and so on.

Thus, in summary, all the tasks would normally have natural suspend points, allowing periods where lower priority tasks will be run when active. At each point where an interrupt occurs and runs an ISR (timer or other), or where a task is blocked by making a call to a blocking kernel function, such as a delay, kernel code is run to assess who gets to run next based on a task being ready to run and its priority over other ready tasks.

Within FreeRTOS, this is done with calls to xTaskSwitchContext(), found within the tasks.c source file. Part of the task’s context data (tskTaskControlBlock) is state that indicates the priority, ready state, and blocked state. An event list is kept of tasks, with a ready list and a delayed list, and ordered by priority. As events occur and time advances, tasks are added and removed from the event list as they are resumed or suspended. Thus, choosing and then switching between tasks becomes a matter of ordered list management. Some of the FreeRTOS Kernel API functions for tasks are listed below:

• xTaskCreate, xTaskDelete
• vTaskStartScheduler, vTaskEndScheduler
• vTaskSuspendAll, vTaskResumeAll
• ?uxTaskPriorityGet, vTaskPrioritySet
• vTaskDelay, vTaskDelayUntil

This list is not exhaustive, but overlaps the main subjects that we have covered so far and are hopefully now obvious in what they do. More details of these functions and how to use them can be found in the FreeRTOS API reference (under “Task Creation” and “Task Control”), but we will be looking at some examples that use the API functions when discussing running FreeRTOS on the RISC-V ISS.

Conclusions

This first article introduced what a real-time operating system is and some of its basic features, with reference to FreeRTOS. In particular the concept of a task as an independently running functions, running concurrently with other tasks. This was achieved with each task having its own private data space, that included information about its status as active or inactive. This allows switching between tasks to be efficient and simple by saving off register state and then updating the stack-point to point to a new task’s local data and restoring the register state for that task.

The concept of time-slicing was explained and the RTOS switching between active tasks at set ‘tick’ intervals. Tasks can have different priorities, with higher priority tasks being selected in preference to lower priority tasks. Also discussed was the fact that tasks can be suspended for other reasons apart from being deselected on time-slicing. This is when a task makes a call to a ‘blocking’ functions, which might be to read a value that is not yet available, or if it makes a call to a delay function which will suspend the task for a given number of ticks. The RTOS’s scheduler functionality provides the management for all of this task execution co-ordination.

In the next article will be discussed how tasks communicate and synchronise with each other, and even how this might be done when running on separate processor cores, in a multi-core environment. Then we will look at the porting of FreeRTOS to the rv32 RISC-V instructions set simulator, and some demonstrations of using the features.

For those that can’t wait until then, you can check out the riscV repository from github, and the freertos directory has a makefile to build a very simple demonstration program. A README.md file gives more details on the required prerequisites etc. You will, of course, also have to build the RISC-V ISS, in the iss directory, which can be done with visual studio on Windows, or using the provided makefile.lnx on Linux.