散列表(哈希表)

能够通过给定的关键字的值直接访问到具体对应的值的一个数据结构。也就是说把关键字映射到一个表中的位置来直接访问记录，以加快访问速度。

通常我们把关键字称为Key，把对应的记录称为value，通过Key访问一个映射表来得到value的地址。这个映射表叫作散列函数或者哈希函数，存放记录的数组叫作散列表。

其中有个情况，就是通过不同的Key，可能访问到同一个地址，这种现象叫作碰撞(Collision)。而通过某个Key一定会到唯一的Value地址。

文件系统

一、文件系统的实现

• 文件和目录是怎样存储。
• 磁盘空间是怎么样管理。
• 怎样使系统有效而可靠地工作。

1.1、文件系统布局

文件系统存放在磁盘上。多数磁盘会划分为一个或多个分区，每个分区中有一个独立的文件系统。磁盘的0号扇区称为主引导记录(Master Boot Record, MBR)。用来引导计算机。在MBR的结尾是分区表。该表给出每个分区的起始和结束地址。表中的一个分区被标记为活动分区。在计算机被引导时，BIOS读入并执行MBR。MBR做的第一件事情使确定活动分区，读入它的第一个块，称为引导块(boot block)，并执行之。引导块中的程序将装载该分区中的操作系统。为统一，每个分区都从一个引导块开始，即使它不包含一个可启动的操作系统。不过未来这个分区也许会有一个操作系统呢。

除了引导块之外，磁盘分区的布局是随着文件系统的不同而变化的。文件系统经常包含有如图所示的一些项目:

第一个是超级块（superblock）, 超级块包含文件系统的所有关键参数，在计算机启动时，或者在该文件系统首次使用时，超级块会被读入内存。超级块中典型信息包括：确定文件系统类型用的魔数，文件系统中块的数量以及其他重要的管理信息。

接着是文件系统中空闲块的信息，例如，可以用位图或指针列表的形式给出。后面也许跟随的是一组i节点，这是一个数据结构数组，每个文件一个，i节点说明了文件的方方面面。接着可能是根目录，它存放文件系统目录树的根部。最后，磁盘的其他部分存放了其他所有的目录和文件。

1.2、文件的实现

文件存储实现的 关键问题是记录各个文件分别用到哪些磁盘块。不同操作系统采用不同的方法。这一节我们讨论研究其中的一些方法。

1.2.1、连续分配

最简单的分配方案是把每个文件作为一连串连续数据块存储在磁盘上。所以，在块大小为1KB的磁盘上，50KB的文件要分 配50个连续的块。对于磁盘块大小为2KB的磁盘，将分配25个连续的块。

在图4-10a中是一个连续分配的例子，这里列出了头40块，从左面0块开始。初始化状态下，磁盘是空的。接着，从磁盘开始处（块0）开始写入长度为4块的文件A。紧接着，在文件A的结尾开始写入一个3块的文件B。

请注意，每个文件都从一个新的块开始，假如文件A实际上只有 3 $\frac{1}{2}$块空间，那么最后一块的结尾就实际上是浪费了一些空间。在图4-10中，一共列出了7个文件，每一个文件都从前面文件结尾的后续块开始。加阴影表示文件分割没有说明别的意思。

连续磁盘空间分配方案存在两大优势：

• 实现简单，记录每个文件用到的磁盘块简化为只需要记住两个数字即可：第一块的磁盘地址和文件的块数。给定了第一块的编号，一个简单的加法就可以找到任何其他块的编号。
• 读操作性能较好，因为在单个操作中就可以从磁盘上读出整个文件。只需要一次寻找(对第一个块)。之后不再需要寻道和旋转延迟，所以，数据以磁盘全带的速率输入。可见连续分配实现简单且具有高的性能。

连续磁盘空间分配方案明显缺陷：

• 随着时间推移，磁盘会变得零碎。

且看b)中，这里删除两个文件D和F。当删除一个文件时，它占用的块自然就释放了，在磁盘上留下一堆空闲块。磁盘不会在这个位置挤压掉这个空洞，因为这样会涉及复制空洞之后的所有文件，可能会有上百万的块。结果是，磁盘上最终既包含文件也有空洞。开始时，碎片并不是问题，因为每个新的文件都在先前文件的结尾部分之后的磁盘空间里写入。但是，磁盘最终会被充满，所以要么压缩磁盘，要么重新使用空洞所在的空闲空间。前者由于代价太高而不可行；后者需要维护一个空洞列表，这是可行的。但是，当创建一个新的文件时，为了挑选合适大小的空洞存入文件，就有必要知道该文件的最终大小。

1.2.2、链表分配

存储文件的第二种方案是为每个文件构造磁盘块链表。如图4-11所示。每个块的第一个字作为指向下一块的指针，块的其他部分存放数据。 与连续分配方案不同，这一方法可以充分利用每个磁盘块。不会因为磁盘碎片而浪费存储空间(除了最后一块中的内部碎片)。同样在目录项中，只需要存放第一块的磁盘地址，文件的其它快就可以从这个首块地址查找到。说什么目录项？？？？？

另一方面，在链表分配方案中，尽管顺序读文件非常方便，但是随机访问却相当缓慢。要获得块n，操作系统每一次都必须从头开始，并且要先读前面的n-1块，这就太慢了。

而且，由于指针占去了一些字节，每个磁盘块存储数据的字节数不再是2的整数次幂。虽然这个问题并不是非常严重，但是怪异的大小确实降低了系统的运行效率，因为许多程序都是以长度为2的整数次幂来读写磁盘块的。由于每个块的前几个字节被指向下一个块的指针所占据，所以要读出完整的一个块大小的信息，就需要从两个磁盘块中获得并拼接信息，这就会导致复制引发额外的开销。

1.2.3、采用内存中的表进行链表分配

取出每个磁盘块的指针字，把它们放在内存的一个表中，就可以解决上述链表的两个不足。图4-12表示了图4-11所示例子的内存中表的内容。这两个图中都有两个文件，文件A依次使用了磁盘块4、7、2、10和12，文件B依次使用了磁盘块6、3、11和14。利用图4-12中的表，可以从第4块开始，顺着链表走到最后，找到文件A的全部磁盘块。同样，从第6块开始，顺这链表走到最后，也能够找出文件B的全部磁盘块。这两个链都是以一个不属于有效磁盘编号的特殊标记(如-1)结束。内存中这样一个表格称为文件分配表(File Allocation Table, FAT)。

按这类方式组织，整个块都可以存放数据。虽然仍要顺着链在文件中查找给定的偏移量，但是整个链都存在于内存中，所以不需要任何磁盘空间引用，这样随机访问相比之前要好很多。与前面的方法相同，不管文件有多大，在目录项中只需要记录一个整数(起始块号)，按照它就可以找到文件的全部块。

这种方法的主要缺点是必须把整个表都存放在内存中。对于1TB的磁盘和1KB大小的块，这张表需要有10亿项，每一项对应一块磁盘块。每项至少三个字节，为了提高查找速度，有时需要4个字节。根据系统对空间或时间的优化方案，这张表要占用3GB或者2.4GB内存。显然FAT的管理方式不能较好地扩展并应用于大型磁盘中。而正是最初的MS-DOS文件系统比较实用，因此windows现在都支持它。

1.2.4、i节点

最后一个记录各个文件分别包含哪些磁盘块的方法是给每个文件赋予一个称为i节点(index-node)的数据结构，这个数据结构中记录了文件属性和文件块的磁盘地址。图14-3是一个简单描述。给定i节点，就能找到文件的所有块。我们看看它和FAT相比的优势是，即只有在对应的文件打开时，其i节点才在内存中。如果每个i节点占用n个字节，最多k个文件同时打开，那么为了打开文件而保留i节点的数组所占的全部内存仅仅时kn个字节，只需要提前保留这么多空间即可。

这个数组通常比文件分配表(FAT)所占据的空间要小。原因就是FAT保留所有磁盘块的链表的大小是与磁盘空间的大小成正比的，磁盘若有n块，文件分配表就需要有n项，磁盘变得越大，文件分配表也将线性增加。相反，i节点机制需要在内存中有一组数组，其大小是和同时打开文件得数量成线性正比的，而与磁盘大小无关。

i节点也有一个问题，如果每一个i节点只能存储固定数量的磁盘地址，那么当一个文件所含的磁盘块超出i节点所能容纳的数目怎么办？

一个解决方案是最后一个“磁盘地址”不指向数据块，而是指向一个包含额外磁盘块地址的块的地址(号拗口)。更高级的解决方案是：可以有两个或更多个包含磁盘地址的块，或指向其他存放地址的磁盘块的磁盘块。Unix和Windows NTFS文件系统采用了相似的方案。

二、目录的实现

读文件前，必须打开文件。打开文件时，操作系统利用用户给出的路径名找到相应的目录项。目录项中提供查找文件磁盘块所需要的信息。？

问操作系统利用用户给出的路径名找到相应的目录项，用户调用fopen系统API，传入文件路径，操作系统中文件系统/目录系统再找到目录项，而后目录项中存放要访问文件属性。

不同系统，这些信息可能是整个文件的磁盘地址(对于连续分配方案)、第一个块的编号(对于两种链表分配方案)或者是i节点号。无论怎么样，目录系统的主要功能是把ASCII文件名映射成定位文件数据所需的信息。

与此密切相关的问题是如何存放文件属性。每个文件系统维护文件所有者、创建时间等文件属性，它们必须存储在某个地方。一种显而易见的方法是把文件属性直接存放在目录项中。很多系统确实是这样实现的。如图4-14a所示：

在这个简单设计中，目录中有一个固定大小的目录项列表，每个文件对应一项，其中包含一个(固定长度)文件名、文件属性的结构体和用以说明磁盘块位置的一个或多个磁盘地址(至某个最大值)。

采用i节点的系统，还存在另一种方法，即把文件属性存放在i节点中而不是目录项中。在这种情形下，目录项会更短：只有文件名和i节点号。如图4-14b所示：

三、共享文件

当几个用户同在一个项目里工作时，他们常常需要共享文件。其结果是，如果一个共享文件同时出现在属于不同用户的不同目录下，工作起来就很方便。 如果一个共享文件同时出现在属于不同用户的不同目录下，工作起来就很方便。如下图所示：

• B 的目录与该共享文件的联系称为一个 链接(link)。
• 文件系统本身是一个有向无环图(DAG)而不是一棵树。

将文件系统组织成有向无环图使得维护变的复杂，必须付出一定的代价。

共享文件是方便的，但也带来一些问题：

authors: [Billow]