操作系统课件第六章3综述

1、Operating SystemOperating SystemPage 12021-10-15Operating SystemOperating Systemq文件和文件系统文件和文件系统q文件的逻辑结构文件的逻辑结构q外存分配方式外存分配方式q目录管理目录管理q文件存储空间的管理文件存储空间的管理q文件共享与文件保护文件共享与文件保护q数据一致性控制数据一致性控制Page 22021-10-15Operating SystemOperating System6.3 外存分配方式外存分配方式 对于任何一个文件，都存在着以下两种形式的结构：对于任何一个文件，都存在着以下两种形式的结构： (1)

2、 文件的文件的(File Logical Structure)。 (2) 文件的文件的， 又称为文件的存储结构，又称为文件的存储结构， 是指文件是指文件在外存上的存储组织形式。在外存上的存储组织形式。 Page 32021-10-15Operating SystemOperating System如何才能有效地利用外存空间如何才能有效地利用外存空间?如何提高对文件的访问速度如何提高对文件的访问速度?Page 42021-10-15Operating SystemOperating Systemq外存的特点外存的特点v容量大，断电后仍可保存信息，速度较慢，容量大，断电后仍可保存信息，速度较慢，成

3、本较低成本较低v两部分组成：驱动部分两部分组成：驱动部分+ +存储介质存储介质v种类很多种类很多v外存空间组织与地址与存取方式非常复杂外存空间组织与地址与存取方式非常复杂vI/O过程方式非常复杂过程方式非常复杂Page 52021-10-15Operating SystemOperating Systemq用户对外存的要求用户对外存的要求v使用：读写外存数据使用：读写外存数据v要求：方便、效率、安全要求：方便、效率、安全q在读写外存时不涉及硬件细节，使用逻辑地址在读写外存时不涉及硬件细节，使用逻辑地址和逻辑操作和逻辑操作q存取速度尽可能快，容量大且空间利用率高存取速度尽可能快，容量大且空间利用

4、率高q外存上存放的信息安全可靠，防止来自硬件的外存上存放的信息安全可靠，防止来自硬件的故障和他人的侵权故障和他人的侵权q方便地共享，动态扩缩，携带拆卸，了解存储方便地共享，动态扩缩，携带拆卸，了解存储情况和使用情况情况和使用情况q以尽可能小的代价完成上述要求以尽可能小的代价完成上述要求Page 62021-10-15Operating SystemOperating Systemq文件的物理结构是指逻辑文件文件的物理结构是指逻辑文件在存储设备在存储设备（外存）（外存）上的上的存储组织形式存储组织形式，它与存储介质的存储特性有，它与存储介质的存储特性有关关q一个文件存储介质，格式化后就分成许多大

5、小相一个文件存储介质，格式化后就分成许多大小相等的单位等的单位存储块（物理盘块），一般来说，存储块（物理盘块），一般来说，每个物理块是一个磁盘的扇区，每个物理块是一个磁盘的扇区，512B。并给每。并给每个存储块有个编号，称为物理块号个存储块有个编号，称为物理块号q物理块是物理块是分配和传输分配和传输信息的信息的基本单位基本单位，其与外存，其与外存设备有关，但与逻辑记录大小无关，如设备有关，但与逻辑记录大小无关，如扇区、簇扇区、簇q文件在逻辑上都可看作是连续的，但在物理设备文件在逻辑上都可看作是连续的，但在物理设备上存放时却有不同的方式，如上存放时却有不同的方式，如连续结构（顺序结连续结构（顺序

6、结构）、链接结构（串联结构）、索引结构、构）、链接结构（串联结构）、索引结构、HASH文件文件等等Page 72021-10-15Operating SystemOperating System6.1.2 文件类型和文件系统模型文件类型和文件系统模型 1. 文件类型文件类型 （1）。它是指把逻辑文件中的记录顺序地存储到它是指把逻辑文件中的记录顺序地存储到连续的物理盘块中。连续的物理盘块中。（2）。它是指文件中的各个记录可以存放在不相它是指文件中的各个记录可以存放在不相邻接的各个物理盘块中，通过物理块中的链接指针，将它邻接的各个物理盘块中，通过物理块中的链接指针，将它们连接成一个链表。们连接成一

7、个链表。（3）。它是指文件中的各个记录可存储在不相邻它是指文件中的各个记录可存储在不相邻接的各个物理块中。接的各个物理块中。Page 82021-10-15Operating SystemOperating Systemq连续分配连续分配q链接分配链接分配q索引分配索引分配Page 92021-10-15Operating SystemOperating Systemq连续分配连续分配(Continuous Allocation)要求为每要求为每一个文件分配一个文件分配一组相邻接的盘块一组相邻接的盘块。一组盘块定。一组盘块定义了磁盘上的一段线性地址义了磁盘上的一段线性地址q在采用连续分配方式时

8、，可把逻辑文件中的记在采用连续分配方式时，可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中，这样所录顺序地存储到邻接的各物理盘块中，这样所形成的文件结构称为形成的文件结构称为顺序文件结构顺序文件结构，此时的物，此时的物理文件称为理文件称为顺序文件顺序文件Page 102021-10-15Operating SystemOperating System1230567491011813141512171819162122232025262724list29303128mailcountfilestartlengthcount02tr143mail196list284f62目 录trfPage 1

9、12021-10-15Operating SystemOperating Systemq 连续分配的主要优缺点连续分配的主要优缺点v优点优点结构简单，容易实现结构简单，容易实现支持顺序存取和随机存取支持顺序存取和随机存取顺序存取速度快顺序存取速度快所需的磁盘寻道次数和寻道时间最少所需的磁盘寻道次数和寻道时间最少v缺点缺点要求有连续的存储空间，不利于动态扩充要求有连续的存储空间，不利于动态扩充容易形成容易形成碎片，空间利用不充分碎片，空间利用不充分必须事先知道文件的长度，用户不方便必须事先知道文件的长度，用户不方便Page 122021-10-15Operating SystemOperatin

10、g Systemq连续分配连续分配q链接分配链接分配q索引分配索引分配Page 132021-10-15Operating SystemOperating Systemq链接分配（链接分配（Chained Allocation）v可通过在每个盘块上的链接指针，将同属于一可通过在每个盘块上的链接指针，将同属于一个文件的多个个文件的多个离散的离散的盘块链接成一个盘块链接成一个链表链表，把，把这样形成的物理文件称为这样形成的物理文件称为链接文件链接文件q这种文件结构这种文件结构不要求连续存放不要求连续存放q对于记录式文件一块中可包含一个逻辑记录或多对于记录式文件一块中可包含一个逻辑记录或多个逻辑记录

11、，也可以若干物理块包含一个逻辑记个逻辑记录，也可以若干物理块包含一个逻辑记录录q链接方式链接方式v隐式链接隐式链接v显式链接显式链接Page 142021-10-15Operating SystemOperating Systemq隐式链接隐式链接文件名文件名 始址始址 末址末址jeep 9 25文件目录文件目录01234567891011121314151617181920212223242526272829303111016-125磁盘空间的链接式分配磁盘空间的链接式分配Page 152021-10-15Operating SystemOperating Systemq隐式链接隐式链接v每

12、个物理块的最末一个字每个物理块的最末一个字(或第一个字或第一个字)作为链作为链接字，它指出后继块的物理地址。链首指针存接字，它指出后继块的物理地址。链首指针存放在该文件目录中。文件的结尾块的指针为放在该文件目录中。文件的结尾块的指针为“”v优点优点离散存储，空间利用率高离散存储，空间利用率高顺序存取效率高顺序存取效率高v缺点缺点随机存取效率太低，若要访问第随机存取效率太低，若要访问第i个物理块，个物理块，必须读出前必须读出前i-1个个Page 162021-10-15Operating SystemOperating Systemq显式链接显式链接v为了克服链接文件的存取效率太低的问题，人为了

13、克服链接文件的存取效率太低的问题，人们提出们提出文件映照的技术文件映照的技术，即把链接文件中的链，即把链接文件中的链接字集中在一结构中，接字集中在一结构中，这样既保持了链接文件这样既保持了链接文件的优点，也克服了其缺点的优点，也克服了其缺点，DOS、WINDOWS系统就采用了这样结构系统就采用了这样结构q文件分配表（文件分配表（File Allocation Table, FAT）Page 172021-10-15Operating SystemOperating Systemq文件分配表（文件分配表（File Allocation Table, FAT）v磁盘格式化后建立，从磁盘的第二个开始

14、，磁盘格式化后建立，从磁盘的第二个开始，有两个相同的有两个相同的FATv用于记录外存分配状况，每个盘块（或簇）用于记录外存分配状况，每个盘块（或簇）占一项，放在内存中，整个系统一张占一项，放在内存中，整个系统一张FATv表的序号为物理盘块号或簇号，从表的序号为物理盘块号或簇号，从0至至N-1v分配给一个文件的所有物理块都在该表中标分配给一个文件的所有物理块都在该表中标出，文件的第一个盘块号记入文件的出，文件的第一个盘块号记入文件的FCB中中Page 182021-10-15Operating SystemOperating Systemq显式链接显式链接012345物理块号物理块号2FCBFA

15、T0451Page 192021-10-15Operating SystemOperating Systemq显式链接显式链接v在在FAT中每个物理块占一个表项，增加中每个物理块占一个表项，增加一个指针指向下一个物理块，最末一个一个指针指向下一个物理块，最末一个物理块的指针为物理块的指针为“”Page 202021-10-15Operating SystemOperating System6EOF11105EOF0123456789FATFCB A4FCB B9Page 212021-10-15Operating SystemOperating SystemPage 222021-10-15O

16、perating SystemOperating SystemPage 232021-10-15Operating SystemOperating Systemq实例实例v对于对于1.2M磁盘，每个物理块大小为磁盘，每个物理块大小为1KB，则共有则共有1.2K个个FAT表项，若每个表项占表项，若每个表项占12位（位（1.5B），则共需），则共需1.8KB的空间来保存的空间来保存FAT。q显式链接分配显式链接分配v优点优点便于快速查找便于快速查找v缺点缺点FAT很大，需较大的内存空间很大，需较大的内存空间Page 242021-10-15Operating SystemOperating Sys

17、temq主要优缺点主要优缺点v优点优点消除了外部碎片，提高外存利用率消除了外部碎片，提高外存利用率文件动态增长时，可动态地为它分配盘块文件动态增长时，可动态地为它分配盘块文件的增删改方便，不需事先知道文件长文件的增删改方便，不需事先知道文件长v缺点缺点存取速度慢存取速度慢只适于只适于顺序存取顺序存取，不适于随机存取不适于随机存取可靠性差，若某一块可靠性差，若某一块指针指针出错，则链断开出错，则链断开更多的寻道次数和寻道时间更多的寻道次数和寻道时间链接指针占用一定的空间链接指针占用一定的空间Page 252021-10-15Operating SystemOperating Systemq连续分

18、配连续分配q链接分配链接分配q索引分配索引分配Page 262021-10-15Operating SystemOperating Systemq一个文件的信息存放在若干不连续物理块中，另一个文件的信息存放在若干不连续物理块中，另一种形式的非连续文件，文件数据存放的存储介一种形式的非连续文件，文件数据存放的存储介质上的物理块号与文件的逻辑块号一一对应，系质上的物理块号与文件的逻辑块号一一对应，系统为这样对应关系统为这样对应关系建立一个专用建立一个专用数据结构数据结构-索引索引表表q索引表：一个文件所有记录的关键字和其它地址索引表：一个文件所有记录的关键字和其它地址的对照表的对照表q一个索引表就

19、是磁盘块地址数组一个索引表就是磁盘块地址数组, ,其中第其中第i i个条目个条目指向文件的第指向文件的第i i块块Page 272021-10-15Operating SystemOperating Systemq单级索引分配单级索引分配v链接分配存在的问题链接分配存在的问题不能支持高效的直接存取不能支持高效的直接存取，要对一个，要对一个较大的文较大的文件件进行进行直接存取直接存取，须首先在，须首先在FAT中顺序地查找中顺序地查找许多盘块号。许多盘块号。FAT需需占用较大占用较大的的内存内存空间空间v索引分配索引分配为为每个文件分配一个索引块每个文件分配一个索引块，把分配给该文件，把分配给该文

20、件的所有盘块号都记录在该索引块中的所有盘块号都记录在该索引块中在建立一个文件时，便为之建立的目录项中填在建立一个文件时，便为之建立的目录项中填上指向该索引块的指针上指向该索引块的指针v支持直接访问支持直接访问对于大文件而言，该方式优于链式分配方式对于大文件而言，该方式优于链式分配方式Page 282021-10-15Operating SystemOperating System012345678910111213141516171819202122232425262728293031文件名文件名 索引表地址索引表地址文件目录文件目录Jeep 19 916 11025 -1 -1 -119Pa

21、ge 292021-10-15Operating SystemOperating Systemq若每个盘块大小为若每个盘块大小为1KB，每个盘块号占，每个盘块号占4B，则索引块中可存放则索引块中可存放256个盘块号，即采用这种个盘块号，即采用这种索引方式时每个文件索引方式时每个文件大小不能大小不能超过超过256KBq索引表组织索引表组织v链接模式链接模式: :一个盘块一个索引表一个盘块一个索引表, ,多个索引多个索引表链接起来表链接起来v多级索引多级索引: :将一个大文件的所有索引表（二将一个大文件的所有索引表（二级索引级索引) )的地址放在另一个索引表（一级索的地址放在另一个索引表（一级索引

22、引) )中中Page 302021-10-15Operating SystemOperating Systemq多级索引分配多级索引分配012-105106254356357985105106254740356357-1125985360740-1125-主索引主索引360第二级索引第二级索引磁盘空间磁盘空间Page 312021-10-15Operating SystemOperating Systemq若每个盘块大小为若每个盘块大小为1KB，每个盘块号占，每个盘块号占4B，则一，则一级索引块中可存放级索引块中可存放256个盘块号，即对应个盘块号，即对应256个个二级索引块二级索引块q每个二

23、级索引块可对应每个二级索引块可对应256个物理磁盘块，采用个物理磁盘块，采用这种索引方式时每个文件大小不能超过这种索引方式时每个文件大小不能超过256*256*1KB=64MBq若每个盘块大小为若每个盘块大小为4K，则最大文件大小为，则最大文件大小为1K*1K*4K=4GBPage 322021-10-15Operating SystemOperating Systemmodeowners (2)time stamps (3)sizeblock counti.addr (0)i.addr (1)direct blockssingle indirectdouble indirecttriple

24、indirectdatadatadatadata-datadata-datadatadatadata直接地址物理盘块索引块Page 332021-10-15Operating SystemOperating Systemq直接地址直接地址v为了提高对文件的检索速度，为了提高对文件的检索速度， 在索引结点中可在索引结点中可设置设置10个直接地址项，个直接地址项， 即用即用iaddr(0)iaddr(9)来存放直接地址来存放直接地址q一次间接地址一次间接地址v对于大、对于大、 中型文件，可再利用索引结点中的地中型文件，可再利用索引结点中的地址项址项iaddr(10)来提供一次间接地址。这种方式来提

25、供一次间接地址。这种方式的实质就是一级索引分配方式的实质就是一级索引分配方式q多次间接地址多次间接地址v当文件长度大于当文件长度大于4 MB+40 KB时时(一次间址与一次间址与10个直接地址项个直接地址项)， 系统还须采用二次间址分配系统还须采用二次间址分配方式。这时，用地址项方式。这时，用地址项iaddr(11)提供二次间接提供二次间接地址。该方式的实质是两级索引分配方式地址。该方式的实质是两级索引分配方式Page 342021-10-15Operating SystemOperating SystemqUNIX系统采用索引文件结构，系统采用索引文件结构，UNIXUNIX系统采用多系统采用

26、多级间接索引结构，对小型文件采用直接索引，对级间接索引结构，对小型文件采用直接索引，对大型文件采用间接索引，从而，既保证绝大多数大型文件采用间接索引，从而，既保证绝大多数的文件有高的存取效率，又能适应存取一些大型的文件有高的存取效率，又能适应存取一些大型文件。（既保证了文件系统的高效率，又使其有文件。（既保证了文件系统的高效率，又使其有很宽的适应面）很宽的适应面）Page 352021-10-15Operating SystemOperating SystemPage 362021-10-15Operating SystemOperating Systemq索引结构优缺点索引结构优缺点v优点：

27、优点： 保持了链接结构的优点保持了链接结构的优点, ,又解决了其缺又解决了其缺点：即能顺序存取点：即能顺序存取, ,又能随机存取，满足了又能随机存取，满足了文件动态增长、插入删除的要求，也能充文件动态增长、插入删除的要求，也能充分利用外存空间分利用外存空间v缺点：缺点： 较多的寻道次数和寻道时间，索引表较多的寻道次数和寻道时间，索引表本身带来了系统开销，如：内外存空间，本身带来了系统开销，如：内外存空间，存取时间存取时间Page 372021-10-15Operating SystemOperating Systemq索引分配的主要问题索引分配的主要问题v需要较多外存空间来建立索引块需要较多外存空间来建立索引块v对于小文件，空间浪费严重对于小文件，空间浪费严重Page 382021-10-15Operating SystemOperating Systemq连