山东大学操作系统复习题计算题
操作系统计算题
（2）对于上述算法，各个作业的周转时间是多少？平均周转时间是多少？
（3）对于上述算法，各个作业的带权周转时间是多少？平均带权周转时间是多少
二、有两个程序，A程序按顺序使用CPU 10S，使用设备甲5S，使用CPU 5S，使用设备乙10S，最后使
用CPU 10S。B程序按顺序使用设备甲10S，使用CPU 10S，使用设备乙5S，使用CPU 5S，使用设备乙10S。在顺序环境下先执行A程序再执行B程序，CPU的利用率是多少？提示：CPU利用率=CPU 运行时间/程序运行时间。
三、在单机系统中，系统中各个进程到达就绪队列的时刻、执行时间和优先级如下表所示。假设进程的
调度时间忽略不计。请分别给出采用下面不同的进程调度算法时各个进程的调度次序，画出执行时
（2）时间片轮换调度算法（时间片为1ms）；
（3）抢占式短进程优先调度算法；
（4）抢占式优先级调度算法；
（5）非抢占式优先级调度算法。
（1）用一个执行时间图描述在非抢占优先级算法时，执行这些作业的情况。
（2）用一个执行时间图描述在RR 算法时（不考虑优先级），执行这些作业的情况（时间片为1
单位）。
五、设系统中只有一台打印机，有三个用户的程序在执行过程中都要使用打印机输出计算结果。设每个
用户程序对应一个进程。问：这三个进程间有什么样的制约关系？试用P 、V 操作写出这些进程使用打印机的算法。
六、有三个进程P1，P2和P3并发工作。进程P1需用资源S3和S1；进程P2需用资源S1和S2；进程
P3需用资源S2和S3。回答：
(1)若对资源分配不加限制，会发生什么情况?为什么?
(2)为保证进程正确工作，应采用怎样的资源分配策略?为什么? 七、用信号灯及P 、V 操作来描述右图 1、说明进程的同步关系：
2、设置信号灯，说明含义、初值。
3、写出程序描述（ 用P 、V 操作描述 P1、P2、P3）。 主函数如下：
main()
{int s13=0,s23=0; cobegin p1; p2; p3; coend}
八、假定系统中有4个进程P1、P2、P3、P4和3种类型的资源R1、R2、R3，数量分别为9、3、6，在
t0时刻的资源分配情况如表所示。
表 t0时刻的资源分配表
Max
Allocation
Need
Available
R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 3 2 2 1 0 0 2 2 2 1
1 2
P2 6 1 3 5 1 1 1 0 2
P3 3
1
4
2
1
1
1
3
P4 4 2 2 0 0 2 4 2 0
（2）P2发出请求向量Request2（1，0，1），系统能否将资源分配给它？ （3）在P2申请资源后，若P1发出请求向量Request1（1，0，1），系统能否将资源分配给
资 源
情
况
进
程
它？
（4）在P1申请资源后，若P3发出请求向量Request3（0，0，1），系统能否将资源分配给它？
九、试化简图1中的进程——资源图，并利用死锁定理给出相应的理论。
十、试化简图2中的进程——资源图，并利用死锁定理给出相应的理论。
Process Allocation Need Available
A 0032 0012 1622
B 1000 1750
C 1354 2356
D 0032 0652
E 0114 0656
试问：⑴该状态是否安全，说明理由？
⑵若某进程提出请求Request(1，2，2，2)后，系统能否将资源分配给它，为什么？十二、考虑某一系统，它有四类资源R1，R2，R3，R4，有五个并发进程P0，P1，P2，P3，P4。请按照银行家算法解答下列问题：
（1）各进程的最大资源请求和已分配的资源矩阵如表所示，计算各进程仍需要请求的资源向量组成的矩阵。
（2）系统当前是处于安全状态吗？
（3）
十三、某虚拟存储器的用户编程空间有若干个页面，每页为1KB，存为16MB。假定某时刻已将一页面调入存，该页逻辑地址为4062B,已知页表寄存器中页表始址为2004B，页表长度为8，此时刻存部
76，假设每移动一个柱面需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。
（1）先来先服务（FCFS）（2）最短寻找时间优先调度（SSTF）
（3）电梯调度法（SCAN）（4）单向扫描（循环扫描C－SCAN）
十五、考虑下述页面走向：
1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6当存块数量分别为3时，试问
FIFO、LRU这两种置换算法的缺页次数各是多少？（所有存开始时都是空的，凡第一次用到的页面都产生一次缺页中断）
十六、某移动臂磁盘的柱面由外向里顺序编号，假定当前磁头停在100号柱面且移动臂方向是向里的，现有如下表所示的请求序列在等待访问磁盘：
表
①写出分别采用“最短查找时间优先算法”和“电梯调度算法”时，实际处理上述请求的次序。
②针对本题比较上述两种算法，就移动臂所花的时间（忽略移动臂改向时间）而言，哪种算法更合适？简要说明之。
十七、
作业都可以立即运行。试问：
（1）1S后，存空白区按首次适应和最佳适应算法的方式，将如何？
（2）2S后，其存空白区按上述两种算法如何？
（3）在（2）后，此时有一个作业I要求进入存，它需要存量为12KB，按上述两种算法，将把哪一块空白区分给它？
十八、某计算机系统的存容量为128KB，对存储器采用可变分区的存储管理办法，现有3个作业(J1，J2，J3)
(1)现有一个需要25KB存储空间的作业J4请求装入存，若采用最先适应分配算法来给J4分配空间。
请给出装入J4后的存分配表。
(2)若采用最优适应算法来给J4分配空间，给出装入J4后的存分配表。
(3)在只有J1，J2，J3三个作业的情况下，J2运行结束撤离后，请给出J2撤离后的存分配表。
十九、某程序在逻辑地址100处有一条取数指令LOAD l，500，而500单元存放数据51888。假设程序被分配到存起始地址5000单元时，试用图示意，采用下述各种方式下的该指令及数据地址的物理地址及相应地址的变换过程。
(1)静态重定位。
(2)采用重定位寄存器实现动态重定位。
(3)采用页表映像(映射)方式，假定页面大小为100单元，其负表各页映射到50，51、52，53，54，
55，…，59物理页上。
二十、对于如下的页面访问序列：1，2，3，4，1，2，5，1，2，3，4，5。当存块数量分别为3和4时，试问：使用FIFO、LRU置换算法产生的缺页中断是多少（画出详细过程）？（所有存开始时都是空的，凡第一次用到的页面都产生一次缺页中断）
二十一、给定下面的段表，已知下面的逻辑地址(其中方括号中的第一个元素为段号，第二个元素为段地址)求其对应的物理地址：
(1)[0,430]；(2)[3,400]；。
二十二、16KB。假定某时刻一用户
二十三、某磁盘组有6片盘片，每片有两个记录面，存储区域径为22cm，外径为33cm，道存储密度为40道/cm，层位存储密度为400b/cm，转速为3000r/min（转/分），问共有多少柱面？盘组总存储量为多少？平均等待时间为多少？
二十四、假设有一个磁盘组共有100个柱面，每个柱面上有8个磁道，每个盘面被分成8个扇区。
现有一个含有6400逻辑记录的文件，逻辑记录的大小与扇区一致，该文件以顺序结构的形式被存储到磁盘上。柱面、磁道、扇区的编号从“0”开始，逻辑记录的编号也从“0”开始。文件信息从0柱面、0磁道、0扇区开始存放，试问：
（1）该文件的3680个逻辑记录应该存放在什么位置？
（2）78柱面的6磁道的6扇区中存放了该文件的第几号逻辑记录？
二十五、假设一个可移动磁头的磁盘具有200个磁道，其编号为0～199，当它刚刚结束了125道的存取后，现正在处理143道的服务请求，假设系统当前I/O请求序列以FIFO顺序排列如下：86，147，91，177，94，150，102，175，130。试问对以下几种磁盘I/O请求调度算法而言，满足以上请求序列，磁头将分别如何移动，请列出磁道访问次序，并计算出移动距离？
（1）先来先服务（FCFS）（2）最短寻找时间优先调度（SSTF）
（3）电梯调度法（SCAN）（4）单向扫描（循环扫描C－SCAN）
二十六、有一移动臂磁盘，共100个磁道，每个磁道分8个扇区，磁盘转速为500r/s（转/秒），磁头每移动一个磁道需要10ms，有一个用户请求访问第25磁道第3扇区，并立即被系统响应，假设磁头当时处于15道上，磁头到达第25道时正处于1扇区的开始位置，试计算该用户至少需要等待多长时间？
二十七、假定磁盘转速为6000r/min（转/分），磁盘格式化时每个盘面被分为9个扇区，现有一个文件共有A，B，C，D，E，F，G，H，I九个逻辑记录要存放在同一磁道上供处理程序使用，假设每个记录的大小与扇区的大小相同，处理程序每次从磁盘读出一个记录后要花2.5ms处理时间。
若忽略其他辅助时间，请回答下列问题：
（3）现在假设已经顺序存放好这9个记录，那么读出该文件需要多少时间？
（4）为了使读出文件需要的时间最短，请重新调整各个记录的存放位置，画出各个记录的存放位置，计算该文件的读出时间，并与（1）进行比较说明。
二十八、某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：（1 ）用PV操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值以及信号量各种取值的含义。
（2 ）在下列横线中填入所定义的信号量，并把应执行的PV操作填入横线中，以保证进程能够正确地并发执行。
main()
{ int ；
；
进入售票厅；
购票；
退出；
；
｝
（3 ）若欲购票者最多为n 个人，写出信号量可能的变化围（最大值和最小值）。
二十九、设有三个人，M，Q，R，其中M负责采购原材料并放到房间A中，Q从房间A中取出原材料并加工成产品后，放到房间B中，R从房间B中取出产品并销售（房间A和B都恰好能放一件原材料）。试用P、V操作描述M，Q，R三人实现上述工作的控制流程。
(1)在下列横线中写出该定义的信号量及其初值。
(2)根据所定义的信号量，把应执行的PV操作填入下列横线中，以保证进程能够正确地并发执行。
main（）
{
int ，，，；
cobegin /*下列进程将并发执行*/
M（）；
Q（）；
R（）；
coend
}
A 和进程C 不能同时读文件F ，进程
B 和进程D 也不能同时读文件F ，为了使这四个进程并发执行时能按系统要求使用文件，现用PV 操作进行管理，请回答下面的问题： （1）在下列程序中填入应定义的信号量及初值。
（2）在下列程序中填上适当的P 、V 操作，以保证它们能正确并发工作：
main （ ） {
int ； cobegin /*下列进程将并发执行*/ A （ ）； B （ ）； C （ ）； D （ ）； coend
}
三十一、 桌上有一只盘子，每次只能放一只水果，爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，
一个儿子专等吃盘子中的橘子，一个女儿专等吃盘子中的苹果。用P —V 操作实现他们这间的同步机制。
三十二、 有5批处理作业（A,B,C,D,E ）几乎同时到达，估计运行的时间分别为2，4，6，8，10分
钟，它们的优先级数分别为1
，2，3，4，5（1为最低优先数）。对下面的每种调度算法，分别计算作业的平均周转时间：
1、优先级算法；
2、时间片轮转法（时间片为2分钟）；
3、FCFS （作业到达顺序为C,D,B,E,A ）;
4、短作业优先