现代操作系统.pptx

16.1 文件和文件系统 现代OS是通过文件系统来组织和管理在计算机中所存储的大量程序和数据；或者说，文件系统的管理功能，是通过把它所管理的程序和数据组织成一系列文件的方法来实现的。文件是数据的一种组织形式，文件管理系统是指文件和对文件进行操纵和管理的软件集合。基于文件系统的概念而把数据的组成分为数据项、记录和文件三级。第1页/共76页2文件、记录和数据项（1）一、数据项：数据项可分成两种类型：1、基本数据项：用于描述一个对象的某种属性的字符集，是数据组织中可以命名的最小逻辑数据单位，又称为数据元素或字段。它除了数据名外，还应有数据类型。表征一实体在数据项上的数据称为值。2、组合数据项：由若干个基本数据项组成，简称组项。第2页/共76页3文件、记录和数据项（2）二、记录：是一组相关数据项的集合，用于描述一个对象某方面的属性。一个记录应包含的数据项，取决于需要描述的对象的哪些方面。一个对象由于他所处的环境不同可把他作为不同的对象。在诸多记录中。为了能唯一地标识一个记录，必须在记录的各个数据项中，确定一个或几个项，把他们的集合称为关键字。也即，关键字是能唯一标识一个记录的数据项集。第3页/共76页4文件、记录和数据项（3）三、文件：是由创建者所定义的，具有文件名的一组相关元素的集合，可分为有结构文件和无结构文件两种。在有结构文件中，文件由若干相关记录组成，无结构文件则被看成是一个字符流。文件在文件系统中是一个最大的数据单位，描述了一个对象集。一个文件必须要有一个文件名，用户利用文件名来访问文件。此外，文件具有自己的属性，属性可包括：文件类型、文件长度、文件的物理位置、文件的存取控制、文件的建立时间等。第4页/共76页5文件类型 对文件的分类有下列几种方法:一、按用途分类：系统文件、用户文件、库文件。二、按文件中的数据形式分类：源文件、目标文件、可执行文件。三、按存取控制属性分类：只执行文件、只读文件、读写文件。第5页/共76页6文件系统模型 文件系统是指含有大量的文件及其属性的说明，对文件进行操纵和管理的软件，以及向用户提供使用文件的接口等的集合。文件系统接口逻辑文件系统基本I/O管理程序（文件组织模块）基本文件系统（物理I/O层）I/O控制层（设备驱动程序）对象及其属性说明对对象操纵和管理的软件集合（1）文件，文件管理的直接对象。（2）目录，对目录的组织和管理，是方便用户和提高文件存取速度的关键。（3）磁盘（带）存储空间。文件系统的核心部分。文件系统的大部分功能，都是在这一层实现。包括命令接口和程序接口两类。文件系统的最底层，主要由磁盘（磁带）驱动程序组成。主要用于处理内存与磁盘(带）机系统之间数据块的交换。完成与磁盘I/O有关的大量事务，有：选择文件所在设备；进行文件逻辑块号到物理块号的转换；空闲盘块的管理；I/O缓冲的制定。处理文件和记录的相关操作。第6页/共76页7文件操作用户通过文件系统所提供的系统调用实施对文件的操作：最基本的文件操作：创建文件：分配外存空间，建立目录项。删除文件：将要删除文件的目录项置为空项，回收空间。读文件；写文件；截断文件：放弃原有文件的内容设置文件的读/写位置：改顺序存取为随机存取。第7页/共76页8文件操作文件的“打开”和“关闭”操作当前OS提供的大多数对文件的操作，其过程大致分为两步：第一步是通过检索文件目录来找到指定文件的属性及其在外存上的位置；第二步是对文件实施相应的操作。为了避免多次重复地检索目录，引入open这一文件系统调用。所谓“打开”是指系统将指名文件的属性从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号（索引）返回给用户，以后便利用返回的索引号向系统提出操作请求。Close系统调用用来关闭文件，OS将把该文件从打开文件表中的表目上删除掉。第8页/共76页9文件操作其他文件操作为方便用户，OS都提供了数条有关文件操作的系统调用，可将这些系统调用分为若干类：最常用的一类是对文件属性进行操作的；另一类是对有关目录的；还有实现文件共享的系统调用；用于对文件系统进行操作的系统调用。第9页/共76页106.2 文件逻辑结构文件系统设计的关键要素，是将诸记录构成一个文件的方法，以及将一个文件存储到外存的方法。任何一个文件，都存在着两种形式的结构：(1)文件的逻辑结构。是从用户观点出发所观察到的文件组织形式，是用户可以直接处理的数据及其结构，独立于物理特性，又称为文件组织。(2)文件的物理结构，又称为文件的存储结构，是文件在外存上的存储组织形式，与存储介质的存储性能有关。对文件的逻辑结构提出的要求有：提高检索效率；便于增、删、改文件的记录；降低文件存储费用。第10页/共76页11文件逻辑结构的类型（1）文件的逻辑结构可分为两大类：一是有结构文件(记录式文件)；二是无结构文件(流式文件)。一、有结构文件：其记录长度可分为定长和不定长两类。组织这些记录的方式有多种。而形成下述几种文件：顺序文件。由一系列记录，按某种顺序排列所形成的文件。其中的记录通常是定长记录。索引文件。当记录为可变长度时，通常为之建立一张索引表，为每个记录在表中设置一表项。索引顺序文件。是上述两种文件方式的结合。它为文件建立一张索引表，为每一组记录中的第一个记录设置一表项。第11页/共76页12文件逻辑结构的类型（2）二、无结构文件：即流式文件，其长度以字节为单位。对流式文件的访问，是利用读写指针来指出下一个要访问的字符。可以把流式文件看作是记录式文件的一个特例。在UNIX系统中，所有的文件都被看作是流式文件，即使是有结构文件，系统不对文件进行格式处理。第12页/共76页13顺序文件（1）一、逻辑记录的排序：文件中的记录可以是任意顺序的，因此，可以按照不同顺序进行排列，一般可归纳为以下两种：串结构。记录之间的顺序与关键字无关，通常的办法是按存入的时间先后来排列。顺序结构。文件中的所有记录按关键字排列。就检索效率而言，对顺序结构文件的检索比对串结构文件的检索要高。第13页/共76页14顺序文件（2）二、对顺序文件的读/写操作R0R1R2RiRptr01I2I3IiIl定长记录文件I0R0I1R10I0+1I0+I1+2I0I1变长记录文件RptrI第14页/共76页15顺序文件（3）三、顺序文件的优缺点：顺序文件的最佳应用场合是对诸记录进行批量存取时。此时，其存取效率是所有逻辑文件中最高的。另外，只有顺序文件才能存储在磁带上，并能有效地工作。在交互应用场合，若用户要求查找或修改单个记录，这时顺序文件表现出来的性能可能很差。其另一缺点是，若想要增加或修改一个记录，都比较困难。解决的办法是为顺序文件配置一个运行记录文件，每隔一定时间就将运行记录文件与原来的主文件合并，产生一个按关键字排序的新文件。第15页/共76页16索引文件 索引文件的组织：索引号 长度 m 指针prt 0 m0 1 m1 i mi R0 R1 Ri 索引表逻辑文件是一个定长记录的顺序文件。对索引文件进行检索，是根据用户提供的关键字进行的。定长记录文件，获得第i个记录的相对于第一个记录首址的地址的公式为：Ai=il。故实现顺序存取和直接存取都较方便.对于可变长记录文件，获得第i个记录相对于第一个记录首址的地址则为：Ai=Ii+i 因而实现直接存取较困难，且访问的效率也低，于是采用索引表的方式。第16页/共76页17索引顺序文件 索引顺序文件是为顺序文件建立一张索引表，将顺序文件中的所有记录分成若干组，在索引表中为每组中的第一个记录建立一个索引项，其中含有记录的键值和指向该记录的指针。检索时，首先利用用户提供的关键字去检索索引表，找到该记录所在记录组中第一个记录的表项，从中得到该记录组第一个记录在主文件中的位置；然后再利用顺序查找法去查找主文件，从中找到所要求的记录。对于一个很大的顺序文件，可以建立多级索引，即为索引文件再建立一张索引表，以提高检索效率。第17页/共76页186.3 外存分配方法为文件分配外存空间时所要考虑的主要问题是：外存空间的有效利用；提高对文件的访问速度。目前，常用的外存分配方法有：连续分配；链接分配；索引分配。文件的物理结构直接与外存分配方式有关，采用不同的分配方式，将形成不同的文件物理结构。第18页/共76页19按文件的物理结构分类顺序文件：指把文件中的记录顺序地存储到连续的物理盘块中。这样，在顺序文件中记录的次序与它们在存储介质上的存放次序一致。链接文件：指文件中的各条记录可以存放在不相邻接的各个物理盘块中，通过物理块中的链接指针连接成一个链表。索引文件：指文件中的各条记录可以存放在不相邻接的各个物理盘块中，建立一张索引表，来实现记录和物理块之间的映射。在索引表中为每条记录设一表项，其中存放该记录的记录号以及所在的物理块号。第19页/共76页20连续分配连续分配要求为每一个文件分配一组相邻接的盘块。一组盘块的地址定义了磁盘上的一段线性地址。采用该方式时，可把逻辑文件中的记录，顺序地存储到邻接的各物理盘块中，这样形成的物理文件称为顺序文件。连续分配方式下存在外部碎片问题，可利用紧凑的方法，将盘上所有文件紧靠在一起，使所有的碎片拼接成一大片连续的存储空间，但一次紧凑所花费的时间较长。连续分配的主要优点有：顺序访问容易。顺序访问速度快。主要缺点是：要求有连续的存储空间。产生许多外部碎片。必须事先知道文件的长度。第20页/共76页21链接分配（1）链接分配是一种离散分配方式，可通过在每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表。由此形成的物理文件称为链接文件。链接分配消除了外部碎片，可显著地提高外存空间的利用率。存储文件时无须事先知道文件的长度，而是根据文件的当前需要，为它分配必须的盘块。当文件动态增长时，可动态地再为它分配盘块。此外对文件的增、删、改也很方便。链接方式可分为隐式链接和显式链接两种形式。第21页/共76页22链接分配（2）一、隐式连接：采用该方式时，是在文件目录的每个目录项中都含有指向链接文件的第一个盘块和最后一个盘块的指针，在每个盘块中都含有一个指向下一个盘块的指针。其主要问题是：它只适合于顺序访问，对随机访问是及其低效的。另外，只通过链接指针来将一大批离散的盘块链接起来，其可靠性较差。为提高检索速度和减少指针所占用的存储空间，可将几个盘块组成一个簇，盘块分配时以簇为单位进行。在链接文件中的每个元素也是以簇为单位。第22页/共76页23链接分配（3）二、显式链接：指把用于链接文件各物理块的指针，显式地存放在内存的一张链接表中。整个磁盘仅设置的一张链接表。表的序号是物理盘块号，每个表项中存放链接指针，即下一个盘块号。在该表中，凡是属于某个文件的第一个盘块号，均作为文件地址被填入相应文件的FCB的“物理地址”字段中。由于分配给文件的所有盘块号都放在该表中，故称该表为文件分配表FAT。链接分配存在的问题:一是不能支持高效地直接存取;二是FAT需占用较大的内存空间。第23页/共76页24 索引分配（1）一、单级索引分配：索引分配方法是为每个文件分配一个索引块（表），把分配给该文件的所有盘块号，都记录在该索引块中，从而索引块就是一个含有许多盘块号的数组。在建立一个文件时，便须在为之建立的目录项中，填上指向该索引块的指针。索引分配方式支持直接访问。不会产生外部碎片。文件较大时该方式优于链接分配方式。其主要问题是可能要花费较多的外存空间。第24页/共76页25索引分配（2）二、多级索引分配：OS为一个大型文件分配磁盘空间时，若所分配出去的盘块号已经装满一索引块时，就再为该文件分配一个索引块，用于将以后继续为该文件分配的盘块号记录于其中，依此类推。再通过链接指针将各索引块按序链接起来。显然当文件太大，其索引块太多时，这种方法是低效的。此时，应为这些索引块再建立一级索引，称为第一级索引，即系统再分配一索引块，作为第一级索引的索引块，将第一块、第二块、等索引块的盘块号填入其中。这样便形成了两级索引分配方式，必要时还可用三级、四级索引分配方式。第25页/共76页 索引分配（3）三、混合索引分配方式：指将多种索引分配方式相结合而形成的一种分配方式。这种方式已在UNIX系统中采用。在UNIX System 5的索引结点中，共设置13个地址项，即iaddr(0)至iaddr(12)。系统把所有地址项分成两类，即直接地址和间接地址。1、直接地址：是指存放文件的那些盘块的盘块号。在索引结点中可设置10个直接地址项，即用iaddr(0)至iaddr(9)来存放直接地址。2、一次间接地址：这种方式的实质就是一级索引分配方式，利用iaddr(10)来提供一次间接地址。3、多次间接地址：利用iaddr(11)来提供二次间接地址，其实质是两级索引方式。同理，利用iaddr(12)来提供三次间接地址。第26页/共76页ModeOwners(2)Time stamps(3)SizeBlock counti.addr(0)i.addr(1)i.addr(9)Single indirectDouble indirectTriple indirectdatadatadata datadatadatadatadatadatadata混合索引分配磁盘索引结点索引块第27页/共76页286.4 目录管理文件目录具有将文件名转换为该文件在外存的物理位置的功能。对文件目录的管理有以下要求：实现“按名存取”。即用户只需提供文件名，就可对文件进行存取。提高对目录的检索速度。从而加快对文件的存取速度。这是在设计一个大中型文件系统时所追求的主要目标。文件共享。允许文件重名。第28页/共76页29文件控制块和索引结点（1）一、文件控制块FCB：是为文件设置的用于描述和控制文件的数据结构。文件管理程序借助FCB对文件实施各种操作。文件与FCB一一对应，把FCB的有序集合称为文件目录。一个FCB就是一个文件目录项。通常一个文件目录也被看作是一个文件，称为目录文件。在FCB中包含的信息有三类：1.基本信息类：包括文件名、文件物理位置（其中包括存放文件的设备名、文件在外存上的盘块号、文件长度）、文件逻辑结构、文件物理结构。2.存取控制信息类：包括文件主的存取权限、核准用户的存取权限、一般用户的存取权限。3.使用信息类：包括文件的建立日期和时间、文件上一次修改的日期和时间、当前使用信息。第29页/共76页30文件控制块和索引结点（2）二、索引结点1.索引结点的引入：在检索目录文件的过程中，只需用到文件名，不需文件的描述信息，有些系统如UNIX，就把文件名和文件描述信息分开。把文件描述信息单独形成一个称之为索引结点的数据结构，简称为i结点，而在文件目录中的每个目录项，则仅由文件名和指向该文件所对应的i结点的指针所构成。这样为找到一个文件，可大大节省系统开销。第30页/共76页31 文件控制块和索引结点（3）2.磁盘索引结点：指存放在磁盘上的索引结点。每个文件有唯一的磁盘i结点。主要包括：文件主标识；文件类型；文件存取权限；文件物理地址；文件长度；文件连接计数；文件存取时间。3.内存索引结点：指存放在内存的索引结点。文件被打开时，要将磁盘索引结点拷贝到内存的索引结点中，以便于以后使用。其增加的内容有：索引结点编号；状态；访问计数；文件所在设备的逻辑设备号；链接指针。第31页/共76页32目录结构 1、单级目录结构；是最简单的目录结构。在整个系统中只建立一张目录表，为每个文件分配一个目录项。单级目录结构的优点是简单，缺点则有：查找速度慢、不允许重名、不便于实现文件共享。只适用于单用户环境。文件名状态位物理地址文件其他属性AlphaReportText第32页/共76页332、两级目录结构两级目录结构如图：用户名子目录指针WangZhangGaoAlphaTestReportTestBetaDeviMisxWang用户目录AlphaTestReportTestBeta优点是提高了检索目录的速度、在不同的用户目录中可以使用相同的文件名、不同用户可使用不同的文件名来访问系统中的同一个共享文件。缺点是当多个用户之间要相互合作去完成同一个大任务，且一用户又要去访访问其他用户文件时，用户目录之间的隔离使诸用户之间不便于共享文件。Gao UFD主文件目录MFD第33页/共76页343、多级目录结构（1）一、目录结构：通常把三级及以上的文件目录结构称为树型结构的目录。它具有检索效率高、允许重名、便于实现文件共享等一系列优点。主目录在树型目录结构中，作为树的根结点，称为根目录。数据文件作为树叶，其他所有目录均作为树的结点。第34页/共76页35多级目录结构：A B C A B D F E D G A J N K J M K A H F A C 123456789101311121415161718192021 为提高文件系统的灵活性，应允许把一个目录文件中的目录项，既能作为目录文件的FCB又能作为数据文件的FCB，具体是哪一种FCB，可用目录项中的一位来表示。例如，在用户A的总目录中，目录A是目录文件的FCB，而目录B和D，则是数据文件的FCB。第35页/共76页36多级目录结构（2）二、路径名：从根目录到任何数据文件，只有唯一的一条通路，在该路径上从树的根开始，把全部目录文件名与数据文件名，依次用“/”连接起来，即构成该数据文件的路径名。系统中的每个数据文件都有唯一的路径名。三、当前目录：又称为工作目录，是树型目录结构中的某个结点。进程对各文件的访问都是相对于当前目录进行的。此时对各文件所使用的路径名，只需从当前目录开始，再逐级通过中间的目录文件，最后达到所要访问的数据文件。将这一路径上的全部目录文件名与数据文件名用“/”连接而成的路径名称为相对路径名。相应地，从树根开始的路径名称为绝对路径名。第36页/共76页37多级目录结构（3）四、增加和删除目录：用户可为自己建立UFD(User File Directory)和子目录，只要不同名，便可在UFD或其子目录中增加一新目录项。删除一个目录时，若该目录下没有任何文件，就可简单地将该目录文件删除，使它在其上一级目录中对应的目录项为空；若存在文件，则有两种处理方式：1、不删除非空目录：当目录中不空时，不能将其删除。若要删除，则必须先删除目录中的文件，使其成为空目录后，才能删除。若目录中还含有子目录，则须采用递归调用方式来将其删除。(MS-DOS)2、可删除非空目录：当要求删除一个目录后，则目录中的所有文件和子目录也一并删除。第37页/共76页38目录查询技术为实现对文件的按名存取，系统须按下述步骤为用户找到其所需文件：系统利用用户提供的文件名去查询文件目录，找出该文件的FCB或i结点；根据FCB或i结点中记录的文件物理地址，换算出文件在磁盘上的物理位置；启动磁盘驱动程序，将所需文件读入内存中。目前，对目录进行查询的方式有两种：线性检索法和Hash法。线性检索法又称为顺序检索法。第38页/共76页查找/usr/ast/mbox的步骤1 1 4Bin7Dev14Lib9Etc6Usr8tmp根目录 132索引结点6是/usr的目录6 1 19Disk30Erik51Jim26Ast45bal132#块是/usr的目录 406索引结点26是/usr/ast目录26 6 64Grant92Books60Mbox81Minix17Src406#块是/usr/ast目录线性检索法的例子第39页/共76页406.5 文件存储空间的管理文件管理要解决的重要问题之一是如何为新创建的文件分配存储空间。解决的办法与内存分配情况有许多相似之处，即同样可采取连续分配方式和离散分配方式。存储空间的基本分配单位都是磁盘块而非字节。为了实现存储空间的分配，系统应为分配存储空间而设置相应的数据结构，应提供对存储空间进行分配和回收的手段。第40页/共76页41 空闲表法和空闲链表法1.空闲表法空闲表法属于连续分配方式，为每个文件分配一个连续的存储空间。系统为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项。空闲盘区的分配算法与内存的动态分配类似，有几种分配算法。采用首次适应算法，系统在为新创建的文件分配空闲盘区时，顺序检索空闲表的各表项，直至找到第一个其大小能满足要求的空闲盘区，将该区分配给用户，同时修改空闲表。系统在对用户所释放的存储空间进行回收时，也采用类似于内存回收的方法，即要考虑回收区是否与空闲表中插入点的前区和后区相邻接，对相邻者应合并。第41页/共76页42 空闲链表法 1、空闲盘块链：将磁盘上的所有空闲空间，以盘块为基本元素拉成一条链。当用户请求分配存储空间时，系统从链首开始，依次摘下适当数目的空闲盘块分配给用户。回收时，系统将回收的盘块依次链入空闲盘块链的尾部。该方法的优点是分配和回收一盘块的过程很简单，缺点是空闲盘块链可能很长。2、空闲盘区链：将磁盘上所有空闲盘区拉成一条链。盘区上除含有指示下一个空闲盘区的指针外，还有标明本区大小的信息。盘区的分配方法通常是采用首次适应算法，这样可在内存中为空闲盘区建立一张链表。回收盘区时，同样也要将与回收区邻接的空闲盘区合并。该方法的优缺点与第一种刚好相反。第42页/共76页位示图法(1)1、位示图：是利用二进制的一位来表示磁盘中的一个块的使用情况。磁盘上的所有盘块都有一个二进制位与之对应，这样由所有盘块所对应的位构成一个集合，称为位示图。位示图也可描述成一个二维数组 map:Var map:array 1m,1n of bit;1 2 3 4 5 6 7 8 9 16123161 1 0 0 0 1 1 1 0 0 1 0 1 1 1 00 0 0 1 1 1 1 1 1 0 0 0 0 1 1 11 1 1 0 0 0 1 1 1 1 1 1 0 0 0 0第43页/共76页44 位示图法(2)2、盘块的分配：根据位示图进行盘块分配时，可分三步进行：顺序扫描位示图，从中找出一个或一组其值均为“0”的二进制位。转换成相应的盘块号。假定找到的为“0”的位，位于位示图的第i行，第j列，则相应的盘块号为：b=n(i-1)+j，其中n表示每行的位数。修改位示图，令mapi，j=1第44页/共76页45位示图法(3)3、盘块的回收：分为两步：将回收盘块的盘块号b转换成位示图中的行号和列号。其公式是：i=(b-1)DIVn+1 j=(b-1)MODn+1修改位示图。令mapi,j=0 这种方法的主要优点是从位示图很容易找到一个或一组相邻接的空闲盘块。此外，位示图占用空间少，可将其保存在内存中，每次进行盘区分配时，无须首先去把磁盘分配表读入内存，省掉了许多的磁盘启动操作。第45页/共76页 成组链接法(1)一、空闲盘块的组织空闲盘块号栈。用来存放当前可用的一组空闲盘块的盘块号（最多为100个号）及栈中尚有的空闲盘块数N，N还兼作栈指针用。由于栈是临界资源，故系统为其设置一把锁。文件区中的所有空闲盘块，被分成若干组。将每组含有的盘块总数N和该组所有的盘块号，记入前一组的第一个盘块的S.free(0)S.free(99)中。这样由各组的第一个盘块可链成一条链。将第一组的盘块总数和所有盘块号记入空闲盘块号栈中，作为当前可供分配的空闲盘块。最末一组只有99个盘块，其盘块号分别记入前一组第一盘块的S.free(0)S.free(99)，S.free(0)中放0。第46页/共76页019899空闲盘块号栈S.free1003002992022013001004003993012992017900990799970014003993011007899799978017901成组链接法一组第47页/共76页 成组链接法(2)二、空闲盘块的分配：当系统要为用户分配文件所需的盘块时，需调用盘块分配过程来完成。栈锁否？从栈顶取出块号，对应的盘块分配给用户。栈指针下移一格栈底吗？调用磁盘读过程，将栈底盘块号所对应的内容读入栈中，并把栈底对应的盘块分配出去。栈中空闲盘块数减1返回返回YNYN第48页/共76页49成组链接法(3)三、空闲盘块的回收 系统回收空闲盘块时要调用回收过程，将回收的盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加1操作。当栈中空闲盘块号数目达到100时，表示栈已满，于是将栈中的100个盘块号记入新回收的盘块中，再将该盘块号作为新的栈底。第49页/共76页506.6 文件共享与文件保护早期实现文件共享的方法一、绕弯路法：允许每个用户获得一“当前目录”，用户所访问的文件都相对于当前目录而言；当用户访问的文件不在其当前目录下时，可通过“向上走”的方式去访问其上级目录。二、连访法：在相应的目录项之间进行链接，即把一个目录中的目录项直接指向另一目录中的目录项。三、利用基本文件目录实现文件共享：在文件系统中设置一基本目录，每个文件在该目录中占有一目录项，用于给出系统赋予的唯一的标识符以及该文件的有关说明，如文件的物理地址、存取控制和管理等信息。此外每个用户有一个符号文件目录，其中的每项中含有其文件的符号名及唯一的标识符。第50页/共76页51多级目录结构：A B C A B D F E D G A J N K J M K A H F A C 123456789101311121415161718192021FJCA根目录访问文件17,其路径是:FBEJ路径名为:*.E.J1访问文件9的路径名是:*.*.C.A第51页/共76页52多级目录结构：A B C A B D F E D G A J N K J M K A H F A C 1234567891013111214151617181920212aFA用户B的作业D对用户C的文件A进行访问。用户B的当前目录是F。用户C的文件，在目录C下。建立的链接a。访问的路径名是：*.D.F第52页/共76页53Sqrt5Beta 6Mist7Alpha6Rep80af9Wang3Zhang4空闲文件目录FFD符号名 ID主文件目录MFDWang的SFD符号名 IDZhang的SFD符号名 IDsqrtWang的BetaZhang的AlphaMistRep0af0123456789ID物理位置基本目录文件第53页/共76页54 基于索引结点的共享方式（1）根目录ABCBBBBCCCBCCCC？包含有共享文件的文件系统怎样建立该链接？若在文件目录中包含了文件的物理地址，则链接时，必须将文件的物理地址拷贝到B目录中。但若以后B或C还要继续向该文件添加新内容，从而要用附加操作Apped来增加新的盘块，但新增的盘块只会出现在执行了Apped操作的目录中。这种变化对其他用户是不可见的，因此新增内容不能共享。解决的办法是引进索引结点。第54页/共76页55 基于索引结点的共享方式（2）引用索引结点，即诸如文件的物理地址及其他文件属性等信息，不再放在目录项中而是放在索引结点中。在文件目录中只设置文件名及指向相应索引结点的指针。此时由任何用户对文件进行Apped操作或修改，所引起的相应索引结点内容的改变，如新增盘块号等，都是其他用户可见的，从而也就能提供给其他用户共享。在索引结点中应有一个链接计数，表示链接到本索引结点上的用户目录项的数目。第55页/共76页56Test rTest rWang用户文件目录Lee用户文件目录Count=2文件物理地址Test索引结点第56页/共76页57进程B链接前后的情况：C的目录Owner=CCount=1链接前B的目录Owner=CCount=2建立链接后C的目录B的目录Owner=CCount=1拥有者删除文件后第57页/共76页58利用符号链实现文件共享（1）B为共享C的一个文件F，可由系统创建一个LINK类型的新文件，将新文件写入B的用户目录中，以实现B的目录与文件F的链接。在新文件中只包含被链接文件F的路径名，称这样的链接方法为符号链接。新文件中的路径名，只被看作是符号链，当B要访问被链接的文件F且正要读LINK类新文件时，被OS截获，OS根据新文件中的路径名去读该文件，于是就实现了用户B对文件F的共享。在利用符号链接方式实现文件共享时，只有文件主才拥有指向其索引结点的指针，共享该文件的其他用户，只有该文件的路径名。第58页/共76页59利用符号链实现文件共享（2）该方式存在的问题是每次访问文件的开销大，增加了磁盘启动的频率，LINKE类型文件要消费一定的磁盘空间。一个很大的优点是能够用于链接世界上任何地方的机器中的文件。基于索引结点的共享方式和符号链方式存在一个共同的问题，就是每一共享文件都具有几个文件名。换言之，每增加一条链路，就增加一个文件名。这实质上是每个用户都使用自己的路径名去访问共享文件。当试图去遍历整个文件系统时，将会多次遍历到该共享文件。例如，当有一个程序要将一个目录中的所有文件转储到磁带上去时，就可能对一个共享文件产生多个拷贝。第59页/共76页60 磁盘容错技术 容错技术是通过在系统中设置冗余部件来提高系统可靠性的一种技术。磁盘容错技术则是通过增加冗余的磁盘驱动器、磁盘控制器等，来提高磁盘系统的可靠性。磁盘容错技术也常称为系统容错技术SFT(System Fault Tolerance)，可分为三个级别：SFT是低级磁盘容错技术，主要用于防止磁盘表面发生缺陷所引起的数据丢失；SFT是中级容错技术，主要用于防止磁盘驱动器和磁盘控制器故障所引起的系统不能正常工作；SFT是高级系统容错技术。第60页/共76页61 第一级容错技术 最早且一直使用的技术，包括双份目录和双份文件分配表以及写后读校验等措施。一、双份目录和双份文件分配表：为防止文件目录和文件分配表被破坏而丢失文件，可在不同的磁盘上或在磁盘的不同区域，分别建立两份目录表和FAT。系统加电后要进行一致性检查。二、热修复重定向和写后读校验1、热修复重定向：系统将一定的磁盘容量作为热修复重定向区，用于存放当发现盘块有缺陷时的待写数据，并对写入该区的所有数据进行登记，以便于以后对数据进行访问。2、写后读校验方式第61页/共76页62第二级容错技术一、磁盘镜象：该工作方式是在每次向文件服务器的主磁盘写入数据后，都要采用写后读校验方式，将数据再同样地写到备份磁盘上，使两个磁盘上有着完全相同的位像图。为实现该功能，硬件上是将两个相同的磁盘驱动器连接在同一个磁盘控制器上。二、磁盘双工：是指将两台磁盘驱动器分别接到两个磁盘控制器上，同样地使两台磁盘机镜像成对。在磁盘双工时，文件服务器同时将数据写到两个处于不同控制器下的磁盘上，使两者有着完全相同的位像图。第62页/共76页63磁盘镜像、磁盘双工示意图主机磁盘控制器磁盘驱动器通道主机磁盘控制器磁盘控制器磁盘驱动器通道通道磁盘镜像示意图磁盘双工示意图第63页/共76页646.7 数据一致性控制数据一致性问题，首先是在数据应用中提出来的。例如，在数据库系统中都配置了能保证数据一致性的软件，以及相应的硬件支持。近年来，该项技术已引入到OS。为实现数据的一致性，需要硬件的支持，其中最重要的是要有一个在理论上不会出现故障和错误的存储器系统，在实际上就是一个高可靠的存储器系统，或称之为稳定存储器。实现一个稳定存储器的措施就是采用冗余技术。第64页/共76页65 事务（1）一、事务的定义：事务是用于访问和修改各种数据项的一个程序单位，被访问的数据可以分散在多个文件中。事务也可以被看作是一系列的读和写操作。当这些操作全部完成时，再以托付(commit)操作来终止事务。只要有一个读或写操作失败，则执行夭折(abort)操作。读或写操作的失败可能是由于逻辑错误，也可能是由于系统故障。一个夭折的事务，已经对某些数据项进行了修改，为使夭折的事务不至引起数据的不一致性，需要将该事务内刚被修改过的数据恢复成原来情况，使系统中各个数据项与该事物未执行时的数据项完全相同。由此可知，事务操作具有原子性。第65页/共76页66事务（2）二、事务记录：是实现事务原子修改的数据结构。这些数据结构被放在稳定存储器中，以记录事务运行时数据项修改的全部信息，又称为运行记录(Log)，该记录包括以下各字段：事务名，标识事务的唯一名字；数据项名，被修改数据项的唯一名字；旧值，修改前数据项的值；新值，修改后数据项将具有的值。在事务记录表中的每一个记录，都描述了事务运行中的重要操作。第66页/共76页67事务（3）三、恢复算法：利用事务记录（Log）表，系统能处理任何故障，而不致使造成非易失性存储器中的信息的丢失。恢复算法利用以下两过程：undo(Ti)过程。把所有被事务Ti修改过的数据，恢复为修改前的数据。redo(Ti)过程。把所有被Ti修改过的数据，置为新值。若系统发生故障，应清理以前所发生的事务。通过查Log表，可把尚未清理的事务分为两类：所包含的各个操作是都已完成的事务。确定的依据是在Log表中既包含又包含记录。所包含的各个操作是并未全部完成的事务。若在Log表中，只有记录而无，则事物Ti便是这类事务。第67页/共76页68 检查点（1）一、检查点(Check Point)的作用：引入检查点的主要目的是使对事务记录表中事务记录的清理工作经常化，即每隔一定时间，作一次下述工作：将驻留在内存中当前事务记录表中的所有记录，输出到稳定存储器中。将驻留在易失性存储器中的所有已修改记录，输出到稳定存储器中。将事务记录表中的记录，输出到稳定存储器中。每当出现一个记录时，系统便利用redo和undo过程实现恢复操作。第68页/共76页69 检查点（2）二、新的恢复算法：引入检查点可减少恢复处理的开销。因在发生故障后，并不需对Log表中的所有事务记录进行处理，只须对最后一个检查点之后的事务记录进行处理。因此，恢复例程首先查找Log表，确定在最近检查点以前开始执行的最后事务Ti。找到后，再返回搜索Log表，便可找到第一个检查点记录，恢复例程从该点开始，返回搜索各个事务的记录，并利用redo或undo过程对他们进行处理。若把所有的事务Ti以后开始执行的事务表为事务集T，则新的恢复操作要求：所有在T中的事务Tk，若在Log表中，出现了记录，则执行redo 操作；未出现记录，则执行undo 操作。第69页/共76页70 并发控制(1)在多用户系统中，可能有多个用户在执行事务，由于事务的原子性，事务对数据项的修改必然是互斥的，这种特性称为顺序性。用于实现事务顺序性的技术称为并发控制。可以利用信号量机制来保证事务处理的顺序性。但在数据库系统和文件服务器中，应用得最多的还是较简单的且较灵活的同步机制锁。第70页/共76页71并发控制(2)一、利用互斥锁来实现顺序性：为每一个对象（共享文件、记录或数据项）设置一把用于实现互斥的互斥锁。当事务Ti要访问某对象时，应先获得该对象的互斥锁。若成功，便可将该对象锁住，于是事务Ti可读/写该对象，其他事务由于未能获得锁而不能访问该对象。若Ti要访问一批对象，则要先获得这一批对象的互斥锁，将他们全部锁住。若成功，便可以执行读/写，操作完成后释放所有的锁。但若这一批中的某些对象已被其他事务锁住，此时应对已被锁住对象进行开锁，宣布此次事务运行失败。但不致引起数据的变化。第71页/共76页72并发控制(3)二、利用互斥锁和共享锁实现顺序性：对于共享文件，是允许多个事务同时去读的，而利用互斥锁锁住文件时，则只允许一个事务去读。因此，利用互斥锁实现顺序性存在效率不高的问题。于是引入共享锁。若事务Ti获得了某对象Q的共享锁，则允许Ti去读Q，但不允许写。若Q已被互斥锁锁住，则Ti必须等待。但若Ti要对Q执行写操作，则还须获得互斥锁。若失败则等待；否则可对Q执行写操作。第72页/共76页73 重复数据的数据一致性问题（1）一、重复文件的一致性：为保证文件系统的可用性，有些系统为关键文件设置了多个重复拷贝，分别存储在不同地方。在有重复文件时，若一个文件被修改，则必须同时修改其他几个文件拷贝，以保证文件中数据的一致性。可采用两种方法：当一个文件被修改时，可查找文件目录，以得到另外几个拷贝的索引结点号，从这些i结点中找到个拷贝的物理位置，然后对他们做同样的修改。为新修改的文件建立几个拷贝，取代原来的文件拷贝。文件1 17文件2 22文件3 12文件4 84文件名 i结点 文件名 i结点 文件1171940文件2227291文件