Understading the Linux Kernel Scheduler

Question

I'm studying the Linux Kernel and am trying to figure out how the Round Robin scheduling algorithm works. In the kernel\sched_rt.c file, there's a method called task_tick_rt defined like this:

static void task_tick_rt(struct rq *rq, struct task_struct *p, int queued)
{
    update_curr_rt(rq);

    watchdog(rq, p);

    /*
     * RR tasks need a special form of timeslice management.
     * FIFO tasks have no timeslices.
     */
    if (p->policy != SCHED_RR)
            return;

    if (--p->rt.time_slice)
            return;

    p->rt.time_slice = DEF_TIMESLICE;

    /*
     * Requeue to the end of queue if we are not the only element
     * on the queue:
     */
    if (p->rt.run_list.prev != p->rt.run_list.next) {
            requeue_task_rt(rq, p, 0);
            set_tsk_need_resched(p);
    }

}

What I don't understand (besides the fact that there's a useless queued parameter) is what the code is trying to achieve by the if (--p->rt.time_slice) check. I don't understand why the task list pointer p is being decremented by 1, in other words, why is the method checking the previous task instead of the current one? Any clarification on this is appreciated.

Answer 1

Check out c operator precedence http://en.wikipedia.org/wiki/Operators_in_C_and_C%2B%2B#Operator_precedence

The -> operator has a higher precedence than the prefix ++, so this particular condition could be written:

if (--(p->rt.time_slice))

In other words, it is the timeslice which is being decremented, not the pointer.

---

The queued parameter may appear useless here, but it has a reason to be there. Specifically notice where task_tick_rt() is called from. Its only reference is when it is assigned to the .task_tick function pointer in the rt_sched_class instance of struct sched_class: http://lxr.free-electrons.com/source/kernel/sched/rt.c#L1991

So we see that each scheduling algorithm has its own struct sched_class function vector which the kernel will call into for scheduling services. If we look at other algorithms, we see the CFS (Completely Fair Scheduling) algorithm also has its own instance of struct sched_class, named fair_sched_class: http://lxr.free-electrons.com/source/kernel/sched/fair.c#L6179

The .task_tick member in the CFS case points to task_tick_fair(): http://lxr.free-electrons.com/source/kernel/sched/fair.c#L5785

Note task_tick_fair() does make use of the queued parameter. So when the .task_tick member is called into (here and here), a 0 or a 1 is passed in for the queued parameter. So while task_tick_rt() doesn't use it, the queued parameter must still be their so the function pointer types in the struct sched_class function vector all match up.

In short, the struct sched_class function vector specifies the interface between scheduling algorithms and the rest of the kernel. The queued parameter is there should a given algorithm choose to use it, but in the case of Round Robin, it is simply ignored.