Clustered preemption: the idle-CPU shortcut can cause priority inversion and delayed wakeups

Summary

ClusteredEDFScheduler::invoke_preemption (main, introduced in #701) returns false
as soon as it finds an idle CPU in the woken task's cpu_set, on the assumption that
the idle CPU will pick the task up. The clustered_fifo branch moves this logic into
the shared invoke_clustered_preemption() in awkernel_async_lib/src/scheduler.rs,
so ClusteredFIFO implementing now inherits the same behavior.

The assumption does not hold in two cases:

1. The idle CPU may already have a higher-priority task queued for it, so it takes
   that one and the woken task stays queued while a lower-priority task keeps running
   on another CPU of the set (priority inversion, unbounded by IPI latency).
2. Several callers reach Scheduler::wake_task without ArcWake::wake, so nobody
   calls wake_cpu(0) and the idle CPU is never woken until the primary CPU's next
   periodic wake_workers() (up to ~1 s without a timer).

The non-clustered schedulers (GEDF, PrioritizedRR, and the former PrioritizedFIFO)
exclude idle CPUs and preempt the lowest-priority busy CPU instead, so they are not
affected.

Affected code

• main: awkernel_async_lib/src/scheduler/clustered_edf.rs, invoke_preemption(),
  the task_running.task_id == 0 => return false check.
• branch clustered_fifo: awkernel_async_lib/src/scheduler.rs,
  invoke_clustered_preemption() (shared by ClusteredEDF and ClusteredFIFO).

Scenario 1: queued contender on the idle CPU

Priorities: T' > H > L. Both L and H have cpu_set = {a, b} (same set; the
issue does not depend on the sets differing). T' has {b} or {a, b}.

1. L runs on a. b is idle (sleeping).
2. T' wakes. b is idle, so no preemption; T' is enqueued. b is woken via
   wake_cpu(0) → wake_workers() → IPI, which takes time.
3. Before b runs get_next_task, H wakes. b is still idle, so H is enqueued too.
4. b wakes and pop_for_cpu(b) returns T' (better key).
5. a runs L, b runs T', and H stays queued although H > L. The inversion
   lasts until L or T' finishes.

The former PrioritizedFIFO would have preempted L in step 3.

Scenario 2: wake paths without wake_cpu(0)

re_schedule() (task/preempt.rs) and do_preemption() call
task.scheduler.wake_task(task) directly. If the woken task's set contains a sleeping
idle CPU, the shortcut enqueues the task and returns, but no IPI is sent to that CPU.
The task waits for the primary CPU's next wake_workers() while a lower-priority task
runs on the other CPU of the set. No third task is needed for this one.

Impact

• ClusteredFIFO: a higher-priority task waits behind a lower-priority one.
• ClusteredEDF: an earlier-deadline job waits behind a later-deadline one, which
  translates directly into deadline misses.
• SPEC_TEST.md maps ClusteredFIFOScheduler to specification/.../preemptive_spin,
  but that model still encodes the old "skip idle CPUs, preempt lowest busy" logic and
  has no notion of affinity, so the model does not describe the implementation.

Why the tests do not catch it

test_clustered_edf and test_clustered_fifo (test_preemption_in_set) only build
the "all CPUs in the set are busy" situation. Neither creates an idle CPU that already
has a higher-priority task queued, nor exercises the re_schedule/do_preemption
re-wake paths with a sleeping CPU in the set.

Options

1. Wake the idle CPU directly. When the shortcut is taken, call
   wake_cpu(idle_cpu) from invoke_clustered_preemption. Fixes scenario 2 and also
   removes the two-IPI round trip through CPU 0, but leaves scenario 1.
2. Check for a queued contender. Treat an idle CPU c as unavailable if
   peek_key_for_cpu(c) on the scheduler's queue returns a key better than the woken
   task's. Requires passing a per-scheduler closure (key types differ: u8 vs
   (u64, u64)) and locking the queue inside GLOBAL_WAKE_GET_MUTEX. Combine with (1).
3. Match GEDF. Exclude idle CPUs and preempt the lowest-priority busy CPU in the
   set. Simple and matches the SPIN model, but it preempts unnecessarily when an idle
   CPU exists, migrates the victim, hammers tasks pinned to a single core, and the
   preempted victim is re-queued via re_schedule without any wake_cpu, so the idle
   CPU may stay asleep while the victim waits. Would need (1) as well.

Whichever option is chosen, the SPIN model under preemptive_spin should be updated
to include affinity and the chosen idle-CPU policy, or the SPEC_TEST.md entry for
ClusteredFIFOScheduler should be dropped until it is.

Low: (None, None) => return false aborts the victim search

In the per-CPU loop, (get_task(running_id), peek_preemption_pending(cpu)) matching
(None, None) makes the whole function return false instead of skipping that CPU.
TASKS removal (run_main, after RUNNING[cpu].swap(0)) does not take
GLOBAL_WAKE_GET_MUTEX, so this is reachable by a race: the loop reads
RUNNING[y] == T, CPU y then finishes T, clears RUNNING[y] and removes T from
TASKS, and get_task(T) returns None.

Under the current idle-CPU shortcut this is harmless: y has just become idle, so
returning false is equivalent to having observed task_id == 0. It only matters if
option 3 is adopted, where idle CPUs must be skipped and the search must continue; in
that case the arm should become continue. Otherwise a comment stating that this arm
is treated like an idle CPU is enough.

Related

• feat(sched): add CPU core affinity via ClusteredEDF scheduler #701 (ClusteredEDF, where the shortcut was introduced)
• branch clustered_fifo (ClusteredFIFO, shares the logic)