所有的应用程序都需要存储和检索信息。进程运行时，它能够在自己的存储空间内存储一定量的信息。然而，存储容量受虚拟地址空间大小的限制。对于一些应用程序来说，存储空间的大小是充足的，但是对于其他一些应用程序，比如航空订票系统、银行系统、企业记账系统来说，这些容量又显得太小了。
第三个问题是，通常需要很多进程在同一时刻访问这些信息。解决这种问题的方式是把这些信息单独保留在各自的进程中。
因此，对于长久存储的信息我们有三个基本需求：
磁盘(Magneticdisk)一直是用来长久保存信息的设备。近些年来，固态硬盘逐渐流行起来。
固态硬盘不仅没有易损坏的移动部件，而且能够提供快速的随机访问。相比而言，虽然磁带和光盘也被广泛使用，但是它们的性能相对较差，通常应用于备份。我们会在后面探讨磁盘，现在姑且把磁盘当作一种大小固定块的线性序列好了，并且支持如下操作
事实上磁盘支持更多的操作，但是只要有了读写操作，原则上就能够解决长期存储的问题。
然而，磁盘还有一些不便于实现的操作，特别是在有很多程序或者多用户使用的大型系统上（如服务器）。在这种情况下，很容易产生一些问题，例如
我们可以针对这些问题提出一个新的抽象-文件。进程和线程的抽象、地址空间和文件都是操作系统的重要概念。如果你能真正深入了解这三个概念，那么你就走上了成为操作系统专家的道路。
文件(Files)是由进程创建的逻辑信息单元。一个磁盘会包含几千甚至几百万个文件，每个文件是独立于其他文件的。事实上，如果你能把每个文件都看作一个独立的地址空间，那么你就可以真正理解文件的概念了。
进程能够读取已经存在的文件，并在需要时重新创建他们。存储在文件中的信息必须是持久的，这也就是说，不会因为进程的创建和终止而受影响。一个文件只能在当用户明确删除的时候才能消失。尽管读取和写入都是最基本的操作，但还有许多其他操作，我们将在下面介绍其中的一些。
文件由操作系统进行管理，有关文件的构造、命名、访问、使用、保护、实现和管理方式都是操作系统设计的主要内容。从总体上看，操作系统中处理文件的部分称为文件系统(filesystem)，这就是我们所讨论的。
从用户角度来说，用户通常会关心文件是由什么组成的，如何给文件进行命名，如何保护文件，以及可以对文件进行哪些操作等等。尽管是用链表还是用位图记录内存空闲区并不是用户所关心的主题，而这些对系统设计人员来说至关重要。下面我们就来探讨一下这些主题。
文件
文件命名
文件是一种抽象机制，它提供了一种方式用来存储信息以及在后面进行读取。可能任何一种机制最重要的特性就是管理对象的命名方式。在创建一个文件后，它会给文件一个命名。当进程终止时，文件会继续存在，并且其他进程可以使用名称访问该文件。
文件命名规则对于不同的操作系统来说是不一样的，但是所有现代操作系统都允许使用1-8个字母的字符串作为合法文件名。
某些文件区分大小写字母，而大多数则不区分。UNIX属于第一类；历史悠久的MS-DOS属于第二类（顺便说一句，尽管MS-DOS历史悠久，但MS-DOS仍在嵌入式系统中非常广泛地使用，因此它绝不是过时的）；因此，UNIX系统会有三种不同的命名文件：maria、Maria、MARIA。在MS-DOS，所有这些命名都属于相同的文件。
许多操作系统支持两部分的文件名，它们之间用.分隔开，比如文件名prog.c。原点后面的文件称为文件扩展名(fileextension)，文件扩展名通常表示文件的一些信息。例如在MS-DOS中，文件名是1-8个字符，加上1-3个字符的可选扩展名组成。在UNIX中，如果有扩展名，那么扩展名的长度将由用户来决定，一个文件甚至可以包括两个或更多的扩展名，例如homepage.html.zip，html表示一个web网页而.zip表示文件homepage.html已经采用zip程序压缩完成。一些常用的文件扩展名以及含义如下图所示
扩展名含义bak备份文件cc源程序文件gif符合图形交换格式的图像文件hlp帮助文件htmlWWW超文本标记语言文档jpg符合JPEG编码标准的静态图片mp3符合MP3音频编码格式的音乐文件mpg符合MPEG编码标准的电影o目标文件（编译器输出格式，尚未链接）pdfpdf格式的文件psPostScript文件tex为TEX格式化程序准备的输入文件txt文本文件zip压缩文件
在UNIX系统中，文件扩展名只是一种约定，操作系统并不强制采用。
名为file.txt的文件是文本文件，这个文件名更多的是提醒所有者，而不是给计算机传递信息。但是另一方面，C编译器可能要求它编译的文件以.c结尾，否则它会拒绝编译。然而，操作系统并不关心这一点。
对于可以处理多种类型的程序，约定就显得及其有用。例如C编译器可以编译、链接多种文件，包括C文件和汇编语言文件。这时扩展名就很有必要，编译器利用它们区分哪些是C文件，哪些是汇编文件，哪些是其他文件。因此，扩展名对于编译器判断哪些是C文件，哪些是汇编文件以及哪些是其他文件变得至关重要。
文件结构
文件的构造有多种方式。下图列出了常用的三种构造方式
上图中的a是一种无结构的字节序列，操作系统不关心序列的内容是什么，操作系统能看到的就是字节(bytes)。其文件内容的任何含义只在用户程序中进行解释。UNIX和Windows都采用这种办法。
把文件看成字节序列提供了最大的灵活性。用户程序可以向文件中写任何内容，并且可以通过任何方便的形式命名。操作系统不会为为用户写入内容提供帮助，当然也不会干扰阻塞你。对于想做特殊操作的用户来说，后者是十分重要的。所有的UNIX版本（包括Linux和OSX）和Windows都使用这种文件模型。
图b表示在文件结构上的第一步改进。在这个模型中，文件是具有固定长度记录的序列，每个记录都有其内部结构。把文件作为记录序列的核心思想是：读操作返回一个记录，而写操作重写或者追加一个记录。第三种文件结构如上图c所示。在这种组织结构中，文件由一颗记录树构成，记录树的长度不一定相同，每个记录树都在记录中的固定位置包含一个key字段。这棵树按key进行排序，从而可以对特定的key进行快速查找。
在记录树的结构中，可以取出下一个记录，但是最关键的还是根据key搜索指定的记录。如上图c所示，用户可以读出指定的pony记录，而不必关心记录在文件中的确切位置。用户也可以在文件中添加新的记录。但是用户不能决定添加到何处位置，添加到何处位置是由操作系统决定的。
文件类型
很多操作系统支持多种文件类型。例如，UNIX（同样包括OSX）和Windows都具有常规的文件和目录。除此之外，UNIX还具有字符特殊文件(characterspecialfile)和块特殊文件(blockspecialfile)。常规文件(Regularfiles)是包含有用户信息的文件。用户一般使用的文件大都是常规文件，常规文件一般包括可执行文件、文本文件、图像文件，从常规文件读取数据或将数据写入时，内核会根据文件系统的规则执行操作，写入可能被延迟，记录日志或者接受其他操作。
字符特殊文件和输入/输出有关，用于串行I/O类设备，如终端、打印机、网络等。块特殊文件用于磁盘类设备。我们主要讨论的是常规文件。
常规文件一般分为ASCII码文件或者二进制文件。ASCII码文件由文本组成。在一些系统中，每行都会用回车符结束（ASCII码是13，控制字符CR，转义字符\r。），另外一些则会使用换行符（ASCII码是10，控制字符LF，转义字符\n）。一些系统（比如Windows）两者都会使用。
ASCII文件的优点在于显示和打印，还可以用任何文本编辑器进行编辑。进一步来说，如果许多应用程序使用ASCII码作为输入和输出，那么很容易就能够把多个程序连接起来，一个程序的输出可能是另一个程序的输入，就像管道一样。
其他与ASCII不同的是二进制文件。打印出来的二进制文件是无法理解的。下面是一个二进制文件的格式，它取自早期的UNIX。尽管从技术上来看这个文件只是字节序列，但是操作系统只有在文件格式正确的情况下才会执行。
这个文件有五个段：文件头、正文、数据、重定位位和符号表。文件头以魔数(magicnumber)为开始，表明这个文件是一个可执行文件（以防止意外执行非此格式的文件）。然后是文件各个部分的大小，开始执行的标志以及一些标志位。程序本身的正文和数据在文件头后面，他们被加载到内存中或者重定位会根据重定位位进行判断。符号表则用于调试。
二进制文件的另外一种形式是存档文件，它由已编译但没有链接的库过程（模块）组合而成。每个文件都以模块头开始，其中记录了名称、创建日期、所有者、保护码和文件大小。和可执行文件一样，模块头也都是二进制数，将它们复制到打印机将会产生乱码。
什么是make程序？在软件发展过程中，make程序是一个自动编译的工具，它通过读取称为Makefiles的文件来自动从源代码构建可执行程序和库，该文件指定了如何导出目标程序。尽管集成开发环境和特定语言的编译器功能也可以用于管理构建过程，但Make仍被广泛使用，尤其是在Unix和类似Unix的操作系统中使用。
当程序从文件中读写数据时，请求会转到内核处理程序(kerneldriver)。如果文件是常规文件，则数据由文件系统驱动程序处理，并且通常存储在磁盘或其他存储介质上的某块区域中，从文件中读取的数据就是之前在该位置写入的数据。
当数据读取或写入到设备文件时，请求会被设备驱动程序处理。每个设备文件都有一个关联的编号，该编号标示要使用的设备驱动程序。设备处理数据的工作是它自己的事儿。
目录(Directories)是管理文件系统结构的系统文件。它是用于在计算机上存储文件的位置。目录位于分层文件系统中，例如Linux，MS-DOS和UNIX。
它显示所有本地和子目录（例如，cdn目录中的big目录）。当前目录是C盘驱动器的根目录。之所以称为根目录，是因为该目录下没有任何内容，而其他目录都在该目录下分支。
文件访问
早期的操作系统只有一种访问方式：序列访问(sequentialaccess)。在这些系统中，进程可以按照顺序读取所有的字节或文件中的记录，但是不能跳过并乱序执行它们。顺序访问文件是可以返回到起点的，需要时可以多次读取该文件。当存储介质是磁带而不是磁盘时，顺序访问文件很方便。
在使用磁盘来存储文件时，可以不按照顺序读取文件中的字节或者记录，或者按照关键字而不是位置来访问记录。这种能够以任意次序进行读取的称为随机访问文件(randomaccessfile)。许多应用程序都需要这种方式。
有两种方法可以表示从何处开始读取文件。第一种方法是直接使用read从头开始读取。另一种是用一个特殊的seek操作设置当前位置，在seek操作后，从这个当前位置顺序地开始读文件。UNIX和Windows使用的是后面一种方式。
文件属性
没有一个系统能够同时具有上面所有的属性，但每个属性都在某个系统中采用。
前面四个属性（保护，口令，创建者，所有者）与文件保护有关，它们指出了谁可以访问这个文件，谁不能访问这个文件。
保护（FileProtection）：用于保护计算机上有价值数据的方法。文件保护是通过密码保护文件或者仅仅向特定用户或组提供权限来实现。
在一些系统中，用户必须给出口令才能访问文件。标志(flags)是一些位或者短属性能够控制或者允许特定属性。
记录长度(record-length)、键的位置(key-position)和键的长度(key-length)等字段只能出现在用关键字查找记录的文件中。它们提供了查找关键字所需要的信息。
当前大小字段指出了当前的文件大小，一些旧的大型机操作系统要求在创建文件时指定文件最大值，以便让操作系统提前保留最大存储值。但是一些服务器和个人计算机却不用设置此功能。
文件操作
使用文件的目的是用来存储信息并方便以后的检索。对于存储和检索，不同的系统提供了不同的操作。以下是与文件有关的最常用的一些系统调用：
目录
文件系统通常提供目录(directories)或者文件夹(folders)用于记录文件的位置，在很多系统中目录本身也是文件，下面我们会讨论关于文件，他们的组织形式、属性和可以对文件进行的操作。
一级目录系统
目录系统最简单的形式是有一个能够包含所有文件的目录。这种目录被称为根目录(rootdirectory)，由于根目录的唯一性，所以其名称并不重要。在最早期的个人计算机中，这种系统很常见，部分原因是因为只有一个用户。下面是一个单层目录系统的例子
该目录中有四个文件。这种设计的优点在于简单，并且能够快速定位文件，毕竟只有一个地方可以检索。这种目录组织形式现在一般用于简单的嵌入式设备（如数码相机和某些便携式音乐播放器）上使用。
层次目录系统
对于简单的应用而言，一般都用单层目录方式，但是这种组织形式并不适合于现代计算机，因为现代计算机含有成千上万个文件和文件夹。如果都放在根目录下，查找起来会非常困难。为了解决这一问题，出现了层次目录系统(HierarchicalDirectorySystems)，也称为目录树。通过这种方式，可以用很多目录把文件进行分组。进而，如果多个用户共享同一个文件服务器，比如公司的网络系统，每个用户可以为自己的目录树拥有自己的私人根目录。这种方式的组织结构如下
根目录含有目录A、B和C，分别属于不同的用户，其中两个用户个字创建了子目录。用户可以创建任意数量的子目录，现代文件系统都是按照这种方式组织的。
路径名
当目录树组织文件系统时，需要有某种方法指明文件名。常用的方法有两种，第一种方式是每个文件都会用一个绝对路径名(absolutepathname)，它由根目录到文件的路径组成。举个例子，/usr/ast/mailbox意味着根目录包含一个子目录usr，usr下面包含了一个mailbox。绝对路径名总是以/开头，并且是唯一的。在UNIX中，路径的组件由/分隔。在Windows中，分隔符为\。在MULTICS中，它是>。因此，在这三个系统中，相同的路径名将被编写如下
Windows\usr\ast\mailboxUNIX/usr/ast/mailboxMULTICS>usr>ast>mailbox
不论使用哪种方式，如果路径名的第一个字符是分隔符，那就是绝对路径。
另外一种指定文件名的方法是相对路径名(relativepathname)。它常常和工作目录(workingdirectory)（也称作当前目录(currentdirectory)）一起使用。用户可以指定一个目录作为当前工作目录。例如，如果当前目录是/usr/ast，那么绝对路径/usr/ast/mailbox可以直接使用mailbox来引用。也就是说，如果工作目录是/usr/ast，则UNIX命令
cp/usr/ast/mailbox/usr/ast/mailbox.bak
和命令
cpmailboxmailbox.bak
具有相同的含义。相对路径通常情况下更加方便和简洁。而它实现的功能和绝对路径安全相同。
一些程序需要访问某个特定的文件而不必关心当前的工作目录是什么。在这种情况下，应该使用绝对路径名。
支持层次目录结构的大多数操作系统在每个目录中有两个特殊的目录项.和..，读作dot和dotdot。dot指的是当前目录，dotdot指的是其父目录（在根目录中例外，在根目录中指向自己）。可以参考下面的进程树来查看如何使用。
一个进程的工作目录是/usr/ast，它可采用..沿树向上，例如，可用命令
cp../lib/dictionary.
把文件usr/lib/dictionary复制到自己的目录下，第一个路径告诉系统向上找（到usr目录），然后向下到lib目录，找到dictionary文件
第二个参数.指定当前的工作目录，当cp命令用目录名作为最后一个参数时，则把全部的文件复制到该目录中。当然，对于上述复制，键入
cp/usr/lib/dictionary.
是更常用的方法。用户这里采用.可以避免键入两次dictionary。无论如何，键入
cp/usr/lib/dictionarydictionary
也可正常工作，就像键入
cp/usr/lib/dictionary/usr/lib/dictionary
一样。所有这些命令都能够完成同样的工作。
目录操作
不同文件中管理目录的系统调用的差别比管理文件的系统调用差别大。为了了解这些系统调用有哪些以及它们怎样工作，下面给出一个例子（取自UNIX）。
文件系统的实现
在对文件有了基本认识之后，现在是时候把目光转移到文件系统的实现上了。之前用户关心的一直都是文件是怎样命名的、可以进行哪些操作、目录树是什么，如何找到正确的文件路径等问题。而设计人员关心的是文件和目录是怎样存储的、磁盘空间是如何管理的、如何使文件系统得以流畅运行的问题，下面我们就来一起讨论一下这些问题。
文件系统布局
文件系统存储在磁盘中。大部分的磁盘能够划分出一到多个分区，叫做磁盘分区(diskpartitioning)或者是磁盘分片(diskslicing)。每个分区都有独立的文件系统，每块分区的文件系统可以不同。磁盘的0号分区称为主引导记录(MasterBootRecord,MBR)，用来引导(boot)计算机。在MBR的结尾是分区表(partitiontable)。每个分区表给出每个分区由开始到结束的地址。系统管理员使用一个称为分区编辑器的程序来创建，调整大小，删除和操作分区。这种方式的一个缺点是很难适当调整分区的大小，导致一个分区具有很多可用空间，而另一个分区几乎完全被分配。
MBR可以用在DOS、MicrosoftWindows和Linux操作系统中。从2010年代中期开始，大多数新计算机都改用GUID分区表（GPT）分区方案。
下面是一个用GParted进行分区的磁盘，表中的分区都被认为是活动的(active)。
当计算机开始引导boot时，BIOS读入并执行MBR。
引导块
MBR做的第一件事就是确定活动分区，读入它的第一个块，称为引导块(bootblock)并执行。引导块中的程序将加载分区中的操作系统。为了一致性，每个分区都会从引导块开始，即使引导块不包含操作系统。引导块占据文件系统的前4096个字节，从磁盘上的字节偏移量0开始。引导块可用于启动操作系统。
在计算机中，引导就是启动计算机的过程，它可以通过硬件（例如按下电源按钮）或者软件命令的方式来启动。开机后，电脑的CPU还不能执行指令，因为此时没有软件在主存中，所以一些软件必须先被加载到内存中，然后才能让CPU开始执行。也就是计算机开机后，首先会进行软件的装载过程。
重启电脑的过程称为重新引导(rebooting)，从休眠或睡眠状态返回计算机的过程不涉及启动。
除了从引导块开始之外，磁盘分区的布局是随着文件系统的不同而变化的。通常文件系统会包含一些属性，如下
超级块
紧跟在引导块后面的是超级块(Superblock)，超级块的大小为4096字节，从磁盘上的字节偏移4096开始。超级块包含文件系统的所有关键参数
文件系统的大小文件系统中的数据块数指示文件系统状态的标志分配组大小
在计算机启动或者文件系统首次使用时，超级块会被读入内存。
空闲空间块
接着是文件系统中空闲块的信息，例如，可以用位图或者指针列表的形式给出。
BitMap位图或者Bitvector位向量
位图或位向量是一系列位或位的集合，其中每个位对应一个磁盘块，该位可以采用两个值：0和1，0表示已分配该块，而1表示一个空闲块。下图中的磁盘上给定的磁盘块实例（分配了绿色块）可以用16位的位图表示为：0000111000000110。
使用链表进行管理
在这种方法中，空闲磁盘块链接在一起，即一个空闲块包含指向下一个空闲块的指针。第一个磁盘块的块号存储在磁盘上的单独位置，也缓存在内存中。
碎片
这里不得不提一个叫做碎片(fragment)的概念，也称为片段。一般零散的单个数据通常称为片段。磁盘块可以进一步分为固定大小的分配单元，片段只是在驱动器上彼此不相邻的文件片段。如果你不理解这个概念就给你举个例子。比如你用Windows电脑创建了一个文件，你会发现这个文件可以存储在任何地方，比如存在桌面上，存在磁盘中的文件夹中或者其他地方。你可以打开文件，编辑文件，删除文件等等。你可能以为这些都在一个地方发生，但是实际上并不是，你的硬盘驱动器可能会将文件中的一部分存储在一个区域内，另一部分存储在另外一个区域，在你打开文件时，硬盘驱动器会迅速的将文件的所有部分汇总在一起，以便其他计算机系统可以使用它。
inode
然后在后面是一个inode(indexnode)，也称作索引节点。它是一个数组的结构，每个文件有一个inode，inode非常重要，它说明了文件的方方面面。每个索引节点都存储对象数据的属性和磁盘块位置
有一种简单的方法可以找到它们ls-lai命令。让我们看一下根文件系统：
inode节点主要包括了以下信息
文件分为两部分，索引节点和块。一旦创建后，每种类型的块数是固定的。你不能增加分区上inode的数量，也不能增加磁盘块的数量。
紧跟在inode后面的是根目录，它存放的是文件系统目录树的根部。最后，磁盘的其他部分存放了其他所有的目录和文件。
文件的实现
最重要的问题是记录各个文件分别用到了哪些磁盘块。不同的系统采用了不同的方法。下面我们会探讨一下这些方式。分配背后的主要思想是有效利用文件空间和快速访问文件，主要有三种分配方案
连续分配链表分配索引分配
连续分配
最简单的分配方案是把每个文件作为一连串连续数据块存储在磁盘上。因此，在具有1KB块的磁盘上，将为50KB文件分配50个连续块。
上面展示了40个连续的内存块。从最左侧的0块开始。初始状态下，还没有装载文件，因此磁盘是空的。接着，从磁盘开始处（块0）处开始写入占用4块长度的内存A。然后是一个占用6块长度的内存B，会直接在A的末尾开始写。
注意每个文件都会在新的文件块开始写，所以如果文件A只占用了3又1/2个块，那么最后一个块的部分内存会被浪费。在上面这幅图中，总共展示了7个文件，每个文件都会从上个文件的末尾块开始写新的文件块。
连续的磁盘空间分配有两个优点。
因此，连续的空间分配具有实现简单、高性能的特点。
这里有两个文件D和F被删除了。当删除一个文件时，此文件所占用的块也随之释放，就会在磁盘空间中留下一些空闲块。磁盘并不会在这个位置挤压掉空闲块，因为这会复制空闲块之后的所有文件，可能会有上百万的块，这个量级就太大了。
刚开始的时候，这个碎片不是问题，因为每个新文件都会在之前文件的结尾处进行写入。然而，磁盘最终会被填满，因此要么压缩磁盘、要么重新使用空闲块的空间。压缩磁盘的开销太大，因此不可行；后者会维护一个空闲列表，这个是可行的。但是这种情况又存在一个问题，为空闲块匹配合适大小的文件，需要知道该文件的最终大小。
想象一下这种设计的结果会是怎样的。用户启动word进程创建文档。应用程序首先会询问最终创建的文档会有多大。这个问题必须回答，否则应用程序就不会继续执行。如果空闲块的大小要比文件的大小小，程序就会终止。因为所使用的磁盘空间已经满了。那么现实生活中，有没有使用连续分配内存的介质出现呢？
CD-ROM就广泛的使用了连续分配方式。
CD-ROM（CompactDiscRead-OnlyMemory）即只读光盘，也称作只读存储器。是一种在电脑上使用的光碟。这种光碟只能写入数据一次，信息将永久保存在光碟上，使用时通过光碟驱动器读出信息。
然而DVD的情况会更加复杂一些。原则上，一个90分钟的电影能够被编码成一个独立的、大约4.5GB的文件。但是文件系统所使用的UDF(UniversalDiskFormat)格式，使用一个30位的数来代表文件长度，从而把文件大小限制在1GB。所以，DVD电影一般存储在3、4个连续的1GB空间内。这些构成单个电影中的文件块称为扩展区(extends)。
就像我们反复提到的，历史总是惊人的相似，许多年前，连续分配由于其简单和高性能被实际使用在磁盘文件系统中。后来由于用户不希望在创建文件时指定文件的大小，于是放弃了这种想法。但是随着CD-ROM、DVD、蓝光光盘等光学介质的出现，连续分配又流行起来。从而得出结论，技术永远没有过时性，现在看似很老的技术，在未来某个阶段可能又会流行起来。
链表分配
第二种存储文件的方式是为每个文件构造磁盘块链表，每个文件都是磁盘块的链接列表，就像下面所示
每个块的第一个字作为指向下一块的指针，块的其他部分存放数据。如果上面这张图你看的不是很清楚的话，可以看看整个的链表分配方案
与连续分配方案不同，这一方法可以充分利用每个磁盘块。除了最后一个磁盘块外，不会因为磁盘碎片而浪费存储空间。同样，在目录项中，只要存储了第一个文件块，那么其他文件块也能够被找到。
另一方面，在链表的分配方案中，尽管顺序读取非常方便，但是随机访问却很困难（这也是数组和链表数据结构的一大区别）。
还有一个问题是，由于指针会占用一些字节，每个磁盘块实际存储数据的字节数并不再是2的整数次幂。虽然这个问题并不会很严重，但是这种方式降低了程序运行效率。许多程序都是以长度为2的整数次幂来读写磁盘，由于每个块的前几个字节被指针所使用，所以要读出一个完成的块大小信息，就需要当前块的信息和下一块的信息拼凑而成，因此就引发了查找和拼接的开销。
使用内存表进行链表分配
由于连续分配和链表分配都有其不可忽视的缺点。所以提出了使用内存中的表来解决分配问题。取出每个磁盘块的指针字，把它们放在内存的一个表中，就可以解决上述链表的两个不足之处。下面是一个例子
上图表示了链表形成的磁盘块的内容。这两个图中都有两个文件，文件A依次使用了磁盘块地址4、7、2、10、12，文件B使用了6、3、11和14。也就是说，文件A从地址4处开始，顺着链表走就能找到文件A的全部磁盘块。同样，从第6块开始，顺着链走到最后，也能够找到文件B的全部磁盘块。你会发现，这两个链表都以不属于有效磁盘编号的特殊标记（-1）结束。内存中的这种表格称为文件分配表(FileApplicationTable,FAT)。
使用这种组织方式，整个块都可以存放数据。进而，随机访问也容易很多。虽然仍要顺着链在内存中查找给定的偏移量，但是整个链都存放在内存中，所以不需要任何磁盘引用。与前面的方法相同，不管文件有多大，在目录项中只需记录一个整数（起始块号），按照它就可以找到文件的全部块。
最后一个记录各个文件分别包含哪些磁盘块的方法是给每个文件赋予一个称为inode(索引节点)的数据结构，每个文件都与一个inode进行关联，inode由整数进行标识。
下面是一个简单例子的描述。
给出inode的长度，就能够找到文件中的所有块。
相对于在内存中使用表的方式而言，这种机制具有很大的优势。即只有在文件打开时，其inode才会在内存中。如果每个inode需要n个字节，最多k个文件同时打开，那么inode占有总共打开的文件是kn字节。仅需预留这么多空间。
这个数组要比我们上面描述的FAT(文件分配表)占用的空间小的多。原因是用于保存所有磁盘块的链接列表的表的大小与磁盘本身成正比。如果磁盘有n个块，那么这个表也需要n项。随着磁盘空间的变大，那么该表也随之线性增长。相反，inode需要节点中的数组，其大小和可能需要打开的最大文件个数成正比。它与磁盘是100GB、4000GB还是10000GB无关。
inode有一个问题是如果每个节点都会有固定大小的磁盘地址，那么文件增长到所能允许的最大容量外会发生什么？一个解决方案是最后一个磁盘地址不指向数据块，而是指向一个包含额外磁盘块地址的地址，如上图所示。一个更高级的解决方案是：有两个或者更多包含磁盘地址的块，或者指向其他存放地址的磁盘块的磁盘块。Windows的NTFS文件系统采用了相似的方法，所不同的仅仅是大的inode也可以表示小的文件。
NTFS的全称是NewTechnologyFileSystem，是微软公司开发的专用系统文件，NTFS取代FAT(文件分配表)和HPFS(高性能文件系统)，并在此基础上进一步改进。例如增强对元数据的支持，使用更高级的数据结构以提升性能、可靠性和磁盘空间利用率等。
目录的实现
文件只有打开后才能够被读取。在文件打开后，操作系统会使用用户提供的路径名来定位磁盘中的目录。目录项提供了查找文件磁盘块所需要的信息。根据系统的不同，提供的信息也不同，可能提供的信息是整个文件的磁盘地址，或者是第一个块的数量（两个链表方案）或inode的数量。不过不管用那种情况，目录系统的主要功能就是将文件的ASCII码的名称映射到定位数据所需的信息上。
在这种简单的设计中，目录有一个固定大小的目录项列表，每个文件对应一项，其中包含一个固定长度的文件名，文件属性的结构体以及用以说明磁盘块位置的一个或多个磁盘地址。
对于采用inode的系统，会把inode存储在属性中而不是目录项中。在这种情况下，目录项会更短：仅仅只有文件名称和inode数量。这种方式如下所示
到目前为止，我们已经假设文件具有较短的、固定长度的名字。在MS-DOS中，具有1-8个字符的基本名称和1-3个字符的可拓展名称。在UNIX版本7中，文件有1-14个字符，包括任何拓展。然而，几乎所有的现代操作系统都支持可变长度的扩展名。这是如何实现的呢？
最简单的方式是给予文件名一个长度限制，比如255个字符，然后使用上图中的设计，并为每个文件名保留255个字符空间。这种处理很简单，但是浪费了大量的目录空间，因为只有很少的文件会有那么长的文件名称。所以，需要一种其他的结构来处理。
上图是SPARC机器使用正序放置。
处理机中的一串字符存放的顺序有正序(big-endian)和逆序(little-endian)之分。正序存放的就是高字节在前低字节在后，而逆序存放的就是低字节在前高字节在后。
这个例子中，有三个文件，分别是project-budget、personnel和foo。每个文件名以一个特殊字符（通常是0）结束，用矩形中的叉进行表示。为了使每个目录项从字的边界开始，每个文件名被填充成整数个字，如下图所示
这个方法的缺点是当文件被移除后，就会留下一块固定长度的空间，而新添加进来的文件大小不一定和空闲空间大小一致。
这个问题与我们上面探讨的连续磁盘文件的问题是一样的，由于整个目录在内存中，所以只有对目录进行紧凑拼接操作才可节省空间。另一个问题是，一个目录项可能会分布在多个页上，在读取文件名时可能发生缺页中断。
处理可变长度文件名字的另外一种方法是，使目录项自身具有固定长度，而将文件名放在目录末尾的堆栈中。如上图所示的这种方式。这种方法的优点是当目录项被移除后，下一个文件将能够正常匹配移除文件的空间。当然，必须要对堆进行管理，因为在处理文件名的时候也会发生缺页异常。
到目前为止的所有设计中，在需要查找文件名时，所有的方案都是线性的从头到尾对目录进行搜索。对于特别长的目录，线性搜索的效率很低。提高文件检索效率的一种方式是在每个目录上使用哈希表(hashtable)，也叫做散列表。我们假设表的大小为n，在输入文件名时，文件名被散列在0和n-1之间，例如，它被n除，并取余数。或者对构成文件名字的字求和或类似某种方法。
无论采用哪种方式，在添加一个文件时都要对与散列值相对应的散列表进行检查。如果没有使用过，就会将一个指向目录项的指针指向这里。文件目录项紧跟着哈希表后面。如果已经使用过，就会构造一个链表（这种构造方式是不是和HashMap使用的数据结构一样？），链表的表头指针存放在表项中，并通过哈希值将所有的表项相连。
查找文件的过程和添加类似，首先对文件名进行哈希处理，在哈希表中查找是否有这个哈希值，如果有的话，就检查这条链上所有的哈希项，查看文件名是否存在。如果哈希不在链上，那么文件就不在目录中。
使用哈希表的优势是查找非常迅速，缺点是管理起来非常复杂。只有在系统中会有成千上万个目录项存在时，才会考虑使用散列表作为解决方案。
另外一种在大量目录中加快查找指令目录的方法是使用缓存，缓存查找的结果。在开始查找之前，会首先检查文件名是否在缓存中。如果在缓存中，那么文件就能立刻定位。当然，只有在较少的文件下进行多次查找，缓存才会发挥最大功效。
共享文件
当多个用户在同一个项目中工作时，他们通常需要共享文件。如果这个共享文件同时出现在多个用户目录下，那么他们协同工作起来就很方便。下面的这张图我们在上面提到过，但是有一个更改的地方，就是C的一个文件也出现在了B的目录下。
如果按照如上图的这种组织方式而言，那么B的目录与该共享文件的联系称为链接(link)。那么文件系统现在就是一个有向无环图(DirectedAcyclicGraph,简称DAG)，而不是一棵树了。
在图论中，如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个有向无环图，我们不会在此着重探讨关于图论的东西，大家可以自行google。
将文件系统组织成为有向无环图会使得维护复杂化，但也是必须要付出的代价。
共享文件很方便，但这也会带来一些问题。如果目录中包含磁盘地址，则当链接文件时，必须把C目录中的磁盘地址复制到B目录中。如果B或者C随后又向文件中添加内容，则仅在执行追加的用户的目录中显示新写入的数据块。这种变更将会对其他用户不可见，从而破坏了共享的目的。
有两种方案可以解决这种问题。
上面的每一种方法都有各自的缺点，在第一种方式中，B链接到共享文件时，inode记录文件的所有者为C。建立一个链接并不改变所有关系，如下图所示。
第一开始的情况如图a所示，此时C的目录的所有者是C，当目录B链接到共享文件时，并不会改变C的所有者关系，只是把计数+1，所以此时系统知道目前有多少个目录指向这个文件。然后C尝试删除这个文件，这个时候有个问题，如果C把文件移除并清除了inode的话，那么B会有一个目录项指向无效的节点。如果inode以后分配给另一个文件，则B的链接指向一个错误的文件。系统通过inode可知文件仍在被引用，但是没有办法找到该文件的全部目录项以删除它们。指向目录的指针不能存储在inode中，原因是有可能有无数个这样的目录。
所以我们能做的就是删除C的目录项，但是将inode保留下来，并将计数设置为1，如上图c所示。c表示的是只有B有指向该文件的目录项，而该文件的前者是C。如果系统进行记账操作的话，那么C将继续为该文件付账直到B决定删除它，如果是这样的话，只有到计数变为0的时刻，才会删除该文件。
对于符号链接，以上问题不会发生，只有真正的文件所有者才有一个指向inode的指针。链接到该文件上的用户只有路径名，没有指向inode的指针。当文件所有者删除文件时，该文件被销毁。以后若试图通过符号链接访问该文件将会失败，因为系统不能找到该文件。删除符号链接不会影响该文件。
符号链接的问题是需要额外的开销。必须读取包含路径的文件，然后要一个部分接一个部分地扫描路径，直到找到inode。这些操作也许需要很多次额外的磁盘访问。此外，每个符号链接都需要额外的inode，以及额外的一个磁盘块用于存储路径，虽然如果路径名很短，作为一种优化，系统可以将它存储在inode中。符号链接有一个优势，即只要简单地提供一个机器的网络地址以及文件在该机器上驻留的路径，就可以连接全球任何地方机器上的文件。
还有另一个由链接带来的问题，在符号链接和其他方式中都存在。如果允许链接，文件有两个或多个路径。查找一指定目录及其子目录下的全部文件的程序将多次定位到被链接的文件。例如，一个将某一目录及其子目录下的文件转存到磁带上的程序有可能多次复制一个被链接的文件。进而，如果接着把磁带读入另一台机器，除非转出程序具有智能，否则被链接的文件将被两次复制到磁盘上，而不是只是被链接起来。
日志结构文件系统
这些因素结合起来意味着许多系统文件中出现性能瓶颈。为此，Berkeley设计了一种全新的文件系统，试图缓解这个问题，这个文件系统就是日志结构文件系统(Log-structuredFileSystem,LFS)。
日志结构文件系统由Rosenblum和Ousterhout于90年代初引入，旨在解决以下问题。
另一方面，当时的文件系统不论是UNIX还是FFS，都有大量的随机读写（在FFS中创建一个新文件至少需要5次随机写），因此成为整个系统的性能瓶颈。同时因为Pagecache的存在，作者认为随机读不是主要问题：随着越来越大的内存，大部分的读操作都能被cache，因此LFS主要要解决的是减少对硬盘的随机写操作。
日志结构文件系统主要使用四种数据结构：Inode、InodeMap、Segment、SegmentUsageTable。
到目前为止，所有写入最初都缓存在内存中，并且追加在日志末尾，所有缓存的写入都定期在单个段中写入磁盘。所以，现在打开文件也就意味着用映射定位文件的索引节点。一旦inode被定位后，磁盘块的地址就能够被找到。所有这些块本身都将位于日志中某处的分段中。
真实情况下的磁盘容量是有限的，所以最终日志会占满整个磁盘空间，这种情况下就会出现没有新的磁盘块被写入到日志中。幸运的是，许多现有段可能具有不再需要的块。例如，如果一个文件被覆盖了，那么它的inode将被指向新的块，但是旧的磁盘块仍在先前写入的段中占据着空间。
为了处理这个问题，LFS有一个清理(clean)线程，它会循环扫描日志并对日志进行压缩。首先，通过查看日志中第一部分的信息来查看其中存在哪些索引节点和文件。它会检查当前inode的映射来查看inode是否在当前块中，是否仍在被使用。如果不是，该信息将被丢弃。如果仍然在使用，那么inode和块就会进入内存等待写回到下一个段中。然后原来的段被标记为空闲，以便日志可以用来存放新的数据。用这种方法，清理线程遍历日志，从后面移走旧的段，然后将有效的数据放入内存等待写到下一个段中。由此一来整个磁盘会形成一个大的环形缓冲区，写线程将新的段写在前面，而清理线程则清理后面的段。
日志文件系统
虽然日志结构系统的设计很优雅，但是由于它们和现有的文件系统不相匹配，因此还没有广泛使用。不过，从日志文件结构系统衍生出来一种新的日志系统，叫做日志文件系统，它会记录系统下一步将要做什么的日志。微软的NTFS文件系统、Linux的ext3就使用了此日志。OSX将日志系统作为可供选项。为了看清它是如何工作的，我们下面讨论一个例子，比如移除文件，这个操作在UNIX中需要三个步骤完成：
在Windows中，也存在类似的步骤。不存在系统崩溃时，这些步骤的执行顺序不会带来问题。但是一旦系统崩溃，就会带来问题。假如在第一步完成后系统崩溃。inode和文件块将不会被任何文件获得，也不会再分配；它们只存在于废物池中的某个地方，并因此减少了可利用的资源。如果崩溃发生在第二步后，那么只有磁盘块会丢失。日志文件系统保留磁盘写入期间对文件系统所做的更改的日志或日志，该日志可用于快速重建可能由于系统崩溃或断电等事件而发生的损坏。
一般文件系统崩溃后必须运行fsck（文件系统一致性检查）实用程序。
为了让日志能够正确工作，被写入的日志操作必须是幂等的(idempotent)，它意味着只要有必要，它们就可以重复执行很多次，并不会带来破坏。像操作更新位表并标记inodek或者块n是空闲的可以重复执行任意次。同样地，查找一个目录并且删除所有叫foobar的项也是幂等的。相反，把从inodek新释放的块加入空闲表的末端不是幂等的，因为它们可能已经被释放并存放在那里了。
为了增加可靠性，一个文件系统可以引入数据库中原子事务(atomictransaction)的概念。使用这个概念，一组动作可以被界定在开始事务和结束事务操作之间。这样，文件系统就会知道它必须完成所有的动作，要么就一个不做。
虚拟文件系统
即使在同一台计算机上或者在同一个操作系统下，都会使用很多不同的文件系统。Windows中的主要文件系统是NTFS文件系统，但不是说Windows只有NTFS操作系统，它还有一些其他的例如旧的FAT-32或FAT-16驱动器或分区，其中包含仍需要的数据，闪存驱动器，旧的CD-ROM或DVD（每个都有自己的独特文件系统）。Windows通过指定不同的盘符来处理这些不同的文件系统，比如C:，D:等。盘符可以显示存在也可以隐式存在，如果你想找指定位置的文件，那么盘符是显示存在；如果当一个进程打开一个文件时，此时盘符是隐式存在，所以Windows知道向哪个文件系统传递请求。
相比之下，UNIX采用了一种不同的方式，即UNIX把多种文件系统整合到一个统一的结构中。一个Linux系统可以使用ext2作为根文件系统，ext3分区装载在/usr下，另一块采用ReiserFS文件系统的硬盘装载到/home下，以及一个ISO9660的CD-ROM临时装载到/mnt下。从用户的观点来看，只有一个文件系统层级，但是事实上它们是由多个文件系统组合而成，对于用户和进程是不可见的。
UNIX操作系统使用一种虚拟文件系统(VirtualFileSystem,VFS)来尝试将多种文件系统构成一个有序的结构。关键的思想是抽象出所有文件系统都共有的部分，并将这部分代码放在一层，这一层再调用具体文件系统来管理数据。下面是一个VFS的系统结构
VFS也有一个对于实际文件的下层接口，就是上图中标记为VFS的接口。这个接口包含许多功能调用，这样VFS可以使每一个文件系统完成任务。因此，要创建一个可以与VFS一起使用的新文件系统，新文件系统的设计者必须确保它提供了VFS要求的功能。一个明显的例子是从磁盘读取特定的块，然后将其放入文件系统的缓冲区高速缓存中，然后返回指向该块的指针的函数。因此，VFS具有两个不同的接口：上一个到用户进程，下一个到具体文件系统。
当系统启动时，根文件系统在VFS中注册。另外，当装载其他文件时，不管在启动时还是在操作过程中，它们也必须在VFS中注册。当一个文件系统注册时，根文件系统注册到VFS。另外，在引导时或操作期间挂载其他文件系统时，它们也必须向VFS注册。当文件系统注册时，其基本作用是提供VFS所需功能的地址列表、调用向量表、或者VFS对象。因此一旦文件系统注册到VFS，它就知道从哪里开始读取数据块。
装载文件系统后就可以使用它了。比如，如果一个文件系统装载到/usr并且一个进程调用它：
open("/usr/include/unistd.h",O_RDONLY)
当解析路径时，VFS看到新的文件系统被挂载到/usr，并且通过搜索已经装载文件系统的超级块来确定它的超块。然后它找到它所转载的文件的根目录，在那里查找路径include/unistd.h。然后VFS创建一个vnode并调用实际文件系统，以返回所有的在文件inode中的信息。这个信息和其他信息一起复制到vnode（内存中）。而这些其他信息中最重要的是指向包含调用vnode操作的函数表的指针，比如read、write和close等。
当vnode被创建后，为了进程调用，VFS在文件描述符表中创建一个表项，并将它指向新的vnode，最后，VFS向调用者返回文件描述符，所以调用者可以用它去read、write或者close文件。
从调用者进程号和文件描述符开始，进而是vnode，读函数指针，然后是对实际文件系统的访问函数定位。
文件系统的管理和优化
能够使文件系统工作是一回事，能够使文件系统高效、稳定的工作是另一回事，下面我们就来探讨一下文件系统的管理和优化。
磁盘空间管理
文件通常存在磁盘中，所以如何管理磁盘空间是一个操作系统的设计者需要考虑的问题。在文件上进行存有两种策略：分配n个字节的连续磁盘空间；或者把文件拆分成多个并不一定连续的块。在存储管理系统中，主要有分段管理和分页管理两种方式。
正如我们所看到的，按连续字节序列存储文件有一个明显的问题，当文件扩大时，有可能需要在磁盘上移动文件。内存中分段也有同样的问题。不同的是，相对于把文件从磁盘的一个位置移动到另一个位置，内存中段的移动操作要快很多。因此，几乎所有的文件系统都把文件分割成固定大小的块来存储。
块大小
一旦把文件分为固定大小的块来存储，就会出现问题，块的大小是多少？按照磁盘组织方式，扇区、磁道和柱面显然都可以作为分配单位。在分页系统中，分页大小也是主要因素。
记录空闲块
一旦指定了块大小，下一个问题就是怎样跟踪空闲块。有两种方法被广泛采用，如下图所示
第一种方法是采用磁盘块链表，链表的每个块中包含极可能多的空闲磁盘块号。对于1KB的块和32位的磁盘块号，空闲表中每个块包含有255个空闲的块号。考虑1TB的硬盘，拥有大概十亿个磁盘块。为了存储全部地址块号，如果每块可以保存255个块号，则需要将近400万个块。通常，空闲块用于保存空闲列表，因此存储基本上是空闲的。
另一种空闲空间管理的技术是位图(bitmap)，n个块的磁盘需要n位位图。在位图中，空闲块用1表示，已分配的块用0表示。对于1TB硬盘的例子，需要10亿位表示，即需要大约130000个1KB块存储。很明显，和32位链表模型相比，位图需要的空间更少，因为每个块使用1位。只有当磁盘快满的时候，链表需要的块才会比位图少。
如果空闲块是长期连续的话，那么空闲列表可以改成记录连续分块而不是单个的块。每个块都会使用8位、16位、32位的计数来与每个块相联，来记录连续空闲块的数量。最好的情况是一个空闲块可以用两个数字来表示：第一个空闲块的地址和空闲块的计数。另一方面，如果磁盘严重碎片化，那么跟踪连续分块要比跟踪单个分块运行效率低，因为不仅要存储地址，还要存储数量。
这种情况说明了一个操作系统设计者经常遇到的一个问题。有许多数据结构和算法可以用来解决问题，但是选择一个最好的方案需要数据的支持，而这些数据是设计者无法预先拥有的。只有在系统部署完毕真正使用使用后才会获得。
现在，回到空闲链表的方法，只有一个指针块保存在内存中。创建文件时，所需要的块从指针块中取出。当它用完时，将从磁盘中读取一个新的指针块。类似地，删除文件时，文件的块将被释放并添加到主存中的指针块中。当块被填满时，写回磁盘。
在某些特定的情况下，这个方法导致了不必要的磁盘IO，如下图所示
上面内存中的指针块仅有两个空闲块，如果释放了一个含有三个磁盘块的文件，那么该指针块就会溢出，必须将其写入磁盘，那么就会产生如下图的这种情况。
如果现在写入含有三个块的文件，已满的指针不得不再次读入，这将会回到上图a中的情况。如果有三个块的文件只是作为临时文件被写入，在释放它时，需要进行另一次磁盘写操作以将完整的指针块写回到磁盘。简而言之，当指针块几乎为空时，一系列短暂的临时文件可能会导致大量磁盘I/O。
避免大部分磁盘I/O的另一种方法是拆分完整的指针块。这样，当释放三个块时，变化不再是从a-b，而是从a-c，如下图所示
现在，系统可以处理一系列临时文件，而不需要进行任何磁盘I/O。如果内存中指针块满了，就写入磁盘，半满的指针块从磁盘中读入。这里的思想是：要保持磁盘上的大多数指针块为满的状态（减少磁盘的使用），但是在内存中保留了一个半满的指针块。这样，就可以既处理文件的创建又同时可以处理文件的删除操作，而不会为空闲表进行磁盘I/O。
对于位图，会在内存中只保留一个块，只有在该块满了或空了的情形下，才到磁盘上取另一个块。通过在位图的单一块上进行所有的分配操作，磁盘块会紧密的聚集在一起，从而减少了磁盘臂的移动。由于位图是一种固定大小的数据结构，所以如果内核是分页的，就可以把位图放在虚拟内存中，在需要时将位图的页面调入。
磁盘配额
为了防止一些用户占用太多的磁盘空间，多用户操作通常提供一种磁盘配额(enforcingdiskquotas)的机制。系统管理员为每个用户分配最大的文件和块分配，并且操作系统确保用户不会超过其配额。我们下面会谈到这一机制。
在用户打开一个文件时，操作系统会找到文件属性和磁盘地址，并把它们送入内存中的打开文件表。其中一个属性告诉文件所有者是谁。任何有关文件的增加都会记到所有者的配额中。
第二张表包含了每个用户当前打开文件的配额记录，即使是其他人打开该文件也一样。如上图所示，该表的内容是从被打开文件的所有者的磁盘配额文件中提取出来的。当所有文件关闭时，该记录被写回配额文件。
当在打开文件表中建立一新表项时，会产生一个指向所有者配额记录的指针。每次向文件中添加一个块时，文件所有者所用数据块的总数也随之增加，并会同时增加硬限制和软限制的检查。可以超出软限制，但硬限制不可以超出。当已达到硬限制时，再往文件中添加内容将引发错误。同样，对文件数目也存在类似的检查。
什么是硬限制和软限制？硬限制是软限制的上限。软限制是为会话或进程实际执行的限制。这允许管理员（或用户）将硬限制设置为允许它们希望允许的最大使用上限。然后，其他用户和进程可以根据需要使用软限制将其资源使用量自限制到更低的上限。
如果用户在退出系统时消除所超过的部分，他们就可以再一次终端会话期间超过其软限制，但无论什么情况下都不会超过硬限制。
文件系统备份
文件系统的毁坏要比计算机的损坏严重很多。无论是硬件还是软件的故障，只要计算机文件系统被破坏，要恢复起来都是及其困难的，甚至是不可能的。因为文件系统无法抵御破坏，因而我们要在文件系统在被破坏之前做好数据备份，但是备份也不是那么容易，下面我们就来探讨备份的过程。
这个问题主要是由于外部条件的原因造成的，比如磁盘破裂，水灾火灾等。
第二个问题通常是由于用户意外的删除了原本需要还原的文件。这种情况发生的很频繁，使得Windows的设计者们针对删除命令专门设计了特殊目录，这就是回收站(recyclebin)，也就是说，在删除文件的时候，文件本身并不真正从磁盘上消失，而是被放置到这个特殊目录下，等以后需要的时候可以还原回去。文件备份更主要是指这种情况，能够允许几天之前，几周之前的文件从原来备份的磁盘进行还原。
其次，对上次未修改过的文件再进行备份是一种浪费，因而产生了一种增量转储(incrementaldumps)的思想。最简单的增量转储的形式就是周期性的做全面的备份，而每天只对增量转储完成后发生变化的文件做单个备份。
周期性：比如一周或者一个月
第三，既然待转储的往往是海量数据，那么在将其写入磁带之前对文件进行压缩就很有必要。但是，如果在备份过程中出现了文件损坏的情况，就会导致破坏压缩算法，从而使整个磁带无法读取。所以在备份前是否进行文件压缩需慎重考虑。
磁盘转储到备份磁盘上有两种方案：物理转储和逻辑转储。物理转储(physicaldump)是从磁盘的0块开始，依次将所有磁盘块按照顺序写入到输出磁盘，并在复制最后一个磁盘时停止。这种程序的万无一失性是其他程序所不具备的。
第二个需要考虑的是坏块的转储。制造大型磁盘而没有瑕疵是不可能的，所以也会存在一些坏块(badblocks)。有时进行低级格式化后，坏块会被检测出来并进行标记，这种情况的解决办法是用磁盘末尾的一些空闲块所替换。
然而，一些块在格式化后会变坏，在这种情况下操作系统可以检测到它们。通常情况下，它可以通过创建一个由所有坏块组成的文件来解决问题，确保它们不会出现在空闲池中并且永远不会被分配。那么此文件是完全不可读的。如果磁盘控制器将所有的坏块重新映射，物理转储还是能够正常工作的。
物理转储和逻辑转储
物理转储的主要优点是简单、极为快速（基本上是以磁盘的速度运行），缺点是全量备份，不能跳过指定目录，也不能增量转储，也不能恢复个人文件的请求。因此句大多数情况下不会使用物理转储，而使用逻辑转储。
逻辑转储(logicaldump)从一个或几个指定的目录开始，递归转储自指定日期开始后更改的文件和目录。因此，在逻辑转储中，转储磁盘上有一系列经过仔细识别的目录和文件，这使得根据请求轻松还原特定文件或目录。
既然逻辑转储是最常用的方式，那么下面就让我们研究一下逻辑转储的通用算法。此算法在UNIX系统上广为使用，如下图所示
待转储的文件系统，其中方框代表目录，圆圈代表文件。黄色的项目表是自上次转储以来修改过。每个目录和文件都被标上其inode号。
此算法会转储位于修改文件或目录路径上的所有目录（也包括未修改的目录），原因有两个。第一是能够在不同电脑的文件系统中恢复转储的文件。通过这种方式，转储和重新存储的程序能够用来在两个电脑之间传输整个文件系统。第二个原因是能够对单个文件进行增量恢复。
逻辑转储算法需要维持一个inode为索引的位图(bitmap)，每个inode包含了几位。随着算法的进行，位图中的这些位会被设置或清除。算法的执行分成四个阶段。第一阶段从起始目录（本例为根目录）开始检查其中所有的目录项。对每一个修改过的文件，该算法将在位图中标记其inode。算法还会标记并递归检查每一个目录（不管是否修改过）。
在第一阶段结束时，所有修改过的文件和全部目录都在位图中标记了，如下图所示
理论上来说，第二阶段再次递归遍历目录树，并去掉目录树中任何不包含被修改过的文件或目录的标记。本阶段执行的结果如下
注意，inode编号为10、11、14、27、29和30的目录已经被去掉了标记，因为它们所包含的内容没有修改。它们也不会转储。相反，inode编号为5和6的目录本身尽管没有被修改过也要被转储，因为在新的机器上恢复当日的修改时需要这些信息。为了提高算法效率，可以将这两阶段的目录树遍历合二为一。
现在已经知道了哪些目录和文件必须被转储了，这就是上图b中标记的内容，第三阶段算法将以节点号为序，扫描这些inode并转储所有标记为需转储的目录，如下图所示
最后，在第四阶段，上图中被标记的文件也被转储，同样，由其文件属性作为前缀。至此，转储结束。
从转储磁盘上还原文件系统非常简单。一开始，需要在磁盘上创建空文件系统。然后恢复最近一次的完整转储。由于磁带上最先出现目录，所以首先恢复目录，给出文件系统的框架(skeleton)，然后恢复文件系统本身。在完整存储之后是第一次增量存储，然后是第二次重复这一过程，以此类推。
尽管逻辑存储十分简单，但是也会有一些棘手的问题。首先，既然空闲块列表并不是一个文件，那么在所有被转储的文件恢复完毕之后，就需要从零开始重新构造。
另外一个问题是关于链接。如果文件链接了两个或者多个目录，而文件只能还原一次，那么并且所有指向该文件的目录都必须还原。
还有一个问题是，UNIX文件实际上包含了许多空洞(holes)。打开文件，写几个字节，然后找到文件中偏移了一定距离的地址，又写入更多的字节，这么做是合法的。但两者之间的这些块并不属于文件本身，从而也不应该在其上进行文件转储和恢复。
最后，无论属于哪一个目录，特殊文件，命名管道以及类似的文件都不应该被转储。
文件系统的一致性
影响可靠性的一个因素是文件系统的一致性。许多文件系统读取磁盘块、修改磁盘块、再把它们写回磁盘。如果系统在所有块写入之前崩溃，文件系统就会处于一种不一致(inconsistent)的状态。如果某些尚未写回的块是索引节点块，目录块或包含空闲列表的块，则此问题是很严重的。
为了处理文件系统一致性问题，大部分计算机都会有应用程序来检查文件系统的一致性。例如，UNIX有fsck；Windows有sfc，每当引导系统时（尤其是在崩溃后），都可以运行该程序。
可以进行两种一致性检查：块的一致性检查和文件的一致性检查。为了检查块的一致性，应用程序会建立两张表，每个包含一个计数器的块，最初设置为0。第一个表中的计数器跟踪该块在文件中出现的次数，第二张表中的计数器记录每个块在空闲列表、空闲位图中出现的频率。
然后检验程序使用原始设备读取所有的inode，忽略文件的结构，只返回从零开始的所有磁盘块。从inode开始，很容易找到文件中的块数量。每当读取一个块时，该块在第一个表中的计数器+1，应用程序会检查空闲块或者位图来找到没有使用的块。空闲列表中块的每次出现都会导致其在第二表中的计数器增加。
如果文件系统一致，则每一个块或者在第一个表计数器为1，或者在第二个表计数器中为1，如下图所示
但是当系统崩溃后，这两张表可能如下所示
其中，磁盘块2没有出现在任何一张表中，这称为块丢失(missingblock)。尽管块丢失不会造成实际的损害，但它的确浪费了磁盘空间，减少了磁盘容量。块丢失的问题很容易解决，文件系统检验程序把他们加到空闲表中即可。
有可能出现的另外一种情况如下所示
其中，块4在空闲表中出现了2次。这种解决方法也很简单，只要重新建立空闲表即可。
最糟糕的情况是在两个或者多个文件中出现同一个数据块，如下所示
比如上图的磁盘块5，如果其中一个文件被删除，块5会被添加到空闲表中，导致一个块同时处于使用和空闲的两种状态。如果删除这两个文件，那么在空闲表中这个磁盘块会出现两次。
文件系统检验程序采取的处理方法是，先分配一磁盘块，把块5中的内容复制到空闲块中，然后把它插入到其中一个文件中。这样文件的内容未改变，虽然这些内容可...