文件的物理结构及存储设备

8.2.2文件的物理结构及存储设备(3)索引文件 索引文件是由系统为每个文件建立一张索引表，表中标明文件的逻辑块号所对应物理块号，索引表自身的物理地址由FCB给出。索引表结构：索引文件这种方法克服了链接文件对随机存取的限制。把所有的指针放在一起：索引块每个文件都有它自己的索引块索引块的第i个条目指向文件的第i个块（随机存取）一个索引块类似于内存分配中的一个页表索引文件的开销要比链接文件大，尤其如果每个文件只有很少的块时，会造成其余索引块的浪费。索引分配a.out16目录项（条目）文件名索引块000102030405060708091011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859212223445356nil012345678910111213...索引块(16)8.2.2文件的物理结构及存储设备 如果索引表很大，超过了一个物理块，则系统势必要像处理其他文件一样，来处理索引表的物理存放方式，这样不利于索引表的动态增删。解决的办法是采用多重索引的方式，也就是说，当索引表所指的物理块超过一块时，再增加一个次级索引表。这样，在高一级索引表表项里所指向的物理块中并不存放实际的文件信息，而是存放的一个索引表，在这个次一级的索引表中所指向的物理块才是存放的文件信息。如果需要，可以增加到3级以上的多级索引。链接索引块a.out16directoryentryfilenameindexblock00010203040506070809101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585939212223445356..........0123456789101112...255indexblock(16)nil57594041nil0123456789101112...255indexblock(39)多层索引a.out16directoryentryfilenameindexblock00010203040506070809101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585926341043nil0123456789101112...255toplevelindexblock(16)......0123456789101112...255......0123456789101112...255......0123456789101112...255......0123456789101112...255secondaryindexblocks组合链接/多层索引TheUnixinodeowner,grouptimestampssizedirectblockssingleindirectdoubleindirecttripleindirectblock(data)block(data)block(data)block(data)block(data)block(data)block(data)block(data)block(data)............(filenameisnotstoredintheinode)indexblock(UsedinBSDUnix)8.2.2文件的物理结构及存储设备2.文件的存储设备文件的存储设备分为不可重复使用的和可重复使用的两类。不可重复使用的文件存储设备也称为I/O式字符设备，如打印纸等。可重复使用的文件存储设备有磁带、磁盘、光盘等，也称块设备。8.2.2文件的物理结构及存储设备 两种典型的存储设备特性及存取方法。(1)顺序存取设备 顺序存取设备通常是指那些容量大、价格低的存储设备。(2)直接存取设备 光盘、磁盘都是一种可直接存取的存储设备(磁盘又分为硬盘和软盘)。①磁盘 磁盘是一种可直接存取(按地址存取)的存储设备，它把信息记录在盘片上，每个盘片有正反两面。②只读型光盘 光盘存储器是利用光学原理存取信息的存储设备8.2.2文件的物理结构及存储设备3.文件结构、存储设备与存取方式 综上所述，文件的物理结构，必须适应文件的存储设备，而不同的存储设备的特性，又决定了其上的文件的存取方式，下面以磁盘和磁带存储设备为例，简要说明3者的关系：①磁盘上的文件结构为连续时，其存取方式一般为顺序或随机。 当文件为连续方式时，存取方式通常为顺序的。②磁带上的文件结构为连续时，其存取方式一般为顺序存取。 当其上文件为索引文件时，存取方式可为顺序、随机两种形式。8.3文文件件管管理理8.3.1文文件件目目录录结结构构1.文文件件目目录录文件件系系统统为为程程序序和和用用户户提提供供了了按按文文件件名名存存取取文文件件的的机机制制，，而而将将文文件件名名转转换换为为存存储储地地址址，，以以及及对对文文件件实实施施控控制制管管理理则则需需通通过过文文件件目目录录来来实实现现。。文件件目目录录的的管管理理和和文文件件存存储储空空间间的的管管理理已已成成为为文文件件管管理理的的重重要要内内容容。。8.3.1文文件目录录结构一个文件由文文件说明和文文件体组成。。文件说明部部分包括文件件的基本信息息、存取控制制信息和文件件使用信息。。①基本信息息包括：文件名，用于于标识一个文文件的符号名名。文件物理位置置，标明文件件内容在外存存上的存储位位置。文件结构，指指示文件的逻逻辑结构和物物理结构。它它决定了文件件的寻址方式式。②存取信息息包括：各类类用户(包括括文件主、核核准用户、普普通用户等)的存取权限限，实现文件件的共享及保保密。③使用信息息包括：文件件创建、修改改的日期和时时间，以及当当前使用的状状态信息。8.3.1文文件目录录结构文件系统将这这些说明部分分的全部信息息集中起来，，以一个数据据结构的形式式表示，称此此结构为文件件控制块FCB(FileControlBlock)。文件目录由文件控制块块组成。文件件系统在每个个文件建立时时都要为它建建立一个文件件目录。文件件目录用于文文件描述和文文件控制，实实现按名存取取和文件信息息共享与保护护，随文件的的建立而创建建，随文件的的删除而消亡亡。不同的操作系系统有不同的的文件目录。。8.3.1文文件目录录结构下面以UNIX文件目录录为例加以说说明。UNIX系统统的文件目录录由目录项和和索引节点两两部分组成（（i节点—加快快文件检索方方法之一）。目录项占占16B，其其中14B为为文件名，2B为指向文文件说明信息息的索引节点点的指针，每每个索引节点点占64B，，包括文件属属性、文件共共享目录数、、时间、文件件存放块号、、文件长度等等说明信息。。8.3.1文文件目录录结构2.文件目目录结构文件目录是由由文件说明组组成的，若干干个文件目录录组成一个专专门的目录文件，目录文件的的结构如何，，关系到文件件的存取速度度和文件的共共享及安全特特性。文件目录结构构是指专门的的目录文件的的组织形式。。常用的目录录结构有单级级目录，二级级目录和多级级目录。8.3.1文文件目录录结构(1)单级级目录文件系统在每每个存储设备备上仅建立一一个目录文件件的目录结构构，称为单级级目录(或称称一级目录)。目录文件件中的每一目目录项(或称称一条记录)对应一个文文件目录，它它包含相对的的数据项(文文件名及扩展展名、物理地地址、说明信信息)，如图图所示。8.3.1文文件目录录结构单级目录的优优点是结构简简单，通过管管理其目录文文件，便可实实现对文件信信息的管理。。单级目录的特特点是：①搜索范围围宽。②不允许文文件重名。③不便于文文件共享。8.3.1文文件目录录结构(2)二级级目录结构二级目录结构构将存储在设设备上的目录录文件分成两两级：第一级级为系统目录录(称主目录录MFD)，，它包含了用用户目录名和和指向该用户户目录的指针针；第二级为为用户目录(称UFD)，它包含了了该用户所有有文件的文件件目录，该文文件目录和上上述单级的目目录一样，包包含了相应文文件的名字，，物理地址等等。8.3.1文文件目录录结构二级目录结构构:8.3.1文文件目录录结构(3)多级级目录结构采用树型数据据结构方法，，便形成一种种树型的结构构目录。这种文件目录录的第一级系系统目录为树树的根节点，，定义为根目目录，文件目目录的第二级级和以下各级级目录均为树树的分支节点点(非终节点点)，均定义义为子目录，，只有树的叶叶节点(终节节点)才为文文件。注：树型目录录的每一级既既可定义目录录也可定义文文件树型目录usrbinetcdevhostsfstabconfbinsbinspooltapetty0tty1tty2rootdateviwhichwhocalendarcronlp8.3.1文文件目录录结构从根目录经各各级子目录到到达文件的通通路上的所有有子目录名称称为文件的存存取路径。文件的绝对路路径（从根目录开始始）文件的相对路路径（从当前目录开开始）在多级目录结结构中，要访访问一个文件件必须从根目目录开始，逐逐级查找各级级子目录，直直到文件。无无疑这样查找找速度较慢。。有必要为系系统建立一个个称之为“工工作目录”的的当前目录（加快文件检索索方法之二），它不一定定是根目录，，当用户不另另外指定缺省省目录时，系系统从该目录录起进行查找找。不同的文文件系统都可可以设置这种种工作目录。。将多级目录结结构进一步推推广，就产生生了无环结构构目录图状结结构目录。8.3.1文文件目录录结构3.文件目目录与文件共共享为了有效的实实现文件共享享，文件系统统在建立文件件目录的过程程中，采用了了以下两种方方法，使文件件只需保存一一个副本，达达到多个用户户共享的目的的。(1)绕道道法(交叉法法)绕道法查找共共享文件的方方法是每个用用户从各自当当前目录开始始，向上返回回到共享文件件所在路径的的交叉节点，，然后沿交叉叉节点顺序向向下访问到共共享文件。8.3.1文文件目录录结构绕道法：链接—文件共享的的另一种方法法真正的树型结结构目录仅允许每每个文件存在在于该结构中中的一个地方方。一个文件或子子目录出现在在目录结构的的几个地方常常常是方便的的。例如，两个程程序员正在某某个相同的项项目上工作，，都希望与项项目关联的若若干文件保存存在自己的目目录中。共享文件（或或目录）不同同于文件拷贝贝。链接在Unix系统中，共享享文件可以通通过创建链接来实现。Unix支持两种类型型的链接。硬链接是复制指向相相同存储区的的目录条目软链接（符号链接）是别名或其它它文件或目录录的指针。(=>在MSWindows中的快捷方式式)链接usrbinetcvarbinsbinspoolrootdateviwhichwhocalendarcronlpadmmailspool硬链接file1file2file3file4file5file6file7directoryafile-8file1file9file10file11file12file13directorybdisk软链接file1file2file3file4file5file6file7directoryafile-8file1file9file10file11file12file13directorybdisk链接问题链接可能引入入一致性问题题。对于硬链接当文件被删除除时会发生什什么？对Unix系统，每个文文件有链接计数。当指向一个文文件的新链接接建立时，该该链接计数增加。当一个文件被被从目录中删删除时，该链接计数减少。如果链接计数是0，该文文件所占据的的空间被释放放。链接问题对于软链接如果原来的文文件被删除，，那么所有软软链接被留下下悬空。这就像发生在在MSWindows的快捷方式8.3.1文文件目录录结构(2)基本本文件目录表表法*为了有效实现现系统文件的的共享，文件件系统需建立立一基本文件件目录BFD，它包括了了文件的结构构、物理块号号、存取控制制和管理信息息。另外，需增加加符号文件目目录表SFD，包括用户户给定的符号号名和系统文文件赋予的文文件说明信息息的内部标识识符。主目录(MFD)记录了了文件名和系系统给定的惟惟一标识。8.3.1文文件目录录结构文件目录表：：8.3.1文文件目录录结构在实现文件共共享时，可以以有以下的两两种模式：①不同时使使用同一文件件。②同时使用用同一文件。。当所有进程都都不修改文件件时，情况比比较简单；如果某些进程程要求对文件件修改，那么么就必需加以以控制，否则则数据一致性性就得不到保保证。控制的的方法有两种种：一种是不允许许读者与写者者，或者写者者与写者同时时打开文件，，但这会降低低文件并发性性，并可能导导致死锁；另一种是允许许其同时打开开文件，由OS为用户提提供相应的互互斥手段，文文件使用者借借用这种手段段保证对文件件的同时共享享不发生冲突突。8.3.2文文件目录录管理如上所述，文文件的目录是是以目录文件件的形式存放放的，当存取取一个文件时时，往往需要要访问多级文文件目录，如如果对每一级级目录访问都都需要到文件件存储设备上上去搜索，势势必占用过多多的CPU时时间，若在系系统启动时，，把全部目录录文件读入内内存，由系统统直接在内存存实施对各级级目录的搜索索则虽然提高高了访问速度度，但需要的的内存容量太太大。一般来说，系系统只把当前前正在使用的的那些文件的的目录表（打开文件表——加快文件检检索方法之三三）复制到内存存中，为此，，系统提供两两种特殊操作作：其一是把有关关的目录文件件复制到内存存指定区，通通常称为打开开文件(Open)；其二是提供用用户不再访问问的有关文件件的目录文件件删除的操作作，通常称为为关闭文件(Close)。8.4文文件存储空间间的分配与管管理由文件的存储储结构可知，，文件信息的的交换都是以以块为单位进进行的。因此此，将文件存存储设备称为为块设备，这这里介绍的存存储空间的管管理实际上是是对文件块空空间而言的，，具体说是指指空闲块的组组织与回收。。一般来说，空空闲块空间的的分配常常有有两种方式：：一种静态分配配；另一种是动态态分配。另外在分配的的区域上，可可以将一个文文件分配在一一个完整的分分区中（以块块或簇为单位位），常使用用包含文件名名、起始地址址、长度的文文件分配表FAT等。8.4.1文文件存储储空间的分配配文件空间分配配常采用：连连续分配、索索引分配、链链接分配3种种方法。1.连续分分配连续分配方式式是将文件存存放在辅存的的连续存储区区中。8.4.1文文件存储储空间的分配配2.索引分分配索引分配方法法主要是利用用文件分配表表FAT给每每个文件分配配一个指出该该文件的索引引表所在的物物理块号的表表目，索引表表所在的索引引块与存储文文件的文件块块是分离的。。文件索引的每每个表目的设设置有两种情情况：一种是直接给给出索引文件件各物理块；；另一种是设置置文件的起始始块和长度，，这有利于连连续分配，也也有利于节省省索引表空间间、提高效率率，如图所示示。8.4.1文文件存储储空间的分配配8.4.1文文件存储储空间的分配配3.链接分分配链接分配文件件空间的方法法是一种离散散分配方式，，适用于文件件长度需动态态增减，或用用户对其文件件的应用不十十分明确的情情况，一般分分配非连续的的辅存空间。。采用链接表方方法链接存储储空间，链接接空间的大小小大多以区或或段为单位。。8.4.1文文件存储储空间的分配配(1)以扇扇区为链接单单位这是给需动态态变化的文件件分配若干磁磁盘扇区，这这些扇区在磁磁盘上可以不不连续，而分分配给同一文文件的各扇区区按其上文件件逻辑记录的的次序用链指指针链接起来来。(2)以区区段(或簇)为单位分配配这不是以扇区区为单位进行行分配，而是是以区段(或或称簇)为单单位进行分配配的。8.4.2磁磁盘空间间管理文件的磁盘存存储空间的管管理包括磁盘盘空间块的分分配和回收。。1.盘块盘块是操作系系统传输数据据的基本单位位，盘块大，，I/O操作作传输数据量量多，传输性性能好，但也也会造成盘空空间的浪费。。既要提高传输输率，又要减减少盘空间的的浪费，是文文件系统追求求的目标，盘盘块是重要因因素之一。8.4.2磁磁盘空间间管理(1)逻辑辑块逻辑磁盘是文文件系统中一一个抽象的存存储概念。系系统将逻辑磁磁盘视为一些些有固定大小小可随机存取取的逻辑块的的线性序列。。磁盘驱动程程序将逻辑块块映射到物理理介质上。一一般情况下，，一个物理磁磁盘被分成物物理上连续的的几个分区，，每个分区就就是一个逻辑辑磁盘，又称称磁盘分区。。通常所说的磁磁盘分区就是是将每一个分分区定义为一一个盘，此盘盘就是一个逻逻辑磁盘。(2)盘区区磁盘分区是将将磁盘上一组组连续的柱面面空间组成一一体，定义为为一个盘区。。其上可有一一个独立的文文件系统。不不同类的文件件系统可占有有不同的盘，，各自定义自自己盘块的大大小。8.4.2磁磁盘空间间管理2.磁盘块块大小①磁盘块大大小。可以理理解为磁盘分分配的单位，，它规定了文文件系统的分分配粒度和磁磁盘I/O粒粒度，盘块大大，有利于增增加系统性能能，不同的文文件系统块大大小也不同，，FFS（FreeBSD的快速速文件系统））可大于等于于4KB，NTFS（NT内核的文文件系统，簇簇的大小并不不依赖于磁盘盘或分区的大大小）可大到到64KB，，FAT32的簇大小可可达到32KB。②片断：是是盘块的组成成单位。8.4.2磁磁盘空间间管理3.盘块管管理盘块管理常用用盘图，链表表和i节点等手段，，因文件系统统而异。(1)盘图图法盘图也称字位位映像图，是是一种常用的的方法，它用用位(bit)的值0、、1来表示磁磁盘上相应物物理块是否被被分配，bit值为1表表示对应物理理块被分配，，为0表示对对应物理块为为空闲。对应一串连续续的bit值值，按字节构构成一张表，，此表可以把把一个完整磁磁盘的使用情情况记载下来来。盘图法分配时：b（（块号）=n（字长）*i（行号号）+j（（列号）回收时：i（（行号）=b（块号）divn（（字长）j（列号）=b（块号））modn（字长）n位m字01234567011000111101011111211000011345678.4.2磁磁盘空间间管理(2)链接接法①链接索引引块。这是一种常用用的方法，它它首先是选择择若干空闲物物理块建立索索引表块，假假设这样块的的大小为1KB，可以设设512个表表目，每个表表目占用16位，以此表表示一个空闲闲物理块的块块号，则每个个表目对应一一个空闲物理理块。而后将这些含含有空闲块号号的索引块之之间用链接方方式链接起来来，即每个索索引块的第0个表目作为为链表的指针针，指向下一一个索引块，，或链尾标志志。8.4.2磁磁盘空间间管理链接索引块：：8.4.2磁磁盘空间间管理②分配与回回收空闲块。。为了操作方便便，通常将索索引链表中的的链头指针所所指向的索引引块的表目中中留出空项(其他索引块块表目项全填填满)，当文文件系统分配配盘空间时从从链表头的索索引块的块尾尾开始，直到到该索引块的的第0个表目目，如果该索索引块仅剩下下第0个表目目，则将该表表目的内容读读到特定块链链头指针中，，然后将原链链头指针指向向的索引块T，分给请求求分配空闲块块的文件。空闲块的回收收则相反，仅仅将释放的空空闲块块号加加到链头指针针指出的索引引表块的尾部部表目中即可可。8.4.2磁磁盘空间间管理—Unix系系统示例在Unix操操作系统中，，把磁盘存储储空间的空闲闲块成组连接接。每100个空闲块为为一组，每一一组的第一个个空闲块中登登记下一组空空闲块的磁盘盘物理块号和和空闲块总数数，最后不足足100块的的那部分磁盘盘物理块及块块数记入专用用块（超级块块）中。Unix系统统示例

假定定共有空闲块块438块，，编号从12到449。。空闲块数395049…12…空闲块数100150149…5251空闲块数100250249…152151空闲块数100350349…252251空闲块数1000449…352351专用块块50#150#250#350#49#149#249#349#449#..........12#51#151#251#351#8.4.2磁磁盘盘空间间管理理—Unix系统统示例例系统初初始化化时先先把专专用块块内容容读到到主存存，当当有申申请空空闲块块要求求时，，就直直接在在主存存中可可以找找到哪哪些块块是空空闲的的，每每分配配一块块后把把空闲闲块数数减1即可可。但要把把一组组中的的第一一块分分配出出去之之前可可以先先把登登记在在块中中的下下一组组的块块号保保存到到专用用块中中（不怕覆覆盖吗吗？）。当一组组空闲闲块分分配完完后，，则再再把专专用块块的内内容复复制到到主存存，以以便继继续分分配时时查找找。8.4.2磁磁盘盘空间间管理理—Unix系统统示例例归还一一块时时，只只要把把归还还块的的块号号登记记到当当前组组中且且空闲闲块数数加1。当一组组已满满100块块时，，则把把主存存中的的内容容写到到当前前归还还的那那块中中，作作为新新组的的第一一块。。9、静夜四四无邻，，荒居旧旧业贫。。。12月-2212月-22Wednesday,December28,202210、雨中黄叶树树，灯下白头头人。。21:14:2521:14:2521:1412/28/20229:14:25PM11、以我我独沈沈久，，愧君君相见见频。。。12月月-2221:14:2521:14Dec-2228-Dec-2212、故故人人江江海海别别，，几几度度隔隔山山川川。。。。21:14:2521:14:2521:14Wednesday,December28,202213、乍见翻翻疑梦，，相悲各各问年。。。12月-2212月-2221:14:2521:14:25December28,202214、他乡乡生白白发，，旧国国见青青山。。。28十十二二月20229:14:25下下午21:14:2512月月-2215、比不了得得就不比，，得不到的的就不要。。。。十二月229:14下下午12月-2221:14December28,202216、行行动动出出成成果果，，工工作作出出财财富富。。。。2022/12/2821:14:2521:14:2528December202217、做做前前，，能能够够环环视视四四周周；；做做时时，，你你只只能能或或者者最最好好沿沿着着以以脚脚为为起起点点的的射射线线向向前前。。。。9:14:25下午9:14下下午21:14:2512月-229、没有失败，，只有暂时停停止成功！。。12月-2212月-22Wednesday,December28,202210、很多多事情情努力力了未未必有有结果果，但但是不不努力力却什什么改改变也也没有有。。。21:14:2621:14:2621:1412/28/20229:14:26PM11、成功就是是日复一日日那一点点点小小努力力的积累。。。12月-2221:14:2621:14Dec-2228-Dec-2212、世间成成事，不不求