首发于我的博客网站(prajna.top) 欢迎大家前去交流，有 pdf 版本。

本文主要是从应用的角度出发，分别阐述操作系统接口，计算机语言，文件系统等背后的一些知识，规范，原理，设计思想，应用法门，让初学者对编码有一个整体的，全局的认识，有一个物理的视角，找到自己的起点。

前言

写这篇文章主要是基于自己大学的经历，当时抱着一腔热血去学计算机编程，可是当把 c /c++ 语言，数据结构，操作系统，计算机组成原理等课程都学完后，却发现自己似乎什么也不会，只会 printf 打印一些字符串。那段时间真的好苦恼，特别想做软件，却不知从何开始，也不知道该如何去使力，蹉跎了好久，浪费了大量的时间。

造成这种现象的主要原因，一是自己缺少那种天赋，二是教学过于侧重基础和理论，每门课程只涉及到一个局部，没有一门课程把这些串起来。我不了解语言的基础库，除了 printf 后，其它 API 都不会用；也不了解具体的操作系统平台的 API；虽然学了 TCP/IP，socket 的具体使用却又不清楚；至于像 fat,ext 等磁盘文件系统的格式，那就更遥远了；我甚至还不清楚计算机语言和编译工具的关系；更要命的是，我还不知道自己不知道这些。说白了就是理论同应用脱节，虽然大学也安排了课程设计，实验和实习，但都只是走了过场，也没有人来指点一下，该看些什么书籍。大学读完，就知道拖拉几个控件做一个窗口，连接一下数据库。

windows + VC 屏蔽了太多的技术细节，可惜大学期间接触的偏偏就是它，对用户这个是好事越傻瓜越好，可是对计算机的学生就要了命了。自从我转投到 linux 开源世界后，终于才发现了什么是自由，什么是编程。当阅读 linux 源码碰到不理解的地方，可以直接修改源码加上打印，分析 kernel 流程。对比着 minix 的源码来学习操作系统结构原理，那些概念就变成实实在在的数据结构和算法，动手写一个 minix 的驱动，微内核和宏内核区别就一目了然了。强烈建议，想学习编程的同学都去拥抱开源世界，然后，再回到自己感兴趣的或工作相关的领域。

计算机语言说白了就是工具，关键还是你要做什么，这样就涉及到了应用，以及专业背景知识。如想做驱动编程，离不开对操作系统驱动架构的了解；想做一个磁盘分区合并，那需要了解文件系统的格式；做个播放器吧，那对视频文件格式，编码格式，编解码 API 的了解必不可少。随着你对软件系统了解的深入，会发现其实一切都是协议。http 是一套 web 通讯的协议；计算机语言是开发工具提供的协议；操作系统是内核空间与应用空间的协议 …，这些协议被各种规范约束--并形成了各种技术。所以，每种技术的背后都一套协议，规则和思想。了解这些才能算真正了解了相关技术。

在这篇文章里面，我以 GNU/Linux 作为平台，从应用的角度出发来把相关的课程来串一串提供一个“物理视图”，让初学者有个全局的认识，能够有一个方向和切入角度，至少知道该找些什么资料来看。

操作系统接口

它是内核对应用空间提供的一套协议，主要包括：

• ABI 可执行文件的结构。
• 系统调用(system call)。
• sysfs 文件系统接口(linux kernel)。

ELF 是编译，链接生成的，执行的时候，由 ld 解析，加载在到内存，最后控制权交给程序入口代码，程序开始执行。因此，它提供了 2 类视图：链接视图和执行视图。

从链接视图上看，ELF 由众多的 Section 组成，编译器先把源码编译成.o 文件，主要是提取函数，全局变量等生成符号表，把它们填充到相应的 Section 里面去。在这个阶段，所有的符号都是没法定位到地址的。

Link 的时候，对.o 文件进行合并，对各个文件内的符号进行重定位，安排它们的地址，如下图所示，link 完成后，g_u8 和 g_flag2 都有地址了。

对于动态链接的函数，在 link 阶段没法安排地址，需要放到 dynsym Section 里面去，在 ld 的时候，来进行定位 -- 这就是所谓的 “ 函数重定位 ”。

​linux 系统提供了可执行程序 readelf 来解析 ELF 文件格式，我们可以使用它来了解一下 ELF 文件的一些通用的 Section。

• bss 是没有指定初始化值的数据，有些编译器会默认全部初始化为 0。
• data 全局变量初始化。
• text 代码。
• init 程序初始化运行的代码。
• fini 程序结束运行的代码。
• symtab 符号表，它是源码编译生成的产物，可以为代码运行，调试提供信息。
  属于辅助性质，不参与 load 和运行，可以用 strip 来删除掉。

‘offset Align’ 是各个 Section 在 ELF 文件内的偏移地址，我们以二进制的方式打开 ELF 文件，根据偏移地址，就可以查看相应 Section 的二进制内容。

从下图中可以看到 .interp 的内容是 “/lib64/ld-linux-x86-64.so.2″，

上面这些就是编译，链接生成 ELF 文件的过程：编译器以源文件作为输入，先提取各个文件的全局变量和函数，生成符号表，再把它们链接到一起，链接的时候对各个符号进行定位，分配地址。对于动态链接库的函数，则推迟到 ’ 加载 ’ 程序到内存的时候进行定位。编译链接后，代码和数据分散到了相应的 section 里面，程序加载的时候，需要把 Section 合并成 Secgment，然后，以 Secgement 为单位加载到内存页面里面去，我们来看一下 Segment 的结构。

ELF 有 9 种 Segment，其中比较核心的是 --

• INTERP，用来指定谁执行这个 ELF 文件，
• LOAD，分别是文本 (代码) 段和数据端。

Segment 同 Section 是有对应关系的，如：

• INTERP -- .interp
• LOAD(文本) -- .interp .init .text .fini .rodata 等。
• LOAD(数据) -- .init_array .fini_array .data .bss 等。

程序执行的时候，先从 INTERP 段找到对应的执行程序--可执行程序一般是 ld.so，首先加载 ELF 文件，根据 Prgrame Header 数据结构，把 section 加载到各个程序段里面，然后，递归重定位动态链接符号，加载这些符合依赖的动态链接库，处理 ELF 文件中的重定位，然后，把控制权交给代码入口，程序开始运行。在这个过程中，ld 最重要的一个事情就是 ’ 重定位 ’，修改 ELF 里面的动态链接函数的符号表。

系统调用(system call)

系统调用是 kernel 提供给应用层的 API，通过软中断来调用。调用的形式是这样

对 ENTER_KERNEL 宏的定义，传统 (i386) 的调用方式是 ‘int $80’，ia64 是 ‘syscall’ 指令来进入 kernel。软中断的流程基本上都是这么几个步骤

• 保存现场。
• 把参数压入相应的寄存器。-- kernel 有定义它们的对应关系。
• 写系统调用号到 %eax 寄存器。
• 调用 int $80 或者 syscall 进入内核。--不同的 CPU 会有不同的指令要求。
  得到结果，恢复现场等。

我们可以在 ’arch/x86/syscalls/’ 目录下找到 syscall 的列表，

最前面的数字就是系统调用号，如：‘syscall 5’ 调用的是 ’open’。总共大约是 400 个左右，涵盖了最基本的应用：如上图中文件相关的操作, 进程类的 (fork, execve) 等。这些系统调用都被 libc 库做了封装，一些简单的底层函数 (如：mount, mkdir, stat) 则只是简单地被包裹了一下，直接软中断到 kernel 了。所以，大家如果想了解文件系统相关 API 的实现，一定要看 kernel 的源码，看 libc 库的源码是没用的，它都是简单地做了一个系统调用的转换。

前面提到过一切都是协议，POSIX 是一个广泛被支持的协议(规范)，Linux 和各类 unix 都对它提供了支持，只要操作系统申明支持 POSIX 接口，它就得实现 POSIX 定义的系统调用。对 linux/unix 而言，POSIX 只是它们的一个子集，它会还会支持 UNIX 世界的一些系统调用规范。总之，有了这些规范，libc 就可以在各个系统间无缝移植。

sysfs 文件系统接口

sysfs 是 linux kernel 以文件系统的方式提供给应用层的接口，在 linux 的世界里，驱动模块都被抽象为文件系统节点，因此，我们对 /sys/ 文件系统进行读写操作，可以与内核里面的驱动层进行交流。具体的接口内容，请查询 ‘/Documentation/ABI/’ 目录下 sysfs-module 文件

计算机语言与编译器

计算机语言就是一套人机交互的协议，好比我们学了英语，就可以同“支持”英语的人交流，来达到我们的一些目的。计算机语言的本质也是一样的，程序员通过某语言来调配它的资源，完成目标任务。无论是什么语言，语法方面都大同小异，无非就是变量定义，表达式加几个循环而已--它的理论源头就是大名鼎鼎的图灵完备的编程语言。图灵从理论上论证了，只要符合图灵完备规则，就可以满足所有的自动化计算的需要。

因此，各种语言的语法都大同小异，那么，为什么我们还需要那么多的语言呢？
这就回到了“什么是计算机语言的本质“这个问题了，语言的核心到底是什么呢？很显然不是语法，而是它编程思想和资源（功能）。每种语言都是为了解决某些问题而存在，都会提供一套语法和平台资源--包括标准库和第三方库。

汇编语言主要是为了方便记忆，对机器指令上做了一个替换，没有汇编语言，我们还需要一边查着芯片手册，一边手敲着 “6F 01 20” 之类的代码。由于它没有提供内存管理和系统结构化的手段，本质上还是机器指令级别的编程。使用汇编语言，我们还得规划内存，挑选寄存器，完成堆栈操作，因此，汇编只适合代码量少的系统。如很小的单片机或者系统的引导代码。高级语言则不同，编译器帮忙搞掂了内存布局，进栈出栈等这些烦琐的事情，直接面向应用。

C 语言提供了面向模块的结构化思想，通过模块化机制，我们可以分工合作，构建起应用。学习 C 语言，就是要了解它的模块化思想，学会如何利用数据结构和函数指针封装模块，提供统一对外接口。另外，还得了解它的库，这个决定了我们能获得多大的资源支持。C 的基本库对系统调用进行了封装，提供了一些跟操作系统相关的函数（文件操作，进程管理，内存相关，socket 等），它没有提供常用的数据结构和算法（比如：链表的构建和排序，二叉树），需要自己处理。在应用层面，它则提供了字符和字符串处理，数学函数(sin,cos,tan,…)，日期和时间等等，可见 C 语言的标准库提供的都是底层的函数，当然了也有一些上层的 GUI 框架利用 C 语言提供接口的，他们在 C 的基础上提供大量的扩展，一步步地架构了自己的系统。

C++ 虽然是 C 的扩展，但它是全新的语言，提供的是面向对象的架构思想。只不是兼容 C 语言规范，它可以利用 C 语言的所有资源。它利用模板来提供标准库（STL）封装了常用的数据结构和算法。官方又提供的 Boost 模板库，拥有了更丰富更强大的功能。利用 STL/Boost 和基础 C 库，都足以开发一些底层软件。C 和 C ++ 的基础库都没有提供图形，多媒体，GUI 框架，用户需要使用第三方的资源，如：SDL，opengl，Qt 等。

像 JAVA 这类带虚拟机的语言最厉害的地方，除了跨平台性，就是它强大的类库。不但封装了常用的数据结构和算法，还集成了 GUI 框架，图形库，多媒体处理，也有很强的 web 处理能力。

python 则提出不要重复造 ” 轮子 ”，因为它提供了大量可用的轮子，从基础的数据结构到大型的应用模块，应有尽有。几句代码就可以完成一个 http 服务器。而且，python 把变量定义这个环节都省了，直接面对要解决的问题，效率极高，特别适合教学，科研，做算法分析和原型验证，工具软件。你想想，现在你突然有了一个算法构想，马上想验证一下，使用的 python 的话，你直接就可以写算法代码了，想当于把算法的伪码拿过来直接就用了。

用 C 语言的话，你得先定义各种数据结构，变量，再编译，排错，真的是很会很急人的，如果涉及到字符串的处理，心早就拔凉拔凉了。
软件编程就是利用语言来调配各种资源来实现目标。学习一门新语言，除了学习语法，更多的关注点还是它提供的编程思想和它的平台资源。你得了解目标语言提供的各种资源，了解它的适用场景，它是为解决什么问题而存在。最好的学习方法是看一些经典的源码，如：mplayer 的 C 语言代码，很好地诠释了什么是模块化设计，真的令人叹为观止，会发现原来自己根本就不会写代码。

学汇编的比 C 语言厉害些吗？
经常会听到这样的争论，有一次地铁上，我在用 C ++ 编码，旁边一个”哥们“问我学习 C ++ 是不是赚钱些，我惟苦笑不已。语言本身没有高下之分，会用这个语言来完成任务才算厉害，最厉害的就是做出产品，像 freebsd, linux 这种划时代的产品，才是真的厉害。对程序员而已，厉害的是你的编程思想和算法能力，行业的专业知识。语言这种东西，只是是信手拈来，实现你的想法而已。

编译器就是语言的某一个具体实现，厂家不同，产品不同，像经典的 TC 和 VC。编译器最基础的功能就是把所支持的源语言，编译成操作系统支持的可执行文件格式。如果，它再提供一个 GUI 界面，增加了源码编辑，断点调试，GUI 框架，那么，它就成了一个开发平台，比如经典的 VC。目前，我们使用的集成开发环境都是融合了编辑，编译，项目管理，资源编辑，GUI 控件布局，代码生成等一系列工具。

对于初学者还是建议大家自己使用 GCC 来作编译器，GDB 来调试，自己写 Makefile 来定义编译规则，再找一个源码编辑工具像 Emacs 或者 Eclipse 之类，这样大家可以很清晰地知道自己在干什么，需要做什么。再使用集成开发工具的时候，知道该怎么去处理各种问题，不然一直稀里糊涂地不不知道一个 ’Run’ 点下去，到底发生了什么，一出问题就傻眼。

如果需要重量级 GUI 框架的，可以考虑 Qt 平台，初学者也不要使用 Qt Creator，可以自己使用 Qt 的工具来做预处理，如：

可以定义相应的规则，把它放到 Makefile 里面，这样就可以使用 make 来进行管理。

数据结构和算法

话说学好了数据结构和算法，就基本解决了编程问题。可是当我们拖拉几个控件，写几个事件，就可以完成工作的时候，不禁会有点疑惑，说好的数据结构和算法呢。--其实，它无处不在，在应用框架里，在中间件里，在 API 里面，在 Kernel 里。C++ 的 STL 和 JAVA 都把一些常用的数据结构封装成了“集合”对象。
数据结构就是对客观对象的抽象，算法则是如何来组织和调用这些数据。在 kernel 里面，我们耳熟能详的概念都是一个个具体的数据结构如：进程，内存页面等等。下面是 linux 的进程数据结构 ’struct task_struct’ 部分片断，可以看到对进程的描述信息（属性）都定义在该结构里面了。

这个就是我们通过 ps 命令看到的进程信息描述，其实在 linux kernel 都是按照线程来管理的，所以，task_struct 也是线程的描述。linux 源码里面就是大量的这种数据结构定义，以及把它们链接起来进行管理的各类链表，二分查找树。

下面简单说下数据结构和算法在 STL 里面的应用。
STL 作为 C ++ 的标准库，它封装了常用的数据结构和算法。<vector> 的数据结构本质上是动态数组，当空间不够的时候，它重新分配空间，并拷贝旧元素到的数组。

• “读”的时间复杂度是常量--可以随机访问。
• “插入”需要额外进行数据拷贝，时间复杂度是 O(n)--n 是 pos 到 end 元素数量，这部分数据需要拷贝。
• “push_back”的操作时间经平摊后是常量级别，vector 在插入元素时，往往会额外多分配一点空间，以免每次插入元素都进行“重分配”和“拷贝”的操作。使用 vector 最好可以显示地给它分配空间，以提高性能。

<list> 是一个链表，“读”和“插入”的时间复杂度是 O(n)--n 是元素的位置，“插入”数据操作的时间消耗是常量级的。

虽然 <vector> 的 ’ 插入 ’ 时间复杂度也是 O(n)，但是，<list> 不需要拷贝后面的元素，只需要移动到相应的位置，它的 ’ 插入 ’ 性能更好，而 <vector> 提供随机访问能力，适合通过 ’ 数组下标 ’ 直接访问场合。

有没有像 <vector> 那样提供随机访问能力，但是又能提供 <list> 那样的插入性能的数据结构呢？
有，那就是 <deque>，它相当于是 <vector> 和 <list> 的一个结合，相当于 <list> 来连接固定大小的 <vector>。

• “读”的时间复杂度是常量--可以随机访问。
• “插入”的时间复杂度是 O(n)--n 是元素的位置。

那是不是可以使用 <deque> 来代替 <vector> 和 <list> 呢？当然不可以：

• <deque> 的内存浪费会比较严重，那怕只有一个元素也会分配一整个数据块。
• <deque> 的随机访问效率还是不如 <vector> 高。
• <deque> 在某个 chunk 的插入也还面临着拷贝末端数据的问题，因此，严格意义上说，它的插入性能还是不如 <list>。

<set> 和 <map> 通常用一棵红黑二叉树来做为数据结构的实现，根据关键字来排序，“查找”，“插入”和”“删除”的时间开销都是 O(lg(n))，它里面的记录是有序排列的，我们根据关键字把它导出来就是一个有序列表，它们的综合性能比较好。

如果需要更快速的访问能力，可以考虑使用带 hash 结构的 <unordered_set> 和 <unordered_map>“查找”，“插入”和”“删除”的平均开销是“常量级”的，性能很好，但是它里面的数据是“无序”的。

文件系统

文件系统就是用来对文件进行增删改查的控制系统，不同类型的文件系统对应着不同的管理策略，但是，无论何种策略都需要解决两个最基本的问题：

• 文件存储。
• 目录访问。

因此文件系统需要在磁盘记录一些额外的信息，所以格式化以后，磁盘容量会小于实际的容量。格式化的过程就是在磁盘上“安装”文件系统的过程，下面以 EXT2 和 FAT32 为例来说说文件系统是如何工作的。

EXT

ext 系列是 linux 下面主打的文件系统，它以 Block 为容量单位，以 Inode 来抽象文件（目录也是文件）。一个硬盘分成多个 Block Group，每个 Group 里面分别存储 Inode 和具体的文件数据，如下图所示：

• Super Block: 又称超级块，是文件系统的头部--如同视频和图像文件都有一个独一无二的头部一样：它包含文件系统的标识(magic 代码 0XEF53)，Block 的大小(1k,2K,4K 或者 8K)，Inode 数量，Block 数量，Inode 大小等等文件系统的元数据。一旦它出现损坏，整个文件系统就将无法识别，那么这个文件系统就损坏了，里面的数据也就丢失了。
• Group Descriptors: 全称 Block Group Descriptor Table 简称 GDT，包含所有的 Group 结构，用来描述每个 Group 里面 Inode 和 Block 的位置，空闲数量等信息。
• Block/Inode Bitmap: 用一个 bit 位来标示是否空闲，如：bit15 代表对应的第 15 个 Block/Inode，0 表示空闲，1 则标示已被占用了。
• Inode Table: 每个 Inode 代表一个文件，它存储着该文件的属性和位置，通过它就可以访问对应的文件。每一个 Block Group 都有相同数量的 Inode，因此，格式化后，所能支持的最大文件个数和每个文件的最大容量都被决定了--Inode 的数量就是所能支持的最大文件数量(包含目录，目录也被抽象为文件)，Inode 的支持的最大寻址空间也就是文件的最大长度。
• Data Blocks：文件数据的地址，是一个长度为 15 的数组。

从上面图中可以看到，每个 Group Block 的结构都是一模一样，除了 Data Blocks 外，内容也都是一样的吗？
因为 Super Block 和 GDT 是非常重要的，所以，每个 Block Group 都有一份备份，因此他们的数据是一样的，由于备份会浪费空间，新版本的 EXT 系统不再要求每个 Group 都进行备份了，格式化的时候，可以选择备份策略。除了这两项外，其它的内容就跟该 Group 的存储的数据有关了。

那么划分 Block Group 的好处有哪些呢？
主要是为了防止文件存储碎片化。在存储的时候，预先保留多余空间，尽量把文件放到一个 Group 里面，因此文件不是互相连续存放的：比如先后创建 2 个文件，第一个文件放在 213 Block，第二个文件可能就 510 Block，预留一部分空间给文件扩展用。当然了，对超大的文件，是会跨 Group 存放的。通过精心的 Block Group 划分，再加上 Linux 灵活的文件分配策略，EXT 文件系统在正常使用情况下“碎片率”是比较低的。

目录结构

目录表没有放到 Inode Table 里面，而是放到 Data Blocks 上了，每个目录节点都对应一个 Inode，它的数据区域（Data Blocks）就是它的目录表。每个目录表项包括：文件名，类型和 Inode 号--通过 Inode 号又能找到下一级目录表，这样就构成了一个目录链表结构。

类 Unix 系统都有一个“根目录”，是路径的起始点，系统就是从根目录开始来遍历目录链表的，它也相当于链表的“根节点”，因此它的位置必需是固定的：Linux 系统的“根目录”Inode 节点号是 2。

下面以一个小容量的 ext2 系统为例来遍历下目录。
首先查找“根节点”，它的内容如下：

BLOCKS: (0):204 表示：该 Inode 只占用了一个 Block(编号从 0 开始起)，内容在 204 号 Block 上，我们现在读取 Inode 2 里面的内容（也就是 204 号 Block）：

根据目录表项的定义解析二进制数据，就可以得到根目录的目录表：

接下来，遍历下一级目录。
如果我们要访问 ”/home” 目录，通过查找表，会发现它的 Inode 号是 1281，然后，读取 Inode 1281 的内容，再根据 BLOCKS 项的信息，读取它的数据块，又可以得到 ’/home’ 的目录表--就如同前面读取“根节点”一样，只是 Inode 2 变成了 Inode 1281。这样反复递归，就可以一级一级地查询到最终的目录或者文件。

以上就是目录存储和查找的过程，目录表存储在 Inode 的数据区域，查找就是从根节点开始，反复递归，直到目的路径。

为什么“根目录”的 Inode 号是 2，而不是 1 或者 0 呢？
Inode 0 表示该 Inode 不存在，类似 C 语言的空指针，这个是为了编码方便。Inode 1 是用存储坏块的，所以，“根目录”就是 Inode 2 了，当然了，不同操作系统的具体实现估计会有差异。

读取文件内容

我们通过目录结构找到文件对应的 Inode 节点后，就可以读取它的内容了。Inode 节点使用一个数组来存储文件所占用的 Block 号（BLOCKS 项的内容），数组的长度为 15，Block 号用 4 个字节来表示。数组的前 12 位是立即寻址，第 13，14 和 15 位则是间接寻址。
下面以 Block 大小为 1024 个字节为例，来说明这个寻址过程。

如上图所示：

• 前 12 位是直接寻址，数组对应的内容就是文件的前 12 块。
• 第 13 位是“一重间接寻址”，它的内容不是文件内容，而是文件的块地址--类似于 C 语言的指针，我们先找到 218 块，再根据 218 块上的 256 个地址 (1K/4) 来读取文件内容，也就是说这个地址的容量是 256 块，范围是[13 ~ 268]。如图中所示，第 13 块的内容在 525 块上，1164 块则是文件的第 268 块--这 256 块不一定是连续存放的。
• 14 位是“二重间接寻址”，意味着连续 2 遍寻址，才能读取到文件内容，因此它支持的容量是 (256*256=65536) 块，可见它相当于 C 语言里面的“指针的指针”。我们先找到 236 块，得到它上面的 256 个地址，再依次读取这 256 个地址得到最终的 65536 个块地址。从图中可以看到，236 块上的第一个块地址是 220，220 块上的第一个块地址是 1165--也就是说该文件逻辑上的第 269 块存储在 1165 号块上，依次方法遍历，可以读取该文件的 65536 块的内容。
• 15 位是“三重间接寻址”，想当于 C 语言里的“指针的指针的指针”，它支持寻址 (256256256=16777216) 个块，就不肇叙了。

分析一下：文件最多可占用 (12+256+256256+256256*256 =16843020) 个 Block，如果 Block 的大小是 1K，那么文件大小的上限约是 16G。对于小于 13 个 Block 的文件是直接寻址，访问速度快。间接寻址，主要是为了增大文件的容量，同时也能快速读取前 12 个 Block 的内容。

FAT

FAT 是 Windows 下的一款经典文件系统，当时 Windows 系统下一定要做两件事情是：碎片整理和杀毒，而这些都同 FAT 文件系统有关。下面先了解下 FAT 系统的基本内容，下图是 FAT 的“物理视图”。

BPB (启动引导区域)-- 相当于 FAT 文件系统的“头部”，定以了 FAT 文件系统的“元数据”：扇区大小，簇的大小，FAT 表的位置和大小，根目录的位置，基本上 FAT 文件系统的物理布局，都定义在这个里面，在系统格式化的时候生成。

FAT--全称是 File Allocation Table(文件分配表)，实质上就是一个大数组，以“簇”为单位，来记录硬盘空间的使用情况：

• FAT12，每个 FAT 表项是 12 bits (1.5 个字节)。
• FAT16，每个 FAT 表项是 16 bits (2 个字节)。
• FAT32，每个 FAT 表项是 32 bits (4 个字节)。

目录结构--目录也被当作（抽象）成一种文件，它的内容就是一个目录表。目录项的定义如下：

根据上面信息，可以画出 FAT16 物理布局图，

• DIR_name: 长度只有 11 个字节--这是 DOS 时代“经典”的文件名过长的原因，FAT32 通过“长文件名”扩展解决了这个问题。
• DIR_FstClus(HI/LO)：数据的起始地址，再通过 FAT 表去查找后续的地址。
• DIR_FileSize: 文件大小，4G 的文件大小限制就是从这里来的--因为它的长度只有 4 个字节。

下面我们以一个只有 10M 的 FAT16 文件系统为例，来实际说明一下 FAT 文件系统的工作过程。首先，解析 BPB 区域，得到 FAT16 的“元数据”，部分重要信息如下：

根据上面信息，可以画出 FAT16 物理布局图，

因为根目录是特殊的数据，也可以说数据区是从 0x9200 开始的。

读取根目录

接下来找到根目录，读取它的目录表：

根据目录项的定义，得到根目录内容如下：

• ROOT_F~1：“~1”表明文件名过长被截了。
• 起始地址：第一个目录项的 ’DIR_FstClusLO'(0x523A)开始的 2 个字节是 0300，由于是低字节在前(little endian)，所以地址是 0x03，而不是 0x0300。同理，第二个目录项目的地址是 0x0d。

计算文件起始位置

文件地址的物理簇号是从 2 开始算起的，因此，ROOT_F~1.IMG 的起始物理地址 (以字节为单位) 计算如下：
文件起始地址：0x9200 + (3 – 2) * 2048 = 0x9A00。

• 0x9200 是根目录除外的数据区域起始地址。
• 2048 是每一个簇的大小。

0x9A00 就是文件的起始地址，当我们读完该簇后，该如何去寻找下一个簇呢？

查找 FAT 表

因为 FAT16 是的 FAT 表项是 2 个字节，因此 FAT[3]是 0x04，也就是说下一个文件簇的位置是 4，完整的查找过程如下：

• FAT[4] == 5
• FAT[5] == 6
• …
• FAT[11] == 12(0c)
• FAT[12] == 0xFFFF (文件结束符)。

可以看出 FAT 就是一个链接，当前的值指向下一个簇号，直到以 0xFFFF 作为结束。
同理读取目录也是一样的，本例中，HOME 目录的起始地址是：0x9200 + (0x0d – 2) * 2048 = 0xEA00

0xea00 的内容同根目录一样，就是该目录下的目录表，如果该目录的内容超过一个簇，也同样去通过 FAT 表去查找其它的内容。

这就是 FAT 文件系统的基本概念和工作流程。不难看出 FAT 采用的这种链表结构，会导致碎片化会很严重，使用时间长了以后，一个文件的簇链得到处都是。另外，FAT 还没有权限管理，病毒程序就如入无人之境，可以随意复制和破坏。FAT 的好处是简单灵活，文件的个数不固定，且占用磁盘空间少。但是，毕竟适应不了目前大容量高性能的要求，微软从 FAT12 打补丁到 FAT32 后，就推出了 NTFS 文件系统。

后记

到这里，文件系统的一些基础知识就介绍完了，那么了解它有哪些实际的意义呢？

首先，像电影里面的黑客，可以直接面对文件系统的原始数据，比如：从文件系统损坏的硬盘里面恢复一些关键文件--通过读取磁盘文件系统的元数据，比如说直接找目录表，看看哪些文件还可以被识别，再查找相应的 Inode 节点(或 FAT 表)，读取它的 BLOCKS(或簇)，只要物理上还没损坏，就能恢复出来。

其次，可以做一些磁盘类的工具，像文件搜索，恢复删除文件之类--文件被删除后，文件系统一般都是修改了些标志位，如：bitmap 的空闲标志置 1，表示空间被释放等，其实文件的内容还在硬盘上，只要及时地找到文件的位置，就有恢复的可能。我曾经用 python 做过一个小工具，可以浏览，提取 iso 9600 文件系统 (光盘) 里的文件，这样可以在不使用虚拟光驱的情况下，把 iso 镜像文件的内容都提取出来。

欢迎大家来我的网站交流: 般若程序蝉