分为六大部分：

一．处理机调度相关基本概念

二．常用调度算法

三．实时调度

四．产生死锁的原因和必要条件

五．预防死锁的方法

六．死锁的检测与解除

一、处理机调度的基本概念

处理机调度：多道程序环境下，动态的把处理机分配给就绪队列中的一个进程使之执行。

提高处理机的利用率、改善系统性能，很大程度上取决于处理机调度的性能。

处理机调度便成为OS设计的中心问题之一。分配的任务由处理机调度程序完成。

1、高级调度（High Scheduling）

又称作业调度或长程调度(Long-Term Scheduling),接纳调度(Admission Scheduling)。主要在早期批处理阶段，处理在外存上的作业。

决定外存后备队列中的哪些作业调入内存;

为它们创建进程、分配必要的资源;

将新创建的进程排在就绪队列上，准备执行。

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

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

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

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

2、低级调度（Low Level Scheduling）

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

 进程调度方式

1）非抢占方式（Non-preemptive Mode）

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

2）抢占方式（Preemptive Mode）

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

3、中级调度（Intermediate-Level Scheduling）

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

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

三种调度的频率和复杂度

进程调度：运行频率最高，算法不能太复杂，以免占用太多的CPU时间。分时系统通常10~100ms便进行一次。

作业调度：一个作业运行完毕退出系统时即触发重新调度一个新作业入内存，周期较长，大约几分钟一次。因而也允许作业调度算法花费较多的时间。

中级调度：运行频率基本上介于上述两种调度之间。

4、调度队列模型

 不论高级、中级或者低级调度，都涉及到进程队列，由此形成了三类调度队列模型。从这三种方式中体验调度的过程。

①仅有进程调度的调度队列模型

常见情况：分时系统。

通常仅设置进程调度，用户键入的命令和数据，都直接送入内存。

调度对象：

处于就绪状态的进程。

组织形式：

栈、树或一个无序链表

用何种形式取决于OS类型和采用的调度算法。如：分时系统中把就绪进程组织成FIFO队列形式：按时间片轮转方式运行。

②具有高级和低级调度的调度队列模型

批处理系统中，还需要作业调度

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

引入中级调度后，进程的状态变化：

就绪状态：分为内存就绪和外存就绪。

阻塞状态：分为内存阻塞和外存阻塞。

  中级调度使进程在上述状态间变化，并使数据在内外存间互换。

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

1)面向用户的准则

周转时间短；

响应时间快：针对分时系统。用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间

均衡性：系统响应时间的快慢与用户所请求的复杂性相适应。

截止时间的保证：针对实时系统的性能指标。开始截止时间和完成截止时间。任务必须按规定的时间开始或完成，调度方式和算法必须能保证该要求。

优先权准则：三大基本OS在调度算法的选择时都可遵循。可以使关键任务达到更好的指标。

2)面向系统的准则

系统吞吐量高：批处理系统的重要指标。

单位时间内所完成的作业数，跟作业本身（与作业平均长度密切相关）和调度算法都有关系；处理机利用率好(主要针对大中型主机)。各类资源的平衡利用(主要针对大中型主机)。

二：常用调度算法

调度的实质就是一种资源分配。不同的系统和系统目标，通常采用不同的调度算法——适合自己的才是最好的。

如批处理系统为照顾为数众多的短作业，应采用短作业优先的调度算法；

如分时系统为保证系统具有合理的响应时间，应采用轮转法进行调度。

目前存在的多种调度算法中，有的算法适用于作业调度，有的算法适用于进程调度；但有些算法作业调度和进程调度都可以采用。

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

(First Come First Service)

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

按照作业提交，或进程变为就绪状态的先后次序分派CPU；

新作业只有当当前作业或进程执行完或阻塞才获得CPU运行

被唤醒的作业或进程不立即恢复执行，通常等到当前作业或进程出让CPU。所以，默认即是非抢占方式。

2.短作业（进程）优先调度算法SJF/SPF

(Shortest Job First) OR (Shortest Process First)

优点：通过上表可见采用SJF/SPF算法，平均周转时间、平均带权周转时间都有明显改善。SJF/SPF调度算法能有效的降低作业的平均等待时间，提高系统吞吐量。

方式：分抢占和非抢占两种方式，上例为简单的非抢占式。

3.高优先权优先调度算法HPF（Highest Priority First）

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

1) 分两种方式：

非抢占式优先权算法；抢占式优先权算法关键点：新作业产生时

2)优先权的类型

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

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

3）高响应比优先调度算法HRRN（Highest Response Raito Next）

短作业优先算法是一种比较好的算法（相当于根据作业长度设定的静态优先权算法），适用于短作业较多的批处理系统中，其主要不足是长作业的运行得不到保证。

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

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

3.基于时间片的轮转调度算法RR (Round Robin)

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

早期分时系统采用的是简单的时间片轮转法，进入90年代后广泛采用多级反馈队列调度算法。

（1）时间片轮转算法

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

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

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

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

（2）多级反馈队列算法FB(Multiple-level Feed Back Queue)

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

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

3）当一个新进程进入内存，引发的调度过程

 三、实时调度

什么是实时系统？

1.指系统能够在限定的响应时间内提供所需水平的服务。

2.指计算的正确性不仅取决于程序的逻辑正确性，也取决于结果产生的时间，如果系统的时间约束条件得不到满足，将会发生系统出错。

  实时任务：具有明确时间约束的计算任务，有软/硬，随机/周期性之分。

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

1）提供必要的信息

   为了实现实时调度，系统应向调度程序提供有关任务的信息；

2）系统处理能力足够强

3）采用抢占式调度机制

4）具有快速切换机制

2.实时调度算法的分类

1）非抢占调度算法

1.非抢占式轮转调度算法。常用于工业生产的群控系统中，要求不太严格。

2.非抢占式优先调度算法。要求相对严格，根据任务的优先级安排等待位置。可用于有一定要求的实时控制系统中。（精心设置可获得百ms级的响应时间）

2）抢占式调度算法

      较严格的实时系统中（t约为数十ms），选择采用抢占式优先权调度算法。根据抢占发生时间可分为：

1.基于时钟：某高优先级任务到达后并不立即抢占，而等下一个时钟中断时抢占。

2.立即抢占：一旦出现外部中断，只要当前任务未处于临界区，就立即抢占处理机。

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

最早截止时间优先EDF（Earliest Deadline First）算法

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

最低松弛度优先LLF（Least Laxity First）算法

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

四．产生死锁的原因和必要条件

死锁（Deadlock）：

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

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

产生死锁的原因可归结为如下两点：

1.竞争资源。系统中供多个进程共享的资源如打印机、公用队列等的数目不满足需要时，会引起资源竞争而产生死锁。

可剥夺和非剥夺性资源

永久性资源和临时性资源

2.进程间推进顺序非法。进程在运行过程中，请求和释放资源的顺序不当，同样会导致死锁。

1)推进顺序合法

2)推进顺序非法

3、产生死锁的必要条件

①互斥条件：进程对所分配到的资源进行排他性使用

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

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

④环路等待条件

4、处理死锁的基本方法

事先预防：

①预防死锁

设置限制条件，破坏四个必要条件的一个或几个，预防发生死锁。

较易实现。限制条件的严格也会导致系统资源利用率和系统吞吐量降低。

②避免死锁

不须事先限制，破坏四个必要条件，而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。

这种事先加以较弱限制的方法，实现上有一定难度，但可获较高的资源利用率及系统吞吐量，目前在较完善的系统中，常用此方法来避免发生死锁。

事后处理：

③检测死锁。

允许系统运行过程中发生死锁，但通过系统检测机构可及时的检测出，能精确确定与死锁有关的进程和资源；然后采取适当的措施，从系统中将已发生的死锁清除掉。

④解除死锁。

与死锁检测配套的一种措施。

常用的实施方法：撤销或挂起一些进程，以便回收一些资源并将他们分配给已阻塞进程，使之转为就绪以继续运行。

死锁的检测与解除措施，有可能使系统获得较好的资源利用率和吞吐量（死锁几率不一定很高），但在实现上难度也最大。

五．预防死锁的方法

①摒弃“请求和保持”条件：所有进程开始运行前，必须一次性的申请其在整个运行过程所需的全部资源（AND）。算法简单、易于实现且很安全。但缺点是资源浪费严重、或进程延迟运行。

②摒弃“不剥夺”条件：允许进程先运行，但当提出的新要求不被满足时必须释放它已保持的所有资源，待以后需要时再重新申请。实现比较复杂且付出很大代价。可能会造成前功尽弃，反复申请和释放等情况。

③摒弃“环路等待”条件：有序设置资源：将所有资源按类型进行线性排队，赋予不同序号。所有进程对资源的请求必须严格按照资源序号递增的次序提出，这样在所形成的资源分配图中，不可能会出现环路。

*由安全状态向不安全状态的转换

只要使系统始终处于安全状态，便可避免发生死锁。

不是所有的不安全状态都是死锁状态。

避免死锁的算法过程（银行家算法）

进程Pi发出资源请求后，系统按下述步骤进行检查：

首先是两个基本判断：

（1）IF Requesti[j]<= Need[i,j]

  THEN 转向步骤2；

  ELSE 认为出错，所需资源数超过宣布的最大值（自我矛盾)

（2）IF Requesti[j]<= Available[j]

  THEN 转向步骤3；

  ELSE 表示尚无足够资源，Pi需等待（现实不满足）

如果上面两步判断都通过了，进入实质的资源分析

（3）系统试探着把资源分配给进程Pi ，并修改相应数据结构的值（假设性操作）：

    Available【j】  =

    Allocation【i,j】=

    Need【i,j】=

（4）系统执行安全性算法，判断新的资源分配状态是否是安全的。

  即：找一个安全序列，使这些进程按顺序执行完）如果能够找到，则将假设操作真正实施完成资源分配。

六．死锁的检测与解除

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

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

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

资源分配图

系统死锁可利用资源分配图来描述。

圆圈表示进程

方框表示一类资源，其中的一个点代表一个该类资源

请求边由进程指向方框中的资源

分配边则由方框中的一个点即资源。

死锁检测算法：

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

* 设置一张资源分配表

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

* 设置一张进程等待表

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

3、死锁的解除

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

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

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