(2)根据所定义的信号量，加上wait和signal原语，写出购票者进程的算法，以保证进程能够正确地并发执行。 (3)若欲购票者最多为n个人，写出信号量可能的变化范围(最大值和最小值)。 解：(1)定义一信号量S，初始值为20。 意义：

S>0 S的值表示可继续进入售 票厅的人数 S=0 表示售票厅中已有20名顾 客(购票者) S<0 |S|的值为等待进入售票 厅的人数 (2) int S=20;

COBEGIN PROCESS PI(I=1，2，……) begin 进入售票厅； wait(S)； 购票； signal(S); 1. 退出；

end； COEND (3)S的最大值为20 S的最小值为20－n

设 input进程不断向缓冲区Q写入信息，output进程不断地将刚由input进程写入的信息读出。试问： （1） 这两个进程有何相互制约关系？

（2） 试用P、V操作写出这两个进程完成这项任务的代码段和信号量的含义及初值。 答：（1）这两个进程的相互制约关系为同步关系；

（2）设两个信号量S1和S2。其中S1表示Q是否为空，初值为1，表示Q是空的；S2表示Q中是否有信息，初值为0，表示Q中无信息。 两进程的代码段如下： input进程 { …… while 信息未处理完毕 { 加工一个信息； P（S1）； 将信息放入Q中； V（S2）； …… } output进程 { …… while 信息未处理完毕 { P（S2）； 从Q中读出一个信息； V（S1）； …… } 2. 两个并发执行的进程A和B的程序如下： 进程A while(true) { N=N+5; } 进程B while(true) { 打印N的值； N=0； } 其中N为整数，初值为4。若进程A先执行了三个循环后，进程A和进程B又并发执行了一个循环，写出可能出现的打印值。正确的打印值应该是多少？请用P、V操作进行管理，使进程A和B并发执行时不会出现与时间有关的错误。

答： 因为N初值为4，若进程A先执行了三个循环，此时N的值为19。当进程A和进程B并发执行时可能会有如下两种执行次序，即进程A先执行一次循环，然后再进程B执行一次循环，此时打印的是正确值24，执行后N中的值为0。但若进程B先执行一次循环，然后再进程A执行一次循环，则打印的值是19，执行后N中的值是5。这是错误的，即发生了与时间有关的错误。用P、V操作进行管理，使进程A和B并发时不会出现与时间有关的错误的程序如下：（S为互斥信号量，初值为1）， 进程A while(true) { P(S); N=N+5; V(S); } 3. 假定在单道批处理环境下有5个作业，各作业进入系统的时间和估计运行时间如下表所示： 作业 1 2 3 4 5 作业 1 2 3 4 5 进入系统时间 8:00 8:20 8:30 9:00 9:10 进入系统时间 8:00 8:20 8:30 9:00 9:10 估计运行时间/分钟 40 30 12 18 5 估计运行时间/分钟 开始时间 结束时间 40 30 12 18 5 周转时间/分钟 进程B while(true) { P(S); 打印N的值； N=0； V(S); } (1) 如果应用先来先服务的作业调度算法，试将下面表格填写完整。 作业平均周转时间T= （2）如果应用最短作业优先的作业调度算法，试将下面表格填写完整。 作业 1 2 3 进入系统时间 8:00 8:20 8:30 估计运行时间/分钟 开始时间 结束时间 40 30 12 周转时间/分钟 4 5 9:00 9:10 18 5 作业平均周转时间T= 答：（1）应用先来先服务的作业调度算法，表格填写如下： 作业 1 2 3 4 5 进入系统时间 8:00 8:20 8:30 9:00 9:10 估计运行时间/分钟 开始时间 结束时间 40 8:00 8:40 30 12 18 5 8:40 9:10 9:22 9:40 9:10 9:22 9:40 9:45 周转时间/分钟 40 50 52 40 35 作业平均周转时间T=43.4 217

（2）应用最短作业优先的作业调度算法，表格填写如下： 作业 1 2 3 4 5 进入系统时间 8:00 8:20 8:30 9:00 9:10 估计运行时间/分钟 开始时间 结束时间 40 8:00 8:40 30 12 18 5 8:52 8:40 9:27 9:22 9:22 8:52 9:45 9:27 周转时间/分钟 40 62 22 45 17 作业平均周转时间T=37.2 186

4. 若在一分页存储管理系统中,某作业的页表如下所示.已知页面大小为1024字节,试将逻

辑地址1011,2148,4000,5012转化为相应的物理地址. 页号 0 1 2 3 物理块号 2 3 1 6 答：本题中,为了描述方便,设页号为P,页内位移为D,则:

对于逻辑地址1011，P=INT(1011/1024)=0，D=1011 mod 1024=1011，查页表第0页在第2块,所以物理地址为3059.

对于逻辑地址2148，P=INT(2148/1024)=2，D=2148 mod 1024=100，查页表第2页在第1块,所以物理地址为1124.

对于逻辑地址4000，P=INT(4000/1024)=3，D=4000 mod 1024=928，查页表第3页在第6块,所以物理地址为7072.

对于逻辑地址5012，P=INT(5012/1024)=4，D=5012 mod 1024=916，因页号超过页表长度,该逻辑地址非法.

5. 根据如下段表： 段号 0 1 2 3 基地址 300 7500 3000 2000 长度 200 540 1010 100 合法（0）/非法（1） （1） 求出逻辑地址为[0，100]的物理地址并将其的合法性填入段上表适当位置； （2） 求出逻辑地址为[3，100]的物理地址并将其的合法性填入上表适当位置； 答：（1）物理地址为：300+100=400，合法性如下表所示。 （2）物理地址为：2000+100=2100，合法性如下表所示。 段号 0 1 2 3 基地址 300 7500 3000 2000 长度 200 540 1010 100 合法（0）/非法（1） 0 1 6. 在一个采用页式虚拟存储管理的系统中,有一用户作业,它依次要访问的字地址序列

是:115,228,120,88,446,102,321,432,260,167,若该作业的第0页已经装入主存,现分配给该作业的主存共300字,页的大小为100字,请回答下列问题:

(1)按FIFO调度算法将产生 次缺页中断,依次淘汰的页号为 ,缺页中断率为 . (2)按LRU调度算法将产生 次缺页中断,依次淘汰的页号为 ,缺页中断率为 . 答：(1)按FIFO调度算法将产生5次缺页中断 ;依次淘汰的页号为:0,1,2; 缺页中断率为:5/10=50%

(2)按LRU调度算法将产生6次缺页中断;依次淘汰的页号为:2,0,1,3; 缺页中断率为:6/10=60%

7. 某系统的进程状态图如下

40

(1)说明一个进程发生变迁1、3、4的原因是什么？

(2)下述因果变迁是否会发生?如果有可能的话,在什么情况下发生？ A)1-> 3 B)2->4 C) 4->1 D) 5->1 E) 3->2

运行 2 因I/O等待 低优先就绪 3 1 5 4 高优先就绪

解：（1）发生变迁1的原因是：当CPU空闲且高优先就绪队列中有进程，则从高优先就绪队列调一个进程到CPU上去执行。

发生变迁3的原因是：当一个在CPU上运行的进程用完它的时间片时，立即退出CPU而进入低优先就绪队列。 发生变迁4的原因是：一个正在CPU上运行的进程需要输入或者输出数据时，退出CPU 而进入等待队列。

（2）A）和B）的因果变迁不可能发生。C）、D）和E）有可能发生，其原因是：

C）4->1：一个正在CPU上运行的进程需要输入或者输出数据时，退出CPU 而进入等待队列，CPU空闲，这时若高优先就绪队列中有进程，则发生调度1。

D) 5->1：当高优先就绪队列和CPU都处于空闲状态时，一个处于等待状态的进程被唤醒进入高优先就绪队列后立即被调度到CPU上去执行。 E) 3->2：当一个在CPU上运行的进程用完它的时间片退出CPU而进入低优先就绪队列时，若高优先就绪队列为空，则立即发生2（即调度低优先就绪队列中的一个进程到CPU上去执行）

41