操作系统 第5章 文件管理

第5章文件管理1第5章文件管理主讲教师：张一品第5章文件管理2内容提要概述文件的结构和存取方式文件目录文件系统的实现文件空间的管理文件系统的安全性和数据一致性Linux的文件系统第5章文件管理35.1概述文件和文件系统文件是在逻辑上具有完整意义的信息集合，它有一个名字作标识文件系统是操作系统中负责存取和管理信息的模块，它用统一的方式管理用户和系统信息的存储、检索、更新、共享和保护，并为用户提供一整套方便有效的文件使用和操作方法。文件的基本特征文件的内容为一组相关信息文件具有保存性文件可按名存取第5章文件管理4文件系统的功能完成文件存储空间的管理实现文件名到物理地址的映射实现文件和目录的操作管理提供文件共享能力和安全可靠措施文件系统向用户提供了有关文件和目录操作的接口第5章文件管理5文件的分类按文件的性质和用途系统文件、库文件、用户文件按文件的组织形式普通文件、目录文件、特殊文件根据使用和管理情况临时文件、永久文件、档案文件按文件系统提出的保护级别读文件、读写文件、不保护文件按文件的数据流向输入型文件、输出型文件、输入输出文件按数据类型分类源程序文件、目标文件、可执行文件按设备类型磁盘文件、磁带文件、软盘文件第5章文件管理65.2文件的结构和存取方式文件组织指文件中信息的配置和构造方式，应该从文件的逻辑结构和组织及文件的物理结构和组织两方面考虑。文件的逻辑结构从用户观点出发，所观察到的文件组织形式，是用户可以直接处理的数据及其结构。即用户概念中的文件文件的物理结构文件在外存上的存储组织形式第5章文件管理7文件的存取方式顺序存取顺序存取是按照文件的逻辑地址顺序存取随机存取--直接存取随机存取法允许用户根据记录的编号存取文件的任一记录，读或写根据记录的逻辑编号索引存取索引存取是一种用在复杂文件系统，特别是数据库管理系统中的存取方法，基于索引文件的读取方法，读或写根据记录按键的某种顺序，而不是记录的逻辑编号，例如成绩的升序第5章文件管理8文件的逻辑结构设计文件系统时，选择逻辑结构应遵循的原则便于修改提高检索效率、使文件信息占据最小的存储空间便于用户进行操作第5章文件管理9文件的逻辑结构分类流式文件（无结构文件）无结构的流式文件是相关的有序字符的集合字符是构成文件的基本单位按长度读取查找困难、管理简单第5章文件管理10结构文件（记录式文件）在逻辑上被看成一组连续有序的记录的集合根据记录的长度分类：定长记录文件处理方便，直接存取变长记录文件处理麻烦，不能直接存取第5章文件管理11(a)定长记录文件；(b)变长记录文件(b)R0…Ri…RnLLL(a)R0…Ri…RnL0lL0L1lLilLiLnlLn第5章文件管理12记录式文件可把文件中的记录按各种不同的方式排列，构成不同的逻辑结构顺序文件索引文件索引顺序文件索引顺序文件是顺序文件的扩展，各记录本身在介质上也顺序排列，有直接处理和修改记录的能力。索引顺序文件能象顺序文件一样进行快速顺序处理，既允许按物理存放次序（记录出现的次序）；也允许按逻辑顺序（由记录主键决定的次序）进行处理。第5章文件管理13关键字逻辑地址姓名其它属性ABZAnBingAnKangAnQingBaoRongBiJingBonLong索引文件顺序文件索引顺序文件第5章文件管理14存储介质概念分类：磁盘、光盘、闪存、磁带卷：一盘磁带、一个磁(或温)盘组或一张软盘都称为一卷。卷是存储介质的物理单位单文件卷、多文件卷、多卷文件、多卷多文件。块：是存储介质上连续信息所组成的一个区域，也叫做物理记录物理单位是主存储器和辅助存储设备进行信息交换的物理单位，每次总是交换一块或整数块信息第5章文件管理15文件的存取方法顺序存储设备顺序存储存储设备是严格依赖信息的物理位置进行定位和读/写的存储设备前面物理块存取之后，后续物理块才能存取磁带机是一种典型的顺序存储设备第5章文件管理16直接存储设备直接存储设备又叫随机存储设备。允许文件系统直接存取对应存储介质上的任意物理块磁盘机是一种典型直接存储存储设备物理块位置：柱面号、磁头号、扇区号T表示每个柱面上的磁道数，S表示每个盘面上的扇区数，则第I个柱面，j磁b头，k扇区对应的块号b为b=k+s*(j+i*t)根据块号计算位置：每个柱面上有d=s*t个盘块，设m=[p/d],n=p%d柱面号=M磁头号=[N/S]扇区号=N%S第5章文件管理17例题1假定有一个磁盘组共有199个柱面，每个柱面上有16个磁道，每个盘面被划分为8个扇区，现有一个含有700个逻辑记录的文件，逻辑记录的大小与扇区的大小一致，该文件以顺序结构被存放在磁盘上，柱面、磁道、扇区、逻辑记录等编号从0开始，该文件信息从1柱面、5磁道、0扇区开始存放，试问：该文件的第380个逻辑记录位于哪个柱面的第几道磁道的第几道扇区第2柱面的第1磁道的第7扇区中存放了该文件的第几个逻辑记录第5章文件管理18解答分析：该文件的第380个逻辑记录位于哪个柱面的第几道磁道的第几道扇区柱面号=[380/128]=2，磁道号=[（380%128）/8]=[124/8]=15扇区号=[（380%128）%8]=[124%8]=4[2，15，4]+[1，5，0]=[3，20，4]=[4，4，4]第2柱面的第1磁道的第7扇区中存放了该文件的第几个逻辑记录7+8*（1+2*16）=271271-16*8-5*8=103第5章文件管理19练习：磁盘共有100个柱面，每个柱面有8个磁头，每个盘面分4个扇区。若逻辑记录与扇区等长，柱面、磁道、扇区均从0起编号。现用16位的200个字(0-199)来组成位示图来管理盘空间。现问：位示图第15个字的第7位为0而准备分配给某一记录，该块的柱面号、磁道号、扇区号是多少?现回收第56柱面第6磁道第3扇区，这时位示图的第几个字的第几位应清0?第5章文件管理20解析：位示图第15个字的第7位对应的块号=15×16(字长)+7=247，而块号247对应的：柱面号=247/(8×4)=7(从0编号，向下取整)磁头号=(247MOD32)/4=5扇区号=247MOD32MOD4=3块号=柱面号×柱面扇区数+磁道号×盘扇区+盘扇区=56×(8×4)+6×4+3=1819字号=1819/16=113位号=1819MOD16=11所以，回收第56柱面第6磁道第3扇区时，位示图的第113字的第11位应清0。第5章文件管理21文件的物理结构文件的物理结构也就是逻辑文件在物理存储空间中的存放方法和组织关系磁带文件的物理结构磁带机是一种顺序存取的设备，一切组织在磁带上的文件都采用顺序结构,磁带上的每个文件都有文件头标、文件信息和文件尾标三个组成部分第5章文件管理22磁盘文件的物理结构顺序文件将一个文件中逻辑上连续的信息存放到磁盘上的依次相邻的块上便形成顺序结构，这类文件叫顺序文件，又称连续文件优点：顺序访问容易、速度快缺点：要求有连续的存储空间、必须事先知道文件的长度第5章文件管理23连续文件起始物理块号(24)文件块数(4)文件说明24252627物理块号逻辑块号0123第5章文件管理24链接文件顺序的逻辑记录被存放在不连续的磁盘块上，用指针把这些磁盘块按逻辑记录的顺序链接起来，则形成了文件的链接结构分类：隐式链接，在每个盘块中部含有一个指向下一个盘块的指针；显示链接，把用于链接文件物理块的指针显式地存放在外存的一张链接表（FAT）中优点：消除了外部碎片、显著地提高外存空间的利用率、无需事先知道文件的长度、插入删除记录容易缺点：隐式链接，只适合于顺序访问、直接访问低效、可靠性较差；显示连接，不能支持高效地直接存取、存放链接指针的表会占用较大的内存空间第5章文件管理25链接文件起始块号(22)文件说明物理块号逻辑块号0121822271830273NULL30PTRS[22]=18、PTRS[18]=27、PTRS[27]=13、PTRS[30]=NULLFCB→22第5章文件管理266EOF11105EOF0123456789FATFCBA4FCBB9MS-DOS的文件物理结构第5章文件管理27直接文件----哈希文件定义：在直接存取存储设备上，记录的关键字与其地址之间可以通过某种方式建立对应关系，利用这种关系实现记录存取的文件称为直接文件“冲突”问题：地址的总数和记录的关键字之间并不存在一一对应的关系，不同的关键字经过变换可能会得到相同的地址解决“冲突”方法：设计出好的变换函数，并且还要求有好的处理冲突的方法优点：存取速度较快，存储空间不必连续，逻辑记录与物理记录之间不存在对应或顺序关系缺点：对冲突的处理需要时间和空间的开销第5章文件管理28哈希文件的构造过程构造转换(hash)函数建立目录文件查找文件溢出处理Hash函数目录文件A=1026号物理块file1文件控制块file2文件控制块01026f键值第5章文件管理29索引文件索引结构是实现非连续存储的另一种方法，适用于数据记录保存有随机存取存储设备上的文件。为文件分配索引块，存放该文件分配的所有盘块号，文件目录项记录该文件索引块的盘块号和文件长度。……文件控制块(a)无键索引表块块块两种索引文件结构示意图…Key1记录键盘块号Key2……KeyN(b)有键索引表文件控制块第5章文件管理30一级索引：只有一个索引块的索引文件二级索引：若为文件分配的索引块为多个，需要为多个索引块再建立一级索引，称为第一级索引，存放索引块的盘块号，就形成了二级索引。多级索引。优点：支持直接访问缺点：索引要花费较多的存储空间混合索引分配方式：指将多种不同级的索引分配方式结合而形成的一种分配方式，有效且实用第5章文件管理31UNIX/Linux多重索引结构01234567891011120…127…0…1270…1270…127…………0…1270…1270…127…0…1270…127…0…1270…127…………………………第5章文件管理32例题2存在某个磁盘上的文件系统，采用混合索引分配方式，其FCB(文件控制块)中共有13个地址，0-9为直接地址，第十个地址为一次间接地址，第十一个地址为二次间接地址，第12个地址为三次间接地址，如果每个盘快的大小为4KB，若每个盘块需要4个字节来描述，则该系统中文件的最大长度是多少？解析：每块中存放的盘块号的数量为4KB/4B=1KB文件的最大长度为：4KB*(10+1K+1k*1K+1k*1k*1K)第5章文件管理33记录式的成组分解概念对于记录式文件，把若干个逻辑记录合成一组存入一块的工作称“记录的成组”每块中的逻辑记录个数称“块因子”从一组逻辑记录中把一个逻辑记录分离出来的操作称“记录的分解”磁带文件的记录成组分解记录的成组和分解可提高磁盘空间利用率磁盘文件的记录成组分解记录的成组和分解不仅可以提高存储介质的利用率，还能减少启动设备的次数。但是记录的成组和分解需要设立主存缓冲区和操作系统增加成组分解操作的功能才能够实现第5章文件管理34例题3假定磁带的记录密度为每英寸800个字符，文件A的每一个逻辑记录长度为160个字符，块与块之间的间隔为0.6英寸，现有200个逻辑记录需要存储在磁带上，一个逻辑记录占用一个物理块，块之间以间隔分割，试计算未分组的磁带空间利用效率。一个记录160个字符，占用空间大小160/800=0.2空间利用效率=物理块长度/(物理块长度+间隔)=0.2/(0.2+0.6)=25%若采取12个记录一组，计算其空间利用效率12个逻辑记录为一组，则物理块大小为一个记录160个字符，则12个记录占用空间大小160*12/800=2.4空间利用效率=物理块长度/(物理块长度+间隔)=2.4/(2.4+0.6)=80%第5章文件管理35练习