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; } /* 进程是交互式进程，并且比过期队列中所有进程的静态优先级高，那么就将它加到活动队列中。这实际上是对交互式进程的优待。 */ else enqueue_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代码注释