EC-20.3 Passing Work Between Tasks Without Losing It

What this is and why it exists

Two tasks sharing anything is where real-time systems go wrong.

The failures have a particular character. They are rare, they depend on exact timing, and they are usually gone by the time anybody looks. A system can pass a week of testing and then fail daily in the field. No amount of staring at the code will show why.

The good news is that the number of correct patterns is small. This topic teaches those patterns and the one famous failure that nearly ended a Mars mission. It also teaches the habit that prevents most of the trouble: asking what would happen if a switch occurred on this exact line.

The vocabulary

• Race condition — a result that depends on the order two pieces of code happen to interleave.
• Critical section — a stretch of code that only one task may be inside at a time.
• Mutex — a lock providing that exclusion, owned by whoever took it.
• Semaphore — a counter used for signalling rather than for exclusion.
• Queue — a kernel object that carries copies of messages from one task to another.
• Priority inversion — a high-priority task blocked indirectly by a lower-priority one.
• Priority inheritance — raising a lock holder's priority to end that block.
• Deadlock — two tasks each holding what the other is waiting for.

The mental model

Everything in this topic follows from one fact: a context switch can happen between any two machine instructions.

A statement that reads a variable, adds one and writes it back is three operations. If a switch happens in the middle and another task does the same thing, one of the two increments disappears. That is a race condition, and the shortest example that produces one is worth writing out by hand once.

Mutual exclusion is the fix for shared data. A mutex makes a section exclusive. The rule that follows is to hold it across the shortest possible stretch, and never across anything that waits. Every moment you hold it is a moment a higher-priority task may be stuck.

Signalling is a different problem, and using a lock for it is a common confusion. A semaphore counts events. The standard shape is an interrupt handler that does almost nothing, signals a semaphore, and lets a task do the real work. That keeps the worst-case interrupt latency short.

Message passing removes the question entirely. A queue carries a copy of the data from sender to receiver, so there is nothing shared and nobody can still be reading it. The copy costs time, and for the small messages typical of embedded work that cost is almost always worth paying.

Now the famous failure. A low-priority task takes a lock. A high-priority task wants the same lock and blocks. A medium-priority task, which needs no lock at all, preempts the low-priority one and runs. The high-priority task is now blocked behind medium-priority work, indefinitely. This is priority inversion, and it is what kept resetting the Mars Pathfinder lander.

The fix is priority inheritance: while a low-priority task holds a lock somebody more important wants, it temporarily gets that higher priority. The block becomes bounded rather than unbounded.

Deadlock is the other classic. Two tasks each hold one lock and each want the other. Testing finds this unreliably, because it needs a precise interleaving. Taking locks in one globally agreed order removes the possibility altogether, rather than making it less likely.

What you should now be able to explain or do

• Write the shortest program that exhibits a race condition, and say where it switches.
• Choose between a mutex, a semaphore and a queue for a given hand-off, with a reason.
• Write an interrupt handler that passes data to a task without a race.
• Explain priority inversion using three tasks, and say what inheritance changes.
• State the ordering rule that prevents deadlock, and say why it beats testing.
• Justify copying a small message rather than sharing a pointer to it.

Check yourself