介绍文件系统的相关概念。
File Concepts
文件是在二级存储上有命名的相关信息集合。
Types:
- Text
- Source/object programs
- Executable programs
- Database records
- Graphic images
- Multimedia
| file type | usual extension | function |
|---|---|---|
| executable | exe, com, bin or none | ready-to-run machine language program |
| object | obj, o | compiled, machine language, not linked |
| source code | c,cc,java,pas, asm, a | source code in various languages |
| batch | bat, sh | commands to the command interpreter |
| text | txt, doc | textual data, documents |
| word processor | wp, tex, rtf, doc | various word-processor formats |
| library | lib, a, so, dll | libraries of routines for programmers |
| print or view | ps, pdf, jpg | ASCII or binary file in a format for printing or viewing |
| archive | arc, zip, tar | related files grouped into one file, sometimes com pressed, for archiving or storage |
| multimedia | mpeg, mov, rm, mp3,avi | binary file containing audio or |
File Attributes
- 名称
- 标识符：
- 文件系统内部唯一标识符
- 由操作系统分配
- 类型
- 位置：
- 文件在磁盘上的位置
- 由操作系统分配
- 大小
- 保护信息：
- 访问权限
- 文件所有者
- 其他用户的访问权限
- 时间、日期和用户标记：
- 创建时间
- 修改时间
- 最后访问时间
- 用户标记
File Structure
- 无结构
- 简单结构
- 定长记录
- 可变长度
- 复杂结构
- 格式化文档
- 可重定向加载文件
File Operations
创建， 打开，关闭，读，写，重命名，删除，重定位（它允许用户或程序在不必顺序读取整个文件的情况下，直接访问文件中的特定位置。）
File Access Methods and Protection
Access Methods
- Sequential Access
- 只能从文件的开头开始读取
- 只能顺序访问
- Direct Access
- 允许在文件的任意位置进行读取和写入
- 允许随机访问
- Indexed Access
Protection
基本操作权限：r w x 读 写 执行
用户分组： 所有者， 组，公共
Directory Structures
磁盘可以被细分为多个分区（partitions），这些分区也被称为 minidisks 或 slices。
分区可以用于存储文件系统，包含文件系统的实体被称为卷（volume）。
每个卷会在设备目录或卷目录表（volume table of contents）中记录该文件系统的相关信息。
磁盘或分区还可以选择不使用文件系统，即作为裸设备使用，或者进行格式化后使用特定的文件系统。
磁盘可以进行 RAID 保护，以防止故障。
Directory Structure
| 目录类型 | 结构特点 | 优点 | 缺点 | 应用场景及示例 |
|---|---|---|---|---|
| 单级目录 | 所有用户共用一个目录，文件直接存于该目录下，无层级区分 | 结构简单，易于理解和实现 | 查找文件效率低，随文件增多查找时间大幅增加；易产生命名冲突，不同用户难以使用相同文件名；无法有效保护用户私人文件，所有文件都在同一层级，易被其他用户访问和修改；缺乏文件分组能力，不便于分类管理文件 | 早期简单操作系统，或在文件数量极少且对安全性、管理便捷性要求不高的特定场景。如一些简单的嵌入式系统，仅存储少量配置文件时可能采用 |
| 两级目录 | 为每个用户创建独立目录，形成两级结构，用户目录下存放各自文件 | 解决了不同用户间文件名冲突问题，同一文件名可在不同用户目录下存在；查找文件效率相比单级目录有所提高，只需在特定用户目录下查找 | 文件分组功能有限，只能按用户进行初步区分，无法根据文件属性、用途等进行更细致的分组管理 | 适用于用户数量相对固定且对文件管理有一定安全性要求，但对文件分组需求不太复杂的场景。如早期的多用户小型办公系统，每个用户有自己的文件目录 |
| 树状结构目录 | 以根目录为起点，形成多层次的树形层次结构，目录下可包含文件和子目录 | 层次清晰，便于文件分类管理和查找，用户可根据文件类别将其存放在不同子目录下；文件组织方式灵活，可根据需求进行深度和广度的扩展 | - | 广泛应用于各类操作系统，如Windows、Linux、Unix等主流操作系统的文件管理。用户在操作系统中创建不同文件夹来存放文档、图片、程序等不同类型文件 |
| 无环图目录 | 允许存在共享子目录和文件，通过链接实现文件或子目录共享 | 可有效减少文件存储空间占用，多个目录可共享同一文件或子目录，避免重复存储；方便文件共享和协作，多个用户或项目可共享相同文件资源 | 共享文件删除时可能产生悬空指针问题，若处理不当，会导致指针指向无效位置，影响系统稳定性；实现和管理相对复杂，需要额外处理共享链接和一致性维护 | 适用于对文件共享需求较高的场景，如企业内部的文档管理系统，多个部门可能需要共享某些文件；软件开发团队中，多个项目可能共享一些公共代码文件 |
| 一般图目录 | 是一种更复杂的目录结构，链接方式更灵活，允许链接到文件和子目录 | 提供了极高的灵活性，可根据实际需求构建复杂的文件关联关系 | 需要解决添加链接时可能产生的循环问题，否则会导致目录结构混乱；实现和管理难度大，对系统资源和算法要求高 | 在一些对文件组织灵活性要求极高的专业领域可能有应用，如大型数据库管理系统中对数据文件的组织；复杂的科研项目文件管理，需要构建复杂的文件关联关系 |
无环图目录的两种实现方式：
- 链接
- 文件信息复制
删除文件时容易产生悬空指针，可删除文件时处理链接/保留文件直到所有引用删除。
一般图目录：可连接文件/子目录，但不能成环（垃圾回收）
Directory Implementation
- Linear List
- Hash Table
File System Structures and Operations
前端：关注文件系统呈现给用户的方式，为用户提供操作文件的接口
后端： 负责创建算法和数据结构，将逻辑文件系统映射到物理辅助存储设备
Layered File System
| 层次 | 功能 | 特点 | 与其他层次关系 | 相关数据结构 |
|---|---|---|---|---|
| 设备驱动层（I/O控制层） | 将逻辑地址转换为硬件特定命令，控制I/O设备数据传输 | 类似翻译器，直接与硬件交互 | 接收基本文件系统命令，操作硬件 | 无独立特定数据结构，依赖硬件控制器数据结构 |
| 基本文件系统层 | 基于逻辑地址向设备驱动层发命令，管理I/O调度、内存缓冲区和缓存 | 负责底层数据块读写，优化I/O操作 | 从文件组织模块获取信息，向设备驱动层发令，为逻辑文件系统提供数据 | 内存缓冲区、缓存 |
| 文件组织模块层 | 管理文件逻辑结构，跟踪逻辑块与空闲块，分配空间 | 理解文件逻辑块，管理空闲空间 | 接收逻辑文件系统请求，为基本文件系统提供逻辑块信息 | 空闲空间管理器相关数据结构 |
| 逻辑文件系统层 | 管理元数据，将文件名转换为文件编号等，进行目录管理和文件保护 | 维护文件系统逻辑视图和安全性 | 与应用程序交互，调用文件组织模块功能 | 文件控制块（FCB，如Unix的inode），包含权限、日期等信息 |
File-System Operations
- 存储数据结构
- 引导控制块：每个卷一份，若卷含操作系统，通常位于卷首，存储引导系统所需信息。
- 卷控制块：每卷一个，记录卷的总块数、空闲块数、块大小和空闲块指针等详细信息。
- 目录结构：组织文件，保存文件名和inode编号等，方便文件定位与访问。
- 文件控制块：每个文件对应一个，包含文件的标识符、权限、大小、日期等详细属性。
- 内存数据结构
- 挂载表：记录每个已挂载卷的信息，用于系统识别和管理卷。
- 目录结构缓存：缓存近期访问的目录信息，提升文件查找和操作效率。
- 系统范围打开文件表：存储每个打开文件的FCB副本及其他相关信息，跟踪管理所有打开文件。
- 每个进程打开文件表：包含指向系统范围打开文件表的指针，以及进程打开文件的特定信息。
- 缓冲区：在文件读写时临时存储文件系统块，缓解磁盘与内存速度差异。
Partitions and Mounting
- 分区（Partition）
- 定义与用途：分区是将磁盘划分成多个相对独立的逻辑区域。一个分区可以是一个包含文件系统的“cooked”卷，若该文件系统可引导，则分区还需存储引导信息；也可以是不包含文件系统、仅为块序列的“raw”卷。根分区一般用于存放操作系统，其他分区可存储不同类型的操作系统、文件系统或保持为原始状态。
- 引导相关：引导块在分区中至关重要，它能够指向引导卷或包含加载内核代码的引导加载程序块集，对于多操作系统启动的情况，引导块可指向引导管理程序。
- 挂载（Mounting）
- 挂载概念：挂载是把存储设备或其文件系统连接到操作系统目录树的过程，使得设备中的文件可被系统访问。比如，将外部存储设备挂载到系统的某个目录后，用户就能通过该目录路径访问设备中的文件。
- 挂载方式：根分区通常在系统启动时挂载，而其他分区的挂载方式较为灵活，可以在系统启动时自动挂载，也能由用户根据需求手动挂载。
Allocation Methods
An allocation method refers to how disk blocks are allocated for files
- Contiguous Allocation
- Linked Allocation
- Indexed Allocation
Extension: File-Allocation Table (FAT)
I-node Example
绿色：逻辑块 黑色：物理磁盘块
Combined with Disk Scheduling
Free Space Management
- Bit Vector/Map：用位向量表示是否空闲（0/1）
- Linked List：将所有空闲块组织成一个链表结构
- Grouping and Counting： 把存储设备上的空闲块划分成若干组，为每组空闲块设置一个计数器
- Space Maps： 创建一个数据结构来详细记录存储设备上各个块的使用状态
Virtual and Remote File Systems
VFS：软件层，用于为操作系统提供统一的文件系统接口。在操作系统内核和具体的文件系统驱动之间充当抽象层。包含文件系统对象的缓存机制，可以同时支持多种不同类型的文件系统。
Remote file systems enable sharing of files across a network.
