Task scheduling, communication and synchronisation
Task scheduling, communication and synchronisation explain how real-time tasks are ordered, how tasks exchange data, and how to avoid race conditions and deadlock in embedded systems.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Task scheduling, communication and synchronisation are core to any RTOS-based embedded system: an engineer uses these to make sure real-time tasks meet deadlines, share data safely, and avoid system stalls (deadlock) or unpredictable behaviour (race conditions). Good design here directly affects correctness, latency and system reliability.
Key ideas
Start with clear definitions (first use of each defined term is bolded):
- Task: a unit of computation scheduled by the RTOS. Often periodic or sporadic; has a computation time (C) and a period (T) or deadline (D).
- Thread / Process: similar concepts; a thread shares address space with other threads of the same process; a process has its own address space. In embedded RTOS, we usually work with tasks/threads.
- RTOS (Real-Time Operating System): an OS designed to provide bounded timing behaviour and deterministic scheduling.
- Scheduler: the algorithm in the RTOS that decides which task runs next. Two main families: fixed-priority (e.g. Rate Monotonic) and dynamic-priority (e.g. Earliest Deadline First).
- Preemptive scheduling: higher-priority task can interrupt a lower-priority one. Non-preemptive: a running task runs until it blocks or finishes.
- Context switch: the OS operation of saving state of one task and restoring state of another; it takes non-zero time.
- Priority inversion: a situation where a low-priority task holds a resource needed by a high-priority task, and a medium-priority task prevents the low-priority task from running, blocking the high-priority task indirectly.
- Priority inheritance: a protocol that temporarily raises the priority of the task holding the resource to the level of the highest blocked task to limit inversion. Related protocols: Priority Ceiling Protocol (PCP) and Stack Resource Policy (SRP), which prevent deadlock and statically bound blocking by assigning ceilings to resources; many RTOSes offer immediate-ceiling (priority-protection) mutexes.
- Critical section: code region that must be executed atomically relative to other tasks accessing the same data.
- Mutex (mutual exclusion): a lock that ensures only one thread can be in the critical section. A binary semaphore is similar but has different ownership semantics. Mutexes have ownership (only the owner may unlock) and typically support priority inheritance/ceiling; they must not be unlocked from ISRs. Binary semaphores have no ownership and are often safe to post (give) from ISRs.
- Semaphore: a synchronization primitive. Binary semaphore (0/1) for mutual exclusion or event signalling; counting semaphore allows limited resource counting.
- Deadlock: state where two or more tasks wait forever for resources held by each other. The four Coffman conditions that together allow deadlock are: mutual exclusion, hold-and-wait, no preemption, and circular wait.
- Spinlock: a lock where a waiting task loops (busy-waits) until the lock is free; suitable for short critical sections on multi-core systems.
- Shared memory vs message passing: two communication models. Shared memory gives fast data exchange but needs synchronization; message passing (queues/mailboxes) transfers ownership and reduces direct sharing.
Scheduling theory (important theorems and assumptions):
Rate Monotonic Scheduling (RMS) is a fixed-priority scheduling policy that assigns higher priority to tasks with shorter period. Among all fixed-priority assignments for independent periodic tasks with D = T (implicit deadlines), RMS is optimal (Liu & Layland, 1973). Assumptions for classical RMS theorems: tasks are independent, periodic, deadlines equal periods (D = T), preemptive scheduling, zero context-switch and scheduling overhead, worst-case execution times known, and no blocking.
RMS Utilization Bound Theorem (exact statement for exam): For n independent periodic tasks under RMS, if the total CPU utilization U = sum(Ci/Ti) ≤ n(2^{1/n} - 1), then the task set is guaranteed schedulable under RMS. This is a sufficient (but not necessary) condition. If U > n(2^{1/n} - 1), schedulability may still be possible but needs exact analysis.
Limit of RMS bound: as n → ∞, n(2^{1/n} - 1) → ln 2 ≈ 0.693. For harmonic task sets (each period is an integer multiple of all shorter periods), RMS can achieve full utilization: if U ≤ 1 the set is schedulable.
Exact schedulability test (response time analysis) for fixed-priority preemptive scheduling: for task i (priority order: 1 highest ... n lowest), the worst-case response time R_i is the smallest R satisfying R_i = C_i + sum_{j in hp(i)} ceil(R_i / T_j) * C_j where hp(i) is the set of tasks with higher priority than i. If R_i ≤ D_i the task meets its deadline. This equation is solved iteratively starting with R_i^(0)=C_i. Stop when it converges (R_i^(k+1) = R_i^(k)); if R_i^(k+1) > D_i at any step, task i is unschedulable.
Earliest Deadline First (EDF) optimality: For preemptive scheduling of independent, periodic (or sporadic) tasks with deadlines equal to periods, EDF can schedule any feasible task set if and only if U ≤ 1. EDF is optimal in the sense that if any algorithm can schedule the set, EDF can too (under the same assumptions).
Communication and synchronisation guidance:
- Use mutexes for protecting shared data; prefer RTOS-provided mutexes with priority inheritance to prevent priority inversion.
- For producer-consumer or inter-task messages, prefer message queues/mailboxes (message passing) to avoid fine-grain shared-memory synchronization where possible.
- Keep critical sections short; prefer disabling interrupts only for very short, time-critical atomic operations. Use a global lock-acquisition order (resource ordering) or ceiling protocols to prevent deadlock when multiple locks are needed.
What to draw (diagrams you may be asked for):
- Gantt chart (time vs tasks) showing preemption points and context switches: draw time on X-axis, task names on Y or stacked lanes, show blocks where tasks run, and arrows showing preemption events.
- Priority inversion diagram: show three tasks L (low), M (medium), H (high) on timeline: L enters critical section, H tries to enter and blocks, M runs and preempts L, H waits; then show priority inheritance raising L to H's priority so M does not preempt.
Assumptions to always state in answers: whether preemption, deadlines equal periods, context switch overhead, independence of tasks, and whether blocking is allowed.
Formulas
U = Σ (C_i / T_i) — total CPU utilization; C_i is worst-case computation time of task i (s), T_i its period (s); applies to periodic task sets.
R_i = C_i + Σ_{j ∈ hp(i)} ceil(R_i / T_j) * C_j — response time equation for fixed-priority preemptive scheduling; R_i is worst-case response time of task i (s); hp(i) are tasks with higher priority.
U_RMS_bound = n (2^{1/n} - 1) — sufficient schedulability bound for n tasks under RMS; dimensionless fraction of CPU.
lim_{n→∞} n (2^{1/n} - 1) = ln 2 ≈ 0.693 — limiting bound.
EDF schedulability condition: U ≤ 1 (if deadlines = periods and preemptive, independent tasks). For constrained deadlines (D_i ≤ T_i), U ≤ 1 is necessary but not sufficient; the exact uniprocessor EDF test is the processor-demand criterion: for all t > 0, Σ_i max(0, floor((t - D_i)/T_i) + 1) C_i ≤ t.
Blocking-aware response time (when mutexes can block at most B_i): R_i = C_i + B_i + Σ_{j ∈ hp(i)} ceil(R_i / T_j) * C_j. Typical bound under uniprocessor fixed-priority scheduling with priority inheritance or ceiling protocols: B_i ≤ the longest critical section of any lower-priority task that uses a resource also used by task i (a task can be blocked at most once).
Note: include context-switch overhead t_cs by adding it to C_i or as interference when required.
Worked examples
Example 1 — RMS utilization test (numerical, exam style): Given three periodic tasks (times in seconds):
- Task A: C1 = 1 ms = 0.001 s, T1 = 4 ms = 0.004 s
- Task B: C2 = 1 ms = 0.001 s, T2 = 5 ms = 0.005 s
- Task C: C3 = 2 ms = 0.002 s, T3 = 10 ms = 0.010 s Step 1: Compute utilizations: U1 = 0.001/0.004 = 0.25; U2 = 0.001/0.005 = 0.2; U3 = 0.002/0.010 = 0.2. Step 2: Total U = 0.25 + 0.2 + 0.2 = 0.65. Step 3: RMS bound for n = 3: U_bound = 3*(2^{1/3} - 1). Compute 2^{1/3} ≈ 1.259921; 2^{1/3} - 1 ≈ 0.259921; U_bound ≈ 3 * 0.259921 = 0.779763. Step 4: Compare: 0.65 ≤ 0.779763, so by the RMS utilization bound the task set is guaranteed schedulable. Answer: Schedulable under RMS (U = 0.65 ≤ 0.77976).
Example 2 — Priority inversion scenario (algorithmic trace): Tasks (priorities: H highest, M medium, L low). Times in ms:
- L: runs and enters mutex, holds for 30 ms (critical section)
- H: becomes ready at t = 5 ms and tries to acquire same mutex
- M: becomes ready at t = 6 ms and runs CPU for 20 ms (no mutex) Trace without priority inheritance:
- t=0: L starts, acquires mutex.
- t=5: H becomes ready, tries to acquire mutex but blocks (waiting for L).
- t=6: M becomes ready. Because H is blocked, scheduler sees M as highest runnable and preempts L; M runs until t=26, further delaying L releasing the mutex; H waits until L resumes and releases mutex, causing long blocking. With priority inheritance:
- When H blocks on the mutex held by L, L temporarily inherits H's priority. M cannot preempt L now. L continues, releases mutex earlier, H acquires it and runs. In this way the blocking experienced by H is limited to the duration of L's critical section. Answer: Priority inheritance removes the medium-priority interference and bounds the blocking time to the low-priority critical section length.
Example 3 — Response time analysis (short): Consider two tasks: τ1 (higher priority) C1=1 ms, T1=4 ms; τ2 (lower) C2=2 ms, T2=5 ms. Test schedulability of τ2 using response time equation. Step 1: For τ2, hp(2) = {τ1}. Start R2^(0) = C2 = 2 ms. Step 2: R2^(1) = C2 + ceil(R2^(0)/T1)*C1 = 2 + ceil(2/4)*1 = 2 + 1 = 3 ms. Step 3: R2^(2) = 2 + ceil(3/4)*1 = 2 + 1 = 3 ms. Converged. Step 4: Compare R2 = 3 ms ≤ D2 (assume D2 = T2 = 5 ms). So τ2 meets deadline. Answer: R2=3 ms ≤ 5 ms, schedulable.
Common mistakes
- Forgetting to include blocking time when locks or non-preemptive sections exist.
- Ignoring context-switch overhead and interrupt latency in tight schedules.
- Using binary semaphore and mutex interchangeably without noting ownership differences (mutexes usually have ownership and support priority inheritance; semaphores may not).
- Trying to use spinlocks for long critical sections on single-core systems (this wastes CPU).
For your exam
Types of questions you will see: definitions (e.g., define priority inversion), short notes (compare message passing vs shared memory), derivations (derive RMS bound or show limit → ln 2), numericals (compute U and apply RMS/EDF; response-time analysis), diagrams (Gantt charts, priority inversion timeline), and small code snippets showing use of mutex/semaphore in pseudocode. What full-marks answers include:
- State assumptions clearly (preemptive? deadlines = periods? context switch overhead?).
- Use correct formulas and show each algebraic or numerical step with units (seconds or ms).
- For proofs: state the theorem, assumptions, and give the standard derivation or refer to the iterative response-time equation and convergence.
- For synchronization questions: list the primitive used (mutex vs semaphore), explain ownership and priority handling, and discuss pros/cons.
Quick check
- Give the RMS utilization bound expression for n tasks.
- Name the four Coffman conditions for deadlock.
- What is the EDF schedulability condition when deadlines equal periods? Answers: U_bound = n(2^{1/n} - 1); mutual exclusion, hold-and-wait, no preemption, circular wait; EDF: U ≤ 1.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?