os：文件系统

文件系统概念

文件系统和文件

文件系统：操作系统中管理持久性数据的子系统，提供数据存储和访问功能

组织、检索、读写访问功能
大多数计算机系统都有文件系统
Google也是一个文件系统

文件：具有符号名，由字节序列构成的数据项集合。

文件系统的基本数据单位
文件名是文件的表示符号

文件系统的功能

分配文件磁盘空间
- 管理文件块（位置和顺序）
- 管理空闲空间（位置）
- 分配算法（策略）
管理文件集合：
- 定位：通过文件名定位文件并读取其内容
- 命名：对文件命名
- 文件系统结构：文件的组织方式
数据可靠和安全
- 可靠：持久保存文件，避免错误和崩溃
- 安全：多层次保护数据安全，减少攻击危害

文件的属性包括：名称、类型、位置、大小、保护、创建者、创建时间、最近修改时间等

文件头：文件系统元数据中的文件信息

文件属性
文件存储位置和顺序

文件系统种类

磁盘文件系统：文件存储在数据存储设备上，如磁盘
- 例如FAT，NTFS，ext2/3，ISO9660
- 不同文件系统的安全要求不同，按照所需选取对应协议即可。
数据库文件系统：
- 文件特征是可被寻址（辨识）的
- 例如WinFS
日志文件系统：
- 记录文件系统的修改/事件
网络/分布式文件系统
- 例如：NFS，SMB，AFS，GFS
特殊文件系统，如管道
虚拟文件系统

关于网络/分布式文件系统

文件可以通过网络被共享

文件位于远程服务器，客户端
客户端远程挂载服务器文件系统
标准系统文件访问被转换成远程访问
标准文件共享协议：NFS（UNIX），CIFS（Win）

分布式文件系统的挑战：

客户端和客户端上的用户辨识很复杂
比如NFS是不安全的
一致性问题
错误处理模式

文件组织和存储

目录、别名和虚拟文件系统

文件以目录的方式组织起来

目录是一类特殊文件
- 目录的内容是文件索引表<文件名, 指向文件的指针>
目录和文件的树型结构
- 早期的文件系统是扁平的(只有一层目录)

目录操作

操作系统应该只允许内核修改目录以确保映射的完整性，应用程序通过系统调用访问目录。

典型目录操作：搜索、创建、删除、列出、重命名、遍历

目录实现

文件名的线性列表包含了指向数据块的指针
- 编程简单
- 执行搜索耗时
哈希表
- 减少目录搜索时间
- 可能会产生冲突（两个文件名的哈希值相同）
- 固定大小

文件别名

两个或多个文件名关联同一个文件

硬链接
- 多个文件项指向一个文件(只在删除最后一个指向这个文件的文件名时，才真正删除该文件的实体)
软链接
- 通过快捷方式指向其他文件
- 通过存储真实文件的逻辑名称来实现

文件目录中的循环

父目录指向子目录，子目录又指回父目录，无限循环

解决循环的办法
- 只允许到文件的链接不允许在子目录里的链接
- 增加链接时用循环检测算法确定是否合理(银行家算法开销大)
实际上是限制路径可遍历文件目录的长度

名字解析(路径遍历)

名字解析是指将逻辑名字转换成物理资源(文件)

遍历文件名录直到找到目标文件

当解析 "/bin/ls"时

读取根目录的文件头(在磁盘固定位置)
读取根目录的数据块搜索 bin 项
读取 bin 的文件头
读取 bin 的数据块搜索 ls 项
读取 ls 的文件头

当前工作目录(PWD)

每个进程都会指向一个文件目录用于解析文件名(可以提高效率)
允许用户指定相对路径来代替绝对路径如 PWD="/bin” 能够解析 “ls”

文件系统挂载

文件系统需要先挂载才能被访问（未挂载的文件系统需要挂载在挂载点上）

虚拟文件系统

目的
- 对所有不同文件系统的抽象
功能
- 提供相同的文件和文件系统接口
- 管理所有文件和文件系统关联的数据结构
- 高效查询例程遍历文件系统
- 与特定文件系统模块的交互

文件系统基本数据结构包括（各中文件系统都应该有）：

文件卷控制块：每个文件系统一个，包括文件系统的详细信息如块、块大小、空余快、计数、指针等，如Unix中的superblock
文件控制块：每个文件一个，包括文件的详细信息如访问权限、拥有者、大小、数据块位置等，如Unix中的vnode
目录项：每个目录项对应一个子目录或文件，将目录项数据结构以及树形布局编码成数据结构，指向文件控制块、父目录、子目录。

这些数据持久存入外存，当需要加载时进入内存，加载的时机分别为：

卷控制模块：当文件系统挂载时进入内存
文件控制块：当文件被访问时进入内存
目录节点：在遍历一个文件路径时进入内存

文件系统的存储视图：

文件分配

背景：大多数文件都很小，一些文件非常大

需要对小文件提供很好的支持，块空间不能太大
必须支持大文件，大文件访问必须高效

如何表示分配给一个文件数据块的位置和顺序就成为一个问题。

分配方式主要有如下几种：

连续分配
链式分配
索引分配

以下我们从存储效率和读写性能等方面来评定这些分配方式。

连续分配

文件头指定起始块和长度
分配策略包括最先匹配、最佳匹配
优点：文件读取表现好，访问高效（随机访问）。
缺点：碎片；文件增长时会出现问题

链式分配

文件以数据块链表方式存储
文件头包含了到第一块和最后一块的指针
优点：创建、增大、缩小很方便，没有碎片
缺点：不支持随机访问，访问效率低；可靠性差（破坏了一个链，后面的数据就会丢失）

索引分配

为每个文件创建一个索引数据块，其中存放指向文件数据块的指针列表
文件头包含了索引数据块指针
优点：直接访问，创建、增大、缩小很方便，没有碎片
缺点：对于小文件来说，有多余开销；多索引块才能实现大文件索引（一个索引快可能放不下所有索引）

大文件可以使用链式索引或者多级索引实现。

链式索引块(IB + IB + …)

多级索引块(IB * IB * …)

UFS多级索引分配(UFS Unix File System)

将各种分配方法融合到一起

文件头包含13个指针
- 10个指针指向数据块
- 第1个指针指向索引块
- 第12个指针指向二级索引快
- 第13个指针指向三级索引快
效果
- 提高了文件大小限制阈值
- 动态分配数据块文件扩展很容易
- 小文件开销小
- 只为大文件分配间接索引块大文件在访问数据块时需要大量查询

空闲空间管理

采用什么数据结构来表示空闲空间？

可以使用位图：用一个01向量来表示整个存储空间的数据块占用情况。0表示空闲，1表示已经分配

其使用简单，但是会产生一个很大的向量

维护起来工作量很大
假定空闲空间在磁盘中均匀分布，则找到空闲块之前平均扫描n/r个数据块（n为磁盘上数据块的总数，r为空闲块的数目）

类似空间分配、页式存储等的思路，这里可以使用链表串联空闲空间。另外可以结合索引结构，实现索引链表，节省空间且容易查找。

RAID

通常磁盘通过分区来最大限度减小寻道时间

分区是一组柱面的集合
每个分区都可以视为逻辑上独立的磁盘

一个拥有完整文件系统实例的外存空间通常常驻在磁盘的单个分区上。

可以将一个磁盘分为多个逻辑分区。
也可以将多个磁盘组成一个逻辑分区

使用多个磁盘的好处：

通过并行改善吞吐量
通过冗余改善可靠性和可用性

冗余磁盘阵列（RAID）

多种磁盘管理技术
RAID分类：RAID-0，RAID-1，RAID-5等
实现：可以通过操作系统内核的文件卷管理实现，也可以通过RAID硬件控制器

RAID-0：磁盘条带化

把数据块分成多个子块，存储在独立的磁盘中
通过独立磁盘上并行数据块访问提供更大的磁盘带宽

RAID-1：磁盘镜像

向两个磁盘写入，从任意一个读取
可靠性成倍增长，读取性能线性增加

RAID-4：带校验的磁盘条带化

数据块级的磁盘条带化+专用奇偶校验磁盘
- 奇偶校验规则可阅读这篇博文
允许从任意一个故障磁盘中恢复，增大可靠性

RAID-5：带分布式校验的磁盘条带化

减小对校验和所在磁盘的读写压力

RAID-3：如上的RAID-0,4,5基于数据块，也可以有基于位的条带化/校验结构。

RAID-6：增加一个奇偶校验块，容许更多的出错。

RAID嵌套

RAID 0 + 1(条带化提高性能再做一个磁盘镜像可靠性提高)

RAID 1 + 0(先做磁盘镜像再做条带化)

文件访问

文件描述符

操作系统在打开文件表（进程独有的和系统级的）中维护的打开文件状态和信息

文件指针
- 最近一次读写位置
- 每个进程分别维护自己的打开文件指针
文件打开计数
- 当前打开文件的次数
- 最后一个进程关闭文件时将其从打开文件表中移除
文件的磁盘位置
- 缓存数据访问信息
访问权限
- 每个进程的文件访问模式信息（其中各个数据结构之间的关系）

文件的用户视图和系统视图

文件的用户视图
- 持久的数据结构
系统访问接口
- 字节序列的集合(Unix)
- 系统不关心存储在磁盘上的数据结构
操作系统的文件视图
- 数据块的集合
- 数据块是逻辑存储单元而扇区是物理存储单元
- 块大小和扇区大小通常是不同的通常是几个扇区构成一个数据块

用户视图到系统视图的转换

文件系统中的基本操作单位是数据块 getc()和putc()即使每次只访问1字节的数据也需要缓存目标数据4096字节

进程读文件
- 获取字节所在的数据块(数据块是逻辑存储单位)
- 返回数据块内对应部分
进程写文件
- 获取数据块
- 修改数据块中对应部分
- 写回数据块

访问模式

操作系统需要了解进程如何访问文件

顺序访问
- 按字节依次读取
- 大多数文件访问都是顺序访问
随机访问
- 从中间读写
- 不常用但很重要
- 虚拟内存中把内存页存储在文件
索引访问
- 依据数据特征进行索引
- 通常操作系统不完整提供索引访问
- 可以在索引内容的磁盘访问之上建立数据库来提供完整索引访问

文件内部结构

无结构
- 单词、字节序列
简单记录结构
- 分列
- 固定长度
- 可变长度
复杂结构
- 格式化的文档(PDF Word)
- 可执行文件

文件共享和访问控制

多用户系统中的文件共享是很有必要的

访问控制
- 每个用户能够获得哪些文件的哪些访问权限
- 访问模式读写执行删除列表
文件访问控制列表(ACL)
- <文件实体, 权限>
Unix模式
- <用户|组|所有人, 读|写|可执行>
- 用户标识ID
  - 识别用户表明每个用户所允许的权限及保护模式
- 组标识ID
  - 允许用户组成组并指定了组访问权限

语义一致性

规定多进程如何同时访问共享文件

与同步算法相似
因磁盘I/O和网络延迟而设计简单
Unix文件系统(UFS)语义(相当于把一致性问题丢回给用户自己处理)
- 对打开文件的写入内容立即对其他打开同一文件的其他用户可见
- 共享文件指针允许多用户同时读取和写入文件
会话语义
- 写入内容只有当文件关闭时可见(一次就要写完整效率低)
读写锁
- 一些操作系统和文件系统提供该功能(又是将一致性问题抛给用户)