Linux进程调度算法之O(1)算法

一.概述

   在一个运行操作系统中的进程数一般都是大于CPU的数目，但是用户看起来好像这些进程是同时在运行的，其原因就是这些进程通过调度算法使每个进程每隔一段时间就放入CPU运行，该时间段非常短，给人的感觉就是这些进程在同时运行。因此需要一些规则来确定调度的时机，即调度策略。

   调度策略有多种，常见的如：分时技术，给每个进程分配时间片，进程运行完时间片后调入另一个进程执行；根据分时技术，给进程确定优先级，优先级高的先运行，有的系统优先级可以动态分配，当某个进程很久没有运行，就动态提高其优先级，给它运行的机会。

二.linux的调度策略

   linux进程的类型可以分为以下的类型：

SCHED_FIFO先进先出的实时进程，该种类型如果没有比它优先级高的实时进程可以运行，该进程就一直占用CPU运行，即使相同相同优先级的实时进程也无法抢占，直到它退出运行。

SCHED_RR时间片轮转的实时进程，对具有该类型的实时进程的分配运行时间片进行运行，当调度运行的时候调度器会把该进程放在该优先级进程链表的末尾。

SCHED_NORMAL普通的分时进程

   linux进程优先级有140个，即从0-139，说明一下，该优先级为进程的静态优先级，还有动态优先级；其中，0-99为实时进程优先级，100-139为普通进程优先级；相同优先级的进程描述符通过链表连接起来；同样，先进先出的实时进程和时间片轮转的实时进程虽然调度策略不同，但是只要优先级相同就连接在同一个链表中，由调度算法进行辨识。

三.普通进程的调度

   进程的静态优先级较高其占用的运行时间片就较长，但是不应使静态优先级较低的进程无法运行。因此，为了比秒进程饥饿，当一个进程用完它的时间片后，它应该被还没有用完时间片得低优先级进程取代。调度程序维护两个进程集合，活动进程集合和过期进程集合。

   活动进程集合:这些进程还没有用完它们的时间片，因此允许它们运行；

   过期进程集合：这些可运行进程已经用完了它们的时间片，并因此被禁止运行，直到所有活动进程都过期。

在实际的实现中，调度程序试图提升交互式进程的性能。用完时间片的活动批处理进程总是变成过期进程。用完时间片得交互式进程通常仍然是活动进程：调度程序重填其时间片并把它留在活动进程集合中。但是，如果最老的过期进程已经等待了很长时间，或者过期进程比交互式进程的静态优先级高，调度程序就把用完时间片得交互式进程移到过期进程集合中。结果，活动进程集合最终会变为空，过期进程将有机会运行。

   进程运行的基本时间片由静态优先级决定，其算法公式如下：

   基本时间片（单位：毫秒） =（140 -静态优先级）X 20  若静态优先级< 120;

   基本时间片（单位：毫秒） =（140 -静态优先级）X 5   若静态优先级>=120;

进程运行调度的时候，其选择进程则是根据进程动态优先级来确定的，进程的动态优先级的确定公式如下：

动态优先级 = max(100, min(静态优先级– bonus + 5, 139))

Bonus是范围从0----10的值，值小于5表示降低动态优先级，值大于5表示增加动态优先级，该值依赖于进程过去的情况，说得更准确一些，是与进程的平均睡眠时间相关。

四．实时进程的调度

每个实时进程都对应一个实时优先级，范围从优先级0-99，共100个优先级。实时进程调度时，总是调度优先级高的进程运行，禁止低优先级进程的执行。普通进程有活动进程集合和过期进程集合的概念，对于实时进程来说则没有这样的概念，但是代码中还是有这样的概念，当一个实时进程调度的时候，直接将该进程描述符放在这个时候活动进程集合中该进程实时优先级对应的队列中，但是没有活动集合和过期集合相互切换的概念。只要你运行了，就把你放在活动集合里。

如果几个可运行的实时进程具有相同的优先级，那么调度程序选择第一个出现在与本地CPU的运行队列相应链表中的进程。

实时进程在如下的情况下被另外一个进程取代：

 1.进程被另外一个具有更高实时优先级的实时进程抢占；

2.进程执行了阻塞操作并进入睡眠;

3.进程停止或者被杀死;

4.进程通过调用系统调用sched_yield资源放弃CPU;

5.进程是基于时间片轮转的实时进程（SCHED_RR）,而且用完了它的时间片。

五．某些代码实例

如果某个实时进程激活，只需将它的进程放入active集合，举例如下:

    staticint try_to_wake_up(task_t * p, unsigned int state, int sync)

             |

----- static voidactivate_task(task_t *p, runqueue_t *rq, int local)

                    |

-----   static inline void__activate_task(task_t *p, runqueue_t *rq)

                              |

-----      static voidenqueue_task(struct task_struct *p, prio_array_t *array)

当然非实时进程启动的时候也可以使用try_to_wake_up

 

创建一个新的进程，并且执行：

void fastcall wake_up_new_task(task_t * p, unsigned longclone_flags)，该进程被加入active中，函数在fork()中被调用。