第3章处理机调度与死锁

每个系统在选择作业调度算法时，既应考虑用户的 要求，又能确保系统具有较高的效率。在每次执行作业 调度时，都须做出以下两个决定。 1)决定接纳多少个作业 作业调度每次要接纳多少个作业进入内存，取决于多 道程序度(Degree of Multiprogramming)，即允许多少 个作业同时在内存中运行。当内存中同时运行的作业数 目太多时，可能会影响到系统的服务质量，比如，使周 转时间太长。但如果在内存中同时运行作业的数量太少 时，又会导致系统的资源利用率和系统吞吐量太低，因 此，多道程序度的确定应根据系统的规模和运行速度等 情况做适当的折衷。
每当作业进入系统时，系统便为每个作业建立一个 JCB，根据作业类型将它插入相应的后备队列中。作业调 度程序依据一定的调度算法来调度它们，被调度到的作 业将会装入内存。在作业运行期间，系统就按照JCB中的 信息对作业进行控制。当一个作业执行结束进入完成状 态时，系统负责回收分配给它的资源，撤消它的作业控 制块。
2)决定接纳哪些作业 应将哪些作业从外存调入内存，这将取决于所采用的 调度算法。最简单的是先来先服务调度算法，这是指将 最早进入外存的作业最先调入内存；较常用的一种算法 是短作业优先调度算法，是将外存上最短的作业最先调 入内存；另一种较常用的是基于作业优先级的调度算法， 该算法是将外存上优先级最高的作业优先调入内存；比 较好的一种算法是“响应比高者优先”的调度算法。
作业步：通常，在作业运行期间，每个作业都必须 经过若干个相对独立，又相互关联的顺序加工步骤才能 得到结果，我们把其中的每一个加工步骤称为一个作业 步，各作业步之间存在着相互联系，往往是把上一个作 业步的输出作为下一个作业步的输入。 作业流：若干个作业进入系统后，被依次存放在外存 上，这便形成了输入的作业流；在操作系统的控制下， 逐个作业进行处理，于是便形成了处理作业流。

进程管理
进程管理
【解答】 ①系统资源总数向量为（9, 3, 6） 各进程对资源需求矩阵为： ②采用银行家算法进行计算分析可知：
进程管理
2、调度算法
现有如下作业序列：作业1（提交时间8.00，运行时间 1.00）；作业2（提交时间8.30，运行时间3.00）；作 业3（提交时间9.00，运行时间0.10）；作业4（提交 时间9.30，运行时间0.50）（单位：小时，以十进制 计）。 试用先来先服务和短作业优先调度算法处 理该作业序列，问哪种作业调度算法性能更好（要求给 出计算的数据和必要的步骤）。(华中科技大学2001年 试题)
处理机调度作业
进程管理
1、银行家算法
某系统有R1、R2和R3共3种资源，在T0时刻P1、P2、P3 和P4这4个进程对资源的占用和需求情况见表2.2，此刻 系统的可用资源向量为（2, 1, 2），问题：(中科院软 件所1999年试题) ①将系统中各种资源总数和此刻各进程对各资源的需求 数目用向量或矩阵表示出来；②如果此时P1和P2均发出 资源请求向量Request(1, 0, 1)，为了保持系统安全 性，应该如何分配资源给这两个进程？说明你所采用策 略的原因；③如果②中两个请求立刻得到满足后，系统 此刻是否处于死锁0
40
50
60
70
80
90
J1: IO2(30ms), CPU(10ms), IO1(30ms), CPU(10ms). J2: IO1(20ms), CPU(20ms), IO2(40ms). J3: CPU(30ms), IO1(20ms).
进程管理
【解答】 （1） 由上图可知：J1从开始到完成的时间是0～ 80msJ2从开始到完成的时间是0～90msJ3从开始到 完成的时间是0～90ms （2） 三个作业全部完成时CPU的利用率是：

抢占方式: 允许调度程序根据某种原则（时间片、优先权、短 进程优先），停止正在执行的进程，而将处理机重新分配 给另一进程。
有利于处理紧急任务，故实时与分时系统中常采用。
3、中级调度（中程/交换调度）
在内存和外存对换区之间按照给定的原则和策略 选择进程对换，以解决内存紧张问题，从而提高内存的 利用率和系统吞吐量，常用于分时系统或具有虚拟存储 器的系统中。
在多道批处理系统中，作业是用户提交给系统的一项相 对独立的工作。操作员把用户提交的作业通过相应的输入设 备输入到磁盘存储器，并保存在一个后备作业队列中。再由 作业调度程序将其从外存调入内存。
3.2.1 批处理系统中的作业 1. 作业和作业步 (1) 作业(Job)。 (2) 作业步(Job Step)。
FCFS 算法比较有利于长作业(进程)，而不利于短作业(进 程)。
进程名 到达时间
服务时间 开始执行时间 完成时间
周转时间
带权周转 时间
A
0
1
0
1
1
1
B
1
100
1
101
100
1
C
2
1
101
102
100
100
D
3
100
102
202
199
1.99
平均周转时间:((1-0)+(101-1)+(102-2)+(202-3)）/4=100 平均等待时间:((0-0)+(1-1)+(101-2)+(102-3))/4 = 49.5
高响应比优先算法是如何实现的呢? 如果我们能为每个 作业引入一个动态优先级，即优先级是可以改变的，令它随 等待时间延长而增加，这将使长作业的优先级在等待期间不 断地增加，等到足够的时间后，必然有机会获得处理机。该 优先级的变化规律可描述为：

第三章处理机调度与死锁1. 高级调度与低级调度的主要任务是什么？为什么要引入中级调度？高级调度的主要任务：用于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程，分配必要的资源，然后，再将新创建的进程插入就绪队列上，准备执行。

低级调度的主要任务：用于决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行将处理机分配给该进程的具体操作。

引入中级调度的主要目的：是为了提高系统资源的利用率和系统吞吐量。

10. 试比较FCFS和SPF两种进程调度算法相同点：两种调度算法都是既可用于作业调度，也可用于进程调度；不同点：FCFS调度算法每次调度都是从后备队列中选择一个或是多个最先进入该队列的作业，将它们调入内存，为它们分配资源，创建进程，然后插入到就绪队列中。

该算法有利于长作业/进程，不利于短作业/进程。

SPF调度算法每次调度都是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存中运行。

该算法有利于短作业/进程，不利于长作业/进程。

15. 按调度方式可将实时调度算法分为哪几种？按调度方式不同，可分为非抢占调度算法和抢占调度算法两种。

18. 何谓死锁？产生死锁的原因和必要条件是什么？a.死锁是指多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进；b.产生死锁的原因有二，一是竞争资源，二是进程推进顺序非法；c.必要条件是: 互斥条件，请求和保持条件，不剥夺条件和环路等待条件。

19．在解决死锁问题的几个方法中，哪种方法最易于实现？哪种方法是资源利用率最高？解决/处理死锁的方法有预防死锁、避免死锁、检测和解除死锁，其中预防死锁方法最容易实现，但由于所施加的限制条件过于严格，会导致系统资源利用率和系统吞吐量降低；而检测和解除死锁方法可是系统获得较好的资源利用率和系统吞吐量。

20. 请详细说明可通过哪些途径预防死锁?a.摒弃"请求和保持"条件：系统规定所有进程开始运行之前，都必须一次性地申请其在整个运行过程所需的全部资源，但在分配资源时，只要有一种资源不能满足某进程的要求，即使其它所需的各资源都空闲，也不分配给该进程，而让该进程等待；b.摒弃"不剥夺"条件：系统规定，进程是逐个地提出对资源的要求的。