印输出。
用算法描述这三个进程的工作情况，并用wait和signal原语实现其同步操作。（共8分） 解：（共8分）
解答：输入进程、计算进程和打印进程之间的同步问题描述如下：
var：mutex1，mutex2，empty1，empty2，full1，full2：=1，1，1，1，0，0； InP:begin repeat
wait(empty1); wait(mutex1);
input a data from keyboard;
Add to buffer1; signal(mutex1); signal(full1); until false end
CalP:begin repeat
wait(full1); wait(mutex1);
Take a data form buffer1; Add to ch1; signal(mutex1); signal(empty1); calculate ch1; wait (empty2); wait(mutex2);
Take a data form ch1; Add to buffer2; signal (mutex2); signal (full2);
until false end
OutP:begin repeat
wait(full2); wait(mutex2);
Take a data from buffer2; Add to printer controler; signal(mutex2); signal(empty2); start printer;
until false end
（评分标准：信号量设置2分，输入进程、计算进程、打印进程各2分）
11．在一个请求分页系统中，有一个长度为 5 页的进程，假如系统为它分配 3 个物理块 ，并且此进程的页面走向为 2，3，2，1，5，2，4，5，3，2，5，2。试用 FIFO 和 LRU 两种算法分别计算出程序访问过程中所发生的缺页次数。（10分） 解：FIFO：
2 3 2 1 5 2 4 5 3 2 5 2 第1页 2 2 2 5 5 5 3 3 3 第2页 3 3 3 2 2 2 5 5 第3页 1 1 1 4 4 4 2
缺页中断次数 = 6
LUR：
2 3 2 1 5 2 4 5 3 2 5 2 第1页 2 2 2 2 5 5 5 3 第2页 3 3 5 2 3 3 5 第3页 1 1 4 4 2 2
缺页中断次数 = 5
12. 进程 A1，A2，?，An 通过 K 个缓冲区向进程 B1，B2，?，Bm 不断地发送消息。发送和接收工作遵循如下规则： 1． 每个发送进程一次发送一个消息，写入缓冲区，缓冲区大小与消息长度
一致； 2． 对每个消息，B1，B2，?，Bm 都需接收一次，读入各自的数据区内； 3． K 个缓冲区都满时，发送进程等待，没有可读的消息时，接收进程等待。 试用 wait 和 signal 原语操作组织正确的发送和接收操作。（10分） 解： BEGIN
Integer Mutex, Avail[n], Full[m]; Integer I;
Mutex:=1;
FOR i:=1 TO m DO BEGIN
Avail[I] := k; Full[I] := 0; END
PROCEDURE Send(K) Integer I;
BEGIN
13．一个进程的大小为5个页面，为它分配了四个物理块。当前每个块的情况如下表所示（都为十进制数，且从0开始计数。）。当虚页4发生缺页时，使用下列的页面置换算法，哪一个物理块将被换出？并解释原因．（10分） 页号 块号 加载时间 访问时间 访问位R 修改位M 2 0 60 161 0 1 1 1 130 160 0 0 0 2 26 162 1 0 3 3 20 163 1 1
１． IFO算法 ２． LRU算法 ３． CLOCK算法
４． 当页面的访问串为：“4，0，0，0，2，4，2，1，0，3，2”的OPT算法 解：1．换出第3号虚页，因为它加载的时间最早； 2．换出第1号虚页，因为它最近最久没被访问；
3．换出第1号虚页，因为它最近既没被访问，又没被修改； 4．换出第3号虚页，因为它离访问点最远。
14. 用整型信号量描述在哲学家进餐问题中，至多允许4个哲学家同时进餐的算法。（10分）
解：public class diningphilosophers {
semaphore [] fork = new semaphore [5] (1); semaphore room = new semaphore (4); int i;
void philosopher (int i) { while (true) think();
wait (room); wait (fork[i]);
wait (fork [(i+1) % 5]); eat();
signal (fork [(i+1) % 5]); signal (fork[i]);
signal (room); } void main() {
parbegin (philosopher (0), philosopher (1), philosopher (2), philosopher (3), philosopher (4)); } }
15．考虑一个有150个存储器单元的系统，如下分配给三个进程： 进程
最大
占有
———————————————————— 1 2 3
使用银行家算法，以确定下面的任何一个请求是否安全：
a．第4个进程到达，最多需要60个存储单元，最初需要25个单元； b．第4个进程到达，最多需要60个存储单元，最初需要35个单元； 如果安全给出安全序列；若不安全给出结果分配简表。（10分） 解：进程 最大 占有 尚需 可用 ———————————————————————— 1 70 45 25 25 2 60 40 20 3 60 15 45 4 60 25 35 安全序列为：1、2、3、4
所以系统是安全的，可以进行分配。 b．
进程 最大 占有 尚需 可用 ———————————————————————— 1 70 45 25 15 2 60 40 20 3 60 15 45 4 60 35 25
当前可用的资源不够任何一个进程运行完毕，所以不安全。
70 60 60
45 40 15
16、（8分）在某采用页式存储管理的系统中，所有作业执行时依次访问的页号
是：1,2，3,4，3,1，5,4,6，2，1,2,5，7,3，2,4 假定开始时先把前4页装入内存。要求完成： （1）先进先出调度算法，作业执行过程中会产生________次缺页中断。依次淘
汰的页号是____________。 （2）最近最少使用算法时，作业执行过程中会产生________次缺页中断。依次
淘汰的页号是____________。 解：1）先进先出调度算法，作业执行过程中会产生_7_次缺页中断。依次淘汰的页号是_1、2、3、4、5、6、2＿。（4分） （2）最近最少使用算法时，作业执行过程中会产生__8__次缺页中断。依次淘汰的页号是2、3、1、5、4、6、1、5。 17、（8分）假定某移动磁盘上，处理了访问56号柱面的请求后，现在正在70号柱面上读信息，目前有下面的请求访问磁盘柱面的序列：
73,68,100,120,60,108,8，50。请写出： （1）用
最短查找时间优先算法，列出响应的次序。 （2）用电梯调度算法，列出响应的次序。 解：（1）用最短查找时间优先算法，响应的次序为68、73、60、50、8、100、108、120。 （2）用电梯调度算法，响应的次序为73、100、108、120、68、60、50、8。
18.设某程序大小为460字，并且它有下面的存储访问序列： 10，11，104，170，73，309，185，245，246，434，458，364 设页面大小是100字，请给出该访问序列的页面走向又设该程序基本可用内存是200字，采用先进先出置换算法(FIFO)，求出其缺页率如果采用最佳置换算法(OPT)，其缺页率又是多少?(注：缺页率=缺页次数/访问页面总数)
解：(共10分)
根据已知条件页面大小是100字，将页面访问序列简化为： 0，0，1，1，0，3，1，2，2，4，4，3(2分)
又因为该程序基本可用内存是200字，可知内存块数为2
采用先进先出置换算法(FIFO)，总共有6次缺页，缺页率为6/12=50%，具体算法如下：(4分) 页面走向
0 0 1 1 0 3 1 2 2 4 4 3 块1 0 0 3 3 4 4块2 1 1 2 2 3 缺页缺 缺 缺 缺 缺 缺
采用最佳置换算法(OPT)，总共有5次缺页，缺页率为5/12=41.6%，具体算法如下：(4分) 页面走向
0 0 1 1 0 3 1 2 2 4 4 3块1 0 0 3 3 3块2 1 1 24缺页缺缺缺缺缺
19、(10分)在一个批处理单道系统中，假设有四道作业，它们的提交时间及运行时间在下表中所列，当第一个作业进入系统后开始调度，假定作业都是仅作计算，采用计算时间短的作业优先调度算法，忽略调度花费时间。 作业进入系统时间 运行时间 开始时间 完成时间 周转时间
1 8：00 2小时
2 8：50 30分钟
3 9：00 6分钟
4 9：30 12分钟
（1） 求出每个作业开始时间、完成时间及周转时间并填入表中。
（2）计算四个作业的平均周转时间应为________. 解：（1）每空0.5分，6分。
作业进入系统时间 运行时间 开始时间 完成时间 周转时间
1 2 3 4 8：00 8：50 9：00 9：30 2小时 8:00 30分钟 10:18 6分钟 10:00 12分钟 10:06 10:00
10:48 10:06 10:18 120分钟 118分钟 66分钟 48分钟
（2）四个作业的平均周转时间应为88分钟.（
20．(4分)一个由3个页面(页号为0、1、2)，每页有2048个字节组成的程序，假定在某时刻调入8个物理块的内存，其页面的页号和物理块号的对照表如下： 逻辑页号 主存块号 0 4 1 7 2 1
请根据页表，计算下列给出的逻辑地址对应的绝对地址。 (1)100 (2)2617 (3)5196 答：（4分）
首先根据逻辑地址查页表，得到主存的块号，再根据公式绝对地址=块号×块长+页内地址进行计算。
（1）100的页号为0（100/2048=2），页内地址为100mod2048=100；查表得主存块号为4，于是绝对地址=4×2048+100=8292；
（2）2617的页号为1（2617/2048=1），页内地址为2617mod2048=569；查表得主存块号为7，于是绝对地址=7×2048+569=14905；
（3）5196的页号为2（5196/2048=2），页内地址为5196mod2048=1100；查表得主存块号为1，于是绝对地址=1×2048+1100=3148； （注：mod为取模运算，即求余数）