一、文件存储空间管理的概念

由于文件存储设备是分成若干个大小相等的物理块，并以块为单位来交换信息的，因此，文件存储空间的管理实质上是一个空闲块的组织和管理问题，它包括空闲块组织，空闲块的分配和空闲块的回收等几个问题。

二、文件存储空间管理的方式

1． 空闲表法（空闲文件目录）

操作系统为磁盘外存上所有空闲区建立一张空闲表，每个表项对应一个空闲区，空闲表中包含序号、空闲区的第一块号、空闲块的块数等信息。

空闲表法适用于连续文件结构，其分配的方式是，在系统为某个文件分配空闲块时，首先扫描空闲表项，如找到合适的空闲区项，则分配给申请者，并把该项从空闲表中去掉。如果一个空闲区项不能满足申请者的要求，则把空闲表中的另一项满足要求的分区分配给申请者（连续文件结构除外）。如果一个空闲表项所含块数超过申请者要求，则为申请者分配了所要的物理块后，再修改该表项。 

2． 空闲链表法（自由链表法）

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

空闲盘块链是将磁盘上的所有空闲分区，以盘块为单位拉成一条链，当用户创建文件请求分配存储空间时，系统从链首开始，依次摘下适当数目的空闲盘块分配给用户；当用户删除文件时，系统将回收的盘块依次加入到空闲盘块链的末尾。

空闲盘区链是将磁盘上的所有空闲盘区（每个空闲盘区可包含若干个盘块）拉成一条链。在管理的线性表中，每一个表项对应一个空闲区，增加一项存放指向空闲块的指针，将磁盘上的所有空闲区（可包含若干个空闲块）拉成一条链。每个空闲区上除含有用于指示下一个空闲区的指针外，还有本盘区大小（盘块数）的信息。 

3． 位示图法

本方法利用二进制的一位来表示磁盘中一个盘块的使用情况，磁盘上所有的盘块都有与之对应的一个二进制位。当其值为0时，表示对应的盘块空闲，当其值为1时，表示对应的盘块已经分配。 

4． 成组链接法

空闲表法和空闲链表由于空闲表太长而不适合大型文件系统的使用。成组链接法是两种方法相结合的一种管理方法，兼备了两种方法的优点而克服了两种方法的缺点。其大致的思想是：把空闲的n个空闲扇区的地址保存在第一个空闲扇区内，其后一个空闲扇区内则保存另一顺序空闲扇区的地址，以此类推，直至所有空闲扇区都予以链接。

以下以UNIX操作系统为例，说明成组链接法的原理。

（1） UNIX操作系统采用索引结构存放文件物理块的地址

    在UNIX 操作系统中，一个块定义为512 bytes,每一个文件对应一个唯一的机内代码，称为i节点，在文件的i节点中，放有存放文件的物理块号，由对应文件的逻辑字节偏移量计算出逻辑块号后，就可搜索i节点的地址索引结构而得文件的物理块号。

（2） UNIX system 的i节点中，定义有一个40字节长的字符数组。

由于每个物理块占用3个字节，因此，此字符组最多可以放下13个物理块号。显然，对于大于13个物理块（6.5KB）的文件，i节点中的索引数组将无法存放所有的物理块号。

（3） UNIX系统把文件分为小型、中型、大型和巨型四种。

（4） UNIX 系统文件的物理结构如图1

（5）UNIX的空闲块管理也使用类似的方法

思维导图

文件的初始化和划分

物理磁盘分为多个文件卷
文件卷分为目录区和文件区
文件区：存放文件数据
目录区：存放文件目录信息（FCB）、用于磁盘存储空间管理的信息

文件存储空间管理方法

1、存储空间管理——空闲表法

用一张表来记录磁盘中的空闲块，空间的回收和分配都只需要对该表进行操作即可

2、存储空间管理——空闲链表法

空闲盘块链：

空闲盘区链：

3、存储空间管理——位示图法

用一张位图来记录每一个物理块的空闲状态，分配和回收都对位图进行操作

4、存储空间管理——成组链接法

超级块

成组链接法必须要有一个超级块，作为硬盘所有物理块的头指针，指向下一组空闲磁盘块。

分配：

回收：

一、外存分配方式

a.目标：有效利用外存空间，提高文件访问速度
b.采用的磁盘分配方式决定了文件的物理结构：
顺序结构；链接式结构；索引式结构。

c.常用的外存组织三种方式：

1. 连续分配（顺序结构）
   a.为每一个文件分配一组相邻的盘块。
   b.逻辑文件中的记录顺序与存储器中文件占用盘块的顺序一致。
   优点：顺序访问容易，读写速度快
   缺点：
   *会产生外存碎片。可紧凑法弥补，但需要额外的空间，和内存紧凑相比更花时间。
   *创建文件时要给出文件大小；存储空间利用率不高，不利于文件的动态增加和修改；
   适用于变化不大顺序访问的文件，在流行的UNIX系统中仍保留了连续文件结构。如对换区

2. 链接分配（不连续）（链接式结构）
   可以为每一个文件分配一组不相邻的盘块。
   设置链接指针，将同属于一个文件的多个离散盘块链接成一个链表，这样形成的文件称为链接文件。会有链接成本。
   （1）优点：
   离散分配，消除外部碎片，提高利用率
   同时适用于文件的动态增长；修改容易
   ==>>不足：
   ①顺序检索的时间成本：不能支持高效的盘块直接存取。要对一个文件进行直接存取，仍需在FAT中顺序的查找许多盘块号。
   ②链接信息的空间成本：FAT需占用较大的内存空间。当磁盘容量较大时，FAT可能要占用数MB以上的内存空间。这是令人难以忍受的
   （2）链接有两种形式：
   ①隐式链接
   a.链接信息隐含记录在盘块数据中；记录中只有开始盘块号和结束盘块号
   b.每个盘块拿出若干字节，记录指向下一盘块号的指针。（减少了每一块存储的字节数）
   c.问题：只能顺着盘块读取，可靠性低（花费的时间长）
   ②显式链接（FAT–file allocationtable）
   a.链接信息以信息表的形式显示存放
   b.属于一个文件的盘块通过链接成为一体，每个链条的首地址作为文件地址记录在相应文件的FCB（文件控制块）的“物理地址”字段中。
   c.记录盘块链接的指针显示地记录为一张链接表
   d.所有已分配的盘块号都记录在其中，称文件分配表（FAT）
   e.为了提高文件系统访问速度，FAT一般常驻内存
   （根据FAT可知外存大小）
   

3. 索引分配（索引式结构）
   a.系统运行时只涉及部分文件，FAT表无需全部调入内存
   b.每个文件单独建索引表（物理盘块索引），记录所有分配给它的盘块号；
   c.建立文件时，便分配一定的外存空间用于存放文件盘块索引表信息；
   （1）单级索引分配
   分配一个盘块存储该文件占用的盘块号
   a.索引形式适合大文件
   b.中、小型文件，只需若干链接即可。若用索引分配方式，用一个盘块存放少量索引信息反而不适用。
   （2）多级索引
   a.若文件较大,存放索引表也需要多个盘块（索引盘块）。
   b.索引盘块亦需要按顺序管理起来
   ☆若索引盘块数量较少，比指针链接方式浪费空间，用指针链接的方式即可；
   ☆若索引盘块较多，需对索引盘块也采用索引方式管理，形成多级索引
   FBC中存放文件名和主索引号，主索引中再存放一级索引
   
   （3）混合组织索引（增量式索引组织方式）
   一个索引结点定义为13个地址项：iaddr（0）~iaddr（12），总的来说分为两种：直接地址、间接地址
   a. iaddr（0）~iaddr（9）存放直接地址，即存文件数据的盘块号（仅需访问磁盘一次）
   b. iaddr（10）存放单级索引的索引盘块号（需两次访问磁盘）
   c. 剩余的用于文件较大时存放多级索引数据。
   *iaddr（11）存放二级索引的主索引盘块号（需三次访问磁盘）
   *iaddr（12）存放三级索引的主索引盘块号（需四次访问磁盘）

例题：

二、存储空间的管理

为实现存储空间分配，系统需要：
a.记住空闲存储空间使用情况；为空间设置相应的数据结构；
b.提供对存储空间分配、回收的操作手段。

典型的管理方法：
（1）空闲表和空闲链表法
①空闲表法
常用于连续分配管理方式
数据结构:
a.系统为外存上的所有空闲区建立一张空闲表
b.每个空闲区对应一个空闲表项（表项包括序号、空闲区的第一个盘块号、空闲盘块数等。）
c.将所有空闲区按其起始盘块号递增的次序排列
②空闲链表法
将所有空闲盘区拉成一条空闲链。
数据结构：链
根据构成链所用基本元素的不同，可把链表分成两种形式：
a.空闲盘块链
优点：分配和回收一个盘块的过程非常简单，链表长，大量分配时需要操作的指针多
b.空闲盘区链
链表长度不定，分配时操作的指针数量相对较少，但分配回收操作相对复杂。

（2）位示图法
值为0表示对应的盘块空闲，为1表示已分配。有的系统则相反。
总块数：mn

a.盘块号计算公式：
j从1开始：盘块号 = 列总数*（i-1）+ j
j从0开始：盘块号 = 列总数*（i-1）+ j+1
b.根据盘块算行列计算公式：
i从1开始：i=(盘块号-1)/列数+1；j=(盘块号-1)%列数+1
i从0开始：i=(盘块号-1)/列数；j=(盘块号-1)%列数
c.优缺点：从位示图中很容易找到一个或一组相邻接的空闲盘块。但限于容量问题，常用于微型机和小型机中

（3）成组链接法
a.大型文件系统，空闲表或空闲链表太长不方便管理操作。
b.UNIX系统中采用成组链接法，这是将两种方法结合而形成的一种空闲盘块管理方法。
c.中心思想：
所有盘块按规定大小划分为组；
组间建立链接；
组内的盘块借助一个系统栈可快速处理，且支持离散分配回收