操作系统应用题及答案.doc

(完整word)操作系统应用题及答案
兰州大学期末考试
应用题
1. 假定在单CPU条件下有下列要执行的作业：
作业
运行时间
优先级
1
10
2
2
4
3
3
3
5
作业到来的时间是按作业编号顺序进行的(即后面的作业依次比前一个作业迟到一个时间单位)
(1）用一个执行时间图描述在采用非抢占式优先级算法时执行这些作业的情况。
(2)对于上述算法,求各个作业的周转时间、带权周转时间？并求出平均周转时间以及平均带权周转时间是多少?
答：（1）作业1 作业3 作业2
1 3 2

1 11 14 18
（2）周转时间:作业1：10 作业2：16 作业3:11
平均周转时间：(10＋16＋11）/3＝37/3
带权周转时间：作业1:1 作业2：4 作业3：11/3
平均带权周转时间：26/9
上述题目也可这样求：
作业
运行时间
开始执行时间
结束时间
周转时间
带权周转时间
1
10
1
11
10
1
3
3
11
14
11
11/3
2
4
14
18
16
4
平均周转时间为:（10+11+16）/3=37/3=12.3
平均带权周转时间为：（1+11/3+4）/3=26/9=2。89
若将该题改为短作业优先（非抢占式）结果一样。
2。 假定在单道批处理环境下有5个作业，各作业进入系统的时间和估计运行时间如下表所示：
作业
进入系统时间
估计运行时间/分钟
1
8：00
40
2
8:20
30
3
8：30
12
4
9:00
18
5
9：10
5

(1） 如果应用先来先服务的作业调度算法,试将下面表格填写完整。
作业
进入系统时间
估计运行时间/分钟
开始时间
结束时间
周转时间/分钟
1
8:00
40
8：00 
8：40 
40 
2
8:20
30
8：40 
9:10 
50 
3
8:30
12
9：10 
9：22 
52 
4
9：00
18
9：22 
9:40 
40 
5
9:10
5
9:40 
9：45 
35 
作业平均周转时间T=43.4（分钟）

（2）如果应用最短作业优先的作业调度算法，试将下面表格填写完整。
作业
进入系统时间
估计运行时间/分钟
开始时间
结束时间
周转时间/分钟
1
8：00
40
8：00 
8：40 
40 
2
8:20
30
8：52 
9：22 
62 
3
8：30
12
8:40 
 8：52
22 
4
9：00
18
9：27 
9：45 
45 
5
9:10
5
9：22 
9：27 
17 
作业平均周转时间T=37.2（分钟)

实际执行序列为：1 3 2 5 4
3。有4个进程P1、P2、P3、P4，它们进入系统的时刻和要求的运行时间如下表所示：
进程
进入时刻
要求运行时间
P1
0。000
3
P2
1.001
6
P3
4。001
4
P4
6.001
2
（1） 画图分别说明，系统采用先来先服务和短进程优先调度算法(非抢占式）时，它们的执行情况。
（2） 分别计算上述两种情况下进程的平均周转时间和平均带权周转时间。
解：(1)FCFS：
进程
进入时刻
要求运行时间
开始时间
完成时间
周转时间
带权周转时间
P1
0。000
3
0.000
3。000
3
1
P2
1.001
6
3.000
9。000
7。999
7。999/6
P3
4。001
4
9。000
13。000
8。999
8.999/4
P4
6.001
2
13.000
15。000
8.999
8.999/2
SPF:
进程
进入时刻
要求运行时间
开始时间
完成时间
周转时间
带权周转时间
P1
0.000
3
0。000
3.000
3
1
P2
1。001
6
3.000
9.000
7。999
7.999/6
P4
6。001
2
9。000
11。000
4.999
4.999/2
P3
4。001
4
11.000
15.000
10。999
10.999/4
(2)
平均周转时间为：FCFS(3+7。999+8.999+8.999）/4=28。997/4=7.25
SPF： (3+7。999+4.999+10.999）/4=26。997/4=6。7
平均带权周转时间：FCFS（1+7。999/6+8.999/4+8.999/2)/4=9/4=2。25
SPF： （1+7。999/6+4.999/2+10。999/4）/4=5。25/4=1。3
4. 假定系统中有4个进程P1、P2、P3、P4和3类资源R1、R2、R3（资源数量分别为9、3、6），在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 0 3
P4 4 2 2 0 0 2 4 2 0

试问： （1)t0时刻是否安全？
（2）P2发出请求向量request2（1，0,1)，系统能否将资源分配给它？（3）在P2申请资源后,若P1发出请求向量request1（1,0，1)，系统能否将资源分配给它？
（4)在P1申请资源后，若P3发出请求向量request3(0,0,1），系统能否将资源分配给它？
答案：（1)调用安全性算法
进程 资源
Work+Allo
Allocation
Need
Finish
R1 R2 R3
R1 R2 R3
R1 R2 R3

P2
6 2 3
5 1 1
1 0 2
TRUE
P1
7 2 3
1 0 0
2 2 2
TRUE
P3
9 3 4
2 1 1
1 0 3
TRUE
P4
9 3 6
0 0 2
4 2 0
TRUE

在t0时刻存在一个安全序列{P2,P1，P3,P4}，故系统是安全的。
（2） 当P2发出请求request2（1，0,1)，因为request2（1,0,1）〈need2（1，0,2)，并且request2（1,0,1）<available（1,1,2),所以进行假分配，修改：Allocation=(5,1，1）+（1,0,1）=（6，1,2)
Need=(1，0，2）-（1,0,1）=(0,0，1)
Available=（1，1，2）-（1，0,1）=（0，1，1)
调用安全性算法：
进程 资源
Work+Allo
Allocation
Need
Finish
R1 R2 R3
R1 R2 R3
R1 R2 R3

P2
6 2 3
6 1 2
0 0 1
TRUE
P1
7 2 3
1 0 0
2 2 2
TRUE
P3
9 3 4
2 1 1
1 0 3
TRUE
P4
9 3 6
0 0 2
4 2 0
TRUE
可以找到一个安全序列{ P2，P1，P3，P4}，故系统是安全的，可以将P2所申请的资源分配给它。
（3） 当P1发出请求request1（1,0,1)，因为request1（1，0,1）〈need1（2,2，2）,但是request1（1，0,1）并不小于等于available，因此暂时不能分配,P1阻塞
（4） 若P3发出请求向量request3（0，0，1），因为request3（0,0，1)<need3(1,0，3)， request3（0，0，1）〈available(0，1,1）,所以进行假分配，修改:Allocation=（2,1,1）+（0，0，1)=（2，1,2）
Need=（1，0,3）—（0,0，1）=(1,0，2）
Available=（0，1,1）—（0，0，1）=(0,1,0）
调用安全性算法：work=（0，1，0）,不能满足任何进程的最大需求,因此此前的假分配将被撤销，进程P3阻塞

5。设系统中有三类资源(A,B，C）和5个进程（P1,P2，P3,P4，P5），A资源的数量为17，B资源的数量为5，C资源的数量为20,T0时刻的系统状态见下表

进程
最大资源需求量
A B C
已分配资源数量
A B C
P1
P2
P3
P4
P5
5 5 9
5 3 6
4 0 11
4 2 5
4 2 4
2 1 2
4 0 2
4 0 5
2 0 4
3 1 4

（1） T0时刻是否为安全状态？若是，请给出安全序列？
（2） 在T0时刻若进程P2请求资源（0，3,4），是否能实施资源分配,为什么
（3） 在(2）的基础上,若进程P4请求资源（2，0，1），是否能实施资源分配,为什么？
（4）在(3）的基础上,若进程P1请求资源（0,2，0），是否能实施资源分配,为什么？
6。一个由3个页面(页号为0、1、2）,每页有2048个字节组成的程序，假定在某时刻调入8个物理块的内存，其页面的页号和物理块号的对照表如下：
逻辑页号
主存块号
0
4
1
7
2
1
请根据页表，计算下列给出的逻辑地址对应的绝对地址。
（1)100 （2）2617 （3）5196
答：首先根据逻辑地址查页表,得到主存的块号，再根据公式绝对地址=块号×块长+页内地址进行计算。
(1）100的页号为0（100/2048=0），页内地址为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为取模运算，即求余数）
7。 在请求分页系统中，某用户的编程空间为16个页面，每页1K，分配的内存空间为8K。假定某时刻该用户的页表如下图所示，试问:
（1）逻辑地址084B（H）对应的物理地址是多少？(用十六进制表示）
答：084B（H）对应的二进制为0000100001001011，因为每页大小为1K,即二进制数低址部分的10位是页内偏移，高址部分为页号,可得页号为2，查找页表，找到对应的块号为4，转换成二进制即为：0001 0000 0100 1011，对应的16进制数为：104B（H）
(2)逻辑地址5000（十进制）对应的物理地址是多少？（用十进制表示)
答：5000除以1024得页号为4,页内偏移为904。查找页表得对应的块号为12，所以5000对应的物理地址为:12×1024+904=13192
（3） 当该用户进程欲访问24A0（H)单元时，会出现什么现象？
答：通过前面的方法得出页号为9,大于页表的长度,因此产生越界中断
页号 块号
0
3
1
7
2
4
3
1
4
12
5
9
6
61
7
20
8. 有一个虚拟存储系统。分配给某进程3页内存，开始时内存为空,页面访问序列如下：
6、5、4、3、2、1、5、1、5、2、1、2、1、2、1、6、5
（1）       若采用先进先出的页面置换算法（FIFO)，缺页次数为多少?置换次数为多少？

序号
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
页面走向
6
5
4
3
2
1
5
1
5
2
1
2
1
2
1
6
5
内存
6
5
4
3
2
1
5
5
5
5
5
5
5
5
5
6
6

6
5
4
3
2
1
1
1
1
1
1
1
1
1
5
5

6
5
4
3
2
2
2
2
2
2
2
2
2
1
1
缺页
√
√
√
√
√
√
√

√

置换

√
√
√
√

√

缺页次数为：8 置换次数为：5
（2） 若采用最近最少使用的页面置换算法(LRU)，缺页次数为多少？置换次数为多少?
序号
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
页面走向
6
5
4
3
2
1
5
1
5
2
1
2
1
2
1
6
5
内存
6
5
5
3
2
1
5
1
5
2
1
2
1
2
1
6
5

6
6
5
3
2
1
5
1
5
2
1
2
1
2
1
6

4
6
5
3
2
2
2
1
5
5
5
5
5
2
1
缺页
√
√
√
√
√
√
√

√
√
置换

√
√
√
√

√
√
缺页次数:9 置换次数：6
9. 在采用请求分页存储管理的系统中，一作业的页面走向为1、2、3、4、3、1、5、4、6、2、1、2、5、7、3、2、4,假定分配给该作业的物理块数为4，开始时4个物理块全部为空。试计算用LRU调度算法时，访问过程中发生的缺页次数和页面置换次数，写出依次应淘汰的页面号。
答案:
序列
1
2
3
4
3
1
5
4
6
2
1
2
5
7
3
2
4
栈
1
2
1
3
2
1
4
3
2
1
3
4
2
1
1
3
4
2
5
1
3
4
4
5
1
3
6
4
5
1
2
6
4
5
1
2
6
4
2
1
6
4
5
2
1
6
7
5
2
1
3
7
5
2
2
3
7
5
4
2
3
7
缺页
√
√
√
√

√

√
√
√

√
√
√

√
置换

√

√
√
√

√
√
√

√
缺页次数为：12 置换次数：8
依次应淘汰的页面号为：2、3、1、5、4、6、1、5
10．在一个请求分页系统中,假如系统分配给一个作业的物理块数为3，此作业的页面走向为4，3，2,1,4，3，5，4,3，2，1,5。试用FIFO和LRU两种算法分别计算出程序访问过程中所发生的缺页次数和置换次数，并给出依次应淘汰的页面号
11。 某移动臂磁盘的柱面由外向里顺序编号,假定当前磁头停在100号柱面且移动臂方向是向里的，现有如下表1所示的请求序列在等待访问磁盘：
　　表1 访问磁盘请求序列
请求次序
1
2
3
4
5
6
7
8
9
10
柱面号
190
10
160
80
90
125
30
20
140
25
回答下面的问题：写出分别采用“最短寻道时间优先算法”和“电梯调度算法”时，实际处理上述请求的次序以及平均寻道时间。
SCAN：
下一个
磁道号
移动
距离
125
140
160
190
90
80
30
25
20
10
25
15
20
30
100
10
50
5
5
10
平均寻
道时间
27
SSTF:
下一个
磁道号
移动
距离
90
80
125
140
160
190
30
25
20
10
10
10
45
15
20
30
160
5
5
10
平均寻
道时间
31
12。 假定一个磁盘有200个柱面，编号为0~199,在完成了对125柱面的请求后，当前正在143号柱面处为一个请求服务。请求队列中还有若干个请求者在等待服务，假设他们依次要访问的柱面号为：86,147,91,177，94，150，102，175,130。请分别计算SSTF、SCAN和CSCAN算法时实际服务的次序和磁臂移动的距离，并求平均寻道长度。
答案：
SSTF: 147 150 130 102 94 91 86 175 177
磁头移动总量：162 平均寻道长度：162/9=18
SCAN： 147 150 175 177 130 102 94 91 86
磁头移动总量：125 平均寻道长度:125/9=13.9
CSCAN：147 150 175 177 86 91 94 102 130
磁头移动总量：165 平均寻道长度：165/9=18。3
13.采用可变分区方式管理主存空间时，若主存中按地址顺序依次有5个大小分别为15KB、28KB、10KB、226KB和110KB的空闲区。现在有5个作业Ja、Jb、Jc、Jd和Je，它们所需的主存依次为10KB、15KB、102KB、26KB和180KB。请问：
（1）如果采用首次适应算法能把这5个作业按Ja~Je的次序全部装入主存吗？P87
（2）用什么分配算法装入这5个作业可使主存的利用率最高?
答案：
（1）不能.
装入Ja后内存空闲区变为：5KB、28KB、10KB、226KB和110KB
装入Jb后内存空闲区变为:5KB、13KB、10KB、226KB和110KB
装入Jc后内存空闲区变为：5KB、13KB、10KB、124KB和110KB
装入Jd后内存空闲区变为：5KB、13KB、10KB、98KB和110KB
因为Je需要180KB的内存区,所以不能满足

（2)用最佳适应算法。
14。假定某系统采用可变分区管理技术，某时刻在内存中有3个大小分别为35KB、25KB、50KB的空闲块，它们的起始地址依次递增.请构造一个内存请求序列，使得首次适应分配算法能满足该请求序列，而最佳适应分配算法则不能。要求对构造出的序列满足分配算法的情况进行简单的文字说明或图示。
答案：
内存请求序列为：5KB、35KB、30KB｜、25KB。设这是4个作业J1、J2、J3、J4的内存请求,则系统采用两种分配法的分配过程如下：
（1） P267
15.一个进程已分配到4个内存块,如下表所示。
页号
内存块号
装入时间
最近访问时间
访问位
修改位
2
0
60
161
0
1
1
1
130
160
0
0
0
2
26
162
1
0
3
3
20
163
1
1
当进程访问自己地址空间中的4号页面时产生缺页中断。请分别用FIFO、LRU、NRU算法,决定缺页中断服务程序选择换出的页面.
答案：
（1）FIFO：页面3最早被装入3号内存块，所以先换出.
（2)LRU：
P267
16。假定磁盘的磁臂现位于6号柱面上，下表列出6个请求者等待访问磁盘，试列出最省时间的响应次序。
序号
1
2
3
4
5
6
柱面号
7
5
15
7
20
5
磁道号
6
5
20
4
9
15
块号
2
6
6
4
5
2
答案：现进行移臂调度，要求移臂时间短；再进行旋转调度，要求旋转周数最少。
最省时间的响应次序为:6-2-1-4—3-5
17。设某文件为链接文件，由5个逻辑记录组成，每个逻辑记录的大小与磁盘块大小相等,均为512B，并依次存放在50、121、75、80、63号磁盘块上。若要存取文件的第1569逻辑字节处地信息,问要访问哪一个磁盘块?
答案：
因为1569=512×3+33,所以要访问字节的逻辑记录号为3,对应的物理磁盘块号为80。故应访问第80号磁盘块。
18。某磁盘共有500000个块，当前有200000个空闲块，每个地址占16位，若用位示图实现该磁盘的空闲块表，则共需要多少个二进制位？
答案：
500000个。