分类： LINUX
2012-08-29 16:01:08
第3章 处理机调度与死锁习题
三、名词解释
高级调度: 又称作业调度，用于决定把外存上处于后备队列中的哪些作业调入内存，并为之创建进程，排在就绪对列上。
低级调度: 又称进程调度，用于选择就绪队列上哪个进程可以获得处理机执行。
中级调度: 又称对换调度，用于将那些暂时不能运行的进程由内存调至外存，排在挂起对列
中，待这些进程重又具备运行条件，且内存又有空闲，将其重新由外存调入内存，排在就绪
队列中。
死锁: 指在多道程序系统中，多个进程在运行过程中因争夺资源造成的一种僵局。
死锁避免: 不需事先采用各种限制措施去破坏产生死锁的必要条件，而是在资源的动态分配过程中，用某种方式去防止系统进入不安全状态，从而避免发生死锁。
进程同步: 程间共同完成一项任务时直接发生相互作用的关系，也就是说，这些具有伙伴关系的进程在执行时间次序上必须遵循确定的规律。
进程互斥: 逻辑上本来完全独立的若干进程，由于竞争同一个资源而产生的相互制约关系。
四、问答题
1、设在单道批处理系统中有四道作业，它们提交的时刻及运行时间如下：
|
作业号 |
提交时刻（h） |
运行时间（h） |
|
1 |
8.0 |
1.0 |
|
2 |
8.5 |
0.5 |
|
3 |
9.0 |
0.2 |
|
4 |
9.1 |
0.1 |
请分别给出在算法FCFS、SJF和HRN中这组作业的调度顺序、平周转时间和平均带权周转时间。
【解答】
FCFS算法调度顺序：1，2，3，4，作业运行情况如下表
|
作业号 |
开始时间 |
完成时间 |
周转时间 |
带权周转时间 |
|
1 |
8.0 |
9.0 |
1.0 |
1.0 |
|
2 |
9.0 |
9.5 |
1.0 |
2.0 |
|
3 |
9.5 |
9.7 |
0.7 |
3.5 |
|
4 |
9.7 |
9.8 |
0.7 |
7.0 |
平均周转时间T=(1.0+1.0+0.7+0.7)/4=0.85
平均带权周转时间W=(1.0+2.0+3.5+7.0)/4=3.375
SJF算法调度顺序：1，3，4，2，作业运行情况如下表
|
作业号 |
开始时间 |
完成时间 |
周转时间 |
带权周转时间 |
|
1 |
8.0 |
9.0 |
1.0 |
1.0 |
|
2 |
9.3 |
9.8 |
1.3 |
2.6 |
|
3 |
9.0 |
9.2 |
0.2 |
1.0 |
|
4 |
9.2 |
9.3 |
0.2 |
2.0 |
平均周转时间T=(1.0+1.3+0.2+0.2)/4=0.675
平均带权周转时间W=(1.0+2.6+1.0+2.0)/4=1.65
HRN算法调度顺序：1，2，4，3，作业运行情况如下表
|
作业号 |
开始时间 |
完成时间 |
周转时间 |
带权周转时间 |
|
1 |
8.0 |
9.0 |
1.0 |
1.0 |
|
2 |
9.0 |
9.5 |
1.0 |
2.0 |
|
3 |
9.6 |
9.8 |
0.8 |
4.0 |
|
4 |
9.5 |
9.6 |
0.5 |
5.0 |
平均周转时间T=(1.0+1.0+0.8+0.5)/4=0.825
平均带权周转时间W=(1.0+2.0+4.0+5.0)/4=3.0
2、有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法，有如下表所示的作业序列，数值越小优先级越高。
|
作业名 |
到达时间 |
运行时间 |
优先数 |
|
A |
10:00 |
40min |
5 |
|
B |
10:20 |
30min |
3 |
|
C |
10:30 |
50min |
4 |
|
D |
10:50 |
20min |
6 |
① 列出所有作业进入内存的时间和结束时间。
② 计算平均周转时间。
【解答】 每个作业的运行将经历两级调度：作业调度和进程调度。只有当作业装入内存后，方能参与进程调度。每次只能有两道作业进入系统内存。
（1）作业进入内存时间和结束时间如下表
|
作业号 |
进入内存时间 |
结束时间 |
|
A |
10:00 |
11:10 |
|
B |
10:20 |
10:50 |
|
C |
11:10 |
12:00 |
|
D |
10:50 |
12:20 |
（2）各作业执行时的周转时间为：
作业A：70分钟 作业 B：30分钟 作业C：90分钟 作业D：90分钟
作业的平均周转时间T=(70+30+90+90)/4=70分钟。
3、假定某计算机系统有R1和R2两类可再使用资源，其中R1有2个单位，R2有1个单位。它们被进程P1和P2所共享，且已知两个进程均以如下顺序使用两类资源。-->申请R1-->申请R2-->申请R1-->释放R1-->释放R2-->释放R1-->
试求出系统运行过程中可能到达的死锁点，并画出死锁点的资源分配图。
答：当两个进程都执行完第1步（都占有了资源R1）时，系统进入不安全状态。这时，无论哪个进程执行完第2步，系统都将进入死锁状态。可能到达的死锁点是：进程P1占有一个单位的R1和一个单位的R2，而进程P2占有一个单位的R1。或者，正好相反。此时系统已无空闲资源，而P1和P2两个进程都不释放自己的资源并申请对方的资源，从而造成死锁。
死锁点的资源分配图（进程—资源图）如图所示。
4、某系统有同类互斥资源m个，供n个进程共享使用。如果每个进程最多申请x个资源（1≤x≤m），试证明：当n(x-1)+1≤m时，系统不会发生死锁。
证明：因为每个进程最多申请x个资源，所以最坏情况是每个进程都得到了（x-1）个资源，并且现在均需申请最后一个资源。此时，系统剩余资源数为m-n(x-1)，于是只要系统中至少还有一个资源可供使用，就可以使这n个进程中某个进程得到其所需要的全部资源，并能够继续执行到完成，归还资源可供其他进程使用。因而不会发生死锁。即只要 m-n(x-1)≥1时，系统就一定不会发生死锁。亦即当n(x-1)+1≤m时，系统不会发生死锁。
5、n个进程共享某种资源R（该资源共有m个可分配单位），每个进程一次一个地申请或释放资源单位。假设每个进程对该资源的最大需求量均小于m，且各进程最大需求量之和小于m+n，试证明该系统中不可能发生死锁。
解：设max（i）表示第i个进程的最大资源需求量，need（i）表示第i个进程还需要的资源量，alloc（i）表示第i个进程已分配的资源量。由题中所给条件可知：
max（1）＋…＋max（n）=（need（1）＋…＋need（n））＋（alloc（1）+…＋alloc（n））
alloc（1）＋…＋alloc（n）= m
另一方面所有进程将陷入无限等待状态。
由上述两式可得：need（1）＋…＋need（n）
上式表示死锁发生后，n个进程还需要的资源量之和小于n，这意味着此刻至少存在一个进程i，need（i）=0，即它已获得了所需要的全部资源。既然该进程已获得了它所需要的全部资源，那么它就能执行完成并释放它占有的资源，这与前面的假设矛盾，从而证明在这个系统中不可能发生死锁。
6、下表给出系统某时刻的资源分配情况。
|
资源 进程 |
Allocation |
Need |
Available | ||||||
|
R1 |
R2 |
R3 |
R1 |
R2 |
R3 |
R1 |
R2 |
R3 | |
|
A |
3 |
1 |
1 |
1 |
0 |
0 |
1 |
2 |
0 |
|
B |
0 |
0 |
0 |
0 |
1 |
2 | |||
|
C |
1 |
1 |
0 |
3 |
0 |
0 | |||
|
D |
1 |
0 |
1 |
0 |
1 |
0 | |||
|
E |
0 |
0 |
0 |
2 |
1 |
0 | |||
试问：（1）该状态是否安全？
（2）若进程B提出请求RequestB（0，1，0），系统能否将资源分配给它？
|
资源 进程 |
Allocation |
Need |
work |
Work+ Allocation |
Finish | ||||||||
|
R1 |
R2 |
R3 |
R1 |
R2 |
R3 |
R1 |
R2 |
R3 |
R1 |
R2 |
R3 | ||
|
A |
3 |
1 |
1 |
1 |
0 |
0 |
1 |
2 |
0 |
4 |
3 |
1 |
TRUE |
|
C |
1 |
1 |
0 |
3 |
0 |
0 |
4 |
3 |
1 |
5 |
4 |
1 |
TRUE |
|
D |
1 |
0 |
1 |
0 |
1 |
0 |
5 |
4 |
1 |
6 |
4 |
2 |
TRUE |
|
E |
0 |
0 |
0 |
2 |
1 |
0 |
6 |
4 |
2 |
6 |
4 |
2 |
TRUE |
|
B |
0 |
0 |
0 |
0 |
1 |
2 |
6 |
4 |
2 |
6 |
4 |
2 |
TRUE |
(1)能找到安全序列存在，其中之一为：A->C->D->E->B，所以该系统处于安全状态。
（2）①：RequestB（0，1，0）≤NeedB（0,1,2）
②：RequestB（0，1，0）≤Available（1,2,0）
③：假设可将资源分配给B，并修改有关数据：
|
资源 进程 |
Allocation |
Need |
Available | ||||||
|
R1 |
R2 |
R3 |
R1 |
R2 |
R3 |
R1 |
R2 |
R3 | |
|
A |
3 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
|
B |
0 |
1 |
0 |
0 |
0 |
2 | |||
|
C |
1 |
1 |
0 |
3 |
0 |
0 | |||
|
D |
1 |
0 |
1 |
0 |
1 |
0 | |||
|
E |
0 |
0 |
0 |
2 |
1 |
0 | |||
进入安全检查，发现任有安全序列存在，其中之一为：D->A->C->E->B。所以，当进程B提出请求RequestB（0，1，0），系统能将资源分配给它。
7、什么是死锁？产生死锁的原因和必要条件？
死锁是指在多道程序系统中，多个进程在运行过程中因争夺资源造成的一种僵局。
产生原因：（1）竞争资源 （2）进程推进顺序不当。
产生的必要条件：
1、互斥条件。进程对所分配的资源进行排它性控制，即在一段时间内某资源仅为一进程所占有。
2、请求和保持条件。当进程因请求资源而阻塞时，对已获得的资源保持不放。
3、不剥夺条件。进程已获得的资源，在未使用完前，不能被剥夺，只能在使用完时由自己释放。
4、环路等待条件。在发生死锁时，必然存在一个进程-资源的环形链，即进程集合{P1，P2，。。。，PN}中的P1等待一个P2占用的资源，P2正在等待一个P3占用的资源，。。。，Pn正在等待已被P1所占用的资源。
8、有5个待运行的作业为A，B，C，D，E，各自估计运行时间为9，6，3，5，x。试问采用哪种运行次序使得平均响应时间为最短？
响应时间=等待时间+要求服务时间 相等 周转时间=结束时间-到达时间
答：由于短作业优先调度算法会使一组作业的平均周转时间最短，
所以：当0＜x＜3时，应该采用的运行顺序为：E, C, D, B, A
当3≤x≤5时，应该采用的运行顺序为：C，E，D，B，A
当5＜x＜6时，应该采用的运行顺序为：C，D，E，B，A
当6≤x≤9时，应该采用的运行顺序为：C，D，B，E，A
当9＜x时，应该采用的运行顺序为：C，D，B，A，E
9、在操作系统中引入并发可提高系统效率。若有两个程序A和B，A程序执行时所做的工作依次需要用CPU：10s；DEV1：5s；CPU：5s；DEV2：10s；CPU：10s。B程序执行时所做的工作依次需要用DEV1：10s；CPU：10s；DEV2：5s；CPU：5s；DEV2：10s。请计算在顺序环境和并发环境下执行A和B两个程序，CPU的利用率分别是多少？
答：①在顺序环境下执行A和B两个程序，CPU的利用率是50%
顺序，一共用时80s，CPU用时40， 40/80=50%。
②在并发环境下执行A和B两个程序，CPU的利用率是89%（假设A程序先执行）
并发，A：10s(CPU)，5s(DEV1)，5s (Wait)，5s(CPU)，10s(DEV2)，10s(CPU)
B：10s(DEV)，10s(CPU)，5s(DEV2)，5s(CPU)，5s (Wait)，10s(DEV2)
用时45s，CPU40s，40/45=8/9=89%
