FreeRTOS is a free, open-source embedded real-time operating system . Studying its kernel can provide a better understanding of the implementation principles of embedded operating systems. This article mainly explains the implementation principles of the task scheduling mechanism, time management mechanism, task management mechanism, and memory allocation strategy in the FreeRTOS system, and points out the advantages and disadvantages of FreeRTOS in applications.
In the embedded systems field, embedded real-time operating systems (RTOS) are being used more and more widely. Using an RTOS allows for more rational and efficient use of CPU resources, simplifies application software design, shortens system development time, and better ensures system real-time performance and reliability. Because RTOS requires certain system resources (especially RAM), only a few real-time operating systems, such as μC/OS-II, embOS, Salvo, and FreeRTOS, can run on microcontrollers with limited RAM. Compared to commercial operating systems like μC/OS-II and embOS, FreeRTOS is a completely free operating system with open-source code, portability, customizability, and flexible scheduling strategies, making it easy to port to various microcontrollers.
The difference between real-time operating systems and non-real-time operating systems
The differences between them are shown in the image below:
In the diagram above, the task on the right has a higher priority than the task on the left. Looking at the real-time operating system, when the higher-priority task 2 is ready, even if task 1 is running, it must immediately relinquish the CPU. Just like an interrupt, task 2 is executed first. Only when task 2 finishes execution or actively suspends (sleeps) to relinquish the CPU can task 1 continue running.
uCOS is such a real-time operating system; it has a preemptive kernel. I've debated with many colleagues whether a high-priority task can interrupt a low-priority task and be executed immediately when a high-priority task is ready and a low-priority task is executing without a sleep state. Unfortunately, many still insist that a sleep state is necessary for task switching. Each time, I can only helplessly use experiments to prove something that shouldn't even be debated.
Now let's look at how time-slice-based operating systems like Linux, Windows, and OSX react to this problem. Undoubtedly, they are non-real-time operating systems; the CPU is not preemptible. As shown in the diagram, even if a high-priority task is ready, it cannot immediately interrupt a low-priority task for execution. It must wait until the low-priority task actively suspends (sleeps) or its time slice expires. Therefore, we often encounter application unresponsiveness issues when using a PC, meaning hardware resources are occupied by other tasks, and the current task cannot be executed immediately.
We usually use non-real-time operating systems for entertainment and work. So when should we use a real-time operating system? Imagine a launched missile needs to perform an attitude adjustment task, while other unimportant tasks are being performed. With a non-real-time operating system, it might wait a while and then pop up a window telling you that the application is unresponsive (if it has a pop-up window). By the time the pop-up appears, the missile has already been launched into outer space! Undoubtedly, devices with high-priority tasks that cannot wait even a moment must use a real-time operating system if you don't want your missile to be launched into outer space.
1. FreeRTOS operating system functions
As a lightweight operating system, FreeRTOS provides features including task management, time management, semaphores, message queues, memory management, and logging, which can basically meet the needs of smaller systems. The FreeRTOS kernel supports priority scheduling algorithms, where each task can be assigned a priority based on its importance, and the CPU always allows the highest-priority ready task to run first. The FreeRTOS kernel also supports round-robin scheduling algorithms, allowing different tasks to use the same priority; when no higher-priority task is ready, tasks of the same priority share CPU time.
The FreeRTOS kernel can be configured as either a preemptive or non-preemptive kernel according to user needs. When FreeRTOS is configured as a preemptive kernel, a high-priority task in the ready state can preempt the CPU usage rights of a low-priority task, thus ensuring that the system meets real-time requirements. When FreeRTOS is configured as a non-preemptive kernel, a high-priority task in the ready state can only run after the currently running task actively releases its CPU usage rights, thus improving CPU efficiency.
2. Principles and Implementation of the FreeRTOS Operating System
2.1 Implementation of Task Scheduling Mechanism
Task scheduling is a crucial concept and core technology of embedded real-time operating systems. For preemptive kernels, a high-priority task, once ready, can preempt a lower-priority task from using the CPU, improving the system's real-time responsiveness. Unlike μC/OS-II, FreeRTOS has no limit on the number of system tasks and supports both priority-based and round-robin scheduling algorithms. Therefore, FreeRTOS uses a doubly linked list instead of a task readiness table for task scheduling. The system-defined linked list and its node data structure are shown below:
typedef struct xLIST { // Define the linked list structure
unsignedportSHORPTusNumberOfItems;
//usNumberOfItems is the length of the linked list; 0 indicates the linked list is empty.
volatile xListItem*pxHead; //pxHead is the head pointer of the linked list
volatile xListItem*pxIndex; //pxIndex points to the current node of the linked list
volatile xListItemxListEnd; // xListEnd is the tail node of the linked list
xList;
struct xLIST_ITEM{ // Defines the structure of the linked list nodes
portTicktypexItemValue;
//The value of xItemValue is used to implement time management.
//portTickType is the clock tick data type.
// You can choose between 16-bit or 32-bit as needed.
volatilestructxLIST_ITEM*pxNext;
// Points to the previous node of the linked list
void *pvOwner; // Pointer to the task control block where this linked list node is located
void *pvContainer; // Points to the linked list containing this linked list node;
In FreeRTOS, each task corresponds to a Task Control Block (TCB), which is defined as follows:
typedefstructtskTaskControlBlock{
portSTACK_TYPE*pxTopOfStack;
// Points to the end of the task stack
portSTACK_TYPE*pxStack;
// Points to the beginning of the task stack
unsignedportSHORTusStackDepth; // Defines the stack depth
signedportCHARpcTaskName[tskMAX_TASK_NAME_LEN]; //Task name
unsignedportCHARucPriority; //Task priority
xListItemxGenericListItem;
// Used to insert TCB into the ready list or waiting list.
xListItemxEventListItem;
// Used to insert TCBs into the event list (such as a message queue).
unsignedportCHARucTCBNumber; // Used for recording functions
}tskTCB;
Copy code
FreeRTOS defines the ready task linked list array as xListpxReady_TasksLists[portMAX_PRIORITIES]. Here, portMAX_PRIORITIES represents the system-defined maximum priority. To make a task with priority n ready, the node xGenericListItem in the corresponding TCB of this task needs to be inserted into the linked list pxReadyTasksLists[n], and the pvContainer in xGenericListItem needs to point to pxReadyTasksLists[n].
When scheduling tasks, the scheduling algorithm first implements priority scheduling. The system searches the ready task linked list array (usNumberOfItems) for the first non-zero priority value, in descending order of priority. This priority is the highest ready priority, and priority scheduling is implemented accordingly. If there is only one ready task at this priority, this ready task enters the running state; if there are multiple ready tasks at this priority, a round-robin scheduling algorithm is used to implement multi-task execution in turn.
If the round-robin scheduling algorithm is executed at priority n, the system first obtains the next node pointed to by the current node by executing the statement (pxReadyTasksLists[n]) → pxIndex = (pxReadyTasks-Lists[n]) → pxIndex → pxNext. Then, it obtains the corresponding task control block through the pvOwner pointer of this node, and finally puts the task corresponding to this task control block into the running state. Therefore, in FreeRTOS, the switching time between tasks of the same priority is one clock cycle.
Taking Figure 1 as an example, let the maximum number of tasks in the system be porttMAX_PRIORITIES. When task scheduling is performed at a certain moment, pxReadyTasksLists is obtained. usNumberOfItems=O(i=2...portMAX_PRIORITIES) and pxReadyTasksLists[1]. usNumberOfItems=3. From this kernel, we can know that the current highest ready priority is 1, and three tasks under this priority have entered the ready state. Since there are multiple ready tasks under the highest ready priority, the system needs to execute the round-robin scheduling algorithm to realize task switching; through the pointer pxIndex, we can know that task 1 is the current task, and the pxNext node of task 1 points to task 2. Therefore, the system points pxIndex to task 2 and executes task 2 to realize task scheduling. When the next clock tick arrives, if the highest ready priority is still 1, as shown in the figure, the system will point pxIndex to task 3 and execute task 3.
To speed up task scheduling, FrecRTOS tracks the highest priority of currently ready tasks using the variable ucTopReadyPriority. When a task is added to the ready list, if its priority is higher than ucTopReadyPriority, then that task's priority is assigned to ucTopReadyPriority. This way, during priority-based scheduling, the scheduling algorithm starts searching from ucTopReadyPriority instead of portMAX_PRIORITIES. This speeds up the search process and reduces kernel shutdown time.
To speed up task scheduling, FrecRTOS tracks the highest priority of currently ready tasks using the variable ucTopReadyPriority. When a task is added to the ready list, if its priority is higher than ucTopReadyPriority, then that task's priority is assigned to ucTopReadyPriority. This way, during priority-based scheduling, the scheduling algorithm starts searching from ucTopReadyPriority instead of portMAX_PRIORITIES. This speeds up the search process and reduces kernel shutdown time.
2.2 Implementation of Task Management
Effective management of multiple tasks is a primary function of an operating system. FreeRTOS provides functions such as task creation, deletion, suspension, resumption, priority setting, and task-related information retrieval. The following discussion focuses on the implementation of task creation and deletion in FreeRTOS. When the `sTaskCreate()` function is called to create a new task, FreeRTOS first allocates the necessary memory. If memory allocation is successful, it initializes the task name, stack depth, and priority of the task control block, and then initializes the task control block's stack according to the stack's growth direction. Next, FreeRTOS adds the currently created task to the ready task list. If the current task has the highest priority, this priority is assigned to the variable `ucTopReadyPriority` (its function is explained in Section 2.1). If the task scheduler is already running and the currently created task has the highest priority, a task switch occurs.
Unlike μC/OS-II, task deletion in FreeRTOS is performed in two steps. When the user calls the vTaskDelete() function, the first step of task deletion is executed: FreeRTOS first removes the task to be deleted from the ready task list and the event wait list, then adds the task to the task deletion list. If the task to be deleted is a currently running task, the system executes the task scheduling function, thus completing the first step of task deletion. When the system's idle task, i.e., the prvldleTask() function, runs, if it finds a task waiting to be deleted in the task deletion list, the second step of task deletion is performed: the memory space occupied by the task is released, and the task is removed from the task deletion list, thus completely deleting the task. It is worth noting that in FreeRTOS, when the system is configured with a non-preemptive kernel, the idle task also has the function of switching between tasks.
By comparing the specific code of μC/OS-II and FreeRTOS, it was found that the two-step deletion strategy is beneficial to reduce kernel shutdown time and the execution time of task deletion functions, especially when deleting multiple tasks.
2.3 Implementation of Time Management
The typical time management function provided by FreeRTOS is vTaskDelay(), which allows you to delay a task for a specific period of time. In FreeRTOS, if a task needs to be delayed by xTicksToDelay clock ticks, the kernel adds xTicksToDelay to the total number of clock ticks currently running (defined as xTickCount, 32 bits) to obtain the number of clock ticks xTimeToWake for the task's next wake-up. Then, the kernel removes the task's task control block from the ready list, assigns xTimeToWake as the node value to the task's xItemValue, and inserts the task control block into different linked lists according to the value of xTimeToWake. If xTimeToWake > xTickCount, meaning there is no overflow in the calculation, the kernel inserts the task control block into the pxDelayedTaskList linked list; if xTimeToWake > xTickCount, meaning there is no overflow in the calculation, the kernel inserts the task control block into the pxDelayedTaskList linked list; if xTimeToWake > xTickCount, the kernel inserts the task control block into the pxDelayedTaskList linked list.
At each clock tick, the kernel increments the current xTick-Count by 1. If xTick-Count is 0, indicating an overflow, the kernel uses pxOverflowDelayedTaskList as the current linked list; otherwise, it uses pxDelayedTaskList. The kernel then compares xTick-Count with xTimeToWake of each node in the linked list. If xTick-Count is equal to or greater than xTimeToWake, the delay time has expired, and the task should be removed from the waiting list and added to the ready list.
Therefore, unlike μC/OS-II, FreeRTOS uses an additive approach for time management. Its advantage is that the execution time of the clock tick function is largely independent of the number of tasks, while the execution time of μC/OS-II's OSMoncTick() is proportional to the number of tasks created in the application. Thus, when there are many tasks, FreeRTOS's time management method can effectively speed up the execution of clock tick interrupt routines.
2.4 Memory Allocation Strategy
FreeRTOS requires the allocation of RAM whenever tasks, queues, and semaphores are created. While the `malloc()` and `free()` functions can be used to allocate and release memory, these functions have the following drawbacks: they are not available in all embedded systems, they consume variable program space, they lack reproducibility, and their execution time is unpredictable. Therefore, in addition to `malloc()` and `free()`, FreeRTOS provides two other memory allocation strategies, allowing users to choose the appropriate strategy based on their needs.
The first method is to simply divide a large block of memory into several smaller blocks, each corresponding to the required memory size. The advantage of this approach is its simplicity and precisely predictable execution time, making it suitable for systems where kernel scheduling occurs only after all tasks and queues have been created. The disadvantage is that, because memory cannot be effectively released, applications cannot delete tasks or queues while the system is running.
The second method uses linked lists to allocate memory, enabling dynamic creation and deletion of tasks or queues. The system organizes the free memory list in ascending order based on the size of the free memory blocks. When an application requests a block of memory, the system searches the free memory list sequentially according to the requested memory size to find the smallest free memory block that meets the request. To improve memory utilization efficiency, if the free memory block is larger than the requested memory, the system will split it in two. One piece is used to satisfy the memory request, and the other is inserted into the linked list as a new free memory block.
The implementation of Method 2 is illustrated below using Figure 2 as an example. Assume that the RAM used for dynamic allocation is 8KB. The system first initializes the free memory block list, treating all 8KB of RAM as a single free memory block. When the application requests 1KB and 2KB of memory respectively, the size of the free memory block becomes 5KB. After the 2KB of memory is used up, the system needs to insert it into the existing free memory block list. Since 2KB < 5KB, this 2KB is inserted before the 5KB memory block. If the application needs to request another 3KB of memory, and the smallest free memory block in the free memory block list that can satisfy the memory request is 5KB, then the 5KB memory is split into two parts: the 3KB part is used to satisfy the memory request, and the 2KB part is inserted into the list as a new free memory block. Subsequently, when the 1KB of memory is used up and needs to be released, the system will insert the 1KB of memory into the free memory list sequentially.
The advantage of Method 2 is that it can use memory efficiently according to task needs, especially when different tasks require different amounts of memory. The disadvantage of Method 2 is that it cannot combine memory released by the application with existing free memory. Therefore, if the application frequently requests and releases memory of "random" sizes, it may cause a large amount of memory fragmentation. This requires that the size of memory requested and released by the application be a "finite" fixed value (as shown in Figure 2, the size of memory requested and released is fixed at 1KB, 2KB, or 3KB). Another disadvantage of Method 2 is that the program execution time has a certain degree of uncertainty.
μC/OS-II's memory management mechanism manages large contiguous blocks of memory as partitions, with each partition containing an integer number of memory blocks of the same size. Because each partition is the same size, frequent memory allocation and deallocation do not cause memory fragmentation. However, its drawback is relatively low memory utilization. When the size of allocated and deallocated memory is a fixed value (e.g., 2KB each), FreeRTOS's Method 2 memory allocation strategy can achieve a similar memory management effect to μC/OS-II.
2.5 Porting FreeRTOS
The FreeRTOS operating system can be easily ported to different processors, and ports to multiple processors, including ARM, MSP430, AVR, PIC, and C8051F, are currently available. Porting FreeRTOS to different processors is similar to μC/OS-II, so this article will not elaborate on FreeRTOS porting. Furthermore, the TCP/IP protocol stack μIP has been ported to FreeRTOS; the specific code can be found on the FreeRTOS website.
2.6 Shortcomings of FreeRTOS
Compared to the common μC/OS-II operating system, FreeRTOS has both advantages and disadvantages. Its shortcomings are twofold. First, in terms of system service functionality, FreeRTOS only provides implementations of message queues and semaphores, and cannot send messages to the message queue in a last-in-first-out (LIFO) order. Second, FreeRTOS is only an operating system kernel, requiring external expansion with third-party GUIs (Graphical User Interfaces), TCP/IP protocol stacks, FS (File System), etc., to implement a more complex system, unlike μC/OS-II, which can seamlessly integrate with μC/GUI, μC/FS, μC/TCP-IP, etc.
3. Conclusion
As an open-source operating system, learning FreeRTOS allows for a better understanding of the implementation principles of embedded real-time operating systems. As a free operating system, using FreeRTOS can reduce system costs and simplify development while meeting the basic needs of smaller systems. In practice, a temperature control system built using the FreeRTOS operating system and the MSP430 microcontroller has proven stable and reliable, achieving good control performance. It is believed that with continued development, FreeRTOS will further improve its functionality to better meet the demands for real-time performance, reliability, and ease of use in embedded operating systems.
