Remove the task-ID tie-break from `Task`'s ordering
Maintainer antworten meist innerhalb von 2 Tagen
Dieses Issue hat noch niemand übernommen.
Bewertung
- Schwierigkeit
- 3/5
- Geschätzter Aufwand
- 1-2 Tage
- Anfängerfreundlichkeit
- 42/100
- Issue-Typ
- Refactoring
- Klarheit
- Größtenteils klar
- Aktivitätsstatus
- Aktiv
- Tech-Stack
- rust
- Bereich
- operating-systems
Rechercherichtung
Start in awkernel_async_lib/src/task.rs at impl Ord for Task, then read PREEMPTION_PENDING_TASKS and peek_preemption_pending()/do_preemption() in scheduler.rs, and the victim selection in prioritized_fifo.rs, prioritized_rr.rs, gedf.rs and clustered_edf.rs. Done means the pending heap orders by priority then FIFO wake sequence via an explicit wrapper, victim selection compares task.priority directly, and Ord/PartialOrd on Task can be removed while preemption tests still pass.
Vom Indexierungsmodell aus dem Issue-Text verfasst.
Beschreibung
Remove the task-ID tie-break from Task's ordering
Summary
impl Ord for Task (awkernel_async_lib/src/task.rs) compares by priority and
breaks ties by task ID (a larger ID is "greater"). The tie-break exists only to
make the ordering total and consistent with PartialEq (which compares IDs); it
has no scheduling meaning. It was introduced in #572 with the opposite direction
and flipped together with the priority direction in #634.
The preemption decision no longer depends on it: Task::preempts() requires a
strictly higher priority (branch fix_equal_priority_preemption, commit 82f9b6a8),
so a task woken with the same priority as a running task no longer preempts it.
Two users of Task: Ord remain. Neither is incorrect, but both make the task ID
part of scheduling behavior where it should not be, and they are the only reason
Task needs an Ord at all.
1. Preemption-pending heaps
scheduler.rs: PREEMPTION_PENDING_TASKS: BTreeMap<usize, BinaryHeap<Arc<Task>>>.
peek_preemption_pending() and do_preemption()'s moved_preemption_pending.pop()
take the heap maximum as the pending task to run next.
Among pending tasks of equal priority, the heap pops the one with the largest ID
first, i.e. LIFO by spawn order, whereas every run queue is FIFO within a priority
level. Task IDs are also reused after u32 wrap-around (Tasks::spawn searches for
a free ID from candidate_id), so "larger ID" does not even mean "newer" in the
long run.
Proposed change: store a wrapper in the heap with an explicit ordering, like the
run queues already do (GEDFTask, AffinityBTreeQueue's (priority, seq) key):
struct PendingTask {
priority: u64, // snapshot of task.priority at push time
seq: u64, // global wake sequence number; smaller = earlier
task: Arc<Task>,
}
// Ord: priority descending, then seq ascending (FIFO among equals).
Snapshotting the priority also fixes a latent issue: PriorityInfo is an atomic
that EDF updates on every wake, and mutating a key while it sits in a BinaryHeap
breaks the heap invariant. remove_preemption_pending() keeps matching by task.id.
2. Victim selection in invoke_preemption*()
prioritized_fifo.rs, prioritized_rr.rs, gedf.rs (max(t, highest_pending),
.min() over (Arc<Task>, cpu_id)) and clustered_edf.rs (running.max(pending),
target_task >= *lowest) use Task: Ord to find the lowest-priority target CPU.
The tie-break cannot change whether preemption happens (all equal-priority
candidates have the same priority, so preempts() gives the same answer for any
of them); it only decides which equal-priority task is preempted. Today that is
the one with the smallest ID. This should compare task.priority directly, e.g.
min_by(|a, b| a.priority.cmp(&b.priority)), picking the first CPU in iteration
order on ties, so the choice is explicit rather than a side effect of Task::cmp.
Result
With 1 and 2 done, Ord/PartialOrd for Task can be removed (keeping
PartialEq/Eq by ID), and the only place where a priority comparison between
tasks happens is Task::preempts() plus the explicit orderings of the run queues
and the pending heap.
Related
- #572 (introduced the tie-break), #634 (flipped its direction)
- branch
fix_equal_priority_preemption/ 82f9b6a8 (strict comparison in the
preemption decision; prerequisite for this issue)
- Vorherrschende Sprache
- Rust
- Sterne
- 282
- Forks
- 12
- Ø Merge
- 2 T. 9 Std.
- Gemergte PRs (30 T.)
- 28
Entwicklungsumgebung
Dieses Projekt bietet weder Dev-Container noch Dockerfile noch Beitragsleitfaden – die Einrichtung liegt bei Ihnen. Beginnen Sie mit der README; die allgemeinen Schritte stehen in unserem Leitfaden für den ersten Beitrag.
Erste Schritte
- Lesen Sie das ganze Issue und danach den Beitragsleitfaden des Projekts.
- Schreiben Sie ins Issue, dass Sie es übernehmen — das erspart doppelte Arbeit.
- Forken Sie das Repository und arbeiten Sie in einem Branch.
- Öffnen Sie einen Pull Request, der die Issue-Nummer nennt.
Mehr aus tier4/awkernel
-
Schwierigkeit 1/5 Unter einer Stunde Anfängerfreundlichkeit 88/100
Maintainer antworten meist innerhalb von 2 Tagen
-
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 75/100
Maintainer antworten meist innerhalb von 2 Tagen
-
Schwierigkeit 4/5 3-5 Tage Anfängerfreundlichkeit 48/100
Maintainer antworten meist innerhalb von 2 Tagen
-
Schwierigkeit 4/5 3-5 Tage Anfängerfreundlichkeit 48/100
Maintainer antworten meist innerhalb von 2 Tagen
-
Deadlock in ixgbeOffen
Schwierigkeit 4/5 3-5 Tage Anfängerfreundlichkeit 25/100
Maintainer antworten meist innerhalb von 2 Tagen
Ähnliche Issues
-
bug ui
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 84/100
userFRM/egui-charts#3363 ·
Maintainer antworten meist innerhalb von 1 Tag
-
ada documentation mobile report
Schwierigkeit 1/5 Unter einer Stunde Anfängerfreundlichkeit 86/100
physicsdolphin/nv-uefi-unlocker#254 · 2 Reaktionen ·
Maintainer antworten meist innerhalb von 1 Tag
-
bug
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 82/100
kindraywind/rustnarok-client#1382 ·
Maintainer antworten meist innerhalb von 1 Tag
-
area:accessibility bug good first issue help wanted priority:p3-low size:small
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 78/100
NecturaLabs/Canopy#209 ·
-
CLI config custom-model enhancement
Schwierigkeit 2/5 1-3 Stunden Anfängerfreundlichkeit 68/100
Maintainer antworten meist innerhalb von 1 Tag