操作系统原理操作系统原理 (56).pdf

操作系统操作系统原理原理 Operating System PrincipleOperating System Principle 1010-4 4-2 2 目录结构目录结构 Organize the Directory（Logically）to Obtain 组织目录的逻辑结构 1、Efficiency locating a file quickly.（效率：快速的定位一个文件）Two users can have same name for different files.（两个用户可以有相同名字的不同文件）2、Naming convenient to users.（命名：方便用户）The same file can have several different names.（相同的文件可以有不同的名字）Single-Level Directory 单级目录 A single directory for all users.（一个对所有用户的简单目录结构）Naming problem（命名问题）Grouping problem（分组）Two-Level Directory 两级目录 为解决一级目录文件命名冲突，并提高对目录文件检索速度而改进 目录分为两级：优点：一级称为主文件目录（MFD），给出用户名，用户子目录所在的物理位置；二级称为用户文件目录（UFD，又称用户子目录），给出该用户所有文件的FCB 解决了文件的重名问题:用户名|文件名 查找时间降低 Two-Level Directory 两级目录 Separate directory for each user.（每个用户有单独的目录结构）user 1 user 2 user 3 user 4 master file directory cat bo a test a data a test x data a user file directory Path name（路径名）Can have the same file name for different user不同的用户可以有相同的文件名 Efficient searching（有效率的搜索）No grouping capability（无法分组）Tree-Structured Directories 树型目录 spell bin programs root start mail dist find count hex reorder p e mail prog copy prt exp reorder list find hex count list obj spell all last first Tree-Structured Directories（Cont.）树状目录（续）Efficient searching（有效的搜索）Grouping Capability（分组的可能）Current directory（working directory）（当前目录工作目录）cd /spell/mail/prog type list Tree-Structured Directories 树型目录 spell bin programs root start mail dist find count hex reorder p e mail prog copy prt exp reorder list find hex count list obj spell all last first Tree-Structured Directories（Cont.）树状目录（续）优点：优点：层次结构清晰，便于管理和保护；有利于文件分类；解决重名问题；提高文件检索速度；缺点：缺点：查找一个文件按路径名逐层检查，由于每个文件都放在外存，多次访盘影响速度 不支持共享 Acyclic-Graph Directories 无环图结构目录 Have shared subdirectories and files.（有共享的子目录和文件）dict spell root list all w count count words list list rade w7 Acyclic-Graph Directories 无环图结构目录 Two different names（aliasing）（别名：两个不同的名字）If dict deletes list dangling pointer.Solutions：（解决方案）BackpointersBackpointers，soso wewe cancan deletedelete allall pointerspointers.（断点断点，我们可以删除所有的指针我们可以删除所有的指针）EntryEntry-holdhold-countcount solutionsolution.（表项保留计数的解决表项保留计数的解决）General Graph Directory 普通图结构目录 avi tc jim root text mail count book book mail unhex hyp avi count unhex hex General Graph Directory（Cont.）普通图结构目录（续）Allow only links to file not subdirectories.（只允许链接到文件而不允许链接到子目录）Garbage collection.（垃圾收集）Every time a new link is added use a cycle detection algorithm to determine whether it is OK.（每次添加一个链接时都用一个检测算法判断是否正确）How do we guarantee no cycles?（如何保证无环）