Priority-based scheduling in FreeRTOS - Deep Dive

Overview - Priority-based scheduling

What is it?

Priority-based scheduling is a way an operating system decides which task to run next based on importance levels called priorities. Each task is assigned a priority number, and the system always runs the highest priority task that is ready to run. If a higher priority task becomes ready, it can interrupt a lower priority one. This helps manage multiple tasks efficiently in real-time systems like FreeRTOS.

Why it matters

Without priority-based scheduling, all tasks would compete equally, causing important tasks to wait too long or miss deadlines. This could lead to slow or unsafe behavior in devices like medical monitors or robots. Priority scheduling ensures critical tasks get immediate attention, making systems responsive and reliable.

Where it fits

Learners should first understand basic multitasking and task states in FreeRTOS. After mastering priority scheduling, they can explore advanced topics like task synchronization, real-time constraints, and interrupt handling.

Mental Model

Core Idea

The system always runs the ready task with the highest priority, preempting lower priority tasks when needed.

Think of it like...

Imagine a busy restaurant kitchen where orders have different urgency levels. The chef always cooks the most urgent order first, even if they are in the middle of a less urgent one.

┌───────────────┐
│ Ready Tasks   │
│ ┌───────────┐ │
│ │ Priority 3│ │  Highest priority task runs
│ ├───────────┤ │
│ │ Priority 2│ │  Runs only if no priority 3 ready
│ ├───────────┤ │
│ │ Priority 1│ │  Runs if no higher priority ready
│ └───────────┘ │
└───────┬───────┘
        │
        ▼
  Running Task

Build-Up - 7 Steps

1

Foundation

Understanding Tasks and Priorities

Concept: Tasks are units of work, each with a priority number indicating importance.

In FreeRTOS, each task you create is assigned a priority from 0 (lowest) to configMAX_PRIORITIES-1 (highest). The scheduler uses these priorities to decide which task to run. Tasks with higher priority numbers are more important.

Result

You know how to assign priorities to tasks when creating them.

Understanding that priorities are numbers representing importance is the base for how scheduling decisions are made.

2

Foundation

What Does Ready State Mean?

Concept: Only tasks that are ready can run; others wait or are blocked.

A task is 'ready' when it can run but is waiting for the CPU. If a task is waiting for something (like a timer or input), it is 'blocked' and not considered by the scheduler. Only ready tasks compete for CPU time.

Result

You can distinguish between ready and blocked tasks.

Knowing which tasks are ready helps understand why some tasks run and others wait.

3

Intermediate

How Preemption Works in Priority Scheduling

🤔Before reading on: do you think a running low priority task stops immediately when a higher priority task becomes ready, or does it finish first? Commit to your answer.

Concept: Higher priority tasks can interrupt lower priority tasks immediately (preemption).

FreeRTOS uses preemptive scheduling by default. If a higher priority task becomes ready, the scheduler stops the currently running lower priority task and switches to the higher priority one. This ensures urgent tasks get CPU time right away.

Result

You understand that higher priority tasks can interrupt lower ones instantly.

Knowing preemption prevents delays in critical tasks and explains why some tasks may pause unexpectedly.

4

Intermediate

Priority Inversion and Its Effects

🤔Before reading on: do you think a low priority task holding a resource can block a higher priority task indefinitely? Commit to your answer.

Concept: Sometimes lower priority tasks block higher priority ones, causing priority inversion.

Priority inversion happens when a low priority task holds a resource needed by a higher priority task. The high priority task waits, effectively lowering its priority. FreeRTOS offers priority inheritance to temporarily raise the low priority task's priority to fix this.

Result

You recognize priority inversion and how FreeRTOS handles it.

Understanding priority inversion is key to designing systems that avoid unexpected delays.

5

Intermediate

Configuring Priorities in FreeRTOS

Concept: You can set task priorities when creating tasks and change them at runtime.

When creating a task with xTaskCreate(), you pass a priority parameter. You can also change a task's priority later with vTaskPrioritySet(). Priorities must be chosen carefully to reflect task importance and avoid starvation.

Result

You can assign and adjust task priorities in FreeRTOS code.

Knowing how to configure priorities lets you control task scheduling behavior precisely.

6

Advanced

How the Scheduler Chooses the Next Task

🤔Before reading on: do you think the scheduler scans all tasks every time to find the highest priority ready task, or does it use a faster method? Commit to your answer.

Concept: FreeRTOS uses efficient data structures to quickly find the highest priority ready task.

FreeRTOS maintains a bitmap of ready tasks by priority. The scheduler uses this bitmap to find the highest priority ready task in constant time without scanning all tasks. This makes scheduling fast and predictable.

Result

You understand the internal efficiency of FreeRTOS scheduling.

Knowing the scheduler's efficiency explains why FreeRTOS is suitable for real-time systems.

7

Expert

Subtle Effects of Equal Priorities and Time Slicing

🤔Before reading on: do you think tasks with the same priority run simultaneously or one after another? Commit to your answer.

Concept: Tasks with equal priority share CPU time using time slicing if enabled.

If configUSE_TIME_SLICING is set, FreeRTOS switches between tasks of equal priority in a round-robin fashion. Without time slicing, the first ready task runs until it blocks or yields. This affects fairness and responsiveness.

Result

You grasp how equal priority tasks share CPU time and how to control it.

Understanding time slicing helps avoid starvation and ensures fair CPU sharing among equal priority tasks.

Under the Hood

FreeRTOS maintains a ready list for each priority level. When a task becomes ready, it is added to its priority list. The scheduler uses a bitmap to track which priority lists have ready tasks. On each tick or event, it finds the highest priority ready list and picks the next task from it. If preemption is enabled, it switches context immediately to the higher priority task. Priority inheritance temporarily boosts a low priority task's priority if it blocks a higher priority task on a mutex.

Why designed this way?

This design balances speed and simplicity. Using bitmaps and priority lists allows constant-time scheduling decisions, crucial for real-time responsiveness. Priority inheritance solves priority inversion without complex protocols. Alternatives like round-robin or simple FIFO scheduling are simpler but can't guarantee timely execution of critical tasks.

┌─────────────────────────────┐
│ Priority Bitmap (ready flags)│
│  1 0 1 0 0 1 0 0 0 0 0 0    │
└─────────────┬───────────────┘
              │
  ┌───────────▼────────────┐
  │ Ready Lists by Priority │
  │ ┌─────┐ ┌─────┐ ┌─────┐ │
  │ │ P10 │ │ P8  │ │ P5  │ │
  │ │TaskA│ │TaskB│ │TaskC│ │
  │ └─────┘ └─────┘ └─────┘ │
  └───────────┬────────────┘
              │
      Scheduler picks highest
      priority ready task to run

Myth Busters - 4 Common Misconceptions

Quick: Does a higher priority task always run immediately when it becomes ready? Commit yes or no.

Common Belief: Higher priority tasks always preempt lower priority tasks instantly.

Reality: If preemption is disabled (configUSE_PREEMPTION=0), higher priority tasks wait until the current task yields or blocks.

Why it matters: Assuming preemption always happens can cause bugs where critical tasks don't run on time.

Quick: Can a low priority task holding a mutex block a high priority task forever? Commit yes or no.

Common Belief: Priority inversion cannot happen in FreeRTOS because priorities always decide who runs.

Reality: Priority inversion can happen if a low priority task holds a mutex needed by a high priority task, causing delays.

Why it matters: Ignoring priority inversion risks system stalls or missed deadlines in real-time applications.

Quick: Do tasks with the same priority run simultaneously? Commit yes or no.

Common Belief: Tasks with the same priority run at the same time on a single-core CPU.

Reality: On a single-core CPU, tasks run one at a time; equal priority tasks share CPU time via time slicing or cooperative yielding.

Why it matters: Misunderstanding this leads to wrong assumptions about task concurrency and timing.

Quick: Does increasing a task's priority always improve system performance? Commit yes or no.

Common Belief: Raising a task's priority always makes the system faster and better.

Reality: Increasing priority can cause lower priority tasks to starve, reducing overall system responsiveness.

Why it matters: Blindly raising priorities can create unbalanced systems and hard-to-debug performance issues.

Expert Zone

1

FreeRTOS uses a bitmap and priority lists to achieve O(1) scheduling, which is critical for predictable real-time behavior.

2

Priority inheritance is a lightweight solution to priority inversion but requires careful mutex usage to avoid deadlocks.

3

Time slicing among equal priority tasks is optional and can be disabled to reduce context switch overhead in some systems.

When NOT to use

Priority-based scheduling is not ideal for systems where fairness is more important than urgency, such as batch processing. Alternatives like round-robin or cooperative scheduling may be better. Also, in multicore systems, more complex schedulers that consider CPU affinity and load balancing are preferred.

Production Patterns

In real-world FreeRTOS applications, critical tasks like sensor reading or communication handlers get highest priorities. Background tasks like logging run at low priority. Priority inheritance is used with mutexes to protect shared resources. Time slicing is enabled or disabled based on system responsiveness needs. Developers carefully tune priorities to avoid starvation and ensure deadlines.

Connections

Real-time Operating Systems (RTOS) Concepts

Priority-based scheduling is a core RTOS concept that builds on multitasking and task states.

Understanding priority scheduling deepens comprehension of how RTOS achieve timely and predictable task execution.

Operating System Process Scheduling

Priority scheduling in FreeRTOS is a specialized form of process scheduling used in general OSes.

Knowing general OS scheduling helps appreciate FreeRTOS's lightweight and deterministic design choices.

Traffic Control Systems

Priority scheduling is similar to traffic lights prioritizing emergency vehicles over regular cars.

Recognizing this connection helps understand how priority ensures urgent tasks get immediate attention, just like emergency vehicles get green lights.

Common Pitfalls

#1 Assigning all tasks the same high priority.

Wrong approach:

xTaskCreate(task1, "Task1", 1000, NULL, 5, NULL);
xTaskCreate(task2, "Task2", 1000, NULL, 5, NULL);

Correct approach:

xTaskCreate(task1, "Task1", 1000, NULL, 5, NULL);
xTaskCreate(task2, "Task2", 1000, NULL, 3, NULL);

Root cause:

Misunderstanding that different priorities are needed to differentiate task importance and scheduling order.

#2 Ignoring priority inversion when using mutexes.

Wrong approach:

Mutex used without priority inheritance enabled, causing high priority task to wait indefinitely.

Correct approach:

Use FreeRTOS mutexes with priority inheritance to prevent inversion.

Root cause:

Not realizing that low priority tasks holding resources can block higher priority tasks.

#3 Disabling preemption but expecting immediate task switches on higher priority readiness.

Wrong approach:

configUSE_PREEMPTION set to 0 but code assumes high priority tasks preempt lower ones immediately.

Correct approach:

Enable preemption with configUSE_PREEMPTION set to 1 for immediate switching.

Root cause:

Confusing cooperative scheduling with preemptive scheduling behavior.

Key Takeaways

Priority-based scheduling runs the highest priority ready task first, ensuring critical tasks get CPU time promptly.

Preemption allows higher priority tasks to interrupt lower priority ones immediately, improving system responsiveness.

Priority inversion can delay high priority tasks if low priority tasks hold needed resources; priority inheritance helps fix this.

FreeRTOS uses efficient data structures to quickly select the next task, making scheduling fast and predictable.

Careful priority assignment and understanding of time slicing are essential to avoid starvation and ensure fair CPU sharing.