处理机调度与死锁

处理机调度：多道程序环境下，动态的把处理机分配给就绪队列中的一个进程使之
执行。提高处理机的利用率、改善系统性能，很大程度上取决于处理机调度的性能。
处理机调度便成为OS设计的中心问题之一。分配的任务由处理机调度程序完成

处理机调度的基本概念

作业进入系统驻留在外存的后备队列上，再至调入内存运行完毕，可能要经历下述三级调度

高级调度

又称作业调度或长程调度(Long-Term Scheduling),接纳调度(Admission Scheduling) 主要在早期批处理阶段，处理在外存上的作业
决定外存后备队列中的哪些作业调入内存; 为它们创建进程、分配必要的资源; 将新创建的进程排在就绪队列上，准备执行。 * 管理的方面比较多

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

批处理系统 ：作业进入系统后先驻留外存， 故需要有作业调度。
分时系统 ：为及时响应，作业由终端直接送 入内存，故不需作业调度。
实时系统 中，通常也不需作业调度。

低级调度

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

进程调度方式

非抢占方式（Non-preemptive Mode） 一旦处理机分配给某进程，该进程一直执行。 决不允许其他进程抢占已分配运行进程的处理机。 2）抢占方式（Preemptive Mode） 允许调度程序根据某种原则，暂停某个正在执 行的进程，将处理机重新分配给另一进程。

中级调度

又称交换调度或中程调度（Medium-Term Scheduling） 引入目的：提高内存利用率和系统吞吐量。 根据条件将一些进程调出或再调入内存

调度队列模型

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

进程调度发生时间

正在执行的进程结束 
正在执行的进程阻塞 
正在执行的进程未完成转就绪（时间片到） 
新就绪了更高优先级的进程（抢占式）
具有高级和低级调度的调度队列模型 ❖ 批处理系统中，还需要作业调度

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

引入中级调度后，进程的状态变化：
❖ 就绪状态：分为内存就绪和外存就绪。
❖ 阻塞状态：分为内存阻塞和外存阻塞。 中级调度使进程在上述状态间变化，并使 数据在内外存间互换。

image.png

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

面向用户的准则

周转时间短： 针对批处理系统的性能指标。作业从提交到完成所经历 的时间。 
CPU执行用时Ts 
总的等待时间Tw = 在后备队列中等待 + 就绪队列上等待 + 阻塞队列中等待（等待I/O操作用时） 
周转时间T=Ts+Tw 
带权周转时间W= T/Ts 
平均周转时间、平均带权周转时间（n个作业求平均）

响应时间快：针对分时系统。用户输入一个请 求（如击键）到系统给出首次响应（如屏幕显示） 的时间
❖均衡性：系统响应时间的快慢与用户所请求的 复杂性相适应。
❖截止时间的保证：针对实时系统的性能指标。 开始截止时间和完成截止时间。任务必须按规定 的时间开始或完成，调度方式和算法必须能保证 该要求。 
❖优先权准则：三大基本OS在调度算法的选择 时都可遵循。可以使关键任务达到更好的指标

面向系统的准则

系统吞吐量高： 批处理系统的重要指标。 单位时间内所完成的作业数，跟作业本身 （与作业平均长度密切相关）和调度算法 都有关系； 

处理机调度与死锁

调度算法

先来先服务调度算法FCFS

一种最简单的调度算法，按先后顺序进行调度。既 可用于作业调度，也可用于进程调度。
 ❖ 按照作业提交，或进程变为就绪状态的先后次 序分派CPU； 
❖ 新作业只有当当前作业或进程执行完或阻塞才 获得CPU运行
 ❖ 被唤醒的作业或进程不立即恢复执行，通常等 到当前作业或进程出让CPU。 （所以，默认即 是非抢占方式）
 不利于短作业（进程） 

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

优点：
 ❖ 通过上表可见采用SJF/SPF算法，平均周转 时间、平均带权周转时间都有明显改善。 SJF/SPF调度算法能有效的降低作业的平均 等待时间，提高系统吞吐量。 方式： 
❖ 分抢占和非抢占两种方式，上例为简单的非 抢占式。
 SJF/SPF的不足： 1. 对短作业有利，但同时造成了对长作 业的不利。 2.由于作业（进程）的长短含主观因素， 不一定能真正做到短作业优先。 3.未考虑作业的紧迫程度，因而不能保证 紧迫性作业（进程）的及时处理。

高优先权优先调度算法HPF

照顾紧迫性作业，使其获得优先处理而引入 调度算法。常用于批处理系统中的作业调度算法， 以及多种操作系统中的进程调度算法 1) 分两种方式：
 ❖非抢占式优先权算法 
❖抢占式优先权算法 关键点：新作业产生时
优先权的类型
 ❖ 静态优先权：创建进程时确定，整个运行 期间保持不变。一般利用某一范围的一个 整数来表示，又称为优先数。
 ❖ 动态优先权：创建进程时赋予的优先权可 随进程的推进或随其等待时间的增加而改 变。

高响应比优先调度算法HRRN

 短作业优先算法是一种比较好的算法（相当于根据 作业长度设定的静态优先权算法），适用于短作业 较多的批处理系统中，其主要不足是长作业的运行 得不到保证。
 ❖ HRRN为每个作业引入动态优先权，使作业的优 先级随着等待时间的增加而以速率a提高： 优先权 =（等待时间+要求服务时间)/要求服务时间 = 响应时间 / 要求服务时间

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

❖ 分时系统新需求：及时响应用户的请求； 采用基于 时间片 的轮转式进程调度算法。
 ❖ 早期分时系统采用的是 简单的时间片轮转法
， 进入90年代后广泛采用 多级反馈队列调度算 法 。 
时间片轮转算法
1. 将系统中所有的就绪进程按照FCFS原则，排成一 个队列。 2. 每次调度时将CPU分派给队首进程，让其执行一 个时间片。时间片的长度从几个ms到几百ms。 3. 在一个时间片结束时，发生时钟中断。 4. 调度程序据此暂停当前进程的执行，将其送到就 绪队列的末尾，并通过上下文切换执行当前就绪 的队首进程。 

多级反馈队列算法FB

1）设置多个就绪队列，各队列有不同的优先 级,优先级从第一个队列依次降低。
 2） 赋予各队列进程执行时间片大小不同, 优 先权越高，时间片越短 。

image.png

实时调度

实时系统

1.指系统能够在限定的响应时间内提供所需水平 的服务。
2.指计算的正确性不仅取决于程序的逻辑正确性， 也取决于结果产生的时间，如果系统的时间约 束条件得不到满足，将会发生系统出错。
实时任务：具有明确时间约束的计算任务， 有软/硬，随机/周期性之分。

实现实时调度的基本条件

1）提供必要的信息 为了实现实时调度，系统应向调度程序提供 有关任务的下述信息：
就绪时间 。该任务成为就绪状态的时间。
开始截止时间、完成截止时间 。
处理时间 。从开始执行到完成所需时间。
资源要求 。任务执行时所需的一组资源。
优先级 。根据任务性质赋予不同优先级。
2）系统处理能力足够强
处理能力不足可能会出现某些实时任务不能 得到及时处理，导致难以预料的后果。 如： 系统中有M个周期性的硬实时任务，处理 时间为Ci，周期时间表示为Pi, 单机系统中必须满足条件
3）采用抢占式调度机制
❖ 硬实时任务：广泛采用抢占机制。
❖ 小的实时系统：如能预知任务的开始 截止时间，为简化调度程序和对任务调 度时所花费的系统开销，可采用非抢占 调度机制，
4）具有快速切换机制
1. 对外部中断的快速响应能力。 ❖ 利用快速硬件中断机构，可在紧迫的 外部事件请求中及时响应。 2. 快速的任务分派能力。 ❖ 使系统中的运行功能单位适当的小，提高切 换速度。类如线程的思想

实时调度算法的分类

非抢占调度算法

该算法较简单，用于一些小型实时系统或要 求不太严格的实时系统中，又可分为：
 1. 非抢占式轮转调度算法。常用于工业生产 的群控系统中，要求不太严格。
 2. 非抢占式优先调度算法。要求相对严格， 根据任务的优先级安排等待位置。可用于 有一定要求的实时控制系统中。（精心设 置可获得百ms级的响应时间）

抢占式调度算法

较严格的实时系统中（t约为数十ms）， 选择采用抢占式优先权调度算法。根据 抢占发生时间可分为：
 1. 基于时钟：某高优先级任务到达后并不 立即抢占，而等下一个时钟中断时抢占。 
2. 立即抢占：一旦出现外部中断，只要当 前任务未处于临界区，就立即抢占处理 机。

最早截止时间优先EDF

根据任务的开始截止时间来确定任务的优先级。 截止时间越早，其优先级越高。 系统保持一个实时任务就绪队列 队列按各任务截止时间的早晚排序 调度程序总是选择就绪队列中的第一个任务，分配处 理机使之投入运行。
 ❖ 新任务产生时，是否等当前程序执行完： 抢占式/非抢占式 
❖ 可能会使作业错过，但可适用于软实时系统

最低松弛度优先LLF

根据任务紧急（或松弛）的程度，来确定任务的优先 级。任务的紧急程度越高（松弛度值越小），优先级就越 高。
 ❖ 松弛度= 截止完成时间 – 还需执行时间 - 当前时间 可理解为当前时刻到开始截止时刻间的差距，随着时间的 推进，这个差值逐渐变小，任务越来越紧迫

处理机调度与死锁

死锁

多道程序系统借助并发执行改善资源利用率， 提高系统吞吐量，但可能发生一种危险——死 锁。 死锁（Deadlock）：指多个进程在运行过 程中，因争夺资源而造成的一种僵局。当进程 处于这种状态时，若无外力作用，它们都将无 法再向前推进。

产生死锁的原因

1. 竞争资源。系统中供多个进程共享的资源 如打印机、公用队列等的数目不满足需要 时，会引起资源竞争而产生死锁。
2. 进程间推进顺序非法。进程在运行过程中， 请求和释放资源的顺序不当，同样会导致 死锁。

产生死锁的必要条件

① 互斥条件：进程对所分配到的资源进行排他性 使用
② 请求和保持条件：进程已经保持了至少一个资 源，又提出新的资源请求，而新请求资源被其 他进程占有只能造成自身进程阻塞，但对自己 已获得的其他资源保持不放，必然影响其他进 程。
③ 不剥夺条件：进程已获得的资源未使用完之前 不能被剥夺，只能在使用完时由自己释放。
④ 环路等待条件

处理死锁的基本方法

① 预防死锁 
❖ 设置限制条件，破坏四个必要条件的一个或几个， 预防发生死锁。
 ❖ 较易实现。限制条件的严格也会导致系统资源利用 率和系统吞吐量降低。
 ② 避免死锁 
❖ 不须事先限制，破坏四个必要条件，而是在资源的 动态分配过程中，用某种方法去防止系统进入不安 全状态，从而避免发生死锁。
 ❖ 这种事先加以较弱限制的方法，实现上有一定难度， 但可获较高的资源利用率及系统吞吐量，目前在较 完善的系统中，常用此方法来避免发生死锁。
③ 检测死锁。
 ❖ 允许系统运行过程中发生死锁，但通过系统检测机 构可及时的检测出，能精确确定与死锁有关的进程 和资源；然后采取适当的措施，从系统中将已发 生的死锁清除掉。
 ④ 解除死锁。 
❖ 与死锁检测配套的一种措施。
 ❖ 常用的实施方法：撤销或挂起一些进程，以便回收 一些资源并将他们分配给已阻塞进程，使之转为就 绪以继续运行。 
❖ 死锁的检测与解除措施，有可能使系统获得较好的 资源利用率和吞吐量（死锁几率不一定很高），但 在实现上难度也最大。

预防死锁的方法

预防死锁
摒弃“环路等待”条件
避免死锁

银行家算法避免死锁

image.png
image.png
image.png

（1）T0时刻的初始状态是安全的； 
（2）下面出现P1请求资源的操作，具体请求 向量为Request1(1,0,2)，利用银行家算法 进行检查该操作是否是安全可行的： 
1）两个基本判断 
Request1(1,0,2)<=Need1(1,2,2) 
Request1(1,0,2)<=Available1(3,3,2) 
2）先假设为P1分配资源，并修改 Available,Allocation1和Need1向量。
3） Request1(1,0,2)后新的资源状态表下再判断新资源状态是否是 安全的。 找到一个安全序列{P1,P3,P4,P0,P2}，因此系统是安全的，该请求是 安全的，可将假设真正实施，将P1所申请的资源分配给它。

死锁的检测与解除

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

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

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

   
   image.png

死锁的检测

检测时机：
当进程等待时检测死锁
定时检测
系统资源利用率下降时检测死锁

死锁定理

简化方法如下：
1.在资源分配图中找出一个既不阻塞又非独立 的进程结点Pi，在顺利的情况下运行完毕，释 放其占有的全部资源。
2.由于释放了资源，这样能使其它被阻塞的进 程获得资源继续运行。消去了Pi的边。
3.经过一系列简化后，若能消去图中所有边， 使结点都孤立，称该图是可完全简化的。

死锁的解除

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

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

2.jpg 3.jpg
](https://img.haomeiwen.com/i5951897/83c04776da3eae4c.jpg?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)
1.jpg