Question

关于Linux的调度！！！

1．编写并调试一个模拟的进程调度程序，采用“最高优先数优先”调度算法对五个进程进行调度。
“最高优先数优先”调度算法的基本思想是把CPU分配给就绪队列中优先数最高的进程。
静态优先数是在创建进程时确定的，并在整个进程运行期间不再改变。
动态优先数是指进程的优先数在创建进程时可以给定一个初始值，并且可以按一定原则修改优先数。例如
：在进程获得一次CPU后就将其优先数减少1。或者，进程等待的时间超过某一时限时增加其优先数的值，等等

Answer 1

进程调度策略就是调度系统种哪一个进程来CPU运行。这种调度分2层考虑。

第一层，进程状态这个是最优先考虑的，也就是说优先级最高的。在linux中只有就绪态的进程才有可能会被调度选中然后占有CPU，其它状态的进程不可能占有的到CPU。下面是linux中进程的状态
TASK_RUNNING:就绪状态，得到CPU就可以运行。
TASK_INTERRUPTIBLE:浅度睡眠，资源到位或者受到信号就会变成就绪态。
TASK_UNINTERRUPTIBLE:深度睡眠，资源到位就会进入就绪态，不响应信号。
TASK_ZOMBIE：僵死态，进程exit后。
TASK_STOPPED：暂停态，收到SIG_CONT信号进入就绪态。

第二层，其实真正在操作系统宴唯中的实现，就是所有就绪态进程链接成一个队列，进程调度时候只会考虑这个队列中的进程，对其它的进程不考虑，这就实现了第一层中的要求。接下来就是就绪队列内部各个进程的竞争了。

Linux采用3种不同的调度政策，SCHED_FIFO（下面简写成FIFO，先来先服务），SCHED_RR（简写成RR，时间片轮流），SCHED_OTHER（下面简写成OTHER）。这里大家就能看出一个问题，采用同等调度政策的进程之间自然有可比性，Linux3种调度政策并存，那么不同调度政策间的进程如何比较呢？可以说他们之间根本就没有可比性。其实在调度时候，调度只看一个指标，那就是各个进程所具有的权值，权值最大的且在可执行队列中排在最前面的就会被调度执行。而权值的计算才会设计到各方面因素，其中调度政策可以说在计算权值中，份量是最重的。

为什么Linux要这么干呢？这是由于事务的多样性决定庆祥的，进程有实时性进程和非实时性的进程2种，FIFO和RR是用来支持实时性进程的调度，我们看一下这3种政策下权值的计算公式就明白了：
FIFO和RR计算公式，权值=1000+进程真正的运行时间
OTHER计算公式，当时间片为0时，权值=0.当时间片不为0时候，权值=剩余时间片+20-nice,同时如果是内核线程有+1的小加分，这是因为内核线程无需用户空间的切换，所以给它加了一分，奖励他在进程切换时候开销小的功劳。时间片好理解，那么nice这个值，用过linux系统的人都知道，这是一个从unix下继承过来的概念，表示谦让度，是一个从20～-19的数，可以通过nice和renice指令来设置。从代码中也能看到值越小就越不会谦让他人。

从这里我们看出FIFO和RR至少有1000的基数，所以在有FIFO和RR调度政策进程存在时，OTHER进程是没有机会被调度的到的。从权值计算公式同时也能看出，FIFO先来先服务的调度政策满足了，但RR这个时间片轮流的调度如果按照这种权值计算是不能满足时间片轮流这一概念的。这里只是权值的计算，在调度时候对RR政策的进程特殊处理。

以上都是权值计算，下面看看真正的调度过程，首先是对RR政策进程的特殊处理，如果当前进程采用的RR政策，那么看他的时间片是否用完，用完了就踢到就绪队列尾部，同时恢复他的时间片。然后是便利整个就绪队列，找到第一个权值最大的进程来运行。

整体调度效果就是：如果有FIFO和RR政策的进程，就优先调度他们2个，他们之间看已执行时间长短决定胜负，而2种政策内部则遵守各自调度政策。而OTHER只有在前面2种不存在于就绪队列时候才有可能执行，他们实际也是轮流执行，但他们之间是靠剩余时间和NICE值来决定胜负。同时就绪队列中排在最前面的最优先考虑在同样权值晌差培情况下。

Answer 2

Linux2.6 版本的 Linux 内核使用了新的调度器算法，它是由 Ingo Molnar开发的 O（1）调度器算法。它在高负载的情况下极其出色，并且对处理器调度有很好的扩展。
Linux2.4 版本的标准调度器中，使用时间片重算的算法。这种算法要求在所有的进程都用尽时间片以后，重新计算下一次运行的时间片。这样每次任务调度的花销不确定，可能因为计算比较复杂，产生较大调度延迟。特别是多处理器系统，可能由于调度的延迟，导致大部分处理器处于空闲
状态，影响系统性能。
新的调度器采用 O（1）的调度算法，通过优先级数组的数据结构来实现。优先级数组可以使每个优先级都有相应的任务队列，还有一个优先级位图，每个优先级对应位图中一位，通过位图可快速执行最高优先镇尺闭级任务。因优先级个数是固定的，所以查找的时间也固定，不受运行任务数的影响。
新的调度器为每个处御裂理器维护 2 个优先级数组：有效数组和过期数组。有效数组内任务队列的进程都还有可以运行的时间片；过期数组内任务队列的进程都没有时间片可以执行。当一个进程的时间片用光时，就把它从有效数组移到过期数组，并且时间片也已经重新计算好了。当需要重新调度这些任务的时候，只要在有效数组和过期数组之间切换就困雹好了。这种交换是O（1）算法的核心。
关于该算法的更多内容，google 一下！
请参考