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

2023/12/51第6章文件管理6.1文件与文件系统6.2文件的逻辑结构6.3外存分配方式6.4目录管理6.5文件存储空间的管理6.6文件的共享与保护6.7数据一致性控制

开始2023/12/52§6.1文件和文件系统OS采用文件系统来组织管理大量的文件。在文件系统中，通常把数据分为数据项、记录和文件三级。2023/12/536.1.1数据项、记录和文件1.数据项:最低级的数据组织形式基本数据项：原子数据，最小逻辑单位，即数据元素、字段。如学号、姓名组合数据项：由若干个基本数据项组成，简称组项。如工资（基本工资、奖励工资）数据项的型和值：型指数据项名字和类型，实体在数据项上的数据则称为值。2023/12/542.记录：一组相关数据项的集合，用于描述一个对象在某方面的属性。关键字：唯一能够标示一条记录的数据项。2023/12/553.文件文件是指由创建者定义、具有文件名的一组相关元素的集合，可分为有结构文件和无结构文件两种。文件还有些具体属性：文件类型文件长度文件物理位置文件的建立时间2023/12/566.1.2文件类型和文件系统模型1.文件类型按用途分类：系统文件用户文件库文件按文件中数据形式分类：源文件目标文件可执行文件2023/12/57按存取控制属性分类：执行文件只读文件读写文件2023/12/582.文件系统模型模型分为三个层次，如图6-2示：对象及属性（文件、目录、磁盘存储空间）对对象操纵和管理的软件集合文件系统的接口（命令接口、程序接口）文件系统接口对对象操纵和管理的软件集合对象及属性用户(程序)图6-22023/12/596.1.3文件操作1.最基本的文件操作创建文件：分配外存空间，创建新的目录项删除文件：删除目录项，收回空间读文件：查找目录找到文件的外存位置写文件：通过目录找到文件的目录项，用目录中的写指针进行写操作截断文件设置文件的读/写位置2023/12/510当前OS所提供的大多数文件操作过程都是这样两步：检索文件目录找到文件的属性和在外存的位置；对文件实施相应的操作。所谓“打开”文件是指将文件的属性从外存拷贝到内存打开文件表的一个表项中，并将该表项的编号返回给用户。2.文件的“打开”和“关闭”操作2023/12/511§6.2文件的逻辑结构计算机文件的两种结构：文件逻辑结构(FileLogicalStructure)：从用户角度出发所观察到的文件组织形式，是用户可以直接处理的数据及其结构，独立于物理特性，又称为文件组织(FileOrganization)。文件物理结构(FilePhysicalStructure)：指文件在外存上的存储组织形式，又称为文件的存储结构。2023/12/512文件逻辑结构对文件逻辑结构的基本要求：提高检索记录的速度便于修改记录降低文件的存储费用：文件占用的空间，不要求连续的大空间。2023/12/5136.2.1文件逻辑结构的类型1有结构文件：也称为记录式文件，组成文件的数据项单位为记录。根据用户和系统管理的需要，可采用多种方式组织记录形成顺序文件、索引文件和索引顺序文件文件逻辑结构可分为两类：2023/12/514顺序文件：一系列记录按照某种顺序排列所形成的文件。其中的记录通常是定长的。索引文件：当记录为可变长时，通常为之建立一张索引表，并为每一个记录设置一个表项，以加快检索记录的速度。索引顺序文件：为文件建立一张索引表，为每一组记录中的第一个记录设置一个表项。2023/12/5152无结构文件：也称流式文件，组成文件的数据单位为ASCII字符，如源程序、可执行文件等。2023/12/5166.2.2顺序文件1.顺序文件分类顺序无序文件（串结构）：各记录之间的顺序与关键字无关，由输入的时间决定先后顺序。顺序有序文件（顺序结构）：所有记录安关键字排序注意：

为提高检索效率，常将顺序文件组织成顺序有序文件。2023/12/5172.对顺序有序文件的读/写操作顺序文件中的记录可以是定长也可以是变长的对于定长记录的顺序文件，如果已知当前记录的逻辑地址，便很容易确定下一个记录的逻辑地址。读写文件时设置一个读指针Rptr和一个写指针Wptr，每读写一条记录分别使Rptr+L和Wptr+L。对于变长记录则指针应加Li+1,如下图2023/12/5182023/12/519对于定长记录文件，如果要查找第i个记录，

可直接根据下式计算来获得第i个记录相对于第一个记录首址的地址：Ai=i×L可变长度记录的文件，要查找其第i个记录，6.2.3索引文件2023/12/520当记录为可变长度时，通常采用索引文件方式。为每个文件建立一张索引表，并将主文件的每个记录的记录号、长度和逻辑地址记录在索引表中。优点：因将可变长的记录的索引转化为定长的记录项的索引，故方便实现直接存取。缺点：每个文件有一索引表，存储费用高。2023/12/5212023/12/522注意索引文件

索引文件由主文件和索引表构成。

①主文件：文件本身。②索引表：在文件本身外建立的一张表，由若干索引项组成。索引表必须按主关键字有序排列。2023/12/523索引文件的存储

1．索引文件的存储

索引文件在存储器上分为两个区：索引区和数据区。索引区存放索引表，数据区存放主文件。

2023/12/5242建立索引文件的过程：（1）按输入记录的先后次序建立数据区和索引表。其中索引表中关键字是无序的

（2）待全部记录输入完毕后对索引表进行排序，排序后的索引表和主文件一起就形成了索引文件2023/12/5256.2.4索引顺序文件是综合顺序和索引两种文件构成方式的优点，先检索索引表，找到所在记录组中第一个记录表项，并找到第一个记录在主文件中位置，然后再顺序查找所需记录。如图6-5示：优点：因只为每组记录的首记录设置一索引表项，因此能有效减少索引表所占的空间。2023/12/526图6-5索引顺序文件…………ChenLin…………BaoRong…………AnKangAnQi其它属性姓名…………ChenLinBaoRongAnQi逻辑地址键索引表2023/12/527

注意：

①通常将索引非顺序文件简称为索引文件。

②索引非顺序文件主文件无序，顺序存取将会频繁地引起磁头移动，适合于随机存取，不适合于顺序存取。

③索引顺序文件的主文件是有序的，适合于随机存取、顺序存取。

④索引顺序文件的索引是稀疏索引。索引占用空间较少，是最常用的一种文件组织。

2023/12/528回顾什么是顺序文件、索引文件、索引顺序文件？索引文件包括哪两部分？索引文件有什么优缺点？2023/12/5296.3外存分配方式连续分配链接(串联)分配索引分配常用的三种外存分配方式：2023/12/5306.3.1连续分配连续分配：为每个文件分配相邻的物理块（数据块/盘块/扇区）。分配给文件的首物理块的地址被登记在它的目录项内。由连续分配方式形成的文件物理结构被称为顺序文件结构，相应的物理文件则称为顺序文件(SequentialFile)。如图6-7示。2023/12/531图6-7磁盘空间的连续分配012345678910111213141516171819202122232425262728293031文件名始址块数count02tr143mail196list284f62文件目录countftrmaillist2023/12/532连续分配优缺点优点(Strongpoint)

：顺序访问容易顺序存取速度快缺点(Disadvantage)：要求连续的存储空间。易产生外存碎片，空间利用率降低须事先知道文件长度。不利于文件动态增长2023/12/5336.3.2链接分配

(LinkedAllocation)一种离散分配方式。通过每个盘块上的链接指针，将同一个文件的多个离散的盘块链接成一个链表。可分为隐式链接和显示链接两种方式。1.隐式链接：将一文件离散地存放在外存上，并将下一个物理块的地址登记在分配给它的前一个物理块中。如图6-8示。2023/12/534某个链接文件示意2023/12/535图6-8磁盘空间的链接式分配文件名始址末址jeep925文件目录01234567891011121314151617181920212223242526272829303111016-1252023/12/536隐式链接优缺点优点：消除了外部碎片，提高利用率允许作业动态增长。缺点：可靠性差：一个指针出现问题，导致整个链断开只适合于顺序访问，不适合随机访问。2023/12/5372.显示链接将文件离散地存放，并将链接各个物理块的指针显式地登记在内存的一张文件分配表FAT(FileAllocationTable)中。2023/12/538显示链接特点优点：显著提高检索速度缺点：不支持大文件随机存取FAT需要占用较大的内存空间2023/12/539思考如果硬盘是16G空间，盘块大小为4K，一个FAT表项占多少位？FAT表需占用多少空间？如果文件A占用硬盘的第11，12，16，14四个盘块，试画出文件A中各盘块间的连接及FAT的情况。2023/12/5406.3.3索引分配也属于离散分配方式，它在存放文件同时，为每个文件建立一个索引表（盘块），以登记物理块号，并在文件目录项的地址字段中填上指向该索引表的指针。如图6-11示。2023/12/541图6-11索引分配方式012345678910111213141516171819202122232425262728293031文件名索引表地址文件目录Jeep1991611025-1-1-1192023/12/5426.3.3索引分配优缺点

(StrongpointandDisadvantage)优点：支持高效的随机存取消除了外部碎片允许文件动态增长。缺点：索引表本身也要花费较多外存空间，造成外存空间浪费。2023/12/54301210510625435635798510510625474035635711259853607401125主索引360第二级索引磁盘空间2023/12/544总结三种外存分配方式连续分配链接分配索引分配思考题：各种分配方式的优缺点是什么？2023/12/545思考题2假设磁盘转速为20ms/圈，磁盘格式化时每个磁道被划分成10个扇区，今有10个逻辑记录（每个记录大小刚好与扇区大小相等）存放在同一条磁道上，处理程序每次从磁道读出一个记录要花费4ms进行处理，先要求顺序处理这10个记录，若磁头现在处于首个逻辑记录的起始位置。按逆时针安排10个逻辑记录（磁盘顺时针方向旋转）处理程序处理完这10条记录花费的时间是多少？按优化分布重新安排这10条记录，计算所需要的时间2023/12/546思考题3假定磁盘的移动臂现在处于第8柱面，有如下6个请求者等待访问磁盘，请你列出最省时间的响应次序：

序号

柱面号

磁头号

扇区号

1

9

6

3

2

7

5

6

3

15

20

6

4

9

4

4

5

20

9

5

6

7

15

2

2023/12/547柱面扇区磁臂磁头硬盘侧视图2023/12/548知识回顾根据外存分配方式（文件的物理结构），将文件分为哪几种类型，各类型有什么特点？本次授课内容6.4目录管理重点：与目录有关的概念及其相互关系索引结点的引入目录结构难点：基于索引结点的目录查询技术6.5文件存储空间管理6.6文件共享和保护知识回顾：文件系统管理的对象包括？课程导入文件（6.2、6.3节）目录（6.4节）磁盘存储空间（6.5节）2023/12/5516.4目录管理对目录管理的要求：能够实现“按名存取”，是目录管理中的最基本功能。提高对目录的检索速度。有利于文件共享允许文件重名。引入目录的背景目录是一种数据结构，用于对系统中的大量文件进行有效的组织和管理而引入。本小节主要内容目录是什么(6.4.1)文件控制块、文件目录项、目录的概念及相互关系目录项的改进(6.4.1)引入索引结点（i）目录项的组织——目录结构(6.4.2)单级目录两级目录多级目录目录查询技术(6.4.3)---难点总体介绍——与目录相关的概念及其相互关系文件的属性信息形成文件控制块(FCB,FileControllerBlock)文件控制块也称为文件目录项多个文件目录项的集合形成文件目录，简称为目录文件目录以文件的形式保存在外存，所形成的文件就叫目录文件，也简称为目录。2023/12/5546.4.1文件控制块和索引结点从文件管理的角度看，一个文件包括两部分：文件主体内容和文件的各种属性信息。文件控制块(FCB)：为正确存取文件，而为文件设置的用于描述和控制文件的数据结构，它包含用于标识、说明、管理和控制文件的各种属性信息，是文件存在的标志。文件与文件控制块一一对应。一个文件控制块也称为一个文件目录项，而多个文件目录项（文件控制块）的有序集合构成文件目录，简称为目录。回顾：描述进程的数据结构？2023/12/5551文件控制块(FCB)1.FCB中的信息包括：基本信息：文件名、物理位置、逻辑结构、物理结构等存取控制信息：各种用户权限（读、写、执行）使用信息：创建日期与时间等图6-15MS-DOS的文件控制块文件名扩展名属性备用时间日期第一块号盘块数2023/12/556索引结点的引入文件查找过程：查找目录文件（占N个盘块）例如：FCB为64B，盘块大小为1KB，若文件目录中有640个FCB，求平均查找一个文件需要启动磁盘的次数？2索引结点索引结点的引入（续）问题：全部属性信息都放入目录中会导致目录文件过大从而影响文件检索的效率。解决方法：将文件名和文件的其他属性（或描述）信息分开，来为目录“瘦身”，由此引入了索引结点（i-node）。2023/12/558索引结点(indexnode)：在Unix/Linux系统中，采用把文件名与文件描述信息分开的方法，使文件描述信息单独形成一个称为索引结点的数据结构，简称为i结点。此时，文件目录项仅由文件名和索引节点编号两部分构成。索引结点分为磁盘索引结点和内存索引结点。UNIX中的目录与索引结点文件名

i结点编号a1b1除文件名以外的文件基本信息（文件主、类型、访问权限、长度、存取时间等）链接计数count索引表（记录文件存放的物理位置）：i.addr(0)~i.addr(12)目录

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

2023/12/5623)内存索引结点是存放在内存中的索引结点。当文件被打开时，要将磁盘索引结点复制到内存索引结点中，此外还增加了一下其他信息：

(1)索引结点编号。用于标识内存索引结点。(2)状态。指示i结点是否上锁或被修改（便于回存）(3)访问计数。每当有一进程要访问此i结点时，将该访问计数加1，访问完再减1（用于文件共享）。(4)文件所属文件系统的逻辑设备号。(5)链接指针。设置有分别指向空闲链表和散列队列的指针。

2023/12/5636.4.2目录结构目录结构的组织关系到文件的存取速度、文件的共享、文件的保护。常用的目录结构：单级目录结构两级目录结构多级目录结构2023/12/5641.单级目录结构在整个文件系统中只建立一张目录表优点：管理和实现简单，能够按名存取；缺点：不能满足对目录管理的要求，如查找速度慢，不允许重名，不便共享。文件名物理地址文件说明状态位File1File2……2023/12/5652.两级目录结构由主文件目录MFD和用户文件目录UFD两级目录构成。如图6-18示。MFD中的目录项对应着不同的用户，UFD的目录项则对应着特定用户拥有的所有文件优点：提高了检索速度允许不同目录文件重名不同用户可使用不同的文件名访问系统中同一文件。2023/12/566图6-18两级目录结构2023/12/5673.多级目录结构为提高目录检索速度和文件系统的性能，对大型文件系统，常采用三级或三级以上的目录结构，即多级目录结构，又称树型目录结构。如图6－19示（方块表示目录文件，圆圈表示普通文件）。这种多级目录结构如同一棵倒置的树，主目录就是树根，称为根目录。每一个树枝结点就是一个子目录，每一片树叶则对应的是一个文件目录项，描述的是一个文件。2023/12/568图6－19多级目录结构根目录下有ABC三个子目录，A子目录下有A子目录和B、D两个文件，A子目录下又包含A和C两个文件文件路径：/A/A/A//A/A/A/A/A/A多级目录结构中的相关概念绝对路径：从根目录/出发到达特定子目录或文件所经过的路径相对路径：从当前目录出发到达特定子目录或文件所经过的路径当前目录：为缩短查找范围，可以为每个进程设置一个当前的工作目录，使得需要查找时只从该工作目录出发而不用从根目录出发。常用”.”表示当前目录，而用“..”表示当前目录的父目录。2023/12/570多级目录结构的优点目录检索速度快允许重名（不同目录）分类管理便于共享6.4.3目录查询技术主要介绍线性检索法，也称作顺序检索法基于索引结点的顺序检索法，在查找某一级目录时的过程如下：顺序查找当前目录中的目录项，得到要找文件的索引结点编号用编号查找索引结点表，得到要找(目录)文件的物理地址（盘块号）读入要找的(目录)文件如果还有下一级，上述过程交替进行，直到找到所需文件或提示找不到所需文件为止。2023/12/572例如基于索引节点：查找/usr/ast/mbox文件名索引节点.1..1bin4dev7lib14etc9usr6tmp8根目录表(1)在根目录表中查找usr目录索引节点文件类型属性物理地址1d…………6d…132………26d496…………60f…200…………索引节点表（外存）(2)读入6号索引节点到内存6.4.3目录查询技术文件名索引节点.6..1are19jkl30hui51ast26lkm45usr目录文件索引节点文件类型属性物理地址1d…………6d…132………26d…496…………60f…200…………索引节点表(3)

从132号盘块读入usr目录文件，查找ast(4)

读入26号索引节点到内存例如基于索引节点：查找/usr/ast/mbox6.4.3目录查询技术例如基于索引节点：查找/usr/ast/mbox文件名索引节点.26..6gran64book92mbox60mini81scr17ast目录文件索引节点文件类型属性物理地址1d………………6d…132…………26d…496…………60f…200…………索引节点表(5)

从496号盘块读入ast目录文件，查找mbox(6)

读入60号索引节点到内存(7)从200号盘块读入mbox文件，查找结束6.4.3目录查询技术2023/12/575小结目录相关概念及相互关系(6.4.1)FCB、文件目录项、目录目录项的改进(6.4.1)引入索引结点（i-node）目录项的组织——目录结构(6.4.2)目录查询技术(6.4.3)本次授课内容6.4目录管理6.5文件存储空间管理重点：位示图及其分配和回收过程6.6文件共享和保护2023/12/5776.5文件存储空间的管理为对文件存储空间进行管理，常用以下几种方法进行：空闲表法空闲链表法位示图法（重点）成组链接法（不做要求）注意：前两种组织方式类似的有：（1）PCB的组织（2）内存管理的动态分区分配中空闲块的组织2023/12/5786.5.1空闲表法和空闲链表法空闲表法：属于连续分配方式，为每个文件分配一块连续空间。系统为外存上的所有空闲区建立一张空闲表，每个空闲区对应一个空闲表项，每个表项包括表项序号、空闲区的第一个盘块号和空闲区的盘块数。分配算法：可采用首次适应算法、循环首次、最佳或最差适应算法。优点：空闲区分配与回收容易。缺点：要求对外存空间连续分配，可能会产生外存碎片。此外空闲表也会浪费很大存储空间。2023/12/579序号第一空闲盘块号空闲盘块数1242933155………图6-21空闲盘块表2023/12/5802空闲链表法：将文件存储空间中的所有空闲区拉成一条空闲链表。根据构成链的基本元素是空闲盘块或空闲盘区，再分为空闲盘块链或空闲盘区链。分配算法:常采用首次适应算法2023/12/5816.5.2位示图法位示图法：利用二进制的一位来表示文件存储空间中的一个盘块的使用情况。其值为0表示空闲，为1表示分配，这样由所有盘块所对应的二进制位构成一个集合，称为位示图。2023/12/5821.位示图1234567891011121314151612345…1100011100100110000111111000011111100011111100002023/12/5832.盘块的分配

(1)顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。(2)将所找到的一个或一组二进制位，转换成与之相应的盘块号。假定找到的其值为“0”的二进制位，位于位示图的第i行、第j列，则其相应的盘块号应按下式计算：

b=n(i-1)+j

式中，

n代表每行的位数。(3)修改位示图，

令map［i,j］=1。2023/12/5843.盘块的回收

(1)将回收盘块的盘块号b转换成位示图中的行号和列号。

转换公式为：i=(b-1)DIVn+1

（DIV相当于”/”）j=(b-1)MODn+1

（MOD相当于”%”）(2)修改位示图。

令map［i,j］=0。

练习某系统的磁盘文件空间共有500块，若用字长为32位的位示图管理盘空间，试问：（1）位示图需要多少个字？（2）第i字第j位对应的块号是多少？（3）给出申请/归还一块的工作流程。本次授课内容6.4目录管理6.5文件存储空间管理6.6文件共享和保护文件共享重点：基于索引结点的共享基于符号链接的共享文件保护重点：磁盘容错技术2023/12/5876.6文件共享与文件保护文件共享:指允许多个用户使用同一文件。文件保护：指防止文件被有意或无意地破坏。文件保密：指防止文件未经授权而被非法窃取。2023/12/5886.6.1基于索引结点的共享方式在树型结构的目录中，当有两个（或多个）用户（进程）要共享一个子目录或文件时，必须将文件或子目录连接到用户的目录中，才能方便地找到该文件。/homeetcbinuserauserbusercABBACusera和userb共享同一个文件AB，此时的目录结构已经不是树形了，而是带有环路文件共享可能出现的问题/homeetcbinuserauserbusercABBACusera和userb共享AB文件名首地址长度其他属性AAB100…Usera文件目录Userb文件目录AB文件名首地址长度其他属性B10012…但是存在问题！！如果usera修改文件长度，则…1215不一致！！说明一个用户对文件的改动对其他用户不可见6.6.1文件的共享1．基于索引结点的共享方式/homeetcbinuserauserbABBA文件名索引节点AAB60Usera文件目录Userb文件目录AB文件名索引节点B60索引节点文件类型属性物理地址1d…………6d…132………26d496…………60fcount=2200…………索引节点表（外存）基于索引节点，文件的改动对所有用户可见2023/12/591如何删除？存在什么问题？基于索引结点的共享方式存在的问题6.6.1文件的共享图6-25进程B链接前后的情况缺点:（1）当文件主C不需要该文件，如果删除文件后，索引结点也被删除，导致B目录指针悬空，B操作文件会出错（2）如果文件主C等待B操作完后才删除，则期间的记账收费会由C承担2023/12/5946.6.2利用符号链实现文件共享为使userb能共享usera的一个文件AB，可以由系统创建一个LINK类型的新文件，取名为Filea，将Filea放入userb的目录中，以实现userb的目录与文件AB的连接。而新建的Filea文件中仅包含共享文件AB的路径。这样的链接方法被称为符号链接。符号链接其实就是Win