【操作系统】第三章 处理机调度与死锁

目录

处理机调度概述

调度算法

实时调度

Linux进程调度

死锁概述

预防死锁

避免死锁

死锁的检测与解除

---

看到这篇内容这么详细，这么多字是不是很烦呢??(?ó﹏ò?)
以下简述重点part：

处理机调度的三个层次（高级/作业、中级/内存，低级/进程）；评价指标

集中常见的调度算法和实时调度的计算；

死锁的定义，原因，条件，预防，解决方法

处理机调度概述

处理机调度层次

1）高级调度（长程调度/?作业调度）
调度对象：作业
根据某种算法，决定将外存上处于后备队列中的作业调入内存，并为它们创建进程和分配必要的资源。然后，将新创建的进程排在就绪队列上等待调度。
主要用于多道批处理系统中

2）中级调度（中程调度/?内存调度）
将暂不运行的进程，调至外存等待
将处于外存上的急需运行的进程，调入内存运行。
即“对换”功能。

3）低级调度（短程调度/?进程调度）
调度对象：进程
根据某种调度算法，决定就绪队列中的哪个进程应获得处理机
应用在于多道批处理、分时和实时OS

进程调度的任务和方式

进程调度的任务：
保存处理机的现场信息
按某种算法选取进程
把处理机分配给进程

进程调度机制（调度程序分为三部分）：
排队器：用于将就绪进程插入相应的就绪队列
分派器：用于将选定的进程移出就绪队列
上下文切换器：进行新旧进程之间的上下文切换

进程调度的方式

非抢占式：
一旦把处理机分配给某进程后，便让该进程一直执行，直至该进程完成或发生某事件而被阻塞时，才再把处理机分配给其他进程，决不允许某进程抢占已经分配出去的处理机。

抢占式：
允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。(现代OS广泛采用)
>?优先权原则：允许优先权高的新到进程抢占当前进程的处理机
>?短作业优先原则：短作业可以抢占当前较长作业的处理机
>?时间片原则：各进程按时间片运行，当一个时间片用完后，便停止该进程的执行而重新进行调度

处理机调度算法的目标

共同目标：资源利用率；公平性；平衡性；策略强制执行

批处理系统的目标：平均周转时间段、系统吞吐量高、处理机利用率高

分时系统的目标：响应时间快、均衡性

实时系统的目标：截止时间的保证、可预测性

评价指标

周转时间：
> 从作业提交给系统开始，到作业完成为止的这段时间间隔。
> 平均周转时间：
> 带权周转时间：权值为作业周转时间T与系统为之服务时间TS之比。
> 平均带权周转时间

响应时间：从用户通过键盘提交请求开始，直到系统首次显示出处理结果为止的一段时间。

等待时间（进程调度）：进程在就绪队列中等待调度的所有时间之和。

调度算法

作业调度算法：
1）先来先服务算法?FCFS；2）短作业优先调度算法SJF；3）优先级调度算法?PR；4）高响应比优先调度算法HRRN；【FCFS、SJF、PR既可用于作业调度，也可用于进程调度】

进程调度算法：
1）先来先服务调度算法(FCFS)；2）短作业优先调度算法(SJF)；3）优先权调度算法(PR)；4）多级队列调度算法；5）多级反馈队列调度算法；6）基于公平原则的调度算法；7）时间片轮转调度算法(RR)

先来先服务调度算法(FCFS)

按照作业到达的先后次序来进行调度

假定作业到达顺序如下: J1 , J2 , J3 ?该调度的甘特图(Gantt)为:

平均等待时间=（0+24+27）/ 3 = 17
平均周转时间=（24+27+30）/ 3 = 27

假定进程到达顺序如下 ?J2 , J3 , J1 .该调度的Gantt图为 :

? 平均等待时间 = (6 + 0 + 3)/3 = 3
? 平均周转时间 = (30+ 3 + 6)/3 = 13
比前例好得多，此结果产生是由于短进程先于长进程到达

短作业优先调度算法(SJF)

SJF算法：既可用于作业，也可用于进程
对作业：从后备队列中选择若干个估计运行时间最短的作业。
对进程：关联到每个进程下次运行的CPU区间长度，调度最短的进程。

对进程调度，SJF有两种模式：
非抢占式SJF
抢占式SJF–抢占发生在有比当前进程剩余时间片更短的进程到达时，也称为最短剩余时间优先调度

SJF是最优的（对一组指定的进程而言），它给出了最短的平均等待时间。

举例：

平均等待时间 = (0 + 6 + 3 + 7)/4 = 4
平均周转时间=(7+10+4+11)/4= 8

平均等待时间 = (9 + 1 + 0 +2)/4 = 3
平均周转时间 = (16+ 5 +1+ 6)/4 = 7

优点：SJF比FCFS算法有明显改进

缺点：
只能估算进程的运行时间（估值不准确），所以通常用于作业调度
对长作业不利
采用SJF算法时，人-机无法实现交互
完全未考虑作业的紧迫程度

优先权调度算法(PR)

既可用于作业调度，也可用于进程调度。

基于作业/?进程的紧迫程度，由外部赋予作业相应的优先级，调度算法根据优先级进行调度。
每个进程都有一个优先数，优先数为整数
默认：小的优先数具有高优先级
目前主流的操作系统调度算法

进程优先级调度算法

优先级调度算法的类型：>?非抢占式? ? ? ? >?抢占式

优先级类型
> 静态类型
创建进程时确定优先数（整数），在进程的整个运行期间保持不变
简单易行，系统开销?小
不够精确，可能会出现优先级低的进程长期没有被调度的情况
>?动态优先级
创建进程时先赋予其一个优先级，然后其值随进程的推进或等待时间的增加而改变

非抢占优先级调度算法举例：

平均等待时间 = (0 + 5 + 16+18+1)/5 =8
平均周转时间 = (16 + 1 + 18+19+6)/5 = 12

优先级调度算法的优点：
实现简单，考虑了进程的紧迫程度
灵活，可模拟其它算法

存在问题：饥饿 ——低优先级的进程可能永远得不到运行

解决方法：老化 —— 视进程等待时间的延长提高其优先数

高响应比优先调度算法HRRN
高响应比优先调度算法是一种优先级调度算法，用于作业调度。
既考虑作业的等待时间，又考虑作业的运行时间

如等待时间相同，运行时间越短，类似于SJF
如运行时间相同，取决于等待时间，类似于FCFS
长作业可随其等待时间的增加而提高，也可得到服务
缺点：每次调度之前，都需要计算响应比，增加系统开销

时间片轮转调度算法(RR)

1）专为分时系统设计，类似于FCFS，但增加了抢占
2）时间片 小单位的CPU时间，通常为10~100毫秒
3）为每个进程分配不超过一个时间片的CPU。时间片用完后，该进程将被抢占并插入就绪队列末尾，循环执行
4）假定就绪队列中有n个进程、时间片为q, 则每个进程每次得到1/n的、不超过q单位的成块CPU时间，没有任何一个进程的等待时间会超过(n-1) q单位

例子：时间片为20的RR

平均等待时间：(57+20+64+80)/4 = 55.25
平均响应时间: (0+20+37+57)/4= 28.5
通常，RR的平均周转时间比SJF长，但响应时间要短一些.

时间片大小的确定
特性：q 大 ?FCFS ；q? 小 增加上下文切换的时间
时间片设置应考虑：系统对响应时间的要求；就绪队列中进程的数目；系统的处理能力
一般准则：时间片/10>进程上下文切换时间
RR例子：

多级队列调度算法
就绪队列从一个分为多个，如:前台[交互式]；后台[批处理]
每个队列有自己的调度算法：前台- RRV；后台- FCFS
调度须在队列间进行
> 固定优先级调度，即前台运行完后再运行后台有可能产生饥饿
>?给定时间片调度，即每个队列得到一定的CPU时间，进程在给定时间内执行;如80%的时间执行前台的RR调度，20%的时间执行后台的FCFS调度

多级反馈队列调度算法
进程能在不同的队列间移动
其他调度算法的局限性：
? > 短进程优先的调度算法，仅照顾了短进程而忽略了长进程
? > 如果并末指明进程的长度，则短进程优先和基于进程长度的抢占式调度算法都将无法使用。
优点：不必事先知道各种进程所需的执行时间；可以满足各种类型进程的需要。
例子：

基于公平原则的调度算法
主要考虑调度的公平性
保证调度算法：性能保证，而非优先运行，如保证处理机分配的公平性(处理机时间为1/n)。
公平分享调度算法：
调度的公平性主要针对用户而言；使所有用户能获得相同的处理机时间或时间比例

实时调度

基于公平原则的调度算法：
实时调度是针对实时任务的调度。
实时任务，都联系着一个截止时间：硬实时HRT任务； 软实时SRT任务
实时调度应具备一定的条件。

实现实时调度的基本条件：
1）提供必要的信息：就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级
2）系统处理能力强：单处理机系统；多处理机系统
3）采用抢占式调度机制
4）采用快速切换机制：对中断具有快速响应能力；快速的任务分派能力

实时调度算法分类：
根据实时任务性质：HRT调度算法；SRT调度算法
根据调度方式：非抢占式调度算法；抢占式调度算法

非抢占式调度算法：
非抢占式轮转调度算法：响应时间：数秒至数十秒；可用于要求不太严格的实时控制系统
非抢占式优先调度算法 响应时间：数秒至数百毫秒 可用于有一定要求的实时控制系统

抢占式调度算法：
基于时钟中断的抢占式优先级调度：响应时间：几十毫秒至几毫秒；可用于大多数实时系统
立即抢占的优先级调度：响应时间：几毫秒至几百微秒；可用于有严格时间要求的实时系统

最早截止时间优先（EDF）调度算法
EDF根据任务的截止时间确定优先级，截止时间越早，优先级越高
既可用于抢占式调度，也可用于非抢占式调度
非抢占式调度用于非周期实时任务
抢占式调度用户周期实时任务

抢占式EDF例子

最低松弛度优先LLF算法
根据任务的紧急程度(松弛度)确定任务优先级
紧急程度越高 (松弛度越低)，优先级越高
松弛度=必须完成时间 - 其本身的运行时间- 当前时间
主要用在抢占式调度方式中
例子：两个周期性实时任务A和B，任务A要求每20 ms执行一次，执行时间为10 ms，任务B要求每50 ms执行一次，执行时间为25 ms

优先级倒置现象
采用优先级调度和抢占方式，可能产生优先级倒置。现象：高优先级进程被低优先级进程延迟或阻塞。
解决方法：
制定一些规定，如规定低优先级进程执行后，其所占用的处理机不允许被抢占；
建立动态优先级继承。

Linux进程调度

默认调度算法：完全公平调度CFS算法。
基于调度器类：允许不同的可动态添加的调度算法并存，每个类都有一个特定的优先级。
总调度器：根据调度器类的优先顺序，依次对调度器类中的进程进行调度。
调度器类：使用所选的调度器类算法（调度策略）进行内部的调度。
调度器类的默认优先级顺序为：Stop_Task＞Real_Time＞Fair＞Idle_Task

普通进程调度：
采用SCHED_NORMAL调度策略。
分配优先级、挑选进程并允许、计算使其运行多久。
CPU运行时间与友好值（-20~+19）有关，数值越低优先级越高。

实时进程调度：
实时调度的进程比普通进程具有更高的优先级。
SCHED_FIFO：进程若处于可执行的状态，就会一直执行，直到它自己被阻塞或者主动放弃CPU。
SCHED_RR：与SCHED_FIFO大致相同，只是进程在耗尽其时间片后，不能再执行，而是需要接受CPU的调度。

死锁概述

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

资源问题：
1）可重用性资源和可消耗性资源
可重用性资源：一次只能分配给一个进程，不允许多个进程共享，遵循：请求资源?使用资源?释放资源 （大部分资源）。
可消耗性资源：由进程动态创建和消耗 （进程间通信的消息）。
2）可抢占性和不可抢占性资源
可抢占性资源：某进程在获得这类资源后，该资源可以再被其他进程或系统抢占，CPU（处理机）和主存区。
不可抢占资源：当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自行释放，打印机、磁带机。

死锁原因：
竞争不可抢占性资源引起死锁：系统中的不可抢占性资源，由于它们的数量不能满足诸进程运行的需要，会使进程在运行过程中，因争夺这些资源而陷入僵局。
竞争可消耗性资源引起死锁
进程推进顺序不当引起死锁：进程推进顺序合法；进程推进顺序非法

死锁：一组等待的进程，其中每一个进程都持有资源，并且等待着由这个组中其他进程所持有的资源。

产生死锁的必要条件：
1）互斥：一段时间内某资源只能被一个进程占用。
2）请求和保持：一个至少持有一个资源的进程等待获得额外的由其他进程所持有的资源
3）不可抢占：一个资源只有当持有它的进程完成任务后，自由的释放。
4）循环等待：等待资源的进程之间存在环 {P0, P1, …, Pn} 。?P0 等待P1占有的资源, P1等待P2占有的资源, …, Pn–1等待Pn占有的资源, P0等待Pn占有的资源

解决死锁的方法：
1）确保系统永远不会进入死锁状态：死锁预防；死锁避免
2）允许系统进入死锁状态，然后恢复系统：死锁检测；死锁恢复
3）忽略这个问题，假装系统中从未出现过死锁。这个方法被大部分的操作系统采用，包括UNIX

处理死锁的方法：
1）预防死锁：破坏死锁的四个必要条件中一个或几个。
2）避免死锁：在资源动态分配时，防止系统进入不安全状态。
3）检测死锁：事先不采取任何措施，允许死锁发生，但及时检测死锁发发生。
4）解除死锁：检测到死锁发生时，采取相应措施，将进程从死锁状态中解脱出来。

预防死锁

破坏死锁的四个必要条件的一个或几个
1）互斥：互斥条件是共享资源必须的，不仅不能改变，还应加以保证
2）请求和保持：必须保证进程申请资源的时候没有占有其他资源
要求进程在执行前一次性申请全部的资源，只有没有占有资源时才可以分配资源
资源利用率低，可能出现饥饿
改进：进程只获得运行初期所需的资源后，便开始运行；其后在运行过程中逐步释放已分配的且用毕的全部资源，然后再请求新资源
3）非抢占：
如果一个进程的申请没有实现，它要释放所有占有的资源；
先占的资源放入进程等待资源列表中；
?进程在重新得到旧的资源的时候可以重新开始
4）循环等待：对所有的资源类型排序进行线性排序，并赋予不同的序号，要求进程按照递增顺序申请资源。
如何规定每种资源的序号是十分重要的；
限制新类型设备的增加；
作业使用资源的顺序与系统规定的顺序不同；
限制用户简单、自主的编程。

避免死锁

死锁避免算法动态检查资源分配状态以确保不会出现循环等待的情况。

资源分配状态定义为可用的与已分配的资源数，和进程所需的最大资源量。

安全状态
当进程申请一个有效的资源的时候，系统必须确定分配后是安全的。
如果存在一个安全序列，则系统处于安全态。
进程序列<P1, P2, …, Pn>是安全的，如果每一个进程Pi所申请的可以被满足的资源数加上其他进程所持有的该资源数小于系统总数。 ?
????????如果 Pi 需要的资源不能马上获得，那么Pi 等待直到所有的Pi-1进程结束。
????????当Pi-1 结束后， Pi获得所需的资源，执行、返回资源、结束。
????????当Pi结束后， Pi+1获得所需的资源执行，依此类推。

基本事实：
如果一个系统在安全状态，就没有死锁
如果一个系统不是处于安全状态，就有可能死锁
死锁避免 =>?确保系统永远不会进入不安全状态

银行家算法
1）针对资源有多个实例
2）每一个进程必须事先声明使用的最大量
3）当一个进程请求资源，它可能要等待
4）当一个进程得到所有的资源，它必须在有限的时间释放它们

数据结构：n为进程的数目，m为资源类型的数目

Requesti =进程 Pi 的资源请求向量， 如果Requesti [m] = k 则进程 Pi 想要资源类型为Rjm的k个实例?? ?

银行家算法的例子

矩阵的内容。Need被定义为Max – Allocation
系统处在安全的状态，因为序列< P1, P3, P4, P2, P0> 满足了安全的标准


执行安全算法表明序列<P1, P3, P4, P0, P2> 满足要求

资源分配图

系统模型：
1）资源类型 R1, R2, . . ., Rm：CPU周期，内存空间，I/O设备
2）每一种资源Ri 有Wi ?种实例
3）每一个进程通过如下方法来使用资源：申请、使用、释放

资源分配图组成：
一个顶点的集合V和边的集合E
1）V被分为两个部分
P = {P1, P2, …, Pn}, 含有系统中全部的进程
R = {R1, R2, …, Rm}, 含有系统中全部的资源
2）请求边：有向边Pi ->?Rj
3）分配边：有向边 Rj -> Pi

????????????????????????无死锁的资源分配图????????????????????????????????????????有死锁的资源分配图

基本事实
如果图没有环，那么不会有死锁！
如果图有环，那么：
????????如果每一种资源类型只有一个实例，那么死锁发生；
????????如果一种资源类型有多个实例，那么可能死锁。

死锁的检测与解除

当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和解除死锁的手段。为此，系统必须：
保存有关资源的请求和分配信息；
提供一种算法，以利用这些信息来检测系统是否已进入死锁状态。

资源分配图的简化：
在资源分配图中，找出一个既不阻塞又非独立的进程结点pi。在顺利的情况下，pi可获得所需资源而继续运行，直至运行完毕，再释放其所占有得全部资源，这相当于消去pi所有的请求边和分配边，使之成为孤立的结点；
p1释放资源后，便可使p2获得资源而继续运行，直到p2完成后又释放出它所占有的全部资源；
在进行一系列的简化后，若能消去图中所有的边，使所有进程都成为孤立结点，则称该图是可完全简化的；若不能通过任何过程使该图完全简化，则称该图是不可完全简化的。

所有的简化顺序，都将得到相同的不可简化图。

S为死锁状态的充分条件是：当且仅当S状态的资源分配图是不可完全简化的。该充分条件称为死锁定理。

检测算法的例子：

另一个实例：

当前系统的状态：
1）可以归还P0所有的资源，但是资源不够完成其他进程的请求。
2）死锁存在，包括进程P1、P2、P3和P4。

常用解除死锁的两种方法：
抢占资源。从一个或多个进程中抢占足够数量的资源给死锁进程，以解除死锁状态。
终止或撤消进程。终止系统中一个或多个死锁进程，直到打破循环环路，使死锁状态消除为止。
> 终止所有死锁进程（最简单方法）
> 逐个终止进程（稍温和方法）

进程终止
> 中断所有的死锁进程。
> 一次中断一个进程，直到死锁环消失。
> 应该选择怎样的中断顺序，使“代价最小”？
进程的优先级；
进程需要计算多长时间，以及需要多长时间结束；
进程使用的资源，进程完成还需要多少资源；
进程是交互的还是批处理的。

本篇主要介绍了OS处理机管理功能中的两个重要内容：处理机调度与死锁。处理机调度分为三个不同层次，进程调度（最基本）。本篇介绍了常用的进程/?作业调度算法，常用的实时调度算法以及关于死锁产生，解决等内容。

看到这最后，辛苦了吧，但是知识以迅雷不及掩耳之势冲入你的大脑了哦，加油~