计算机操作系统课件(第四版)第78章

1、第七章第七章 文件管理文件管理第一节第一节文件和文件系统文件和文件系统第二节第二节文件的逻辑结构文件的逻辑结构第三节第三节文件文件目录目录第四节第四节文件共享文件共享17.1文件和文件系统文件和文件系统OS通过文件系统来组织和管理计算机中通过文件系统来组织和管理计算机中存储的大量数据和程序。存储的大量数据和程序。7.1.1文件、记录和数据项文件、记录和数据项7.1.2文件类型和文件系统模型文件类型和文件系统模型7.1.3文件操作文件操作27.1.1、文件、记录和数据项文件、记录和数据项l基于文件系统的概念，可以把数据组成分为基于文件系统的概念，可以把数据组成分为数据项数据项、记录记录和和文件文

2、件三级三级文件文件记录记录1记录记录2记录记录n数据项数据项1数据项数据项2数据项数据项n3例例1 1：学生成绩单：学生成绩单数据项数据项文件文件记录记录41.数据项数据项l基本数据项：描述一个对象的基本数据项：描述一个对象的某种某种属性的字符集属性的字符集l组合数据项：由组合数据项：由若干个若干个基本数据项组成基本数据项组成2.记录记录l记录是一组相关记录是一组相关数据项数据项的集合，用于描述一个对的集合，用于描述一个对象的某些属性。象的某些属性。l关键字：能够关键字：能够唯一唯一标识一个记录的数据项标识一个记录的数据项5l3.文件文件是指由创建者所定义的、具有文件名的一组是指由创建者所定义

3、的、具有文件名的一组相关数据元素的集合；相关数据元素的集合；l文件的属性文件的属性：文件类型、文件长度、文件的物理位：文件类型、文件长度、文件的物理位置、文件的建立时间等。置、文件的建立时间等。61、文件的类型、文件的类型1）按文件的性质和用途分：）按文件的性质和用途分：l系统文件：由系统软件构成的文件，只允许调用执系统文件：由系统软件构成的文件，只允许调用执行，不允许用户读和修改。行，不允许用户读和修改。l用户文件：只允许文件的授权者使用。用户文件：只允许文件的授权者使用。l库文件：允许用户调用不允许修改。库文件：允许用户调用不允许修改。7.1.2、文件类型和文件系统模型、文件类型和文件系统

4、模型7 2）按文件中数据的形式分：）按文件中数据的形式分：源文件、目标文件、可执行文件源文件、目标文件、可执行文件3）按存取控制属性分：）按存取控制属性分：l只执行文件、只读文件、读写文件只执行文件、只读文件、读写文件4）按组织形式和处理方式分：）按组织形式和处理方式分：l普通文件：普通文件：ASCII码或二进制码组成的字符文件码或二进制码组成的字符文件l目录文件：由文件目录组成目录文件：由文件目录组成l特殊文件：系统中的各类特殊文件：系统中的各类I/O设备设备82 2、文件系统模型、文件系统模型1)对象及其属性对象及其属性l文件：文件管理的直接对象文件：文件管理的直接对象l目录目录：方便用户

5、对文件的存取和检索：方便用户对文件的存取和检索l磁盘（磁带）存储空间磁盘（磁带）存储空间对象及其属性对象及其属性对对象操纵和管理对对象操纵和管理的软件集合的软件集合文件系统接口文件系统接口用户（程序）用户（程序）9例：例：MS-DOSMS-DOS的目录结构的目录结构盘盘块块数数首首盘盘块块号号日日期期时时间间备备用用属属性性扩扩展展名名文文件件名名10l3) 3) 文件系统的接口文件系统的接口l命令接口：用户与文件系统的接口命令接口：用户与文件系统的接口l程序接口：用户程序与文件系统的接口程序接口：用户程序与文件系统的接口l2) 2) 对对象操纵和管理的软件集合对对象操纵和管理的软件集合（核心

6、）（核心）l功能：对文件存储空间、文件目录的管理、地址功能：对文件存储空间、文件目录的管理、地址转换机制、文件读写、文件的共享与保护。转换机制、文件读写、文件的共享与保护。对象及其属性对象及其属性对对象操纵和管理对对象操纵和管理的软件集合的软件集合文件系统接口文件系统接口117.1.3、文件操作、文件操作用户通过文件系统提供的用户通过文件系统提供的系统调用系统调用实施对文件的操作实施对文件的操作1 1、最基本的文件操作、最基本的文件操作1 1）创建文件）创建文件：分配外存空间：分配外存空间建立目录项建立目录项2 2）删除文件）删除文件：删除目录项：删除目录项回收外存空间回收外存空间3 3）读文

7、件）读文件：文件名、内存目标地址、目录项、读指：文件名、内存目标地址、目录项、读指针针4 4）写文件）写文件：文件名、内存中源地址、目录项、写指：文件名、内存中源地址、目录项、写指针针122、文件的打开与关闭、文件的打开与关闭l打开：打开：系统将指名文件的属性（包括文件在外存的系统将指名文件的属性（包括文件在外存的物理位置）从外存拷贝到内存物理位置）从外存拷贝到内存打开文件表打开文件表的一个表的一个表目中，将表目编号返回用户目中，将表目编号返回用户l关闭：关闭：将文件从打开文件表的表目上删除，释放表将文件从打开文件表的表目上删除，释放表目空间目空间3、其它操作、其它操作l对文件属性的操作：对文

8、件属性的操作：改变文件名、文件主、访问权改变文件名、文件主、访问权l对文件目录的操作：对文件目录的操作：创建、删除目录等创建、删除目录等137.2文件的逻辑结构文件的逻辑结构 文件逻辑结构是从用户角度观察到的文件组织形式文件逻辑结构是从用户角度观察到的文件组织形式 文件物理结构是文件在外存上的存储组织形式文件物理结构是文件在外存上的存储组织形式文件逻辑结构的类型文件逻辑结构的类型顺序文件顺序文件索引文件索引文件索引顺序文件索引顺序文件14 提高检索速度提高检索速度 便于修改便于修改 减少文件占用的存储空间减少文件占用的存储空间对文件逻辑结构提出的基本要求：对文件逻辑结构提出的基本要求：157.

9、2.17.2.1、文件逻辑结构的类型、文件逻辑结构的类型1、有结构文件（记录式文件）、有结构文件（记录式文件）l1）定义：定义：由一个以上的记录构成的文件由一个以上的记录构成的文件l2）基本分类：基本分类：定长记录、变长记录定长记录、变长记录l3）文件的组织：文件的组织：l顺序文件：一系列记录按某种顺序排列形成顺序文件：一系列记录按某种顺序排列形成l索引文件：记录为变长，索引文件：记录为变长，每个每个记录一个索引表项记录一个索引表项l索引顺序文件：索引顺序文件：每组每组记录的第一个记录设一表项记录的第一个记录设一表项162 2、无结构文件（流式文件）、无结构文件（流式文件）l定义：定义：由字符

10、流构成的文件由字符流构成的文件l大量的源程序、可执行文件、库函数等大量的源程序、可执行文件、库函数等l文件长度以文件长度以字节字节为单位为单位l对流式文件的访问采用对流式文件的访问采用读写指针读写指针指出下一个要访指出下一个要访问的字符问的字符lUNIXUNIX系统中所有文件都被看作是流式文件系统中所有文件都被看作是流式文件177.2.27.2.2、顺序文件、顺序文件1 1、逻辑记录的排序、逻辑记录的排序l串结构串结构( (以时间排序以时间排序) )、顺序结构（按关键字排序）、顺序结构（按关键字排序）2 2、对顺序文件的读、对顺序文件的读/ /写操作写操作l1 1）定长记录：）定长记录：Rpt

11、r:= Rptr + LRptr:= Rptr + Ll2 2）变长记录：）变长记录：Rptr:= Rptr + LiRptr:= Rptr + LiR0R1R2Ri- 0- L- 2L- 3L- iLLRptr- 0L0R0LiRi-L0+1-(L0+1)+(Li-1+1)- (L0+1)+(Li+1)L0Rptr- 1183、顺序文件的优缺点：、顺序文件的优缺点：l1）优点：适于批量存取、能用于磁带存储）优点：适于批量存取、能用于磁带存储l2）缺点：）缺点：查找查找/修改修改/增增/删删单个记录单个记录效率低，系统效率低，系统开销大开销大R0R1R2Ri- L- 2L- 3L- iLLRp

12、tr顺序文件顺序文件197.2.37.2.3、索引文件、索引文件2 2、索引表索引表本身是一个定长记录的顺序文件本身是一个定长记录的顺序文件l索引号（记录键或关键字）索引号（记录键或关键字）l长度长度l指针指针索引号索引号长度长度指针指针0m0 xx1m1xx2m2xximixx索引表索引表R0R1R2Ri逻辑文件逻辑文件 1 1、利用定长记录的顺序文件访问变长记录的文件、利用定长记录的顺序文件访问变长记录的文件检索时，利用用户程序检索时，利用用户程序提供的关键字和查找算提供的关键字和查找算法法 ，检索索引表，检索索引表，访访问问主文件的记录。主文件的记录。向索引文件中增加新向索引文件中增加新

13、记录时，需修改索引记录时，需修改索引表。表。207.2.47.2.4、索引顺序文件、索引顺序文件索引顺序文件索引顺序文件是顺序文件和索引文件的结合，是是顺序文件和索引文件的结合，是最常见的一种逻辑文件形式。最常见的一种逻辑文件形式。原理：原理：1）顺序文件中的所有记录分为）顺序文件中的所有记录分为若干个组若干个组；2）为顺序文件建立一张索引表，在索引表中为）为顺序文件建立一张索引表，在索引表中为每组中的第一个记录建立一个索引项；每组中的第一个记录建立一个索引项；21索引键索引键逻辑地址逻辑地址AAABAAACAA索引表索引表AAAAABDAACBAAACAA逻辑文件逻辑文件主键主键其它属性其它

14、属性检索时，利用用户程序提供的关键字和查找算法，检索时，利用用户程序提供的关键字和查找算法，检索索引表检索索引表，.，利用顺序查找法查找，利用顺序查找法查找主文件主文件227.2.57.2.5、直接文件和哈希文件、直接文件和哈希文件1、直接文件、直接文件前述文件结构对记录进行存取时，都需利用给定前述文件结构对记录进行存取时，都需利用给定的记录键值（关键字），对线性表或链表进行建的记录键值（关键字），对线性表或链表进行建设，以找到指定记录的物理地址。设，以找到指定记录的物理地址。直接文件直接文件：根据给定的记录键值，直接获得物理：根据给定的记录键值，直接获得物理地址。即记录键值本身决定了记录的物

15、理地址地址。即记录键值本身决定了记录的物理地址键值转换键值转换由记录键值到记录物理地址的转换由记录键值到记录物理地址的转换232、哈希文件、哈希文件是目前应用最广泛的一种直接文件。是目前应用最广泛的一种直接文件。利用利用hash函数，将记函数，将记录键值转换为相应记录的地址。录键值转换为相应记录的地址。为了能实现文件存储空间的动态分配，由为了能实现文件存储空间的动态分配，由Hash函数所求得函数所求得的并非是相应记录的地址，而是的并非是相应记录的地址，而是指向一目录表相应表目的指指向一目录表相应表目的指针针，该表目的内容指向相应记录所在的物理块。，该表目的内容指向相应记录所在的物理块。例如，例

16、如，Hash函数函数A=H(K)K:记录键值记录键值A：该记录在目录表中对应表目的位置：该记录在目录表中对应表目的位置键值键值Hash函数函数f247.3文件目录文件目录目录管理的要求目录管理的要求文件控制块和索引结点文件控制块和索引结点目录结构目录结构目录查询技术目录查询技术25目录管理的要求目录管理的要求目录目录：用于标识系统中文件及其物理地址的一种数：用于标识系统中文件及其物理地址的一种数据结构，供检索使用。据结构，供检索使用。目录管理的要求：目录管理的要求：l实现实现“按名存取按名存取”最基本的功能最基本的功能l提高对目录的检索速度提高对目录的检索速度l文件共享文件共享l允许文件重名允

17、许文件重名267.3.1、文件控制块和索引结点、文件控制块和索引结点1、文件控制块（、文件控制块（FCB）l定义定义：描述和控制文件的数据结构：描述和控制文件的数据结构lFCB的有序集合称为的有序集合称为文件目录文件目录（或目录文件）（或目录文件）lFCB包含的信息项包含的信息项l基本信息：基本信息：文件名文件名/物理位置物理位置/逻辑结构逻辑结构/物理结构物理结构l存取控制信息：存取控制信息：不同用户存取权限不同不同用户存取权限不同l使用信息：使用信息：建立建立/修改的日期、时间等修改的日期、时间等盘盘块块数数第第一一块块号号日日期期时时间间备备用用属属性性扩扩展展名名文文件件名名MS-DO

18、S的的FCB272、索引结点、索引结点l1）索引结点的引入）索引结点的引入：l文件很多时，目录文件占用大量盘块。查找目录时文件很多时，目录文件占用大量盘块。查找目录时要多次启动磁盘，顺序读取存放目录文件的盘块。要多次启动磁盘，顺序读取存放目录文件的盘块。l实际上实际上，检索目录文件时，只需要利用文件名进行，检索目录文件时，只需要利用文件名进行查找，所以可以给文件目录瘦身。查找，所以可以给文件目录瘦身。lUNIX系统中，把文件名和文件描述信息分开，由系统中，把文件名和文件描述信息分开，由文件描述信息单独构成文件描述信息单独构成索引结点（简称索引结点（简称i结点）结点）lFCB改变为改变为：文件名

19、指向：文件名指向i结点的指针结点的指针280 13 14 15UNIX的文件目录的文件目录29l2）磁盘索引结点）磁盘索引结点：（每个文件唯一）：（每个文件唯一）文件主标识符文件主标识符：标识文件拥有者：标识文件拥有者文件类型文件类型文件存取权限文件存取权限文件物理地址文件物理地址：每个索引结点有：每个索引结点有13个地址项，直个地址项，直接或间接给出盘块号接或间接给出盘块号文件长度文件长度文件连接计数文件连接计数：所有指向该文件的文件名的指针计数所有指向该文件的文件名的指针计数文件存取时间文件存取时间：文件最近被存取修改的时间和索：文件最近被存取修改的时间和索引结点被修改的时间。引结点被修改

20、的时间。30l3）内存索引结点）内存索引结点：存放在内存中的索引结点。存放在内存中的索引结点。当文件被打开时，要将磁盘的索引结点拷贝到内当文件被打开时，要将磁盘的索引结点拷贝到内存的索引结点中。存的索引结点中。增加了以下内容：增加了以下内容：索引结点编号、状态、访问计数、文件所属文件索引结点编号、状态、访问计数、文件所属文件系统的逻辑设备号、链接指针系统的逻辑设备号、链接指针317.3.2、目录结构、目录结构1、单级目录结构、单级目录结构l在整个文件系统中建立一张目录表，每个文件占一在整个文件系统中建立一张目录表，每个文件占一个目录项。个目录项。l目录项包括目录项包括：文件名、扩展名、长度、类

21、型、物理：文件名、扩展名、长度、类型、物理地址及其它文件属性。地址及其它文件属性。xxxxxxxxxxxx文件名文件名2xxxxxxxxxxxx文件名文件名1状态位状态位文件说明文件说明物理地址物理地址文件名文件名表明目录项表明目录项是否空闲是否空闲32单级目录结构单级目录结构l新建文件新建文件时，要检索所有目录项，保证新文件名唯时，要检索所有目录项，保证新文件名唯一。建立新表项，置状态位为一。建立新表项，置状态位为1。l删除文件删除文件时，找到目录项，回收空间，清除目录项时，找到目录项，回收空间，清除目录项l优点优点：简单、能实现按名存取：简单、能实现按名存取l缺点缺点： 查找速度慢；查找速

22、度慢； 不允许重名；不允许重名； 不便于文件共享，只能适用于单用户环境。不便于文件共享，只能适用于单用户环境。xxxxxxxxxxxx文件名文件名2xxxxxxxxxxxx文件名文件名1状态位状态位文件说明文件说明物理地址物理地址文件名文件名表明目录项表明目录项是否空闲是否空闲332、两级目录结构、两级目录结构l为每个用户建立一个单独的用户文件目录，由用户为每个用户建立一个单独的用户文件目录，由用户的所有的所有FCB组成。组成。l系统中再建立一个主文件目录。每个用户的目录文系统中再建立一个主文件目录。每个用户的目录文件占一个目录项。件占一个目录项。xxxxSunxxxxWangxxxxZhan

23、g指向子目录指针指向子目录指针用户名用户名TestAlphaTestReportmisxDeviceBetaAlphaTestReportTestDeviceBetaMisxMFDUFD34两级目录结构两级目录结构l用户可请求系统为自己用户可请求系统为自己建立建立UFD，也可请求系统，也可请求系统将其将其撤消撤消。l新建新建用户文件时，用户文件时，OS检查用户检查用户UFD文件名，文件名，建立新表项。建立新表项。l删除删除用户文件时，用户文件时，OS查找用户查找用户UFD 文件目录文件目录项，回收存储空间，删除目录项。项，回收存储空间，删除目录项。l优点：优点： 提高检索目录的速度提高检索目录

24、的速度 不同的用户目录中文件可以同名不同的用户目录中文件可以同名353、多级目录结构、多级目录结构（树型目录结构）（树型目录结构）l1）目录结构：）目录结构：大型文件系统采用三级或三级以上的目录结构。大型文件系统采用三级或三级以上的目录结构。CBADBADEFAGCAKNJKMJFHA1234567891011121314151617 18 19 20 21ab36多级目录结构多级目录结构l2）路径名：）路径名： 从根目录到任何数据文件，都有一条从根目录到任何数据文件，都有一条唯一唯一的通路，的通路，把全部目录文件名和数据文件名，依次用把全部目录文件名和数据文件名，依次用“/”链接链接起来，构

25、成该数据文件的路径名（绝对路径）。起来，构成该数据文件的路径名（绝对路径）。如：如：B/E/J3）当前目录：）当前目录：进程在一定时间内所访的文件仅限于某个文件目进程在一定时间内所访的文件仅限于某个文件目录之下，该文件目录可设置为当前目录。录之下，该文件目录可设置为当前目录。把从当前目录开始直到数据文件为止构成的路径把从当前目录开始直到数据文件为止构成的路径名叫做名叫做相对路径相对路径。例如：用户。例如：用户B的当前目录是的当前目录是E，则，则可使用相对路径名可使用相对路径名“J”来访问自己的来访问自己的J文件。文件。374）增加和删除目录）增加和删除目录l增加目录：增加目录： 用户可为自己建

26、立用户可为自己建立UFD，并可再创建子目录。创建，并可再创建子目录。创建文件时，先查看自己的文件时，先查看自己的UFD及其子目录，无重名文及其子目录，无重名文件则在件则在UFD或某子目录中增加一个新目录项。或某子目录中增加一个新目录项。l删除目录：删除目录： 若为空目录，可直接删除目录项。若为空目录，可直接删除目录项。 若非空目录，则：若非空目录，则： a、不删除非空目录。采用递规方式删除。、不删除非空目录。采用递规方式删除。 b、可删除非空目录。所有文件、可删除非空目录。所有文件/子目录同时删除。子目录同时删除。MS-DOS38目录查询技术一目录查询技术一l线性检索法（顺序检索）：线性检索法

27、（顺序检索）： a.单级目录中单级目录中，利用用户提供的文件名，利用顺，利用用户提供的文件名，利用顺序查找法，从文件目录中找到指名文件的目录项。序查找法，从文件目录中找到指名文件的目录项。 b.在树型目录中在树型目录中，用户提供的文件名是由多个文，用户提供的文件名是由多个文件分量名组成的路径名，此时须对多级目录进行件分量名组成的路径名，此时须对多级目录进行查找查找7.3.3、目录查询技术、目录查询技术39根目录文件根目录文件假定用户给定的文件路径名是假定用户给定的文件路径名是/usr/ast/mbox，则查，则查找过程如下：找过程如下：/usr的目录文件的目录文件/usr/ast的目录文件的目

28、录文件40目录查询技术二目录查询技术二lHash方法：方法： 建立一张建立一张Hash索引文件目录后，便可利用索引文件目录后，便可利用Hash方方法进行查询。即系统利用用户提供的文件名并将法进行查询。即系统利用用户提供的文件名并将它变换为文件目录的索引值，再利用该索引值到它变换为文件目录的索引值，再利用该索引值到目录中去查找。目录中去查找。lHash冲突冲突n个不同的文件名有可能转换为相同个不同的文件名有可能转换为相同的的Hash值值41l一种处理冲突的有效规则：一种处理冲突的有效规则：l（1）利用）利用Hash法索引查找目录时，目录项空，表法索引查找目录时，目录项空，表示无文件示无文件l（2

29、）如果目录项中的文件名与指定文件名匹配，）如果目录项中的文件名与指定文件名匹配，表示找到文件，并找出文件的物理地址。表示找到文件，并找出文件的物理地址。l（3）如果目录项中的文件名与指定文件名不匹配，）如果目录项中的文件名与指定文件名不匹配，即即“冲突冲突”。需将。需将Hash值在加上一个常数，形成值在加上一个常数，形成新的索引值，再返回第一步重新开始查找。新的索引值，再返回第一步重新开始查找。427.4文件共享文件共享基基于于索索引引结结点点的的共共享享方方式式利利用用符符号号链链实实现现文文件件共共享享437.4.17.4.1、基于索引结点的共享方式、基于索引结点的共享方式引入引入：l在树

30、型结构目录中，多用户要共享一个文件，必须在树型结构目录中，多用户要共享一个文件，必须将共享文件链接到多个用户目录中。将共享文件链接到多个用户目录中。如何建立如何建立B目录与共享文件的链接呢？目录与共享文件的链接呢？l方法一：在目录文件中每个目录项是原始的方法一：在目录文件中每个目录项是原始的FCB，则在链接时，必须将文件的物理地址则在链接时，必须将文件的物理地址COPY到到B目目录中。录中。l缺点缺点：以后：以后B或或C继续向该文件添加的内容（盘块）继续向该文件添加的内容（盘块）将不能被共享。将不能被共享。ABCBBBCCCCCCC?BA根目录盘块数盘块数盘块号盘块号filec盘块数盘块数盘块

31、号盘块号文件名文件名2文件名文件名1物理地址物理地址盘块号盘块号盘块数盘块数C目录文件目录文件B目录文件目录文件盘块数盘块数盘块号盘块号filec盘块数盘块数盘块号盘块号文件名文件名2文件名文件名1盘块号盘块号盘块数盘块数44基于索引结点的共享方式基于索引结点的共享方式l文件目录中只设置文件名及指向相应索引结点的指文件目录中只设置文件名及指向相应索引结点的指针；针；l文件的物理地址及其它的文件属性等信息只存放在文件的物理地址及其它的文件属性等信息只存放在索引结点中；索引结点中；C用户文件目录用户文件目录CmnFile1Owner=CCount=2物理地址物理地址索引结点索引结点CmnFile1

32、B用户文件目录用户文件目录CmnFile1链接计链接计数数缺点：用户缺点：用户C不再需要此文件时不能执行删除不再需要此文件时不能执行删除457.4.27.4.2、利用符号链实现文件共享、利用符号链实现文件共享符号链与符号链接符号链与符号链接l由系统创建一个由系统创建一个LinkLink类型新文件，新文件中包含类型新文件，新文件中包含被链接（共享）文件的路径名。被链接（共享）文件的路径名。l要访问共享文件，则必须先访问要访问共享文件，则必须先访问LinkLink新文件，此新文件，此时将被时将被OSOS截获，截获，OSOS根据新文件中的路径名去读共根据新文件中的路径名去读共享文件，这种方式称为享文

33、件，这种方式称为符号链接符号链接。l只有文件主（文件创建者）才拥有指向文件索引只有文件主（文件创建者）才拥有指向文件索引结点的指针。因此，文件主可随时删除此文件结点的指针。因此，文件主可随时删除此文件46优缺点：优缺点：l能够链接任何地方的文件能够链接任何地方的文件l按路径查找的访问开销大，需要冗余的索引结点按路径查找的访问开销大，需要冗余的索引结点l允许使用多个不同的名字访问共享文件，因此遍允许使用多个不同的名字访问共享文件，因此遍历文件系统时会重复访问此共享文件。历文件系统时会重复访问此共享文件。filecfilebOwner=C类型：普通类型：普通文件物理地址文件物理地址Owner=B类

34、型：类型：LINK文件物理地址文件物理地址C的目录的目录B的目录的目录文件文件filec文件文件fileb符号链接符号链接符号链符号链47第八章第八章 磁盘存储器的管理磁盘存储器的管理第一节第一节外存的组织方式外存的组织方式第二节第二节文件存储空间的管理文件存储空间的管理488.1外存的组织方式外存的组织方式连续分配连续分配顺序式文件结构顺序式文件结构链接分配链接分配链接式文件结构链接式文件结构索引分配索引分配索引式文件结构索引式文件结构 外存分配方式即文件的物理组织形式。文件的物外存分配方式即文件的物理组织形式。文件的物理结构与外存分配方式有关，采用不同的分配方式时，理结构与外存分配方式有关

35、，采用不同的分配方式时，将形成不同的文件物理结构。将形成不同的文件物理结构。分配方式分配方式 文件物理结构文件物理结构498.1.18.1.1、连续组织方式、连续组织方式1 1、连续分配方式原理：、连续分配方式原理：l为每一个文件分配一组相邻接的盘块；为每一个文件分配一组相邻接的盘块；l把逻辑文件中的记录顺序的存储到邻接的各物理把逻辑文件中的记录顺序的存储到邻接的各物理盘块中，此时的文件结构称为顺序文件结构。盘块中，此时的文件结构称为顺序文件结构。目录目录26f418list314tr20coulengthstarfile048121591316201721261014182237111519

36、23coutrflist503 3、连续分配的优缺点、连续分配的优缺点l顺序访问容易，并可实现直接存取；顺序访问容易，并可实现直接存取；l顺序访问速度快；（磁头的移动距离最少）顺序访问速度快；（磁头的移动距离最少）l缺点：缺点：要求有连续的存储空间（定期做紧凑处要求有连续的存储空间（定期做紧凑处理）、必须事先知道文件的长度。理）、必须事先知道文件的长度。2 2、外部碎片问题、外部碎片问题l随着空间的分配和回收，磁盘空间会出现一些随着空间的分配和回收，磁盘空间会出现一些小的、难以再利用的连续区，称为外存的碎片。小的、难以再利用的连续区，称为外存的碎片。l“碎片碎片”的解决方法的解决方法“紧凑紧凑

37、”518.1.28.1.2、链接组织方式、链接组织方式将文件装到多个将文件装到多个离散离散的盘块中，是离散的分配方式。的盘块中，是离散的分配方式。原理：原理：通过在每个盘块上的链接指针，将同属于一个文件的通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，形成多个离散的盘块链接成一个链表，形成链接式文件结链接式文件结构构。物理文件称为。物理文件称为链接文件链接文件。类型：类型：l隐式链接隐式链接l显式链接显式链接521、隐式链接隐式链接l在文件的每个在文件的每个目录项目录项中，都含有指向链接文件第中，都含有指向链接文件第一盘块和最后一个盘块的指针。一盘块和最后一个盘块的

38、指针。l每个每个盘块中盘块中都有指向下一个盘块的指针。都有指向下一个盘块的指针。l特点：特点：只适合于顺序访问，随机访问效率极低。只适合于顺序访问，随机访问效率极低。53隐式链接隐式链接目录目录起始块号起始块号:4结束块号结束块号:2文件名文件名:jeep01236789451011542、显式链接、显式链接l把用于链接文件各物理块的指针，显式地存放在把用于链接文件各物理块的指针，显式地存放在内存内存的一张的一张“链接表链接表”中。该表在整个磁盘只设置中。该表在整个磁盘只设置一张。即一张。即文件分配表文件分配表（FAT）。序号为盘块号）。序号为盘块号0.n-1lFCB（文件控制块）：每个文件的

39、首盘块号作为（文件控制块）：每个文件的首盘块号作为文件地址记录在文件地址记录在FCB中。中。550122EOF3475678物理块号物理块号FAT81FCB物理地址物理地址:4显式链接显式链接568.1.38.1.3、FATFAT和和NTFSNTFS技术技术微软的文件系统：微软的文件系统：lFAT12早期早期MS-DOS系统系统lFAT16MS-DOSlFAT32Win95、Win98lNTFSWinNT、Win2000、Winxp上述文件分配方式基本类似于上述文件分配方式基本类似于显式链接显式链接57“卷卷”概念的引入：概念的引入：源于早期的源于早期的MS-DOS的的FAT文件系统。文件系统

40、。支持将支持将一个物理磁盘一个物理磁盘分成分成四个逻辑磁盘四个逻辑磁盘，每个逻辑盘，每个逻辑盘就是一个就是一个卷卷（分区）。（分区）。C、D、E、F四个卷。四个卷。每个卷每个卷都是一个能被单独格式化的使用的都是一个能被单独格式化的使用的逻辑单元逻辑单元。都划出单的区域存放自己的都划出单的区域存放自己的目录和目录和FAT表表，以及自己，以及自己的逻辑驱动器字母。的逻辑驱动器字母。581、FAT12：l1）以盘块为基本分配单位）以盘块为基本分配单位在早期的在早期的MS-DOS系统中。采用显式链接的方式。系统中。采用显式链接的方式。每个磁盘分区都有每个磁盘分区都有FAT表。文件的首盘块号放在自己表。

41、文件的首盘块号放在自己的的FCB中，中，FAT的每个表项中存放下一个盘块号。的每个表项中存放下一个盘块号。例如：例如：下面计算该文件系统中，磁盘的最大容量。下面计算该文件系统中，磁盘的最大容量。FAT表项为表项为12位。位。FAT表中最多有表中最多有个表项。个表项。盘块大小盘块大小512B，每个磁盘分区的容量为，每个磁盘分区的容量为一个物理磁盘共四个分区，总容量为一个物理磁盘共四个分区，总容量为40962MB(4096*512B)8MB590EOF122EOF34756078物理块号物理块号FAT81FCBA物理地址物理地址:4MS-DOS的文件物理结构的文件物理结构FCBB物理地址物理地址:

42、6例例1：MS-DOS的文件物理结构的文件物理结构文件文件A占用盘块号：占用盘块号：4、7、8、1、2文件文件B占用盘块号：占用盘块号：6、0602）簇的基本概念）簇的基本概念为了适应不断增大的磁盘容量的需要，以为了适应不断增大的磁盘容量的需要，以簇簇为基本单为基本单位进行分配。位进行分配。簇是一组连续的扇区。簇的大小一般为簇是一组连续的扇区。簇的大小一般为2n个个盘块。盘块。MS-DOS中，簇的容量：中，簇的容量：一个、一个、2个、个、4个、个、8个个扇区扇区簇为一个扇区时，磁盘容量：簇为一个扇区时，磁盘容量：簇为两个扇区时，磁盘容量：簇为两个扇区时，磁盘容量：簇为四个扇区时，磁盘容量：簇为

43、四个扇区时，磁盘容量：簇为八个扇区时，磁盘容量：簇为八个扇区时，磁盘容量：8MB16MB32MB64MB簇的优点：适应不断增大的磁盘容量。缺点：簇内碎片簇的优点：适应不断增大的磁盘容量。缺点：簇内碎片612、FAT16FAT12表最多只允许表最多只允许4096个表项，即最多分为个表项，即最多分为4096个簇。解决办法：增加个簇。解决办法：增加FAT表的宽度，以增加表的宽度，以增加FAT表表的表项数目。的表项数目。FAT16FAT表宽度表宽度16位。最多允许位。最多允许65536个表项。个表项。（216=65536）即最多可有）即最多可有65536个簇。个簇。把具有把具有16位表宽的位表宽的FA

44、T表称为表称为FAT16。簇中的盘块数可为簇中的盘块数可为4、8、16、32、64，因此，因此，最大最大分区空间：分区空间：216*64*512=2048MB缺点：簇内碎片太大。缺点：簇内碎片太大。FAT12和和FAT16不支持长文件名，受不支持长文件名，受8+3格式限制。格式限制。623、FAT32用用32位表示位表示FAT表的表项宽度。最多允许表的表项宽度。最多允许232个表项个表项FAT32的每个簇都固定为的每个簇都固定为4KB。FAT32分区的最大空间分区的最大空间4KB*232=2TBFAT32主要应用于主要应用于Win98及后续及后续Windows系统。系统。优点：优点：簇较小，簇

45、较小，簇内碎片减少簇内碎片减少。支持的磁盘容量大。支持的磁盘容量大缺点：缺点：1、文件分配表太大，文件分配表太大，运行速度慢运行速度慢。2、有最小管理空间限制。卷至少有、有最小管理空间限制。卷至少有65537个个簇，所以簇，所以不支持不支持容量容量小于小于512MB的分区。的分区。3、单个文件长度、单个文件长度不能大于不能大于4GB4、不能保持向下兼容。、不能保持向下兼容。634、NTFS1）NTFS新特性新特性适用于适用于Win2000、xp、2003等。等。使用了使用了64位磁盘地址。支持位磁盘地址。支持264字节磁盘分区。字节磁盘分区。支持长文件名，支持长文件名，255个字符。个字符。具

46、有容错功能。具有容错功能。提供了数据的一致性。提供了数据的一致性。提供了文件加密、文件压缩。提供了文件加密、文件压缩。642）NTFS的磁盘组织的磁盘组织以以簇簇作为空间分配和回收的基本单位。一个簇包含作为空间分配和回收的基本单位。一个簇包含2n个盘块个盘块，大多数情况下，簇大小为，大多数情况下，簇大小为4kB。支持扇区大小不是支持扇区大小不是512字节的字节的非标准磁盘非标准磁盘。3）NTFS的文件组织的文件组织以以卷卷为单位，将一个卷中的所有文件信息、目录信息、为单位，将一个卷中的所有文件信息、目录信息、可用的未分配空间信息，以文件记录的方式记录在主可用的未分配空间信息，以文件记录的方式记

47、录在主控文件表中（控文件表中（MFT）。）。每个文件占一行，称为该文件每个文件占一行，称为该文件的元数据的元数据，也称，也称文件控制字文件控制字。元数据大小。元数据大小1KB文件较小时，文件较小时，文件的所有信息都存储在元数据中文件的所有信息都存储在元数据中文件较大时，文件较大时，文件的一部分属性存储在元数据中，其文件的一部分属性存储在元数据中，其他属性，如文件内容放在其他簇中，并用指针连接。他属性，如文件内容放在其他簇中，并用指针连接。654）NTFS的不足之处的不足之处只能被只能被WinNT识别。识别。NTFS可存取可存取FAT系统文件，但系统文件，但是，反之不可以。即缺乏兼容性。是，反之

48、不可以。即缺乏兼容性。668.1.48.1.4、索引组织方式、索引组织方式1 1、链接分配方式的缺点：、链接分配方式的缺点：l不能支持高效的直接存取不能支持高效的直接存取lFATFAT需要占用较大的内存空间需要占用较大的内存空间2 2、单级索引分配、单级索引分配l基本思想：基本思想：将每个文件对应的盘块号集中存放将每个文件对应的盘块号集中存放l方法：方法：为每个文件分配一个索引块（表），该为每个文件分配一个索引块（表），该文件的所有盘块号记录在内。文件的所有盘块号记录在内。67索引分配方式的索引分配方式的优缺点优缺点：l是一种离散分配方式，不会产生外部碎片是一种离散分配方式，不会产生外部碎片l

49、支持直接访问支持直接访问l缺点：缺点：花费较多的外存空间花费较多的外存空间04812159131620172126101418223711151923countFile块序号块序号Jeep19目录目录 9 16 1 10 22 -119索引表索引表683、多级索引分配、多级索引分配l基本思想：基本思想：为大文件分配磁盘空间时，可形成多个索引块，为大文件分配磁盘空间时，可形成多个索引块，需建立索引块的索引，放到一个索引块中，形需建立索引块的索引，放到一个索引块中，形成两级索引分配方式。成两级索引分配方式。l如果文件非常大，还可用三级、四级索引分配如果文件非常大，还可用三级、四级索引分配方式。方式

50、。69第二级索引第二级索引012105106254356357985105106254356357985磁盘空间磁盘空间36074011253607401125第一级索引第一级索引两级索引分配两级索引分配704、混合索引分配、混合索引分配l多种索引分配方式相结合而形成的一种分配方式。多种索引分配方式相结合而形成的一种分配方式。既采用了直接地址，又采用了一级、两级或多级索既采用了直接地址，又采用了一级、两级或多级索引分配方式。引分配方式。l已在已在UNIX系统中采用。索引结点中共设系统中采用。索引结点中共设13个地址个地址项。其中项。其中i.addr(0)i.addr(9)存放直接地址，其它存放

51、直接地址，其它地址项提供间接地址。地址项提供间接地址。71datedatedatedatedatedatedatedatei.addr(0)i.addr(1)SingleindirectDoubleindirect混合索引方式混合索引方式索引结点索引结点728.2文件存储空间的管理文件存储空间的管理空闲表法和空闲链表法空闲表法和空闲链表法位示图法位示图法成组链接法成组链接法分配方式：连续分配、离散分配分配方式：连续分配、离散分配存储空间的基本分配单位是以磁盘块（扇区）存储空间的基本分配单位是以磁盘块（扇区）为单位，而非字节。为单位，而非字节。738.2.1、空闲表法和空闲链表法、空闲表法和空闲

52、链表法1、空闲表法、空闲表法连续分配方式连续分配方式l为外存上的所有空闲区建立一张空闲表为外存上的所有空闲区建立一张空闲表l存储空间的分配与回收存储空间的分配与回收l分配：首次适应算法、循环首次适应算法分配：首次适应算法、循环首次适应算法l回收：考虑邻接的前后空闲区拼接合并回收：考虑邻接的前后空闲区拼接合并742、空闲链表法、空闲链表法离散分配方式离散分配方式l空闲盘块链空闲盘块链将磁盘上的所有空闲空间，以盘块为单位拉成将磁盘上的所有空闲空间，以盘块为单位拉成一条链。一条链。分配盘块时从链首开始；回收盘块时插入链尾分配盘块时从链首开始；回收盘块时插入链尾l空闲盘区链空闲盘区链将磁盘上所有空闲盘

53、区（每个盘区可包含若干将磁盘上所有空闲盘区（每个盘区可包含若干个盘块）拉成一条链。个盘块）拉成一条链。每个盘区含有：指示下一个盘区的指针；每个盘区含有：指示下一个盘区的指针；本盘区大小的信息本盘区大小的信息分配盘区常采用首次适应算法；回收时要和相分配盘区常采用首次适应算法；回收时要和相邻空闲盘区合并邻空闲盘区合并758.2.28.2.2、位示图法、位示图法1、位示图、位示图l利用二进制的一位来表示磁盘中一个盘块的使用利用二进制的一位来表示磁盘中一个盘块的使用情况。由所有盘块所对应的位构成一个集合，称情况。由所有盘块所对应的位构成一个集合，称为为位示图位示图。用。用mxn个位数构成个位数构成位示

54、图位示图。2、盘块的分配（分三步进行）、盘块的分配（分三步进行）l顺序扫描位示图，找到一个或一组值为顺序扫描位示图，找到一个或一组值为“0”的位；的位；l将找到的位转换成与之相对应的盘块号：将找到的位转换成与之相对应的盘块号：b=n(i-1)+jl修改位示图，令修改位示图，令mapi,j=1761100011100100110000111111000011111100011111100001234.161 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16位示图位示图773 3、盘块的回收（分两步进行）、盘块的回收（分两步进行）l将回收的盘块号转换成位示图中的行号和列号：

55、将回收的盘块号转换成位示图中的行号和列号： i=(b-1) DIV n +1 j=(b-1) MOD n +1i=(b-1) DIV n +1 j=(b-1) MOD n +1l修改位示图，修改位示图，令令mapi,j=0优点优点l从位示图中很容易找到一个或一组相邻接的空闲从位示图中很容易找到一个或一组相邻接的空闲盘块；盘块；l位示图占用空间小，可常驻内存；位示图占用空间小，可常驻内存；l常用于微型机和小型机中，如常用于微型机和小型机中，如CP/MCP/M788.2.38.2.3、成组链接法、成组链接法结合了空闲表法和空闲链表法而形成的一种空闲盘块结合了空闲表法和空闲链表法而形成的一种空闲盘块

56、管理方法，克服了表太长的缺点。（管理方法，克服了表太长的缺点。（UNIXUNIX采用采用）1 1、空闲盘块的组织、空闲盘块的组织l空闲盘块号栈超级块空闲盘块号栈超级块l每每100100个空闲盘块作为一组个空闲盘块作为一组l将第一组的盘块总数和所有的盘块号，记入空闲盘将第一组的盘块总数和所有的盘块号，记入空闲盘块号栈中块号栈中l每组含有的盘块数和所有盘块记入前一组的末盘块每组含有的盘块数和所有盘块记入前一组的末盘块l最后一组只有最后一组只有9999个盘块，以个盘块，以0作为结束标志作为结束标志79空闲盘块号栈总数s.free019899201299300400399301500499401599

57、501第一组第二组第三组最后一组80栈底栈顶2 2、空闲盘块的分配、空闲盘块的分配用户申请一个盘块用户申请一个盘块超级块中空闲块总数超级块中空闲块总数1？从栈顶取出盘块号，从栈顶取出盘块号，将对应盘块分给用户将对应盘块分给用户将栈底盘块号对应的盘块内容读入栈中，将栈底盘块号对应的盘块内容读入栈中，把原栈底对应的盘块分配出去把原栈底对应的盘块分配出去NY将回收盘块的盘块号记入空闲盘块号栈顶部，总数将回收盘块的盘块号记入空闲盘块号栈顶部，总数1当栈中原空盘块总数当栈中原空盘块总数100时（栈满），将现有栈中的时（栈满），将现有栈中的100个盘块号，记入新回收盘块中，再将其盘块号作为个盘块号，记入新

58、回收盘块中，再将其盘块号作为新栈底。新栈底。3 3、空闲盘块的回收、空闲盘块的回收81118245584568空闲块数空闲块数98118245584568Unix系统中超级块如下图示，问：系统中超级块如下图示，问：（1）当用户释放了）当用户释放了78，89，108，204物理块物理块后，超级块中的变化情况如何？后，超级块中的变化情况如何？（2）当用户又申请了五个物理）当用户又申请了五个物理块，超级块中的变化情况如何？块，超级块中的变化情况如何？82836.6.3磁盘容错技术磁盘容错技术磁盘数据的不安全因素磁盘数据的不安全因素l人为因素：有意或无意的（错误）行为；人为因素：有意或无意的（错误）行

59、为；l系统因素：系统的某些（个）部分出现异常；磁盘故障系统因素：系统的某些（个）部分出现异常；磁盘故障l自然因素：时间的推移，磁盘上的数据溢出或消失。自然因素：时间的推移，磁盘上的数据溢出或消失。可以采取的措施可以采取的措施l通过存取控制机制，防止人为因素；通过存取控制机制，防止人为因素；l通过磁盘容错技术，来防止磁盘故障；通过磁盘容错技术，来防止磁盘故障；l通过通过“后备系统后备系统”，来防止自然因素。，来防止自然因素。容错技术（系统容错技术）：容错技术（系统容错技术）：l通过增加冗余的磁盘驱动器、控制器等方法，来提高磁通过增加冗余的磁盘驱动器、控制器等方法，来提高磁盘系统可靠性的一种技术。

60、盘系统可靠性的一种技术。84容错技术分类容错技术分类三类三类低级磁盘容错技术低级磁盘容错技术SFT-I、中级磁盘容错技术、中级磁盘容错技术SFT-II、基于集群技术的容错功能基于集群技术的容错功能1、低级磁盘容错技术、低级磁盘容错技术SFT-Il防止因磁盘表面发生缺陷所引起的数据丢失。防止因磁盘表面发生缺陷所引起的数据丢失。l1）双份目录和双份文件分配表）双份目录和双份文件分配表l在不同磁盘或磁盘的不同区域中，分别建立主在不同磁盘或磁盘的不同区域中，分别建立主目录、主文件分配表；备份目录和文件分配表目录、主文件分配表；备份目录和文件分配表l当主目录、主文件分配表损坏时，系统自动启当主目录、主文