操作系统18-文件1

18..1/332020年1月操作系统第五章文件系统P2035.1文件和文件系统5.2文件逻辑结构5.3目录管理5.4外存存储空间管理5.5文件共享和保护内存空间有限，无掉电保护不利于长期存放.解决办法：必须将信息资源以文件的形式存放到外存介质上软件资源存放于外存的必要性外存文件的管理文件的逻辑组织文件的共享与保护文件在外存上的存放18..2/332020年1月操作系统文件：具有文件名的一组相关信息的集合，是信息组织的一种通用形式。文件的组成:5.1文件及文件系统5.1.1文件的基本概念18..3/332020年1月操作系统学号学生成绩课程1成绩课程2成绩学号课程1成绩课程2成绩学号课程1成绩课程2成绩学号课程1成绩课程2成绩记录课程1数据项*数据项是数据组织中的最小单位，用于描述一个对象的某种属性表征一个具体的数据项时：数据项名；数据项数据类型；数据项的数据（值）*记录是若干相关数据项的集合。相对完整的描述一个对象。关键字：能够唯一标识一个记录的一个或多个数据项*文件由若干相关记录组成，描述对象的集合数据项，记录，文件18..4/332020年1月操作系统5.1.2文件的分类按用途分类：（1）系统文件（2）用户文件（3）库文件按文件中的数据形式分类：（1）源文件（2）目标文件（3）可执行文件文件按保护方式类：（1）只读文件（2）读写文件（3）执行文件按文件的性质类：（1）普通文件（2）目录文件（3）特殊文件18..5/332020年1月操作系统文件系统是操作系统中含有大量文件及其属性说明，对文件进行操纵和管理的软件，以及向用户提供使用文件的接口的集合。5.1.3文件系统模型P206文件系统接口对对象操纵和管理的软件集合逻辑文件系统基本I/O管理程序（文件组织模块）基本文件系统（物理I/O层）I/O控制层(设备驱动程序)对象及其属性说明(文件、目录、磁盘)文件和记录的相关操作：允许用户和应用利用符号文件名访问文件及其中的记录。1）选择文件所在设备2）逻辑块号-物理块号3）管理空闲盘块4）指定I/O缓冲区最底层：启动I/O操作，处理设备中断处理内外存间数据块的交换(1)(2)(3)(4)18..6/332020年1月操作系统例：用户访问文件的过程用户通过符号文件名访问文件（4）盘号变换：逻辑盘号－物理盘号（3）找到文件在外存上的位置启动I/O操作（1）进行内存外存间数据块的交换（2）在内存中进行进一步的操作（.doc/.exe…）18..7/332020年1月操作系统5.2文件逻辑结构P208任何文件都存在两种类型的结构：设计要求：访问性能：便于检索；便于修改存储性能：向物理存储转换方便，节省空间文件的物理结构（物理组织）：文件在外存上的存储组织形式。文件的逻辑结构（逻辑组织）：文件的逻辑组织是指从用户观点出发讨论文件内部的逻辑结构(logicalstructure)或用户访问模式；它可以独立于外存上的物理存储。18..8/332020年1月操作系统1.文件逻辑结构的类型1）有结构文件：记录式文件文件是记录的集合.每个记录由彼此相关的数据项构成。如果文件中所有记录的长度都相同，则这种文件为定长记录文件定长记录文件的长度=记录个数X记录长度。变长记录文件的长度为各记录长度之和。例如:学生登记表文件xsdjb.mdb姓名学号籍贯通信地址邮政编码李铭925678武昌武昌关山街125号430074司马乐925679北京北京海军路88号10003418..9/332020年1月操作系统文件由字节流组成，称为流式文件。不划分记录，顺序访问，每次读写访问可以指定任意数据长度。DOS、WINDOWS系统中的普通文件都是流式文件。UNIX中所有文件都看作是流式文件，系统不对文件进行格式处理2）无结构文件（如源程序、可执行程序、库函数）：18..10/332020年1月操作系统流式文件就象给一张白纸给用户，用户可将他的信息意地写到纸上，没有任何格式上的限制。记录式文件就象给一张表格给用户，用户要按表规定格式填信息。显然，结构式文件对用户的限制很大，使用起来就不方便,但处理起来简便容易.3）两种文件的比较18..11/332020年1月操作系统2、文件的存取方法（访问方法）顺序存取：是按照文件的逻辑地址顺序存取，后一次存取总是在前次存取的基础上进行的。在有结构文件中，这反映为按记录的排列顺序来存取，例如：当前记录为Ri，则下一条记录为Ri+1在流式文件中，顺序存取反映当前读写指针的变化，例如：当前指针rPtr,下一存取位置的指针为rPtr+1随机存取（直接存取）：允许用户根据记录的编号来存取文件的任一记录，或者是根据存取命令把读写指针移动到欲读写处来读写。每次存取操作都要指定存取操作的开始位置.对于有结构文件：如果文件是定长记录的，只要给出记录号就能求出该记录的首地址。如果文件是变长记录结构的，直接存取将是非常困难的。对于流式文件：按键存取（索引存取）：不是按记录号，而是按索引表中的对应关系存取记录。18..12/332020年1月操作系统流式文件中提供文件存取操作有：fread(buffer,size,count,fp);fwrite(buffer,size,count,fp);这两个操作总是从当前位置开始读（或写）,执行顺序存取操作fseek(fp,offset,mode)调整文件的读写起始位置，若在fread、fwrite之前执行fseek操作，就调整了文件的读写指针（读写开始的位置），实现了随机存取。流式文件的存取:根据存取命令把读写指针移动到欲读写处来读写。每次存取操作都要指定存取操作的开始位置18..13/332020年1月操作系统3.有结构文件的记录组织方式：1）顺序文件(sequentialfile)逻辑记录的排序：串结构(记录间顺序由时间决定，与关键字无关)；顺序结构（记录间顺序按关键字排列）对顺序文件的访问性能：顺序存取，定长文件可以实现直接存取：LLL…LLRptrRptr定长记录文件不定长记录文件优点:适于进行批量存取;缺点:查找或修改单个记录时,性能较差。增删记录困难——事务文件18..14/332020年1月操作系统2)索引文件(indexedfile)为变长记录文件创建索引表，对于原文件中的每一个变长记录，都对应索引表中的一个表项。索引表是一个定长记录的顺序文件，可方便地实现直接存取。索引表表项：索引号记录长度m指针Ptr检索过程：1.按关键字查表，找到相应表项2.由表项中的指针值访问相应的记录缺点：占用了部分存储空间，代价较高。18..15/332020年1月操作系统3）索引顺序文件(indexed-sequentialfile)是顺序文件和索引文件结合的产物。实现变长记录文件的直接存取，代价较低。也加快了顺序文件的检索速度。具体做法：将顺序文件中的所有记录按关键字的取值划分若干个区间（或组）。为整个顺序文件建立一张索引表，每一表项对应一个分组，用组中的第一个记录表示。检索过程：1.按索引文件的检索方式找到相应的组，2.按顺序文件的检索方式找到相应的记录。18..16/332020年1月操作系统键逻辑地址姓名其它属性ABZAnBingAnKangAnQingBaoRongBiJingBonLong索引文件逻辑文件索引顺序文件示意图18..17/332020年1月操作系统Hash文件:定义一个散列函数h(k)，使得对于给定的键k，散列函数h(k)将其变换为k所对应的地址例：记录关键值为“ANDING”利用字母在字母表中排序的和计算出记录地址或找出指向相应记录的指针1+14+4+9+14+7=594)Hash文件目前应用最广泛的一种直接文件:直接文件:不需像前面的方法那样按照键值进行检索,找到记录的物理地址.而是根据给定的键值,直接获得指定记录的物理地址.18..18/332020年1月操作系统5.3目录管理P2235.3.1目录内容5.3.2目录结构类型5.3.3目录查询技术18..19/332020年1月操作系统5.3.1目录内容P224为了对一个文件进行正确的存取，用文件控制块（FCB）描述和控制文件访问的控制信息（不包括文件内容）。即：文件属性信息(properties)，其中的一部分是用户可获取的。文件与文件控制块一一对应。文件目录是文件控制块(FCB)的有序集合。文件目录也是一个文件。基本信息存取控制信息使用信息文件控制块(FCB)18..20/332020年1月操作系统1、文件增多--文件控制块多--目录结构庞大,检索效率下降2、目录检索时仅需要文件名这一信息，因此考虑将文件名和文件描述信息分开，以简化FCB结构如：盘块大小1KB，若一个FCB为64B则：每个盘块存放16个FCB;若一个文件目录中共有640个FCB,需要占用40各盘块。查找一个文件平均需要启动磁盘20次。18..21/332020年1月操作系统实现：目录中仅放有文件名，文件的其他信息放在索引结点里文件名文件名文件名文件名索引结点目录外存FCB简化成只包含文件名和索引结点编号索引结点的引入：如:unix中一个目录仅占16个字节，其中14个字节是文件名，2个字节为索引节点指针18..22/332020年1月操作系统例：目录部分——启动磁盘次数问题在某个文件系统中，每个盘块512字节，文件控制块占64个字节，其中文件名占8个字节。如果索引结点编号占2个字节，对一个存放在磁盘上256个目录项的目录，试比较引入索引结点前后，为找到其中一个文件的FCB，平均启动磁盘的次数。18..23/332020年1月操作系统问题分析：未引入索引结点时：FCB占64字节：则一个盘块可存放512/64=8个FCB。因此一个含有256个目录项的目录需要存放在256/8=32个盘块中。检索一个文件，需平均启动磁盘次数为（32+1）/2=16.5次。引入索引结点后：FCB被简化为由文件名和索引结点编号组成，即占8+2个字节。则一个盘块可存放512/10=51.2个FCB，因此一个含有256个目录项的目录需要存放在256/51.2=5个盘块中。找到匹配的目录项平均启动磁盘次数为（5+1）/2=3次，得到索引结点编号后，还需启动磁盘将对应文件的索引结点读入内存，故平均启动磁盘4次。目录是由FCB构成的。18..24/332020年1月操作系统文件目录管理的设计要求：目录是由文件说明索引组成的用于文件检索的特殊文件。1.实现按名存取2.提高对目录的检索速度3.实现文件共享4.允许文件重名18..25/332020年1月操作系统5.3.2目录结构类型设计目标：能提高检索效率。单级目录结构：整个目录组织是一个线性结构，系统中的所有文件都建立在一张目录表中。它主要用于单用户操作系统。如下图:特点：结构简单、实现了按名存取；文件多时，查找速度慢；不允许重名；不便于实现文件共享；18..26/332020年1月操作系统两级目录结构两级目录结构：在根目录下，每个用户对应一个目录（第二级目录）；在用户目录下是该用户的文件。适用于多用户系统，各用户可有自己的专用目录。用户名用户的文件目录zhaoqiansunli主目录文件名programdocumentzhao的目录qian的目录文件名paperprogram2、文件共享1、提高了检索速度3、文件重名18..27/332020年1月操作系统目录项描述一个子目录表：描述一个文件目录表记录式文件包含三级或三级以上的文件目录结构称为树型结构目录。在文件数目较多时，便于系统和用户将文件分散管理。但目录级别太多时，会增加路径检索时间。1、树型结构的组成根结点——根目录树结点——各级子目录叶结点——文件子目录名文件名文件名子目录名子目录名文件名文件名子目录名子目录名文件名文件名子目录名树型目录结构（多级目录结构）18..28/332020年1月操作系统树型目录结构18..29/332020年1月操作系统2、文件路径ABC根目录EPABDFEDBGAE