操作系统文件管理OS第六章(2)

文件管理OperatingSystem22020/2/126.3外存分配方式连续分配1链式分配2索引分配332020/2/12外存分配外存分配时需要考虑外存利用率和文件访问速度文件的物理结构与外存分配方式相关，不同物理结构的文件对同样的逻辑文件内容在外存中存放的方式和组织关系是不同的连续分配：形成顺序文件结构链接分配：形成链式文件结构索引分配：形成索引文件结构注意文件逻辑结构和物理结构间的映射关系42020/2/12连续分配（顺序文件）逻辑文件中的纪录被顺序地存储到邻接的各物理盘块中逻辑文件中的纪录顺序和存储器中所占用盘块顺序一致52020/2/12连续分配（顺序文件）012345678910111213141516171819202122232425262728293031filestartLengthcount02tr143mail196list284f62counttrmaillistf62020/2/12连续分配优点实现简单，顺序访问容易支持直接存取和随机存取寻道次数少、寻道时间短缺点外存碎片较多，且紧凑费时需要事先知道文件长度，不利于文件动态增长，外存利用率难以保证删除和插入较困难72020/2/12链式分配（链式文件）通过在每个盘块上的链接指针将同属于一个文件的多个离散的盘块链接成一个链表，分为显式和隐式两种优点消除外碎片，提高内存利用率支持文件动态增长对文件增删方便82020/2/12隐式链接文件目录的各目录项中都含有指向链式文件第一个盘块和最后一个盘块的指针；每个盘块中都含有一个指向后继盘块的指针eg：若每个盘块占用1KB空间，后继盘块指针长度为32bit，则一个占据了4个盘块的隐式链式文件最多可容纳的字节数为多少？4*(1024-4)＝4080B92020/2/12隐式链接分配01012345678169251011121314151161718192021222324-125262728293031filestartendjeep925102020/2/12隐式链接优点适合顺序访问缺点对随机访问极为低效：无论所需盘块离首盘块距离多远都要从首盘块开始进行磁盘启动断链现象可能性较高：链中一个指针的问题会导致整个链断开改进使用“簇”为单位进行分配和链的管理优点：减小指针所占用存储空间、提高检索速度缺点：内碎片问题112020/2/12显式链接把用于链接文件各物理块的指针显式地放在内存的一张链接表（文件分配表FAT）中各磁盘仅拥有一张链接表，该表按照物理盘块号排序，每个表项中均存放有后继盘块的链接指针各文件的FCB中将其占用的首盘块号填入“物理地址”字段优点查找纪录的过程在内存进行检索速度高磁盘访问次数少122020/2/12显式链接2FCBEOF451012345外存内存FAT132020/2/12显式链接（MS－DOS的文件物理结构）4FCBA9FCBB6EOF11105EOF01234567891011N142020/2/12显式链接链接文件虽然避免了连续分配方式对连续空间的需求，但出现了其他问题不支持高效的直接存取：需要在FAT中顺序查找盘块号FAT占用内存空间较大：文件占用的盘块号分散在FAT中，使用时需要将FAT全部调入才能保证文件所有盘块可被找到152020/2/12单级索引分配创建文件时，将每个文件占用的盘块编号放在一个索引块中，在文件的目录项中记录指向该索引块的指针打开文件时，只需把该文件的索引块调入内存即可162020/2/12单级索引分配优点支持直接访问不会产生外碎片对大文件的存取支持较佳缺点需要花费较多外存空间：对小文件而言，索引块本身占用的空间比例较高，且其利用率极低172020/2/12多级索引分配为索引块本身再设置多层索引，形成多级索引方式eg：若每个盘块大小为4KB，每个盘块号占4字节，则在一个索引块中可以存放1K个盘块号，一级索引时，每个文件最大为1K*4KB二级索引时，每个文件最大为1K*1K*4KB182020/2/12两级索引分配360740……105106254…356357………………主索引二级索引360740012105106254356357磁盘空间192020/2/12混合索引分配方式将多种索引分配方式相结合而形成的一种分配方式eg：UNIX系统中采用直接地址、一级索引、二级索引和三级索引相结合的分配方式UNIX的索引结点中共设有13个地址项iaddr(0)~iaddr(12)，所有的地址被分为直接地址和间接地址۩直接地址：iaddr(0)~iaddr(9)，前10个地址项中分别存放某文件各物理盘块号，小于40KB的文件可以通过它们直接实现数据存取۩一次间接地址：iaddr(10)，一级索引分配方式，使用一次间址块实现对文件所占用的多个盘块的索引（最大4MB）۩多次间接地址：iaddr(11)指向二次间址块，记录所有一次间址块盘号（最大4GB）；iaddr(12)指向三次间址块，记录所有二次间址盘块号（最大4TB）202020/2/12混合索引方式modeowners(2)timestamps(3)sizeblockcounti.addr(0)i.addr(1)…i.addr(9)singleindirectdoubleindirecttripleindirect索引结点datadatadatadatadata............datadatadatadata直接地址间接地址212020/2/126.4目录管理FCB与i-node1目录结构2目录查询技术3222020/2/12目录用于标识系统中文件及其物理地址、以便检索使用的数据结构文件目录帮助用户以逻辑关系对文件实施有效管理实现按名存取：目录管理的基本功能，以文件名定位数据在外存的存储地址提高对目录的检索速度：大中型系统中通常设置较合理的目录结构提高目录乃至文件的检索速度文件共享：多用户共享一个文件时只在外存保留一份副本，以节省空间，提高文件利用率提供文件重名功能：支持不同用户对不同文件使用相同名字，满足用户操作习惯232020/2/12FCB为保证对文件的正确存取而为其配备的用于描述和控制文件的数据结构文件与FCB一一对应，FCB的集合称为目录文件或文件目录，即文件目录中的每个项就是一个FCB242020/2/12FCBFCB的组成基本信息۩文件名：唯一标识一个文件的字符串۩文件物理地址：文件在外存上的存储位置，包括设备名、起始盘块号、文件长度۩文件逻辑结构：流式或纪录式、纪录数۩文件物理结构：顺序结构、链式结构、索引结构存取控制信息۩文件拥有者、同组用户、一般用户的存取权限使用信息۩文件建立时间、上次修改时间、当前使用信息（连接数、修改与否等）根据OS自身的功能需求不同，FCB的组成也有所变化252020/2/12FCB（MS-DOS）文件名扩展名属性备用时间日期首块号盘块数262020/2/12i-node检索文件时仅使用文件名即可定位相应目录项、得到文件物理地址，因此可以将文件名与文件描述信息分开存放，后者形成索引结点，前者与指向索引结点的指针共同构成文件目录中的目录项意义检索占用大量盘块的大型文件目录时，无需多次启动磁盘就能找到所需数据文件的目录项文件名和索引结点指针组成的目录项占用空间小，检索速度快且比较次数少272020/2/12i-node磁盘索引结点磁盘上各文件的所对应的唯一索引结点组成۩用户、群组和他人标识۩文件类型说明：常规文件、目录文件、设备文件等۩各类用户存取权限۩文件物理地址۩文件长度۩文件连接计数：本FS中指向本文件的文件名指针总数۩文件存取时间：文件和文件的索引结点最近被修改的时间等۩eg：UNIX系统中，磁盘索引节点以静态形式存在于磁盘上，内核把它们读进内存索引节点表中以使用它们282020/2/12UNIXi-nodeUNIX的磁盘索引节点主要由如下字段组成文件所有者标识：所有权定义了对一个文件具有存取权的用户集合，分为个体所有与“用户组”所有文件类型文件存取许可权：系统按文件所有者、文件的用户组所有者及其它组用户三个类别对文件进行保护。每类都可以分别设置其读、写和执行此文件的权限文件存取时间文件连接数目：表示在本目录树（本分区）中有多少个文件名指向此文件文件数据的磁盘地址明细表：虽然用户们把文件中的数据在逻辑上作为字节流来看，但是系统把这些数据保存在不连接的磁盘块上。索引节点标出了包括有文件数据的磁盘块文件长度292020/2/12i-node内存索引结点文件被open时，需要将磁盘索引结点copy到内存索引结点中内存索引结点可以用来映射多种不同FS的磁盘索引结点，其中增加了以下内容۩索引结点编号：内存索引结点的唯一标识۩状态：i-node是否上锁或修改۩访问计数：内存中正在访问此进程的总数۩文件所属FS的逻辑设备号۩链接指针：指向空闲链表和散列队列的指针302020/2/12目录结构文件目录的组织形式，其性能优良与否影响文件系统存取速度单级目录结构两级目录结构多级目录结构312020/2/12单级目录结构整个FS只建立一张线性目录表，每个文件对应其中一个目录项文件名物理地址文件说明状态位shadowpasswd…特点结构简单查找速度慢文件不允许重名不便于文件共享只适用于单用户环境322020/2/12两级目录在根目录（主目录）下，为每个用户建立一个用户目录（UFD）为改变一级目录结构中的目录命名冲突，并提高对目录文件检索速度而改进目录分为两级：一级称为主文件目录MFD（MasterFileDirectory），其各目录项保存用户名和指向该用户文件目录的指针；二级称为用户文件目录UFD(UserFileDirectory)），给出该用户所有文件的FCB332020/2/12两级目录用户名用户子目录指针TommyAnnMary…AlphatestTommy根目录laughtestAnn根目录cryGODMary根目录342020/2/12两级目录使用方法用户注册时提出UFD申请，系统为其建立用户文件目录；反之，用户不再需要UFD时，系统为其撤销用户的大部分文件操作在自己的UFD范围内完成：创建时不跟自身文件重名即可；删除时只从自身UFD中寻找指定名称文件特点提高目录检索速度不同用户目录中，可以使用相同文件名，如上图Tommy和Ann的test文件不同用户可以使用不同文件名访问同一个共享文件，如上图Ann的laugh和Mary的cry文件有利于各用户隔离，不利于多用户协作（共享他人文件困难）352020/2/12多级目录（树型目录结构）在文件数目较多（大型FS）时，便于系统和用户将文件分散管理目录级别太多时，会增加路径检索时间目录的层次关系：根目录、父目录、子目录等当前目录(工作目录)：当前所处目录，为了便于小范围内指明路径而设置路径：各目录或文件可以用由根目录或当前目录开始依次经过的各级目录名再加上最终的目录名或文件名来表示，由根目录开始的路径称为绝对路径，由当前目录开始的路径称为相对路径362020/2/12在树型目录结构中增删目录创建目录：在创建者的UFD中搜索当前目录或指定目录中是否有重名，若无就在指定地点创建新目录，若有返回错误提示删除目录：删除相应目录项时要考虑被删除目录是否为空，通常采用不删除非空目录的安全方法372020/2/12目录查询技术查询过程根据用户提供文件名查询目录，找到该文件的FCB或i-node根据FCB或i-node中记录的物理地址找到文件在磁盘上的物理地址启动磁盘驱动器将文件读入内存查询方式线性检索哈希方式382020/2/12线性检索法（顺序检索法）单级目录利用文件名顺序查找目录表中相应目录项树型目录通过对组成目录路径的多个分量的逐一查找搜索所需目录项eg：检索linux系统中的/