操作系统17：外存组织方式和文件存储管理

目录

1、外存的组织方式

（1）连续组织方式

（2）链接组织方式

2.1 - 隐式链接

2.2 - 显式链接

（3）索引组织方式

3.1 - 单级索引组织方式

3.2 - 多级索引组织方式

3.3 - 增量式索引组织方式

2、文件存储空间的管理

（1）空闲表法和空闲链表法

1.1 - 空闲表法

1.2 - 空闲链表法

（2）位示图法

（3）成组链接法

3.1 - 空闲盘块的组织

3.2 - 空闲盘块的分配与回收

---

1、外存的组织方式

        文件的物理结构直接与外存的组织方式有关。对于不同的外存组织方式，将形成不同的文件物理结构。目前常用的外存组织方式有：

• 连续组织方式。在对文件采取连续组织方式时，为每个文件分配一片连续的磁盘空间，由此所形成的文件物理结构将是顺序式的文件结构。
• 链接组织方式。在对文件采取链接组织方式时，可以为每个文件分配不连续的磁盘空间，通过链接指针将一个文件的所有盘块链接在一起，由此所形成的将是链接式文件结构。
• 索引组织方式。在对文件采取索引组织方式时，所形成的将是索引式文件结构。

//各种文件组织方式的优劣，可类比对应的数据结构性能的优劣，如数组、链表、Hash表等

（1）连续组织方式

        连续组织方式又称连续分配方式，要求为每一个文件分配一组相邻接的盘块。通常它们都位于一条磁道上，在进行读/写时，不必移动磁头。在采用连续组织方式时，可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中，这样所形成的文件结构称为顺序文件结构，此时的物理文件称为顺序文件。//产生顺序文件，保证了逻辑记录顺序与磁盘块的顺序一致

        这种组织方式保证了逻辑文件中的记录顺序与存储器中文件占用盘块的顺序的一致性。为使系统能找到文件存放的地址，应在目录项的“文件物理地址”字段中记录该文件第一个记录所在的盘块号和文件长度(以盘块为单位)。

        连续组织方式的主要优点：顺序访问容易且访问速度快。由连续分配所装入的文件，其所占用的盘块可能是位于一条或几条相邻的磁道上，磁头的移动距离最少，因此，这种对文件访问的速度是几种存储空间分配方式中最高的一种。//速度最快

        连续组织方式的主要缺点：

• 分配连续的存储空间，会产生出许多外部碎片，严重地降低了外存空间的利用率。如果定期利用紧凑方法来消除碎片则又需花费大量的机器时间。
• 必须事先知道文件的长度。文件的大小有时只能靠估算，一般情况下会将文件长度估得比实际的大（预防不足），从而造成浪费。
• 不能灵活地删除和插入记录。为保持文件的有序性，在删除和插入记录时，都需要对相邻的记录做物理上的移动，还会动态地改变文件的大小。

（2）链接组织方式

        采用链接组织方式时，可为文件分配多个不连续的盘块，再通过每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，由此所形成的物理文件称为链接文件。

        链接组织方式的主要优点是：//解决了连续分配方式的不足

• 消除了磁盘的外部碎片，提高了外存的利用率。
• 对插入、删除和修改记录都非常容易。
• 能适应文件的动态增长，无需事先知道文件的大小。

        链接方式又可分为隐式链接和显式链接两种形式。

2.1 - 隐式链接

        采用隐式链接组织方式时，在文件目录的每个目录项中，都须含有指向链接文件第一个盘块和最后一个盘块的指针，而在每个盘块中都含有一个指向下一个盘块的指针。如下图所示：

// 上图所示的链接顺序为：9->16->1->10->25，一共使用了5个盘块

        如果一个指针占用 4 个字节，对于盘块大小为 512 字节的磁盘，则每个盘块中只有 508 个字节可供用户使用。//指针太多，浪费磁盘空间

        隐式链接组织方式的主要问题在于，它只适合于顺序访问，它对随机访问是极其低效的。此外，只通过链接指针将一大批离散的盘块链接起来，其可靠性较差，因为只要其中的任何一个指针出现问题，都会导致整个链的断开。//随机访问低效+可靠性差

        对指针占用磁盘空间的改进思路：

        为了提高检索速度和减小指针所占用的存储空间，可以将几个盘块组成一个簇(cluster)，以簇为单位进行盘块分配，但这种方式却增大了内部碎片。//就是把多个盘捆成一起使用一个指针，连续分配和链式分配的折中版本

2.2 - 显式链接

        把用于链接文件各物理块的指针显式地存放在内存的一张链接表中，该表在整个磁盘中仅设置一张。//指针不再是隐式的放在物理盘块中了，而是放在内存中的一张表里

        如上图所示，表的序号是物理盘块号，从 0 开始，直至 N - 1（N为盘块总数）。在每个表项中存放链接指针，即下一个盘块号。//链接顺序为：2->4->5->1

        在该表中，凡是属于某一文件的第一个盘块号，均作为文件地址被填入文件的 FCB 的“物理地址”字段中。由于查找记录的过程是在内存中进行的，因而不仅显著地提高了检索速度，而且大大减少了访问磁盘的次数。//寻址提速

        由于分配给文件的所有盘块号都放在该表中，故把该表称为文件分配表 FAT(File Allocation Table)。

//在文件分配表的实际应用过程中，可以发现 FAT 始终与磁盘大小及利用率上存在着矛盾

windows 系统中的 FAT12 -> FAT16 -> FAT32 -> NTFS：

        FAT12 以盘块为基本分配单位，每个 FAT 表项占12 位，所以表中最多允许有 4096(2^12) 个表项。//如果盘块大小固定，那么存储空间的大小也就限制了，所以使用簇（多个磁盘块组合）

        FAT16 将表项位数增至 16 位，最大表项数将增至 65536(2^16)个，支持硬盘容量的增加。//如果表项固定，磁盘容量太大，那么簇就越大（多个磁盘块组合），簇越大，内部碎片就越多

        FAT32 将表项位数增至 32 位，能支持更小的簇，使磁盘具有更高的存储器利用率。//主要是随着磁盘空间加大，解决内部碎片过多的问题，因为 FAT32 比 FAT16 文件要大，所以访问效率要比 FAT16 慢。

        NTFS 是以簇作为磁盘空间分配和回收的基本单位的。一个文件占用若干个簇，簇只属于一个文件。这样，在为文件分配磁盘空间时，就无须知道盘块的大小，只要根据不同的磁盘容量，选择相应大小的簇，使 NTFS 具有了与磁盘物理块大小无关的独立性。// NTFS（New Technology File System）以簇为基本单位

（3）索引组织方式

        链接组织方式虽然解决了连续组织方式所存在的问题，但又出现了另外两个问题，即：

• 不能支持高效的直接存取，要对一个较大的文件进行存取，须在 FAT 中顺序地查找许多盘块号。
• FAT 需占用较大的内存空间，当磁盘容量较大时，FAT 可能要占用数 MB 以上的内存空间。

3.1 - 单级索引组织方式

        思想：事实上，在打开某个文件时，只需把该文件占用的盘块的编号调入内存即可，完全没有必要将整个 FAT 调入内存。

        索引分配方法就是为每个文件分配一个索引块(表)，把分配给该文件的所有盘块号都记录在该索引块中。在建立一个文件时，只须在为之建立的目录项中填上指向该索引块的指针。

        索引组织方式的主要优点是支持直接访问。当要读文件的第 i 个盘块时，可以直接从该文件的索引块中找到第 i 个盘块的盘块号；此外索引分配方式也不会产生外部碎片。当文件较大时，索引分配方式无疑要优于链接分配方式。//适合中大型文件

        索引组织方式的主要问题是，每当建立一个索引文件时，应为该文件分配一个索引块将分配给该文件的所有盘块号记录于其中。在每一个索引块中可存放数百个盘块号。但对于中、小型文件，其本身通常只占有数个到数十个盘块，甚至更少，但仍须为之分配一索引块。可见，对于小文件采用索引分配方式时，其索引块的利用率将是极低的。//对于小文件来说，浪费索引块空间

3.2 - 多级索引组织方式

        当文件太大，其索引块太多时，应为这些索引块再建立一级索引，称为第一级索引，即系统再分配一个索引块，作为第一级索引的索引块，将第一块、第二块、···.··等索引块的盘块号填入到此索引表中，这样便形成了两级索引分配方式。如果文件非常大时，还可用三级、四级索引分配方式。//为索引块再建立索引

        多级索引的主要优点是：大大加快了对大型文件的查找速度。其主要缺点是，在访问一个盘块时，其所需启动磁盘的次数随着索引级数的增加而增多，即使是对于小文件，也是如此。实际情况是，通常总是以中、小文件居多，而大文件是较少的。因此可见，如果在文件系统中仅采用了多级索引组织方式，并不能获得理想的效果。//多级索引方式适合对大文件的查找

3.3 - 增量式索引组织方式

        思想：为了能较全面地照顾到小、中、大及特大型作业，可以采取多种组织方式来构成文件的物理结构。//小文件使用直接寻址，中等文件使用单级索引，大型文件使用多级索引

        所谓增量式索引组织方式，就是基于上述的基本思想来组织的，它既采用了直接寻址方式，又采用了单级和多级索引组织方式(间接寻址)。通常又可将这种组织方式称为混合组织方式。在 UNIX 系统中所采用的就是这种组织方式。

        在 UNIX System V 的索引结点中设有 13 个地址项，即 addr-0 ~ addr-12，该系统的外存组织方式如下：

1. 直接地址。为了提高对文件的检索速度，在索引结点中可设置直接地址项（一般为10个，addr-1 ~ addr-9），用来存放直接地址（盘块号），这样就可以直接获得该文件的盘块地址。一般把这种寻址方式称为直接寻址。
2. 一次间接地址。对于大、中型文件，只采用直接地址是不现实的。为此，需再利用索引结点中的地址项 addr-10 来提供一次间接地址(single indirect)。这种方式的实质就是单级索引分配方式。
3. 多次间接地址。当文件长度太大时，使用一次间址与 10个直接地址项时地址空间仍不足，系统还需采用二次间址分配方式。这时，用地址项 addr-11 提供二次间接地址(double indirect)。该方式的实质是两级索引分配方式。同理，地址项 addr-12 作为三次间接地址(triple indirect)。

2、文件存储空间的管理

        为了实现上述任何一种文件组织方式，都需要为文件分配盘块，因此必须知道磁盘上哪些盘块是可用于分配的。故在为文件分配磁盘时，除了需要文件分配表外，系统还应为可分配存储空间设置相应的数据结构，即设置一个磁盘分配表(Disk Allocation Table)，用于记住可供分配的存储空间情况。//文件分配磁盘 -> 文件分配表+磁盘分配表

        此外，还应提供对盘块进行分配和回收的手段。不论哪种分配和回收方式，存储空间的基本分配单位都是磁盘块而非字节。

        下面介绍几种常用的文件存储空间的管理方法。

（1）空闲表法和空闲链表法

1.1 - 空闲表法

        什么是空闲表？

        系统为外存上的所有空闲区建立一张空闲表，每个空闲区对应一个空闲表项，表项中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息。再将所有空闲区按其起始盘块号递增的次序排列，形成空闲盘块表，如下图所示。//空闲表用在文件的连续分配方式中

        存储空间的分配与回收

        空闲盘区的分配与内存的分区(动态)分配类似，同样是采用首次适应算法和最佳适应算法等，它们对存储空间的利用率大体相当，都优于最坏适应算法。

        在系统为某新创建的文件分配空闲盘块时，先顺序地检索空闲表的各表项，直至找到第一个其大小能满足要求的空闲区，再将该盘区分配给用户(进程)，同时修改空闲表。//适应算法分配

        系统在对用户所释放的存储空间进行回收时，也采取类似于内存回收的方法，即要考虑回收区是否与空闲表中插入点的前区和后区相邻接，对相邻接者应予以合并。//回收空闲区合并

        应该说明，在内存分配上，虽然较少采用连续分配方式，然而在外存的管理中，由于这种分配方式具有较高的分配速度，可减少访问磁盘的 I/O 频率，故它在诸多分配方式中仍占有一席之地。

1.2 - 空闲链表法

        空闲链表法是将所有空闲盘区拉成一条空闲链。根据构成链所用基本元素的不同，可把链表分成两种形式：空闲盘块链和空闲盘区链。//构成链的单位不同

        空闲盘块链

        空闲盘块链将磁盘上的所有空闲空间以盘块为单位拉成一条链，其中的每一个盘块都有指向后继盘块的指针。

        当用户因创建文件而请求分配存储空间时，系统从链首开始，依次摘下适当数目的空闲盘块分配给用户。当用户因删除文件而释放存储空间时，系统将回收的盘块依次挂在空闲盘块链的末尾。//盘块分配与回收

        这种方法的优点是用于分配和回收一个盘块的过程非常简单，但在为一个文件分配盘块时，可能要重复操作多次，分配和回收的效率较低。又因为它是以盘块为单位，相应的空闲盘块链会很长。//分配和回收多个盘块时效率低

        空闲盘区链

        空闲盘区链将磁盘上的所有空闲盘区(每个盘区可包含若个盘块)拉成一条链。在每个盘区上除含有用于指示下一个空闲盘区的指针外，还应有能指明本盘区大小(盘块数)的信息。

        分配盘区的方法与内存的动态分区分配类似，通常采用首次适应算法。在回收盘区时，同样也要将回收区与相邻接的空闲盘区相合并。在采用首次适应算法时，为了提高对空闲盘区的检索速度，可以采用显式链接方法，亦即，在内存中为空闲盘区建立一张链表。

         空闲盘区链的优点和缺点刚好与空闲盘块链的优缺点相反，即分配与回收的过程比较复杂，但分配和会收的效率可能较高，每次为文件分配多个连续的块，且空闲盘区链较短。

（2）位示图法

        什么是位视图？

        位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况。当其值为 “0” 时，表示对应的盘块空闲；为 “1” 时，表示已分配。本质就是用一位的两种状态来标志空闲和已分配两种情况。

        磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，称为位示图。通常可用 m x n 个位数来构成位示图，并使 m x n 等于磁盘的总块数，如下图所示。位示图也可描述为一个二维数组 map [ m，n ]：//一个二进制位代表一个盘块

        盘块的分配

        根据位示图进行盘块分配时，可分三步进行：//查找->转换->修改

1. 顺序扫描位示图，从中找到值为“0”的二进制位。
2. 将所找到的二进制位转换成与之相应的盘块号。
3. 修改位示图，令 map [ i，j ] = 1。

        盘块的回收

        盘块的回收分两步：//转换 -> 修改

1. 将回收盘块的盘块号转换成位示图中的行号和列号。
2. 修改位示图。令 map [ i，j ] = 0。

        位视图的主要优点是从图中很容易找到一个或一组相邻接的空闲盘块。例如，我们需要找到 6个相邻接的空闲盘块，这只需在位示图中找出 6 个其值连续为 “0” 的位即可。

        此外，由于位示图很小，占用空间少，因而可将它保存在内存中，进而使在每次进行盘区分配时，无需首先把盘区分配表读入内存，从而节省了许多磁盘的启动操作。

//位视图占用空间下，查找速度快

        因此，位示图常用于微型机和小型机中，如 CP/M、Apple-DOS 等 OS 中。

（3）成组链接法

        空闲表法和空闲链表法都不适用于大型文件系统，因为这会使空闲表或空闲链表太长。在UNIX 系统中采用的是成组链接法，这是将上述两种方法相结合而形成的一种空闲盘块管理方法，它兼备了上述两种方法的优点而克服了两种方法均有的表太长的缺点。//空闲表+空闲链表

3.1 - 空闲盘块的组织

        空闲盘块号栈：用来存放当前可用的一组空闲盘块的盘块号(最多含 100 个号)，以及栈中尚有的空闲盘块(号)数 N。顺便指出，N 还兼作栈顶指针用。例如，当 N = 100 时，它指向 S.free(99)。//使用栈来保存盘块号，每一个栈保存100个盘块

        由于栈是临界资源，每次只允许一个进程去访问，故系统为栈设置了一把锁。下图示出了空闲盘块号栈的结构。其中，S.free(0) 是栈底，栈满时的栈顶为 S.free(99)。

        文件区：文件区中的所有空闲盘块被分成若干个组，比如，将每 100 个盘块作为一组。假定盘上共有 10000 个盘块，每块大小为 1KB，其中第 201 ~ 7999 号盘块用于存放文件，即作为文件区，这样，该区的最末一组盘块号应为 7901 ~ 7999；次末组为 7801 ~ 7900，倒数第二组的盘块号为 301 ~ 400；第一组为 201 ~ 300，如上图所示。

        盘块链：将每一组含有的盘块总数 N 和该组所有的盘块号记入其前一组的第一个盘块的 S.free(0) ~ S.free(99) 中。这样，由各组的第一个盘块可链成一条链。

        空闲盘块号：将第一组的盘块总数和所有的盘块号记入空闲盘块号栈中，作为当前可供分配的空闲盘块号。

        结尾标志：最末一组只有 99 个盘块，其盘块号分别记入其前一组的 S.free(1) ~ Sfree(99) 中而在 S.free(0) 中则存放 “0”，作为空闲盘块链的结束标志。(注：最后一组的盘块数应为 99，不应是 100，因为这是指可供使用的空闲盘块。其编号应为（1 ~ 99），0 号中放空闲盘块链的结尾标志。)

3.2 - 空闲盘块的分配与回收

        当系统要为用户分配文件所需的盘块时，须调用盘块分配过程来完成。

        该过程首先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格。

        若该盘块号已是栈底，即 S.free(0)，这是当前栈中最后一个可分配的盘块号。由于在该盘块号所对应的盘块中记有下一组可用的盘块号，因此，须调用磁盘读过程将栈底盘块号所对应盘块的内容读入栈中，作为新的盘块号栈的内容，并把原栈底对应的盘块分配出去(其中的有用数据已读入栈中)。然后，再分配一相应的缓冲区(作为该盘块的缓冲区)。最后，把栈中的空闲盘块数减 1 并返回。//对S.free(0)需要做特殊处理，因为这个盘块记有下一组可用的盘块号

        在系统回收空闲盘块时，须调用盘块回收过程进行回收。它是将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加 1 操作。当栈中空闲盘块号数目已达 100 时表示栈已满，便将现有栈中的 100 个盘块号记入新回收的盘块中，再将其盘块号作为新栈底。