2.2 处理机调度

思维导图:http://naotu.baidu.com/file/35e6a671a1ba8ea330fef1fdbbc77691?token=bab169749f3ae744

调度的概念

调度的基本概念

处理机调度就是从就绪队列中，按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程并发地执行。

调度的层次

1. 高级调度（作业调度）：从外存的后备队列选择一个（或者多个）作业，给他们分配内存、输入、输出设备等必要的资源，建立进程，将这些进程送入就绪队列中，让他们获取竞争处理机的权利。
2. 中级调度（内存调度）：将暂时不能运行的进程从内存调至外存，状态变为挂起状态。当这些进程已经具备运行条件且内存空闲，中级调度在将这些进程重新调入内存，并修改状态为就绪状态（目的：为了提高内存利用率和系统吞吐量）
3. 低级调度（进程调度）：从就绪队列选取一个进程，将其状态改为运行状态，分配CPU。（是最基本的，不可或缺的）

调度的时机、切换与过程

现代操作系统中，不能进行进程的调度和切换的情况，应置系统的请求调度标志：

1. 处理中断的过程
2. 进程在操作系统内核程序临界区
3. 其他需要完全屏蔽中断的院子操作过程：如加锁、解锁、中断现场保护、恢复等原子操作。

现代操作系统中，应该进行进程的调度和切换的情况：

1. 当发生引起调度条件，且目前的进程无法进行下去。如果操作系统只在这种情况下进行进程调度，属于非剥夺调度。
2. 中断处理结束或者自陷处理结束后，返回被中断进程的用户态程序执行现场前，若置上请求调度标志，就马上进行进程调度与切换。，属于剥夺方式调度

进程调度方式

1. 非剥夺调度方式（非抢占式）
2. 剥夺调度方式(抢占式)：当进程正在处理器上运行时，系统可根据所规定的原则剥夺分配给此进程的处理器，并将进程移入就绪列队，选择其他进程运行。

调度的基本准则

1. CPU利用率
2. 系统吐吞量：单位时间内CPU完成作业的数量
3. 周转时间：从作业提交到作业完成花的时间
4. 等待时间：从作业提交到处理机开始处理作业花的时间。处理机调度算法只会影响作业在就绪队列中等待时间
5. 响应时间：从用户提交到系统首次产生响应所用的时间。

典型的调度算法

1. 先来先服务调度算法（FCFS）:适用于作业调度和进程调度。属于不可剥夺调度算法。
2. 短作业优先调度算法（SPF）
3. 优先级调度算法：优先级用于描述进程的紧迫程度
4. 高响应比优先调度算法
   • 
5. 时间片轮转调度算法：
   • 时间片的长短取决于：系统的响应时间、就绪队列中的进程数目以及系统的处理能力。
6. 多级反馈队列调度算法：是时间片轮转调度算法和优先级调度算法的综合。

调度算法比较

		先来先服务	短作业优先	优先级调度	高响应比优先	时间片轮转	多级反馈队列
能否是可抢占	否	能	能	能	能	队列内算法不一定
能否是不可抢占	能	能	能	能	否	队列内算法不一定
优点	1. 有利于CPU繁忙型作业；2. 有利于长作业	平均等待时间最少，效率最高	无
缺点	1. 不利于短作业；2.不利于I/O繁忙型作业。	长作业会饥饿，估计时间不易确定无
适用于	无	作业调度和批处理调度
默认决策模式	非抢占	非抢占