7、8目录、文件管理

文件控制块—FCB

为了能对一个文件进行正确的存取，必须为文件设置用于描述和控制文件的数据结构，称之为“文件控制块”（FCB）

文件与文件控制块一一对应

记录文件名及其存放地址、文件的说明和控制信息。（是谁？在哪里？什么权？）

文件管理程序借助于文件控制块中的信息对文件施以各种操作。

把文件控制块的有序集合称为文件目录，即一个文件控制块就是一个目录项。通常一个文件目录也被看作是一个文件，称为目录文件。

目录管理的要求如下：

实现“按名存取”；（最基本功能）

提高对目录的检索速度；

文件共享；

允许文件重名。

两级目录的特点：

基本克服了单级目录的缺点，并具有以下优点：

提高了检索目录的速度。

在不同的目录中可重名。

不同用户还可以使用相同/不同的文件名来访问系统中的同一个共享文件。

不提供子目录操作，还不方便；各用户之间被完全隔离的话用户访问其他用户文件时，不方便合作。

多级目录结构

层次结构更清晰、提供更灵活的权限管理等

但目录级别太多时也会增加路径检索层次，增加磁盘访问时间。

按文件的逻辑结构将文件分为两大类：记录式文件和流式文件。

按物理结构划分，文件主要有三类：顺序文件、链接文件、索引文件。

操作系统实现按名存取的关键在于：解决文件名与文件存储地址的转换。

（1）文件逻辑结构的类型

有结构文件（记录式）

①定长记录

②变长记录

如何组织记录：

顺序文件。系统需按该类型记录“长度”，通常定长。

索引文件。系统需为文件建立索引表。

索引顺序文件。建索引表，记录每组记录的第一个记录位置。

无结构文件（字符流式）

字节为单位，利用读写指针依次访问。

系统对该类文件不需格式处理。

①顺序文件

串结构：按记录形成的时间顺序串行排序。记录顺序与关键字无关；

顺序结构：按关键字排序。

检索方法：

从头检索，顺序查找要找的记录，定长的计算相对快。

顺序结构，可用折半查找、插值查找、跳步查找等算法提高效率

顺序结构：记录按关键字排序，可按关键字检索

定长：结合折半查找算法等提高检索速度

变长：从第1个记录开始顺序扫描，直到扫描到要检索的关键字标识的记录（例如：数据库、文件系统的基于文件名排序的目录检索）

顺序文件的优缺点：

不方便随机存取某条记录，但适用批量存取的场合。

适合磁带等特殊介质。

单记录的查找、修改等交互性差；增减不方便（改进办法：把增删改的记录登记在一个事务文件中，在某段时间间隔后再与原文件合并更新）

②索引文件

一个索引文件可以有多个索引表

    为方便用户根据不同记录属性检索记录，为顺序文件建立多个索引表，每种能成为检索条件的域都配备一张索引表。

索引文件的优缺点：

适用于变长记录，可提高检索速度，实现直接存取

索引表增加了存储开销

③索引顺序文件

④直接文件

外存分配方式

目标：有效利用外存空间，提高文件访问速度

常用三种方式：

连续分配

缺点：

会产生外存碎片。可紧凑法弥补，但需要额外的空间，和内存紧凑相比更花时间。

创建文件时要给出文件大小；存储空间利用率不高，不利于文件的动态增加和修改；

适用于变化不大顺序访问的文件，在流行的UNIX系统中仍保留了连续文件结构。如对换区

链接分配（不连续）

优点：

离散分配，消除外部碎片，提高利用率

同时适用于文件的动态增长；修改容易

索引分配

链接的不足：

顺序检索的时间成本：不能支持高效的盘块直接存取。要对一个文件进行直接存取，仍需在FAT中顺序的查找许多盘块号。

链接信息的空间成本：FAT需占用较大的内存空间。当磁盘容量较大时，FAT可能要占用数MB以上的内存空间。这是令人难以忍受的

改进：

系统运行时只涉及部分文件，FAT表无需全部调入内存

每个文件单独建索引表（物理盘块索引），记录所有分配给它的盘块号；

建立文件时，便分配一定的外存空间用于存放文件盘块索引表信息；

存储空间的管理

1）空闲表和空闲链表法

2）位示图法

3）成组链接法