复习题_问答题部分New (2).doc

第二章
1、已知一个求值公式(3A+2B)/(A+5B2+C)，若A、B、C已赋值，试画出该公式求值过程的前趋图。
解：令 S1：X1 = 3A;
S2：X2 = 2B;
S3：X3 = X1+X2;
S4：X4 = 5B2;
S5：X5 = A+X4+C;
S6：X6 = X3/X5
则求值过程的前趋图为：

2、已知一个求值公式(B2+AB)/(5B+A)，若A、B已赋值，试画出该公式求值过程的前趋图。
解：令 S1：X1 = B2；
S2：X2 = AB；
S3：X3 = X1 + X2；
S4：X4 = 5B；
S5：X5 = X4 + A；
S6：X6 = X3 / X5。
则求值过程的前趋图为： (自己画出)
3、写出实现两个进程单向同步问题的伪码。（参考讲义）

3、写出通过信号量实现生产进程和消费进程（单缓冲区）双向同步的伪码。（参考讲义）
解：
定义信号量：
var s1,s2: semaphore :=1,0;
生产进程伪码：
Process P:
begin
while(true) do
begin
生产一个产品；
wait(s1); //P操作，等待可以生产的信号量
将产品放入缓冲区。。。。。。//其他操作
singal(s2); //V操作，发送可以消费的信号量
end
end
消费进程伪码：
Process C:
begin
while(true) do
begin
wait(s2); //P操作，等待可以消费的信号量
从缓冲区中取出产品进行消费。。。。。。//其他操作
singal(s1); //V操作，发送可以生产的信号量
end
end

4、写出通过信号量实现进程1和进程2互斥访问共享资源（临界资源）的伪码。（参考讲义）
解：定义信号量：
var s: semaphore :=1;
访问资源进程1伪码：
Process P1:
begin
while(true) do
begin
wait(s); //P操作，申请访问资源权限的的信号量
临界区代码; //其他访问资源操作
singal(s); //V操作，释放访问资源权限的信号量
end
end
访问资源进程2伪码：（同P1类似）
Process P2:
begin
while(true) do
begin
wait(s); //P操作，申请访问资源权限的的信号量
临界区代码; //其他访问资源操作
singal(s); //V操作，释放访问资源权限的信号量
end
end
5、写出具有缓冲池（n个缓冲区）的生产者-消费者问题的伪码。（参考讲义、教材）
6、写出公共汽车司机和售票员同步问题的伪码。（参考讲义）
解：信号量定义
var s1,s2:semaphore:=0,0;
//s1为控制能否行车的信号量
//s2为控制能否开门的信号量
司机进程：
Process Driver:
begin
while(true) do
begin
wait(s1);
加油行车；
到站停车；
singal(s2);
end
end
售票员进程：
Process Conductor:
begin
while(true) do
begin
关车门;
singal(s1);
售票；
wait(s2);
开车门；
end
end
7、读者-写者同步问题（参考讲义和教材）
第三章
1、系统有5个进程，其就绪时刻(指在该时刻已经在就绪队列中就绪)、服务时间如下表所示。当分别采用先来先服务(FCFS)和短进程优先(SPF)算法时，画出调度过程，并计算平均周转时间和平均带权周转时间。(参考P91-92)
进程
就绪时刻
服务时间
P1
0
2
P2
2
5
P3
4
3
P4
6
6
P5
8
1
解：（1） 采用FCFS算法时，调度过程如下表所示：
进程
就绪时刻
服务时间
开始执行时间
完成时间
周转时间
带权周转时间
P1
0
2
0
2
2
1
P2
2
5
2
7
5
1
P3
4
3
7
10
6
2
P4
6
6
10
16
10
5/3
P5
8
1
16
17
9
9
平均周转时间=
平均带权周转时间=

（2）采用最短进程优先算法时，调度过程如下表所示：
进程
就绪时刻
服务时间
开始执行时间
完成时间
周转时间
带权周转时间
P1
0
2
0
2
2
1
P2
2
5
2
7
5
1
P3
4
3
7
10
6
2
P4
6
6
11
17
11
11/6
P5
8
1
10
11
3
3
平均周转时间=
平均带权周转时间=

2、系统中有5个进程，每个进程的运行时间和到达时刻如下表所示。若采用时间片轮转调度算法(时间片为1)，画出进程执行过程，并计算平均周转时间和平均带权周转时间。(参考P95)
进程
到达时刻
运行时间
P1
0
5
P2
1
1
P3
2
2
P4
3
1
P5
4
3
解：进程执行过程如下：

平均周转时间：(11+1+6+2+8)/5 = 5.6
平均带权周转时间：(11/5+1/1+6/2+2/1+8/3)/5≈2.17

3、系统中有5个进程，每个进程的运行时间、优先级和到达时刻如下表所示。若采用抢占式优先级调度算法(优先级越大越优先执行)，画出进程执行过程，并计算平均周转时间和平均带权周转时间。
进程
到达时刻
运行时间
优先级
P1
0
5
4
P2
1
1
6
P3
2
2
2
P4
3
1
3
P5
4
3
5

4、假定系统中有三个进程P1、 P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，如下表所示：
进 程
最 大 需 求
已 分 配
P1
P2
P3
10
4
9
5
2
2
(1) 该状态是否是安全状态？请说明理由。
解：T0时刻，系统是处于安全状态，因为此时的空闲磁带机资源为3，存在一个安全序列<P2、P1、P3>，即只要系统按此进程序列分配磁带机资源，就能够使三个进程都顺利完成。（为什么？）
(2) 若到达一新进程P4，请求1台磁带机，其最大需求为4台，是否可以分配？请说明理由。(参考P108)
解：可以进行资源分配。因为将1台磁带机分配给P4后，尚有2台空闲磁带机，存在一个安全序列<P2、P4、P1、P3>，即只有系统按此进程序列分配磁带机资源，就能够使四个进程都顺利完成。（为什么？）

5、 设系统中有3种类型的资源(A，B，C)和5个进程P1、P2、P3、P4、P5，A资源的数量为17，B资源的数量为5，C资源的数量为20，在T0时刻系统状态如下表所示。系统采用银行家算法实施死锁避免策略。（参考P110）

进程
最大资源需求量
已分配资源数量
A
B
C
A
B
C
P1
5
5
9
2
1
2
P2
5
3
6
4
0
2
P3
4
0
11
4
0
5
P4
4
2
5
2
0
4
P5
4
2
4
3
1
4
剩余资源数
A
B
C
2
3
3
(1) T0时刻是否为安全状态？若是，请给出安全序列；
解：
进程
最大资源需求量
已分配资源数量
Need资源需求量
A
B
C
A
B
C
A
B
C
P1
5
5
9
2
1
2
3
4
8
P2
5
3
6
4
0
2
1
3
4
P3
4
0
11
4
0
5
0
0
6
P4
4
2
5
2
0
4
2
2
1
P5
4
2
4
3
1
4
1
1
0
剩余资源数
A
B
C
2
3
3
T0时刻是安全状态。
存在安全序列<P4、P2、P3、P5、P1>(为什么？能否找出其他安全序列？)
(2) 若在T0时刻进程P2请求资源(0, 3, 4)，是否能实施资源分配？为什么？
解：若在T0时刻进程P2请求资源(0, 3, 4)，不能实施资源分配。 因为请求资源数(0, 3, 4)≤可用资源数(2, 3, 3)不成立，没有足够资源。
(3) 在(1)的基础上，若进程P4请求资源(2, 0, 1)，是否能实施资源分配？为什么？
进程
最大资源需求量
已分配资源数量
Need资源需求量
A
B
C
A
B
C
A
B
C
P1
5
5
9
2
1
2
3
4
8
P2
5
3
6
4
0
2
1
3
4
P3
4
0
11
4
0
5
0
0
6
P4
4
2
5
4
0
5
0
2
0
P5
4
2
4
3
1
4
1
1
0
剩余资源数
A
B
C
0
3
2
解：可以实施分配，因为分配后有安全序列：<P4、P2、P3、P5、P1 >(为什么？能否找出其他安全序列？),即分配后的状态是安全的。

6、假定系统中有三个进程P1、 P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示： (参考教材P108)
进 程
最 大 需 求
已 分 配
可 用
P1
P2
P3
10
4
9
5
2
2
3
(1) T0时刻是否为安全状态？若是，请给出安全序列；
(2) 在T0时刻P3申请一台磁带机，请问能否实施资源分配，为什么？
解：参考教材
7、理解FCFS和SJF作业调度算法思想。

8、理解时间片轮转算法思想

9、通过上课所讲示例理解EDF（最早截止时间优先）算法和LLF(最低松弛度优先)算法思想。

第四章
1、某系统采用动态分区分配方式管理内存，内存空间为640KB，高端40KB用来存放操作系统。在内存分配时，系统优先使用空闲区低端的空间。对下列的请求序列：作业1申请130KB，作业2申请60KB，作业3申请100KB，作业2释放60KB，作业4申请200KB，作业3释放100KB，作业1释放130KB，作业5申请140KB，作业6申请60KB，作业7申请50KB，作业6释放60KB，请分别画图表示出使用首次适应算法和最佳适应算法进行内存分配和回收后，内存的实际使用情况。(参考教材和讲义)
解：参考教材、讲义和下题方法
2. 某操作系统采用分区存储管理技术。操作系统在低地址占用了100KB的空间，用户区主存从100KB处开始占用512KB。初始时，用户区全部为空闲，分配时截取空闲分区的低地址部分作为已分配区。在执行以下申请、释放操作序列后：请求300KB；请求100KB；释放300KB；请求150KB；请求50KB；请求90KB，进行以下回答：
(1) 分别采用首次适应算法和最佳适应算法时，主存的实际使用情况如何？分别画出主存分布图，并指出空闲分区的首地址和大小；
(2) 若随后又要请求80KB，针对上述两种情况产生什么后果？说明了什么问题？（参考教材和讲义）
(1) 采用首次适应算法时，主存分布图如下图

空闲区1：首地址390KB，大小10KB；
空闲区2：首地址500KB，大小112KB；
(2) 采用最佳适应算法时，主存分布图如下图

空闲区1：首地址340KB，大小60KB；
空闲区2：首地址550KB，大小62KB；
(3) 若随后又要请求分配80KB，首次适应算法可顺利分配，而最佳适应算法不能。说明首次适应算法可在高址端保留大分区。
3、某分页系统的逻辑地址为16位，其中高6位为页号，低10位为页内偏移量，则在这样的地址结构中：
(1) 一页有多少个字节？
(2) 逻辑地址可有多少页？
(3) 一个进程最大的逻辑地址空间是多少KB？（参考P130）
解：210 = 1024 因此一页有1024字节
26 = 64 因此逻辑地址可有64页
216 = 64KB 因此一个进程最大的逻辑地址空间是64KB

4、某系统采用页式存储管理策略，拥有逻辑空间32页，每页为2KB，拥有物理空间1MB。
(1)写出逻辑地址的格式。
解：11位页内地址，5位页号

(2)若不考虑访问权限等，进程的页表最多有多少项？每项至少有多少位？
解：因为有32个逻辑页面，所以页表有32项。因为有1M/2K= 2的9次方物理块，所以每个页表项至少有9位

(3)如果物理空间减少一半，页表结构应相应作怎样的改变？
解：32项，每项至少需要8位

5、对于如下表所示的段表，请将逻辑地址(0,137)，(1,4000)，(2,3600)，(5,230)转换成物理地址。（参考讲义）
段号
内存始址
段长
0
50K
10KB
1
60K
3KB
2
70K
5KB
3
120K
8KB
4
150K
4KB
解：(0,137)对应的物理地址为：
50K+137 = 50*1024+137 = 51337;
(1,4000)的段内偏移地址越界，是一个不合法逻辑地址；
(2,3600)对应的物理地址为：
70K+3600 = 75280
(5,230)的段号越界，是一个不合法逻辑地址。
6、在一个请求分页系统中，假如一个作业的页面走向为4，3，2，1，4，3，5，4，3，2，l，5，目前它还没有任何页装入内存，当分配给该作业的物理块数目M分别为3和4时，请分别计算采用OPT、LRU和FIFO页面淘汰算法时访问过程中所发生的缺页次数和缺页率，并比较所得的结果。
解：请参照讲义画出调页过程，
7、系统为某进程分配了三个物理块， 页面访问顺序为：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1，试问采用OPT、FIFO、LRU置换算法时会产生多少次缺页中断？(假定初始时所有页面均未装入内存；请画出置换过程)
解：参照讲义

8、在某个分页管理系统中，某一个进程有4个页面，被分别装入到主存的第3、4、6、8块中，假定页面和块大小均为1024字节，当进程在CPU上运行时，执行到一条传送指令：MOV 2100, 3100
请计算出MOV指令中两个操作数(逻辑地址)的物理地址。
解：2100 / 1024 = 2 第2页放在第6块中
2100 % 1024 = 52
6×1024 + 52 = 6196
因此第一个操作数的物理地址为6196。
3100 / 1024 = 3 第3页放在第8块中
3100 % 1024 =28
8×1024 + 28 = 8220
因此第二个操作数的物理地址为8220。

9、已知某分页系统，主存容量为64KB，页面大小为1KB。对于一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中。将十进制的逻辑地址1023、2500、3500、4500转换成物理地址。（参考讲义）
解：逻辑地址1023的页号和页内偏移地址分别为：
1023/1024 = 0, 1023%1024 = 1023
所以其的物理地址为：2*1024+1023 = 3041
逻辑地址2500的页号和页内偏移地址分别为：
2500/1024 = 2, 2500%1024 = 452
所以其的物理地址为：6*1024+452 = 6596
逻辑地址4500>4*1024-1，所以不是一个合法地址。

第五章
1、试说明spooling系统的组成和工作原理。（参考讲义和教材）
2、磁盘请求以15、32、25、5、60、10、48磁道的序列到达磁盘驱动器。寻道时移动一个磁道需要8ms，当分别采用FCFS算法、最短寻道时间优先算法、SCAN算法、CSCAN算法时，磁道的访问顺序是怎样的？平均寻道时间是多少？假设磁头的起始位置位于磁道18，朝大磁道号方向移动。（参考讲义）
解：采用FCFS算法，磁道的访问顺序如下：
从18号磁道开始
磁道访问顺序
移动距离（磁道数）
15
3
32
17
25
7
5
20
60
55
10
50
48
38
平均寻道时间为：(3+17+7+20+55+50+38)/7*8=？

采用最短寻道时间优先算法，磁道的访问顺序如下：
从18号磁道开始
磁道访问顺序
移动距离（磁道数）
15
3
10
5
5
5
25
10
32
7
48
12
60
12
平均寻道时间为：(3+5+5+10+7+12+12)/7*8=？

采用SCAN算法，磁道的访问顺序如下：
从18号磁道开始
磁道访问顺序
移动距离（磁道数）
25
7
32
7
48
12
60
12
15
45
10
5
5
5
平均寻道时间为：(7+7+12+12+45+5+)/7*8=？

采用CSCAN算法，磁道的访问顺序如下：
从18号磁道开始
磁道访问顺序
移动距离（磁道数）
25
7
32
7
48
12
60
12
5
55
10
5
15
5
平均寻道时间为：(7+7+12+12+55+5+)/7*8=？

3、磁盘请求以20、44、40、4、80、12、76磁道的序列到达磁盘驱动器。寻道时移动一个磁道需要3ms，当采用SCAN算法时，磁道的访问顺序是怎样的？平均寻道时间是多少？假设磁头的起始位置位于磁道40，磁头向小磁道方向移动。（参考讲义）
4、磁盘请求以20、44、40、4、80、12、76磁道的序列到达磁盘驱动器。寻道时移动一个磁道需要3ms，当采用CSCAN算法时，磁道的访问顺序是怎样的？平均寻道时间是多少？假设磁臂的起始位置位于磁道40，磁头向大磁道方向移动。（参考讲义）

5、假设磁盘访问序列：98，183，37，122，14，124，65，67
读写头起始位置：53
(1) 安排磁头服务序列
(2) 计算磁头移动总距离（道数）（参考讲义）

第六章
1、存放在某个磁盘上的文件系统采用混合索引分配方式，其FCB中共有13个地址项，第0~9个地址项为直接地址，第10个地址项为一次间接地址，第11个地址项为二次间接地址，第12个地址项为三次间接地址。如果每个盘块的大小为512字节，若盘块号需要用3个字节来描述，而每个盘块最多存放170个盘块地址，则该文件系统允许文件的最大长度是多少？（参考教材和下题）

2、有某操作系统对外存分配采用混合索引分配方式，在索引节点中包含文件的物理结构数组iaddr[13]，其中前10项iaddr[0]~iaddr[9]为直接地址，iaddr[10]为一次间接地址，iaddr[11]为二次间接地址，iaddr[12]为三次间接地址。如果系统的盘块大小是1KB，每个磁盘块要4个字节标识，请问该文件系统支持的单个文件的最大长度是多少？假设某文件的索引节点已在内存，但其他信息均在外存，为了访问该文件中字节偏移量为15000的内容，需要几次访问磁盘？(参考教材)
解：每个盘块可以存盘块号个数=1KB/4B=256个
直接地址可以表示10个盘块
一次间接地址可以表示256个盘块
二次间接地址可以表示256*256=64K个盘块
三次间接地址可以表示2563=16M个盘块
支持的文件最大长度=(10+256+64K+16M)*1KB=16843018KB≈16G
15000B / 1KB = 14
访问第14个盘块(从0开始编号)需要访问一次间接地址，因此需要访问2次磁盘

3、设某文件为隐式链接文件，由5个盘块组成，盘块号依次为50、121、75、80、63，每个盘块大小为512字节，用4个字节保存盘块号。若要存取文件的第1532逻辑字节处的信息，问要访问哪一个磁盘块？块内偏移量是多少？（参考教材）
解：每个盘块使用512-4=508个字节保存文件内容，
1532 / 508 = 3，
因此要访问第3个盘块，即80号盘块。
1532 % 508 = 8,即块内偏移量是8字节。

5、在某个文件系统中，每个盘块为512字节，文件控制块占64个字节，其中文件名占14个字节。如果索引节点编号占2个字节，对一个存放在磁盘上的512个目录项的目录，试比较引入索引结点前后，为找到其中一个文件的FCB，平均启动磁盘的次数。（教材P225）

4、理解FAT文件存储方式。