linux内核进程调度—scheduler_tick函数解析
本博，我们详细分解每次定时器中断调用的最重要的更新时间片的函数 —— scheduler_tick函数
当每次时钟节拍到来时，即我们提到过的timer_interrupt会调用do_timer_interrupt_hook，从而调用do_timer和update_process_times函数，update_process_times则就是用来更新进程使用到的一些跟时间相关的字段，其罪重要的是调用scheduler_tick()更新时间片剩余节拍数：
void scheduler_tick(void)
{
unsigned long long now = sched_clock();
struct task_struct *p = current;
int cpu = smp_processor_id();
struct rq *rq = cpu_rq(cpu);
update_cpu_clock(p, rq, now);
rq->timestamp_last_tick = now;
if (p == rq->idle) {
if (wake_priority_sleeper(rq))
goto out;
rebalance_tick(cpu, rq, SCHED_IDLE);
return;
}
/* Task might have expired already, but not scheduled off yet */
if (p->array != rq->active) {
set_tsk_need_resched(p);
goto out;
}
spin_lock(&rq->lock);
if (rt_task(p)) {
if ((p->policy == SCHED_RR) && !--p->time_slice) {
p->time_slice = task_timeslice(p);
p->first_time_slice = 0;
set_tsk_need_resched(p);
/* put it at the end of the queue: */
requeue_task(p, rq->active);
}
goto out_unlock;
}
if (!--p->time_slice) {
dequeue_task(p, rq->active);
set_tsk_need_resched(p);
p->prio = effective_prio(p);
p->time_slice = task_timeslice(p);
p->first_time_slice = 0;
if (!rq->expired_timestamp)
rq->expired_timestamp = jiffies;
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 {
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, rq, NOT_IDLE);
}
scheduler_tick()负责执行以下步骤：
1. 把转换为纳秒的TSC的当前值，也就是读取处理器中，存放记录着当前距离开机后时间戳寄存器的值，存入本地运行队列的timestamp_last_tick字段。我们在相关博文中提到过了，CPU中有个TSC硬件机制，当系统的时钟节拍为1GHz时，那么时间戳每纳秒增加1次。这个时间戳是从函数sched_clock()获得的。
2. 检查当前进程是否是本地CPU的swapper进程（通过p == rq->idle语句判断），如果是，执行下面的子步骤：
a) 如果本地运行队列除了swapper进程外，还包括另外一个可运行的进程，就设置当前进程的TIF_NEED_RESCHED字段，以强迫进行重新调度。就像我们稍后在讲schedule函数博文所看到的，如果内核支持超线程技术，那么，只要一个逻辑CPU运行队列中的所有进程都有比另一个逻辑CPU（两个逻辑CPU对应同一个物理CPU）上已经在执行的进程有低得多的优先级，前一个逻辑CPU就可能空闲，即使它的运行队列中有可运行的进程。
b) 跳转到第7步（没有必要更新swapper进程的时间片计数器）
3. 检查current->array是否指向本地运行队列的活动链表（通过p->array != rq->active语句判断）。如果不是，说明该进程已经过期，已经处于rq->expired链表中，但还没有被替换，则设置他的TIF_NEED_RESCHED字段，以强迫进行重新调度并跳转到第7步。
4. 获得this_rq()->lock自旋锁。
5. 递减当前进程的时间片计数器，并检查是否已经用完时间片（!--p->time_slice）。由于进程的调度类型不同（rt_task(p)），函数所执行的这一步操作也有很大的差别，我们马上将会讨论它。
6. 释放this_rq()->lock自旋锁。
7. 调用rebalance_tick()函数，该函数应该保证不同CPU的运行队列包含数量基本相同的可运行进程，以后博文还会详细谈到。
更新实时进程的时间片：
如果当前进程是先进先出（FIFO）的实时进程，即在代码中，不进入最后两个if条件断，则函数scheduler_tick()什么都不做。实际上在这种情况下，current所表示的当前进程想占用CPU多久就占用多久，而且不可能比其他优先级低或其他优先级相等的进程所抢占，因此，维持当前进程的最新时间片计数器是没有意义的。
前面讲过，基于时间片轮转的实时进程（rt_task(p) && (p->policy == SCHED_RR)）不能更新其动态优先级，而只能修改其时间片。那么，如果current表示基于时间片轮转的实时进程（通过(p->policy == SCHED_RR) && !--p->time_slice语句判断），scheduler_tick()就递减它的时间片计数器并检查时间片是否被用完：
if (current->policy == SCHED_RR && !--current->time_slice) {
current->time_slice = task_timeslice(current);
current->first_time_slice = 0;
set_tsk_need_resched(current);
requeue_task(p, rq->active);
}
如果函数确定时间片确实用完了，就执行一系列操作以达到抢占当前进程的目的，如果必要的话，就尽快抢占。
第一步操作包括调用task_timeslice()来重填进程的时间片计数器，查看“进程调度的数据结构和优先级 ”博文。该函数检查进程的静态优先级，并根据前面“进程的优先级”公式返回相应的基本时间片。此外，current的first_time_slice字段被清零：该标志被fork系统调用例程中的copy_process()设置，并在进程的第一个时间片刚用完时立刻清零。
第二步，scheduler_tick()函数调用函数set_tsk_need_resched()设置进程的TIF_NEED_RESCHED标志。该标志强制调用schedule()函数，以便current指向的进程能被另外一个有相同优先级或更高优先级的实时进程所取代。
scheduler_tick()的最后一步操作包括把进程描述符移到与当前进程优先级相应的运行队列活动链表的尾部（requeue_task函数本质上执行的是list_add_tail(¤t->run_list,this_rq( )->active->queue+current->prio);）。把current指向的进程放到链表的尾部，可以保证每个优先级与它相同的可运行实时进程获得CPU时间片以前，它不会再次被选择来执行。这是基于时间片轮转的调度策略。进程描述符的移动是通过两个步骤完成的：先调用list_del()把进程从运行队列的活动链表中删除，然后调用list_add_tail()把进程重新插入到同一个活动链表的尾部。
更新普通进程的时间片：
如果当前进程是普通进程（第四个首层if），函数scheduler_tick()执行下列操作：
1. 递减时间片计数器（current->time_slice）。
2. 检查时间片计数器。如果时间片用完，函数执行下列操作
a) 调用dequeue_task()从可运行进程的this_rq()->active集合中删除current指向的进程。
b) 调用set_tsk_need_resched( )设置TIF_NEED_RESCHED标志。
c) 更新current指向的进程的动态优先级：current->prio = effective_prio(current);。函数effective_prio()读current的static_prio和sleep_avg字段，并根据前一博文的公式计算出进程的动态优先级。
d) 重填进程的时间片：
current->time_slice = task_timeslice(current);//前面代码，请仔细琢磨
current->first_time_slice = 0;
e) 如果本地运行队列数据结构中的expired_timestamp字段等于0（即过期进程集合为空），就把当前时钟节拍值赋给expired_timestamp：
if (!this_rq( )->expired_timestamp)
this_rq( )->expired_timestamp = jiffies;
f) 把当前进程插入活动进程集合或过期进程集合：
if (!TASK_INTERACTIVE(current) || expired_starving(rq) {//如果当前进程不是交互进程，或者运行队列上有饥饿进程存在
enqueue_task(current, this_rq( )->expired);
if (current->static_prio < this_rq( )->best_expired_prio)
this_rq( )->best_expired_prio = current->static_prio;
} else
enqueue_task(current, this_rq( )->active);
如果用前面列出的公式（3）识别出进程是一个交互式进程，TASK_INTERACTIVE宏就产生1。函数expired_starving检查运行队列中的第一个过期进程的等待时间是否已经超过1000个时钟节拍乘以运行队列中的可运行进程数加1，如果是，函数返回1。如果当前进程的静态优先级大于一个过期进程的静态优先级，函数也也返回1。
3. 否则，即时间片没有用完（current->time_slice不等于0），检查当前进程的剩余时间片是否太长：
if (TASK_INTERACTIVE(p) && !((task_timeslice(p) -
p->time_slice) % TIMESLICE_GRANULARITY(p)) &&
(p->time_slice >= TIMESLICE_GRANULARITY(p)) &&
(p->array == rq->active)) {
list_del(¤t->run_list);
list_add_tail(¤t->run_list,
this_rq( )->active->queue+current->prio);
set_tsk_need_resched(p);
}
宏TIMESLICE_GRANULARITY产生两个数的乘积给当前进程的bonus，其中一个数为系统中的CPU数量，另一个为成比例的常量。基本上，具有高静态优先级的交互式进程，其时间片被分成大小为TIMESLICE_GRANULARITY的几个片段，以使这些进程不会独占CPU。
好啦，重要的scheduler_tick函数就介绍到这里，如果看不懂就回头去看看相关的数据结构。下一讲里，我们将通过介绍try_to_wake_up函数，给大家详细讲解进程是如何由其他状态进入到运行状态的。