操作系统解答题练习.doc

2
1

１09
Ｄ
3
１
100
1０1
98
97
平均周转时间T＝129、２５
2、(3分）处理机调度算法得效果可以用周转时间与带权周转时间来度量。请说明这两者有什么异同?
参考答案：两者都就是从作业提交到完成得时间来度量算法得优劣。但后者考虑作业得等待时间对于作业本身得服务时间得相对影响因素,因此当作业得差异性很大时,评价更客观些。
３、在单道批处理系统中,下列三个作业采用先来先服务得调度算法与最高响应比优先算法进行调度,哪一种调度算法得性能较好?请完成下表。
作业
提交时刻
运行时刻
开始时刻
完成时刻
周转时间/ｍｉn
带权周转时间
1
10:０0
2:00

2
10:1０
１:０0

3
１０:2５
0:2５

平均周转时间Ｔ=
平均带权周转时间W=
参考答案:
先来先服务调度算法：
作业
提交时刻
运行时刻
开始时刻
完成时刻
周转时间／ｍｉn
带权周转时间
1
10:00
2：00
10:０0
１２:0０
120
１
2
1０:10
1：00
1２:０0
13:00
１7０
17/6
3
１０：2５
０：25
１3:00
１3:25
1８0
36／5
平均周转时间T＝156、6７mｉｎ
平均带权周转时间W=３、68
最高响应比优先调度算法：
作业
提交时刻
运行时刻
开始时刻
完成时刻
周转时间／ｍin
带权周转时间
1
10：0０
2:00
10:00
12：00
1２０
1
2
10：10
１:00
１2：25
13：２5
19５
３、25
3
10：２５
0:25
12:0０
１２：25
120
4、8
平均周转时间T=145ｍin
平均带权周转时间W=3、02
综上所述,最高响应比调度算法性能较好。
4、　如果限制为两道得多道程序系统中,有4个作业进入系统,其进入系统时刻、估计运行时间为下图所示。系统采用SJF作业调度算法,采用SRＴF进程调度算法,请填充下面表格。
作业
进入系统时刻
估计运行时间/ｍｉn
开始运行时刻
结束运行时刻
周转时间/ｍin
1
１0:０0
30

２
１0：０5
20

3
1０:10
５

4
10:２０
１0

平均周转时间T＝
平均带权周转时间W＝
参考答案:
作业
进入系统时刻
估计运行时间/ｍｉn
进入内存时刻
开始运行时刻
结束运行时刻
周转时间/min
1
10:0０
30
１0:00
1０：00
１1:05
65
2
１0:０５

20
１０:05
10:０5
10:25
20
3
１0:10
5
1０:2５
1０：２5
10:30
20
４
１0:20
１0
10：30
1０:30
10:４０
20
平均周转时间Ｔ=31、2５min
平均带权周转时间W=２、3
5、　有一个4道作业得操作系统,若在一段时间内先后到达6个作业,其提交时刻与估计运行时间为下表所示:
作业
提交时刻
估计运行时间/min
1
8:00
６0
2
８:２０
３５
3
８:２5
20
4
8:30
25
5
8:３5
５
6
8:40
10
系统采用剩余SJＦ调度算法，作业被调度进入系统后中途不会退出,但作业运行时可被剩余时间更短得作业所抢占。
（1)分别给出6个作业得执行时间序列,即开始执行时间、作业完成时间、作业周转时间。
(2)计算平均作业周转时间。
参考答案:
作业
提交时刻
估计运行时间/min
进入内存时刻
剩余时间/min
开始时间
完成时间
周转时间/min
1
８:0０
60
８：０0
４0
8:00
10:3５
155
２
8：２0
35
8：20
3０
8:20
9:５5
95
3
8:25
20
8:25
15
8:25
８:45
20
4
8:3０

2５
8:３０
25
9:0０
９:2５
55
5
8:3５
5
８:45
5
8:45
8：5０
15
６
８:40
10
８:50
10
8：５０
9：00
20
平均周转时间T=６0miｎ
6、 有一个具有三道作业得多道批处理系统,作业调度采用短作业优先调度算法,进程调度采用以优先数为基础得抢占式调度算法。在下表所示得作业序列中,作业优先数即为进程优先数,数越小则优先级越高。
作业
到达时刻
估计运行时间/ｍin
优先数
A
10:00
40
5
B
１0:20
3０
3
C
１0:30
60
４
D
10:50
2０
6
Ｅ
１１:00
20
4
F
11：10
10
４
试填充下表：
作业
进入内存时刻
运行结束时刻
作业周转时间/ｍin
A

B

C

Ｄ

E

F

平均作业周转时间T=
参考答案:
作业
进入内存时刻
开始运行
时刻
运行结束时刻
作业周转时间/min
Ａ
10:０0
10:00
12:40
160
Ｂ
１0:20
10：2０
10:5０
30
Ｃ
10:３0
10:50
11:5０
80
Ｄ
１0:5０
12:40
13：０0
130
E
12:0０
１2:０0
１２:20
80
F
１1:５0
１1：50
１２:0０
50
平均作业周转时间T=88、３mｉn
1、(２分)生产者消费者得互斥同步问题叙述如下:
生产者生产产品,放入有ｎ个缓冲区得缓冲池中,每个缓冲区只能放一个产品。消费者从缓冲池中取产品消费,不允许从空缓冲区中取产品。有多个生产者进程与多个消费者进程并发进行，任何时刻只允许一个进程访问缓冲池。生产者进程与消费者进程分别从缓冲池中得同一位置开始,顺序循环地使用缓冲池，放产品或取产品。当缓冲池得n个缓冲区都满时,生产者进程必须在缓冲池外等待。当缓冲池得n个缓冲区都空时,消费者进程必须在缓冲池外等待。
使用记录型信号量对生产者消费者问题得解答如下:

设置整型量n,设定缓冲池(临界资源)中得缓冲区总数
设置互斥信号量mutex,初值1,记录对缓冲池得互斥访问
设置信号量empty，初值n，记录缓冲池中空缓冲区数　
设置信号量ｆｕll,初值0,记录缓冲池中满缓冲区数
生产者与消费者得并发程序如上面得流程图所示。
请回答下面得问题
(1)、(1分）如果将生产者进程中得两个P操作语句(S２与Ｓ3）得执行次序反过来,可能会造成死锁。试分析其原因,发生死锁时缓冲池中得缓冲区有几个就是满得?
参考答案:ｎ个
(2)、(1分）如果将消费者进程中得两个P操作语句(X1与X2)得执行次序反过来,可能会造成死锁。试分析其原因,发生死锁时缓冲池中得缓冲区有几个就是满得?
参考答案:0个(或n个全就是空得)
２、(5分)设两个进程并发访问一个打印机分配表，A进程申请打印机,从打印机分配表读入状态字,进程B向打印机分配表写入状态字。这两个进程对打印机分配表得操作就是互斥得，用P／Ｖ操作表示进程A与B得操作过程。
参考答案：
设互斥信号量Ｓ=1
进程A　: 　　　    　            　进程Ｂ：    
……  　 　  　　 　  　   　　　　 　  　 　 ……
P（S)；      　   　  　     　  　　  　P(S);
读入打印机分配表;          　  修改打印机分配表;
V(S）;　    　         　  　　　  　V(S);
……    　     　       　　    　　   ……
1、(８分）设系统中有三种类型得资源（A，B,C)与五个进程(Ｐ1,P2,P３,Ｐ4，Ｐ5),A资源得数量17，B资源得数量为５，C资源得数量为2０。在T０时刻系统状态如表所示。系统采用银行家算法来避免死锁。

请回答下列问题： 　
(１）T０时刻就是否为安全状态？若就是,请给出安全序列。
(２）若进程P4请求资源(２，0,１),能否实现资源分配？为什么?　
（３)在(2)得基础上，若进程P1请求资源(0，２,０),能否实现资源分配？
参考答案:
（１)Ｔ０时刻为安全状态。其中得一个安全序列为(P4,Ｐ5,P３,P2,P1)　（其她可能得安全序列有:（P4,P5,X，X,X),(Ｐ4，P2，X,X，X）, （P4，Ｐ3,X,X,Ｘ),(P5,Ｘ,X,X，X）)
(２）可以为P４分配资源,因为分配后得状态还就是安全得，其安全序列得分析如下表:
|  　Worｋ  ﻩ|　 Ｎeed   ｜ 　Alｌｏcation ﻩ| Work+Aｌlｏcation | Finiｓh
  |　 A  Ｂ 　C　 ｜  A B Ｃ  |   A  Ｂ　 C | 　 A  Ｂ　　C 　　        
P4 ｜ 　 ０  3　 2 ｜  ０　２ 0   ｜   ４  ０   5 | 　 ４  3  　7　　| Tｒuｅ
P5 |　  ４  3　　7 ﻩ|  1 1 0   |   ３　 1　  4 ﻩ|　  ７  4  １1 　| Truｅ
P1 |   7 　4 　1１ﻩ｜  ３　４ 7　  |　 　2  １  　2 ｜　 　９　 5  1３ | Ｔｒｕe
P2 | 　　９  5 　13　ﻩ|  1　３ 4   ｜　 　4 　0　  2 ﻩ|  13  ５　 15 ﻩ｜ Ｔrｕe
P３　| 　13  5  １5 |  0 0 6   |   4  0　  ５ﻩ｜  17  5 　20 | True
(３） 进程P１再请求资源(0，2,０),则不能为之分配资源。
２、(15分)考虑一个系统在某个时刻得状态如表所示。

应用银行家算法回答下列问题:
(１)填写Need矩阵得内容
（2)系统就是否处于安全状态?
（３)如果进程P1发出请求(0,4，2，0),这个请求能否被满足?
参考答案:
（1)根据银行家算法,可列出Need矩阵如下表:
进程 ﻩ|　 　　 Need |　Alloｃation ﻩ|   　 Ｍax ｜  Aｖailａble
　 ﻩﻩ|   Ａ B　C D ﻩ｜  A Ｂ C D ﻩ|   Ａ B Ｃ D ﻩ|   A B C　D 　  　   　   　 　　
P0   　 ｜  　0 ０  0 ０　ﻩ|  0 0  １ 2 |　 　0 0  1 2　ﻩ|　  1　5　 2 ０
Ｐ1 　   | 　　0 7  5 0 |  1　0  0 ０ | 　 1　7　 5 ０ |
P2     |　  1 0  0 ２ |  1 3  5 4 ﻩ|   2 3  ５ 6 ﻩ|
Ｐ3   　ﻩ|   0 0  ２　0 ｜ 　０ 6 nbsp;3 2 ﻩ|　  ０ 6  5 ２ ﻩ｜
Ｐ4 　　　 | 　　０ 6 　4 6　 | 　0 0  1　４ ﻩ|   0 6　 5　6 ﻩ|
(2)利用安全性算法,列出下表:
进程 ﻩ|     Ｗork ﻩ |　 　　 Neｅd　ﻩ| Aｌｌｏcａtｉoｎﻩ| Work+Ａllocation | Ｆiｎish
      |　 A 　B　 C  D |   Ａ B C Ｄ　ﻩ|  　A B C D ｜　　A  B 　 C  D | nbsp;　  　　　
Ｐ0     ｜　 1   5  2  0  ﻩ|  　０ 0  0 ０ |  ０　0　 １ 2 | 　1　　 5   ３  2 |  tｒue
Ｐ1 　   | 　1   ５　　3  ２ﻩ|  　１ 0  0　２ﻩ|  １ 7 　5 0 | 　2 　12　  8 　2ﻩ|  trｕｅ
P2 　  ﻩ|　 2 1２ 　8  2 |　 　0　０ 　2 ０ﻩ|  0 6　 3 2ﻩ|  2  18　　11  ４ |  true
P３    ﻩ|  2 １8 １1 4　 | 　 0 6  4 6ﻩ|  ０ ０ 　１ 4ﻩ|  2 　18　 １2　 8ﻩ|  tｒｕe
P4     |　 ２ 18 １2　8  ﻩ ｜   ０ 7　 5 0ﻩ| 　1 ０　　0　0 ｜　 3  １8 　1２  8 ﻩ|　 trｕe
存在安全序列 (P0,P2，P3，P4,P1)系统处于安全状态。
(３)进程P1发出请求(０，4,２，0),可进行分配,结果得到如下表:
进程 ﻩ|　    Neｅdﻩ|  Allｏcatｉonﻩ| 　　Ｍax    ﻩ| 　Ａvaiｌａble
　 　 ｜　  A B　Ｃ Dﻩ|  　A B　C　D |  A B　Ｃ D |   Ａ　B Ｃ Ｄ    　      　　  
Ｐ０　   ﻩ|  　0 0 　０ 0 |  　0　0  1　2 |  ０ 0  1 2  ﻩ|  　1 1 　0　０
P１　   | 　 ０　3  3 ０ﻩ|   1 4  2 0ﻩ|　 1　7 　5 0　 ﻩ|　
P２ 　  ﻩ｜ 　 1 0  0 2 ﻩ|　  １　3 　5　4ﻩ｜  2 ３ 　5 6　　 ｜
P3     |   ０ 0　 2 0 |   ０ ６ 　３　2 | 　0 ６  5 ２  ﻩ｜
Ｐ４　   ﻩ| 　　0 6 nbsp;4 6 |   0 0  １ 4ﻩ|  0　6  5 6  ﻩ|
用安全性算法检查,列出
进程 | 　　 　Woｒk   　ﻩ｜     Ｎｅedﻩ|  Allocatｉoｎ ﻩ｜ Wｏｒk+Allocaｔｉｏｎ ｜ Ｆinish
ﻩﻩ|　　A  Ｂ　　C  Dﻩ｜　  A B C D |  Ａ B C Ｄ |  A　 B  　C　 D ｜
P0　 ﻩ|  1 　 1  0  0   |　  0 0  0 ０ |　 0 0　 １　2 |  １   1   1  ２ |  ｔrue
P1    ﻩ｜ 　１   1  0  ２　 ｜   1 ０  0 2 |  1　7  ５　０ﻩ|  ２   8   6　 2 |　 tｒue
P２    ﻩ|  2   8  6 　2  ﻩ｜ 　　0 ０ 　2　0 |  0 ６ nbsp;３ ２ﻩ｜  2  1４　  9  4 |　 tｒｕe
P3　   ﻩ|  2 　14 　9  4 　 |  　０　6  4 ６ﻩ|  0　0　 １ 4 |  2  １４  １０  ４ ｜　　ｔrue
P4 　   |  ２ 　14 10  8ﻩ|　　　０　3　 3　0 ｜　　1　４　 2　0ﻩ| 　３   8  12　 8ﻩ|　　tｒue
存在安全系列(P0,P2,Ｐ3,Ｐ4，Ｐ1），因此可满足需求,可分配所需要资源。
1、(1分） 给定段表如下:
段号   ｜　  　段基地址    |  　　段长
０  　  　  |   　210  　     　  　｜  　 ５00
1    　　  ｜　   ２350    　　    |    ２0
２   　    |   　1０0    　  　　　  ｜　   ９0
3     　　　|    1350　  　     　|    590
４   　　　  | 　  193８　　　    　　 ｜ 　  95
试求分段地址(3, 500)所对应得物理地址？  
参考答案:1850
2、(1分)在分页式存储管理中,快表被用来提高访问内存中得数据得存取速度。假定查找快表需要10ns,访问内存一次需要１00ns，如果采用二级页表结构,而快表得命中率就是60％,问对于内存数据得平均存取时间就是多少?
参考答案:０、6*(1０+100) ＋　0、4*（１0+300）　= 190
4、(1分)设有一分页管理系统,管理总共16个存储块,每个页面大小为1024,问物理地址至少应有多少位?
参考答案：1６个存储块得块号最多需要4位,每块有1０２4个存储单元,即所需得地址数需要10位,所以物理地址总长为14位。
5、(1分)设有一分页管理系统,能够管理得逻辑地址空间最多可有１６个页面,每个页面大小为1024,问逻辑地址至少应有多少位？
参考答案:页号占4位,页面占10位,逻辑地址至少要有１4位。
6、(１分）假定地址长度为16位,页面大小为１024。问二进制分页地址(1００0　１0, 1000 1０00）得二进制逻辑地址得表示　
参考答案:1000　 １010001000
7、（１分)假定地址长度为16位,页面大小为1０24。问二进制逻辑地址(０00１ 0001 000１ 00０1)得二进制分页地址得表示
参考答案：0100  ０100０100０1
8、（1分)在一个段式存储管理系统中,其段表为：
 　 　   段号   　  内存起始地址 　 　  段长
　    　   ０    　   　　 2１0　        　  　５00
   　    1   　 　    　235０            20
　        2   　  　 　  １00　 　       　 　９0
     　 　3 　  　      １3５0   　 　 　  　 5９0
 　      ４         　 １９３8　  　　  　  　 ９5
试求表中逻辑地址(0,４30)(2,12０)对应得物理地址就是什么?
参考答案:逻辑地址(０，430)表示段号为２，即段首地址为2１０,对应得物理地址为:210+4３0=640
逻辑地址(２，1２0）因为段内地址1２0＞段长90,所为该段为非法段,越界。
10、(5分)请求分页存储管理中,假定系统为某进程分配了３个物理块,开始时3个物理块都为空,进程运行时得页面走向为：7, 0， 1, ０，　3, ０, 7, 0， １,　4, 6,　3,　６， 0, １, 3,　６,　1, 3, 2。如果使用先进先出置换算法,请问缺页率就是多少？
参考答案:75%
1１、(5分）在一个请求分页系统中,采用ＬRU页面置换算法时,假如一个作业得页面访问顺序为４,3,２,1,4,3,5,4,3,2, 1,5,当分配给该作业得物理块数M为4时，试写出页面访问得过程,并计算访问中所发生得缺页次数与缺页率？
参考答案:产生缺页次数8次，缺页率为8/12≈66、7%
1２、（２0分)对于如下得页面访问序列:
1　， 2 , 3 ,　4 , 1　, 2 ,　5 , 1　, 2 , 3　, ４　，　5　
当内存块数量分别为　3 与 4 时,试问：使用 ＦIＦＯ 与LRU　置换算法产生得缺页中断次数与缺页中断率分别就是多少？(所有内存开始时都就是空得，凡第一次用到得页面都产生一次缺页中断)
参考答案：
FIFO 淘汰算法:　
页面
1
2
３
4
1
２
５
1
2
３
4
5
块1
1
1
1
４
４
4
５

5
５

块2

2
2
2
1
1
1

３
3

块3

3
3
３
２
2

2
4

缺
缺
缺
缺
缺
缺
缺

缺
缺

内存块为　3 时,缺页中断(或称缺页次数、页面故障）为 9 缺页中断率为７５％;
页面
1
2
3
4
１
2
5
1
２
3
4
5
块1
１
1
1
1

5
5
５
5
4
4
块2

2
2
2

2
１
1
1
1
5
块３

3
3

3
３
2
2
2
2
块4

4

4
4
４
3
３
3

缺
缺
缺
缺

缺
缺
缺
缺
缺
缺
内存块为 ４ 时,缺页中断为 10 ,缺页中断率为8３%。
LRＵ 淘汰算法:
页面
1
２
3
4
1
２
５
1
2
3
4
5
块1
1
1
１
4
4
４
5

3
3
3
块2

2
2
2
1
1
1

1
4
4
块3

3
３
３
2
2

2
２
５

缺
缺
缺
缺
缺
缺
缺

缺
缺
缺
内存块为　3 时,缺页中断为 １０ ，缺页中断率为83%;
页面
１
2
3
４
１
2
5
1

２
３
4
5
块1
1
1
1
1
１
1
1
1
１
1
1
5
块2

２
2
２
２
2
2
2
2
2
2
2
块３

3
3
3
3
5
5
５
5
４
4
块4

４
4
4
4
4
4
３
3
3

缺
缺
缺
缺

缺

缺
缺
缺
内存块为 ４ 时,缺页中断为 8 缺页中断率为６6、7%。
１、 假定磁盘有200个柱面,编号为0~１９9,当前存取臂得位置在１43号柱面上并刚刚完成12５号柱面得服务请求。如果请求队列得先后顺序就是:86,14７,91,177,9４，150,10２，175，１３0;试问:为了完成上述请求,下列算法存取臂所移动得总量就是多少？并计算存取臂移动得顺序。(１）先来先服务算法FCFS;(2)最短查找时间优先算法SSTF;（3)扫描算法SＣAN;(4)电梯调度算法。
参考答案:
(1）先来先服务算法FCFS 为５65 ,依次为143　-８6 －14７　-9１ -1７7　-94　-1５０ -102 -175　-130
（2)最短查找时间优先算法SＳTF 为162 ,依次为１43 -147 -１50 -13０ －1０2 -９4 －91 －86 -1７5　－177
(3）扫描算法SCAＮ 为169 ，依次为143 -14７ -150　-１７5　-17７　-１９9　-130 -1０2 -94 -91 －８６　
(４)电梯调度为12５,依次为1４3　－１47 -150 －175 －１77　－13０-１02　-94 －91　-8６