Skip to content

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

Open

Description

@ytakano

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.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions