coperating-systemschedulingxv6rr

MLFQ anf RR in XV6


I am trying to understand how the MLFQ and RR in XV6 work. An implementation i have seen is as follows:

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);
    }
}

I am not that steady in C, but do understand the code provided. However i dont understand how the priority will change using MLFQ and how an process will run for an specified amount of time until a switch in RR. Am i totally off if i think it is an interrupt happening here witch is implemented in the trap.c file? In that case can anyone answer how this is implemented in the trap.c file?

Thanks for the answer in advance.


Solution

  • If the MLFQ is correctly implemented, some logic should be handling the trap and updating the process's priority. This may be inside usertrap in trap.c, or inside the yield function in proc.c. The former function should call the latter with the reason the process yielded as an argument, and this can be used to edit the priority if for example the timeslice were used up.