[科普中国]-空间分配

简介

存储器是计算机系统的重要组成部分。对于通用计算机而言，存储层次至少应具有三级：最高层为 CPU 寄存器，中间为主存，最底层是辅存。空间分配是指对主存和辅存空间分配。主存空间分配是指根据一定规则和策略将主存空间分配给进程或程序；外存空间分配则是按照一定策略将将文件存储到外存中。

主存空间分配方法直接存储分配方式直接存储分配方式要求存储器的可用空间已经确定，且确保各程序所用的地址之间互不重叠。缺点是用户感到不方便，存储器的利用率也不高。

静态存储分配方式静态存储分配方式中。在程序被装入、连接时，才确定它们在主存中的相应位置(物理地址)。系统必须分配其要求的全部存储空间．否则不能装入该用户程序。程序将占据着分配给它的存储空间直到程序结束。该存储空间的位置固定不变，也不能动态地申请存储空间。这种方式无法实现用户对存储空间的动态扩展，而且也不能有效地实现存储器资源的共享。

动态存储分配方式动态存储分配方式是不一次性将整个程序装入到主存中。可根据执行的需要，部分地动态装入。同时，在装入主存的程序不执行时，系统可以收回该程序所占据的主存空间。再者，用户程序装入主存后的位置，在运行期间可根据系统需要而发生改变。此外，用户程序在运行期间也可动态地申请存储空间以满足程序需求。由此可见，动态存储分配方式在存储空间的分配和释放上，表现得十分灵活，现代的操作系统常采用这种存储方式1。

外存空间分配方式连续分配方式连续分配(Continuous Allocation)要求为每一个文件分配一组相邻接的盘块。 一组盘块的地址定义了磁盘上的一段线性地址。例如，第一个盘块的地址为 b，则第二个盘块的地址为b+1，第三个盘块的地址为 b+2……。通常，它们都位于一条磁道上，在进行读/写时，不必移动磁头，仅当访问到一条磁道的最后一个盘块后，才需要移到下一条磁道，于是又去连续地读/写多个盘块。在采用连续分配方式时，可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中，这样所形成的文件结构称为顺序文件结构，此时的物理文件称为顺序文件。这种分配方式保证了逻辑文件中的记录顺序与存储器中文件占用盘块的顺序的一致性。为使系统能找到文件存放的地址，应在目

录项的“文件物理地址”字段中，记录该文件第一个记录所在的盘块号和文件长度(以盘块数进行计量)。图 1示出了连续分配的情况。图中假定了记录与盘块的大小相同。Count 文件的第一个盘块号是 0，文件长度为 2，因此是在盘块号为 0 和 1 的两盘块中存放文件 1 的数据。

如同内存的动态分区分配一样，随着文件建立时空间的分配和文件删除时空间的回收，将使磁盘空间被分割成许多小块，这些较小的连续区已难于用来存储文件，此即外存的碎片。同样，我们也可以利用紧凑的方法，将盘上所有的文件紧靠在一起，把所有的碎片拼接成一大片连续的存储空间。例如，可以运行一个再装配例程(repack routine)，由它将磁盘A 上的大量文件拷贝到一张软盘 B 或几张软盘(C，D，…)上，并释放原来的 A 盘，使之成为一个空闲盘。然后再将软盘 B(C，D，…)上的文件拷回 A 盘上。这种方法能将含有多个文件的盘上的所有空闲盘块都集中在一起，从而消除了外部碎片。但为了将外存上的空闲空间进行一次紧凑，所花费的时间远比将内存紧凑一次所花费的时间多得多。

链接分配如同内存管理一样， 连续分配所存在的问题就在于: 必须为一个文件分配连续的磁盘空间。如果在将一个逻辑文件存储到外存上时，并不要求为整个文件分配一块连续的空间，而是可以将文件装到多个离散的盘块中，这样也就可以消除上述缺点。在采用链接分配(Chained Allocation)方式时，可通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，把这样形成的物理文件称为链接文件。

由于链接分配是采取离散分配方式，消除了外部碎片，故而显著地提高了外存空间的利用率；又因为是根据文件的当前需要，为它分配必需的盘块，当文件动态增长时，可动态地再为它分配盘块，故而无需事先知道文件的大小。此外，对文件的增、删、改也十分方便。链接方式又可分为隐式链接和显式链接两种形式。

索引分配单级索引分配

链接分配方式虽然解决了连续分配方式所存在的问题，但又出现了下述另外两个问题：

(1) 不能支持高效的直接存取。 要对一个较大的文件进行直接存取， 须首先在 FAT 中顺序地查找许多盘块号。

(2) FAT 需占用较大的内存空间。由于一个文件所占用盘块的盘块号是随机地分布在FAT 中的， 因而只有将整个 FAT 调入内存， 才能保证在 FAT 中找到一个文件的所有盘块号。当磁盘容量较大时，FAT 可能要占用数兆字节以上的内存空间，这是令人难以接受的。

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

内存。为此，应将每个文件所对应的盘块号集中地放在一起。索引分配方法就是基于这种想法所形成的一种分配方法。它为每个文件分配一个索引块(表)，再把分配给该文件的所有盘块号都记录在该索引块中，因而该索引块就是一个含有许多盘块号的数组。在建立一个文件时，只需在为之建立的目录项中填上指向该索引块的指针。图3示出了磁盘空间的索引分配图。

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

索引分配方式的主要问题是：可能要花费较多的外存空间。每当建立一个文件时，便须为之分配一个索引块，将分配给该文件的所有盘块号记录于其中。但在一般情况下，总是中、小型文件居多，甚至有不少文件只需 1～2 个盘块，这时如果采用链接分配方式，只需设置 1～2 个指针。如果采用索引分配方式，则同样仍须为之分配一索引块。通常是采用一个专门的盘块作为索引块，其中可存放成百个、甚至上千个盘块号。可见，对于小文件采用索引分配方式时，其索引块的利用率将是极低的。

多级索引分配

当 OS 为一个大文件分配磁盘空间时， 如果所分配出去的盘块的盘块号已经装满一个索引块时， OS 便为该文件分配另一个索引块， 用于将以后继续为之分配的盘块号记录于其中。依此类推，再通过链指针将各索引块按序链接起来。显然，当文件太大，其索引块太多时，这种方法是低效的。此时，应为这些索引块再建立一级索引，称为第一级索引，即系统再分配一个索引块，作为第一级索引的索引块，将第一块、第二块……等索引块的盘块号填入到此索引表中，这样便形成了两级索引分配方式。如果文件非常大时，还可用三级、四级索引分配方式。

混合索引分配方式

所谓混合索引分配方式，是指将多种索引分配方式相结合而形成的一种分配方式。例如，系统既采用了直接地址，又采用了一级索引分配方式，或两级索引分配方式，甚至还采用了三级索引分配方式。 这种混合索引分配方式已在 UNIX 系统中采用。 在 UNIX SystemⅤ的索引结点中， 共设置了13个地址项， 即iaddr(0)～iaddr(12)， 如图所示。 在BSD UNIX的索引结点中，共设置了 13 个地址项，它们都把所有的地址项分成两类，即直接地址和间接地址。

1) 直接地址

为了提高对文件的检索速度，在索引结点中可设置 10 个直接地址项，即用 iaddr(0)～iaddr(9)来存放直接地址。换言之，在这里的每项中所存放的是该文件数据所在盘块的盘块号。假如每个盘块的大小为 4 KB，当文件不大于 40 KB 时，便可直接从索引结点中读出该文件的全部盘块号。

2) 一次间接地址

对于大、中型文件，只采用直接地址是不现实的。为此，可再利用索引结点中的地址项 iaddr(10)来提供一次

间接地址。这种方式的实质就是一级索引分配方式。图中的一次间址块也就是索引块，系统将分配给文件的多个盘块号记入其中。在一次间址块中可存放 1 K个盘块号，因而允许文件长达 4 MB。

3) 多次间接地址

当文件长度大于 4 MB + 40 KB 时(一次间址与 10 个直接地址项)， 系统还须采用二次间址分配方式。这时，用地址项 iaddr(11)提供二次间接地址。该方式的实质是两级索引分配方式。系统此时是在二次间址块中记入所有一次间址块的盘号。在采用二次间址方式时，文件最大长度可达 4 GB。同理，地址项 iaddr(12)作为三次间接地址，其所允许的文件最大长度可达 4 TB。