16
7.2.1一级目录结构

一级目录结构：为外存上的全部文件设立一张线性排 列的目录表，包含所有文件的FCB。每建立一个新文 件即在目录中增加一个FCB，每当删除一个文件即删 除对应的FCB，当要访问一个文件时，先按文件名在 目录中找到对应的文件FCB。
cat test data … record
文件目录
文件
文 件 1
文 件 2
文 件 3
文 件 n
17

一级目录通常按卷（可理解为一盘磁带，一个逻辑磁盘） 构造，即把一卷中的全部文件形成一级目录表，保存在 该卷的固定区域，使用时先将目录表读到内存。
优点：简单，实现容易，能实现“按名存取”。 缺点：

1）当系统中的文件数很多时，则查找时间长；
9
• 文件的物理组织方法
① 顺序结构 文件顺序连续存放于文件存储器上（如磁带文 件，光盘文件）。 L1
变 长 L2 记录2 记 录 记录2 记录3 主要优点：1）顺序访问容易；2）顺序访问速度快。 文 件 …… 主要缺点： …… 连 续 1）必须已知文件的最大长度； 存 2）扩展性差，不宜用来存放用户文件、数据库文件等经常被 L 记录m Lm 放 结 修改的文件。 记录m 构 等长记录文件连续存放结构
13
索引结构不仅适应于顺序存取，也适应于随机存取。

缺点是：
⑴ 增加了存储空间的开销。
⑵ 在存取文件时需要至少访问存储器二次以上。一 次是访问索引表，另一次根据索引表提供的物理块号 访问文件信息。 改进的方法：当对某个文件进行操作之前，系统预 先把索引表放入内存。因此，文件的存取就可直接在 内存通过索引表确定物理地址块号，而访问磁盘的动 作只需要一次。
11
③ 索引结构 文件不连续存放于文件存储器上，使用一张索引 表来定位文件中的数据。
索引表
文件
Myfile Count 索引块 3 5 逻辑块号 0 1 物理块号 14 20 14 20
8 2 主要问题： 8 Mail 30 3 25 1）可能要花费较多的外存空间。对于小文件采用索引文件时， 25 其索引块的利用率将是极低的。 图9-13 索引结构 2）当文件很大时，文件索引表比较大。若索引表的大小超过 由于这些物理块是不连续的，逻辑文件信息的连续性是通过 了一个物理块，则必须把索引表以文件形式存放。这不利于索 索引表中记录的物理块的块号反映出来，因此把这个文件的 引表的动态增加；索引表也可按串联方式存放。这却增加了存 物理结构称为索引结构，或索引文件。 放索引表的时间开销。
树形目录结构的特点如下：
1.解决了重名问题； 2.层次清楚； 3.提高检索文件的速度； 4.能进行存取权限的控制，在子目录中可规定存取权限， 则检索文件时需核对存取权限，可实现对文件的保护和 保密。 22
7.2.4 无环图目录结构
引入原因：树形目录结构不便于实现文件共享。 无环图目录结构或文件：允许若干目录共同描述 或共同指向被共享的子目录或文件。
目录区 文件区 目录区 文件区
盘2 盘3
24
目录区 文件区
盘1
卷3
2.文件存储器空间管理 文件区和目录区自由空间表示 （将盘空间等分成物理块）：
位向量（bitmap表）。某一柱面 中的扇区按约定方法顺序编号， 每一物理块由bitmap表中的一位 表示，1表示占用，0表示空闲。 空闲块链表。将所有空闲块线性 链接或成组链接。查找效率低。
L
记录1
记录1
10
② 链接结构（串联文件）
文件不连续地存放于文件存储器上，但使用指针 按文件数据顺序将其链接起来。
文件 Myfile Count Mail 起始块 14 20 30 结束块 25 16 27 物理块号 连接指针 14 20 20 8 8 25 25 -1
逻辑块号 0 1 2 3 优点：能够利用每一个存储块，不会因为磁盘碎片而浪费存储空间。 缺点： 文件的链接结构 ① 指针要占用字节，降低了系统的运行效率和减少了存储空间。 ② 搜索效率低； ③ 只适应逻辑上连续文件，且顺序存取。
12
多级索引：索引表所指的物理块中存放的不是文 件信息，而是装有这些信息的物理块地址。

主索引 文件 索引块 300 第二级索引 300 100 105 ┇ 500 ┇ ┇ ┇ 1100 100 ┇ 105 ┇ 1103 ┇ 1105 ┇ 磁盘空间 0 1
myfile 3
┇ ┇
400
1100 1103 注： 若一个物理块可装 ┇ 下n个物理块地址，则经 1105 过二级索引，可寻址的文 ┇ 件长度将变为n*n块。若 文件长度大于n*n块，则 可用三级索引、四级索引 图9-14 多级索引结构 等方式。
户文件目录为本用户的每一个文件设置一个目录项。
19
主文件目录 User1
User2
User3
User4
系统文件 怎么放？
用户文件目录
A Test Data A A Test A Test Data
文件
二级目录结构
优点：按名查找文件的时间减少，一定程度上解决同名问 题。 缺点：1）若一个用户拥有的文件数越多，则在他的目录中 查找一个文件所花费的时间就越长。 2）用户无法对自己的文件进行再分类安排。
2）易发生重名问题；
3）不便于实现文件共享。
18
7.2.2 二级目录结构

基本思想：
1）第一级为主文件目录MFD(Master File Directory)， 主文件目录以用户名为索引，对每个用户都设置一个指
向用户文件目录的指针。
2）第二级为用户文件目录UFD(User File Directory)，用
A
树形目录结构
21
若文件在当前目录中，则存取文件时只要指出文件名就 行，文件系统将在当前目录中寻找该文件。

若文件不在当前目录中，但在当前目录的下级目录中， 则可用相对路径名指定文件，文件系统就从当前目录开始 沿着指定的路径查找该文件。例如：

绝对路径名 相对路径名
rootቤተ መጻሕፍቲ ባይዱuser1/A/B A/B
20
7.2.3 树形目录结构
多级目录结构象一棵倒置的有根树，故称为树形目录结 构。树型目录结构即是目录的层次结构。
根目录 (root) User1 User2 User3 User4
用户目录 A Test Data A A Test Test Data
用户子目 B 录 路径名 绝对路径名 当前目录 相对路径名
• 文件系统的基础：大容量磁盘。
• 为了对外存储器空间管理和对其上文件的按名 访问而引入文件系统。
2
1.文件系统的功能
支持文件所占存储介质空间的分配/释放； 支持文件相对起始数据的逻辑块定位到外存 上的物理块； 支持对文件访问的安全检查； 支持对文件的访问。

2.将文件系统类比页式存储管理 页式存储管理将一个进程分页存放于主存， 页表是逻辑页到物理页的定位信息；
第7章 文件系统

主要内容：文件的概念，文件结构和存取方法，
文件目录结构，文件访问系统调用，文件存储
空间布局与管理，文件保护，文件系统的基本 模型。

重点：文件的概念，文件的逻辑结构、物理结 构。

难点：存取方法，文件目录及其组织结构。
1
为什么引入文件和文件系统
• 为了方便使用、管理系统公共程序和数据以及 用户自己的程序和数据。
7
7.1.3

文件的物理存储
文件存储器的物理特性 磁带
顺序访问设备→要求文件顺序存放于磁带 上。
磁带设备的存取速度（或信息传输率）与信息密度（字符数/英寸）、 磁带带速（英寸/秒）和块间间隙有关。
8
磁盘

直接（随机）访问设备→文件可顺序、链接式或随 机（通过类似页表的索引结构访问）存放于设备上。 光盘 定位速度快，可直接访问，但往往是一次性写入， 不可删除和重写文件。一般是连续地存放。 物理记录与逻辑记录的关系 ①对直接访问设备等分成物理块，称为物理记录，利 于空间的分配/释放和读/写。 ②需实现逻辑记录到物理记录的映射。
031001 031002 032003 ┆
网通0301 网通0301 电商0302 ┆
85 78 80 ┆

文件的访问方式

顺序访问
程序依次访问文件中的信息，操作系 统自动记录文件访问的当前位置。磁 带、磁盘可采用这种方式。

直接（随机）访问 程序读/写时直接给出要访问数据的逻 辑位置（如第几个字节或第几个记录） 及长度，由OS将逻辑地址转换成物理 地址并访问之。磁盘访问模式。

root
Dict
spell
List
all
w
count
count
words list
缺点：1）可能重复遍历图中的某些节点； List rade w7 2）删除共享节点时可能会产生悬挂指针。 图9-4 无环图目录结构 3）共享时难以保证FCB的一致；
23
7.3
文件存储器空间布局与管理
1.文件存储器空间的划分与初始化 文件存储于文件卷中，文件卷可以是一个物理 盘，也可以是一个物理盘的一部分，一个支持 超大型文件的文件卷也可以由多个物理盘组成。 参见下图： 卷1 卷2

文件系统将一个文件分块存放于外存，文件 控制块包含文件的定位信息。

3
3.按用途分类文件

系统文件
如操作系统核心目标代码文件，驱动程序文件， 注册库配置文件。

库文件，实用程序文件 windows中的.dll，.exe。
如UNIX中的ls，more等程序； 其他文件

如用户源程序文件，数据文件，各种应用程序 用的数据文件。