FreeRTOS »

Priority - a key for Scheduler

Priority is the key which is informed to the operating system about the importance of a task and the order in which a group of waiting tasks needs to execute. By setting the priorities of the tasks, those that need to react to critical or time-sensitive events can preempt lower priority and background tasks.

#arm   #freertos  

Last update: 2022-06-29

---

Table of Content

Priority

Priority is the key which is informed to the operating system about the importance of a task and the order in which a group of waiting tasks needs to execute.

MCU runs user tasks in Thread Mode, interrupt handlers in Handler mode, thus there are two types of Priority.

Interrupt Priority

Lower Interrupt Priority Value means higher Interrupt Priority Level

• __NVIC_PRIO_BITS defines some bits used for Priority Levels.
• The lowest Interrupt priority is set by configLIBRARY_LOWEST_INTERRUPT_PRIORITY
• The maximum Interrupt priority is set by configLIBRARY_MAX_SYSCALL_INTERRUPT_PRIORITY

→ Priority of a peripheral interrupt should be between them.

• configKERNEL_INTERRUPT_PRIORITY decides the priority for the kernel interrupts:

  • SysTick: scheduler’s tick
  • PendSV: context switcher
  • SVC: superior call

  Refer to System-Call Exception.

• configMAX_SYSCALL_INTERRUPT_PRIORITY decides the maximum priority for APIs that is called from an ISR.

  • FreeRTOS APIs ending with FromISR are interrupt safe, but even these APIs should not be called from ISRs having priority above the priority defined by configMAX_SYSCALL_INTERRUPT_PRIORITY.

  → Any ISR that uses RTOS APIs must have priority manually set to a number being equal or greater than configMAX_SYSCALL_INTERRUPT_PRIORITY.

Interrupt Safe APIs

FreeRTOS APIs ending with the work FromISR are safe to be called from an ISR.

FreeRTOS APIs which do not end with the work FromISR are unsafe to be called from an ISR.

Why do we have 2 flavors of the same function?

Let’s take an example of changing task in ISR:

void ISR_Func() {
    xTaskGenericNotify();
}

void xTaskGenericNotify() {
    1. write notification value
    2. unblock a higher priorty task?
        2.1. yes --> do taskYIELD
                 --> Usage Fault Exception
}

During the ISR function, Task Notification changes the current task to a higher priority task. However, the processor is in the Handler Mode (during ISR), it is NOT ALLOWED to switch to Thread Mode if ISR is not returned.

Task Priority

Lower Task Priority Value means lower Task Priority Level

In FreeRTOS, task priority is the opposite of interrupt priority.

• Each task is assigned a priority from 0 to (configMAX_PRIORITIES - 1), where configMAX_PRIORITIES is defined within FreeRTOSConfig.h.

  • If configUSE_PORT_OPTIMISED_TASK_SELECTION = 1, an optimized task selection mechanism will use a ‘count leading zeros’ type instruction (for task selection in a single instruction). In this case, configMAX_PRIORITIES cannot be higher than 32.

• Low priority numbers denote low priority tasks. The idle task has priority zero (tskIDLE_PRIORITY).

• The FreeRTOS scheduler ensures that tasks in the Ready or Running state will always be given processor (CPU) time in preference to tasks of a lower priority that are also in the ready state. In other words, the task placed into the Running state is always the highest priority task that is able to run.

• Any number of tasks can share the same priority. If configUSE_TIME_SLICING is not defined, or if configUSE_TIME_SLICING is set to 1, then Ready state tasks of equal priority will share the available processing time using a time sliced round-robin scheduling scheme.

Priority Inversion

Original post at Part 11 (Priority Inversion). Credit to digikey.com.

Furter reading in How to use priority inheritance.

Priority inversion is a bug that occurs when a high priority task is indirectly preempted by a low priority task. For example, the low priority task holds a lock that the high priority task must wait for to continue executing.

How it happens

In the simple case, the high priority task (Task H) would be blocked as long as the low priority task (Task L) held the lock. This is known as “bounded priority inversion,” as the length of time of the inversion is bounded by however long the low priority task is in the critical section (holding the lock).

 

Unbounded priority inversion occurs when a medium priority task (Task M) interrupts Task L while it holds the lock. It’s called “unbounded” because Task M can now effectively block Task H for any amount of time, as Task M is preempting Task L (which still holds the lock).

 

Solution for unbounded priority inversion

There are a few ways to combat unbounded priority inversion. Two popular methods include priority ceiling protocol and priority inheritance.

Priority ceiling protocol

Priority ceiling protocol involves assigning a “priority ceiling level” to each resource or lock. Whenever a task works with a particular resource or takes a lock, the task’s priority level is automatically boosted to that of the priority ceiling associated with the lock or resource. The priority ceiling is determined by the maximum priority of any task that needs to use the resource or lock.

Example: As the priority ceiling of the lock is 3, whenever Task L takes the lock, its priority is boosted to 3 so that it will run at the same priority as Task H. This prevents Task M (priority 2) from running until Tasks L and H are done with the lock.

 

Priority inheritance

Priority inheritance involves boosting the priority of a task holding a lock to that of any other (higher priority) task that tries to take the lock.

Example: Task L takes the lock. Only when Task H attempts to take the lock is the priority of Task L boosted to that of Task H’s. Once again, Task M can no longer interrupt Task L until both tasks are finished in the critical section.

 

In both priority ceiling protocol and priority inheritance, Task L’s priority is dropped back to its original level once it releases the lock. Also note that both systems only prevent unbounded priority inversion. Bounded priority inversion can still occur.

Mutex vs Binary Semaphore

Most of RTOS, including FreeRTOS, mutex is implemented with Priority Inheritance.

Solution for bounded priority inversion

We can only avoid or mitigate bounded priority inversion through good programming practices. Some possible tips include (pick and choose based on your project’s need):

• Keep critical sections short to cut down on bounded priority inversion time
• Avoid using critical sections or locking mechanisms that can block a high priority task
• Use one task to control a shared resource to avoid the need to create locks to protect it

To demonstrate the last point, we could use a “service task” that was in charge of managing a shared resource. For example, we could use queues to send and receive messages from a task that handled the serial port.

 

Hard blocking critical section

Using Semaphore/ Mutex may not totally prevent priority inversion. There is a crude way to hardly block the critical section when it is running: disabling interrupts and scheduler.

FreeRTOS provides two functions to enter and exit critical session:

• taskENTER_CRITICAL()
• taskEXIT_CRITICAL()

Comments