跳转至

HW4：理解各类文件系统与基于 FAT16 的语义文件系统设计

作业说明

  • 本次作业内容涵盖各类文件系统、磁盘调度算法等相关知识；
  • 同时，部分题目会结合实验4 的相关代码与概念，大家遇到不熟悉的概念可以阅读实验文档与代码的相关部分；
  • 由于本次作业发布时，理论课可能尚未讲完文件系统的全部内容，同学们可以先完成已经学习过的部分；
  • 本次作业完成周期为 3 周，截止时间为 6 月 21 日 23:59 (周日)；
  • 同学们若对某题题述有疑问或者认为某题有错误/歧义，请及时联系助教。

题目1：简答题

请回答以下问题：

  • 什么是打开文件表（open-file table）以及我们为什么需要它？
  • 什么是 RAID5 和 RAID6 ？
  • 解释"755"的文件权限含义。
  • 什么是索引结点，它的成员通常有哪些？

题目2：磁盘调度算法

假设一个磁盘驱动器有 5000 个柱面，从 0 到 4999。该驱动器目前正在处理请求柱面 2150，以前请求柱面为 1805。按 FIFO 顺序的等待请求队列是：

2069, 1212, 2296, 2800, 544, 1618, 356, 1523, 4965, 3681

从当前磁头位置开始，针对以下每个磁盘调度算法，磁臂移动以满足所有等待请求总的移动距离是多少。

  • FCFS
  • SSTF
  • SCAN
  • LOOK
  • C-SCAN
  • C-LOOK

题目3：理解 FAT16 读写过程

在做此题前，同学们需要先了解 FAT16 文件系统的结构与数据存储的方式。考虑满足如下数据的 FAT16 文件系统管理的磁盘：目录项大小为 32B，扇区（即“块”）大小为 512B，每簇 1 扇区。回答：

  1. 此文件系统支持的文件最大字节长度约是多少？给出理由。

  2. 不将读入的块缓存到内存中，假设 data 的目录项是根目录下的第 20 个目录项，file1.txt 的目录项是 data 下第 40 个目录项，目录项读取采用从目录下第一个目录项开始逐个按文件名匹配的方式查找，若有上层请求读取 /data/file1.txt 的前 1KB 数据，将触发多少次按块读取的磁盘 I/O ？假设所有对 FAT 表的读取都在一个块内，若将读入的块缓存，将触发多少次按块读取的磁盘 I/O ？回答中请给出理由。

子目录

根目录是磁盘上固定的块，存放其下文件的目录项；而子目录存储其下文件目录项的位置是灵活的，它实际上是一个（数据簇只用来存放其下文件目录项的）文件，所以从子目录读取目录项就需要从它的数据簇中去读取，这使得子目录可以增长。注意：根目录的存放目录项的数据块是磁盘上连续的，且根目录不可增长，而子目录存放目录项的数据簇是链表形式连接的。

  1. 相比于连续分配要求一个文件占用磁盘上一段连续的簇，说明 FAT16 文件系统的簇链设计的优劣势，你能举例说明连续分配的用处吗？

题目4：索引分配文件系统与日志

考虑目录项为如下结构的索引分配文件系统：

struct dirent {
    uint index_node_number;
    uint direct_block_addr[14];
    uint indirect_block_addr;
}

其中 index_node_number 是该目录项的索引号，direct_block_addr 是保存该文件直接数据块地址的数组，indirect_block_addr 是保存该文件间接数据块地址的数组，间接数据块中保存若干个指向保存文件数据的块的地址。

图11-9

请结合教材中图11-9关于索引分配文件系统的数据存储方式图， 考虑挂载块大小为 512B、使用以上文件系统的磁盘，请回答：

  1. 此文件系统支持的文件最大字节长度是多少？给出计算过程。

  2. 现有一请求要为一大小为 6KB 的文件追加 3KB 数据，需要分配几个空闲数据块、写入哪些数据？

  3. 该索引分配的文件系统由超级块（存储文件系统元数据）、inode 位图区（标识哪些 index_node_number 对应的 inode 已经被使用）、数据位图区（标识哪些数据块已被使用）、inode 区（保存 inode）、数据区（保存数据块）构成。每次更新一个文件，都必须考虑相应的功能区是否要更新。然而，倘若在一次操作中途内核崩溃，例如掉电，就可能导致磁盘上的数据只更新了一半就停止了，这时会产生文件系统一致性问题。为了确保数据一致性，该文件系统采用日志来记录磁盘更新，协议如下：

    1. 将块号为 800-809 的数据块设置为日志区，块 800 用来写入日志头，它包含了某次操作要更新的块列表，日志头是否有效等信息；
    2. 磁盘上任何块要更新都需要先将该块的数据写入日志区的块，并且一次操作中对同一个块只允许一次更新；
    3. 将所有要更新的块都写入日志区后，将相关信息写入日志头；
    4. 更新要更新的块，更新完之后清空日志头；
    5. 若崩溃恢复时发现日志头有效，按照日志头中的信息与日志区的数据块将数据写入要更新的块；否则忽略。

    请分别分析崩溃发生在以下节点的恢复时内核会如何工作，文件系统是否将该操作持久化入磁盘：日志数据块已经写入，但日志头还没有写入；内核已经更新了部分块，但是还没有更新完毕。

题目5：FAT16 目录项与关键词伪目录项

实验代码中的 FAT16 目录项结构如下：

struct dirent {
    uchar name[11];
    uchar attr;
    uchar ntres;
    uchar crt_time_tenth;
    ushort crt_time;
    ushort crt_date;
    ushort last_acc_date;
    ushort first_cluster_hi;
    ushort wrt_time;
    ushort wrt_date;
    ushort first_cluster_lo;
    uint file_size;
} __attribute__((packed));

实验4 设计的关键词伪目录项可以参考如下结构：

struct keyword_dirent {
    uchar flag;
    uchar data1[10];
    uchar attr;
    uchar data2[20];
} __attribute__((packed));

其中 flag 高 4 位固定为 0x9，低 4 位标为“该关键词伪目录项是对应文件的第几个关键词伪目录项”，attr 固定为 0x0F，其余字段均存储关键词字符串，以空格为分隔符，以 '\0' 为结尾。关键词伪目录项与其对应的文件目录项在磁盘上的逻辑结构为

[KW0][KW1]...[KWn-1][DIRENT]

  1. 解释 dirent 中 name 的构成，解释 first_cluster 的用途，并说明 first_cluster 在 FAT16 中如何计算。

  2. 阅读设置关键词的流程，如文末图（实验4 文档 Part2 3.1.3），不需要关注具体的实现细节，只需要知道大致流程，重点关注 1-5 步骤。根据以下命令序列，写出各标号命令执行完毕后文件 A、B、C 在磁盘上的连续逻辑结构，例如，cmd 0 对应的结构为 [KW0-A][DIRENT-A][DIRENT-B]，已删除的目录项用 [DEL] 标记，注意：已删除的槽位可以复用，假设在这之前父目录下没有文件。

touch A
kwset A os 
touch B # cmd 0
kwset B inference training LLM acceleration compute-processing-unit neural-processing-unit
touch C # cmd 1
kwset B compute-processing-unit neural-processing-unit # cmd 2
kwset A filesystem fat16 SemanticFS VectorBase # cmd 3

实验4 Part2 3.1.3