1.处理机调度的基本概念

1）高级调度：

又称作业调度或长程调度(Long-Term Scheduling),接纳调度(Admission Scheduling)

作业调度决定的细节

接纳多少作业——取决于多道程序度。应根据系统的规模和运行速度等情况综合考虑。

接纳哪些作业——取决于采用的调度算法。如先来先服务，短作业优先等

系统运行并不一定存在高级调度

批处理系统：作业进入系统后先驻留外存，故需要有作业调度。

分时系统：为及时响应，作业由终端直接送入内存，故不需作业调度。

实时系统中，通常也不需作业调度。

2）低级调度：

也称为进程调度、微观调度或短程调度（Short-Term Scheduling）。决定内存就绪队列中的哪个进程获得处理机，进行分配工作。是最基本的一种调度，在三种基本OS中都有。

（1）进程调度方式

非抢占方式（Non-preemptive Mode）

一旦处理机分配给某进程，该进程一直执行。决不允许其他进程抢占已分配运行进程的处理机。

抢占方式（Preemptive Mode）

允许调度程序根据某种原则，暂停某个正在执行的进程，将处理机重新分配给另一进程。

(2)进程调度方式比较

（3）中级调度

又称交换调度或中程调度（Medium-Term Scheduling）

引入目的：提高内存利用率和系统吞吐量。根据条件将一些进程调出或再调入内存。

（4）调度队列模型

仅有进程调度的调度队列模型： 分时系统

具有高级和低级调度的调度队列模型：批处理系统中，还需要作业调度

同时具有三级调度的调度队列模型

（5）选择调度方式和调度算法的若干准则

① 面向用户的准则：

周转时间短、响应时间快、均衡性、截止时间的保证、优先权准则

② 面向系统的准则：

系统吞吐量高、处理机利用率好(主要针对大中型主机)、各类资源的平衡利用(主要针对大中型主机)

2.常用调度算法

1）先来先服务调度算法FCFS

一种最简单的调度算法，按先后顺序进行调度。既可用于作业调度，也可用于进程调度。

2）短作业（进程）优先调度算法SJF/SPF（抢占式和非抢占式）

SJF/SPF的不足：

①. 对短作业有利，但同时造成了对长作业的不利。

②.由于作业（进程）的长短含主观因素，不一定能真正做到短作业优先。

 ③.未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）的及时处理。

3）高优先权优先调度算法HPF （抢占式和非抢占式）

照顾紧迫性作业，使其获得优先处理而引入调度算法。常用于批处理系统中的作业调度算法，以及多种操作系统中的进程调度算法

（1）优先权的类型

静态优先权：创建进程时确定，整个运行期间保持不变。一般利用某一范围的一个整数来表示，又称为优先数。

动态优先权：创建进程时赋予的优先权可随进程的推进或随其等待时间的增加而改变。

（2）进程优先权的确定

进程类型、进程对资源的需求、用户需求

4）高响应比优先调度算法HRRN

HRRN为每个作业引入动态优先权，使作业的优先级随着等待时间的增加而以速率a提高：

  优先权 =（等待时间+要求服务时间)/要求服务时间= 响应时间 / 要求服务时间

（1）同时到达的作业优先权相同。

（2）当执行时间相同的作业，优先权的高低决定于其等待时间的长短，也就是先来先服务。

5）基于时间片的轮转调度算法RR�

分时系统新需求：及时响应用户的请求；采用基于时间片的轮转式进程调度算法。

（1）时间片轮转算法

将系统中所有的就绪进程按照FCFS原则，排成一个队列。

每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。

在一个时间片结束时，发生时钟中断。

调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前就绪的队首进程。

（2）多级反馈队列算法FB

设置多个就绪队列，各队列有不同的优先级,优先级从第一个队列依次降低。

 赋予各队列进程执行时间片大小不同, 优先权越高，时间片越短。

6）几种常用调度算法的比较

3.实时调度

1）实现实时调度的基本条件

提供必要的信息

系统处理能力足够强

采用抢占式调度机制

具有快速切换机制

2）实时调度算法的分类

非抢占调度算法

抢占式调度算法

3）常用的几种实时调度算法

（1）最早截止时间优先EDF

根据任务的开始截止时间来确定任务的优先级。截止时间越早，其优先级越高。

（2）最低松弛度优先LLF�

根据任务紧急（或松弛）的程度，来确定任务的优先级。任务的紧急程度越高（松弛度值越小），优先级就越高。

松弛度= 截止完成时间 – 还需执行时间 - 当前时间

可理解为当前时刻到开始截止时刻间的差距，随着时间的推进，这个差值逐渐变小，任务越来越紧迫。

4.产生死锁的原因和必要条件

死锁（Deadlock）：指多个进程在运行过程中，因争夺资源而造成的一种僵局。当进程处于这种状态时，若无外力作用，它们都将无法再向前推进。

死锁（Deadlock）: 指进程之间无休止地互相等待!

饥饿（Starvation）:指一个进程无休止地等待！

1）竞争资源引起进程死锁

可把系统中的资源分为两类：

可剥夺和非剥夺性资源

永久性资源和临时性资源

2）进程推进顺序不当引起死锁

3） 产生死锁的必要条件

互斥条件：

进程对所分配到的资源进行排他性使用

请求和保持条件：

进程已经保持了至少一个资源，又提出新的资源请求，而新请求资源被其他进程占有只能造成自身进程阻塞，但对自己已获得的其他资源保持不放，必然影响其他进程。

不剥夺条件：

进程已获得的资源未使用完之前不能被剥夺，只能在使用完时由自己释放。

环路等待条件

4）处理死锁的基本方法

事先预防：

（1）预防死锁：

（2）避免死锁：

事后处理：

（3）检测死锁

（4）解除死锁

5.预防死锁的方法

1）预防死锁

（1）摒弃“请求和保持”条件

（2）摒弃“不剥夺”条件

（3）摒弃“环路等待”条件

6.死锁的检测与解除

当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和解除死锁的手段，为此系统必须：

保存有关资源的请求和分配信息；

提供一种算法，以利用这些信息来检测系统是否已进入死锁状态。

1）死锁的检测

检测时机：

当进程等待时检测死锁

定时检测

系统资源利用率下降时检测死锁

2）死锁定理

利用资源分配图简化法来检测死锁

3）死锁检测算法：

* 每个进程和资源指定唯一编号

* 设置一张资源分配表

  记录各进程与其占用资源之间的关系

* 设置一张进程等待表

  记录各进程与要申请资源之间的关系

4）死锁的解除

当发现进程死锁时，便应立即把它们从死锁状态中解脱出来。常采用的方法是：

剥夺资源：

从其他进程剥夺足够数量的资源给死锁进程以解除死锁状态。

撤销进程：

最简单的是让全部进程都死掉；温和一点的是按照某种顺序逐个撤销进程，直至有足够的资源可用，使死锁状态消除为止。

5）死锁处理方法比较