第10章 文件管理1

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第10章 文件系统,文件系统负责管理外存上的文件，并为用户提供对文件进行存取、共享及保护手段。,10,。,1,概述,10,。,1,。,1,文件和文件系统,文件（,files,）是有名字的、存储在某种介质上的一组有意义的信息。名字、信息和介质是文件三个不可缺少的基本要素；,作为一种数据结构，文件可划分为记录，记录又可划分为数据项，,数据项是可以命名和存取的最小逻辑单位；,文件可以有各种不同的分类方法，见,P,214-215,。,10,。,1,。,2,文件系统,文件系统（,FS,：,File System,）这个词，在不同的上下文可以有不同的含义（,），这里我们把它理解为操作系统中与管理文件有关的软件和数据的集合；,文件系统的功能是：,1,，实现文件的按名存取；,2,，为用户提供接口；,3,，实施对文件和目录的管理；,4,，文件存储空间的分配及回收；,4,，文件的共享及保护；,文件系统的软件体系结构,文件系统的软件体系结构从下往上共有五层：,基本,I/O,控制层；,基本文件系统层；,基本,I/O,管理程序层；,逻辑文件系统层；,文件系统接口；,不同的系统层次的划分可能不一样，上面只是其中一种划分方法；,每个层次的功能见,P,214,的说明。,文件系统的软件体系结构图,层次的上下级关系是按调用原则确定的。,文件系统接口,逻辑文件系统层,基本,I/O,管理程序层,基本文件系统层,基本,I/O,控制层,用户存取要求,物理磁盘,10.2 文件结构及存储设备,文件结构指文件的组织形式，文件有两种形式的结构：,逻辑结构：,又称文件组织，是从用户观点出发所看到的文件组织形式；,物理结构：,又称文件的存储结构，是文件在外存上的存储形式。它与存储设备特性、外存分配方式有关；,10,。,2,。,1,文件的逻辑结构,文件的逻辑结构可分为两类：,记录式文件：,是一种有结构文件，由一组相关记录组成。又分为：,等长记录文件：又称定长记录文件，是指文件中所有记录的长度相等；,变长记录文件：是指文件中各记录长度不相等；,流式文件：,是一种无结构文件，由字符序列构成。流式文件可看做是以一个字符为一个记录的文件；,一个系统的文件是流式的还是记录式的要从系统调用指令的参数来判断；,9,。,2,。,2,文件的物理结构,文件的物理结构指的是一个文件在外存上的存储组织形式，它与存储介质的存储特性有关；,文件存储设备通常是块设备，物理块是分配及传输文件信息的基本单位。物理块的大小与设备有关，但与逻辑记录的大小无关，因此一个物理块中可以存放若干个逻辑记录，一个逻辑记录也可以存放在若干个物理块中；,常见的文件物理结构有以下几种形式：,顺序结构；,链接结构；,索引结构；,顺序结构,顺序结构又称连续结构，它将一个在逻辑上连续的信息存放在外存连续的物理块中；,以顺序结构存放的文件称为顺序文件或连续文件；,特点：,顺序存取速度较快；对等长记录文件支持随机访问。但因要求连续存放，会产生碎片，同时也不利于文件的动态扩充。,链接结构,链接结构又称串联结构，它将一个逻辑文件的信息存放在外存不连续物理块中，且在每个物理块中设置一个指向下一个物理块的指针；,采用链接结构存放的文件称为链接文件或串联文件；,特点：,可解决碎片问题，便于文件动态增长。但只能顺序访问，因而查找效率较低，指针占用存储空间。,索引结构,索引结构将一个逻辑文件的信息存放于外存的若干个物理块中，并为每个文件建立一个索引表，其中的每个表目存放文件信息所在的逻辑块号和与之对应的物理块号；,采用索引结构存放的文件称为索引文件；,特点：,既可以顺序访问也可以随机访问，但增加了存储空间开销，且要两次访问外存。,10,。,2,。,3,文件的存取方法,常用的文件存取方法有：,顺序存取法；,直接存取法；,按键存取法；,顺序存取法,顺序存取法是按照文件信息的逻辑顺序依次存取；,在记录式文件中，顺序存取反映为按记录的排列顺序来存取；在流式文件中，顺序存取反映为当前读写指针的变化方式；,对定长记录的顺序文件，若知道当前记录地址，则很易确定下一个记录地址：,rptr,rptr,L,其中,L,为文件记录的长度，,rptr,为读写指针。,直接存取法,直接存取法又称随机存取法，允许按任意顺序存取文件中的任何一个物理记录；,对于定长记录的顺序文件，若知道文件的起始地址和记录长度，则第,i,个记录（,i0，1，2，）,的首地址为：,rptr,addr,iL,其中,addr,是该文件的首地址，,L,为记录长度。,按键存取法,按键存取法实质上也是直接存取法，它是根据文件记录中的数据项，通常称为关键字，经过某种方法计算处理，转换成相应的物理地址后进行存取。这种方法有时也叫散列存取法，或者相联存取法。,10,。,2,。,4,文件存储设备,文件的存储设备主要有磁带、磁盘、光盘等；,存储设备的特性可以决定文件的存取方法；,下面介绍以磁带为代表的顺序存取设备和以磁盘为代表的直接存取设备。,磁带,磁带是一种典型的顺序存取设备。由于磁带机的启动和停止要花费一定的时间，因此在磁带的相邻物理块之间设计有一段间隙将它们隔开，如下所示。,磁带,间隙 第,i,块 间隙 第,i1,块 间隙,磁带（续）,磁带的存取速度与信息密度（字符数,/,英寸）、磁带带速（英寸,/,秒）和块间间隙有关；,如果带速高、信息密度大且所需块间隙（磁头启动和停止时间）小，则磁带存取速度高。反之，若磁带带速低、信息密度小且所需块间隙（磁带启动和停止时间）大，则磁带存取速度低。,磁盘,磁盘是典型的直接存取设备；,磁盘一般由若干磁盘片组成，可沿一个方向同轴高速旋转。每个盘面对应一个磁头，磁臂可沿半径方向移动；,磁盘上的一系列同心圆称为磁道，磁道沿径向又分成大小相等的多个扇区，不同盘片半径相同的所有磁道组成一个柱面；,磁盘上的每个物理块可用柱面号，磁头号和扇区号表示。,磁盘数据组织和格式示意图,磁臂,磁头,3,0,1,2,3,4,5,6,7,磁道 第,i,扇区,间隙 标识字段 间隙 数据字段 间隙,磁盘访问时间,磁盘访问时间由三部分组成：,寻道时间：,指将磁头从当前位置移动到指定磁道所经历的时间。由启动磁臂时间和磁头移动多条磁道的时间构成；,旋转延迟时间：,指扇区移动到磁头下面所经历的时间。平均旋转延迟时间是每转所需时间的一半；,传输时间：,指从磁盘上读出数据或向磁盘写入数据所经历的时间；,由于这三部分操作均涉及机械运动，故磁盘块的访问时间约为0.010.1,s,之间，其中寻道时间所占的比例最大。,存储设备、存取方法与物理结构间的关系,文件的物理结构与文件存储器的特性和存取方法密切相关；,磁带是一种顺序存取设备，适合采用顺序结构存放文件，相应的存取方法通常是顺序存取法；,磁盘属于直接存取存储设备，前述的几种物理结构都可以采用。存取方法也可以多种多样。,存储设备,磁 盘,磁 带,物理结构,顺序结构,链接结构,索引结构,顺序结构,存取方法,顺序、直接,顺序,顺序、直接,顺序,磁盘调度算法,磁盘是可以被多个进程“同时”使用的设备。当有多个进程都请求访问磁盘时，应采用一种适当的调度算法确定它们的执行顺序，以使各进程对磁盘的平均访问时间（主要是寻道时间）最短。这些调度算法有：,1,，先来先服务,FCFS,；,2,，最短寻道时间优先,SSTF,；,3,，扫描法,SCAN,；,4,，循环扫描法,CSCAN,；,下面逐一介绍。,设从100号磁道开始，磁盘访问请求的执行顺序为：55、58、39、18、90、160、150、38、184；,先来先服务算法,先来先服务算法按进程请求访问磁盘的先后次序进行调度。特点是简单易行，但未对寻道进行优化。,平均寻道长度为：55.3,146,184,10,150,112,38,70,160,72,90,21,18,19,39,3,58,45,移动距离,55,下一磁道号,最短寻道时间优先算法,最短寻道时间优先算法选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象；,特点：寻道性能比,FCFS,好，但可能会使某些请求总也得不到服务；,平均寻道长度为：27.6,24,184,132,150,10,160,20,18,1,38,16,39,3,55,32,58,10,移动距离,90,下一磁道号,扫描法-,SCAN,SCAN,算法在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象。因这种算法中磁头移动规律颇似电梯的运行，故又称为电梯调度算法；,特点：具有较好的寻道性能，能避免进程饥饿，但不利于两端磁道的请求；,平均寻道长度为：27.8,20,18,16,39,1,38,3,55,32,58,94,90,24,184,10,160,50,移动距离,150,下一磁道号,循环扫描算法,CSCAN,CSCAN,算法是,SCAN,算法的改良，它规定磁头单向服务。例如，自里向外移动时服务，自外向里时空跑，如此循环进行扫描；,特点：该算法消除了对两端磁道请求的不公平；,平均寻道长度为：35.8,32,90,16,55,3,58,1,39,20,38,166,18,24,184,10,160,50,移动距离,150,下一磁道号,10.3 文件存储空间的分配与管理,10,。,3,。,1,文件存储空间的分配,文件存储空间的分配常采用以下两种策略：,静态分配：,在文件建立时一次分配所需的全部空间；,动态分配：,在运行中根据需要进行分配和回收；,文件存储空间的分配通常以块或簇为单位，一个簇是几个连续的物理块；,常用的文件存储空间分配方式有：,连续分配；,链接分配；,索引分配；,连续分配示意图,为文件分配连续的磁盘空间；,用户必须在分配前说明待创建文件所需的存储空间大小。然后系统查找空闲区管理表，若有就给文件分配所需的存储空间，否则文件不能建立。,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,文件,A,目录,文件名 起始块号 长度,A 2 3,B 9 5,C 18 8,文件,B,文件,C,链接分配,链接分配有两种实现方案：,以扇区为单位的链接分配；,以区段（簇）为单位的链接分配；,以扇区为单位的链接分配：,按文件的要求分配若干个磁盘扇区，属于同一文件的各扇区按文件记录的逻辑次序用链接指针链接起来；,当文件增长时就为文件分配新的空闲扇区，并将其链接到文件链上；同样当文件缩短时将释放的扇区归还给系统；,特点：,消除了碎片，不需要压缩。但查找慢，链接指针的存储及维护有一些开销；,链接分配示意图,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,文件,B,目录,文件名 起始块号 长度,B 1 5,以区段（或簇）为单位分配,以区段（或簇）为单位分配,是连续分配和非连续分配的结合，现广为使用。区段由若干个连续扇区组成，文件所分各区段可以用链接指针、索引表等方法来管理；,文件分配表,FAT,是该分配方法用以记录磁盘分配现状的数据结构；该表整个磁盘仅设一张，其结构如下屏所示。表的序号是物理块号，从,0,开始直至,N,1,（,N,为盘块总数）；每个表项中的内容为存放文件的下一个盘块号；文件的首地址（第一个盘块号）存放在该文件的目录中。从目录中找到文件的首地址后，根据,FAT,就能找到文件在磁盘上的所有物理块号；,文件分配表示意图,文件控制块（,FCB,）保存的块号是,2,，通过查,FAT,，可获得该文件的块号序列为：,2,，,4,，,5,，,1,；,FCB,0,4,5,1,2,FAT,物理块号,0,1,2,3,4,5,文件分配表讨论（,1,）,假定磁盘块的大小为1,KB，,对于1.2,MB,的软盘，其文件分配表,FAT,需要占用多少存储空间？,该