PrioritizedRR: `invoke_preemption_tick()` pops and re-queues a lower-priority queue head on every primary loop iteration

オープン
#729 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る

メンテナーはふだん 2 日以内に返信

まだ誰も着手していません。

評価

難易度
4/5
見積もり時間
3〜5日
初心者へのやさしさ
42/100
issue の種類
バグ
明瞭さ
明確に書かれている
活発さ
活発
技術スタック
rust

調査の方向性

Start in awkernel_async_lib/src/scheduler/prioritized_rr.rs at invoke_preemption_tick() and trace how get_next_task(false) feeds push_preemption_pending and the IPI. Then read preempt.rs do_preemption() to see where a lower-priority pending task is re-queued through wake_task, and check the peek support in PriorityQueue and AffinityBTreeQueue. Done means the tick peeks before popping, skips lower-priority rotation, and refreshes last_executed_time when it does not preempt.

索引モデルが issue の本文から書いたものです。

説明

PrioritizedRR: invoke_preemption_tick() pops and re-queues a lower-priority queue head on every primary loop iteration

Summary

PrioritizedRRScheduler::invoke_preemption_tick()
(awkernel_async_lib/src/scheduler/prioritized_rr.rs) decides to rotate a running
PrioritizedRR task only by elapsed time. When the quantum (4 ms) has expired it calls
get_next_task(false), which removes the highest-priority runnable task from the
run queues, pushes it to the target CPU's preemption-pending heap and sends an IPI,
without comparing its priority with the running task.

If that task has a lower priority than the running one (e.g. the CPU runs RR(1) and
the queue head is RR(0)), do_preemption() on the target CPU does not preempt and
re-queues the task through Scheduler::wake_task, which appends it to the tail of
its priority level. Nothing refreshes last_executed_time (it is updated only on
dispatch in run_main/yield_and_pool), so on the next primary loop iteration the
quantum is still "expired" and the whole sequence repeats with the new queue head.

Flow

  1. kernel/src/main.rs primary loop → scheduler::wake_task() → for every worker CPU
    running a PrioritizedRR task: invoke_preemption_tick(cpu_id, task_id). Without a
    timer the primary loop spins with wait_microsec(10), so this fires continuously.
  2. invoke_preemption_tick(): elapsed > interval → get_next_task(false) pops the
    queue head → push_preemption_pending → set_need_preemption → send_ipi.
  3. preempt.rs do_preemption(): the pending task has a strictly lower priority than
    the running task → remove_preemption_pending + next.scheduler.wake_task(next),
    i.e. back into the run queue at the tail of its level.
  4. last_executed_time unchanged → step 2 again on the next iteration.

Consequences

  • One IPI per RR-running CPU per primary loop iteration, for as long as the queue head
    has a lower priority than every running RR task.
  • The lower-priority FIFO level is rotated by one task on every tick, so FIFO order
    within that level is not preserved: when a CPU becomes free, the task that runs is
    whichever one happens to be at the head, not the one that waited longest.
  • Each round moves the task run queue → pending heap → run queue, with the
    corresponding counter updates and lock acquisitions.

This predates #725: the old check current_task > next re-queued a lower-priority
next in the same way. #725 only removed the equal-priority case (which is now the
intended quantum rotation).

Fix

  • In invoke_preemption_tick(), peek at the best runnable task before popping and
    only pop/send the IPI if its priority is at least that of the running task. This
    needs a peek counterpart of get_next_task(false) across the schedulers (the
    PriorityQueue and AffinityBTreeQueue both support peeking).
  • When the tick decides not to rotate, refresh the quantum origin
    (last_executed_time) so the tick does not fire again on the next iteration.
主要言語
Rust
スター
282
フォーク
12
平均マージ
2日 9時間
マージ済み PR(30日)
28

環境構築

このプロジェクトには開発コンテナ、Dockerfile、コントリビューションガイドがありません。まず README を読み、一般的な手順ははじめてのコントリビューションガイドを参照してください。

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

tier4/awkernel のほかの issue

tier4/awkernel の issue をすべて見る

似ている issue

Rust の issue をもっと見る

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。