文件的组织结构 PPT课件

1 第五章 文件系统 2 学习目标 1 理解文件系统的管理目标与操作系统其他部分管理目标的区别 掌握文件及文件系统的相关概念 2 理解并掌握文件系统的管理思想和手段 包括 熟练掌握文件系统对文件目录的组织 文件系统的逻辑结构 物理结构 文件存储空间的管理方法 理解文件共享与保密的机制 3 理解文件系统的实现过程 3 目录 5 1概述5 2文件目录5 3文件的组织结构5 4文件存储空间管理5 5文件的共享 保护与保密5 6文件系统的实现 4 5 1 1文件与文件系统5 1 2文件的分类 5 1概述 5 1 文件2 文件系统 5 1 1文件与文件系统 6 所谓 文件 是一组带标识的 在逻辑上有完整意义并存储于物理介质上的信息项的集合 文件的标识即为文件名 一个文件的文件名是在创建该文件时给出的 信息项构成了文件内容的基本单位 文件是一个抽象机制 它提供了一种把信息保存在介质上 而且便于以后存取的方法 用户不必关心操作系统管理文件的细节 1 文件 7 所谓 文件系统 是指与文件管理有关的那部分软件 被管理的文件以及管理所需要的数据结构 如目录 索引表等 的总体 2 文件系统 8 文件系统 的作用 从用户的角度来看 文件系统主要是实现 按名存取 对文件进行存取控制 负责管理 控制用户建立文件 读写文件 修改文件 复制文件和撤销文件等操作 从系统管理的角度来看 文件系统主要是实现文件存储空间的组织 分配以及文件的存储 检索 共享 保护等管理 2 文件系统 9 作为一个统一的文件管理机构 文件系统应具有下述功能 1 统一管理文件的存储空间 实施存储空间的分配和回收 2 实现文件从名字空间到辅存地址空间的映射 即实现文件的按名存取 以对用户透明的方式管理名字空间 3 实现文件信息的共享 并提供文件的保护和保密措施 2 文件系统 10 4 向用户提供一个方便使用的接口 提供面向文件系统的操作命令 以及提供对文件的操作命令 如信息存取 加工等 5 系统维护及向用户提供有关信息 6 保持文件系统的执行效率 文件系统在操作系统接口中占的比例最大 用户使用操作系统的感觉在很大程度上取决于对文件系统的使用效果 7 提供与I O的统一接口 2 文件系统 11 1 按文件的用途分类2 按文件的组织形式分类3 其他常见的几种分类方式 5 1 2文件的分类 12 通常按文件的用途把文件分为三类 1 系统文件操作系统和各种系统应用程序和数据所组成的文件 2 库函数文件标准子程序及常用应用程序组成的文件 3 用户文件用户文件是用户委托文件系统保存的文件 1 按文件的用途分类 13 通常按文件的组织形式把文件分为三类 1 普通文件普通文件主要是指 文件的组织是形式为文件系统中所规定的最一般格式的文件 例如由字符流组成的文件 普通文件既包括系统文件 也包括用户文件 库函数文件和用户使用程序文件等 2 目录文件目录文件是由文件的目录构成的特殊文件 3 特殊文件特殊文件在形式上与普通文件相同 也可进行查找目录等操作 2 按文件的组织形式分类 14 按照信息的保存期限可划分为 临时文件 即保存临时性信息的文件 永久性文件 其信息需要长期保存的文件 档案文件 即保存在作为 档案 用的磁盘上 以备查证和恢复时使用的文件 按照文件的保护方式可划分为 只读文件 读写文件 可执行文件等 按照文件的逻辑结构可划分为 流式文件 记录式文件等 3 其他常见的几种分类方式 15 按照文件的物理结构可划分为 顺序文件 连续文件 链接文件 索引文件等 按照文件的存取方式可划分为 顺序存取文件 随机存取文件等 以上种种文件系统的分类目的是 对不同文件进行管理 提高系统效率 3 其他常见的几种分类方式 16 5 2 1文件目录的组成5 2 2文件目录结构5 2 3文件目录操作 5 2文件目录 17 系统为每个文件设置一个描述性数据结构 文件控制块FCB FileControlBlock 文件目录就是文件控制块的有序集合 即把所有文件控制块有机地组织起来 就构成了文件目录 随系统的不同 一个文件的FCB中所包含的内容及大小不尽一样 5 2 1文件目录的组成 18 一般地 文件控制块中会包含如下的内容 1 基本信息 文件名 文件类型 文件组织 5 2 1文件目录的组成 19 一般地 文件控制块中会包含如下的内容 2 地址信息 起始地址文件存放在辅存的起始物理地址 例如 磁盘号 柱面号 磁道号或在磁盘上的块号 已使用大小文件的大小 以字节 字或块来衡量 分配大小文件的最大尺寸 5 2 1文件目录的组成 20 一般地 文件控制块中会包含如下的内容 3 存取控制信息 文件主拥有文件的控制权 访问控制可包括有权限用户的用户名和口令 允许的操作控制读 写 执行和在网上的传输等 5 2 1文件目录的组成 21 一般地 文件控制块中会包含如下的内容 4 使用信息 创建日期文件首次存放在目录中的时间 读时间最后一次读文件记录的时间 修改时间最后一次更新 插入或删除记录的时间 备份时间文件最后一次备份到其他存储介质的时间 5 2 1文件目录的组成 22 1 一级目录结构2 二级目录结构3 多级目录结构 5 2 2文件目录结构 23 在整个系统设置一张线性目录表 表中包括了所有文件的文件控制块 每个文件控制块都指向一个普通文件 如图5 1所示 这就是一级 单级 目录结构 存在的问题 不能重名 检索速度慢 1 一级目录结构 24 在二级目录结构中 目录被分为两级 第一级称为主文件目录 MainFileDirectory 简称MFD 给出了用户名和用户子目录所在的物理位置 第二级成为用户文件目录 UserFileDirectory 简称UFD 又称用户子目录 给出了该用户所有文件的FCB 这样 由MFD和UFD共同形成了二级目录 二级目录的结构如图5 2所示 2 二级目录结构 25 2 二级目录结构 26 把二级目录的层次关系加以推广 就形成了多级目录 又称树型目录 如图5 3所示 在多级层次目录中 有一个根目录和许多分目录 分目录不但可以包含文件 而且还可以包含下一级的分目录 这样依次推广下去就形成了多级层次目录 3 多级目录结构 27 3 多级目录结构 28 多级目录结构的优点是便于文件分类 且具有下列优点 1 层次清晰 2 解决了文件重名问题 3 查找搜索速度快 缺点 查找一个文件按路径名逐层检查 由于每个文件都放在辅存 多次访问磁盘影响速度 结构相对比较复杂 3 多级目录结构 29 几种常用的目录操作 1 创建目录 2 删除目录 3 检索目录 4 打开目录 5 关闭目录 5 2 3文件目录操作 30 目录实现的最简单的算法是线性表算法 每个表项由文件名和指向数据块的指针组成 当要搜索一个目录项时 可以采用线性搜索 这个算法实现简单 但运行很耗时 比如创建一个新的文件时 需要先搜索整个目录以确定没有同名文件存在 然后再在线性表的末尾添加一条新的目录项 1 线性表算法 31 采用哈希表 Hash 算法时 目录项信息存储在一个哈希表中 进行目录搜索时 首先根据文件名来计算一个哈希值 然后得到一个指向表中文件的指针 即搜索的时间消耗与目录项的数量无关 这样该算法就可以大幅度地减少目录搜索时间 插入和删除目录项都很简单 2 哈希表算法 32 哈希表的主要难点是选择合适的哈希表长度与适当的哈希函数 否则目录项冲突的情况增多 即两个文件名返回的哈希值一样的情形 搜索的效率又将退化为线性表算法时的效率 2 哈希表算法 33 B 树B 树数据结构是一种平衡树 对于存储在磁盘上的数据来说 平衡树是一种理想的分类组成方式 这是因为它可以使得查找一个数据项所需的磁盘访问次数减到最少 3 其他算法 34 3 其他算法 图5 6B 树组织文件的逻辑形式 35 由于使用B 树存储文件 文件按顺序排列 所以可以快速查找目录 并且可以快速返回已经排好序的文件名 同时 因为B 树是向宽度扩展而不是深度扩展 NTFS的目录检索时间不会随着目录的增大而增加 3 其他算法 36 5 3 1文件的逻辑结构5 3 2文件的物理结构5 3 3文件的存储 5 3文件的组织结构 37 所谓文件的逻辑结构就是从用户观点出发所见到的文件结构 文件分为流式文件和记录式文件两种 记录式又分为定长记录文件和不定长记录两种 5 3 1文件的逻辑结构 38 5 3 1文件的逻辑结构 39 文件的物理结构和组织是指逻辑文件在物理存储空间中的存放方法和组织关系 文件的存储结构涉及块的划分 记录的排列 索引的组织 信息的搜索等许多问题 有两类方法可用来构造文件的物理结构 计算法指针法 5 3 2文件的物理结构 40 计算法的存取效率较高 又不必增加存储空间存放附加控制信息 能把分布范围较广的键均匀地映射到一个存储区域中 指针法设置专门指针 指明相应记录的物理地址或表达各记录之间的关联 索引文件 索引顺序文件 连接文件 倒排文件等均属此类 5 3 2文件的物理结构 41 1 顺序结构2 链接结构3 索引结构 5 3 2文件的物理结构 42 顺序结构又称连续结构 这是一种最简单的文件物理结构 它把逻辑上连续的文件信息依次存放到辅存连续编号的物理块中 如果一个文件长n块 并从物理块号b开始存放 则该文件占据物理块号b b 1 b 2 b n 1 如图5 8所示 1 顺序结构 43 1 顺序结构 图5 8文件的顺序结构 44 顺序结构的优缺点顺序结构的好处是文件存取非常简单迅速 支持顺序存取和随机存取 顺序结构的缺点在于 文件不能动态增长 另外 随着文件不停地被分配和被删除 空闲空间逐渐被分割为很小的碎片 1 顺序结构 45 链接结构的文件将逻辑上连续的文件分散存放在若干不连续的物理块中 每个物理块都设有一个指针 指向其后续的物理块 2 链接结构 46 图5 9文件链接结构 47 链接结构的优缺点链接结构的好处是存储碎片问题迎刃而解了 有利于文件动态扩充 有利于文件插入和删除 提高了磁盘空间利用率 链接分配算法的主要缺点是 存取速度慢 不适于随机存取 磁头移动多 效率相对较低 存在可靠性问题 如指针出错等问题 链接指针要占用一定的空间 2 链接结构 48 1 索引结构的原理如果把每个磁盘块的指针字取出 放在主存的表或索引中 就构成文件的第三种物理结构 即索引结构 3 索引结构 49 3 索引结构 图5 10索引文件结构 50 2 索引文件结构的优缺点索引文件结构保持了链接结构的优点 又解决了其缺点 其优点表现为 索引结构文件既适于顺序存取 也适用于随机存取 索引文件可以满足文件动态增长的要求 也满足了文件插入 删除的要求 索引文件还能充分利用辅存空间 3 索引结构 51 2 索引文件结构的优缺点索引结构也存在一些缺点 比如较多的寻道次数和寻道时间 以及索引表本身增加了存储空间的开销等 显然 如果文件很大 它的文件索引表也就较大 如果索引表的大小超过了一个物理块 那么必须决定索引表的物理存放方式 3 索引结构 52 1 顺序存取存储设备2 直接存取存储设备 5 3 3文件的存储 53 块是存储介质上连续信息所组成的一个区域 也叫做物理记录 块是主存储器和辅助存储设备进行信息交换的物理单位 每次总是交换一块或多块信息 决定块的大小要考虑到用户使用方式 数据传输效率和存储设备类型等多种因素 5 3 3文件的存储 54 顺序存取存储设备是严格依赖信息的物理位置进行定位和读写的存储设备 所以 从存取一个信息块到存取另一个信息块要花费较多的时间 1 顺序存取存储设备 55 磁盘是一种直接存取存储设备 又叫随机存取存储设备 它的每个物理记录有确定的位置和唯一的地址 存取任何一个物理块所需的时间几乎不依赖于此信息的位置 2 直接存取存储设备 56 5 4 1空闲区表法5 4 2空闲块链法5 4 3位图法 5 4文件存储空间管理 57 磁盘上连续的空闲盘块组成一个 空闲区 系统为磁盘上所有的空闲区建立一张 空闲区表 每个空闲区对应一个表项 每个表项应说明它的序号 包括的空闲块个数 第一个空闲块的块号等信息 再将所有空闲区按其起始块号递增的次序排列 如表5 2所示 5 4 1空闲区表法 58 5 4 1空闲区表法 表5 2空闲区表 59 所谓空闲块链 就是将文件存储空间中所有空闲块顺序链接在一起 形成一个链表 链表中的每一结点记录一个空闲块的物理块号 同时记录下一空闲块的指针 这个由空闲块组成的链表称为 空闲块链表 使用这种管理方法 只要给出链首地址 就能查找到文件存储空间中所有的空闲块 5 4 2空闲块链表法 60 系统划出若干字节 为每个文件存储设备建立一张位图 位图中的一个位 bit 对应文件存储空间的一个物理块 若该位为1 表示对应的块被占用 若该位为0 表示对应物理块空闲 在进行存储空间的分配和回收时 只需要找到位图中相应的位 将0改为1 分配 或将1改为0 回收 即可 5 4 3位图法 61 采用空闲区表法和空闲块链法进行存储空间的分配和回收 都需在文件存储区中查找空闲区表项或链接块号 必须启动外设通过I O才能完成 采用位图法 由于位图占用空间很少 因而可将