1、调度策略和算法

进程调度策略：决定以怎样的方式选择一个新进程运行的这组规则。

其基本要求是高效、公平。常用的进程调度策略如下：

①、优先级高优先调度策略：将处理器分配给就绪进程队列中优先级最高的进程。各进程的优先级通常由进程调度程序根据进程的实际情况动态计算出来。

优先级静态策略是在进程创建初期根据进程类型（是系统还是用户进程、前台还是后台进程）、要求的资源量（处理器占用时间、内存量等）以及运行时间等确定其级别，一旦确定后在整个进程运行期间不再调整。优先级静态策略易于实现但不尽合理，因为可能会造成低优先级的进程等待时间过长。

动态优先级策略是在进程运行过程中不断随进程状态的变化调整其优先级。该算法要求在每个进程的控制块中，动态记录该进程使用和放弃处理器的时间，以便在调度时根据处理器使用时间长短确定其优先级。

比如，某进程等待使用处理器时间较长，可适当调高其优先级，反之，则降低其优先级。这种策略可以获得较好的调度效果，但实现较复杂。

②、时间片轮转调度策略：系统将处理器分配给就绪队列中位于队首的进程，并规定其执行的一段时间（称为时间片）。当该进程用完时间片后，进程调度程序将其送至就绪队列的队尾，并把处理器分配给就绪队列中的下一个位于队首的进程，再执行同样大小的时间片。依次轮转，使就绪队列中的所有进程都可以轮流获得一个时间片的处理器执行时间。这种策略又称为先来先服务策略，较为公平。

③、多重循环轮转调度策略：预设若干个循环轮转时间片长短不同的就绪队列。进程从阻塞状态进入就绪状态时，首先进入时间片最短的队列，获得处理器并运行完短时间片后，再排入下一个较长时间片的队列，以此类推，虽然进程开始时的时间片很短，但下一次轮到后时间会增加若干倍，因此，进入的就绪队列时间片越来越长。这样有利于执行时间较短的进程以较短的时间片完成进程处理，而需时较长的进程可获较长的时间片，以免频繁中断进程影响处理器效率。

2 调度算法

Linux进程：

调度算法根据是普通进程还是实时进程有很大的区别

2.1 普通进度的调度

1、调度程序使用静态优先级（决定了进程的基本时间片）来估价这个进程与其他普通进程之间调度的程度。（普通进程的静态优先级100【最高优先级】到139【最低优先级】）

--静态优先级越高（其值越小），基本时间片就越长；与优先级低的进程相比，通常优先级较高的进程获得更长的CPU时间片。

2、动态优先级是调用程序在选择新进程来运行的时候使用的数。（普通进程除了静态优先级还有动态优先级）

bonus是范围从0~10的值，值小于5表示降低动态优先级以示惩罚，值大于5表示增加动态优先级以示奖赏。bonus与进程的平均睡眠时间(进程在睡眠状态所消耗的平均纳秒数)有关。

平均睡觉时间越大bonus越大。

3、即使具有较高静态优先级的普通进程获得了较大的CPU时间片，也不应该使静态优先级较低的进程无法运行。避免进程饥饿，当一个进程用完它的时间片时，它应该被还没有用完时间片的低优先级进程取代。

为了实现这种机制，调度程序维持两个不相交的可运行进程的集合。

活动进程：这些进程还没有用完它们的时间片，因此运行它们运行。

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

2.2 实时进程调度

1、实时进程都与一个实时优先级相关，实时优先级范围1（最高优先级）~99（最低优先级）；调度程序总是让优先级高的程序运行。实时进程运行过程中，禁止低优先级进程的执行。

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

3、实时进程只有在下面情况才会被另外一个进程取代：

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

   （2）进程执行了阻塞操作并进入睡眠；

   （3）进程停止或被杀死；

  （4）进程通过调用系统调用sched_yield()自愿放弃CPU；

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