《操作系统》文件管理

文件

常考知识点

• UNIX相关知识
  • UNIX采用树型目录结构，文件信息存放在索引节点中，超级块是用来描述文件系统的
  • UNIX系统所有设备都被视为特殊的文件
  • UNIX每个目录文件中，默认有两个目录项，“.”表示当前目录，“..”表示父目录
• 各种表，图
  • 打开文件表：存放已经打开文件信息的表，将指名文件的属性从外存复制到内存，再使用该文件时直接返回索引
  • 位图：利用二进制的一位来表示磁盘中的一个盘块的使用情况。当其值为“0”时，表示对应的盘块空闲；为“1”时，表示已经分配(或者把"0"作为盘块已分配的标记，把“1”作为空闲标志)。磁盘上的所有盘块都有一个二进制位与之对应，通常可用m * n个位数来构成m行n列的位示图，并使m * n等于磁盘的总块数
  • 空闲盘链表：以盘块或盘区为单位组成一条空闲链
  • 索引表：记录每个文件所存放的盘块地址
  • 系统调用表：一张由指向实现各种系统调用的内核函数的函数指针组成的表，该表可以基于系统调用函数进行索引，来定位函数地址，完成系统调用
• 文件性能相关
  • 与单个文件长度/大小有关的因素：文件块大小，地址项个数，间接地址索引的级数（索引节点总数与单个文件大小无关）
  • 提高文件访问速度的方法：提前读，延迟写，为文件分配连续的簇，采用磁盘高速缓存
  • 文件在磁带上采用连续存放方式：在硬盘上不采用连续存放方法；在内存上采用随机存放方法
  • 连续结构的文件数据读最快，链式的方法不能随机存取，索引的方法占面积
• 文件打开相关
  • 文件打开open时把FCB读到内存，不是把文件内容读到内存（即不会读入文件数据，只有read的时候才会读数据）
  • open参数包含文件名
  • read/write参数不包含文件名，而是open返回的文件索引
• 文件保护相关
  • 防止文件受损的方法
    • 备份
  • 用于多用户之间的存取权限保护
    • 存取控制矩阵方法
• 其他
  • 系统级安全管理包括注册和登录
  • 用户确定文件的逻辑结构，由操作系统设计者根据文件存储器的特性确定文件的物理结构，一旦确定，由操作系统管理

基本概念

• 文件是什么
  • 文件是以硬盘为载体的存储在计算机上的信息集合
  • 文件可以是文本文档，图片，程序
  • 用户进行的输入输出中，以文件为基本单位
• 文件组成
  • 一块存储空间
  • 分类和索引的信息
  • 关于访问权限的信息
• 文件特性
  • 可以长期存储在硬盘中
  • 允许可控制的进程间共享访问
  • 能够被组织成复杂的结构
• 文件属性/元数据
  • 文件名：文件类型
  • 创建者：所有者
  • 位置、大小、保护、创建信息

文件数据结构

• 目录项
  • 相关概念
    • 目录项/PCB = 用来记录文件的名字，索引节点指针以及其他目录项的层级关联关系
    • 目录/目录文件 = FCB的集合
    • 为了实现按名存取，在文件系统中为每个文件设置用于描述和控制文件的数据结构，称作文件控制块FCB，也叫做目录项
    • 目录也被视作一个文件，该文件叫做目录文件
    • 目录项时由内核维护的一个数据结构，缓存在内存，目录项文件存储在磁盘
    • 目录文件存放该目录中所有子目录文件和数据文件的目录
  • 包含信息
    • 基本信息：文件名，文件物理位置，文件逻辑结构，文件物理结构
    • 存取控制信息：文件主或核准用户或一般用户的存取权限
    • 使用信息：文件创立时间，上次修改时间
• 索引节点
  • 概念
    • 索引节点是用来记录文件的元信息，是文件的唯一表示
    • 索引节点同样占用磁盘空间
    • 将文件描述信息从目录项分离，即应用了索引节点的方法
    • 使用索引节点可以减少查找文件时的I/O信息量
  • 分类
    • 磁盘索引节点
      • 指存放在磁盘上的索引节点，每个文件有一个唯一的磁盘索引节点
      • 包含内容：文件的主标识符：文件类型；文件存取权限；文件物理地址；文件长度；文件链接计数；文件存取时间
    • 内容索引节点
      • 指存放在内存中的索引节点，文件打开后，将磁盘索引节点复制到内存中
      • 新增内容：索引节点编号；状态；访问计数；逻辑设备号；链接指针

文件操作

• 基本操作
  • 创建文件；写文件；读文件；重新定位文件；删除文件；截断文件
• 文件打开的过程
  • 文件打开就是调用open，根据文件名搜索目录，将指明文件的属性（包括该文件在外上的物理地址）从外存复制到内存打开文件表的一个表目中，并将该表目的编号（索引）返回给用户
  • 打开文件操作的主要工作就是把指定文件的目录复制到内存指定的区域
  • open操作会把文件的PCB调入内存，而不会把文件内容读到内存，只有进程希望获取文件内容时才会读入文件内容
• 文件打开和关闭关联的信息
  • 文件指针：文件打开计数；文件磁盘位置；访问权限
  • 文件描述符时打开文件的标识
• 写入文件的过程
  • 举例
    • 【用户空间】write() $\rightarrow$【虚拟文件系统】sys_write() $\rightarrow$ 【文件系统】文件系统的写方法 $\rightarrow$ 磁盘
  • 解释
    • 首先用open系统调用打开文件，open的参数中包含文件的路径名和文件名
    • 使用write写数据，其中write使用open所返回的文件描述符，不使用文件名为参数【read同理】
    • 使用完文件后，要用close系统调用关闭文件，避免资源的泄露

代码

1
2
3
4
5

fd = open(name,flag);//打开文件
write(fd,...);//写数据
read(fd,...);//读数据
close(fd);//关闭文件

文件保护

• 目的
  • 解决对文件的读，写，执行的许可问题
  • 一个文件的访问常由用户访问权限和文件属性（包括保存在PCB中对文件访问的控制信息）共同设置
• 保护的方式
  • 非访问控制方法
    • 口令
      • 定义
        • 用户建立一个文件时需要提供口令
        • 用户请求访问时必须提供相应的口令
      • 优点
        • 时间空间开销不多
      • 缺点
        • 口令直接存在系统内部，不安全
    • 加密方法
      • 定义
        • 对文件进行加密，访问时需要密钥
      • 优点
        • 保密性强，节省了存储空间
      • 缺点
        • 编码和译码需要时间
  • 访问控制方法
    • 访问控制目的：控制用户对文件的访问方式
    • 访问控制对象：读；写；执行；添加；删除；列表清单
    • 访问控制机制必须由系统实现
      • 方法一
        • 定义
          • 为每个文件和目录增加一个访问控制列表ACL
          • 该表规定每个用户及其所允许的空间管理
        • 优点
          • 可以使用复杂的访问方法
        • 缺点
          • 长度无法预计并且可能导致复杂的空间管理
      • 方法二
        • 定义
          • 采用精简的访问列表
          • 该列表采用拥有者，组和其他三种用户类型
        • 优点
          • 只需要三个域即可列出访问表中这三类用户的访问权限

文件的逻辑结构

• 定义
  • 文件中的数据在在逻辑层面是如何组织起来的
• 无结构文件/流式文件
  • 最简单的文件组织形式，是有序相关信息项的集合，以字节为单位
  • 对基本信息单元操作不多的文件适合该方式，如源代码文件，目标代码文件
• 有结构文件/记录式文件
  • 顺序文件
    • 串结构：只能按顺序查找，费时
    • 顺序结构：可采用折半查找，检索效率高
    • 顺序查找平均次数$\frac{N}{2}$;索引查找平均次数$N^{\frac{1}{2}}$
  • 索引文件
    • 提高了存取速度，但索引表增加了存储空间
  • 索引顺序文件
    • 同一组中的关键字可以无序，但组与组之间的关键字必须有序
    • 先通过索引表查找所在组，然后在该组中使用顺序查找

文件的物理结构【文件在外存上的存储组织形式】

• 定义

  • 研究文件数据在物理存储设备上是如何分布和组织的
  • 文件在磁带上
    • 连续存放方式
  • 文件在磁盘上
    • 不采用连续存放方式
  • 文件在内存上
    • 随机存放方式

• 文件存储方式

  • 文件的存储即为对磁盘非空闲块的管理
  • 顺序分配
    • 特点
      • 文件头需要指定起始块的位置和长度
      • 要求连续的存储空间
      • 可随机访问
    • 访问磁盘次数
      • 访问磁盘1次
    • 优点
      • 顺序存取速度块，当文件是定长时可以根据文件起始地址及记录长度进行随机访问
    • 缺点
      • 要求连续的存储空间，会产生外部碎片，不利于文件的动态扩充
    • 例图
      • 
  • 链表分配
    • 特点
      • 存放是离散的，不用连续的，于是就可以消除磁盘碎片
      • 可大大提高磁盘空间的利用率，同时文件的长度可以动态扩展
      • 隐式链接无法直接访问数据块，只能通过指针顺序访问文件
      • 显式链接把用于链接文件各数据块的指针，显式地存放在内存的一张链接表中
      • 内存中的这样一个表格称为文件分配表FAT(File Allocation Table)
      • 不可随机访问
    • 访问磁盘次数
      • 需要访问磁盘n次
    • 优点
      • 无外部碎片，提高了外存空间的利用率，动态增长较方便
    • 缺点
      • 只能按照文件的指针链顺序访问，查找效率低，指针信息存放消耗内存或磁盘空间
    • 例图
      • 
  • 索引分配
    • 特点
      • 为每个文件创建一个索引数据块存放指向文件数据块的指针列表
      • 可随机访问
    • 访问磁盘次数
      • m级需要访问磁盘m+1次
    • 优点
      • 可以随机访问，易于文件的增删
    • 缺点
      • 索引表增加存储空间的开销，索引表的查找策略对文件系统效率影响较大
    • 例图
      • 
  • 链表 + 索引
    • 特点
      • 索引数据块留出一个存放下一个索引数据块的指针
    • 例图
      • 
  • 索引 + 索引（多级索引）
    • 特点
      • 通过一个索引块来存放多个索引数据块
    • 例图
      • 
    • 举例
      • unix系统的inode结构
        • 对于小文件使用直接查找的方式可减少索引数据块的开销
        • 对于大文件则以多级索引的方式来支持
        • 所以大文件在访问数据块时需要大量查询
          • 存放文件所需的数据块小于10块，采用直接查找的方式
          • 存放文件所需的数据块大于10块，则采用一级间接索引方式
          • 前面两种方式都不够存放大文件，则采用二级间接索引方式
          • 二级间接索引页不够存放大文件，则采用三级间接索引文件

文件的存储空间管理

• 本质
  • 文件的存储空间管理就是对磁盘空闲块的管理
• 方法
  • 空闲表法
    • 为所有空闲空间建立一张表
    • 表内容包括空闲区的第一个块号和该空闲区的块个数
    • 例图
      • 
  • 空闲链表法
    • 每一个空闲块里有一个指针指向下一个空闲块
    • 这样能够很方便地找到空闲块并管理起来
    • 例图
      • 
  • 位图法
    • 位图时利用二进制的一位来表示磁盘中一个盘块的使用情况
    • 磁盘上所有的盘块都有一个二进制与之对应
      • 当值为0时，表示对应的盘块空闲
      • 值为1时，表示对应的盘块已分配
      • 通常可用m * n个位数来构成m行n列的位示图
      • 且m * n 等于磁盘的总块数
  • 成组链法
    • 结合空闲表和空闲链表的优点，克服表长的缺点

文件系统

基本概念和目标

• 概念
  • 文件系统 = OS中复杂管理持久数据的子系统
  • 文件系统 = 与文件管理有关的软件 + 被管理的文件 + 试试文件管理所需的数据结构
  • 文件系统需先挂到某个目录才可正常使用
  • 文件的基本操作单位就是数据块
• 目标
  • 实现对文件的基本操作 = 按名存储和查找文件 + 组织成合适的结构 + 文件共享 + 文件保护【用户角度】
  • 管理与磁盘的信息交换 + 完成逻辑结构和物理结构的变换【OS角度】
  • 组织文件在磁盘上的存放 + 采取好的文件排放顺序和磁盘调度方法【OS角度】
• 分类
  • 磁盘的文件系统
    • 直接把数据存储在磁盘中，比如Ext 2/3/4,XFX等都是这类文件系统
  • 内存的文件系统
    • 这类文件系统的数据不是存储在硬盘的，而是占用内存空间
    • 读写此类文件的实际上时读写内核中相关的数据
  • 网络的文件系统
    • 用来访问其他计算机主机数据的文件系统，比如NFS,SMB等

文件系统的层次结构

• I/O控制
  • 设备驱动程序：将输入的命令翻译成底层硬件的特定指令
  • 中断处理程序：利用指令使IO设备与系统交互
• 基本文件系统
  • 向对应的设备驱动程序发送通用命令，以读取和写入磁盘的物理块
  • 管理内存缓冲区，保存各种文件系统，目录和数据块的缓冲
• 文件组织模块
  • 组织文件及其逻辑块和物理块
  • 可以将逻辑地址转换为物理地址
  • 有空闲空间管理器，以跟踪未分配的块，根据需要提供给文件组织模块
• 逻辑文件系统
  • 用于管理元数据信息（包括文件系统的所有结构，不包括文件内容）
  • 管理目录结构
  • 通过FCB维护文件结构
  • 负责文件保护

文件系统的布局

• 在磁盘中的结构
  • 例图
    • 
  • 引导块
    • 在系统启动时用于启用引导
  • 块组
    • 超级块
      • 包含文件系统的重要信息
      • inode总个数，块总个数，每个块组的inode个数，每个块组的块个数
    • 块组描述符
      • 包含文件系统中各个块组的状态
      • 块组中空闲块和inode的数目等，每个块组都包含了文件系统中所有块组的组描述符信息
    • 数据位图和inode位图
      • 用于表示对应的数据块或inode时空闲的，还是被使用中
    • inode列表
      • 包含了块组中所有的inode，inode用于保存文件系统中与各个文件和目录相关的所有元数据
    • 数据块
      • 包含文件的有用数据
• 在内存中的结构
  • 内存中的信息用于管理文件系统并通过缓存来提高信息
  • 结构类型
    • 内存中的安装表
    • 内存中的目录结构的缓存包含最近访问目录的信息
    • 整个系统的打开文件表
    • 每个进程的打开文件表

虚拟文件系统VFS

• 目的
  • 为用户程序提供了文件系统操作的统一接口，屏蔽了不同文件系统差异和操作细节
• 特性
  • 能提高系统性能
  • 不是一种实际的文件系统
  • 只存在于内存中，不存在与任何外存空间中
  • 在系统启动时建立，在系统关闭时消亡
• VFS的数据结构
  • 超级块对象
  • 索引节点对象
  • 目录项对象
  • 文件对象

用户空间、系统调用、虚拟文件系统、缓存、文件系统和存储之间的关系

分区和安装

• 一个磁盘可划分为多个区，每个分区都可以创建单独的文件系统，每个分区都可包含不同的操作系统
• 文件在使用前必须先安装（即挂载）

目录

常考点

• 目录结构
  • 在树型目录中，为了加快文件检索速度，可设置当前目录，于是文件路径可以从当前目录开始查找
  • 文件系统采用多级目录的目的是解决命令冲突
  • 树型目录结构中，用户对文件的首次访问通常采用文件路径名，之后对文件的访问通常使用文件描述符
• 目录检索
  • 在顺序检索法时，只要路径名的一个分量名未找到，就应停止查找
• 文件共享
  • 用户进程的打开文件表关于同一个文件不一定相同，例如读写指针位置不一定相同
• 其他
  • 整个文件系统只有一个系统文件打开表（里面表项都是不重复的），同一文件打开多次只需改变引用计数

目录管理要求

• 实现按名存取
• 需提高目录的检索速度
• 需要提供用于控制访问文件的信息
• 允许不同用户对不同文件采用系统的名字

目录结构

• 单级目录结构
  • 定义
    • 整个文件系统只建立一张目录表
    • 每个文件占一个目录项
  • 优点
  • 缺点
    • 查找速度慢
    • 文件不允许重名
    • 不便于文件共享
    • 不适合多用户的OS
  • 结构图
    • 
• 两级目录结构
  • 定义
    • 文件目录分为主文件目录MDF和用户文件目录UFD
    • MDF记录用户名UFD所在的存储位置
    • UFD记录用户文件的FCB信息
  • 优点
    • 解决了多用户之间的文件重名问题
    • 文件系统可以在目录上实现访问限制
  • 缺点
    • 缺乏灵活性，不能对文件分类
  • 结构图
    • 
• 树型目录结构
  • 定义
    • 使用绝对路径，相对路径，当前路径的结构
    • 不用用户的文件、文件名可相同可不同
    • 大多OS采用这种目录结构
  • 优点
    • 可以很方便对文件进行分类
    • 能够有小进行文件的管理和保护
  • 缺点
    • 利于文件共享
    • 查找文件增加了磁盘访问次数，会影响查询速度
  • 例图
    • 
• 无环图目录结构
  • 定义
    • 在树型目录结构上
    • 加入有向边，组成一个有向无环图
  • 优点
    • 实现了文件共享
  • 缺点
    • 使系统的管理变得更加复杂
  • 例图
    • 

目录的查询/检索

• 概念
  • 目录查询通过在磁盘上反复搜索完成，需要不断进行I/O操作，开销大
  • 可以将当前使用文件目录复制到内存，从而降低磁盘操作次数，提高系统速度
• 实现方法
  • 线性列表【对应线性查找】
    • 定义
      • 采取线性列表存储文件目录项
    • 优点
      • 实现简单
    • 缺点
      • 查找费时
  • 哈希表【对应散列查找】
    • 定义
      • 采取哈希表存储文件目录项
    • 优点
      • 查找迅速，插入删除简单
    • 缺点
      • 需要一些措施来避免冲突

文件共享

• 概念
  • 文件共享使多个用户共享同一个文件，系统只需保留该文件的一个副本
• 文件共享方式
  • 基于索引节点的关系方式【硬链接】
    • 定义
      • 硬链接就是多个指针指向同一个索引节点
      • 文件的物理地址和其他文件属性信息放在索引节点中
    • 特点
      • 硬链接不可用与跨文件系统
      • 硬链接查找速度比软链接块
    • 新增文件时
      • 建立硬链接时，引用计数值加一
    • 删除文件时
      • 删除文件时，计数值减一
      • 若得到的值不为0，则不能删除此文件
      • 即只要还有一个指针在，索引节点就不会被删除
    • 例图
      • 
  • 基于符号链实现文件共享【软链接】
    • 定义
      • 软链接相当于重新创建一个文件
      • 新文件只包含被链接文件的路径名
    • 特点
      • 软链接可以跨文件系统
    • 新增文件时
      • 符号链接，计数值直接复制
    • 删除文件时
      • 删除操作对符号链接不可见
      • 以后再通过符号链接访问时，若发现文件不存在，直接删除符号链接
    • 示例
      • windows 的快捷方式