File Allocation 文件的实现 续

链表分配 Linked List Allocation
  • 保持磁盘块的链表
  • 缺点
    • 随机存取速度慢
    • 一个块中的数据量不是2的幂

由于指针占去了一些字节，每个磁盘块存储数据的字节数不再是2的整数次幂

采用内存中的表进行链表分配 Linked List Allocation using an index
  • 从每个块中取出表指针字并将它们放入内存中的索引表FAT（File Allocation Table 文件分配表）中。
  • 好处
    • 整个块可用于数据
    • 存储在内存中，速度快
  • 缺点
    • 占用大量内存。需要将整个表放在内存中
    • 对于 200-GB 磁盘，该表将占用 600M 或 800M 内存。

I-node (index-node)

  • 是一种数据结构，给每个文件赋予一个i节点

  • 列出文件块的属性和磁盘地址

  • 给定i节点，就能找到文件的所有块

  • 这种机制有很大的优势，即只有在对应文件打开时，其i节点才在内存中

  • 占用空间比FAT小

  • i节点的问题

Directories 目录的实现

  • 打开文件时，文件系统使用路径名来定位目录条目(directory entry)。
  • 目录：提供查找磁盘块所需的信息。
    1. 整个文件的磁盘地址（连续块）
    2. 第一个块的数量（链表）
    3. I-node的数量（I-node）
  • 在哪里存储属性？ 在目录中还是在 I 节点中？
两种存储属性的方法
  • 目录条目中的固定大小条目、磁盘地址和属性 (MS-DOS/Windows)
  • 每个条目仅引用一个 I 节点的目录 (UNIX)
处理目录中的长文件名
  • Fixed-length names 定长名称（浪费空间）
  • In-line 行（删除文件时，会引入一个可变大小的间隙（a））

  • Heap 堆（堆管理需要额外的努力（b））

如何搜索每个目录中的文件？
  • Linearly 线性（慢）
  • Hash table 哈希表（更快的查找但更复杂的管理）
  • Cache the results of searches 缓存搜索结果
Shared files 共享文件
  • 共享文件用于允许文件出现在多个目录中。
  • 目录和共享文件之间的连接称为链接(link)。 文件系统是有向无环图 (DAG)。

  • 问题：
    • 如果目录包含磁盘地址，则必须在目录 B 中制作C目录中的磁盘地址的副本。如果 C 或 B 往文件中添加内容，新的数据块将仅出现在添加工作的用户的目录中。
  • 解决方案：
    • 不要在目录中列出磁盘块地址，而是在一个小的数据结构中，目录指向这个数据结构。例如，索引节点、i节点
    • 创建一个类型为 link 的新文件，其中包含链接到的文件的路径名 → 符号链接(symbolic linking)
  • 两种方法的缺点

数据结构

符号链接

Virtual File Systems 虚拟文件系统

  • 定义：虚拟文件系统（或虚拟文件系统交换机）是内核中的软件层，为用户空间程序提供文件系统接口。

    • 从“the”文件系统到许多文件系统类型
    • 示例 – Ext2、UFS(Solaris)、NFS、Ext3、Veritas、ReiserFS、XFS、ISO9660 (CD)、UDF (DVD) 等。

  • 不同类型文件系统的相同 API

    • 将文件系统通用操作与实现细节分开
    • 系统调用程序到 VFS API 而不是特定的 FS 接口

  • 非常灵活的用例：

    • 远程用户文件和本地系统文件？
    • 从 USB 启动？ 网络？

问题

文件如果很大，i节点块的大小需要变大，可能还需要指向另一块包含额外块地址的块的地址，所以B、C、D有关

Check Points

Please describe the advantages and disadvantages of contiguous allocation.

  • 随机读取速度快，实现简单，性能好（无需寻道）
  • 需要提前知道文件大小，文件删除后留下碎片

Please describe the advantages and disadvantages of linked listed allocation.

  • 文件大小可拓展，充分利用磁盘空间
  • 随机存储慢，数据大小不是2的幂次

Please describe the advantages and disadvantages of FAT.

  • 随机存储速度快，文件大小可拓展
  • 占用内存大量空间，