🏷️ 知识点：外存空间管理
某文件系统的簇和磁盘扇区大小分别为 1KB 和 512B。若一个文件的大小为 1026B，则系统分配给该文件的磁盘空间大小是（ ）。
A. 1026B B. 1536B C. 1538B D. 2048B
[tag_link]
正确答案：D
在文件系统中，磁盘空间以簇为单位分配，每个簇的大小为 1KB（1024B）。而磁盘扇区大小为 512B，但分配时只考虑簇的整数倍。
下列选项中，可用于文件系统管理空闲磁盘块的数据结构是（ ）。
Ⅰ. 位图
Ⅱ. 索引结点
Ⅲ. 空闲磁盘块链
Ⅳ. 文件分配表 (FAT)
A. 仅Ⅰ、Ⅱ B. 仅Ⅰ、Ⅲ、Ⅳ C. 仅Ⅰ、Ⅲ D. 仅Ⅱ、Ⅲ、Ⅳ
[tag_link]
正确答案：B
传统的文件系统 管理空间磁盘的方法 包括空闲表法、空闲链表法、位示图和成组链接法，Ⅰ、Ⅲ 正确。文件分配表（FAT）的表项与物理磁盘块一一对应，并且可以用一个特殊的数字 -1 表示文件的最后一块，用 -2 表示这个磁盘块是空闲的（当然，规定用 -3、-4 来表示也是可行的）。因此文件分配表（FAT）不仅记录了文件中各个块的先后链接关系，同时还标记了空闲的磁盘块，操作系统可以通过 FAT 对文件存储空间进行管理，Ⅳ正确。索引结点是操作系统为了实现文件名与文件信息分开而设计的数据结构，存储了文件描述信息，索引结点属于文件目录管理部分的内容，Ⅱ错误。
文件系统需要额外的外存空间记录空闲块的位置，占用外存空间大小与当前空闲块数量无关的是（）。
A. 位示图 B. 空闲表 C. 成组链接 D. 空闲链表
[tag_link]
正确答案：A
A. 文件系统需要额外的外存空间记录空闲块的位置，占用外存空间大小与当前空闲块数量无关的是位示图。位示图是一种常用的记录空闲块位置的方法，它使用一个位来表示一个块是否空闲。位示图的大小取决于磁盘的总块数，而与当前的空闲块数量无关。 B. 空闲表：空闲表是一种记录磁盘空闲块位置的方法它使用一个表来记录空闲块的位置。空闲表的大小会随着空闲块的数量的变化而变化。 C. 成组链接：成组链接是一种记录该组中其他块的位置。成组链接的大小会随着空闲块数量的变化而变化。 D. 空闲链表：空闲链表是一种记录酸盘空闲块位置的方法，它使用一个链表来记录所有空闲块的位置。空闲链表的大小会随着空闲块数量的变化而变化。
某操作系统采用可变分区分配存储管理方法，操作系统占用低地址部分的 126KB。用户区大小为 386KB，且用户区始址为 126KB，用空闲分区表管理空闲分区。若分配时采用分配空闲区高地址部分的方案，且初始时用户区的 386KB 空间空闲，对申请序列：作业 1 申请 80KB，作业 2 申请 56KB，作业 3 申请 120KB，作业 1 释放 80KB，作业 3 释放 120KB，作业 4 申请 156KB，作业 5 申请 81KB。如果采用首次适应算法处理上述序列，则最小空闲块的大小为（ ）。
A. B. C. D.
[tag_link]
正确答案：B
我们按照序列逐步模拟存储分配与释放过程。 操作系统占用低地址 126KB，用户区始址 126KB，大小 386KB，即用户区范围为 126KB～512KB。 初始时，整个用户区空闲，空闲分区表仅有一个分区：起始地址 126KB，大小 386KB。 分配时采用首次适应算法，且从找到的空闲分区的高地址部分切割。
**作业 1 申请 80KB**：查找第一个大小≥80KB 的空闲分区（126KB, 386KB），从高地址部分切割 80KB，分配后空闲分区变为（126KB, 306KB）。 作业 1 占据 432KB～512KB。
**作业 2 申请 56KB**：查找第一个大小≥56KB 的空闲分区（126KB, 306KB），从高地址部分切割 56KB，分配后空闲分区变为（126KB, 250KB）。 作业 2 占据 376KB～432KB。
**作业 3 申请 120KB**：查找第一个大小≥120KB 的空闲分区（126KB, 250KB），从高地址部分切割 120KB，分配后空闲分区变为（126KB, 130KB）。 作业 3 占据 256KB～376KB。
**作业 1 释放 80KB**：释放区域为 432KB～512KB，与现有空闲分区（126KB, 130KB）不相邻，空闲分区表变为两个：（126KB, 130KB）和（432KB, 80KB）。
**作业 3 释放 120KB**：释放区域为 256KB～376KB，与第一个空闲分区（126KB, 130KB）相邻（结束于 256KB），合并为（126KB, 250KB）。 第二个空闲分区（432KB, 80KB）不变。 空闲分区表为（126KB, 250KB）和（432KB, 80KB）。
**作业 4 申请 156KB**：查找第一个大小≥156KB 的空闲分区（126KB, 250KB），从高地址部分切割 156KB，分配后该分区变为（126KB, 94KB）。 作业 4 占据 220KB～376KB。 空闲分区表为（126KB, 94KB）和（432KB, 80KB）。
**作业 5 申请 81KB**：查找第一个大小≥81KB 的空闲分区（126KB, 94KB），从高地址部分切割 81KB，分配后该分区变为（126KB, 13KB）。 作业 5 占据 139KB～220KB。 空闲分区表最终为（126KB, 13KB）和（432KB, 80KB）。
最终有两个空闲块，大小分别为 13KB 和 80KB，最小空闲块大小为 13KB，对应选项 B。
现有一个容量为10GB 的磁盘分区，磁盘空间以簇 (Cluster) 为单位进行分配，簇的大小为4KB, 若 采用位图法管理该分区的空闲空间，即用一位 (bit) 标识一个簇是否被分配，则存放该位图所需簇的个数 为 ( ) 。
A.80
B.320
C.80K
D.320K
[tag_link]
正确答案：A
簇 的总数为 10GB/4KB = 2.5M, 用一位标识一簇是否被分配，则整个磁盘共需要 2.5M 位，即需要 2.5M/8 =320KB, 因此共需要 320KB/4KB = 80 个簇，选 A。
下列选项中，可被文件系统用于外存空间使用情况的是（ ）。
A. 目录 B. 系统打开文件表 C. 文件分配表（FAT） D. 文件控制块（FCB）
[tag_link]
正确答案：C
文件分配表（FAT）是文件系统用来记录磁盘块（簇）使用情况的数据结构。它记录了哪些磁盘块是空闲的，哪些已经被文件占用，因此文件系统可以通过 FAT 来管理空闲空间。
- A. 目录用于存储文件和子目录的元数据（如文件名、位置等），但不直接管理空闲空间。
- B. 系统打开文件表：用于记录当前打开的文件及其状态，与空闲空间管理无关。
- D. 文件控制块（FCB）：FCB 记录单个文件的元数据（如大小、位置等），不直接记录整个外存空间使用情况。
假设计算机系统采用 CSCAN（循环扫描）磁盘调度策略，使用 2KB 的内存空间记录 16384 个磁盘块的空闲状态。
(1) 请说明在上述条件如何进行磁盘块空闲状态的管理。
(2) 设某单面磁盘的旋转速度为 6000rpm，每个磁道有 100 个扇区，相邻磁道间的平均移动的时间为 1ms。若在某时刻，磁头位于 100 号磁道处，并沿着磁道号增大的方向移动（见下图），磁道号的请求队列为 50, 90, 30, 120，对请求队列中的每个磁道需读取 1 个随机分布的扇区，则读完这个扇区点共需要多少时间？需要给出计算过程。
(3) 如果将磁盘替换为随机访问的 Flash 半导体存储器（如 U 盘、SSD 等），是否有比 CSCAN 更高效的磁盘调度策略？若有，给出磁盘调度策略的名称并说明理由；若无，说明理由。
[tag_link]
1）用 位图 表示磁盘的空闲状态。每位表示一个磁盘块的空闲状态，共需要 16384/32 = 512字 = 512×4字节 = 2KB，正好可放在系统提供的内存中。
2）采用 C-SCAN 调度算法，访问磁道的顺序和移动的磁道数见下表。
| 被访问的下一个磁道号 | 移动距离（磁道数） |
|---|---|
| 120 | 20 |
| 30 | 90 |
| 50 | 20 |
| 90 | 40 |
移动的磁道数为 20+90+20+40 = 170，故总的移动磁道时间为 170ms。由于转速为 6000rpm，则平均旋转延迟为 5ms，总的旋转延迟时间 = 20ms。由于转速为 6000rpm，则读取一个磁道上一个扇区的平均读取时间为 0.1ms，总的读取扇区的时间为 0.4ms。综上，读取上述磁道上 所有扇区所花的总时间为 190.4ms。
3）采用 FCFS 调度策略更高效。因为 Flash 半导体存储器的物理结构不需要考虑寻道时间和旋转延迟，可直接按 I/O 请求的先后顺序服务。