Linux2.6.36中实时调度分析
Linux/kernel/sched_rt.c(1800lines)
Linux实时调度分为先进先出调度和时间片轮转
SCHED_FIFO：
适用于对响应时间要求比较高，而起执行时间比较短的实时进程。实时进程按照其入队的先后顺序执行，除非因中断等原因主动放弃cpu或者是遇到更高优先级进程抢断，否则该进程一直占用cpu；
SCHED_RR：
适用于对时间响应要求高而且执行时间较长的进程，各进程轮询使用cpu，当进程的时间片用完时将从运行队列出队，然后加入队尾。
优先级：
实时进程的优先级为0—99，非实时进程的优先级是100—139，所以任何时候只要有实时进程，先执行的都是实时进程。这些优先级在linux-2.6.36\include\linux\sched.h 文件中的struct task_struct中有定义：
初级会计职称培训
struct task_struct{
……
unsigned int rt_priority;
unsigned int policy;
……
};
policy有是个状态SCHED_FIFO SCHED_RR SCHED_OTHER SCHED_YIELD SCHED_LITMUS SCHED_IDLE SCHED_BATCH前三种表示三中不同的调度方式，最后两种属于特殊的，SCHED_YIELD只要进程属于这种，即任何进程都可以抢占它。
实现O(1)时间片重新分配：
在实时调度中，每一个cpu维护自己的一个运行队列（active array），为了实现O(1)时间的重新分配时间片，还有一个辅助的队列（expired array），前一个是运行队列，里面装着的都是等待运行的任
对外汉语教师资格证考试
务，当时间片结束后，调度器重新计算进程的时间片，优先级，从active中删除，加入expired队列中，当active变为空的时候，两个指向队列的指针呼唤，active取得expired的任务后继续运行，从而达到O(1)时间内完成时间片的分配。在2.4版中，只有一个队列，一个时间片分配后等所有的任务执行完毕再分配时间片，复杂度是O(n)，n是任务数。
可抢占，多cpu之间平衡（调度器负载均衡）：
为了实现实时性，linux中的任务是可抢占的。而且每一个内核会整体维护一个数组，记录当前每一个cpu运行的任务的优先级的高低。当有一个实时的任务需要运行时，即开始发生抢占，若在当前的cpu上能任务的优先级比新来的低，则抢占之，否则，从优先级的数组中找到当前所有cpu中优先级最低的cpu下手，抢占之。若是这个任务之前是被绑定在某一个cpu上的，醒来时发现当前cpu上的任务优先级比自己的高，但是因为绑定了cpu，即使其他的cpu可以抢占也只能在当前的cpu上运行。
有时候会出现某一个cpu很忙而其他的cpu空闲的情况，所以有load_balance机制，即从繁忙的cpu上调任务到空闲的cpu上运行。在繁忙的cpu上有push机制，即那些任务是可以被push出去的，当然他们都是在expired array中，即不是能立刻得到运行的队列。而空闲的cpu在运行的时候会尝试从其他的cpu上那些push的任务中寻找优先级较高的来执行，若能找到，能pull过来在空闲的cpu上运行，不能则运行自己的运行队列。
为了快速寻找优先级最高的任务，rt_prio_array结构体是这样定义的：
struct rt_prio_array{
DECLARE_BITMAP(bitmap,MAX_RT_PRIO+1);
struct list_head queue[MAX_RT_PRIO];
};
即每一个对应的优先级下面有一个队列，表示这个优先级下的队列，若队列为空，则bitmap 对应位为0，否则为1，寻找时使用sched_find_first_bit能找到队列的最高优先级的队列，然后行队列中取到任务：
index=sched_find_first_bit(array->bitmap);
queue=array->queue+index;
实时调度类：
实时调度主要是实现它自己的调度类，供文件sched.c使用。Linux实时调度是属于软实时，虽然内核
可抢占，也使用了很多方式让实时进程能快速得到相应，但是并没有处理有关内存分配的情况，即即使任务能得到快速调度，但是不能为任务分配内存，也会让任务无法运行的。实时调度类如下
static const struct sched_class rt_sched_class={
.next=&fair_sched_class,
.enqueue_task=enqueue_task_rt,
cafe是什么意思>emm什么意思.dequeue_task=dequeue_task_rt,
.yield_task=yield_task_rt,
.check_preempt_curr=check_preempt_curr_rt,
.pick_next_task=pick_next_task_rt,
.put_prev_task=put_prev_task_rt,
#ifdef CONFIG_SMP
.lect_task_rq=lect_task_rq_rt,
.t_cpus_allowed=t_cpus_allowed_rt,
.rq_online=rq_online_rt,
.rq_offline=rq_offline_rt,
.pre_schedule=pre_schedule_rt,
.post_schedule=post_schedule_rt,
.task_woken=task_woken_rt,
.switched_from=switched_from_rt,
#endif
.t_curr_task=t_curr_task_rt,
.task_tick=task_tick_rt,
.get_rr_interval=get_rr_interval_rt,
特拉帕特里克
.
prio_changed=prio_changed_rt,
.switched_to=switched_to_rt,
};
根据调度类的顺序来分析函数：
函数原型:static void
enqueue_task_rt(struct rq*rq,struct task_struct*p,int flags)
函数功能：当某一个task属于Runnable时，就会调用这个函数，将task加入到运行队列中，并调用inc_rt_tasks函数，将rt_nr_running加1，rt_nr_running表示运行队列中有多少任务是属于runnable的，（从队列中删除一个任务或添加任务到队列中）调用了：enqueue_rt_entity
如何学习彩妆
enqueue_pushable_task
dequeue_task_rt
2.2.dequeue_task_rt
函数原型：
static void dequeue_task_rt(struct rq*rq,struct task_struct*p,int flags)其中flags没有任何作用
函数功能：更新调度信息
update_curr_rt(rq);
实际工作，将rt_从运行队列中删除然后
添加到队列尾部
dequeue_rt_entity(rt_);
从push表中删除p(即此时p不能迁移到其他的cpu运行)
dequeue_pushable_task(rq,p);
yield_task_rt
3.3.yield_task_rt
函数原型：static void yield_task_rt(struct rq*rq)
函数功能：yield为放弃的意思，放弃当前运行的任务，然其他任意的任务都可以抢占cpu 调用：requeue_task_rt(rq,rq->curr,0);//只将curr移动到链表的末尾即可。unexpected
check_preempt_curr_rt
4.4.check_preempt_curr_rt
函数原型：static void
check_preempt_curr_rt(struct rq*rq,struct task_struct*p,int flags)函数功能：flags没有作用该函数将检查当前运行的任务是否可被抢占
1.根据p的优先级比当前任务的高（即数值较小）或者是调度类型是
SCHED_LITMUS，则调用函数：
resched_task(rq->curr);//就将当前任务设置为可抢占的。
2.若p的优先级和当前任务的优先级相等且不需要调度，则调用：
check_preempt_equal_prio(rq,p);
根据当前可用cpu的数目，当前任务是否可以迁移等因素，决定是否要重新
调度
pick_next_task_rt
5.5.pick_next_task_rt
函数原型：static struct task_struct*pick_next_task_rt(struct rq*rq)
函数功能：选择下一个可运行的任务
1.可能是当前任务结束后有从bitmap中寻找最高优先级的
2.或者是从其他的push队列中找到后将其从push队列总删除
put_prev_task_rt
6.6.put_prev_task_rt
函数原型：static void put_prev_task_rt(struct rq*rq,struct task_struct*p)
函数功能：把上一个执行完毕的任务放在runqueue中合适的位置
1.更新调度信息
2.若当前的任务还是active，有合适的cpu运行，将其加入push队列中等待其
它cpu拉取过去运行
lect_task_rq_rt
7.7.lect_task_rq_rt
函数原型：static int
lect_task_rq_rt(struct rq*rq,struct task_struct*p,int sd_flag,int flags)函数功能：若当前任务是实时任务，则唤醒其他运行队列中的任务（试图找一个更高优先级的任务），若当前任务不是实时任务，简单的从运行队列中开始一个实时任务即可。
t_cpus_allowed_rt
8.8.t_cpus_allowed_rt
函数原型：static void t_cpus_allowed_rt(struct task_struct*p,
const struct cpumask*new_mask)
函数功能：迁移之后，设置任务p可运行的cpu（估计cpumask即标记那些cpu是这个任务可使用的cpu），同时还会设置可迁移的任务数目等等
rq_online_rt
9.9.rq_online_rt
函数原型：static void rq_online_rt(struct rq*rq)
函数功能：
设置rq负载
cappuccino
激活rq运行时间
设置cpu的优先级（可能）
cpupri_t(&rq->rd->cpupri,rq->cpu,rq->rt.highest_prio.curr);
rq_offline_rt
10.
10.rq_offline_rt
函数原型：static void rq_offline_rt(struct rq*rq)
函数功能：
清除负载
是运行时间失效
使cpu优先级变成CPUPRI_INVALID
cpupri_t(&rq->rd->cpupri,rq->cpu,CPUPRI_INVALID);
pre_schedule_rt
11.
11.pre_schedule_rt
函数原型：static void pre_schedule_rt(struct rq*rq,struct task_struct*prev)
函数功能：调用pull_rt_task(rq);
即从其他的cpu上的运行队列中拉取（pull）任务过来运行
post_schedule_rt
12.post_schedule_rt
12.
函数原型：static void post_schedule_rt(struct rq*rq)
函数功能：调用push_rt_tasks(rq);//将任务推送出去运行
13.13.task_woken_rt
task_woken_rt 函数原型：static void task_woken_rt(struct rq *rq,struct task_struct *p)
函数功能：要是任务没有运行而且也没有打算立即启动重新调度，就应该将任务推出去（到
其他的cpu ），调用push_rt_tasks(rq);
14.14.switched_from_rt
switched_from_rt 函数原型：static void
switched_from_rt(struct rq *rq,struct task_struct *p,int running)
函数功能：
15.15.t_curr_task_rt
t_curr_task_rt 函数原型：static void t_curr_task_rt(struct rq *rq)
函数功能：设置运行队列中当前任务的调度实体的exec_start 为rq->clock
struct task_struct *p =rq->curr;
p->.exec_start =rq->clock;
dequeue_pushable_task(rq,p);//将p 从rq 中删除
16.16.task_tick_rt
task_tick_rt 函数原型：static void
task_tick_rt(struct rq *rq,struct task_struct *p,int queued)
函数功能：决定那些任务需要执行，那些任务需要踢出runqueue
管理任务的时间片
若不是SCHED_RR 则不需要管理
设置时间片，若时间片已经用完则返回
若队列里面不止一个任务，设置时间片以后重新调度
_rr_interval_rt
get_rr_interval_rt 函数原型：static unsigned
int get_rr_interval_rt(struct rq *rq,struct task_struct *task)
函数功能：获SCHED_RR 任务的时间片长度
若是SCHED_RR 返回默认时间片DEF_TIMESLICE ，否则为0
18.18.prio_changed_rt
prio_changed_rt 函数原型：static void
prio_changed_rt(struct rq *rq,struct task_struct *p,
int oldprio,int running)parachute
函数功能：改变优先级，然后初始化push 或者是pull
若优先级oldprio <p->prio ，则尝试pull 更高的优先级任务过来运行
aggressively
若p 的优先级大于当前最高优先级而且当前任务就是p ，则重新调度
19.19.switched_to_rt
switched_to_rt 函数原型：static void switched_to_rt(struct rq *rq,struct task_struct *p,
int running)
函数功能：当改变一个任务成实时任务时，实时任务的运行队列可能会过载。这种情况下，
我们就要尝试将他们推送到其他的运行队列
