《计算机操作系统》课件OS-chapter 7

第七章文件管理1、掌握文件和文件系统的概念2、掌握文件的逻辑结构、物理结构及文件的存取方法。本章重点：1、文件的存取方式和物理结构2、文件外存空间的管理

本章难点：

引言文件和文件管理文件组织和存取方式文件的物理组织（文件在外存上的存贮方式）文件存贮器的管理文件目录文件的存取控制文件的使用磁盘调度小结

7.1引言软件资源系统程序工具软件中间件标准子程序库用户程序及数据一、文件系统的引入计算机系统运行过程中要解决的问题：程序运行在内存，内存信息易失，需要外存保存需要永久保存的软件资源OS本身就是一种重要的系统资源，它不能全部常驻内存，OS本身也需要具有文件功能用户在完成某些任务的过程中要使用的某些私有或公共的软件资源来协助完成自己的任务。用户编制完成的或未完成的程序存放在什么地方，需要访问的数据存放在什么地方，从而使得人们可以再利用已有的软件资源。文件管理将把存贮、检索、共享和保护文件的手段提供给OS和用户，以达到进一步方便用户，提高资源利用率的目的对用户而言，文件系统是OS中最直接可见部分能否方便地使用OS以及OS的可信赖程度往往取决于文件系统的好坏而文件系统的好坏与组织文件的方式、存贮文件的方式以及保存文件系统的外存之间的管理有很大的关系二、文件系统的作用7.2文件和文件系统的概念

一、文件：是具有文件名的一组相关联信息的集合。文件是OS进行信息管理的基本单位。进程是的基本单位线程是的基本单位作业是的基本单位一、文件：是具有文件名的一组相关联信息的集合。文件是OS进行信息管理的基本单位。进程是的基本单位线程是的基本单位作业是的基本单位二、文件分类记录式文件：1.按结构分流式文件：由若干称为记录的较小单位组成。有一组相关联的字符流组成，文件中没有记录的概念。记录：是一个有意义的信息集合。长度等长：记录数×长度不等长：记录长度之和流式：所有字符数系统文件：2.按性质和用途分库文件：由系统软件构成的文件，由OS核心及其它系统程序和数据所组成。只允许用户通过系统调用来执行，不允许用户读和修改。由标准子程序库组成。允许用户执行、不允许修改用户文件：由用户生成并委托给系统保存的文件。只读文件：允许文件主及核准的用户读，但不允许写、不允许修改。读写文件：允许文件主及核准的用户读、写，但禁止未核准的用户读写。可执行文件：只允许核准的用户执行，不允许读、写。3.按对文件实施的保护级别分为：不保护文件：所有用户都可以访问。输入文件：4.按文件信息中的流向分为：输出文件：读卡机上的文件。打印机上的文件。输入/输出文件：磁盘上的文件。普通文件：系统中最一般格式的文件。目录文件：由文件的目录信息构成，系统可以通过它检索其它文件。特殊文件：系统对外部设备以文件的形式管理。5.按文件的组织和处理方式分：6.按文件的存在方式分逻辑文件：用户看到的建立在逻辑结构基础上文件叫逻辑文件。物理文件：存储在物理设备上的文件叫物理文件。定义：OS中与文件管理有关的那部分软件、被管理的文件以及实施管理所需的一些数据结构（包括各级目录、索引表等）的总体。三、文件系统从系统的角度讲：文件系统是对文件的存贮空间进行组织、分配、回收、负责文件的存储，并对存入文件实施保护、检索的系统。它负责为用户建立文件、撤销、读写、修改、复制；控制文件的存取。文件系统主要实现文件的按名存取。用户只有知道文件名即可存取文件中的信息。而无需知道文件究竟存放在什么地方。从用户角度看：⑴按名存取

用户只要知道文件名，无需知道文件的物理位置和结构、文件物理位置的变化，并不影响文件的存取。四、文件系统的功能⑵统一性对文件操作有很多：随机访问、顺序访问、建立删除、读写等。文件系统向用户提供了统一的界面来完成各种不同的操作。⑶文件的共享与保护用户希望自己存放在文件系统中的文件能安全可按照用户的愿望实现共享，因些文件系统提供各种可靠的安全保护设施以防止未授权的用户对文件进行非法操作，并防止该操作造成的信息破坏。⑴有效地分配文件存贮器的存储空间五、文件系统的任务⑵提供文件的逻辑结构，物理结构和存取方法⑶实现文件的逻辑结构转变成物理结构⑷实现文件的共享，提供各种存取控制机制⑸提供文件的各种操作界面。7.3文件的逻辑结构和存取方式一、文件的逻辑结构

定义：从用户的观点出发所看到的文件组织形式，说明文件的基本元素逻辑上是如何定义的。基本元素又是如何聚集成其它的元素。一直到最后构成文件为止。即：用户看到文件面貌。1.逻辑结构的定义2.选取文件的逻辑结构应遵循以下原则

当用户对文件信息进行修改操作时，给定的逻辑结构应能尽量减少对已存储好的文件信息的变动当用户需要对文件信息进行操作时，给定的逻辑结构应使文件系统在尽可能短的时间内查找到需要的记录或基本信息单位应使文件信息占据尽可能小的存储空间应便于用户进行操作。(1)流式由字符构成单词，单词→段、段→页、页→文件典型的流式文件：源程序、文本文档3.文件逻辑结构类型特点：管理简单、查找困难(2)记录式：由字符构成字段，字段→记录、记录→文件

典型的记录式文件：数据库表特点：查找方便(3)记录式文件的常见结构特点：适用性强，适用于任何类型的文件搜索性能差，查找某个记录需要找遍整个文件连续结构：将记录按生成的先后顺序连续排列。多重结构：把记录按关键字和记录名排列成行列式结构R1R2R3RnK1K2K3

Kn1011010010000010行列对应位置为1表示该记录中有该键，否则没有行列式结构浪费空间，所以规划成多重结构把行列式中0项去掉，以键Ki为队首，以包含键Ki的记录为队列元素构成记录队列。K1K2K3

KnRi→Rj→Rk→…Rx→Ry→Rz→…多重结构存在什么问题？多重结构的问题：多重结构查找时优于连续结构，但是每个队列中和键直接相连的只有一个记录，查找某一记录时查找效率较低。把含有相同键的记录指针全部指向该键。转置结构：K1含有K1的所有记录指针RiRiRi顺序结构：把文件中的键按规定的顺序排列起来把文件中的键按规定的顺序排列起来顺序结构二、文件的存取方式

1.顺序存取2.随机存取3.按键存取1.顺序存取

R0R1R2…RiRi+1…RnR0R1R2…RiRi+1…Rnm02mim(i+1)mnmm0m0+m1按照文件的逻辑地址进行读写操作Rptr:读指针Rptr←Rptr+mRptr←Rptr+mi由于顺序文件是顺序存取的，可以采用预先缓冲技术，加速文件的输入/输出。2.直接存取

如果文件是定长时，LA=lxm如果是变长记录，只能采用索引结构来实现直接存取对直接存取的文件用户除了要给出文件名外，还要给出记录号l

索引项长度指针0m01m1nmnR0R1Rn3.按键存取对文件的搜索包括：键的搜索和记录的搜索文件的存取根据给定的键或记录进行先找到记录的逻辑位置，然后转换成物理位置。搜索方法：（1）线性搜索法：依次比较进行搜索。（2）散列法：定义散列函数，将对应的键变换成逻辑地址。（3）二分法：将键排序，采用折半法。7.4文件的物理组织（文件在外存上的存贮方式）

一、顺序结构（顺序文件、连续文件）把一个文件按文件的逻辑顺序存放在外存的一片的物理块中的结构。OS只要知道第一块的块号和块数就可以了特点：利用率低、有碎片、修改困难、存取速度快、顺序访问、不能动态增加文件长度。文件说明信息文件A第一物理块号（10）文件长度（4）物理存储设备10111213…物理块号1234逻辑块号二、链接结构（串联文件）是一种非连续结构，存放文件信息的每一物理块中有一个指针，指向逻辑上连续的下一个物理块，这个指针的长度由物理设备的容量决定。特点：利用率高、不会有碎片、访问速度慢、不能进行随机访问、修改容易文件说明信息文件A第一物理块号（10）物理存储设备物理块号逻辑块号1015152222131301234三、索引结构按这种结构存放的文件叫索引文件。块与块可以不连续，为一个文件的所有块建立一张表，叫索引表，在内存中存放索引表的首地址，实现由逻辑块号到物理块号的映射。文件说明信息索引表指针索引表特点：利用率高、没有碎片、可以顺序访问、修改容易但索引也要有开销（时间、空间）（即开销大）。逻辑物理块号块号015202225多级索引0123456789101112DataDataDataDataDataDataDataDataDataData1Indexindexindex2Indexindexindexdatadata3Indexindexindexdata（1）不超过10块不用索引（2）10-138块用1级索引（3）138-138+1282用2级索引（4)138+1282-138+1282+1283用3级索引7.5文件存贮器的管理1、位示图文件存贮器的管理是对存贮空间的分配和回收特点：分配回收算法简单，空间开销大。160GB的硬盘。每块1024B，位示图需要占多大？01001000101110………………2、空白文件目录把文件存贮器中未分配的一片组织成一个空白文件。空白文件是由空闲块组成的文件，系统按文件的结构把存贮介质上的空闲块组成一个或多个空白文件。进行分配时，系统从空白文件目录中扫描出一块合适的空白区进行分配，然后修改空白文件的目录块号始址块数file0011020file0025080file003200300F1F3F23、空白块链将空闲块链接指针链接在一起，需要时从链头摘取所所要块数，然后修改链首指针回收时把释放的空闲块插入链头或链尾。……4、空白块成组链接将外存上的空闲块分组，组的大小固定50块或100块每一组的块首记在另一个空闲块中。放在磁盘上的资源表中

32块99块99块……4号……96号……10号……专用块专用块专用块专用块7.6文件目录将每个文件的文件名与文件的实际物理地址之间建立一种连接，由文件目录来实现。文件存入物理空间后，文件是怎样实现“按名存取”的呢？文件目录由文件目录项构成。一、文件目录项的内容：·标识信息：如文件名、用户名等。·结构信息：逻辑结构记录式：流式：定长：记录数，每记录长度变长：记录数，文件总长文件字节数物理结构顺序文件链接文件索引文件：首块号索引表首址·存取控制信息：文件的属性，哪些用户对文件有何种权限·其它信息：建立、修改日期、时间等。·实际物理地址：二、文件目录结构1、单级目录结构物理卷：文件系统中把一片软盘、一个区或一卷磁带叫做一个物理卷单级目录结构：优点：一个物理卷上的所有文件都登记在一个目录中，当用户要求建立文件时，系统就在这个目录中寻找一个表目，填写文件有关内容。删除文件时，删除相应的表目并回收文件所占的物理块。读写操作

管理简单，适用于单用户系统或容量小的存贮设备。缺点：⑴检索效率低：文件多时目录大。⑵重名问题⑶不利于文件共享GO控制权交给文件系统根据给定的文件名搜索单级目录表文件名在目录表中吗？计算读写信息的物理块号是调用设备管理程序控制权转移否读还是写？写分配存储空间改写目录表读失败返回R2、二级目录结构文件目录分成主目录（MFD）和用户目录（UFD）。系统为用户建立一个主目录，再为这些文件建立用户文件目录。MAXSORTSORTABC用户名UFD地址张三李四……文件名其它信息文件首址ABCSORT……文件名其它信息文件首址SORTMAX……文件引入：解决单级目录结构中文件命名冲突、提高搜索速度CCCC不同用户的文件共享优点：搜索时间快解决重名实现文件共享3、多级目录结构除了最低一级的物理块中装有文件信息外，其它每一级目录中存放下一级目录或文件的说明信息最高层为根目录，最低层为文件根SUB1SUB2SUB3SUB11SUB12SUB31SUB32A1A1A2A3A4A1A1A2A3优点：层次清楚解决了文件重名问题查找速度快绝对路径：从根目录开始的路径相对路径：从当前目录开始4、多级目录的文件共享文件系统的一个重要任务就是进行文件共享文件共享的方法：（1）绕道法：用相对路径（2）链接法：在目录表之间建立链接需要指明被共享的文件和被链接的目录（3）基本文件目录表BFD：把所有文件的目录信息分成两部分：一部分包含文件的结构信息、物理块号、存取控制、管理信息等，由系统赋予唯一的内部标识符来标识；另一部分则由用户给出的符号名和系统给出的内部标识符组成，前者为符号文件目录SFD、基本文件目录BFD因为要访问多个目录文件，故效率较低标识符物理块号123456789b.cd.cw.cm.cWang3zhang5主目录MFDb.c2d.c4Wang的SFDb.c2w.c7Sub19Zhang的SFDm.c8Sub1的SFD根AB…C…DJEGFKHIL…SNPUQRTVW…文件系统如图所示：图中框表示目录，圈表示普通文件。根目录常驻内存，目录文件组织成链接文件，不设文件控制块，普通文件组织成索引文件，目录表目指示下一级文件名及其磁盘地址，各占两个字节，共4个字节。若下级文件是目录文件，指示其第一个磁盘块地址。若下级文件是普通文件，指示其文件控制块的磁盘地址。每个目录文件磁盘块的后4个字节用于拉链使用。下级文件在上级目录文件中的次序为图中的左至右，每个磁盘块有512字节，与普通文件一页等长普通文件的文件控制块共13项，采用多级索引结构，每个磁盘地址占2个字节前10项指示文件块；11项指示1级索引块；）12项指示2级索引块；13项指示3级索引块问：（1）一个普通文件最多可能有多少个文件页？（2）若要读文件J中的某一页，最多启动文件读操作多少次？（3）若要读文件W中的某一页最少启动文件读操作多少次？（4）对（3），为最大限度减少启动磁盘的次数，可采用什么方法？此时，最多启动磁盘读操作多少次？7.7文件的存取控制1、存取控制矩阵：用二维矩阵进行存取控制，其中一维表示用户，另一维表示文件，对应的矩阵元素表示用户对文件的存取控制权。用户提出存取要求时，文件系统根据该矩阵的元素进行比较，不匹配则拒绝执行。当文件和用户数都很多时，存取控制矩阵十分庞大，对它有访问要占据大量的内存空间和CPU时间。如:100用户2000个文件,若每个权限需1个字节,则该矩阵需2000000个Byte

用户V1V2……Vn

权限文件f1RRWXRXf2RWX____f3____fm___RWX2、存取控制表：存取控制矩阵的简化矩阵很大，但内容很低稀疏，很多空项，所以可以简化以储空间。把矩阵按行划分，为每个文件建立一张存取控制表，表中指出各类用户对该文件的存取权限。存取控制表在文件建立时，填写并可随时修改，可以存放在文件目录表中。文件打开时，随文件一并移到内存。文件A用户权限文件RWXA组RXB组R其它__3、口令：①给每个文件一个口令，附在文件目录项中，用户访问文件时必须提供口令。②给每个用户规定一个口令，用户在注册时输入口令。注册后用户对自己的文件进行任何操作可防止冒名者破坏文件。口令简单，但口令记忆较难，另外系统管理员可随时查看口令7.8文件的使用文件是以系统调用方式或命令方式为用户提供服务：对文件的操作分三类有关文件属性的操作（设置或访问文件的属性）有关目录的操作（建立、改变、删除）有关文件本身的操作（文件建立、撤消、打开、关闭、读写）一、文件的建立与撤消1、文件的建立（CREATE）CREAT（文件名，文件属性，设备号）在指定的物理卷上建立一个文件，同时建立相应的目录。2、关闭文件CLOSE：CLOSE（文件名）对文件的读/写操作完成后一定要关闭文件。步骤：①若内存中文件内容已被修改，则把它写回外存。②释放内存文件所占空间。二、文件的读写1、写文件:write（文件名，N，M）将内存中的某一段信息，写到外存文件中去。N要写内容的长度；M要写入内容的起始地址。2、读文件：把文件信息从外存读入内存：read（文件名，N，M）N读的长度；M读到内存的具体位置。二、其它操作1、拷贝：copyfrom源to目标2、加：append(文件名，M)3、修改：modify4、移动：MOVE7.9磁盘调度

1、磁盘结构磁臂磁头1、磁盘访问时间=寻道时间+旋转延迟时间+数据传输时间2.磁盘调度算法（1）FCFS（先到先服务）（2）SSFT（最短寻道时间优先）（3）SCAN（扫描算法）（4）CSCAN（循环扫描算法）磁头当前位置为100道，磁盘访问序列：23、376、205、132、19、61、190、398、29、4、18、40，采用FCFS的寻道次数先到先服务：100233762051321961190398294184067+353+171+73+113+42+129+208+369+25+14+22=1586R磁头当前位置为100道，磁盘访问序列：23、376、205、132、19、61、190、398、29、4、18、40，采用SSFT的寻道次数SSFT：100132190205614029231918437639832+71+15+144+21+11+6+4+1+14+372+22=713R磁头当前位置为100道，磁头向着磁盘内侧移动，磁盘访问序列：23、376、205、132、