File-System
File-System 负责管理外存
A file is a sequence of bytes stored on some device
Allocation Methods 文件物理结构
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
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 bit (即 32K bytes)
空闲链表
将所有空闲磁盘块用链表连接起来
Unix 成组连接法(next page)
将 n 个空闲块的地址存在第一个空闲块中，而最后一块包含另外 n 个空闲 块的地址，如此继续
空闲表法
记录第一块的地址和紧跟第一块的连续的空闲块的数量 n
Review Question
1. 解释打开和关闭操作的目的？
- 打开操作的目的：
- 为文件的后续操作（读、写、修改等）做准备。
- 系统会创建一个 打开文件表项，记录文件的相关信息（如文件指针、访问权限等），以便快速访问。
- 减少频繁的目录检索，提高文件操作效率。
- 关闭操作的目的：
- 释放文件打开时分配的系统资源（如内存、打开文件表等）。
- 确保文件的所有数据被正确写回存储介质，避免数据丢失。
2. 什么叫文件“按名存取”？文件系统如何实现文件的按名存取？
- 文件“按名存取”：
- 用户通过文件名（逻辑标识符）访问文件，而无需关心文件在物理存储设备中的具体位置。
- 文件系统负责将文件名映射到存储设备的物理地址，实现透明访问。
- 文件系统实现按名存取的方法：
- 目录结构：文件系统维护一个目录表，每个文件名对应一个目录项，记录文件的元数据（如文件大小、物理地址、权限等）。
- 文件控制块（FCB）：目录项指向文件控制块，文件控制块保存文件的实际存储信息。
- 文件名解析：当用户访问文件时，文件系统通过目录结构和文件控制块找到对应的文件存储位置。
3. 文件系统提供系统调用或命令 rename 实现文件改名，同样也可以通过把文件拷贝到新文件并删除原文件来实现文件更名，试述两种方法的不同。
- 使用
rename实现文件改名：- 特点：只修改文件系统的目录项，更新文件名。
- 效率：操作非常快，不需要移动文件的实际数据。
- 适用场景：文件在同一文件系统中更名。
- 通过拷贝和删除实现文件更名：
- 特点：将文件内容复制到新文件，再删除旧文件。
- 效率：耗时较多，因为需要读写文件数据。
- 适用场景：文件跨文件系统时更名，或实现文件备份。