操作系统课件.ppt

二 链接分配 链接文件 2 显式链接 所有链接指针统一存放在一张显式的链接表 fat表 文件分配表 中 每个FAT表项对应于磁盘数据区的一个盘块 数据区簇号 介质类型 磁盘 2 显式链接 若文件f1占据了2 4 5 1四个盘块 MS DOS的文件物理结构 6 EOF 11 10 5 EOF 0 1 2 3 4 5 6 7 8 9 FAT FCBA 4 FCBB 9 10 11 A B 物理块号 文件A占据了4 6 11三个盘块 文件B占据了9 10 5三个盘块 2 显式链接 FAT的大小表项数目 磁盘数据区盘块数 表项长度 保证能存放下最大的盘块号 为了方便检索 FAT表项长度扩充为半个字节的整数倍 如1 2MB的软盘 盘块大小为512B 则 盘块数为 2 4K个FAT表项长度为 12位 即1 5B FAT占3 6KB存储空间 显式链接分配的优缺点 去除了隐式链接结构的两个缺点 不支持高效的随机存取 如 大文件的随机存取 FAT文件系统 FAT12 FAT16 FAT32 FAT12 每个FAT表项占12位 项数2 12 4K项 即每个卷最多4K簇 若每簇512B 则一个文件卷 2MB空间 一个物理磁盘可分为4个分区 所以物理盘最大为8MB 若每簇为8个扇区 则物理盘最大可达64MB 簇越大 则能支持更大的磁盘容量 但因簇内碎片而造成的浪费也随之增加 FAT16 每个FAT表项占16位 项数2 16 64K项 即每个卷最多64K簇 簇大小2KB到32KB 一个文件卷最大可达 216X32KB 2GB FAT文件系统 FAT12 FAT16 FAT32 FAT32 每个FAT表项占32位 FAT表项的高4位保留不用 因此每个文件卷最多有268 435 445个簇 簇的大小最大为32K 每个文件卷必须包含至少65 527簇 FAT32文件系统最大支持32GB的文件卷 根目录文件夹位于数据区 根目录下子目录和文件的数量限制不复存在 FAT16 FAT32簇大小比较 FAT32比FAT16支持更小的簇和更大的磁盘容量 减少了磁盘空间的浪费 FAT文件系统磁盘组织结构 FAT32引导区主要内容 每扇区字节数 通常512B每簇扇区数 FAT1的位置 磁盘分区大小 扇区数 FAT表大小 扇区数 根目录位置 引导区备份扇区的位置 文件系统类型 Fat32数据区 链接文件性能评价 1 存储空间利用率高 2 文件创建时用户不必指出文件的大小 3 文件动态扩充和修改容易 4 顺序存取效率较高 随机存取效率较低 1 什么是索引文件索引表 系统为每个文件建立的逻辑块号与物理块号的对照表 索引块 存放文件的索引表的物理块 其块号保存在文件FCB的物理地址中 物理文件由数据文件和索引表构成 这种物理文件称为索引文件 三 索引分配 索引文件 2 单级索引分配 三 索引分配 索引文件 文件file1分配到4个磁盘块 14 15 30 40 索引表超过1块时 连续存放 隐式链接 多级索引等 2 单级索引分配 三 索引分配 索引文件 单级索引方式优缺点 采用离散分配 消除文件存储空间的外部碎片 随机存取效率高 索引表需占大量文件盘空间 尤其是常用的中小型文件 浪费严重 3 多级索引分配 文件file2分配到1000个磁盘块 2 3 5 20 22 25 1200 1511 若每个盘块号占4B 每个盘块1KB 4 混合索引分配 Unix系统中 i节点中有13个物理地址项i addr 13 i addr 0 i addr 9 直接地址 i addr 10 一次间接地址 i addr 11 二次间接地址 i addr 12 三次间接地址 假设盘块大小为4KB 每个盘块号占4B 则 一个磁盘块中能存放1K个磁盘块块号 a1034 a10 a1 4 混合索引分配 i节点 逻辑文件 物理块号 a0 a9 a1033 d c0 b0 a2057 a2058 a3081 直接地址 一次间址块 二次间址块 三次间址块 a1034 a10 a1 4 混合索引分配 i节点 逻辑文件 物理块号 a0 a9 a1033 d c0 b0 a2057 a2058 a3081 直接地址 二次间接地址 三次间接地址 一次间接地址 文件的前10个物理块号直接存放到文件i结点的前10个物理地址项i addr 0 i addr 9 中 这10个物理地址项因此叫做直接地址 文件的其余全部物理块号 除前10个外 依次登记到若干个一级索引盘块中 首个一级索引盘块的物理块号登记在文件i结点的第10个物理地址i addr 10 中 因此这个物理地址项被叫做一次间址项 其余的一级索引盘块的物理块号则依次登记到若干个二级索引盘块中 首个二级索引盘块的物理块号登记在文件i结点的第11个物理地址i addr 11 中 因此这个物理地址项被叫做二次间址项 其余的二级索引盘块的物理块号则依次登记到1个三级索引盘块中而该三级索引盘块的物理块号则登记在文件i结点的第12个物理地址i addr 12 中 因此这个物理地址项被叫做三次间址项 4 混合索引分配 data 10个数据块 i节点 data data data 假设某个文件总共需要n个磁盘块 则 1 当n 10时 所有数据盘块块号全部依次存放在i addr 0 i addr 9 中 4 混合索引分配 2 当10 n 10 1024时 前面10个数据盘块号全部存放在i addr 0 i addr 9 中 i addr 12 i addr 11 i addr 10 i addr 9 i addr 8 i addr 1 i addr 0 i节点 4 混合索引分配 2 10 n 1034 剩下的不超过1024个数据块号放在一个一级索引块 即一次间址块 中 并将该一次间址块块号存入i addr 10 中 4 混合索引分配 2 10 n 1034 总结 i addr 12 i addr 11 i addr 10 i addr 9 i addr 8 i addr 1 i addr 0 i节点 一次间址块 4 混合索引分配 3 当1034 n 10 1024 1M时 前面10个数据块号全部存放在i addr 0 i addr 9 中 i addr 12 i addr 11 i addr 10 i addr 9 i addr 8 i addr 1 i addr 0 i节点 4 混合索引分配 3 1034 n 1034 1M 剩下的不超过1024 1M个数据块号放在不超过1025个一次间址块 1024个 1024个 不超过1025个 4 混合索引分配 3 1034 n 1034 1M 将第一个一次间址块块号存入i addr 10 中 将剩下的不超过1024个一次间址块块号存入一个二级索引块 二次间址块 中 并将该二次间址块块号存入i addr 11 中 4 混合索引分配 3 1034 n 1034 1M 总结 i addr 12 i addr 11 i addr 10 i addr 9 i addr 8 i addr 1 i addr 0 i节点 4 混合索引分配 3 1034 1M n 1034 1M 1G 前面10个数据块号全部存放在i addr 0 i addr 9 中 i addr 12 i addr 11 i addr 10 i addr 9 i addr 8 i addr 1 i addr 0 i节点 4 混合索引分配 3 1034 1M n 1034 1M 1G 剩下的不超过1024 1M 1G个数据块号放在不超过1025 1M个一次间址块中 1024个 1024个 4 混合索引分配 3 1034 1M n 1034 1M 1G 将第一个一次间址块块号存入i addr 10 中 剩下的不超过1024 1M个一次间址块块号存入 1025个二次间址块中 1025 1M个 i addr 12 i addr 11 i addr 10 i addr 9 i addr 8 i addr 1 i addr 0 i节点 4 混合索引分配 3 1034 1M n 1034 1M 1G 再将第一个二次间址块存入i addr 11 中 剩下的不超过1024个二次间址块号存入一个三次间址块中 最后将该三次间址块块号存入i addr 12 中 二次间址块 1025个 4 混合索引分配 3 1034 1M n 1034 1M 1G 总结 四 文件物理结构的比较 顺序文件的优点是不需要额外的空间开销 只要在文件目录中指出文件的大小和首块的块号即可 对顺序的访问效率很高 适应于顺序存取且文件不经常修改的情况 缺点是动态地增长和缩小系统开销很大 文件创建时要求用户提供文件的大小 存储空间浪费较大 链接文件克服了连续文件的不足之处 但文件的随机访问系统开销较大 适应于顺序访问的文件 索引文件既适应于顺序存访问 也适应于随机访问 是一种比较好的文件物理结构 但要有用于索引表的空间开销和文件索引的时间开销 UNIX系统是使用索引结构成功的例子 西安电子科技大学2002 多选题1 文件的物理结构一般有 A连续文件B流式文件C记录式文件D串联文件E索引文件答案 ADE 西安电子科技大学2002 多选题2 连续结构的文件适合采用 存取方法A顺序存取B直接存取C按键存取D分区存取E以上均不对答案 AB 华中科技大学2000年 某文件系统采用单级索引文件结构 假定文件索引表的每个表项占3个字节 即用3个字节存放一个磁盘块的块号 每个磁盘块的大小为512B 试问 1 该文件系统能支持的最大文件大小是多少字节 能管理的最大磁盘空间是多大 2 若采用2级或3级索引 该文件系统能支持的最大文件大小是多少字节 能管理的最大磁盘空间是多大 分析 1 由于索引表占用一个大小为512B的磁盘 所以该文件系统的索引表可以管理512 3 170个表项 而每一个表项对应一个物理块 因此该文件系统可以支持的最大文件为 170 512B 87040B 85K能管理的最大磁盘空间 224 512B2 若采用二级索引 则是 170 170 512B 7225KB3 若采用三级索引 则是 170 170 170 512B 2456500KB 2398 93M 例 混合索引分配方式 FCB中13个地址项 第0 9个地址项为直接地址 第10个地址项为一次间接地址 第11个地址项为二次间接地址 第12个地址项为三次间接地址 盘块大小为512字节 盘块号需要3个字节来描述 每个盘块最多存放170个盘块地址 问 1 该文件系统允许文件的最大长度是多少 2 将文件的字节偏移量5000 15000 85000转换为物理块号和块内偏移量 3 假设某个文件的FCB已在内存 但其他信息均在外存 为了访问文件中某个位置的内容 最少需要几次访问磁盘 最多需要几次访问磁盘 解答 1 通过直接地址可访问到10个数据块 通过一次间址还可再访问到170个数据块 通过二次间址还可再访问到1702个数据块 通过三次间址还可再访问到1703个数据块 所以文件的最大长度可达 10 170 1702 1703 4942080块 2 5000 512 9 392字节偏移量5000的逻辑块号为9 块内偏移量为392B由于9 10 故 可直接从FCB的第9个地址项处得到逻辑块9对应的物理盘块号 块内偏移量仍为392B 2 15000 512 29 152字节偏移量15000的逻辑块号为29 块内偏移量为152B由于10 29 10 170 而29 10 19 故 可从FCB的第10个地址项 即一次间址项中得到一次间址块的地址 并将它读入内存 再从一次间址块的第19项 即该块的第57 59这三个字节 中获得逻辑块29对应的物理盘块号 块内偏移量仍为152B 2 150000 512 292 496字节偏移量150000的逻辑块号为292 块内偏移为496B由于10 170 292 10 170 170 170292 10 170 112112 170 0 112故需要 从FCB的第11个地址项中得到二次间址块的地址 并将该二次间址块读入内存 再从该二次间址块的第0项中获得一个一次间址块的地址 并把该一次间址块读入内存 再从该一次间址块的第112项中获得逻辑块292对应的物理盘块号 块内偏移量为496 3 由于文件的FCB已在内存 为了访问文件中某个位置的内容 最少需要1次访问磁盘即可从内存的FCB中直接获得一个直接地址 然后去访问对应的文件数据盘块 最多需要4次访问磁盘第1次是读三次间址块 第2次是读二次间址块 第3次是读一次间址块 第4次是访问文件的数据盘块 6 4目录管理 对目录管理的要求如下 实现 按名存取 2 提高对目录的检索速度 3 文件共享 4 允许文件重名 文件系统最基本的目标 文件控制块 FCB 文件控制块是OS用来存放描述文件 管理文件的文件属性信息的数据结构 文件 FCB 文件内容文件与FCB一一对应FCB是文件存在的唯一标志 一 文件控制块和索引结点 文件控制块 FCB FCB中应包含的内容 基本信息类 文件名 文件物理地址和文件的长度 顺序文件链接文件索引文件 起始磁盘块号 单级索引多级索引混合索引 索引块块号 最高级索引块块号 直接地址 一次间址 二次间址等 字节数或盘块数 一 文件控制块和索引结点 文件控制块 FCB FCB中应包含的内容 基本信息类 文件逻辑结构 文件主标识符和组标识符 文件物理结构 一 文件控制块和索引结点 一 文件控制块和索引结点 文件控制块 FCB 2 存取控制信息类文件主的权限 核准用户的权限 一般用户的权限 3 使用信息类 文件建立日期及时间 文件最近访问日期及时间 文件最近修改日期及时间 文件链接计数 FCB跟文件内容一样存放在文件存储器中 当文件打开时 FCB的内容被读入内存 FCB的实现方式 一个FCB就是一个目录项 目录项的有序集合形成文件目录 如MS DOS 将FCB拆分成文件名和索引结点两部分 如UNIX 一 文件控制块和索引结点 磁盘 如 3 5寸双面双密度软盘80磁道 面18扇区 道512字节 扇区1扇区 簇它的盘空间分配情况如下 又如 360KB的软盘 根目录区为 个扇区 里面可存放112个目录项 FCB 举例 MS DOS 磁盘布局 文件名首字节 00h 从未用过的目录项 E5h 已删除文件的目录项 05H 实际该字节为的值为E5H 2Eh 子目录标记项 其他 文件 子目录名的首字节 举例 MS DOS 文件控制块DOS的FCB就是目录项 每个FCB占32B 一 文件控制块和索引结点 属性 文件名 扩展名 属性 保留 时间 日期 起始簇号 文件长度 8B 4B 2B 2B 2B 10B 1B 3B 一 文件控制块和索引结点 举例 MS DOS 文件控制块 文件名 扩展名 属性 保留 时间 日期 起始块号 文件长度 8B 4B 2B 2B 2B 10B 1B 3B 时间 最近修改时间 一 文件控制块和索引结点 举例 MS DOS 文件控制块 文件名 扩展名 属性 保留 时间 日期 起始块号 文件长度 8B 4B 2B 2B 2B 10B 1B 3B 日期 最近修改日期 一 文件控制块和索引结点 举例 MS DOS 文件控制块 2 索引结点 i节点 1 索引结点的引入 假设 某个目录中有640个目录项64B FCB1kB 磁盘块若采用一个FCB就是一个目录项的方式 则 16个目录项 磁盘块上述目录文件需要40个磁盘块在该目录中检索一个文件平均需要启动磁盘20次 2 索引结点 i节点 1 索引结点的引入 i节点 目录项 1 i结点 2 i结点 3 i结点 UNIX文件卷布局 上