浙大远程操作系统原理离线作业及答案

Request1(0,4,2,0) <= available(1,5,2,0) 新的状态为

Allocation Max Need Available P0 0 0 1 2 0 0 1 2 0 0 0 0 1 1 0 0 P1 1 4 2 0 1 7 5 0 0 3 3 0 P2 1 3 5 4 2 3 5 6 1 0 0 2 P3 0 6 3 2 0 6 5 2 0 0 2 0 P4 0 0 1 4 0 6 5 6 0 6 4 2

该状态是安全的，存在安全序列如，所以可以分配资源给P1。

8.3某系统有五个固定分区，其长度依次为100K, 500K, 200K, 300K, 600K。今有四个进程，对内存的需求分别是212K, 417K, 112K,

426K。当分别用First-fit, Best-fit, Worst-fit算法响应这四个进程的内存申请时，请分别给出系统的内存分配动态。哪种算法最有效？

答：根据First-fit、Best-fit、Worst-fit算法，计算结果如下： First-fit:

212K进程装到500K分区 417K进程装到600K分区 112K进程装到200K分区 426K进程暂时等待 Best-fit:

212K进程装到300K分区 417K进程装到500K分区 112K进程装到200K分区 426K进程装到600K分区 Worst-fit:

212K进程装到600K分区 417K进程装到500K分区 112K进程装到300K分区 426K进程暂时等待

8.5 对下列问题，试比较连续内存分配方案、纯段式分配方案、纯页式分配方案中的内存组织方法：

a. 外部碎片 b. 内部碎片 c. 共享跨进程代码的能力

答：连续内存分配会产生外部碎片，因为地址空间是被连续分配的，当旧进程结束，新进程

初始化的时候，洞会扩大。连续内存分配也不允许进程共享代码，因为一个进程的虚拟 内存段是不被允许闯入不连续的段的。纯段式分配也会产生外部碎片，因为在物理内存 中，一个进程的段是被连续放置的，以及当死进程的段被新进程的段所替代时，碎片也 将会产生。然而，段式分配可以使进程共享代码；比如，两个不同的进程可以共享一个 代码段，但是有不同的数据段。纯页式分配不会产生外部碎片，但会产生内部碎片。进 程可以在页granularity中被分配，以及如果一页没有被完全利用，它就会产生内部碎片 并且会产生一个相当的空间浪费。在页granularity，页式分配也允许进程共享代码。 8.9考虑一个分页式存储管理系统，其页表常驻内存。

（1）如果内存访问耗时200 ns，那么，访问内存中的数据需要多长时间？

（2）如果引入联想寄存器，而且75%的页面可以从关联寄存器中找到，那么，此时的有效访问时间为多少？(假设访问关联寄存器的时间可以忽略)

答：（1）400纳秒，其中，200纳秒访问页表，200纳秒访问内存中的数据。

（2）有效访问时间 = 0.75 * (200纳秒访问内存数据+0纳秒访问关联寄存器) + 0.25 * (200纳秒访问内存数据+200纳秒访问页表) = 250纳秒 8.12假设有下列段表：

段 基地址 段长度 0 219 600 1 2300 14

2 90 100 3 1327 580 4 1952 96

下列逻辑地址对应的物理地址是什么？

（1） 0,430 （2）1,10 （3）2,500 （4）3,400 （5）4,112 答：（1）219 + 430 = 649 （2）2300 + 10 = 2310

（3） 第2段的有效长度是100。段内偏移量500超过了这个上限，所以这是个非法地址

（4） 1327 00 = 1727 （5）第4段的有效长度是96。段内偏移量112超过了这个上限，所以这是个非法地址

9.5假设一个“按需调页”虚拟存储空间，页表由寄存器保存。在存在空闲页帧的条件下，处理一次缺页的时间是8毫秒。如果没有

空闲页面，但待换出页面并未更改，处理一次缺页的时间也是8毫秒。如果待换出页面已被更改，则需要20毫秒。访问一次内存的时间是100纳秒。假设70％的待换出页面已被更改，请问缺页率不超过多少，才能保证有效访问时间小于或等于200纳秒？ 答：设缺页率为P。题目并没有明确，当缺页中断时，内存中是否有空闲页帧，所以假设内存总是忙的。

访问内存中页面：(1 - P) * 100ns

页面不在内存，但不需要保存待换出页面：P * (1 – 70%) * (8ms+100ns) 页面不在内存，但需要保存待换出页面：P * 70% * (20ms+100ns)

所以，有效访问时间=(1 - P) * 100ns + P * (1 – 70%) * (8ms+100ns) + P * 70% * (20ms+100ns) = 200ns P = 0.000006

9.10对一个请求调页系统测得如下数据：

? ? ?

CPU利用率20%

用作页面交换的磁盘的利用率97.7% 其它I/O设备利用率5%

下列措施中，哪些会改善CPU利用率（如果有的话），请说明理由：

(1) 安装一个更快的CPU

(2) 安装一个更大容量的磁盘用作页面交换 (3) 增加并发进程数 (4) 减少并发进程数 (5) 安装更多内存

(6) 安装更快的硬盘，或安装更多的硬盘和控制器 (7) 增加一个预取页面算法 (8) 增加页面长度

答：a.首先判断系统正在频繁地进行换页操作。所以，减少并发进程数会显著地减少换页操作，提高CPU的利用率。其它措施也有些效果，例如，安装更多内存。

b.安装一个更快的CPU。没用。

c.安装一个更大容量的磁盘用作页面交换。没用，交换空间本来就足够了。 d.增加并发进程数。没用，情况将会更糟。 e.减少并发进程数。效果明显。

f.安装更多内存。可能会有效果，因为空闲页帧增加了，换页的几率将相对减少。 g.安装更快的硬盘，或安装更多的硬盘和控制器。效果不明显。 h.增加一个预取页面算法。效果不确定。

i.增加页面长度。如果顺序访问居多，则会减少缺页次数。如果随机访问居多，因为单

个页面占用更大的物理空间，页帧总数减少，所以缺页次数会增加；因为页面长度增加，页面的传输时间会增加。综上，此方案的效果不确定。

9.14一页式虚拟存储系统，用于页面交换的磁盘的平均访问、传输时间是20毫秒。页表保存在主存，访问时间1微秒。也就是说，

每引用一次指令或数据，需要访问两次内存。为改善性能，我们可以增设一个关联寄存器。如果页表项在关联寄存器里，则只要访问一次内存就够了。假设80％的访问，其页表项在关联寄存器中；剩下的20％里，10％的访问（即总数的2％）会产生缺页。请计算有效访问时间。

答：有效访问时间 = 80% * 1微秒 + (1-80%)((1-10%) * 1微秒 * 2 + 10% * (1微秒 * 2 + 20毫秒))= 0.8+0.2 * (0.9 * 2+0.1*20002)

= 0.8+0.2 * 2002 = 401.2微秒

9.01在某请求分页管理系统中，一个作业共5页，作业执行时依次访问如下页面：1，4，3，1，2，5，1，4，2，1，4，5，若分配给

该作业的主存块数为3，分别采用FIFO、LRU，试求出缺页中断的次数及缺页率。(要求画出页面置换情况表) 答：(1)采用FIFO页面置换算法，其缺页情况如表所示：

FIFO页面置换算法的缺页情况

页面走向 块1 块2 块3 1 1 4 √ 1 4 3 √ 2 4 3 √ 2 5 3 √ 2 5 1 √ 4 5 1 √ 4 2 1 √ 4 2 5 √ 1 4 3 1 2 5 1 4 2 1 4 5 缺页 √ 缺页中断次数为9，缺页率为9/12=75%。

(2)采用LRU页面置换算法，其缺页情况如表所示。

LRU页面置换算法的缺页情况 页面走向 块1 块2 块3 1 1 4 √ 1 4 3 √ 1 2 3 1 2 5 1 4 5 √ 1 4 2 √ 1 4 5 √ 1 4 3 1 2 5 1 4 2 1 4 5 缺页 √ √ √ 缺页中断次数为8，缺页率为8/12=67%。

10.1 假设有一个文件系统，它里面的文件被删除后，当连接到该文件的链接依然存在时，文件的磁盘空间会再度被利用。如果一个新的文件被创建在同一个存储区域或具有同样的绝对路径名，这会产生什么问题？如何才能避免这些问题？

答：假设F1是旧的文件，F2是新的文件。当一个用户通过已存在的链接访问F1，实际却是访问F2。这里使用的是对文件F1的存取保护而不是与文件F2相关的存储保护。

采用删除指向一个已删除文件的所有链接的方法避免该问题。可以通过几种方法实现： 1．设置一个记录指向一个文件的所有链接的链表，当这个文件被删除时，删掉这些链接。 2．保留这些链接，当试图访问一个已被删除的文件时，删掉这些链接。

3．设置一个文件的指针链表（或计数器），当指向该文件的所有指针被删除时才真正删除这个文件。

10.9 有些系统文件提供文件共享时候只保留文件的一个拷贝，而另外的一个系统则是保留多个拷贝，对共享文件的每一个用户提供一个拷贝，论述这种方法的相对优点。

答：在一个单一的复制，同时更新了一个文件可能会导致用户获得不正确的信息，文件被留在了不正确的状态. 随着多份拷贝，它会浪费存储而且各种副本可能不一致

11.6假设一个在磁盘上的文件系统，其中逻辑块和物理块大小为512字节。假定每个文件的信息已经在内存中，对于三种分配策略中的每一种（连续、链接、索引），请回答下面这些问题。

（1）说明在这个系统中是如何实现从逻辑地址到物理地址映射的？（对于索引分配，假设文件的长度总是小于512块）。 （2）如果当前位于逻辑块10（即最后一次访问的逻辑块是10），且希望访问逻辑块4，必须从磁盘上读多少个物理块？ 答：令Z是开始逻辑地址（块号）。

a. 若使用连续分配策略时。用512去除逻辑地址，则X和Y分别表示得到的整数和余数。

（1）将X加上Z得到物理块号，Y为块内的位移 （2）1

b. 若使用链接分配策略。用511去除逻辑地址，则X和Y分别表示得到的整数和余数。

（1）查找链表到第X+1块，Y+1位该块内的位移量 （2）4

c. 若使用索引分配策略。用512去除逻辑地址，则X和Y分别表示得到的整数和余数。

（1）把索引块读入内存中，则物理块地址存放在索引块在第X位置中，Y为块内的位移量 （2）2

11.01 考虑一个含有100块的文件。假如文件控制块（和索引块,当用索引分配时）已经在内存中。当使用连续、链接、单级索引分配策略时，各需要多少次磁盘I/O操作？假设在连续分配时，在开始部分没有扩张的空间，但在结尾部分有扩张空间，并且假设被增加块的信息已在内存中： （1）在开始增加一块。 （2）在中间增加一块。 （3）在末端增加一块。

（4）在开始删除一块。 （5）在中间删除一块。 （6）在末端删除一块。

答：各种策略相应的磁盘I/O操作次数如表 连续 链接 索引 a. 201 1 1 b. 101 52 1 c. 1 3 1 d. 198 1 0 e. 98 52 0 f. 0 100 0

11.02有一磁盘组共有10个盘面，每个盘面上有100个磁道，每个磁道有16个扇区。假设分配以扇区为单位。 （1） 若使用位示图管理磁盘空间，问位示图需要占用多少空间？

（2） 若空白文件目录的每个表目占用5个字节，问什么时候空白文件目录大于位示图？

答：空白文件目录是管理磁盘空间的一种方法，该方法将文件存储设备上的每个连续空闲区看作一个空白文件，系统为所有空白文件单独建立一个目录，每个空白文件在这个目录中占一个表项；表项的内容至少包括第一个空白块的地址（物理块号）、空白块的数目。 （1）由题设所给条件可知，磁盘组扇区总数为16*100* 10=16000（个）

因此，使用位示图描述扇区状态需要的位数为16000（位）/8(位/字节）=2000（字节） （2)已知空白文件目录的每个表项占5个字节．而位示图需占2000字节．即2000字节 可存放的表项数为2000/5=400（个）．

当空白区数目大于400时，空白文件目录大于位示图。

12.2 假设一个磁盘驱动器有5000个柱面，从0到4999，驱动器正在为柱面143的一个请求提供服务，且前面的一个服务请求是在柱面125。按FIFO顺序，即将到来的请求队列是 86，1470，913，1774，948，1509，1022，1750，130

从现在磁头位置开始，按照下面的磁盘调度算法，要满足队列中即将到来的请求要求磁头总的移动距离（按柱面数计）是多少？ a. FCFS b. SSTF c. SCAN d. LOOK e. C-SCAN

答：a. FCFS的调度是143 ， 86 ， 1470 ， 913 ， 1774 ， 948 ， 1509 ， 1022 ， 1750 ， 130 。总寻求距离是7081 。

b. SSTF的调度是143 ， 130 ， 86 ， 913 ， 948 ， 1022， 1470， 1509， 1750， 1774。总寻求距离是1745。 c. SCAN的调度是143 ， 913 ， 948 ， 1022， 1470， 1509， 1750， 1774 ， 4999 ， 130 ， 86 。总寻求距离是9769 。 d. LOOK的调度是143 ， 913 ， 948 ， 1022， 1470， 1509， 1750， 1774， 130 ， 86 。总寻求距离是3319 。 e. C-SCAN的调度是143 ， 913 ， 948 ， 1022 ， 1470 ， 1509 ， 1750 ， 1774 ， 4999 ， 86 ， 130 。总寻求距离是9985 。

f. C-LOOK的调度是143 ， 913 ， 948 ， 1022 ， 1470 ， 1509 ， 1750 ， 1774 ， 86 ， 130 。总寻求距离是3363 。 12.14 MTBF（平均无故障时间）是硬盘可靠性的一个指标。虽然这个指标被称作“时间”，但实际上MTBF通常是以设备的正常工作

小时数度量的。

(1) 如果一个系统包含1000个磁盘驱动器，每个驱动器的MTBF是750000小时，下面的描述中哪一个最符合该系统发生一次磁

盘故障的时间：每1000年，每世纪，每十年，每个月，每个星期，每天，每小时，每分钟，每秒钟？

(2) 统计表明，一个20到21岁的美国公民平均死亡率为千分之一，由此推论20岁的MTBF时间（单位由小时转换为年），对于

一个20岁的人来说，MTBF给出期望的寿命是多大？

(3) 某类磁盘驱动器，生产商保证的MTBF为1百万小时 你能推算出它们的保质期是多少年吗？

答：

(1) 750000 / 1000=750(小时) 约等于31天，每个月发生一次磁盘故障。

(2) 1年是8760小时，8760小时 / 0.001 ＝ 8760000小时（1000年）也就是说对于一个20岁的人来说，MTBF给出期望的寿命是

1000年，这没有任何实际意义。

(3) 从上一小题可看出，MTBF给出期望的寿命没有任何实际意义。一般来说，磁盘驱动器设计的寿命是5年，假如真的有一个MTBF

为1百万小时的磁盘，那么在其期望的寿命内是不可能有故障的。

12.01 假设计算机系统采用CSCAN（循环扫描）磁盘调度策略，使用2KB的内存空间记录16384个磁盘块的空闲状态。 （1） 请说明在上述条件下如何进行磁盘块空闲状态管理。

（2） 设某单面磁盘旋转速度为每分钟6000转。每个磁道有100个扇区，相邻磁道间的平均移动时间为1ms。若在某时刻，磁头位于

100号磁道处，并沿着磁道号增大的方向移动（如下图所示），磁道号请求队列为50、90、30、120，对请求队列中的每个磁道需读取1个随机分布的扇区，则读完这4个扇区总共需要多少时间？要求给出计算过程。

（3） 如果将磁盘替换为随机访问的Flash半导体存储器（如U盘、SSD等），是否有比CSACN更高效的磁盘调度策略？若有，给出

磁盘调度策略的名称并说明理由；若无，说明理由。

答：（1）用位图表示磁盘的空闲状态。每一位表示一个磁盘块的空闲状态，共需要16384/8=2048字节=2KB。系统提供的2KB内存能正好能表示16384个磁盘块。

（2）采用CSCAN调度算法，访问磁道的顺序为50、90、30、120，则磁头移动磁道长度为20+90+20+40=170，总的移动磁道时间为170×1ms=170ms。

由于转速为6000转/分，则平均旋转延迟为（60/6000）/2 s=5ms，要访问4个磁道，总的旋转延迟时间为=4×5ms=20ms。 由于转速为6000转/分，则读取一个磁道上的一个扇区的平均读取时间为（60/6000）/100 s =0.1ms，总的读取扇区的时间=4×0.1ms=0.4ms。

读取上述磁道上所有扇区所花的总时间=170ms+20ms+0.4ms=190.4 ms

（3）采用FCFS（先来先服务）调度策略更高效。因为Flash半导体存储器的物理结构不需要考虑寻道时间和旋转延迟，可直接按I/O请求的先后顺序服务。

13.3考虑单用户PC机上的下列I/O操作：

（1）图形用户界面下使用鼠标

（2）在多任务操作系统下的磁带驱动器（假设没有设备预分配） （3）包含用户文件的磁盘驱动器

（4）使用存储器映射I/O，直接和总线相连的图形卡

在操作系统中使用缓冲技术，假脱机技术，Cache技术，或者它们的组合来实现上述操作。实现时使用轮询I/O还是中断I/O？为什么？

答：（1）在鼠标移动时，如果有高优先级的操作产生，为了记录鼠标活动的情况，必须使用缓冲技术，另外，假脱机技术和Caching技术不是很必要，而应采用中断驱动I/O方式。

（2）由于磁带驱动器和目标或源I/O设备间的吞吐量不同，必须采用缓冲技术；为了能对储存在磁带上的数据进行快速访问，必须采用Caching技术；当有多个用户需要对磁带进行读或写的时候，假脱机技术也是必须采用的；为了取得最好的性能，应该采用中断驱动I/O方式。

（3）为了能使数据从用户作业空间传送到磁盘或从磁盘传送到用户作业空间，必须采用缓冲技术；同样道理，也必须采用Caching技术；由于磁盘是属于共享设备，故没必要采用假脱机技术；最好采用中断驱动I/O方式。

（4）为了便于多幅图形的存取及提高性能，缓冲技术是可以采用的，特别是在显示当前一幅图形时又要取得下一幅图形时，应采用双缓冲技术；基于存储器映射及直接和总线相连的图形卡是快速和共享设备，所以没必要采用假脱机技术和Caching技术；轮询I/O和中断I/O只对输入和I/O是否完成的检测有用，而对于采用存储器映射的设备不必用到上述两种I/O方式。 13.01驱动程序是什么？为什么要有设备驱动程序？用户进程怎样使用驱动程序？ 答：（1）用户进程与设备控制器之间的通信程序称为设备驱动程序。

（2）设备驱动程序是控制设备动作的核心模块，如设备的打开、关闭、读、写等，用来控制设备上数据的传输。它直接与硬件

密切相关，处理用户进程发出的I/O请求。

（3）用户进程使用设备驱动程序时，设备驱动程序的处理过程为：将用户进程抽象的I/O要求转换为具体的要求，检查I/O请求的合法性，读出和检查设备的状态，传送必要的参数，设置设备工作方式，启动I/O设备。