第七章 文件管理(汤小丹版操作系统笔记) 超全超详细！！！

第七章 文件管理

7.1 文件和文件系统

为什么需要文件系统

• 内存是易失设备，且容量有限
• 系统及程序，数据，文档以文档形式存于外存，用时调入
• 用户直接管理外存文件不现实
• OS增加文件管理功能，专门管理外存文件，并提供文件存取，共享，保护等手段
• 文件系统方便用户，保证文件安全性，提高系统资源利用率

7.1.1 数据项，记录和文件

前言

文件系统将程序和数据组织为文件的方式进行管理

文件: 具有文件名的若干相关元素(记录)的集合

记录:一组有意义数据项的集合

文件系统把数据组成分为,数据项，记录和文件三级。

数据项

• 数据项是文件系统中最低级的数据组织格式

• 数据项分为两种类型:

  基本数据项：即字段，描述对象某种属性，最小数据逻辑单位

  组合数据项：也称复合项，由若干个基本数据项组成

• 基本数据除数据名外，还需要数据类型

记录

• 记录是一组相关数据项的集合
• 记录描述对象在某方面的属性，如学生记录
• 关键字唯一能够标识一个记录的数据项
• 关键字由一个记录的一个或多个数据项组成

文件

• 文件:由创建者定义，具有文件名的一组相关记录的集合
• 文件分为有结构文件和无结构文件
• 有结构文件由若干个相关记录组成
• 无结构文件可看成一个字符流(字符串)
• FS中文件时最大的数据单位，描述对象的集合

文件属性

①文件类型 ②文件长度 ③文件物理位置 ④文件创建时间，修改时间等

7.1.2 文件名和类型

文件名和文件拓展名

• 文件名用于标识不同文件
• 扩展名,文件后缀，指示文件类型，是添加在文件名后若干附加字符，是文件一部分，用"."分割开

文件类型

• 根据性质和用途分类
  • 系统文件:由系统软件构成的文件。大多数系统文件只允许用户调用，不允许读写
  • 用户文件:用户的源代码，目标文件，可执行文件或数据构成的文件
  • 库文件:由标准子例程及常用库函数等所构成的文件。允许用户调用，但不允许修改
• 根据文件中数据形式来分类
  • 源文件:由源程序和数据构成，通常为ASCII码或汉字构成。
  • 目标文件:经过编译，但尚未链接的目标代码，后缀名为".obj"
  • 可执行文件:目标代码经过链接后所形成的文件，后缀名为".exe"
• 按存取控制属性分类
  • 可执行文件:运行用户调用和执行，不允许读和写
  • 只读文件:只允许文件主及授权用户去读，不允许写
  • 读写文件:文件主和授权用户可以读写
• 按组织形式和处理方式分类
  • 普通文件:各种程序，数据，文档等文件
  • 目录文件:由文件目录组成的文件，通过目录文件可查询下属性文件信息，可读写
  • 特殊文件:系统里的各种I/O设备，系统按文件方式操作设备。对设备文件的操作由设备驱动程序完成。

7.1.3 文件系统的结构层次

文件系统可分为三个层次

最底层是对象及其属性，中间层是对对像进行操纵和管理软件的集合，最高层文件系统提供给用户的接口。

图2 .文件系统的层次结构

对象及其属性层

文件系统管理对象包括:

①文件

②目录

• 目录含文件名，文件属性，文件物理地址
• 目录管理的目的为了方便对文件进行检索和读取

③磁盘(磁带)存储空间

• 管理文件和目录占用外存空间，提高外存利用率和读写速度

对对象操纵和管理软件集合

文件系统的核心部分

管理对象:目录，文件，存储空间

功能

①对文件存储空间的管理

②对文件目录和管理

③对文件的逻辑地址转化为物理地址

④对文件读和写的保护

⑤对文件共享和保护

文件系统接口

FS以接口形式向用户提供操作文件和记录的方法和手段。两种接口:

• 命令接口:直接交互，用户通过键盘命令取得文件系统的服务。
• 程序接口:用户程序和FS的接口，通过系统调用取得文件系统的服务，例如Creat，Open

与文件系统有关的软件的四次结构

FS采用层次组织结构，每次包含一定功能，处于某层的软件智能调用同层或更底层中的功能模块。

FS有关的软件分四层

• IO控制层:FS最底层，由磁盘驱动程序组成
• 基本文件系统，处理内存和磁盘块的数据交换
• 基本IO管理程序，处理磁盘IO事务，如空闲块管理，缓冲管理，逻辑块号转物理块号
• 逻辑文件系统，处理与记录和文件有关的操作，如符号文件名，访问文件，文件保护

7.1.4 文件操作

• 最基本文件操作

①创建文件，分配空间，建立目录项，写入属性。

②删除文件，删除目录项，回收空间。

③读文件，由文件名查目录找到具体目录项，用文件指针读

④写文件，由文件名查目录找到具体目录项，用文件指针写

⑤设置文件读/写文件，设置文件指针，实现文件随机访问

• 文件的打开和关闭操作

“打开”(open)系统调用，避免多次重复检索外存目录，第一次操作某文件时必须先打开文件

open操作

将文件项(属性)从外存目录拷贝到内存打开文件表，并返回表目编号(文件句柄或指针)，建立表目和文件的关联，以后直接在内存中找到文件信息，节省文件检索开销

文件完成时要调用close系统调用关闭

close操作

断开内存打开文件表表目与外存文件的关联，并删除修改该表目信息

文件的其他操作

• 操作文件的属性调用，如修改文件名，所有者，文件类型，文件访问权，查询文件类型(大小，状态)…
• 操作文件的系统调用，如创建目录，删除目录，改变当前目录和工作目录等。
• 实现文件的共享的系统调用，已经操作文件的系统调用等。

7.2 文件的逻辑结构

文件的逻辑结构和物理结构

用户角度，文件由一系列逻辑记录组成，逻辑记录是存取文件的基本单位

文件系统高层主要关心逻辑结构，如何把逻辑记录构成逻辑文件

文件系统低层主要关心物理结构，如何将文件存储到外存

逻辑结构

也称文件组织，是用户看到的文件组织形式，决定如何读写文件

物理结构

又称文件存储结构，指文件在外存上的存储组织形式，用户不可见。与外存特性及分配方式有关

7.2.1 文件逻辑结构的类型

• 文件逻辑结构基本要求

①有助于提高文件检索速度和效率

②方便修改文件:增加，删除和修改记录

③降低文件占用的存储空间，不要求大片连续存储空间

• 按文件是否有结构分类

① 有结构文件:由若干个记录组成，也称记录式文件

② 无结构文件:由字符流构成，也称流式文件

有结构文件

记录式文件记录描述一个实体，各记录有相同或不同数目的数据项

根据记录长度分类:

• 定长记录:记录长度，记录长度相同；文件长度用记录数表示；处理方便，开销小；可提高检索速度，方便修改
• 变长记录:记录长度不相同，每类记录长度已知；检索速度慢，不利于文件处理和修改。

无结构文件

• 有结构文件一般用于DBMS，源程序，可执行文件，库文件等采用无结构文件
• 文件长度以字节为单位
• 利用读写指针访问流式文件，指针指向下一个要访问的字符
• 流式文件可看成记录文件:一个记录仅有一个字节构成

• 按文件组织方式分类

①顺序文件 :由多个记录按顺序排列，定长或变长记录。

②索引文件 :为可变长记录建立索引表，每个记录占一个索引表，加快里检索速度。

③索引顺序文件:顺序文件与索引文件结合。建立索引表，每组记录中第一个里设置一个索引表项。

7.2.2 顺序文件

• 顺序文件的排列方式:

串结构:

• 按存入时间先后排列，记录顺序与关键字无关
• 每次必须从头开始检索，速度慢

顺序结构:

• 用户指定关键字，记录按关键字排序
• 折半查找，插值查找。跳步查找等可提高顺序结构文件检索效率

• 顺序文件的优缺点

• 最佳应用场合:批量存取文件的记录。备份还原
• 逻辑文件中顺序文件存取效率最高
• 顺序存储设备只能采用顺序文件结构
• 缺点:
  • 交互式应用场合顺序文件查找和修改性能差
  • 增删记录难，解决办法:另外配置一运行记录文件，定期与原文件合并

7.2.3 记录寻址

访问顺序文件首先要找到记录首地址

查找记录首地址方式有:显式查找和隐式查找

• 隐式寻址方式

对于定长记录顺序文件，由当前记录确定下一记录地址

• Wptr:=Wptr+L ，L为记录长度

对于定长记录，由0号记录确定n号记录地址

• Wptr:=Wptr0+L*N ，L为记录长度

• 显式寻址方式

• 对定长记录可以直接或随机访问
• 可变长记录文件不能用显式寻址方式访问
• 定长记录文件随机访问方法
  • 通过记录序号:记录首址=记录序号*记录长度
  • 利用关键字:系统关键字和所有记录顺序比较
• DBMS采用可变长，基于关键字记录
• 目录检索是基于关键字(文件名)检索

7.2.4 索引文件

• 按关键字建立索引

• 变长记录文件查找必须从首记录查起，耗时长，效率低
• 为变长记录文件建立一张索引表
  • 每个记录设一表项，记录器首地址长度
  • 索引表按关键字排序
  • 索引表本身是定长记录顺序文件
  • 实现变长记录的随机存取

查找过程: ①折半查找 ②访问记录

优点，加快检索速度，实现直接存取，用于及时性要求较高的场合

• 具有多个索引表的索引文件

• 按关键字建立索引表的索引文件只能按关键字检索
• 用户需求:希望能按不同属性(关键字)检索记录
• 为顺序文件建立多个索引表，为每一种检索域(属性或关键字)配置索引表。索引表中按相应的属性或关键字排序

索引文件的特点:

将顺序文件改造为可随机查找，提高查找速度

索引文件插入和删除记录页方便

需要配置索引表，每个记录一个表项，增加存储开销

7.2.5 索引顺序文件

• 索引顺序文件的特征

• 索引顺序文件时对顺序文件的改进

• 两个新特征:

  引入文件索引表，实现对索引顺序文件的随机访问

  增加溢出文件，记录新增加，删除和修改的文件

• 索引顺序文件是顺序文件和索引文件的结合

• 一级索引顺序文件

• 简单的索引顺序文件只使用一级索引
• 索引建立方法
  • 将变长顺序记录文件所有记录分为若干组
  • 建立索引表，每组第一个记录建立索引项，含关键字和记录指针
• 索引顺序文件是最常见的逻辑文件形式

一级索引顺序文件检索方法

检索方法:

• 根据关键字用折半查找法找到该组第一个记录
• 再用顺序法查找主文件找到记录

性能分析:10000个记录

• 顺序文件:平均检索5000次(N/2)
• 索引顺序文件:平均检索100次(sqrt(N)/2),提高50倍

• 二级索引顺序文件

为索引表再建立一张索引表，形成两级索引表

优点:对于非常大的顺序文件，可进一步提高检索效率

性能分析:10⁶记录

• 顺序文件:平均检索10⁶/2次

• 索引顺序文件:平均查找1000次

• 二级索引顺序文件:一级每100记录为一组，共10000组；

  二级每100记录为1组，共100组；平均查找此时 50+50+50=150次

7.2.6 直接文件和哈希文件

• 直接文件

• 前述方法根据记录键值，检索线性表，链表或索引表，以找到记录物理地址
• 直接文件根据关键字可直接获得记录物理地址
• 这种关键字到记录物理地址的转换称为键值转换
• 直接文件在于在什么地方实现键值转换

• 哈希文件

• 目前应用最广泛的直接文件
• 利用hash函数(散列函数)将关键字转换为记录地址
• 为实现文件存储空间动态分配，hash函数得到执指向目录表表目指针，其内容记录物理地址
• 哈希函数问题:键值冲突
• 把哈希函数作为系统标准库函数，供文件存取时调用

7.3 文件目录

对目录管理的要求

文件目录用于标识文件属性及物理地址，供文件检索使用

要求:

• 实现"按名存取"
• 提高对目录的检索速度
• 文件共享:节省空间
• 允许文件重名

7.3.1 文件控制块和索引节点

• 文件控制块FCB是描述和控制文件的数据结构

• 文件管理程序借助FCB操作文件

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

• 文件目录即文件控制块的有序集合，每个文件控制块是一个文件目录项

• 文件目录也是一个文件，称为目录文件

文件控制块FCB内容

FCB含有三类信息:基本信息，存取控制信息及使用信息

基本信息包括

① 文件名:标识文件的符号名

② 文件物理位置:设备，起始盘块，盘快数(或长度)

③ 文件逻辑结构:记录式/流式；定长/变长

④ 文件的物理结构:顺序式/链接式/索引式

存取控制信息

文件主，授权用户以及一般用户的存取权限

使用信息类

建立日期和时间，最近修改日期时间，以及当前使用信息(打开该文件的进程数，是否被其他进程锁住，是否需要写回磁盘)

• 不同的OS的文件系统，FCB内容不同

MS-DOS文件控制块

FCB长32字节，包含文件名，拓展名，首个盘块号，文件长度，建立时间，文件属性等

索引节点

索引节点的引入

• 文件目录存放在磁盘上，占用大量盘块

• 检索目录的过程，只用到文件名，其他文件描述信息在检索目录时不需调入内存

• UNIX系统采用把文件名与文件描述信息分开的办法

• 文件的描述信息单独构成索引节点，简称i结点

• 文件目录项仅由文件名和文件i结点构成

• UNIX系统一个目录占16B,文件名14B,i结点指针2B，1KB盘块可放64个目录项

磁盘索引节点

每个文件唯一的磁盘索引结点放于磁盘，主要内容:

• 文件主标识符:拥有该文件的个人或小组标识符
• 文件类型:正规文件/目录文件/特殊文件
• 文件存取权限，各类用户的存取权限
• 文件物理地址，有13个地址iaddr(0)-iaddr(12),以直接或间接方式给出数据文件所在盘块编号
• 文件长度，字节数为单位
• 文件连接计数，所有指向该文件名的指针计数
• 存取时间，最近存取，最近被修改及i结点最近被修改时间

内存索引节点

文件打开时将磁盘索引结点拷贝到内存的索引结点

内存索引结点增加以下内容

• 索引结点编号，用于标识内存索引结点
• 状态，i结点是否上锁或被修改
• 访问计数，访问i结点的进程数
• 文件所属文件系统的逻辑设备号
• 链接指针，指向空闲链表和散列队列的指针

7.3.2 简单文件目录

目录结构组织

• 目录结构组织关系到文件系统的存取速度，文件安全和共享
• 常用文件目录形式:
  • 单级目录
  • 两级目录
  • 树形目录

单级文件目录

最简单文件目录，整个文件系统只有一张目录表

每个文件占有一个目录项，含文件名，文件扩展名，文件长度，物理地址，文件类型，文件说明，状态位，以及其他文件属性

每当创建一个新文件时，必须先检索所有目录项，以保证新文件名在目录中是唯一的。然后在从目录表中找到一块空白目录项，填入新文件的文件名及其它说明信息，并置状态位为1。

删除文件时，先到到改文件目录项，回收存储空间后，再清除该目录项

特点

优点

• 简单，只实现按名存取

缺点

• 查找速度慢，平均检索N/2，只适合小规模单用户环境
• 不允许重名
• 不便实现文件共享，只用同一文件名访问同一文件

两级文件目录

• 每个用户建立单独用户文件目录UFD,由用户所有的FCB组成

• 系统建立一个主文件目录MFD,每个用户目录文件占一目录项，包括用户名和指向用户目录文件的指针

特点

优点

• 提高检索目录的速度
• 不同用户目录可以使用相同文件名
• 不同用户可使用不同文件名访问同一共享文件

缺点

一个用户无法访问其他用户文件，多个用户间不便于共享文件

7.3.3 树形结构目录

树形目录

① 现代OS中最通用且实用的文件目录是树形结构目录

② 主目录被称为根目录，每个文件系统只能有一个根目录

③ 每个文件和每个目录只能有一个父目录

④ 数据文件称为树叶，其他目录为树节点，或子目录

⑤ 目录文件中的目录项可以是数据文件FCB也可以是目录文件FCB

⑥ 树型目录可提高目录检索速度和文件系统的性能

路径名和当前目录

路径名

• 树形目录中，从根目录到任何文件都有唯一通路
• 从根目录开始，把全部目录文件名和数据文件名依次用"/"连接，即文件路径名
• 每个文件路径都是唯一的
• 图8中 J的路径为/B/F/J

当前目录，相对路径，绝对路径

• 每次访问文件都从根目录开始检索很麻烦
• 为每个进程设置一个"当前目录"，又称"工作目录"
• 进程对文件的访问都相对于"当前目录"进行
• 从当前目录直到数据文件所构成的路径为相对路径
• 从根目录直到数据文件所构成的路径为绝对路径

树形目录特点

• 查询速度快；结构更清晰；文件管理和保护更容易
• 查找文件需逐级访问中间结点，增加磁盘访问次数
• UNIX,WINDOWS,LINUX都采用树型目录

目录操作

① 创建目录:在树形目录结构中，用户可为自己建立UFD,并可再创建子目录。创建目录时，只需查看在自己的UFD及其子目录有无新建文件的相同文件名，若无，便可在UFD或其某个目录中增加一个新目录项

② 删除目录:

• 不可删除非空目录:MS-DOS
• 可删除非空目录

③ 改变目录：设置当前目录

④ 移动目录

⑤ 链接(Link)操作:使文件由多个父目录，方便共享

⑥ 查找:可指定起始目录，精确匹配/局部匹配，通配符

7.3.4 目录查询技术

文件访问过程

• 用文件名查询目录，找到FCB或索引结点
• 根据FCB或索引结点中文件物理地址(盘块号)，算出磁盘物理位置
• 通过磁盘驱动程序将文件读入内存

查询目录方式

• 线性检索法
• Hash方法

线性检索法

• 线性检索法又称顺序检索法
• 单极目录利用文件名顺序查找到目录项
• 树形目录中，文件名由多个文件分量名组成，需多级目录进行查找

Hash方法

• 建立Hash索引文件目录，使用Hash方法进行查询

  ①将文件名用Hash方法变换为文件目录的索引值

  ②利用索引值查找目录

• 优点：显著提高索引速度

• 文件名出现通配符(*,?)时不能使用Hash方法检索

• Hash冲突:不同文件名转换为相同Hash值

7.4 文件共享

• 文件共享:多个进程(用户)访问同一文件
• 系统只需保留共享文件一份副本，节省存储空间
• 共享方式:基于DAG图实现共享，利用符号链接实现共享

7.4.1 有向无循环图实现文件共享

有向无循环图

• 树形目录每个文件一个父目录，不适合文件共享
• 若允许一个文件有多个父目录，虽破坏树的特性，但可实现文件共享
• 多用户共享文件或目录时，必须将其连接到多个用户的父目录，构成一个DAG
• 解释共享时存在的问题:共享文件目录中不能包含物理盘块号！！！

利用索引结点

解决方法: 共享索引节点而不是目录项

• 文件物理地址及属性不放在目录项，而放在索引节点。目录只设置文件名及指向索引节点指针。
• 共享文件目录项都指向同一索引节点
• 索引节点增加count字段记录连接数

7.4.2 利用符号链接实现文件共享

利用符号链接的基本思想

• 基本思想

  允许文件或目录有多个父目录，但只有一个主父目录，其他都是通过符号链接方式创建的链接父目录

• 特点

  属主结构仍是简单树，方便文件查找，删除

如何利用符号实现链接共享

• 使用Link命令创建链接文件，这种链接方式为符号链接
• Link共享文件在链接父目录创建LINK类型同名新文件
• 新文件只包含被链接文件(共享文件)的路径名，即符号链接
• 用符号链接打开文件时，OS根据路径名找到共享文件，然后访问

利用符号链接的优点

• 只有文件主拥有指向共享文件索引的结点的指针
• 其他用户只有共享文件路径名
• 不会发生文件主删除共享文件后留下悬空指针的情况
• 与HTML类似，符号链接可访问网络上的文件

利用符号链接存在问题

• 要根据文件路径逐级查找目录，直到找到共享文件的索引结点，增大开销访问
• 每个共享用户要建立符号链，要配置索引结点，耗费磁盘空间

PS:两种共享方式共同问题

① 一个共享文件有多个文件名

② 遍历文件系统时会多次遍历共享文件

③ 拷贝目录时共享文件产生多个拷贝

7.5 文件保护

影响文件安全性因素以及采取的措施

• 主要因素:

  ①人为因素，误操作

  ②系统因素，掉电，磁盘故障

  ③自然因素，10年保存期

• 三个措施

  ① 存取控制机防止人为因素

  ② 系统容错技术防止系统部分故障

  ③ 建立后备文件系统，防止自然因素

系统资源保护机制

• OS中都配置这种保护机制

• 进程只能在保护域内执行操作，且只能访问具有访问权的对象

• 保护机制

  ① 访问权 ② 保护域 ③访问矩阵，包括访问控制表和访问权限表

7.5.1 保护域

访问权

• 为保护系统对象，由系统控制进程对对象访问
• 对象可以是硬件对象，也可以是软件对象
• 进程对对象执行操作的权限，称为访问权
• 访问权可以用有序对(对象名，权集)表示，如{F₁,R/W}

保护域

• 保护域用于保护系统资源，简称"域"
• "域"是进程对一组对象访问权的集合，进程只能在指定域内执行操作
• "域"规定进程能访问的对象和能执行的操作

进程和域之间的静态关系

• 进程和域一一对应，一个进程只联系一个域
• 进程生命期中可用资源是固定的，这种域称为静态域
• "静态域"通常赋予进程的访问权超过其实际需要
• 例如:初期磁带机，结束时打印机

进程和域间的动态联系方式

• 进程和域一对多的关系，一个进程可联系多个域
• 进程运行分为多个阶段，每个阶段联系一个域
• 优点:根据实际需要规定某个阶段能访问的对象
• 例如:开始阶段，中间阶段，快结束阶段
• 把进程和域一对多联系方式称为动态联系方式
• 动态联系方式要有保护域切换功能

7.5.2 访问矩阵

基本访问矩阵

• 访问矩阵用于描述系统的访问控制

• 行代表域，列代表对象，每项由访问权组成

• 访问权access(i,j)定义了域D_I中进程对对象Q_j的操作集

• 访问权由资源拥有者或管理者决定

具有域切换权的访问矩阵

• 为实现进程和域之间的动态联系，进程可进行域切换
• 仅当进程有切换权时，才能进行域切换
• 访问矩阵中增加几个对象(目的域)
• 当前仅当swich∈access(i,j)时，才允许进程从域i切换到域j

7.5.3 访问矩阵的修改

拷贝权

• 拷贝权，所有权及控制权，可实现对访问矩阵有控修改
• 拷贝权将某域中的访问权(access(i,j))扩展到同一列的其他域，即为进程在其他域中也赋予同一对象的访问权(access(i,j))
• 拷贝权不能扩散，这种拷贝方式成为限制拷贝

所有权

• 利用所有权能增加或删除对对象的访问权
• 若access(i,j)包含所有权，则域D_I上的进程可以增加或删除任何其他域进程对对象j(j列)的访问权

控制权

• 拷贝权，所有权改变同一列各项的访问权，即改变不同域进程对同一对象的范围跟权
• 控制权用于改变同一行(域)的权限，即同一域中进程对其他对象的访问权
• 若access(i,j)包含了控制权，域D_i的进程可以删除域D_J进程对各对象的任何访问权

7.5.4 访问矩阵的实现

• 访问矩阵概念简单，但实现困难

• 域数量和对象很庞大，访问矩阵时空开销大

• 进程访问对象有限，访问矩阵是稀疏矩阵

• 访问矩阵实现方式:

  ①按列(对象)划分为控制访问表

  ②按行(域)划分为访问权限表

访问控制表

• 访问矩阵按列划分，每个对象建立一张访问控制表ACL
• 删除所有空项，访问控制表由有序对(域，权集)组成
• 减少访问控制表占用的存储空间，并提高查找速度
• 当对象是文件时，访问控制表放于FCB或i结点中
• 访问控制表可定义对对象的缺省访问权集

• 域是一个抽象的概念，域的实现方式

  ① 每个用户一个域，权限取决于用户身份

  ② 每个进程一个域，权限取决于进程身份

访问权限表

• 访问矩阵按行划分，每行构成一个访问权限表
• 某个域对每个对象操作权限构成表，每项为该域对某对象的访问权限
• 将访问权限表存于系统区，以保护权限表
• 大多数系统同时采用访问控制表和访问权限表，为每个对象建立访问控制表，当用户第一次检查范文控制表，再为进程建立访问权限。

• 参考：计算机操作系统（第四版）（汤小丹)