…………………（4分）
2. （6分）当进程X和进程Y共享某个资源r，进程并
发执行时的程序如下： 请回答：
(1) 两个进程并发执行时，能否保证互斥地使用资源？为什么？
(2) 如果要使两个进程交替使用资源，若仍使用P、V操作来进行管理，写出应定义的信号量及其初值。
(3) 修改上述程序，使两个进程能交替使用资源r。
答：（6分）
(1) 能保证互斥使用资源。因为在两个进程中，“使用资源r”都是作为临界区，由P(S)和V(S)操作保证了互斥执行，S的初值定义为1，符合要求。
(2) 要使两个进程交替使用资源，仅仅保证互斥使用是不够的，必须要两个进程互相等待互相通知。为此，必须定义新的信号量。定义两个私有信号量S1和S2。假定进程X先使用资源，那么进程X的私有信号量S1的初值定义为1，进程Y的私有信号量S2的初值定义为0。轮流使用可以保证互斥，因此信号量S可以不要。
(3) 两个进程可以改写为
3. （8分）有一只铁笼子，每次只能放一只动物，猎手向笼子中放入老虎，农民向笼
中放入猪，动物园等待取笼中的老虎，饭店取笼中的猪，试用PV操作写出同步执行的程序。 解：
信号量设置 semaphore empty，pig，tiger;
empty=1: 笼子的空位，笼子中只能放一个动物； pig=0: 笼子中猪的个数； tiger=0: 笼子中老虎的个数；
第 26 页 共 35 页
4. （8分）
有三个进程PA、PB和PC合作解决文件打印问题：PA将文件记录从磁盘读入主存的缓冲区1，每执行一次读一个记录；PB将缓冲区1的内容复制到缓冲区2，每执行一次复制一个记录；PC将缓冲区2的内容打印出来，每执行一次打印一个记录。缓冲区的大小等于一个记录的大小。请用P、V操作来保证文件的正确打印。 PA PB PC 缓冲区1 缓冲区2
（提示：这是一个Producer—Consumer问题）
答案：（8分）
（说明：PA、PB、PC每答对一个给2分；实线仅做描述用答案中可不画出；若仅给出
上述答案，未事先对信号量empty1、2和full1、2做说明，扣2分）
5. （8分）有一个仓库，可以存放A和B两种产品，但要求： （1）每次只能存入一种产品（A或B）； （2）-N < A产品数量 - B产品数量 < M.
其中，N和M是正整数。试用P、V操作描述产品A和B的入库过程。 答案：（8分）
信号量设置 semaphore mutex, sa, sb; …………………（2分） mutex=1: 对仓库互斥操作
sa= M-1: 当前还允许A入库的数量 sb= N -1: 当前还允许B入库的数量
第 27 页 共 35 页
main() { cobegin provider_A(); provider_B(); coend }
provider_A() …………………（3分） { while(true) { p(sa); p(mutex); 放入零件A; v(mutex) v(sb);
} }
provider_B() …………………（3分） { while(true) { p(sb); p(mutex); 放入零件B; v(mutex) v(sa);
} }
6. （6分）已知某程序访问以下页面：0、1、4、2、0、2、6、5、1、2、3、2、1、2、
6、2、1、3、6、2，如果程序有3个页框可用且使用下列替换算法，求出现缺页的次数。（1）FIFO替换算法（2）LRU替换算法 解：（8分） （1）FIFO算法总是淘汰最先进入内存页面，即选择在内存中驻留时间最长的页予以淘汰。算法如图所示：
0 1 4 2 0 2 6 5 1 2 3 2 1 2 6 2 1 3 6 2 0 0 0 2 2 1 1 1 0 4 4 4 2 5 5 5 3 0 0 1 1 1 6 6 6 2 2 3 6 2 3 6 1 2 6 1 缺页率=13/20=65% （2）LRU算法是最近最久未使用的页面予以淘汰。算法如图所示：
第 28 页 共 35 页
7. （8分）在一个采用页式虚拟存储管理的系统中，有一用户作业，它依次要访问的
字地址序列是：115，228，120，88，446，102，321，432，260，167，若该作业的第0页已经装入主存，现分配给该作业的主存共300字，页的大小为100字，请回答下列问题：
（1）按FIFO调度算法将产生几次缺页中断，依次淘汰的页号序列是什么，缺页中断率为多少？
（2）按LRU调度算法将产生几次缺页中断，依次淘汰的页号序列是什么 ，缺页中断率为多少？
答：（8分）
此题的关键在于如何通过字地址序列确定页号和常驻集大小！！！（给出2者的分析给2分）
（1）按FIFO调度算法将产生5次缺页中断；依次淘汰的页号为：0，1，2； 缺页中断率为：5/10=50%
（2）按LRU调度算法将产生6次缺页中断；依次淘汰的页号为：2，0，1，3； 缺页中断率为：6/10=60%
8. （8分）在一个请求分页存储管理系统中，一个作业的页面走向为4，3，2，1，4，
3，5，4，3，2，1，5。当分配给该作业的物理块数为3、4时，是计算下述页面值换算法时的缺页率（假设开始执行时主存中没有页面）。
1） 先进先出置换算法
2） 最近最久未使用淘汰算法 答：（8分）
FIFO 物理块数为3 缺页率 9/12 0 1 2
4 4 P
3 4 3 P
2 4 3 2 P
1 1 3 2 P
4 1 4 2 P
3 1 4 3 P
5 5 4 3 P
4
3
2 5 2 3 P
1 5 2 1 P
5
第 29 页 共 35 页
FIFO 物理块数为4 缺页率 10/12 0 1 2 3
4 4 P
3 4 3 P
2 4 3 2 P
1 4 3 2 1 P
4
3
5 5 3 2 1 P
4 5 4 2 1 P
3 5 4 3 1 P
2 5 4 3 2 P
1 1 4 3 2 P
5 1 5 3 2 P
LRU 物理块数为3 缺页率 10/12 0 1 2
4 4 P
3 4 3 P
2 4 3 2 P
1 1 3 2 P
4 1 4 2 P
3 1 4 3 P
5 5 4 3 P
4
3
2 2 4 3 P
1 2 1 3 P
5 2 1 5 P
LRU 物理块数为4 缺页率 8/12 0 1 2 3
4 4 P
3 4 3 P
2 4 3 2 P
1 4 3 2 1 P
4
3
5 4 3 5 1 P
4
3
2 4 3 5 2 P
1 4 3 1 2 P
5 5 3 1 2 P
9. （8分）一个虚拟存储器中，主存容量为400字节，划分为4块，采用LRU算法。
虚地址流为22，214，146，618，270，490，492，168，96，128。（注明：先从内存低地址部分装入），问： 1） 出虚页地址流；
2） 画出实存中的调度过程示意图； 3） 写出实地址流； 4） 计算命中率； 解：（8分，每小问2分）
1） 0，2，1，6，2，4，4，1，0，1（给出分析，直接给出答案将扣分） 2）
0 0 2 0 2 1 0 2 1 6 0 2 1 6 2 4 4 2 1 6 4 1 0 4 2 1 0 1 第 30 页 共 35 页