Search code examples
freertos

What is the complexity of the scheduler of the FreeRTOS?

I've searched through the documentation of FreeRTOS, but couldn't find anything related to the complexity of its scheduler. So, what is the complexity of it? Is there a way that I can detect it myself?

Solution

  • The FreeRTOS kernel stores the TCB (Task Control Block) instance pointers in an array of doubly-linked lists. Indexes of the array represent the priority group that a task belongs to. Here is a visual diagram of it. Note that the list contains only the TCB's of tasks that are in the ready state. Illustration of FreeRTOS Ready Task List Data Structure

    Each time the scheduler runs, the algorithm selects the first TCB that is located at the highest index*(i.e. highest priority)* possible. If the doubly-linked list of the highest priority has multiple elements, then it selects the first one. A round-robin mechanism is used for this purpose. It is obvious that this process is independent of the count of the tasks which are ready to be scheduled. Therefore, the time complexity is O(1).