分析了一下2.6.29内核的调度程序，花了不少时间，可是自己还是觉得不是很清楚，里面有些地方可能还不正确。
进程调度分析——关于2.6.29内核源代码
选题理由：Linux 是一个庞大、高效而复杂的操作系统，它的内核包括进程调度、内存管理、进程间通信、虚拟文件系统和网络接口五部分，其中，进程调度是多任务操作系统的核心。
1、进程调度的时机
进程状态转换
当前进程时间片用完
设备驱动程序运行时
从内核态返回到用户态
从中断或系统调用中返回；
进程重新允许抢占；
主动进入休眠（例如wait_event_interruptible()接口）
2、进程调度的依据
调度程序运行时，要在所有处于可运行状态的进程中选择最值得运行的进程投入运行。那么就需要有选择的依据
1.策略（policy）
SCHED_NORMAL(SCHED_OTHER):普通的分时进程
SCHED_FIFO :先入先进的实时进程
SCHED_RR： 时间片轮转的实时进程
SCHED_BATCH:批处理进程，与普通进程不被抢占的情况类似
SCHED_IDLE:
linux对调度策略定义如下：
#define SCHED_NORMAL 0
#define SCHED_FIFO 1
#define SCHED_RR 2
#define SCHED_BATCH 3
#define SCHED_IDLE 5
2.CFS调度器
⑴Linux 2.9.26中用到了CFS调度器，CFS 即Completely Fair Scheduler，是 Ingo Molnar
使用的一个新的桌面（desktop）进程调度器，后被加入到Linux 2.6.23。可以说，CFS基本上在实时硬件上模拟了一个理想的、精确的多任务CPU。
⑵在CFS中，虚拟运行时间通过每任务（per-task）的p->se.vruntime值来表示和跟踪。这样就可以确定时间戳（timestamp）和某个任务应该得到的期望CPU时间。（在一个理想的硬件上，任意时间内所有任务都应拥有相同的p->se.vruntime值）。CFS的选择也很简单，总是选择p->se.vruntime值最小的任务先运行。它总是在可运行（runable）任务之间拆分CPU时间，尽可能的使其接近“理想多任务硬件”。
⑶CFS没有使用运行队列（runqueue）原来的数据结构，它使用了按照时间排序的红黑树（rbtree）来构造一个未来任务执行的时间线（timeline）.CFS包含rq->cfs.min_vruntime,它是一个单调递增的值，跟踪运行队列中最小虚拟运行时间。随着系统的运行，min_vruntime用来尽可能的将新激活的进程放在树的左侧。
⑷正在运行的任务的总数是通过rq->cfs.load来统计的。随着p->se.vruntime值的不断增加，直到树中某任务红黑树中“最左任务”。这时新的最左任务被选中，投入运行。
⑸特殊的，CFS使用纳秒计时，不依赖任何jiffies或者HZ。应此，CFS也就没有时间片（timeslices）的概念，没有任何形式的检测。
3、进程调度算法
Linux 2.6.29内核的调度算法采用了红黑树算法。红黑树是平衡二叉树的一种，它有很好的性质，树中的结点都是有序的，而且因为它本身就是平衡的，所以查找也不会出现非常恶劣的情况，基于二叉树的操作的时间复杂度是O（log(N)）。
4、主要数据结构
1.运行队列rq
struct rq {
spinlock_t lock; //保护进程链表（runqueue）的自旋锁
unsigned long nr_running;//运行队列链表中可运行进程的数量
unsigned long cpu_load[CPU_LOAD_IDX_MAX];//基于runqueue平均进程数的 CPU负载因子
unsigned char idle_at_tick;//空闲
unsigned long last_tick_seen;
unsigned char in_nohz_recently;
struct load_weight load;//在本地CPU上负载的任务
unsigned long nr_load_updates;//负载更新的次数
u64 nr_switches;//CPU执行进程切换的次数
struct cfs_rq cfs;//指向CFS运行队列结构的指针
struct rt_rq rt; //指向实时进程的指针
struct list_head leaf_cfs_rq_list; //在本地CPU上添加CFS叶
struct list_head leaf_rt_rq_list;//在本地CPU上添加实时叶
unsigned long nr_uninterruptible;//不可中断的进程数
struct task_struct *curr, *idle;//指向当前进程和空闲进程的指针 unsigned long next_balance;//下一个平衡
struct mm_struct *prev_mm;//指向当前进程的mm的指针
u64 clock;//时钟数目
atomic_t nr_iowait;//曾经在runqueue但是现在正在等待I/O操作完成的进程数
struct root_domain *rd;//根域
struct sched_domain *sd;//指向当前CPU的基本调度域
int active_balance;//标志一些进程将被从一个本地运行队列转移到其他的运行队列
int push_cpu;//没有使用
int cpu;//运行队列对应的CPU号
int online;
unsigned long avg_load_per_task;平均负载任务的数目
struct task_struct *migration_thread;//迁移内核线程的进程描述符指针
struct list_head migration_queue;//从运行队列中被删除的进程链表
｝
2.task_struct中增加部分
int prio, static_prio, normal_prio;//进程优先级
unsigned int rt_priority;//实时进程的优先级
struct list_head children; //指向孩子节点的链表
struct list_head sibling; //同一个父节点的孩子的链表
struct sched_entity *parent;//指向调度程序入口的指针
struct cfs_rq *cfs_rq; //指向排好队的运行队列指针
struct cfs_rq *my_q; //指向该（cfs）运行队列的组的指针
5、调度函数schedule()的实现
函数schedule()实现调度程序。它的任务是从运行队列的链表中找到一个进程，并将CPU分配给这个进程。它可以由多个内核控制方式调用，可以直接调用也可以延迟调用。
实现过程中的几个重要的变量：
rq->cur:全局变量，表示当前正在运行的进程
prev: 局部变量，表示调度发生之前执行的进程，用来保存current的值
next: 局部变量，表示调度之后要执行的进程。
schedule()函数的关键操作是设置next局部变量，使它指向被选中的进程，该进程将取代current进程。如果系统中没有优先级高于current进程的可运行进程，那么最终next与current相等，将不发生任何进程切换。
首先，schedule()函数禁用内核抢占，并初始化一些局部变量：
need_resched:
preempt_disable(); //禁止内核抢占
cpu = smp_processor_id();//获得当前CPU的ID号，并赋值给局部变量cpu
rq = cpu_rq(cpu); //使rq指向CPU对应的运行队列（runqueue）
rcu_qsctr_inc(cpu);
prev = rq->curr;//使prev指向当前执行的进程
switch_count = &prev->nivcsw; //记录切换次数
release_kernel_lock(prev);//释放大内核锁
need_resched_nonpreemptible:
schedule_debug(prev); //如果禁止内核抢占，而又调用了cond_resched就会出错。这里就是用来捕获该错误的。
下一步，关闭本地中断，获取所要保护的运行队列（runqueue）的自旋锁（spinlock），为查找可运行进程做准备。
spin_lock_irq(&rq->lock); //获取自旋锁
update_rq_clock(rq); //更新所保护的runqueue的锁
clear_tsk_need_resched(prev);//清TIF_NEED_RESCHED标志
接下来，检查prev的状态。如果不是可运行状态，而且没有在内核态被抢占，就应该从运行队列中删除prev进程。但是，如果它是非阻塞挂起信号，而且状态为TASK_INTERRUPTIBLE，函数就把该进程的状态设置为TASK_RUNNING，并将它插入到运行队列。这个操作与把处理器分配给prev是不同的，它只是给prev一次选中执行的机会。
if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
if (unlikely(signal_pending_state(prev->state, prev)))//进程是非阻塞挂起信号，而且状态为TASK_INTERRUPTIBLE
prev->state = TASK_RUNNING; //设置状态为TASK_RUNNING
else
deactivate_task(rq, prev, 1);//从运行队列中将该进程删除
switch_count = &prev->nvcsw;
}
如果运行队列中没有可运行的进程存在，函数就调用idle_balance(),从另外一个运行队列迁移一些可运行进程到本地运行队列中。
if (unlikely(!rq->nr_running))
idle_balance(cpu, rq);
如果prev和next不是同一个进程，则将其进行交换
if (likely(prev != next)) {
sched_info_switch(prev, next);
rq->nr_switches++;
rq->curr = next;
++*switch_count;
context_switch(rq, prev, next); /* unlocks the rq */
//建立next的地址空间。如果next是一个内核线程，它使用perv所使用的地址空间。如果next是一个普通进程，用next的地址空间替换prev的地址空间。空间的交换可能会将堆栈的底翻转从而更新局部变量。
cpu = smp_processor_id();//更新局部变量
rq = cpu_rq(cpu);
} else //如果prev和next是同一个进程就不进行切换
spin_unlock_irq(&rq->lock);//释放中断请求的自选锁，接受中断请求
最后，schedule()在需要的时候重新获得大内核锁，重新启用内核抢占，并检查是否一些其他的进程已经设置了当前的TIF_NEED_RESCHED标志。如果是，则整个schedule（）函数重新开始执行，否则，函数结束。
if (unlikely(reacquire_kernel_lock(current) < 0))//当前进程占有大内核锁
goto need_resched_nonpreemptible;
preempt_enable_no_resched();
if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))//进程已经设置了当前进程的TIF_NEED_RESCHED标志
goto need_resched;