四川大学操作系统期中考试2014

一．问答题：

1．什么是多道程序设计技术？有何特点?

多道程序设计技术是指同时将多个程序放入内存，并允许它们交替运行和共享系统中的各类资源。当一道程序因为各种原因（如I/O请求）而暂停执行时，CPU立即转入另一道程序执行。

2．当被阻塞进程所等待的事件出现时，如所需要的数据到达或者等待的I/O操作完成，则会调用原语操作唤醒等待的进程。请问唤醒被阻塞进程的进程与阻塞进程之间存在哪些关系？

与阻塞进程相关的进程（如共享同一资源的进程）。 3．在同一进程的线程中存在哪些重要的关系？ 共享进程的地址空间。

二．应用题

1设有8个程序prog1,prog2,prog3,…,prog8。它们在并发系统中执行时有如图所示的控制关系，试用P、V操作实现这些程序间的同步。

Prog2 Prog1

Prog3 Prog4 Prog5

Prog7 Prog6

Prog8

解答:

本题是典型的进程同步问题,即进程A执行完后才可执行进程B,只需在两进程之间设置信号量。

Var s13,s14,s15,s23,s24,s25,s36,s58,s68,s47,s78:semaphore:=0,0,0,0,0,0,0,0,0,0,0;

begin

parbegin

begin prog1;V(s13);V(s14);V(s15);end; begin prog2;V(s23);V(s24);V(s25);end; begin P(s13);P(s23); prog3;V(s36);end; begin P(s14);P(s24); prog4;V(s47);end; begin P(s15);P(s25); prog5;V(s58);end; begin P(s36); prog6;V(s68);end; begin P(s47); prog7;V(s78);end; begin P(s68);P(s58);P(s78); prog8;end; Parent; End;

2.设系统状态如下： 资源情况 Max Allocation Need 进程 A B C D A B C D A B C D Available A B C D P1 0 0 1 2 0 0 1 2 P2 1 7 5 0 1 0 0 0 P3 2 3 5 6 1 3 5 4 P4 0 6 5 2 0 6 3 2 P5 0 6 5 6 0 0 1 4 用银行家算法回答下列问题: (1) Need的内容是什么? (2) 系统是否处于安全状态?

(3) 如果P2请求(0,4,2,0),能否立即得到满足? 解答:

(1) Need = Max – Allocation

?0000??0750???Need=?1002?

??0020????0642?? 1 5 2 0 (2) 系统中有5个进程,若存在一个序列使得Pi以后还需要的资

源可以通过现有资源加上所有Pj(j

系统现有资源为(1,5,2,0) 资源情况 Allocation Need Available 进程 A B C D A B C D A B C D P1 0 0 1 2 0 0 0 0 1 5 2 0 P4 0 6 3 2 0 0 2 0 1 5 0 0 P3 1 3 5 4 1 0 0 2 0 5 0 0 P2 1 0 0 0 0 7 5 0 P5 0 0 1 4 0 6 4 2 安全序列为P1,P4,P3,P2,P5。 (3) 能立即得到满足,因为可用资源为(1,5,2,0) 。

3. 有5个任务A到E几乎同时到达,它们预计运行时间为10,6,2,4,8分钟,其优先级分别为3,5,2,1,4,这里5为最高优先级。对于下列每一种调度,计算其平均进程周转时间(进程切换开销可以不计) 。 (1) :先来先服务(按A,B,C,D,E) (2) 优先级调度

(3) 时间片为1分钟的调度 解答:先来先服务为19.2分钟 优先级调度为20分钟 时间片为20.4分钟

4. 设有两优先级相同的进程P1，P2如下，信号量S1，S2的初值均为0，已知

Z=2，试问P1，P2执行结束后，X=？，Y=？，Z=？。 进程P1 进程P2 。。。。。 。。。。。 Y：=1； X：=1； Y：=Y+Z； X：=X+1； V（S1）； P（S1）； Z：=Y+1； X：=X+Y； P（S2）； V（S2）； Y：=Z+Y； Z：=X+Z； 。。。。。 。。。。。 答： X=5，Z=9，Y=12

X=5，Z=9，Y=7 X=5，Z=4，Y=7

5。考虑一个并发程序，具有二个进程P，Q

A：试列出这二个进程并发执行时所有可能的交叉

B：并给出二进程按A，D，B，E，C顺序执行时的同步算法。 P进程 Q进程 A D B E C 解:

P开始：

A D E B C，A B D E C，A B C D E A D B E C，A D B C E，A B D C E Q开始：

D E A B C，D A E B C，D A B E C D A B C E

6。四人到公园门口集合,人齐后一起进入,试用Wait,Signal操作写出相应的同步算法.

等待信息量：S：=0 互斥信息量Mutex：=1 计数变量：Count：=0 Wait（Mutex） Count：=Count+1

IF Count=4 THEN {Signal(S);Signal(S)

Signal(S);Signal(Mutex)} ELSE {Signal(Mutex),Wait(S)} 进入公园（Count的还原？）

7. （1）主存容量最大可为256K，分128个物理块？每块2K (2) 0, 物理地址是 1010111011100B