Author: Liu Bin, Wang Qi, Liu Lili, Ocean University of China
Abstract: FreeRTOS is a free embedded real-time operating system with open source code. By studying its kernel, one can better understand the implementation principles of embedded operating systems. This article mainly elaborates on the task scheduling mechanism, time management mechanism, task management mechanism, and memory allocation strategy implementation principles in the FreeRTOS system, and points out the advantages and disadvantages of FreeRTOS in applications. In the embedded field, embedded real-time operating systems are becoming increasingly widely used. Using an embedded real-time operating system (RTOS) can utilize CPU resources more reasonably and effectively, simplify application software design, shorten system development time, and better ensure system real-time performance and reliability. Since RTOS requires a certain amount of system resources (especially RAM), only a few real-time operating systems like μC/OS-II, embOS, Salvo, and FreeRTOS can run on small RAM microcontrollers. Compared to commercial operating systems like C/OS-II and embOS, FreeRTOS is a completely free operating system with open source code, portability, scalability, and flexible scheduling strategies, making it easy to port to various microcontrollers.
Differences Between Real-Time Operating Systems and Non-Real-Time Operating Systems
The differences between them are detailed in the figure below:
In the above figure, 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 give up CPU usage, just like an interrupt, executing task 2 first. After task 2 is completed or voluntarily suspends (sleeps) to yield the CPU, task 1 can continue to run.
uCOS is such a real-time operating system, and it has a preemptive kernel. I have debated with many colleagues about whether a high-priority task can interrupt a low-priority task that is running without sleeping when it becomes ready. Unfortunately, many people still insist that sleep is required to switch tasks, and I can only helplessly prove this with experiments each time.
Now, let’s see how our Linux/Windows/OSX, which are based on time-slice rotation, handle this issue. Undoubtedly, they are all non-real-time operating systems, and the CPU is non-preemptive. As can be seen from the above figure, even if a high-priority task becomes ready, it cannot immediately interrupt a low-priority task to execute; it must wait until the low-priority task voluntarily suspends (sleeps) or the time slice ends to be executed. Therefore, we often encounter unresponsive applications when using PCs. This means that 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 office work, so when should we use real-time operating systems? Imagine a missile that needs to perform an attitude adjustment task. If there are other non-essential tasks running at that moment, if it is a non-real-time operating system, it may wait a while and then pop up a window telling you that the application is unresponsive (if it has a window to pop up). By the time the pop-up appears, the missile may have already shot into outer space! Undoubtedly, devices with such high-priority tasks cannot afford to wait even a moment and must use a real-time operating system if you don’t want your missile to go into outer space.
1. Functions of FreeRTOS Operating System As a lightweight operating system, FreeRTOS provides functions including task management, time management, semaphores, message queues, memory management, logging functions, etc., which can basically meet the needs of smaller systems. The FreeRTOS kernel supports priority scheduling algorithms, and each task can be assigned a certain priority based on its importance. The CPU always allows the highest-priority task in the ready state to run first. The FreeRTOS kernel also supports round-robin scheduling algorithms, allowing different tasks to share CPU time when no higher priority tasks are ready. The FreeRTOS kernel can be set to either a preemptive kernel or a non-preemptive kernel based on user needs. When FreeRTOS is set to a preemptive kernel, ready high-priority tasks can preempt the CPU usage of low-priority tasks, ensuring that the system meets real-time requirements. When FreeRTOS is set to a non-preemptive kernel, ready high-priority tasks can only run after the currently running task voluntarily releases CPU usage, which can improve CPU running efficiency.
2. Principles and Implementation of FreeRTOS Operating System 2.1 Implementation of Task Scheduling Mechanism The task scheduling mechanism is an important concept in embedded real-time operating systems and is a core technology. For preemptive kernels, once a high-priority task is ready, it can preempt the CPU usage of lower priority tasks, improving the system’s real-time response capability.
Scheduling Methods Supported by FreeRTOSFreeRTOS supports three scheduling methods: preemptive scheduling, time-slice scheduling, and cooperative scheduling. In practice, preemptive scheduling and time-slice scheduling are mainly used, while cooperative scheduling is rarely used.
Preemptive Scheduling Each task has a different priority, and tasks will run continuously until preempted by a higher-priority task or encounter a blocking API function, such as vTaskDelay. Time-Slice Scheduling Each task has the same priority, and tasks will run for a fixed number of time slices or encounter a blocking API function, such as vTaskDelay, before executing task switching among tasks of the same priority.
What is a Scheduler In simple terms, a scheduler uses relevant scheduling algorithms to determine which task needs to be executed at the current moment. All schedulers have a common characteristic: The scheduler can distinguish between ready tasks and suspended tasks (tasks that are suspended due to delays, waiting for semaphores, waiting for mailboxes, waiting for event groups, etc.). The scheduler can select one of the ready tasks and then activate it (by executing that task). The currently executing task is the running task. The biggest difference between different schedulers is how they allocate completion time among ready tasks. The core of embedded real-time operating systems is the scheduler and task switching, and the core of the scheduler is the scheduling algorithm. The implementation of task switching is not significantly different among various embedded real-time operating systems; the basic hardware kernel architecture is similar, and task switching is also similar. However, the scheduling algorithms can differ. Below, we will mainly learn about preemptive schedulers and time-slice schedulers. The basic concept of a preemptive scheduler is that in practical applications, different tasks require different response times. For example, in an application that requires the use of a motor, keyboard, and LCD display, the motor needs a faster response than the keyboard and LCD. If we use a cooperative scheduler or time-slice scheduling, the motor will not receive a timely response. In this case, preemptive scheduling is a must. If preemptive scheduling is used, once the highest-priority task is ready, it can always gain control of the CPU. For example, when a running task is preempted by another high-priority task, the current task’s CPU usage is taken away, or it is said to be suspended, and the high-priority task immediately gains control of the CPU and runs. For instance, if an interrupt service program makes a high-priority task ready, when the interrupt completes, the interrupted low-priority task is suspended, and the high-priority task begins running. Using a preemptive scheduler makes it predictable when the highest-priority task can gain control of the CPU and run, while optimizing task-level response times. Overall, the most critical point to grasp about learning preemptive scheduling is that each task is assigned a different priority, and the preemptive scheduler will select the highest-priority task from the ready list and run that task. The implementation of FreeRTOS’s preemptive scheduler is that if the user disables time-slice scheduling in the FreeRTOS configuration file FreeRTOSConfig.h, then each task must be configured with a different priority. When FreeRTOS multi-tasking starts executing, it will generally execute as follows: The highest-priority task Task1 is executed first and will continue running until it encounters a system blocking API function, such as a delay, waiting for an event flag, or waiting for a semaphore. Task1 will be suspended, releasing CPU execution rights, allowing lower-priority tasks to execute. The FreeRTOS operating system continues to execute the next highest-priority task in the task ready list, Task2. During Task2’s execution, there are two scenarios: Task1 may recover from the suspended state to the ready state due to a delay, receiving a semaphore message, etc., and under the action of the preemptive scheduler, Task2’s execution will be preempted by Task1. Task2 will continue running until it encounters a blocking API function, such as a delay, waiting for an event flag, or waiting for a semaphore. Task2 will be suspended, and the next highest-priority task in the ready list will be executed. If the user creates multiple tasks and uses the preemptive scheduler, the execution will generally follow the above two rules. According to the preemptive scheduler, the current task is either preempted by a higher-priority task or releases CPU usage by calling a blocking API to allow lower-priority tasks to execute; if there are no user tasks, an idle task will execute. 
Operating Conditions: This description only applies to preemptive scheduling. Create three tasks: Task1, Task2, and Task3. Task1 has a priority of 1, Task2 has a priority of 2, and Task3 has a priority of 3. In the FreeRTOS operating system, the lower the numerical value set, the lower the task priority, so Task3 has the highest priority, and Task1 has the lowest priority. This flowchart is part of the FreeRTOS operating process. The operating process is described as follows:
At this point, Task1 is running. During its execution, Task2 becomes ready, and under the action of the preemptive scheduler, Task2 preempts the execution of Task1. Task2 enters the running state, and Task1 transitions from the running state to the ready state. Task2 is running, and during its execution, Task3 becomes ready, and under the action of the preemptive scheduler, Task3 preempts the execution of Task2. Task3 enters the running state, and Task2 transitions from the running state to the ready state. During Task3’s execution, it calls a blocking API function, such as vTaskDelay, and Task3 is suspended. Under the action of the preemptive scheduler, the next highest-priority task to execute is Task2, which transitions from the ready state to the running state. Task2 is running, and during its execution, Task3 becomes ready again. Under the action of the preemptive scheduler, Task3 preempts the execution of Task2. Task3 enters the running state, and Task2 transitions from the running state to the ready state. The above describes a simple process of task scheduling and switching through preemptive scheduling among tasks of different priorities.
Basic Concept of Time-Slice Scheduler In small embedded RTOS, the most commonly used time-slice scheduling algorithm is the Round-robin scheduling algorithm. This scheduling algorithm can be used in preemptive or cooperative multitasking. Additionally, time-slice scheduling is suitable for situations where task real-time response is not required. Implementing the Round-robin scheduling algorithm requires assigning a dedicated list to tasks of the same priority to record the currently ready tasks and allocating a time slice (the length of time to run) for each task.
The implementation of the FreeRTOS time-slice scheduler is that only tasks of the same priority will use time-slice scheduling. Additionally, the user needs to enable the macro definition in the FreeRTOSConfig.h file: #define configUSE_TIME_SLICING 1. By default, this macro definition has already been enabled in the FreeRTOS.h file, so users do not need to enable it separately in the FreeRTOSConfig.h file. Below, we will illustrate the operation process of time-slice scheduling in FreeRTOS with the following flowchart to give everyone a visual understanding. 
Operating Conditions: This description only applies to time-slice scheduling. Create four tasks of the same priority: Task1, Task2, Task3, and Task4. Each task is allocated a time slice size of 5 system clock ticks. The operating process is described as follows: First, run Task1, and after running for 5 system clock ticks, switch to Task2 through time-slice scheduling. Task2 runs for 5 system clock ticks, then switches to Task3 through time-slice scheduling. Task3, during its execution, calls a blocking API function. Even though the time slice size of 5 system clock ticks has not been exhausted, it will still switch to the next task, Task4, through time-slice scheduling. (Note that the unused time slice will not be used again; the next time Task3 is executed, it will still run for 5 system clock ticks.) Task4 runs for 5 system clock ticks, then switches back to Task1 through time-slice scheduling. The above describes a simple process of task scheduling and switching through time-slice scheduling among tasks of the same priority.
Conclusion:
Time-slice scheduling and preemptive scheduling are generally both enabled, so that when priorities are the same, time-slice scheduling is used, and when priorities differ, preemptive scheduling is used. By default, time-slice scheduling is enabled in FreeRTOS.h:
While preemptive scheduling requires the user to enable it, it is generally enabled in FreeRTOSConfig.h:
Different from μC/OS-II, FreeRTOS does not limit the number of system tasks, supporting both priority scheduling algorithms and round-robin scheduling algorithms. Therefore, FreeRTOS uses a bidirectional linked list instead of a ready task table to perform task scheduling. The system-defined linked list and linked list node data structures are as follows:
FreeRTOS defines the ready task linked list array as xList pxReadyTasksLists[portMAX_PRIORITIES]. Where portMAX_PRIORITIES is the system-defined maximum priority. To make the task with priority n enter the ready state, the corresponding node xGenericListItem in the TCB of this task must be inserted into the linked list pxReadyTasksLists[n], and the pvContainer in xGenericListItem must point to pxReadyTasksLists[n] to achieve this. When scheduling tasks, the scheduling algorithm first implements priority scheduling. The system searches for the first non-zero priority in the ready task linked list array in descending order of priority. This priority is the current highest ready priority, based on which priority scheduling is implemented. If there is only one ready task at this priority, it enters the running state; if there are multiple ready tasks at this priority, the round-robin scheduling algorithm is used to execute multiple tasks in turn. If executing round-robin scheduling at priority n, the system first executes the statement (pxReadyTasksLists[n])->pxIndex = (pxReadyTasksLists[n])->pxIndex->pxNext to get the next node pointed to by the current node, then uses the pvOwner pointer of this node to get the corresponding task control block, and finally makes this task control block’s corresponding task enter the running state. As can be seen, in FreeRTOS, the context switch time between tasks of the same priority is one clock tick cycle. Taking Figure 1 as an example, suppose the system’s maximum task number is portMAX_PRIORITIES, at a certain moment during task scheduling, it is found that pxReadyTasksLists[i].usNumberOfItems=O(i=2…portMAX_PRIORITIES) and pxReadyTasksLists[1].usNumberOfItems=3. Thus, the kernel knows that the current highest ready priority is 1, and there are three tasks in the ready state at this priority. Since there are multiple ready tasks at the highest ready priority, the system must execute the round-robin scheduling algorithm to achieve task switching; through the pointer pxIndex, it can be seen that task 1 is the current task, and task 1’s pxNext node points to task 2. Therefore, the system points pxIndex to task 2 and executes task 2 to achieve task scheduling. When the next clock tick arrives, if the highest ready priority remains 1, as can be seen from the figure, the system will point pxIndex to task 3 and execute task 3.
Figure 1 Task Scheduling Illustration
To speed up task scheduling, FreeRTOS tracks the current highest ready priority through the variable ucTopReadyPriority. When a task is added to the ready linked list, if this task’s priority is higher than ucTopReadyPriority, the task’s priority is assigned to ucTopReadyPriority. Thus, when performing priority scheduling, the scheduling algorithm starts searching from ucTopReadyPriority instead of portMAX_PRIORITIES. This speeds up the search and shortens the kernel interrupt time.
2.3 Implementation of Time Management
FreeRTOS provides a typical time management function called vTaskDelay(). Calling this function allows a task to be delayed for a specific period. In FreeRTOS, if a task wants to delay for xTicksToDelay clock ticks, the system kernel adds the total number of clock ticks the system has run (defined as xTickCount, 32-bit length) to xTicksToDelay to obtain the clock ticks number xTimeToWake for the task’s next wake-up. Then, the kernel removes the task’s task control block from the ready linked list, assigns xTimeToWake as the node value to the task’s xItemValue, and inserts the task control block into different linked lists based on the xTimeToWake value. 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 an overflow in the calculation, the kernel inserts the task control block into the pxOverflowDelayedTaskList linked list.
Each time a clock tick occurs, the kernel increments the current xTickCount by 1. If the result of xTickCount is 0, an overflow occurs, and the kernel will use pxOverflowDelayedTaskList as the current linked list; otherwise, the kernel will use pxDelayedTaskList as the current linked list. The kernel then compares xTickCount with each node’s xTimeToWake in the linked list. If xTickCount is equal to or greater than xTimeToWake, it indicates that the delay time has arrived, and the task should be removed from the waiting list and added to the ready list.
Unlike μC/OS-II, FreeRTOS adopts an “addition” method to implement time management. The advantage is that the execution time of the time tick function is basically independent of the number of tasks, while μC/OS-II’s OSTimeTick() execution time is proportional to the number of tasks created in the application. Therefore, when the number of tasks is large, FreeRTOS’s time management method can effectively speed up the execution of clock tick interrupt programs.
2.4 Memory Allocation Strategy Every time a task, queue, or semaphore is created, FreeRTOS requires a certain amount of RAM to be allocated. Although using malloc() and free() functions can achieve memory allocation and release, these two functions have the following disadvantages: they are not available in all embedded systems, consume unpredictable program space, lack reentrancy, and have uncertain execution times. Therefore, in addition to using malloc() and free() functions, FreeRTOS also provides two other memory allocation strategies, allowing users to choose different memory allocation strategies based on actual needs.
The first method is to simply divide a large block of memory into several small blocks according to the size of the required memory. The advantage of this approach is that it is relatively simple, with strictly determinable execution times, suitable for systems where all tasks and queues are created before kernel scheduling; the disadvantage is that memory cannot be effectively released, and the application cannot delete tasks or queues during system operation.
The second method is to use linked lists to allocate memory, allowing for dynamic creation and deletion of tasks or queues. The system organizes free memory blocks by size in a linked list from smallest to largest. When the application requests a block of memory, the system searches the free memory linked list in order to find the smallest free memory block that meets the request. To improve memory usage efficiency, when a free memory block is larger than the requested memory, the system splits this free memory block into two parts. One part is used to meet the memory request, and the other part is inserted as a new free memory block into the linked list.
Below, an example of the implementation of method 2 is presented. Suppose the total RAM for dynamic allocation is 8KB; the system first initializes the free memory block linked list, treating the entire 8KB RAM as a single free memory block. When the application requests 1KB and 2KB of memory, the size of the free memory block becomes 5KB. When the 2KB memory is used up, the system needs to insert the 2KB into the existing free memory block linked list. Since 2KB < 5KB, it is inserted before the 5KB memory block. If the application requests 3KB of memory again, the smallest free memory block that meets the allocation requirement in the free memory linked list is 5KB. Therefore, the 5KB memory is split into two parts: a 3KB part to satisfy the memory request, and a 2KB part inserted as a new free memory block in the linked list. Subsequently, if the 1KB memory is used up and needs to be released, the system will insert the 1KB memory into the free memory linked list in order.
Figure 2 Memory Management Using Free Memory Block Linked List
Method 2’s advantage is that it can efficiently use memory according to task needs, especially when different tasks require different sizes of memory. The disadvantage of method 2 is that it cannot mix the memory released by the application with the original free memory, so if the application frequently requests and releases “random” sizes of memory, it may cause a lot of memory fragmentation. This requires that the sizes of memory requested and released by the application be “limited” fixed values (such as in Figure 2, where the sizes of requested and released memory are fixed at 1KB, 2KB, or 3KB). Another disadvantage of method 2 is that the execution time has a certain degree of uncertainty.
μC/OS-II’s memory management mechanism manages continuous large blocks of memory by partitioning, where each partition contains an integer number of memory blocks of the same size. Since each partition’s size is the same, even if memory is frequently requested and released, it will not cause memory fragmentation issues. However, its disadvantage is relatively low memory utilization. When the sizes of requested and released memory are fixed values (such as both being 2KB), FreeRTOS’s method 2 memory allocation strategy can achieve similar memory management effects as μC/OS-II.
2.5 Portability of FreeRTOS FreeRTOS can be conveniently ported to different processors. It has been provided for various processors such as ARM, MSP430, AVR, PIC, C8051F, etc. The porting of FreeRTOS on different processors is similar to μC/OS-II, so this article will not elaborate further on the porting of FreeRTOS. Additionally, the TCP/IP protocol stack μIP has been ported to FreeRTOS, and the specific code can be found on the FreeRTOS website.
2.6 Limitations of FreeRTOS Compared to the common μC/OS-II operating system, FreeRTOS has both advantages and disadvantages. Its limitations are partly reflected in the system’s service functions, such as FreeRTOS only providing the implementation of message queues and semaphores, and it cannot send messages to the message queue in a last-in-first-out order. On the other hand, FreeRTOS is just an operating system kernel; it requires third-party extensions for GUI (Graphical User Interface), TCP/IP protocol stack, 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 can better grasp the implementation principles of embedded real-time operating systems. As a free operating system, using FreeRTOS can reduce system costs and simplify development difficulty while basically meeting the needs of smaller systems. In practice, a temperature control system composed of the FreeRTOS operating system and MSP430 microcontroller is stable and reliable, achieving good control effects. It is believed that with the passage of time, FreeRTOS will continue to improve its functionality to better meet people’s requirements for the real-time performance, reliability, and usability of embedded operating systems.
This article is reproduced from “Microcontroller and Embedded Applications”