聊城大学计算机12第2学期操作系统A卷.docx
《聊城大学计算机12第2学期操作系统A卷.docx》由会员分享,可在线阅读,更多相关《聊城大学计算机12第2学期操作系统A卷.docx(15页珍藏版)》请在冰点文库上搜索。
聊城大学计算机12第2学期操作系统A卷
聊城大学计算机学院2012—2013学年第2学期2011级本科期末考试《操作系统》试题(闭卷A卷)
题号
一
二
三
四
五
总分
复核人
得分
一、单项选择题(共15题,每题2分,共30分)将答案填写在下面表格中!
得分
阅卷人
题号
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
答案
1.批处理系统的主要缺点是()。
A、CPU的利用率不高B、失去了交互性
C、不具备并行性D、以上都不是
2.分段管理提供()维的地址结构。
A、1B、2C、3D、4
3.虚拟内存的容量只受()的限制。
A、物理内存的大小B、磁盘空间的大小
C、数据存放的实际地址D、计算机地址位数
4.若当前进程因时间片用完而让出处理机时,该进程应转变为()状态。
A、就绪B、等待C、运行D、完成
5.产生死锁的四个必要条件是互斥条件和(),不剥夺条件和环路等待。
A、请求和阻塞条件B、请求和释放条件
C、请求和保持条件D、释放和阻塞条件
6.在()中,要求空闲分区按空闲区地址递增顺序链接成空闲分区链。
A、首次适应算法B、最坏适应算法
C、最佳适应算法D、循环首次适应算法
7.在请求调页中可采用多种置换算法,其中LRU是()置换算法。
A、最佳B、最近最久未用C、最近未用D、最少使用
8.为了对紧急进程或重要进程进行调度,调度算法应采用()。
A、先进先出调度算法B、优先级法C、最短作业优先调度D、时间片轮转法
9.页式存储管理的快表一般存放在()。
A、内存B、外存C、硬盘D、CACHE
10.一作业8:
00到达系统,估计运行时间为1小时,若10:
00开始执行该作业,其响应比是()。
A、1.5B、1C、2D、3
11.在页式存储管理中,若地址用m个2进制位表示,页内地址部分占用n个2进制位,则最大允许程序有()个页面。
A、2mB、2nC、2m-nD、2n-1
12.若干个等待访问磁盘者依次要访问的磁道为20,44,40,4,80,12,76,当前磁头位于40号柱面,若用最短寻道时间优先磁盘调度算法,则访问顺序为()。
A、20,44,40,4,80,12,76B、40,44,20,12,4,76,80
C、40,44,76,80,20,1,2,4D、40,44,76,80,4,12,20
13.某计算机系统中有8台打印机,有K个进程竞争使用,每个进程最多需要3台。
该系统可能会发生死锁的K的最小值是()。
A、2B、3C、4D、5
14.程序员利用系统调用打开I/O设备时,通常使用的设备标识是()。
A、逻辑设备名B、物理设备名
C、主设备号D、从设备号
15.对临界资源应采取()访问方式来实现共享.
A、互斥B、同时C、抢夺D、并发
二、填空题(共6题,每空1分,共10分)
得分
阅卷人
1.设有8页的逻辑空间,每页有1024字节,它们被映射32块的物理存储区中,那么,逻辑地址的有效位()位,物理地址至少是()位。
2.按资源分配特点,设备类型可分为以下三类:
(),(),()。
3.通常,进程实体是由()、程序、()这三部分组成。
4.()是操作系统中采用空间换时间的技术。
5.刚被调出的页面又立即要用而装入,而装入后不久又被调出,如此反复,使调度非常频繁,这种现象称为()。
6.在请求式分页存储管理系统中,不能在计算机中实现的页面淘汰算法是()。
三、简答题(共4题,每题5分,共20分)
得分
阅卷人
1.(5分)某车站售票厅,任何时刻最多可容纳20名购票者进入,当售票厅中少于20名购票者时,则厅外的购票者可立即进入,否则需在外面等待。
若把一个购票者看作一个进程,请回答下列问题:
(1)用PV操作管理这些并发进程时,应怎样定义信号量,写出信号量的初值以及信号量各种取值的含义。
(2)若欲购票者最多为n个人,写出信号量可能的变化范围(最大值和最小值)。
2.(5分)三个进程P1、P2和P3并发工作。
进程P1需要资源S3和S1;进程P2需用资源S1和S2;进程P3需用资源S2和S3,请回答:
(1)若对资源分配不加限制,会发生什么情况?
为什么?
(2)为保证进程正确工作,应采用何种资源分配策略?
为什么?
3.(5分)简要回答影响缺页率的因素有哪些?
4.(5分)以独占设备为例简述设备分配的过程。
四、计算题(共5题,每题6分,共30分)
得分
阅卷人
1.(6分)设某计算机的逻辑地址空间和物理地址空间均为64KB,按字节编址。
若某进程最多需要6页(Page)存储空间,页的大小为1KB。
操作系统采用固定分配局部置换策略为此进程分配4个页框。
页号
块号
装入时刻
访问位
0
7
130
1
1
4
230
1
2
2
200
1
3
9
160
1
当该进程执行到时刻260时,要访问逻辑地址为17CAH的数据,请问答下列问题:
(1)该逻辑地址对应的页号是多少?
(2)若采用先进先出置换算法,该逻辑地址对应的物理地址是多少?
要求给出计算过程。
(3)若采用时钟置换算法,该逻辑地址对应的物理地址是多少?
(设搜索下一页的指针沿顺时针方向移动,且当前指向2号页框)。
2.(6分)有一个具有两道作业的批处理系统,作业调度采用短作业优先调度算法,进程调度采用以优先数为基础的抢占式调度算法,如表所示的作业序列(表中所列作业优先数即为进程优先数,数值越小优先级越高)
作业名
到达时间
估计运行时间
优先数
A
10:
00
40分
5
B
10:
20
30分
3
C
10:
30
50分
4
D
10:
50
20分
6
(1)列出所有作业进入内存时间及结束时间。
(2)计算平均周转时间。
3.(6分)假设有A,B,C,D4个记录存放在磁盘的某个磁道上,该磁道划分成4块,每块存放1个记录,其布局如下表所示。
块号
1
2
3
4
记录号
A
B
C
D
现在要顺序处理这些记录。
假定磁盘转速为20ms/圈,处理程序每次从磁盘读出一个记录后要花5ms进行处理,若磁头现在正处于首个逻辑记录的始点位置。
请问:
(1)处理程序处理完这4个记录所花费的时间是多少?
(2)按最优化分布重新安排这4个逻辑记录,写出记录的安排,并计算出所需要处理的时间。
4.(6分)在一个采用页式虚拟存储管理的系统中,有一用户作业,它依次要访问的字地址序列是:
115,228,120,88,446,102,321,432,260,167,若该作业的第0页已经装入主存,现分配给该作业的主存共300字,页的大小为100字,请回答下列问题:
(1)按FIFO调度算法将产生多少次缺页中断,依次淘汰的页号是什么,计算缺页中断率。
(2)按LRU调度算法将产生多少次缺页中断,依次淘汰的页号是什么,计算缺页中断率。
5.(6分)某系统有A、B、C、D四类资源可供五个进程P1、P2、P3、P4、P5共享。
系统对这四类资源的拥有量为:
A类3个、B类14个、C类12个、D类12个。
进程对资源的需求和分配情况如下,按银行家算法回答下列问题:
进程
已占有资源
最大需求数
ABCD
ABCD
P1
0012
0012
P2
1000
1750
P3
1354
2356
P4
0632
0652
P5
0014
0656
(1)现在系统中的各类资源还剩余多少?
(2)现在系统是否处于安全状态?
为什么?
(3)如果现在进程P2提出需要A类资源0个、B类资源4个、C类资源2个和D类资源0个,系统能否去满足它的请求?
请说明原因。
五、程序与算法(共10分)
得分
阅卷人
一条小河上有一座独木桥,规定每次只允许一个人过桥。
现河东和河西都有相等的人数在等待过桥,为了使两边的人都有同样的过桥机会,规定某边的一个人过桥后要让另一边的一个人过桥,即两边的人交替过桥。
如果把每个过桥者看做一个进程,为保证安全,用PV操作来管理。
(1)写出应定义的信号量及其初值。
(2)假定开始时让河东的一个人先过桥,然后交替过桥。
请用适当的PV操作,达到上述管理要求。
聊城大学计算机学院2012—2013学年第2学期2011级本科期末考试《操作系统》试题A卷
参考答案及评分标准
一、单项选择题(共15题,每题2分,共30分)将答案填写在下面表格中!
题号
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
答案
B
B
D
A
C
A
B
B
D
D
C
B
C
A
A
二、填空题(共6题,每空1分,共10分)
1.1315
2.独占设备共享设备虚拟设备
3.PCB(或进程控制块)数据集合
4.Spooling技术
5.抖动
6.最佳算法
三、简答题(共4题,每题5分,共20分)
注:
本题答案均为参考答案,与本答案有出入,可酌情给分。
1.(5分)某车站售票厅,任何时刻最多可容纳20名购票者进入,当售票厅中少于20名购票者时,则厅外的购票者可立即进入,否则需在外面等待。
若把一个购票者看作一个进程,请回答下列问题:
(1)用PV操作管理这些并发进程时,应怎样定义信号量,写出信号量的初值以及信号量各种取值的含义。
(2)若欲购票者最多为n个人,写出信号量可能的变化范围(最大值和最小值)。
答:
(1)定义一信号量S,初始值为20。
S>0S的值表示可继续进入售票厅的人数
S=0 表示售票厅中已有20名顾客(购票者)
S<0|S|的值为等待进入售票厅的人数 (3分)
(2)S的最大值为20
S的最小值为20-N(2分)
2.(5分)三个进程P1、P2和P3并发工作。
进程P1需要资源S3和S1;进程P2需用资源S1和S2;进程P3需用资源S2和S3,请回答:
(1)若对资源分配不加限制,会发生什么情况?
为什么?
(2)为保证进程正确工作,应采用何种资源分配策略?
为什么?
答:
(1)若对进程间的资源分配不加限制,可能会发生死锁。
若进程P1、P2和P3分别获得资源S3、S1和S2,后再继续申请资源时会导致进程间的“循环等待”,并且这种状态将永远持续下去。
(2分)
(2)为保证系统处于安全状态,应采用下面列举3种资源分配策略:
1)采用静态资源分配:
由于执行前已获得所需全部资源,故不会出现占有资源又等待资源的现象,从而避免资源的循环等待。
2)采用资源按序分配,避免出现循环等待资源的现象。
3)采用银行家算法进行分配资源前的检测。
(3分)
3.(5分)简要回答影响缺页中断率的因素有哪些?
答:
4个因素,分别是:
(1)分配给程序的主存块数;
(2)页面的大小;(3)程序编制方法;(4)页面调度算法。
(5分)
4.(5分)以独占设备为例简述设备分配的过程。
答:
(1)设备的分配。
根据物理设备名,查找SDT;找出该设备的DCT,得该设备的状态:
忙则将进程的PCB排入设备队列中等待;闲则分配设备给进程。
(1分)
(2)控制器的分配。
根据设备的DCT找到与之相连的控制器的COCT,从中得到控制器的状态:
忙则将进程的PCB排入控制器的等待队列中;闲则分配控制器给进程。
(2分)
(3)通道的分配。
如果系统有通道,则根据控制器的COCT找到与之相连的通道的CHCT,从中得到通道的状态:
忙则将进程的PCB挂入通道的等待队列中;否则分配通道给进程。
(2分)
只有在三者都分配成功时,设备分配才算成功。
四、计算题(共5题,每题6分,共30分)
注:
本题答案均为参考答案,与本答案有出入,可酌情给分。
1.(6分)设某计算机的逻辑地址空间和物理地址空间均为64KB,按字节编址。
若某进程最多需要6页(Page)存储空间,页的大小为1KB。
操作系统采用固定分配局部置换策略为此进程分配4个页框。
页号
块号
装入时刻
访问位
0
7
130
1
1
4
230
1
2
2
200
1
3
9
160
1
当该进程执行到时刻260时,要访问逻辑地址为17CAH的数据,请问答下列问题:
(1)该逻辑地址对应的页号是多少?
(2)若采用先进先出置换算法,该逻辑地址对应的物理地址是多少?
要求给出计算过程。
(3)若采用时钟置换算法,该逻辑地址对应的物理地址是多少?
(设搜索下一页的指针沿顺时针方向移动,且当前指向2号页框)。
答案:
17CAH=(0001011111001010)2
(1)页大小为1K,所以页内偏移地址为10位,于是前6位是页号,
所以第一问的解为:
5(2分)
(2)FIFO,则被置换的页面所在页框为7,所以对应的物理地址为(0001111111001010)21FCAH(2分)
(3)CLOCK,则被置换的页面所在页框为2,所以对应的物理地址为(0000101111001010)20BCAH(2分)
2.(6分)有一个具有两道作业的批处理系统,作业调度采用短作业优先调度算法,进程调度采用以优先数为基础的抢占式调度算法,如表所示的作业序列(表中所列作业优先数即为进程优先数,数值越小优先级越高)
作业名
到达时间
估计运行时间
优先数
A
10:
00
40分
5
B
10:
20
30分
3
C
10:
30
50分
4
D
10:
50
20分
6
(1)列出所有作业进入内存时间及结束时间。
(2)计算平均周转时间。
答案:
各作业进入内存的时间和结束时间见表:
作业名
进入内存时间
结束时间
A
10:
00
11:
10
B
10:
20
10:
50
C
11:
10
12:
00
D
10:
50
12:
20
各作业执行时的周转时间为:
A:
70分钟B:
30分钟C:
90分钟D:
90分钟(4分)
平均周转时间:
70分钟(2分)
3.(6分)假设有A,B,C,D4个记录存放在磁盘的某个磁道上,该磁道划分成4块,每块存放1个记录,其布局如下表所示。
块号
1
2
3
4
记录号
A
B
C
D
现在要顺序处理这些记录。
假定磁盘转速为20ms/圈,处理程序每次从磁盘读出一个记录后要花5ms进行处理,若磁头现在正处于首个逻辑记录的始点位置。
请问:
(1)处理程序处理完这4个记录所花费的时间是多少?
(2)按最优化分布重新安排这4个逻辑记录,写出记录的安排,并计算出所需要处理的时间。
答案:
磁盘旋转速度为20ms/周,磁道划分为4块,每块存放一个记录,所以读出一个记录要花5ms的时间。
优化前处理的总时间=(5+5)+(5*4+5)+(5*4+5)+(5*4+5)=85
优化后记录的顺序为:
A、C、B、D
优化后处理的总时间=(5+5)+(5+5)+(5+5+5)+(5+5)=45
4.(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%(3分)
(2)按LRU调度算法将产生6次缺页中断;依次淘汰的页号为:
2,0,1,3;
缺页中断率为:
6/10=60%(3分)
5.(6分)某系统有A、B、C、D四类资源可供五个进程P1、P2、P3、P4、P5共享。
系统对这四类资源的拥有量为:
A类3个、B类14个、C类12个、D类12个。
进程对资源的需求和分配情况如下,按银行家算法回答下列问题:
进程
已占有资源
最大需求数
ABCD
ABCD
P1
0012
0012
P2
1000
1750
P3
1354
2356
P4
0632
0652
P5
0014
0656
(1)现在系统中的各类资源还剩余多少?
(2)现在系统是否处于安全状态?
为什么?
(3)如果现在进程P2提出需要A类资源0个、B类资源4个、C类资源2个和D类资源0个,系统能否去满足它的请求?
请说明原因。
答案:
(1)A:
1;B:
5;C:
2;D:
0(2分)
(2)need矩阵为:
P10000
P20750
P31002
P40020
P50642
存在安全序列,如P1,P3,P4,P5,P2,所以安全。
(2分)
(3)能,因为试探分配后,可用资源为1,1,0,0。
可找到安全序列,所以可分配。
(3分)
五、程序与算法(共10分)
注:
本题答案为参考答案,与本答案有出入,可酌情给分。
一条小河上有一座独木桥,规定每次只允许一个人过桥。
现河东和河西都有相等的人数在等待过桥,为了使两边的人都有同样的过桥机会,规定某边的一个人过桥后要让另一边的一个人过桥,即两边的人交替过桥。
如果把每个过桥者看做一个进程,为保证安全,用PV操作来管理。
(1)写出应定义的信号量及其初值。
(2)假定开始时让河东的一个人先过桥,然后交替过桥。
请用适当的PV操作,达到上述管理要求。
答:
(1)定义两个信号量S1和S2,S1:
=1,S2:
=0。
(2)假定开始时让河东的一个人先过桥,则用PV操作管理时的程序应如下:
processE->W;
begin
……
P(S1);
过桥;
V(S2);
……
end;
processW->E;
begin
……
P(S2);
过桥;
V(S1);
……
end;