西安交通大学操作系统原理课件第十到十一章

Chapter10FileSystem•FileConcept(文件概念)•FileStructure(文件结构)•AccessMethods(存取方法)•DirectoryStructure(目录结构)•FileOperations(文件操作)•Free-SpaceManagement(自由空间管理)•Protection(保护)•EfficiencyandPerformance(效率和性能)FileSystemFunction•实现逻辑文件与物理文件间的转换(文件组织)•有效分配和管理文件存储空间•目录管理，实现文件的按名存取–名字空间映射存储空间•提供合适的存取方法(顺序\随机)•进行存取控制验证(安全性)•为用户提供文件操作(使用接口)FileConcept•Afileisanamedcollectionofrelatedinformationthatisrecordedonsecondarystorage.•Types：（类型）–Data（数据）•Numeric（数字）•Character（字符）•Binary（二进制）–Program（程序）FileAttributes•Informationaboutfilesarekeptinthedirectorystructure，whichismaintainedonthedisk.（属性信息保存在磁盘上的目录结构中）–Name–onlyinformationkeptinhuman-readableform.（文件名：唯一的以人们可以理解的方式保存的信息）–Type–neededforsystemsthatsupportdifferenttypes.（类型：需要系统提供支持）–Location–pointertofilelocationondevice.（位置：指向文件在设备上的存储位置的指针）–Size–currentfilesize.（大小：当前文件的大小）–Protection–controlswhocandoreading，writing，executing.（保护：控制对文件的读取，改写和执行的权限）–Time，date，anduseridentification–dataforprotection，security，andusagemonitoring.（时间，日期和用户身份：保护和安全需要的数据）FileTypes•按用途分类：–系统文件：由系统软件构成的文件，大多数系统文件只允许用户调用，而不允许用户去读或修改它。–库文件：指由系统提供给用户使用的各种标准子程序库。这类文件允许用户调用，但不允许用户修改。–用户文件：用户委托文件系统保存的文件。如源程序，目标程序，原始数据等。FileTypes•按文件的保护方式分类只读文件；读写文件；只执行文件•按文件的逻辑结构分类流式文件；记录式文件•按文件的物理结构分类顺序（连续）文件；链接文件；索引文件FileTypes•按信息流向分类:–输入文件–输出文件–输入/输出文件(存储设备)•按文件中的数据分类:–源文件–目标文件–可执行文件FileTypes•按文件的性质分类:–普通文件–目录文件–特殊文件StorageDevice文件的存储设备•文件的存储设备主要有磁带，磁盘，光盘等，存储设备的特性可以决定文件的存取方法。•物理块（块）–文件的存储设备常常划分为若干大小相等的物理块–以块为单位进行信息的存储、传输StorageDevice文件的存储设备•磁带：–永久保存大容量数据;–顺序存取设备：前面的物理块被存取访问之后，才能存取后续物理块的内容;–存取速度较慢：主要用于后备存储，或存储不经常用的信息，或用于传递数据的介质;第i块间隙第i+1块StorageDevice文件的存储设备•磁盘：–直接存取设备，三种文件物理结构都可以采用•若文件是顺序存取的，采用顺序结构和链接结构都可行•若采用直接存取方式且文件大小不固定，则应采用索引结构磁道扇区FileStructureandAccessMethods•AccessMethod•LogicalStructure•PhysicalStructureAccessMethods•与文件的组织方式有关•常用的存取方法：–Sequentialaccess(顺序存取)–Directaccess(直接/随机存取)AccessMethods•Sequentialaccess–Thesimplestaccessmethod–按照文件信息的逻辑顺序依次存取•在记录文件中:按记录的排列顺序来存取•在流式文件中:反映为当前读写指针的变化，在存取完一段信息后，读写指针自动加上这段信息的长度，以便指出下次存取时的位置–Worksaswellonsequential-accessdevicesasitdoesonrandom-accessonesAccessMethods•Directaccess–随机存取是根据记录的编号来直接存取文件中的任意一个记录，而无需存取其前面的记录。–对于连续文件(固定长度),第i个记录的地址(addr0为首记录地址,L为记录长度):rptr:=addr0+i*L–对于索引文件:先随机查找索引表,再取地址FileStructure•逻辑结构:用户对文件的组织结构•物理结构:文件在外存储器上的存储结构•物理结构直接影响存储空间的使用和检索文件信息的速度;•逻辑文件保存到存储介质上的工作由文件系统来做，这样可减轻用户的负担。文件的逻辑结构•文件从逻辑结构上分成二种，一种是无结构的流式文件，另一种是有结构的记录式文件。–流式文件是指对文件内信息不再划分单位，它是依次的一串字符流构成的文件。–记录式文件是用户把文件内的信息按逻辑含义划分独立的信息单位，每个单位称为一个逻辑记录（简称记录）。所有记录通常都是描述一个实体集的，有着相同或不同数目的数据项，记录的长度可分为定长和不定长记录两类。文件的逻辑结构-顺序文件(SequentialFile)•顺序文件的所有记录按键值的约定次序组织•记录可以是定长的，也可以是变长的•顺序文件常用于批量记录读取，对于访问某个记录的请求则处理性能不佳文件的逻辑结构-顺序文件(SequentialFile)•对于定长记录文件，若要查找第i个记录，可根据下式得到相对于第一个记录首址的地址：Ai=i*d（d为记录的长度）;•对于非定长记录文件，若要查找第i个记录，则需要有每个记录的长度：Ai=∑di+i（d为记录的长度）;•为解决这类问题，往往建立一张索引表，记录下每个记录的长度及指向该记录的指针，从而方便了直接存取;文件的逻辑结构-索引文件(IndexedFile)•索引文件对主文件中的记录按需要的数据项（一个或几个）建索引表;•为每个记录设置一个表项;•索引文件本身是顺序文件组织.文件的逻辑结构-索引顺序文件(IndexedSequentialFile)•索引顺序文件是基于键的约定次序组织的。将顺序文件中的所有记录分为若干个组；再为顺序文件建立一张索引表，表中记录每个组的第一个记录，该索引项包含记录的键值和指向该记录的指针。它是顺序文件和索引文件的结合。•检索时，先根据关键字去检索索引表，找到该记录所在组的第一个记录的位置，然后再利用顺序查找法去查找主文件，找到所需记录关键字逻辑地址姓名其它属性ABZAnBingAnKangAnQingBaoRongBiJingBonLong索引文件顺序文件索引顺序文件文件的物理结构•文件在外存的存放组织形式称为文件的物理结构•文件的物理结构取决于外存的分配方式–连续分配——顺序结构–链接分配——链接结构–索引分配——索引结构文件的物理结构-顺序结构•将逻辑上连续的文件信息依次存放在外存连续的物理块中–优点：•简单,支持随机存取和顺序存取•顺序存取速度快•所需的磁盘寻道次数和寻道时间最少–缺点：•要求连续的存储空间•会产生碎片•要求用户给出文件最大长度:不利于文件的动态扩充•不利于文件的插入和删除ContiguousAllocationContiguousallocationofdiskspacefor7filesStateofthediskafterfilesDandFhavebeenremoved顺序结构ContiguousAllocationofDiskSpace文件的物理结构-链接结构•隐式链接：一个文件的信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块;•优点：–提高了磁盘空间利用率,不存在外部碎片问题;–有利于文件插入和删除;–有利于文件动态扩充;LinkedAllocation•缺点：–存取速度慢，不适于随机存取–可靠性问题，如指针出错–更多的寻道次数和寻道时间•链接结构的一个变形:显式链接–文件分配表FAT（整个磁盘只有一张）文件的物理结构-链接结构FAT文件分配表文件的物理结构-索引结构•一个文件的信息存放在若干不连续物理块中，系统为每个文件建立一个索引表，并将这些块的块号存放在索引表中;•一个索引表就是磁盘块地址数组,其中第i个条目指向文件的第i块;ExampleofIndexedAllocation文件的物理结构-索引结构•优点:–保持链接结构的优点，又克服了其缺点:•既能顺序存取又能随机存取;•满足了文件动态增长\插入删除要求;•能充分利用外存空间;•缺点:–较多的寻道次数和寻道时间;–索引表本身带来了系统开销,如：内外存空间，存取时间;•索引表组织:–链接模式:大的文件，索引表占了若干个盘块，一个盘块一个索引表,多个索引表链接起来–多级索引:将一个大文件的所有索引表（二级索引)的地址放在另一个索引表（主索引，一级索引)中•在两级索引分配方式，若每个盘块大小为1KB，每个盘块号占4字节，则一个索引块中可存放256个盘块号。则两级索引最多可包含的盘块号总数为64K个（256*256）。因此，所允许的文件的最大长度为64MB（64K*1KB）。文件的多级索引结构•混合索引UNIX文件系统采用的是多级混合索引结构(综合模式)。每个文件的索引表为13个索引项，每项2个字节。最前面10项直接登记存放文件信息的物理块号（直接寻址）如果文件大于10块，则利用第11项指向一个物理块，该块中最多可放256个物理块的块号（一次间接寻址）。对于更大的文件还可利用第12和第13项作为二次和三次间接寻址CombinedScheme:UNIXUFS(4Kbytesperblock)块地址指针1块地址指针2块地址指针3块地址指针4块地址指针5块地址指针6块地址指针7块地址指针8块地址指针9块地址指针10地址指针11地址指针12地址指针13数据块数据块数据块...一级索引表数据块数据块...数据块数据块......一级索引表二级索引表一级索引表二级索引表三级索引表.........数据块数据块直接盘块UNIX混合索引I节点存储设备，访问方式和文件物理结构之间的关系存储设备磁盘磁带物理结构顺序结构链接结构索引结构顺序结构存取方法直接或顺序顺序直接或顺序顺序文件长度固定可变/固定可变/固定固定FileDirectory•Somesystemsstoremillionsoffileondisk.•Tomanageallthesedata,weneedtoorganizethem.•Thisorganizationinvolvestheuseofdirectory.FileDirectory•Acollectionofnodescontaininginformationaboutallfiles;•Boththedirectorystructureandthefilesresideondisk;F1F2F3F4FnDirectoryFilesFiledirectory•文件控制块FCB–用于描述和控制文件的数据结构，它至少要包括文件名和存放文件的盘物理地址–文件控制块的有序集合称为文件目录，即一个文件控制块FCB就是一个文件目录项。AFCBcontains•文件基本信息：文件名，用户