汉英字典-铜皮
第六章
作业
1
．存
放在某个磁盘上的文件系统，采用混合索引分配方式，其
FCB
中共有
13
个地址项，第
0~9
个地址项为直接地址，第
10
个地址项为一次
间接地址，第
11
个地址项为二次间接地址，第
12
个地址项为三次间接地址。如果每个盘块的大
小为
512
字节，
若盘块号需要用
3
个字节来描述，
而每个盘块最多存放
170
个盘
块地址：
(1)
该文件系统允许文件的最大长度是多少
< br>
(2)
将文件的字节偏移量
5
000
、
15000
、
150000
转换为物理块号和块内偏移量。
答
：（
1
）
该
文
件
系
统
中
一
个
< br>文
件
的
最
大
长
度
可
达
：
10+170+170*170+170*170*170=
4942080
块
=4942080*512
< br>字节
=2471040KB
（
2
）
5000/512
得到商为
9
，余数为
392<
/p>
，即字节偏移量
5000
对应的逻辑块号
为
9
，块内偏移量为
392
。由于
9<10
，故可直接从该文件的
FCB
的第
9
个地址项处
得到物理盘块号，块内偏移量为
392
。
15000/512
得到商为
29
，余数为
152
，即字节偏移量
15000
对应的逻辑块
号为
29
，块内偏移量为
152<
/p>
。由于
10
≤
2
9<10+170
，而
29-10=19
，故可从
FCB
的第
10
个地址项，即一次间址项中得到一次间址的地址；并从一次间址块的第
19
项（即该块的第
57~59
这
3
个字节）中获得对应的物理盘块号，块内偏移量
为
152
。
150000/512
得到商为
292
，余数为
496
，即字节偏移量
15
0000
对应的逻辑
块
号
为
292
，
块
内
偏
移
量
< br>为
496
。
由
< br>于
10+170
≤
292<10
+170+170*170,
而
292-(10+170)=1
12
，
112/170
得到商为
0
，余数为
112
，
故可从
FCB
的第
11
个地
址项，
即二次间址项中得到二次间址块的地址，<
/p>
并从二次间址块的第
0
项中获得
一个一次间址块的地址，再从该一次间址块的第
112
< br>项中获得对应的物理盘块
号，块内偏移量为
496
。
（
3
）由于文件的
FCB
已在内存，为了访问文件中某
个位置的内容，最少需要
1
次访问磁盘（即可通过直接地址直接
读文件盘块）
，最多需要
4
次访问磁盘
（第
一次是读三次间址块，
第二次是读二次间址块，
第三次是读一次间址块，
第四次
是读文件盘块）<
/p>
。
2.
在某个文件系统中，每个盘块为
512
个字
节，文件控制块占
64
个字节，其中
文
件名占
8
个字节。如果索引结点编号占
2
个字节，对于一个存放在磁盘上的
256
个目录项的目录，试比较引入索引结点前喉，为找到其中一个文件的
FCB
，
平均启动磁盘的次数
答：在引入索引结点前，每个目录项中存放的是对应文件的
FCB
，故
256
个目录
项的目录总共需
要占用
256*64/512=32
个盘块。
< br>因此，
在该项目录中检索到一个
文件，平均启动磁盘的次
数为（
1+32
）
/2=
。
在引入索引结点
之后，每个目录项中只需存放文件名和索引结点的编号，因
此
2
56
个目录项的目录总共需要占用
256*(8+2)/512
=5
个盘块。
因此，
找到匹配
的目录项平均需要启动
(1+5)/2
，即
3
次磁盘；而得到索引结点编号后，还需启
动磁盘将对应文件的索引结点读入内存，
故平均需要启动磁盘
4
次。
可见，
引入
索引结点后，可大大减少启动磁盘的次数，从而有效地提高检索文件的速度。
第五章
作业
1
．有
一移动臂磁盘，共
100
个磁道，每个磁道分
< br>8
个扇区，磁盘转速为
500r/s
（转
/
秒）
，磁头每移动一个磁道
需要
10ms,
有一用户请求访问第
2
5
磁道第
3
扇
区，并立即被系统响应，假设磁头当时处于
15
道
上，磁头到达第
25
道时
正处
于
1
扇区的开始位置，试计算该用
户至少需要等待多长时间
2.
若有
磁盘共有
200
个柱面，其编号为０～
199
，假定磁头刚完成
56
号磁道的
访问，磁头正在
98
号磁道上，并向磁
道号增加的方向移动，现有一个请求队列
在等待访问磁盘，访问的磁道号分别为
190
，
97
，
90
，
45
，
150
，
32
，
162
，
108
，
112
，
80
。请写出分别采用
FCFS
、
SSTF
、
SCAN
和
CSCAN
算法进行调度磁盘时的请
求次序，并计算出它们的平
均寻道长度。
3
．假定磁盘转速为<
/p>
20ms/
圈，磁盘格式化时每个磁道被划分成
< br>10
个扇区，今有
10
个逻辑记
录（每个记录的大小刚好与扇区大小相等）存放在同一磁道上，处
理程序每次从磁盘读出
一个记录后要花费
4ms
进行处理，现要求顺序处理这
10
个记录，若磁头现在正处于首个逻辑记录的始点位置。请问：
（
1
）按逆时针方
向安排
10
个逻辑记录（磁盘顺时针方向转）
< br>，处理程序处理完
这
10
个记录
所花费的时间是多少
（
2
）
按最优化分布重新安排这
10
< br>个逻辑记录，
写出记录的安排，
并计算出所需
要处理的时间。
1.
某系统采用页式存储管理策略，拥有逻辑空间
32
页，每页
2K
，拥有物理空间
1M
。
（
1
）请写出逻辑地址的格式。
（
2
）若不考虑访问权限等，进程的页表有多少项每项至少有多少位<
/p>
（
3
）如果物
理空间减少一半，页表结构应相应作怎样的改变
答：
（
1
）该系统拥有逻辑空间
32
页，故逻辑地址中页号必须用
5
位来描述；而
每页为
2K
，因此，页
内地址必须用
11
位来描述，这样可得到它的逻辑地址格式
如下：
15
11 10 0
页号
页内地址
（
2
）每个进程最多有
32
个页面，因此，进程的页表项最多为
32
项；若不
考虑
访问权限等，则页表项中只需给出页所对应的物理块号，
1
M
的物理空间可分成
2
9
个内存块，故每个页表项至少有
9
位。
（
3
）如果物理空间减少
一半，则页表中页表项数仍不变，但每项的长度可减少
1
位。<
/p>
2.
对一个将页表存放在内存中的分页
系统：
（
1
）如果访问内存需要微秒，有效访问时间为多少
（
2
）如果加一快表，且假定在快表中找到页表项的几率高达
90
％，则有效访问
时间是多少（假定查找快表需花的
时间是
0
）
答：
（
1
）有效访问时间为；
2*=
微秒
(2)<
/p>
有效访问时间为：
*+*2*=
微秒
3
．某分页系统，主存容量为
64K
，页面大小为
1K
，对一个
4
页大的作业，其
0
、
1
、
2
、
3
页分别被分配到主存的
2
、
4
、
6<
/p>
、
7
块中。
<
/p>
(1)
将十进制的逻辑地址
1023
、
2500
、
35
00
、
4500
转换为物理地址。
(2)
以十进制的逻辑地址
1023
为例画出地址变换过程图。
答：
（
1
）对上述逻辑地址
，可先计算出它们的页号和页内地址（逻辑地址除以页
面大小，得到的商为页号，余数为
页内地址）
，然后通过页表转换成对应的物理
地址。
①逻辑地址
1023:1023/1K
，得到页号为
0
，页内地址为
< br>1023
，查页表找到对应
的物理块号为
2
，故物理地址为
2*1K+1023=3071
②逻辑地址
2500:2500/1K<
/p>
，得到页号为
2
，页内地址为
452
，查页表找到对应的
物理块号为
6
，故物理地址为
6*1K+452=6596<
/p>
③逻辑地址
3500:3500/1K
，得到页号为
3
，页内地址为
428
，查页表找到对应的
物理块号为
7
，故物理地址为
7*1K+428=7596
④逻辑地址为
4500:4500/
1K
，得到页号为
4
，页内地址为
404
，因页号不小于页
表长度故产生越界
中断。
4
．某操作系统采用可变分区分配存储管理方法，用户区为
512K
且始址为
0
，用
空闲分区表管理空闲
分区。
若分配时采用分配空闲区低地址部分的方案，
且初始
时用户区的
512K
空间空闲，对下述申请
序列：
申请
300K
，申请
100K
，释放
300
K
，申请
150K
，申请
30K
，申请
40K
，申请
60K
，
释放
30K
回答下列问题：
(1)
采用首次适应算法，空闲分区中有哪些空块
(2)
采用最佳适应算法，空闲分区中有哪些空块
(3)
如再申请
100K
，针对
(1)
和
(2)
各有什么结果
5
．在一分页存储管理系统中，逻辑地址长度为
16
位，页面大小为
4096
字节，<
/p>
现有一逻辑地址为
2F6AH
，且第
0
、
1
、
2
页依次存放在物理块
5
、
10
、
11
中，问
相应的物理地址为多少
答：
由题目所给条件可知，该系统的逻辑地址为
16
位，其中高
4
位为页号。页
面大小
4096
字节，共要占有二进制
12
位，低
12
位为页内地址；另外，由于题
目中给出的逻辑地址是十六进制数，
故可先将其转换成二进制数以直接获得页号
和页内地址，再完成地址的转换
2F6A
H
为
000
，由此看出，逻辑地址（<
/p>
2F6A
）
16
的页号为（
0010
）
2
，即
2
，故页
号合法；从页
表中找到对应的内存块号为
11
，即（
1011
）
2
；与页内地址（）
2
拼接形成物理地址（
010
）
2
，即（
BF6A
）
16
。
6.
在一个段式存储管理系统中，其段表如图
1<
/p>
段号
内存起始地址
段长
0 210
500
1 2350
20
2 100
90
3 1350
590
4 1938
95
图
1
试求图
2
逻辑地址对应的物理地址。
段号
段内位移
0
430
1
10
2
500
3
400
4
112
5
32
图
2
答：<
/p>
（
1
）段号
0<
/p>
小于段表长
5
，故段号合法；由段表的第
0
项可获得段的内存始
址为
210
，段长为
500;
由于段内地址
430
，小于段长
500
，故段内地址也是合法
的，因此可得出对应的物理地址为
210+430=640
。
（
2
）段号
1
小于段表长
5
，故段号合法；由段表的第
1
项可获得段的内存始址
为
2350
，段长为
20;
由于段内地址
10
，小于段长
20
< br>，故段内地址也是合法的，
因此可得出对应的物理地址为
2350+10=2360
。
（
3
）段号
2
小于段
表长
5
，故段号合法；由段表的第
2<
/p>
项可获得段的内存始址
为
100
，段长为
90;
由于段内地址
< br>500
，超过段长
90
，故产生
越界中断。
（
5
）段号
5
等于段表长，故段号不合法，产生越界中断。
7
．在一采取局部置换策略的请求分
页系统中，分配给某个作业的内存块数是
4
，
< br>其中存放的四个页面的情况如表所示。
物理块
虚页号
装
入
时
最后一次访问时
访
< br>问
修
改
间
间
位
位
0
2
60
157
0
1
1
2
3
1
0
3
160
26
20
161
158
163
1
0
1
0
0
1
上面的所有数字均为十进制，
所有时间都是从进程开始运行时从
0
开始计
数的时
钟数。请问，如果系统采用下列置换算法，将选择哪一页进行换出
（
1
）
FIFO
算法；
（
2
）
LRU
算法；
（
3
）改进的
Clock
算法。
答：
（
1
）
FIFO
算法选择的换出页是物
理块
3
中的第
3
页。
（
2
）
LRU
算法选择的换出页是物理块
0
中的第
2
页。
（
3
）改进的
Clock
算法选择的换出页是物理块
2
中的第
0
页。
8.
在一个请求分页系统中，假如一个作业的页面走向为：
4
，
3
，
2<
/p>
，
1
，
4
，
3
，
5
，
4
，
3
，
2
，
1
，
5
，目前它还没有任何页装入内存，当分配给该作业的物
理块数目
M
分别为
3
< br>和
4
时，请分别计算采用
OPT
、
LRU
和
F
IFO
页面淘汰算法时访问过程
中所发生的缺页数和缺页率，并
比较所得的结果。
M=3
时，
OPT
算法
页面走向
4
3
2
1
4
3
5
4
3
2
1
5
以后最长时间不用
√
√√√
√
√√
2
1
1
1
5
4
4/3
3/2
1/2
3
3
3
4
3
3
5
4
4
4
4
3
4
4
3
5
5
5
9.
某页
式虚拟存储管理系统的物理空间共
3k
，页面大小为
1k
，一进程按下列地
址顺序引用内存单元：
3635
，
3632
，
1140
，
3584
，
2892
，
3640
，
0040
，
21
48
，
1700
，
2145
，
3290
，
0000
，
1102
，<
/p>
1100
。如果上述数字均为十进制数，而内存中尚未装
入任何页。给出使用
LRU
算法时的缺页率，并
与
FIFO
时的情况进行比较。
答：
（
1
）根据题
意，分配给作业的内存块数为
3
，而页面的引用次序为
3
、
3
、
1
、
3
、
< br>2
、
3
、
0
、
2
、
1
、
2
、
3
、
0
、
1
、
1
。因此，可以计算出，采用
LRU
算法时，缺
页次数为
8
，采用
FIFO
算法时，缺页次数为<
/p>
6
。
LRU
算法
用最近的过去来作为预
测最近的将来的依据，
一般认为其有较好
的性能，
但实现时，
要记录最近在内存
的每个页面的使用情况，比
FIFO
困难，其开销也大。有时，
因页面的过去和未
来的走向之间并无必然的联系，如上面，
LR
U
算法的性能就没想象中那么好。
第三章
作业
作业号
到达时间
运行时间
1.
假
设
有
四个作业
,
它们提交、
1
运
行
时
间
如
下
表
所
2
示。若采用
先
来
先
服
务、短作业
优先、响应
3
< br>
比
高
者
优
先
调
度
算
法，试问平
均
周
转
时
4
间
和
带
权
周
转
时
间
为
多
少
（时间单位：小时，
以十进制进行计算。
）
2.
假如
有四道作业，它们的提交时间及运行时间如下表所示。
作业号
到
达
时
运
行
时
开
始
时
完
成
时
周转时间
带
权
周
转
间（时）
间（时）
间（时）
间（时）
T
（时）
时间（时）
1
8:00
2
3
4
8:50
9:00
9:50
假设系统采用单道程序设计技术，
请给出系统在分别采用
FCFS
（先来先服务）
、
SJT
（短作业优先）和
H
RN
（响应比高者优先）作业调度算法时它们的调度作业
顺序、
作业的平均周转时间
T
和平均带权周转时间
W
，并相互比较之。
解：
（
1
）
FCFS
（
2
）
SJF
（
3
）响应比高者优先
第一个作业完成时间为，此时其它作业的响应比计算如下：
R2=+/=4
R3=+10-9)/=11
R4=+/=
根据响应比高者优先调
度原则，
应先运行作业
3
，
作业
3
完成时间为
,
此时作业
2
和作业
4
的响应比计算如下：
R2=+
根据响应比高者优先调度原则，应先运行作业
2
，作业
2
完成时间为
,
最后
运行作业
4
，作业<
/p>
4
完成时间为。
作业号
到达时间
运行时间
完成时间
周转时间
带
权
周
平
均
周<
/p>
平
均
带
权
转时间
转时间
周转时间
1
1
2
3
4
11
3.
假
设一个系统中有
5
个进程，
它们的到达
时间和服务时间如表所示，
忽略
I/O
以及其他开销时间，若分别按先来先服务
(FCFS)
、非抢占
及抢占的短进程优先
(SPF)
高响应比优先
< br>(HRRN)
、
时间片轮转
(R
R
，
时间片
=1)
调度算法进行
CPU
调度，
请给出
各进程的完成时间、
周转时间、
带权周转时间、
平均周转时间和平均带权
周转时间。
进程
到达时间
服务时间
A
B
C
D
E
解：
FCFS
进程
完
成<
/p>
时
间
周
转
时
间
带
权
周
转时间
SPF(
非
完
成
时
抢占
)
间
A
3
3
3
0
2
4
6
8
B
9
7
9
C
13
9
15
3
6
4
5
2
D
18
12
20
E
20
12
11
平均
汉英字典-铜皮
汉英字典-铜皮
汉英字典-铜皮
汉英字典-铜皮
汉英字典-铜皮
汉英字典-铜皮
汉英字典-铜皮
汉英字典-铜皮
-
上一篇：第10章所有者权益习题及答案
下一篇：小学绩效考核方案