文件的物理结构及存储设备市公开课金奖市赛课一等奖课件

8.2.2文献物理结构及存储设备(3)索引文献 索引文献是由系统为每个文献建立一张索引表，表中标明文献逻辑块号所相应物理块号，索引表本身物理地址由FCB给出。索引表结构：第1页第1页索引文献这种办法克服了链接文献对随机存取限制。把所有指针放在一起：索引块每个文献都有它自己索引块索引块第i个条目指向文献第i个块（随机存取）一个索引块类似于内存分派中一个页表索引文献开销要比链接文献大，尤其假如每个文献只有很少块时，会造成其余索引块浪费。第2页第2页索引分派a.out16目录项（条目）文献名索引块000102030405060708091011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859212223445356nil012345678910111213...索引块(16)第3页第3页8.2.2文献物理结构及存储设备 假如索引表很大，超出了一个物理块，则系统势必要像处理其它文献同样，来处理索引表物理存储方式，这样不利于索引表动态增删。处理办法是采用多重索引方式，也就是说，当索引表所指物理块超出一块时，再增长一个次级索引表。这样，在高一级索引表表项里所指向物理块中并不存储实际文献信息，而是存储一个索引表，在这个次一级索引表中所指向物理块才是存储文献信息。假如需要，能够增长到3级以上多级索引。第4页第4页链接索引块a.out16directoryentryfilenameindexblock00010203040506070809101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585939212223445356..........0123456789101112...255indexblock(16)nil57594041nil0123456789101112...255indexblock(39)第5页第5页多层索引a.out16directoryentryfilenameindexblock00010203040506070809101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585926341043nil0123456789101112...255toplevelindexblock(16)......0123456789101112...255......0123456789101112...255......0123456789101112...255......0123456789101112...255secondaryindexblocks第6页第6页组合链接/多层索引TheUnixinodeowner,grouptimestampssizedirectblockssingleindirectdoubleindirecttripleindirectblock(data)block(data)block(data)block(data)block(data)block(data)block(data)block(data)block(data)............(filenameisnotstoredintheinode)indexblock(UsedinBSDUnix)第7页第7页8.2.2文献物理结构及存储设备2.文献存储设备文献存储设备分为不可重复使用和可重复使用两类。不可重复使用文献存储设备也称为I/O式字符设备，如打印纸等。可重复使用文献存储设备有磁带、磁盘、光盘等，也称块设备。第8页第8页8.2.2文献物理结构及存储设备 两种典型存储设备特性及存取办法。(1)顺序存取设备 顺序存取设备通常是指那些容量大、价格低存储设备。(2)直接存取设备 光盘、磁盘都是一个可直接存取存储设备(磁盘又分为硬盘和软盘)。①磁盘 磁盘是一个可直接存取(按地址存取)存储设备，它把信息统计在盘片上，每个盘片有正反两面。②只读型光盘 光盘存储器是利用光学原理存取信息存储设备第9页第9页8.2.2文献物理结构及存储设备3.文件结构、存放设备与存取方式 总而言之，文件物理结构，必须适应文件存放设备，而不同存放设备特性，又决定了其上文件存取方式，下面以磁盘和磁带存放设备为例，简明说明3者关系：①磁盘上文件结构为连续时，其存取方式普通为次序或随机。 当文件为连续方式时，存取方式通常为次序。②磁带上文件结构为连续时，其存取方式普通为次序存取。 当其上文件为索引文件时，存取方式可为次序、随机两种形式。第10页第10页8.3文献管理8.3.1文献目录结构1.文献目录文献系统为程序和用户提供了按文献名存取文献机制，而将文献名转换为存储地址，以及对文献实行控制管理则需通过文献目录来实现。文献目录管理和文献存储空间管理已成为文献管理主要内容。第11页第11页8.3.1文献目录结构 一个文献由文献阐明和文献体构成。文献阐明部分包括文献基本信息、存取控制信息和文献使用信息。①基本信息包括：文献名，用于标识一个文献符号名。文献物理位置，标明文献内容在外存上存储位置。文献结构，批示文献逻辑结构和物理结构。它决定了文献寻址方式。②存取信息包括：各类用户(包括文献主、核准用户、普通用户等)存取权限，实现文献共享及保密。③使用信息包括：文献创建、修改日期和时间，以及当前使用状态信息。第12页第12页8.3.1文献目录结构文件系统将这些说明部分全部信息集中起来，以一个数据结构形式表示，称此结构为文件控制块FCB(FileControlBlock)。文件目录由文件控制块组成。文件系统在每个文件建立时都要为它建立一个文件目录。文件目录用于文件描述和文件控制，实现按名存取和文件信息共享与保护，随文件建立而创建，随文件删除而消亡。不同操作系统有不同文件目录。第13页第13页8.3.1文献目录结构下面以UNIX文献目录为例加以阐明。UNIX系统文献目录由目录项和索引节点两部分构成（i节点—加快文献检索办法之一）。目录项占16B，其中14B为文献名，2B为指向文献阐明信息索引节点指针，每个索引节点占64B，包括文献属性、文献共享目录数、时间、文献存储块号、文献长度等阐明信息。第14页第14页8.3.1文献目录结构2.文献目录结构文献目录是由文献阐明构成，若干个文献目录构成一个专门目录文献，目录文献结构如何，关系到文献存取速度和文献共享及安全特性。文献目录结构是指专门目录文献组织形式。惯用目录结构有单级目录，二级目录和多级目录。第15页第15页8.3.1文献目录结构(1)单级目录 文献系统在每个存储设备上仅建立一个目录文献目录结构，称为单级目录(或称一级目录)。目录文献中每一目录项(或称一条统计)相应一个文献目录，它包括相正确数据项(文献名及扩展名、物理地址、阐明信息)，如图所表示。第16页第16页8.3.1文献目录结构单级目录长处是结构简朴，通过管理其目录文献，便可实现对文献信息管理。单级目录特点是：①搜索范围宽。②不允许文献重名。③不便于文献共享。第17页第17页8.3.1文献目录结构(2)二级目录结构 二级目录结构将存储在设备上目录文献分成两级：第一级为系统目录(称主目录MFD)，它包括了用户目录名和指向该用户目录指针；第二级为用户目录(称UFD)，它包括了该用户所有文献文献目录，该文献目录和上述单级目录同样，包括了相应文献名字，物理地址等。第18页第18页8.3.1文献目录结构二级目录结构:

第19页第19页8.3.1文献目录结构(3)多级目录结构采用树型数据结构办法，便形成一个树型结构目录。这种文献目录第一级系统目录为树根节点，定义为根目录，文献目录第二级和下列各级目录均为树分支节点(非终节点)，均定义为子目录，只有树叶节点(终节点)才为文献。注：树型目录每一级既可定义目录也可定义文献第20页第20页树型目录usrbinetcdevhostsfstabconfbinsbinspooltapetty0tty1tty2rootdateviwhichwhocalendarcronlp第21页第21页8.3.1文献目录结构从根目录经各级子目录抵达文件通路上全部子目录名称为文件存取路径。文件绝对路径（从根目录开始）文件相对路径（从当前目录开始）在多级目录结构中，要访问一个文件必须从根目录开始，逐层查找各级子目录，直到文件。无疑这么查找速度较慢。有必要为系统建立一个称之为“工作目录”当前目录（加紧文件检索方法之二），它不一定是根目录，当用户不另外指定缺省目录时，系统从该目录起进行查找。不同文件系统都能够设置这种工作目录。将多级目录结构深入推广，就产生了无环结构目录图状结构目录。第22页第22页8.3.1文献目录结构3.文献目录与文献共享 为了有效实现文献共享，文献系统在建立文献目录过程中，采用了下列两种办法，使文献只需保留一个副本，达到多个用户共享目的。(1)绕道法(交叉法) 绕道法查找共享文献办法是每个用户从各自当前目录开始，向上返回到共享文献所在路径交叉节点，然后沿交叉节点顺序向下访问到共享文献。第23页第23页8.3.1文献目录结构绕道法：第24页第24页链接—文献共享另一个办法真正树型结构目录仅允许每个文件存在于该结构中一个地方。一个文件或子目录出现在目录结构几个地方经常是方便。比如，两个程序员正在某个相同项目上工作，都希望与项目关联若干文件保留在自己目录中。共享文件（或目录）不同于文件拷贝。第25页第25页链接在Unix系统中，共享文献能够通过创建链接来实现。Unix支持两种类型链接。硬链接

是复制指向相同存储区目录条目软链接（符号链接）是别名或其它文献或目录指针。

(=>在MSWindows中快捷方式)第26页第26页链接usrbinetcvarbinsbinspoolrootdateviwhichwhocalendarcronlpadmmailspool第27页第27页硬链接file1file2file3file4file5file6file7directoryafile-8file1file9file10file11file12file13directorybdisk第28页第28页软链接file1file2file3file4file5file6file7directoryafile-8file1file9file10file11file12file13directorybdisk第29页第29页链接问题链接也许引入一致性问题。对于硬链接当文献被删除时会发生什么？对Unix系统，每个文献有链接计数。当指向一个文献新链接建立时，该链接计数增长。当一个文献被从目录中删除时，该链接计数减少。假如链接计数是0，该文献所占据空间被释放。第30页第30页链接问题对于软链接假如本来文献被删除，那么所有软链接被留下悬空。这就像发生在MSWindows快捷方式第31页第31页8.3.1文献目录结构(2)基本文献目录表法*为了有效实现系统文献共享，文献系统需建立一基本文献目录BFD，它包括了文献结构、物理块号、存取控制和管理信息。另外，需增长符号文献目录表SFD，包括用户给定符号名和系统文献赋予文献阐明信息内部标识符。主目录(MFD)统计了文献名和系统给定惟一标识。第32页第32页8.3.1文献目录结构文献目录表：第33页第33页8.3.1文献目录结构 在实现文件共享时，能够有以下两种模式：①不同时使用同一文件。②同时使用同一文件。当全部进程都不修改文件时，情况比较简朴；假如一些进程要求对文件修改，那么就必需加以控制，不然数据一致性就得不到确保。控制方法有两种：一个是不允许读者与写者，或者写者与写者同时打开文件，但这会降低文件并发性，并可能造成死锁；另一个是允许其同时打开文件，由OS为用户提供对应互斥手段，文件使用者借用这种手段确保对文件同时共享不发生冲突。第34页第34页8.3.2文献目录管理如上所述，文献目录是以目录文献形式存储，当存取一个文献时，往往需要访问多级文献目录，假如对每一级目录访问都需要到文献存储设备上去搜索，势必占用过多CPU时间，若在系统启动时，把所有目录文献读入内存，由系统直接在内存实行对各级目录搜索则即使提升了访问速度，但需要内存容量太大。普通来说，系统只把当前正在使用那些文献目录表（打开文献表—加快文献检索办法之三）复制到内存中，为此，系统提供两种特殊操作：其一是把相关目录文献复制到内存指定区，通常称为打开文献(Open)；其二是提供用户不再访问相关文献目录文献删除操作，通常称为关闭文献(Close)。第35页第35页8.4文献存储空间分派与管理由文献存储结构可知，文献信息互换都是以块为单位进行。因此，将文献存储设备称为块设备，这里简介存储空间管理事实上是对文献块空间而言，详细说是指空闲块组织与回收。普通来说，空闲块空间分派经常有两种方式：一个静态分派；另一个是动态分派。另外在分派区域上，能够将一个文献分派在一个完整分区中（以块或簇为单位），常使用包括文献名、起始地址、长度文献分派表FAT等。第36页第36页8.4.1文献存储空间分派 文献空间分派常采用：连续分派、索引分派、链接分派3种办法。1.连续分派 连续分派方式是将文献存储在辅存连续存储区中。

第37页第37页8.4.1文献存储空间分派2.索引分派索引分派办法主要是利用文献分派表FAT给每个文献分派一个指出该文献索引表所在物理块号表目，索引表所在索引块与存储文献文献块是分离。文献索引每个表目的设置有两种情况：一个是直接给出索引文献各物理块；另一个是设置文献起始块和长度，这有助于连续分派，也有助于节约索引表空间、提升效率，如图所表示。第38页第38页8.4.1文献存储空间分派第39页第39页8.4.1文献存储空间分派3.链接分派链接分派文献空间办法是一个离散分派方式，适合用于文献长度需动态增减，或用户对其文献应用不十分明确情况，普通分派非连续辅存空间。采用链接表办法链接存储空间，链接空间大小大多以区或段为单位。第40页第40页8.4.1文献存储空间分派(1)以扇区为链接单位 这是给需动态改变文献分派若干磁盘扇区，这些扇区在磁盘上能够不连续，而分派给同一文献各扇区按其上文献逻辑统计顺序用链指针链接起来。(2)以区段(或簇)为单位分派 这不是以扇区为单位进行分派，而是以区段(或称簇)为单位进行分派。第41页第41页8.4.2磁盘空间管理 文献磁盘存储空间管理包括磁盘空间块分派和回收。1.盘块盘块是操作系统传播数据基本单位，盘块大，I/O操作传播数据量多，传播性能好，但也会造成盘空间浪费。既要提升传播率，又要减少盘空间浪费，是文献系统追求目的，盘块是主要原因之一。第42页第42页8.4.2磁盘空间管理(1)逻辑块 逻辑磁盘是文件系统中一个抽象存放概念。系统将逻辑磁盘视为一些有固定大小可随机存取逻辑块线性序列。磁盘驱动程序将逻辑块映射到物理介质上。普通情况下，一个物理磁盘被分成物理上连续几个分区，每个分区就是一个逻辑磁盘，又称磁盘分区。 通常所说磁盘分区就是将每一个分区定义为一个盘，此盘就是一个逻辑磁盘。(2)盘区 磁盘分区是将磁盘上一组连续柱面空间组成一体，定义为一个盘区。其上可有一个独立文件系统。不同类文件系统可占有不同盘，各自定义自己盘块大小。第43页第43页8.4.2磁盘空间管理2.磁盘块大小①磁盘块大小。能够了解为磁盘分派单位，它要求了文件系统分派粒度和磁盘I/O粒度，盘块大，有利于增加系统性能，不同文件系统块大小也不同，FFS（FreeBSD快速文件系统）可大于等于4KB，NTFS（NT内核文件系统，簇大小并不依赖于磁盘或分区大小）可大到64KB，FAT32簇大小可达到32KB。②片断：是盘块组成单位。第44页第44页8.4.2磁盘空间管理3.盘块管理 盘块管理惯用盘图，链表和i节点等手段，因文献系统而异。(1)盘图法 盘图也称字位映像图，是一个惯用办法，它用位(bit)值0、1来表示磁盘上相应物理块是否被分派，bit值为1表示相应物理块被分派，为0表示相应物理块为空闲。 相应一串连续bit值，按字节构成一张表，此表能够把一个完整磁盘使用情况记载下来。第45页第45页盘图法分派时：b（块号）=n（字长）*i（行号）+j（列号）回收时：i（行号）=b（块号）divn（字长） j（列号）=b（块号）modn（字长）n位m字0123456701100011110101111121100001134567第46页第46页8.4.2磁盘空间管理(2)链接法①链接索引块。 这是一个惯用办法，它首先是选择若干空闲物理块建立索引表块，假设这样块大小为1KB，能够设512个表目，每个表目占用16位，以此表示一个空闲物理块块号，则每个表目相应一个空闲物理块。 而后将这些含有空闲块号索引块之间用链接方式链接起来，即每个索引块第0个表目作为链表指针，指向下一个索引块，或链尾标志。第47页第47页8.4.2磁盘空间管理链接索引块：第48页第48页8.4.2磁盘空间管理②分派与回收空闲块。 为了操作以便，通常将索引链表中链头指针所指向索引块表目中留出空项(其它索引块表目项全填满)，当文献系统分派盘空间时从链表头索引块块尾开始，直到该索引块第0个表目，假如该索引块仅剩余第0个表目，则将该表目的内容读到特定块链头指针中，然后将原链头指针指向索引块T，分给请求分派空闲块文献。 空闲块回收则相反，仅将释放空闲块块号加到链头指针指出索引表块尾部表目中即可。第49页第49页8.4.2磁盘空间管理—Unix系统示例在Unix操作系统中，把磁盘存储空间空闲块成组连接。每100个空闲块为一组，每一组第一个空闲块中登记下一组空闲块磁盘物理块号和空闲块总数，最后不足100块那部分磁盘物理块及块数记入专用块（超级块）中。第50页第50页Unix系统示例

假定共有空闲块438块，编号从12到449。空闲块数395049…12…空闲块数100150149…5251空闲块数100250249…152151空闲块数100350349…252251空闲块数1000449…352351专用块50#150#250#