1、计算机学科专业基础综合计算机操作系统-13 及答案解析(总分：100.00，做题时间：90 分钟)一、综合应用题(总题数：24，分数：100.00)1.文件系统通常提供了 OPEN、CLOSE、READ、WRITE、CREATE、DELETE 等文件操作系统调用，但是在使用DELETE 系统调用时通常会返回“文件正在使用”的错误。如果用户需要这个 DELETE 操作不返回这样的错误(即只要这个文件存在就一定能删除的 DELETE 语义)，那么 DELETE 系统调用应该怎样实现? （分数：6.00）_2.假设一个文件系统使用索引结构(索引仅包含磁盘块号)组织文件内容块，每块的大小为 16KB，
2、磁盘空间为 1GB。现假设一个目录中包含 3 个文件，其大小分别为 10KB、1089KB、129MB，请问这些文件总共在磁盘中占用了多大的空间?(不计其目录项占用的空间) （分数：6.00）_3.一个磁盘系统中，最大的柱面号为 100，最小柱面号为 0。假设当前磁头位置的柱面号为 54，正在从小号柱面向大号柱面方向移动。现在请求队列中要求访问的柱面号顺序为 99，18，44，18，67，75。如果使用 SCAN 算法，服务的顺序为何?移动长度为何? （分数：4.00）_4.旋转型存储设备上信息的优化分布能减少若干输入/输出服务的总时间。例如，有 10 个记录A，B，J 存放在某磁盘的某一磁道
3、上，假定这个磁道划分成 10 个扇区，每个扇区存放一个记录，安排如下表 l 所示。现在要从该磁道上顺序地将 AJ 的 10 个记录读出，如果磁盘旋转一周需花费 20ms，处理程序每读出一个记录后花 4ms 进行处理。试问处理完 10 个记录的总时间是多少(从找到 A 记录开始计算)?为了缩短处理时间，应该进行分布优化，试问应如何安排这些记录?并计算优化后处理的总时间(从找到 A 记录开始计算)。 扇区 1 2 3 4 5 6 7 8 9 10 记录号 A B C D E F G H I J （分数：4.00）_5.为什么磁盘调度算法通常不考虑旋转延迟? （分数：4.00）_考虑一个树形层次结构
4、文件系统，空闲空间使用空闲空间列表表示。（分数：4.00）(1).如果因为计算机崩溃引起空闲空间信息丢失，此时应该怎么处理?（分数：2.00）_(2).设计一种空闲空间管理方法，保证在异常情况下丢失信息最少。（分数：2.00）_6.在 Windows 系统中，当用户双击 Windows Explorer 列出的一个文件时，系统会运行一个程序，并且将这个文件作为运行程序的参数。请给出操作系统可以知道运行哪个程序的两种(甚至两种以上)方法。 （分数：4.00）_7.许多操作系统都提供了一个系统调用将一个给定的文件换一个新名字(rename)。这个系统调用和以下的操作序列之间有什么差别? (1)将原
5、有文件复制为一个名字为新名字的文件； (2)将原来的文件删除。 （分数：4.00）_8.在许多系统中可以将文件的某一部分映射到内存。这样的系统必须对这个操作强加哪些限制?怎样才能实现这样的操作? （分数：4.00）_9.一个简单的操作系统仅仅支持单个的目录，但是允许任意数量的文件，文件名字也可以任意长。可以使用这个结构模拟一个层次的文件系统吗?怎样才能实现? （分数：4.00）_10.在 UNIX 和 Windows 系统中，可以使用一个特殊的系统调用实现随机访问，这个系统调用允许将“当前位置”移动到文件的任意位置。如果没有这个系统调用，你是否有另外的随机访问方法?你的方法有什么优缺点? （分
6、数：4.00）_11.文件的连续分配将导致磁盘碎片，请讨论顺序结构和索引结构文件中的存储碎片问题。 （分数：4.00）_12.磁盘块连续分配避免碎片的一种方法是在文件删除时使用紧致(compact)。因为所有文件都是连续的，因此拷贝文件时，读取源数据需要一个寻道和旋转延迟，紧接着进行全速传输，文件内容写回也需要相同的工作。假设平均寻道时间为 5ms，旋转延迟为 4ms，传输速率为 8MB/s，平均文件大小为 8KB，那么一次紧致需要多长时间?依照这样的速度，紧致 16GB 磁盘上的一半数据需要多长时间? （分数：4.00）_13.观察下图的索引结点结构形式，如果现在每个结点包含 10 个 4B
7、 直接地址，每个磁盘块大小为1024KB，那么支持的最大文件大小是多少? （分数：4.00）_14.两个计算机系的学生马丁和汤姆对索引结点展开了讨论。马丁坚持认为因为现在的内存这么大而且便宜，在打开文件的时候可以直接将文件控制块复制到内存的文件控制块表中，没有必要浪费 CPU 时间去搜索它是否已经打开。而汤姆并不这样认为。你认为谁是对的?为什么? （分数：4.00）_15.空闲磁盘空间可以使用一个空闲链表或者位映射来进行跟踪。磁盘地址需要 D 位表示，在一个有 B 块的磁盘中有 F 块是空闲的，请说明使用空闲链表占用空间少于位映射占用空间所必须满足的条件。如果 D是 16，那么应该有多大的空间
8、必须是空闲的? （分数：4.00）_空闲空间位映射在格式化后，开始时总是形如 1000 0000 0000 0000(第一块被“根”目录占用)。系统总是从最低数目的块开始搜索空闲块。这样在写文件 A(需要 6 块)后位映射类似于 1111 1110 0000。请写出下列操作过程中位映射的变化情况。（分数：4.00）(1).写文件 B，需要 5 块；（分数：1.00）_(2).删除文件 A；（分数：1.00）_(3).写文件 C，需要 8 块；（分数：1.00）_(4).删除文件 B。（分数：1.00）_16.有人建议将 UNIX 中每个文件的第一部分与 FCB 存放在磁盘的同一块中，请问这样做
9、有什么优缺点? （分数：4.00）_17.文件系统的性能取决于 cache 命中率。在满足请求时，如果块在 cache 中则需要 1ms，而磁盘读则需要 40ms。假设命中率为 h，请给出满足一个请求所需的平均时间。 （分数：4.00）_18.一个软盘有 40 个柱面，每个柱面移动的寻道时间为 6ms。如果不刻意地将文件块靠近分配，那么逻辑上连续的两块之间大致平均相隔 13 个柱面。如果操作系统采用合适的策略，逻辑连续的块之间可能只会间隔 2 个柱面。那么在两种情况下，读取 100 块的文件分别需要多长时间(旋转延迟 100ms，每块的传送时间为 25ms)? （分数：4.00）_19.一个个
10、人计算机销售商宣传自己的磁盘驱动器使用了电梯算法，而且将一个柱面内的多个请求按照扇区排序。结果某个测试机构对整个磁盘随机读取 10000 次进行测试，发现测试结果与 FCFS 算法的结果相同。请问这个销售商撒了什么谎? （分数：4.00）_20.下图是磁盘块大小与数据率和空间利用率之间的关系。假设一个磁盘平均寻道时间为 8ms，旋转速度为 1500rpm，每个磁道(track)262144B。在块大小为 1KB、2KB 和 4KB 的情况下，其空间利用率和数据率分别是多少?为什么? （分数：4.00）_21.某一文件系统使用了 2KB 磁盘块。系统中的中等文件大小为 1KB。如果真的每个文件刚
11、好 1KB 大小，那么系统空间利用率为多少?实际系统中的空间利用率应该高于这个数还是低于这个数?为什么? （分数：4.00）_22.假设当前时刻内存中只有“根”目录 FCB，没有其他路径信息，而且所有目录的大小刚好是一个磁盘块大小，那么打开一个文件/usr/ast/courses/os/handout.t 共需要多少次的磁盘操作? （分数：4.00）_计算机学科专业基础综合计算机操作系统-13 答案解析(总分：100.00，做题时间：90 分钟)一、综合应用题(总题数：24，分数：100.00)1.文件系统通常提供了 OPEN、CLOSE、READ、WRITE、CREATE、DELETE 等文
12、件操作系统调用，但是在使用DELETE 系统调用时通常会返回“文件正在使用”的错误。如果用户需要这个 DELETE 操作不返回这样的错误(即只要这个文件存在就一定能删除的 DELETE 语义)，那么 DELETE 系统调用应该怎样实现? （分数：6.00）_正确答案：()解析：这样的 DELETE 系统调用可以有两种实现方法： (1)如果没有用户打开这个文件则按照一般的方法进行处理。如果发现有用户已经打开了文件，则立即向DELETE 调用者返回成功信息。而对于已经打开文件的程序可以有两种实现方法：一种是在它们后续使用这个文件的系统调用中返回“文件已经删除”的错误；另一种是在这些进程的打开文件表
13、中置入“文件已删除”的标记，当所有用户进程均关闭了这个文件之后删除这个文件。 (2)如果没有用户打开这个文件则按照一般的方法进行处理。如果发现有用户已经打开了文件，则阻塞DELETE 的调用进程，等待所有打开待删除文件的用户进程均关闭了这个文件之后再删除这个文件，最后唤醒 DELETE 的调用进程继续执行。 解析 文件系统的实现(甚至操作系统的实现)是应用驱动的结果，没有一种语义是确定的，只是因为要保持一定的使用习惯(如题目中所给的错误就是一种约定)才采用目前的语义。但是如果特殊的应用要求特殊的接口，操作系统必须根据情况进行改进。 给出的解答方法实际上是异步和同步接口的问题。第 1 种方法采用
14、的是异步语义接口；第 2 种方法采用的是同步语义接口。绝大多数的 I/O 接口都可以归结为异步和同步两类，只是大多数程序员更多地习惯使用同步接口。2.假设一个文件系统使用索引结构(索引仅包含磁盘块号)组织文件内容块，每块的大小为 16KB，磁盘空间为 1GB。现假设一个目录中包含 3 个文件，其大小分别为 10KB、1089KB、129MB，请问这些文件总共在磁盘中占用了多大的空间?(不计其目录项占用的空间) （分数：6.00）_正确答案：()解析：使用如图所示的索引结构，那么，10KB 大小的文件占用一个数据块，占用磁盘空间为 16KB；1GB磁盘共有 1GB/16KB=65536 块，索引
15、块中每个索引项需要 16 位，因此一个索引块最多有 1KB 个索引项，最大索引 16MB。 那么，1089KB 大小的文件需要一个索引块和 69 个数据块，为 6916KB+16KB=1120KB；129MB 大小的文件需要 1 个一级索引块、9 个二级索引块和 8256 个数据块，为 132256KB。 3.一个磁盘系统中，最大的柱面号为 100，最小柱面号为 0。假设当前磁头位置的柱面号为 54，正在从小号柱面向大号柱面方向移动。现在请求队列中要求访问的柱面号顺序为 99，18，44，18，67，75。如果使用 SCAN 算法，服务的顺序为何?移动长度为何? （分数：4.00）_正确答案：
16、()解析：99，75，67，44，18，18。解析 这是磁盘调度算法中最常见的考查形式，应该属于比较容易的题目，但是有几个地方应该注意 SCAN 和 C-SCAN、LOOK 和 C-LOOK 以及 LOOK 和 SCAN 之间的区别。另外对于 SCAN 和 LOOK 算法而言，磁头的移动方向对服务次序的影响截然不同。最后对于所有算法而言，磁头的当前位置直接影响磁头的移动距离。4.旋转型存储设备上信息的优化分布能减少若干输入/输出服务的总时间。例如，有 10 个记录A，B，J 存放在某磁盘的某一磁道上，假定这个磁道划分成 10 个扇区，每个扇区存放一个记录，安排如下表 l 所示。现在要从该磁道上
17、顺序地将 AJ 的 10 个记录读出，如果磁盘旋转一周需花费 20ms，处理程序每读出一个记录后花 4ms 进行处理。试问处理完 10 个记录的总时间是多少(从找到 A 记录开始计算)?为了缩短处理时间，应该进行分布优化，试问应如何安排这些记录?并计算优化后处理的总时间(从找到 A 记录开始计算)。 扇区 1 2 3 4 5 6 7 8 9 10 记录号 A B C D E F G H I J （分数：4.00）_正确答案：()解析：根据磁盘旋转一周所花费的时间得知读取一个扇区所花的时间是 20(ms/周)10(扇区/周)=2(ms/扇区)。而处理扇区 1 的记录 A 需要 4ms，因此当处理
18、完这个扇区的数据之后，磁头已经转过了 2 个扇区，到达扇区 4，因此还需要等待磁头旋转到扇区 2(相隔 8 个扇区)。这样读取扇区 2 上记录 B 的旋转延迟为82=16(ms)，读取时间为 2ms，记录 B 的处理时间为 16+2+4=22(ms)。依次类推，B，C，J 记录的处理时间均为 22ms，因此总的处理时间为 6+922=204(ms)。 为了降低旋转延迟，应该采用如表的记录安排方式： 扇区 1 2 3 4 5 6 7 8 9 10 记录号 A H E B I F C J G D 此时因为不存在旋转延迟，因此总的处理时间为 10(2+4)=60(ms)。 解析 这是另一类考查磁盘调
19、度方法的题目，它主要通过对旋转延迟的理解来解答。问题的关键在于扇区数据的处理时间与旋转速度之间的差异，这个差异决定了扇区与记录之间的对应关系。题目中记录处理时间与扇区读取时间正好是倍数关系，因此 BJ 记录的旋转延迟都为 0，如果它们之间不是倍数关系，那么还应该计算旋转延迟。5.为什么磁盘调度算法通常不考虑旋转延迟? （分数：4.00）_正确答案：()解析：大多数磁盘并没有将旋转位置信息输出给主机，因此在大多数情况下操作系统在进行磁盘调度时无法得到旋转信息，也就无法在调度算法中考虑到它的影响。 即使是磁盘系统可以提供旋转位置信息，但是由于磁盘依然在旋转，因此这个信息到达主机时往往是不准确的，而
20、且处理时间往往是变化的，所以操作系统在进行调度时获得的旋转位置信息是不正确的。 另外，磁盘请求往往是以逻辑块的形式作为参数，而逻辑块与物理块之间的映射比较复杂，在调度算法中计算这种映射会大大增加调度开销。 总之，无论是从可行性上还是从性能上考虑，调度算法都不考虑磁盘的旋转位置。考虑一个树形层次结构文件系统，空闲空间使用空闲空间列表表示。（分数：4.00）(1).如果因为计算机崩溃引起空闲空间信息丢失，此时应该怎么处理?（分数：2.00）_正确答案：()解析：为了重构空闲空间列表，有必要实现一种“垃圾回收”机制。它需要搜索整个目录结构，以确定哪些磁盘块已经分配给了文件，然后将那些未分配的内存块登
21、记到空闲空间列表中。(2).设计一种空闲空间管理方法，保证在异常情况下丢失信息最少。（分数：2.00）_正确答案：()解析：为了保证信息尽量减少丢失，可以将它们在磁盘中存放多份。 注： 垃圾回收过程的性能受到文件控制块存储位置和结构、文件索引结构等方面的影响很大，空闲空间列表的重构性能低于位映射。当然采取的策略可以是先假设所有的空间均空闲，然后为空闲空间表建立Hash 表，当发现磁盘块已经分配时，将其从表中删除。此时，空闲空间列表更常见的形式是链接结构。在磁盘中存放多个空闲空间信息备份时，提高了操作系统的管理开销，因为每当发生磁盘块分配操作之后，便需要同时更新所有备份。6.在 Windows
22、系统中，当用户双击 Windows Explorer 列出的一个文件时，系统会运行一个程序，并且将这个文件作为运行程序的参数。请给出操作系统可以知道运行哪个程序的两种(甚至两种以上)方法。 （分数：4.00）_正确答案：()解析：基本思想是使用关联规则即使用某种特定规则将文件和处理程序关联起来。一种规则可以是文件名字的后缀；一种规则可以是特定文件的前缀；还可以使用通配符号等。7.许多操作系统都提供了一个系统调用将一个给定的文件换一个新名字(rename)。这个系统调用和以下的操作序列之间有什么差别? (1)将原有文件复制为一个名字为新名字的文件； (2)将原来的文件删除。 （分数：4.00）_
23、正确答案：()解析：两者之间的区别在于 rename 可以是一个原子操作。后者的操作序列可能引起错误，比如在(1)完成之后(2)开始之前，其他人可能将原有文件移动到其他位置。8.在许多系统中可以将文件的某一部分映射到内存。这样的系统必须对这个操作强加哪些限制?怎样才能实现这样的操作? （分数：4.00）_正确答案：()解析：内存映射(memory-mapped)文件概念。9.一个简单的操作系统仅仅支持单个的目录，但是允许任意数量的文件，文件名字也可以任意长。可以使用这个结构模拟一个层次的文件系统吗?怎样才能实现? （分数：4.00）_正确答案：()解析：可以。比如使用一些特定的文件名字，使用“
24、.”表示目录的结束，使用“/”作为文件的名字，/A/B/C 文件表示 A 目录下 B 子目录的 C 文件。10.在 UNIX 和 Windows 系统中，可以使用一个特殊的系统调用实现随机访问，这个系统调用允许将“当前位置”移动到文件的任意位置。如果没有这个系统调用，你是否有另外的随机访问方法?你的方法有什么优缺点? （分数：4.00）_正确答案：()解析：一种方法是使用 open/close/read 方法模拟，当文件指针向文件尾移动时，使用 read 移动文件指针。如果想移动文件头，则可以关闭文件后打开文件，再使用 read；另一种方法是将文件内容全部读入一个缓冲区中，使用内存指针移动模拟
25、文件指针移动。这两种方法均存在过度 I/O 的缺点。11.文件的连续分配将导致磁盘碎片，请讨论顺序结构和索引结构文件中的存储碎片问题。 （分数：4.00）_正确答案：()解析：顺序结构在文件内容发生移动时容易产生内部碎片；索引结构文件在索引小文件时容易产生索引块内部碎片(这也是 UNIX 使用特殊索引结构的主要原因)。12.磁盘块连续分配避免碎片的一种方法是在文件删除时使用紧致(compact)。因为所有文件都是连续的，因此拷贝文件时，读取源数据需要一个寻道和旋转延迟，紧接着进行全速传输，文件内容写回也需要相同的工作。假设平均寻道时间为 5ms，旋转延迟为 4ms，传输速率为 8MB/s，平均
26、文件大小为 8KB，那么一次紧致需要多长时间?依照这样的速度，紧致 16GB 磁盘上的一半数据需要多长时间? （分数：4.00）_正确答案：()解析：一次紧致大约 10ms 左右；紧致 8GB 数据，大约是 1M 个文件，因此大约需要 10000s 左右。13.观察下图的索引结点结构形式，如果现在每个结点包含 10 个 4B 直接地址，每个磁盘块大小为1024KB，那么支持的最大文件大小是多少? （分数：4.00）_正确答案：()解析：10 个直接地址则最大可容纳 10MB 数据，而一个间接地址可以容纳 1024MB 数据，因此最大文件大小为 1034MB。14.两个计算机系的学生马丁和汤姆对
27、索引结点展开了讨论。马丁坚持认为因为现在的内存这么大而且便宜，在打开文件的时候可以直接将文件控制块复制到内存的文件控制块表中，没有必要浪费 CPU 时间去搜索它是否已经打开。而汤姆并不这样认为。你认为谁是对的?为什么? （分数：4.00）_正确答案：()解析：马丁的方法在多个进程打开同一个文件时产生共享的问题，即，一个进程对文件内容的修改结果对其他进程不可见。15.空闲磁盘空间可以使用一个空闲链表或者位映射来进行跟踪。磁盘地址需要 D 位表示，在一个有 B 块的磁盘中有 F 块是空闲的，请说明使用空闲链表占用空间少于位映射占用空间所必须满足的条件。如果 D是 16，那么应该有多大的空间必须是空
28、闲的? （分数：4.00）_正确答案：()解析：空闲链表所需的空间为 FD 位，而位映射占用的空间为 B 位，因此使用空闲链表占用空间小于位映射的条件是：FDB。如果 D=16，则 FB/16，即有 6.25%的空闲。空闲空间位映射在格式化后，开始时总是形如 1000 0000 0000 0000(第一块被“根”目录占用)。系统总是从最低数目的块开始搜索空闲块。这样在写文件 A(需要 6 块)后位映射类似于 1111 1110 0000。请写出下列操作过程中位映射的变化情况。（分数：4.00）(1).写文件 B，需要 5 块；（分数：1.00）_正确答案：()解析：1111 1111 1111
29、 0000；(2).删除文件 A；（分数：1.00）_正确答案：()解析：1000 0001 1111 0000；(3).写文件 C，需要 8 块；（分数：1.00）_正确答案：()解析：1111 1111 1111 1100；(4).删除文件 B。（分数：1.00）_正确答案：()解析：1111 1110 0000 1100。16.有人建议将 UNIX 中每个文件的第一部分与 FCB 存放在磁盘的同一块中，请问这样做有什么优缺点? （分数：4.00）_正确答案：()解析：优点是可以在读取 FCB 时顺便读取文件的开始部分，大多数文件操作均是从头开始操作文件，因此可以减少文件 I/O 次数；缺
30、点是对于一些中型大小的文件增加了后续 I/O 的次数(寻找索引)。17.文件系统的性能取决于 cache 命中率。在满足请求时，如果块在 cache 中则需要 1ms，而磁盘读则需要 40ms。假设命中率为 h，请给出满足一个请求所需的平均时间。 （分数：4.00）_正确答案：()解析：h1+(1-h)40(ms)。18.一个软盘有 40 个柱面，每个柱面移动的寻道时间为 6ms。如果不刻意地将文件块靠近分配，那么逻辑上连续的两块之间大致平均相隔 13 个柱面。如果操作系统采用合适的策略，逻辑连续的块之间可能只会间隔 2 个柱面。那么在两种情况下，读取 100 块的文件分别需要多长时间(旋转延
31、迟 100ms，每块的传送时间为 25ms)? （分数：4.00）_正确答案：()解析：前一种情况所需时间为 99613+100(100+25)(ms)；后一种情况所需时间为9962+100(100+25)(ms)。19.一个个人计算机销售商宣传自己的磁盘驱动器使用了电梯算法，而且将一个柱面内的多个请求按照扇区排序。结果某个测试机构对整个磁盘随机读取 10000 次进行测试，发现测试结果与 FCFS 算法的结果相同。请问这个销售商撒了什么谎? （分数：4.00）_正确答案：()解析：磁盘调度算法是在操作系统中实现的，磁盘驱动器服务不应该实现特殊的调度方法，而只会使用FCFS 方法。20.下图是
32、磁盘块大小与数据率和空间利用率之间的关系。假设一个磁盘平均寻道时间为 8ms，旋转速度为 1500rpm，每个磁道(track)262144B。在块大小为 1KB、2KB 和 4KB 的情况下，其空间利用率和数据率分别是多少?为什么? （分数：4.00）_正确答案：()解析：(右侧的磁盘空间利用率的单位应该是 0.1%)，在块大小为 1KB、2KB、4KB 时的磁盘空间利用率依次为 100%、100%、50%；其数据率依次为 80KB/s、160KB/s、320KB/s 左右。至于空间利用率的降低是因为系统中文件大小是 2KB 左右。数据率逐步提高的原因是因为旋转速度为 1500rpm，即平均
33、的旋转延迟为40ms；每个磁道为 256KB，在块大小为 1KB、2KB 和 4KB 时分别可以存放 256 块、128 块、64 块，因为旋转延迟是寻道时间的 5 倍，因此磁道中存放的块越多，寻找一个块所需的时间也就越长，数据率也就越小。21.某一文件系统使用了 2KB 磁盘块。系统中的中等文件大小为 1KB。如果真的每个文件刚好 1KB 大小，那么系统空间利用率为多少?实际系统中的空间利用率应该高于这个数还是低于这个数?为什么? （分数：4.00）_正确答案：()解析：这种情况下空间利用率为 50%。实际情况下，特别是在 Windows 环境下，大多数文件大小远远高于2KB，因此空间利用率会高于这个数字。22.假设当前时刻内存中只有“根”目录 FCB，没有其他路径信息，而且所有目录的大小刚好是一个磁盘块大小，那么打开一个文件/usr/ast/courses/os/handout.t 共需要多少次的磁盘操作? （分数：4.00）_
