资源简介

The Best R&D Courses
处理机调度
3.1 处理机调度的层次和调度算法的目标
　　在多道程序系统中，调度的实质是一种资源分配，处理机调度是对处理机资源进行分配。处理
机调度算法是指根据处理机分配策略所规定的处理机分配算法。在多道批处理系统中，一个作业从
提交到获得处理机执行，直至作业运行完毕，可能需要经历多级处理机调度，下面先来了解处理机
调度的层次。
The Best R&D Courses
处理机调度
3.1.1 处理机调度的层次
　　1. 高级调度(High Level Scheduling)
　　2. 低级调度(Low Level Scheduling)
　　3. 中级调度(Intermediate Scheduling)
The Best R&D Courses
高级调度 ( 按照某种规则，从后备队列 外存 内存 最低 无 创建态 就绪态
作业调度) 中选择合适的作业将其调入 (面向作业)
内存，并为其创建进程
中级调度 ( 按照某种规则，从挂起队列 外存 内存 中等 挂起态 就绪态 (
内存调度) 中选择合适的进程将其数据 (面向进程) 阻塞挂起 阻塞态)
调回内存
低级调度 ( 按照某种规则，从就绪队列 内 存 CPU 最高 就绪态 运行态
进程调度) 中选择一个进程为其分配处
理机
The Best R&D Courses
处理机调度
3.1.2 处理机调度算法的目标
　　1. 处理机调度算法的共同目标
　　(1) 资源利用率。为提高系统的资源利用率，应使系统中的处理机和其它所有资源都尽可能地保
持忙碌状态，其中最重要的处理机利用率可用以下方法计算：
CPU 有效工作时间
CPU 的利用率 = CPU 有效工作时间 CPU 空闲等待时间
The Best R&D Courses
处理机调度
　　(2) 公平性。公平性是指应使诸进程都获得合理的CPU 时间，不会发生进程饥饿现象。公平性
是相对的，对相同类型的进程应获得相同的服务；但对于不同类型的进程，由于其紧急程度或重要
性的不同，则应提供不同的服务。
　　(3) 平衡性。由于在系统中可能具有多种类型的进程，有的属于计算型作业，有的属于I/O型。
为使系统中的CPU和各种外部设备都能经常处于忙碌状态，调度算法应尽可能保持系统资源使用的
平衡性。
　　(4) 策略强制执行。对所制订的策略其中包括安全策略，只要需要，就必须予以准确地执行，即
使会造成某些工作的延迟也要执行。
The Best R&D Courses
处理机调度
　　2. 批处理系统的目标
　　(1) 平均周转时间短。
　　对每个用户而言，都希望自己作业的周转时间最短。但作为计算机系统的管理者，则总是希望
能使平均周转时间最短，这不仅会有效地提高系统资源的利用率，而且还可使大多数用户都感到满
意。应使作业周转时间和作业的平均周转时间尽可能短。否则，会使许多用户的等待时间过长，这
将会引起用户特别是短作业用户的不满。可把平均周转时间描述为：
1 nT [ T i]n i 1
The Best R&D Courses
处理机调度
　　为了进一步反映调度的性能，更清晰地描述各进程在其周转时间中，等待和执行时间的具体分
配状况，往往使用带权周转时间，即作业的周转时间T与系统为它提供服务的时间Ts之比，即
W = T/Ts。而平均带权周转时间则可表示为：
W 1
n T
i
n i 1 T s
The Best R&D Courses
处理机调度
　　(2) 系统吞吐量高。由于吞吐量是指在单位时间内系统所完成的作业数，因而它与批处理作业的
平均长度有关。事实上，如果单纯是为了获得高的系统吞吐量，就应尽量多地选择短作业运行。
　　(3) 处理机利用率高。对于大、中型计算机，CPU价格十分昂贵，致使处理机的利用率成为衡量
系统性能的十分重要的指标；而调度方式和算法又对处理机的利用率起着十分重要的作用。如果单
纯是为使处理机利用率高，应尽量多地选择计算量大的作业运行。由上所述可以看出，这些要求之
间是存在着一定矛盾的。
The Best R&D Courses
处理机调度
　　3. 分时系统的目标
　　(1) 响应时间快。
　　(2) 均衡性。
　　4. 实时系统的目标
　　(1) 截止时间的保证。
　　(2) 可预测性。
The Best R&D Courses
处理机调度
　　　　3.2 作业与作业调度
　　在多道批处理系统中，作业是用户提交给系统的一项相对独立的工作。操作员把用户提交的作
业通过相应的输入设备输入到磁盘存储器，并保存在一个后备作业队列中。再由作业调度程序将其
从外存调入内存。
The Best R&D Courses
处理机调度
3.2.1 批处理系统中的作业
　　1. 作业和作业步
　　(1) 作业(Job)。
　　(2) 作业步(Job Step)。
The Best R&D Courses
处理机调度
　　2. 作业控制块(Job Control Block，JCB)
　　为了管理和调度作业，在多道批处理系统中，为每个作业设置了一个作业控制块JCB，它是作
业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。通常在JCB中包
含的内容有：作业标识、用户名称、用户账号、作业类型(CPU 繁忙型、I/O 繁忙型、批量型、终
端型)、作业状态、调度信息(优先级、作业运行时间)、资源需求(预计运行时间、要求内存大小等)、
资源使用情况等。
The Best R&D Courses
处理机调度
　　3. 作业运行的三个阶段和三种状态
　　作业从进入系统到运行结束，通常需要经历收容、运行和完成三个阶段。相应的作业也就有
“后备状态”、“运行状态”和“完成状态”。
　　(1) 收容阶段。
　　(2) 运行阶段。　　
　　(3) 完成阶段。
The Best R&D Courses
处理机调度
3.2.2 作业调度的主要任务
　　作业调度的主要任务是，根据JCB中的信息，检查系统中的资源能否满足作业对资源的需求，
以及按照一定的调度算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配
必要的资源。然后再将新创建的进程排在就绪队列上等待调度。因此，也把作业调度称为接纳调度
(Admission Scheduling)。在每次执行作业调度时，都需做出以下两个决定。
　　1. 接纳多少个作业
　　2. 接纳哪些作业
The Best R&D Courses
处理机调度
3.2.3 先来先服务(FCFS)和短作业优先(SJF)调度算法
　　1. 先来先服务(first-come first-served，FCFS)调度算法
　　FCFS是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采
用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间
最长的作业，而不管该作业所需执行时间的长短，从后备作业队列中选择几个最先进入该队列的作
业，将它们调入内存，为它们分配资源和创建进程。然后把它放入就绪队列。
The Best R&D Courses
处理机调度
　　2. 短作业优先(short job first，SJF)的调度算法
　　由于在实际情况中，短作业(进程)占有很大比例，为了能使它们能比长作业优先执行，而产生了
短作业优先调度算法。
　　1) 短作业优先算法
　　SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求
的运行时间来衡量的。SJF算法可以分别用于作业调度和进程调度。在把短作业优先调度算法用于作
业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内
存运行。
The Best R&D Courses
处理机调度
　　2) 短作业优先算法的缺点
　　SJF调度算法较之FCFS算法有了明显的改进，但仍然存在不容忽视的缺点：
　　(1) 必须预知作业的运行时间。在采用这种算法时，要先知道每个作业的运行时间。即使是程序
员也很难准确估计作业的运行时间，如果估计过低，系统就可能按估计的时间终止作业的运行，但
此时作业并未完成，故一般都会偏长估计。
　　(2) 对长作业非常不利，长作业的周转时间会明显地增长。更严重的是，该算法完全忽视作业的
等待时间，可能使作业等待时间过长，出现饥饿现象。
The Best R&D Courses
处理机调度
　　(3) 在采用FCFS算法时，人—机无法实现交互。
　　(4) 该调度算法完全未考虑作业的紧迫程度，故不能保证紧迫性作业能得到及时处理。
The Best R&D Courses
处理机调度
3.2.4 优先级调度算法和高响应比优先调度算法
　　1. 优先级调度算法(priority-scheduling algorithm，PSA)
　　我们可以这样来看作业的优先级，对于先来先服务调度算法，作业的等待时间就是作业的优先
级，等待时间越长，其优先级越高。对于短作业优先调度算法，作业的长短就是作业的优先级，作
业所需运行的时间越短，其优先级越高。但上述两种优先级都不能反映作业的紧迫程度。
The Best R&D Courses
处理机调度
　　2. 高响应比优先调度算法(Highest Response Ratio Next，HRRN)
　　在批处理系统中，FCFS算法所考虑的只是作业的等待时间，而忽视了作业的运行时间。而SJF
算法正好与之相反，只考虑作业的运行时间，而忽视了作业的等待时间。高响应比优先调度算法则
是既考虑了作业的等待时间，又考虑作业运行时间的调度算法，因此既照顾了短作业，又不致使长
作业的等待时间过长，从而改善了处理机调度的性能。
The Best R&D Courses
处理机调度
　　高响应比优先算法是如何实现的呢 如果我们能为每个作业引入一个动态优先级，即优先级是
可以改变的，令它随等待时间延长而增加，这将使长作业的优先级在等待期间不断地增加，等到足
够的时间后，必然有机会获得处理机。该优先级的变化规律可描述为：
等待时间 要求服务时间
优先权
要求服务时间
The Best R&D Courses
处理机调度
　　由于等待时间与服务时间之和就是系统对该作业的响应时间，故该优先级又相当于响应比RP。
据此，优先又可表示为：
R 等待时间 要求服务时间 响应时间P 要求服务时间 要求服务时间
The Best R&D Courses
进程调度
　　　　　3.3 进 程 调 度
　　进程调度是OS中必不可少的一种调度。因此在三种类型的OS中，都无一例外地配置了进程调度。
此外它也是对系统性能影响最大的一种处理机调度，相应的，有关进程调度的算法也较多。
The Best R&D Courses
进程调度
3.3.1 进程调度的任务、机制和方式
　　1. 进程调度的任务
　　进程调度的任务主要有三：
　　(1) 保存处理机的现场信息。
　　(2) 按某种算法选取进程。
　　(3) 把处理器分配给进程。
The Best R&D Courses
进程调度
　　2. 进程调度机制
　　为了实现进程调度，在进程调度机制中，应具有如下三个基本部分，如图3-1所示。
　　(1) 排队器。
　　(2) 分派器。
　　(3) 上下文切换器。
The Best R&D Courses
进程调度
图3-1 进程调度机制
The Best R&D Courses
进程调度
　　3. 进程调度方式
　　1) 非抢占方式(Nonpreemptive Mode)
　　在采用这种调度方式时，一旦把处理机分配给某进程后，就一直让它运行下去，决不会因为时
钟中断或任何其它原因去抢占当前正在运行进程的处理机，直至该进程完成，或发生某事件而被阻
塞时，才把处理机分配给其它进程。
The Best R&D Courses
进程调度
　　2) 抢占方式(Preemptive Mode)
　　这种调度方式允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的
处理机重新分配给另一进程。在现代OS中广泛采用抢占方式，这是因为：对于批处理机系统，可以
防止一个长进程长时间地占用处理机，以确保处理机能为所有进程提供更为公平的服务。在分时系
统中，只有采用抢占方式才有可能实现人—机交互。在实时系统中，抢占方式能满足实时任务的需
求。但抢占方式比较复杂，所需付出的系统开销也较大。
The Best R&D Courses
进程调度
3.3.2 轮转调度算法
　　1. 轮转法的基本原理
　　在轮转(RR)法中，系统将所有的就绪进程按FCFS策略排成一个就绪队列。系统可设置每隔一定
时间(如30 ms)便产生一次中断，去激活进程调度程序进行调度，把CPU分配给队首进程，并令其执
行一个时间片。当它运行完毕后，又把处理机分配给就绪队列中新的队首进程，也让它执行一个时
间片。这样，就可以保证就绪队列中的所有进程在确定的时间段内，都能获得一个时间片的处理机
时间。
The Best R&D Courses
进程调度
　　2. 进程切换时机
　　在RR调度算法中，应在何时进行进程的切换，可分为两种情况：① 若一个时间片尚未用完，
正在运行的进程便已经完成，就立即激活调度程序，将它从就绪队列中删除，再调度就绪队列中队
首的进程运行，并启动一个新的时间片。② 在一个时间片用完时，计时器中断处理程序被激活。如
果进程尚未运行完毕，调度程序将把它送往就绪队列的末尾。
The Best R&D Courses
进程调度
　　3. 时间片大小的确定
　　在轮转算法中，时间片的大小对系统性能有很大的
影响。
　　图3-2示出了时间片大小对响应时间的影响，其中图(a)是时间片略大于典型交互的时间，而图(b)
是时间片小于典型交互的时间。图3-3示出了时间片分别为q = 1和q = 4时对平均周转时间的影响。
The Best R&D Courses
进程调度
图3-2 时间片大小对响应时间的影响
The Best R&D Courses
进程调度
作业 进程名 A B C D E 平均
情况 到达时间 0 1 2 3 4
时 间 片 服务时间 4 3 4 2 4
完成时间 15 12 16 9 17
RR
周转时间 15 11 14 6 13 11.8
q=1
带权周转时间 3.75 3.67 3.5 3 3.33 3.46
完成时间 4 7 11 13 17
RR
周转时间 4 6 9 10 13 8.4
q=4
带权周转时间 1 2 2.25 5 3.33 2.5
图3-3 q = 1和q = 4时进程的周转时间
The Best R&D Courses
进程调度
3.3.3 优先级调度算法
　　1. 优先级调度算法的类型
　　优先级进程调度算法，是把处理机分配给就绪队列中优先级最高的进程。这时，又可进一步把
该算法分成如下两种。
　　(1) 非抢占式优先级调度算法。
　　(2) 抢占式优先级调度算法。
The Best R&D Courses
进程调度
　　2. 优先级的类型
　　1) 静态优先级
　　静态优先级是在创建进程时确定的，在进程的整个运行期间保持不变。优先级是利用某一范围
内的一个整数来表示的，例如0～255中的某一整数，又把该整数称为优先数。确定进程优先级大小
的依据有如下三个：
　　(1) 进程类型。
　　(2) 进程对资源的需求。
　　(3) 用户要求。
The Best R&D Courses
进程调度
　　2) 动态优先级
　　动态优先级是指在创建进程之初，先赋予其一个优先级，然后其值随进程的推进或等待时间的
增加而改变，以便获得更好的调度性能。
The Best R&D Courses
进程调度
3.3.4 多队列调度算法
　　如前所述的各种调度算法，尤其在应用于进程调度时，由于系统中仅设置一个进程的就绪队列，
即低级调度算法是固定的、单一的，无法满足系统中不同用户对进程调度策略的不同要求，在多处
理机系统中，这种单一调度策略实现机制的缺点更显突出，由此，多级队列调度算法能够在一定程
度上弥补这一缺点。
The Best R&D Courses
进程调度
3.3.5 多级反馈队列(multileved feedback queue)调度算法
　　1. 调度机制
　　多级反馈队列调度算法的调度机制可描述如下：
　　(1) 设置多个就绪队列。
　　图3-4是多级反馈队列算法的示意图。
The Best R&D Courses
进程调度
图3-4 多级反馈队列调度算法
The Best R&D Courses
进程调度
　　(2) 每个队列都采用FCFS算法。当新进程进入内存后，首先将它放入第一队列的末尾，按FCFS
原则等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可撤离系统。否则，即它在一
个时间片结束时尚未完成，调度程序将其转入第二队列的末尾等待调度；如果它在第二队列中运行
一个时间片后仍未完成，再依次将它放入第三队列，……，依此类推。当进程最后被降到第n队列后，
在第n队列中便采取按RR方式运行。
The Best R&D Courses
进程调度
　　(3) 按队列优先级调度。调度程序首先调度最高优先级队列中的诸进程运行，仅当第一队列空闲
时才调度第二队列中的进程运行；换言之，仅当第1～(i-1)所有队列均空时，才会调度第i队列中的进
程运行。如果处理机正在第i队列中为某进程服务时又有新进程进入任一优先级较高的队列，此时须
立即把正在运行的进程放回到第i队列的末尾，而把处理机分配给新到的高优先级进程。
The Best R&D Courses
进程调度
　　2. 调度算法的性能
　　在多级反馈队列调度算法中，如果规定第一个队列的时间片略大于多数人机交互所需之处理时
间时，便能较好地满足各种类型用户的需要。
　　(1) 终端型用户。
　　(2) 短批处理作业用户。
　　(3) 长批处理作业用户。
The Best R&D Courses
进程调度
3.3.6 基于公平原则的调度算法
　　1. 保证调度算法
　　保证调度算法是另外一种类型的调度算法，它向用户所做出的保证并不是优先运行，而是明确
的性能保证，该算法可以做到调度的公平性。一种比较容易实现的性能保证是处理机分配的公平性。
如果在系统中有n个相同类型的进程同时运行，为公平起见，须保证每个进程都获得相同的处理机时
间1/n。
The Best R&D Courses
进程调度
　　在实施公平调度算法时系统中必须具有这样一些功能：
　　(1) 跟踪计算每个进程自创建以来已经执行的处理时间。
　　(2) 计算每个进程应获得的处理机时间，即自创建以来的时间除以n。
　　(3) 计算进程获得处理机时间的比率，即进程实际执行的处理时间和应获得的处理机时间之比。
　　(4) 比较各进程获得处理机时间的比率。如进程A的比率最低，为0.5，而进程B的比率为0.8，
进程C的比率为1.2等。
　　(5) 调度程序应选择比率最小的进程将处理机分配给它，并让该进程一直运行，直到超过最接近
它的进程比率为止。
The Best R&D Courses
进程调度
　　2. 公平分享调度算法
　　分配给每个进程相同的处理机时间，显然，这对诸进程而言，是体现了一定程度的公平，但如
果各个用户所拥有的进程数不同，就会发生对用户的不公平问题。
The Best R&D Courses
实时调度
　　　　　　3.4 实 时 调 度
　　在实时系统中，可能存在着两类不同性质的实时任务，即HRT任务和SRT任务，它们都联系着
一个截止时间。为保证系统能正常工作，实时调度必须能满足实时任务对截止时间的要求。为此，
实现实时调度应具备一定的条件。
The Best R&D Courses
实时调度
3.4.1 实现实时调度的基本条件
　　1. 提供必要的信息
　　为了实现实时调度，系统应向调度程序提供有关任务的信息：
　　(1) 就绪时间，是指某任务成为就绪状态的起始时间，在周期任务的情况下，它是事先预知的一
串时间序列。
　　(2) 开始截止时间和完成截止时间，对于典型的实时应用，只须知道开始截止时间，或者完成截
止时间。
The Best R&D Courses
实时调度
　　(3) 处理时间，一个任务从开始执行，直至完成时所需的时间。
　　(4) 资源要求，任务执行时所需的一组资源。
　　(5) 优先级，如果某任务的开始截止时间错过，势必引起故障，则应为该任务赋予“绝对”优先
级；如果其开始截止时间的错过，对任务的继续运行无重大影响，则可为其赋予“相对”优先级，
供调度程序参考。
The Best R&D Courses
实时调度
　　2. 系统处理能力强
　　在实时系统中，若处理机的处理能力不够强，则有可能因处理机忙不过，而致使某些实时任务
不能得到及时处理，从而导致发生难以预料的后果。假定系统中有m个周期性的硬实时任务HRT，它
们的处理时间可表示为Ci，周期时间表示为Pi，则在单处理机情况下，必须满足下面的限制条件系统
才是可调度的：
m
C i 1
i 1 P i
The Best R&D Courses
实时调度
　　提高系统处理能力的途径有二：一是采用单处理机系统，但须增强其处理能力，以显著地减少
对每一个任务的处理时间；二是采用多处理机系统。假定系统中的处理机数为N，则应将上述的限制
条件改为：
m
C i N
i 1 Pi
The Best R&D Courses
实时调度
　　3. 采用抢占式调度机制
　　在含有HRT任务的实时系统中，广泛采用抢占机制。这样便可满足HRT任务对截止时间的要求。
但这种调度机制比较复杂。
The Best R&D Courses
实时调度
3.4.2 实时调度算法的分类
　　可以按不同方式对实时调度算法加以分类：① 根据实时任务性质，可将实时调度的算法分为硬
实时调度算法和软实时调度算法；② 按调度方式，则可分为非抢占调度算法和抢占调度算法。
　　1. 非抢占式调度算法
　　(1) 非抢占式轮转调度算法。
　　(2) 非抢占式优先调度算法。
The Best R&D Courses
实时调度
　　2. 抢占式调度算法
　　可根据抢占发生时间的不同而进一步分成以下两种调度算法：
　　(1) 基于时钟中断的抢占式优先级调度算法。
　　(2) 立即抢占(Immediate Preemption)的优先级调度算法。　　
　　图3-5中的(a)、(b)、(c)、(d)分别示出了四种情况的调度时间。
The Best R&D Courses
实时调度
图3-5 实时进程调度
The Best R&D Courses
死锁
3.5.2 计算机系统中的死锁
　　1. 竞争不可抢占性资源引起死锁
　　通常系统中所拥有的不可抢占性资源其数量不足以满足多个进程运行的需要，使得进程在运行
过程中，会因争夺资源而陷入僵局。
The Best R&D Courses
死锁
　　我们可将上面的问题利用资源分配图进行描述，用方块代表可重用的资源(文件)，用圆圈代表进
程，见图3-12所示。
The Best R&D Courses
死锁
图3-12　共享文件时的死锁情况
The Best R&D Courses
死锁
　　2. 竞争可消耗资源引起死锁
　　现在进一步介绍竞争可消耗资源所引起的死锁。图3-13示出了在三个进程之间，在利用消息通
信机制进行通信时所形成的死锁情况。
The Best R&D Courses
死锁
图3-13 进程之间通信时的死锁
The Best R&D Courses
死锁
3.5.3 死锁的定义、必要条件和处理方法
　　1. 死锁的定义
　　在一组进程发生死锁的情况下，这组死锁进程中的每一个进程，都在等待另一个死锁进程所占
有的资源。
The Best R&D Courses
死锁
　　2. 产生死锁的必要条件
　　虽然进程在运行过程中可能会发生死锁，但产生进程死锁是必须具备一定条件的。综上所述不
难看出，产生死锁必须同时具备下面四个必要条件，只要其中任一个条件不成立，死锁就不会发生：
　　(1) 互斥条件。
　　(2) 请求和保持条件。
　　(3) 不可抢占条件。
　　(4) 循环等待条件。
The Best R&D Courses
死锁
　　3. 处理死锁的方法
　　目前处理死锁的方法可归结为四种：
　　(1) 预防死锁。
　　(2) 避免死锁。
　　(3) 检测死锁。
　　(4) 解除死锁。
The Best R&D Courses
死锁
　　　　3.6 预 防 死 锁
　　预防死锁的方法是通过破坏产生死锁的四个必要条件中的一个或几个，以避免发生死锁。由于
互斥条件是非共享设备所必须的，不仅不能改变，还应加以保证，因此主要是破坏产生死锁的后三
个条件。
The Best R&D Courses
死锁
3.6.1 破坏“请求和保持”条件
　　为了能破坏“请求和保持”条件，系统必须保证做到：当一个进程在请求资源时，它不能持有
不可抢占资源。该保证可通过如下两个不同的协议实现：
　　1. 第一种协议
　　该协议规定，所有进程在开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资
源。
The Best R&D Courses
死锁
　　2. 第二种协议
　　该协议是对第一种协议的改进，它允许一个进程只获得运行初期所需的资源后，便开始运行。
The Best R&D Courses
死锁
3.6.2 破坏“不可抢占”条件
　　为了能破坏“不可抢占”条件，协议中规定，当一个已经保持了某些不可被抢占资源的进程，
提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。
这意味着进程已占有的资源会被暂时地释放，或者说是被抢占了，从而破坏了“不可抢占”条件。
The Best R&D Courses
死锁
3.6.3 破坏“循环等待”条件
　　一个能保证“循环等待”条件不成立的方法是，对系统所有资源类型进行线性排序，并赋予不
同的序号。
The Best R&D Courses
死锁
　　　　3.7 避 免 死 锁
　　避免死锁同样是属于事先预防的策略，但并不是事先采取某种限制措施，破坏产生死锁的必要
条件，而是在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。这种方法所施加
的限制条件较弱，可能获得较好的系统性能，目前常用此方法来避免发生死锁。
The Best R&D Courses
死锁
3.7.1　系统安全状态
　　在死锁避免方法中，把系统的状态分为安全状态和不安全状态。当系统处于安全状态时，可避
免发生死锁。反之，当系统处于不安全状态时，则可能进入到死锁状态。
　　1. 安全状态
　　在该方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配
的安全性。
The Best R&D Courses
死锁
　　2. 安全状态之例
　　假定系统中有三个进程P1、P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3
分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台
空闲未分配，如下表所示：
进 程 最 大 需 求 已 分 配 可 用
P1 10 5 3
P2 4 2
P3 9 2
The Best R&D Courses
死锁
　　3. 由安全状态向不安全状态的转换
　　如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。
The Best R&D Courses
死锁
3.7.2 利用银行家算法避免死锁
　　最有代表性的避免死锁的算法是Dijkstra的银行家算法。起这样的名字是由于该算法原本是为银
行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。在OS中也
可用它来实现避免死锁。
The Best R&D Courses
死锁
　　1. 银行家算法中的数据结构
　　为了实现银行家算法，在系统中必须设置这样四个数据结构，分别用来描述系统中可利用的资
源、所有进程对资源的最大需求、系统中的资源分配，以及所有进程还需要多少资源的情况。
　　(1) 可利用资源向量Available。
　　(2) 最大需求矩阵Max。
　　(3) 分配矩阵Allocation。
　　(4) 需求矩阵Need。
The Best R&D Courses
死锁
　　2. 银行家算法
　　设Requesti是进程Pi的请求向量，如果Request i[j]=K，表示进程Pi需要K个Rj类型的资源。当
Pi发出资源请求后，系统按下述步骤进行检查：
　　(1) 如果Request i[j]≤Need[i, j]，便转向步骤(2)； 否则认为出错，因为它所需要的资源数已
超过它所宣布的最大值。
　　(2) 如果Request i[j]≤Available[j]，便转向步骤(3)； 否则，表示尚无足够资源，Pi须等待。
The Best R&D Courses
死锁
　　(3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：
　Available[j] = Available[j] - Request i[j];
　 　Allocation[i, j] = Allocation[i, j] + Request i[j];
　　Need[i, j] = Need[i, j] - Request i[j];
　　(4) 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源
分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程
Pi等待。
The Best R&D Courses
死锁
　　3. 安全性算法
　　系统所执行的安全性算法可描述如下：
　　(1) 设置两个向量：① 工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，
它含有m个元素，在执行安全算法开始时，Work := Available；② Finish：它表示系统是否有足够
的资源分配给进程，使之运行完成。开始时先做Finish[i] := false；当有足够资源分配给进程时，
再令Finish[i] := true。
The Best R&D Courses
死锁
　　(2) 从进程集合中找到一个能满足下述条件的进程：
　　① Finish[i]=false;
　　② Need[i, j]≤Work[j];
　　若找到，执行步骤(3)，否则，执行步骤(4)。
　　(3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
　　　　Work[j] = Work[j]+Allocation[i, j];
　　　　Finish[i] =true;
　　　　go to step 2;
　　(4) 如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全
状态。
The Best R&D Courses
死锁
　　4. 银行家算法之例
　　假定系统中有五个进程{P0, P1, P2, P3, P4}和三类资源{A, B, C}，各种资源的数量分别为10、
5、7，在T0时刻的资源分配情况如图3-15所示。
The Best R&D Courses
死锁
资源 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
(2 3 0)
P1 3 2 2 2 0 0 1 2 2
(3 0 2) (0 2 0)
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
图3-15 T0时刻的资源分配表
The Best R&D Courses
死锁
　　(1) T0时刻的安全性：利用安全性算法对T0时刻的资源分配情况进行分析(如图3-16所示)可知，
在T0时刻存在着一个安全序列{P1, P3, P4, P2, P0}，故系统是安全的。
The Best R&D Courses
死锁
资源 Max Need Allocation Work+Allocation
情况 Finish
进 程 A B C A B C A B C A B C
P1 3 3 2 1 2 2 2 0 0 5 3 2 true
P3 5 3 2 0 1 1 2 1 1 7 4 3 true
P4 7 4 3 4 3 1 0 0 2 7 4 5 true
P2 7 4 5 6 0 0 3 0 2 10 4 7 true
P0 10 4 7 7 4 3 0 1 0 10 5 7 true
图3-16 T0时刻的安全序列
The Best R&D Courses
死锁
　　(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-17所示。
The Best R&D Courses
死锁
资源 Work Need Allocation Work+Allocation
情况 Finish
进 程 A B C A B C A B C A B C
P1 2 3 0 0 2 0 3 0 2 5 3 2 true
P3 5 3 2 0 1 1 2 1 1 7 4 3 true
P4 7 4 3 4 3 1 0 0 2 7 4 5 true
P0 7 4 5 7 4 3 0 1 0 7 5 5 true
P2 7 5 5 6 0 0 3 0 2 10 5 7 true
图3-17 P1申请资源时的安全性检查
The Best R&D Courses
死锁
　　(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发出请求向量Request0(0，2，0)，系统按银行家算法进行检查：
　　① Request0(0，2，0)≤Need0(7，4，3)；
　　② Request0(0，2，0)≤Available(2，3，0)；
　　③ 系统暂时先假定可为P0分配资源，并修改有关数据，如图3-18所示。
The Best R&D Courses
死锁
资源 Allocation Need Available
情况
进 程 A B C A B C A B C
P0 0 3 0 7 2 3 2 1 0
P1 3 0 2 0 2 0
P2 3 0 2 6 0 0
P3 2 1 1 0 1 1
P4 0 0 2 4 3 1
图3-18 为P0分配资源后的有关资源数据
The Best R&D Courses
死锁
　　(5) 进行安全性检查：可用资源Available(2，1，0)已不能满足任何进程的需要，故系统进入不
安全状态，此时系统不分配资源。
The Best R&D Courses
死锁
　　 3.8 死锁的检测与解除
　　如果在系统中，既不采取死锁预防措施，也未配有死锁避免算法，系统很可能会发生死锁。在
这种情况下，系统应当提供两个算法：
　　① 死锁检测算法。该方法用于检测系统状态，以确定系统中是否发生了死锁。
　　② 死锁解除算法。当认定系统中已发生了死锁，利用该算法可将系统从死锁状态中解脱出来。
The Best R&D Courses
死锁
3.8.1 死锁的检测
　　为了能对系统中是否已发生了死锁进行检测，在系统中必须：① 保存有关资源的请求和分配信
息；② 提供一种算法，它利用这些信息来检测系统是否已进入死锁状态。
　　1. 资源分配图(Resource Allocation Graph)
　　系统死锁，可利用资源分配图来描述。
The Best R&D Courses
死锁
　　2．死锁定理
　　我们可以利用把资源分配图加以简化的方法(图3-19)，来检测当系统处于S状态时，是否为死锁
状态。简化方法如下：
　　(1) 在资源分配图中，找出一个既不阻塞又非独立的进程结点Pi。在顺利的情况下，Pi可获得所
需资源而继续运行，直至运行完毕，再释放其所占有的全部资源，这相当于消去Pi的请求边和分配边，
使之成为孤立的结点。在图3-20(a)中，将P1的两个分配边和一个请求边消去，便形成图(b)所示的情
况。
The Best R&D Courses
死锁
图3-20 资源分配图的简化
The Best R&D Courses
死锁
　　(2) P1释放资源后，便可使P2获得资源而继续运行，直至P2完成后又释放出它所占有的全部资
源，形成图(c)所示的情况，即将P2的两条请求边和一条分配边消去。
　　(3) 在进行一系列的简化后，若能消去图中所有的边，使所有的进程结点都成为孤立结点，则称
该图是可完全简化的；若不能通过任何过程使该图完全简化，则称该图是不可完全简化的。
The Best R&D Courses
死锁
3.8.2 死锁的解除
　　1. 终止进程的方法
　　1) 终止所有死锁进程
　　这是一种最简单的方法，即是终止所有的死锁进程，死锁自然也就解除了，但所付出的代价可
能会很大。因为其中有些进程可能已经运行了很长时间，已接近结束，一旦被终止真可谓“功亏一
篑”，以后还得从头再来。还可能会有其它方面的代价，在此不再一一列举。
The Best R&D Courses
死锁
　　2) 逐个终止进程
　　稍微温和的方法是，按照某种顺序，逐个地终止进程，直至有足够的资源，以打破循环等待，
把系统从死锁状态解脱出来为止。但该方法所付出的代价也可能很大。因为每终止一个进程，都需
要用死锁检测算法确定系统死锁是否已经被解除，若未解除还需再终止另一个进程。另外，在采取
逐个终止进程策略时，还涉及到应采用什么策略选择一个要终止的进程。选择策略最主要的依据是，
为死锁解除所付出的“代价最小”。但怎么样才算是“代价最小”，很难有一个精确的度量。
The Best R&D Courses

展开更多......

收起↑