文件管理课件

第六章

文件管理06文件管理6.1文件和文件系统6.2文件的逻辑结构6.3外存分配方式6.4目录管理6.5文件存储空间的管理6.6文件共享与文件保护6.7数据一致性控制第六章文件管理06文件管理引言对大多数用户来说，文件是操作系统中最为常见的对象，对文件的操作也是操作系统中最为常用的操作之一。06文件管理文件管理系统就是操作系统中实现文件统一管理的一组软件和相关数据的集合，它是专门负责管理和存取文件信息的软件机构，简称文件系统。文件系统

实现“按名存取”；提供方便的操作和统一的调用接口，屏蔽底层细节。用户

组织、分配、回收文件的存储空间；负责文件的存储、检索、共享和保护。系统06文件管理6.1文件和文件系统6.1.1文件、记录、数据项(说明包含关系)

数据项基本数据项：可命名的最小逻辑单位/字段组合数据项：由若干基本数据项组成基本数据项的类型和数据记录一组相关数据项的集合关键字：能唯一地标识出记录的基本/组合数据项06文件管理二、基本概念文件(file)sort.c定义：是记录在外存上的，具有文件名的，在逻辑上具有完整意义的一组相关信息项的集合。信息项：是构成文件内容的基本单位，可以是一个字符，也可以是一个记录。磁带磁盘光盘优盘从用户的角度看，文件是逻辑外存的最小分配单元，即信息(数据)只能以文件的形式写入外存。06文件管理文件的组成部分sort.c文件目录

文件名称文件类型文件存储位置文件大小访问权限时间、日期、用户标识

……文件体：文件真实的内容。文件说明(属性)：操作系统为了管理文件所用到的信息。06文件管理文件、记录和数据项之间的层次关系06文件管理6.1.2文件类型和文件系统模型文件类型1、按用途分类系统文件用户文件库文件2、按文件中的数据形式分类源文件目标文件可执行文件3、按文件中的存取控制分类只执行文件只读文件可读写文件4、按组织形式和处理方式分类普通文件目录文件特殊文件06文件管理6.1.3文件操作文件的基本操作：创建文件：外存空间

增加目录项

记录文件名及外存地址

(2)删除文件:目录项清空

回收存储空间(3)读文件：给出(文件名和读入的内存地址)

查找（目录项）(4)写文件：给出(文件名和内存源地址)

利用目录中的写指针进行写操作(5)截断文件：需要更新时(6)设置文件的读/写位置。随机存取

从所设置的位置开始读取06文件管理打开/关闭操作打开：将文件的属性从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号（索引)返回给用户。关闭：当用户不再需要对文件实施操作时，删除打开文件表的表目。打开文件表表目1表目2表目3….对文件的操作步骤：(1)检索文件目录找到指定文件的属性及其在外存的位置(2)进行操作。06文件管理文件系统模型概念：文件和对文件进行操纵和管理的软件集合。三个层：文件(对象及属性)

文件操作

文件访问接口

文件系统接口对对象操纵和管理的软件集合对象及其属性用户（程序）对象：文件、目录、磁盘存储空间06文件管理一、文件系统管理的对象及属性（1）文件（2）目录：例：目录项用于方便用户对文件的存取和检索。（3）物理存储空间的管理，好坏将影响访问速度。06文件管理文件系统模型二、对对象操纵和管理的软件集合：（1）对文件存储空间的管理（2）对文件目录的管理（3）文件的地址转换机制（4）文件的读写管理、文件共享和保护功能三、文件系统接口命令接口：程序接口：06文件管理6.2文件逻辑结构逻辑结构：用户所能观察和访问到的文件的数据结构组织，独立于物理特性，容易检索和修改。又称为文件组织。逻辑结构的要求：提高检索速度、便于修改、降低存储费用。物理结构：文件在外存上的组织形式。无论是逻辑还是物理结构，都会影响到文件的检索速度06文件管理6.2.1逻辑结构类型一、无结构文件：流式文件源程序、可执行文件、库函数等，以字节为单位，利用读/写指针进行下一个字符的访问。二、有结构文件：记录式文件记录的长度分为（1）定长记录（2）变长记录定长记录

变长记录字符流06文件管理根据用户和管理上的需要，对记录的组织方式不同：文件可分为（1）顺序文件：按照某种顺序排列所形成的文件，通常是定长记录（2）索引文件：变长记录，为该文件建立一个索引表，为文件中的每个记录设置一个表项。（3）索引顺序文件：顺序组织多个组，每组记录中的第一个记录设置一索引项。06文件管理6.2.2顺序文件一、逻辑记录的排序（1）按记录录入的时间排:串结构。（2）按关键字排序：顺序结构。后一种情况更有利于提高查询速度。如可用折半查找法等。二、对顺序文件的读/写操作定长记录顺序文件：例：顺序读易于定位，甚至可随机读取。变长记录：不易定位，只能顺序读取。06文件管理06文件管理6.2.3索引文件由变长记录组成的顺序文件不容易直接存取，因此，为其建立一有序的索引表，对索引采用折半查找，速度更快。特点：提高了速度，增加了存储开销——放索引文件。增、删记录时，对索引表作相应的修改。06文件管理6.2.4索引顺序文件将顺序文件中若干记录分为一组，每组的第一项在索引表中占一项。06文件管理6.3外存分配方法（文件物理组织）6.3.1连续分配（磁带，磁盘都可采用）（顺序文件）每个文件分配一组相邻盘块。特点：简单、碎片（1）顺序访问容易且速度快，因磁头移动距离小，（2）要求连续空间，一段时间后需整理磁盘以消除外部碎片。（3）必须事先知道长度。文件对应目录项（属性）中包含：始址、总块数。06文件管理sort.c012301234567891011121314文件目录起址长度54sort.c文件名称外存06文件管理6.3.2链接分配（串连文件/链接文件）文件离散地分配于各盘块中，以提高外存利用率，文件长度可变，易于增删，只能顺序存取。对应目录项：链表的首指针一、隐式链接文件目录表中有start块号，每块中有下一块号。特点：只适合于顺序访问，对随机访问效率低，可靠性差。簇：包含多个块的单位，当以它为单位分配并链接，可减少访问时间，但增大了内部碎片06文件管理sort.c012301234567891011121314文件目录起址5sort.c文件名称datanext06文件管理二、显式链接：把用于链接文件各个物理块的指针显式存放在内存的一张表中，查找在内存中进行。显式链接结构物理地址字段06文件管理6.3.3FAT和NTFS技术FAT(Table)：文件分配表早期MS-DOS操作系统中，引入了“卷”

该系统支持将一个物理磁盘分成4个逻辑磁盘每一个逻辑磁盘就是一个“卷”：也叫“分区”“卷”：文件系统的信息、一组文件、空闲空间06文件管理

6.3.3FAT和NTFS技术1．FAT121)以盘块为基本分配单位早期MS-DOS操作系统所使用的是FAT12文件系统，在每个分区中都配有两张文件分配表FAT1和FAT2，在FAT的每个表项中存放下一个盘块号，它实际上是用于盘块之间的链接的指针，通过它可以将一个文件的所有的盘块链接起来，而将文件的第一个盘块号放在自己的FCB中。06文件管理MS-DOS的文件物理结构

物理地址字段物理地址字段06文件管理DOS对于1.2MB软盘，盘块大小为512B，每个FAT表项占12位，在每个FAT中共2.4k个表项，故FAT表共占用3.6k.1.2MB/512B=2.4K个表项每个表项占12位，则2.4K个表项占用的存储空间为2.4K*12b/8b=3.6KB06文件管理以盘块为单位分配，允许的最大磁盘容量：每个FAT表项占12位，最多允许有4096个表项,若以盘块为基本分配单位，每盘块的大小一般为512B，则每个磁盘分区的容量为2MB(4096×512B（扇区大小)）。一个物理磁盘支持4个逻辑磁盘分区，相应的磁盘最大容量仅为8MB。DOS系统使用FAT12的文件系统时所允许的最大磁盘容量06文件管理簇的基本概念簇是一组连续的扇区，在FAT中它是作为一个虚拟扇区，簇的大小一般是2n(n为整数)个盘块当一个簇有2个扇区时，磁盘的最大容量为4*4MB=16MB当一个簇有8个扇区时，磁盘的最大容量为4*16MB=64MB评价：使FAT表占用更少的存储空间，并减少访问FAT表的存取开销，提高文件系统的效率；但这也会造成更大的簇内零头06文件管理2．FAT16将FAT表的宽度增至16位，最大表项数将增至65536个，此时便能将一个磁盘分区分为65536(216)个簇。我们把具有16位表宽的FAT表称为FAT16。如果我们在FAT16的每个簇中可以有的盘块数为64，由此得出FAT16可以管理的最大分区空间为：216×64×512B=2048MB。评价：碎片大06文件管理FAT表的宽度为32位，可以表示232=4294967296项

FAT32的每个簇都固定为4KB

可以管理的单个最大磁盘空间达到4KB*232=2TB3．FAT32评价：减少浪费，但是速度慢，不支持容量小于512的分区，不能向下兼容06文件管理

4．NTFS

NTFS(NewTechnology)特征：64位磁盘地址支持长文件名具有系统容错功能提供了数据的一致性文件加密、文件压缩06文件管理NTFS文件系统中，把卷上簇的大小称为“卷因子”，也是物理磁盘扇区的整数倍，一般是2n(n为整数)个盘块。为了在传输效率和簇内碎片之间进行折中，大多情况下，卷因子的大小都为4KB。06文件管理6.3.4索引分配（索引文件）一、单级索引链接分配问题：不能高效直接存取；FAT需占较大的内存。原理：为每个文件分配一个索引块，记录文件的盘块号。特点：（1）支持直接访问、不会产生碎片。（2）文件较大时有利。文件较小时浪费外存空间（还需为小文件建索引块）（3）当文件较大时，索引块太多，查找速度减慢解决：当索引块太多时，则需建立多级索引06文件管理索引分配06文件管理6.3.3索引分配（索引文件）二、多级索引两级:为多个索引块再建立一级索引。设一个盘块大小为1kB，每个盘块号占4B。一个索引块中可以放256个盘块号。则2级索引存放的文件的盘块号总数为：256×256=64k,故文件的最大长度为64M。06文件管理多级索引06文件管理6.3.3索引分配（索引文件）三、混合索引分配方式一、二、三、多级索引相结合而形成的一种分配方式以UNIXSystemv的索引节点为例：设每个块大小为4kB，每个盘块号占4个字节，则1.直接地址i.addr(0)~i.addr(9)：小文件（<40kB)可直接从索引结点中读出该文件的全部盘块号2.一次间址i.addr(10)：在一次间址块中可存放1k个盘块号，则文件可长达4MB3.多次寻址:4G->4T。06文件管理图混合索引方式06文件管理6.4目录管理在一个计算机系统中，通常存储有大量的文件。为了能对这些文件实施有效的管理，必须将它们合理的组织起来，这主要是通过文件目录来实现的。功能：

（1）按名存取；（2）提高检索速度；（3）文件共享；（4）允许文件重名。文件目录：文件控制块的有序集合，又称目录文件。06文件管理6.4.1文件控制块和索引结点一、文件控制块FCB（描述和控制文件的数据结构）1.基本信息（1）文件名（2）文件物理位置:(设备名，起始盘块号，文件长度)（3）文件逻辑结构流式记录式：定长、变长（4）文件物理结构：顺序放离散放：链式、索引式06文件管理文件控制块FCB2.存取控制信息(安全性)。文件主/核准用户/一般用户存取权限。3.使用信息类：（1）文件的建立日期/时间；（2）文件上一次修改时间；（3）当前使用信息。例：DOS的文件控制块文件名扩展名属性时间日期第一块号盘块数06文件管理二、索引结点1.引入例：一个FCB为64B，一个盘块为1KB，设文件共有3076个，因一个盘块只能放1024/64=16个FCB，故文件目录占了3076/16=192个盘块，当要访问某文件，查找目录需多次启动磁盘。FCB中含:文件名、描述信息，它们较占空间。索引结点：含文件描述信息的数据结构。在UNIX系统中称为i结点。目录项中只有文件名和指向i结点的指针。06文件管理二、索引结点a.将FCB分为文件名、i（index)结点指针和相应的i结点，其中文件名和i结点指针占16字节。b.离散存放目录结构查询时只调入文件名部分，找到后才调入相应结点。文件名索引结点编号文件名1文件名2……013141506文件管理2.磁盘索引结点（1）文件主标识符；（2）文件类型；（3）文件存取权限；（4）文件物理地址；(给出盘块号)（5）文件长度；（6）文件连接（共享）计数；（7）文件存取时间。06文件管理3.内存索引节点文件打开后，将磁盘索引结点的内容部分或全部子集拷贝到内存，并增加以下内容。（1）索引结点编号；（2）状态；（上锁、修改）（3）访问（共享）计数；（4）逻辑设备号；（5）链接指针:i节点的组织结构。06文件管理6.4.2目录结构单级目录结构（1）新建文件时——>空白目录项——>加入目录表（2）删除文件——>回收块——>清除占用目录项特点：（1）简单、按名存取（2）速度慢/不允许重名/不便于共享(不能用不同名字访问同一文件)。文件名物理地址文件说明状态位文件名1文件名2…图单级目录06文件管理6.4.2目录结构为了克服单级目录的缺点（速度慢/不允许重名/不便于共享）为每一个用户建立一个单独的用户文件目录UFD：由用户所有文件的文件控制块组成。在系统中再建立一个主文件目录MFD，每个用户文件目录都要占一个目录项（包括用户名和指向该用户目录文件的指针）06文件管理两级目录结构：如图MFD（主文件目录）+UFD（用户文件目录）用户可以请求建立和撤销UFD。特点:（1）提高了速度:如：n个用户，每用户最多m个文件，则最坏速度为n+m而非n*m（2）可重名（3）可共享06文件管理图两级目录结构6.4.2目录结构06文件管理二级目录结构06文件管理6.4.2目录结构树型目录结构（多级目录）（图）一、树型目录：目录文件中的目录项可为：目录文件或数据文件的FCB。二、路径名：/B/F/J三、当前目录/工作目录。把从当前目录开始直到数据文件为止所构成的路径名称为相对路径。把从树根开始的路径名称为绝对路径。四、增/删除（可/不可删除非空目录）五、评价：查询速度快、层次结构清晰、管理和保护文件方便。增加了磁盘访问次数06文件管理图

多级目录结构06文件管理6.4.3目录查询技术过程：文件名——目录项（FCB）或索引结点——盘块号——

启动磁盘——

驱动程序线性检索法：/usr/ast/mbox06文件管理6.5文件存储空间管理

空闲表法：连续分配方式分配：首次/循环首次/最佳/最坏回收：判断是否合并。序号第一空闲盘块号空闲盘块数12429331554——空闲盘块表：06文件管理6.5文件存储空间管理空闲链表法1.空闲盘块链将磁盘上所有空闲空间，以盘块为单位拉成一条链。优点：分配和回收简单。分配：从链首开始找下适当数目的盘块分配给用户。回收：将回收的盘块依次插入空闲盘块链的末尾。2.空闲盘区链：将磁盘上所有空闲盘区拉成一条链一个盘区含多个盘块，类似于内存分区分配与回收(合并)。分配:首次适应算法。回收：考虑合并。06文件管理6.5文件存储空间管理6.5.2位示图法（可采用连续或离散分配）1.位示图：一个二进制位表示一个盘块的使用情况。06文件管理6.5文件存储空间管理2.盘块的分配：（1）顺序扫描，找一个或一组“=0”的块。（2）根据找到的行/列得到盘块号。b=n(i-1)+j（3）修改位示图。3.回收（1）由盘块号得(i,j) i=(b-1)divn+1j=(b-1)modn+1（2）修改位示图06文件管理6.5文件存储空间管理6.5.3成组链接法一、空闲盘块的组织。（1）空闲盘块号栈：空闲盘块的盘块号、尚有的空闲盘块号数N(2)文件区中的所有空闲盘块被分成若干个组，假定盘上共有10000个盘块，每块大小为1KB，其中第201～7999号盘块用于存放文件，即作为文件区，这样，该区的最末一组盘块号应为7901～7999；次末组为7801～7900……；第二组的盘块号为301～400；第一组为201～300，如图所示。(3)将每一组含有的盘块总数N和该组所有的盘块号记入其前一组的第一个盘块的S.free(0)～S.free(99)中。06文件管理(4)将第一组的盘块总数和所有的盘块号记入空闲盘块号栈中，作为当前可供分配的空闲盘块号。(5)最末一组只有99个盘块，其盘块号分别记入其前一组的S.free(1)～S.free(99)中，而在S.free(0)中则存放“0”，作为空闲盘块链的结束标志。06文件管理图

空闲盘块的成组链接法06文件管理二、空闲盘块的分配与回收分配：到s.free(0)时，由于该块内容为下一组的盘号，将内容加入空闲盘块号栈中，再分配。回收：到s.free(100)时，将空闲盘块栈中内容放入新到的回收块中，将该回收块作为栈底。06文件管理6.6文件共享与保护6.6.1基于索引结点的共享方式06文件管理6.6文件共享与保护6.6.1基于索引结点的共享方式（1）建立链接时，将共享文件的物理地址链拷贝到目录中。缺点：文件增、改时，其它用户不知道，造成新增内容不能共享。（2）共享索引结点：当count>1时，这时文件主也不能删文件。否则，指针悬空。06文件管理图

基于索引结点的共享方式06文件管理图

进程B链接前后的情况06文件管理6.6文件共享与保护6.6.2利用“符号链”实现文件共享。建立一“符号链”（LINK)文件，该文件中包含被链接文件的路径名。这样，仅原文件指向索引结点，其它链接文件仅包含原文件的路径名，文件主可对原文件删除等。06文件管理6.6.3磁盘容错技术影响系统安全的因素：人为、系统、自然确保系统安全性采取措施：(1)存取控制机制(2)磁盘容错技术（系统容错技术SFT）(3)“后备系统”06文件管理6.6.3磁盘容错技术第一级容错技术SFT-Ⅰ（防止磁盘表面缺陷）1)双份目录和双份文件分配表2)热修复重定向和写后读校验第二级容错技术SFT-Ⅱ1)磁盘镜像(DiskMirroring)。图左2)磁盘双工(DiskDuplexing)。图右06文件管理6.7数据一致性控制6.7.1事务

1.事务的定义事务是用于访问和修改各种数据项的一个程序单位。事务也可以被看作是一系列相关读和写操作。被访问的数据可以分散地存放在同一文件的不同记录中，也可放在多个文件中。只有对分布在不同位置的同一数据所进行的读和写(含修改)操作全部完成时，才能再以托付操作(CommitOperation)来终止事务。只要有一个读、写或修改操作失败，便须执行夭折操作(AbortOperation)。读或写操作的失败可能是由于逻辑错误，也可能是系统故障所导致的。06文件管理2.事务记录(TransactionRecord)·事务名：用于标识该事务的惟一名字；·数据项名：它是被修改数据项的惟一名字；·旧值：修改前数据项的值；·新值：修改后数据项将具有的值。06文件管理3.恢复算法恢复算法可利用以下两个过程：

(1)undo〈Ti〉。该过程把所有被事务Ti修改过的数据，恢复为修改前的值。

(2)redo〈Ti〉。该过程能把所有被事务Ti修改过的数据，设置为新值。如果系统发生故障，系统应对以前所发生的事务进行清理。06文件管理6.7.2检查点1.检查点(CheckPoints)的作用引入检查点的主要目的，是使对事务记录表中事务记录的清理工作经常化，即每隔一定时间便做一次下述工作：首先是将驻留在易失性存储器(内存)中的当前事务记录表中的所有记录，输出到稳定存储器中；其次是将驻留在易失性存储器中的所有已修改数据，输出到稳定存储器中；然后是将事务记录表中的〈检查点〉记录，输出到稳定存储器中；最后是每当出现一个〈检查点〉记录时，系统便执行上小节所介绍的恢复操作，利用redo和undo过程实现恢复功能。06文件管理2.新的恢复算法恢复例程首先查找事务记录表，确定在最近检查点以前开始执行的最后的事务Ti。在找到这样的事务后，再返回去搜索事务记录表，便可找到第一个检查点记录，恢复例程便从该检查点开始，返回搜索各个事务的记录，并利用redo和undo过程对它们进行处理。如果把所有在事务Ti以后开始执行的事务表示为事务集T，则新的恢复操作要求是：对所有在T中的事务TK,如果在事务记录表中出现了〈TK托付〉记录，则执行redo〈TK〉操作；反之，如果在事务记录表中并未出现〈TK托付〉记录，则执行undo〈TK〉操作。06文件管理6.7.3并发控制利用互斥锁实现“顺序性”2.利用互斥锁和共享锁实现顺序性06文件管理6.7.4重复数据的数据一致性问题1.重复文件的一致性图UNIX类型的目录06文件管理2.盘块号一致性的检查图

检查盘块号一致性情况06文件管理图

检查盘块号一致性情况06文件管理3.链接数一致性检查为每个盘块建立一个表项，其中含有该索引结点号的计数值。在进行检查时，从根目录开始查找，每当在目录中遇到该索引结点号时，便在该计数器表中相应文件的表项上加1。当把所有目录都检查完后，便可将该计数器表中每个表项中的索引结点号计数值与该文件索引结点中的链接计数count值加以比较，如果两者一致，表示是正确的；否则，便是发生了链接数据不一致的错误。06文件管理如果索引结点中的链接计数count值大于计数器表中相应索引结点号的计数值，则即使在所有共享此文件的用户都不再使用此文件时，其count值仍不为0，因而该文件不会被删除。这种错误的后果是使一些已无用户需要的文件仍驻留在磁盘上，浪费了存储空间。解决的方法是用计数器表中的正确的计数值去为count重新赋值。反之，如果出现count值小于计数器表中索引结点号计数值的情况时，就有潜在的危险。假如有两个用户共享一个文件，但是count值仍为1，这样，只要其中有一个用户不再需要此文件时，count值就会减为0，从而使系统将此文件删除，并释放其索引结点及文件所占用的盘块，导致另一共享此文件的用户所对应的目录项，指向了一个空索引结点