表补充完整。
题36表 FCFS与SJF的比较
作业号 J1 J2 J3 提交时刻 (小时) 10:00 10:30 11:00 平均周转时间 带权平均周转时间 25. 设磁盘有200个磁道，磁道请求序列按到达的时间顺序为；
27、129、110、186、147、41、10、64、120
假设磁头的起始位置是100且正向129磁道移动，填写下面的表格:
FIFO调度算法 下一个被 访问的磁道 平均寻道数
26. 系统中的进程集合如题37表-1所示，当采用SPN(短进程优先)调度算法时，填写题37
表-2。
题37表1 系统中的进程集合
进程名 A B C D E
进程名 A 题37表2 进程的运行状况 到达时间 处理时间 开始时间 结束时间 周转时间 第26页 共35页
执行时间 (小时) 2 1 0.5 FCFS 开始时间 结束时间 开始时间 SJF 结束时间 SCAN调度算法 下一个被 访问的磁道 平均寻道数 跨越的磁道数 跨越的磁道数 到达时间 0 1 3 9 12 处理时间 3 5 2 5 5 带权周转时间 B C D E 平均周转时间 带权平均周转时间
27. 设有一组作业，它们的到达时间和所需CPU时间如下所示。
作业号 1 2 3 4 到达时间 9:00 9:40 9:50 10:10 所需CPU时间 70分钟 30分钟 10分钟 5分钟 若分别采用FCFS和SJF调度算法，它们的调度顺序、作业周转时间以及平均周转时间各是什么？
28. 设某系统在时刻t可供某类资源R的数量为1，用银行家算法判断题35表所示的系统
状态是否安全，说明你的判断依据。
题 35 表 某系统在时刻t的状态 进程 P1 P2 P3 已占R类资源的数量 4 3 6 最大需求 8 9 8 29. 设某分页存储系统的页面大小为4KB，逻辑地址为16位，在时刻t，内存中的页表如
题36表所示，画图表示将逻辑地址1F6C转换为物理地址的过程。
题36表
页号 0 1 2
30. 设磁头当前位于30柱面，正在向0磁道运动，进程对磁盘柱面的请求序列为：
（10,22,20,2,40,6,38）。当分别采用SSTF、寻道算法时，填写题37表。
题37表
SSTF-当前磁道30 磁道访问序列 移动的磁道数 C-SCAN-当前磁道30 磁道访问序列 第27页 共35页
物理块号 3 5 8 移动的磁道数 移动总磁道数 移动总磁道数 31. 若进程P的页面走向为：4,3,2,1,4,3,5,4,3,2,1,5；系统为进程P分配4个物理内存块，当
缺页时，采用局部置换策略，试分别填写题38表-1和题38表-2（若产生缺页，则在相应的缺页标记列填写“√”）。
题38表-1采用LRU算法的页面置换表 页面走向 内存中的页面 缺页标记 页面走向 内存中的页面 缺页标记
五、综合题
1. 在银行家算法中，若出现下述资源分配情况：
进程 P0 P1 P2 P3 P4 Allocation 0 0 3 2 1 0 0 0 1 3 5 4 0 3 3 2 0 0 1 4 Need 0 0 1 2 1 7 5 0 2 3 5 6 0 6 5 2 0 6 5 6 Available 1 6 2 2 4 4 3 3 2 2 1 1 4 4 3 3 5 5 4 4 3 3 2 2 1 1 5 5 题38表-2采用FIFO算法的页面置换表
试问：⑴该状态是否安全？
⑵如果进程P2提出请求Request（1，2，2，2）后，系统能否将资源分配给它？
2. 在一个请求分页系统中，假定系统分配给一个作业的物理块数为３，并且此作业的页面
走向为２、３、２、１、５、２、４、５、３、２、５、２。试用FIFO和LRU两种算法分别计算出程序访问过程中所发生的缺页次数。
3. 有一阅览室，读者进入时必须先在一张登记表上进行登记，该表为每一座位设置一个表
目，包括座号和读者姓名。读者离开时要注销掉登记信息，阅览室中共有100个座位，试写出利用信号量机制实现管理阅览室的同步算法
第28页 共35页
4. 判断下面的同步算法是否正确？若有错，请指出错误原因并改正。
题38图-1 题38图-2
注：信号量S的初值为0 注：信号量S1、S2的初值均为0
1）设A、B为两并发进程，两进程共用缓冲区Q，A向Q写入信息，B从缓冲区Q读出信息,算法如题38图-1；
2）设A、B为两并发进程，共享一临界资源，算法如题38图-2。
5. 设系统的当前状态如下：
Available:
process P1 P2 P3 P4 P5
1) 计算各个进程的Still needs ，填入表格空白处； 2) 系统是否处于安全状态，为什么？ 3) 系统是否死锁？为什么？
4) 如果系统会死锁，那些进程会死锁？
6. 在一个采用页式虚拟存储管理的系统中，有一用户作业，它依次要访问的字地址序列是：
115，228，120，88，446，102，321，432，260，167，若该作业的第0页已经装入主存，现分配给该作业的主存共300字，页的大小为100字，请分析当分别采用FIFO和LRU页面置换算法时，将产生多少次缺页中断，依次淘汰的页号是哪些？缺页中断率
Current allocation R1 0 2 0 2 0 R2 0 0 0 3 3 R3 0 0 3 5 3 R4 2 0 4 4 2 maximum demand R1 0 2 6 4 0 R2 0 7 6 3 6 R3 1 5 5 5 5 R4 2 0 6 6 2 R1 Still needs R2 R3 R4
第29页 共35页
为多少？。
7. 用PV操作解决读者-写者问题的正确程序如下： semaphore S=1, Sr=1; int rc=0; reader (i){ P(Sr)
rc=rc+1;
if(rc==1) P(S); V(Sr); read file; P(Sr); rc=rc-1
if(rc==0) V(S); V(Sr); }
writer(j) P(S);
Write file; V(S) }
请回答：
（1）信号量 Sr的作用；
（2）程序中什么语句用于读写互斥，写写互斥； （3）若规定仅允许5个进程同时读怎样修改程序？
8. 系统中有甲、乙两个用户，甲用户有文件A、B，乙用户有文件A、C、D；甲用户的文
件A与乙用户的文件A不是同一个文件，甲用户的文件B与乙用户的文件C是同一个文件。请绘图设计一个目录组织方案，并做必要的说明。
9. 设系统中有n+1个进程，其中有n个发送进程P1、P2、…、Pn，一个接受进程Q。发
送进程Pi不断将消息发送到缓冲区buf中，接受进程Q不断地从缓冲区中取消息，而且必须取走发送进程发来的每一条消息。假设刚开始时缓冲区buf为空，试用信号量和类C语言设计一个算法，解决上述进程间的同步问题。
10. 在虚拟分页存储管理系统中，假定系统为某进程分配了四个主存块并将开始4页先装入
主存，页的引用顺序为（7,1,2,0,3,0,4,2,3,0,3,2,7,0,1），当分别FIFO、LRU调度算法时将产生多少次缺页中断？依次淘汰的页分是什么？
11. 有3个并发进程R，M，P，它们共享一个缓冲器B。进程R负责从输入设备读信息，
每读出一个记录后把它存放在缓冲器B中；进程M在缓冲器B中加工进程R存入的记录；进程P把加工后的记录打印输出。缓冲器B中每次只能存放一个记录，当记录被加工输出后，缓冲器B中又可存放一个新记录。请用PV操作编写使进程R，M，P能
第30页 共35页