第四课 调度和 死锁 (Scheduling and Deadlock )
教学目的：
在多道程序系统中，一个作业从提交到执行完成，要经历多级调度，调度的好坏要影响系统的运行性能，因此调度是多道系统的关键。为了改善系统 资源 的利用率和提高系统处理能力，多道程序系统中采用多个进程的并发执行，但它也可能发生死锁的危险，研究死锁的原因和产生条件，采用预防死锁、避免死锁、检测死锁和解除死锁等多种方法防止死锁是多道程序系统重要的研究课题。
教学要求：
1 熟悉 处理机三级调度 概念和 处理机调度模型,掌握作业的状态和作业 调度的功能。
掌握进程调度的方式和功能,熟悉 调度方式和算法的选择准则,掌握七种 调度算法及适合范围。
2 掌握 死锁的定义和产生死锁的原因,掌握 死锁的四个必要条件； 熟悉 预防死锁的方法，熟练掌握银行家算法及其在死锁避免中的应用；掌握资源分配图的简化及其死锁定理，
熟悉 解除死锁的方法。
4.1调度 (Scheduling)的类型和模型作业经提交 --外存 — 作业调度 — 内存 — 进程 — 进程调度 — 运行分时系统 — 登陆 — 进程 — 调度 — 运行
4.1.1 调度类型
1。高级 (Long-term)调度 ―― 作业调度作业调度用于决定把外存输入井上处于作业后备队列上的哪些作业调入内存，并为它们创建进程、分配必要的资源，然后再将新创建的进程排在就绪队列上，准备执行。在批处理系统中，
作业是先驻留在外存的输入井上的，因此需要有作业调度。然而在分时系统中，通过键盘输入的命令和数据直接进入内存，
无需作业调度。在实时系统中，也通常无需作业调度。
宏观上：作业调度微观上：进程调度
4.1调度 (Scheduling)的类型和模型
1。 作业的状态作业从进入到运行结束，一般需要经历,提交,,,后备,,,运行,和
,完成,四个阶段。
提交状态一个作业被提交给机房后正在通过 SPOOLing系统进行输入或用户通过终端向计算机中键入其作业时所处于的状态为提交状态。
后备状态作业已经过 SPOOLing系统输入到 磁盘输入井,等待调入内存运行，此时作业处于后备状态。为了管理和调度作业，为每个作业设置一个 作业控制块 （ JCB）。 作业控制块记录了作业类型和资源要求等有关信息。作业控制块按作业类型组成一个或多个 后备作业队列 。
运行状态一个在后备作业队列的作业被作业调度程序选中后，分配必要的资源，建立一组相应的进程后，调入内存，该作业就进入运行状态。进程各状态（进程运行态、
内存进程就绪态、内存阻塞态、外存进程就绪态、外存进程阻塞态等）都对应作业运行状态。
完成状态当进程正常运行结束或因发生错误而终止时，作业进入完成状态。终止作业程序将负责善后处理。
4.1调度 (Scheduling)的类型和模型作业调度的功能：
作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转变 。
作业调度功能：
1.记录已进入系统的各作业的情况 （ JCB,Job Control
Block） ；
2.按一定的调度算法,从后备作业中选择一个或几个作业进入系统内存； （ 接纳多少个作业 —多道程序并发度？ 接纳那些个作业？ ）
3.为被选中的作业创建进程,并且为其申请系统资源；
4.作业加束后作善后处理工作 。
4.1调度 (Scheduling)的类型和模型作业控制块（ JCB，
Job Control Block）
每个作业进入系统时由系统为其建立一个作业控制块 JCB
（ Job Control
Block),它是存放作业控制和管理信息的数据结构,主要信息见右图 。
（ 在外存 ）
4.1调度 (Scheduling)的类型和模型
2。低级 (Short-term)调度 ―― 进程调度进程调度决定就绪队列中哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程的操作。进程调度是最基本的调度，任何操作系统都有进程调度。
1）非抢占式一直执行直到完毕或自阻塞。
适用于大多数的批处理系统，
但不适合实时系统。
2）抢占式时间片：
优先级（ PCB）：
短作业（进程）（ PCB,JCB）,
4.1调度 (Scheduling)的类型和模型进程调度的方式
非抢占方式采用这种调度方式时，一旦把处理机分配给某进程后，便让进程一直执行，直到该进程完成或发生某事件而被阻塞时，
才把处理机分配给其它进程，决不允许某进程抢占已经分配出去的处理机。
这种调度方式的优点是实现简单、系统开销小，适用于大多数批处理系统环境。缺点是难以满足紧急任务的要求，不适用于实时、分时系统要求。
抢占方式 （ Preemptive mode）
这种调度方式，允许进程调度程序根据某个原则，去仃止某个正在执行的进程，将已分配给进程的处理机，重新分配给另一个进程。抢占的原则有：
时间片原则。各进程按时间片运行，当一个时间片用完后，
便仃止该进程的执行而重新进行调度。这个原则适用于分时系统。
优先权原则。通常是对一些重要的和紧急的进程赋予较高的优先权。当这种进程进入就绪队列时，例如由阻塞态转换为就绪态，或从静止就绪态转为活动就绪态时，或新创建进入就绪态的进程进入就绪队列时，如果其优先权比正在执行的进程优先权高，便仃止正在执行的进程，将处理机分配给优先权高的进程，使之执行。
进程调度的功能
记录系统中所有进程的执行情况进程管理模块在各进程的 PCB表中记录系统各进程的执行情况和状态特征，并将各 PCB表根据进程状态特征和资源要求排成相应的队列，并进行动态队列转换。
选择占有处理机进程进程调度的主要功能是按照一定的策略（由它决定的调度算法），选择一个处于就绪态的进程，使其获得处理机执行。
进行进程上下文切换进程上下文实际上是进程执行活动全过程的静态描述，
一个进程的执行是在进程上下文中执行。当正在执行的进程由于某种原因要让出处理机时，系统要做上下文切换，
以使另一个进程得以执行。
3。中级 (Medium-term)调度 —— 对换目的：为了提高主存利用率和系统吞吐量。由于在进程并发执行过程中，为了充分发挥内存的效能，需将那些暂时不能运行的进程从内存调到外存盘交换区去等待，此时进程状态为挂起状态；而当这些进程又重新具备运行条件，且内存又有空闲时，由 中级调度 把它们从外存 — 内存，状态置为就绪态。
在 UNIX系统中中级调度就是存储管理中的对换，采用虚拟存储技术的分时系统往往设立中级调度。
4.1调度 (Scheduling)的类型和模型就绪 态执行 态 静止就绪阻塞 态 中级调度图：处理机三级调度作业调度 作业运行状态外存外存 (盘 )交换区作业后备状态作业提交状态 作业 完成状态终止 作业静止就绪静止阻塞中级调度主存进程调度 运行态就绪态阻塞态
4.1.2 处理机调度队列模型
1。仅有进程调度的调度队列模型在分时系统中通常仅设置了进程调度。此时系统有一个就绪队列，每个进程运行一个时间片，进程运行一个时间片后如未完成，则被放在就绪队列末尾。如进程运行中因等待某事件（例如申请 I/O而等待 I/O完成），则需排入阻塞队列，
系统因阻塞的原因不同可设几个阻塞队列。 P98图 4-1
2。有进程调度和中级调度队列模型在具有虚拟存储器技术的分时系统中（例如 UNIX系统等），
一般采用具有进程调度和中级调度的调度模型。在该模型中比第一种模型增加了中级调度，则相对于上模型也增加了外存进程就绪队列和外存进程阻塞队列。中级调度时或从内存就绪队列调到外存的就绪队列，或从内存阻塞队列调到外存阻塞队列，或从外存进程就绪队列调到内存就绪队列。
处理机调度模型 -1
3。具有高级调度和低级调度的调度队列模型在多道批处理系统中，一般处理机管理设置作业和进程两级调度。它比第一个模型增加了高级调度。模型增加了在磁盘的作业后备队列，作业调度的任务是从作业后备队列中选一个作业为它创建至少一个进程，并分配资源，将它排入内存进程就绪队列末尾。 P99图 4-2
4。同时具有三级调度的调度队列模型在通用系统的多模式 OS中，一般采用具有三级调度的调度队列模型，由于多模式 OS同时支持批处理、分时和实时处理，所以它必须具有以上模型，见图所示。
图,具有三级调度队形模型中级调度调出
CP
U
交互型作业分时间片完等待事件完成内存进程就绪队列外存进程就绪队列外存进程阻塞队列内存进程阻塞队列事件发生作业调度后备作业队列批量作业 中级调度调入中级调度调出磁盘
4.1.3 调度方式和算法的选择准则
1.面向用户的准则和评价
周转时间短（ 批处理系统 ）
它是评价批处理系统的重要性能指标。作业周转时间 Ti是指从作业提交给系统开始，到作业完成为止的这段时间间隔。
平均周转时间 T = 1/n×
平均带权周转时间 W = 1/n×
一个作业的带权周转时间 Wi=Ti/Tsi（ 作业的周转时间 Ti/实际服务时间 Tsi）
][
1
n
i
Ti
]/[
1
n
i
T siTi
提交作业 后备队列 就绪队列 CPU 等待 I/O完成作业调度进程调度周转时间调度方式和算法的选择准则 -1
响应时间快（ 分时系统 ）
响应时间是评价分时系统的性能指标。响应时间为截止时间的保证（ 实时系统 ）
它是用来评价实时系统的重要指标，截止时间是某任务必须执行的最迟时间，或完成的最迟时间。
优先权准则（ 批处理、分时和实时系统 ）
在选择批处理、分时和实时系统的调度算法时，都可引用优先权准则，以便让那些紧急的作业（或事件），得到及时的处理。在要求较严格的场合，往往还需选择抢占调度方式，才能保证紧急作业得到及时的处理。
键入请求 CPU处理请求 显示器显示请求 响应响应时间调度方式和算法的选择准则 -2
2。 面向系统的准则
达到系统设计目标系统的设计目标是选择算法的主要依据。例如批处理系统所追求的是充分发挥和提高计算机的效率，分时系统则侧重于保护用户的请求及时给予响应，
实时系统所关心的是不要丢失实时信息并给予处理。
系统吞吐量大这是用来评价批处理系统的重要指标。系统吞吐量是单位时间内完成的作业数，它与批处理作业的平均长度具有密切关系。
处理机利用率高对于大中型多用户系统，由于 CPU价格十分昂贵，所以处理机利用率成为衡量大、中型系统性能的十分重要指标，但对单用户微机或某些实时系统，该准则就不那么重要。
各类资源的平衡利用在大中型系统中，有效地利用各类资源（包括 CPU,外存,I/O设备等）也是一个重要指标，对于微型机和某些实时系统，该准则也不重要。
4.2 作业／进程调度算法进程调度（ PCB）,就绪队列如何排列？基于某种算法。
作业调度（ JCB）：
4.2.1 先来先服务 First-Come-First-Served （ FCFS）（ 作业／
进程）调度算法
FCFS是一种最简单的调度算法，可用于作业或进程调度。此算法的原则是按照作业到达后备作业队列（或进程进入就绪队列）的先后次序来选择作业（或进程）。 FCFS算法属于非抢占方式，一旦一个进程占有处理机，它就一直运行下去，直到该进程完成或者因等待某事件而不能继续运行时才释放处理机。
FCFS算法易于实现，表面上很公平。 (最好辅以图示 )
周转时间 =完成时间 -到达时间平均周转时间 =周转时间 /服务时间 P102（ 辅以时间轴）
4.2.2 短作业／进程优先 (SJF/Shortest Process Next)调度算法这种调度算法主要用于作业调度，它从作业后备队列中挑选所需运行时间
（估计值）最短的作业进入主存运行。这一算法有利于短作业，对长作业不利。采用 SJF有利于系统减少平均周转时间和平均带权周转时间。
4.2 作业／进程调度算法
P102实例，画时间轴讲解。
分析：
（ 1）平均周转、带权周转在 SJF中有改善。
（ 2）短作业 D,FCFS中周转为 1，带权周转为 5.5；
SJF中周转为 3，带权周转为 1.5。 ----有明显改善。
所以 SJF可降低平均等待时间，提高系统吞吐量。
缺点：不利于长作业； 未考虑紧迫性。
EXAMPLE,OLD WOMAN /FELLOWS ---friedcake
4.2 作业／进程调度算法作业／进程调度算法 -1
4.2.3时间片轮转 Round-Robin（ RR） 调度算法一、基本原理它用于进程调度，是分时系统采用的主要调度算法。进程调度程序总是选择就绪队列中第一个进程，允许其占有处理机一个时间片的时间。当执行的时间片用完时，调度程序便仃止该进程的执行，并将它送就绪队列的末尾，等待分配下一时间片再执行。然后把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，
在一给定的时间内，均能获得一时间片处理机执行时间。
二、时间片大小的确定在 RR算法中，时间片的大小对系统性能有很大的影响。
时间片太长 -----FCFS算法时间片太小 -----频繁切换占用 CPU。 P104与图 4-5、图 4-6。
作业／进程调度算法 -2
4.2.4 高响应比优先 Highest Response Ratio Next
(HRRN)(作业 )调度算法按照高响应比优先的原则，在每次选择作业投入运行时，先计算此时后备作业队列中每个作业的响应比 RP然后选择其值最大的作业投入运行。主要用于批处理系统。
RP值定义为：
RP＝ （已等待时间＋要求运行时间）／要求运行时间
＝ 1＋ 已等待时间／要求运行时间。
HRN算法实际上是 FCFS算法和 STF算法的折衷 。
分析：
（ 1）若干作业同时到达，短作业先调入执行；
（ 2）若干作业要求执行时间相同，先到作业先执行；
（ 3）一般情况，按计算 RP值调度。
例：作业 A,B,C,D分别在时刻 0,1（ B,C）,2提交，要求服务时间为 10，
8,10,2，则按高响应比优先调度算法有：
0时刻调度作业 A运行,10时刻，计算 B,C,D的 RPb RPcc RPd----作业 D执行
12时刻，计算 B,C的 RPb RPc ----作业 B---作业 C。
作业／进程调度算法 -3
例,假定在一个处理机上执行以下五个作业：
作业号 A B C D E
到达时间 0 1 2 3 4
运行时间 4 3 5 2 4
分别采用 FCFS,SJF,RR（ 时间片＝ 1） 和 HRN(响应比高者优先 )
四种调度算法时,试做,（ 1） 画出调度图；
（ 2） 计算每个作业的周转时间和带权周转时间 ；
（ 3）计算平均周转时间和平均带权周转时间。
调度图：
T 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
FCFS A A A A B B B C C C C C D D E E E E
SJF A A A A D D B B B E E E E C E E E E
RR A B C D E A B C D E A B C E A C E C
HRN A A A A B B B D D C C C C C E E E E
例解：
作业号
A B C D E 平均到达时间
0 1 2 3 4
运行时间
4 3 5 2 4
完成时间
4 ① 7 ② 12 ③ 14 ④ 18 ⑤
周转时间
4 6 10 11 14 9
F C F S
带权周转时间
1 2 2 5,5 3,5 2,8
完成时间
4 ① 9 ③ 18 ⑤ 6 ② 13 ④
周转时间
4 8 16 3 9 8
SJF
带权周转时间
2 2,6 7 3,1 1,5 2,2 5 2,1
例解 -1
作业号
A B C D E 平均到达时间
0 1 2 3 4
运行时间
4 3 5 2 4
完成时间
15 ③ 12 ② 18 ⑤ 9 ① 17 ④
周转时间
15 11 16 6 13 1 2,4
RR
带权周转时间
3,7 5 3,6 7 3,2 3 3,2 5 3,3 7
完成时间
4 ① 7 ② 14 ④ 9 ③ 18 ⑤
周转时间
4 6 12 6 14 8,4
H R R N
带权周转时间
1 2 2,4 3 3,5 2,3 8
例解 -2
高响应比优先 (HRRN)(作业 )调度算法计算：
T=0,只有作业 A已到达，调度作业 A运行 。
T=4,作业 A完成，作业 B,C,D,E已到达，计算作业 B,C,D、
E响应比 RP分别为,1+3/3,1+2/5,1+1/2,1+0/4，作业 B响应比最大调度运行。
T=7,作业 B完成，作业 C,D,E已到达，计算作业 C,D,E响应比 RP分别为,1+5/5,1+4/2,1+3/4，作业 D响应比最大调度运行。
T=9,作业 D完成，作业 C,E已到达，计算作业 C,E响应比 RP分别为,1+7/5,1+5/4，作业 C响应比最大调度运行。
T=14,作业 C完成，只有作业 E未完成，调度作业 E运行 。
作业／进程调度算法 -4
4.2.5优先权 (Priority)调度算法一、算法类型
（ 1）抢占式：主要用于严格的实时系统中
（ 2）非抢占式：主要用于批处理和不严格的实时系统中按照进程的优先权大小来调度，使高优先权进程得到优先处理的调度策略称为优先权调度算法 。
二、优先权的类型进程的优先权的设置可以是静态的，也可以是动态的。
（ 1） 静态优先权 在进程创建时确定，且的在整个生命期中保持不变。确定进程优先权的依据有：
进程类型，通常系统进程（例如对换进程）的优先权高于一般用户态进程的优先权；
进程对资源的需求，如进程执行时间及内存需要省的进程应赋予较高的优先权；
根据用户要求，由用户的紧迫程度及用户所付费用的多少来确定进程的优先权。
（ 2）动态优先权 是指在创建进程时所赋予的优先权，可以随进程的推进而改变，以便获得更好的调度性能。改变优先权的因数，随系统不同而不同，
最常考虑的因素的进程的等待时间，已使用处理机的时间，或者资源使用情况等。
作业／进程调度算法 -5
在 UNIX系统 V中处于核心态和用户态的优先权不同。进程处于核心态的优先权高，处于核心态的进程优先权又分二类，一类是因等待磁盘 I/O,等待缓冲器等不可中断优先权最高，而另一类因等待 TTY输入输出等可中断优先权其次。处于用户态的优先权相对较低，用户态优先权又分为 n+1级优先权。优先数为 0级的优先权最高，优先数为 n级的优先权最低。
用户态优先权是可变的，它随着占用 CPU时间的增加而降低。
核心每隔 1秒钟便按下述公式对各进程重新计算其用户优先数
（优先数与优先权成反比关系）。
优先数＝最近使用 CPU的时间／ 2＋基本用户优先数。
上机实验：要求按动态优先权调度做进程调度仿真。
实验内容另讲。
4.2.6．多级队列调度算法（批处理和分时系统结合使用）
多级队列调度是根据作业的性质和类型的不同，将就绪队列再分为若干个子队列，所有的作业（或进程）按其性质排入相应的队列中，而不同的就绪队列采用不同的调度算法。
作业／进程调度算法 -6
例如前后台系统可以建立两个就绪队列，批处理作业所建立进程进入后台就绪队列；交互型作业所建立的进程进入前台就绪队列。前台采用时间片轮转算法，进程按 FCFS等策略排序，后台采用优先权高优先的调度算法或者短作业优先的调度算法。
对多级就绪队列调度策略有两种，一种是各就绪队列按进程性质赋予不同的优先权，优先权高的就绪队列的进程优先被调度，例如上例中前台就绪队列的优先权比后台就绪队列的优先权高，所以前台队列中的进程优先被调度。而只有当优先权高的就绪队列空时，方才调度优先权其次的就绪队列进程，在上例中只有前台队列空时，才调度后台就绪队列。
这样，只有较高优先权的就绪队列都空时才调度最低优先权就绪队列的进程。
另一种调度就绪队列的方式是为每个队列分配一定的占用
CPU时间的比例。如在上例中为前台队列分配 80％的 CPU时间，
给后台队列分配 20％的 CPU时间。
作业／进程调度算法 -7
7。多级反馈 (Feedback)队列调度算法
前面介绍的各种用作进程调度的算法，都有在一定的局限性，如短进程优先算法仅照顾了短进程而怠慢了长进程。况且对进程运行的长短，往往难以正确估计，所以短进程优先的调度算法无法正确使用。而多级反馈队列调度算法，则不必事先知道各种进程所需的执行时间，仍能基本满足短进程优先和 I/O频繁的进程优先的需要，因而是目前公认的较好的一种进程调度算法。在 UNIX系统,WindowsNT,OS/2中都采用了类似的调度算法。
WindowsNT采用可抢占动态优先级多级就绪队列调度算法。
NT执行体支持 32级优先级，并将它们分成两类，实时优先级
（ 16－ 31）和可变优先级（ 1－ 15）,0级为系统保留。每个优先级一个就绪队列，高序号队列为高优先级，调度程序从高优先级的队列开始往下找，如高优先级队列为空时才再往下找，直至找到一个线程。
作业／进程调度算法 -8
各个就绪队列中进程执行时间片的大小也各不相同，在优先级越高的队列中，每个进程的执行时间片就规定得越小。
当一个线程执行完一个完整的时间段后被中断抢占处理器，
而被抢占的线程优先级降低一级而进入下级就绪队列，如此继续，直至降到线程的基本优先级。而一个线程从阻塞态变为就绪态时要提高优先级，提高的幅度与等待的事件有关。如等待键盘输入所提高的幅度要大于等待磁盘 I/O。
在 NT中，交互式线程处于高优先级,I/O型线程处于中间优先级，计算型线程处于低优先级，系统还设置一个空闲线程，其优先级为 0，是优先级最低的线程，只要处理空闲，就执行该线程。
图,多级反馈队列就绪队列 1 时间片 S1 时间片完时间片完就绪队列 2 时间片 S2>S1
运行运行运行就绪队列 n 时间片 Sn>Sn-1
完成完成完成时间片完阻塞队列 i
阻塞阻塞阻塞事件发生
4.6 死锁的基本概念在两个进程并发执行时，当 PA进程占有 R1,PB进程占用 R2
时,PA要求 R2,由于 PB已占 R2有而得不到,PA进程只有等待； PB申请 R1,由于 PA已占有 R1,而得不到,PB进程只有等待，就出现了死等的情况。哲学家进餐。
例 1：有两个进程 PA和 PB,它们在运行的过程中要共享使用两个独占设备 R1和 R2。 设 SR1,表示设备 R1可用,初值为 1； SR2表示设备 R2可用,两个进程并发执行的程序如下：
死锁的概念例 2：三个进程共享使用一台打印机的程序若有一个进程少写了一个 V/signal操作 。
死锁的概念例 3：生产者－消费者问题
当缓冲区满时,生产者仍可顺利执行 p(mutex)操作,
于是它对缓冲区有控制权,
然后,当它执行 p(empty)
时,由于没有空缓冲区被挂起 。 能将这个生产者释放的是有一个消费者从缓冲区中取走一个产品,并执行 v(empty)操作,但由于缓冲区已被生产者占用,
出现了死锁 。
4.6 死锁的基本概念死锁的定义,
死锁就是两个或两个以上的进程等候着一个永远不会发生的事件时所取的一种系统状态 。 因竞争资源而造成的一种僵局,若无外力作用,这些进程将永远不能推进 。
4.6.1死锁的原因和条件
1。死锁的原因
竞争资源引起死锁在多道程序系统，多个进程共享系统的资源。系统资源分为二类，一类是不可抢占的资源，如打印机、磁带机等。当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自动释放。另一类是可抢占的资源，如 CPU,内存等。由于系统拥有的不可抢占的资源有限，多个进程共享竞争不可抢占的资源就可能引起死锁。
竞争临时性资源（软件资源） /消耗性资源。 P120图 4-15
进程推进顺序不当引起死锁在多道程序系统中，并发执行的进程推进序列不可予测，有些推进顺序，
进程可以顺利完成，这些推进顺序是合法的；而有的推进顺序会引起进程无限期地等待永远不会发生的条件而不能向前推进，造成了死锁。
死锁的原因和条件 -1
进程推进顺序不当引起死锁例：
进程 P和 Q并发执行，进程 P和 Q程序如下：
Process P Process Q
..,.
Get A Get B
..,.
Get B Get A
..,.
Release A Release B
..,.
Release B Release A
..,.
进程 P和 Q按路径 1,2,5,6推进顺序合法，按 3,4推进顺序非法，见下图：
进程推进顺序不当引起死锁例：
Progress
of Q
Release
A
Release
B
Get A
Get B
Get A Get B Release A
Release B
Progress
of P
A
Required B Required
A
Required
B
Required
deadlock
inevitable
1 2
3
4
5
6
P and Q
want B
P and Q
want A
死锁的原因和条件 -1
4.6.2 产生死锁的必要条件（ Conditions for Deadlock ）
互斥（ Mutual exclusion ）条件,一个资源一次只能被一个进程所使用，即是排它性使用。进程在访问某些资源时不可避免地产生互斥性。
不可抢占（ No preemption ）条件,一个资源仅能被占有它的进程所释放，而不能被别的进程强占。
请求和保持（ Hold-and-wait ）条件,进程已经保持了至少一个资源，但又提出了新的资源要求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对已经获得的其它资源保持不放。
环路等待（ Circular wait ）条件,当每类资源只有一个时，
在发生死锁时，必然存在一个进程 -资源的环形链。如一系统状态的资源分配图所示,P1正在等待一个 P2 占用的资源 R2，
P2正在等待一个 P1占用的资源 R1。
死锁的原因和条件 -2
资源分配图由结点和边组成。结点有二类，一类是进程结点，用园圈表示；另一类是资源结点，用小方框表示一类资源，用方框中的小圈表示资源数。边也有二类，一类是分配边，它由资源结点指向进程结点，另一类是申请边，它由进程结点指向资源结点。
返回
R1
R2
P1 P2
死锁的原因和条件 -3
4.6.3 处理 死锁的基本方法
a,死锁的预防静态方法：在进程执行前采取的措施，通过设置某些限制条件，去破坏产生死锁的四个必要条件之一或几个，防止发生死锁。
B.死锁的避免动态的方法：在进 程 执行过程中采取的措施，不需事先采取限制措施破坏产生死锁的必要条件，而是在进程申请资源时用某种方法去防止系统进入不安全状态，从而避免发生死锁。银行家算法。
C.死锁的检测和解除这种方法预先并不采用任何限制措施，允许系统在运行过程中发生死锁，但可通过系统设置的检测机构及时检测死锁的发生，如检测到死锁，则采用撤消进程等死锁解除方法使系统正常工作。
4.7 死锁的预防 (Deadlock Prevention)和避免预防死锁的方法是破坏四个产生死锁的必要条件之一。
1。 破坏互斥条件互斥使用是资源本身特征所决定的。使用硬软件结合可改变资源本身特性，例如采用 SPOOLing技术可将,独享,打印机改变为,共享,的打印机。
2。 破坏不可抢占条件抢占式调度法主要用于处理机和存贮器资源调度，它们的状态容易保存和恢复。但此法对外部设备和私存数据不宜使用。 P1占有 R1,P2在申请 R1时,P1不释放，产生死锁； 破坏不可 剥夺条件，系统强行剥夺 R1---P2,P1以后执行时，需退回申请 R1之前，造成 P1执行产生死尸。
死锁的预防 -1
3。 破坏请求和保持条件系统可采用 资源静态予分配方式 来破坏请求保持条件。系统要求所有进程一次性地申请在整个运行过程中全部资源，
若系统有足够资源满足给进程，则在运行前，一次性将其所需要的所有资源分配给该进程。这样该进程在整个运行期间，
便不再提出资源要求，从而摒弃了请求条件。这种预防死锁的方法，优点是简单、易予实现且很安全，但其资源利用率很低，进程也延迟运行。定义数组（ Basic,Fortran）。 实际现在的 OS。
4。 破坏循环等待条件有序资源使用法该方法将所有的资源按类型进行线性排队，并赋予不同的序号。例如令输入机的序号为 1，打印机序号为 2，磁盘机序号为 3等。
死锁的预防 -2
所有进程对资源的请求必须严格按资源序号递增的次序提出。
这样在所形成的资源分配图中不可能再出现环路，因而摒弃了,环路等待,条件，在采用这种策略时总有一个进程占据了较高序号的资源，它继续请求的资源必然是空闲的，因而进程可以一直向前推进。这种预防死锁的策略可以提高资源利用率，但在进程使用各类资源的顺序与系统规定的顺序不同时会造成资源浪费的情况。
资源按级分配法该方法是把资源递增排序成若干等级（如 L1,L2……,Lm），
其中每级可包含几类资源，要求每个进程在获得了 Lj级中资源之后,它才能申请更高级的 LK（ LK＞ Lj） 级中的资源；如果它还需申请比 LK级低的 LI级（ LI<LK） 资源，则必须先释放所有大于 LI级的资源。该方法是 Haveder 1968年在设计 IBM／
360 OS时提出的，资源共分三级，第一级数据集或文件，第二级主存，第三级 I/O设备。
4.7.2 系统的安全状态该方法允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会导致系统从安全状态向不安全状态转换，便可将资源分配给进程；否则不分配资源，进程必须阻塞等待。从而避免发生死锁。
1.系统的 安全状态动态分配资源，分配前，先考虑安全性，若预分配后 — 安全态，则可以分配，非安全态，则不分配。
安全状态是指系统的一种状态，在此状态开始系统能按某种顺序（例如
P1,P2…… Pn） 来为各个进程分配其所需资源，直至最大需求，使每个进程都可顺序地一个个地完成。这个序列（ P1,P2……,Pn） 称为 安全序列 。若系统此状态不存在一个安全序列，则称系统处于 不安全状态 。
2 实例：
假如系统中有 P1,P2和 P3三个进程和 12台磁带机。各进程最大需求和 T0时刻分配状态如下：
进程 最大需求 已分配 还需请求 可用
P1 10 5 5 3
P2 4 2 2
P3 9 2 7
死锁的避免 -1
分析 T0状态，利用现有空闲资源数 3，能否可以找到一个安全序列,即系统按此进程序列分配资源，每个进程都可顺利完成，其步骤如下：
（ 1）先将可用的 3台磁带机中 2台分配给 P2,P2满足了最大的资源需求，在有限时间内推进完毕，释放它占有的 4台资源，使可用资源数量增至 5台。
（ 2）再将可用的 5台磁带机分配给 P1,P1满足了最大的资源需求，在有限时间内推进完毕，释放它占有的 10台资源，使可用资源数量增至 10台。
（ 3）最后将可用 10台中 7台磁带机分配给 P3,P3推进完毕，释放它占有的
9台资源，使可用资源数量增至 12台。
这样三进程可按照（ P2,P1,P3） 序列顺序地一个个执行完成，则（ P2、
P1,P3） 序列是安全序列，所以在 T0时刻，系统处于安全状态。
2。由安全状态向不安全状态的转换如果在 T0 状态不按安全序列进行分配，可能会导致系统进入一个不安全状态，例如在 T0状态下 P3中申请 2台磁带机。如系统实施此次分配使系统状态由 T0变为 T1状态，分析 T1状态安全情况。
死锁的避免 -2
T1时刻状态：
进程 最大需求 已分配 还需请求 可用
P1 10 5 5 > 1
P2 4 2 2 > 1
P3 9 4 5 > 1
因为找不到一个安全序列使所有进程顺序地一个个地运行完毕，所以 T1状态是不安全状态，由于实施分配给 2台磁带机给 P3的操作会引起系统状态由安全状态 T0向不安全状态下的转换，所以为了避免死锁，上述的分配只是安全检测，检测后判定这样的申请不能满足,P3为申请 2台磁带机而必须阻塞等待。
4.7.3利用银行家算法避免死锁最具代表的避免死锁算法是 Dijkstra的银行家算法，这是由于该算法用于银行系统现金贷款的发放而得名。
银行家算法的数据结构
可用资源向量 Available [m]---0..m-1
m为系统中资源种类数,Available[j]=k表示系统中第 j类资源数为 k个。
最大需求矩阵 Max[n,m]— n行 m列
n为系统中进程数,Max[i,j]=k表示进程 i对 j类资源的最大需求数为中 k。
已分配矩阵 Allocation[n,m]
它定义了系统中每一类资源当前已分配给每一进程资源数，
Allocation[i,j]=k表示进程 i已分得 j类资源的数目为 k个。
进一步需求矩阵 Need[n,m]
它表示每个进程尚需的各类资源数,Need[i,j]=k 表示进程
i还需要 j类资源 k个。 Need[i,j]=Max[i,j]-Allocation[i,j]
利用银行家算法避免死锁 -1
银行家算法
假设在进程并发执行时进程 i提出请求 j类资源 k个后，
表示为 Requesti[j]=k。 系统按下述步骤进行安全检查：
如果 Requesti≤Need i则继续以下检查，否则显示需求申请超出最大需求值的错误。
如果 Requesti≤Available 则继续以下检查，否则显示系统无足够资源,Pi阻塞等待。
系统试探把要求的资源分配给进程 i并修改有关数据结构的值：
Available = Available-Requesti ；
Allocationi =Allocationi+Requesti ；
Needi=Needi-Requesti ；
利用银行家算法避免死锁 -2
系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态，若安全，才正式将资源分配给进程 i,以完成本次分配；否则将试探分配作废，恢复原来的资源分配状态，
让进程 Pi等待。
③安全性算法安全性算法执行步骤如下：
A.初始化设置工作向量 Work[m]表示系统可提供的各类资源数目，
用以保护原数据结构有关值。 Work = Available,设置完成标志向量 Finish[n]。 Finish[i] = false 表示 i进程尚末完成，如值为 true则表示进程 i已完成。
B.从进程集合 n中找到一个能满足下述二个条件,Finish[i] =
false和 Necdi≤Work,如找到则执行步骤 C,如找不到同时满足以上二条件的进程则执行步骤 D。
利用银行家算法避免死锁 -3
C.当进程 i获得资源后可顺利执行直到完成，并释放出分配给它的资源，表示如下：
work = work+Allocationi ； Finish[i]=true ； 转执行步骤 B。
D.如果所有的 Finish[i]＝ ture,则表示系统处于安全状态，
否则系统处于不安全状态。
银行家算法 例：
假定系统中有五个进程 {P0,P1,P2,P3,P4}和三种类型资源
{A,B,C},每一种资源的数量分别为 10,5,7。各进程的最大需求,T0时刻资源分配情况如下 所示。
Max Allocation Need Available
A B C A B C A B C A B C
P0 7 5 3 0 1 0 7 4 3 3 3 2
P1 3 2 2 2 0 0 1 2 2
P2 9 0 2 3 0 2 6 0 0
P3 2 2 2 2 1 1 0 1 1
P4 4 3 3 0 0 2 4 3 1
试问,① T0时刻是否安全？
② P1请求资源 Request1(1,0,2)是否允许？
③ P4请求资源 Request4(3,3,0)是否允许？
银行家算法 例 -1
T0时刻是否安全？
从表中可找出一个序列 (P1,P3,P4,P2,P0） 使各进程 顺序地一个个地执行 完成 。
Max Allocation Need Available Available
(分配资源前 ) (释放 资源 后）
A B C A B C A B C A B C A B C
P0 7 5 3 0 1 0 7 4 3 =< 10 4 7? 10 5 7
P1 3 2 2 2 0 0 1 2 2 =< 3 3 2? 5 3 2
P2 9 0 2 3 0 2 6 0 0 =< 7 4 5? 10 4 7
P3 2 2 2 2 1 1 0 1 1 =< 5 3 2? 7 4 3
P4 4 3 3 0 0 2 4 3 1 =< 7 4 3? 7 4 5
安全序列为 {P1,P3,P4,P2,P0},T0时刻系统是安全的。
P1请求资源 Request1(1,0,2)可否允许？
银行家算法 例 -2
Request1(1,0,2)≤Need 1(1,2,2),P1请求在最大需求范围内。
Request1(1,0,2)≤ Available(3,3,2),可用资源可满足 P1请求需要。
试探把要求的资源分配给进程 P1并修改有关数据结构的数值：
Available = Available(3,3,2)－
Request1(1,0,2)=Available(2,3,0)；
Need1 = Need1(1,2,2)－ Request1(1,0,2)= Need1(0,2,0)；
Allocation1
=Allocation1(2,0,0)+Request1(1,0,2)=Allocation1(3,0,2)；
利用安全性算法检查试探将资源分配后状态的安全性如下：
银行家算法 例 -3
Max Allocation Need Available Available
(分配资源前 ) (释放 资源 后）
A B C A B C A B C A B C A B C
P0 7 5 3 0 1 0 7 4 3 =< 10 4 7? 10 5 7
P1 3 2 2 3 0 2 0 2 0 =< 2 3 0? 5 3 2
P2 9 0 2 3 0 2 6 0 0 =< 7 4 5? 10 4 7
P3 2 2 2 2 1 1 0 1 1 =< 5 3 2? 7 4 3
P4 4 3 3 0 0 2 4 3 1 =< 7 4 3? 7 4 5
因为先分配资源给 P1进程符合按安全序列 {P1,P3,P4,P2,P0}
分配资源，所以试探将资源分配给进程 P1后的状态是安全的，
可将资源分配给进程 P1。
P4请求资源 Request4(3,3,0)是否允许？
Request4(3,3,0)≤Need 4(4,3,1),P4请求在最大需求范围内。
Request4(3,3,0)≤Available(2,3,0) 不成立，即可用资源暂不能满足 P4请求资源需要,P4阻塞等待。
4.8死锁的检测 (Deadlock Detection)
死锁的避免算法增加了系统的开销，死锁的检测采用资源分配图的简化判断是否发生了不安全状态。如发现系统处于不安全状态时，即执行死锁解除的策略，采用此法开销相对减少。
1。资源分配图的简化,
系统处于某 S状态时可用资源分配图表示，可用资源分配图简化来判断系统是否处于死锁状态。资源分配图简化的方法如下：在资源分配图中找一个既不阻塞又非孤立的进程结点
PI（ 如某进程既无已分配的资源也不需申请资源，即既无分配边又无申请边，则该进程结点是孤立结点），让它获得所需资源而继续运行直至完毕，再释放它拥有的所有的资源，
这相当于取消 PI的分配边和请求边，使它成为孤立结点。
经过以上简化，如所有的进程结点都是孤立结点则称资源分配图是可完全简化的。若不能通过任何过程使该图完全简化，
则该图是不可完全简化的。资源分配图简化如 下图,
R1 R2 R1 R2
。。
P1
资源分配图的简化例,
。。
。
P1
P2
。 。
。
P1
P2
。。
。。
。
P2
。。
R1 R2
死锁的检测 -1
2。死锁定理：
S为死锁状态的充分条件是：尚且仅当 S状态的资源分配图是不可完全简化的，该充分条件称为死锁定理。
3。死锁检测的数据和算法 类似于银行家算法。
（ 5）死锁的解除
当检测死锁的软件 判别死锁存在时,就要解除死锁,使系统从死锁中恢复。
第一种是强制性地从系统中撤消一个或多个死锁的进程以断开循环等待链,并收回分配给终止进程的全部资源供剩下的进程使用。借助于撤消进程来解除死锁可以使用两种方法。
一种是撤消全部的死锁进程，这显然会断开死锁环路，但代价太大。另一种方法是逐个撤消死锁的进程直至死锁环路消除。这里存在一个按照什么原则进行逐个撤消进程的问题。
目前较实用而又简便的方法是撤消那些代价最小的进程。所谓影响一个进程的撤消代价因素有该进程的优先权，该进程运行到今的运行代价（包括 CPU时间，使用资源的种类和时间等）、与相关的作业类型和外部代价等。
死锁的解除 -1
死锁恢复的另一种办法是使用一个有效的挂起和解除机构来挂起一些死锁的进程,其实质是从被挂起的进程那里抢占资源以解除死锁，许多学者认为在此领域的研究工作比起其它死锁恢复的办法更为重要。例如一个系统提供了检查点和重新启动的便利的话，我们可以暂时仃止一个系统，而后从各进程的最近的检查点（系统保留了检查点的状态）逐次地重新启动。这既可以从死锁中恢复，又使进程损失最小（从检查点以后的损失）。但许多系统还没有此功能，在 IBM4300系列等机器上提供了此类功能。
习题
1,在操作系统中处理机管理由作业管理和进程管理两部分组成,
作业管理把作业流分成提交,后备,运行,完成四个状态,
进程管理把进程分成就绪,执行,阻塞三个基本状态 。 作业由后备状态到运行状态由﹎﹎ B﹎﹎ 完成,进程由就绪状态到执行状态由﹎﹎ C﹎﹎,用户进程的祖先进程由﹎﹎ E﹎﹎ 建立的 。
A,B,C,D,E,(1)作业调度程序； (2)进程调度程序； (3)存储管理程序； (4)输入输出程序； (5)假脱机 （ SPOOLing） 处理程序； (6)交通程序； (7)设备管理程序 。
2,操作系统的主要性能参数：﹎﹎ A﹎﹎ 指的是单位时间内系统处理的作业量 。 ﹎﹎ B﹎﹎ 指的是从作业或命令的输入到其结束的间隔时间,在分析性能时常用其倒数 。 ﹎﹎ C﹎﹎ 指的是在一个给定的时间内,系统的一个指定成份被使用的时间比例 。
A,B,C,(1)周转时间； (2)处理时间； (3)消逝时间； (4)利用率； (5)生产率； (6)吞吐量 。
习题 -1
3,在所学的调度算法中,对所有进程和作业都是公平合理的调度算法是﹎﹎ A﹎﹎； 最有利于提高系统吞吐量的作业调度算法是﹎﹎ B﹎﹎； 能兼顾作业等待时间和作业执行时间调度算法是﹎﹎ C﹎﹎； 最有利于提高资源的使用率,能使短作业,
长作业及交互作业用户都比较满意的调度算法是﹎﹎ D﹎﹎；
为实现人机交互作用应采用调度算法是﹎﹎ E﹎﹎； 能对紧急作业进行及时处理的调度算法是﹎﹎ F﹎﹎ 。
A,B,C,D,(1)FCFS调度算法； (2)短作业优先调度算法； (3)
时间片轮转法； (4)多级反馈队列调度算法； (5) 高响应比优先算法； (6)基于优先权的剥夺调度算法 。
4.假定在一个处理机上执行以下五个作业，
作 业 号 1 2 3 4 5
到 达 时 间 0 2 4 6 8
运 行 时 间 3 6 4 5 2
当分别采用 FCFS,SJF(短作业优先 )和 HRRN（ 响应比高者优先）
三种调度算法时，试问,
习题 -2
⑴ 三种调度算法调度次序为﹎﹎ A﹎﹎,﹎﹎ B﹎﹎ 和﹎﹎ C﹎﹎；
⑵ 采用 FCFS调度算法时 1--5号作业的周转时间为﹎﹎ D1﹎﹎,
﹎﹎ E1﹎﹎,﹎﹎ F1﹎﹎,﹎﹎ G1﹎﹎ 和﹎﹎ H1﹎﹎； 采用
SJF调度算法时 1--5号作业的周转时间为﹎﹎ D2﹎﹎,﹎﹎ E2
﹎﹎,﹎﹎ F2﹎﹎,﹎﹎ G2﹎﹎ 和﹎﹎ H2﹎﹎； 采用 HRRN调度算法时 1--5号作业的周转时间为﹎﹎ D3﹎﹎,﹎﹎ E3﹎﹎,
﹎﹎ F3﹎﹎,﹎﹎ G3﹎﹎ 和﹎﹎ H3﹎﹎；
⑶ 三种调度算法的平均周转时间为﹎﹎ I﹎﹎,﹎﹎ J﹎﹎ 和﹎
﹎ K﹎﹎ 。
A,B,C,(1)1 2 3 4 5 ; (2)5 1 3 4 2 ; (3)1 5 3 4 2 ;
(4)1 2 5 3 4 ; (5)1 2 3 5 4 ;
D1---H1,D2---H2,D3---H3,(1)1 (2)2 (3)3 (4)4 (5)5
(6)6 (7)7 (8)8 (9)9 (10)10 (11)11 (12)12 (13)13
(14)14 (15)15 (16)16 (17)17 (18)18 (19)19 (20)20
I,J,K,(1)7.0 (2)7.6 (3)8.0 (4)8.6 (5)9.0 (6)9.6
(7)10.0 (8)11.0
习题 -3
5,产生死锁的基本原因是﹎﹎ A﹎﹎ 和﹎﹎ B﹎﹎,产生死锁的四个必要条件是互斥条件﹎﹎ C﹎﹎,不剥夺条件和﹎﹎ D﹎
﹎ 。
A,(1)资源分配不当； (2)系统资源不足； (3)作业调度不当；
(4)资源的独占性 。
B,(1)进程推进顺序非法； (2)进程调度不当； (3)系统中进程太多； (4)CPU运行太快 。
C,(1)请求和阻塞条件； (2)请求和释放条件； (3)请求和保持条件； (4)释放和阻塞条 件； (5)释放和请求条件 。
D,(1)线性增长条件； (2)环路条件； (3)无序释放条件； (4)
有序请求条件； (5) 无序请求条件 。
习题 -4
6．预防死锁的论述中，﹎﹎ A﹎﹎ 条是正确的论述。
(1)由于产生死锁的基本原因是系统资源不足，因而预防死锁的有效方法，是根据系统规模，配置足够的系统资源。
(2)由于产生死锁的另一种基本原因是进程推进顺序不当，因而预防死锁的有效方法，是使进程的推进顺序合法。
(3)因为只要系统不进入不安全状态，便不会产生死锁，故预防死锁的有效方法，是防止系统进入不安全状态。
(4)可以通过破坏产生死锁的四个必要条件之一或其中几个的方法，来预防发生死锁。
习题 -5
7,试描述避免死锁的银行家算法,若系统运行中出现下述资源分配情况进程 ALLOCATION NEED AVAILABLE
A B C D A B C D A B C D
P0 0 0 3 2 0 0 1 2 1 6 2 2
P1 1 0 0 0 1 7 5 0
P2 1 3 5 4 2 3 5 6
P3 0 3 3 2 0 6 5 2
P4 0 0 1 4 0 6 5 6
该系统是安全,安全序列为﹎﹎ A﹎﹎,﹎﹎ B﹎﹎,﹎﹎ C﹎﹎,
﹎﹎ D﹎﹎,﹎﹎ E﹎﹎ 。
如果进程 P2此时提出资源申请 （ 1,2,2,2）,系统﹎﹎ F﹎
﹎ 将资源分配给它 。
A---E,(1)P0 (2)P1 (3)P2 (4)P3 (5)P4
B,(1) 能 (2) 不能
8,试述死锁产生的原因和必要条件及解决死锁的方法 。
教学目的：
在多道程序系统中，一个作业从提交到执行完成，要经历多级调度，调度的好坏要影响系统的运行性能，因此调度是多道系统的关键。为了改善系统 资源 的利用率和提高系统处理能力，多道程序系统中采用多个进程的并发执行，但它也可能发生死锁的危险，研究死锁的原因和产生条件，采用预防死锁、避免死锁、检测死锁和解除死锁等多种方法防止死锁是多道程序系统重要的研究课题。
教学要求：
1 熟悉 处理机三级调度 概念和 处理机调度模型,掌握作业的状态和作业 调度的功能。
掌握进程调度的方式和功能,熟悉 调度方式和算法的选择准则,掌握七种 调度算法及适合范围。
2 掌握 死锁的定义和产生死锁的原因,掌握 死锁的四个必要条件； 熟悉 预防死锁的方法，熟练掌握银行家算法及其在死锁避免中的应用；掌握资源分配图的简化及其死锁定理，
熟悉 解除死锁的方法。
4.1调度 (Scheduling)的类型和模型作业经提交 --外存 — 作业调度 — 内存 — 进程 — 进程调度 — 运行分时系统 — 登陆 — 进程 — 调度 — 运行
4.1.1 调度类型
1。高级 (Long-term)调度 ―― 作业调度作业调度用于决定把外存输入井上处于作业后备队列上的哪些作业调入内存，并为它们创建进程、分配必要的资源，然后再将新创建的进程排在就绪队列上，准备执行。在批处理系统中，
作业是先驻留在外存的输入井上的，因此需要有作业调度。然而在分时系统中，通过键盘输入的命令和数据直接进入内存，
无需作业调度。在实时系统中，也通常无需作业调度。
宏观上：作业调度微观上：进程调度
4.1调度 (Scheduling)的类型和模型
1。 作业的状态作业从进入到运行结束，一般需要经历,提交,,,后备,,,运行,和
,完成,四个阶段。
提交状态一个作业被提交给机房后正在通过 SPOOLing系统进行输入或用户通过终端向计算机中键入其作业时所处于的状态为提交状态。
后备状态作业已经过 SPOOLing系统输入到 磁盘输入井,等待调入内存运行，此时作业处于后备状态。为了管理和调度作业，为每个作业设置一个 作业控制块 （ JCB）。 作业控制块记录了作业类型和资源要求等有关信息。作业控制块按作业类型组成一个或多个 后备作业队列 。
运行状态一个在后备作业队列的作业被作业调度程序选中后，分配必要的资源，建立一组相应的进程后，调入内存，该作业就进入运行状态。进程各状态（进程运行态、
内存进程就绪态、内存阻塞态、外存进程就绪态、外存进程阻塞态等）都对应作业运行状态。
完成状态当进程正常运行结束或因发生错误而终止时，作业进入完成状态。终止作业程序将负责善后处理。
4.1调度 (Scheduling)的类型和模型作业调度的功能：
作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转变 。
作业调度功能：
1.记录已进入系统的各作业的情况 （ JCB,Job Control
Block） ；
2.按一定的调度算法,从后备作业中选择一个或几个作业进入系统内存； （ 接纳多少个作业 —多道程序并发度？ 接纳那些个作业？ ）
3.为被选中的作业创建进程,并且为其申请系统资源；
4.作业加束后作善后处理工作 。
4.1调度 (Scheduling)的类型和模型作业控制块（ JCB，
Job Control Block）
每个作业进入系统时由系统为其建立一个作业控制块 JCB
（ Job Control
Block),它是存放作业控制和管理信息的数据结构,主要信息见右图 。
（ 在外存 ）
4.1调度 (Scheduling)的类型和模型
2。低级 (Short-term)调度 ―― 进程调度进程调度决定就绪队列中哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程的操作。进程调度是最基本的调度，任何操作系统都有进程调度。
1）非抢占式一直执行直到完毕或自阻塞。
适用于大多数的批处理系统，
但不适合实时系统。
2）抢占式时间片：
优先级（ PCB）：
短作业（进程）（ PCB,JCB）,
4.1调度 (Scheduling)的类型和模型进程调度的方式
非抢占方式采用这种调度方式时，一旦把处理机分配给某进程后，便让进程一直执行，直到该进程完成或发生某事件而被阻塞时，
才把处理机分配给其它进程，决不允许某进程抢占已经分配出去的处理机。
这种调度方式的优点是实现简单、系统开销小，适用于大多数批处理系统环境。缺点是难以满足紧急任务的要求，不适用于实时、分时系统要求。
抢占方式 （ Preemptive mode）
这种调度方式，允许进程调度程序根据某个原则，去仃止某个正在执行的进程，将已分配给进程的处理机，重新分配给另一个进程。抢占的原则有：
时间片原则。各进程按时间片运行，当一个时间片用完后，
便仃止该进程的执行而重新进行调度。这个原则适用于分时系统。
优先权原则。通常是对一些重要的和紧急的进程赋予较高的优先权。当这种进程进入就绪队列时，例如由阻塞态转换为就绪态，或从静止就绪态转为活动就绪态时，或新创建进入就绪态的进程进入就绪队列时，如果其优先权比正在执行的进程优先权高，便仃止正在执行的进程，将处理机分配给优先权高的进程，使之执行。
进程调度的功能
记录系统中所有进程的执行情况进程管理模块在各进程的 PCB表中记录系统各进程的执行情况和状态特征，并将各 PCB表根据进程状态特征和资源要求排成相应的队列，并进行动态队列转换。
选择占有处理机进程进程调度的主要功能是按照一定的策略（由它决定的调度算法），选择一个处于就绪态的进程，使其获得处理机执行。
进行进程上下文切换进程上下文实际上是进程执行活动全过程的静态描述，
一个进程的执行是在进程上下文中执行。当正在执行的进程由于某种原因要让出处理机时，系统要做上下文切换，
以使另一个进程得以执行。
3。中级 (Medium-term)调度 —— 对换目的：为了提高主存利用率和系统吞吐量。由于在进程并发执行过程中，为了充分发挥内存的效能，需将那些暂时不能运行的进程从内存调到外存盘交换区去等待，此时进程状态为挂起状态；而当这些进程又重新具备运行条件，且内存又有空闲时，由 中级调度 把它们从外存 — 内存，状态置为就绪态。
在 UNIX系统中中级调度就是存储管理中的对换，采用虚拟存储技术的分时系统往往设立中级调度。
4.1调度 (Scheduling)的类型和模型就绪 态执行 态 静止就绪阻塞 态 中级调度图：处理机三级调度作业调度 作业运行状态外存外存 (盘 )交换区作业后备状态作业提交状态 作业 完成状态终止 作业静止就绪静止阻塞中级调度主存进程调度 运行态就绪态阻塞态
4.1.2 处理机调度队列模型
1。仅有进程调度的调度队列模型在分时系统中通常仅设置了进程调度。此时系统有一个就绪队列，每个进程运行一个时间片，进程运行一个时间片后如未完成，则被放在就绪队列末尾。如进程运行中因等待某事件（例如申请 I/O而等待 I/O完成），则需排入阻塞队列，
系统因阻塞的原因不同可设几个阻塞队列。 P98图 4-1
2。有进程调度和中级调度队列模型在具有虚拟存储器技术的分时系统中（例如 UNIX系统等），
一般采用具有进程调度和中级调度的调度模型。在该模型中比第一种模型增加了中级调度，则相对于上模型也增加了外存进程就绪队列和外存进程阻塞队列。中级调度时或从内存就绪队列调到外存的就绪队列，或从内存阻塞队列调到外存阻塞队列，或从外存进程就绪队列调到内存就绪队列。
处理机调度模型 -1
3。具有高级调度和低级调度的调度队列模型在多道批处理系统中，一般处理机管理设置作业和进程两级调度。它比第一个模型增加了高级调度。模型增加了在磁盘的作业后备队列，作业调度的任务是从作业后备队列中选一个作业为它创建至少一个进程，并分配资源，将它排入内存进程就绪队列末尾。 P99图 4-2
4。同时具有三级调度的调度队列模型在通用系统的多模式 OS中，一般采用具有三级调度的调度队列模型，由于多模式 OS同时支持批处理、分时和实时处理，所以它必须具有以上模型，见图所示。
图,具有三级调度队形模型中级调度调出
CP
U
交互型作业分时间片完等待事件完成内存进程就绪队列外存进程就绪队列外存进程阻塞队列内存进程阻塞队列事件发生作业调度后备作业队列批量作业 中级调度调入中级调度调出磁盘
4.1.3 调度方式和算法的选择准则
1.面向用户的准则和评价
周转时间短（ 批处理系统 ）
它是评价批处理系统的重要性能指标。作业周转时间 Ti是指从作业提交给系统开始，到作业完成为止的这段时间间隔。
平均周转时间 T = 1/n×
平均带权周转时间 W = 1/n×
一个作业的带权周转时间 Wi=Ti/Tsi（ 作业的周转时间 Ti/实际服务时间 Tsi）
][
1
n
i
Ti
]/[
1
n
i
T siTi
提交作业 后备队列 就绪队列 CPU 等待 I/O完成作业调度进程调度周转时间调度方式和算法的选择准则 -1
响应时间快（ 分时系统 ）
响应时间是评价分时系统的性能指标。响应时间为截止时间的保证（ 实时系统 ）
它是用来评价实时系统的重要指标，截止时间是某任务必须执行的最迟时间，或完成的最迟时间。
优先权准则（ 批处理、分时和实时系统 ）
在选择批处理、分时和实时系统的调度算法时，都可引用优先权准则，以便让那些紧急的作业（或事件），得到及时的处理。在要求较严格的场合，往往还需选择抢占调度方式，才能保证紧急作业得到及时的处理。
键入请求 CPU处理请求 显示器显示请求 响应响应时间调度方式和算法的选择准则 -2
2。 面向系统的准则
达到系统设计目标系统的设计目标是选择算法的主要依据。例如批处理系统所追求的是充分发挥和提高计算机的效率，分时系统则侧重于保护用户的请求及时给予响应，
实时系统所关心的是不要丢失实时信息并给予处理。
系统吞吐量大这是用来评价批处理系统的重要指标。系统吞吐量是单位时间内完成的作业数，它与批处理作业的平均长度具有密切关系。
处理机利用率高对于大中型多用户系统，由于 CPU价格十分昂贵，所以处理机利用率成为衡量大、中型系统性能的十分重要指标，但对单用户微机或某些实时系统，该准则就不那么重要。
各类资源的平衡利用在大中型系统中，有效地利用各类资源（包括 CPU,外存,I/O设备等）也是一个重要指标，对于微型机和某些实时系统，该准则也不重要。
4.2 作业／进程调度算法进程调度（ PCB）,就绪队列如何排列？基于某种算法。
作业调度（ JCB）：
4.2.1 先来先服务 First-Come-First-Served （ FCFS）（ 作业／
进程）调度算法
FCFS是一种最简单的调度算法，可用于作业或进程调度。此算法的原则是按照作业到达后备作业队列（或进程进入就绪队列）的先后次序来选择作业（或进程）。 FCFS算法属于非抢占方式，一旦一个进程占有处理机，它就一直运行下去，直到该进程完成或者因等待某事件而不能继续运行时才释放处理机。
FCFS算法易于实现，表面上很公平。 (最好辅以图示 )
周转时间 =完成时间 -到达时间平均周转时间 =周转时间 /服务时间 P102（ 辅以时间轴）
4.2.2 短作业／进程优先 (SJF/Shortest Process Next)调度算法这种调度算法主要用于作业调度，它从作业后备队列中挑选所需运行时间
（估计值）最短的作业进入主存运行。这一算法有利于短作业，对长作业不利。采用 SJF有利于系统减少平均周转时间和平均带权周转时间。
4.2 作业／进程调度算法
P102实例，画时间轴讲解。
分析：
（ 1）平均周转、带权周转在 SJF中有改善。
（ 2）短作业 D,FCFS中周转为 1，带权周转为 5.5；
SJF中周转为 3，带权周转为 1.5。 ----有明显改善。
所以 SJF可降低平均等待时间，提高系统吞吐量。
缺点：不利于长作业； 未考虑紧迫性。
EXAMPLE,OLD WOMAN /FELLOWS ---friedcake
4.2 作业／进程调度算法作业／进程调度算法 -1
4.2.3时间片轮转 Round-Robin（ RR） 调度算法一、基本原理它用于进程调度，是分时系统采用的主要调度算法。进程调度程序总是选择就绪队列中第一个进程，允许其占有处理机一个时间片的时间。当执行的时间片用完时，调度程序便仃止该进程的执行，并将它送就绪队列的末尾，等待分配下一时间片再执行。然后把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，
在一给定的时间内，均能获得一时间片处理机执行时间。
二、时间片大小的确定在 RR算法中，时间片的大小对系统性能有很大的影响。
时间片太长 -----FCFS算法时间片太小 -----频繁切换占用 CPU。 P104与图 4-5、图 4-6。
作业／进程调度算法 -2
4.2.4 高响应比优先 Highest Response Ratio Next
(HRRN)(作业 )调度算法按照高响应比优先的原则，在每次选择作业投入运行时，先计算此时后备作业队列中每个作业的响应比 RP然后选择其值最大的作业投入运行。主要用于批处理系统。
RP值定义为：
RP＝ （已等待时间＋要求运行时间）／要求运行时间
＝ 1＋ 已等待时间／要求运行时间。
HRN算法实际上是 FCFS算法和 STF算法的折衷 。
分析：
（ 1）若干作业同时到达，短作业先调入执行；
（ 2）若干作业要求执行时间相同，先到作业先执行；
（ 3）一般情况，按计算 RP值调度。
例：作业 A,B,C,D分别在时刻 0,1（ B,C）,2提交，要求服务时间为 10，
8,10,2，则按高响应比优先调度算法有：
0时刻调度作业 A运行,10时刻，计算 B,C,D的 RPb RPcc RPd----作业 D执行
12时刻，计算 B,C的 RPb RPc ----作业 B---作业 C。
作业／进程调度算法 -3
例,假定在一个处理机上执行以下五个作业：
作业号 A B C D E
到达时间 0 1 2 3 4
运行时间 4 3 5 2 4
分别采用 FCFS,SJF,RR（ 时间片＝ 1） 和 HRN(响应比高者优先 )
四种调度算法时,试做,（ 1） 画出调度图；
（ 2） 计算每个作业的周转时间和带权周转时间 ；
（ 3）计算平均周转时间和平均带权周转时间。
调度图：
T 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
FCFS A A A A B B B C C C C C D D E E E E
SJF A A A A D D B B B E E E E C E E E E
RR A B C D E A B C D E A B C E A C E C
HRN A A A A B B B D D C C C C C E E E E
例解：
作业号
A B C D E 平均到达时间
0 1 2 3 4
运行时间
4 3 5 2 4
完成时间
4 ① 7 ② 12 ③ 14 ④ 18 ⑤
周转时间
4 6 10 11 14 9
F C F S
带权周转时间
1 2 2 5,5 3,5 2,8
完成时间
4 ① 9 ③ 18 ⑤ 6 ② 13 ④
周转时间
4 8 16 3 9 8
SJF
带权周转时间
2 2,6 7 3,1 1,5 2,2 5 2,1
例解 -1
作业号
A B C D E 平均到达时间
0 1 2 3 4
运行时间
4 3 5 2 4
完成时间
15 ③ 12 ② 18 ⑤ 9 ① 17 ④
周转时间
15 11 16 6 13 1 2,4
RR
带权周转时间
3,7 5 3,6 7 3,2 3 3,2 5 3,3 7
完成时间
4 ① 7 ② 14 ④ 9 ③ 18 ⑤
周转时间
4 6 12 6 14 8,4
H R R N
带权周转时间
1 2 2,4 3 3,5 2,3 8
例解 -2
高响应比优先 (HRRN)(作业 )调度算法计算：
T=0,只有作业 A已到达，调度作业 A运行 。
T=4,作业 A完成，作业 B,C,D,E已到达，计算作业 B,C,D、
E响应比 RP分别为,1+3/3,1+2/5,1+1/2,1+0/4，作业 B响应比最大调度运行。
T=7,作业 B完成，作业 C,D,E已到达，计算作业 C,D,E响应比 RP分别为,1+5/5,1+4/2,1+3/4，作业 D响应比最大调度运行。
T=9,作业 D完成，作业 C,E已到达，计算作业 C,E响应比 RP分别为,1+7/5,1+5/4，作业 C响应比最大调度运行。
T=14,作业 C完成，只有作业 E未完成，调度作业 E运行 。
作业／进程调度算法 -4
4.2.5优先权 (Priority)调度算法一、算法类型
（ 1）抢占式：主要用于严格的实时系统中
（ 2）非抢占式：主要用于批处理和不严格的实时系统中按照进程的优先权大小来调度，使高优先权进程得到优先处理的调度策略称为优先权调度算法 。
二、优先权的类型进程的优先权的设置可以是静态的，也可以是动态的。
（ 1） 静态优先权 在进程创建时确定，且的在整个生命期中保持不变。确定进程优先权的依据有：
进程类型，通常系统进程（例如对换进程）的优先权高于一般用户态进程的优先权；
进程对资源的需求，如进程执行时间及内存需要省的进程应赋予较高的优先权；
根据用户要求，由用户的紧迫程度及用户所付费用的多少来确定进程的优先权。
（ 2）动态优先权 是指在创建进程时所赋予的优先权，可以随进程的推进而改变，以便获得更好的调度性能。改变优先权的因数，随系统不同而不同，
最常考虑的因素的进程的等待时间，已使用处理机的时间，或者资源使用情况等。
作业／进程调度算法 -5
在 UNIX系统 V中处于核心态和用户态的优先权不同。进程处于核心态的优先权高，处于核心态的进程优先权又分二类，一类是因等待磁盘 I/O,等待缓冲器等不可中断优先权最高，而另一类因等待 TTY输入输出等可中断优先权其次。处于用户态的优先权相对较低，用户态优先权又分为 n+1级优先权。优先数为 0级的优先权最高，优先数为 n级的优先权最低。
用户态优先权是可变的，它随着占用 CPU时间的增加而降低。
核心每隔 1秒钟便按下述公式对各进程重新计算其用户优先数
（优先数与优先权成反比关系）。
优先数＝最近使用 CPU的时间／ 2＋基本用户优先数。
上机实验：要求按动态优先权调度做进程调度仿真。
实验内容另讲。
4.2.6．多级队列调度算法（批处理和分时系统结合使用）
多级队列调度是根据作业的性质和类型的不同，将就绪队列再分为若干个子队列，所有的作业（或进程）按其性质排入相应的队列中，而不同的就绪队列采用不同的调度算法。
作业／进程调度算法 -6
例如前后台系统可以建立两个就绪队列，批处理作业所建立进程进入后台就绪队列；交互型作业所建立的进程进入前台就绪队列。前台采用时间片轮转算法，进程按 FCFS等策略排序，后台采用优先权高优先的调度算法或者短作业优先的调度算法。
对多级就绪队列调度策略有两种，一种是各就绪队列按进程性质赋予不同的优先权，优先权高的就绪队列的进程优先被调度，例如上例中前台就绪队列的优先权比后台就绪队列的优先权高，所以前台队列中的进程优先被调度。而只有当优先权高的就绪队列空时，方才调度优先权其次的就绪队列进程，在上例中只有前台队列空时，才调度后台就绪队列。
这样，只有较高优先权的就绪队列都空时才调度最低优先权就绪队列的进程。
另一种调度就绪队列的方式是为每个队列分配一定的占用
CPU时间的比例。如在上例中为前台队列分配 80％的 CPU时间，
给后台队列分配 20％的 CPU时间。
作业／进程调度算法 -7
7。多级反馈 (Feedback)队列调度算法
前面介绍的各种用作进程调度的算法，都有在一定的局限性，如短进程优先算法仅照顾了短进程而怠慢了长进程。况且对进程运行的长短，往往难以正确估计，所以短进程优先的调度算法无法正确使用。而多级反馈队列调度算法，则不必事先知道各种进程所需的执行时间，仍能基本满足短进程优先和 I/O频繁的进程优先的需要，因而是目前公认的较好的一种进程调度算法。在 UNIX系统,WindowsNT,OS/2中都采用了类似的调度算法。
WindowsNT采用可抢占动态优先级多级就绪队列调度算法。
NT执行体支持 32级优先级，并将它们分成两类，实时优先级
（ 16－ 31）和可变优先级（ 1－ 15）,0级为系统保留。每个优先级一个就绪队列，高序号队列为高优先级，调度程序从高优先级的队列开始往下找，如高优先级队列为空时才再往下找，直至找到一个线程。
作业／进程调度算法 -8
各个就绪队列中进程执行时间片的大小也各不相同，在优先级越高的队列中，每个进程的执行时间片就规定得越小。
当一个线程执行完一个完整的时间段后被中断抢占处理器，
而被抢占的线程优先级降低一级而进入下级就绪队列，如此继续，直至降到线程的基本优先级。而一个线程从阻塞态变为就绪态时要提高优先级，提高的幅度与等待的事件有关。如等待键盘输入所提高的幅度要大于等待磁盘 I/O。
在 NT中，交互式线程处于高优先级,I/O型线程处于中间优先级，计算型线程处于低优先级，系统还设置一个空闲线程，其优先级为 0，是优先级最低的线程，只要处理空闲，就执行该线程。
图,多级反馈队列就绪队列 1 时间片 S1 时间片完时间片完就绪队列 2 时间片 S2>S1
运行运行运行就绪队列 n 时间片 Sn>Sn-1
完成完成完成时间片完阻塞队列 i
阻塞阻塞阻塞事件发生
4.6 死锁的基本概念在两个进程并发执行时，当 PA进程占有 R1,PB进程占用 R2
时,PA要求 R2,由于 PB已占 R2有而得不到,PA进程只有等待； PB申请 R1,由于 PA已占有 R1,而得不到,PB进程只有等待，就出现了死等的情况。哲学家进餐。
例 1：有两个进程 PA和 PB,它们在运行的过程中要共享使用两个独占设备 R1和 R2。 设 SR1,表示设备 R1可用,初值为 1； SR2表示设备 R2可用,两个进程并发执行的程序如下：
死锁的概念例 2：三个进程共享使用一台打印机的程序若有一个进程少写了一个 V/signal操作 。
死锁的概念例 3：生产者－消费者问题
当缓冲区满时,生产者仍可顺利执行 p(mutex)操作,
于是它对缓冲区有控制权,
然后,当它执行 p(empty)
时,由于没有空缓冲区被挂起 。 能将这个生产者释放的是有一个消费者从缓冲区中取走一个产品,并执行 v(empty)操作,但由于缓冲区已被生产者占用,
出现了死锁 。
4.6 死锁的基本概念死锁的定义,
死锁就是两个或两个以上的进程等候着一个永远不会发生的事件时所取的一种系统状态 。 因竞争资源而造成的一种僵局,若无外力作用,这些进程将永远不能推进 。
4.6.1死锁的原因和条件
1。死锁的原因
竞争资源引起死锁在多道程序系统，多个进程共享系统的资源。系统资源分为二类，一类是不可抢占的资源，如打印机、磁带机等。当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自动释放。另一类是可抢占的资源，如 CPU,内存等。由于系统拥有的不可抢占的资源有限，多个进程共享竞争不可抢占的资源就可能引起死锁。
竞争临时性资源（软件资源） /消耗性资源。 P120图 4-15
进程推进顺序不当引起死锁在多道程序系统中，并发执行的进程推进序列不可予测，有些推进顺序，
进程可以顺利完成，这些推进顺序是合法的；而有的推进顺序会引起进程无限期地等待永远不会发生的条件而不能向前推进，造成了死锁。
死锁的原因和条件 -1
进程推进顺序不当引起死锁例：
进程 P和 Q并发执行，进程 P和 Q程序如下：
Process P Process Q
..,.
Get A Get B
..,.
Get B Get A
..,.
Release A Release B
..,.
Release B Release A
..,.
进程 P和 Q按路径 1,2,5,6推进顺序合法，按 3,4推进顺序非法，见下图：
进程推进顺序不当引起死锁例：
Progress
of Q
Release
A
Release
B
Get A
Get B
Get A Get B Release A
Release B
Progress
of P
A
Required B Required
A
Required
B
Required
deadlock
inevitable
1 2
3
4
5
6
P and Q
want B
P and Q
want A
死锁的原因和条件 -1
4.6.2 产生死锁的必要条件（ Conditions for Deadlock ）
互斥（ Mutual exclusion ）条件,一个资源一次只能被一个进程所使用，即是排它性使用。进程在访问某些资源时不可避免地产生互斥性。
不可抢占（ No preemption ）条件,一个资源仅能被占有它的进程所释放，而不能被别的进程强占。
请求和保持（ Hold-and-wait ）条件,进程已经保持了至少一个资源，但又提出了新的资源要求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对已经获得的其它资源保持不放。
环路等待（ Circular wait ）条件,当每类资源只有一个时，
在发生死锁时，必然存在一个进程 -资源的环形链。如一系统状态的资源分配图所示,P1正在等待一个 P2 占用的资源 R2，
P2正在等待一个 P1占用的资源 R1。
死锁的原因和条件 -2
资源分配图由结点和边组成。结点有二类，一类是进程结点，用园圈表示；另一类是资源结点，用小方框表示一类资源，用方框中的小圈表示资源数。边也有二类，一类是分配边，它由资源结点指向进程结点，另一类是申请边，它由进程结点指向资源结点。
返回
R1
R2
P1 P2
死锁的原因和条件 -3
4.6.3 处理 死锁的基本方法
a,死锁的预防静态方法：在进程执行前采取的措施，通过设置某些限制条件，去破坏产生死锁的四个必要条件之一或几个，防止发生死锁。
B.死锁的避免动态的方法：在进 程 执行过程中采取的措施，不需事先采取限制措施破坏产生死锁的必要条件，而是在进程申请资源时用某种方法去防止系统进入不安全状态，从而避免发生死锁。银行家算法。
C.死锁的检测和解除这种方法预先并不采用任何限制措施，允许系统在运行过程中发生死锁，但可通过系统设置的检测机构及时检测死锁的发生，如检测到死锁，则采用撤消进程等死锁解除方法使系统正常工作。
4.7 死锁的预防 (Deadlock Prevention)和避免预防死锁的方法是破坏四个产生死锁的必要条件之一。
1。 破坏互斥条件互斥使用是资源本身特征所决定的。使用硬软件结合可改变资源本身特性，例如采用 SPOOLing技术可将,独享,打印机改变为,共享,的打印机。
2。 破坏不可抢占条件抢占式调度法主要用于处理机和存贮器资源调度，它们的状态容易保存和恢复。但此法对外部设备和私存数据不宜使用。 P1占有 R1,P2在申请 R1时,P1不释放，产生死锁； 破坏不可 剥夺条件，系统强行剥夺 R1---P2,P1以后执行时，需退回申请 R1之前，造成 P1执行产生死尸。
死锁的预防 -1
3。 破坏请求和保持条件系统可采用 资源静态予分配方式 来破坏请求保持条件。系统要求所有进程一次性地申请在整个运行过程中全部资源，
若系统有足够资源满足给进程，则在运行前，一次性将其所需要的所有资源分配给该进程。这样该进程在整个运行期间，
便不再提出资源要求，从而摒弃了请求条件。这种预防死锁的方法，优点是简单、易予实现且很安全，但其资源利用率很低，进程也延迟运行。定义数组（ Basic,Fortran）。 实际现在的 OS。
4。 破坏循环等待条件有序资源使用法该方法将所有的资源按类型进行线性排队，并赋予不同的序号。例如令输入机的序号为 1，打印机序号为 2，磁盘机序号为 3等。
死锁的预防 -2
所有进程对资源的请求必须严格按资源序号递增的次序提出。
这样在所形成的资源分配图中不可能再出现环路，因而摒弃了,环路等待,条件，在采用这种策略时总有一个进程占据了较高序号的资源，它继续请求的资源必然是空闲的，因而进程可以一直向前推进。这种预防死锁的策略可以提高资源利用率，但在进程使用各类资源的顺序与系统规定的顺序不同时会造成资源浪费的情况。
资源按级分配法该方法是把资源递增排序成若干等级（如 L1,L2……,Lm），
其中每级可包含几类资源，要求每个进程在获得了 Lj级中资源之后,它才能申请更高级的 LK（ LK＞ Lj） 级中的资源；如果它还需申请比 LK级低的 LI级（ LI<LK） 资源，则必须先释放所有大于 LI级的资源。该方法是 Haveder 1968年在设计 IBM／
360 OS时提出的，资源共分三级，第一级数据集或文件，第二级主存，第三级 I/O设备。
4.7.2 系统的安全状态该方法允许进程动态地申请资源，系统在进行资源分配之前，先计算资源分配的安全性。若此次分配不会导致系统从安全状态向不安全状态转换，便可将资源分配给进程；否则不分配资源，进程必须阻塞等待。从而避免发生死锁。
1.系统的 安全状态动态分配资源，分配前，先考虑安全性，若预分配后 — 安全态，则可以分配，非安全态，则不分配。
安全状态是指系统的一种状态，在此状态开始系统能按某种顺序（例如
P1,P2…… Pn） 来为各个进程分配其所需资源，直至最大需求，使每个进程都可顺序地一个个地完成。这个序列（ P1,P2……,Pn） 称为 安全序列 。若系统此状态不存在一个安全序列，则称系统处于 不安全状态 。
2 实例：
假如系统中有 P1,P2和 P3三个进程和 12台磁带机。各进程最大需求和 T0时刻分配状态如下：
进程 最大需求 已分配 还需请求 可用
P1 10 5 5 3
P2 4 2 2
P3 9 2 7
死锁的避免 -1
分析 T0状态，利用现有空闲资源数 3，能否可以找到一个安全序列,即系统按此进程序列分配资源，每个进程都可顺利完成，其步骤如下：
（ 1）先将可用的 3台磁带机中 2台分配给 P2,P2满足了最大的资源需求，在有限时间内推进完毕，释放它占有的 4台资源，使可用资源数量增至 5台。
（ 2）再将可用的 5台磁带机分配给 P1,P1满足了最大的资源需求，在有限时间内推进完毕，释放它占有的 10台资源，使可用资源数量增至 10台。
（ 3）最后将可用 10台中 7台磁带机分配给 P3,P3推进完毕，释放它占有的
9台资源，使可用资源数量增至 12台。
这样三进程可按照（ P2,P1,P3） 序列顺序地一个个执行完成，则（ P2、
P1,P3） 序列是安全序列，所以在 T0时刻，系统处于安全状态。
2。由安全状态向不安全状态的转换如果在 T0 状态不按安全序列进行分配，可能会导致系统进入一个不安全状态，例如在 T0状态下 P3中申请 2台磁带机。如系统实施此次分配使系统状态由 T0变为 T1状态，分析 T1状态安全情况。
死锁的避免 -2
T1时刻状态：
进程 最大需求 已分配 还需请求 可用
P1 10 5 5 > 1
P2 4 2 2 > 1
P3 9 4 5 > 1
因为找不到一个安全序列使所有进程顺序地一个个地运行完毕，所以 T1状态是不安全状态，由于实施分配给 2台磁带机给 P3的操作会引起系统状态由安全状态 T0向不安全状态下的转换，所以为了避免死锁，上述的分配只是安全检测，检测后判定这样的申请不能满足,P3为申请 2台磁带机而必须阻塞等待。
4.7.3利用银行家算法避免死锁最具代表的避免死锁算法是 Dijkstra的银行家算法，这是由于该算法用于银行系统现金贷款的发放而得名。
银行家算法的数据结构
可用资源向量 Available [m]---0..m-1
m为系统中资源种类数,Available[j]=k表示系统中第 j类资源数为 k个。
最大需求矩阵 Max[n,m]— n行 m列
n为系统中进程数,Max[i,j]=k表示进程 i对 j类资源的最大需求数为中 k。
已分配矩阵 Allocation[n,m]
它定义了系统中每一类资源当前已分配给每一进程资源数，
Allocation[i,j]=k表示进程 i已分得 j类资源的数目为 k个。
进一步需求矩阵 Need[n,m]
它表示每个进程尚需的各类资源数,Need[i,j]=k 表示进程
i还需要 j类资源 k个。 Need[i,j]=Max[i,j]-Allocation[i,j]
利用银行家算法避免死锁 -1
银行家算法
假设在进程并发执行时进程 i提出请求 j类资源 k个后，
表示为 Requesti[j]=k。 系统按下述步骤进行安全检查：
如果 Requesti≤Need i则继续以下检查，否则显示需求申请超出最大需求值的错误。
如果 Requesti≤Available 则继续以下检查，否则显示系统无足够资源,Pi阻塞等待。
系统试探把要求的资源分配给进程 i并修改有关数据结构的值：
Available = Available-Requesti ；
Allocationi =Allocationi+Requesti ；
Needi=Needi-Requesti ；
利用银行家算法避免死锁 -2
系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态，若安全，才正式将资源分配给进程 i,以完成本次分配；否则将试探分配作废，恢复原来的资源分配状态，
让进程 Pi等待。
③安全性算法安全性算法执行步骤如下：
A.初始化设置工作向量 Work[m]表示系统可提供的各类资源数目，
用以保护原数据结构有关值。 Work = Available,设置完成标志向量 Finish[n]。 Finish[i] = false 表示 i进程尚末完成，如值为 true则表示进程 i已完成。
B.从进程集合 n中找到一个能满足下述二个条件,Finish[i] =
false和 Necdi≤Work,如找到则执行步骤 C,如找不到同时满足以上二条件的进程则执行步骤 D。
利用银行家算法避免死锁 -3
C.当进程 i获得资源后可顺利执行直到完成，并释放出分配给它的资源，表示如下：
work = work+Allocationi ； Finish[i]=true ； 转执行步骤 B。
D.如果所有的 Finish[i]＝ ture,则表示系统处于安全状态，
否则系统处于不安全状态。
银行家算法 例：
假定系统中有五个进程 {P0,P1,P2,P3,P4}和三种类型资源
{A,B,C},每一种资源的数量分别为 10,5,7。各进程的最大需求,T0时刻资源分配情况如下 所示。
Max Allocation Need Available
A B C A B C A B C A B C
P0 7 5 3 0 1 0 7 4 3 3 3 2
P1 3 2 2 2 0 0 1 2 2
P2 9 0 2 3 0 2 6 0 0
P3 2 2 2 2 1 1 0 1 1
P4 4 3 3 0 0 2 4 3 1
试问,① T0时刻是否安全？
② P1请求资源 Request1(1,0,2)是否允许？
③ P4请求资源 Request4(3,3,0)是否允许？
银行家算法 例 -1
T0时刻是否安全？
从表中可找出一个序列 (P1,P3,P4,P2,P0） 使各进程 顺序地一个个地执行 完成 。
Max Allocation Need Available Available
(分配资源前 ) (释放 资源 后）
A B C A B C A B C A B C A B C
P0 7 5 3 0 1 0 7 4 3 =< 10 4 7? 10 5 7
P1 3 2 2 2 0 0 1 2 2 =< 3 3 2? 5 3 2
P2 9 0 2 3 0 2 6 0 0 =< 7 4 5? 10 4 7
P3 2 2 2 2 1 1 0 1 1 =< 5 3 2? 7 4 3
P4 4 3 3 0 0 2 4 3 1 =< 7 4 3? 7 4 5
安全序列为 {P1,P3,P4,P2,P0},T0时刻系统是安全的。
P1请求资源 Request1(1,0,2)可否允许？
银行家算法 例 -2
Request1(1,0,2)≤Need 1(1,2,2),P1请求在最大需求范围内。
Request1(1,0,2)≤ Available(3,3,2),可用资源可满足 P1请求需要。
试探把要求的资源分配给进程 P1并修改有关数据结构的数值：
Available = Available(3,3,2)－
Request1(1,0,2)=Available(2,3,0)；
Need1 = Need1(1,2,2)－ Request1(1,0,2)= Need1(0,2,0)；
Allocation1
=Allocation1(2,0,0)+Request1(1,0,2)=Allocation1(3,0,2)；
利用安全性算法检查试探将资源分配后状态的安全性如下：
银行家算法 例 -3
Max Allocation Need Available Available
(分配资源前 ) (释放 资源 后）
A B C A B C A B C A B C A B C
P0 7 5 3 0 1 0 7 4 3 =< 10 4 7? 10 5 7
P1 3 2 2 3 0 2 0 2 0 =< 2 3 0? 5 3 2
P2 9 0 2 3 0 2 6 0 0 =< 7 4 5? 10 4 7
P3 2 2 2 2 1 1 0 1 1 =< 5 3 2? 7 4 3
P4 4 3 3 0 0 2 4 3 1 =< 7 4 3? 7 4 5
因为先分配资源给 P1进程符合按安全序列 {P1,P3,P4,P2,P0}
分配资源，所以试探将资源分配给进程 P1后的状态是安全的，
可将资源分配给进程 P1。
P4请求资源 Request4(3,3,0)是否允许？
Request4(3,3,0)≤Need 4(4,3,1),P4请求在最大需求范围内。
Request4(3,3,0)≤Available(2,3,0) 不成立，即可用资源暂不能满足 P4请求资源需要,P4阻塞等待。
4.8死锁的检测 (Deadlock Detection)
死锁的避免算法增加了系统的开销，死锁的检测采用资源分配图的简化判断是否发生了不安全状态。如发现系统处于不安全状态时，即执行死锁解除的策略，采用此法开销相对减少。
1。资源分配图的简化,
系统处于某 S状态时可用资源分配图表示，可用资源分配图简化来判断系统是否处于死锁状态。资源分配图简化的方法如下：在资源分配图中找一个既不阻塞又非孤立的进程结点
PI（ 如某进程既无已分配的资源也不需申请资源，即既无分配边又无申请边，则该进程结点是孤立结点），让它获得所需资源而继续运行直至完毕，再释放它拥有的所有的资源，
这相当于取消 PI的分配边和请求边，使它成为孤立结点。
经过以上简化，如所有的进程结点都是孤立结点则称资源分配图是可完全简化的。若不能通过任何过程使该图完全简化，
则该图是不可完全简化的。资源分配图简化如 下图,
R1 R2 R1 R2
。。
P1
资源分配图的简化例,
。。
。
P1
P2
。 。
。
P1
P2
。。
。。
。
P2
。。
R1 R2
死锁的检测 -1
2。死锁定理：
S为死锁状态的充分条件是：尚且仅当 S状态的资源分配图是不可完全简化的，该充分条件称为死锁定理。
3。死锁检测的数据和算法 类似于银行家算法。
（ 5）死锁的解除
当检测死锁的软件 判别死锁存在时,就要解除死锁,使系统从死锁中恢复。
第一种是强制性地从系统中撤消一个或多个死锁的进程以断开循环等待链,并收回分配给终止进程的全部资源供剩下的进程使用。借助于撤消进程来解除死锁可以使用两种方法。
一种是撤消全部的死锁进程，这显然会断开死锁环路，但代价太大。另一种方法是逐个撤消死锁的进程直至死锁环路消除。这里存在一个按照什么原则进行逐个撤消进程的问题。
目前较实用而又简便的方法是撤消那些代价最小的进程。所谓影响一个进程的撤消代价因素有该进程的优先权，该进程运行到今的运行代价（包括 CPU时间，使用资源的种类和时间等）、与相关的作业类型和外部代价等。
死锁的解除 -1
死锁恢复的另一种办法是使用一个有效的挂起和解除机构来挂起一些死锁的进程,其实质是从被挂起的进程那里抢占资源以解除死锁，许多学者认为在此领域的研究工作比起其它死锁恢复的办法更为重要。例如一个系统提供了检查点和重新启动的便利的话，我们可以暂时仃止一个系统，而后从各进程的最近的检查点（系统保留了检查点的状态）逐次地重新启动。这既可以从死锁中恢复，又使进程损失最小（从检查点以后的损失）。但许多系统还没有此功能，在 IBM4300系列等机器上提供了此类功能。
习题
1,在操作系统中处理机管理由作业管理和进程管理两部分组成,
作业管理把作业流分成提交,后备,运行,完成四个状态,
进程管理把进程分成就绪,执行,阻塞三个基本状态 。 作业由后备状态到运行状态由﹎﹎ B﹎﹎ 完成,进程由就绪状态到执行状态由﹎﹎ C﹎﹎,用户进程的祖先进程由﹎﹎ E﹎﹎ 建立的 。
A,B,C,D,E,(1)作业调度程序； (2)进程调度程序； (3)存储管理程序； (4)输入输出程序； (5)假脱机 （ SPOOLing） 处理程序； (6)交通程序； (7)设备管理程序 。
2,操作系统的主要性能参数：﹎﹎ A﹎﹎ 指的是单位时间内系统处理的作业量 。 ﹎﹎ B﹎﹎ 指的是从作业或命令的输入到其结束的间隔时间,在分析性能时常用其倒数 。 ﹎﹎ C﹎﹎ 指的是在一个给定的时间内,系统的一个指定成份被使用的时间比例 。
A,B,C,(1)周转时间； (2)处理时间； (3)消逝时间； (4)利用率； (5)生产率； (6)吞吐量 。
习题 -1
3,在所学的调度算法中,对所有进程和作业都是公平合理的调度算法是﹎﹎ A﹎﹎； 最有利于提高系统吞吐量的作业调度算法是﹎﹎ B﹎﹎； 能兼顾作业等待时间和作业执行时间调度算法是﹎﹎ C﹎﹎； 最有利于提高资源的使用率,能使短作业,
长作业及交互作业用户都比较满意的调度算法是﹎﹎ D﹎﹎；
为实现人机交互作用应采用调度算法是﹎﹎ E﹎﹎； 能对紧急作业进行及时处理的调度算法是﹎﹎ F﹎﹎ 。
A,B,C,D,(1)FCFS调度算法； (2)短作业优先调度算法； (3)
时间片轮转法； (4)多级反馈队列调度算法； (5) 高响应比优先算法； (6)基于优先权的剥夺调度算法 。
4.假定在一个处理机上执行以下五个作业，
作 业 号 1 2 3 4 5
到 达 时 间 0 2 4 6 8
运 行 时 间 3 6 4 5 2
当分别采用 FCFS,SJF(短作业优先 )和 HRRN（ 响应比高者优先）
三种调度算法时，试问,
习题 -2
⑴ 三种调度算法调度次序为﹎﹎ A﹎﹎,﹎﹎ B﹎﹎ 和﹎﹎ C﹎﹎；
⑵ 采用 FCFS调度算法时 1--5号作业的周转时间为﹎﹎ D1﹎﹎,
﹎﹎ E1﹎﹎,﹎﹎ F1﹎﹎,﹎﹎ G1﹎﹎ 和﹎﹎ H1﹎﹎； 采用
SJF调度算法时 1--5号作业的周转时间为﹎﹎ D2﹎﹎,﹎﹎ E2
﹎﹎,﹎﹎ F2﹎﹎,﹎﹎ G2﹎﹎ 和﹎﹎ H2﹎﹎； 采用 HRRN调度算法时 1--5号作业的周转时间为﹎﹎ D3﹎﹎,﹎﹎ E3﹎﹎,
﹎﹎ F3﹎﹎,﹎﹎ G3﹎﹎ 和﹎﹎ H3﹎﹎；
⑶ 三种调度算法的平均周转时间为﹎﹎ I﹎﹎,﹎﹎ J﹎﹎ 和﹎
﹎ K﹎﹎ 。
A,B,C,(1)1 2 3 4 5 ; (2)5 1 3 4 2 ; (3)1 5 3 4 2 ;
(4)1 2 5 3 4 ; (5)1 2 3 5 4 ;
D1---H1,D2---H2,D3---H3,(1)1 (2)2 (3)3 (4)4 (5)5
(6)6 (7)7 (8)8 (9)9 (10)10 (11)11 (12)12 (13)13
(14)14 (15)15 (16)16 (17)17 (18)18 (19)19 (20)20
I,J,K,(1)7.0 (2)7.6 (3)8.0 (4)8.6 (5)9.0 (6)9.6
(7)10.0 (8)11.0
习题 -3
5,产生死锁的基本原因是﹎﹎ A﹎﹎ 和﹎﹎ B﹎﹎,产生死锁的四个必要条件是互斥条件﹎﹎ C﹎﹎,不剥夺条件和﹎﹎ D﹎
﹎ 。
A,(1)资源分配不当； (2)系统资源不足； (3)作业调度不当；
(4)资源的独占性 。
B,(1)进程推进顺序非法； (2)进程调度不当； (3)系统中进程太多； (4)CPU运行太快 。
C,(1)请求和阻塞条件； (2)请求和释放条件； (3)请求和保持条件； (4)释放和阻塞条 件； (5)释放和请求条件 。
D,(1)线性增长条件； (2)环路条件； (3)无序释放条件； (4)
有序请求条件； (5) 无序请求条件 。
习题 -4
6．预防死锁的论述中，﹎﹎ A﹎﹎ 条是正确的论述。
(1)由于产生死锁的基本原因是系统资源不足，因而预防死锁的有效方法，是根据系统规模，配置足够的系统资源。
(2)由于产生死锁的另一种基本原因是进程推进顺序不当，因而预防死锁的有效方法，是使进程的推进顺序合法。
(3)因为只要系统不进入不安全状态，便不会产生死锁，故预防死锁的有效方法，是防止系统进入不安全状态。
(4)可以通过破坏产生死锁的四个必要条件之一或其中几个的方法，来预防发生死锁。
习题 -5
7,试描述避免死锁的银行家算法,若系统运行中出现下述资源分配情况进程 ALLOCATION NEED AVAILABLE
A B C D A B C D A B C D
P0 0 0 3 2 0 0 1 2 1 6 2 2
P1 1 0 0 0 1 7 5 0
P2 1 3 5 4 2 3 5 6
P3 0 3 3 2 0 6 5 2
P4 0 0 1 4 0 6 5 6
该系统是安全,安全序列为﹎﹎ A﹎﹎,﹎﹎ B﹎﹎,﹎﹎ C﹎﹎,
﹎﹎ D﹎﹎,﹎﹎ E﹎﹎ 。
如果进程 P2此时提出资源申请 （ 1,2,2,2）,系统﹎﹎ F﹎
﹎ 将资源分配给它 。
A---E,(1)P0 (2)P1 (3)P2 (4)P3 (5)P4
B,(1) 能 (2) 不能
8,试述死锁产生的原因和必要条件及解决死锁的方法 。
