文件的物理结构及存储设备(共54页).ppt

1、8.2.2 文件的物理结构及存储设备n(3) 索引文件 索引文件是由系统为每个文件建立一张索引表，表中标明文件的逻辑块号所对应物理块号，索引表自身的物理地址由FCB给出。 索引表结构 ： FCB . . 文件 A 索引表指针 . . 文件 A 的索引表 记录号 物理块号 0 4 1 7 2 10 R1 4 R2 7 R3 10 索引文件n这种方法克服了链接文件对随机存取的限制。n把所有的指针放在一起：索引块n每个文件都有它自己的索引块n索引块的第 i 个条目指向文件的第 i 个块随机存取n一个索引块类似于内存分配中的一个页表n索引文件的开销要比链接文件大，尤其如果每个文件只有很少的块时，会造成

2、其余索引块的浪费。索引分配.8.2.2 文件的物理结构及存储设备 如果索引表很大，超过了一个物理块，那么系统势必要像处理其他文件一样，来处理索引表的物理存放方式，这样不利于索引表的动态增删。解决的方法是采用多重索引的方式，也就是说，当索引表所指的物理块超过一块时，再增加一个次级索引表。这样，在高一级索引表表项里所指向的物理块中并不存放实际的文件信息，而是存放的一个索引表，在这个次一级的索引表中所指向的物理块才是存放的文件信息。如果需要，可以增加到3级以上的多级索引。 链接索引块多层索引组合链接/多层索引8.2.2 文件的物理结构及存储设备2. 文件的存储设备n文件的存储设备分为不可重复使用的和

3、可重复使用的两类。n不可重复使用的文件存储设备也称为I/O式字符设备，如打印纸等。n可重复使用的文件存储设备有磁带、磁盘、光盘等，也称块设备。 8.2.2 文件的物理结构及存储设备两种典型的存储设备特性及存取方法。n(1) 顺序存取设备顺序存取设备通常是指那些容量大、价格低的存储设备。 n(2) 直接存取设备光盘、磁盘都是一种可直接存取的存储设备(磁盘又分为硬盘和软盘)。n 磁盘磁盘是一种可直接存取(按地址存取)的存储设备，它把信息记录在盘片上，每个盘片有正反两面。n 只读型光盘光盘存储器是利用光学原理存取信息的存储设备 8.2.2 文件的物理结构及存储设备3. 文件结构、存储设备与存取方式综

4、上所述，文件的物理结构，必须适应文件的存储设备，而不同的存储设备的特性，又决定了其上的文件的存取方式，下面以磁盘和磁带存储设备为例，简要说明3者的关系：n 磁盘上的文件结构为连续时，其存取方式一般为顺序或随机。当文件为连续方式时，存取方式通常为顺序的。n 磁带上的文件结构为连续时，其存取方式一般为顺序存取。当其上文件为索引文件时，存取方式可为顺序、随机两种形式。8.3 文件管理8.3.1 文件目录结构1. 文件目录文件系统为程序和用户提供了按文件名存取文件的机制，而将文件名转换为存储地址，以及对文件实施控制管理那么需通过文件目录来实现。文件目录的管理和文件存储空间的管理已成为文件管理的重要内容

5、。8.3.1 文件目录结构一个文件由文件说明和文件体组成。文件说明局部包括文件的根本信息、存取控制信息和文件使用信息。 根本信息包括：文件名，用于标识一个文件的符号名。文件物理位置，标明文件内容在外存上的存储位置。文件结构，指示文件的逻辑结构和物理结构。它决定了文件的寻址方式。 存取信息包括：各类用户(包括文件主、核准用户、普通用户等)的存取权限，实现文件的共享及保密。 使用信息包括：文件创立、修改的日期和时间，以及当前使用的状态信息。8.3.1 文件目录结构n文件系统将这些说明局部的全部信息集中起来，以一个数据结构的形式表示，称此结构为文件控制块FCB (File Control Block

6、)。n文件目录由文件控制块组成。文件系统在每个文件建立时都要为它建立一个文件目录。文件目录用于文件描述和文件控制，实现按名存取和文件信息共享与保护，随文件的建立而创立，随文件的删除而消亡。n不同的操作系统有不同的文件目录。 8.3.1 文件目录结构n下面以UNIX文件目录为例加以说明。nUNIX系统的文件目录由目录项和索引节点两局部组成i节点加快文件检索方法之一。目录项占16B，其中14B为文件名，2B为指向文件说明信息的索引节点的指针，每个索引节点占64B，包括文件属性、文件共享目录数、时间、文件存放块号、文件长度等说明信息。 文 件 名 指 针 . . . . . . 文 件 名i 索 引

7、 节 点 号 . . . . . . 文 件 属 性 . . . 文 件 长 度 . . . 索 引 节 点 64B 8.3.1 文件目录结构2. 文件目录结构文件目录是由文件说明组成的，假设干个文件目录组成一个专门的目录文件，目录文件的结构如何，关系到文件的存取速度和文件的共享及平安特性。文件目录结构是指专门的目录文件的组织形式。常用的目录结构有单级目录，二级目录和多级目录。8.3.1 文件目录结构n(1) 单级目录n文件系统在每个存储设备上仅建立一个目录文件的目录结构，称为单级目录(或称一级目录)。目录文件中的每一目录项(或称一条记录)对应一个文件目录，它包含相对的数据项(文件名及扩展名、

8、物理地址、说明信息)，如下图。 文 件 名 物 理 地 址 文 件 说 明 信 息 X1 R1 W1 X2 R2 W2 . . . . . . . . . 8.3.1 文件目录结构n单级目录的优点是结构简单，通过管理其目录文件，便可实现对文件信息的管理。 n单级目录的特点是：n 搜索范围宽。n 不允许文件重名。n 不便于文件共享。 8.3.1 文件目录结构n(2) 二级目录结构 二级目录结构将存储在设备上的目录文件分成两级：第一级为系统目录(称主目录MFD)，它包含了用户目录名和指向该用户目录的指针；第二级为用户目录(称UFD)，它包含了该用户所有文件的文件目录，该文件目录和上述单级的目录一样

9、，包含了相应文件的名字，物理地址等。 8.3.1 文件目录结构二级目录结构: XQX SET XQX help 系统目录 User l User N 用户目录名 用户目录指针 XQX help 文件名 物理地址 User l 用户目录 User N 用户目录 XQX SET 8.3.1 文件目录结构n(3) 多级目录结构n采用树型数据结构方法，便形成一种树型的结构目录。n这种文件目录的第一级系统目录为树的根节点，定义为根目录，文件目录的第二级和以下各级目录均为树的分支节点(非终节点)，均定义为子目录，只有树的叶节点(终节点)才为文件。n注：树型目录的每一级既可定义目录也可定义文件注：树型目录的

10、每一级既可定义目录也可定义文件 树型目录8.3.1 文件目录结构n从根目录经各级子目录到达文件的通路上的所有子目录名称为文件的存取路径。n文件的绝对路径从根目录开始n文件的相对路径从当前目录开始n在多级目录结构中，要访问一个文件必须从根目录开始，逐级查找各级子目录，直到文件。无疑这样查找速度较慢。有必要为系统建立一个称之为“工作目录的当前目录加快文件检索方法之二，它不一定是根目录，当用户不另外指定缺省目录时，系统从该目录起进行查找。不同的文件系统都可以设置这种工作目录。n将多级目录结构进一步推广，就产生了无环结构目录图状结构目录。8.3.1 文件目录结构3. 文件目录与文件共享 为了有效的实现

11、文件共享，文件系统在建立文件目录的过程中，采用了以下两种方法，使文件只需保存一个副本，到达多个用户共享的目的。 (1) 绕道法(交叉法) 绕道法查找共享文件的方法是每个用户从各自当前目录开始，向上返回到共享文件所在路径的交叉节点，然后沿交叉节点顺序向下访问到共享文件。 8.3.1 文件目录结构绕道法：被 共 享 文 件 交 叉 点共 享 文 件当 前 目 录文 件链接文件共享的另一种方法n真正的树型结构目录仅允许每个文件存在于该结构中的一个地方。n一个文件或子目录出现在目录结构的几个地方常常是方便的。n例如，两个程序员正在某个相同的工程上工作，都希望与工程关联的假设干文件保存在自己的目录中。n

12、共享文件或目录不同于文件拷贝。链接n在 Unix 系统中，共享文件可以通过创立链接来实现。nUnix 支持两种类型的链接。n硬链接 是复制指向相同存储区的目录条目n软链接符号链接是别名或其它文件或目录的指针。 ( = 在 MS Windows 中的快捷方式)链接硬链接软链接链接问题n链接可能引入一致性问题。n对于硬链接n当文件被删除时会发生什么？n对 Unix 系统，每个文件有链接计数。n当指向一个文件的新链接建立时，该链接计数增加。n当一个文件被从目录中删除时，该链接计数减少。n如果链接计数是 0，该文件所占据的空间被释放。链接问题n对于软链接n如果原来的文件被删除，那么所有软链接被留下悬空

13、。n这就像发生在 MS Windows 的快捷方式8.3.1 文件目录结构n(2) 根本文件目录表法*n为了有效实现系统文件的共享，文件系统需建立一根本文件目录BFD，它包括了文件的结构、物理块号、存取控制和管理信息。n另外，需增加符号文件目录表SFD，包括用户给定的符号名和系统文件赋予的文件说明信息的内部标识符。n主目录(MFD)记录了文件名和系统给定的惟一标识。8.3.1 文件目录结构文件目录表 ：标 识 符物 理块 号0123456789主 目 录 (M FD)文 件 名IDA3B5空 闲 文 件 目 录A 的 SFD文 件 名IDX1.t4X2.t6B 的 SFD文 件 名IDy1.c

14、6sub.d8sub.d 的 SFD文 件 名IDy2 .c7Y3 .b9基 本 文 件 目 录 (BFD)x1.tx2.ty1.cy2.cy3.b8.3.1 文件目录结构在实现文件共享时，可以有以下的两种模式： 不同时使用同一文件。 同时使用同一文件。当所有进程都不修改文件时，情况比较简单；如果某些进程要求对文件修改，那么就必需加以控制，否那么数据一致性就得不到保证。控制的方法有两种：一种是不允许读者与写者，或者写者与写者同时翻开文件，但这会降低文件并发性，并可能导致死锁；另一种是允许其同时翻开文件，由OS为用户提供相应的互斥手段，文件使用者借用这种手段保证对文件的同时共享不发生冲突。 8.

15、3.2 文件目录管理n如上所述，文件的目录是以目录文件的形式存放的，当存取一个文件时，往往需要访问多级文件目录，如果对每一级目录访问都需要到文件存储设备上去搜索，势必占用过多的CPU时间，假设在系统启动时，把全部目录文件读入内存，由系统直接在内存实施对各级目录的搜索那么虽然提高了访问速度，但需要的内存容量太大。n一般来说，系统只把当前正在使用的那些文件的目录表翻开文件表加快文件检索方法之三复制到内存中，为此，系统提供两种特殊操作：n其一是把有关的目录文件复制到内存指定区，通常称为翻开文件(Open)；n其二是提供用户不再访问的有关文件的目录文件删除的操作，通常称为关闭文件(Close)。8.4

16、 文件存储空间的分配与管理 n由文件的存储结构可知，文件信息的交换都是以块为单位进行的。因此，将文件存储设备称为块设备，这里介绍的存储空间的管理实际上是对文件块空间而言的，具体说是指空闲块的组织与回收。n一般来说，空闲块空间的分配常常有两种方式：n一种静态分配；n另一种是动态分配。n另外在分配的区域上，可以将一个文件分配在一个完整的分区中以块或簇为单位，常使用包含文件名、起始地址、长度的文件分配表FAT等。8.4.1 文件存储空间的分配文件空间分配常采用：连续分配、索引分配、链接分配3种方法。1. 连续分配连续分配方式是将文件存放在辅存的连续存储区中。 FAT文件名起始块号长度Y125Y293

17、 1 2 3 4 5 6 7 8 9 10 11 12y1y1y1y1y1y2y2y2盘块8.4.1 文件存储空间的分配2. 索引分配索引分配方法主要是利用文件分配表FAT给每个文件分配一个指出该文件的索引表所在的物理块号的表目，索引表所在的索引块与存储文件的文件块是别离的。 文件索引的每个表目的设置有两种情况：一种是直接给出索引文件各物理块；另一种是设置文件的起始块和长度，这有利于连续分配，也有利于节省索引表空间、提高效率，如下图。8.4.1 文件存储空间的分配 FA T 文件名 索引块号 . . . . . . X1 9 X2 1 . . . . . . 索引块X2 7 12 2 索引块X

18、1 起始块 长度 3 3 10 2 1 2 3 4 5 6 7 8 9 10 11 12 X2 X1 X1 X1 X2 X1 X1 X2 盘块 8.4.1 文件存储空间的分配3. 链接分配链接分配文件空间的方法是一种离散分配方式，适用于文件长度需动态增减，或用户对其文件的应用不十清楚确的情况，一般分配非连续的辅存空间。采用链接表方法链接存储空间，链接空间的大小大多以区或段为单位。8.4.1 文件存储空间的分配n(1) 以扇区为链接单位n 这是给需动态变化的文件分配假设干磁盘扇区，这些扇区在磁盘上可以不连续，而分配给同一文件的各扇区按其上文件逻辑记录的次序用链指针链接起来。n(2) 以区段(或簇

19、)为单位分配n 这不是以扇区为单位进行分配，而是以区段(或称簇)为单位进行分配的。 8.4.2 磁盘空间管理 文件的磁盘存储空间的管理包括磁盘空间块的分配和回收。1. 盘块盘块是操作系统传输数据的根本单位，盘块大，I/O操作传输数据量多，传输性能好，但也会造成盘空间的浪费。既要提高传输率，又要减少盘空间的浪费，是文件系统追求的目标，盘块是重要因素之一。8.4.2 磁盘空间管理n(1) 逻辑块 逻辑磁盘是文件系统中一个抽象的存储概念。系统将逻辑磁盘视为一些有固定大小可随机存取的逻辑块的线性序列。磁盘驱动程序将逻辑块映射到物理介质上。一般情况下，一个物理磁盘被分成物理上连续的几个分区，每个分区就是

20、一个逻辑磁盘，又称磁盘分区。 通常所说的磁盘分区就是将每一个分区定义为一个盘，此盘就是一个逻辑磁盘。n(2) 盘区磁盘分区是将磁盘上一组连续的柱面空间组成一体，定义为一个盘区。其上可有一个独立的文件系统。不同类的文件系统可占有不同的盘，各自定义自己盘块的大小。 8.4.2 磁盘空间管理2. 磁盘块大小 磁盘块大小。可以理解为磁盘分配的单位，它规定了文件系统的分配粒度和磁盘I/O粒度，盘块大，有利于增加系统性能，不同的文件系统块大小也不同，FFSFreeBSD 的快速文件系统可大于等于4KB，NTFSNT内核的文件系统，簇的大小并不依赖于磁盘或分区的大小可大到64KB，FAT32的簇大小可到达3

21、2KB。 片断：是盘块的组成单位。 8.4.2 磁盘空间管理3. 盘块管理盘块管理常用盘图，链表和i节点等手段，因文件系统而异。n(1) 盘图法 盘图也称字位映像图，是一种常用的方法，它用位(bit)的值0、1来表示磁盘上相应物理块是否被分配，bit值为1表示对应物理块被分配，为0表示对应物理块为空闲。 对应一串连续的bit值，按字节构成一张表，此表可以把一个完整磁盘的使用情况记载下来。 盘图法n分配时：b块号=n字长* i行号+ j列号n回收时：i行号=b块号div n字长n j列号=b块号mod n字长 n位m字012345670110001111010111112110000113456

22、78.4.2 磁盘空间管理n(2) 链接法n 链接索引块。n 这是一种常用的方法，它首先是选择假设干空闲物理块建立索引表块，假设这样块的大小为1KB，可以设512个表目，每个表目占用16位，以此表示一个空闲物理块的块号，那么每个表目对应一个空闲物理块。n 而后将这些含有空闲块号的索引块之间用链接方式链接起来，即每个索引块的第0个表目作为链表的指针，指向下一个索引块，或链尾标志。 8.4.2 磁盘空间管理链接索引块： 超级块 T1 T1 T2 T2 T3 T3 8.4.2 磁盘空间管理n 分配与回收空闲块。n 为了操作方便，通常将索引链表中的链头指针所指向的索引块的表目中留出空项(其他索引块表目项全填满)，当文件系统