操作系统C第6章文件管理-new分析课件.ppt

1、2022-12-221第第6章章 文件管理文件管理 6.1 文件与文件系统文件与文件系统 6.2 文件的逻辑结构文件的逻辑结构 6.3 外存分配方式外存分配方式 6.4 目录管理目录管理 6.5 文件存储空间的管理文件存储空间的管理 6.6 文件的共享与保护文件的共享与保护 6.7 数据一致性控制数据一致性控制 开 始2022-12-2226.1 文件和文件系统文件和文件系统vOS采用采用文件系统文件系统来组织管理大量的文件。来组织管理大量的文件。v在文件系统中，通常把数据分为在文件系统中，通常把数据分为数据项数据项、记录记录和和文件文件三级。三级。2022-12-2236.1.1数据项、记录

2、和文件数据项、记录和文件1.数据项数据项:最低级的数据组织形式最低级的数据组织形式1)基本数据项基本数据项：原子数据，最小逻辑单位，：原子数据，最小逻辑单位，即数据元素、字段。如学号、姓名即数据元素、字段。如学号、姓名2)组合数据项组合数据项：由若干个基本数据项组成，：由若干个基本数据项组成，简称组项。如工资（基本工资、奖励工资）简称组项。如工资（基本工资、奖励工资）数据项的型和值：型指数据项名字和类型，数据项的型和值：型指数据项名字和类型，实体在数据项上的数据则称为值。实体在数据项上的数据则称为值。2022-12-2242.记录：一组相关数据项的集合，用于描述记录：一组相关数据项的集合，用于

3、描述一个对象在某方面的属性。一个对象在某方面的属性。关键字：唯一能够标示一条记录的数据项。关键字：唯一能够标示一条记录的数据项。2022-12-2253.文件文件v 文件文件是指由创建者定义、具有文件名的一组相是指由创建者定义、具有文件名的一组相关元素的集合关元素的集合，可分为，可分为有结构有结构文件和文件和无结构无结构文文件两种。件两种。v 文件还有些具体属性：文件还有些具体属性：文件类型文件类型 文件长度文件长度 文件物理位置文件物理位置 文件的建立时间文件的建立时间2022-12-2266.1.2 文件类型和文件系统模型文件类型和文件系统模型1.文件类型文件类型1)按用途分类：按用途分类

4、：1)系统文件系统文件2)用户文件用户文件3)库文件库文件2)按文件中数据形式分类：按文件中数据形式分类：1)源文件源文件2)目标文件目标文件3)可执行文件可执行文件2022-12-2273)按存取控制属性分类：按存取控制属性分类：1)执行文件执行文件2)只读文件只读文件3)读写文件读写文件2022-12-2282.文件系统模型文件系统模型模型分为三个层次，如图模型分为三个层次，如图6-2示：示：1)对象及属性（文件、对象及属性（文件、目录、磁盘存储空间）目录、磁盘存储空间）2)对对象操纵和管理的对对象操纵和管理的软件集合软件集合3)文件系统的接口（命文件系统的接口（命令接口、程序接口）令接口

5、、程序接口）文件系统接口文件系统接口对对象操纵和管理对对象操纵和管理的软件集合的软件集合对象及属性对象及属性用户用户(程序程序)图图6-22022-12-2296.1.3 文件操作文件操作1.最基本的文件操作最基本的文件操作1)创建文件：分配外存空间，创建新的目录项创建文件：分配外存空间，创建新的目录项2)删除文件：删除目录项，收回空间删除文件：删除目录项，收回空间3)读文件：查找目录找到文件的外存位置读文件：查找目录找到文件的外存位置4)写文件：通过目录找到文件的目录项，用目写文件：通过目录找到文件的目录项，用目录中的写指针进行写操作录中的写指针进行写操作5)截断文件截断文件6)设置文件的读

6、设置文件的读/写位置写位置2022-12-2210 当前当前OS所提供的大多数文件操作过程都是这所提供的大多数文件操作过程都是这样两步：检索文件目录找到文件的属性和在样两步：检索文件目录找到文件的属性和在外存的位置；对文件实施相应的操作。外存的位置；对文件实施相应的操作。所谓所谓“打开打开”文件是指将文件的属性从外存文件是指将文件的属性从外存拷贝到内存打开文件表的一个表项中，并将拷贝到内存打开文件表的一个表项中，并将该表项的编号返回给用户。该表项的编号返回给用户。2.文件的文件的“打开打开”和和“关闭关闭”操作操作2022-12-22116.2 文件的逻辑结构文件的逻辑结构计算机文件的两种结构

7、：计算机文件的两种结构：v 文件文件逻辑结构逻辑结构(File Logical Structure)：从用从用户角度出发所观察到的文件组织形式，是用户角度出发所观察到的文件组织形式，是用户可以直接处理的数据及其结构，独立于物户可以直接处理的数据及其结构，独立于物理特性，又称为理特性，又称为文件组织文件组织(File Organization)。v文件文件物理结构物理结构(File Physical Structure)：指文指文件在外存上的存储组织形式，又称为文件的件在外存上的存储组织形式，又称为文件的存储结构。存储结构。2022-12-2212文件逻辑结构文件逻辑结构对文件逻辑结构的基本要求

8、：对文件逻辑结构的基本要求：v提高检索记录的速度提高检索记录的速度v便于修改记录便于修改记录v降低文件的存储费用：文件占用的空间，降低文件的存储费用：文件占用的空间，不要求连续的大空间。不要求连续的大空间。2022-12-22136.2.1文件逻辑结构的类型文件逻辑结构的类型1 有结构文件有结构文件：也称为：也称为记录式文件记录式文件，组成文，组成文件的数据项单位为记录件的数据项单位为记录。根据用户和系统管理的需要，可采用多种根据用户和系统管理的需要，可采用多种方式组织记录形成方式组织记录形成顺序文件顺序文件、索引文件索引文件和和索引顺序文件索引顺序文件文件逻辑结构可分为两类文件逻辑结构可分为

9、两类：2022-12-2214 顺序文件顺序文件：一系列记录按照某种顺序排列所：一系列记录按照某种顺序排列所形成的文件。其中的记录通常是定长的。形成的文件。其中的记录通常是定长的。索引文件索引文件：当记录为可变长时，通常为之建：当记录为可变长时，通常为之建立一张索引表，并为每一个记录设置一个表立一张索引表，并为每一个记录设置一个表项，以加快检索记录的速度。项，以加快检索记录的速度。索引顺序文件索引顺序文件：为文件建立一张索引表，为：为文件建立一张索引表，为每一组记录中的第一个记录设置一个表项。每一组记录中的第一个记录设置一个表项。2022-12-22152 无结构文件无结构文件：也称：也称流式

10、文件流式文件，组成文件的数，组成文件的数据单位为据单位为ASCII字符，如源程序、可执行文字符，如源程序、可执行文件等。件等。2022-12-22166.2.2 顺序文件顺序文件1.顺序文件分类顺序文件分类1)顺序无序文件（顺序无序文件（串结构）：各记录之间的串结构）：各记录之间的顺序与关键字无关，由输入的时间决定先后顺序与关键字无关，由输入的时间决定先后顺序。顺序。2)顺序有序文件（顺序有序文件（顺序结构）：所有记录安顺序结构）：所有记录安关键字排序关键字排序注意：注意：为提高检索效率，常将顺序文件组织为提高检索效率，常将顺序文件组织成顺序有序文件。成顺序有序文件。2022-12-22172

11、.对顺序有序文件的读对顺序有序文件的读/写操作写操作 顺序文件中的记录可以是定长也可以是变顺序文件中的记录可以是定长也可以是变长的长的 对于定长记录的顺序文件，如果已知当前对于定长记录的顺序文件，如果已知当前记录的逻辑地址，便很容易确定下一个记记录的逻辑地址，便很容易确定下一个记录的逻辑地址。读写文件时设置一个读指录的逻辑地址。读写文件时设置一个读指针针Rptr和一个写指针和一个写指针Wptr，每读写一条每读写一条记录分别使记录分别使Rptr+L和和Wptr+L。对于变长记录则指针应加对于变长记录则指针应加Li+1,如下图如下图2022-12-22182022-12-2219 对于定长记录文件

12、，如果要查找第对于定长记录文件，如果要查找第i个记录，个记录，可直接根据下式计算来获得第可直接根据下式计算来获得第i个记录相对于个记录相对于第一个记录首址的地址：第一个记录首址的地址：Ai=iL 可变长度记录的文件，要查找其第可变长度记录的文件，要查找其第i个记录，个记录，6.2.3索引文件索引文件2022-12-2220v当当记录为可变长度记录为可变长度时，通常采用索引文件方时，通常采用索引文件方式。式。v为为每个文件每个文件建立一张索引表，并将主文件的建立一张索引表，并将主文件的每个记录的记录号、长度和逻辑地址记录在每个记录的记录号、长度和逻辑地址记录在索引表中。索引表中。v优点：因优点：

13、因将可变长的记录将可变长的记录的索引转化为的索引转化为定长定长的记录项的记录项的索引，故方便实现直接存取。的索引，故方便实现直接存取。v缺点：缺点：每个文件每个文件有一索引表有一索引表，存储费用高。存储费用高。2022-12-22212022-12-2222注意注意 索引文件索引文件 索引文件由主文件和索引表构成。索引文件由主文件和索引表构成。主文件：文件本身。主文件：文件本身。索引表：在文件本身外建立的一张表，由索引表：在文件本身外建立的一张表，由若干索引项组成。索引表必须按主关键字有若干索引项组成。索引表必须按主关键字有序排列。序排列。2022-12-2223索引文件的存储索引文件的存储1

14、索引文件的存储索引文件的存储 索引文件在存储器上分为两个区：索引区和索引文件在存储器上分为两个区：索引区和数据区。索引区存放索引表，数据区存放主数据区。索引区存放索引表，数据区存放主文件。文件。2022-12-2224 2 建立索引文件的过程：建立索引文件的过程：（1）按输入记录的先后次序建立数据区和按输入记录的先后次序建立数据区和索引表。其中索引表中关键字是无序的索引表。其中索引表中关键字是无序的（2）待全部记录输入完毕后对索引表进行待全部记录输入完毕后对索引表进行排序，排序后的索引表和主文件一起就形成排序，排序后的索引表和主文件一起就形成了索引文件了索引文件2022-12-22256.2.

15、4索引顺序文件索引顺序文件v是综合是综合顺序顺序和和索引索引两种文件构成方式的两种文件构成方式的优点，先检索优点，先检索索引表索引表，找到所在记录组，找到所在记录组中第一个记录表项，并找到第一个记录中第一个记录表项，并找到第一个记录在主文件中位置，然后再顺序查找所需在主文件中位置，然后再顺序查找所需记录记录。如如图图6-5示：示：v优点优点：因只为每组记录的：因只为每组记录的首记录首记录设置一设置一索引表项，因此能有效减少索引表所占索引表项，因此能有效减少索引表所占的空间。的空间。2022-12-2226图图6-5 索引顺序文件索引顺序文件Chen LinBao RongAn KangAn Q

16、i其它属性其它属性姓名姓名Chen LinBao RongAn Qi逻辑地址逻辑地址键键索引表2022-12-2227 注意：注意：通常将索引非顺序文件简称为索引文件。通常将索引非顺序文件简称为索引文件。索引非顺序文件主文件无序，顺序存取索引非顺序文件主文件无序，顺序存取将会频繁地引起磁头移动，适合于随机存取，将会频繁地引起磁头移动，适合于随机存取，不适合于顺序存取。不适合于顺序存取。索引顺序文件的主文件是有序的，适合索引顺序文件的主文件是有序的，适合于随机存取、顺序存取。于随机存取、顺序存取。索引顺序文件的索引是稀疏索引。索引索引顺序文件的索引是稀疏索引。索引占用空间较少，是最常用的一种文件

17、组织。占用空间较少，是最常用的一种文件组织。2022-12-2228回回 顾顾 什么是顺序文件、索引文件、索引顺序文件？什么是顺序文件、索引文件、索引顺序文件？索引文件包括哪两部分？索引文件包括哪两部分？索引文件有什么优缺点？索引文件有什么优缺点？2022-12-22296.3 外存分配方式外存分配方式连续连续分配分配链接链接(串联串联)分配分配索引索引分配分配常用的三种外存分配方式：常用的三种外存分配方式：2022-12-22306.3.1 连续分配连续分配连续分配连续分配：为每个文件分配：为每个文件分配相邻相邻的物理块的物理块（数据块（数据块/盘块盘块/扇区）。扇区）。分配给文件的首物理块

18、的地址被登记在它分配给文件的首物理块的地址被登记在它的目录项内。的目录项内。由连续分配方式形成的文件物理结构被称由连续分配方式形成的文件物理结构被称为为顺序文件结构顺序文件结构，相应的物理文件则称为，相应的物理文件则称为顺序文件顺序文件(Sequential File)。如。如图图6-7示。示。2022-12-2231图图6-7 磁盘空间的磁盘空间的连续分配连续分配012345678910111213141516171819202122232425262728293031文件名文件名 始址始址 块数块数count 0 2tr 14 3mail 19 6list 28 4f 6 2 文件目录文件

19、目录countftrmaillist2022-12-2232连续分配优缺点连续分配优缺点优点优点(Strongpoint)：顺序访问容易顺序访问容易顺序存取速度快顺序存取速度快缺点缺点(Disadvantage)：要求连续的存储空间。易产生外存碎片，空要求连续的存储空间。易产生外存碎片，空间利用率降低间利用率降低须事先知道文件长度。不利于文件动态增长须事先知道文件长度。不利于文件动态增长2022-12-22336.3.2 链接分配链接分配(Linked Allocation)一种一种离散分配方式离散分配方式。通过每个盘块上的链接指针，将同一个文通过每个盘块上的链接指针，将同一个文件的多个离散的

20、盘块链接成一个链表。件的多个离散的盘块链接成一个链表。可分为可分为隐式链接隐式链接和和显示链接显示链接两种方式。两种方式。1.隐式链接隐式链接：将一文件离散地存放在外存上，：将一文件离散地存放在外存上，并将下一个物理块的地址登记在分配给它并将下一个物理块的地址登记在分配给它的前一个物理块中。如的前一个物理块中。如图图6-8示。示。2022-12-2234某个链接文件示意某个链接文件示意2022-12-2235图图6-8 磁盘空间的链接式分配磁盘空间的链接式分配文件名文件名 始址始址 末址末址jeep 9 25文件目录文件目录01234567891011121314151617181920212

21、223242526272829303111016-1252022-12-2236隐式链接隐式链接优缺点优缺点优点优点：消除了外部碎片，提高利用率消除了外部碎片，提高利用率允许作业动态增长。允许作业动态增长。缺点缺点：可靠性差：一个指针出现问题，导致整个链可靠性差：一个指针出现问题，导致整个链断开断开只适合于顺序访问，不适合随机访问。只适合于顺序访问，不适合随机访问。2022-12-22372.显示链接显示链接 将文件离散地存放，并将链接各个物理块的将文件离散地存放，并将链接各个物理块的指针显式地登记在内存的一张文件分配表指针显式地登记在内存的一张文件分配表FAT(File Allocation

22、 Table)中。中。2022-12-2238显示链接显示链接特点特点优点优点：显著提高检索速度：显著提高检索速度缺点缺点：不支持大文件随机存取不支持大文件随机存取FAT需要占用较大的内存空间需要占用较大的内存空间2022-12-2239思思 考考如果硬盘是如果硬盘是16G空间，盘块大小为空间，盘块大小为4K，一个一个FAT表项占多少位？表项占多少位？FAT表需占用多少空间？表需占用多少空间？如果文件如果文件A占用硬盘的第占用硬盘的第11，12，16，14四四个盘块，试画出文件个盘块，试画出文件A中各盘块间的连接及中各盘块间的连接及FAT的情况。的情况。2022-12-22406.3.3 索引

23、分配索引分配也属于也属于离散分配离散分配方式，它在存放文件同时，方式，它在存放文件同时，为每个文件建立一个为每个文件建立一个索引表（盘块）索引表（盘块），以，以登记物理块号，并在文件目录项的地址字登记物理块号，并在文件目录项的地址字段中填上指向该索引表的指针。如段中填上指向该索引表的指针。如图图6-11示。示。2022-12-2241图图6-11索引分配方式索引分配方式012345678910111213141516171819202122232425262728293031文件名文件名 索引表地址索引表地址文件目录文件目录Jeep 19 916 11025-1-1-1192022-12-22

24、426.3.3 索引分配优缺点索引分配优缺点(Strongpoint and Disadvantage)优点优点：支持高效的随机存取支持高效的随机存取消除了外部碎片消除了外部碎片允许文件动态增长。允许文件动态增长。缺点缺点：索引表本身也要花费较多外存空间，造索引表本身也要花费较多外存空间，造成外存空间浪费。成外存空间浪费。2022-12-224301210510625435635798510510625474035635711259853607401125主索引主索引360第二级索引第二级索引磁盘空间磁盘空间2022-12-2244总结三种外存分配方式总结三种外存分配方式 连续分配连续分配 链

25、接分配链接分配 索引分配索引分配思考题：各种分配方式的优缺点是什么？思考题：各种分配方式的优缺点是什么？2022-12-2245思考题思考题 2假设磁盘转速为假设磁盘转速为20ms/圈，磁盘格式化时每个磁道圈，磁盘格式化时每个磁道被划分成被划分成10个扇区，今有个扇区，今有10个逻辑记录（每个记个逻辑记录（每个记录大小刚好与扇区大小相等）存放在同一条磁道录大小刚好与扇区大小相等）存放在同一条磁道上，处理程序每次从磁道读出一个记录要花费上，处理程序每次从磁道读出一个记录要花费4ms进行处理，先要求顺序处理这进行处理，先要求顺序处理这10个记录，若个记录，若磁头现在处于首个逻辑记录的起始位置。磁头

26、现在处于首个逻辑记录的起始位置。1.按逆时针安排按逆时针安排10个逻辑记录（磁盘顺时针方向旋个逻辑记录（磁盘顺时针方向旋转）处理程序处理完这转）处理程序处理完这10条记录花费的时间是多条记录花费的时间是多少？少？2.按优化分布重新安排这按优化分布重新安排这10条记录，计算所需要的条记录，计算所需要的时间时间2022-12-2246思考题思考题 3 假定磁盘的移动臂现在处于第假定磁盘的移动臂现在处于第8柱面，有如下柱面，有如下6个请个请求者等待访问磁盘，请你列出最省时间的响应次序：求者等待访问磁盘，请你列出最省时间的响应次序：序号序号 柱面号柱面号 磁头号磁头号 扇区号扇区号1 9 6 32 7

27、 5 63 15 20 64 9 4 45 20 9 56 7 15 22022-12-2247柱面柱面扇区扇区磁臂磁臂磁头磁头硬盘侧视图硬盘侧视图2022-12-2248知知 识识 回回 顾顾 根据外存分配方式（文件的物理结构），将根据外存分配方式（文件的物理结构），将文件分为哪几种类型，各类型有什么特点？文件分为哪几种类型，各类型有什么特点？本次授课内容本次授课内容 6.4 目录管理目录管理 重点：重点：与目录有关的概念及其相互关系与目录有关的概念及其相互关系 索引结点的引入索引结点的引入 目录结构目录结构 难点：难点：基于索引结点的目录查询技术基于索引结点的目录查询技术 6.5 文件存储

28、空间管理文件存储空间管理 6.6 文件共享和保护文件共享和保护 知识回顾：文件系统管理的对象包括？知识回顾：文件系统管理的对象包括？课课 程程 导导 入入文件（文件（6.2、6.3节）节）目录目录（6.4节）节）磁盘存储空间磁盘存储空间（6.5节）节）2022-12-22516.4 目录管理目录管理对对目录管理的要求目录管理的要求：1)能够实现能够实现“按名存取按名存取”，是目录管理，是目录管理中的最基本功能。中的最基本功能。2)提高提高对目录的对目录的检索速度检索速度。3)有利于文件有利于文件共享共享4)允许文件允许文件重名重名。引入目录的背景引入目录的背景 目录是一种数据结构，用于对系统中

29、的目录是一种数据结构，用于对系统中的大量文件进行有效的组织和管理而引入。大量文件进行有效的组织和管理而引入。本小节主要内容本小节主要内容 目录是什么目录是什么(6.4.1)文件控制块、文件目录项、目录的概念及相文件控制块、文件目录项、目录的概念及相互关系互关系 目录项的改进目录项的改进(6.4.1)引入索引结点（引入索引结点（i）目录项的组织目录项的组织目录结构目录结构(6.4.2)单级目录单级目录 两级目录两级目录 多级目录多级目录 目录查询技术目录查询技术(6.4.3)-难点难点总体介绍总体介绍与目录相关的概念及与目录相关的概念及其相互关系其相互关系 文件的属性信息形成文件的属性信息形成文

30、件控制块文件控制块(FCB,File Controller Block)文件控制块也称为文件控制块也称为文件目录项文件目录项 多个文件目录项的集合形成多个文件目录项的集合形成文件目录，简称为目录文件目录，简称为目录 文件目录以文件的形式保存在外存，所形成的文件就文件目录以文件的形式保存在外存，所形成的文件就叫叫目录文件，也简称为目录目录文件，也简称为目录。2022-12-22546.4.1 文件控制块和索引结点文件控制块和索引结点从文件管理的角度看，一个文件包括两部分：文从文件管理的角度看，一个文件包括两部分：文件主体内容和文件的各种属性信息。件主体内容和文件的各种属性信息。文件控制块文件控制

31、块(FCB)：为正确存取文件，而为文件为正确存取文件，而为文件设置的设置的用于描述和控制文件的数据结构，它包含用于描述和控制文件的数据结构，它包含用于标识、说明、管理和控制文件的各种属性信用于标识、说明、管理和控制文件的各种属性信息，息，是文件存在的标志是文件存在的标志。文件与文件控制块一一对应。文件与文件控制块一一对应。一个文件控制块也称为一个文件目录项，一个文件控制块也称为一个文件目录项，而多个而多个文件目录项（文件控制块）的有序集合构成文件文件目录项（文件控制块）的有序集合构成文件目录，简称为目录。目录，简称为目录。回顾：描述进程的数据结构？回顾：描述进程的数据结构？2022-12-22

32、551 文件控制块文件控制块(FCB)1.FCB中的信息包括：中的信息包括：基本信息：基本信息：文件名、物理位置、逻辑结构、物文件名、物理位置、逻辑结构、物理结构等理结构等 存取控制信息：存取控制信息：各种用户权限（读、写、执行）各种用户权限（读、写、执行）使用信息使用信息：创建日期与时间等：创建日期与时间等图图 6-15 MS-DOS的文件控制块的文件控制块 文文件件名名扩扩展展名名属属性性备备用用时时间间日日期期第第一一块块号号盘盘块块数数2022-12-22561)索引结点的引入索引结点的引入文件查找过程：查找目录文件（占文件查找过程：查找目录文件（占N个盘块）个盘块）例如：例如：FCB

33、为为64B，盘块大小为，盘块大小为1KB，若文件，若文件目录中有目录中有640个个FCB，求平均查找一个文件，求平均查找一个文件需要启动磁盘的次数？需要启动磁盘的次数？2 索引结点索引结点索引结点的引入（续）索引结点的引入（续）问题：全部属性信息都放入目录中会导致目录问题：全部属性信息都放入目录中会导致目录文件过大从而影响文件检索的效率。文件过大从而影响文件检索的效率。解决方法：解决方法：将文件名和文件的其他属性（或描将文件名和文件的其他属性（或描述）信息分开述）信息分开，来为目录，来为目录“瘦身瘦身”，由此引，由此引入了入了索引结点（索引结点（i-node）。2022-12-2258索引结点

34、索引结点(index node)：在在Unix/Linux系统中，系统中，采用把文件名与文件描述信息分开的方法，采用把文件名与文件描述信息分开的方法，使文件使文件描述信息单独形成一个称为索引结点描述信息单独形成一个称为索引结点的数据结构，的数据结构，简称为简称为i结点结点。此时，文件目录项仅由此时，文件目录项仅由文件名和索引节点编文件名和索引节点编号两部分号两部分构成。构成。索引结点分为索引结点分为磁盘索引结点磁盘索引结点和和内存索引结点内存索引结点。UNIX中的目录与索引结点中的目录与索引结点文件名文件名 i 结点编号结点编号a1b1除文件名以外的文除文件名以外的文件基本信息（文件件基本信息

35、（文件主、类型、访问权主、类型、访问权限、长度、存取时限、长度、存取时间等间等）链接计数链接计数count索引表（记录文件索引表（记录文件存放的物理位置存放的物理位置）：）：i.addr(0)i.addr(12)目录目录 i 结点结点modeowners(2)time stamps(3)sizeblock counti.addr(0)i.addr(1)direct blockssingle indirectdouble indirecttriple indirectdatadatadatadatadatadatadatadatadatadataUNIX中的中的 i 结点（结点（i-node）由

36、两部分组成！由两部分组成！文文件件基基本本描描述述信信息息索索引引表表i.addr(0)i.addr(9)为为一级索引一级索引i.addr(10)为为二级索引二级索引i.addr(11)为为三级索引三级索引i.addr(12)为为四级索引四级索引2022-12-22612)磁盘索引结点磁盘索引结点存放在磁盘上的索引结点，每个文件有唯一的磁盘索引结点。存放在磁盘上的索引结点，每个文件有唯一的磁盘索引结点。(1)文件主标识符文件主标识符(2)文件类型文件类型(3)文件存取权限文件存取权限(4)文件物理地址文件物理地址(5)文件长度文件长度(6)文件连接计数文件连接计数(7)文件存取时间文件存取时间

37、 2022-12-22623)内存索引结点内存索引结点是存放在内存中的索引结点。是存放在内存中的索引结点。当文件被打开时，要将磁盘索当文件被打开时，要将磁盘索引结点复制到内存索引结点中引结点复制到内存索引结点中，此外还增加了一下其他信息：，此外还增加了一下其他信息：(1)索引结点编号。用于标识内存索引结点。索引结点编号。用于标识内存索引结点。(2)状态。指示状态。指示i结点是否上锁或被修改（结点是否上锁或被修改（便于回存便于回存）(3)访问计数。访问计数。每当有一进程要访问此每当有一进程要访问此i结点时，结点时，将将该访问计数加该访问计数加1，访问完再减访问完再减1（用于文件共享用于文件共享）

38、。）。(4)文件所属文件系统的逻辑设备号。文件所属文件系统的逻辑设备号。(5)链接指针。链接指针。设置有分别指向空闲链表和散列队列设置有分别指向空闲链表和散列队列的指针。的指针。2022-12-22636.4.2 目录结构目录结构目录结构的组织关系到文件的存取速目录结构的组织关系到文件的存取速度、文件的共享、文件的保护。度、文件的共享、文件的保护。常用的目录结构：常用的目录结构：单级单级目录结构目录结构 两级两级目录结构目录结构 多级多级目录结构目录结构2022-12-22641.单级目录结构单级目录结构在整个文件系统中只建立一张目录表在整个文件系统中只建立一张目录表 优点优点：管理和实现简单

39、，能够按名存取；：管理和实现简单，能够按名存取；缺点缺点：不能满足对目录管理的要求，如查找：不能满足对目录管理的要求，如查找速度慢，速度慢，不允许重名，不便共享不允许重名，不便共享。文件名文件名物理地址物理地址文件说明文件说明状态位状态位File1File22022-12-22652.两级目录结构两级目录结构 由主文件目录由主文件目录MFD和用户文件目录和用户文件目录UFD两级两级目录构成。如目录构成。如图图6-18示。示。MFD中中的目录项对应着不同的用户，的目录项对应着不同的用户，UFD的的目录项则对应着特定用户拥有的所有文件目录项则对应着特定用户拥有的所有文件优点优点：提高了检索速度提高

40、了检索速度允许不同目录文件重名允许不同目录文件重名不同用户可使用不同的文件名访问系统中同一文件。不同用户可使用不同的文件名访问系统中同一文件。2022-12-2266图图6-18两级目录结构两级目录结构2022-12-22673.多级目录结构多级目录结构 为提高目录检索速度和文件系统的性能，对为提高目录检索速度和文件系统的性能，对大型文件系统，常采用大型文件系统，常采用三级三级或或三级以上三级以上的目的目录结构，即录结构，即多级目录结构多级目录结构，又称，又称树型树型目录结目录结构。如图构。如图619示（示（方块表示目录文件，圆圈表方块表示目录文件，圆圈表示普通文件示普通文件）。）。这种多级目

41、录结构如同一棵倒置的树，主目这种多级目录结构如同一棵倒置的树，主目录就是树根，称为录就是树根，称为根目录根目录。每一个树枝结点就是一个每一个树枝结点就是一个子目录子目录，每一片树，每一片树叶则对应的是一个文件目录项，描述的是一叶则对应的是一个文件目录项，描述的是一个文件。个文件。2022-12-2268图图619 多级目录结构多级目录结构根目录下有ABC三个子目录，A子目录下有A子目录和B、D两个文件，A子目录下又包含A和C两个文件文件路径：/A/A/A/A/A/A/A/A/A多级目录结构中的相关概念多级目录结构中的相关概念 绝对路径：绝对路径：从根目录从根目录/出发出发到达特定子目录或到达特

42、定子目录或文件所经过的路径文件所经过的路径 相对路径：从相对路径：从当前目录出发当前目录出发到达特定子目录到达特定子目录或文件所经过的路径或文件所经过的路径 当前目录：为缩短查找范围，可以为每个进当前目录：为缩短查找范围，可以为每个进程设置一个当前的工作目录，使得需要查找程设置一个当前的工作目录，使得需要查找时只从该工作目录出发而不用从根目录出发。时只从该工作目录出发而不用从根目录出发。常用常用”.”表示当前目录，而用表示当前目录，而用“.”表示当前目表示当前目录的父目录录的父目录。2022-12-2270多级目录结构的优点多级目录结构的优点目录检索速度快目录检索速度快允许重名（不同目录）允许

43、重名（不同目录）分类管理分类管理便于共享便于共享6.4.3 目录查询技术目录查询技术 主要介绍线性检索法，也称作顺序检索法主要介绍线性检索法，也称作顺序检索法 基于索引结点的顺序检索法，在查找某一基于索引结点的顺序检索法，在查找某一级目录时的过程如下：级目录时的过程如下：顺序查找当前目录中的目录项，得到要找文件顺序查找当前目录中的目录项，得到要找文件的索引结点编号的索引结点编号 用编号查找索引结点表，得到要找用编号查找索引结点表，得到要找(目录目录)文件文件的物理地址（盘块号）的物理地址（盘块号）读入要找的读入要找的(目录目录)文件文件 如果还有下一级，上述过程交替进行，直到找如果还有下一级，

44、上述过程交替进行，直到找到所需文件或提示找不到所需文件为止。到所需文件或提示找不到所需文件为止。2022-12-2272例如基于索引节点：查找例如基于索引节点：查找/usrusr/ast/mbox/ast/mbox文件名索引节点.1.1bin4dev7lib14etc9usrusr6 6tmp8根目录表根目录表(1)在根目录表中查找在根目录表中查找usr目录目录索引节点文件类型属性物理地址1d6 6d d13213226d49660f200索引节点表（外存）索引节点表（外存）(2)读入读入6号索引节点到号索引节点到内存内存6.4.3 目录查询技术目录查询技术文件名索引节点.6.1are19jk

45、l30hui51astast2626lkm45usr目录文件目录文件索引节点文件类型属性物理地址1d6d1322626d d49649660f200索引节点表索引节点表(3)从132号盘块读入usr目录文件，查找ast(4)读入读入26号号索引索引节点节点到到内存内存例如基于索引节点：查找例如基于索引节点：查找/usrusr/astast/mbox/mbox6.4.3 目录查询技术目录查询技术例如基于索引节点：查找例如基于索引节点：查找/usr/ast/usr/ast/mboxmbox文件名索引节点.26.6gran64book92mboxmbox6060mini81scr17ast目录文件索

46、引节点文件类型属性物理地址1d6d13226d4966060f f200200索引节点表(5)从496号盘块读入ast目录文件，查找mbox(6)读入60号索引节点到内存(7)从从200号盘块读入号盘块读入mbox文件，查找结束文件，查找结束6.4.3 目录查询技术目录查询技术2022-12-2275小结小结 目录相关概念及相互关系目录相关概念及相互关系(6.4.1)FCB、文件目录项、目录、文件目录项、目录 目录项的改进目录项的改进(6.4.1)引入索引结点（引入索引结点（i-node）目录项的组织目录项的组织目录结目录结构构(6.4.2)目录查询技术目录查询技术(6.4.3)本次授课内容本

47、次授课内容 6.4 目录管理目录管理 6.5 文件存储空间管理文件存储空间管理 重点：位示图及其分配和回收过程重点：位示图及其分配和回收过程 6.6 文件共享和保护文件共享和保护2022-12-22776.5文件存储空间的管理文件存储空间的管理v 为对文件存储空间进行管理，常用以下几为对文件存储空间进行管理，常用以下几种方法进行：种方法进行：1.空闲表法空闲表法2.空闲链表法空闲链表法3.位示图法（重点）位示图法（重点）4.成组链接法（不做要求）成组链接法（不做要求）注意：前两种组织方式类似的有：（1）PCB的组织（2）内存管理的动态分区分配中空闲块的组织2022-12-22786.5.1 空

48、闲表法和空闲链表法空闲表法和空闲链表法1.空闲表法空闲表法：属于：属于连续分配连续分配方式，为每个文件分配方式，为每个文件分配一块连续空间。系统一块连续空间。系统为外存上的所有空闲区建立为外存上的所有空闲区建立一张空闲表，每个空闲区对应一个空闲表项一张空闲表，每个空闲区对应一个空闲表项，每，每个表项包括表项序号、空闲区的第一个盘块号和个表项包括表项序号、空闲区的第一个盘块号和空闲区的盘块数。空闲区的盘块数。2.分配算法：可采用首次适应算法、循环首次、最分配算法：可采用首次适应算法、循环首次、最佳或最差适应算法。佳或最差适应算法。优点优点：空闲区分配与回收容易。：空闲区分配与回收容易。缺点缺点：

49、要求对外存空间连续分配，可能会产生外存碎：要求对外存空间连续分配，可能会产生外存碎片。此外空闲表也会浪费很大存储空间。片。此外空闲表也会浪费很大存储空间。2022-12-2279序号序号第一空闲盘块号第一空闲盘块号空闲盘块数空闲盘块数1242933155图图6-21空闲盘块表空闲盘块表2022-12-22802 空闲链表法空闲链表法：将文件存储空间中的所：将文件存储空间中的所 有空闲区拉成一条空闲链表。有空闲区拉成一条空闲链表。v 根据构成链的基本元素是根据构成链的基本元素是空闲盘块空闲盘块或或空闲盘区空闲盘区，再分为，再分为空闲盘块链空闲盘块链或或空闲空闲盘区链盘区链。v 分配算法分配算法:

50、常采用首次适应算法常采用首次适应算法2022-12-22816.5.2 位示图法位示图法位位示图法：利用示图法：利用二进制二进制的的一位一位来表示文来表示文件存储空间中的一个盘块的使用情况。件存储空间中的一个盘块的使用情况。其值为其值为0表示空闲，为表示空闲，为1表示分配，这样表示分配，这样由所有盘块所对应的二进制位构成一个由所有盘块所对应的二进制位构成一个集合，称为位示图。集合，称为位示图。2022-12-22821.位示图位示图 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 161234511000111001001100001111110000111111000