OS_第六章文件管理

OS OS
Created At :
Count:4.6k Views 👀 : Comment:
  1. 第六章-文件管理

第六章-文件管理

  • 文件和文件系统
    • 文件、记录和数据项 图片
    • 文件类型
      • 按 文件性质与用途 分类：系统文件、用户文件、库文件
      • 按 文件中的数据形式 分类：源文件、目标文件、可执行文件
      • 按 存取控制属性 分类：只执行文件、只读文件、读写文件
      • 按 文件的组织形式和处理方式 分类：普通文件、目录文件、特殊文件
    • 文件系统模型 图片
    • 常用文件系统格式类型（补充）
      • FAT12
      • FAT16
      • FAT32
  • 文件的逻辑结构
    • 文件的逻辑结构和物理结构的区别
      • 逻辑结构： 从用户观点出发所观察到的文件组织形式 ，即 文件由一系列的逻辑记录组成，是用户可以直接处理的数据及其结构 ， 独立于文件的物理特性，又称为文件组织
      • 物理结构：指的是 系统将文件存储在外存上所形成的一种存储组织形式
    • 文件逻辑结构的类型
      • 按照文件是否有结构分类
        • 有结构文件（ 记录式文件 ）：用 每个记录来描述实体集中的一个实体 ，根据记录的长度又可以分为 定长记录和变长记录 两种。 图片
          • 按文件的组织方式分类：根据 有结构文件 中的 各条记录 在 逻辑上如何组织 进一步分类
            • 顺序文件：文件中的记录 逻辑上顺序排列 （表格）,根据记录之间的顺序 是否按照关键字顺序排列 又可以分为： 串结构、顺序结构 图片
            • 索引文件： 针对可变长记录 ，建立一张 索引表（索引表本身是定长记录的顺序文件） ，为每个记录设置一个表项，加快对记录的检索速度，以关键字作为key 图片
            • 索引顺序文件： 索引文件+顺序文件，为一组记录 设置一个索引表项， 减少索引表的大小，每个索引表项指向一个顺序文件 图片
            • 检索效率分析
              • 分析 图片
              • 多级索引 举例说明 （进一步加快检索速度） 图片
        • 无结构文件：.txt文件、源程序、可执行文件、库函数等等，即 流式文件 ， 文件的长度以字节为单位。
  • 外存分配方式
    • 文件的物理结构与外存分配： 文件的物理结构 即 文件在外存上的存储组织形式
    • 连续分配（ 顺序文件 ）：（ Tips :类似与内存分页，磁盘中的存储单元也会被分为磁盘块，对应的文件也会分成文件快， 一般地，磁盘块=文件块=内存块=页面 ）
      • 连续分配示意图 图片
      • 连续分配评测 图片
    • 链接分配（ 链接式文件结构 ）： 支持离散分配 ，通过盘块上的指针实现 同一文件多个离散盘块的链接
      • 隐式链接： 通过每个文件块内指针指向下一个盘块实现链接
        • 隐式链接示意图 图片
        • 评价 图片
      • 显式链接： 把用于链接文件的各个物理块的指针显式地存放在一张表中，即文件分配表（FAT：File Allocation Table）
        • FAT介绍： 一张磁盘只会建立一张FAT，开机时便将其放入内存，并常驻内存
          • FAT空间开销计算 图片
          • 簇的概念： 簇是一组连续的扇区 ， 一个簇通常有2n个盘块 ，一般一个簇有（ 1,2,4,8 个扇区），显然有若一个簇包含8个扇区，则磁盘的寻址范围最大容量可以扩大8倍, 以簇为基本分配单位的好处是能适应磁盘容量不断增大的情况，还可以减少FAT表项个数，使得FAT占用更少的内存， 但是 簇的引用也造成了更大的簇内零头
        • 评价： 图片
      • 链接分配总结 图片
    • 索引分配（ 索引式文件结构 ）
      • 索引分配的基本思想： 文件打开仅须把该文件所占用盘块编号调入内存 即可， 故可将每个文件所对应的盘块号集中地存放一个所谓的索引块中 ，形成一个 索引表
      • 索引分配的实现过程 图片
      • 索引分配的拓展：( 文件太大解决方案 )
        • 链接方案：若 索引表太大 ，一 个索引块装不下，可以将多个索引块链接起来存放，显然这种方案是低效的 图片
        • 多层索引方案
          • 两层/多层索引方案（ 适合中、大作业 ） 图片
          • 混合索引（ UNIXOS ）方案（ 兼顾小、中、大作业 ） 图片
            • 直接寻址 ：直接地址项存放对应文件数据的盘块的盘块号， 盘块大小4KB、盘块号占4B，则支持长度在4KB×10 = 40KB以内的文件
            • 一次间接寻址 ： i.addr(10)指向对应文件的一级索引块 ，一级索引块可含4KB/4B = 1K个盘块号，故支持长度在 (4KB×1K=4MB)+40KB 以内的文件
            • 多次间接寻址 ： i.addr(11)、 i.addr(12)分别指向对应文件的两级索引块和三级索引块 ，所以支持文件长度可达( 4KB×1K×1K ×1K=4TB)+(4KB×1K×1K=4GB)+4MB+40KB
      • 索引分配总结 图片
    • 顺序分配、链接分配、索引分配总结 图片
    • 直接文件和散列文件 图片
  • 文件存储空间管理
    • 文件存储空间管理的一些概念
      • 对非空闲磁盘块的管理（存放了文件数据的磁盘块）
      • 对空闲磁盘块的管理
      • 存储空间的划分与初始化 图片
    • 空闲表法（ 连续分配方式 ） 图片
    • 空闲链表法（ 针对连续分配、离散分配 ） 图片
      • 空闲盘块链（ 适用离散分配方式 ）： 以盘块为单位 组成一条空闲链
      • 空闲盘区链（ 适用连续、离散分配方式 ）： 盘区为单位 组成一条空闲链
    • 位示图法：用每个二进制bit位表示一个盘块是否空闲 图片
      • 盘块号（b）与（行号，列号）【i,j】 的相互转换公式 b = ni +j (n表示字长)
    • 成组链接法（ 针对大型文件系统，UNIX采用了成组链接法管理空闲磁盘块 ）
      • 成组链接法工作原理 图片
      • 成组链接法的分配
        • 检查空闲盘块号栈是否上锁 ，若未上锁，则从 栈顶 取出一空闲块：（1）若其不是栈底， 即该组空闲盘块号不为1 ，则将其盘块分给用户，然后将栈顶指针下移一格，对S.free作减1操作。（2） 若是栈底，该块对应的盘块中记有下一组可用的盘块号 ，因此， 必须先将该盘块的内容读入超级块的空闲盘块号栈中，然后再将该盘块分配出去 。 若s_nfree为0，而且栈底登记的盘块号为0，则表示系统中无空闲盘块可分配。
      • 成组链接法的回收
        • 检查空闲盘块号栈，若未上锁 ，若栈中空闲盘块号数N<100，即 栈未满，则执行空闲盘块号数N的加1操作，并将回收盘块的盘块号记入空闲盘块号栈的栈顶 ； 若 栈已满 ，应 将空闲盘块号栈的当前内容包括盘块数及所有盘块号记入新回收的盘块中 ，同时 将新回收盘块的盘块号作为S.free(0)即栈底，并置空闲盘块号栈的空闲盘块数N为1
  • 目录管理
    • 目录管理基本要求
      • 实现 “按名存取”（文件名=>外存地址）
      • 提高目录检索速度及文件存取速度
      • 文件共享
      • 允许文件重名，以便于文件使用
    • 文件控制块（ File Control Block ） 图片
      • 一个文件对应一个PCB，一个PCB就是一个文件目录项
      • FCB的有序集合称为文件目录
      • FCB包括了文件的基本信息 ，包括 文件名、物理地址、逻辑结构、物理结构，存取控制信息 （读/写/读写）， 使用信息 （文件创立时间、修改时间），其中 最重要最基本的信息是文件名及其文件存放的物理地址，这实现了文件的按名存取，实现了文件名到物理地址的映射。
    • 目录结构
      • 单级目录结构：早期OS不支持多级目录， 整个系统中只建立一张目录表，每个文件占一个目录项 图片
        • 实现了“按名存取”
        • 查找速度慢，不允许重名，不便于文件共享
      • 两级目录结构：早期的多用户OS， 采用两级目录结构 ， 分为主文件目录和用户文件目录 图片
        • 优化了目录检索的速度 ，例子（MFD指的是 主文件目录 ， UFD： 用户文件目录 ） 图片
        • 两级目录结构允许不同用户的文件名重复，但两级目录结构依然缺乏灵活性，用户不能对文件再分类
        • 用户隔离不便于文件共享和用户间协作
      • 多级目录结构（ 树形目录 ） 图片
        • 绝对/相对路径（ 相对路径的引入有效减少了IO次数 ）：若使用绝对路径，OS根据绝对路径一层一层地找到下一级目录；但很多时候，用户会连续访问同一目录内多个文件，每次都从根目录开始查找显然是低效的，引入当前路径后，磁盘I/O次数减少，提高了文件访问效率。
      • 无环图目录结构（ 在树形目录的基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图，更方便的实现多个用户间文件共享 ） 图片
    • 索引结点（ FCB的优化 ）
      • 索引结点引入的必要性： 当文件很多时，文件目录可能占用大量的盘块，而FCB中有冗长信息是在目录检索中是不需要的 ， 目录检索只用到了文件名， 所以在 UNIX系统 中， 将文件名与文件描述信息分开 ， 将文件描述信息单独形成一个成为索引结点的数据结构，简称为i结点 ，在 文件目录中每个目录项仅由文件名和指向该文件所对应的i结点指针组成 ，其中 14个字节为文件名，2字节为指向i结点的指针。 图片
      • FCB与索引结点的开销比较： 图片
    • 目录查询技术
      • 实现文件按名存取的基本步骤
        • 系统根据用户提供的文件名，对文件目录进行查询，找出该文件的文件控制块或索引结点
        • 按照对应文件控制块或索引结点中所记录的文件物理地址（盘块号），计算出文件在磁盘上的物理地址
        • 启动磁盘驱动程序，将所存取的文件读入内存进行具体读写操作
      • UNIX文件卷组织结构
        • 系统引导块0#
        • 超级块1 #
        • 磁盘索引结点块 2# ~ K#
        • 文件数据块 K+1# ~ N#
      • 以UNIX系统为例，目录查询举例说明 图片
  • 文件共享与保护
    • 文件共享的概念：指系统应 允许多个用户（进程）共享同一份文件 ，从而在系统中 只需保存该共享文件的一个副本即可
    • 早期文件共享的方法
      • 绕弯路法 图片
      • 连访法（ 类似于链接法 ） 图片
    • 基于索引结点的共享方式（ 硬链接 ）：基本原理： 借助索引结点，结点中设置计数变量count ，用于 表示链接到本索引结点上的用户目录项数 ，当count==0时，由OS负责删除文件。 图片
    • 基于符号链的共享方式（ 软链接 ）：基本原理：在 Windows系统中的.Link类型文件 就是采用了 软连接 的形式实现的文件共享，里面存放的是 共享文件的绝对地址 ，所以 访问该文件需要查询多级目录 ，会有 多次磁盘I/O ，因此 软连接的速度要比硬链接慢 图片
    • 文件系统安全保护影响因素及其对策
      • 人为因素
        • 存取控制机制
          • 保护域
            • 保护域的概念： 保护域 指的是 进程对一组对象（软件、硬件）访问权的集合 图片
            • 进程和域间静态联系： 一个进程只联系一个域 ， 在进程的整个生命周期中，其可用资源是固定的 ，这种域成为 “静态域”
            • 进程和域间动态联系： 一个进程联系多个域 ， 进程的每个运行阶段链联系一个域 ，这样可 根据运行的实际需要规定进程的每个阶段中所能访问的对象。
          • 访问矩阵： 利用一个矩阵来描述系统的访问控制，其中行表示不同的域，列表示不同的对象 [R:读 ；W：写 ；E：执行] 图片
            • 基本的访问矩阵 / 具有域切换权的访问矩阵 ：如上图， 表示（D1域可以切换到D2域），（D2域可以切换到D3域）
          • 访问矩阵的修改：指的是 不同域之间的修改
            • 拷贝权：用“ * ”表示，需要注意的是 拷贝是限制拷贝 ，不能把*也拷贝过去， 限制了访问权的进一步扩散 图片
            • 所有权： 用“ O ”表示 ， 若拥有该对象的所有权，可以增删其他域的访问权 图片
            • 控制权（ 与前两者不同，前两者均是在不同域之间的变化，即同一列，而控制权是在一个域中的变化，即同一行的变化 ），RT： D2对D3域有控制权，所以可以增删D3域中各对象的访问权 图片
          • 访问矩阵的简化策略
            • 必要性与可行性： 必要性：系统中有众多的域，而且有很多的对象，时空开销难以接受 ； 可行性：访问矩阵中很多表项都是空的，所以该矩阵为稀疏矩阵，可以进行压缩
            • 简化对策
              • 访问控制表（ 按列划分 ）：为 每一列（即每个对象） 建立一张访问控制表ACL，在该表中，把该列所有的空项剔除。
              • 访问权限表（按行划分） ：为 每一行（即每个域） 建立一张访问权限表。ＲＴ，在该例中， 图片
      • 系统因素
        • 系统容错技术
      • 自然因素
        • 后备系统
    • 磁盘容错技术
      • 基本概念: 设置冗余部件以提高系统可靠性
      • 低级磁盘容错技术SFT-I ：双份目录与双份文件分配表；热修复重定向、写后读校验
      • 中级磁盘容错技术SFT-I： 磁盘镜像与磁盘双工
  • 数据一致性控制
    • 数据一致性问题及技术： 当一个数据被分别存储到多个文件中时，便会出现数据的一致性问题 技术： 硬件支持-稳定存储器 ：理论上不会出现故障和错误，实际上 高度可靠的存储器系统 ； 采用冗余技术 ，即将一份信息同时驻留在多个独立的非易失性的存储器上
    • 事务概念及恢复算法
      • 事务的定义： 事务是用于访问和修改各种数据项的一个程序单位 。事务也可以被看做是 一系列相关读和写操作 。 事务可以在同一文件不同记录中，也可以在多个文件中 。事务具有 “原子性”特征（提交操作/夭折操作）
      • 事务记录表（ 运行记录 ）：每一项记录都描述了 事务运行中的重要事务操作 ，表中包括（ 事务名、数据项名、旧值、新值 ）
      • 恢复算法
        • 针对 已完成事务 ： Ｒｅｄｏ操作 ： 将所有已被修改的数据设置为新值
        • 针对 夭折事务 （ 没有全部完成的事务 ）： Ｕｎｄｏ操作 ： 将所有已被修改的数据恢复为修改前的值
    • 检查点及恢复算法改进：如上述所述， 一旦系统发生故障，必须检查整个日志表，以确定哪些事务需要利用redo过程去设置新值，哪些事务需要利用undo将所有修改的数据恢复为修改前的值 ，因此 引入检查点，使对事务记录表中事务记录的清理工作经常化。
      • 检查点的作用： 首先 是将驻留在 易失性存储器 中的 当前事务记录表中的所有记录输出到稳定存储器 中； 其次 是将驻留在 易失性存储器 中的 所有已修改数据 输出到 稳定存储器 中； 然后 是将事务记录表中的 <检查点> 记录输出到 稳定存储器 中；最后是每当出现一个<检查点>记录时，系统便执行上述恢复操作。
      • 恢复算法改进： 首先 ，查找事务记录表，确定在 最近检查点以前 开始执行的 最后事务Ti ；然后 针对Ti以后开始执行的事务集 T中的事务Tk区别不同情况 分别执行恢复操作Redo(Tk) /Undo(Tk)； 最后 ， 发生故障或检查点时执行恢复算法
    • 并发控制技术
      • 用于实现事务顺序性的技术：在 多用户系统和计算机网络环境 下，可能有 多个用户在同时执行事务 ，由于 事务具有原子性 ， 只有在一个事务执行完后，才允许另一事务执行 ，即 各事务对数据项的修改是互斥的 ，这便是 所谓的顺序性 ，而把 用于实现事务顺序性的技术称为并发控制。
      • 利用互斥锁来实现顺序性： 为每一个共享对象设置一个互斥锁：简单易行，效率不高。
      • 利用互斥锁和共享锁来实现顺序性： 共享锁 与 互斥锁 的区别， 共享文件只允许一个事务去写但允许多个事务同时读 ，类似于 读者——写者问题解决方案。
    • 重复数据的一致性问题
      • 重复文件的一致性 图片
      • 盘块号一致性的检查：（一个盘块要么是空闲块，要么是文件盘，所以 两个盘块数计数相加应该是1） 图片
        • 丢失举例 图片
        • 重复举例 图片
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 2542608082@qq.com

©2023 TanJ

Built with Hexo and 3-hexo theme