XV6中MLFQ与RR调度机制疑问及trap.c实现问询

问题背景 #

我正试图理解XV6中的MLFQ（多级反馈队列）和RR（轮转调度）的工作机制，已参考以下实现代码，但不清楚MLFQ中进程优先级如何变化，以及RR中进程运行指定时间后触发切换的机制，猜测这是由trap.c文件中的中断实现的，想知道具体细节。

调度器实现代码 #

void rr_scheduler(void) {
    struct proc *p;
    struct cpu *c = mycpu();

    c->proc = 0;
    intr_on();

    for (p = proc; p < &proc[NPROC]; p++)
    {
        acquire(&p->lock);
        if (p->state == RUNNABLE)
        {
            // Switch to chosen process.  It is the process's job
            // to release its lock and then reacquire it
            // before jumping back to us.
            p->state = RUNNING;
            c->proc = p;
            swtch(&c->context, &p->context);

            // Process is done running for now.
            // It should have changed its p->state before coming back.
            c->proc = 0;
        }
        release(&p->lock);
    }
}

void mlfq_scheduler(void){
    struct proc *p;
    struct cpu *c = mycpu();

    c->proc = 0;
    intr_on();

    char high_avail = 0;
    do
    {
        high_avail = 0;
        for (p = proc; p < &proc[NPROC]; p++)
        {
            acquire(&p->lock);
            if (p->priority > 0)
            {
                release(&p->lock);
                continue;
            }

            if (p->state == RUNNABLE)
            {
                high_avail = 1;
                // Switch to chosen process.  It is the process's job
                // to release its lock and then reacquire it
                // before jumping back to us.
                p->state = RUNNING;
                c->proc = p;
                swtch(&c->context, &p->context);
                // check if we are still the right scheduler
                if (sched_pointer != &mlfq_scheduler)
                {
                    release(&p->lock);
                    return;
                }

                // Process is done running for now.
                // It should have changed its p->state before coming back.
                c->proc = 0;
            }
            release(&p->lock);
        }
    } while (high_avail);

    //  RR on low prio - break when high prio found
    for (p = proc; p < &proc[NPROC]; p++)
    {
        acquire(&p->lock);
        if (p->priority == 0 && p->state == RUNNABLE)
        {
            // found high prio - switch to high prio task
            release(&p->lock);
            break;
        }

        if (p->state == RUNNABLE)
        {
            // Switch to chosen process.  It is the process's job
            // to release its lock and then reacquire it
            // before jumping back to us.
            p->state = RUNNING;
            c->proc = p;
            swtch(&c->context, &p->context);
            // check if we are still the right scheduler
            if (sched_pointer != &mlfq_scheduler)
            {
                release(&p->lock);
                return;
            }

            // Process is done running for now.
            // It should have changed its p->state before coming back.
            c->proc = 0;
        }
        release(&p->lock);
    }
}

核心机制解析 #

1. RR调度的时间片切换触发机制 #

轮转调度的时间片切换确实依赖trap.c中的时钟中断处理逻辑，具体流程：

• XV6通过硬件定时器每隔固定时间（通常10ms）触发时钟中断，中断发生后CPU自动切换到内核态，执行trap()函数。
• 在trap()中先判断中断类型是否为时钟中断（T_IRQ0 + IRQ_TIMER）。
• 如果是当前运行的用户进程触发的时钟中断，内核会减少该进程的时间片计数（如p->ticks--）。当时间片耗尽（p->ticks == 0）时，内核将进程状态设为RUNNABLE，调用yield()触发调度器切换，让下一个RUNNABLE进程获得CPU。
• 每次调度器选中新进程时，会重置其时间片计数为预设值（如10），确保每个进程每次最多运行一个时间片。

2. MLFQ调度的优先级变化逻辑 #

从代码来看，MLFQ通过p->priority字段区分优先级：priority <= 0为高优先级队列，priority > 0为低优先级队列，高优先级进程会被优先调度，只有高优先级无RUNNABLE进程时，才用RR方式调度低优先级进程。优先级调整依赖中断和进程状态变化，核心场景：

• 时间片耗尽降级：高优先级进程用完时间片后，内核将其priority加1（降低优先级），放入低优先级队列，避免高优先级进程长期占用CPU。
• IO唤醒升级：低优先级进程因等待IO（磁盘、键盘输入等）进入睡眠，完成IO被唤醒时，内核将其priority重置为0（恢复高优先级），奖励等待IO的进程，避免饥饿。
• 定期优先级重置：部分MLFQ实现会定期将所有进程优先级重置为最高，防止低优先级进程永远得不到调度，XV6的该实现通常也会在时钟中断的周期性处理中加入此逻辑。

内容的提问来源于stack exchange，提问作者Markus helbæk