《操作系统课件第六章.ppt》由会员分享，可在线阅读，更多相关《操作系统课件第六章.ppt（59页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、Operating SystemOperating System第六章第六章第六章第六章 文件管理文件管理文件管理文件管理q文件和文件系统文件和文件系统q文件的逻辑结构文件的逻辑结构q外存分配方式外存分配方式q目录管理目录管理q文件存储空间的管理文件存储空间的管理q文件共享与文件保护文件共享与文件保护q数据一致性控制数据一致性控制2/17/20231Operating SystemOperating System文件的逻辑结构文件的逻辑结构文件的逻辑结构文件的逻辑结构q文件逻辑结构的类型文件逻辑结构的类型q顺序文件顺序文件q索引文件索引文件q索引顺序文件索引顺序文件q直接文件和哈希文件直接文件
2、和哈希文件2/17/20232Operating SystemOperating System文件逻辑结构的类型文件逻辑结构的类型文件逻辑结构的类型文件逻辑结构的类型q文件组织的两种观点文件组织的两种观点v用用户户观观点点（逻逻辑辑结结构构）：研研究究的的是是用用户户思思维维中中的的抽抽象象文文件件，也也叫叫逻逻辑辑文文件件。其其目目的的是是为为用用户户提提供供一一种种结结构构清清晰晰、使使用用简简便便的的逻逻辑辑组组织织。用用户户按按此此去存储、检索和加工处理有关文件信息。去存储、检索和加工处理有关文件信息。v实实现现观观点点（物物理理结结构构）：研研究究的的是是存存储储在在物物理理设设备备
3、介介质质上上的的实实际际文文件件，即即物物理理文文件件。其其目目的的是是选选择择一一些些性性能能良良好好、设设备备利利用用率率高高的的物物理理结结构构。系系统按此和外部设备打交道，控制信息的传输。统按此和外部设备打交道，控制信息的传输。q对逻辑结构的要求对逻辑结构的要求v提高检索速度提高检索速度v便于修改便于修改v降低文件的存储费用降低文件的存储费用2/17/20233Operating SystemOperating System文件逻辑结构的类型文件逻辑结构的类型文件逻辑结构的类型文件逻辑结构的类型q有结构文件有结构文件记录式文件记录式文件v按记录长度分按记录长度分定长记录定长记录变长记录
4、变长记录v根据用户和系统管理需要分根据用户和系统管理需要分顺序文件顺序文件索引文件索引文件索引顺序文件索引顺序文件q无结构文件无结构文件v流式文件流式文件 其长度以字节为单位其长度以字节为单位v采用读写指针来指出下一个要访问的字符采用读写指针来指出下一个要访问的字符v如如 源程序、源程序、可执行文件、可执行文件、库函数库函数等等2/17/20234Operating SystemOperating System文件逻辑结构的类型文件逻辑结构的类型文件逻辑结构的类型文件逻辑结构的类型文件逻辑结构文件逻辑结构文件逻辑结构文件逻辑结构有结构文件有结构文件有结构文件有结构文件（记录式）（记录式）（记录
5、式）（记录式）无结构文件无结构文件无结构文件无结构文件（流式）（流式）（流式）（流式）定长记录定长记录定长记录定长记录变长记录变长记录变长记录变长记录顺序文件顺序文件顺序文件顺序文件索引文件索引文件索引文件索引文件索引顺序文件索引顺序文件索引顺序文件索引顺序文件2/17/20235Operating SystemOperating System文件逻辑结构的类型文件逻辑结构的类型 1.有结构文件有结构文件uu定长记录定长记录定长记录定长记录：文件中所有记录的文件中所有记录的长度都是相同长度都是相同长度都是相同长度都是相同的，所有记录中的，所有记录中的各数据项，都处在相同的位置，具有相同的顺序和
6、长度。的各数据项，都处在相同的位置，具有相同的顺序和长度。uu变长记录变长记录变长记录变长记录：指文件中各记录的指文件中各记录的长度不相同长度不相同长度不相同长度不相同。顺序文件顺序文件顺序文件顺序文件：由一系列记录按某种顺序排列所形成的文件，其由一系列记录按某种顺序排列所形成的文件，其中的记录通常是中的记录通常是定长记录定长记录定长记录定长记录。索引文件索引文件索引文件索引文件：当记录为当记录为变长记录变长记录变长记录变长记录时，通常为之建立一张索引表，时，通常为之建立一张索引表，并为每个记录设置一张表项，以加快对记录的检索速度。并为每个记录设置一张表项，以加快对记录的检索速度。索引顺序文件
7、索引顺序文件索引顺序文件索引顺序文件：是是上述上述上述上述2 2种文件的一个结合种文件的一个结合种文件的一个结合种文件的一个结合，它为文件建立，它为文件建立一张索引表，为每一组记录中的第一个记录设置一个表项。一张索引表，为每一组记录中的第一个记录设置一个表项。2/17/20236Operating SystemOperating System文件的逻辑结构文件的逻辑结构文件的逻辑结构文件的逻辑结构q文件逻辑结构的类型文件逻辑结构的类型q顺序文件顺序文件q索引文件索引文件q索引顺序文件索引顺序文件q直接文件和哈希文件直接文件和哈希文件2/17/20237Operating SystemOpera
8、ting System顺序文件顺序文件顺序文件顺序文件q逻辑记录的排序逻辑记录的排序v串结构串结构各记录之间的顺序与关键字无关各记录之间的顺序与关键字无关通常由时间来决定通常由时间来决定存在问题存在问题v顺序结构顺序结构文件中的所有记录按关键字文件中的所有记录按关键字(词词)排列排列记录号记录号学号学号姓名姓名性别性别出生时间出生时间11赵赵23钱钱34孙孙45李李56周周620吴吴2/17/20238Operating SystemOperating System顺序文件顺序文件顺序文件顺序文件q对对顺序文件顺序文件(Sequential File)的读的读/写操作写操作记录长度记录长度记录
9、记录起始地址起始地址2/17/20239Operating SystemOperating System顺序文件顺序文件顺序文件顺序文件q顺序文件的优缺点顺序文件的优缺点v优点优点结构简单，容易实现结构简单，容易实现顺序文件的最佳应用场合，是在对诸记录进行顺序文件的最佳应用场合，是在对诸记录进行批量存取批量存取时，即每次要读或写一大批记录时，即每次要读或写一大批记录只有顺序文件才能存储在磁带上，并能有效地只有顺序文件才能存储在磁带上，并能有效地工作工作v缺点缺点如果用户如果用户(程序程序)要求要求修改修改单个记录，单个记录，顺序文顺序文件所表现出来的件所表现出来的性能就可能很差性能就可能很差如
10、果想如果想增加或删除增加或删除一个记录，一个记录，都比较困难都比较困难（需（需移动移动大量数据）大量数据）创建文件必须给出大小，不利于动态增长创建文件必须给出大小，不利于动态增长2/17/202310Operating SystemOperating System文件的逻辑结构文件的逻辑结构文件的逻辑结构文件的逻辑结构q文件逻辑结构的类型文件逻辑结构的类型q顺序文件顺序文件q索引文件索引文件q索引顺序文件索引顺序文件q直接文件和哈希文件直接文件和哈希文件2/17/202311Operating SystemOperating System索引文件索引文件索引文件索引文件q对对定长记录定长记录文
11、件，如果要查找第文件，如果要查找第i个记录，个记录，可直接可直接根据下式计算来获得第根据下式计算来获得第i个记录相对于第一个记录个记录相对于第一个记录首址的地址首址的地址Ai=iLq对于对于可变长度记录可变长度记录的文件，要查找其第的文件，要查找其第i个记录时，个记录时，须首先计算出该记录的首地址，须首先计算出该记录的首地址，Li为第为第i个记录长个记录长度度2/17/202312Operating SystemOperating System索引文件索引文件索引文件索引文件索引文件的组织索引文件的组织 索引本身是一个定长记录的顺序文件，主文件中每个记录在索引本身是一个定长记录的顺序文件，主文
12、件中每个记录在索引表中占一个表项，可采用快速查找算法，如字典索引表中占一个表项，可采用快速查找算法，如字典2/17/202313Operating SystemOperating System2/17/202314Operating SystemOperating System索引文件索引文件 2、索引文件的检索步骤：、索引文件的检索步骤：（1）根据用户提供的关键字，利用折半查找法去检索索）根据用户提供的关键字，利用折半查找法去检索索引表，从中找到相应的表项；引表，从中找到相应的表项；（2）再利用该表项中给出的指向记录的指针值，去访问）再利用该表项中给出的指向记录的指针值，去访问所需记录。所需
13、记录。（3）要向索引文件中增加一个记录，便须对索引表进行）要向索引文件中增加一个记录，便须对索引表进行修改。修改。3、优点、优点 检索速度快，主要用于对信息处理的及时性要求较高检索速度快，主要用于对信息处理的及时性要求较高的场合。的场合。4、缺点、缺点 存储费用高，因为除了主文件外，还需配置一张索引存储费用高，因为除了主文件外，还需配置一张索引表，且每个记录都有一个索引项。表，且每个记录都有一个索引项。2/17/202315Operating SystemOperating System文件的逻辑结构文件的逻辑结构文件的逻辑结构文件的逻辑结构q文件逻辑结构的类型文件逻辑结构的类型q顺序文件顺序
14、文件q索引文件索引文件q索引顺序文件索引顺序文件q直接文件和哈希文件直接文件和哈希文件2/17/202316Operating SystemOperating System索引顺序文件索引顺序文件索引顺序文件索引顺序文件q索引顺序文件（索引顺序文件（Index Sequential File）是最是最常见的一种逻辑文件组织形式，是常见的一种逻辑文件组织形式，是顺序文件与索顺序文件与索引文件的结合引文件的结合q克服了变长记录文件不便于直接存取的缺点，代克服了变长记录文件不便于直接存取的缺点，代价也不太大价也不太大q将顺序文件中的所有记录分为若干个将顺序文件中的所有记录分为若干个组组，为，为每组每
15、组中的第一个记录中的第一个记录建立索引项，其中含有该记录的建立索引项，其中含有该记录的键值及指向该记录的指针键值及指向该记录的指针2/17/202317Operating SystemOperating System索引顺序文件索引顺序文件索引顺序文件索引顺序文件索引顺序文件索引顺序文件 2/17/202318Operating SystemOperating System2/17/202319Operating SystemOperating System文件检索速度文件检索速度文件检索速度文件检索速度q对顺序文件检索对顺序文件检索v若记录数据为若记录数据为N，则检索一条记录时，最好的情况，
16、则检索一条记录时，最好的情况是第一条记录即为所求；最坏的情况是最后一条记是第一条记录即为所求；最坏的情况是最后一条记录为所求；平均检索录为所求；平均检索N/2条记录条记录q对索引文件检索对索引文件检索v可采用折半查找等方法，平均查找可采用折半查找等方法，平均查找 条记录条记录q对索引顺序文件检索对索引顺序文件检索v索引文件与顺序文件的结合索引文件与顺序文件的结合键值键值150100252012.52/17/202320Operating SystemOperating System索引顺序文件索引顺序文件 qq将顺序文件中若干记录分为一组，每组的第一项在索将顺序文件中若干记录分为一组，每组的第
17、一项在索将顺序文件中若干记录分为一组，每组的第一项在索将顺序文件中若干记录分为一组，每组的第一项在索引表中占一项。引表中占一项。引表中占一项。引表中占一项。qq速度：速度：速度：速度：qq例例例例1 1 1 1：10000100001000010000个记录，顺序文件：个记录，顺序文件：个记录，顺序文件：个记录，顺序文件：5000500050005000次查找查到。次查找查到。次查找查到。次查找查到。vv索引顺序文件，设索引顺序文件，设索引顺序文件，设索引顺序文件，设100100100100个记录一组，索引表的找法设为顺序法个记录一组，索引表的找法设为顺序法个记录一组，索引表的找法设为顺序法个
18、记录一组，索引表的找法设为顺序法的情况下，则查找次数为的情况下，则查找次数为的情况下，则查找次数为的情况下，则查找次数为50+50=10050+50=10050+50=10050+50=100。qq例例例例2 2 2 2：1000000100000010000001000000个纪录：个纪录：个纪录：个纪录：qq低级索引：（低级索引：（低级索引：（低级索引：（100100100100个纪录一组）：个纪录一组）：个纪录一组）：个纪录一组）：10000100001000010000。qq高级索引：高级索引：高级索引：高级索引：100100100100vv速度：速度：速度：速度：100+50=150
19、100+50=150100+50=150100+50=1502/17/202321Operating SystemOperating System第六章第六章第六章第六章 文件管理文件管理文件管理文件管理q文件和文件系统文件和文件系统q文件的逻辑结构文件的逻辑结构q外存分配方式外存分配方式q目录管理目录管理q文件存储空间的管理文件存储空间的管理q文件共享与文件保护文件共享与文件保护q数据一致性控制数据一致性控制2/17/202322Operating SystemOperating System6.3 外存分配方式外存分配方式 对于任何一个文件，都存在着以下两种形式的结构：对于任何一个文件，都
20、存在着以下两种形式的结构：(1)文件的文件的逻辑结构逻辑结构逻辑结构逻辑结构(File Logical Structure)。(2)文件的文件的物理结构物理结构物理结构物理结构，又称为文件的存储结构，又称为文件的存储结构，是指文件是指文件在外存上的存储组织形式。在外存上的存储组织形式。2/17/202323Operating SystemOperating System外存分配方式外存分配方式外存分配方式外存分配方式如何才能有效地利用外存空间如何才能有效地利用外存空间?如何提高对文件的访问速度如何提高对文件的访问速度?2/17/202324Operating SystemOperating S
21、ystem文件的物理结构文件的物理结构文件的物理结构文件的物理结构q外存的特点外存的特点v容量大，断电后仍可保存信息，速度较慢，容量大，断电后仍可保存信息，速度较慢，成本较低成本较低v两部分组成：驱动部分两部分组成：驱动部分+存储介质存储介质v种类很多种类很多v外存空间组织与地址与存取方式非常复杂外存空间组织与地址与存取方式非常复杂vI/O过程方式非常复杂过程方式非常复杂2/17/202325Operating SystemOperating System文件的物理结构文件的物理结构文件的物理结构文件的物理结构q用户对外存的要求用户对外存的要求v使用：读写外存数据使用：读写外存数据v要求：方便
22、、效率、安全要求：方便、效率、安全q在读写外存时不涉及硬件细节，使用逻辑地址在读写外存时不涉及硬件细节，使用逻辑地址和逻辑操作和逻辑操作q存取速度尽可能快，容量大且空间利用率高存取速度尽可能快，容量大且空间利用率高q外存上存放的信息安全可靠，防止来自硬件的外存上存放的信息安全可靠，防止来自硬件的故障和他人的侵权故障和他人的侵权q方便地共享，动态扩缩，携带拆卸，了解存储方便地共享，动态扩缩，携带拆卸，了解存储情况和使用情况情况和使用情况q以尽可能小的代价完成上述要求以尽可能小的代价完成上述要求2/17/202326Operating SystemOperating System文件的物理结构文件
23、的物理结构文件的物理结构文件的物理结构q文件的物理结构是指逻辑文件文件的物理结构是指逻辑文件在存储设备在存储设备（外存）（外存）上的上的存储组织形式存储组织形式，它与存储介质的存储特性有，它与存储介质的存储特性有关关q一一个个文文件件存存储储介介质质，格格式式化化后后就就分分成成许许多多大大小小相相等等的的单单位位存存储储块块（物物理理盘盘块块），一一般般来来说说，每每个个物物理理块块是是一一个个磁磁盘盘的的扇扇区区，512B。并并给给每每个存储块有个编号，称为物理块号个存储块有个编号，称为物理块号q物理块是物理块是分配和传输分配和传输信息的信息的基本单位基本单位，其与外存，其与外存设备有关，
24、但与逻辑记录大小无关，如设备有关，但与逻辑记录大小无关，如扇区、簇扇区、簇q文件在逻辑上都可看作是连续的，但在物理设备文件在逻辑上都可看作是连续的，但在物理设备上存放时却有不同的方式，如上存放时却有不同的方式，如连续结构（顺序结连续结构（顺序结构）、链接结构（串联结构）、索引结构、构）、链接结构（串联结构）、索引结构、HASH文件文件等等2/17/202327Operating SystemOperating System按文件的物理结构分类按文件的物理结构分类按文件的物理结构分类按文件的物理结构分类（1）顺序文件顺序文件顺序文件顺序文件。它是指把逻辑文件中的记录顺序地存储到它是指把逻辑文件中
25、的记录顺序地存储到连续的物理盘块中。连续的物理盘块中。（2）链接文件链接文件链接文件链接文件。它是指文件中的各个记录可以存放在不相它是指文件中的各个记录可以存放在不相邻接的各个物理盘块中，通过物理块中的链接指针，将它邻接的各个物理盘块中，通过物理块中的链接指针，将它们连接成一个链表。们连接成一个链表。（3）索引文件索引文件索引文件索引文件。它是指文件中的各个记录可存储在不相邻它是指文件中的各个记录可存储在不相邻接的各个物理块中。接的各个物理块中。2/17/202328Operating SystemOperating System外存分配方式外存分配方式外存分配方式外存分配方式q连续分配连续分
26、配q链接分配链接分配q索引分配索引分配2/17/202329Operating SystemOperating System连续分配连续分配连续分配连续分配q连续分配连续分配(Continuous Allocation)要求为每一要求为每一个文件分配个文件分配一组相邻接的盘块一组相邻接的盘块。一组盘块定义。一组盘块定义了磁盘上的一段线性地址了磁盘上的一段线性地址q在采用连续分配方式时，可把逻辑文件中的记在采用连续分配方式时，可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中，这样所录顺序地存储到邻接的各物理盘块中，这样所形成的文件结构称为形成的文件结构称为顺序文件结构顺序文件结构，此时的物，此
27、时的物理文件称为理文件称为顺序文件顺序文件2/17/202330Operating SystemOperating System连续分配连续分配连续分配连续分配2/17/202331Operating SystemOperating System连续分配连续分配连续分配连续分配q连续分配的主要优缺点连续分配的主要优缺点v优点优点结构简单，容易实现结构简单，容易实现支持顺序存取和随机存取支持顺序存取和随机存取顺序存取速度快顺序存取速度快所需的磁盘寻道次数和寻道时间最少所需的磁盘寻道次数和寻道时间最少v缺点缺点要求有连续的存储空间，不利于动态扩充要求有连续的存储空间，不利于动态扩充容易形成容易形成
28、碎片，空间利用不充分碎片，空间利用不充分必须事先知道文件的长度，用户不方便必须事先知道文件的长度，用户不方便2/17/202332Operating SystemOperating System外存分配方式外存分配方式外存分配方式外存分配方式q连续分配连续分配q链接分配链接分配q索引分配索引分配2/17/202333Operating SystemOperating System链接分配链接分配链接分配链接分配q链接分配（链接分配（Chained Allocation）v可通过在每个盘块上的链接指针，将同属于一可通过在每个盘块上的链接指针，将同属于一个文件的多个个文件的多个离散的离散的盘块链接
29、成一个盘块链接成一个链表链表，把，把这样形成的物理文件称为这样形成的物理文件称为链接文件链接文件q这种文件结构这种文件结构不要求连续存放不要求连续存放q对于记录式文件一块中可包含一个逻辑记录或多对于记录式文件一块中可包含一个逻辑记录或多个逻辑记录，也可以若干物理块包含一个逻辑记个逻辑记录，也可以若干物理块包含一个逻辑记录录q链接方式链接方式v隐式链接隐式链接v显式链接显式链接2/17/202334Operating SystemOperating System链接分配链接分配链接分配链接分配q隐式链接隐式链接文件名文件名 始址始址 末址末址jeep 9 25文件目录文件目录0123456789
30、1011121314151617181920212223242526272829303111016-125磁盘空间的链接式分配磁盘空间的链接式分配2/17/202335Operating SystemOperating System链接分配链接分配链接分配链接分配q隐式链接隐式链接v每个物理块的最末一个字每个物理块的最末一个字(或第一个字或第一个字)作为链作为链接字，它指出后继块的物理地址。链首指针存接字，它指出后继块的物理地址。链首指针存放在该文件目录中。文件的结尾块的指针为放在该文件目录中。文件的结尾块的指针为“”v优点优点离散存储，空间利用率高离散存储，空间利用率高顺序存取效率高顺序存取
31、效率高v缺点缺点随机存取效率太低，若要访问第随机存取效率太低，若要访问第i个物理块，个物理块，必须读出前必须读出前i-1个个2/17/202336Operating SystemOperating System链接分配链接分配链接分配链接分配q显式链接显式链接v为了克服链接文件的存取效率太低的问题，人为了克服链接文件的存取效率太低的问题，人们提出们提出文件映照的技术文件映照的技术，即把链接文件中的链，即把链接文件中的链接字集中在一结构中，接字集中在一结构中，这样既保持了链接文件这样既保持了链接文件的优点，也克服了其缺点的优点，也克服了其缺点，DOS、WINDOWS系统就采用了这样结构系统就采用
32、了这样结构q文件分配表（文件分配表（File Allocation Table,FAT）2/17/202337Operating SystemOperating System链接分配链接分配链接分配链接分配q文件分配表（文件分配表（File Allocation Table,FAT）v磁磁盘盘格格式式化化后后建建立立，从从磁磁盘盘的的第第二二个个开开始始，有两个相同的有两个相同的FATv用于记录外存分配状况，每个盘块（或簇）用于记录外存分配状况，每个盘块（或簇）占一项，放在内存中，整个系统一张占一项，放在内存中，整个系统一张FATv表的序号为物理盘块号或簇号，从表的序号为物理盘块号或簇号，从0
33、至至N-1v分配给一个文件的所有物理块都在该表中标分配给一个文件的所有物理块都在该表中标出，文件的第一个盘块号记入文件的出，文件的第一个盘块号记入文件的FCB中中2/17/202338Operating SystemOperating System链接分配链接分配链接分配链接分配q显式链接显式链接2/17/202339Operating SystemOperating System链接分配链接分配链接分配链接分配q显式链接显式链接v在在FAT中每个物理块占一个表项，增加中每个物理块占一个表项，增加一个指针指向下一个物理块，最末一个一个指针指向下一个物理块，最末一个物理块的指针为物理块的指针为“
34、”2/17/202340Operating SystemOperating System链接分配链接分配链接分配链接分配2/17/202341Operating SystemOperating SystemDOSDOSDOSDOS磁盘访问操作流程磁盘访问操作流程磁盘访问操作流程磁盘访问操作流程文件名文件名文件名文件名磁盘目录表磁盘目录表磁盘目录表磁盘目录表FDTFDTFDTFDT磁盘参数表磁盘参数表磁盘参数表磁盘参数表文件位置分配文件位置分配文件位置分配文件位置分配表表表表FATFATFATFAT磁盘扇区磁盘扇区磁盘扇区磁盘扇区定位定位定位定位扇区物理扇区物理扇区物理扇区物理操作操作操作操作磁
35、盘基数表磁盘基数表磁盘基数表磁盘基数表2/17/202342Operating SystemOperating System链接分配链接分配链接分配链接分配q实例实例v对于对于1.2M磁盘，每个物理块大小为磁盘，每个物理块大小为1KB，则共有则共有1.2K个个FAT表项，若每个表项占表项，若每个表项占12位位（1.5B），则共需），则共需1.8KB的空间来保存的空间来保存FAT。q显式链接分配显式链接分配v优点优点便于快速查找便于快速查找v缺点缺点FAT很大，需较大的内存空间很大，需较大的内存空间2/17/202343Operating SystemOperating System链接分配链接
36、分配链接分配链接分配q主要优缺点主要优缺点v优点优点消除了外部碎片，提高外存利用率消除了外部碎片，提高外存利用率文件动态增长时，可动态地为它分配盘块文件动态增长时，可动态地为它分配盘块文件的增删改方便，不需事先知道文件长文件的增删改方便，不需事先知道文件长v缺点缺点存取速度慢存取速度慢只适于只适于顺序存取顺序存取，不适于随机存取不适于随机存取可靠性差，若某一块可靠性差，若某一块指针指针出错，则链断开出错，则链断开更多的寻道次数和寻道时间更多的寻道次数和寻道时间链接指针占用一定的空间链接指针占用一定的空间2/17/202344Operating SystemOperating System外存分
37、配方式外存分配方式外存分配方式外存分配方式q连续分配连续分配q链接分配链接分配q索引分配索引分配2/17/202345Operating SystemOperating System索引分配索引分配索引分配索引分配q一个文件的信息存放在若干不连续物理块中，另一个文件的信息存放在若干不连续物理块中，另一种形式的非连续文件，文件数据存放的存储介一种形式的非连续文件，文件数据存放的存储介质上的物理块号与文件的逻辑块号一一对应，系质上的物理块号与文件的逻辑块号一一对应，系统为这样对应关系统为这样对应关系建立一个专用建立一个专用数据结构数据结构-索引索引表表q索引表：一个文件所有记录的关键字和其它地址索
38、引表：一个文件所有记录的关键字和其它地址的对照表的对照表q一个索引表就是磁盘块地址数组一个索引表就是磁盘块地址数组,其中第其中第i i个条目个条目指向文件的第指向文件的第i i块块2/17/202346Operating SystemOperating System索引分配索引分配索引分配索引分配q单级索引分配单级索引分配v链接分配存在的问题链接分配存在的问题不能支持高效的直接存取不能支持高效的直接存取，要对一个，要对一个较大的文较大的文件件进行进行直接存取直接存取，须首先在，须首先在FAT中顺序地查找中顺序地查找许多盘块号。许多盘块号。FAT需需占用较大占用较大的的内存内存空间空间v索引分配
39、索引分配为为每个文件分配一个索引块每个文件分配一个索引块，把分配给该文件，把分配给该文件的所有盘块号都记录在该索引块中的所有盘块号都记录在该索引块中在建立一个文件时，便为之建立的目录项中填在建立一个文件时，便为之建立的目录项中填上指向该索引块的指针上指向该索引块的指针v支持直接访问支持直接访问对于大文件而言，该方式优于链式分配方式对于大文件而言，该方式优于链式分配方式2/17/202347Operating SystemOperating System索引分配索引分配索引分配索引分配012345678910111213141516171819202122232425262728293031文件
40、名文件名 索引表地址索引表地址文件目录文件目录Jeep 19 916 11025-1-1-1192/17/202348Operating SystemOperating System索引分配索引分配索引分配索引分配q若每个盘块大小为若每个盘块大小为1KB，每个盘块号占，每个盘块号占4B，则索引块中可存放则索引块中可存放256个盘块号，即采用这种个盘块号，即采用这种索引方式时每个文件索引方式时每个文件大小不能大小不能超过超过256KBq索引表组织索引表组织v链接模式链接模式:一个盘块一个索引表一个盘块一个索引表,多个索引多个索引表链接起来表链接起来v多级索引多级索引:将一个大文件的所有索引表（二
41、将一个大文件的所有索引表（二级索引级索引)的地址放在另一个索引表（一级索的地址放在另一个索引表（一级索引引)中中2/17/202349Operating SystemOperating System索引分配索引分配索引分配索引分配q多级索引分配多级索引分配2/17/202350Operating SystemOperating System索引分配索引分配索引分配索引分配q若每个盘块大小为若每个盘块大小为1KB，每个盘块号占，每个盘块号占4B，则一，则一级索引块中可存放级索引块中可存放256个盘块号，即对应个盘块号，即对应256个个二级索引块二级索引块q每个二级索引块可对应每个二级索引块可对应
42、256个物理磁盘块，采用个物理磁盘块，采用这种索引方式时每个文件大小不能超过这种索引方式时每个文件大小不能超过256*256*1KB=64MBq若每个盘块大小为若每个盘块大小为4K，则最大文件大小为，则最大文件大小为1K*1K*4K=4GB2/17/202351Operating SystemOperating System混合索引分配混合索引分配混合索引分配混合索引分配直接地址物理盘块索引块2/17/202352Operating SystemOperating System混合索引分配混合索引分配混合索引分配混合索引分配q直接地址直接地址v为了提高对文件的检索速度，为了提高对文件的检索速度
43、，在索引结点中可在索引结点中可设置设置10个直接地址项，个直接地址项，即用即用iaddr(0)iaddr(9)来存放直接地址来存放直接地址q一次间接地址一次间接地址v对于大、对于大、中型文件，可再利用索引结点中的地中型文件，可再利用索引结点中的地址项址项iaddr(10)来提供一次间接地址。这种方式来提供一次间接地址。这种方式的实质就是一级索引分配方式的实质就是一级索引分配方式q多次间接地址多次间接地址v当文件长度大于当文件长度大于4 MB+40 KB时时(一次间址与一次间址与10个直接地址项个直接地址项)，系统还须采用二次间址分配系统还须采用二次间址分配方式。这时，用地址项方式。这时，用地址
44、项iaddr(11)提供二次间接提供二次间接地址。该方式的实质是两级索引分配方式地址。该方式的实质是两级索引分配方式2/17/202353Operating SystemOperating System索引分配索引分配索引分配索引分配qUNIX系统采用索引文件结构，系统采用索引文件结构，UNIXUNIX系统采用多系统采用多级间接索引结构，对小型文件采用直接索引，对级间接索引结构，对小型文件采用直接索引，对大型文件采用间接索引，从而，既保证绝大多数大型文件采用间接索引，从而，既保证绝大多数的文件有高的存取效率，又能适应存取一些大型的文件有高的存取效率，又能适应存取一些大型文件。（既保证了文件系统
45、的高效率，又使其有文件。（既保证了文件系统的高效率，又使其有很宽的适应面）很宽的适应面）2/17/202354Operating SystemOperating System2/17/202355Operating SystemOperating System例题：例题：例题：例题：设文件索引结点中有设文件索引结点中有7个地址项，其中，个地址项，其中，4个地址个地址为直接地址索引，为直接地址索引，2个地址是一级间接地址索引个地址是一级间接地址索引,1个地址是二级间接地址索引，每个地址项的大个地址是二级间接地址索引，每个地址项的大小为何小为何4B，若磁盘索引块的磁盘数据块大小写均，若磁盘索引块的
46、磁盘数据块大小写均为为256B，则表示的单个文件最大长度是，则表示的单个文件最大长度是_.2/17/202356Operating SystemOperating System索引分配索引分配索引分配索引分配q索引结构优缺点索引结构优缺点v优点：优点：保持了链接结构的优点保持了链接结构的优点,又解决了其缺又解决了其缺点：即能顺序存取点：即能顺序存取,又能随机存取，满足了又能随机存取，满足了文件动态增长、插入删除的要求，也能充分文件动态增长、插入删除的要求，也能充分利用外存空间利用外存空间v缺点：缺点：较多的寻道次数和寻道时间，索引表较多的寻道次数和寻道时间，索引表本身带来了系统开销，如：内外存
47、空间，存本身带来了系统开销，如：内外存空间，存取时间取时间2/17/202357Operating SystemOperating System索引分配索引分配索引分配索引分配q索引分配的主要问题索引分配的主要问题v需要较多外存空间来建立索引块需要较多外存空间来建立索引块v对于小文件，空间浪费严重对于小文件，空间浪费严重2/17/202358Operating SystemOperating System文件物理结构的比较文件物理结构的比较文件物理结构的比较文件物理结构的比较q连连续续文文件件的的优优点点是是不不需需要要额额外外的的空空间间开开销销，只只要要在在文文件件目目录录中中指指出出文文
48、件件的的大大小小和和首首块块的的块块号号即即可可，对对顺顺序序的的访访问问效效率率很很高高。适适应应于于顺顺序序存存取取。缺缺点点是是动动态态地地增增长长和和缩缩小小系系统统开开销销很很大大；文文件件创创建建时时要求用户提供文件的大小；存储空间浪费较大。要求用户提供文件的大小；存储空间浪费较大。q链链式式文文件件克克服服了了连连续续文文件件的的不不足足之之处处，但但文文件件的的随随机机访访问问系系统统开开销销较较大大。适适应应于于顺顺序序访访问问。DOS系系统统中中改改造造了了链链式式文文件件的的结结构构，使使其其克克服服了链式文件的不足，但增加了系统的危险性。了链式文件的不足，但增加了系统的危险性。2/17/202359