第三章 处理机调度与死锁第三章 处理机调度与死锁
3.1 处理机调度的基本概念
3.2 进程调度算法
3.3 实时调度
3.4 多处理机系统中的调度
3.5 产生死锁的原因和必要条件
3.6 预防死锁的方法和死锁避免
3.7 死锁的检测和解除
3.1 处理机调度的基本概念在多道程环境下，进程数目往往多于处理机数目，致使它们争用处理机。
这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，
使之执行。分配处理机的任务是由进程调度程序完成的。它是操作系统设计的中心问题之一。
进程调度要解决的问题
WHAT：按什么原则分配 CPU
— 进程调度算法
WHEN：何时分配 CPU
— 进程调度的时机
HOW,如何分配 CPU
— CPU调度过程（进程的上下文切换）
1,高级、中级和低级调度
处理机是计算机系统中的重要资源
处理机调度算法对整个计算机系统的综合性能指标有重要影响
可把处理机调度分成三个层次：
高级调度
中级调度
低级调度
高级调度 也称为作业调度或宏观调度高级调度的时间尺度通常是分钟、小时或天
中级调度 涉及进程在内外存间的交换，从存储器资源管理的角度来看，把进程的部分或全部换出到外存上，可为当前运行进程的执行提供所需内存空间，将当前进程所需部分换入到内存。指令和数据必须在内存里才能被处理机直接访问
低级调度 也称微观调度，从处理机资源分配的角度来看，处理机需要经常选择就绪进程或线程进入运行状态，低级调度的时间尺度通常是毫秒级的。由于低级调度算法的频繁使用，要求在实现时做到高效
2.进程调度的任务进程调度的任务是控制协调进程对 CPU的竞争,即按一定的调度算法从就绪队列中选中一个进程，把 CPU的使用权交给被选中的进程
3.确定算法的原则
具有公平性
资源利用率高（特别是 CPU利用率）
在交互式系统情况下要追求响应时间（越短越好）
在批处理系统情况下要追求系统吞吐量
4.进程调度方式
非剥夺方式：分派程序一旦把处理机分配给某进程后便让它一直运行下去,直到进程完成或发生某事件而阻塞时,才把处理机分配给另一个进程 。
剥夺方式：当一个进程正在运行时,系统可以基于某种原则,剥夺已分配给它的处理机,将之分配给其它进程 。 剥夺原则有：
优先权原则,短进程优先原则,时间片原则 。
5.进程调度性能衡量的指标
周转时间
响应时间
CPU-I/O执行期
6.进程调度模型
1)只有进程调度的调度队列模型图 3 - 1 仅具有进程调度的调度队列模型
2)具有高低级调度的调度队列模型图 3-2 具有高、低两级调度的调度队列模型
3)具有三级调度的调度队列模型图 3-3 具有三级调度时的调度队列模型
7.选择进程调度方式的准则
面向用户的准则：周转时间短；响应时间快；截止时间的保证；优先权准则
面向系统的准则：系统吞吐量高；
处理机利用率好；各类资源的平衡利用
3.2 进程调度算法
先进先出 (FIFO)算法
最短 CPU运行期优先调度算法
最高优先权优先调度算法
轮转法
多级反馈队列
1.先进先出 (FIFO)算法该算法总是把处理机分配给最先进入就绪队列的进程,一个进程一旦分得处理机,便执行下去,
直到该进程完成或阻塞时,才释放处理机 。
优点,实现简单,缺点,没考虑进程的优先级
2.最短 CPU运行期优先调度算法
该算法从就绪队列中选出,下一个
CPU执行期,最短的进程,为之分配处理机 。
该算法虽可获得较好的调度性能,但难以准确地知道下一个 CPU执行期,
而只能根据每一个进行的执行历史来预测 。
图 3-4 FCFS和 SJF调度算法的性能
3,FCFS和 SJF的性能比较
4.最高优先权优先调度算法该算法总是把处理机分配给就绪队列中具有最高优先权的进程 。 常用以下两种方法来确定进程的优先权 (优先级根据优先数来决定 )
静态优先数法：静态优先权是在创建进程时确定的,在整个运行期间不再改变 。 依据有：进程类型,进程对资源的要求,用户要求的优先权 。
动态优先数法：在进程创建时创立一个优先数,
但在其生命周期内优先数可以动态变化 。 如等待时间长优先数可改变
5.高响应比优先调度算法优先权的变化规律可描述为：
由于等待时间与服务时间之和,就是系统对该作业的响应时间,故该优先权又相当于响应比 RP。
据此,又可表示为：
6,轮转法把 CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程,进程轮流占有
CPU,当时间片用完时,即使进程未执行完毕,系统也剥夺该进程的 CPU,将该进程排在就绪队列末尾 。 同时系统选择另一个进程运行
简单轮转法：系统将所有就绪进程按 FIFO规则排队,按一定的时间间隔把处理机分配给队列中的进程 。 这样,就绪队列中所有进程均可获得一个时间片的处理机而运行 。
多级队列方法：将系统中所有进程分成若干类,每类为一级 。
7.分时系统中常用时间片轮转法时间片选择问题,
固定时间片可变时间片与时间片大小有关的因素：
系统响应时间就绪进程个数
CPU能力
1)简单轮转法的调度模型
2)多队列反馈调度算法将就绪队列分为 N级，每个就绪队列分配给不同的时间片，队列级别越高，
时间越长，级别越小，时间片越小，最后一级采用时间片轮转，其他队列采用先进先出； 系统从第一级调度，当第一级为空时，系统转向第二个队列,.....当运行进程用完一个时间片，
放弃 CPU时，进入下一级队列；等待进程被唤醒时，进入原来的就绪队列；当进程第一次就绪时，进入第一级队列
* 首先系统中设置多个就绪队列
* 每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大
* 各个队列按照先进先出调度算法
* 一个新进程就绪后进入第一级队列
* 进程由于等待而放弃 CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列
* 当有一个优先级更高的进程就绪时，可以抢占
CPU，被抢占进程回到原来一级就绪队列末尾
* 当第一级队列空时，就去调度第二级队列，如此类推
* 当时间片到后，进程放弃 CPU，回到下一级队列
3)多队列反馈调度算法
8.进程调度的时机
当一个进程运行完毕，或由于某种错误而终止运行
当一个进程在运行中处于等待状态（等待
I/O）
分时系统中时间片到
当有一个优先级更高的进程就绪（可抢占式）
例如：新创建一个进程，一个等待进程变成就绪
在进程通信中，执行中的进程执行了某种原语操作（ P操作，阻塞原语，唤醒原语）
何时切换进程只要 OS取得对 CPU的控制，进程切换就可能发生，如,
– 超级用户调用
来自程序的显式请求 (如：打开文件 )，该进程通常会被阻塞
– 陷阱
最末一条指令导致出错，会引起进程移至退出状态
– 中断
外部因素影响当前指令的执行，控制被转移至 IH（中断处理程序）
9.引起进程调度的原因
正在执行的进程执行完毕或因发生某事件而不能再继续执行；
执行中的进程因提出 I/O请求而暂停执行；
在进程通信或同步过程中执行了某种原语操作如 P操作,阻塞,挂起原语等；
在可剥夺式调度中,有比当前进程优先权更高的进程进入就绪队列；
在时间片轮转法中,时间片完 。
通常系统是按先来先服务或优先权形式来组织调度队列 。
10.进程调度算法
其中,RQ为就绪队列指针,EP为运行队列指针 。
3.3 实 时 调 度
1.实现实时调度的基本条件
提供必要的信息 (就绪时间、截止时间、处理时间、资源优先级 )
系统处理能力强
采用抢占式调度机制
具有快速切换机制
2.实时调度算法的分类
1)非抢占式调度算法,
非抢占式轮转调度算法
非抢占式优先调度算法
2)抢占式调度算法,
基于时钟中断的抢占优先调度算法
立即抢占优先权调度算法。
图 3-5 实时进程调度
3.常用的几种实时调度算法
1）最早截止时间优先即 EDF(Earliest Deadline First)算法图 3-6 EDF算法用于非抢占调度方式
2）最低松弛度优先 (LLF)算法该算法是根据任务紧急 (或松弛 )的程度,来确定任务的优先级 。 该算法主要用于可抢占调度方式中 。
假如在一个实时系统中,有两个周期性实时任务 A和
B,任务 A要求每 20 ms执行一次,执行时间为 10 ms；任务 B只要求每 50 ms执行一次,执行时间为 25 ms。
图 3-7 A和 B任务每次必须完成的时间在刚开始时 (t1=0),A1必须在 20ms时完成,而它本身运行又需 10 ms,可算出 A1的松弛度为 10ms； B1必须在 50ms
时完成,而它本身运行就需 25 ms,可算出 B1的松弛度为 25
ms,故调度程序应先调度 A1执行 。 在 t2=10 ms时,A2的松弛度可按下式算出：
A2的松弛度 =必须完成时间 -其本身的运行时间 -当前时间
=40 ms-10 ms-10 ms=20 ms
类似地,可算出 B1的松弛度为 15ms,调度程序应选择
B2运行 。 t3=30 ms时,A2的松弛度已减为 0,B1的松弛度为
15 ms,于是调度程序应抢占 B1的处理机而调度 A2运行 ……,
图 3-8 利用 ELLF算法进行调度的情况
3.4 多处理机系统中的调度
1.多处理器系统的类型
(1) 紧密耦合 (Tightly Coupted)MPS。
(2) 松散耦合 (Loosely Coupled)MPS。
2.对称 多处理器系统和非对称多处理器系统
3.进程分配方式
(1)
静态分配 (Static Assigenment)方式动态分配 (Dynamic Assgement)方式
(2)非对称 MPS中的进程分配方式
4,进程 (线程 )调度方式
(1）自调度 (Self-Scheduling)方式
（ 2）成组调度 (Gang Scheduling)方式第三章 处理机调度与死锁
3.5 产生死锁的原因和必要条件
3.5.1 死锁的概念
1.死锁例子,
一个由于 申请不同类型资源 而产生死锁的例子
设系统有一台打印机 (R1)一台扫描仪
(R2),两进程共享这两台设备 。
用信号量 S1表示 R1是否可用,用信号量
S2表示 R2是否可用,S1,S2初值为 1。
死锁例子这两个进程在并发执行过程中,可能会发生死锁 。 大家可以思考一下,如何修改,进程才不会发生死锁 。
2.死锁概念
指多个进程因竞争共享资源而造成的一种僵局,若无外力作用,这些进程都将永远不能再向前推进 。
即：一组进程中,每个进程都无限等待被该组进程中另一进程所占有的资源,因而永远无法得到的资源,这种现象称为进程死锁,这一组进程就称为死锁进程 。
3.关于死锁的一些结论
参与死锁的进程最少是两个
参与死锁的进程至少有两个已经占有资源
参与死锁的所有进程都在等待资源
参与死锁的进程是当前系统中所有进程的子集注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。
4.永久性资源和临时性资源永久性资源：可以被多个进程多次使用（可再用资源）
可抢占资源
不可抢占资源临时性资源：只可使用一次的资源；
如信号量,中断信号，同步信号等（可消耗性资源）
“申请 --分配 --使用 --释放”模式
3.5.2 产生死锁的原因
1.竞争系统资源
2.进程的推进顺序不当
1,竞争系统资源若系统中只有一台打印机 R1和一台读卡机 R2,可供进程 P1和 P2共享 。 若 形成环路,这样会产生死锁 。
2.进程的推进顺序不当
在进程 P1和 P2并发执行时,按照左图曲线 ①②③ 所示顺序推进时,两进程会顺利完成,我们称这种推进顺序是合法的 。
若按曲线 ④ 的顺序推进时,进入不安全区 D内,两进程再推进会产生死锁 。
3.5.3 产生死锁的必要条件
互斥条件 （ 资源独占 ）
请求和保持条件 （ 部分分配,
占有申请 ）
不剥夺条件 （ 不可强占 ）
环路等待条件 。
解决死锁的基本办法
预防死锁
避免死锁
检测死锁
解除死锁
3.6 预防死锁的方法和避免死锁
1.预防死锁的方法在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一。
1)资源一次性分配； (破坏请求和保持条件 )
2)可剥夺资源； 即当某进程新的资源未满足时,
释放已占有的资源 (破坏不可剥夺条件 )
3)资源有序分配法 ；做法：系统给每类资源赋予一个编号,每一个进程按编号递增的顺序请求资源,释放则相反 (破坏环路等待条件 )
2,死锁避免
死锁避免定义,在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。
预防死锁的几种策略,会严重地损害了系统性能 。
因此要施加较弱的限制,从而获得较满意得系统性能来避免死锁 。
由于在避免死锁的策略中,允许进程动态地申请资源 。 因而,系统在进行资源分配之前预先计算资源分配的安全性 。 若此次分配不会导致系统进入不安全状态,则将资源分配给进程；否则,进程等待 。
其中最具有代表性的避免死锁算法是银行家算法 。
3,安全状态与不安全状态安全状态指系统能按某种进程顺序来为每个进程分配其所需资源,直至最大需求,使每个进程都可顺序完成 。 若系统不存在这样一个序列,则称系统处于不安全状态 。
1)安全序列一个进程序列 {P1,…,Pn}是安全的，如果对于每一个进程
Pi(1≤ i≤ n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程 Pj (j < i )当前占有资源量之和，
系统处于安全状态。
(安全状态一定是没有死锁发生的 )
2) 安全状态之例我们通过一个例子来说明安全性 。 假定系统中有三个进程 P1,P2和 P3,共有 12台磁带机 。 进程 P1总共要求 10台磁带机,P2和 P3分别要求 4台和 9台 。 假设在 T0时刻,进程 P1、
P2和 P3已分别获得 5台,2台和 2台磁带机,尚有 3台空闲未分配,如下表所示：
进 程 最 大 需 求 已 分 配 可 用
P1
P2
P3
10
4
9
5
2
2
3
3) 由安全状态向不安全状态的转换如果不按照安全序分配资源,则系统可能会由安全状态进入不安全状态 。 例如,在 T0时刻以后,P3又请求 1台磁带机,若此时系统把剩余 3台中的 1台分配给 P3,则系统便进入不安全状态 。 因为,此时也无法再找到一个安全序列,
例如,把其余的 2台分配给 P2,这样,在 P2完成后只能释放出 4台,既不能满足 P1尚需 5台的要求,也不能满足 P3尚需 6
台的要求,致使它们都无法推进到完成,彼此都在等待对方释放资源,即陷入僵局,结果导致死锁 。
安全状态与不安全状态不安全状态,不存在一个安全序列，
不安全状态一定导致死锁
4.利用银行家算法避免死锁
1)银行家算法中的数据结构
(1) 可利用资源向量 Available。 这是一个含有 m
个元素的数组,其中的每一个元素代表一类可利用的资源数目,其初始值是系统中所配置的该类全部可用资源的数目,其数值随该类资源的分配和回收而动态地改变 。 如果 Available［ j］ =K,则表示系统中现有 Rj类资源 K个 。
(2) 最大需求矩阵 Max。 这是一个 n× m的矩阵,它定义了系统中 n个进程中的每一个进程对 m类资源的最大需求 。 如果
Max［ i,j］ =K,则表示进程 i需要 Rj类资源的最大数目为 K 。
(3) 分配矩阵 Allocation。 这也是一个 n× m的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数 。 如果
Allocation［ i,j］ =K,则表示进程 i当前已分得 Rj类资源的数目为 K。
(4) 需求矩阵 Need。 这也是一个 n× m的矩阵,用以表示每一个进程尚需的各类资源数 。 如果 Need［ i,j］ =K,则表示进程
i还需要 Rj类资源 K个,方能完成其任务 。
Need［ i,j］ =Max［ i,j］ -Allocation［ i,j］
2)银行家算法设 Requesti是进程 Pi的请求向量,如果 Requesti［ j］
=K,表示进程 Pi需要 K个 Rj类型的资源 。 当 Pi发出资源请求后,
(1) 如果 Requesti［ j］ ≤Need［ i,j］,便转向步骤 2；
否则认为出错,因为它所需要的资源数已超过它所宣布的最大值 。
(2) 如果 Requesti［ j］ ≤Available［ j］,便转向步骤
(3)；否则,表示尚无足够资源,Pi须等待 。
(3) 系统试探着把资源分配给进程 Pi,并修改下面数据
Available［ j］ ∶ =Available［ j］ -Requesti［ j］ ;
Allocation［ i,j］ ∶ =Allocation［ i,j］ +Requesti［ j］ ;
Need［ i,j］ ∶ =Need［ i,j］ -Requesti［ j］ ;
(4) 系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态 。 若安全,才正式将资源分配给进程 Pi，
以完成本次分配；否则,将本次的试探分配作废,恢复原来的资源分配状态,让进程 Pi等待 。
3)安全性算法
(1) 设置两个向量,① 工作向量 Work,它表示系统可提供给进程继续运行所需的各类资源数目,它含有 m个元素,
在执行安全算法开始时,Work∶ =Available; ② Finish,它表示系统是否有足够的资源分配给进程,使之运行完成 。 开始时先做 Finish［ i］ ∶ =false; 当有足够资源分配给进程时,
再令 Finish［ i］ ∶ =true。
(2) 从进程集合中找到一个能满足下述条件的进程：
① Finish［ i］ =false; ② Need［ i,j］ ≤Work［ j］ ； 若找到,执行步骤 (3),否则,执行步骤 (4)。
(3) 当进程 Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,
Work［ j］ ∶ = Work［ i］ +Allocation［ i,j］ ;
Finish［ i］ ∶ = true;
go to step 2;
(4) 如果所有进程的 Finish［ i］ =true都满足,则表示系统处于安全状态；否则,系统处于不安全状态 。
4) 银行家算法之例假定系统中有五个进程 ｛ P0,P1,P2,P3,P4｝ 和三类资源 ｛ A,
B,C｝,各种资源的数量分别为 10,5,7,在 T0时刻的资源分配情况如图 3-15 所示 。
图 3-8 T0时刻的资源分配表
(1) T0时刻的安全性：
图 3-9 T0时刻的安全序列
(2) P1请求资源,P1发出请求向量 Request1(1,0,2)，
系统按银行家算法进行检查：
① Request1(1,0,2)≤Need1(1,2,2)
② Request1(1,0,2)≤Available1(3,3,2)
③ 系统先假定可为 P1分配资源,并修改 Available,
Allocation1和 Need1向量,由此形成的资源变化情况如图 3-
15 中的圆括号所示 。
④ 再利用安全性算法检查此时系统是否安全。
图 3-10 P1申请资源时的安全性检查
(3) P4请求资源,P4发出请求向量 Request4(3,3,0),系
① Request4(3,3,0)≤Need4(4,3,1);
② Request4(3,3,0) < Available(2,3,0),让 P4等待 。
(4) P0请求资源,P0发出请求向量 Requst0(0,2,0),系统按
① Request0(0,2,0)≤Need 0(7,4,3);
② Request0(0,2,0)≤Available(2,3,0);
③ 系统暂时先假定可为 P0分配资源，并修改有关数据，
如图 3-18 所示。
图 3-11 为 P0分配资源后的有关资源数据允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行
3.7 死锁的检测和解除
1.检测时机当进程等待时检测死锁
（其缺点是系统的开销大）
定时检测系统资源利用率下降时检测死锁
2.死锁检测算法
每个进程和资源指定唯一编号
设置一张资源分配表记录各进程与其占用资源之间的关系
设置一张进程等待表记录各进程与要申请资源之间的关系
1) 资源分配表和进程等待表资源分配表 进程等待表
r1 p2 p1 r1
r2 p5 p2 r3
r3 p4 p4 r4
r4 p1
… … … …
2)资源分配表和进程等待表当进程 P4申请资源 3时，会产生死锁吗？
3)检测算法
3.死锁的解除重要的是以最小的代价恢复系统的运行。方法如下：
1）重新启动
2）撤消进程
3）剥夺资源
4）进程回退
4.资源分配图用有向图描述进程的死锁准确、形象系统由若干类资源构成，一类资源称为一个资源类；每个资源类中包含若干个同种资源，称为资源实例资源分配图二元组 G=（ V,E）
V：结点集，分为 P,R两部分
P={p1,p2,…,pn},R={r1,r2,…,rm}
E：边的集合，其元素为有序二元组,
(pi,rj)或 (rj,pi)
表示法,
资源类,用方框表示（资源的不同类型）
资源实例,用方框中的黑圆点表示（存在于每个资源中）
进程,用圆圈中加进程名表示分配边,资源实例?进程的一条有向边申请边,进程?资源类的一条有向边
5,死锁定理如果资源分配图中没有环路，
则系统中没有死锁，如果图中存在环路则系统中可能存在死锁。
如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件。
有环有死锁有环无死锁
2,死锁定理图 3-12 资源分配图的简化
6,资源分配图化简方法如下,
1）找一个非孤立点进程结点且只有分配边，去掉分配边，将其变为孤立结点
2）再把相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配边
7.解除死锁当发现有进程死锁后,便应立即把它从死锁状态中解脱出来,常采用的方法有：
剥夺资源：从其它进程剥夺足够数量的资源给死锁进程,以解除死锁状态；
撤消进程：可以直接撤消死锁进程或撤消代价最小的进程,直至有足够的资源可用,
死锁状态消除为止；所谓代价是指优先级,
运行代价,进程的重要性和价值等 。
死锁的解除图 3-13 付出代价最小的死锁解除方法
3.1 处理机调度的基本概念
3.2 进程调度算法
3.3 实时调度
3.4 多处理机系统中的调度
3.5 产生死锁的原因和必要条件
3.6 预防死锁的方法和死锁避免
3.7 死锁的检测和解除
3.1 处理机调度的基本概念在多道程环境下，进程数目往往多于处理机数目，致使它们争用处理机。
这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，
使之执行。分配处理机的任务是由进程调度程序完成的。它是操作系统设计的中心问题之一。
进程调度要解决的问题
WHAT：按什么原则分配 CPU
— 进程调度算法
WHEN：何时分配 CPU
— 进程调度的时机
HOW,如何分配 CPU
— CPU调度过程（进程的上下文切换）
1,高级、中级和低级调度
处理机是计算机系统中的重要资源
处理机调度算法对整个计算机系统的综合性能指标有重要影响
可把处理机调度分成三个层次：
高级调度
中级调度
低级调度
高级调度 也称为作业调度或宏观调度高级调度的时间尺度通常是分钟、小时或天
中级调度 涉及进程在内外存间的交换，从存储器资源管理的角度来看，把进程的部分或全部换出到外存上，可为当前运行进程的执行提供所需内存空间，将当前进程所需部分换入到内存。指令和数据必须在内存里才能被处理机直接访问
低级调度 也称微观调度，从处理机资源分配的角度来看，处理机需要经常选择就绪进程或线程进入运行状态，低级调度的时间尺度通常是毫秒级的。由于低级调度算法的频繁使用，要求在实现时做到高效
2.进程调度的任务进程调度的任务是控制协调进程对 CPU的竞争,即按一定的调度算法从就绪队列中选中一个进程，把 CPU的使用权交给被选中的进程
3.确定算法的原则
具有公平性
资源利用率高（特别是 CPU利用率）
在交互式系统情况下要追求响应时间（越短越好）
在批处理系统情况下要追求系统吞吐量
4.进程调度方式
非剥夺方式：分派程序一旦把处理机分配给某进程后便让它一直运行下去,直到进程完成或发生某事件而阻塞时,才把处理机分配给另一个进程 。
剥夺方式：当一个进程正在运行时,系统可以基于某种原则,剥夺已分配给它的处理机,将之分配给其它进程 。 剥夺原则有：
优先权原则,短进程优先原则,时间片原则 。
5.进程调度性能衡量的指标
周转时间
响应时间
CPU-I/O执行期
6.进程调度模型
1)只有进程调度的调度队列模型图 3 - 1 仅具有进程调度的调度队列模型
2)具有高低级调度的调度队列模型图 3-2 具有高、低两级调度的调度队列模型
3)具有三级调度的调度队列模型图 3-3 具有三级调度时的调度队列模型
7.选择进程调度方式的准则
面向用户的准则：周转时间短；响应时间快；截止时间的保证；优先权准则
面向系统的准则：系统吞吐量高；
处理机利用率好；各类资源的平衡利用
3.2 进程调度算法
先进先出 (FIFO)算法
最短 CPU运行期优先调度算法
最高优先权优先调度算法
轮转法
多级反馈队列
1.先进先出 (FIFO)算法该算法总是把处理机分配给最先进入就绪队列的进程,一个进程一旦分得处理机,便执行下去,
直到该进程完成或阻塞时,才释放处理机 。
优点,实现简单,缺点,没考虑进程的优先级
2.最短 CPU运行期优先调度算法
该算法从就绪队列中选出,下一个
CPU执行期,最短的进程,为之分配处理机 。
该算法虽可获得较好的调度性能,但难以准确地知道下一个 CPU执行期,
而只能根据每一个进行的执行历史来预测 。
图 3-4 FCFS和 SJF调度算法的性能
3,FCFS和 SJF的性能比较
4.最高优先权优先调度算法该算法总是把处理机分配给就绪队列中具有最高优先权的进程 。 常用以下两种方法来确定进程的优先权 (优先级根据优先数来决定 )
静态优先数法：静态优先权是在创建进程时确定的,在整个运行期间不再改变 。 依据有：进程类型,进程对资源的要求,用户要求的优先权 。
动态优先数法：在进程创建时创立一个优先数,
但在其生命周期内优先数可以动态变化 。 如等待时间长优先数可改变
5.高响应比优先调度算法优先权的变化规律可描述为：
由于等待时间与服务时间之和,就是系统对该作业的响应时间,故该优先权又相当于响应比 RP。
据此,又可表示为：
6,轮转法把 CPU划分成若干时间片,并且按顺序赋给就绪队列中的每一个进程,进程轮流占有
CPU,当时间片用完时,即使进程未执行完毕,系统也剥夺该进程的 CPU,将该进程排在就绪队列末尾 。 同时系统选择另一个进程运行
简单轮转法：系统将所有就绪进程按 FIFO规则排队,按一定的时间间隔把处理机分配给队列中的进程 。 这样,就绪队列中所有进程均可获得一个时间片的处理机而运行 。
多级队列方法：将系统中所有进程分成若干类,每类为一级 。
7.分时系统中常用时间片轮转法时间片选择问题,
固定时间片可变时间片与时间片大小有关的因素：
系统响应时间就绪进程个数
CPU能力
1)简单轮转法的调度模型
2)多队列反馈调度算法将就绪队列分为 N级，每个就绪队列分配给不同的时间片，队列级别越高，
时间越长，级别越小，时间片越小，最后一级采用时间片轮转，其他队列采用先进先出； 系统从第一级调度，当第一级为空时，系统转向第二个队列,.....当运行进程用完一个时间片，
放弃 CPU时，进入下一级队列；等待进程被唤醒时，进入原来的就绪队列；当进程第一次就绪时，进入第一级队列
* 首先系统中设置多个就绪队列
* 每个就绪队列分配给不同时间片，优先级高的为第一级队列，时间片最小，随着队列级别的降低，时间片加大
* 各个队列按照先进先出调度算法
* 一个新进程就绪后进入第一级队列
* 进程由于等待而放弃 CPU后，进入等待队列，一旦等待的事件发生，则回到原来的就绪队列
* 当有一个优先级更高的进程就绪时，可以抢占
CPU，被抢占进程回到原来一级就绪队列末尾
* 当第一级队列空时，就去调度第二级队列，如此类推
* 当时间片到后，进程放弃 CPU，回到下一级队列
3)多队列反馈调度算法
8.进程调度的时机
当一个进程运行完毕，或由于某种错误而终止运行
当一个进程在运行中处于等待状态（等待
I/O）
分时系统中时间片到
当有一个优先级更高的进程就绪（可抢占式）
例如：新创建一个进程，一个等待进程变成就绪
在进程通信中，执行中的进程执行了某种原语操作（ P操作，阻塞原语，唤醒原语）
何时切换进程只要 OS取得对 CPU的控制，进程切换就可能发生，如,
– 超级用户调用
来自程序的显式请求 (如：打开文件 )，该进程通常会被阻塞
– 陷阱
最末一条指令导致出错，会引起进程移至退出状态
– 中断
外部因素影响当前指令的执行，控制被转移至 IH（中断处理程序）
9.引起进程调度的原因
正在执行的进程执行完毕或因发生某事件而不能再继续执行；
执行中的进程因提出 I/O请求而暂停执行；
在进程通信或同步过程中执行了某种原语操作如 P操作,阻塞,挂起原语等；
在可剥夺式调度中,有比当前进程优先权更高的进程进入就绪队列；
在时间片轮转法中,时间片完 。
通常系统是按先来先服务或优先权形式来组织调度队列 。
10.进程调度算法
其中,RQ为就绪队列指针,EP为运行队列指针 。
3.3 实 时 调 度
1.实现实时调度的基本条件
提供必要的信息 (就绪时间、截止时间、处理时间、资源优先级 )
系统处理能力强
采用抢占式调度机制
具有快速切换机制
2.实时调度算法的分类
1)非抢占式调度算法,
非抢占式轮转调度算法
非抢占式优先调度算法
2)抢占式调度算法,
基于时钟中断的抢占优先调度算法
立即抢占优先权调度算法。
图 3-5 实时进程调度
3.常用的几种实时调度算法
1）最早截止时间优先即 EDF(Earliest Deadline First)算法图 3-6 EDF算法用于非抢占调度方式
2）最低松弛度优先 (LLF)算法该算法是根据任务紧急 (或松弛 )的程度,来确定任务的优先级 。 该算法主要用于可抢占调度方式中 。
假如在一个实时系统中,有两个周期性实时任务 A和
B,任务 A要求每 20 ms执行一次,执行时间为 10 ms；任务 B只要求每 50 ms执行一次,执行时间为 25 ms。
图 3-7 A和 B任务每次必须完成的时间在刚开始时 (t1=0),A1必须在 20ms时完成,而它本身运行又需 10 ms,可算出 A1的松弛度为 10ms； B1必须在 50ms
时完成,而它本身运行就需 25 ms,可算出 B1的松弛度为 25
ms,故调度程序应先调度 A1执行 。 在 t2=10 ms时,A2的松弛度可按下式算出：
A2的松弛度 =必须完成时间 -其本身的运行时间 -当前时间
=40 ms-10 ms-10 ms=20 ms
类似地,可算出 B1的松弛度为 15ms,调度程序应选择
B2运行 。 t3=30 ms时,A2的松弛度已减为 0,B1的松弛度为
15 ms,于是调度程序应抢占 B1的处理机而调度 A2运行 ……,
图 3-8 利用 ELLF算法进行调度的情况
3.4 多处理机系统中的调度
1.多处理器系统的类型
(1) 紧密耦合 (Tightly Coupted)MPS。
(2) 松散耦合 (Loosely Coupled)MPS。
2.对称 多处理器系统和非对称多处理器系统
3.进程分配方式
(1)
静态分配 (Static Assigenment)方式动态分配 (Dynamic Assgement)方式
(2)非对称 MPS中的进程分配方式
4,进程 (线程 )调度方式
(1）自调度 (Self-Scheduling)方式
（ 2）成组调度 (Gang Scheduling)方式第三章 处理机调度与死锁
3.5 产生死锁的原因和必要条件
3.5.1 死锁的概念
1.死锁例子,
一个由于 申请不同类型资源 而产生死锁的例子
设系统有一台打印机 (R1)一台扫描仪
(R2),两进程共享这两台设备 。
用信号量 S1表示 R1是否可用,用信号量
S2表示 R2是否可用,S1,S2初值为 1。
死锁例子这两个进程在并发执行过程中,可能会发生死锁 。 大家可以思考一下,如何修改,进程才不会发生死锁 。
2.死锁概念
指多个进程因竞争共享资源而造成的一种僵局,若无外力作用,这些进程都将永远不能再向前推进 。
即：一组进程中,每个进程都无限等待被该组进程中另一进程所占有的资源,因而永远无法得到的资源,这种现象称为进程死锁,这一组进程就称为死锁进程 。
3.关于死锁的一些结论
参与死锁的进程最少是两个
参与死锁的进程至少有两个已经占有资源
参与死锁的所有进程都在等待资源
参与死锁的进程是当前系统中所有进程的子集注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。
4.永久性资源和临时性资源永久性资源：可以被多个进程多次使用（可再用资源）
可抢占资源
不可抢占资源临时性资源：只可使用一次的资源；
如信号量,中断信号，同步信号等（可消耗性资源）
“申请 --分配 --使用 --释放”模式
3.5.2 产生死锁的原因
1.竞争系统资源
2.进程的推进顺序不当
1,竞争系统资源若系统中只有一台打印机 R1和一台读卡机 R2,可供进程 P1和 P2共享 。 若 形成环路,这样会产生死锁 。
2.进程的推进顺序不当
在进程 P1和 P2并发执行时,按照左图曲线 ①②③ 所示顺序推进时,两进程会顺利完成,我们称这种推进顺序是合法的 。
若按曲线 ④ 的顺序推进时,进入不安全区 D内,两进程再推进会产生死锁 。
3.5.3 产生死锁的必要条件
互斥条件 （ 资源独占 ）
请求和保持条件 （ 部分分配,
占有申请 ）
不剥夺条件 （ 不可强占 ）
环路等待条件 。
解决死锁的基本办法
预防死锁
避免死锁
检测死锁
解除死锁
3.6 预防死锁的方法和避免死锁
1.预防死锁的方法在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一。
1)资源一次性分配； (破坏请求和保持条件 )
2)可剥夺资源； 即当某进程新的资源未满足时,
释放已占有的资源 (破坏不可剥夺条件 )
3)资源有序分配法 ；做法：系统给每类资源赋予一个编号,每一个进程按编号递增的顺序请求资源,释放则相反 (破坏环路等待条件 )
2,死锁避免
死锁避免定义,在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。
预防死锁的几种策略,会严重地损害了系统性能 。
因此要施加较弱的限制,从而获得较满意得系统性能来避免死锁 。
由于在避免死锁的策略中,允许进程动态地申请资源 。 因而,系统在进行资源分配之前预先计算资源分配的安全性 。 若此次分配不会导致系统进入不安全状态,则将资源分配给进程；否则,进程等待 。
其中最具有代表性的避免死锁算法是银行家算法 。
3,安全状态与不安全状态安全状态指系统能按某种进程顺序来为每个进程分配其所需资源,直至最大需求,使每个进程都可顺序完成 。 若系统不存在这样一个序列,则称系统处于不安全状态 。
1)安全序列一个进程序列 {P1,…,Pn}是安全的，如果对于每一个进程
Pi(1≤ i≤ n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程 Pj (j < i )当前占有资源量之和，
系统处于安全状态。
(安全状态一定是没有死锁发生的 )
2) 安全状态之例我们通过一个例子来说明安全性 。 假定系统中有三个进程 P1,P2和 P3,共有 12台磁带机 。 进程 P1总共要求 10台磁带机,P2和 P3分别要求 4台和 9台 。 假设在 T0时刻,进程 P1、
P2和 P3已分别获得 5台,2台和 2台磁带机,尚有 3台空闲未分配,如下表所示：
进 程 最 大 需 求 已 分 配 可 用
P1
P2
P3
10
4
9
5
2
2
3
3) 由安全状态向不安全状态的转换如果不按照安全序分配资源,则系统可能会由安全状态进入不安全状态 。 例如,在 T0时刻以后,P3又请求 1台磁带机,若此时系统把剩余 3台中的 1台分配给 P3,则系统便进入不安全状态 。 因为,此时也无法再找到一个安全序列,
例如,把其余的 2台分配给 P2,这样,在 P2完成后只能释放出 4台,既不能满足 P1尚需 5台的要求,也不能满足 P3尚需 6
台的要求,致使它们都无法推进到完成,彼此都在等待对方释放资源,即陷入僵局,结果导致死锁 。
安全状态与不安全状态不安全状态,不存在一个安全序列，
不安全状态一定导致死锁
4.利用银行家算法避免死锁
1)银行家算法中的数据结构
(1) 可利用资源向量 Available。 这是一个含有 m
个元素的数组,其中的每一个元素代表一类可利用的资源数目,其初始值是系统中所配置的该类全部可用资源的数目,其数值随该类资源的分配和回收而动态地改变 。 如果 Available［ j］ =K,则表示系统中现有 Rj类资源 K个 。
(2) 最大需求矩阵 Max。 这是一个 n× m的矩阵,它定义了系统中 n个进程中的每一个进程对 m类资源的最大需求 。 如果
Max［ i,j］ =K,则表示进程 i需要 Rj类资源的最大数目为 K 。
(3) 分配矩阵 Allocation。 这也是一个 n× m的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数 。 如果
Allocation［ i,j］ =K,则表示进程 i当前已分得 Rj类资源的数目为 K。
(4) 需求矩阵 Need。 这也是一个 n× m的矩阵,用以表示每一个进程尚需的各类资源数 。 如果 Need［ i,j］ =K,则表示进程
i还需要 Rj类资源 K个,方能完成其任务 。
Need［ i,j］ =Max［ i,j］ -Allocation［ i,j］
2)银行家算法设 Requesti是进程 Pi的请求向量,如果 Requesti［ j］
=K,表示进程 Pi需要 K个 Rj类型的资源 。 当 Pi发出资源请求后,
(1) 如果 Requesti［ j］ ≤Need［ i,j］,便转向步骤 2；
否则认为出错,因为它所需要的资源数已超过它所宣布的最大值 。
(2) 如果 Requesti［ j］ ≤Available［ j］,便转向步骤
(3)；否则,表示尚无足够资源,Pi须等待 。
(3) 系统试探着把资源分配给进程 Pi,并修改下面数据
Available［ j］ ∶ =Available［ j］ -Requesti［ j］ ;
Allocation［ i,j］ ∶ =Allocation［ i,j］ +Requesti［ j］ ;
Need［ i,j］ ∶ =Need［ i,j］ -Requesti［ j］ ;
(4) 系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态 。 若安全,才正式将资源分配给进程 Pi，
以完成本次分配；否则,将本次的试探分配作废,恢复原来的资源分配状态,让进程 Pi等待 。
3)安全性算法
(1) 设置两个向量,① 工作向量 Work,它表示系统可提供给进程继续运行所需的各类资源数目,它含有 m个元素,
在执行安全算法开始时,Work∶ =Available; ② Finish,它表示系统是否有足够的资源分配给进程,使之运行完成 。 开始时先做 Finish［ i］ ∶ =false; 当有足够资源分配给进程时,
再令 Finish［ i］ ∶ =true。
(2) 从进程集合中找到一个能满足下述条件的进程：
① Finish［ i］ =false; ② Need［ i,j］ ≤Work［ j］ ； 若找到,执行步骤 (3),否则,执行步骤 (4)。
(3) 当进程 Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,
Work［ j］ ∶ = Work［ i］ +Allocation［ i,j］ ;
Finish［ i］ ∶ = true;
go to step 2;
(4) 如果所有进程的 Finish［ i］ =true都满足,则表示系统处于安全状态；否则,系统处于不安全状态 。
4) 银行家算法之例假定系统中有五个进程 ｛ P0,P1,P2,P3,P4｝ 和三类资源 ｛ A,
B,C｝,各种资源的数量分别为 10,5,7,在 T0时刻的资源分配情况如图 3-15 所示 。
图 3-8 T0时刻的资源分配表
(1) T0时刻的安全性：
图 3-9 T0时刻的安全序列
(2) P1请求资源,P1发出请求向量 Request1(1,0,2)，
系统按银行家算法进行检查：
① Request1(1,0,2)≤Need1(1,2,2)
② Request1(1,0,2)≤Available1(3,3,2)
③ 系统先假定可为 P1分配资源,并修改 Available,
Allocation1和 Need1向量,由此形成的资源变化情况如图 3-
15 中的圆括号所示 。
④ 再利用安全性算法检查此时系统是否安全。
图 3-10 P1申请资源时的安全性检查
(3) P4请求资源,P4发出请求向量 Request4(3,3,0),系
① Request4(3,3,0)≤Need4(4,3,1);
② Request4(3,3,0) < Available(2,3,0),让 P4等待 。
(4) P0请求资源,P0发出请求向量 Requst0(0,2,0),系统按
① Request0(0,2,0)≤Need 0(7,4,3);
② Request0(0,2,0)≤Available(2,3,0);
③ 系统暂时先假定可为 P0分配资源，并修改有关数据，
如图 3-18 所示。
图 3-11 为 P0分配资源后的有关资源数据允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行
3.7 死锁的检测和解除
1.检测时机当进程等待时检测死锁
（其缺点是系统的开销大）
定时检测系统资源利用率下降时检测死锁
2.死锁检测算法
每个进程和资源指定唯一编号
设置一张资源分配表记录各进程与其占用资源之间的关系
设置一张进程等待表记录各进程与要申请资源之间的关系
1) 资源分配表和进程等待表资源分配表 进程等待表
r1 p2 p1 r1
r2 p5 p2 r3
r3 p4 p4 r4
r4 p1
… … … …
2)资源分配表和进程等待表当进程 P4申请资源 3时，会产生死锁吗？
3)检测算法
3.死锁的解除重要的是以最小的代价恢复系统的运行。方法如下：
1）重新启动
2）撤消进程
3）剥夺资源
4）进程回退
4.资源分配图用有向图描述进程的死锁准确、形象系统由若干类资源构成，一类资源称为一个资源类；每个资源类中包含若干个同种资源，称为资源实例资源分配图二元组 G=（ V,E）
V：结点集，分为 P,R两部分
P={p1,p2,…,pn},R={r1,r2,…,rm}
E：边的集合，其元素为有序二元组,
(pi,rj)或 (rj,pi)
表示法,
资源类,用方框表示（资源的不同类型）
资源实例,用方框中的黑圆点表示（存在于每个资源中）
进程,用圆圈中加进程名表示分配边,资源实例?进程的一条有向边申请边,进程?资源类的一条有向边
5,死锁定理如果资源分配图中没有环路，
则系统中没有死锁，如果图中存在环路则系统中可能存在死锁。
如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件。
有环有死锁有环无死锁
2,死锁定理图 3-12 资源分配图的简化
6,资源分配图化简方法如下,
1）找一个非孤立点进程结点且只有分配边，去掉分配边，将其变为孤立结点
2）再把相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配边
7.解除死锁当发现有进程死锁后,便应立即把它从死锁状态中解脱出来,常采用的方法有：
剥夺资源：从其它进程剥夺足够数量的资源给死锁进程,以解除死锁状态；
撤消进程：可以直接撤消死锁进程或撤消代价最小的进程,直至有足够的资源可用,
死锁状态消除为止；所谓代价是指优先级,
运行代价,进程的重要性和价值等 。
死锁的解除图 3-13 付出代价最小的死锁解除方法
