《操作系统精髓与设计原理·第五版》习题答案(10)

长度 长度 长度 长度 如果磁头沿着增大的方向，只有SCAN和C-SCAN的结果有变化 SCAN 下一个被访问的磁道 110 120 129 147 186 64 41 27 10 平均寻道长度 横跨的磁道数 10 10 9 18 39 122 23 14 17 29.1 C-SCAN 下一个被访问的磁道 110 120 129 147 186 10 27 41 64 平均寻道长度 横跨的磁道数 10 10 9 18 39 176 17 14 23 35.1 1.4考虑一个磁盘，有N个磁道，磁道号从0到(N-1)，并且假设请求的扇区随机地均匀分布在磁盘上。现

在要计算一次寻道平均跨越的磁道数。

a.首先，计算当磁头当前位于磁道t时，寻道长度为j的可能性。提示：这是一个关于确定所有组

合数目的问题，所有磁道位置作为寻道目标的可能性是相等的。

b.接下来计算寻道长度为K的可能性。提示：这包括所有移动了K个磁道的可能性之和。 c.使用下面计算期望值得公式，计算一次寻道平均跨越的磁道数目： N-1

E[X]=∑i∑Pr[x=i] i=0

d．说明档N比较大时，一次寻道平均跨越的磁道数接近N/3.

（a）设P[j/t]表示位于磁道t，寻道长度为j的概率，知随机访问一个任何一个磁道的可能性为相

等为1/N，因此我们有P[j/t]=1/N,t<=j-1或者t>=N-j;P[j/t]=2/N,j-1

（b）令P[k]=∑P[k/t]*P[t]=1/N∑P[k/t],由（a）可知，取值1/N的有2k个磁道，取值为2/N有

（N-k）个，

所以有

46

P[k]=（2k/N+2(N-k)/N）/N=2(N-k)/N*N

(c)E[k]=∑k*P[k]=∑2k(N-k)/N*N =(N*N-1)/3N

(d)当N比较大时，从上文可以看出一次寻道平均跨越磁道数接近N/3 11.5下面的公式适用于高速缓冲存储器和磁盘高速缓存： Ts=Tc+M×Td

请把这个公式推广到N级存储器结构，而不是仅仅2级。 定义：

Ai=从i级存储器找到信息的时间；

Hi=消息在第i级存储器并且没有在更高级存储器的概率； Bi=从第（i+1）级向第i级传送一块数据的时间。

假设缓存在1级存储上，主存在2级存储上，如此下去，形成一个N级存储结构，因此有 Ts=∑AiHi 若消息在M1层，可以立即被读，如果在M2中，不在M1中，那么这块数据从M2传到M1中再读。 因此 A2=B1+A1

进而有 A3=B2+A2=B1+B2+A1 即有 Ai=A1+∑Bj

所以 Ts=T1∑Hi+∑∑BjHi 因为 ∑Hi=1

最后可得 Ts=T1+∑∑BjHi

11.6对基于频率的替换算法（见图11.12），定义Fnew,Fmiddle和Fold分别为包含新区，中间区和的高

速缓存片段，显然Fnew+Fmiddle+Fold=1.如果有 a．Fold=1—Fnew

b. Fold=1/（高速缓存大小） 请分别描述该策略。

图11.11的中间区是空的，因此这种策略退化为图11.11a的策略。 老区由一块组成，并且我们有LRU替换策略。

11.7对于一个有9个磁道的磁带，磁带速度为120英寸每秒，磁带密度为1600线位/英寸，请问它的传送

率为多少？

密度可表示为1600线位每英寸，因此传送速率为1600×1200=192000线位每秒。

11.8假设有一个2400英寸的磁带盘，记录间的间隙为0.6英寸，这个间隙是磁带在读操作之间的停止；

在间隙期间磁带速度成线性增加或减小，磁带的其他与习题11.7相同。磁带上的数据按物理记录组织，每个物理记录包含固定数目的由用户定义的单元，称为逻辑记录。

a.在磁带上读取分装在10个物理记录中的120个逻辑记录需要多少时间？ b．同样。如果是分装在30个物理记录中，则需要多少时间？

c.对于上述每种分块方案，整个磁带分别可以保存多少个逻辑记录？ d．对于上述每种分块方案，有效的总传速率分别是多少？ e.磁带的容量是多少？

假设每个记录由30块组成。

b．我们先定义从一个物理块加间隙到了另一块的读取时间

物理块的大小=（30个逻辑记录每物理记录）×（120比特每逻辑记录）

=3600字节

物理块的长度=3600字节/（1600比特/英寸）=2.35英寸 间隙的长度=0.6英寸

传输一个块加间隙的传输时间=2.25/120+0.6/60=0.02875秒 磁带上块的数目=（2400×12）/（2.25+0.6）=10105物理块

47

因此，读取时间为 10105×0.02875=291秒

c.如果分装在30个物理记录中，磁带包含10105个物理记录和

30×10105=303150个逻辑记录。

d.分装在30个物理记录中的有效传输数率：

R=（303150×120）/291=125010字节/秒

e．容量=303150×120=36378000字节

11.9如果磁盘中扇区大小固定为每扇区为512字节，并且每磁道96个磁区，每面110个磁道，一共有8

个可用的面，对于习题11.8（b），计算存储这些逻辑记录需要多少磁盘空间（扇区、磁道和面）。忽略文件头记录和磁道索引，并假设记录不能跨越两个扇区。 每个扇区能容纳4个记录，所需扇区数=303150/4=75788 所需磁道数=75788/96=790 所需面数=790/110=8

11.10考虑习题11.9所描述的磁盘系统，假设该磁盘的旋转速度为360r/m。一个处理器使用中断驱动I/O

从磁盘中读取一个扇区，每个字节一个中断。如果处理每个中断需要2.5us，处理器花费在处理I/O上的时间占多少百分比（忽略寻道时间）？

每扇区512字节，每字节一个中断，所以每扇区512个中断。 中断总时间=2.5×512=1280us。

每个扇区读取时间=60s/m×360r/m×96扇区/磁道=1736us 处理器花费在处理I/O上的时间百分比=100×1280/1736=74％

11.11如果使用DMA策略并假设每个扇区一个中断，重做习题11.10。

使用DMA策略，中断总时间=2.5us

处理器花费在处理I/O上的时间百分比=100×2.5/1736=0.14％

11.12一个32位计算机有两个选择通道和一个多路通道，每个选择通道支持两个磁盘和两个磁带部件。多

路通道有两个行式打印机、两个卡片阅读机，并连接着10个VDT终端。假设有以下的传送率： 磁盘驱动器 800KB/s 磁带驱动器 200KB/s 行式打印机 6.6KB/s 卡片阅读机 1.2KB/s VDT 1KB/s

系统中的最大合计传送率为多少？

每次只有一个驱动设备能在选择通道上得到服务，

因此 ， 最大速率=800+800+2×6.6+2×1.2+10×1=1625.6KB/s

11.13当条带大小比I/O大小小时，磁盘条带化显然可以提高数据传送率。同样，相对于单个的大磁盘，

由于RAID 0可以并行处理多个I/O请求，显然它可以提高性能。但是，相对于后一种情况，磁盘条带化还有必要存在吗？也就是说，相对于没有条带化的磁盘阵列，磁盘条带化可以提高I/O请求速度的性能吗？

这取决于I/O请求类型。对于一种极端情况，如每次只有一个进程有一个大I/O请求时，磁盘条带化可以提高性能。但如果有许多进程有许多小的I/O请求时，相对于RADI 0没有条带化的磁盘阵列可以提高性能。

第12章 文件管理

12.1、定义：B=块大小 R=记录大小 P=块指针大小 F=组块因子，即一个块中期望的记录数。对图12.6中描述的三种组块方法分别给出关于F的公式。 答案：

固定组块： 最大整数

48

当一个可变长度记录被保存到组块中的时候，组块中会增加一个标记着记录边界的数据，用来标识记录。当跨越式记录桥联块边界的时候，需要用到一些关联着后继组块的结构。一种可能情况是在每个记录前加一个长度标识。另一种可能情况是在两个记录之间加一个特殊的区分标识。因此，我们假设每一个记录需要一个标识，并且标识大小约等于块指针大小。对于跨越式组块，指向它下一个组块的大小为P的块指针被包含在每一个组块中，所以跨越式记录可以很容易地被重定位。由此可知：

可变组块跨越式：

由于不采用跨越的方式，可变长度非跨越式组块会导致平均R/2的空间浪费，但不需要指向后继组块的指针：

12.2、一种避免预分配中的浪费和缺乏邻近性问题的方案是，分配区的大小随着文件的增长而增加。例如，开始时，分区的大小为一块，在以后每次分配时，分区的大小翻倍。考虑一个有n条记录的文件，组块因子为F，假设一个简单的一级索引用做一个文件分配表。

a.给出文件分配表中入口数的上限（用关于F和n的函数表示）。

b.在任何时候，已分配的文件空间中，未被使用的空间的最大量是多少？ 答案：a.

b.未被使用的空间总是小于已分配文件空间。 12.3、当数据

a.很少修改并且以随机顺序频繁地访问时， b.频繁地修改并且相对频繁地访问文件整体时， c.频繁地修改并以随机顺序频繁地访问时，

从访问速度、存储空间的使用和易于更新（添加／删除／修改）这几方面考虑，为了达到最大效率，你将选择哪种文件组织？ 答案：a.索引文件 b.索引顺序文件

c.索引文件或散列文件

12.4、目录可以当做一种只能通过受限方式访问的“特殊文件”实现，也可以当做普通文件实现。这两种方式分别有哪些优点和缺点？

答案：很明显地，如果操作系统把目录当做一种通过受限方式访问的“特殊文件”实现，安全性更容易被加强。把目录当做一种通过受限方式访问的普通文件实现使得操作系统更统一地管理对象，更容易地创建和管理用户目录。

12.5、一些操作系统具有一个树结构的文件系统，但是把树的深度限制到某个比较小的级数上。这种限制对用户有什么影响？它是如何简化文件系统的设计的（如果能简化）？

答案：这是一个少见的专题。如果操作系统构造一个文件系统以便子目录被允许包含在一个主目录底下，那么就很少或没有额外的逻辑被要求允许包含任意深度的子目录。限制子目录树的深度造成对用户组织文件空间不必要地限制。

12.6、考虑一个层次文件系统，空闲的磁盘空间保留在一个空闲空间表中。 a.假设指向空闲空间的指针丢失了。该系统可以重构空闲空间表吗？ b.给出一种方案，确保即使出现了一次存储失败，指针也不会丢失。

49

答案：a.可以重构。使用的方法与许多LISP的垃圾收集系统用的方法非常相似。首先，我们将建立一种数据结构，代表磁盘的每一块，并且这个磁盘支持一种文件系统。在这里某种映射是比较合适的。然后，我们从这个文件系统的根目录开始，通过文件系统的递归下降寻找，我们标记每一块已被文件使用的磁盘块。当完成的时候，我们将为没有被使用的磁盘块建立一个空闲列表。这实质上就是UNIX命令fsck的功能。

b.在磁盘上一个或多个地方备份空闲空间列表指针。无论何时列表的开端发生变化，备份指针也同样更新。这样将会保证即使发生了存储器或者磁盘块错误，你也总是能找到一个有效的指针值。

12.7、考虑由一个索引节点所表示的UNIX文件的组织（见图12.13）.假设有12个直接块指针，在每个索引节点中有一个一级、二级和三级间接指针。此外，假设系统块大小和磁盘扇面大小都是8K。如果磁盘块指针是32位，其中8位用于标识物理磁盘，24位用于标识物理块，那么 a.该系统支持的最大文件大小是多少？ b.该系统支持的最大文件系统分区是多少？ c.假设主存中除了文件索引节点外没有其他息，访问在位置12，423，956中的字节需要多少次磁盘访问？ 答案：a.找出每一个块中根据指针大小来划分块大小的磁盘块指针的数目： 8K/4 = 2K pointers per block I-Node所支持的最大文件大小是：

12 + 2K + (2K×2K) + (2K×2K×2K) 直接寻址 一级间接寻址 二级间接寻址 三级间接寻址 12 + 2K + 4M + 8G blocks 将以上数据乘以块大小（8K），得到： 96KB+16MB+32GB+64TB

这就是该系统支持的最大文件大小。

b.每一个分区中都有24位用于识别物理块，由此可知：

24

2×8K = 16M×8K = 128GB

c.由问题（a）中所得的信息可知，直接块只覆盖了第一个96KB区域，而一级间接块覆盖了接下来的16MB区域。被请求文件的位置是13MB而其偏移很明显地随机落在了一级间接块中。因此会有2次磁盘存储访问。一次是为了一级间接块，一次是为了包含被请求数据的块。

第13章 网 络

13.1、a.假设法国和中国总理需要通过电话达成一项协定。但是他们都不会说对方的语言，而且身边也没有翻译能将对方的语言翻译过来。但是，他们的工作人员中都有英语翻译人员。请画出与图13.8类似的图来描述这种情况，并说明每一层之间的交互过程。 b.现在假设中国总理只有日语翻译人员，法国总理有德语翻译人员。在德国有德语和日语翻译人员。请画图来说明协定过程并描述电话交谈过程。 答案：

两个总理的讲话就好像他们在直接同对方讲话，例如：当法国总理讲话时，他定位他的话是直接对中国总理说的。尽管如此，事实上这些信息还是经由电话系统经过拉两个翻译。法国总理的翻译把他的话翻译程英文并告诉中国总理的翻译，中国总理的翻译收到后将之翻译成中文。

50

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库《操作系统精髓与设计原理·第五版》习题答案(10)在线全文阅读。