调度：
操作系统的调度程序的两项任务：
1： 调度：
实现调度策略，决定就绪的进程、线程竞争cpu的次序的裁决原则。说白了就是进程和线程何时应该放弃cpu和选择那个就绪进程、线程来执行。
2： 分派：
原来实现调度机制如何时分复用cpu，处理好上下文交换的细节、完成进程、线程和cpu的绑定和放弃的具工作。
linux 2.4 调度：
1：policy ：
进程的调度策略：
1）SCHED_FIFO : 实时进程使用的的先进先出策略，进程会一直占用cpu除非其自动放弃cpu。
2）SCHED_RR : 实时进程的轮转策略，当分配个u进程的时间片用完后，进程会插入到原来优先级的队列中。
3）SHED_OTHER：普通进程基于优先级的的时间片轮转调度。
2：priority：进程的静态优先级。
3：nice：进程用来控制优先级的因子。在-20～19间的整数。增加nice的值会使优先级降低。默认值为0。
4：rt_priority：实时进程的优先级。
5：counter：一个计时器，进程目前的剩余时间片。用来动态计算进程的动态优先级。系统将休眠次数多的进程的剩余时间叠会加起来。
6：schedule()的流程：
1）检查是否有软中断请求。有则先执行。
2）如果当前进程的调度策略为RR并且counter==0,将此进程移到运行进程队列的尾部。重新计算counter的值。
3）若当前进程的状态为 TASK_INTERRUPTIBLE 且有信号接收，则将进程状态设置为TASK_RUNNING，若当前进程的状态不是TASK_RUNNING,则将进程从可执行的队列中移出，将其进程描述符的need_resched置为0。
4) 选择出可运行队列中最大权值，保存在变量c中，与之对应的进程描述符保存在变量next中。
5）检查c是否为0,c==0,则队列中的所有进程的时间片都用完了。此时对队列中所有进程的时间片重新计算。重新执行第5步。
6）如果netx==当前进程，则结束调度进程。否则，进行进程切换。
过程：2.4的调度算法，将所有的就绪进程组织成一条可运行队列，不管是单核环境还是smp环境，cpu都只从这条可运行队列中循环遍历直到挑选到下一个要运行的进程。如果所有的进程的时间片都用完，就重新计算所有进程的时间片。
2.4调度的数据结构：
2.4调度的不足：
1）一个明显的缺点就是时间复杂度为O(n)，每次都要遍历队列，效率低！。虽然说O(n)的复杂度看起来不是很糟糕，而且系统能容纳进程数量也不一定会很大，但复杂度为O(n)还是很难忍受的。
2）由于在smp环境下多个cpu还是使用同一条运行队列，所以进程在多个cpu间切换会使cpu的缓存效率降低，降低系统的性能。
3）多个cpu共享一条运行队列，使得每个cpu在对队列操作的时候需要对运行队列进行加锁，这时如果其他空闲cpu要访问运行队列，则只能等待了。由2、3两点可以看出2.4的调度算法对smp环境的伸缩性不高！不能很好地支持smp环境。
4）不支持内核抢占，内核不能及时响应实时任务，无法满足实时系统的要求（即使linux不是一个硬实时，但同样无法满足软实时性的要求）。
5）进程的剩余时间是除了nice值外对动态优先级影响最大的因素，并且系统将休眠次数多的进程的剩余时间叠加起来，从而得出更大的动态优先级。这体现了系统更倾向优先执行I/O型进程。内核就是通过这种方式来提高交互进程的优先级，使其优先执行。但休眠多的进程就代表是交互型的进程吗？并不是的，这只能说明它是I/O型进程。I/O型进程需要进行I/O交互，如读写磁盘时进程会经常处于休眠的状态。如果把这种进程当成是交互进程，反而会影响其他真正的交互进程。
6）简单的负载平衡。那个cpu空闲就把就绪的进程调度到这个cpu上去执行。或者某个cpu的进程的优先级比某个进程低，就调度到那个cpu上去执行。这样简单的负载平衡缺点不言而喻。进程迁移比较频繁，而且出现2、3的情况。这样的负载平衡弊大于利！
linux 2.6 O(1)调度：
1：policy：调度策略跟2.4的一样。
2：rt_priority：实时进程的优先级。在0～99之间。MAX_RT_PRIO为100。不参与优先级的计算。
3：static_prio：非实时进程的静态优先级，由nice值转换而来，-20
2：优先级数组代码如图：
1）nr_active：数组内可运行的进程
2）DECLARE_BITMP(…)：优先级位图的宏。找出优先级最高的且有就绪进程的队列。
3）list_head queue：使用通用链表，优先级队列。
linux 2.6 O(1)调度的数据结构（active or expired）：
每个cpu维护一个自己的运行队列，每个运行队列有分别维护自己的active队列与expried队列。当进程的时间片用完后就会被放入expired队列中。当active队列中所有进程的时间片都用完，进程执行完毕后，交换active队列和expried。这样expried队列就成为了active队列。这样做只需要指针的交换而已。当调度程序要找出下一个要运行的进程时，只需要根据上面提过的位图宏来找出优先级最高的且有就绪进程的队列。这样的数据组织下，2.6的调度程序的时间复杂度由原来2.4的O(n)提高到O(1)。而其对smp环境具有较好的伸缩性。
数据结构的组织如下：
linux 2.6 O(1) 调度的进程优先级：
2.6调度有140个优先级级别，由0～139, 0～99 为实时优先级，而100～139为非实时优先级。上面的图有说。
特点：
1）动态优先级是在静态优先级的基础上结合进程的运行状态和进程的交互性来计算。所以真正参与调度的是进程的动态优先级。而进程的交互性是通过进程的睡眠时间来判断的（这点从根本上来说还是和2.4思想的一样）。所以动态优先级是通过静态优先级和进程睡眠时间来计算的。这里要注意的是，动态优先级是非实时进程插入优先级队列的依据。但实时进程是根据rt_prioirty来插入队列的，实时进程的实时优先级由进程被创建到进程结束都是不会改变的。但其执行的时间片是根据静态优先级来计算的。
2）进程优先级越高，，它每次执行的时间片就越长。
3）使用TASK_INTERACTIVE()宏来判断进程是否为交互进程，该宏是基于nice来判断的，nice值越高，优先级越低，这样交互性越低。
可是我知道结果是惨淡的，但还是心存希望！
