1.CPU调度：

任务是控制、协调进程对CPU的竞争，即按一定的调度算法从就绪队列中选择一个进程，把CPU的使用权交给被选中的进程。如果没有就绪进程，系统会安排一个系统空闲进程或idle进程

2.CPU调度要解决三个问题：

（1）按着什么原则选择下一个要执行的进程

（2）何时进行选择

（3）如何让被选中的进程上CPU运行 调度过程（上下文切换）

3.CPU调度的时机：

事件发生->当前正在运行的进程暂停->硬件机制响应后->进入OS，处理相应的事件->结束处理后：某些进程的状态会发生变化，也可能又创建了一些新的进程->就绪队列改变了->需要进程调度根据预设的调度算法从就绪队列中选一个进程

即内核对中断、异常、系统调用处理后返回用户态时

（1）进程正常终止 或 某种错误终止

（2）新进程创建 或 一个等待进程变为就绪

（3）运行态->阻塞态

（4）运行态->就绪态

4.进程切换：一个进程让出CPU，另一个进程使用

两部分工作：

（1）切换全局页目录以加载一个新的地址空间

（2）切换内核栈和硬件上下文，其中硬件上下文包括了内核执行新进程需要的全部信息，如CPU相关寄存器

切换过程包括对原来运行进程各种状态的保存和对新进程的各种状态恢复

5.上写文切换的具体步骤：

A让出给B

（1）保存A的上下文环境（程序计数器，程序状态字，其他寄存器）

（2）用新状态和其他相关信息更新进程A的ＰＣＢ

（3）把进程A移至合适的队列（就绪、阻塞）

（4）将进程B的状态设置为运行态

（5）从进程B的PCB中恢复上下文

6.上下文切换开销

（1）直接开销：内核完成切换所用时间（保存、恢复寄存器；切换地址空间）

（2）间接开销：高速缓存，缓冲区缓存、TLB（translation lookup buffer）失效

7.衡量调度算法的指标：

吞吐量：每单位时间完成的进程数目

周转时间：提出请求到运行完成的时间

响应时间：提出请求到第一次响应时间

CPU利用率：CPU做有效工作的时间比例

等待时间：每个进程在就绪队列中等待的时间

8.进程的优先级：

优先级：表现出进程的重要和紧迫性

优先数：表现优先级，unix优先数小的优先级高

静态优先级：进程创建时制定，运行中不改变

动态优先级：运行过程中会变 如等待时间长的应该改优先级

9.抢占CPU：

可抢占式Preemptive（可剥夺）：

当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的CPU，提供给具有更高优先级的进程使用

不可抢占：

某一进程被调度运行后，除非由于自身原因不能运行，否则一直运行下去

10.时间片：

一个时间段，分配给调度上CPU的进程，确定了允许改进程运行的时间长度。

考虑因素：进程切换的开销；对响应时间的要求；就绪进程的个数；CPU能力；进程的行为

（以后会讲时间片轮转算法）

11批处理系统中的调度算法：

（1）先来先服务(FCFS)：

按照进程就绪的小猴顺序使用CPU；非抢占

优点：公平，实现简单

缺点：长进程后面的短进程等待时间长，用户体验不好

（2）短作业优先SJF

具有最短完成时间的进程优先执行

非抢占

优点：

最短平均周转时间（在所有进程同时可运行）

缺点：

源源不断的短任务到来，可能使长的任务得不到运行

（3）最短剩余时间优先 SRTN

SJF+抢占

（4）最高相应比优先（HRRN）

调度时，首先计算每个进程的响应比R；选择R最高的进程执行

R=周转时间/处理时间=（处理时间+等待时间）/处理时间=1+等待时间/处理时间

12.交互式系统中采用的调度算法：

（1）时间片轮转调度算法：RR

目标：为短任务改善平均响应时间

解决问题的思路：

周期性切换；每个进程分配一个时间片；时钟中断->轮转

如何选择合适的时间片：50-60ms左右

优缺点：

公平；有利于交互计算，响应时间长；由于进程切换，时间片轮转要花费较高的开销

CPU开销在切换上占1%

对于大小相同的进程：不好

（2）虚拟轮转法：virtual RR

它增加了一个I/O队列，当一个进程被I/O阻塞后它加入到I/O队列，在就绪后它I/O队列有高于就绪队列的优先级，该进程后续的执行时间与已执行时间的和不会超过时间片。 

（3）最高优先级调度算法：

选择优先级最高的进程投入运行

通常：系统进程优先级高于用户进程；前台进程优先级高于后台进程；操作系统更偏好I/O型进程

优先级可以是静态不变的，也可以动态调整：优先数可以决定优先级

就绪队列可以按着优先级组织

实现简单：不公平

13.优先级反转问题：（基于优先级的抢占式）

一个低优先级进程持有一个高优先级进程所需要的资源，是的高优先级进程等待低优先级进程运行

影响：系统错误；高优先级进程停滞不前，导致系统性能降低

解决方案：

（1）设置优先级上限

（2）优先级继承

（3）使用中断禁止

14.多级反馈队列调度算法：

unix 的一个分支BSD5.3采用的一个调度算法

基本思想：（非抢占）

设置多个就绪队列，第一队列优先级最高

系统给不同就绪队列中的进程分配长度不同的时间片，第一队列时间片最小；随着队列优先级级别降低，时间片变大

当第一级队列为空，在第二级队列调度……

各级队列按着时间片轮转方式进行调度

当一个新创建进程就绪后，进入第一季队列

进程用完时间片而放弃CPU，进入下一级就绪队列

由于阻塞而放弃CPU的进程进入相应的等待队列，一旦等待的时间发生，该进程回到原来一级就绪队列

若允许抢占：

当有一个优先级更高的进程就绪时，可以抢占CPU被抢占的进程回到原来一级的就绪队列队尾、

15.各种比较

16.多处理器调度算法设计：

不仅决定选择呢一个进程执行，还需要考虑在哪个CPU上执行

要考虑进程在多个CPU之间迁移的开销：高速缓存失效，TLB失效；尽可能使进程总是在同一个CPU上执行

考虑负载均衡

17.Linux操作系统采用的调度算法

linux2.4简单的基于优先级调度

linux2.6O(1)调度器 SD  、RSDL调度器补丁

linux2.7 CFS调度器

18.windows线程调度

调度单位是线程

采用基于动态优先级、抢占式调度，结合时间配额的调整

引发线程调度条件（之前的4个）+一个线程优先级改变+一个线程改变了他的亲和处理机集合

32个优先级，三类：

16-31实时优先级：不改变其优先级

1-15可变优先级：基本优先级，当前优先级

0 系统线程（零页线程：用于对系统中的空闲物理页面清零）

19.线程的时间配额：

不是时间长度值，而是一个称谓配额单位

一个线程用完自己的时间配额，如果没有其他相同的优先级的线程，windows将重新给该线程分配一个新的时间配额

20.windows线程调度策略：

（1）主动切换：运行态让出CPU变为阻塞态

（2）抢占：阻塞态的唤醒，抢占CPU

当线程被抢占时，被放回相应优先级就绪队列的队首：

处于实时优先级的线程再被抢占时，时间配额被重置为一个完整的时间配额

处于可变优先级的线程在被抢占时，时间配额不变，重新得到CPU后将运行剩余的时间配额

（3）时间配额用完：

优先级没有降低：

如果队列中没有其他就绪线程，选择下一个线程执行，该线程回到原来的就绪队列末尾；

如果队列中没有其他就绪线程，系统给线程A分配一个新的时间配额，让他继续运行。

优先级降低：windows将选择一个更高优先级的线程

21.Windows提升线程优先级：（1-15）

I/O操作完成

信号量或事件等待结束

前台进程中的线程完成一个等待操作

由于窗***动而唤醒窗口线程

线程处于就绪态超过一定时间还没有运行