文件物理组织方式

        抛出一个问题来引出我们的话题。我们的一个hello.c的文件是怎么样存贮到我们的磁盘上面的。我们磁盘又怎么就可以将test,c文件从磁盘上面读取出来，展示到我们的屏幕上面的。

连续文件结构

        首先，一个最简单的方法就是将文件顺序的存放到磁盘上面。但是有一个问题就随之出现了。像“我文件到底占有几个盘块，这个文件的创建者是谁”等类似信息又在哪里？所以，人们为了更好，更方便的控制文件，就设计了一个控制文件的数据结构——FCB(File Control Block)，这个可以类比为我们的进程中的PCB,都是记录了进程/文件的相关信息。回到刚刚的话题，那么顺序文件究竟又是怎么样存放的呢。可以看下面这张图。

从这幅图就可以看到，文件A内容的首地址就放在第5号盘块上面，文件A一共有7个盘块。所以，盘块5，6，7，8，9，10，11都是文件A的内容。文件B的内容也是可以类似的得到。顺序文件的好处在于能够随机存取文件中的内容。什么意思捏。就是说，我现在想要操作文件A的第200个字符到250个字符，对于顺序文件很好计算，假设一个盘块粗存放150个字符。所以，第200个字符就一定在盘块6上面，并且距离开头50个字符。这个就是顺序文件的一大优点，能够顺序存取。

        那么，顺序文件这种方式有什么问题吗？显然，一个问题的最初想法肯定是会又很多漏洞的。顺序文件的缺点在于：1.文件的大小得在文件创建的时候就就给定，不然，磁盘到底分配几个盘块给你，这个是不知道的；2.文件的大小不能方便的动态增长。就拿上卖弄的图来说，你得文件A如果想要增加内容的话，就只能写在12号盘块上面了，但是又不能将其覆盖。要么把文件A整体移动到别的有8块空闲盘块的位置去，要么把文件B移动到有3块空闲的位置上去。显然，这都是很消耗时间的。

串连文件结构

        为了解决顺序文件带来的不便，人们提出了索引文件（链式文件）。就像下面这个样子。

每一个FCB里面记录的是文件的第一个盘块号，然后每一个盘块里面还有一个指针专门用来记录下一个盘块的位置。这个样子就很好的解决了不能动态增长的问题。只要之后要增加文件内容，只要往后面添加文件指针就好了。
        一切看起来似乎很完美了，但是他也有它的缺点。我现在要找文件LLL12的第400个字符，并修改。因为文件不是顺序存放的，所以每一次我想要读取特定的字符的时候，得从头到尾的扫描一遍，直到找到我想要文件的位置。这样子就需要花费极大的时间了。还有一个问题，因为每一个盘块不再存放的内容不再是2的整数次幂了，因为得花一定的字节来存放指向下一个文件位置的信息。他们两个就好比数组和链表一样，各有个的优点和缺点。

引入FAT的串连文件结构

        为了找到一个更好的存放文件的方法，人们提出了索引顺序文件，整合了上面两种方法的优点。大家看这个图：

内存中会有这样一张FAT表，用来记录所有文件的存放的位置信息。这样子，既保证了能够随机存取（当然也得花点时间，但是这个是在内存中，总比索引文件从磁盘块上读取信息来的快），又保证了能够动态增长。这个也是windows用的FAT16,FAT32技术。但是这个就是最好的了吗？我之前的文章有写过关于内存管理中的分页机制。当时，我们为什么要提出多级页表的机制。这里的问题和那里是一样的。如果你的磁盘大小为200G,然后你得盘块为1KB,那么你得这张表得有20010241024项。有2亿项左右。如果一个表项占4个字节，那占了好多内存。也就说，你得内存不用来做别的事情了，就用来存放FAT表了。当然，微软之后也提出了改进的方法，例如引入了簇的概念。这里我就不再展开了。

索引文件结构

        现在的Unix和Linux都是采用这种方式来管理文件的。之所以FAT特别占用内存，原因就是因为它将所有的盘块号的索引都放进内存了。但是现实是不需要这样做的。我们仅仅只需要将自己的需要操作的文件的信息放进内存就好了。

可以看到，我们的索引表是在磁盘上面的，我们需要这个文件的时候就去从磁盘上将文件索引读取出来就好，这样子避免了内存空间的浪费。但是也结果缺点也是：增加了访问一次磁盘的操作。

        这样一种方式也不是万事无忧的。一个盘块大概可以存放数百个索引号，对于一些小文件来说，仅仅只需要10几个索引号就好了，这样子就造成了浪费。但是对于一些大文件来说，一个索引块还不能将其存放好，所以还得增加一个磁盘块来记录索引。同时还得把这个索引块也得加入到FCB中。但是这样子不就导致了每一个FCB的大小不一样了吗？因为有的使用一个盘块来记录索引，有的使用两个，有的使用三个…所以，想到我们的多级页表，我们这里使用多级索引就可以了。如下图：

文件的逻辑结构

        上面谈的都是文件的物理结构，是实实在在的文件的存放方式。那么，对于我们编程人员来说，文件的组织形式又是怎样的。

流式文件

        构成文件的基本单位式字符，文件时有逻辑意义的，无结构的一串字符的集合。Unix认为中的文件都是流式文件。这样的好处就是灵活性大。

记录文件

        文件是由若干个记录组成的，每一个记录有一个键，可以按键查找。

文件目录

        不知道大家有没有注意到，我们上面说的都是一个一个文件，但是实际上我们的电脑上面还有文件夹。另外，上面刚刚说了FCB这个概念，那么FCB又是存放在那里的，又是以怎么的形式存放的呢？这些都是下面我们要讨论的问题。这里先引入几个概念。

文件目录：把所有的FCB组织在一起，就构成了文件目录，即文件控制块的有序集合。
目录项：构成文件目录的项目（可以就是FCB）
目录文件：为了实现对文件目录的管理，通常将文件目录以文件的形式保存在外存。该文件称为目录文件。

        同样的道理，我们使用最简单的最粗暴的方法来存放FCB，就将所有的FCB放在一个目录文件里面。这个样子问题在于在寻找FCB的时候就是一个麻烦了。因为目录文件一般也是存在在磁盘上的。那么你就得每一次将文件目录所在的磁盘块先读出来，然后去找看看有没有自己想要的目录，没有的话，继续匹配，直到该磁盘块上的信息读取完毕。如果还没有的话就继续读取下一块磁盘信息。所以，这个方法不太好。

        于是人们又想出了两级目录，利用用户的来分开不同的目录文件。其实这个从本质上还是没有解决上面的那个问题。

        所以，最后提出了目录树的概念。也就是我们现在通用的目录树结构。看图最清楚啦。

这个样子就可以大大减少我们访问磁盘的次数了。好吧，其实也没有怎么减少我们的访问次数，我觉得是可以使用某种目录访问的算法来达到减少访问次数。

        那么综合一下，看看我们到底是怎么样来访问这个文件的。就使用上面的那幅图，我现在想要访问/b/ba目录。第一步，找到‘/’目录所在的地方，也就是根目录（root）所在的盘块号。但是似乎没有条件可以知道root目录的盘块号在哪里。所以，设计者们决定就使用一个固定盘块取存放根目录的信息（这里就是涉及到一个系统能否自举，我们必须得存一些固定的东西，其中就包括根目录的存放的位置）。那么我们现在就可以直接将根目录里面存放的FCB全部读取出来了。很明显，里面存放的就是a,b,c两个目录，一个文件的FCB，然后逐个读取FCB的信息，将其文件名与给定的‘b’进行比较，然后就找了目录b所对应的信息了。大家想一想，是不是有些不对劲的地方。我只需要文件的名字就好了啦，为什么要一次性将所有的FCB读取出来呢？要知道，每一个FCB也是很占大小的，磁盘的操作也是相当慢的，我们能少读一次就少读一次。所以，人们就提出了inode概念，也是我们俗称 i节点 。inode包括“目录的名字”，和“该目录的FCB存在盘块在的编号”。也就说，最后我们的目录文件存放的不再是文件的FCB了，而是inode。inode中有文件名和指向该文件所对应的 i 结点（FCB）的指针。现在再来举一个例子，就都清楚了。现在查找/usr/ast/mbox，那么查找步骤是：

首先找到根节点的inode信息，在《鸟哥的Linux私房菜》那本书上说，根节点的Inode在2号Inode节点上。我们假设读取了2号inode节点的信息，发现它指向了100号磁盘块，也就是上面的图中的第一幅画。然后读取该数据块的信息，进行匹配“usr”。找到后，知道inode为6号的地方存放的是目录usr的FCB的信息。然后读取6号inode节点的信息（这个节点还有一些其他的信息，也就是usr目录的FCB信息），找到它的目录下的文件的信息存放在132号盘块上。然后读取盘块为132号的信息，继续匹配字符“ast”,找到它的息在26号Inode上面。读取inode为26号的信息，找到它的文件信息存放在盘块号为496上面。所以读取496盘块信息，最后找到了mbox的inode节点的信息存放在60号上面。

        其实我这里我自己都觉得有些矛盾。首先在汤小丹老师《计算机操作系统》第4版的书第251页上说到：“…如Unix系统，便采用了把文件名和与文件描述符信息分开的方法，亦即，使文件描述信息单独形成一个称为索引节点的数据结构，简称为i节点。在文件目录中的每个目录项仅由文件名和指向该文件所对应的的i节点的指针所构成。”
        而在《鸟哥的Linux私房菜》中说到，inode节点的主要内容是记录文件的属性以及该文件实际的数据存放在几号block内。
        那么我就想要问，
        1.Inode节点到底存放的是什么内容
        2.Inode节点是不是也是存放在磁盘上面的

这里的内容是我想清楚后写上去的
目录项里面的确只有文件名和i节点号，然后i节点号指向了一个data block来描述自己的信息。当然，里面还有data blcok号来进一步描述文件信息。就像这张图：

        最后，那我们还是通过一张图来分析这个文件系统的工作原理。

首先，将一个磁盘分成了启动扇区和多个blockGroup。每一个blockGroup的东西就很重要了。首先第一个是superblock（超级块），用来记录文件系统的整体信息，例如inode和block总量，使用量，剩余量等等，是一个国定大小数据结构。文件系统的描述可以和superblock放在一起理解。块对应表就是用来记录data block的使用情况。inode对应表就是用来记录inode使用情况。前面说的这些都是固定大小的数据结构，所以，我们的根节点信息就放在他们的后面，相当于一个固定的位置。inodetable就是一个一个inode的集合，不是一张表的意思，指的是这一块位置都是存放inode节点的。inode就是用来记录文件的属性和文件数据真正存放的位置，也就是data block的盘号。最后的data block就是真正用来存放实际数据的。所以每一次我们重点就是要获取该文件的Inode节点信息，知道了它以后，我们就可以知道一切信息了。

        那么我们知道Indeo节点后，就可以知道文件存放的所有盘块信息了。不过要区分一点，这里说到文件系统是EXT2文件系统，和前面说的FAT不是一种方式。

文件存储空间的管理

        前面都是在讲怎么将文件分配到空闲磁盘上面去，上面的问题解决完了以后，我们是不是得想这样一个问题？OS怎么知道哪里有空闲盘块给你使用？文件删除后，空闲盘块又是怎么回收的呢？这个就是我们下面要讨论的问题。

空闲表法

        这个是一种连续分配的方式，适用于顺序文件的存储。这个也有它的优点，这里就不多讲了。

空闲链表法

        这个就是将空闲的盘块形成一个链表。当用户需要盘块的时候，就取出适当的盘块数给用户，回收时将盘块挂在空闲盘块的末尾。

位示图法

        位式图法是利用二进制的一位来表示磁盘中一个盘块的使用情况。

成组链法

        这个是一个较好的方法，需要掌握！

参考资料

https://wenku.baidu.com/view/defd02599a6648d7c1c708a1284ac850ad02043b