文件的物理结构及存储设备市公开课一等奖百校联赛特等奖课件.pptx

8.2.2 文件物理结构及存放设备n(3)索引文件 索引文件是由系统为每个文件建立一张索引表，表中标明文件逻辑块号所对应物理块号，索引表本身物理地址由FCB给出。索引表结构：第1页索引文件n这种方法克服了链接文件对随机存取限制。n把全部指针放在一起：索引块n每个文件都有它自己索引块n索引块第 i 个条目指向文件第 i 个块（随机存取）n一个索引块类似于内存分配中一个页表n索引文件开销要比链接文件大，尤其假如每个文件只有极少块时，会造成其余索引块浪费。第2页索引分配a.outa.out1616目录项（条目）目录项（条目）文件名文件名索引块索引块000001010202030304040505060607070808090910101111121213131414151516161717181819192020212122222323242425252626272728282929303031313232333334343535363637373838393940404141424243434444454546464747484849495050515152525353545455555656575758585959212122222323444453535656nilnil0 01 12 23 34 45 56 67 78 89 91 10 01 11 11 12 21 13 3.索引块索引块(16)(16)第3页8.2.2 文件物理结构及存放设备 假如索引表很大，超出了一个物理块，则系统势必要像处理其它文件一样，来处理索引表物理存放方式，这么不利于索引表动态增删。处理方法是采取多重索引方式，也就是说，当索引表所指物理块超出一块时，再增加一个次级索引表。这么，在高一级索引表表项里所指向物理块中并不存放实际文件信息，而是存放一个索引表，在这个次一级索引表中所指向物理块才是存放文件信息。假如需要，能够增加到3级以上多级索引。第4页链接索引块a.outa.out1616directory entrydirectory entryfilenamefilenameindex blockindex block0000 0101 0202 0303 0404 0505 0606 0707 0808 09091010 1111 1212 1313 1414 1515 1616 1717 1818 19192020 2121 2222 2323 2424 2525 2626 2727 2828 29293030 3131 3232 3333 3434 3535 3636 3737 3838 39394040 4141 4242 4343 4444 4545 4646 4747 4848 49495050 5151 5252 5353 5454 5555 5656 5757 5858 59593939212122222323444453535656.0 01 12 23 34 45 56 67 78 89 9101011111212.255255index blockindex block(16)(16)nilnil5757595940404141nilnil0 01 12 23 34 45 56 67 78 89 9101011111212.255255index blockindex block(39)(39)第5页多层索引a.outa.out1616directory entrydirectory entryfilenamefilenameindex blockindex block0000 0101 0202 0303 0404 0505 0606 0707 0808 09091010 1111 1212 1313 1414 1515 1616 1717 1818 19192020 2121 2222 2323 2424 2525 2626 2727 2828 29293030 3131 3232 3333 3434 3535 3636 3737 3838 39394040 4141 4242 4343 4444 4545 4646 4747 4848 49495050 5151 5252 5353 5454 5555 5656 5757 5858 59592626343410104343nilnil0 01 12 23 34 45 56 67 78 89 9101011111212.255255top level index blocktop level index block(16)(16).0 01 12 23 34 45 56 67 78 89 9101011111212.255255.0 01 12 23 34 45 56 67 78 89 9101011111212.255255.0 01 12 23 34 45 56 67 78 89 9101011111212.255255.0 01 12 23 34 45 56 67 78 89 9101011111212.255255secondary index blockssecondary index blocks第6页组合链接/多层索引The Unix inodeThe Unix inodeowner,groupowner,grouptimestampstimestampssizesizedirect blocksdirect blockssingle indirectsingle indirectdouble indirectdouble indirecttriple indirecttriple indirectblock(data)block(data)block(data)block(data)block(data)block(data)block(data)block(data)block(data)block(data)block(data)block(data)block(data)block(data)block(data)block(data)block(data)block(data).(filename is not(filename is notstored in the inode)stored in the inode)index blockindex block(Used in BSD Unix)(Used in BSD Unix)第7页8.2.2 文件物理结构及存放设备2.文件存放设备n文件存放设备分为不可重复使用和可重复使用两类。n不可重复使用文件存放设备也称为I/O式字符设备，如打印纸等。n可重复使用文件存放设备有磁带、磁盘、光盘等，也称块设备。第8页8.2.2 文件物理结构及存放设备两种经典存放设备特征及存取方法。n(1)次序存取设备次序存取设备通常是指那些容量大、价格低存放设备。n(2)直接存取设备光盘、磁盘都是一个可直接存取存放设备(磁盘又分为硬盘和软盘)。n 磁盘磁盘是一个可直接存取(按地址存取)存放设备，它把信息统计在盘片上，每个盘片有正反两面。n 只读型光盘光盘存放器是利用光学原理存取信息存放设备 第9页8.2.2 文件物理结构及存放设备3.文件结构、存放设备与存取方式总而言之，文件物理结构，必须适应文件存放设备，而不一样存放设备特征，又决定了其上文件存取方式，下面以磁盘和磁带存放设备为例，简明说明3者关系：n 磁盘上文件结构为连续时，其存取方式普通为次序或随机。当文件为连续方式时，存取方式通常为次序。n 磁带上文件结构为连续时，其存取方式普通为次序存取。当其上文件为索引文件时，存取方式可为次序、随机两种形式。第10页8.3 文件管理8.3.1 文件目录结构1.文件目录n文件系统为程序和用户提供了按文件名存取文件机制，而将文件名转换为存放地址，以及对文件实施控制管理则需经过文件目录来实现。n文件目录管理和文件存放空间管理已成为文件管理主要内容。第11页8.3.1 文件目录结构一个文件由文件说明和文件体组成。文件说明部分包含文件基本信息、存取控制信息和文件使用信息。n 基本信息包含：n文件名，用于标识一个文件符号名。n文件物理位置，标明文件内容在外存上存放位置。n文件结构，指示文件逻辑结构和物理结构。它决定了文件寻址方式。n 存取信息包含：各类用户(包含文件主、核准用户、普通用户等)存取权限，实现文件共享及保密。n 使用信息包含：文件创建、修改日期和时间，以及当前使用状态信息。第12页8.3.1 文件目录结构n文件系统将这些说明部分全部信息集中起来，以一个数据结构形式表示，称此结构为文件控制块FCB(File Control Block)。n文件目录由文件控制块组成。文件系统在每个文件建立时都要为它建立一个文件目录。文件目录用于文件描述和文件控制，实现按名存取和文件信息共享与保护，随文件建立而创建，随文件删除而消亡。n不一样操作系统有不一样文件目录。第13页8.3.1 文件目录结构n下面以UNIX文件目录为例加以说明。nUNIX系统文件目录由目录项和索引节点两部分组成（i节点加紧文件检索方法之一）。目录项占16B，其中14B为文件名，2B为指向文件说明信息索引节点指针，每个索引节点占64B，包含文件属性、文件共享目录数、时间、文件存放块号、文件长度等说明信息。第14页8.3.1 文件目录结构2.文件目录结构n文件目录是由文件说明组成，若干个文件目录组成一个专门目录文件，目录文件结构怎样，关系到文件存取速度和文件共享及安全特征。n文件目录结构是指专门目录文件组织形式。惯用目录结构有单级目录，二级目录和多级目录。第15页8.3.1 文件目录结构n(1)单级目录文件系统在每个存放设备上仅建立一个目录文件目录结构，称为单级目录(或称一级目录)。目录文件中每一目录项(或称一条统计)对应一个文件目录，它包含相正确数据项(文件名及扩展名、物理地址、说明信息)，如图所表示。第16页8.3.1 文件目录结构n单级目录优点是结构简单，经过管理其目录文件，便可实现对文件信息管理。n单级目录特点是：n 搜索范围宽。n 不允许文件重名。n 不便于文件共享。第17页8.3.1 文件目录结构n(2)二级目录结构 二级目录结构将存放在设备上目录文件分成两级：第一级为系统目录(称主目录MFD)，它包含了用户目录名和指向该用户目录指针；第二级为用户目录(称UFD)，它包含了该用户全部文件文件目录，该文件目录和上述单级目录一样，包含了对应文件名字，物理地址等。第18页8.3.1 文件目录结构二级目录结构:第19页8.3.1 文件目录结构n(3)多级目录结构n采取树型数据结构方法，便形成一个树型结构目录。n这种文件目录第一级系统目录为树根节点，定义为根目录，文件目录第二级和以下各级目录均为树分支节点(非终节点)，均定义为子目录，只有树叶节点(终节点)才为文件。n注：树型目录每一级既可定义目录也可定义文件注：树型目录每一级既可定义目录也可定义文件 第20页树型目录usrusrbinbinetcetcdevdevhostshostsfstabfstabconfconfbinbinsbinsbinspoolspooltapetapetty0tty0tty1tty1tty2tty2rootrootdatedatevi viwhichwhichwhowhocalendarcalendarcroncronlplp第21页8.3.1 文件目录结构n从根目录经各级子目录抵达文件通路上全部子目录名称为文件存取路径。n文件绝对路径（从根目录开始）n文件相对路径（从当前目录开始）n在多级目录结构中，要访问一个文件必须从根目录开始，逐层查找各级子目录，直到文件。无疑这么查找速度较慢。有必要为系统建立一个称之为“工作目录”当前目录（加紧文件检索方法之二），它不一定是根目录，当用户不另外指定缺省目录时，系统从该目录起进行查找。不一样文件系统都能够设置这种工作目录。n将多级目录结构深入推广，就产生了无环结构目录图状结构目录。第22页8.3.1 文件目录结构3.文件目录与文件共享 为了有效实现文件共享，文件系统在建立文件目录过程中，采取了以下两种方法，使文件只需保留一个副本，到达多个用户共享目标。n(1)绕道法(交叉法)绕道法查找共享文件方法是每个用户从各自当前目录开始，向上返回到共享文件所在路径交叉节点，然后沿交叉节点次序向下访问到共享文件。第23页8.3.1 文件目录结构绕道法：第24页链接文件共享另一个方法n真正树型结构目录仅允许每个文件存在于该结构中一个地方。n一个文件或子目录出现在目录结构几个地方经常是方便。n比如，两个程序员正在某个相同项目上工作，都希望与项目关联若干文件保留在自己目录中。n共享文件（或目录）不一样于文件拷贝。第25页链接n在 Unix 系统中，共享文件能够经过创建链接来实现。nUnix 支持两种类型链接。n硬链接 是复制指向相同存放区目录条目n软链接（符号链接）是别名或其它文件或目录指针。(=在 MS Windows 中快捷方式)第26页链接usrusrbinbinetcetcvarvarbinbinsbinsbinspoolspoolrootrootdatedatevi viwhichwhichwhowhocalendarcalendarcroncronlplpadmadmmailmailspoolspool第27页硬链接file 1file 1file 2file 2file 3file 3file 4file 4file 5file 5file 6file 6file 7file 7directory adirectory afile-8file-8file 1file 1file 9file 9file 10file 10file 11file 11file 12file 12file 13file 13directory bdirectory bdiskdisk第28页软链接file 1file 1file 2file 2file 3file 3file 4file 4file 5file 5file 6file 6file 7file 7directory adirectory afile-8file-8file 1file 1file 9file 9file 10file 10file 11file 11file 12file 12file 13file 13directory bdirectory bdiskdisk第29页链接问题n链接可能引入一致性问题。n对于硬链接n当文件被删除时会发生什么？n对 Unix 系统，每个文件有链接计数。n当指向一个文件新链接建立时，该链接计数增加。n当一个文件被从目录中删除时，该链接计数降低。n假如链接计数是 0，该文件所占据空间被释放。第30页链接问题n对于软链接n假如原来文件被删除，那么全部软链接被留下悬空。n这就像发生在 MS Windows 快捷方式第31页8.3.1 文件目录结构n(2)基本文件目录表法*n为了有效实现系统文件共享，文件系统需建立一基本文件目录BFD，它包含了文件结构、物理块号、存取控制和管理信息。n另外，需增加符号文件目录表SFD，包含用户给定符号名和系统文件赋予文件说明信息内部标识符。n主目录(MFD)统计了文件名和系统给定惟一标识。第32页8.3.1 文件目录结构文件目录表：第33页8.3.1 文件目录结构在实现文件共享时，能够有以下两种模式：n 不一样时使用同一文件。n 同时使用同一文件。n当全部进程都不修改文件时，情况比较简单；n假如一些进程要求对文件修改，那么就必需加以控制，不然数据一致性就得不到确保。控制方法有两种：n一个是不允许读者与写者，或者写者与写者同时打开文件，但这会降低文件并发性，并可能造成死锁；n另一个是允许其同时打开文件，由OS为用户提供对应互斥伎俩，文件使用者借用这种伎俩确保对文件同时共享不发生冲突。第34页8.3.2 文件目录管理n如上所述，文件目录是以目录文件形式存放，当存取一个文件时，往往需要访问多级文件目录，假如对每一级目录访问都需要到文件存放设备上去搜索，势必占用过多CPU时间，若在系统开启时，把全部目录文件读入内存，由系统直接在内存实施对各级目录搜索则即使提升了访问速度，但需要内存容量太大。n普通来说，系统只把当前正在使用那些文件目录表（打开文件表加紧文件检索方法之三）复制到内存中，为此，系统提供两种特殊操作：n其一是把相关目录文件复制到内存指定区，通常称为打开文件(Open)；n其二是提供用户不再访问相关文件目录文件删除操作，通常称为关闭文件(Close)。第35页8.4 文件存放空间分配与管理 n由文件存放结构可知，文件信息交换都是以块为单位进行。所以，将文件存放设备称为块设备，这里介绍存放空间管理实际上是对文件块空间而言，详细说是指空闲块组织与回收。n普通来说，空闲块空间分配经常有两种方式：n一个静态分配；n另一个是动态分配。n另外在分配区域上，能够将一个文件分配在一个完整分区中（以块或簇为单位），常使用包含文件名、起始地址、长度文件分配表FAT等。第36页8.4.1 文件存放空间分配文件空间分配常采取：连续分配、索引分配、链接分配3种方法。1.连续分配连续分配方式是将文件存放在辅存连续存放区中。第37页8.4.1 文件存放空间分配2.索引分配n索引分配方法主要是利用文件分配表FAT给每个文件分配一个指出该文件索引表所在物理块号表目，索引表所在索引块与存放文件文件块是分离。n文件索引每个表目标设置有两种情况：n一个是直接给出索引文件各物理块；n另一个是设置文件起始块和长度，这有利于连续分配，也有利于节约索引表空间、提升效率，如图所表示。第38页8.4.1 文件存放空间分配第39页8.4.1 文件存放空间分配3.链接分配n链接分配文件空间方法是一个离散分配方式，适合用于文件长度需动态增减，或用户对其文件应用不十分明确情况，普通分配非连续辅存空间。n采取链接表方法链接存放空间，链接空间大小大多以区或段为单位。第40页8.4.1 文件存放空间分配n(1)以扇区为链接单位 这是给需动态改变文件分配若干磁盘扇区，这些扇区在磁盘上能够不连续，而分配给同一文件各扇区按其上文件逻辑统计次序用链指针链接起来。n(2)以区段(或簇)为单位分配 这不是以扇区为单位进行分配，而是以区段(或称簇)为单位进行分配。第41页8.4.2 磁盘空间管理 文件磁盘存放空间管理包含磁盘空间块分配和回收。1.盘块n盘块是操作系统传输数据基本单位，盘块大，I/O操作传输数据量多，传输性能好，但也会造成盘空间浪费。n既要提升传输率，又要降低盘空间浪费，是文件系统追求目标，盘块是主要原因之一。第42页8.4.2 磁盘空间管理n(1)逻辑块 逻辑磁盘是文件系统中一个抽象存放概念。系统将逻辑磁盘视为一些有固定大小可随机存取逻辑块线性序列。磁盘驱动程序将逻辑块映射到物理介质上。普通情况下，一个物理磁盘被分成物理上连续几个分区，每个分区就是一个逻辑磁盘，又称磁盘分区。通常所说磁盘分区就是将每一个分区定义为一个盘，此盘就是一个逻辑磁盘。n(2)盘区磁盘分区是将磁盘上一组连续柱面空间组成一体，定义为一个盘区。其上可有一个独立文件系统。不一样类文件系统可占有不一样盘，各自定义自己盘块大小。第43页8.4.2 磁盘空间管理2.磁盘块大小n 磁盘块大小。能够了解为磁盘分配单位，它要求了文件系统分配粒度和磁盘I/O粒度，盘块大，有利于增加系统性能，不一样文件系统块大小也不一样，FFS（FreeBSD 快速文件系统）可大于等于4KB，NTFS（NT内核文件系统，簇大小并不依赖于磁盘或分区大小）可大到64KB，FAT32簇大小可到达32KB。n 片断：是盘块组成单位。第44页8.4.2 磁盘空间管理3.盘块管理盘块管理惯用盘图，链表和i节点等伎俩，因文件系统而异。n(1)盘图法 盘图也称字位映像图，是一个惯用方法，它用位(bit)值0、1来表示磁盘上对应物理块是否被分配，bit值为1表示对应物理块被分配，为0表示对应物理块为空闲。对应一串连续bit值，按字节组成一张表，此表能够把一个完整磁盘使用情况记载下来。第45页盘图法n分配时：b（块号）=n（字长）*i（行号）+j（列号）n回收时：i（行号）=b（块号）div n（字长）j（列号）=b（块号）mod n（字长）n位m字0123456701100011110101111121100001134567第46页8.4.2 磁盘空间管理n(2)链接法n 链接索引块。这是一个惯用方法，它首先是选择若干空闲物理块建立索引表块，假设这么块大小为1KB，能够设512个表目，每个表目占用16位，以此表示一个空闲物理块块号，则每个表目对应一个空闲物理块。而后将这些含有空闲块号索引块之间用链接方式链接起来，即每个索引块第0个表目作为链表指针，指向下一个索引块，或链尾标志。第47页8.4.2 磁盘空间管理链接索引块：第48页8.4.2 磁盘空间管理n 分配与回收空闲块。为了操作方便，通常将索引链表中链头指针所指向索引块表目中留出空项(其它索引块表目项全填满)，当文件系统分配盘空间时从链表头索引块块尾开始，直到该索引块第0个表目，假如该索引块仅剩下第0个表目，则将该表目标内容读到特定块链头指针中，然后将原链头指针指向索引块T，分给请求分配空闲块文件。空闲块回收则相反，仅将释放空闲块块号加到链头指针指出索引表块尾部表目中即可。第49页8.4.2 磁盘空间管理Unix系统示例n在Unix操作系统中，把磁盘存放空间空闲块成组连接。每100个空闲块为一组，每一组第一个空闲块中登记下一组空闲块磁盘物理块号和空闲块总数，最终不足100块那部分磁盘物理块及块数记入专用块（超级块）中。第50页Unix系统示例假定共有空闲块438块，编号从12到449。空闲块数39504912空闲块数1001501495251空闲块数100250249152151空闲块数100350349252251空闲块数1000449352351专用块专用块 50#150#250#350#49#149#249#349#449#.12#51#151#251#351#第51页8.4.2 磁盘空间管理Unix系统示例n系统初始化时先把专用块内容读到主存，当有申请空闲块要求时，就直接在主存中能够找到哪些块是空闲，每分配一块后把空闲块数减1即可。n但要把一组中第一块分配出去之前能够先把登记在块中下一组块号保留到专用块中（不怕覆盖吗？）。n当一组空闲块分配完后，则再把专用块内容复制到主存，方便继续分配时查找。第52页8.4.2 磁盘空间管理Unix系统示例n偿还一块时，只要把偿还块块号登记到当前组中且空闲块数加1。n当一组已满100块时，则把主存中内容写到当前偿还那块中，作为新组第一块。第53页