Chapter 11: File System Implementation
ch11 File System Implementation.pdf 操作系统（本）2024-12-17 第 7-8 节
File-System(organized) Structure
文件系统是操作系统中以文件方式管理计算机软件资源的软件、被管理的文件和数据结构（如目录和索引表等）的集合
为了提供对磁盘的高效且便捷的访问，操作系统通过文件系统来轻松地存储、 定位、提取数据
分层设计的文件系统
- Application Programs
- 逻辑文件系统
- 管理内存
- 管理元数据：文件系统的所有结构数据，而不包括实际数据（或文件内容）
- 文件组织模块
- 管理外存
- 知道文件及其逻辑块和物理块
- 基本文件系统
- 向合适的设备驱动程序发送一般命令就可对磁盘上的物 理块进行读写
- I/O 控制
File-System Implementation
In-Memory File System Structures
- An in-memory partition table(分区表)
- An in-memory directory structure（目录结构）
- The system-wide open-file table （系统打开文件表）
- The per-process open-file table （进程打开文件表）
Directory Implementation
Linear list（线性检索法）
使用存储文件名和数 据块指针的线性列表（数组、链表等），容易实现
采用线性搜索来查找特定条目（缺点）
Hash Table（哈希表）
linear list with hash data structure.
减少了目录搜索时间，但有 collisions 碰撞、冲突，即两个文件名哈希到相同的位置
Allocation Methods，文件物理结构
An allocation method refers to how disk blocks are allocated for files
连续分配 Contiguous Allocation
每个文件占据磁盘上的一组连续的块
访问文件很容易，为新文件找空间比较困难，文件很难增长
旧文件要扩张就得移动到更大的空闲空间，还得定期整理零散的空闲块，巨麻烦
Extent-Based Systems （基于长度系统）
一种修正的连续分配方法
该方法开始分配一块连续空间，当空间不够时，另一块被称为扩展的连续空间会添加到原来的分配中
相应的，文件块的位置(文件属性之一)为开始地址、块数、加上一个指向下一扩展的指针
就是，扩张时不用移动原来已有的部分，原有部分加一个指针指向新的块即可
链接分配 linked allocation
Each file is a linked list of disk blocks: blocks may be scattered anywhere on the disk. 每个 block 都有一个指针，指向该文件的下一个 block
文件创建与增长容易，但不能随机访问，必须要遍历，且指针需要占用空间
簇：将多个连续块组成簇，磁盘以簇为单位进行分配
分配簇(Cluster)比分配块(block)更节省指针占用的空间，减少访问时间
索引分配 indexed allocation
将所有的数据块指针集中到索引块中，索引块中的第 i 个条目指向文件的第 i 块
目录条目包括索引块的地址
索引分配支持直接访问，且没有外部碎片问题，但索引块本身可能会浪费空间
UNIX、Linux 直接间接混合分配方法
每个盘块大小为 4KB 时：
当文件不大于 48KB 时，便可直接从索引结点中读出该文件全部盘块号，这样读小文件时速度快；
如文件大于 48KB 时，系统再 逐步增加一级索引、二级索引和三级索引，这样最大管理的文件为 48KB＋ 4MB＋4GB＋4TB，达到管理大文件的目标。
12 x 4K = 48KB
1024 x 4K = 4 MB
1024 x 1024 x 4K = 4 GB
1024 x 1024 x 1024 x 4K = 4 TB
[!EXAMPLE]
Free-Space Management
位图
- bit [i] = 0 -> block [i] 空闲
- bit [i] = 1 -> block [i] 被占用
第一个空闲块的计算：一个字的位数 × 值为 1 的字数 ＋ 第一个值为 0 的位的偏移
位图需要额外的空间：块大小为 2^12 字节，磁盘大小为 2^30 字节(1GB)， N = 2^30 / 2^12 = 2^18 (即 32K bytes)
空闲链表
将所有空闲磁盘块用链表连接起来
Unix 成组连接法(next page)
将 n 个空闲块的地址存在第一个空闲块中，而最后一块包含另外 n 个空闲 块的地址，如此继续
空闲表法
记录第一块的地址和紧跟第一块的连续的空闲块的数量 n
Review Question
