1. 调用时机

一般会在时钟中断时被调用，作用有：

• 剥夺时间片耗完的进程的CPU使用权，当然具体细节上没这么简单；
• 进行定时的CPU间负载均衡处理；

2. 大致流程

• idle进程(swapper进程)的处理。

  idle进程没有时间片可言，主要思路是如果当前逻辑CPU的可执行队里已有进程，应该尽快调度。

  这里所指的调度还是延时调度，也就是设置TIF_NEED_RESCHED，

  还会有些强制调度之类的处理，细节暂未研究；

• 实时进程的处理。

  在这版本的源码中，没有调度类的概念，实时进程和普通进程是放在相同的可执行队列的。

  实时进程的调度状况：

  • 如果可执行的话，会一直停留在active队列，

    优先级比所有普通进程高，

    因此如果实时进程没有阻塞，同一逻辑CPU中的普通进程没机会运行；

  • SCHED_RR类型的实时进程在时间片消耗完后，会被放到active队列的末尾，

    并且设置TIF_NEED_RESCHED位，

    因此拥有不小于当前优先级的其他实时进程会被调度到；

  • SCHED_FIFO类型的实时进程，就真的除非被更高优先级的实时进程抢占，

    时钟中断这边并不能让它们让出CPU；

• 交互式进程的处理

  • 当时间片用完时，

    设置TIF_NEED_RESCHED位；

    但当其比expired队列所有进程优先级都高时，

    并不放入expired队列中，而是重新放入active队列中；

    这是对交互式进程的一种优待处理；

  • 当时间片未用完时，

    交互式进程的时间片会被细分为粒度，当运行完一个粒度后，

    就需要重新调度，也就是设置TIF_NEED_RESCHED位；

    这是对交互式进程的一种削弱，毕竟地位没有实时进程高；

• 普通非交互式进程的处理

  • 当时间片用完时，

    设置TIF_NEED_RESCHED位，并放入到expired队列中；

  • 当时间片未用完时，不作任何操作；

• 定时负载均衡

  ​ 在整个函数结束之前执行的一步，对各个CPU进行负载均衡处理。

  ​ 具体有点复杂，会在load_balance()的文章进行大致介绍；

3. 源码注释

/** This function gets called by the timer code, with HZ frequency.* We call it with interrupts disabled.** It also gets called by the fork code, when changing the parent's* timeslices.*/
/*** 维持当前最新的time_slice计数器* 每次时钟节拍到来时，scheduler_tick函数将被调用，以执行与调度相关的操作。*/
void scheduler_tick(void)
{int cpu = smp_processor_id();runqueue_t *rq = this_rq();task_t *p = current;/*** 把转换为纳秒的TSC的当前值存入本地运行队列的timestamp_last_tick中。这个时间戳由sched_clock获得。*/rq->timestamp_last_tick = sched_clock();// idle进程的处理 //if (p == rq->idle) {/*** wake_priority_sleeper()的逻辑如下:* 	1.检查运行队列中除了IDLE进程外，是否还有其他可运行进程;* 	2.如果有，就设置当前进程的TIF_NEED_SCHEDULED字段;* 	3.好像多核处理器会直接强迫调度？*	scheduler_tick()是被时钟中断调用的，*	因此，如果是单核情况下，肯定会等到中断返回后再正式调度;* rebalance_tick(cpu, rq, NOT_IDLE);*/if (wake_priority_sleeper(rq))goto out;/** * 平衡每个CPU上的可执行队列，* 目标当然就是全部长度都一样。*/rebalance_tick(cpu, rq, SCHED_IDLE);/*** 没有必要更新IDLE进程的时间片计数器，所以此处直接返回。*/return;}/* Task might have expired already, but not scheduled off yet *//*** 检查current->array是否指向本地运行队列的活动链表。* 如果不是，说明进程已经过期但还没有被替换，设置TIF_NEED_SCHEDULED标志，以强制进行重新调度。*/ if (p->array != rq->active) {set_tsk_need_resched(p);goto out;}/*** 获得运行队列的自旋锁。*/spin_lock(&rq->lock);/** The task was running during this tick - update the* time slice counter. Note: we do not update a thread's* priority until it either goes to sleep or uses up its* timeslice. This makes it possible for interactive tasks* to use up their timeslices at their highest priority levels.*/// 实时进程的处理 //if (rt_task(p)) {/** RR tasks need a special form of timeslice management.* FIFO tasks have no timeslices.*//*** 对SCHED_RR类型的实时进程，需要递减它的时间片。* 对SCHED_FIFO类型的实时进程，什么都不做，退出。* * 当SCHED_RR类型的实时进程，其时间片耗尽后，* 1.更新时间片;* 2.设置TIF_NEED_SCHEDULED字段，以便返回用户时进行调度;* 3.将其放到active的末尾，这样的效果是能让优先级相同的其他实时进程被调度到;* * 这版的内核在实时进程和普通进程方面比较混乱，全部都放在一个可执行队列中，* 依靠不把实时进程放到expired队列，和实时进程永远比普通进程优先级高，* 这两点来实现实时进程长久占用CPU的效果。* */if ((p->policy == SCHED_RR) && !--p->time_slice) {/* 重新计算它的时间片,它根据进程的静态优先级来计算它的时间片。 */p->time_slice = task_timeslice(p);/*** 直到这里，说明进程一定不是第一次运行了，它已经用完了一次它的时间片，将first_time_slice置为0.* 这样，它即使退出，也不会将剩余的时间片还给父进程了。*/p->first_time_slice = 0;/*** 设置调度标志，以达到尽快抢占的目的。*/set_tsk_need_resched(p);/* put it at the end of the queue: *//*** 将实时进程放到队列末尾。这样，如此链表中还有其他同优先级的RR进程，其他进程就能够得到运行了。*/requeue_task(p, rq->active);}goto out_unlock;}// 普通进程的处理 ///* 首先递减普通进程的时间片计数器。如果用完，继续执行以下操作 */if (!--p->time_slice) {/*** 既然用完了，就将当前进程从活动集合中摘除。*/dequeue_task(p, rq->active);/*** 当然，当前进程既然已经过期，就必须设置重新调度标志，以便在中断返回前调用schedule选择另外一个进程来运行。*/set_tsk_need_resched(p);/*** 更新当前进程的动态优先级。* effective_prio根据当前进程的static_prio和sleep_avg字段，计算进程的动态优先级。*/p->prio = effective_prio(p);/*** 重填进程的时间片*/p->time_slice = task_timeslice(p);/*** 既然当前进程的一个时间片已经用完，当然就需要清除first_time_slice标志了。*/p->first_time_slice = 0;/*** 如果本地运行队列的expired_timestamp为0,表示过期进程集合为空。* 并且当前进程马上就会变成过期进程，那么将当前jiffies赋给expired_timestamp* expired_timestamp表示当前队列中，过期队列中最老进程被插入过期队列的时间。*/if (!rq->expired_timestamp)rq->expired_timestamp = jiffies;/*** 把当前进程插入过期集合或者活动集合。* TASK_INTERACTIVE判断当前进程是否是一个交互式进程。* TASK_INTERACTIVE宏检查运行队列中的第一个过期进程的等待时间* 是否已经超过1000个时钟节拍乘以运行队列中的可运行进程数+1，* 如果是返回1.* 如果当前进程的静态优先级大于过期进程的静态优先级，也返回1.*/if (!TASK_INTERACTIVE(p) || EXPIRED_STARVING(rq)) {/*** 当前进程不是交互式进程，或者过期队列中有优先级更高的进程，那么将当前进程插入到过期队列。*/enqueue_task(p, rq->expired);/*** 如果当前进程是过期队列中优先级最高的低，就更新过期队列的最高优先级。*/if (p->static_prio < rq->best_expired_prio)rq->best_expired_prio = p->static_prio;} /* 进程是交互式进程，并且比过期队列中所有进程的静态优先级高，那么就将它加到活动队列中。这实际上是对交互式进程的优待。 */elseenqueue_task(p, rq->active);} /* 普通进程的时间片还没有用完，需要进一步检查是否时间片太长 */else {/** Prevent a too long timeslice allowing a task to monopolize* the CPU. We do this by splitting up the timeslice into* smaller pieces.** Note: this does not mean the task's timeslices expire or* get lost in any way, they just might be preempted by* another task of equal priority. (one with higher* priority would have preempted this task already.) We* requeue this task to the end of the list on this priority* level, which is in essence a round-robin of tasks with* equal priority.** This only applies to tasks in the interactive* delta range with at least TIMESLICE_GRANULARITY to requeue.*//*** 总的来说，就是对交互式进程进行限制，防止它独占CPU，* 因为交互式进程有一定优待，有可能时间片用完后，仍然停留在active队列中，* 一定情况下，可能像实时进程那样，一直占着CPU。* * 但是交互式进程，地位比实时进程低，不允许这样的行为，* 所以这里就进行了一点削弱。* 把交互式进程的时间片分成几份也就是TIMESLICE_GRANULARITY，* 用完一份之后就重新调度一下。*/if (TASK_INTERACTIVE(p) && !((task_timeslice(p) -p->time_slice) % TIMESLICE_GRANULARITY(p)) &&(p->time_slice >= TIMESLICE_GRANULARITY(p)) &&(p->array == rq->active)) {requeue_task(p, rq->active);set_tsk_need_resched(p);}}
out_unlock:/*** 释放自旋锁。*/spin_unlock(&rq->lock);
out:/*** 调用rebalance_tick函数，该函数应该保证不同CPU的运行队列包含数量基本相同的可运行进程。*/rebalance_tick(cpu, rq, NOT_IDLE);
}

参考

《深入理解linux内核》

baoyou.xie Linux 2.6.12代码注释