1.CPU调度程序

   每当CPU空闲时，OS必须从就绪队列选择一个进程来执行。进程选择由短期调度程序或CPU调度程序执行。调度程序从内存中选择一个能执行的进程，并为之分配CPU。

2.抢占：可以选择

             （1）当一个进程从运行状态切换到就绪状态；（eg：当出现中断时）

             （2）当一个进程从等待状态切换到就绪状态；（eg：I/O完成）

   非抢占/协作：没有选择，只有调度，一个新进程（如果就绪队列中已有一个进程存在）必须被选择执行。

（1）当一个进程从运行状态切换到等待状态（eg：I/O请求，或调用wait等待一个子进程的终止）；

（2）当一个进程终止；

3.分派程序：是一个模块，用来将CPU的控制交给由短期调度程序选择的进程。

   功能：切换上下文；  切换到用户模式；   跳转到用户程序的合适位置，以重新启动程序；

   分派延迟：分派程序停止一个进程而启动另外一个所花时间。

4.调度准则：

   （1）CPU使用率；

   （2）吞吐量：一个时间单元内所完成进程的数量；

   （3）周转时间：从进程提交到进程完成的时间段。为所有时间段之和，including 等待进入内存，在就绪队列中等待，在CPU上执行和I/O执行。

   （4）等待时间：在就绪队列中等待所花费时间。CPU调度算法只影响进程在就绪队列中等待所花的时间。

   （5）响应时间：从提交请求到产生第一响应的时间。

5.先到先服务（FCFS）调度（非抢占）

   先请求CPU的进程先分配给CPU。用FIFO队列实现。

补充：对于第一个Gantt图：周转时间：（24+27+30）/3 = 27                 响应时间：（0+24+27）/3 = 17

6.最短作业优先调度（SJF）（非抢占）

   最短下一个CPU区间的算法，当CPU空闲时，它会赋给具有最短CPU区间的进程。如果两个进程具有同样长度，则使用FCFS。

7.最短剩余时间优先调度（抢占式的SJF调度）

   当一个新进程到达就绪队列而以前的进程还在执行时，需要选择。与当前运行的进程相比，新进程可能会有一个更短的CPU区间。抢占SJF算法可抢占当前运行的进程。

Ps：响应时间：（0+0+15+2）/4=17           周转时间：（17+4+24+7）/4 = 13

8.优先级调度：（既可以抢占，也可以非抢占，实际应用中为抢占）

   每一个进程都有一个优先级与其关联，具有最高优先级的进程会分配到CPU，具有相同优先级的进程按照FCFS。

  for windows: 数字越大，优先级越高               for Linux：与windows相反

问题：无穷阻塞/饥饿：使某个低优先级进程无穷等待CPU

            解决方法： 老化：逐渐增加在系统中等待很长时间的进程的优先级。

9.轮转法调度（增加了抢占以切换进程）（RR）

   定义一个较小时间单元，称为时间片。通常为10-100ms

若时间片很小，则RR算法称为处理器共享。   根据经验，80%的CPU区间应小于时间片。

10.多级队列调度：

    适用于进程可容易的分为不同组的情况，例如一个常用的划分方法是前台（交互）和后台（批处理）进程。

    将就绪队列分成多个独立队列（见图）。根据进程属性，如内存大小，优先级，类型，一个进程被永久的分配到一个队列。每个队列有自己的调度算法。例如前台队列使用RR，后台使用FCFS。

另外，队列之间必须有调度，通常采用固定优先级抢占调度。即每个队列与更底层队列相比有绝对的优先级。另一种可能是在队列之间划分时间片。

11.多级反馈队列调度：

    允许进程在队列之间移动，主要思想为根据不同CPU区间的特点以区分进程。如果进程使用更多CPU时间，则它会被转移到更低优先级队列。

注：进入就绪队列的进程被放入队列0里面，其中每个进程都有8ms的时间片，若进程不能在这一时间内完成，则被移动到队列1的尾部。

       如果队列0为空，队列1的头部进程会得到一个16ms的时间片。如果它不能完成，那么将被抢占，并被放到队列2中。只有当队列0和

       队列1为空时，队列2内的进程才可根据FCFS运行。

12.多处理器调度：

    12.1 多处理器调度的方法

     （1）非对称处理：只有一个处理器（主服务器）访问系统数据结构，处理所有的调度决定，I/O处理以及其他系统活动，其他处理器只执行用户代码。

     （2）对称多处理（SMP）：每个处理器自我调度。所有进程可能处于一个共同的就绪队列中，或每个处理器都有自己的私有就绪进程队列。

   12.2 处理器亲和性：绝大多数SMP系统试图避免将进程从一个处理器移动至另一个处理器，而是努力使一个进程在同一个处理器上运行。

          软亲和性：OS设法将一个进程保持在同一个处理器，但不能做任何保证。

          硬亲和性：允许进程指定它不允许移动至其他处理器。

   12.3 负载均衡

        设法将工作负载平均地分配到SMP系统中的所有处理器上。通常只是对拥有自己私有的可执行进程的处理器而言是必要的。在具有共同队列的系统中，通常不需要负载均衡（一旦处理器空闲，它立刻从共同队列中取走一个可执行进程）。在绝大多数SMP当代OS中，每个处理器都具有一个可执行进程的私有队列。

       两种方法：push migration:一个特定任务周期性检查每个处理器上的负载，若发现不平衡，即通过将进程从超载处理器移动到（or推送）空闲或不太忙的处理器。

                        pull（拉） migration：当空闲处理器从一个忙的处理器上推送（pull）一个等待任务。

   12.4 对称多线程（SMT）/超线程技术

      在同一个物理处理器上生成多个逻辑处理器，向操作系统呈现一个多逻辑处理器的视图。每个逻辑处理器都有自己的架构状态。SMT是硬件提供的。

13.线程调度

    13.1竞争范围

     进程竞争范围（PCS):线程库调度用户级线程到一个有效的LWP上运行。

     系统竞争范围（SCS):内核决定调度哪个内核线程到CPU上。