第六章 文件管理

文件

数据项&记录&文件

数据项分为：

• 基本数据项：描述对象的某些属性，例如学生的年龄，姓名学号等
• 组合数据项：由若干个基本数据项组合而成

记录：一组相关数据项的集合，用于描述一个对象在某方面的属性

文件：文件是指由创建者所定义的、 具有文件名的一组相关元素的集合，可分为有结构文件和无结构文件两种

• 有结构文件：文件由若干个相关的记录组成
• 无结构文件：被看成一个字符流

文件的属性

• 文件的类型

  • 
  • 
  • 
  • 

• 文件的长度

• 文件的物理位置

• 文件的创立时间

文件系统模型

• 对象及其属性：文件管理的对象有文件、目录和文件存储器
• 对对象操纵和管理的软件集合。这是文件系统的核心部分，实现了
  • 对文件存储空间的管理
  • 文件目录管理
  • 文件的逻辑地址向物理地址的转换
  • 文件的读写管理
  • 文件的共享和保护
• 文件系统接口。文件系统向用户提供的接口有命令接口、程序接口、图形用户接口三类，用户可以通过它们来使用文件系统。

文件的逻辑结构

文件的逻辑结构：从用户观点出发，所观察到的文件组织形式，是用户可以直接处理的数据及结构，独立于物理特性，又称为文件组织

• 无结构文件：流式文件
• 有结构文件：由一组相似的记录组成，又称记录式文件。每个记录又有若干数据项组成
• 根据有结构文件中的各条记录在逻辑上如何组织可以分为三类

顺序文件

顺序文件：文件中的记录一个接一个地顺序排列

• 串结构：记录之间的顺序与关键字无关
• 顺序结构：记录之间的顺序按关键字顺序排列

• 对于可变长记录，无法实现随机存取
• 对于定长记录，可随机存取，串结构无法快速检索
• 增加/删除一个记录比较困难

索引文件

解决可变长记录的随机存取

• 优点：将一个需要顺序查找的文件改造成一个可随机查找的文件，极大地提高了对文件的查找速度。
• 利用索引文件插入和删除记录也非常方便
• 缺点：除了主文件外还需要配置索引表，增加了存储开销

索引顺序文件

索引表是一个定长记录的串结构的顺序文件

• 基本克服了变长记录的顺序文件不能随机访问，以及不便于记录的删除和插入的缺点
• 仍保留的顺序文件的关键特征，即记录是按关键字的顺序组织起来的

多级索引顺序文件

文件的物理结构

对任一文件都存在两种形式的结构

• 文件的逻辑结构：从用户观点出发，所观察到的文件组织形式，是用户可以直接处理的数据及结构，独立于物理特性，又称为文件组织
• 文件的物理结构：又称为文件的存储结构。是指系统将文件存储在外存上所形成的一种存储组织形式，用户看不见，与存储介质的存储性能有关还和采用的外存分配方式有关
• 文件的逻辑结构和物理结构都将影响文件检索的速度

连续分配（顺序分配）

顺序文件结构

连续分配要求为每个文件分配一组相邻接的盘块，一组盘块的地址定义了磁盘上的一段线性地址。

• 把逻辑文件中的数据顺序地存储到物理上邻接的各个数据块中，这样形成的物理文件可以顺序读取
• 文件目录中为每个文件建立一个表项，其中记载文件的第一个数据库地址及文件长度
• 对于顺序文件连续读写多个数据库内容时，性能较好

• 优点：
  • 顺序访问容易，可以随机存取可以很快检索文件中的一个数据库
  • 顺序访问速度快
    • 磁头移动距离短，效率高
• 缺点：
  • 要求有连续的存储空间，可能会导致外部碎片，降低外存利用率【可以紧凑】
  • 必须事先直到文件的长度
    • 空间利用率不高
    • 不利于文件尺寸的动态增长

链接分配

• 链接文件：采用链接分配方式时，可通过在每个盘块上的链接指针，将同属于一个文件的多个离散盘块链接成一个链表，把形成的文件称为链接文件

• 隐式链接

  • 文件目录的每个目录项中，都须含有指向链接文件第一个盘块和最后一个盘块的指针，每个盘块中都含有指向下一个盘块的指针
  • 
  • 主要问题：只适合顺序访问，对随机访问极其低效
    • 为了提高检索速度和减少指针所占用的存储空间，可以将几个盘块组成一个簇
    • 减少了查找时间和指针所占用空间，但增大了内部碎片

• 显式链接

  • 把用于链接文件各物理块的指针，显示地存放在内存的一张链接表中
  • 整个磁盘仅设置一张文件分配表（FAT）
    • 分配给文件的所有盘块号都存放在该表中
  • 凡是属于某一文件的第一个盘块号，均作为文件地址被填入相应文件的FCB的物理地址字段中
  • 查找记录的过程是在内存中进行的，因而不仅显著提高了检索速度，而且大大减少了访问磁盘的次数
  • 

• 优点：

  • 无外部碎片，没有磁盘空间浪费
  • 无需事先知道文件大小。文件动态增长时，可动态分配空闲盘块

• 缺点：

  • 不能支持高效随机/直接访问，仅适合于顺序存取
  • 需要为指针分配空间【隐式链接】
  • 可靠性低
  • 文件分配表占用较大内存

索引分配

链接分配的问题

• 不能支持高效的直接存取
• FAT需要占用较大的内存空间1

假设每个盘块大小为1KB，每个盘块号占4个字节，则在一个索引块中可放256个文件物理块的盘块号。在两级索引时，最多可包含的存放文件的盘块的盘块号总数为256*256=64K个盘块号。可以得出：采用两级索引时，所允许的文件最大长度为64MB。

文件存储空间的管理

• 存储空间的基本分配单位是磁盘块

• 空闲分区表：属于连续分配方式，为每个文件分配一块连续的存储空间，系统为空闲区建立一张空闲表，存储序号，第一空闲盘块号和空闲盘块数。适合于可变大小分区的连续分配

• 

  分配时，可以按照之前的分配算法进行分配，如首次适应算法，当删除文件释放空间时，系统回收其存储空间，合并相邻空闲分区。

  实现简单，空闲分区分布较分散且数量较多时，空闲分区表很大需要较大的内存空间，会降低空闲分区表的检索速度

  浪费存储空间，不适合登记分散且数目很多的空闲分区，不利于基于存储块的链接文件和索引文件的存储空间分配

• 空闲链表法

  • 空闲盘块链：以盘块为单位，将空闲的盘块连接成一条链，当创建文件时，从链表头开始，依次摘下适当的数目的空闲盘块进行分配，系统回收时，将回收的盘块依次插入链表尾部

    • 优点：用于分配和回收一个盘块的过程非常简单

  • 空闲盘区链：以空闲盘区（可能包含多个连续空闲盘块）为单位，将空闲盘区连接成一条链，分配时一般采用首次适用算法，在回收盘区时，同样也要将回收区域相邻接的空闲盘区相合并

  • 

  • 问题：一段时间后，可能空闲分区链表中太多小分区，文件分配的存储空间太过分散，删除回收需要很长时间，若一个文件申请连续存储空间，则需要花费较长时间查找相邻的空闲分区

  • 适合非连续存储文件位示图：利用0,1表示物理块是否被使用，一般采用二维数组来存储，在进行盘块分配时，书序扫

    描位示图，从中找出一个或一组的空闲盘块，进行分配后更改位示图中的值

• 位示图：利用0,1表示物理块是否被使用，一般采用二维数组来存储，在进行盘块分配时，顺序扫描位示图，从中找出一个或一组的空闲盘块，进行分配后更改位示图中的值

  • 
  • 盘块的回收：
  • 将回收盘块的盘块号转换为位示图的行号和列好
    • i = (b-1)div n + 1，j = (b-1)mod n + 1
  • 修改位示图 map[i,j] = 0
  • 优点：
    • 很容易找到一个或一组连续的空闲分区
    • 占用空间小
  • 缺点：
    • 对于大硬盘难以将位示图全部装入内存
    • 磁盘空间快用完，性能严重下降

• 成组链接法

  • 

  • 

  • 

  • 每一组的第一个盘块用来记录下一组的盘块数量和盘块号的信息，其余号对应空闲块；每一个用于记录的磁盘块都是记录下一组的信息。

    

    分配201号盘块

    

    把300的磁盘块数据复制到超级块中

    回收没满直接插

    

    回收满了，新建一个区，先复制超级块，再新建超级块指向新回收的块

    

    

文件目录

• 文件目录也是一种数据结构，用于标识系统中的文件及其物理地址，供检索时使用

  • 对目录管理的要求如下：
    • 实现按名存取
    • 提高对目录的检索速度
    • 文件共享
    • 允许文件重名

• **文件控制块【FCB】：**用于描述和控制文件的数据结构

  • 从文件管理的角度来看，文件由文件体和FCB组成
  • 文件控制块是操作系统为了管理文件而设置的数据结构，存放了文件的有关说明信息，记录了系统对文件进行管理所需要的全部信息
  • FCB是文件存在的标志
  • FCB保存在文件目录中，一个FCB就是一个目录项
  • 内容包含
    • 基本信息：文件名、文件类型等
      • 地址信息：卷【存储文件的设备】、起始地址、文件长度
    • 存取控制信息：文件存取权限
    • 使用信息：创建时间、修改时间、访问时间

• 文件目录：文件控制块的有序集合

• 目录项：构成文件目录的项目，就是FCB

• **目录文件：**为了实现对文件目录的管理，通常将文件目录以文件的形式保存在外存，文件叫做目录文件。

索引结点

• UNIX系统中，采用了把文件名和文件描述信息分开的方式，把文件描述信息单独形成一个数据结构，叫索引结点
  • 为什么引入？
    • 在检索目录文件时，只用到了文件名，仅当找到一个目录项时，才需要从目录项中读取出该文件的物理地址，而其他一些对该文件进行描述的信息在检索目录时一概不要，显然在检索目录时这些信息不需要调入内存

目录结构

• 单级目录结构：所有用户的全部文件目录保存在一张目录表中，每个文件的目录项占用一个表项

  • 
  • 优点：实现了按名存取
  • 缺点
    • 查找速度慢
    • 不允许重名
    • 不便于实现文件共享

• 两级目录结构：分为主目录和用户目录

  • 为每个用户建立单独的用户文件目录
  • 系统中为所有用户建立一个主文件目录
  • 
  • 优点：
    • 一定程度解决了重名问题
    • 提高了文件目录检索效率
    • 简单的文件共享
  • 问题：不便用户文件的逻辑分类

• 层次目录结构：现在使用的多级目录，主目录称为根目录，数据文件称为树叶，其他的目录称为树的结点

  • 

  • 路径名：从树的根目录开始，把全部目录文件名和数据文件名，依次用/连接起来，即构成该数据文件的路径名

    • 系统中每个文件都有唯一的路径名

  • 当前目录：为每个进程设置一个当前目录，又称为工作目录。进程对各个文件的访问都相对于当前目录进行

  • 从当前目录到数据文件为止所构成的路径名称为相对路径名

  • 查询速度更快，层次结构更加清晰，能更有效地进行文件的管理和保护

  • 

  • 

  • 

文件共享和访问控制

文件共享的有效控制涉及两方面

• 同时存取
• 存取权限

• 实现文件共享的实质是可以从不同地方打开同一个文件
• 首要步骤是找到文件的目录项进而读取文件在外存的起始地址

链接目录项实现文件共享

即有向无环图实现

利用索引结点实现文件共享

• 文件物理地址及其它文件的属性相关信息，不再是存放在目录项中，而是放在索引结点中，在文件目录中只设置文件名和指向相应索引结点的指针
• 可以通过共享文件索引结点来共享文件。当用户需要共享文件时，新建目录项将索引结点指针指向共享文件的索引结点

利用符号链共享

由系统创建一个Link类型的新文件，新文件中只包含被创文件的路径名

新文件中的路径名，则只被看作是符号链。当B要访问被链接的文件F且正要读LINK类新文件时，将被OS截获， OS根据新文件中的路径名去读该文件，于是就实现了用户B对文件F的共享。

• 只是文件主才拥有指向其索引结点的指针，而共享文件的其他用户只有路径名
  • 优点：能连接任何机器上的文件
  • 缺点：备份可能产生多个拷贝

利用URL实现文件共享

总结