Essential Requirements：

• 必须可以存放大量信息
• 信息可以持久存储，到进程结束
• 可以支持文件并发访问

Long-Term Information Storage

• 块状存储
  • 磁盘
  • 磁带
  • 光盘
  • 闪盘
• 块级别操作
  • 读第i块
  • 写第i块

File Concept

文件的属性

文件：一组有意义的信息的集合
大小
文件名
逻辑结构（内容）：字节序列、记录序列、树
文件类型：二进制文件、ASCII文件。可执行文件、存档文件。
文件访问权限（保护信息）、文件
文件属性：如创建的时间和日期、文件大小等附加信息。

文件操作：Create、Delete、open、close、read、write、Append、Seek、Get Attributes、Set Attributes、Rename
文件物理结构：存放在块中

Directory Concept

Directory

文件夹，包含文件

一级目录系统

层次目录存储

文件多的情况下，就需要层次结构（目录树），通过这种方式，可以把文件以自然的方式分组。
树形目录结构不便于实现文件的共享，所以提出了无环图目录结构，可以用不同的文件名指向同一个文件，使得整个目录是一个有向无环图。

路径名

绝对路径名（absolute path name）
相对路径名（relative path name）：与工作目录一同使用，可以不用绝对路径，而使用相对路径。（使用相对路径检索文件可以减少磁盘I/O操作）
工作目录（working directory）

目录操作

create、delete、opendir、closedir、readdir、rename
link（多个目录中出现同一个文件，增加了该文件i-node的计数器，有时称为硬链接。Hard link、symbolic link）
unlink（删除目录项）

目录实现

File Share & Protection

File System Implementation

文件系统的类型

• Traditional：ext2
• Newest：ext3、ReiserFS、IBM JFS、xfs
• Other UNIX：minix、ext、xiafs
• FAT-12、FAT16、FAT-32、VFAT、NTFS

文件系统布局

• 主引导记录（Master Boot Record，MBR）：用来引导计算机，是引导块（boot block）
• 分区表（Partitions）
• 超级块（Superblock）包含文件系统所有关键参数，计算机启动时，或文件系统首次使用时，把超级块读入内存。
• i-node：是一个数据结构数组，每个文件一个。i-node说明了文件的方方面面信息。
  

  文件的实现

连续分配

每个文件作为一连串连续数据块存储在磁盘上。每个文件都从一个新的块开始存放。

优点：

1. 实现简单：记录每个文件只需记住第一块的磁盘地址和文件的块数
2. 读操作性能好：单个操作就可以从磁盘上读出整个文件，只需要一次，之后就不再需要寻道和旋转延迟。

缺点：随着时间推移，磁盘会变得零碎
适用于CD-ROM这样的文件系统，所有文件大小事先知道，而且后续不会再改变

链表分配

每个块的第一个字作为指向下一块的指针，块的其他部分存放数据。

优点：可以充分利用每个磁盘块
缺点：

1. 尽管顺序读文件非常方便，但是随机访问却相当缓慢（因为每次都要从文件的第一个块开始读）
2. 由于指针占用了一些字节，所以每个磁盘块中存储数据的字节数不是2的整数次幂，降低了系统的运行效率。（因为有些程序以2的整数次幂读写磁盘块，所以要读出一个完整的块，就要从两个磁盘块中获取和拼接信息，就引发了额外的开销）

在内存中采用表的链表分配

取出每个磁盘块的指针字，把它们放在内存的一个表中，就可以解决上述链表分配的两个不足。
内存中这样一个表格称为文件分配表（File Allocation Table，FAT）。

缺点：必须把整个表都存放在内存中。

i-node

给每个文件赋予一个i-node（index-node）的数据结构，其中列出了文件属性和文件块的磁盘地址。

优点：只有在对应文件打开时，i-node才在内存中。如果每个i-node占有n个字节，最多允许k个文件同时打开，那么只需要在内存中提前保留n×k个字节。

i-node的实现：给i-node偏移量，算第几块

• 同样，要会根据多层索引、混合索引（上面这个i-node）计算出文件的最大长度
• 要能自己分析访问某个数据块所需要的读磁盘次数（每次读入下一级索引块都需要一次读磁盘操作，还要看看顶级索引块 是否已经调入内存）

目录的实现

目录入口：

• File Control Block，FCB 文件控制块
• Fixed-size Variable-size

目录中提供了查找文件磁盘块所需要的信息：

• 整个文件的磁盘地址（连续分配方案）
• 第一个块的编号（两种链表分配方案）
• i-node编号

目录项中长文件名

• 长文件名(a)方法，存在文件属性后面。缺点是有空位 & 在删除后会留下空隙，久而久之造成碎片复杂。
• 长文件名(b)方法，文件项存放指向文件名的指针，文件名存储在堆中，文件名不需要再从字的边界开始，堆中不会有空隙，但是需要有好多指针。

加快文件搜索

• 散列处理文件名，将文件名存放在散列表中。但是需要维护散列表，管理复杂。
  将查找结果存入高速缓存，在查找之前，先看看高速缓存中有没有。

共享文件

共享文件的文件系统就是要给有向无环图（DAG），而不是一棵树。

硬链接（Hard link）

使用两个文件名指向同一个内部数据结构（i-node）来代表一个文件
i-node中维护一个计数器，用来统计连接到当前文件的连接数目。当数目为0时候才真正删除这个文件。

符号链接（symbolic linking）

是一类特殊的文件，这个文件包含了另一个文件的路径名（绝对路径or相对路径）
真正的文件所有者才有一个i-node的指针。当文件被删除的时候，符号连接找不到文件；而删除符号连接根本不影响该文件。
优点：能够跨越磁盘的界限，甚至可以命名在远程计算机上的文件
缺点：但是符号链接需要额外的开销，性能不如硬连接

虚拟文件系统

File System Management

Disk Space Management

块大小

根据文件系统中大量的文件大小，选择一个合适的块的大小，一般4KB？

记录空闲块

管理空闲块的方法

1. 磁盘块链表：每个块中包含尽可能多的空闲磁盘块号
2. 位图：n个块的磁盘需要n位的位图，空闲块用1表示，反之用0表示。
3. 成组连接法

磁盘配额

系统管理员分给每个用户拥有文件和块的最大数量，操作系统确保每个用户不超过分给他们的配额

文件系统备份

物理转储：从磁盘0块开始，将全部的磁盘块按顺序输出到磁带上，直到最后一块复制完毕。

• 优点：简单、极为快速
• 缺点：既不能能跳过选定目录，也无法增量转储，还不能满足恢复个人文件的请求。

逻辑转储：从一个或几个指定的目录开始，递归地转储其自给定基准日期（例如，最近一次增量转储或全面系统转储的日期）后有所更改的全部文件和目录。

• 全部转储
• 增量转储

File System Reliability

文件系统一致性

块的一致性检查
文件的一致性检查

File System Performance

高速缓存（Block cache）

或者缓冲区高速缓存（buffer cache），可以减少磁盘访问次数，提高访问速度。

算法

同页面置换算法：FIFO算法、第二次机会算法、LRU算法。

块提前读

在需要用到快之前，提前将其写入高速缓存，从而提高命中率（局部性原理）

减少磁盘臂运动

把有可能顺序存取的块放在一起，最好放在同一个柱面上，从而减少磁盘臂的移动次数。

1. i-node 放在磁盘的开始块
2. 把磁盘分为柱面组，每个组有自己的块和i-node（这样快）

File System Cases

例子，先不看了。