第一题

  1. 分析磁盘访问数据的时间。假设磁盘请求以柱面 10、35、20、70、2、3 和 38 的次序进入磁盘驱动器。寻道时磁头每移动一个柱面需要5ms，以下各算法所需的寻道时间是多少：

（1） 先来先服务

（2） 最短寻道时间优先

（3） SCAN 算法

（4） LOOK 算法

说明：假设以上三种情况磁头初始位置为 15。对于（3）和（4），磁头当前向大柱面号方向运行，磁盘最大柱面号为 85。

（1）磁头移动的次序：

15 -> 10 -> 35 -> 20 -> 70 -> 2 -> 3 -> 38

寻道时间：$(5 + 25 + 15 + 50 + 68 + 1 + 35)*5=995$

（2）磁头移动的次序：

15 -> 10 -> 3 -> 2 -> 20 -> 35 -> 38 -> 70

寻道时间：$(5+7+1+18+15+3+32)*5=405$

15 -> 20 -> 10 -> 3 -> 2 -> 35 -> 38 -> 70

寻道时间：$(5+10+7+1+33+3+32)*5=455$

（3）磁头移动的次序：

15 -> 20 -> 35 -> 38 -> 70 -> 85 -> 10 -> 3 -> 2

寻道时间：$(5+15+3+32+15+75+7+1)*5=765$

（4）磁头移动的次序：

15 -> 20 -> 35 -> 38 -> 70 -> 10 -> 3 -> 2

寻到时间：$(5+15+3+32+60+7+1)*5=615$

第二题

2. 在 I/O 系统中引入缓冲区的主要目标是什么？某文件占 8 个磁盘块，现要把该文件的磁盘块逐个读入主存缓冲区，并送用户区进行分析。一个缓冲区与磁盘块大小相等。把一个磁盘块读入缓冲区的时间为100μs，缓冲区数据传送到用户区的时间是 50μs，CPU 对一块数据进行分析的时间为 50μs。分别计算在单缓冲区和双缓冲区结构下，分析完该文件的时间是多少？

主要目标：提高外设利用率

  • 匹配CPU与外设的不同处理速度。
  • 减少对CPU的中断次数。
  • 提高CPU和I/O设备之间的并行性。

单缓冲区：$(100 + 50) * 8 + 50 = 1250us$

双缓冲区：$100*8+100 = 900us$

第三题

3. 请结合操作系统课所学习的内容总结从哪些方面可以提高文件系统的性能。

  • 硬件：使用读写更快的外设，处理器以及总线，增加内存的容量
  • 磁盘碎片整理：将磁盘上的碎片重新整理为连续的空间，提高文件的读写速度
  • 块高速缓存：在内存中为磁盘块设置的一个缓冲区，保存了磁盘中某些块的副本，读取磁盘时，先读取缓冲区存在
  • RAID技术：使用多个物理盘，进行并行交叉存取
  • 提前读取：预测

第四题

4. 简述文件控制块（FCB-File Control Block）中所管理的主要信息。

  • 基本信息

    • 文件名：字符串，通常在不同系统中允许不同的最大长度（可修改）
    • 物理位置
    • 文件逻辑结构：有/无结构（记录文件，流式文件）
    • 文件物理结构：（如顺序，索引等）

  • 访问控制信息

    • 文件所有者（属主）
    • 访问权限（控制各用户可使用的访问方式）：如读、写、执行、删除等；

  • 使用信息

    • 创建时间，上一次修改时间，当前使用信息等。

第五题

5. 在文件系统中，访问一个文件 f 时首先需要从目录中找到与 f 对应的目录项。假设磁盘物理块的大小为 1KB，一个目录项的大小为 128字节，文件的平均大小为 100KB。该文件系统的目录结构如下图所示。假定不考虑磁盘块的提前读和缓存等加速磁盘访问技术。请回答以下问题：

image-20240524225217835

（1） 按照当前的目录结构，且采用串联文件方式对数据块进行组织，并且根目录的目录项已读入内存中。如果目标文件 f 在第三级目录下，且其对应的第三级目录的目录项可以一次从磁盘读出，访问文件 f 中的一个块平均需要访问几次磁盘？

（2） 如果采用 i 节点的方法来构建文件目录，假定文件名占 14 个字节，i 节点的指针占 2 个字节。如果仅采用直接索引，每个第三级目录下的文件数不超过 50 个，且根目录的 i 节点已读入内存，访问第三级目录下的一个文件的一个块平均需要访问几次磁盘？

（3） 假设该文件系统的空间最大容量为 16ZB(1ZB=270B)。如果文件的FCB 中包括 512 字节的索引区，且允许采用一级索引进行组织，那么该文件系统支持的最大文件是多少字节？

(1) 由图中可知，第三级目录位于/usr2下面。

  1. 根目录的目录项已在内存，因此可以直接读取到对应usr2的目录项，进而需要访问磁盘读取usr2目录的内容（即对应d0-d127 的目录项）。一个磁盘块可以放$2^{10}/2^7 =8$ 个目录项，所以读取全部d0-d127的目录项需要访问128/8=16次磁盘，平均需要访问(1+16)/2=8.5次磁盘。

  2. 进一步，需要读取第三级目录的内容（即对应目标文件f的目录项），因为题目要求：“第三级目录的目录项可以一次从磁盘读出”，因此1次从磁盘中读出对应f的目录项。

  3. 文件占用的磁盘块数为:$100/1=100$块，按照串联方式进行组织，访问一个块平均需要访问磁盘$(1+100)/2=50.5$次。(注：题中未给出指针大小，可忽略)

综上，访问第三级目录下一个文件的一个块平均需要访问磁盘8.5+1+50.5=60次。

(2) 一个目录项占16个字节，因此一个磁盘块可以放$2^{10}/2^4 =2^6 =64$个目录项。

  1. 读取根目录的内容需读取 1 次磁盘：根目录 inode 已在内存中，根目录下只有 3个目录项，可以 1 次读取。

  2. 读取 usr2 的 inode 需读取 1 次磁盘：从对应 usr2 的目录项中可获得 usr2 的 inode 号，进而通过读取磁盘可获得 usr2 的 inode。

  3. 读取 usr2 目录的内容（即对应 d0-d127 的目录项）需读取 1.5 次磁盘：读取整个第三级目录所对应的目录项需要访问磁盘 $128/64=2$ 次,因此平均需要读取$(1+2)/2=1.5$ 次。

  4. 读取第三级目录的 inode 需读取 1 次磁盘。

  5. 读取第三级目录的内容需读取 1 次磁盘：由于第三级目录下的文件不超过 50 个，因此读取 1 次磁盘即可将对应全部文件的目录项读出。

  6. 读取文件的 inode 需要读取 1 次磁盘。

  7. 读取文件的 1 个块需要读取 1 次磁盘：由于采用直接索引，故根据 inode 可直接读取磁盘上文件的一个块。

综上，访问第三级目录下一个文件的一个块平均需要 1+1.5+1+1+1+1=7.5 次磁盘。

(3) 文件系统管理的数据块数为$162^{70}/2^{10}=2^{64}$，为表示这些磁盘块，需要$64/8=8$个字节，因此索引区可存放$512/8=64$个磁盘块号。因此，在采用一级索引的情况下，支持的最大文件为$642^{10}/8*2^{10}B=8MB$。