计算机操作系统(5) 文件管理
2023-08-09 14:53:19 # NJU # 计算机操作系统

第五章 文件管理

5.1 文件系统概述

5.1.1 文件的概念

文件的概念

  • 文件是具有符号名的，在逻辑上具有完整意义的一组相关信息项的序列

  • 文件(document)与计算机文件(file)

  • 文件名是由字母、数字和其他符号组成的一个字符串，其格式和长度因系统而异

文件的命名

  • 文件命名一般包括文件名和扩展名：
    • 前者用于识别文件，后者用于标识文件特性，两者之间用圆点隔开
  • 每个 OS 都有约定的扩展名，Windows中：
    • .COM表示可执行的二进制代码文件
    • .EXE表示可执行的浮动二进制代码文件
    • .LIB表示库程序文件
    • .BAT表示批命令文件
    • .OBJ表示编译或汇编生成的目标文件
  • UNIX的约定文件名，请大家自己阅读

文件的分类

  • 按用途可分成：系统文件、库文件、用户文件
  • 按保护级别可分成：只读文件、读写文件、不保护文件
  • 按信息时限可分成：临时文件、永久文件、档案文件
  • 按设备类型可分成：磁盘文件、磁带文件、光盘文件、软盘文件
  • 还可以按文件的逻辑结构或物理结构分类

引入文件的优点

  • 用户使用方便：使用者无需记住信息存放在辅助存储器中的物理位置，也无需考虑如何将信息存放到存储介质上，只要知道文件名，给出有关操作系统要求便可存取信息，实现了”按名存取”

  • 文件安全可靠：由于用户通过文件系统才能实现对文件的访问，而文件系统能提供各种安全、保密和保护措施，故可防止对文件信息的有意或无意的破坏或窃用

  • 文件可备份：可组织转储或备份，在文件使用过程中出现硬件故障时，文件系统可组织重执，提高可靠性

  • 文件可共享：文件系统还能提供文件的共享功能，如不同的用户可以使用同名或异名的同一文件，提高了文件和文件空间的利用率

  • 总之，把数据组织成文件形式加以管理和控制是计算机数据管理的重大进展

5.1.2 文件系统及其功能

文件系统的概念

  • 文件系统是操作系统中负责存取和管理信息的模块，它用统一的方式管理用户和系统信息的存储、检索、更新、共享和保护，并为用户提供一整套方便有效的文件使用和操作方法

文件系统中的文件

  • 文件这一术语不但反映了用户概念中的逻辑结构，而且和存放它的辅助存储器(也称文件存储器)的存储结构紧密相关
  • 所以，同一个文件必须从逻辑文件和物理文件两个侧面来观察他

文件系统的功能

  • 文件系统面向用户的功能是

    • 文件的按名存取
    • 文件的共享和保护
    • 文件的操作和使用

  • 为了实现这些功能，OS 必须考虑

    • 文件目录的建立和维护
    • 存储空间的分配和回收
    • 数据的保密和保护
    • 监督用户存取和修改文件的权限
    • 实现在不同存储介质上信息的表示方式、编址方式、存储次序，以及信息检索等问题

文件系统的组成

image-20221124135005799

5.2 文件的组织

5.2.1 文件的存储

卷和块

  • 文件存储介质有磁带、光盘和磁盘
  • 卷是存储介质的物理单位，对应于一盘磁带、一块软盘、一个光盘片、一个硬盘分区
  • 块是存储介质上连续信息所组成的一个区域，也叫做物理记录

  • 块在主存储器和辅助存储器进行信息交换的物理单位，每次总是交换一块或整数块信息

  • 决定块的大小要考虑用户使用方式、数据传输效率和存储设备类型等多种因素

  • 不同类型的存储介质，块的长短常常各不相同；对同一类型的存储介质，块的大小一般相同，但也可以不同
  • 外围设备由于启停机械动作或识别不同块的要求，两个相邻块之间必须留有间隙
    • 间隙是块之间不记录用户代码信息的区域

顺序存取存储设备的信息安排

  • 顺序存取设备是严格依赖信息的物理位置次序进行定位和读写的存储设备
  • 磁带机是最常用的一种顺序存取存储设备，它具有存储容量大、稳定可靠、卷可装卸和便于保存等优点，广泛用作存档
  • 磁带的一个突出特点是块长的变化范围较大，块可以很小，也可以很大，原则上没有限制
  • 光盘也是一种顺序存取存储设备

直接存取存储设备的信息安排

  • 磁盘是一种直接存取存储设备，又叫随机存取存储设备
  • 移臂与旋转两维组织，存取速度高
  • 它的每个物理记录有确定的位置和唯一的地址，存取任何一个物理块所需的时间几乎不依赖于此信息的位置

5.2.2 文件的逻辑结构

逻辑文件

  • 逻辑文件，又称为文件的逻辑结构
    • 独立于物理环境的，用户概念中的抽象信息组织方式
    • 用户能观察到的，并加以处理的数据集合
  • 文件的逻辑结构分为两种形式
    • 一种是流式文件
    • 一种是记录式文件

流式文件

  • 流式文件指文件内的数据不再组成记录，只是由一串依次的字节组成的信息流序列
  • 这种文件常常按长度来读取所需信息，也可以用插入的特殊字符作为分界

记录式文件

  • 记录式文件是一种有结构的文件，它是若干逻辑记录信息所组成的记录流文件
  • 逻辑记录是文件中按信息在逻辑上的独立含义所划分的信息单位
  • 如，每个职工的工资信息是一个逻辑记录；整个单位职工的工资信息便组成了该单位工资信息的记录式文件

image-20221124142641691

记录式文件与数据库

  • 数据库管理系统也支持逻辑记录
  • 但数据库有别于记录式文件，数据库中的记录之间可以通过数据冗余构成某种联系
  • 数据库管理系统支持基于联系的数据查询，文件系统则不行

5.2.3 记录的成组与分解

成组与分解的提出

  • 一个物理记录只存放一个逻辑记录可能造成极大的浪费

  • 若干个逻辑记录合并成一组，写入一个块叫记录的成组，每块中的逻辑记录数称块因子

  • 对于流式文件，一个物理记录可以存放很多个连续字节

成组与分解操作

  • 系统设置独立于用户数据区的输入/输出缓冲区
  • 记录的成组操作在输出缓冲区内进行，凑满一块后才将缓冲区内的信息写到存储介质上
  • 当存储介质上的一个物理记录读进输入缓冲区后，把逻辑记录从块中分离出来的操作叫记录的分解操作

成组与分解操作示意

image-20221124145408709

成组与分解的特征

  • 优点：记录成组与分解不仅节省存储空间，还能减少输入输出操作次数，提高系统效率
  • 记录成组与分解处理带来的新特征：
    • 用户读请求，导致包含该逻辑记录的物理块读入输入缓冲区；这一操作可能读入了多个逻辑记录，这一现象称为提前读
    • 用户写请求，首先是写入输出缓冲区，只有当该缓冲区中的逻辑记录满后才会引起实际输出，这一现象称为推迟写

5.2.4 文件的物理结构

文件的物理结构

  • 文件的物理结构和组织是指文件在物理存储空间中的存放方法和组织关系
  • 又称为物理文件
  • 文件的存储结构涉及块的划分、记录的排列、索引的组织、信息的搜索等许多问题
  • 其优劣直接影响文件系统的性能

顺序文件

  • 将一个文件中逻辑上连续的信息存放到存储介质的依次相邻的块中便形成顺序结构，这类文件叫顺序文件，又称连续文件
  • 磁带文件、光盘文件是典型例子

顺序文件的优缺点

  • 优点：顺序存取记录时速度较快
    • 批处理文件，系统文件用得最多
    • 采用磁带存放顺序文件时，总可以保持快速存取的优点
  • 缺点
    • 建立文件前需要能预先确定文件长度，以便分配存储空间
    • 修改、插入和增加文件记录有困难

连接文件

  • 连接文件，又称串联文件；连接结构的特点是使用连接字来表示文件中各个物理块之间的先后次序
  • 第一块文件信息的物理地址由文件目录给出，而每一块的连接字指出了文件的下一个物理块位置；连接字内容为 0 时，表示文件至本块结束
  • 像输入井、输出井等都用此类文件

image-20221124144402437

连接文件的特点

  • 优点
    • 易于对文件记录做增、删、改，易于动态增长记录
    • 不必预先确知文件长度
    • 存储空间利用率高
  • 缺点
    • 存放指针需额外的存储空间
    • 由于存取须通过缓冲区，待获得连接字后，才能找到下一物理块的地址，因而，仅适用于顺序存取

直接文件

  • 直接文件，又称散列文件，它通过计算记录的关键字建立与其物理存储地址之间的对应关系
  • 这种变换通常采用散列法 (hash法)
  • 计算寻址结构可能出现’冲突’，即不同的关键字可能变换出相同的地址来，解决办法有拉链法、循环探查法、二次散列法、溢出区法等

索引文件

  • 索引文件为每个文件建立了一张索引表，其中，每个表目包含一个记录的键(或逻辑记录号)及其存储地址
  • 索引表的地址可由文件目录指出，查阅索引表先找到相应记录键(或逻辑记录号)，然后获得数据存储地址

索引文件的访问方式

  • 索引文件在文件存储器上分两个区：索引区和数据区
  • 访问索引文件需两步操作：第一步查找索引表，第二步获得记录物理地址
  • 需要两次访问辅助存储器，若文件索引已预先调入主存储器，那么，就可减少一次内外存信息交换

索引文件的特点

  • 索引结构可以被认为是连接结构的一种扩展，除了具备连接文件的优点外，还克服了它只能作顺序存取的缺点，具有直接读写任意一个记录的能力，便于文件的增、删、改
  • 索引文件的缺点是：增加了索引表的空间开销和查找时间

索引表的组织

  • 一级索引
  • 二级索引
  • 多级索引

一种多级索引结构

image-20221124145124548

5.3 文件目录

5.3.1 文件目录结构

文件目录

  • 文件目录是实现文件的 “按名存取” 的关键数据结构
  • 文件系统的基本功能之一就是负责文件目录的建立、维护和检索，要求编排的目录便于查找、防止冲突
  • 文件目录需要永久保存，因此也组织成文件存放在磁盘上，称目录文件

一级目录结构

  • 一级目录结构：在操作系统中构造一张线性表，与每个文件的相关属性占用一个目录项，构成了一级目录结构
  • 由于用户与文件众多，容易重名，不利记忆

二级目录结构

  • 第一级为主文件目录，它用于管理所有用户文件目录，它的目录项登记了系统接受的用户的名字及该用户文件目录的地址
  • 第二级为用户的文件目录，它为该用户的每个文件保存一个登记栏，其内容与一级目录的目录项相同
  • 每一用户只允许查看自己的文件目录

image-20221124151737496

二级目录结构的特点

  • 采用二级目录管理文件时，因为任何文件的存取都通过主文件目录，于是可以检查访问文件者的存取权限，避免一个用户未经授权就存取另一个用户的文件，使用户文件的私有性得到保证，实现了对文件的保密和保护
  • 特别是不同用户具有同名文件时，由于各自有不同的用户文件目录而不会导致混乱
  • 对于同一个用户而言，同样存在文件多、容易重名问题

树形目录结构

  • 每一级目录可以登记下一级目录，也可以登记文件，从而，形成了层次文件目录结构
  • 层次目录结构通常采用树形目录结构，它是一棵倒向的有根树，树根是根目录；从根向下，每一个树分叉是一个子目录；而树叶是文件

树形目录结构的特点

  • 较好地反映现实世界中具有层次关系的数据集合和较确切地反映系统内部文件的组织结构
  • 不同文件可以重名，只要它们不位于同一末端的子目录中
  • 易于规定不同层次或子树中文件的不同存取权限，便于文件的保护、保密和共享

树形目录结构中的文件定位

  • 在树形目录结构中，一个文件的全名包括从根目录开始到文件为止，通路上遇到的所有子目录路径，又称为路径名
  • 各子目录名之间用正斜线 / (反斜线 \ )隔开
  • 一个硬盘分区可以组织成一颗子树
    • 每棵子树可以对应于一个逻辑盘符(Win)
    • 也可以把众多子树嫁接成一颗大树(UNIX)

树形目录结构

image-20221124152156116

5.3.2 文件目录管理

文件查找

  • 文件查找是文件目录管理的重要工作，”按名存取”文件就是系统根据用户提供的文件路径名来搜索各级文件目录，找到该文件
    • 可以从根目录查起(绝对路径名)
    • 也可以从”当前目录”查起(相对路径名)，用.表示当前目录，..表示父目录
    • 现代操作系统都设置有改变工作目录命令，即变更当前工作目录

目录项查找

  • 搜索具体目录项时，可以采用顺序查找法，依次扫描文件目录中的目录项，将目录项中的名字与欲查找的文件名相比较
  • 可以采用一些优化办法加快查找目录的速度
    • 目录表项是按键的顺序编排，则可以采用”二分查找法”
    • 或者采用”杂凑法”，把每个文件名经过变换函数变换成唯一的目录表表项

文件目录处理

  • 树型目录结构存在的一个问题是：当一个文件经过许多目录节点时，使用很不方便；系统在沿路径查找目录时，往往要多次访问文件存储器，使访问速度大大减慢
  • 若把所有文件的目录都复制到主存，访问速度是加快了，但又增加了主存的开销
  • 一种有效办法是把常用和正在使用的那些文件目录复制进主存，这样，既不增加太多的主存开销，又可明显减少目录查找时间

活动文件表

  • 系统可以为每个用户进程建立一张活动文件表，当用户使用一个文件之前，先通过”打开”操作，把该文件有关目录信息复制到指定主存区域，有关信息填入活动文件表，以建立用户进程和该文件索引的联系
  • 当不再使用该文件时，使用”关闭”，切断用户进程和这个文件的联系，同时，若该目录已被修改过，则应更新辅存中对应的文件目录

5.4 文件的共享、保护和保密

5.4.1 文件的安全与保护

文件的安全与保护

  • 文件是计算机系统的重要资源，因此，要求文件系统具有保障文件安全的手段，提供文件保密的措施，有效地实现文件的共享
  • 文件共享是指不同用户共同使用某些文件
  • 文件保护是指防止文件被破坏
  • 文件保密则是指防止文件及其内容被其他用户窃取

文件共享

  • 文件共享是计算机用户完成共同任务所必需的
  • 文件共享带来许多好处，如：
    • 减少用户大量重复性劳动
    • 免除系统复制文件的工作
    • 节省文件占用的存储空间
    • 减少程序设计输入输出文件的次数

文件共享的并发控制

  • 在允许文件共享的系统中，操作系统应提供手段实现对共享文件的同步控制
  • 多个进程可能同时存取一个文件，如果它们同时进行读操作，操作系统应对文件进行公用控制
  • 如果有进程进行写操作，例如，有两个进程，进程A要求修改文件，同时进程B要求读出同一文件中的数据，则操作系统必须提供同步控制机制，以保证文件数据的完整性

文件的保密措施

  • 文件保密是指文件及其内容不能被未经文件主授权的其他用户窃取
  • 文件的保密措施有以下几种：
    1. 隐蔽文件目录
    2. 设置口令
    3. 使用密码

5.4.2 文件的保护

文件的保护

  • 文件保护是指防止文件被破坏
  • 操作系统必须提供文件保护机制，有效实现文件的完整性
  • 常用的文件保护办法
    • 文件副本
    • 文件存取矩阵与文件存取表
    • 文件属性

文件的副本

  • 文件系统必须要有防止硬软件故障，保存信息完整性的能力
  • 文件副本是主要实现机制
    • 动态多副本技术
    • 转储、备份与恢复

动态多副本

  • 第一种办法是在多个介质上维持同一内容的文件，并且在更新内容时同时进行
  • 这种方法需要增加设备费用和系统负载，一般适用于容量较小且较为重要的文件，例如不需更新的系统文件及专用文件，当文件发生故障时只要切换到备用设备就可

文件转储

  • 文件转储：定时把文件复制转储到其它介质上，当某介质上出现故障时，复原转储文件
  • 转储又可分成两种方式：
    • 一是在一定时间间隔或一个单位处理结束时，系统自动复写更新过的文件和数据
    • 二是每天或每周把文件信息全部复写一遍，需要时再通过装入转储文件来恢复系统，诸如BACKUP、RESTORE等命令

文件的存取控制矩阵

  • 系统为每个用户设置访问每个文件对象的存取属性
  • 系统的全部用户对全部文件的存取属性就组成的一个二维矩阵，称为存取控制矩阵
  • image-20221205103154217

存取控制表

  • 由于操作系统拥有很多用户和众多文件，存取控制矩阵是一个稀疏矩阵，可以将其简化为一张存取控制表
  • 每行包括：用户、文件、存取属性
  • 存取控制表仅登记那些对文件拥有存取属性的部分

基于存取控制矩阵/表的文件保护

  • 存取属性：可以有访问、读、写、执行、创建、删除、授权等等
  • 系统通过查阅(矩阵/表)核对用户对文件的存取权限
  • 文件属主使用GRANT、REVOKE等命令进行授权，甚至把授权权转授给他信任的用户
  • 系统管理用户(超级用户)等同于文件属主权限，并获得对系统文件的授访问权权限

文件属性

  • 存取控制表的一种简化方法是用户分类，再针对每类用户规定文件属性
  • 用户分类：属主、合作者、其他
  • 文件属性：读、写、执行、…
  • 文件属性可以放在文件目录项中，管理大为简化
  • 用户使用文件时，通过核对文件属性，实现保护

文件属性的例子

image-20221205103440530

5.5 文件的使用

5.5.1 文件的存取方法

文件的存取方法

  • 文件存取方法是操作系统为用户程序提供的使用文件的技术和手段
  • 文件存取方法在某种程度上依赖于文件的物理结构

顺序存取

  • 按记录顺序进行读／写操作的存取方法称顺序存取
  • 读操作根据读指针读出当前记录，同时推进读指针，指向下一次要读出的记录
  • 写操作则设置写指针，把一个记录写到文件末端，同时推进写指针
  • 允许对读指针进行前跳或后退 n (整数)个记录的操作

直接存取

  • 很多应用场合要求快速地以任意次序直接读写某个记录
  • 例如，航空订票系统，用航班号作标识，把特定航班的所有信息存放在物理块中，用户预订某航班时，直接计算出该航班的存位置

索引存取

  • 基于索引文件的索引存取方法
  • 对于这种文件，信息块的地址都可以通过查找记录键而换算出
  • 除可采用按键存取外，也可以采用顺序存取或直接存取的方法
  • 实际的系统中，大都采用多级索引，以加速记录查找过程

5.5.2 文件的使用

文件的使用

  • 用户通过两类接口与文件系统联系
  • 第一类是与文件有关的操作命令，例如，UNIX中的cat，cd，cp，find，mv， rm，mkdir，rmdir等等
  • 第二类是提供给用户程序使用的文件类系统调用，基本文件类系统调用有：建立、打开、读/写、定位、关闭、撤销

建立文件

  • “建立文件” 用于创建一个文件
  • 所需参数：文件名、设备类(号)、文件属性及存取控制信息
  • 处理流程：在相应设备上建立一个文件目录项，为文件分配第一个物理块，在活动文件表中申请一个项，登记有关目录信息，并返回一个文件句柄

撤销文件

  • “撤销文件”用于删除一个文件
  • 所需参数：文件名和设备类(号)
  • 处理流程：若文件没有关闭，先关闭文件；若为共享文件，进行联访处理；在目录文件中删去相应目录项；释放文件占用的文件存储空间

打开文件

  • “打开文件” 用于建立起文件和用户进程之间的使用联系
  • 所需参数：文件名、设备类(号)、打开方式
  • 处理流程：在主存活动文件表中申请一个项，返回一个文件句柄；根据文件名查找目录文件，把目录信息复制到活动文件表相应栏；按存取控制说明检查访问的合法性；若打开的是共享文件，则应有相应处理

关闭文件

  • “关闭文件” 用于结束一个文件的读写
  • 所需参数：文件句柄
  • 处理流程：将活动文件表中该文件的”当前使用用户数”减1；若此值为0，则收回此活动文件表；完成”推迟写”；若活动文件表目内容已被改过，则应先将表目内容写回文件存储器上相应表目中，以使文件目录保持最新状态

读/写文件

  • “读/写文件”用于读写文件
  • 所需参数参数：文件句柄、用户数据区地址、读写的记录或字节个数
  • 处理流程：按文件句柄从活动文件表中找到该文件的目录项信息；根据目录项指出的该文件的逻辑和物理组织方式，把相关逻辑记录转换成物理块

定位文件

  • “定位文件”用于调整所打开文件的读写指针位置
  • 所需参数：文件句柄，定位指针

5.6 文件系统的实现

5.6.1 辅存空间管理

辅存空间管理

  • 磁盘等大容量辅存空间被OS及许多用户共享，用户进程运行期间常常要建立和删除文件，OS应能自动管理和控制辅存空间
  • 随着用户文件不断建立和撤销，文件存储空间会出现许多’碎片’
  • OS解决’碎片’的办法是整理’碎片’；在整理过程中，往往对文件重新组织，让其存放在连续存储区中

辅存空间的分配方式

  • 连续分配：存放在辅存空间连续存储区中(连续的物理块号)
    • 优点是顺序访问时速度快，管理较为简单，但为了获得足够大的连续存储区，需定时进行’碎片’整理
  • 非连续分配：动态分配给若干扇区或簇(几个连续扇区)，不要求连续
    • 优点是辅存空间管理效率高，便于文件动态增长和收缩

空闲块的管理: 位示图

  • 使用若干字节构成一张表，表中每一字位对应一个物理块，字位的次序与块的相对次序一致。
  • 字位为”1”表示相应块已占用，字位为”0”状态表示该块空闲
  • 其主要优点是，可以把位示图全部或大部分保存在主存中，再配合现代计算机都具有的位操作指令，可实现高速物理块分配和去配

空闲块的管理：空闲块成组连接法

image-20221208010437962

image-20221208010507041

5.6.2 文件系统的实现层次

image-20221208010558457

补充内容

1. Inode、目录项、层次目录结构

Linux特殊目录项建立方法

Linux系统的 FCB 中的文件名和其他管理信息分开，其他信息单独组成一个数据结构，称为索引节点 inode，此索引节点在磁盘上的位置由 inode号 标识。

image-20221205082251475

文件名(含路径) $\stackrel{目录检索}{\longrightarrow}$ 目录项 $\longrightarrow$ [文件名(不含路径), inode号]

Inode

  • 文件系统中的每个文件都有一个磁盘 inode 与之对应，这些inode被集中存放于磁盘上的 inode 区。FCB 对于文件的作用，犹如 PCB 对于进程的作用，集中这个文件的所有相关信息，找到inode，就能获得此文件的必要信息。
1
2
3
4
5
6
7
8
struct inode {
    unsigned long i_ino; /*inode号*/
    atomic_t i_count; /*inode引用数*/
    kdev_t i_dev; /*inode所在设备*/
	...
    union {
    }
}
  • 数据块索引在union结构的每个具体文件系统中，其中的 i_data[15] 数组给出数据块地址索引
    • 前12项为直接索引，第13项为一次间接索引，第14项为二次间接索引，第15项为三次间接索引。
  • 磁盘 inode 记录文件的属性和相关信息，文件访问过程中会频繁地用到它，不断来回于内外存之间引用它，当然是极不经济的。为此，为此，在内存区开辟一张 活动inode 表。磁盘inode 反映文件静态特性，活动inode 反映文件动态特性。
  • 当访问某文件时，若在活动inode 表中找不到其inode，就申请一个空闲活动 inode，把磁盘inode 内容复制给它，随之就可用来控制文件读写
  • 当用户关闭文件时，活动inode 的内容回写到对应的磁盘inode 中，再释放活动inode 以供它用。把FCB的主要内容与索引节点号分开，不仅能够加快目录检索速度，而且，便于实现文件共享。

层次目录结构

  • 每一级目录可以是下一级目录的说明，也可以是文件的说明，形成层次关系
  • 多级目录结构采用树型结构，是一棵倒向有根树，树根是根目录；从根向下，每个树枝是一个子目录；而树叶是文件
  • 树型多级目录优点:
    • 较好地反映现实世界中具有层次关系的数据集合和确切地反映系统内部文件的分支结构；
    • 不同文件可重名，只要它们不位于同一末端子目录中，易于规定不同层次或子目录中文件的不同存取权限，便于文件的保护、保密和共享等，有利于系统的维护和查找。
  • 如果规定每个文件都只有一个父目录，称为纯树型目录结构，其缺点是文件共享不是对称的，父目录有效拥有该文件，其他被授权用户必须经过属主目录才能对该文件进行访问
  • 有向无环图目录 尽管它允许文件有多个父目录而破坏树的特性，但不同用户可以对称方式实现文件共享，即可能属于不同用户的多个目录，使用不同文件名能访问和共享同一个文件。
  • 有向无环图目录结构的维护比纯树型目录结构复杂，由于一个文件可能有多个父目录，需为每个文件维护一个引用计数，用来记录文件的父目录个数，仅当引用计数为1时，删除操作才移去文件，否则仅仅把相关记录从父目录中删去。
  • Linux支持多父目录，但其中一个是主父目录，它是文件拥有者，且文件被物理存储在此目录下，其他次父目录通过link方式来连结和引用文件，允许任一父目录删除共享文件。
    • 下图示例这种文件共享的情形，文件/home/fei1为myfile.c的主父目录(图中实线表示)，/home/fei2和/home/fei3/fei4均为文件myfile.c的次父目录(图中虚线表示)。
  • Windows实现被称作”快捷方式”的多父目录连结，快捷方式是一些指向不同文件夹(子目录)和菜单之间任意复制和移动的文件及文件夹的指针，删除快捷方式就是删除指针。

image-20221205093920792

2. Unix/Linux文件系统的多重索引结构

image-20221205094000697

在UNIX系统中，每个i节点中分别含有 10 个直接地址的索引和一、二、三级间接索引。若每个盘块放128个盘块地址，则一个1MB的文件分别占用多少各级索引所使用的数据物理块？20MB的文件呢？设每个盘块有512B。

image-20221205094103433

3. 文件系统的功能与实现

3.1 文件系统调用的实现

  • 文件系统提供给用户程序的一组系统调用，包括：创建、删除、打开、关闭、读、写和控制，通过这些系统调用用户能获得文件系统的各种服务。
  • 在为应用程序服务时，文件系统需要沿路径查找目录以获得该文件的各种信息，这往往要多次访问文件存储器，使访问速度减慢，若把所有文件目录都复制到主存，访问速度可加快，但却又增加主存开销。
  • 方案: 把常用和正在使用的那些文件目录复制进主存，这样，既不增加太多主存开销，又可明显减少查找时间
  • 系统为每个用户进程建立一张活动文件表，用户使用文件之前先通过”打开”操作，把该文件的文件目录复制到指定主存区域
  • 当不再使用该文件时，使用”关闭”操作切断和该文件目录的联系，这样，文件被打开后，可被用户多次使用，直至文件被关闭或撤销，大大减少访盘次数，提高文件系统的效率

文件系统磁盘结构

  1. 超级块：占用 1# 号块

    • 占用1#号块，存放文件系统结构和管理信息

      如记录inode表所占盘块数、文件数据所占盘块数、主存中登记的空闲盘块数、主存中登记的空闲块物理块号、主存中登记的空闲inode数、主存中登记的空闲inode编号，及其他文件管理控制信息

    • 可见超级块既有盘位示图的功能，又记录整个文件卷的控制数据。

    • 每当一个块设备作为文件卷被安装时，该设备的超级块就要复制到主存系统区中备用，而拆卸文件卷时，修改过的超级块需复制回磁盘的超级块中。

  2. 索引节点区：2#～k+1# 块

    • 存放inode表，每个文件都有各种属性，它们被记录在称为索引节点inode的结构中；所有inode都有相同大小，且inode表是inode结构的列表，文件系统中的每个文件在该表中都有一个inode。又分磁盘inode表和主存活动inode表，后者解决频繁访问磁盘inode表的效率问题

  3. 数据区：k+2#～n# 为数据块

    • 文件的内容保存在这个区域，磁盘上所有物理块的大小是一样的，如果文件包含超过一块的数据，则文件内容会存放在多个盘块中
重要数据结构
  • 用户打开文件表
    • 进程的PCB结构中保留一个files_struct，称为用户打开文件表或文件描述符表，表项的序号为文件描述符fd，该登记项内登记系统打开文件表的一个入口指针fp，通过此系统打开文件表项连接到打开文件的活动inode
  • 系统打开文件表
    • 是为解决多用户进程共享文件、父子进程共享文件而设置的系统数据结构file_struct，主存专门开辟最多可登记256项的系统打开文件表区，当打开一个文件时，通过此表项把用户打开文件表的表项与文件活动inode联接起来，以实现数据的访问和信息的共享
  • 主存活动inode表
    • 为解决频繁访问磁盘索引节点inode表的效率问题，系统开辟的主存区，正在使用的文件的inode被调入主存活动索引节点inode中，以加快文件访问速度

image-20221205100646528

image-20221205100848938

文件系统调用

文件的创建
1
2
3
int fd, mode;
char *filenamep;
fd = create(filenamep, mode);
  1. 为新文件分配索引节点和活动索引节点，并把索引节点编号与文件分量名组成新目录项，记到目录中
  2. 在新文件所对应的活动索引节点中置初值，如置存取权限i_mode，连接计数i_nlink等
  3. 分配用户打开文件表项和系统打开文件表项，置表项初值，读写位移f_offset清”0”
  4. 把各表项及文件对应的活动索引节点用指针连接起来，把文件描述字返回给调用者。
文件的删除
  • 删除把指定文件从所在的目录文件中除去
  • 如果没有连接用户(i_link 为”1”)，还要把文件占用的存储空间释放。删除系统调用形式为：unlink(filenamep)
  • 在执行删除时，必须要求用户对该文件具有”写”操作权
文件的打开
1
2
3
int fd, mode;
char * filenamep;
fd = open (filenamep, mode);
  • 检索目录，把它的外存索引节点复制到活动索引节点表
  • 根据参数mode核对权限，如果非法，则这次打开失败
  • 当”打开”合法时，为文件分配用户打开文件表项和系统打开文件表项，并为表项设置初值。通过指针建立这些表项与活动索引节点间的联系。把文件描述字，即用户打开文件表中相应文件表项的序号返回给调用者
文件的关闭
1
2
int fd;
close (fd);
  • 根据fd找到用户打开文件表项，再找到系统打开文件表项。释放用户打开文件表项
  • 把对应系统打开文件表项中的f_count减”1”，如果非”0” ，说明还有进程共享这一表项，不用释放直接返回；否则释放表项
  • 把活动索引节点中的i_count减”1” ，若不为”0”，表明还有用户进程正在使用该文件，不用释放而直接返回，否则在把该活动索引节点中的内容复制回文件卷上的相应索引节点中后，释放该活动索引节点
  • f_count和i_count分别反映进程动态地共享一个文件的两种方式
    • f_count反映不同进程通过同一个系统打开文件表项共享一个文件的情况
    • i_count反映不同进程通过不同系统打开文件表项共享一个文件的情况
    • 通过两种方式，进程之间既可用相同的位移指针f_offset，也可用不同位移指针f_offset共享同一个文件
读文件
1
2
3
int nr, fd, count;
char buf [ ]
nr = read (fd, buf, count);
  • 系统根据f_flag中的信息，检查读操作合法性
  • 再根据当前位移量f_offset值，要求读出的字节数，及活动索引节点中i_data[15]指出的文件物理块存放地址，把相应的物理块读到缓冲区中，然后再送到bufp指向的用户主存区中。

image-20221205102611877

写文件
1
nw = write(fd, buf, count);
  • buf是信息传送的源地址，即把buf所指向的用户主存区中的信息，写入到文件中。
文件的随机存取
  • 在文件初次”打开”时，文件的位移量f_offset清空为零，以后的文件读写操作总是根据offset的当前值，顺序地读写文件。为了支持文件的随机访问，提供系统调用lseek，它允许用户在读、写文件前，事先改变f_offset的指向
  • 系统调用的形式为：
1
2
3
4
long lseek;
long offset;
int whence, fd;
lseek(fd, offset, whence);
  • 文件描述字 fd 必须指向一个用读或写方式打开的文件
  • 当whence是”0”时，则f_offset被置为offset
  • 当whence是”1”时，则f_offset被置为文件当前位置加上offset。

3.2 文件共享

文件的静态共享

1
2
chat * oldnamep, * newnamep;
link(oldnamep, newnamep);
  • 检索目录找到 oldnamep 所指向文件的索引节点inode编号
  • 再次检索目录找到 newnamep 所指文件的父目录文件，并把已存在文件的索引节点inode编号与别名构成一个目录项，记入到该目录中去
  • 把已存在文件索引节点inode的连接计数 i_nlink 加 1

image-20221208130412662

  • 链接实际上是共享已存在文件的索引节点 inode，完成链接的系统调用
    • link("/home/fei1/myfile.c", "/home/fei2/myfile.c");
    • link("/home/fei1/myfile.c", "/home/fei3/fei4/testfile.c");
  • 执行后，三个路径名指的是同一个文件:
    • /home/fei1/myfile.c，/home/fei2/myfile.c，/home/fei3/fei4/testfile.c

文件解除链接调用形式为

1
unlink(namep);
  • 解除链接与文件删除执行的是同一系统调用代码。删除文件是从文件主角度讲的，解除文件连接是从共享文件的其他用户角度讲的。都要删去目录项，把 i_nlink 减 “1”，不过，只有当i_nlink减为”0”时，才真正删除文件。

文件的动态共享

  • 文件动态共享是系统中不同的用户进程或同一用户的不同进程并发访问同一文件
  • 这种共享关系只有当用户进程存在时才可能出现，一旦用户的进程消亡，其共享关系也就自动消失
  • 文件的每次读写由一个读/写位移指针指出要读写的位置。现在的问题是：应让多个进程共用同一个读/写位移，还是各个进程具有各自的读写位移呢?
  • 同一用户父、子进程协同完成任务，使用同一读/写位移，同步地对文件进行操作
  • 该位移指针宜放在相应文件的活动索引节点中。当用系统调用fork建立子进程时，父进程的PCB结构被复制到子进程的PCB结构中，使两个进程的打开文件表指向同一活动的索引节点，达到共享同一位移指针的目的。

image-20221208133726368

  • 多用户共享文件，每个希望独立地读、写文件，这时不能只设置一个读写位移指针，须为每个用户进程分别设置一个读、写位移指针
  • 位移指针应放在每个进程用户打开文件表的表目中。这样，当一个进程读、写文件，并修改位移指针时，另一个进程的位移指针不会随之改变，从而，使两个进程能独立地访问同一文件

image-20221208133846993

文件的符号链接共享

  • 操作系统可支持多个物理磁盘或多个逻辑磁盘(分区)，那么，文件系统是建立一棵目录树还是多棵目录树呢?
  • Windows采用将盘符或卷标分配给磁盘或分区，并将其名字作为文件路径名的一部分。

  • UNIX/Linux的每个分区有自己的文件目录树，当有多个文件系统时，可通过安装的办法整合成一棵更大的文件目录树。

  • 问题：系统中每个文件对应一个inode，编号是唯一的，但两个不同的磁盘或分区都含有相同inode号对应的文件，也就是说，整合的目录树中，inode号并不唯一地标识一个文件

    • 办法：拒绝创建跨越文件系统的硬链接

  • 符号链接又称软链接，是一种只有文件名，不指向inode的文件

  • 符号链接共享文件的实现思想：
    • 用户A目录中形式为afile -> bfile，实现A的目录与B的文件的链接。其中只包含被链接文件bfile的路径名而不是它的inode号，而文件的拥有者才具有指向inode的指针
    • 当用户A要访问被符号链接的用户B的文件bfile，且要读“符号链接”类文件时，被操作系统截获，它将依据符号链接中的路径名去读文件，于是就能实现用户A使用文件名afile对用户B的文件bfile的共享
  • 优点：能用于链接计算机系统中不同文件系统中的文件，可链接计算机网络中不同机器上的文件，此时，仅需提供文件所在机器地址和该机器中文件的路径名
  • 缺点：搜索文件路径开销大，需要额外的空间查找存储路径。

3.3 文件空间管理

磁盘文件空间分配采用两种办法

  • 连续分配：文件存放在辅存空间连续存储区中，在建立文件时，用户必须给出文件大小，然后，查找到能满足的连续存储区供使用。
  • 非连续分配：一种方法是以块(扇区)为单位，扇区不一定要连续，同一文件的扇区按文件记录的逻辑次序用链指针连接或位示图指示
  • 另一种方法是以簇为单位，簇是由若干个连续扇区组成的分配单位；实质上是连续分配和非连续分配的结合。各个簇可以用链指针、索引表，位示图来管理

磁盘空闲空间管理方法

位示图

  • 磁盘空间通常使用固定大小的块，可方便地用位示图管理，用若干字节构成一张位示图，其中每一字位对应一个物理块，字位的次序与块的相对次序一致，字位为‘1’表示相应块已占用，字位为‘0’表示该块空闲。
  • 微型机操作系统VM/SP、Windows和Macintosh等操作系统均使用这种技术管理文件存储空间
  • 主要优点是：每个盘块仅需 1 个附加位，如盘块长 1KB，位示图开销仅占 0.012%；可把位示图全部或大部分保存在主存，再配合现代机器都具有的位操作指令，实现高速物理块分配和去配

空闲区表

  • 该方法常用于连续文件，将空闲存储块的位置及其连续空闲的块数构成一张表。
  • 分配时，系统依次扫描空闲区表，寻找合适的空闲块并修改登记项；
  • 删除文件释放空闲区时，把空闲区位置及连续的空闲区长度填入空闲区表，出现邻接的空闲区时，还需执行合并操作并修改登记项。
  • 空闲区表的搜索算法有首次适应、邻近适应、最佳适应和最坏适应算法等，参见pp.239。

空闲块链

  • 把所有空闲块连接在一起，系统保持指针指向第一个空闲块，每一空闲块中包含指向下一空闲块的指针
  • 申请一块时，从链头取一块并修改系统指针
  • 删除时释放占用块，使其成为空闲块并将它挂到空闲链上
  • 这种方法效率低，每申请一块都要读出空闲块并取得指针，申请多块时要多次读盘，但便于文件动态增长和收缩

UNIX/Linux空闲块成组连接法

  • 存储空间分成 512 字节一块。假定文件卷启用时共有可用文件 338 块，编号从 12 至 349。每 100 块划分一组，每组第一块登记下一组空闲块的盘物理块号和空闲总数

image-20230203174705186

3.4 主存映射文件

  • 首先，用于读写文件的操作在功能与格式上与读写主存的操作有很大不同，如果能消除这种差异就能简化编程工作
  • 其次，文件中的数据是一部分一部分在进程空间与磁盘空间之间传送，文件操作实现不但管理复杂且开销较大，能否找出一种方法既降低开销，又能通过直接读写主存来使用文件信息呢?
  • 针对这一点，最早由MULTICS首创通过结合虚存管理和文件管理技术来提供一种新的文件使用方法，称主存映射文件，UNIX/Linux及Windows等现代操作系统都已实现这一功能。

主存映射文件

什么是主存映射文件

  • 系统提供两个新的系统调用
    1. 映射文件，有两个参数：一个文件名和一个虚拟地址，把一个文件映射到进程地址空间。
    2. 移去映射文件，让文件与进程地址空间断开，并把映射文件的数据写回磁盘文件。
  • 优点是：方便易用、节省空间、便于共享、灵活高效

image-20230224141108533

优点：进程读写虚存内容相当于执行文件读写操作，在建立映射后，不再需要使用文件系统调用来读写数据，能大大降低开销；在主存中仅需一个页面副本，既节省空间，又不需要缓冲到主存的复制操作

文件系统的系统视图

image-20230224142310663

3.5 虚拟文件系统

  • 第一个虚拟文件系统在1986年由Sun公司开发成功，并在SunOS中使用。
  • 虚拟文件系统也称虚拟文件系统开关VFS (Virtual Filesystem Switch)
  • 它是内核的一个子系统，提供一个通用文件系统模型，该模型概括所能见到的文件系统常用功能和行为，处理一切和底层设备驱动相关的细节，为应用程序提供标准的接口(文件系统API)。

虚拟文件系统要实现以下目标

  • 同时支持多种文件系统
  • 多个文件系统应与传统的单一文件系统没有区别，在用户面前表现为一致的接口
  • 提供通过网络共享文件的支持，访问远程结点上的文件系统应与访问本地结点的文件系统一致
  • 可以开发出新的文件系统，以模块方式加入到操作系统中。

Linux虚拟文件系统

image-20230224143118663

虚拟文件系统设计思想

  1. 应用层：
    • VFS模型源于UNIX文件系统，使得用户可直接使用标准UNIX文件系统调用来操作文件，无需考虑具体文件系统特性和物理存储介质，通过VFS访问文件系统，才使得不同文件系统之间的协作性和通用性成为可能
  2. 虚拟层：
    • 对所有具体文件系统的共同特性进行抽象的基础上，形成一个与具体文件系统实现无关的虚拟层，并在此层次上定义与用户的一致性接口
  3. 实现层：
    • 该层使用类似开关表技术进行具体文件系统转接，实现各种具体文件系统的细节，每一个是自包含的，包含文件系统实现的各种设施，如超级块、节点区、数据区以及各种数据结构和文件类的操作函数

虚拟文件系统

VFS实质上是一种存在于主存中的，支持多种类型具体文件系统的运行环境，功能有：

  • 记录安装的文件系统类型
  • 建立设备与文件系统的联系
  • 实现面向文件的通用操作
  • 涉及特定文件系统的操作时映射到具体文件系统中去。

Linux虚拟文件系统

image-20230224145414967

VFS的组成

  • 超级块对象 - 代表一个文件系统。
    • 存放已安装的文件系统信息，如果是基于磁盘的文件系统，该对象便对应于存放在磁盘上的文件系统控制块，每个文件系统都对应一个超级块对象。
    • 如Ext2超级块，并被存放在磁盘特定扇区上，当内核对一个具体文件系统进行初始化和注册时，调用alloc_super()函数为其分配一个VFS超级块，并从磁盘读取具体文件系统超级块中的信息填充进来，即VFS超级块在具体文件系统安装时才建立，并在它们卸载时被自动删除，可见VFS超级块仅存于主存中。
  • 索引节点对象 - 代表一个文件。
    • 存放通用的文件信息，如果是基于磁盘的文件系统，该对象对应于存放在磁盘上的文件FCB，即每个文件的inode对象，而每个inode都有一个inode索引节点号，唯一地标识某个文件系统中的指定文件。
    • 对于UNIX类文件系统来说，这些信息从磁盘inode直接读入VFS的inode对象中。可把具体文件系统存放在磁盘上的inode称为静态节点，它的内容被读入主存VFS的inode才能工作，后者也称为动态节点
  • 目录项对象 - 代表路径中的一个组成部分。
    • 存放目录项与对应文件进行链接的各种信息，VFS把最近最常使用的dentry对象放在目录项高速缓存中，加快文件路径名搜索过程，以提高系统性能
  • 文件对象 - 代表由进程已打开的一个文件。
    • 存放已打开文件与进程的交互信息，这些信息仅当进程访问文件期间才存于主存中
    • 文件对象在执行系统调用open()时创建，执行系统调用close()时撤销。
    • 每个文件都用一个32位数字来表示下一个读写的字节位置，通常称它为文件位置或偏移量(offset)，每当打开一个文件时，偏移量被置0，读写操作便从这里开始，允许通过系统调用lseek对文件位置作随机定位。
    • Linux建立文件对象(file)来保存打开文件的文件位置，file结构除保存文件当前位置外，还把指向该文件inode的目录项指针也放在其中，并形成一个双向链表，称系统打开文件表。
    • 操作系统之所以不直接使用dentry结构是因为多个进程能够打开同一个文件，因为每一个file结构实际上对应了一个进程的一次打开过程。file结构中记录了文件访问模式，读写指针等信息。
    • 文件描述符fd用来描述打开的文件，每个进程用一个files_struct结构来记录文件描述符的使用情况，这个结构称为用户打开文件表。
    • 指向该结构的指针被保存在进程的task_struct结构的成员files中

image-20230224150106624

image-20230224150641250

image-20230224151231371

image-20230224153404909

image-20230224153529284

image-20230224153625151

image-20230224153643673

image-20230224153725825

文件系统注册与注销，安装与卸载

文件系统的注册与注销

  • Linux支持多个物理磁盘，每个磁盘可划分为一个或多个磁盘分区，每个分区上可建立一个文件系统，一个安装好的Linux操作系统究竟支持几种不同类型的文件系统，是通过文件系统类型注册链表来描述的，VFS以链表形式管理已注册的具体文件系统。
  • 向系统注册文件系统类型有两种途径
    • 一是在编译操作系统内核时确定可支持哪些文件系统，在文件系统被引导时，在VFS中进行注册
    • 二是文件系统当作可装载模块，通过insmod/rmmod命令在装入该文件系统模块时向VFS注册/注销。

image-20230224153910074

  1. 文件系统安装: 文件系统类型名、所在物理设备名、安装点，再用mount命令安装

  2. 文件系统安装过程: 寻找匹配的file_system_type、查找安装点VFS inode、分配一个VFS超级块、利用read_super()函数读入参数、申请一个vfsmount数据结构。

  3. 文件系统卸载过程: 是否可卸载、如果为“脏”把VFS超级块写回磁盘、删去vfsmount。

文件系统的缓存机制

VFS inode缓存

  • 把当前使用的inode采用散列技术保存起来，从中快速找到所需inode

VFS目录高速缓存

  • 系统维护表达路径与inode对应关系的VFS目录缓存，其中存放被访问过的目录。

页高速缓冲区

  • Linux维护一组页缓冲区，它独立于任何类型的文件系统，被所有物理设备所共享
  • 优点：
    • 数据一经使用，就在页缓冲区中留下备份，再次使用时可直接找回，避免不必要的磁盘I/O
    • “脏”页写回磁盘时，可适当进行排序，实现磁盘驱动调度优化。

EXT2文件系统

  • EXT(92年)和EXT2(94年)是专为Linux设计的可扩展文件系统。
  • EXT2把它所占用的磁盘逻辑分区划分为块组，每个块组依次包括超级块、组描述符表、块位示图、inode位示图、inode表以及数据块。
  • 块位示图集中本组各数据块的使用情况
  • inode位示图记录inode表中inode的使用情况。
  • inode表保存本组所有的inode，inode用于描述文件，一个inode对应一个文件和子目录，有一个唯一的inode号，并记录了文件在外存的位置、存取权限、修改时间、类型等信息。

文件系统结构

image-20230224155556986

EXT2的超级块

  • Ext2超级块用来描述目录和文件在磁盘上的静态分布，包括尺寸和结构，每个块组都有一个超级块，只有块1的超级块才被读入主存工作，直至卸载，其他块组的超级块仅作为恢复备份。
  • 超级块主要包括：块组编号、块数量、块长度(1KB至4KB)、空闲块数量、inode数量、空闲inode数量、第一个inode号、第一个数据块位置、每个块组中的块数、每个块组的inode数，以及安装时间、最后一次写时间、安装信息、文件系统状态信息等内容。

EXT2的组描述符

  • 数据块位示图。表示数据块位示图占用的块号，此位示图反映块组中数据块的分配情况，在分配或释放数据块时需使用数据块位示图。
  • inode位示图。表示inode位示图占用的块号，此位示图反映块组中inode的分配情况，在创建或删除文件时需使用inode位示图。
  • inode表。块组中inode占用的数据块数，系统中的每个文件对应一个inode，每个inode都由一个数据结构来描述。
  • 空闲块数、空闲inode数和已用数目。

EXT2的inode

inode用于描述文件，一个inode对应一个文件和子目录，有一个唯一的inode号，并记录了文件的类型及存取权限、用户和组标识、修改/访问/创建/删除时间、link数、文件长度和占用块数、在外存的位置、以及其他控制信息。

Linux数据块分配策略

EXT2采用两个策略减少文件碎片

  • 原地先查找策略：为文件分配数据块时，尽量在文件原有数据块附近查找。先试探紧跟文件末尾的数据块，然后试探位于同一个块组相邻的64个数据块，接着在同一个块组中寻找其他空闲数据块；实在不得己才搜索其他块组，且首先考虑8个一簇的连续的块。
  • 预分配策略：引入预分配机制，就从预分配的数据块取一块来用，紧跟该块后的若干个数据块空闲的话，也被保留，保证尽可能多的数据块被集中成一簇。
  • 数据结构中包含属性prealloc_block和prealloc_count，前者指向可预分配数据块链表中第一块的位置，后者表示可预分配数据块的总数。
Prev
2023-08-09 14:53:19 # NJU # 计算机操作系统
Next