调度单位
进程描述，位于运行栈底部，可通过偏移定位
thread_info {
task_struct *task; //基本调度单位(下面展开)
flags //TIF_NEED_RESCHED表明需要调度
cpu //CPU号
。。。
}
任务调度的基本单位
task_struct {
state //状态, TASK_RUNNING, ZOMBIE或其他
*thread_info
prio 动态优先级
static_prio 静态优先级
sleep_avg 平均睡眠时间
policy 调度算法,NORMAL, RR, FIFO
time_slice 剩余的时间片
rt_priority 实时优先级
... ...
}
运行队列(调度控制结构)
runqueue {
task_struct *curr 正在运行的任务
prio_array *active 活动的优先队列
prio_array *expired 过期的优先队列
prio_array arrays[2] 实际优先队列
...
}
优先队列（O(1)调度算法的结构）
prio_array {
nr_active 队列中的任务数
bitmap[BITMAP_SIZE]
// 优先位图, 用1表示对应优先级有进程需要调度，0表示没有。通过位查找，快速找到优先级最高的任务。
list_head queue[MAX_PRIO] 优先队列
}
优先级
linux把进程分为实时调度与一般调度。实时调度优先级为0~99, 只用FCFS或RR来调度。非实时的一般进程优先级为100~139，即其计算公式为100（最高实时优先级）+20+nice。其中nice值为-20~19, 由进程创建时指定。动态优先级根据进程的交互性来动态计算优先级，一般以nice为基数，加上-5~+5的交互性奖罚。通过计算sleep_avg来评估进程的交互性，如果sleep_avg比较多，即该进程为IO消耗型，可把其优先级降低(不需占用太多CPU)，反之亦然。
时间片
进程的可用时间片是按照计算出来的优先级按比例分配。数值为5~800ms, 默认值为100ms.
可调度标志
内核提供了一个need_resched标志来表明是否需要重新执行一个调度。当某个进程耗尽它的时间片时，scheduler_tick()就会设置这个标志；当一个优先级高的进程进入可执行状态的时候，try_to_wake_up()也会设置这个标志。在返回用户空间以及从中断返回的时候，内核也会检查need_resched标志。如果已被设置，内核会在继续执行之前调用调度程序
调度算法
核心由schedule()函数和scheduler_tick()函数实现。schedule函数从优先级数组prio_array中选取优先级最高的进程 --> 获取进程的thread_info --> 实施context switch切换到新的进程运行。而scheduler_tick()主要是更新时间片，时钟中断程序会自动调用scheduler_tick。scheduler_tick判断当前进程
若为实时进程，且时间片耗尽，重新计算时间片，并重新插入活跃队列的尾部。
若为普通进程，且时间片耗尽，重新计算时间片，移入过期队列。
当活跃优先级队列中已没有剩余的被调度进程，活跃优先级队列与过期优先级队列的指针进行交换，进入新一轮的调度。2.6版本内核每次时间片用完就重新计算时间片，大大提升了调度效率。
何时调度？（何时被调用schedule()）
1. 直接主动调用
2. 活动进程进入睡眠
3. 设置need_resched.当从内核态返回用户态时检测这个位，如果为1，则调度schedule().
以下三种情况会设置need_schedule
a. 时钟中断服务程序中，用完自己的时间片
b. 当唤醒一个睡眠进程时，该进程有更高优先级
c. 一个进程改变了调度策略，优先级等。
何时抢占？
用户抢占
1. 当从系统调用返回到用户态
2. 从中断程序返回到用户态。
内核抢占
2.6版本的内核是可以抢占的。
1. 从中断返回内核时，若内核不拥有锁，则可被抢占。若拥有锁，则不可抢占。这是内核通过preempt_count变量来判断的。
2. 内核阻塞，导致调用schedule()
参考
linux kernel 2.6进程调度分析
Robert Love
