操作系统 第12章 文件管理

112.1概述12.1.1文件和文件系统文件由文件名字标识的一组信息的集合。文件系统文件系统是操作系统中负责存取和管理信息的模块，它用统一的方式管理用户和系统信息的存储、检索、更新、共享和保护，并为用户提供一整套方便有效的文件使用和操作方法。2文件的理想属性长期存在进程间可共享结构文件系统提供的对文件的典型操作创建删除打开关闭读写312.1.2文件结构域基本数据单元。记录一组相关的域的集合。文件一组相似记录的集合。数据库一组相关的数据的集合。412.1.3文件管理系统文件管理系统是一组系统软件，为使用文件的用户和应用程序提供服务。一个文件管理系统需要满足以下目标：满足数据管理的要求和用户的需求，包括存储数据和执行上述操作的能力。最大限度地保证文件中的数据有效。优化性能，包括总体吞吐量和响应时间。为各种类型的存储设备提供I/O支持。减少或消除丢失或破坏数据的可能性。向用户进程提供标准I/O接口例程集。在多用户系统中为多个用户提供I/O支持。5文件系统架构堆顺序索引顺序索引散列逻辑I/O基本I/O管理程序基本文件系统磁盘设备驱动磁带设备驱动用户程序612.2文件组织和访问文件组织指文件记录中的逻辑结构，由用户访问文件的方式确定。文件在辅存中的物理组织取决于分块策略和文件分配策略。基本文件组织方式：堆顺序文件索引顺序文件索引文件直接或散列文件712.2.1堆数据按到达的顺序被收集，没有结构，对记录的访问通过穷举查找的方式进行。适用场合：当数据在处理前采集并存储时，或者当数据难以组织时。当保存的数据大小和结构不同时，堆文件空间使用情况良好，能较好地用于穷举查找，且易于修改。对大多数应用都不适应。812.2.2顺序文件每条记录都使用一种固定的格式，所有记录都具有相同的长度，并且由相同数目、长度固定的域按特定的顺序组成。通常用于批处理应用中，如果涉及对所有记录的处理，通常是最佳的。唯一可以很容易地存储在磁盘和磁带中的文件组织。对于查询或更新记录的交互式应用，性能很差。912.2.3索引顺序文件保留顺序文件的关键特征：记录按照关键域的顺序组织。增加了两个特征：文件索引溢出文件极大地减少了访问单条记录的时间，同时保留了文件的顺序特性。1012.2.4索引文件摒弃顺序性和关键字的概念，只能通过索引来访问记录。对记录的放置位置没有限制。大多用于对信息的及时性要求比较严格且很少会对所有数据进行处理的应用程序中。1112.2.5直接文件或散列文件使用基于关键字的散列，能直接访问磁盘中任何一个地址已知的块。通常在要求快速访问时使用，并且记录的长度是固定的，一次只访问一条记录。1212.3B树B树是具有以下特征的一种树状结构：一个包含若干节点和叶子的树；每个节点至少包含一个用来唯一标识文件记录的关键码，并且包含多于一个的指向子节点或叶子的指针。一个节点包含的关键码和指针的数目是可变的，相关限制如下：每个节点的关键码数量不能超过一个特定的最大值；每个节点的关键码按照非减次序来存储。每个关键码对应一个子节点，以该子节点为根的子树包含所有关键码均小于等于当前的关键码并且大于前一个关键码的节点。一个节点包含一个额外的最右子节点，以该节点为根的子树所包含的所有关键码，都大于该节点包含的任意关键码。最小度数为d的B树要满足的性质每个节点最多有2d-1个关键码和2d个子女。除根节点外，每个节点都至少有d-1个关键码和d个指针。根节点最少有1个关键码和2个子女。所有的叶子都在同一层，不包含任何信息。一个包含k个指针的非叶子节点有k-1个关键码。13插入一个新的关键码1.在树中搜索这个关键码。如果该关键码不在树中，那么会到达最底层的一个节点。2.如果这个节点的关键码少于2d-1，那么把新的关键码按照适当的顺序插入该节点。3.如果这个节点是满的（包含2d-1个关键码），那么以这个节点的中间的关键码为界把该节点分裂为两个新的节点，每个新节点都包含d-1个关键码，并且把中间的关键码提升到上一层，提升过程见步骤4。如果新的关键码的值小于中间的关键码，则把它插入左边的新节点，否则插入右边的新节点。144.提升的节点按步骤3的规则插入到父节点中。因此，如果父节点已满，它必须被分裂，并且它的中间的关键码被提升到上一层。5.如果提升的过程到达了根节点并且根节点是满的，那么按步骤3的规则插入。这样，中间的关键码变成了一个新的根节点并且树的高度增加1151623516171738588963032394344525960210676823516171738588909630323943445259602106768a.最小度数d=3的B树b.插入关键码key=9017c.插入关键码key=457385889096525960210676823395161713032434445525960210676830324344455123396171887384859096d.插入关键码key=841812.4文件目录12.4.1内容基本信息文件名文件类型文件组织地址信息卷起始地址使用大小分配大小19访问控制信息所有者访问信息许可的行为使用信息数据创建创建者身份最后一次读访问的日期最后一次读用户的身份最后一次修改的日期最后一次修改者的身份最后一次备份的日期当前使用2012.4.2结构层次或树型结构是普遍采用的一种方法。2112.4.3命名文件命名唯一性问题路径名工作目录2212.5文件共享访问权限无知道执行读追加更新改变保护删除同时访问加锁互斥和死锁问题2312.6记录组块1、需考虑的问题：块的长度是固定的还是可变的？大多数系统中，块是固定长度的。与记录的平均大小相比，块的相对大小是多少？综合考虑顺序访问的频率和访问的局部性潜能，倾向于用大的块，以减少I/O传送时间。2、记录组块的方法固定组块可变长度跨越式组块可变长度非跨越式组块24252612.7辅助存储管理12.7.1文件分配文件分配涉及到的问题：当创建一个新文件时，是否一次性地分配所需要的最大空间？预分配与动态分配在分配文件时，分区的大小应该是多少？可变的大规模连续分区块为跟踪分配给文件的分区，应该使用哪种数据结构或表？文件分配表271、预分配与动态分配预分配策略要求在发出创建文件的请求时，声明该文件的最大大小。若不能可靠地估计文件可能的最大大小，通常会多估计一些，以避免分配的空间不够。——浪费动态分配只有在需要时才给文件分配空间。282、分区大小选择一个分区大小时，需要折中考虑单个文件的效率和整个系统的效率。邻近空间可以提高性能；数目较多的小分区会增加用于管理分配信息表的大小；使用固定大小的分区可以简化空间的再分配；使用可变大小的分区或固定大小的小分区，可以减少由于超额分配而产生的未使用存储空间的浪费。综合考虑的两种选择：可变的大规模连续分区大小可变避免了浪费，文件分配表比较小空间很难再次利用块小的固定分区提供了更多的灵活性可能需要较大的表或更复杂的结构293、文件的分配方法—（1）连续分配30（2）链接分配31（3）索引分配3212.7.2空闲空间的管理磁盘分配表常用的空闲空间管理技术位表链接空闲区索引空闲块列表卷一组在辅助存储上可寻址的扇区的集合，操作系统或应用程序用卷来进行数据存储。一个卷中的扇区在物理存储设备上不需要是连续的，只需要对操作系统或应用程序来讲是连续的。一个卷可能是更小的卷合并或组合后的结果。3312.8文件系统安全访问矩阵主体对象访问权限3412.9UNIX文件管理UNIX区分六种类型的文件普通文件目录文件特殊文件命名管道链接文件符号链接35文件名14Bi-node#2B…………mytest.c56…………目录文件的内容…………存取权限，大小，文件主，建立/修改日期，磁盘地址等56文件属性i-node#磁盘上的i-node表64B12.9.1索引节点36思考：UNIX使用i-node的好处是什么？因为按文件名检索目录文件时，只用到了文件名。当找到该文件名时，才需要它的其它描述信息。所以在把存放该目录文件的盘块从外存调入内存进行比较时，应使一个盘块中包含尽量多的文件名，以减少启动磁盘次数，加快按名存取的速度。所以引入索引节点。例：设物理块大小为512B，某目录下有128个文件。原来的FCB占64B，则每物理块能容纳512/64=8个FCB，则该目录文件需占128/8=16块，查找一个文件的平均访盘次数为：（1+16）/2=8.5次。采用i-node后：文件名部分有16B，i-node部分有64B，每物理块能容纳512/16=32个文件名部分或512/64=8个i-node，则该目录的文件名部分需占128/32=4块，i-node部分需占128/8=16块。查找一个文件的平均访盘次数为：（1+4）/2+1=3.5次。3701234567891011120…127…0…1270…1270…127…………0…1270…1270…127…0…1270…127…0…1270…127…………………………12.9.2文件分配38如果块长4KB（即索引块和数据块长4K），每个指针（盘块号）4B，则采用这种索引分配时，允许的文件最大尺寸是多少？4KB×（4KB/4B）=4MB3912.9.3目录树型目录12.9.4卷结构一个UNIX文件系统驻留在一个单一逻辑磁盘或磁盘分区上，包含以下元素：引导块超级块索引节点表数据块40三种访问模式：read、write、execute三类用户：RWXa)owneraccess7111（文件主）b)groupaccess6110（同组用户）c)publicaccess5101（其他用户）12.9.5-12.9.6UNIX文件访问控制41作业复习题12.11习题12.3