哈工程考研课件-第6章 文件管理.ppt

《哈工程考研课件-第6章 文件管理.ppt》由会员分享，可在线阅读，更多相关《哈工程考研课件-第6章 文件管理.ppt（93页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章第六章 文件管理文件管理6.1 概述概述6.2 文件的逻辑结构文件的逻辑结构6.3 外存分配方式外存分配方式6.4 文件目录管理文件目录管理6.5 文件存储空间管理文件存储空间管理6.6 文件系统的可靠性和安全性文件系统的可靠性和安全性6.7 文件系统的数据一致性控制文件系统的数据一致性控制6.1 概述概述 所有的计算机应用程序都要所有的计算机应用程序都要:存储信息存储信息,检索信息检索信息三个基本要求：三个基本要求：能存储大量信息、长期保存信息、可共享信息能存储大量信息、长期保存信息、可共享信息解决方法解决方法:把信息以文件形式存在磁盘或其他介质上把信息以文件形式存在磁盘或其他介质上通

2、过操作系统管理文件：通过操作系统管理文件：文件的结构文件的结构,命名命名,存取存取,使用使用,保护和实现方法保护和实现方法用户观点用户观点(方便方便)：如何命名如何命名,如何访问如何访问,如何如何共享共享,如何保护文件。如何保护文件。操作系统观点操作系统观点(高效高效)：文件目录怎样实现文件目录怎样实现,怎样管理存储空间怎样管理存储空间,文件存储文件存储位置位置,磁盘实际运作方式磁盘实际运作方式(与设备管理的接口与设备管理的接口)等等等等6.1.1 文件与文件系统文件与文件系统 计算机中用到大量的信息计算机中用到大量的信息(程序和数据程序和数据)资源资源,平平时总是把它们以文件的形式长期存放在

3、外存中时总是把它们以文件的形式长期存放在外存中,需要时需要时可随时调入内存。文件系统就是统一管理这些信息资可随时调入内存。文件系统就是统一管理这些信息资源的源的OS软件软件,它管理文件的存储、检索和更新它管理文件的存储、检索和更新,提供提供安全可靠的共享和保护手段安全可靠的共享和保护手段,方便的给用户使用。方便的给用户使用。1.文件文件 文件是具有文件名的若干文件是具有文件名的若干(数目不定数目不定)相关元素的相关元素的集合集合,它是文件系统中的最大数据单位它是文件系统中的最大数据单位;可分为有结构可分为有结构文件和无结构文件文件和无结构文件;有结构文件的元素是记录有结构文件的元素是记录,记录

4、是记录是有意义的数据项的集合有意义的数据项的集合,无结构文件则是一个字符流无结构文件则是一个字符流,称为流式文件。称为流式文件。文件名文件名:ASCII码和汉字组成码和汉字组成,支持文件扩展名支持文件扩展名 文件属性文件属性:文件类型、文件文件类型、文件(当前当前)长度、长度、文件物理位置、文件建立时间文件物理位置、文件建立时间3.记录记录 有结构文件中有结构文件中,一组相关的数据项组成记录一组相关的数据项组成记录,若干若干条记录组成文件条记录组成文件,在各记录中能够唯一标识一个记录在各记录中能够唯一标识一个记录的数据项集合称为关键字的数据项集合称为关键字(key),通常用一个数据项作通常用一

5、个数据项作为关键字。为关键字。2.数据项数据项 有结构文件中有结构文件中,数据项是最低级的数据组织形式。数据项是最低级的数据组织形式。(1)基本数据项基本数据项:用于描述一个对象的某种属性的数据用于描述一个对象的某种属性的数据,是数据组织中可以命名的最小逻辑单位是数据组织中可以命名的最小逻辑单位,又称为字段。又称为字段。(2)组合数据项组合数据项:由若干个基本数据项组成由若干个基本数据项组成,简称组项。简称组项。记录记录1记录记录2记录记录i记录记录n数据项数据项1 数据项数据项2数据项数据项n文件文件4.文件系统模型文件系统模型(1)文件系统管理的对象其属性文件系统管理的对象其属性(相关的数

6、据结构相关的数据结构)文件、目录、存储空间。文件、目录、存储空间。(2)对对象操纵和管理的软件集合对对象操纵和管理的软件集合 读写管理、目录管理、共享和保护管理、存储空间读写管理、目录管理、共享和保护管理、存储空间 管理、地址映射、系统维护、物理管理、地址映射、系统维护、物理 I/O、设备驱动设备驱动(3)向用户提供一个方便使用的接口向用户提供一个方便使用的接口 命令接口、程序接口命令接口、程序接口文件系统接口文件系统接口 对对象操纵和管理的软件集合对对象操纵和管理的软件集合对象及其属性对象及其属性文件系统文件系统三层膜型三层膜型用户用户(程序程序)Surface LayoutSpindleS

7、urfaceTracksTrack kSectorsGapsAdapted from:Computer Systems:A Programmers PerspectivePlatter ViewSurface 0Surface 1Surface 2Surface 3Surface 4Surface 5Cylinder kSpindlePlatter 0Platter 1Platter 2Adapted from:Computer Systems:A Programmers PerspectiveDisk in ActionSpindleRecordsApplicationsStructured

8、 Record FilesRecord-Stream TranslationStream-Block TranslationByte Stream FilesStorage deviceStream-Block Translationb0b1b2bi.5.文件系统的功能文件系统的功能(1)统一的存储空间管理统一的存储空间管理,实施存储空间的分配与回收实施存储空间的分配与回收(2)实现文件的按名存取实现文件的按名存取 名字空间名字空间 映射映射 存储空间存储空间(逻辑地址转换为物理地址逻辑地址转换为物理地址)(3)实现文件信息的共享实现文件信息的共享,并提供文件的保护和保密措并提供文件的保护和保

9、密措施施(4)对文件的读写管理、目录管理对文件的读写管理、目录管理(5)系统维护及向用户提供有关信息系统维护及向用户提供有关信息(6)提供与提供与I/O设备的统一接口设备的统一接口(7)向用户提供方便使用的命令接口和程序接口向用户提供方便使用的命令接口和程序接口 (提供对文件系统和对文件的操作命令和语句提供对文件系统和对文件的操作命令和语句)文件系统在文件系统在OS 接口中占的比例最大接口中占的比例最大,用户使用用户使用OS的感觉在很大程度上取决于对文件系统的使用效果的感觉在很大程度上取决于对文件系统的使用效果.6.1.2 文件类型文件类型 为了提高系统管理文件的效率为了提高系统管理文件的效率

10、;提高用户界面友好提高用户界面友好性性,对文件进行分类。对文件进行分类。1.按文件性质和用途分类按文件性质和用途分类 系统文件：由系统软件构系统文件：由系统软件构 成的文件成的文件 用户文件：由用户产生的各种文件用户文件：由用户产生的各种文件 库文件：标准子程序及常用的例程构成的文件库文件：标准子程序及常用的例程构成的文件2.按信息保存期限分类按信息保存期限分类 临时文件；永久文件；档案文件临时文件；永久文件；档案文件3.按文件中的数据形式分类按文件中的数据形式分类 源文件、目标文件、可执行文件、数据文件源文件、目标文件、可执行文件、数据文件4.按文件的存储控制属性分类按文件的存储控制属性分类

11、 只执行文件；只读文件；读写文件。只执行文件；只读文件；读写文件。5.按文件的逻辑结构分类按文件的逻辑结构分类 流式文件流式文件(无结构无结构)；记录式文件；记录式文件(有结构有结构)。7.按文件的物理结构分类按文件的物理结构分类 顺序顺序(连续连续)文件；链接文件；索引文件文件；链接文件；索引文件8.UNIX系统将文件分为三类系统将文件分为三类普通文件普通文件(regular)包含的是用户信息包含的是用户信息,一般为一般为ASCII或二进制文件或二进制文件目录文件目录文件(directory)管理文件系统的系统文件管理文件系统的系统文件 特殊文件特殊文件(special file)设备文件设

12、备文件(将外设看作文件将外设看作文件)字符设备文件字符设备文件:用于模仿串行用于模仿串行I/O设备设备,如终端如终端,打印机打印机,网络等网络等 块设备文件块设备文件:模仿磁盘模仿磁盘 为了方便系统和用户了解文件的类型为了方便系统和用户了解文件的类型,常把文件类常把文件类型作为扩展名放在文件名的后面型作为扩展名放在文件名的后面,二者之间用二者之间用.隔开。隔开。6.1.3 文件操作文件操作1.文件的文件的打开打开和和关闭关闭操作操作 打开打开(open)文件文件,是系统将指名文件的属性是系统将指名文件的属性(类类型型,外存物理位置等外存物理位置等)从外存拷贝到内存打开文件表的从外存拷贝到内存打

13、开文件表的一个表目中一个表目中,并将该表目的编号并将该表目的编号(索引号索引号)返回给用户。返回给用户。此后此后,用户对文件的操作直接通过索引号进行用户对文件的操作直接通过索引号进行,避免了避免了对文件的再次检索。对文件的再次检索。关闭关闭(close)操作操作,将内存中的已修改的数据写将内存中的已修改的数据写到外存上到外存上,并将对应表目从打开文件表中删除。并将对应表目从打开文件表中删除。2.基本操作基本操作 创建文件创建文件:分配外存空间分配外存空间,建目录项填入各种属性建目录项填入各种属性 删除文件删除文件:将该目录项置为空项将该目录项置为空项,释放外存空间释放外存空间 读文件写文件读文

14、件写文件:目录项中得文件在外存目录项中得文件在外存位置位置,读写读写 截断文件截断文件:将文件内容置空将文件内容置空 设置文件读写的位置设置文件读写的位置:设置文件读写指针的位置设置文件读写指针的位置6.2 文件的逻辑结构文件的逻辑结构文件的逻辑结构文件的逻辑结构:从用户角度看文件的组织形式从用户角度看文件的组织形式文件的物理结构文件的物理结构:文件在外存上的存储组织形式文件在外存上的存储组织形式6.2.1 文件的逻辑结构类型文件的逻辑结构类型 1.有结构文件有结构文件(记录文件记录文件)文件是由若干个记录组成文件是由若干个记录组成,每条记录有其内部结构每条记录有其内部结构 按记录长度分按记录

15、长度分:定长记录、变长记录定长记录、变长记录 按记录间的关系分按记录间的关系分:顺序、索引、索引顺序顺序、索引、索引顺序 2.无结构文件无结构文件 又称为流式文件又称为流式文件,是元素长度为是元素长度为1的无结构字节流的无结构字节流,如如:源程序源程序,可执行文件可执行文件,库函数库函数,C语言的数据文件等。语言的数据文件等。在在UNIX系统中所有的文件被看作流式文件。系统中所有的文件被看作流式文件。好处：提供很大的灵活性。好处：提供很大的灵活性。一条记录一条记录一个字节一个字节流式文件流式文件 记录文件记录文件6.2.2 顺序文件顺序文件 1.文件的逻辑排序文件的逻辑排序 串结构：各记录的逻

16、辑顺序按存入的时间排序。串结构：各记录的逻辑顺序按存入的时间排序。有序结构：各记录的逻辑顺序按关键字排序。有序结构：各记录的逻辑顺序按关键字排序。2.对顺序文件的读对顺序文件的读/写操作写操作 顺序文件只能顺序读或顺序写顺序文件只能顺序读或顺序写,可设置读可设置读/写指针写指针Rptr和和Wptr,指向下一记录的逻辑地址。指向下一记录的逻辑地址。对定长记录对定长记录:每当读完一条记录时执行每当读完一条记录时执行:Rptr=Rptr+L 每当写完一条记录时执行每当写完一条记录时执行:Wptr=Wptr+L 对变长记录对变长记录:每当读完一条记录时执行每当读完一条记录时执行:Rptr=Rptr+L

17、i 每当写完一条记录时执行每当写完一条记录时执行:Wptr=Wptr+Li 3.优点优点:批量存取效率高批量存取效率高,缺点缺点:查找增删低效不方便查找增删低效不方便6.2.3 索引文件索引文件 对定长记录文件对定长记录文件,要查找第要查找第 i 个纪录个纪录,可直接计算可直接计算:Ai=A0+i*L (A0和和Ai是第是第0和第和第i个纪录的逻辑地址个纪录的逻辑地址)对变长记录文件对变长记录文件,要查找第要查找第 i 个纪录个纪录,则要计算则要计算:Ai=A0+i+Li (假定每个纪录前用假定每个纪录前用1字节存储长度字节存储长度)要实现直接存取文件要实现直接存取文件,对定长记录用公式计算很

18、方对定长记录用公式计算很方便便,但对变长记录却很困难但对变长记录却很困难;为此可建立一张索引表为此可建立一张索引表,索索引表本身是定长引表本身是定长记录文件记录文件,可直可直接计算在索引表接计算在索引表上找第上找第i 个纪录个纪录,按其指针值找到按其指针值找到指向的记录。指向的记录。i-1i=0R0R1.Ri.0 L0 1 L1 .i Li .索索引引表表逻逻辑辑文文件件 如果要按给定的关键字查找对应的记录如果要按给定的关键字查找对应的记录,对于定长对于定长记录文件记录文件,当纪录无序时只能顺序查找当纪录无序时只能顺序查找,效率很低效率很低;当当纪录是按的关键字排序时可直接用折半查找纪录是按的

19、关键字排序时可直接用折半查找,但插入和但插入和删除效率很低。对变长记录文件删除效率很低。对变长记录文件,如果没有索引表只能如果没有索引表只能顺序查找顺序查找,效率很低效率很低;而加了索引表后而加了索引表后,由于索引表是按纪录的关键字排由于索引表是按纪录的关键字排序的序的,检索时检索时,可用折半查找索引表可用折半查找索引表,按其指针值指向按其指针值指向的记录与给定的关键字比较的记录与给定的关键字比较,查到为止。当向索引文件查到为止。当向索引文件增加新纪录时需要修改索引表。增加新纪录时需要修改索引表。优点：检索数度块。优点：检索数度块。缺点：每个记录都对应一个索引项缺点：每个记录都对应一个索引项,

20、存储费用大。存储费用大。6.2.3 索引顺序文件索引顺序文件 对变长记录文件对变长记录文件,用索引表存储费用大用索引表存储费用大,结合索引结合索引文件和顺序文件的优点文件和顺序文件的优点,构成索引顺序文件构成索引顺序文件;所有记录所有记录逻辑上按关键字有序排列逻辑上按关键字有序排列,并将记录分为若干组并将记录分为若干组,索引索引表为每组的第一个记录建立一个索引表项表为每组的第一个记录建立一个索引表项,检索时先根检索时先根据索引表键值确定该记录在哪一组据索引表键值确定该记录在哪一组,再按该表项指针指再按该表项指针指向的主文件中的位置顺序查找到所要的记录。如向的主文件中的位置顺序查找到所要的记录。

21、如An FenAn Kan.Bao He.An FenBao He .Lan Lin .索索引引表表逻逻辑辑文文件件姓名姓名 其它属性其它属性键键 逻辑地址逻辑地址 如果某顺序文件的记录数为如果某顺序文件的记录数为N,则顺序检索平均查则顺序检索平均查找找N/2个记录。而对于索引顺序文件每组个记录。而对于索引顺序文件每组N个记录个记录,平平均查找均查找N个记录个记录;效率大大提高。对于特大型文件可效率大大提高。对于特大型文件可建立多级索引表。建立多级索引表。6.2.4 直接文件和哈希文件直接文件和哈希文件1.直接文件直接文件:根据给定的记录键值根据给定的记录键值,直接获得指定记录的直接获得指定记

22、录的物理地址物理地址,这种由给定的记录键值到记录的物理地址的这种由给定的记录键值到记录的物理地址的转换称为转换称为键值转换键值转换,关键是用什么函数进行转换。关键是用什么函数进行转换。2.哈希文件哈希文件:用哈希函数用哈希函数(或称散列函数或称散列函数)进行进行键值转换键值转换,为了能实现文件存储空间的动态分配为了能实现文件存储空间的动态分配,通常由哈希函数通常由哈希函数求得的不是记录的地址求得的不是记录的地址,而是指向目录表相应表项的指而是指向目录表相应表项的指针针,表项的内容指向相应记录所在的物理块。如表项的内容指向相应记录所在的物理块。如 目录表目录表Hash(k)键值键值哈希函数哈希函

23、数物物理理块块6.3 外存分配方式外存分配方式 文件的物理结构与外存分配方式有关。文件的物理结构与外存分配方式有关。常用分配方式有常用分配方式有:连续分配、链接分配和索引分配连续分配、链接分配和索引分配。对应的物理结构对应的物理结构:连续结构、链接式结构和索引结构连续结构、链接式结构和索引结构6.3.1.连续分配连续分配 为每个文件分配一组连续的相邻物理块为每个文件分配一组连续的相邻物理块,形成的形成的文件结构称顺序文件结构文件结构称顺序文件结构,物理文件称顺序文件。这物理文件称顺序文件。这种分配方式保证了记录的逻辑顺序种分配方式保证了记录的逻辑顺序,与占用盘块的物与占用盘块的物理顺序一致理顺

24、序一致;在目录项的在目录项的文件物理地址文件物理地址字段中存放字段中存放该文件的第一个记录所在盘块号和文件长度该文件的第一个记录所在盘块号和文件长度(块数块数)。如如:目录目录 file start length f1 0 2 tr 14 3 mail 19 6 .2.连续分配的优缺点连续分配的优缺点优点优点:顺序存取简单容易顺序存取简单容易,也支持直接也支持直接(随机随机)存取。存取。顺序存取速度快顺序存取速度快,寻道次数和寻道时间最少。寻道次数和寻道时间最少。也适合随机访问也适合随机访问,计算出盘块地址直接访问。计算出盘块地址直接访问。缺点缺点:易产生外部碎片易产生外部碎片,降低外存空间的

25、利用率降低外存空间的利用率;可可利利 用紧凑法将外部碎片拼接成连续存储空间用紧凑法将外部碎片拼接成连续存储空间,但紧凑但紧凑 一次需要进行大量的磁盘操作花费大量的时间。一次需要进行大量的磁盘操作花费大量的时间。不利于文件的插入和删除。不利于文件的插入和删除。必须事先知道文件的大小必须事先知道文件的大小,对于动态增长的文对于动态增长的文件效果较差。需要估算预留的连续外存空间件效果较差。需要估算预留的连续外存空间,预留预留空间不足将引起大片磁盘空间的移动空间不足将引起大片磁盘空间的移动,预留空间太预留空间太大将使大量的外存空间长期空闲。大将使大量的外存空间长期空闲。6.3.2 链接分配链接分配 将

26、文件存放在多个离散的盘块中将文件存放在多个离散的盘块中,同一文件的盘块同一文件的盘块链接成一个链表链接成一个链表,消除外部碎片消除外部碎片,显著的提高了外存显著的提高了外存空间的利用率空间的利用率,有利于文件插入和删除有利于文件插入和删除,有利于文件有利于文件的动态扩充。的动态扩充。1.隐式链接隐式链接 在文件目录的每个目录项中在文件目录的每个目录项中,都含有指向链接文件都含有指向链接文件第一个盘块和最后一个盘块的指针第一个盘块和最后一个盘块的指针,而在每个盘块而在每个盘块中都含有指向下一个盘块的指针中都含有指向下一个盘块的指针,只有只有508字节供使用。字节供使用。缺点缺点:只适合顺序访问只

27、适合顺序访问,随机访问要从头查找极低效。随机访问要从头查找极低效。可靠性差可靠性差,盘块的指针出现问题会导致链断开。盘块的指针出现问题会导致链断开。更多的寻道次数和寻道时间。更多的寻道次数和寻道时间。解决方法解决方法:可将几个盘块组成一个簇可将几个盘块组成一个簇,减少查找指定块的时间减少查找指定块的时间。First blockHead:417.LengthByte 0Byte 4095.LengthByte 0Byte 4095.LengthByte 0Byte 4095.Block 0Block 1Block N-1Linked ListsEach Block Contains a Head

28、er WithNumber of Bytes in the Block-Allows Storage of Variable Length BlocksPointer to Next BlockBlocks Need Not Be ContiguousFiles Can Expand and ContractConsequently,Seeks Can Be Slow 2.显式链接显式链接 将链接文件各物理块的指针存放在内存的一张链将链接文件各物理块的指针存放在内存的一张链接表中接表中,整个磁盘仅设一张表称为文件分配表整个磁盘仅设一张表称为文件分配表(FAT),表项的序号是物理盘块号表项的序号

29、是物理盘块号,每个表项中存放链接指针每个表项中存放链接指针(下一盘块号下一盘块号)。每个文件的第一个盘块号填入该文件。每个文件的第一个盘块号填入该文件的文件控制块的文件控制块(FCB)的的物理地址物理地址字段中。记录的查字段中。记录的查找过程全部在内存中进行找过程全部在内存中进行,检索速度快、访问磁盘磁检索速度快、访问磁盘磁盘次数少、可靠性高。（盘次数少、可靠性高。（MS-DOS的的FAT）FCBf1FAT 9 4 0 7 3 1 11 0 1 2 3 4 5 6 7 8 9 10 11 12 13.2FCBf26FAT中每项的大小中每项的大小与磁盘最大容量以与磁盘最大容量以及簇的大小有关及簇

30、的大小有关4716.3.3 索引分配索引分配 链接分配存在的问题：链接分配存在的问题：要顺序查找许多盘块号要顺序查找许多盘块号,不支持高效的直接存取。不支持高效的直接存取。FAT占用较大的内存空间。占用较大的内存空间。1.单级索引分配单级索引分配 为每个文件分配一个集中存放的索引块为每个文件分配一个集中存放的索引块(表表),该表该表实质就是磁盘块地址数组实质就是磁盘块地址数组,其中第其中第i项存放指向文件的第项存放指向文件的第i块盘块号块盘块号,该文件的目录项中存储了指向该索引块的指该文件的目录项中存储了指向该索引块的指针针;支持直接存取支持直接存取,如如:记录号记录号m 第第i块块 盘块号盘

31、块号012345.91611025-1.索索引引块块目录目录 file 块号块号 f1 19 fr 31 .2.多级索引分配多级索引分配 对于大文件对于大文件,当分配的盘块号已装满一个索引块时当分配的盘块号已装满一个索引块时,必须另分配索引块必须另分配索引块,各索引块通过指针连结起来各索引块通过指针连结起来,文件文件太大索引块太多时太大索引块太多时,检索索引块将是低效的检索索引块将是低效的,此时应为此时应为这些索引块再建立一级索引这些索引块再建立一级索引,形成了两级索引形成了两级索引,必要时必要时还可建立更多级的索引分配方式。还可建立更多级的索引分配方式。3.混合索引分配方式混合索引分配方式

32、索引分配方式的索引块花费较多空间索引分配方式的索引块花费较多空间,小文件索引小文件索引块利用率更低。块利用率更低。UNIX用用混合混合索引模式避免此缺点。每索引模式避免此缺点。每个文件的索引结点含个文件的索引结点含13个地址项个地址项 i.addr(0)i.addr(12),每项每项2个字节个字节;前前10项存放直接地址项存放直接地址(物理块号物理块号),若文若文件大于件大于40kB，则用则用i.addr(10)指向单级索引块进行一次指向单级索引块进行一次间接寻址间接寻址,该块中最多可放该块中最多可放1k个物理块号个物理块号,文件可长达文件可长达4MB;还可用还可用 i.addr(11)和和

33、i.addr(12)作为二次和三次作为二次和三次间接寻址间接寻址,文件最大长度分别可达文件最大长度分别可达4GB和和4TB。.datadata.datadatadata.data.datadata.datadatadata.datamodeownerstime stampssizeblock counti.addr(0)i.addr(1)i.addr(9)i.addr(10)i.addr(11)i.addr(12).间接间接地址项地址项混合索引方式混合索引方式直接直接地址项地址项DatamodeownerDirect block 0Direct block 1Direct block 11Si

34、ngle indirectDouble indirectTriple indirectinodeDataDataIndexDataDataIndexIndexIndexIndexIndexIndexIndexIndexDataDataDataDataUNIX FilesWith 4K Blocks4K x 12=48KFor Single Indirect1000 Indices/Block4K x 1000=4MFor Double Indirect4K x 1,000,000 For Triple Indirect4K x?6.3.4 文件物理结构、存取方式与存储介质的关系文件物理结构、存

35、取方式与存储介质的关系存取方式存取方式:顺序存取方式顺序存取方式,随机随机(直接直接)存取方式存取方式存储介质存储介质物理结构物理结构存取方式存取方式磁带磁带连续结构连续结构顺序存取顺序存取磁盘磁盘连续连续链接链接索引索引顺序顺序顺序顺序顺序顺序随机随机 随机随机 对比三种分配的优缺点对比三种分配的优缺点 连续分配连续分配 优点优点:顺序存取简单高效顺序存取简单高效,寻道距离次数少寻道距离次数少,访问速度快访问速度快,也适合随机访问也适合随机访问,算出块地址直接访问。算出块地址直接访问。缺点缺点:有外部碎片有外部碎片,外存利用率低外存利用率低,插入和删除不容易插入和删除不容易 链接分配链接分配

36、优点优点:消除外存碎片消除外存碎片,外存利用率高外存利用率高,有利于文件的动有利于文件的动 态扩充态扩充,容易插入和删除容易插入和删除,缺点缺点:不适合随机访问不适合随机访问,可靠性差可靠性差,寻道次数多速度慢寻道次数多速度慢 显式链接分配可显著减少寻道次数显式链接分配可显著减少寻道次数,提高检索速提高检索速 度度,但但FAB占用了较大的内存空间占用了较大的内存空间 索引分配索引分配优点优点:链接分配的全部优点链接分配的全部优点,还适合随机访问还适合随机访问,寻道次寻道次数数 少少,检索速度快。检索速度快。缺点缺点:索引块费较多空间索引块费较多空间,小文件尤甚小文件尤甚,混合索引可避免。混合索

37、引可避免。课后题课后题:P219 6,7,9,106.4 文件目录管理文件目录管理目录管理的基本要求目录管理的基本要求:实现实现按名存取按名存取提高对目录的检索速度提高对目录的检索速度允许文件共享允许文件共享允许文件重名允许文件重名6.4.1文件控制块和索引结点文件控制块和索引结点1.文件控制块文件控制块(FCB):是操作系统为管理文件而设置是操作系统为管理文件而设置的用于描述和控制文件的数据结构的用于描述和控制文件的数据结构,存放了为管理文存放了为管理文件所需的所有有关信息。件所需的所有有关信息。文件和文件和FCB一一对应一一对应,FCB的有序集称为文件目的有序集称为文件目录录,一个一个FC

38、B 就是一个目录项就是一个目录项,为实现对文件目录的为实现对文件目录的管理管理,通常将文件目录以文件的形式保存在外存上通常将文件目录以文件的形式保存在外存上,这个文件就叫目录文件。这个文件就叫目录文件。文件控制块的内容：文件控制块的内容：基本信息基本信息:文件名文件名,扩展名扩展名,文件主名文件主名 文件物理地址文件物理地址:存放设备名存放设备名,起始盘块号起始盘块号,文件长文件长度度 文件逻辑结构文件逻辑结构:流式或记录文件流式或记录文件,定长或不定长定长或不定长 文件物理结构文件物理结构:顺序、链接式、索引文件顺序、链接式、索引文件存取控制信息存取控制信息:文件主、核准用户和一般用户的存取

39、权限文件主、核准用户和一般用户的存取权限使用信息使用信息:文件的建立日期文件的建立日期,最后修改日期最后修改日期,最后访问日期最后访问日期,当前使用信息当前使用信息(共享计数共享计数,是否被锁住是否被锁住,已被修改是否存已被修改是否存盘盘)文件名文件名 扩展名扩展名 属性属性 备用备用 时间时间 日期日期 起始块号起始块号 盘块数盘块数MS-DOS的文件控制块的文件控制块(32个字节个字节)2.索引结点索引结点(i结点结点)(1)索引结点的引入索引结点的引入 当目录中文件很多时当目录中文件很多时,文件目录要占用大量的盘块文件目录要占用大量的盘块,查找目录时需要将这些盘块逐块调入内存查找目录时需

40、要将这些盘块逐块调入内存,将给定的文将给定的文件名与目录中的文件名逐一比较件名与目录中的文件名逐一比较;假如一个假如一个FCB为为64B,1KB的盘块只能存的盘块只能存16个个FCB,一个目录有一个目录有640个个FCB,需需占用占用40个盘块个盘块,查找一个目录平均要启动磁盘查找一个目录平均要启动磁盘20次。次。检索目录时只用到了文件名检索目录时只用到了文件名,如果将如果将FCB中的文件中的文件名而和描述信息分开存储名而和描述信息分开存储,就可以增加目录的每个盘块就可以增加目录的每个盘块中的文件数中的文件数,减少访盘次数减少访盘次数,加快检索速度加快检索速度;UNIX系统中系统中就采用这种方

41、法就采用这种方法,将文件描述信息单独存放在索引结点将文件描述信息单独存放在索引结点中中(简称简称i结点结点),目录项仅由文件名和指向该文件对应目录项仅由文件名和指向该文件对应的的 i结点的指针构成结点的指针构成,UNIX的目录项仅占的目录项仅占16B,1KB的的盘块能存盘块能存64个目录项访盘次数降到原来的个目录项访盘次数降到原来的1/4。(2)磁盘索引结点磁盘索引结点 存放在磁盘上的索引结点存放在磁盘上的索引结点,每个文件有唯一的一个每个文件有唯一的一个modeownerstime stampssizeblock counti.addr(0)i.addr(1)i.addr(9)i.addr(

42、10)i.addr(11)i.addr(12)文件类型文件类型:普通文件、目录文件普通文件、目录文件 特殊文件特殊文件文件主文件主:所有者和小组标识符所有者和小组标识符时间标记时间标记:文件最近被访问时间文件最近被访问时间 文件最近被修改时间文件最近被修改时间 i结点最近被修改时间结点最近被修改时间文件长度文件长度:字节长度字节长度连接计数连接计数:指向该文件的指针计数指向该文件的指针计数直接地址直接地址:10项直接盘块地址项直接盘块地址间接地址间接地址:3种级别的索引块地址种级别的索引块地址(3)磁盘索引结点内存索引结点磁盘索引结点内存索引结点 存放在存放在内存内存上的索引结点上的索引结点,

43、文件打开时将磁盘索引文件打开时将磁盘索引结点拷贝到内存的索引结点中结点拷贝到内存的索引结点中,并增加一下几项当前正并增加一下几项当前正使用的内容。使用的内容。(1)索引结点编号索引结点编号:用来标识内存索引结点用来标识内存索引结点(2)状态状态:i结点是否上锁或被修改结点是否上锁或被修改(3)访问计数访问计数:正在访问此正在访问此 i结点的进程数结点的进程数(4)所属的逻辑设备号所属的逻辑设备号(5)链接指针链接指针:指向空闲链表和散列队列的指针指向空闲链表和散列队列的指针6.4.2 目录结构目录结构1.单级目录结构单级目录结构 为所有文件建立一个目录文件为所有文件建立一个目录文件(组成一线性

44、表组成一线性表)优点优点:简单，易实现简单，易实现缺点缺点:(1)目录项太多时查找速度慢平均检索时间长目录项太多时查找速度慢平均检索时间长 (2)不允许重名不允许重名,限制了用户对文件的命名限制了用户对文件的命名 (3)不便于实现文件共享不便于实现文件共享,只适用于单用户环境只适用于单用户环境2.二级目录结构二级目录结构 为改变一级目录文件目录命名冲突为改变一级目录文件目录命名冲突,而改进而改进,可可用不同文件名共享同一文件。用不同文件名共享同一文件。目录分为两级目录分为两级:一级称为主文件目录一级称为主文件目录MFD,给出用给出用户名户名,用户子目录所在的物理位置用户子目录所在的物理位置;二

45、级称为用户文二级称为用户文件目录件目录UFD(用户子目录用户子目录),给出该用户所有文件的给出该用户所有文件的FCB。优点优点:提高了检索目录的速度提高了检索目录的速度,解决了文件重名问题解决了文件重名问题和文件共享问题和文件共享问题,不同用户用不同文件名访问同一文不同用户用不同文件名访问同一文件件。缺点：缺点：增加了系统空间开销增加了系统空间开销MFD 用户名用户名 指针指针 Zhang WangLi .UFD(Z)FCB(fz1)FCB(fz2)FCB(fz3).fz1fz2fz3.UFD(W)FCB(fw1)FCB(fw2).fw1fw2.UFD(L)FCB(fl1)FCB(fl2).f

46、l1fl2.二级目录结构二级目录结构3.多级目录结构多级目录结构(树型目录树型目录)目录结构目录结构:大型文件系统通常采用三级或三级以上的目大型文件系统通常采用三级或三级以上的目 录结构录结构,构成树型目录构成树型目录,主目录称为根目录主目录称为根目录,其其它它 目录均作为树的分支结点目录均作为树的分支结点,文件称为树叶。文件称为树叶。路径名路径名:在树型目录结构在树型目录结构,从根目录到各文件从根目录到各文件,用经历用经历的的 全部目录名和文件名表示唯一的路径名。全部目录名和文件名表示唯一的路径名。当前目录当前目录:可为每个进程设置一个可为每个进程设置一个当前目录当前目录,进程对进程对 文件

47、的访问都相对于文件的访问都相对于当前目录当前目录进行。进行。优点：优点：层次结构清晰层次结构清晰,便于管理和保护便于管理和保护,解决重名问题解决重名问题,文件共享问题文件共享问题,查找速度加快。查找速度加快。缺点：缺点：增加了系统空间开销增加了系统空间开销,查找一个文件按路径名逐查找一个文件按路径名逐 层检查层检查,由于每个文件都放在外存由于每个文件都放在外存,级数太多级数太多时时 访盘次数增多影响速度。访盘次数增多影响速度。D E FA B CeR S TfA C acA B abX Y ZD E CS R srxyzdecUNIX文件系统结构文件系统结构 i i i i i i i i i

48、root目录目录bin user dev bin目录目录s1 user目录目录Liu Lidev目录目录 Liu目录目录f1 t1 Li目录目录t1 e2 6.4.3 目录查询技术目录查询技术1.线性检索法线性检索法单级目录：单级目录：用户给出文件名用户给出文件名,按名顺序查找目录项按名顺序查找目录项多级目录根据路径名顺序查找各级目录：多级目录根据路径名顺序查找各级目录：全路径名：从根开始全路径名：从根开始 相对路径：从当前路径相对路径：从当前路径 各级目录未查到时应停止查询各级目录未查到时应停止查询,返回返回文件未找到文件未找到,查到则根据盘块号指针读入下级目录继续查。查到则根据盘块号指针读

49、入下级目录继续查。2.Hash方法方法 建立一张建立一张 Hash索引文件目录索引文件目录,利用利用Hash函数直函数直接将文件名转换为索引值直接查找接将文件名转换为索引值直接查找,解决冲突的规则解决冲突的规则:(1)该目录项为空则未找到该目录项为空则未找到 (2)文件名文件名(或子目录名或子目录名)匹配则找到匹配则找到 (3)该目录项非空则发生冲突该目录项非空则发生冲突,将将Hash值加一常数值加一常数(与目录长度互质与目录长度互质)继续查找继续查找1.外存的特点外存的特点容量大容量大,断电后仍可保存信息断电后仍可保存信息,速度较慢速度较慢,成本较低成本较低由两部分组成由两部分组成:驱动部分

50、驱动部分+存储介质存储介质种类很多种类很多,外存空间组织与地址与存取方式非常复杂外存空间组织与地址与存取方式非常复杂I/O过程方式非常复杂过程方式非常复杂2.用户对外存的要求用户对外存的要求 读写外存数据读写外存数据,方便、高效、安全方便、高效、安全(1)读写时不涉及硬件细节读写时不涉及硬件细节,使用逻辑地址和逻辑操作使用逻辑地址和逻辑操作(2)存取速度尽可能快，容量大且空间利用率高存取速度尽可能快，容量大且空间利用率高(3)信息安全可靠信息安全可靠,防止来自硬件的故障和他人的侵权防止来自硬件的故障和他人的侵权(4)可以方便地共享可以方便地共享,动态扩缩动态扩缩,携带拆卸携带拆卸,了解使用情况