12文件系统

21.1文件系统的概念

21.1.1文件系统和文件

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

组织、检索、读写访问数据

大多数计算机系统都有文件系统

Google也是一个文件系统

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

文件系统的基本数据单位

文件名是文件的标识符号

文件系统的功能

■分配文件磁盘空间

管理文件块（位置和顺序）

管理空闲空间(位置)

分配算法(策略)

■管理文件集合

定位：文件及其内容（找到位置并读出内容）

命名：通过名字找到文件

文件系统结构：文件组织方式

■数据可靠和安全

`安全：多层次保护数据安全

`可靠

持久保存文件

避免系统崩溃、媒体错误、攻击等

文件属性（对文件的描述）

文件是记录在外存上的相关信息的具有名称的集合。从用户角度而言，文件是逻辑外存的最小分配单元，即数据除非在文件中，否则不能写到外存。

■文件属性（方便访问）

名称、类型、位置、大小、保护、创建者、创建时间、最近修改时间、…

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

文件属性

文件存储位置和顺序

21.1.2文件描述符

文件描述符是指打开的文件它在内存当中所维护的相关信息

打开文件和文件描述符

■文件访问模式

进程访问文件数据前必须先“打开”文件

■内核跟踪进程打开的所有文件

操作系统为每个进程维护一个打开文件表

文件描述符是打开文件的标识

文件描述符

■操作系统在打开文件表中维护的打开文件状态和信息

`文件指针

最近一次读写位置

每个进程分别维护自己的打开文件指针

`文件打开计数

当前打开文件的次数

最后一个进程关闭文件时，将其从打开文件表中移除

`文件的磁盘位置

缓存数据访问信息

`访问权限

每个进程的文件访问模式信息

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

■文件的用户视图

持久的数据结构

■系统访问接口

字节序列的集合(UNIX)

系统不关心存储在磁盘上的数据结构

■操作系统的文件视图

数据块的集合

数据块是逻辑存储单元，而扇区是物理存储单元

块大小<>扇区大小

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

■进程读文件

获取字节所在的数据块（必须整块读）

返回数据块内对应部分

■进程写文件

获取数据块

修改数据块中对应部分

写回数据块

■文件系统中的基本操作单位是数据块

例如, getc()和putc()即使每次只访问1字节的数据，也需要缓存目标数据4096字节

访问模式

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

■顺序访问:按字节依次读取

大多数的文件访问都是顺序访问

■随机访问:从中间读写（对系统的性能影响很大）

不常用,但仍然重要(例如,虚拟内存中把内存页存储在文件)

■索引访问:依据数据特征索引

通常操作系统不完整提供索引访问

数据库是建立在索引内容的磁盘访问上

索引文件示例

文件内部结构

■无结构

单词、字节序列

■简单记录结构

分列

固定长度

可变长度

■复杂结构（由应用程序来识别）

格式化的文档(如, MS Word, PDF)

可执行文件

文件共享和访问控制

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

■访问控制

每个用户能够获得哪些文件的哪些访问权限

访问模式:读、写、执行、删除、列表等

■文件访问控制列表(ACL)

<文件实体,权限>

■Unix模式

<用户|组|所有人,读|写|可执行>

用户标识ID

识别用户,表明每个用户所允许的权限及保护模式

组标识ID

允许用户组成组，并指定了组访问权限

语义一致性

一致性语义(consistency semantics)是评估文件系统对文件共享支持的一个重要准则。这是描述多用户同时访问共享文件时的语义。特别地，这些语义规定了一个用户所修改的数据何时对另一用户可见。这种语义通常是由文件系统代码来实现的。

■规定多进程如何同时访问共享文件，如何协调？

与同步算法相似

因磁盘I/O和网络延迟而设计简单

■Unix文件系统(UFS)语义

对打开文件的写入内容立即对其他打开同一文件的其他用户可见

共享文件指针允许多用户同时读取和写入文件

■会话语义

写入内容只有当文件关闭时可见

■读写锁

一些操作系统和文件系统提供该功能

概念：保护

当信息保存在计算机系统中，需要保护其安全，使之不受物理损坏(瓦不藕J趁)和非法访问(保护)。

■可靠性通常是由文件备份来提供的。

会自动或人工的定时备份

■保护通过控制访问来实现的。

通过身份来确定操作权限

文件加密

21.1.3目录

分层文件系统

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

■目录是一类特殊的文件

目录的内容是文件索引表<文件名,指向文件的指针>

■目录和文件的树型结构

早期的文件系统是扁平的(只有一层目录)

目录操作

■典型目录操作

搜索文件

创建文件

删除文件

列目录

重命名文件

遍历路径

■操作系统应该只允许内核修改目录

确保映射的完整性

应用程序通过系统调用访问目录

目录实现

■文件名的线性列表，包涵了指向数据块的指针（检索或者说增删它的时间会很长）

编程简单

执行耗时

■哈希表– 哈希数据结构的线性表

减少目录搜索时间

冲突– 两个文件名的哈希值相同

固定大小

概念：绝对路径名从根开始并给出路径上的日录名.直到所指定的文件。相对路径名从当前目录开始定义路径。

21.1.4文件别名

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

■硬链接:多个文件项指向一个文件（要删除到最后一个指向文件实体的硬链接，才能把文件删除掉）

■软链接:以“快捷方式”指向其他文件（软链接的话删除文件实体就删除了文件实体，删除软链接就只删除了其别名）

通过存储真实文件的逻辑名称来实现

文件目录中的循环（子目录指向父目录）

■如何保证没有循环？

只允许到文件的链接，不允许在子目录的链接

增加链接时，用循环检测算法确定是否合理

■更多实践

限制路径可遍历文件目录的数量

名字解析（路径遍历）

■名字解析:把逻辑名字转换成物理资源（如文件）

依据路径名，在文件系统中找到实际文件位置

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

■举例:解析“/bin/ls”

读取根目录的文件头(在磁盘固定位置）

读取根目录的数据块，搜索“bin”项

读取bin的文件头

读取bin的数据块;搜索“ls”顶

读取ls的文件头

■当前工作目录(PWD)

每个进程都会指向一个文件目录用于解析文件名

允许用户指定相对路径来代替绝对路径,如，用PWD=“/bin” 能够解析 “ls”

文件系统挂载

挂接是指把未挂载文件系统的根目录对应到根文件系统里的某一个目录

■文件系统需要先挂载才能被访问

■未挂载的文件系统被挂载在挂载点上

21.1.5文件系统种类

■磁盘文件系统

文件存储在数据存储设备上,如磁盘

例如: FAT, NTFS, ext2/3, ISO9660,等(不同的文件系统优化不一样，安全要求不一样)

■数据库文件系统

文件特征是可被寻址（辨识）的

例如: WinFS

■日志文件系统(日志文件系统指文件系统上 所有修改都会做相应的记录以避免系统个操作执行到一半而导致文件系统损坏，由此导致数据丢失)

记录文件系统的修改/事件

■网络/分布式文件系统

例如: NFS, SMB, AFS, GFS

■特殊/虚拟文件系统（如管道）

网络/分布式文件系统

■文件可以通过网络被共享

文件位于远程服务器

客户端远程挂载服务器文件系统

标准系统文件访问被转换成远程访问

标准文件共享协议

NFS for Unix, CIFS for Windows

■分布式文件系统的挑战

`客户端和客户端上的用户辨别起来很复杂

例如, NFS是不安全的

`一致性问题

错误处理模式

21.2虚拟文件系统

文件系统的实现

■分层结构

虚拟（逻辑）文件系统（VFS，Virtual File System）

特定文件系统模块

虚拟文件系统（VFS）

■目的

对所以不同文件系统的抽象

■功能

提供相同的文件和文件系统接口

管理所以文件和文件系统关联的数据结构

高效查询例程，遍历文件系统

与特定文件系统模块的交互

文件系统基本数据结构

■引导控制块（boot control block）

包括系统从该卷引导操作系统所需要信息。

■文件卷控制块（Unix：“superblock”）

每个文件系统对应一个文件控制块，里面描述文件系统详细信息，包括块、块大小、空余块、计数/指针等

■文件控制块（unix：“vnode”or“inode”）

每一个文件有一个文件控制块，里面描述了这个文件的详细信息，比如说这个文件的访问权限拥有者大小和数据块所在的位置等等

■目录项

每个目录项对应着一个子目录或者说一个文件，所有这些目录项的数据结构

和树状的分层结构形成了文件系统的数据结构，主要维护的是每一个目录项所对应的文件控制块的位置，父目录子目录的位置。

文件系统的组织视图

文件系统的存储结构

■文件系统数据结构

卷控制块（每个文件系统一个）

文件控制块（每个文件一个）

目录节点（每个目录项一个）

■持久存储在外层中

存储设备的数据块中

■何时需要加载进内存

卷控制块：当文件系统挂载时进入内存

文件控制块：当文件访问时进入内存

目录节点：在遍历一个文件路径是进入内存

文件系统的存储视图

20.3文件缓存和打开文件

多种磁盘缓存位置

有的系统有一块独立内存用做缓冲缓存，位于其中的块假设马上需要使用。其他系统采用页面缓存(page cache)来缓存文件数据。页面缓存使用虚拟内存技术，将文件数据作为页而不是面向文件系统的块来缓存。称为统一虚拟内存。

数据块缓存

■数据块按需读入内存

提供read()操作

预读:预先读取后面的数据块

■数据块使用后被缓存（日后我可能这一块还会再用到)

假设数据将会再次用到

写操作可能被缓存和延迟写入

■两种数据块缓存方式

数据块缓存(把磁盘上的东西在内存里做一个反向的缓存)

页缓存:统一缓存数据块和内存页

页缓存

■虚拟页式存储

在虚拟地址空间中虚拟页面可映射到本地外存文件中

■文件数据块的页缓存

在虚拟内存中文件数据块被映射成页

文件的读/写操作被转换成对内存的访问

可能导致缺页和/或设置为脏页

问题:页置换算法需要协调虚拟存储和页缓存间的页面数

文件系统中打开文件的数据结构

■文件描述符

·每个被打开的文件都有一个文件描述符

·文件状态信息

目录项、当前文件指针、文件操作设置等

■打开文件表

每个进程一个进程打开文件表

一个系统级的打开文件表

有文件被打开时，文件卷就不能被卸载

打开文件表

打开某一个文件就对应着相应的目录项、文件控制块和文件的内容，需要在内存当中有缓存，这些信息在内存当中的记录就构成了我们这里的系统打开文件表。这个系统打开文件表里有一些内容是各个进程是不一样的，那这些不一样的部分就构成了我们进程的打开文件表，而进程打开文件表里呢共同的部分会映射到系统的打开文件表里头，这样的话两个进程共用的部分就在打开文件表里。这就是我们这里说到的进程打开文件表和系统打开文件表

打开文件锁

■一些文件系统提供文件锁，用于协调多进程的文件访问

强制– 根据锁保持情况和访问需求确定是否拒绝访问

劝告– 进程可以查找锁的状态来决定怎么做

21.4文件分配

文件分配是指我们把哪些块，分配给一个文件来存它的数据

■文件大小

大多数文件都很小

需要对小文件提供很好的支持

块空间不能太大

■一些文件非常大

必须支持大文件(64位文件偏移）

大文件访问需要高效

文件分配

■如何表示分配给一个文件数据块的位置和顺序

■分配方式

连续分配（分配一个起点，然后连续的若干个数据块用来存在这个文件）

链式分配（在第一块里记第二块的位置一直到最后一块）

索引分配（分配一个块里面专门用来存序号，里面都有哪些块存了数据，这些块的顺序是啥样子

■指标

存储效率：外部碎片等

读写性能：访问速度

连续分配

文件头指定起始块和长度

■分配策略

·最先匹配,最佳匹配, ...

■优点

·文件读取表现好

·高效的顺序和随机访问

■缺点

·碎片！

·文件增长问题

预分配？

按需分配？

链式分配

文件以数据块链表方式存储

文件头包含了到第一块和最后一块的指针，第一块里有第二块的指针。

■优点

创建、增大、缩小很容易

没有碎片

■缺点

·无法实现真正的随机访问

·可靠性差

破坏一个链，后面的数据块就丢了

索引分配

■为每个文件创建一个索引数据块

指向文件数据块的指针列表

■文件头包含了索引数据块指针，索引块里面有每一块的序号和它们的顺序

■优点

创建、增大、缩小很容易

没有碎片

支持直接访问

■缺点

当文件很小时，存储索引的开销

如何处理大文件?加索引块

大文件的索引分配

UFS多级索引分配

■文件头包含13个指针

10个指针指向数据块

第11个指针指向索引块

第12个指针指向二级索引块

第13个指针指向三级索引块

■效果

提高了文件大小限制阀值

动态分配数据块，文件扩展很容易

小文件开销小

只为大文件分配间接数据块，大文件在访问数据块时需要大量查询

21.5空闲空间管理和冗余磁盘阵列RAID

空闲空间管理

■跟踪记录文件卷中未分配的数据块

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

位图，链表，组，计数。

空闲空间组织:位图

■用位图代表空闲数据块列表

111111111111111001110101011101111...

Di = 0表明数据块i是空闲,否则，表示已分配

■使用简单但是可能会是一个大的很大向量表

·160GB磁盘-> 40M数据块-> 5MB位图

·假定空闲空间在磁盘中均匀分布，则找到“0”之前要扫描n/r

n =磁盘上数据块的总数

r =空闲块的数目

其他空闲空间组织方式

磁盘分区

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

分区是一组柱面的集合

每个分区都可视为逻辑上独立的磁盘

磁盘上有磁头移动，是一种机械运动，所以性能比较慢。

一个典型的磁盘文件系统组织

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

左边：把一号磁盘分成A和B两个分区，每一个分区有一套自己的完整的文件系统实例，它有目录、文件，通常前面还有文件卷控制块。

右边：把多个磁盘合在一起变成一个逻辑的分区，可以扩大磁盘分区的容量，以便于能在一个分区里存更多的数据。

多磁盘管理

利用多个独立的磁盘，同时使用来提高它的性能也就说通过并行提高它的吞吐量，然后来提高它的可靠性

■使用多磁盘可改善

吞吐量(通过并行)

通过在多个磁盘上分散数据，可以改善传输率。最简单形式是，数据分散是在多个磁盘上分散每个字节的各个位，这种分散称为位级分散。

·可靠性和可用性(通过冗余)

可靠性问题的解决方法是引入冗余。存储额外信息，这是平常不需要的，但在磁盘出错时可以用来重新修补损坏信息。因此即使磁盘损坏，数据也不会损坏。

■冗余磁盘阵列(RAID, Redundant Array of Inexpensive Disks)

多种磁盘管理技术

RAID分类，如, RAID-0, RAID-1, RAID-5

■冗余磁盘阵列的实现

软件：操作系统内核的文件卷管理

硬件：RAID硬件控制器(I/O)

RAID-0：磁盘条带化

■把数据块分成多个子块，存储在独立的磁盘中

通过独立磁盘上并行数据块访问提供更大的磁盘带宽

RAID-1:磁盘镜像

■向两个磁盘写入相同内容，从任何一个读取

可靠性成倍增长

读取性能线性增加

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

■数据块级的磁盘条带化加专用奇偶校验磁盘

允许从任意一个故障磁盘中恢复

校验磁盘存储校验和，依据前四个计算校验和提高了可靠性和读写性能

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

把校验和做了一个分散，分布在N个磁盘上而不是一个磁盘上。避免对单个校验和磁盘的过度使用。

基于位和基于块的磁盘条带化

■条带化和奇偶校验按“字节”或者“位”

RAID-0/4/5:基于数据块

RAID-3:基于位

可纠正多个磁盘错误的冗余磁盘阵列

■RAID-5:每组条带块有一个奇偶校验块

允许一个磁盘错误

■RAID-6:每组条带块有两个冗余块

允许两个磁盘错误

RAID嵌套

RAID 0+1：一组磁盘被分散成条，每一条再镜像到另一条。RAID-0提供了性能，而RAID-1提供了可靠性。适用于对性能和可靠性都要求高的环境。然而，这增加了用于存储的磁盘数量，所以也更为昂贵。

RAID 1+0：磁盘先镜像，再分散。如果单个磁盘不可用，但其镜像仍如其他磁盘一样可用。