第三章 处理机调度与死锁
一、名词解释
1．作业
不仅包含了程序和数据，还配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存的。
2．处理机调度
是多道程序系统中对处理机资源进行分配。
3．周转时间
指从作业被提交给系统开始，到作业完成为止的这段时间间隔。
4．死锁
一个进程集合中的每个进程都在等待只能由该集合中其他进程才能引发的事件，那么这组进程进入死锁状态。
* 死锁概念，造成死锁原因，如何避免死锁
5．临时性资源
临时性资源又称可消耗性资源，它是在进程运行期间，由进程动态地创建和消耗的。可消耗性资源通常是由生产者进程创建，由消费者进程消耗。
* 调度的所有算法（优先级的设计）
* 管程如同封装
二、选择题
1．作业调度是从处于（后备）状态的队列中选取作业投入运行，（周转时间）是指作业进入系统到作业完成所经过的时间间隔，（最高优先权优先）算法不适合作业调度。
A：（1）运行；（2）提交；（3）后备；（4）完成；（5）阻塞；（6）就绪。
B：（1）响应时间；（2）周转时间；（3）运行时间；（4）等待时间；（5）触发时间。
C：（1）先来先服务；（2）短作业优先；（3）最高优先权优先；（4）时间片轮转。
2．如果为每一个作业只建立一个进程，则为了照顾短作业用户，应采用（短作业优先）；为照顾紧急作业的用户，应采用（基于优先权的剥夺调度算法）；为能实现人机交互作用应采用（时间片轮转算法）；为了兼顾短作业和长时间等待的作业应采用（高响应比优先）；为了使短作业、长作业及交互型作业用户都比较满意应采用（多级反馈队列调度算法）；为了使作业的平均周转时间最短应采用（短作业优先算法）。
3．系统产生死锁是指（若干进程等待被其他进程所占用而又不可能被释放的资源）。产生死锁的基本原因是（资源分配不足）和（进程推进顺序不当），产生死锁的四个必要条件是互斥条件、（请求和保持条件）、不剥夺条件和（环路条件）。
4．下述解决死锁的方法中，属于死锁预防策略的是（资源有序分配法），属于死锁避免策略的是（银行家算法）。
5．死锁的预防是通过破坏产生死锁的四个必要条件来实现的。下列方法中，（一次性分配策略）破坏了“请求与保持”条件，（资源有序分配策略）破坏了“循环等待”条件。
A，B：（1）银行家算法；（2）一次性分配策略；（3）资源有序分配策略；（4）SPOOLing技术。
三、填空题
1．作业的输入方式包括（联机输入）、（脱机输入）、（直接耦合）和（SPOOLING系统）。
2．作业在其生存期间会经历（收容）、（运行）、执行以及（完成）等状态。
3．处理机调度的类型分为（低级调度）、中级调度和（高级调度）。其中，中级调度又称为（内存调度）和（交换调度）。
4．优先数的确定分为（静态优先数）和（动态优先数）两种。
5．根据响应时间分类，可以将实时系统分为（强实时系统）、（弱实时系统）和一般实时系统。
6．死锁的处理方法包括（预防）、（避免）、（检测）和（解除）。
四、判断题
1．（F）系统处于不安全状态必然会导致死锁。
2．（T）竞争可同时共享的资源，不会导致系统进入死锁状态。
3．（F）计算作业的优先权应高于I/O型作业的优先权。
4．（F）资源要求多的作业，其优先权应高于资源要求少的作业。
5．（T）在动态优先权时，随着进程执行时间的增加，其优先权降低。
6．（T）预防死锁设置的限制条件比避免死锁严格，不利于进程的并发执行。
7．（F）实时系统的输出结果的正确性仅仅依赖于结果的正确性。
8．（T）在多级反馈队列调度算法中，优先权越高的队列，其执行的时间片越短。
9．（F）响应比是等待时间与要求服务的时间之比。 //响应比=作业周转时间/作业执行时间
10．（T）作业的概念一般用于早期批处理系统和现在的大型机、巨型机系统中，对于微机和工作站系统一般不使用作业的概念。
五、问答题
1. 假设一个系统中有5个进程，它们的到达时间和服务时间如下表所示，忽略IO及其他系统开销时间，若分别按照先来先服务（FCFS）、非抢占和抢占的短作业优先（SJF）、高响应比优先（HRRN）和时间片轮转（RR，时间片为1）算法进行CPU调度，请给出各个进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。
进程 | 到达时间 | 服务时间 |
A | 0 | 3 |
B | 2 | 6 |
C | 4 | 4 |
D | 6 | 5 |
E | 8 | 2 |
FCFS：
进程 | 完成时间 | 周转时间 | 带权周转时间 | 平均周转时间 | 平均带权周转时间 |
A | 3 | 3 | 1 | 8.6 | 2.56 |
B | 9 | 7 | 1.17 | ||
C | 13 | 9 | 2.25 | ||
D | 18 | 12 | 2.4 | ||
E | 20 | 12 | 6 |
非抢占的SJF：
进程 | 完成时间 | 周转时间 | 带权周转时间 | 平均周转时间 | 平均带权周转时间 |
A | 3 | 3 | 1 | 7.6 | 1.84 |
B | 9 | 7 | 1.17 | ||
E | 11 | 3 | 1.5 | ||
C | 15 | 11 | 2.75 | ||
D | 20 | 14 | 2.8 |
抢占的SJF：
进程 | 完成时间 | 周转时间 | 带权周转时间 | 平均周转时间 | 平均带权周转时间 |
A | 3 | 3 | 1 | 7.2 | 1.59 |
C | 8 | 4 | 1 | ||
E | 10 | 2 | 1 | ||
B | 15 | 13 | 1.8 | ||
D | 20 | 14 | 9 |
HRRN：
进程 | 完成时间 | 周转时间 | 带权周转时间 | 平均周转时间 | 平均带权周转时间 |
A | 3 | 3 | 1 | 8 | 2.14 |
B | 9 | 7 | 1.17 | ||
C | 13 | 9 | 2.25 | ||
E | 15 | 7 | 3.5 | ||
D | 20 | 14 | 2.8 |
时间片轮转（RR，时间片为1）：
进程 | 完成时间 | 周转时间 | 带权周转时间 | 平均周转时间 | 平均带权周转时间 |
A | 4 | 4 | 1.33 | 10.8 | 2.71 |
E | 15 | 7 | 3.5 | ||
C | 17 | 13 | 3.25 | ||
B | 18 | 16 | 2.67 | ||
D | 20 | 14 | 2.8 |
AA BA BC BD CB ED CB EDCB DD
优先新的进程，执行完的进程到队尾。
被剥夺的进程回到就绪队列的末尾，重新排队，等待再次运行
2. 若有3个周期性任务，任务A要求每20ms执行一次，执行时间为10ms；任务B要求每50ms执行一次，执行时间为10ms；任务C要求每50ms执行一次，执行时间为15ms。应如何按最低松弛度优先算法对它们进行CPU调度？（答案格式：时间线方式）
A1 C1 A2 B1 A3 C2 A4 B2 A5
3. 在银行家算法中，若出现下面的资源分配情况：
进程 | Max | Need | Available |
P0 | 0 0 4 4 | 0 0 1 2 | 1 6 2 2 |
P1 | 2 7 5 0 | 1 7 5 0 | |
P2 | 3 6 10 10 | 2 3 5 6 | |
P3 | 0 9 8 4 | 0 6 5 2 | |
P4 | 0 6 6 10 | 0 6 5 6 |
(1) 请计算分配矩阵的值，并判断该状态是否安全？
(2) 若进程P2提出请求Request(1,2,2,2)，系统能否将资源分配给它？
(3) 如果系统立即满足P2的上述请求，请问系统是否立即进入死锁状态？
（1）
计算分配矩阵的值：
进程 | Max | Allocation | Need | Available |
P0 | 0 0 4 4 | 0 0 3 2 | 0 0 1 2 | 1 6 2 2 |
P1 | 2 7 5 0 | 1 0 0 0 | 1 7 5 0 | |
P2 | 3 6 10 10 | 1 3 5 4 | 2 3 5 6 | |
P3 | 0 9 8 4 | 0 3 3 2 | 0 6 5 2 | |
P4 | 0 6 6 10 | 0 0 1 4 | 0 6 5 6 |
判断安全性：利用安全性算法对此刻的资源分配情况进行分析，存在一个安全序列{P0,P3,P1,P2,P4}，故系统是安全的。
进程 | Work | Need | Allocation | Work+Allocation | Finish |
P0 | 1 6 2 2 | 0 0 1 2 | 0 0 3 2 | 1 6 5 4 | TRUE |
P3 | 1 6 5 4 | 0 6 5 2 | 0 3 3 2 | 1 9 8 6 | TRUE |
P1 | 1 9 8 6 | 1 7 5 0 | 1 0 0 0 | 2 9 8 6 | TRUE |
P2 | 2 9 8 6 | 2 3 5 6 | 1 3 5 4 | 3 12 13 10 | TRUE |
P4 | 3 12 13 10 | 0 6 5 6 | 0 0 1 4 | 3 12 14 14 | TRUE |
（2）
P2提出请求向量Request(1,2,2,2)，系统按银行家算法进行检查：
1 Request（1，2，2，2）< Need（2，3，5，6）；
2 Request（1，2，2，2）< Available（1，6，2，2）；
3系统先假定可以为P2分配资源，并修改Available，Allocation，Need向量；
进程 | Max | Allocation | Need | Available |
P0 | 0 0 4 4 | 0 0 3 2 | 0 0 1 2 | 0 4 0 0 |
P1 | 2 7 5 0 | 1 0 0 0 | 1 7 5 0 | |
P2 | 3 6 10 10 | 2 5 7 6 | 1 1 3 4 | |
P3 | 0 9 8 4 | 0 3 3 2 | 0 6 5 2 | |
P4 | 0 6 6 10 | 0 0 1 4 | 0 6 5 6 |
4进行安全性检查：可用资源Available(0,4,0,0)已经不能满足任何进程的需求，故系统进入不安全状态，此时系统不分配资源。
（3）
如果系统立即满足P2的上述请求，并不会马上进入死锁状态。因为此时上述进程并没有申请新的资源，并因得不到资源而进入阻塞状态。只有当上述进程提出新的请求，并导致所有没有执行完的多个进程因得不到资源而阻塞时，系统才进入死锁状态。