张惠娟副教授Mszhj@163com.ppt

张惠娟副教授Mszhj163com Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望内容框架概述体系结构进程管理内存管理文件管理外设管理2内容Chp13:MassstorageStructureChp11:Filesystem3Module11:File-SystemFileConceptDirectoryStructureFree-SpaceManagementFileImplementationEfficiencyandPerformanceProtectionRecovery4引言文件定义文件系统定义FileAttributesFileOperationsFiletypeFileStructureAccessMethodsFileConcept5引言计算机应用程序都要：存储信息和检索信息 能够存储大量的信息 长期保存信息 可以共享信息FileConcept6解决方法文件 信息以一种单元，即文件的形式存储在磁盘或其他外部介质上。文件是通过操作系统来管理的，包括：文件的结构、命名、存取、使用、保护、实现方法。FileConcept7文件系统负责信息组织、存储和访问，提供高效、快速和方便的信息存储和访问功能。FileConcept8用户观点 文件系统如何呈现在其面前，如：一个 文件由什么组成、如何命名，如何保护 文件、可进行何种操作等。操作系统观点 文件目录怎样实现、怎样管理存储空间、文件存储位置、磁盘实际运作方式(与设备管理的接口)等等FileConcept9文件定义是一组带标识的、在逻辑上有完整意义的信息项的序列。其中：标识是文件名 信息项是构成文件内容的基本单位 长度是单个字节或多个字节 文件内容由文件建立者和使用者解释FileConcept10文件的各信息项之间具有顺序关系FileConcept编号：0 1 i n-1信息项信息项信息项信息项 信息项信息项.信息项信息项.读写指针11文件系统是操作系统中统一管理信息资源的一种软件。管理文件的存储、检索、更新，提供安全可靠的共享和保护手段，并且方便用户使用。FileConcept12文件系统的功能统一管理文件的存储空间，实施存储空间的分配与回收。实现文件的按名存取 名字空间 映射 存储空间实现文件信息的共享，并提供文件保护和保密措施FileConcept13向用户提供方便使用的接口 如提供对文件系统操作命令、提供对文件的操作命令：信息存取、加工等系统维护及向用户提供有关信息文件系统的执行效率提供与I/O的统一接口FileConcept14FileAttributesInformationaboutfilesarekeptinthedirectorystructure,whichismaintainedonthedisk.Nameonlyinformationkeptinhuman-readableform.Typeneededforsystemsthatsupportdifferenttypes.Locationpointertofilelocationondevice.FileConcept15Sizecurrentfilesize.Protectioncontrolswhocandoreading,writing,executing.Time,date,and user identificationdataforprotection,security,andusagemonitoring.FileConcept16FileOperationscreatewritereadrepositionwithinfilefileseekdeletetruncateFileConcept17open(Fi)searchthedirectorystructureondiskforentryFi,andmovethecontentofentrytomemory.close(Fi)movethecontentofentryFiinmemorytodirectorystructureondisk.FileConcept18Filetype分类目的 对不同文件进行管理,提高系统效率；提高用户界面友好性按信息保存期限分类 临时文件；永久文件；档案文件按文件保护方式分类 只读文件；读写文件；可执行文件FileConcept19按文件性质和用途分类系统文件用户文件库文件 FileConcept20按文件的逻辑结构分类 流式文件；记录式文件按文件的物理结构分类 顺序（连续）文件；链接文件；索引文件FileConcept21FileConcept22FileStructure逻辑结构 物理结构FileConcept23逻辑结构 是从用户角度研究文件的组织形式无结构文件有结构文件 FileConcept24一条记录一个字节字节序列 记录序列 树FileConcept25无结构文件：流式文件 构成文件的基本单位是字符，文件是有逻辑意义的、无结构的一串字符的集合。文件 一个无结构字节序列 好处 提供很大的灵活性FileConcept26有结构文件：记录文件 文件是由若干个记录组成，每个记录有一个键，可按键进行查找。文件 一个固定长度记录的序列，每条记录有其内部结构FileConcept27物理结构 从系统角度来看文件，从文件在物理介质上的存放方式来研究文件.连续（顺序）结构 链接结构 索引结构 FileConcept28连续结构（顺序）文件信息存放在若干连续的物理块中FileConcept29012345678910111213141516171819202122232425262728293031文件名文件名 始址始址 块数块数count 0 2tr 14 3mail 19 6list 28 4f 6 2 文件目录文件目录countftrmaillistFileConcept30优点简单 支持顺序存取和随机存取顺序存取速度快所需的磁盘寻道次数和寻道时间最少FileConcept31缺点 文件不能动态增长 预留空间:浪费 重新分配和移动 不利于文件插入和删除 外部碎片问题 存储压缩技术FileConcept32链接结构 文件信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块。FileConcept33文件目录文件名文件名 始址始址 末址末址jeep 9 2501234567891011121314151617181920212223242526272829303111016-125FileConcept34优点提高了磁盘空间利用率,不存在外部碎片问题有利于文件插入和删除有利于文件动态扩充FileConcept35缺点存取速度慢，不适于随机存取可靠性问题，如指针出错更多的寻道次数和寻道时间链接指针占用一定的空间FileConcept36索引结构文件信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构-索引表，并将这些块的块号存放在一个索引表中 一个索引表就是磁盘块地址数组,其中第i个条目指向文件的第i块FileConcept37012345678910111213141516171819202122232425262728293031文件名文件名 索引表地址索引表地址文件目录文件目录Jeep 19 916 11025-1-1-11938优点保持了链接结构的优点,又解决了其缺点：即能顺序存取,又能随机存取满足了文件动态增长、插入删除要求能充分利用外存空间FileConcept39缺点较多的寻道次数和寻道时间索引表本身带来了系统开销 如：内外存空间，存取时间FileConcept40索引表组织链接模式 一个盘块一个索引表,多个索引表链接起来多级索引 将一个大文件的所有索引表（二级索引)的地址放在另一个索引表（一级索引)中 综合模式 UNIX文件系统采用多级索引结构(综合模式)。FileConcept41综合模式每个文件索引表为13个索引项，每项2个字节。最前面10项直接登记存放文件信息的物理块号（直接寻址）如果文件大于10块，则利用第11项指向一个物理块，该块中最多可放256个文件物理块的块号（一次间接寻址）。对于更大的文件还可利用第12和第13项作为二次和三次间接寻址 UNIX采用了三级索引结构后，文件最大可达16兆个物理块FileConcept4243AccessMethods 顺序存取方式 随机(直接)存取方式FileConcept44存储介质存储介质物理结构物理结构存取方式存取方式磁带磁带连续结构连续结构顺序存取顺序存取磁盘磁盘连续连续链接链接索引索引顺序顺序顺序顺序顺序顺序随机随机 随机随机FileConcept45基本概念目录结构文件访问方法目录结构改进DirectoryStructure46基本概念文件控制块（FCB）文件控制块是操作系统为管理文件而设置的数据结构，存放了为管理文件所需的所有有关信息（文件属性）文件控制块是文件存在的标志DirectoryStructure47文件控制块内容NameTypeAddressCurrentlengthMaximumlengthDatelastaccessed(forarchival)Datelastupdated(fordump)OwnerID(whopays)Protectioninformation(discusslater)DirectoryStructure48文件目录 把所有FCB组织在一起，就构成了文件目录，即文件控制块的有序集合目录项 构成文件目录的项目（目录项就是FCB）目录文件 为实现对文件目录的管理，通常将文件目录以文件形式保存在外存，这个文件就叫目录文件。DirectoryStructure49目录结构目的一级目录二级目录树型目录（多级目录）其它方法DirectoryStructure50目的Efficiencylocatingafilequickly.Namingconvenienttousers.Twouserscanhavesamenamefordifferentfiles.Thesamefilecanhaveseveraldifferentnames.Groupinglogicalgroupingoffilesbyproperties,(e.g.,allPascalprograms,allgames,)DirectoryStructure51一级目录结构Asingledirectoryforallusers.DirectoryStructure52 优点 简单、易实现 缺点NamingproblemGroupingproblem DirectoryStructure53二级目录结构Separatedirectoryforeachuser.DirectoryStructure54优点PathnameCanhavethesaemfilenamefordifferentuserEfficientsearchingNogroupingcapability缺点增加系统开销DirectoryStructure55树型目录结构DirectoryStructure56优点层次结构清晰，便于管理和保护有利于文件分类解决重名问题提高文件检索速度能进行存取权限的控制 缺点 查找一个文件按路径名逐层检查，由于每个文件都放在外存，多次访盘影响速度DirectoryStructure57其它方法哈希表算法目录项信息存在一哈希表中搜索时根据文件名计算哈希值得到一个指向表中文件的指针其他算法 如B+树DirectoryStructure58文件访问方法目录检索 用户给出文件名，按名寻找目录项 根据路径名检索：全路径名：从根开始 相对路径：从当前目录开始DirectoryStructure59文件寻址 根据FCB中文件物理地址等信息，求出文件的任意记录或字符在存取介质上的地址，称为文件寻址。DirectoryStructure60 目录改进改进目的 加快目录检索DirectoryStructure61改进方法 采用目录项分解法，把FCB分成两部分。符号目录顶（次部）文件名，文件号 基本目录项（主部）除文件名外的所有项目 如：UNIX：I节点（索引节点）DirectoryStructure6263 例：一个FCB有48个字节，符号目录项占 8字节，文件名6字节，文件号2字节，基本目录项占 48-6=42字节。假设，物理块大小512字节DirectoryStructure64 解：分解前：占512/48=10个FCB 分解后：占512/8=64个符号目录项或512/42=12个基本目录项 假设：目录文件有128个目录项 分解前：占13块 分解后：符号文件占2块 基本文件占11块DirectoryStructure65 查找一个文件的平均访盘次数 分解前：(1+13)/2=7次 分解后：(1+2)/2+1=2.5次 减少了访问硬盘的次数，提高了检索速度DirectoryStructure66数据结构管理方法Free-SpaceManagement67数据结构空闲块表 所有空闲块记录在一个表中空闲块链表 把所有空闲块链成一个链 Free-SpaceManagement68管理方法位图法成组链接法Free-SpaceManagement69位示图 用一串二进制位反映磁盘空间中的分配使用 情况,每个物理块对应一位,分配物理块为1，否则为0。申请物理块时，在位示图中查找为0的位，返回对应物理块号；归还时，将对应位转置0 描述能力强，适合各种物理结构Free-SpaceManagement70计算公式已知字号i，位号j块号i字长j已知块号字号块号/字长位号块号mod字长Free-SpaceManagement71已知块号，则磁盘地址：柱面号块号/（磁头数扇区数）磁头号（块号mod（磁头数扇区数）/扇区数扇区号（块号mod（磁头数扇区数）mod扇区数已知磁盘地址：块号柱面号（磁头数扇区数）磁头号扇区数扇区号Free-SpaceManagement72成组链接法Free-SpaceManagement7374S.freeS.free100300299。201空闲盘空闲盘块栈块栈019910040039930110050049940175ProtectionFileowner/creatorshouldbeabletocontrol:whatcanbedonebywhomTypesofaccessReadWriteExecuteAppendDeleteList76FileImplementation数据结构文件执行77数据结构系统文件表用户文件表两种表间的关系FileImplementation78系统文件表系统打开文件表（整个系统一张）放在内存，用于保存已打开文件的FCB文件号、共享计数、修改标志FileImplementation79用户文件表 每个进程一个，进程的PCB中，记录了用户打开文件表的位置。FileImplementation80FileImplementation两种表间的关系用户打开文件表指向系统打开文件表多个进程共享同一个文件，则多个用户打开文件表目对应系统打开文件表的同一入口8182文件执行文件操作执行过程文件共享FileImplementation83文件操作提供设置和修改对用户文件存取权限的服务提供建立、修改、改变、删除目录的服务提供文件共享、设置访问路径的服务提供创建、打开、读、写、关闭、撤消文件等服务文件系统维护文件系统的转储和恢复FileImplementation84文件执行Create()Open()Read()FileImplementation85Create()实质是建立文件的FCB，并建立必要的存储空间，分配空FCB，根据提供的参数及需要填写有关内容，返回一个文件描述.FileImplementation86执行过程：1)检查参数的合法性2)检查同一目录下有无重名文件3)在目录中有无空闲位置4)填写目录项内容5)返回FileImplementation87Open()文件使用前都要先打开，即把FCB送到内存。fd=open（文件路径名，打开方式）FileImplementation88执行过程：1)根据文件路径名查目录，找到FCB主部；2)根据打开方式、共享说明和用户身份检查访问合法性；3)根据文件号查系统打开文件表，看文件是否已被打开；是共享计数加1，否则将外存中的FCB主部等信息填入系统打开文件表空表项，共享计数置为1；FileImplementation894)在用户打开文件表中取一空表项，填写打开方式等，并指向系统打开文件表对应表项。5)返回信息 fd：文件描述符，是一个非负整数，用于以后读写文件。FileImplementation90 Read()1)检查长度是否为正整数2)根据文件名查找目录，确定该文件在目录中的位置。3)根据隐含参数中的进程主和目录中该文件的存储权限数据，检查是否有权读？4)由文件内位置与要读的长度计算最末位置，将其与目录中的文件长度比较，超过否？FileImplementation915)根据参数中的位置、长度和目录中的映射信息，确定块号、块数、块内位移与长度。（多次读盘）6)根据下一块号读块至内存缓冲区7)根据块内位移长度取出要读的内容，送至参数中的内存目的地址8)根据块内长度或起始块号+块数，确定还读下一块吗？同时确定下一块块号FileImplementation92文件共享定义 一个文件被多个用户或程序使用目的 节省时间和存储空间，减少了用户工作量 进程间通过文件交换信息FileImplementation93实现方法 由系统目录实现对文件的共享 对要共享的文件进行连接 通过“连接（Link）”命令，在用户自己的目录项中对要共享的文件建立起相应的表目，即建立两个文件的等价关系FileImplementation9495EfficiencyandPerformanceEfficiencydependenton:diskallocationanddirectoryalgorithmstypesofdatakeptinfilesdirectoryentry96Performancediskcacheseparatesectionofmainmemoryforfrequentlysuedblocksfree-behindandread-aheadtechniquestooptimizesequentialaccessimprovePCperformancebydedicatingsectionofmemroyasvirtualdisk,orRAMdisk.EfficiencyandPerformance97VariousDisk-CachingLocationsEfficiencyandPerformance98一致性检查安全性写方式备份Recovery99一致性检查检查必要性一种检查方法Recovery100必要性磁盘块内存写回磁盘块在写回之前，系统崩溃，则文件系统出现不一致。因此，需要设计一个实用程序，当系统再次启动时，运行该程序，检查磁盘块和目录系统。Recovery101一种检查方法 两张表，每块对应一个表中的计数器，初值为0。Recovery102103104105106安全性写方式谨慎写 对写操作进行逐个排序的写方式更新磁盘的请求按一定顺序完成几项子操作更新磁盘FAT文件系统：通写磁盘修改立即写到磁盘 可恢复性好速度性能差Recovery107延迟写利用回写高速缓存的方法得到高速可恢复性差Recovery108可恢复文件系统采用事务日志来实现文件系统的写入既考虑安全性，又考虑速度性能Recovery109Recovery备份Usesystemprogramstoback updatafromdisktoanotherstoragedevice(floppydisk,magnetictape).Recoverlostfileordiskbyrestoringdatafrombackup.110