操作系统第6章

1、第六章第六章文件管理文件管理文件文件n文件是指由创建者所定义的、具有文件名的一文件是指由创建者所定义的、具有文件名的一组相关元素的集合。可分为有结构文件和无结构组相关元素的集合。可分为有结构文件和无结构文件两种。文件两种。 文件文件记录记录1记录记录2记录记录n数据项数据项1数据项数据项2数据项数据项n文件类型文件类型n按用途分类按用途分类n按数据形式分类按数据形式分类n按存取控制属性分类按存取控制属性分类n按组织形式和处理方式分类按组织形式和处理方式分类系统文件系统文件用户文件用户文件库文件库文件源文件源文件目标文件目标文件可执行文件可执行文件只执行文件只执行文件只读文件只读文件读写文件读写

2、文件普通文件普通文件目录文件目录文件特殊文件特殊文件文件系统文件系统n文件系统是指操作系统中各类文件、管理文件的文件系统是指操作系统中各类文件、管理文件的软件，以及管理文件所涉及到的数据结构等信息软件，以及管理文件所涉及到的数据结构等信息的集合。的集合。文件系统接口文件系统接口对象及其属性对象及其属性用户（程序）用户（程序）对对象操纵对对象操纵和管理的软和管理的软件集合件集合逻辑文件系统逻辑文件系统基本基本I/O管理程序管理程序(文件组织模块文件组织模块)基本文件系统基本文件系统(物理物理I/O层层)I/O控制层控制层(设备驱动程序设备驱动程序)文件管理系统管理的对象有：文件管理系统管理的对象

3、有： n文件文件文件管理的直接对象；文件管理的直接对象；n目录目录方便用户对文件检索和存取。包含文件方便用户对文件检索和存取。包含文件名和文件属性的说明；名和文件属性的说明；n磁盘存储空间磁盘存储空间对文件和目录占用的外存空间对文件和目录占用的外存空间进行管理，可以提高外存利用率，加快文件的进行管理，可以提高外存利用率，加快文件的检索速度。检索速度。对象及其属性对象及其属性这是文件管理系统的核心部分。主要功能包括：这是文件管理系统的核心部分。主要功能包括：n对文件存储空间的管理；对文件存储空间的管理；n对文件目录的管理；对文件目录的管理；n将文件的逻辑地址转换为物理地址的机制；将文件的逻辑地址

4、转换为物理地址的机制；n对文件读和写的管理；对文件读和写的管理；n对文件的共享与保护等功能；对文件的共享与保护等功能； 对对象操纵和管理的软件集合对对象操纵和管理的软件集合nI/O控制层控制层(设备驱动程序设备驱动程序) 启动启动I/O操作和对操作和对设备发来的中断信号处理；设备发来的中断信号处理；n基本文件系统基本文件系统(物理物理I/O层层) 处理内存与磁盘处理内存与磁盘系统之间数据块的交换；系统之间数据块的交换；n基本基本I/O管理程序管理程序(文件组织模块文件组织模块) 完成与完成与I/O有关的大量事物：选择文件所在的设备、地址映有关的大量事物：选择文件所在的设备、地址映射、空闲盘块的

5、管理、射、空闲盘块的管理、I/O缓冲的指定；缓冲的指定；n逻辑文件系统逻辑文件系统处理文件和记录的相关操作；处理文件和记录的相关操作；(1) 命令接口命令接口 (2) 程序接口程序接口文件系统的接口文件系统的接口文件操作文件操作 n创建文件创建文件系统要为新文件分配必要的外存空系统要为新文件分配必要的外存空间，并在文件系统的目录中为之建一个目录项；间，并在文件系统的目录中为之建一个目录项； n删除文件删除文件系统应先从目录中找到要删除文件系统应先从目录中找到要删除文件的目录项，使之成为空项，然后回收该文件所占的目录项，使之成为空项，然后回收该文件所占用的存储空间；用的存储空间； n读文件读文件

6、须在系统调用中给出文件名和文件被须在系统调用中给出文件名和文件被读入的内存目标地址；读入的内存目标地址；n写文件写文件须在系统调用中给出文件名和文件须在系统调用中给出文件名和文件在内存中的源地址；在内存中的源地址；n截断文件截断文件文件内容需要全部更新时，将原文件内容需要全部更新时，将原文件的长度设置为文件的长度设置为0；n设置文件的读设置文件的读/写位置写位置用于设置文件读写指用于设置文件读写指针的位置，以便每次读写文件时，不是从其开始针的位置，以便每次读写文件时，不是从其开始端开始，而是从所设置的位置处开始；端开始，而是从所设置的位置处开始；文件的文件的“打开打开”操作操作n系统将指名文件

7、的属性从外存拷贝到内存打开文件系统将指名文件的属性从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号返回给用户。表的一个表目中，并将该表目的编号返回给用户。n用户再要求对该文件进行操作时，系统直接利用索用户再要求对该文件进行操作时，系统直接利用索引号到打开文件表中去查找，从而避免了对文件的引号到打开文件表中去查找，从而避免了对文件的再次检索。再次检索。文件文件“关闭关闭”操作操作n如果用户不再需要对该文件实施相应的操作时，如果用户不再需要对该文件实施相应的操作时，可利用可利用“关闭关闭”(close)系统调用来关闭此文件，系统调用来关闭此文件，OS把该文件从打开文件表中的表目上删除掉。把

8、该文件从打开文件表中的表目上删除掉。OS提供了有关文件操作的系统调用：提供了有关文件操作的系统调用：n一类是有关对文件属性进行操作的，即允许用户一类是有关对文件属性进行操作的，即允许用户直接设置和获得文件的属性；直接设置和获得文件的属性；n另一类是有关目录的，如创建一个目录，删除一另一类是有关目录的，如创建一个目录，删除一个目录，改变当前目录和工作目录等；个目录，改变当前目录和工作目录等；n用于实现文件共享的系统调用和用于对文件系统用于实现文件共享的系统调用和用于对文件系统进行操作的系统调用等。进行操作的系统调用等。 其它文件操作其它文件操作文件的结构文件的结构（1）文件的逻辑结构）文件的逻辑

9、结构 用户可以直接处理的数据及其结构，它独立于文用户可以直接处理的数据及其结构，它独立于文件的物理特性，又称为文件组织；件的物理特性，又称为文件组织； (2) 文件的物理结构文件的物理结构 又称为文件的存储结构，是指文件在外存上的存又称为文件的存储结构，是指文件在外存上的存储组织形式；储组织形式； 文件逻辑结构的类型文件逻辑结构的类型n有结构文件有结构文件由一个以上的记录构成的文件；由一个以上的记录构成的文件；n无结构文件无结构文件由字符流构成的文件；由字符流构成的文件；n根据记录长度根据记录长度(1)定长记录定长记录(2)变长记录变长记录 n根据用户和系统管理上的需要根据用户和系统管理上的需

10、要(1)顺序文件顺序文件 (2)索引文件索引文件 (3)索引顺序文件索引顺序文件 有结构文件有结构文件n无结构文件又称流式文件，构成文件的基本单位无结构文件又称流式文件，构成文件的基本单位是字符，文件是有逻辑意义的、无结构的一串字是字符，文件是有逻辑意义的、无结构的一串字符的集合。符的集合。n其长度以字节为单位。对流式文件的访问，采用其长度以字节为单位。对流式文件的访问，采用读写指针来指出下一个要访问的字符。读写指针来指出下一个要访问的字符。n在在UNIX系统中，所有的文件都被看作是流式文系统中，所有的文件都被看作是流式文件，系统不对文件进行格式处理；件，系统不对文件进行格式处理； 无结构文件

11、无结构文件顺序文件逻辑记录的排序顺序文件逻辑记录的排序 n第一种是串结构，各记录之间的顺序与关键字无第一种是串结构，各记录之间的顺序与关键字无关，按存入时间的先后排列；关，按存入时间的先后排列；n第二种情况是顺序结构，指文件中的所有记录按第二种情况是顺序结构，指文件中的所有记录按关键字关键字(词词)排列。可以按关键词的长短从小到大排列。可以按关键词的长短从小到大排序，也可以从大到小排序；或按其英文字母顺排序，也可以从大到小排序；或按其英文字母顺序排序；序排序； 对顺序文件的读对顺序文件的读/写操作写操作n对于定长记录文件，如果要查找第对于定长记录文件，如果要查找第i个记录，第个记录，第i个记录

12、相对于第一个记录首址的地址为：个记录相对于第一个记录首址的地址为： Ai= iLn对于变长度记录文件，要查找第对于变长度记录文件，要查找第i个记录，要顺个记录，要顺序地查找每个记录，获得相应记录的长度序地查找每个记录，获得相应记录的长度Li，然，然后按下式计算出第后按下式计算出第i个记录的首址。假定在每个个记录的首址。假定在每个记录前用一字节指明该记录的长度，则：记录前用一字节指明该记录的长度，则：10iiiiiLA定长和变长记录文件定长和变长记录文件 R0R1R2R3RiLLLLLL2L3L4LL(i+1)LRptr(a) 定长记录文件定长记录文件L0R0L1R1RiWptr(b)变长记录文

13、件变长记录文件Li00L0L0+1L1L0+L1+2Li(Lk+1)i-1K=0(Lk+1)iK=0顺序文件的优缺点顺序文件的优缺点 n最佳应用场合是在对诸记录进行批量存取时，最佳应用场合是在对诸记录进行批量存取时，即每次要读或写一大批记录；即每次要读或写一大批记录；n在交互应用场合，用户要求查找或修改单个记在交互应用场合，用户要求查找或修改单个记录，便要逐个地查找诸记录录，便要逐个地查找诸记录, ,性能就可能很差；性能就可能很差；n增加或删除一个记录，比较困难；增加或删除一个记录，比较困难；索引文件索引文件n为变长记录文件建立一张索引表，对主文件中为变长记录文件建立一张索引表，对主文件中的每

14、个记录，在索引表中设一个相应的表项，用的每个记录，在索引表中设一个相应的表项，用于记录该记录的长度于记录该记录的长度L以及指向该记录的指针；以及指向该记录的指针；n根据用户提供的关键字，利用折半查找法去检根据用户提供的关键字，利用折半查找法去检索索引表，从中找到相应的表项；索索引表，从中找到相应的表项；n利用该表项中给出的指针值，去访问所需的记利用该表项中给出的指针值，去访问所需的记录录;索引表索引表索引号索引号0长度长度 m指针指针 ptrm01m1imiR0R1Ri逻辑文件逻辑文件索引顺序文件索引顺序文件 n是顺序文件和索引文件相结合的产物；是顺序文件和索引文件相结合的产物；n将顺序文件中

15、的所有记录分为若干个组，为顺序将顺序文件中的所有记录分为若干个组，为顺序文件建立一张索引表；文件建立一张索引表；n在索引表中为每组中的第一个记录建立一个索引在索引表中为每组中的第一个记录建立一个索引项，含有该记录的键值和指向该记录的指针项，含有该记录的键值和指向该记录的指针; ;n检索时，先利用用户提供的关键字检索时，先利用用户提供的关键字, ,按某种查找算法按某种查找算法去检索索引表；去检索索引表；n找到该记录所在记录组中第一个记录的表项，从中得找到该记录所在记录组中第一个记录的表项，从中得到该记录组第一个记录在主文件中的位置；到该记录组第一个记录在主文件中的位置；n再利用顺序查找法去查找主

16、文件，从中找到所要求的再利用顺序查找法去查找主文件，从中找到所要求的记录；记录；键键An QiBao RongChen Lin逻辑地址逻辑地址姓姓 名名An QiAn Kang其它属性其它属性Bao Rong逻辑文件逻辑文件直接文件直接文件n可根据给定的记录键值，直接获得指定记录的物可根据给定的记录键值，直接获得指定记录的物理地址理地址; ;n记录键值本身就决定了记录的物理地址记录键值本身就决定了记录的物理地址; ;n由记录键值到记录物理地址的转换被称为键值转由记录键值到记录物理地址的转换被称为键值转换换; ;哈希哈希(Hash)文件文件 Hash文件的逻辑结构文件的逻辑结构n利用利用Hash

17、函数，将记录键值转换为相应记录的地址函数，将记录键值转换为相应记录的地址;n由由Hsah函数所求的是指向一目录表相应表目的指针，函数所求的是指向一目录表相应表目的指针，该表目的内容指向相应记录所在的物理块该表目的内容指向相应记录所在的物理块;fHash函数函数目录表目录表键值键值n连续分配连续分配n链接分配链接分配n索引分配索引分配外存分配方式外存分配方式磁道磁道(柱面柱面)扇区扇区磁臂磁臂磁头磁头盘面盘面n为每一个文件分配一组相邻接的盘块为每一个文件分配一组相邻接的盘块; ;n把逻辑文件中的记录顺序地存储到邻接的各物把逻辑文件中的记录顺序地存储到邻接的各物理盘块中理盘块中; ;n这样形成的文

18、件结构称为顺序文件结构这样形成的文件结构称为顺序文件结构, ,物理文物理文件称为顺序文件件称为顺序文件; ;连续分配方式连续分配方式mail1230567491011813141512171819162122232025262724list29303128countfilestart lengthcount02tr143mail196list284f62目录目录 tr f连续分配的主要优缺点连续分配的主要优缺点 n优点：优点：(1)顺序访问容易顺序访问容易; (2)顺序访问速度快顺序访问速度快;n缺点：缺点：(1)要求有连续的存储空间要求有连续的存储空间; (2)必须事先知道文件的长度必须事先

19、知道文件的长度;链接分配链接分配n 文件的信息存放在若干不连续的物理块中；文件的信息存放在若干不连续的物理块中；n各块之间通过指针连接，前一个物理块指向下各块之间通过指针连接，前一个物理块指向下一个物理块；一个物理块；n可分为隐式链接和显式链接；可分为隐式链接和显式链接；16隐式链接隐式链接 25123056749101181314151217181916212223202526272429303128filestartendjeep925目录目录101-1显式链接显式链接 012345物理块号物理块号2FCBFAT-1451缺点：缺点：n存取速度慢，不适于随机存取存取速度慢，不适于随机存取;

20、n可靠性问题，如指针出错可靠性问题，如指针出错;n更多的寻道次数和寻道时间更多的寻道次数和寻道时间;n链接指针占用一定的空间链接指针占用一定的空间;FAT16与与FAT32n在在FAT16的情况下，分区越大簇就相应的要增大，存储的情况下，分区越大簇就相应的要增大，存储效率就越低，势必造成存储空间的浪费。效率就越低，势必造成存储空间的浪费。nFAT32可以大大地节约磁盘空间。文件在磁盘上是以簇可以大大地节约磁盘空间。文件在磁盘上是以簇的方式存放的，簇里存放了一个文件就不能再存放另外的方式存放的，簇里存放了一个文件就不能再存放另外的文件。的文件。n假如一个磁盘的分区大小为假如一个磁盘的分区大小为5

21、12MB，基，基 于于FAT16的系统的系统的簇的大小为的簇的大小为8KB，而，而FAT32系统的簇的大小仅是系统的簇的大小仅是4KB，那么，现在我们存放一个那么，现在我们存放一个3KB的文件，的文件，FAT16系统就会有系统就会有5KB的空间的空间 被浪费，而被浪费，而FAT32的浪费则会少一些。如果的浪费则会少一些。如果分区达到分区达到1GB，FAT16的簇为的簇为16KB，而，而FAT32还是还是4KB，节省的也就更多了。节省的也就更多了。 FAT32FAT32是是FAT系列文件系统的最后一个产品，每个簇系列文件系统的最后一个产品，每个簇固定为固定为4KB ； n最大单文件大小：最大单文

22、件大小：4GB (Fat16分区是分区是2 GB )n最大文件数量：最大文件数量： 268,435,437n最长档名限制：最长档名限制： 8.3或者长文件名或者长文件名255个字符个字符n最大卷大小：最大卷大小： 8 TB（8*1024GB）（在）（在windows 2000和和windows XP环境下格式化程序只能创建最大环境下格式化程序只能创建最大32GB的的FAT32文件系统）文件系统） http:/ NT以及之后的以及之后的Windows 2000、Windows XP、Windows Server 2003、Windows Server 2008、Windows Vista和和Wi

23、ndows 7的标准文件的标准文件系统。系统。nNTFS采用了更小的簇，大小可由格式化命令或格式采用了更小的簇，大小可由格式化命令或格式化程序按磁盘容量和应用需求来确定，可以更有效率化程序按磁盘容量和应用需求来确定，可以更有效率地管理磁盘空间。地管理磁盘空间。nNTFS 提供长文件名、数据保护和恢复，并通过目录提供长文件名、数据保护和恢复，并通过目录和文件许可实现安全性。和文件许可实现安全性。NTFS 支持大硬盘和在多个支持大硬盘和在多个硬盘上存储文件硬盘上存储文件(称为卷称为卷)。n在在NTFS分区上分区上,可以为共享资源、文件夹以及文件设可以为共享资源、文件夹以及文件设置访问许可权限。置访

24、问许可权限。http:/ 一个文件的信息存放在若干不连续物理块中，一个文件的信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构系统为每个文件建立一个专用数据结构索引索引表，并将这些块的块号存放在一个索引表中；表，并将这些块的块号存放在一个索引表中；n索引分配方式支持直接访问，当要读文件的第索引分配方式支持直接访问，当要读文件的第i个盘块时，可以方便地直接从索引块中找到第个盘块时，可以方便地直接从索引块中找到第i个盘块的盘块号；个盘块的盘块号；123056749101181314151217181916212223202526272429303128countfile块序号块序号j

25、eep19目录目录91611025-1-1-119单级索引表的优缺点单级索引表的优缺点优点：优点：n即能顺序存取，又能随机存取；即能顺序存取，又能随机存取；n满足了文件动态增长、插入删除的要求；满足了文件动态增长、插入删除的要求；n能充分利用外存空间；能充分利用外存空间；缺点：缺点：n索引表本身带来了系统开销索引表本身带来了系统开销, ,如：内外存空间，如：内外存空间，存取时间存取时间; ;例题例题 设一个文件占据了设一个文件占据了100个物理块，对于连续结个物理块，对于连续结构、链接结构和索引结构的文件，如果要将一块信构、链接结构和索引结构的文件，如果要将一块信息按下述要求操作，假设文件的文

26、件控制块已经在息按下述要求操作，假设文件的文件控制块已经在内存，问分别要启动多少次磁盘内存，问分别要启动多少次磁盘I/O操作？（链接操作？（链接方式使用单链表，无头尾指针）方式使用单链表，无头尾指针）（1）加一块在文件的首部；）加一块在文件的首部；（2）加一块在文件中间（第）加一块在文件中间（第51块）；块）；（3）加一块在文件结尾。）加一块在文件结尾。（1）在文件中的首部插入一块，）在文件中的首部插入一块，n连续结构需要移动所有盘块，共启动磁盘连续结构需要移动所有盘块，共启动磁盘200次，次，然后再启动首部的盘块，写入插入内容，所以是然后再启动首部的盘块，写入插入内容，所以是201次；次；n

27、链接文件需要启动一个盘块并把指针指向第一链接文件需要启动一个盘块并把指针指向第一个盘块，所以是个盘块，所以是1次；次；n索引文件需要启动一个盘块，然后在索引表中索引文件需要启动一个盘块，然后在索引表中添加指向该块的指针，所以启动盘块添加指向该块的指针，所以启动盘块1次；次；（2）在文件中间插入一块，）在文件中间插入一块，n连续结构需要移动后面连续结构需要移动后面50个盘块，共启动磁盘个盘块，共启动磁盘100次，然后再启动中间盘块，写入插入内容，次，然后再启动中间盘块，写入插入内容，所以是所以是101次；次；n链接文件需要先启动一次盘块写入新内容，然链接文件需要先启动一次盘块写入新内容，然后启动

28、前后启动前50个盘块，并把第个盘块，并把第50盘块指针指向新盘盘块指针指向新盘块，启动新盘块，指针指向第块，启动新盘块，指针指向第51盘块，共盘块，共52次；次；n索引文件需要启动一个盘块，然后在索引表中索引文件需要启动一个盘块，然后在索引表中添加指向该块的指针，所以启动盘块添加指向该块的指针，所以启动盘块1次；次；（3）在文件尾部插入一块，）在文件尾部插入一块，n直接将主存信息写入磁盘，所以是直接将主存信息写入磁盘，所以是1次；次；n链接文件需要先启动链接文件需要先启动1次盘块写入新内容，然后次盘块写入新内容，然后启动前启动前100个盘块，并修改第个盘块，并修改第100盘块指针，共盘块指针，

29、共101次；次；n索引文件需要启动一个盘块，然后在索引表中索引文件需要启动一个盘块，然后在索引表中添加指向该块的指针，所以启动盘块添加指向该块的指针，所以启动盘块1次；次；思考？思考？n对于一个磁盘上的文件系统，文件的物理结构可对于一个磁盘上的文件系统，文件的物理结构可以采用连续、链接和索引文件的方式。如果当前位以采用连续、链接和索引文件的方式。如果当前位于逻辑块于逻辑块10，且希望访问逻辑块，且希望访问逻辑块4，那么，必须分，那么，必须分别从盘上读几个物理块？别从盘上读几个物理块？n连续方式，需要读连续方式，需要读1个物理块；个物理块；n链接方式，需要读链接方式，需要读5个物理块；个物理块；

30、n索引方式，需要读索引方式，需要读2个物理块；个物理块；多级索引分配多级索引分配将一个大文件的所有索引表（二级索引将一个大文件的所有索引表（二级索引) )的地址的地址放在另一个索引表（一级索引放在另一个索引表（一级索引) )中；中；01210510625435635798510510625474035635711259853607401125主索引主索引360第二级索引第二级索引磁盘空间磁盘空间n如每个盘块的大小为如每个盘块的大小为1KB，每个盘块号占，每个盘块号占4个字节，个字节，则一个索引块中可存放则一个索引块中可存放256个盘块号；个盘块号；n两级索引表，最多可包含的存放文件的盘块的盘两

31、级索引表，最多可包含的存放文件的盘块的盘块号总数块号总数N=256*256=64K个盘块号；个盘块号；n采用两级索引时，允许的文件最大长度为采用两级索引时，允许的文件最大长度为64MB；n倘若盘块大小为倘若盘块大小为4KB，一级索引和二级索引所允，一级索引和二级索引所允许的最大文件长度可达多大？许的最大文件长度可达多大？modeowners (2)time stamps (3)sizeblock counti.addr (0)i.addr (1)direct blockssingle indirectdouble indirecttriple indirectdatadatadatadatad

32、atadatadatadatadatadata混合索引分配方式混合索引分配方式n直接地址直接地址在索引结点中可设置在索引结点中可设置10个直接地址项，即用个直接地址项，即用iaddr(0)iaddr(9)来存放直接地址。在这里的每项中来存放直接地址。在这里的每项中所存放的是该文件数据的盘块的盘块号；所存放的是该文件数据的盘块的盘块号；n一次间接地址一次间接地址地址项地址项iaddr(10)来提供一次间接地址。实质就是一级来提供一次间接地址。实质就是一级索引分配方式；索引分配方式；n多次间接地址多次间接地址地址项地址项iaddr(11)提供二次间接地址。该方式的实质是提供二次间接地址。该方式的实

33、质是两级索引分配方式；两级索引分配方式；采用混合索引方式，假如每个盘块大小为采用混合索引方式，假如每个盘块大小为4KB，盘块，盘块号占用号占用4B；n直接地址可寻址的最大范围为直接地址可寻址的最大范围为40K（10*4K）n一次间接地址可寻址的最大范围为一次间接地址可寻址的最大范围为4M（1K*4K）n二次间接地址可寻址的最大范围为二次间接地址可寻址的最大范围为4G（1K*1K*4K）n三次间接地址可寻址的最大范围为三次间接地址可寻址的最大范围为4T（1K*1K*1K*4K）n目录：所有文件控制块目录：所有文件控制块(FCB)组织在一起，就构组织在一起，就构成了文件目录，即文件控制块的有序集合

34、成了文件目录，即文件控制块的有序集合;n目录项：构成文件目录的项目目录项：构成文件目录的项目(目录项就是目录项就是FCB)n目录文件：为了实现对文件目录的管理，通常目录文件：为了实现对文件目录的管理，通常将文件目录以文件的形式保存在外存，这个文件将文件目录以文件的形式保存在外存，这个文件就叫目录文件；就叫目录文件；目录管理目录管理filestart lengthcount02tr143mail196list284f62目录目录文件控制块（文件控制块（FCB）n是是OS为管理文件而设置的数据结构，存放了为管为管理文件而设置的数据结构，存放了为管理文件所需的所有有关信息；理文件所需的所有有关信息；

35、n文件控制块是文件存在的标志；文件控制块是文件存在的标志；n文件控制块的内容：文件控制块的内容： 基本信息基本信息存取控制信息存取控制信息使用信息使用信息文文件件名名扩扩展展名名属属性性备备用用时时间间日日期期第第一一块块号号盘盘块块数数索引结点索引结点文件名文件名索引结点编号索引结点编号文件名文件名1文件名文件名2n把文件名与文件描述信息分开，使文件描述信息单把文件名与文件描述信息分开，使文件描述信息单独形成一个称为索引结点的数据结构，简称独形成一个称为索引结点的数据结构，简称i结点。结点。n在文件目录中的每个目录项仅由文件名和指向所对在文件目录中的每个目录项仅由文件名和指向所对应的应的i结

36、点的指针构成；结点的指针构成；UNIX的文件目录的文件目录n磁盘索引结点磁盘索引结点磁盘上的索引结点磁盘上的索引结点l每个文件有唯一的一个磁盘索引结点；每个文件有唯一的一个磁盘索引结点；l包括：主标识符、类型、存取权限、物理地址、长包括：主标识符、类型、存取权限、物理地址、长度、连接计数、存取时间；度、连接计数、存取时间；n内存索引结点内存索引结点内存的中索引结点内存的中索引结点l当文件被打开时，将磁盘索引结点拷贝到内存的索当文件被打开时，将磁盘索引结点拷贝到内存的索引结点中引结点中;l增加如增加如 下的内容：索引结点编号、状态、访问计数、下的内容：索引结点编号、状态、访问计数、文件所属文件系

37、统的逻辑设备号、链接指针。文件所属文件系统的逻辑设备号、链接指针。例题例题n在实现文件系统时，为加快文件目录的检索速度，可利在实现文件系统时，为加快文件目录的检索速度，可利用用“文件控制块分解法文件控制块分解法”。假设目录存放在磁盘上，每。假设目录存放在磁盘上，每个盘块个盘块512字节，文件控制块占字节，文件控制块占64字节，其中文件名占字节，其中文件名占8字节，通常将文件控制块分解成两部分，第一部分占字节，通常将文件控制块分解成两部分，第一部分占10字节（包括文件名和文件内部号），第二部分占字节（包括文件名和文件内部号），第二部分占54字节字节（包括文件内部号和文件其他描述信息）。（包括文件

38、内部号和文件其他描述信息）。n假定某一目录文件共有假定某一目录文件共有254个文件控制块，试分别给出个文件控制块，试分别给出采用分解法前和分解法后，查找该目录的某一个文件控采用分解法前和分解法后，查找该目录的某一个文件控制块的平均访问磁盘次数。制块的平均访问磁盘次数。n采用分解法前采用分解法前n一个盘块存放一个盘块存放512/64=8个目录项，个目录项，254个目录项需要个目录项需要32个盘块；个盘块；n查找一个文件的平均访问盘块数：查找一个文件的平均访问盘块数：(1+32)/2=16.5次；次；n采用分解法后采用分解法后n一个盘块存放一个盘块存放512/10=51个目录项，个目录项，254个

39、目录项需要个目录项需要5个盘块；个盘块；n查找文件的第一部分的平均访问盘块数查找文件的第一部分的平均访问盘块数：(1+5)/2=3次；次；n查找第二部分需要访问磁盘查找第二部分需要访问磁盘1次，所以查找一个文件控次，所以查找一个文件控制块的平均访问磁盘次数是制块的平均访问磁盘次数是3+1=4次；次；单级目录结构单级目录结构 文件名文件名物理地址物理地址文件说明文件说明状态位状态位文件名文件名1文件名文件名2在整个文件系统中只建立一张目录表，每个文件占在整个文件系统中只建立一张目录表，每个文件占一个目录项，目录项中含有文件名、文件扩展名、一个目录项，目录项中含有文件名、文件扩展名、文件长度、文件

40、类型、文件物理地址以及其他文件文件长度、文件类型、文件物理地址以及其他文件属性。属性。n优点：优点：简单且能实现目录管理的基本功能简单且能实现目录管理的基本功能按名存取；按名存取；n缺点：缺点：(1) 查找速度慢；查找速度慢； (2) 不允许重名；不允许重名； (3) 不便于实现文件共享；不便于实现文件共享； 两级目录两级目录目录分为两级：目录分为两级：n一级称为主文件目录一级称为主文件目录MFD，每个用户目录文件，每个用户目录文件都占有一个目录项，包含用户名和指向该用户子都占有一个目录项，包含用户名和指向该用户子目录的指针；目录的指针；n二级称为用户文件目录二级称为用户文件目录UFD(又称用

41、户子目录又称用户子目录)，给出该用户所有文件的给出该用户所有文件的FCB；用户名用户名WangZhangGao指向子目录指针指向子目录指针Wang用户目录用户目录AlphaTestAlphaTestReportTestZhang用户目录用户目录ReportTestGao用户目录用户目录BetaDeviceMisxBetaDeviceMisx优点：优点：(1)提高了检索目录的速度；提高了检索目录的速度； (2)在不同的用户目录中，可使用相同的文件名；在不同的用户目录中，可使用相同的文件名；(3)不同用户还可使用不同的文件名来访问系统中不同用户还可使用不同的文件名来访问系统中的同一个共享文件；的同

42、一个共享文件； 多级目录结构（树型目录）多级目录结构（树型目录）n多级目录结构又称为树型目录结构；多级目录结构又称为树型目录结构；n主目录称为根目录，数据文件称为树叶，其主目录称为根目录，数据文件称为树叶，其他目录均作为树的结点；他目录均作为树的结点；ABCFED13ABD2GA4AC5671011JNK12JMK13AHF141516b1718192021a89路径名路径名n在树形目录结构中，从根目录到任何数据文件，在树形目录结构中，从根目录到任何数据文件，都只有一条惟一的通路。系统中的每一个文件都有都只有一条惟一的通路。系统中的每一个文件都有惟一的路径名。惟一的路径名。n从树的根从树的根(

43、即主目录即主目录)开始，把全部目录文件名与数开始，把全部目录文件名与数据文件名，依次地用据文件名，依次地用“/”连接起来，构成该数据文连接起来，构成该数据文件的路径名件的路径名(path name);n从树根开始的路径名称为绝对路径名从树根开始的路径名称为绝对路径名(absolute path name)。当前目录当前目录n从当前目录开始，逐级经过中间的目录文件，从当前目录开始，逐级经过中间的目录文件，最后到达要访问的数据文件。这一路径上的全部最后到达要访问的数据文件。这一路径上的全部目录文件名与数据文件名用目录文件名与数据文件名用“/”连接形成路径名。连接形成路径名。n从当前目录开始直到数据

44、文件为止所构成的路从当前目录开始直到数据文件为止所构成的路径名，称为相对路径名径名，称为相对路径名(relative path name)；目录查询技术目录查询技术n户用访问一个已存在的文件，系统首先利用用户户用访问一个已存在的文件，系统首先利用用户提供的文件名对目录进行查询，找出该文件的文提供的文件名对目录进行查询，找出该文件的文件控制块或对应索引结点；件控制块或对应索引结点；n根据根据FCB或索引结点中所记录的文件物理地址或索引结点中所记录的文件物理地址(盘盘块号块号)，换算出文件在磁盘上的物理地址；，换算出文件在磁盘上的物理地址；n再通过磁盘驱动程序将所需文件读入内存；再通过磁盘驱动程序

45、将所需文件读入内存；（1）线性检索法）线性检索法n又称顺序检索法；又称顺序检索法；n在单级目录中，利用用户提供的文件名，用顺在单级目录中，利用用户提供的文件名，用顺序查找法直接从文件目录中找到指名文件的目录序查找法直接从文件目录中找到指名文件的目录项；项；n在树型目录中，用户提供的文件名是由多个文在树型目录中，用户提供的文件名是由多个文件分量名组成的路径名，对多级目录进行查找；件分量名组成的路径名，对多级目录进行查找；查找查找/usr/ast/mbox的步骤的步骤例题例题 某文件系统中，根目录长驻内存。某文件系统中，根目录长驻内存。目录文件采用链接结构，普通文件采用目录文件采用链接结构，普通文

46、件采用三级索引结构。三级索引结构。 假设一个物理块放假设一个物理块放10个目录项，一个个目录项，一个目录下最多放目录下最多放40个文件。如果下级文件个文件。如果下级文件是目录文件，则上级目录项指向该目录是目录文件，则上级目录项指向该目录文件的首地址；如果下级文件是普通文文件的首地址；如果下级文件是普通文件，则上级目录项指向该文件的文件控件，则上级目录项指向该文件的文件控制块。制块。 假设索引表地址放在假设索引表地址放在FCB中，如果中，如果要读取要读取K的某一块，需要启动硬盘最少的某一块，需要启动硬盘最少几次，最多几次？（假设文件按自左向几次，最多几次？（假设文件按自左向右的顺序建立）右的顺序

47、建立）ROOTABCDEFGHIJK. .ADGHK读读ADGHK的某一块的某一块 因为目录文件采用链接形式因为目录文件采用链接形式, 每个磁盘块存每个磁盘块存放放10个下级文件的描述个下级文件的描述, 一个目录下最多存放一个目录下最多存放40个下级文件，故一个目录文件最多占个下级文件，故一个目录文件最多占4个物个物理块。根目录文件已在内存，故不必启动硬理块。根目录文件已在内存，故不必启动硬盘读入它。盘读入它。 最少最少 最多最多n根目录文件根目录文件nA目录文件目录文件 1次次 4次次nD目录文件目录文件 1次次 4次次nG目录文件目录文件 1次次 4次次nH目录文件目录文件 1次次 4次次

48、nK文件控制块文件控制块 1次次 1次次nK文件某一块文件某一块 4次次 4次次 共共 9次次 21次次ROOTABCDEFGHIJK. .（2）Hash方法方法n系统利用用户提供的文件名并将它变换为文件系统利用用户提供的文件名并将它变换为文件目录的索引值；目录的索引值；n再利用该索引值到目录中去查找，提高检索速再利用该索引值到目录中去查找，提高检索速度；度；文件存储空间的管理文件存储空间的管理n空闲分区表法空闲分区表法n空闲分区链法空闲分区链法n位示图法位示图法n成组链接法成组链接法空闲块表空闲块表n属于连续分配方式，为每个文件分配一块连续的存属于连续分配方式，为每个文件分配一块连续的存储空

49、间；储空间； n系统为外存上所有空闲区建立一张空闲表，每个空系统为外存上所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项，其中包括表项序号、该空闲区对应于一个空闲表项，其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息；闲区的第一个盘块号、该区的空闲盘块数等信息；序号序号第一空闲盘块号第一空闲盘块号空闲盘块数空闲盘块数12429331554n空闲盘区的分配与内存的动态分配类似，采用首次空闲盘区的分配与内存的动态分配类似，采用首次适应算法、循环首次适应算法等；适应算法、循环首次适应算法等；n在系统为某新创建的文件分配空闲盘块时，先顺序在系统为某新创建的文件分配空闲盘块时，先顺

50、序地检索空闲表的各表项，直至找到第一个其大小能满地检索空闲表的各表项，直至找到第一个其大小能满足要求的空闲区，再将该盘区分配给用户足要求的空闲区，再将该盘区分配给用户( (进程进程) )，同，同时修改空闲表。时修改空闲表。存储空间的分配存储空间的分配n系统在对用户所释放的存储空间进行回收时，也采系统在对用户所释放的存储空间进行回收时，也采取类似于内存回收的方法，即要取类似于内存回收的方法，即要考虑回收区是否与空考虑回收区是否与空闲表中插入点的前区和后区相邻接，对相邻接者应予闲表中插入点的前区和后区相邻接，对相邻接者应予以合并；以合并； 存储空间的回收存储空间的回收空闲链表法空闲链表法 将所有空

51、闲区拉成一条空闲链，可分为：将所有空闲区拉成一条空闲链，可分为：n空闲盘块链空闲盘块链将磁盘上的所有空闲空间，以盘块为单位拉成一将磁盘上的所有空闲空间，以盘块为单位拉成一条链；条链；n空闲盘区链空闲盘区链 将磁盘上的所有空闲空盘区（每个盘区可包含若将磁盘上的所有空闲空盘区（每个盘区可包含若干个盘块），拉成一条链；干个盘块），拉成一条链；1234567891011 12 13 1415161120001110010011020001111110000111311100011111100004.16位图法位图法n用一串二进制位反映磁盘空间中分配使用情况用一串二进制位反映磁盘空间中分配使用情况, 每

52、个物每个物理块对应一位理块对应一位, 分配物理块为分配物理块为1，否则为，否则为0；n申请物理块时，可以在位示图中查找为申请物理块时，可以在位示图中查找为0的位，返回对的位，返回对应物理块号；应物理块号；n归还时；将对应位转置归还时；将对应位转置0盘块的分配盘块的分配 n顺序扫描位示图，从中找出一个或一组其值为顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位的二进制位(“0”表示空闲时表示空闲时)；n将所找到的一个或一组二进制位，转换成与之相将所找到的一个或一组二进制位，转换成与之相应的盘块号。假定找到的其值为应的盘块号。假定找到的其值为“0”的二进制位，的二进制位，位于位示的第位于位

53、示的第i行、第行、第j列，则其相应的盘块号应按列，则其相应的盘块号应按下式计算：下式计算： b=n(i-1)+j， n代表每行的位数；代表每行的位数；n修改位示图，修改位示图， 令令mapi,j=1；盘块的回收盘块的回收 n将回收盘块的盘块号转换成位示图中的行号和将回收盘块的盘块号转换成位示图中的行号和列号。列号。 转换公式为：转换公式为： i=(b-1)DIV n+1 j=(b-1)MOD n+1n修改位示图。令修改位示图。令map i,j=1； 成组链接法成组链接法 UNIX系统采用的空闲盘块管理方法，把空闲块分成若干系统采用的空闲盘块管理方法，把空闲块分成若干组，把指向一组中各空闲块的指

54、针集中在一起。组，把指向一组中各空闲块的指针集中在一起。1004003993013001003002992022012991004003992013019907999790179007899780179997901空闲盘空闲盘块号栈块号栈S.free019899n首先检查空闲盘块号栈是否上锁，如未上锁，便首先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格；给用户，然后将栈顶指针下移一格；n若该盘块号已是栈底，即若该盘块号已是栈底，即S.free(0)，将栈底盘块号，将栈底盘块号所对应盘

55、块的内容读入栈中，作为新的盘块号栈的所对应盘块的内容读入栈中，作为新的盘块号栈的内容；把原栈底对应的盘块分配出去内容；把原栈底对应的盘块分配出去(其中的有用其中的有用数据已读入栈中数据已读入栈中)；n再分配一相应的缓冲区再分配一相应的缓冲区(作为该盘块的缓冲区作为该盘块的缓冲区)。最。最后，把栈中的空闲盘块数减后，把栈中的空闲盘块数减1并返回。并返回。 空闲盘块的分配空闲盘块的分配n将回收盘块的盘块号记入空闲盘块号栈的顶部，将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加并执行空闲盘块数加1操作。操作。n当栈中空闲盘块号数目已达当栈中空闲盘块号数目已达100时，表示栈已满，时，表示

56、栈已满，便将现有栈中的便将现有栈中的100个盘块号，记入新回收的盘块个盘块号，记入新回收的盘块中，再将其盘块号作为新栈底。中，再将其盘块号作为新栈底。 空闲盘块的回收空闲盘块的回收例题例题nUNIX系统采用空闲块成组链接的方法管理磁系统采用空闲块成组链接的方法管理磁盘空闲空间，如图所示。问此事若一个文件盘空闲空间，如图所示。问此事若一个文件A需要需要5个盘块，则系统会将哪些盘块分配给它？个盘块，则系统会将哪些盘块分配给它？若之后有个文件若之后有个文件B被删除，它占用的盘块号为被删除，它占用的盘块号为333，334，404，405，782，则回收这些盘块，则回收这些盘块后，专用块的内容如何？后，

57、专用块的内容如何？空闲块数空闲块数450495612.空闲块数空闲块数100150149.5251空闲块数空闲块数1000449.352.专用块专用块50*150*解：解：n从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格。所以在专用块中可获得然后将栈顶指针下移一格。所以在专用块中可获得12、56、49、50块；块；n盘块号盘块号50已是栈底，即已是栈底，即S.free(0)，须调用磁盘读过程，将栈，须调用磁盘读过程，将栈底盘块号所对应盘块的内容读入栈中，再分配一相应的盘块，底盘块号所对应盘块的内容读入栈中，再分配一

58、相应的盘块，分配分配51号盘块；号盘块；n文件文件A得到第得到第12、56、49、50和和51块。块。空闲块数空闲块数450495612.空闲块数空闲块数100150149.5251空闲块数空闲块数1000449.352.专用块专用块50*n将回收盘块的盘块号记入空闲盘块号栈的顶部，记录块将回收盘块的盘块号记入空闲盘块号栈的顶部，记录块号号333，并执行空闲盘块数加，并执行空闲盘块数加1操作；操作；n当栈中空闲盘块号数目已达当栈中空闲盘块号数目已达100时，表示栈已满，便将时，表示栈已满，便将现有栈中的现有栈中的100个盘块号，记入新回收的盘块中，再将个盘块号，记入新回收的盘块中，再将其盘块号

59、作为新栈底。其盘块号作为新栈底。n然后专用块中依次记录块号：然后专用块中依次记录块号：334，404，405，782空闲块数空闲块数4.空闲块数空闲块数150149.52空闲块数空闲块数1000449.352.专用块专用块33333440440578299100334*n基于索引结点的共享方式基于索引结点的共享方式n利用符号链实现文件共享利用符号链实现文件共享文件共享与文件保护文件共享与文件保护AABBBBBCCCCC根目录根目录?CCCn在树型结构目录中，当有两个或多个用户要共在树型结构目录中，当有两个或多个用户要共享一个子目录或文件时，必须将共享文件或子目享一个子目录或文件时，必须将共享文件或子目录链接到两个或多个用户的目录中，才能方便地录链接到两个或多个用户的目录中，才能方便地找到该文件。找到该文件。基于索引结点的共享方式基于索引结点的共享方式n引入索引结点，将文件的物理地址及其它的文件属引入索引结点，将文件的物理地址及其它的文件属性等信息，不再放在目录项中，而是放在索引结点性等信息，不再放在目录项中，而是放在索引结点中，文件目录中只设置文件名及指向相应索引结点中，文件目录中只设置文件名及指向相应索引结点的指针。的