第六章文件管理2

1、第六章 文件管理文件管理的功能文件管理的功能 文件的按名存取实现文件的共享、保护和保密 文件目录的建立与维护 逻辑文件到物理文件的转换 文件存储空间的分配和管理 提供一组可供用户使用的文件操作 文件：文件：具有文件名文件名的一组相关信息相关信息的集合。6.1 6.1 文件和文件系统文件和文件系统1）文件的相关概念）文件的相关概念 文件类型文件类型 按性质与用途划分：系统文件，用户文件，库文件 按数据形式划分：源文件，目标文件，可执行文件 按数据存取方式划分：只读文件，读写文件，只 可执行文件 文件的组成文件的组成文件名、基本内容、文件属性（说明信息） 文件的结构文件的结构逻辑结构逻辑结构：物理

2、结构物理结构：呈现在用户面前的文件自身的组织形式与结构，根据其基本内容的组织方式可分为有结构文件和无结构文件文件在物理存储器上的组织形式与存储结构。其分配方式可分为连续分配、链接分配和索引分配2 2）文件系统）文件系统 用于对文件进行组织、存储与管理的子系统。用于对文件进行组织、存储与管理的子系统。l 用户角度用户角度：存储信息和使用信息的接口（按名存取：命令，程序接口）l 系统角度系统角度：负责文件存储空间管理文件系统接口文件系统接口管理程序集合管理程序集合管理对象：文件、文件管理对象：文件、文件目录、文件存储空间目录、文件存储空间文件系统结构模型文件系统结构模型 文件系统类型lFATlVF

3、ATlNTFSlEXT2lHPFS 注：现代OS一般支持多种文件系统3）文件操作）文件操作用户通过文件系统的接口对文件所能实现的操作用户通过文件系统的接口对文件所能实现的操作。l基本操作基本操作创建文件、 删除文件、 读文件、 写文件、设置文件读写指针l其他操作其他操作目录操作、修改文件属性、设置文件访问权限、更改文件名l 打开文件与关闭文件打开文件与关闭文件打开：文件属性从外存拷贝到内存打开文件表的一个打开：文件属性从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号返回给用户表目中，并将该表目的编号返回给用户关闭：文件从打开文件表中的表目上删除掉关闭：文件从打开文件表中的表目上删除掉6

4、.2 6.2 文件的逻辑结构文件的逻辑结构p 记录式文件结构（又称有结构文件）记录式文件结构（又称有结构文件） 用户把文件内的信息按逻辑上独立的含义划 分信息单位，每个单位称为一个记录p 流式文件结构（又称无结构文件）流式文件结构（又称无结构文件） 对文件内信息不再划分单位，它是依次的一串字符流构成的文件文件由字符（字节）序列构成 文件 记录 n 记录 2 记录 1 数据项n 数据项2 数据项1 图图1： 文件，记录和数据项之间的层次关系文件，记录和数据项之间的层次关系1）组成）组成文件文件由若干记录记录组成，每个记录又由若干数据项数据项组成 记录：记录：数据的基本单位(存取访问的基本对象)

5、数据项：数据项：数据的最小单位（指基本数据项）n 记录式文件结构记录式文件结构lllR0R1Ri数据项数据项1数据项数据项2数据项数据项n定长记录文件定长记录文件R0R1R2Ril0l1l2li变长记录文件变长记录文件2）类型：）类型： 定长记录文件定长记录文件 变长记录文件变长记录文件3）逻辑文件）逻辑文件根据记录的不同组织方式形成不同的逻辑文件l顺序文件顺序文件l索引文件索引文件l索引顺序文件索引顺序文件 顺序文件顺序文件 顺序文件一般是定长记录，记录中的数据项顺序文件一般是定长记录，记录中的数据项的类型长度与次序固定，一般还有一个可以唯一的类型长度与次序固定，一般还有一个可以唯一标识记录

6、的数据项，称为键（标识记录的数据项，称为键（key），记录按键），记录按键值的约定次序组织。值的约定次序组织。 顺序文件常用于批处理应用，对于更新某个顺序文件常用于批处理应用，对于更新某个记录的请求的处理性能不佳记录的请求的处理性能不佳 索引文件索引文件建立一张索引表，记录变长记录的长度及逻辑首址索引号索引号长度长度l逻辑首址逻辑首址01il0l1li索引表索引表逻辑文件逻辑文件R0R1Ri注：索引表本身是一个按记录键值排序的定长记录的顺序文件注：索引表本身是一个按记录键值排序的定长记录的顺序文件 索引顺序文件索引顺序文件 顺序文件与索引文件的结合（可减少索引表的长度）关键字逻辑地址姓名其它属

7、性ABZAn BingAn KangAn QingBao RongBi JingBon Long索引文件顺序文件4）存取方法顺序存取顺序存取按照文件的逻辑地址顺序存取，在记录式文件中，这反映为按记录的排列顺序来存取随机存取随机存取允许用户根据记录的编号来存取文件的任一记录6.3 6.3 文件的物理结构文件的物理结构 1）文件的存储方式）文件的存储方式 连续分配存储方式 离散分配存储方式链接分配方式索引分配方式2）连续分配）连续分配顺序文件顺序文件 逻辑文件中连续的信息存储到磁盘连续的物理盘块中所形成的文件（位于同一磁道或相邻磁道）。在文件控制块FCB（或在目录）中存放文件第一个记录所存放的盘块

8、号ADRR和文件总的盘块数NContiguous Allocation of Disk Space优点优点：有利于文件的顺序存取，且可获得较高的存取速度缺点缺点：要求有足够大的连续盘块空间，不利于文件的动态增长，且易产生“磁盘碎片”3 3）链接分配）链接分配链接文件链接文件 为文件分配离散的盘块离散的盘块，其间（逻辑块间）的逻辑关系通过链接指针链接形成，链接方式有两种： 隐式链接：隐式链接：链接指针设置在每个物理盘块最后一个单元。管理链接文件只需在文件控制块FCB中存储文件头块信息的盘块号，有时也存储文件尾块信息的盘块号。Linked Allocation of disk space优点：优点

9、：缺点：缺点： 显式链接：显式链接：用于链接文件各物理块的指针显式地存放在内存的一张链表中，分配给文件的所有盘块号都放在该表中，故该表也称为文件分配表（FAT） 优点：优点：能提高检索速度大大减少访问磁盘的次数 缺点：缺点：文件分配表FAT需占用大量空间消除外碎片，存储空间利用率提高；有利于文件动态增长文件的直接存取需多次读盘获取链接地址（指针），不利于直接存取；可靠性差4）索引分配方式）索引分配方式 采用离散分配方式存储文件，为采用离散分配方式存储文件，为每个文件每个文件建立一张建立一张索索引表引表，记录逻辑块与物理块的对应关系，通过查找索引表，记录逻辑块与物理块的对应关系，通过查找索引表获

10、得物理盘块地址。获得物理盘块地址。在在FCBFCB中放置了索引表指针，它指向中放置了索引表指针，它指向索引表始址，索引表存放在盘块中。索引表始址，索引表存放在盘块中。012349161102501234逻辑块逻辑块物理块号物理块号文件文件索引块（盘块）索引块（盘块）索引表被存放在专门的盘块中，该盘块称为索引块Example of Indexed Allocation优点：方便直接存取（查找索引表后直接读优点：方便直接存取（查找索引表后直接读/写盘块）写盘块）缺点：索引表占用外存空间，需先读索引块，文件很缺点：索引表占用外存空间，需先读索引块，文件很大时，占用多个块，且查找索引表花费时间大时，占

11、用多个块，且查找索引表花费时间索引表查找速度问题的解决索引表查找速度问题的解决I.采用两级索引，针对一般不太长文件采用两级索引，针对一般不太长文件II. 采用多级索引，针对较长文件采用多级索引，针对较长文件III. 采用混合索引，长、短文件均适用采用混合索引，长、短文件均适用 二级索引二级索引: :将一个大文件的所有索引表（二级索将一个大文件的所有索引表（二级索引引) )的地址放在另一个索引表（一级索引的地址放在另一个索引表（一级索引) )中中. . 混合索引（混合索引（UNIX O.SUNIX O.S采用）采用）由于由于8080以上文件是小文件，为了解决能高速存取小文件以上文件是小文件，为了

12、解决能高速存取小文件和管理大文件的矛盾，和管理大文件的矛盾，UNIXUNIX将直接寻址、一级索引、二级将直接寻址、一级索引、二级索引和三级索引结合起来，形成了混合寻址方式。索引和三级索引结合起来，形成了混合寻址方式。019101112主索引表主索引表iaddr（0） iaddr（9）iaddr（10）iaddr（11）iaddr（12）索引结点索引结点直接地址直接地址一次间址一次间址二次间址二次间址三次间址三次间址索引分配方式对应的物理文件称为索引文件索引分配方式对应的物理文件称为索引文件UNIX UNIX /Linux直接间接混合寻址方式直接间接混合寻址方式 二次间接块二次间接块一次间接块一

13、次间接块 三次间接块三次间接块 . . . . 。 . . . . . . . .di_addr0 di_addr1 di_addr2 . . . di_addr9 di_addr10 一次间接一次间接di_addr11 二次间接二次间接di_addr12 三次间接三次间接1034#数据数据块块0#1#2#9#10#5）三种分配方式比较）三种分配方式比较连续链接索引空间要求较高（连续）不高不高存取方式顺序存取高速亦可直接存取只适合顺序存取顺序、直接存取均可缺点不利于文件动态增长，易产生磁盘碎片隐式链接不利于直接存取显式链接需占用内存空间（链表）索引表占用外存盘块空间，查索引表需花费一定时间文件

14、结构归纳文件结构归纳逻辑结构物理结构概念与定义 文件自身的组织形式与结构用户所能看到的数据的组织形式文件在物理存储器上的组织形式与结构用户看不见的、根据不同分配方式形成的不同的物理文件形式记录式文件流式文件顺序文件链接文件索引文件思考题： 一个文件系统中有一个一个文件系统中有一个20MB20MB大文件和一个大文件和一个20KB20KB小文小文件件, ,当分别采用连续、链接、二级索引和当分别采用连续、链接、二级索引和UNIX S V UNIX S V 分配方案时分配方案时( (每块大小为每块大小为4096B,4096B,每块地址用每块地址用4B4B表示表示) )，问问: :1.1.各文件系统管理

15、的最大的文件是多少各文件系统管理的最大的文件是多少? ? 2.2.每种方案对大、小二文件各需要多少专用块来记录每种方案对大、小二文件各需要多少专用块来记录文件的物理地址文件的物理地址( (说明各块的用途说明各块的用途) ?) ?解答：解答：1 1：各种分配方案的文件系统可管理的最大文件：各种分配方案的文件系统可管理的最大文件v连续分配连续分配：不受限制，可大到整个磁盘文件区。v链接分配链接分配：同上。v二级索引二级索引：由于盘块大小为4KB，每个地址用4B表示，一个盘块可存1K个索引表目，二级索引可管理的最大文件容量为4KB1K1K4GB，如要管理更大的文件需采用三索引，它可管理4TB大小文件

16、。vUNIXUNIX混合分配：混合分配：可管理的最大文件为40KB4MB+4GB4TB。解答：解答：2 2：每种分配方案对每种分配方案对20MB20MB大文件和大文件和20KB20KB小文件各需要多少小文件各需要多少专用块来记录文件的物理地址专用块来记录文件的物理地址? ?v连续分配连续分配：对大小二个文件都只需在文件控制块FCB中设二项，一是首块物理块块号，另一是文件总块数，不需专用块来记录文件的物理地址。v链接分配链接分配：对大小二个文件都只需在文件控制块FCB中设二项，一是首块物理块块号，另一是文件尾块数；同时在每块存文件的物理块中设置存贮下一块块号的指针。解答：解答：v 二级索引二级索

17、引：对大小文件都固定要用二级索引，对20KB小文件，用一块作第一级索引，用另一块作二级索引，共用二块专用物理块作索引块，对于20MB大文件，用一块作第一级索引，用5块作第二级索引，共用六块专用物理块作索引块。v UNIXUNIX的混合分配的混合分配：对20KB小文件只需在文件控制块FCB的i_addr13中使用前5个表目存放文件的物理块号，不需专用索引块。对20MB大文件，FCB的i_addr13中使用前10个表目存放大文件前10块物理块块号，用一级索引块一块保存大文件接着的1K块块号，还要用二级索引存大文件以后的块号，二级索引使用第一级索引1块，第二级索引4块。总共也需要6块专用物理块来存放

18、文件物理地址。6.4 文件目录管理文件目录管理 1）概）概 述述 目录管理的基本要求目录管理的基本要求能实现“按名存取按名存取”的目标具有较高的查询（检索）速度可实现文件共享允许不同用户采用相同的文件名文件目录 存放文件说明信息及存取控制信息的一种数据结构，用于标识系统中的文件及其物理地址供检索时使用。一个文件目录项又称为一个文件控制块文件控制块（FCB）。）。FCB中包含的信息有以下三类： 基本信息：基本信息：文件名，用户名，文件类型、文件长度，文件结构(逻辑结构，物理结构)等 控制信息：控制信息：文件主及其他用户的存取权限等 使用信息：使用信息：文件建立日期、最后一次修改日期，当前使用的信

19、息如打开文件的进程数等2 2）索引结点）索引结点为减少目录数据量，减少读盘次数，提高目录查询速度 即将文件名与文件说明信息分开存放文件名文件名Z1Ws索引结点编号索引结点编号文件长度文件长度文件结构文件结构物理地址物理地址文件长度文件长度文件结构文件结构物理地址物理地址Z1文件索引结点文件索引结点Ws文件索引结点文件索引结点Z1文件文件Ws文件文件文件目录文件目录磁盘索引结点：磁盘索引结点： 文件建立时生成，每个文件有惟一的一个磁盘索引结点，主要包括文件主标识符、文件类型、文件存取权限、文件物理地址等相关文件说明信息。内存索引结点内存索引结点： 文件操作，打开文件时建立。将磁盘索引结点拷贝到内

20、存索引结点并增加如下内容：索引结点编号、状态、访问计数、文件所属文件系统的逻辑设备号、链接指针。 例：设某文件系统中有128个文件，每个文件的FCB占48B，其中文件名6B。索引节点编号2B.假设磁盘盘块大小为512B。求引入索引节点之前和之后查找一个文件所需的平均读盘次数。解：引入前一盘块可存放的FCB数：512/48=10（个）引入后一盘块可存放的目录项数512/8=64（个） 可存放的索引节点数：512/42=12（个）128个文件在索引节点引入前目录项占128/10=13个盘块；索引节点引入后目录项占2块，索引节点占11块。故查找一个文件的平均访盘次数 引入前：(1+13)/2=7次

21、引入后：(1+2)/2 +1 =2.5次3）目录结构简介）目录结构简介单级目录结构单级目录结构文件名文件长度物理地址状态f11Zs10Ls1整个文件系统一张表格，每个文件占有一个目录项整个文件系统一张表格，每个文件占有一个目录项 文件的建立和删除文件的建立和删除建立新文件：建立新文件： 删除文件：删除文件： 优点：优点： 缺点：缺点：查目录，无同名文件则找一个空目录（状态为0）分配给新文件使用（填入相关说明信息）查目录，找到同名者，根据物理地址回收外存空间，将对应表目状态置为0（表目回收）文件名与物理文件一一对应，可实现“按名存取”，目录结构简单，管理简单不允许重名，不便于共享，故一般适用于单

22、用户 两级目录结构两级目录结构用户名用户名 目录指针目录指针ZhangWangLi文件名文件名物理地址物理地址Z1Z2文件名文件名物理地址物理地址WaWb文件名文件名物理地址物理地址LimWaZ1Z2WaWbLimWa主目录主目录MFD（整个文件系统一张）（整个文件系统一张）用户文件目录用户文件目录UFD（每个用户一张表）（每个用户一张表） 文件的建立和删除文件的建立和删除用户登录建立新文件：需分配MFD表目和UFD空间用户退出：需释放UFD空间和对应MFD表目 建立、删除文件必须先查主目录，再查用户文件目录， 然后实施操作 优点优点提高了目录的查询（检索）速度允许不同用户取相同文件名，利于文

23、件的保护可用不同文件名共享使用同一文件 缺点缺点用户不能建立自己的子目录多级目录结构（三级或三级以上目录）多级目录结构（三级或三级以上目录）ABCABDFEDGAACJNKJMKAHF123456789101112131415161718192021多级目录组织多级目录组织在多级目录中，第一级目录称为根目录，目录中的非叶结点在多级目录中，第一级目录称为根目录，目录中的非叶结点均为子目录，树叶结点均为文件，多级目录也称树形目录。均为子目录，树叶结点均为文件，多级目录也称树形目录。根根目录目录文文件件Unix 的树型多级目录的树型多级目录 路径名路径名从根目录开始到该文件的通路上所有各级目录名拼起

24、来得从根目录开始到该文件的通路上所有各级目录名拼起来得到（文件名）到（文件名），各子目录之间可用分隔符隔开。 例：ls文件的路径名为：/bin/ls（绝对路径名）（绝对路径名） 当前目录（工作目录）当前目录（工作目录）访问文件从当前目录开始，相对于当前目录而设置路径访问文件从当前目录开始，相对于当前目录而设置路径。 例：当前目录为/usr/bin子目录 则dc文件的路径名为：./dc（相对路径名）（相对路径名）优点：优点： 允许文件重名，利于文件共享和保护，具有较高的查询速度，特别是在当前目录下查找文件将更为快捷。缺点：缺点： 多级查找可能要多次读盘（读子目录文件），降低查找速度6.5 6.5

25、 文件存储空间的分配与管理文件存储空间的分配与管理1）分配要求与算法）分配要求与算法 基本要求：基本要求： -有利于外存空间的充分利用-具有较高的访问速度 常用算法常用算法 -空闲表法（连续分配方式）-空闲链表法-位示图法-成组链接法2）空闲表法）空闲表法 数据结构：数据结构：序号第一个空闲盘块号空闲盘块数1242933155空闲表空闲表 盘块的分配与回收盘块的分配与回收 分配：查空闲表，找到一个足够大的空闲盘区，一分为二分配之 回收：先进行回收盘区的邻接合并，再记入（修改）空闲表 特点：可为文件分配连续盘块空间，但会产生磁盘碎片建立一张空闲表，记录所有空闲盘区情况建立一张空闲表，记录所有空闲

26、盘区情况（2, 3, 4, 5）（9, 10, 11）（15, 16, 17, 18, 19）3）空闲链表法）空闲链表法数据结构数据结构: 空闲盘区链表空闲盘区链表：以空闲盘区为单位链成一条链表 空闲盘块链表空闲盘块链表：以空闲盘块为单位链成一条链表将磁盘上所有空闲盘区链接在一个队列中将磁盘上所有空闲盘区链接在一个队列中 空闲链空闲链表表 空闲链头块块号空闲链头块块号3 3 空闲链尾块块号空闲链尾块块号2020 8 8 16 16 10 10 20 20 物理块号物理块号 3 8 3 8 16 10 2016 10 20 分配与回收（针对空闲盘块链）分配与回收（针对空闲盘块链） 分配：分配：查

27、空闲链表，只要链表不空，便可根据文件需要的盘块数逐一摘下空闲盘块分配之 回收：回收：将所有回收盘块一一插入（插在链尾）空闲盘块链 特点：特点：为文件分配不连续的盘块空间，空间利用率高，采用隐式链表会增加（分配时）读盘次数注：空闲盘区链是空闲表的另一种结构形式，可采用类似可变分区分配算法为文件分配连续存储空间4）成组链接法（）成组链接法（UNIX O.S采用）采用）算法思想：成组链接法是空闲表和空闲链表的结合。将磁算法思想：成组链接法是空闲表和空闲链表的结合。将磁盘空闲块盘空闲块分成若干组分成若干组，如将每，如将每100100个盘块作为一组，用个盘块作为一组，用索引索引表表表示；该组空闲块总数和

28、各空闲块块号存入下一组的第表示；该组空闲块总数和各空闲块块号存入下一组的第一个空闲块中（从后往前分组），一个空闲块中（从后往前分组），各组各组通过链接指针连在通过链接指针连在一起形成一起形成链表，链表，最后不满最后不满100100块的那组空闲块总数和各空闲块的那组空闲块总数和各空闲块块号记入磁盘区专用管理块（超级块）的块块号记入磁盘区专用管理块（超级块）的空闲盘块号栈空闲盘块号栈的的s_nfrees_nfree和和s_free100s_free100中。其数据结构如下所示：中。其数据结构如下所示： 超级超级 块块（已在内存）（已在内存）栈顶栈顶分配与回收（借助空闲盘块号栈分配与回收（借助空闲盘

29、块号栈） 分配分配a)出栈，将栈顶盘块号分配出去；b)当分配到栈底盘块时，先将栈底盘块出栈，将该盘块数据读到内存空闲盘块号栈中，再将原栈底盘块分配出去； 回收回收 a)进栈，依次将回收盘块号压入栈中；b)当栈满时，若再回收一个盘块，先将栈内数据写到该新回收盘块中，将栈清空，再将该回收盘块进栈 特点：特点： 利用空闲盘块存放（暂时）链接数据，只需为空闲盘块号栈分配辅助存储空间（内存及外存）即可，且为分配、回收操作进行的读、写盘次数相对较少成组链接法盘块分配回收示例：成组链接法盘块分配回收示例：v空闲盘块的分配：空闲盘块的分配： 开始的空闲盘块资源如下图开始的空闲盘块资源如下图(a)(a)所示。所

30、示。 1 1）如果某一个文件要求申请一个空闲块）如果某一个文件要求申请一个空闲块 将s_nfree-1=38，s_free38即12号块分配给申请者。如果还要申请，则继续。经过若干次申请后s_nfree=2，如图(b)所示。 2 2）如果此时又有一个文件要申请）如果此时又有一个文件要申请4 4块块 首先可以得到栈底元素s_free0的盘块号50先将50块中的内容读出：把50#块中的总块数100赋给超级块的s_nfree，并把对应的100个物理块号复制到数组s_free100中，如图(c)所示； 然后再把50块分配给申请者，最后再将51、52块分配给申请者。如下图(d)所示。v空闲盘块的释放：空

31、闲盘块的释放： 1 1）假定有一个文件占用了三）假定有一个文件占用了三个物理块，块号分别是个物理块，块号分别是180180，181181，182182。未释放。未释放前的空闲盘块的状态如下图前的空闲盘块的状态如下图(a)(a)所示。所示。 释放时首先填写182到s_nfree65中，然后s_nfree+1=66，同理释放181，180块，释放后的空闲盘块如图(b)所示。 2)2)假设某时刻磁盘的空闲盘块状况如下图假设某时刻磁盘的空闲盘块状况如下图(a)(a)所示。如果有所示。如果有一个文件释放所要占用的一个文件释放所要占用的4 4块，块号分别为块，块号分别为190190，185185，1841

32、84，170170。 其释放过程为：首先有2块的块号170，184写入超级块中，其状态如下图(b)所示。此时s_free=100,表示内存中登记的空闲块已经满。还要释放185、190，则系统把当前卷资源表中的空闲块数100连同100个登记项，写到185#中，然后将s_nfree清0，再将185、190#填入到超级块中，如图(c)所示。5）位示图法）位示图法利用计算机存储单元的一位指示对应盘块的空闲及分配情况利用计算机存储单元的一位指示对应盘块的空闲及分配情况取值取值0和和1分别表示空闲和占用分别表示空闲和占用 分配和回收过程分配和回收过程 特点：特点：位示图的大小由磁盘空间的大小（物理块总数）

33、决定，位示图的描述能力强，适合各种物理结构。既可分配连续盘块空间，又可离散分配，辅助空间占用较少6.6 文件的共享与保护文件的共享与保护1）基于索引结点的共享方法）基于索引结点的共享方法文件名文件名 索引结点指针索引结点指针TestWang用户文件目录用户文件目录文件名文件名 索引结点指针索引结点指针TestZhang用户文件目录用户文件目录Test文件文件不同用户（进程）的文件目录某文不同用户（进程）的文件目录某文件表目指向同一文件索引结点件表目指向同一文件索引结点特点：文件主删除文件，索引结点同时消失，共享用户共享指针悬空；此种链接不能跨越文件系统2）利用符号链实现文件共享）利用符号链实现文件共享文件名文件名指针指针TestW用户文件目录用户文件目录文件名文件名指针指针TestZ用户文件目录用户文件目录Test索引结点索引结点Test文件文件（Link）索引结点）索引结点（Link）文件（符号链接）文件（符号链接）其只包含其只包含Test文件的路径名文件的路径名文件主访问文件：文件主访问文件：直接通过文件索引结点直接通过文件