提桶跑路笔记

408操作系统—4.文件管理

  • 文件系统基础
  • 目录
  • 文件系统

文件系统基础

文件的基本概念

  • 文件定义

    • 以硬盘为载体的存储在计算机上的信息集合
    • 可以是文本、图片、程序
    • 用户进行的输入输出中，以文件作为基本单位

  • 文件组成

    1. 一块存储空间
    2. 分类和索引信息
    3. 访问权限信息

  • 文件属性

    • 文件名称、文件类型
    • 创建者、所有者
    • 位置、大小、保护、创建修改存取信息

  • 文件分类

    1. 性质与用途

      系统文件、用户文件、库文件

    2. 数据形式

      源文件、目标文件、可执行文件

    3. 存取控制属性

      可执行文件、只读文件、读/写文件

    4. 组织形式和处理方式

      普通文件、目录文件、特殊文件

  • 文件特性

    1. 可以长期存储在硬盘中
    2. 允许可控制的进程间共享访问
    3. 能够被组织成复杂的结构

文件的数据结构

文件控制块(File Control Block，FCB)

  • 概念

    • FCB 描述文件元数据，实现按名存取，一个 FCB 对应一个文件
    • FCB 的集合称为​文件目录，​文件目录也被视为一个​目录文件
    • 目录文件存放目录中所有子目录文件和数据文件目录
    • 主要用于早期文件系统

  • 主要包含信息

    • 基本信息

      文件名、文件物理位置、文件逻辑结构、文件物理结构

    • 存取控制信息

      文件主、核准用户或一般用户的存取权限

    • 使用信息

      文件建立时间、上次修改时间等

索引节点（i 节点，inode）

  • 概念

    • 文件描述信息单独形成索引节点，不包含文件名

    • 文件名和索引节点号（索引节点指针）构成目录项，下图为一个目录

      ​image​

    • 记录文件的元信息，每个文件和目录都有一个唯一的索引节点编号

    • 使用索引节点可以减少文件查找时的 I/O 量

      原因：检索目录时只用到了文件名，不需要其他信息，因此将文件名以外的其他信息从目录中剥离成为索引节点，减少查找时调入内存的目录大小

    ​image​

  • 分类

    1. 磁盘索引节点

      存放在磁盘上的索引节点

      包含内容：文件主标识符、文件类型、文件存取权限、文件物理地址、文件长度、文件链接计数、文件存取时间

    2. 内存索引节点

      存放在内存中的索引节点，文件打开后，将磁盘索引节点复制到内存中

      新增内容:索引节点编号、状态、访问计数、逻辑设备号、链接指针

文件的操作

文件的基本操作

  • 创建文件

    1. 分配外存空间
    2. 创建目录项

  • 删除文件

    1. 文件名查找目录
    2. 删除文件对应目录项和 FCB
    3. 回收磁盘空间和内存空间

  • 读文件

    1. 文件名查找目录
    2. 目录项得到外存地址
    3. 通过读指针进程读操作

  • 写文件

    同读文件，每次发生写操作时更新写指针

文件打开的过程

  1. 调用 open 系统调用
  2. 根据文件名搜索目录，
  3. 将目录项从外存复制到内存打开文件表的一个表目中
  4. 将该表目的编号(也叫索引)返回给用户
  5. 当再次请求打开时可节省检索开销

多进程同时打开文件

采用整个系统打开文件表​和​每个进程打开文件表

  • 整个系统表

    包含与进程无关的信息

    如文件在磁盘上的位置、访问日期和文件大小

  • 每个进程表

    保存的是进程对文件的使用信息

    如文件的当前读写指针、文件访问权限、指向系统表中项目指针

  • 过程

    进程打开一个文件，系统表和该进程表包含文件条目

    当另一进程打开同一文件，只在自己进程表添加条目并指向系统表即可

    打开计数器记录打开文件的进程数量，位于系统表中

    调用 close 关闭文件，删除进程表中对应条目，打开计数器-1，归零时即可从系统表中删除该条目

  • 文件描述符（文件句柄）

    只要完成 open 调用，再使用 read、write、Lseek、close 等文件操作的系统调用，就不再使用文件名，而使用文件描述符

    即文件名不是打开文件表的一部分

文件打开和关闭的关联信息

  • 文件指针

    跟踪上次读写位置作为当前文件位置的指针

    对打开文件的某个进程唯一，因此必须与磁盘文件属性分开保存

  • 文件打开计数

    记录当前文件打开和关闭的数量

    因为多个进程可能打开同一个文件，所以系统在删除打开文件条目之前，必须等待最后一个进程关闭文件

  • 文件磁盘位置

    大多数文件操作要求系统修改文件数据

    查找磁盘上的文件所需的信息保存在内存中，以便系统不必为每个操作都从磁盘上读取该信息

  • 访问权限

    每个进程打开文件都需要有一个访问模式(创建、只读、读写、添加等)

    保存在进程的打开文件表中，以便操作系统能够允许或拒绝后续的 I/O 请求

文件保护

  1. 文件保护的目的

    防止文件共享导致文件被破坏，或未经核准的用户修改文件，即解决文件读写执行的许可问题

  2. 访问类型

    读、写、执行、添加、删除、列表清单

    对于高层功能重命名、复制、编辑等可以通过上述低级功能的请求完成，因此保护可以只在低层提供

  3. 访问控制

    • 访问控制列表（Access-Control List，ACL）

      使用访问控制列表规定每个用户名以及所允许的访问类型

      ​image​

      对于方法二：拥有者按拥有者权限访问，若用户与文件主同组按同组权限访问，否则按其他用户访问

    • 口令

      建立文件时提供口令，建立 FCB 时附带口令

      用户访问时必须提供口令

      口令存储在系统内，不安全

    • 密码

      对文件加密，访问需要秘钥

      保密性强，但编码译码耗时

    口令和密码没有控制用户的访问类型

文件的逻辑结构

用户角度出发看到的文件组织形式，即逻辑层面的组织

无结构文件/流式文件

由字符流构成的最简单的文件组织形式，是有序相关信息项的集合，以字节为单位

无结构文件对记录的访问只能通过穷举搜索进行

对基本信息单元操作不多的文件适合该方式，如源代码文件，目标代码文件

有结构文件/记录式文件

由一个以上记录构成的文件，由记录长度可分为：

  1. 定长记录

    文件中所有记录的长度都是相同的，各数据项都在记录中的相同位置，具有相同的长度

    检索记录的速度快，方便用户对文件进行处理，广泛用于数据处理中

  2. 变长记录

    文件中各记录的长度不一定相同，原因可能是记录中所包含的数据项数目不同，也可能是数据项本身的长度不定

    检索记录只能顺序查找，速度慢

有结构文件按记录的组织形式可以分为：

  1. 顺序文件

    文件记录按顺序排列，记录可为定长记录顺序文件、变长记录顺序文件

    记录排列有两种结构

    1. 串结构

      记录顺序与关键字无关，通常是按存入的先后时间进行排列

      必须从头开始顺序依次查找，比较费时

    2. 顺序结构

      记录按关键字顺序排列

      定长记录顺序文件，检索时可采用折半查找，效率较高

  2. 索引文件

    定长记录可直接计算得到记录地址，变长记录需要顺序累加来查找，效率低下

    建立索引表，包含指向记录的指针和记录长度

    索引表按关键字排序，故也是定长记录顺序文件，将变长记录顺序文件顺序检索，转化为定长记录索引文件随机检索

    索引表增加了存储占用

    ​image​

  3. 索引顺序文件

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

    将变长记录顺序文件中所有记录分组，将分组后的第一个记录添加到新建立的索引表中，建立一个表项

    变长记录顺序文件（逻辑文件）中同组内关键字可以无序，但组与组之间必须有序

    查找时，先查找索引表确定分组，在组中再顺序查找

    ​image​

    顺序文件查找平均次数 $\frac N2$，索引顺序文件查找平均次数 $\sqrt{N}$

  4. 直接文件/散列文件（Hash File）

    给定记录的键值或通过散列函数转换的键值直接决定记录的物理地址

    散列文件具有很高的存取速度，但是会引起冲突，即不同关键字的散列函数值可能相同

文件的物理结构

即文件数据在物理设备上是如何分布和组织的

文件在磁带上—> 连续存放方式 文件在磁盘上—> 不采用连续存放方式 文件在内存上—> 随机存放方式

连续分配

每个文件在磁盘上有一组连续的块

文件的记录项记录文件第一个磁盘块块号和占用块数

​image​

优点：

  1. 支持顺序访问和直接访问
  2. 顺序访问容易且速度快，文件所占用的块位于相邻磁道

缺点：

  1. 连续分配时将产生外部碎片，与内存分配类似
  2. 必须知道文件长度，且无法动态增长占用空间
  3. 为保持有序性，删除和插入记录时需要对相邻记录物理移动

链接分配

一种离散分配方式

优点：

  1. 消除磁盘外部碎片，提高利用率
  2. 便于动态分配盘块
  3. 插入删除修改方便​​

分为两种方式：隐式链接和显示链接

  1. 隐式链接

    • 概念

      目录项含有文件第一和最后块块号

      除最后一块，每一块都保存指向下一个块的指针，用户可见

      ​image​

    • 缺点：

      1. 仅支持顺序访问
      2. 不稳定，任何一个指针出问题文件将丢失
      3. 存储指针也需要消耗空间

    • 改进

      将几个盘块组成一个簇，按簇进行分配，可以大幅减少查找时间，同时可以节省指针的空间占用

  2. 显示链接

    • 概念

      链接各个块的指针，显式存放于内存的链接表中，一个磁盘一张，即文件分配表（File Allocation Table,FAT）

      表项中存放下一个盘块指针，文件目录只记录文件起始块号

      ​image​

    • 优点

      1. 支持顺序访问和直接访问
      2. FAT 在系统启动时读入内存，检索在内存中进行，提高了速度，减少访问磁盘速度，但需要占用一定内存

索引分配

  1. 单级索引分配方式

    • 概念

      一个文件创建一个索引块，将该文件的所有盘块号都记录在索引块中

      打开某个文件就将文件对应的索引块调入，无需加载整个 FAT

      ​image​

    • 优点

      1. 支持直接访问，即索引块第 i 块即文件第 i 块
      2. 不会产生外部碎片

    • 缺点

      • 增加额外存储开销
      • 小文件索引块利用率低
      • 大文件链接多个索引块效率低

  2. 多级索引分配方式

    • 概念

      设置一主索引，将索引块盘块号填入，即二级索引分配方式

      类似内存管理多级页表

      文件过大还可以继续增加级数

      ​image​

    • 优点

      极大加快大型文件查找速度

    • 缺点

      访问文件时，启动磁盘次数随索引级数增加而增加

  3. 混合索引分配方式

    • 概念

      • 小文件直接使用 FCB，直接寻址
      • 中文件单级索引，一次寻址
      • 大文件二级三级索引分配

      ​image​

    • 计算

      假设一个块 4KB

      1. 直接地址

        文件不大于 40KB，也就是 10 个块时，可以直接从索引节点中读出全部块号

      2. 一次间接地址

        一次间址块中可以存放 1024 个盘块号

        即可以表示不大于 1000 x 4KB = 4MB 大小的文件

        一次间址与直接地址同时使用时取和即 4MB+40KB

      3. 多次间接地址

        二次间址时可以表示 1K x 1K x 1024 = 4GB 大小文件

        同时使用时最大 4GB+4MB+40KB

        三次即再增加 4TB

目录

目录的基本概念

FCB 的有序集合——文件目录

一个 FCB——文件目录项

文件目录将文件管理系统和文件集合关联起来

  • 目录管理的基本要求

    1. 实现“按名存取”
    2. 提高目录的检索速度
    3. 提供用于控制访问文件的信息
    4. 允许不同用户对不同文件采用相同的名字

目录结构

结构 定义 优点 缺点 结构图
单级目录结构 1. 整个文件系统只有一张目录表
2. 一个文件一个目录项		 1. 速度慢
2. 不允许重名
3. 不便于共享
4. 不适合多用户		 ​image​
两级目录结构 1. 主文件目录（User File Directory,UFD）+ 用户文件目录（UFD）
2. MFD 记录记录用户名和 UFD 所在位置
3. UFD 记录用户文件 FCB		 1. 解决多用户文件重名
2. 文件系统目录上实现访问限制		 1. 不灵活
2. 不能文件分类		 ​image​
树型目录结构 1. 使用绝对路径，相对路径，当前路径
2. 当前目录可通过系统调用更改
3. 不同用户文件文件名可相同
4. 大多系统使用		 1. 可以文件分类
2. 有效管理、保护文件
 1. 查找文件速度受影响
2. 不便于共享		 ​image​
无环目录结构 1. 基于树形目录
2. 加入有向边，组成有向无环图
3. 同一文件或子目录可以出现在多个目录中
4. 存在共享计数器，归 0 时才删除，否则仅删除共享链		 1. 实现文件共享 1. 使系统管理复杂 ​image​

目录的操作

  1. 搜索

    使用文件时，需要搜索目录，找到该文件的对应目录项

  2. 创建文件

    在目录中增加目录项

  3. 删除文件

    在目录中删除相应的目录项

  4. 创建目录

    在树形目录结构中，用户可创建自己的用户文件目录，并可创建子目录

  5. 删除目录

    ① 不删除非空目录，删除时要先删除目录中的所有文件，并递归地删除子目录

    ② 可删除非空目录，目录中的文件和子目录同时被删除

  6. 移动目录

    将文件或子目录在不同的父目录之间移动，文件的路径名也会随之改变

  7. 显示目录

    用户可以请求显示目录的内容，如显示该用户目录中的所有文件及属性

  8. 修改目录

    某些文件属性保存在目录中，因而这些属性的变化需要改变相应的目录项

目录实现

访问文件时，操作系统利用路径名找到相应目录项，目录项中提供了查找文件磁盘块所需要的信息。

目录实现的基本方法有线性列表和哈希表两种

实现目录的目的就是为了查找文件磁盘块

  1. 线性表

    文件名和数据块指针的线性列表

    创建和删除文件都直接在目录中顺序搜素

    • 重用目录项

      目录项被删除或标记为无效后，能够再次利用这些空间来存储新的目录项

      1. 将目录项标记为删除或无效，新目录项覆盖标记位置
      2. 将被删除的目录项位置加入到空闲表中，新目录项插入位置从空闲表中得到
      3. 将目录的最后一个目录项复制到删除位置，并减少目录的长度

    采用链表结构可以减少删除文件的时间

    • 优点：实现简单
    • 缺点：查找费时

  2. 哈希表

    将目录项映射到一个数组中，每个目录项的存储位置由其键值经过哈希函数计算得到

    核心思想是通过计算一个索引值来直接访问存储位置，从而实现快速的插入、删除和查找操作

    • 优点：查找迅速，插入删除简单
    • 缺点：需要措施避免两个文件名称哈希到同一个位置

文件共享

多个用户共享同一个文件，而系统中只保留该文件一份，节省存储空间

基于索引节点的共享方式（硬链接）

在索引节点中增加一个链接计数 count（引用计数）

只有当计数为 0 时才会真正删除文件，其他则删除目录项并计数-1

  • 特点

    1. 硬链接不可以跨文件系统
    2. 硬链接查找速度更快
    3. 索引节点相同，因此硬链接拥有相同的文件权限和属性

下图为共享前，共享后，删除后的情况

​image​

基于符号链实现文件共享（软链接）

符号链接是一个特殊类型的文件，包含指向目标文件的路径信息

创建软链接实际上就是创建了一个新文件，新文件只包含被链接文件的路径名

如下图，访问文件 L 时，再根据 L 存储的路径访问 F，对 F 进行读写操作

​image​

  • 特点

    1. 可以跨文件系统
    2. 只有文件主拥有共享文件索引节点指针
    3. 被链接文件如果被删除，软链接不可见该删除操作，被访问时直接删除软链接
    4. 每次访问都需要 1 次以上的磁盘访问，慢，软链接占用磁盘空间
    5. 符号链接权限与目标文件无关，访问权限取决于目标文件

文件系统

文件系统结构

文件系统（File system）提供高效和便捷的磁盘访问，以便允许存储、定位、提取数据

  • 文件系统作用

    1. 定义文件系统用户接口，涉及定义文件及其属性、所允许的文件操作、如何组织文件的目录结构
    2. 创建算法和数据结构，映射逻辑文件系统到物理外存设备

  • 文件系统层次结构

    1. I/O 控制层

      • 设备驱动程序将输入的命令翻译成底层硬件的特定指令
      • 中断处理程序利用这些指令使 I/O 设备与系统交互

    2. 基本文件系统

      • 向对应的设备驱动程序发送通用命令，以读取和写入磁盘的物理块
      • 管理内存缓冲区，保存各种文件系统，目录和数据块的缓冲

    3. 文件组织模块

      • 组织文件及其逻辑块和物理块，将逻辑地址转换为物理地址
      • 有空闲空间管理器，以跟踪未分配的块，根据需要提供给文件组织模块

    4. 逻辑文件系统

      • 管理元数据信息（包括文件系统的所有结构，不包括文件内容）
      • 管理目录结构
      • 通过 FCB 维护文件结构
      • 负责文件保护

​image​

文件系统布局

文件系统在磁盘中的结构

磁盘中可能划分一个或多个分区（windows 中的本地磁盘），每个分区一个独立的文件系统

​image​

  1. 主引导记录（Master Boot Record,MBR）

    位于磁盘的 0 号扇区，用来引导计算机

    MBR 的后面是分区表，该表给出每个分区的起始和结束地址。表中的一个分区被标记为活动分区

    当计算机启动时，BIOS 读入并执行 MBR。MBR 确定活动分区，读入其第一块，即引导块

  2. 引导块（boot block）

    MBR 执行引导块中的程序，其负责启动该分区中的操作系统

    分区都统一从​引导块​开始，即使不含有操作系统，不排除以后可能安装，Win系统称为分区引导扇区

    除了从引导块开始，其余布局是随着文件系统的不同而变化的

  3. 超级块（super block）

    包含文件系统的所有关键信息

    在计算机启动时，或者在该文件系统首次使用时，超级块会被读入内存

    • 典型信息包括但不限于

      • 分区的块的数量
      • 块的大小
      • 空闲块的数量和指针
      • 空闲的FCB数量
      • FCB指针

  4. 文件系统中空闲信息

    1. 空闲块位图

      记录空闲块

    2. 空闲inode位图

      记录空闲inode

  5. inode列表

    包含了分区中的所有inode

  6. 根目录，文件和目录

    根目录存放文件系统目录树的根部，磁盘的其他部分存放了其他所有目录和文件

文件系统在内存中的结构

内存中信息用于管理文件系统并通过缓存来提高性能

  1. 内存中的安装表

    每个已安装文件系统分区的有关信息

  2. 内存中的目录结构的缓存

    包含最近访问目录

  3. 整个系统的打开文件表

    每个打开文件的FCB副本，打开计数等

  4. 每个进程的打开文件表

    进程打开文件的文件描述符

    指向整个系统打开文件表对应表项的指针

外存空闲空间管理

一个硬盘可以划分两个分区，每个分区文件系统独立，包含文件系统的分区即卷（volume）

卷可以是一整个硬盘，可以是硬盘的一部分，也可以是多磁盘的RAID集

​image​

卷中文件数据空间（文件区）和FCB空间（目录区）隔离

空闲存储空间的管理实际上就是空闲块的管理，空闲块的组织分配回收等问题

空闲表法

连续分配方式

空闲表包含空闲区第一块块号和空闲块数

​image​

盘块分配：首次适应算法，最佳适应算法等

盘块回收：参考内存回收

空闲链表法

  1. 空闲盘块链

    空闲空间以块为单位拉成链，每个块都有指针指向下一个空闲块

    请求时，依次取出适当数量的块分配，释放时，依次将块插入末尾

    ​image​

  2. 空闲盘区链

    空闲盘区拉成链，盘区包含若干相邻空闲块，盘区含有指向下一个盘区第一块的指针

    分配通常使用首次适应算法，回收参考内存回收

盘块链分配回收效率低，但实现过程简单

盘区链分配回收效率高，但实现过程复杂

位示图法

利用二进制一位表示磁盘一个块的情况，每个块都有一个对应，0空闲1分配

​image​

i行j列的块号为$b=n(i-1)+j$

$i=(b-1) \mathrm{DIV} n+1\ j=(b-1) \mathrm{MOD} n+1$——取商和取余

优点：容易找到图中相邻空闲块；占用空间小，存储于内存中减少磁盘开销

缺点：图随磁盘增大而增大，常用于小型计算机

成组链接法

unix系统常用，结合空闲表和空闲链表优点

空闲盘块分组，每组第一个盘块记录下一组空闲盘块的数量和所有空闲盘块号

第一组保存在内存的空闲盘块号栈中，空闲盘块号栈还保存有栈中尚存的空闲块数量N

​image​

  • 分配

    由栈顶取出一空闲盘块分配，同时栈顶指针下移，N-1

    若取出的块已经是栈底，则从磁盘入栈下一组块，再将原栈底块分配（此时该块信息已被读入）

  • 回收

    回收盘块存入空闲盘块号栈顶，栈中数量满时，将栈中空闲盘块号存入下一个新回收盘块，将新回收盘块作为新栈底

位示图表和空闲盘块好栈存放在磁盘卷头位置——超级块

虚拟文件系统

虚拟文件系统（VFS） 屏蔽了不同文件系统的差异和操作细节，向上为用户提供了文件操作的统一调用接口

​image​

  • 功能

    1. 统一接口：

      • 提供了一组通用的文件操作接口，例如打开、读取、写入和关闭文件等。
      • 不同的文件系统通过实现这些接口，可以无缝地被操作系统和应用程序使用。

    2. 抽象层：

      • 将文件系统的具体实现细节与用户空间程序隔离开来。
      • 通过这种抽象，应用程序可以在不修改代码的情况下访问不同的文件系统。

    3. 文件系统挂载：

      • 允许多个文件系统挂载到同一个文件系统树上。
      • 不同的文件系统可以挂载到不同的挂载点，使得用户可以通过统一的路径访问不同的文件系统。

  • 特性

    1. 提高系统性能
    2. 采用面向对象思想
    3. 不是实际文件系统
    4. 只存在内存中
    5. 系统启动时建立，关闭时消亡

  • 对象类型

    1. 超级块对象（Superblock Object）

      包含文件系统的全局信息，例如块大小、空闲块数量等

    2. inode对象（Inode Object）

      包含文件或目录的元数据，例如文件大小、所有者、权限等

    3. 目录项对象（Dentry Object）

      表示目录中的一个目录项，用于路径名解析

    4. 文件对象（File Object）

      表示一个已打开的文件，包含文件的当前读写位置、访问模式等信息

文件系统挂载

文件系统在使用前需要进行挂载（Mounting）

将设备中的文件系统挂载到一个逻辑目录中，通过该逻辑目录就可以访问设备上的文件，此处的设备为逻辑设备，一个硬盘上的多个磁盘为多个逻辑设备

‍