文件管理

计算机系统，文件管理部分的知识结构，以及内部各小点之间的联系，外观虽然很普通，但是本人注重学习效率，整体把我知识结构，力求达到最佳的复习效果，希望同学们喜欢

文件管理

• 1. 基本概念
  • 什么是文件
    • 以计算机硬件位载体
    • 储存在计算机上的
    • 信息集合
    • 概念
    • 用户进行输入输出的基本单位
  • 基于结构的定义
    • 数据项：描述对象某种属性的1个值（可命名的最小的逻辑数据--原子数据）
      • 若干相关的数据项
    • 记录：一组相关数据项的集合
      • 若干相关的记录
    • 文件：一组相关信息的集合
      • 有结构文件（记录式文件）
      • 无结构文件（字符流）
  • 文件的属性
    • 名称、标识符、类型、位置、大小、保护、时间、日期、用户标识符
      • 还包括存在FCB中的文件访问控制信息
  • 文件系统要实现的基本操作
    • 创建文件
    • 写文件
    • 读文件
      • 使用read系统调用，也需要使用open返回的指针
    • 打开和关闭文件
      • 首次
      • 使用系统调用open
        • cup进入核心态
      • open根据文件名搜索目录，并从外存将找到的目录项复制到打开文件表（内存）中
        • 是将文件的FCB调入内存
      • open返回一个指向该目录项的指针
      • 通过使用该指针，完成所有的I/O操作
      • 设置打开计数器count，当有用户打开时，count＋1， 有一个用户关闭时count-1，当=0时，系统将回收分配给 该文件的内存空间
    • 文件重定位
    • 删除文件
    • 截断文件
    • 其它操作都可以直接使用该指针
• 2. 文件的逻辑结构
  • 文件内部结构
    • 无结构文件
    • 有结构文件
      • 顺序文件
        • 通常是定长的也可以是变长的
        • 在物理上
          • 顺序存储（默认）
          • 链式存储
        • 逻辑上时顺序的
        • 不方便增删
      • 索引文件
        • 建立索引表（1个表项指向1个文件）
        • 索引表本身就是一个顺序文件
        • 索引表按关键字排列则可实现快速检索
        • 方便增删，实现随机存取
        • 索引表需要占用额外空间
      • 索引顺序文件
        • 建立索引表（每个表项对应1组记录）
        • 1.顺序查找索引表，找到该文件所在的那1组记录
        • 2.顺序查找该组记录，找到目标文件
      • 直接文件/散列文件
        • 通过给定键值找到文件
        • 通过散列函数转换出键值找到文件
        • 可能会引起冲突，不同关键字的散列函数值可能相同
  • 文件之间的逻辑结构（目录结构）
    • 目录的实现
      • 自身就是一种顺序文件（目录文件）
      • 目录中的1个目录项就是1个文件控制块FCB
        • 该文件基本信息
        • 存取控制信息
        • 使用信息
        • FCB
      • 实际的系统中，目录中只有文件名和索引节点指针
        • 什么事索引节点
          • 文件的其它信息（检索时用不到的）存放在索引节点中
          • 每个文件对应1个索引节点
          • 目录项的大小变小，单个磁盘块存放的目录项就越多，查询文件时访问磁盘的的次数和就越少
    • 多种目录结构
      • 单级（只有一张目录表）
      • 两级（分为主文件目录、用户文件目录）
      • 文件不可重名或不能按类别存放、分层次管理）
      • 多级（树形）
        • 系统根据文件路径访问文件
        • 文件路径
          • 绝对路径（从根目录出发）
          • 相对路径（从当前目录出发）
        • 可重名、可对文件进行分类，解决命名冲突，符合多层次管理的需求
        • 不便于文件的共享
      • 无环图
        • 在多级目录的基础上，加一些指向同一文件（共享文件）的有向边
        • 位共享文件设置“共享计数器”记录当前共享的用户数
        • 当共享文件计数器=0时，系统将该文件删除
        • 用户不可以删除文件，只是删除了自己指向该文件的那个指针
• 3. 文件共享
  • 静态共享（用户对同一文件的共享）
    • 基于索引节点实现 （硬链接）
      • 两个用户的目录项中都有一个指向同一文件的目录项
      • 为索引节点设置链接计数器count，记录当前用户共享个数
      • 用户删除共享文件时，不能直接将该文件删除，是向count-1，而后删除自己的对应目录项
      • 只有当count=0时，由系统负责将该文件删除
      • 不可直接删除共享文件
    • 利用符号链接实现 （软链接）
      • 系统创建link类型文件F（符号链接）【包含该共享文件的路径名】
      • 将F写入另一个用户的目录中（索引节点中）
      • 只有文件主才拥有指向该文件的指针
      • 另一个用户访问文件时，系统找到所以节点--找到F--根据其中的路径访问文件
      • 若文件主将文件删除，其他用户新建一个名字相同的文件，则原本的共享用户还是可以找到文件，但是该文件不时原来那个文件了
      • 共享用户每次访问都要检索一遍文件路径，增加了磁盘启动频率
      • 可直接删除共享文件
    • 从文件系统的层面看，这两种共享方法，都增加了该共享文件的文件名个数，如果从整个系统进行搜索，会找到多个该文件
  • 动态共享（进程对同一文件的共享）
• 4. 文件保护
  • 实现方式
    • 口令保护
      • 用户建立一个文件时需要一个口令，系统将其附在FCB中
      • 告诉允许共享该文件的其他用户
      • 口令直接存储在系统内部，不够安全
    • 加密保护
      • 用户对文件进行加密，访问文件时需要密钥
      • 编码和译码需要一定时间
      • 由用户实现
    • 访问控制
      • 由系统实现
      • 根据用户身份进行控制
      • 为每个文件和目录增加一个访问控制列表
        • 规定每个用户名对应的允许访问的文件类型
        • 可以使用复杂的访问方法
        • 长度无法预计，可能空间管理更复杂
      • 精简的访问列表
        • 三种用户类型
          • 拥有者（文件的创建者）
          • 组（一组需要共享文件且具有类似访问的用户
          • 其它
• 5. 文件系统的实现 （文件的物理结构）
  • 文件分配方式（如何为文件分配磁盘块）
    • 顺序分配
      • 必须为一个文件分配连续的存储空间
      • 目录内容【起始块号，文件长度】
      • 顺序存取速度快，可随机访问
      • 容易产生碎片
    • 链接分配
      • 隐式链接
        • 每个磁盘块有指向下一个磁盘快的指针
        • 目录内容【起始块号，结束块号】
        • 解决了碎片问题，外存利用率高
        • 只可以顺序访问，不可随机访问
      • 显式链接
        • 磁盘块有指向下一个磁盘快的指针，另外建立一张文件分配表（FAT）记录磁盘块的先后关系
        • 目录内容：【起始块号】
        • 拥有隐式链接的优点，另外FAT常驻内存，通过FAT可实现对文件的随机访问
        • FAT需要占用一定的存储空间
        • FAT中可用-1、-2等代表最后的磁盘块、空闲的磁盘块等，因此，系统也可用FAT对空闲磁盘块进行管理
    • 索引分配
      • 将每个文件占用的所有磁盘块号都集中在一起，建立一张索引表，单独存放在一个磁盘块中，该磁盘块称为索引块
      • 三种索引分配方案
        • 为解决索引块占用空间问题
        • 链接方案
          • 为解决大文件索引块大的问题
          • 将多个索引块链接起来用
        • 多层索引
          • 建立多级索引结构
        • 混合索引
          • 索引表中既有直接地址，又有多级索引指针
  • 文件存储空间管理（如何管理空闲的磁盘块）
    • 存储空间划分初始化
      • 文件卷（逻辑卷）
        • 目录区
          • 文件目录
          • 空闲表
          • 位示图
          • 超级块
          • 。。。
        • 文件区
    • 管理策略
      • 空闲表法
        • 建立空闲盘块表【记录连续空闲区的起始盘块号、盘块数】
        • 分配
          • 首次适应
          • 最佳适应等
        • 回收
          • 注意合并相邻的空闲区
      • 空闲链表法
        • 空闲盘块链
          • 以盘块为单位组成
          • 分配
            • 从链头依次取下空闲块进行分配
          • 回收
            • 从链尾依次插入回收的盘块
        • 空闲盘区链
          • 以盘区为单位组成
          • 分配
            • 采用首次适应、最佳适应等
          • 回收
            • 相邻空闲盘块合并后插入链尾
      • 位示图法
        • 用2位二进制位表示盘块编号【字号/位号】
        • 考点：盘块号b与（字号i，位号j）的转换
          • i、j从0开始
            • b=ni+j
            • i=b/n向上取整
            • j=b%n
          • i、j从1开始
            • b=n(i-1)+(j-1)
            • i-1=b/n向上取整
            • j-1=b%n
      • 成组链接法
• 6. 磁盘组织与管理
  • 磁盘的结构
    • 盘片
      • 盘面（每个盘面都可以用作磁盘）
        • 磁道
          • 柱面（所有盘片上相对位置相同的磁道组成柱面）
        • 扇区
          • 可寻址的最小单位
        • 磁盘的物理地址结构（柱面号，盘面号，扇区号）
          • 这样的地址结构顺序，可减少访问连续存储空间时，磁头的移动次数和距离
    • 主轴
    • 磁头
  • 磁盘调度算法
    • 一次读写操作时间(Ta=Ts+Tr+Tt)
      • 寻找时间Ts=m×n+s
      • 延迟时间Tr=1/2r
      • 传输时间Tt=b/rN
      • m：磁盘驱动器速度相关的常数 s：启动磁臂的时间 n：跨越n条磁道 r：磁盘转速 N一个磁道上的字节数 b：所需读写的字节数
    • 如何减少延迟时间
      • 交替编号
        • 同一盘片中的编号交替
      • 错位命名
        • 不同盘片之间对应的编号错位
          • 比如：1号盘面的0号和2号盘面的0号，在磁盘中固定盘片时，上面的0和下面的0，相对位置要错开
    • 如何减少寻找时间
    • 调度算法
      • FCFS算法
        • 先来先服务
      • SSTF算法
        • 每次相应与当前磁头位置最近的哪一个访问请求
        • 可能导致饥饿
      • SCAN算法
        • 磁头朝一个方向移动，一路（按地址大小和移动方向）顺序访问“沿途”的请求
        • 只有到达磁盘边缘才改变移动方向，返回途中也是（按地址大小和移动方向）顺序访问请求
        • 各磁道的响应平率不平均
      • C-SCAN算法
        • 磁头朝一个方向移动，一路（按地址大小和移动方向）顺序相应请求
        • 到达磁盘边缘后立即快速返回至初始位置，返回途中不处理响应
      • LOOK算法
        • LOOK
          • SCAN算法的改进
          • 只要在当前磁头移动方向上没有相关地址的访问请求，磁头立即掉头
        • C-LOOK
          • C-SCAN算法的改进
          • 只要在当前磁头移动方向上没有相关地址的访问请求，磁头立即返回到反方向上最远的那个请求访问的地址
  • 磁盘管理
    • 磁盘初始化
      • 低级格式化（物理格式化）：划分扇区
      • 磁盘分区：（C盘、D盘……）
      • 逻辑格式化：建立文件系统（建立目录文件、建立用于存储空间管理的水结构)
    • 引导块
      • 计算机启动时需要运行初始化程序（自举程序）
      • ROM中存放很小的自举装入程序
      • 完整的自举程序存放在初始块（引导块）中
    • 坏块管理
      • 简单的磁盘：逻辑格式化时将坏块标记出来
      • 复杂的磁盘：磁盘控制器维护一个坏块链，并管理备用扇区
• 设备
• 设备管理模块
  • 对该文件对应的物理块中的数据进行操作，对磁盘设备发出请求
• 辅助分配模块
  • 分配和回收存储空间
• 物理文件系统
  • 将逻辑地址转换为物理地址
• 逻辑文件系统与 文件信息缓冲区
  • 将用户要操作的文件号转换为逻辑地址
• 存取控制模块
  • 验证用户是否有访问控制权限
• 文件目录系统
  • 根据用户提供的路径，找到对应文件的FCB或索引节点
• 用户调用接口
  • 为用户提供文件操作功能接口
• 提高访问 文件速度
  • 提前读（将可能要访问的数据读入缓冲区）
  • 延迟写（将数据写入缓冲区，并写上“延迟写”的标志，先 不写入磁盘更新该文件，当该块缓冲区要被分配出去 时，才将数据写入磁盘，减少了访问磁盘的次数）
  • 为文件分配连续簇
  • 采用磁盘高速缓存
• 系统级安全管理
  • 注册
  • 登录