操作系统第七章.ppt

路径(path)： 每个目录或文件，可以由根目录开始依次经由的各级目录名，加上最终的目录名或文件名来表示. 优点： 层次结构清晰，便于管理和保护,解决重名问题,查找速度加快. 缺点： 查找一个文件按路径名逐层检查，由于每个文件都放在外存，多次访盘影响速度。 7.3.3 树形结构目录 改进的多级目录： 为了提高目录检索速度，可把目录中的文件说明（文件描述符）信息分成两个部分： 符号文件目录： 由文件名和文件内部标识组成的树状结构，按文件名排序. 基本文件目录（索引节点目录）： 由其余文件说明信息组成的线性结构，按文件内部标识排序. 基本文件目录: 符号文件目录的层次结构: 7.3.4 目录查询技术 对目录进行查询的方式： 线性检索法和Hash方法 线性检索法： 又称为顺序检索法，在单级目录中，利用用户提供的文件名，用顺序查找法直接从文件目录表中找到指名文件的目录项。在树型目录中，用户提供的文件名是由多个文件分量名组成的路径名，此时须对多级目录进行查找。 1 1 4 7 9 14 6 8 bal · · bin dev 496 lib etc usr tmp 6 1 19 30 51 26 45 26 6 64 92 17 60 81 132 ast jim erik dick src minix mbox books grants · · · · · · · 根目录 结点6是 /usr的目录 132#块是 /usr的目录 结点26是 /usr/ast目录 496#块是 /usr/ast目录 在结点6中查 找usr字段 查找/usr/ast/mbox的步骤: Hash方法： 如果建立了一张 Hash索引目录，利用Hash方法进行查询。 系统利用用户提供的文件名并将它变换为文件目录的索引值，再利用该索引值到目录中去查找，将显著的提高检索速度。 在进行文件名转换时，可能把不同的文件名转换为相同的Hash值，解决此问题的方法是： 在利用Hash法索引查找目录时，如果目录表中相应的目录项是空的，表示系统中并无指定文件； 如果目录表项中的文件名与指定文件名相匹配，表示该目录项正式所要寻找的文件所对应的目录项，可以从中找到该文件的物理地址； 如果在目录表项中的文件名与指定文件名不匹配，表示发生了冲突，此时需将Hash值再加上一个常数（该常数应与目录的长度值互质），形成新的索引值，再返回到第一步重新开始查找。 7.4 文件共享 定义: 一个文件被多个用户或程序使用。 目的： 节省时间和存储空间，减少了用户 工作量；进程间通过文件交换信息。 早期实现文件共享的方法 绕弯路法:早期的MULTICS等操作系统中所采用的一种共享文件方法.该方法中,允许用户获得一个“当前目录”.用户所访问的所有文件都是相对于当前目录; 当所访问的文件不在其当前目录下时,可以通过“向上走”的方式去访问其上级目录.为此用“*”表示一个目录的父目录.假定当前目录为F,若用户要访问E的文件J,可利用路径名*.E.J,还可以利用*.*.C.A来访问文件, 缺点：路径绕弯; 文件n,文件1：不同的文件名可以 访问该文件。 连访法:在目录项之间进行链接.一个目录中的目录项直接指向另一目录中的目录项.在连访法实现文件共享时,应在文件说明中增加一连访属性,以指示文件说明中的物理地址是一指向文件或共享文件的目录项的指针,应包括共享该文件的“用户计数”,用于表示共有多少用户需要使用此文件,仅当已无用户再需要此文件时才可将此共享文件撤消. 缺点：（1）增加了连访属性 （2）增加“用户计数” （3）文件n,文件1：不同的文件名可以 访问该文件。 利用基本文件目录实现文件共享: 在文件系统中设置一个基本目录，每个文件在该目录中均占有一个目录项，用于给出系统赋予的、对应于该文件名的唯一标识符（整数），以及该文件的有关说明信息。 0 1 2 3 4 5 6 7 8 9 · · · · · · · · · · Wang 3 Zhang 1 Mist Alpha Report Oaf 7 6 8 9 空闲文件目录 ··· ··· ··· ID物理位置 主文件目录MFD 符号名 ID Sqrt Beta 5 6 ··· 符号名 ID 符号名 ID 主目录MFD Zhang的SFD Sqrt Wang的Beta Zhang的Alpha Mist Report Oaf W