第六章 文件系统课件.ppt

文件系统概念 文件逻辑结构与存取方法 文件的物理结构与存储设备 文件存储空间管理 文件目录管理 文件存取控制 文件使用 文件系统层次模型,第8章 文件系统(外存管理）,信息是计算机系统中的重要资源。文件系统是操作系统中的一个重要组成部分，负责信息的组织、存储和访问。 文件系统的功能就是提供高效、快速和方便的信息存储和访问功能。本章的主要内容就是信息的组织。,8.1 文件系统概念,图8.1操作系统的软硬件管理,8.1.1、文件系统的引入,方便的文件访问和控制：以符号名称作为文件标识，便于用户使用；并发文件访问和控制：在多道程系统中支持对文件的并发访问和控制；统一的用户接口：在不同设备上提供同样的接口，方便用户操作和编程；多种文件访问权限：在多用户系统中的不同用户对同一文件会有不同的访问权限；优化性能：存储效率、检索性能、读写性能；差错恢复：能够验证文件的正确性，并具有一定的差错恢复能力；,1、文件管理的目的,1. 文件概念,文件体：文件本身的信息文件说明：文件存储和管理信息；如：文件名、文件内部标识、文件存储地址、访问权限、访问时间等,文件是具有名字的一段程序或数据的集合，是相关字符流的集合或相关记录的集合 。文件名是文件的标识符号。文件包括两部分：,8.1.2 文件与文件系统的基本概念,文件系统是操作系统中管理文件的机构，是与管理文件有关的软件以及数据的统称，它负责为用户建立、撤销、读写、修改和复制文件，能提供文件存储和访问功能。,2. 文件系统基本概念,3、文件系统特点,友好的用户界面，用户只对文件操作，不管文件结构和存放的物理位置对文件按名存取，对用户透明某些文件可以被多个用户或进程共享使用磁盘、磁带或光盘等大容量存储器存储信息,按存放时限分类根据系统保留文件的时间：临时文件、永久文件和档案文件。按设备类型分类根据文件存储介质的设备类型：磁盘文件、磁带文件、卡片文件和打印文件等。按文件的组织结构分类文件的逻辑结构：流式文件和记录式文件。文件的物理结构（物理文件）：顺序文件、链接文件和索引文件等。,4、文件分类,按文件的性质和用途划分系统文件。用户只能调用，不能修改库文件。允许用户读取和执行，不允许修改用户文件。文件的建立者能够拥有所有的权限,4、文件分类（续）,按组织形式，文件划分为普通文件。包括系统文件、用户文件和库函数文件和实用程序等目录文件。由目录信息构成的特殊文件。特殊文件。所有输入、输出设备组成的文件，系统在对这些设备处理时，将其看成文件处理。,4、文件分类（续）,文件的分类是为了更好地管理和使用，这样，不仅提高了文件的存取速度，对文件的共享和保护也有利一般系统级与用户级要进行不同的管理，例如，一个系统文件工作时要读入内存，放在内存的某一固定区，有较高的保护级别，一般用户不允许进入。而一般用户的用户文件是在另外管辖的可用区有空闲时才能被调入指定的内存用户区,5、文件分类的原因,8.1.3 文件系统的结构和功能元素,1、 文件系统的结构,启动该设备上的I/O操作，处理I/O请求,处理与磁盘或磁带交换的数据块。,负责所有文件I/O的开始或结束。选择执行文件的I/O设备，外存的分配；,使用户和应用程序能够访问到记录。逻辑I/O处理的是文件记录。,在应用程序和文件系统及保存数据的设备之间提供了一种标准接口。,设备驱动程序：负责启动该设备上的I/O操作，处理I/O请求的完成。基本文件系统（物理I/O层）：处理与磁盘或磁带交换的数据块。基本I/O管理程序：负责所有文件I/O的开始或结束。选择执行文件的I/O设备，外存的分配。,2、文件系统结构元素,逻辑I/O：使用户和应用程序能够访问到记录。 物理I/O层处理的是数据块，逻辑I/O处理的是文件记录。它提供一种通用的记录I/O的能力。访问方法层 ：与用户最近的一层。在应用程序和文件系统及保存数据的设备之间提供了一种标准接口。不同的访问方法反映出不同的文件结构和访问数据的不同方法。,2、文件系统结构元素（续）,文件访问：文件的创建、打开和关闭，文件的读写；目录管理：用于文件访问和控制的信息，不包括文件内容文件结构管理：划分记录，顺序，索引访问控制：并发访问和用户权限限额(quota)：限制每个用户能够建立的文件数目、占用外存空间大小等审计(auditing)：记录对指定文件的使用信息（如访问时间和用户等），保存在日志中,3. 文件系统服务功能元素,4. 文件系统实现的功能模块,文件的分块存储：与外存的存储块相配合I/O缓冲和调度：性能优化文件定位：在外存上查找文件的各个存储块外存存储空间管理：如分配和释放。主要针对可改写的外存如磁盘。外存设备访问和控制：包括由设备驱动程序支持的各种基本文件系统如硬盘，软盘，CD ROM等,8.2 文件的逻辑结构与存取方法,文件组织讨论文件的内部逻辑结构，主要考虑因素是文件存储性能和访问性能。,8.2.1 文件的逻辑结构,文件逻辑结构的设计要求：访问性能：便于检索；便于修改存储性能：向物理存储转换方便，节省空间，可靠性，维护简单文件的不同组织层次：域、记录、文件,文件的逻辑结构是指从用户观点出发讨论文件内部的逻辑结构(logical structure)或用户访问模式；它可以独立于在外存上的物理存储。是用户可以直接处理的数据及其结构。,（1）无结构文件,文件体为字节流，不划分记录，顺序访问，每次读写访问可以指定任意数据长度。当前操作系统中常用的文件组织。,1、文件逻辑结构分类,概念：把文件中的记录按照各种不同的方式排列，构成不同的逻辑结构，方便用户对文件的各种操作。记录：一个具有特殊意义的信息单位，由该记录在文件中的逻辑地址（相对位置）与记录名所对应的一组关键字、属性及属性值组成。,（2）、有结构文件记录式文件,图8.2记录组成,典型记录的组成元素,连续结构多重结构转置结构,2、记录式结构文件分类,概念：把记录按生成的先后顺序连续排列的逻辑结构。特点：适用性强，可用于所有文件，记录的排列顺序与记录内容无关，有利于记录的追加和变更。缺点：查找性能比较差,（1）连续结构,概念把记录按关键字和记录名排列成行列式结构，则一个包含n个记录名、 m个关键字的文件构成一mn维行列式。特点能根据关键字和记录名快速定位某条记录缺点浪费空间，n条记录需要m*n的空间改进措施：采用多重队列。 将行列式中为0的项去除，以关键字ki为队首，以包含关键字ki的记录为队列元素构成一个记录队列。M个关键字就构成了多个队列。,（2）多重结构,文件记录式结构之多重结构及改进图,图8.3文件的记录名和关键字构成的行列式,图8.4文件的多重结构,概念把含有相同关键字的记录指针全部指向该关键字，即把所有与同一关键字对应的记录指针连续置于目录中该关键字位置，是对多重结构的变化,图8.5文件的转置结构,（3）转置结构,4、顺序结构（索引结构）,概念：按照某种关键字排序进行存放优点：能够根据待查记录的关键字快速找到某个记录,（1）累积文件pile堆文件,文件体为无结构记录序列，通过分隔符来划分记录，各记录大小和组成可变。新记录总是添加到文件末尾。如日志log，或电子邮件的邮箱文件(mailbox)。检索必须从头开始。是一种简单的文件组织方式，当数据难以组织时使用。,4、记录式文件结构具体实例,2、顺序文件,文件体为大小相同、格式固定的排序记录序列。它由一个主文件和一个临时文件组成。记录按某个关键字域(key field)排序，存放在主文件(master file)中。新记录暂时保存在日志或事务文件等临时文件中(log file or transaction file)，定期归并入主文件，并按正确顺序产生一个新文件。访问时可以采用二分搜索。,在顺序文件（主文件main file）的基础上，另外建立索引(index)和溢出文件(overflow file)。这样做的目的是加快顺序文件的检索速度。在索引文件中，可将关键字域中的取值划分若干个区间（如AZ可以划分为A到Z共28个区间），每个区间对应一个索引项，后者指向该区间的开头记录。新记录暂时保存在溢出文件中，定期归并入主文件。主文件中记录要求做到分块有序,3、索引顺序文件,3、索引顺序文件,索引顺序文件特点,特点通过划分层次，在记录数量较大时，比顺序文件大大缩短检索时间。顺序文件是N/2(这时可使用折半查找)，而索引顺序文件（一级索引）是i/2 + N/(2*i)，其中i为索引长度。索引还可以是多级的。如：有1000,000条记录的顺序文件的平均检索长度为500,000，而在添加一个有1000条索引项的索引文件后，平均检索长度为1000。索引顺序文件限制：基于文件的一个关键字域（属性）进行处理。当需要基于其他域而不是关键字域进行搜索一个记录时，将会受到限制；,直接访问磁盘中任何一个地址已知的块。记录大小相同。由主文件和溢出文件组成。记录位置由哈希函数确定。检索时给出记录编号，通过哈希函数计算出该记录在文件中的相对位置。访问速度快， 通常一次只访问一条记录。,5、哈希文件或直接文件,用户在一个文件上的操作：“读”和“写”。 写：存储介质 内存 读：内存 存储介质顺序存取法: 按照文件信息的逻辑顺序依次存取。按记录的排列顺序来存取。如：为了存取记录Ri , 必须先通过记录R1 R2 Ri-1 随机存取法(直接存取）:可以按任意的次序对文件进行读写操作。如可根据记录的编号来直接存取文件中的任意一个记录 索引存取：对文件中的记录按某个数据项的值进行排列，从而可以根据键值来快速存取。,8.2.2 文件的存取方法,概念又称索引存取，根据关键字来快速定位记录在文件中的位置，从而进行文件内容的修改。在具体的查找过程中，分为关键字搜索、记录的搜索或二者的结合搜索（见下图）,1、关键字存取法,对指定记录Ri的搜索过程如下：,对文件中的内容进行存取，根据记录是否根据关键字进行排序，可划分为线性搜索法散列法二分搜索法（1）线性搜索法特点：最简单、最直观的搜索法。从第一个记录开发搜索，直到找到或在未找到情况下搜索到最后一个记录结束。搜索时间复杂度和文件中记录长度成正比。缺点：搜索效率低。,2、记录搜索算法,定义：根据关键字，采用相应的散列函数，得到某个记录在文件中的逻辑地址。如果有两个关键字对应的地址相同，则采用再散列或其他方法来解决地址冲突问题。特点：能够根据关键字快速定位相同关键字的记录，在最理想情况下能够一次定位。,（2）散列法,概念：首先要根据关键字大小进行排序，每次取记录中间值和待查关键字进行比较，以此类推。,（3）二分搜索法,文件的使用:文件的性质决定了文件的使用，也决定了存取方式的选择。例如，如源程序文件用顺序存取法、数据库文件用随机存取法存储介质的特性 磁带：适合顺序存取。总是从磁头的当前位置开始读写磁带上的信息。磁盘：既可采用顺序存取方式，又可采用随机存取方式。,3、文件存取方法的相关因素,从文件在物理介质上的存放方式来研究文件。连续结构（顺序）串联结构索引结构,8.3 文件的物理结构与存储设备,一个文件的信息存放在若干连续物理块中 优点:简单，适用于一次性写入的操作 支持顺序存取和随机存取，顺序存取速度快 所需的磁盘寻道次数和寻道时间最少（因为由于空间的连续性，当访问下一个磁盘块时，一般无需移动磁头）,0,15,18,31,1、连续结构(顺序),缺点:文件不能动态增长（可能文件末尾处的空块已经分配给别的文件）不利于文件插入和删除外部碎片问题（反复增删文件后）,1.连续结构(顺序)（续）,类似于数组,1.连续结构存储图示,概念 一个文件的信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块。,思考：如何实现逻辑块号到物理块号的转换？,2、串联结构,类似于链表,2.串联结构图示,2.串联结构优缺点,优点 提高了磁盘空间利用率,不存在外部碎片问题 有利于文件插入和删除，但效率不高 有利于文件动态扩充缺点 存取速度慢，不适于随机存取 可靠性问题，如指针出错 更多的寻道次数和寻道时间 链接指针占用一定的空间,3、索引结构（考试重点）,概念 一个文件的信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构-索引表，并将这些块的块号存放在一个索引表中.,3.索引结构存储图,一个索引表就是磁盘块地址数组,其中第i个条目指向文件的第i块。（每个条目是逻辑块号与物理块号的映射，需要占据一定的外存空间）,思考 索引表的存放？ 大文件如何处理？,3.索引结构图示,3.索引结构优缺点,优点：保持了链接结构的优点,又解决了其缺点即能顺序存取,又能随机存取满足了文件动态增长、插入删除的要求（只要有空闲块）能充分利用外存空间缺点：较多的寻道次数和寻道时间.索引表本身带来了系统开销.如：内外存空间，存取时间,3.索引结构索引表组织（考试重点）,索引表组织多级索引:将一个大文件的所有索引表（二级索引)的地址放在另一个索引表（一级索引)中。,多重索引结构,图8.11 多重索引结构,每个文件的索引表为13个索引项，每项2个字节。前10项直接登记存放文件信息的物理块号（直接寻址）;第11项指向一个物理块，该块中最多可放256个文件物理块的块号（一次间接寻址）。第12和第13项作为二次和三次间接寻址;UNIX中采用了三级索引结构后，文件最大可达16兆个物理块（10+256+2562+2563）,UNIX文件系统采用的是多级索引结构(综合模式)。,作业思考题,1、 文件系统采用多重索引结构搜索文件内容。设块长为512字节，每个块号长3字节，如果不考虑逻辑块号在物理块中所占的位置，分别求二级索引和三级索引时可寻址的文件最大长度。,4.存取设备、存取方法和物理结构之间的关系,顺序存取设备：只有在前面的物理块被访问过之后，才能存取后续的物理块的内容。如 ：磁带直接（随机）存取设备：存取磁盘上任一物理块的时间不依赖于该物理块所处的位置，如 ：磁盘固定头磁盘：每个磁道设置一个磁头，变换磁道时不需要磁头的机械移动，速度快但成本高移动头磁盘：一个盘面只有一个磁头，变换磁道时需要移动磁头，速度慢但成本低,8.3.2 文件的存储设备,1、磁带顺序存储设备,图8.12磁带的结构,影响磁带设备的存取速度或数据传输率因素信息密度磁带速度块间间隙,2、直接存储设备（随机存取）,图8.13磁盘的结构,扇区Sector：介质划分的最小单位块(簇)Block：与内存交换数据的最小单位文件卷（Volume）：一个独立的可装卸的文件存储介质。一个卷被分成几个部分：如卷控制区、目录表区、文件存储区，卷资源表柱面Cyclinder磁道track物理地址形式：磁头号、磁道号、扇区号,2、直接存储设备（随机存取）图示介绍,2、直接存储设备（随机存取）,磁盘完成过程由三个动作组成：寻道（时间）：磁头移动定位到指定磁道。旋转延迟（时间）：等待指定扇区从磁头下旋转经过数据传输（时间）：数据在磁盘与内存之间的实际传输,光盘 光盘容量大，速度快，价格便宜，但一般不可写 可读写光盘驱动器价格贵，写过程很麻烦 光盘的空间结构与磁盘类似 磁带,预分配(preallocation)：创建时(这时已知文件长度)一次分配指定的存储空间，如文件复制时的目标文件。动态分配(dynamic allocation)：需要存储空间时才分配（创建时无法确定文件长度），如写入数据到文件。,1. 新创建文件的存储空间（文件长度）分配方法,8.4 文件存储空间管理(分配与回收）,2. 文件存储单位: 簇（cluster）,簇的大小簇较大：提高I/O访问性能，减小管理开销；但簇内碎片浪费问题较严重；簇较小：簇内的碎片浪费较小，特别是大量小文件时有利；但存在簇编号空间不够的问题（如FAT12、16、32）；,文件的存储空间通常由多个分立的簇组成，而每个簇包含若干个连续的扇区(sector)。,2. 文件存储单位: 簇（cluster）,簇的分配方法：两种簇大小可变，其上限较大：I/O访问性能较好，文件存储空间的管理困难（类似于动态分区存储管理）簇大小固定，较小：文件存储空间使用灵活，但I/O访问性能下降，文件管理所需空间开销较大,3. 文件存储空间管理方法,连续分配(contiguous)：只需记录第一个簇的位置，适用于预分配方法。链式分配(chained)：在每个簇中有指向下一个簇的指针。索引分配(indexed)：文件的第一个簇中记录了该文件的其他簇的位置。,3、磁盘空闲空间管理方法,位示图(bitmap) : 块寻址算法空闲空间链接(chained free space)： 扩展：成组链接法空闲文件目录：在一个空闲簇中记录其他几个空闲簇的位置。,返回,磁盘空闲空间管理的数据结构通常称为磁盘分配表， 分配的基本单位是簇。 空闲空间的三种管理方法：,可以上述方法结合，应用于不同的场合。如：位示图应用于索引结点表格，链接和索引结合应用于文件区的空闲空间。,1.空闲文件目录,将文件存储设备上的每个连续空闲区看作一个空白文件，系统为所有空白文件单独建立一个目录。每个空白文件在这个目录中占用一个表目。表目的内容包括第一个空白块的地址（物理块号），空白块的数目。如：分配和回收过程：扫描目录，找到符合条件的项。,思考：空闲文件目录存储在哪里？,2.空闲块链,在每个空白块中建立一个链接指针，指向下一个空白块的位置，从而将所有空白块链接在一起，设置一个头指针指向空白块链的第一个物理块。分配时，从头指针的位置依次取下几块空白块分配给文件，当撤消文件时，回收。内存消耗少，但遍历的效率低，I/O负担重。改进的方法是成组链法。,Y,W,Z,首指针X,X,Y,W,Z,改进：一块中存放多个空闲块的块号，成组块链法？,（1）空闲块链链接方法,按空闲区大小顺序链接按释放顺序链接以上两种链接方法需要消耗一定的系统开销成组链接法相对于前面两种链接法有优势,（2）成组链法的工作原理,图8.14成组链法的组织,成组链法的工作原理（续）,空闲存储设备的分组处理（1）把文件存储设备的所有空闲块按50块划分为一组，组的划分从后往前进行；（2）每组的第一块用来存放前一组中各块的块号和总块数，总块数基本固定为50；（3）第一块为49，因为第一组前面没有其他组；最后一组有可能不够50，存储设备的空闲块不一定是50的倍数，该组的物理块号和总块数放在文件资源管理表中,成组链法的工作原理（续）,成组链法的分配和释放（1）系统启动，文件资源管理表复制到内存，在内存中存放最后一组空闲块的块号和总块数的堆栈，在内存中进行空闲块的分配和释放；（2）在分配和释放空闲块中始终有堆栈指针为Ptr，Ptr的初始值为该组空闲块的总块数，在分配时该指针值减1；（3）当堆栈中只剩下最后一个空闲块号时，系统启动设备管理程序，将下一组的块号和总块数读入内存，并重设Ptr指针大小；（4）在删除文件进行空间回收时，Ptr值加1；当Ptr值为50，当有新的块需要回收时，回收该块；然后Ptr值重设为1另起一个新组。,3、位示图,（1）每个存储设备都需要设置一个位示图（2）原理 1）系统从内存中画出若干个字节，为每个文件存储设备建立一张位示图 2）在位示图中，每个文件存储设备的物理块都对应一个比特位；如果该位为0， 表示所对应的物理块为空闲；如该位为1，则表示所对应的块已被分配出去。,4、文件卷,磁盘分区(partition)：通常把一个物理磁盘的存储空间划分为几个相互独立的部分，称为分区。文件卷(volume)：或称为逻辑驱动器(logical drive)。在同一个文件卷中使用同一份管理数据进行文件分配和外存空闲空间管理，而在不同的文件卷中使用相互独立的管理数据。一个文件不能分散存放在多个文件卷中，其最大长度不超过所在文件卷的容量。通常一个文件卷只能存放在一个物理外设上（并不绝对），如一个磁盘分区或一盘磁带。分区和文件卷的关系,4、文件卷,格式化(format)：在一个文件卷上建立文件系统，即：建立并初始化用于进行文件分配和外存空闲空间管理的管理数据。通常，进行格式化操作使得一个文件卷上原有的文件都被删除。扩展文件卷集(extended volume set)：一个文件卷由一个或几个磁盘上的多个磁盘分区依次连接组成。可以容纳长度大于磁盘分区容量的文件。实例：Windows NT中的扩展文件卷集。,思考：磁盘格式化需要做那些事情？,目录内容 目录结构类型 文件别名的实现,目录（文件）是由文件说明组成的用于文件检索的特殊文件。为了有效的利用存储空间及迅速准确的完成由文件名到文件物理块的转换，必须将文件名及其结构信息等按一定的组织结构排列，以方便文件的搜索。文件目录的管理解决：存储空间的有效利用、快速检索、文件命名冲突、文件共享等问题。,8.5 文件目录管理,8.5.1 目录内容,文件的组成（1）组成部分：文件说明和文件体（2）文件体：文件本身信息，包括记录式或字符式文件中内容（3）文件说明：又叫文件控制块（FCB)，至少包括文件名、与文件名相对应的文件内部标识符、文件信息在存储设备上的第一个物理块地址、文件逻辑结构、物理结构、存取控制和管理信息。（4）目录文件：由多个文件说明组成（5）文件系统利用目录文件完成按名存取和对文件信息的共享与保护,8.5.1 目录内容,文件名：有多个别名(alias)别名的数目文件类型：可有多种不同的划分方法，如： 有无结构（记录文件，流式文件） 内容（二进制，文本） 用途（源代码，目标代码，可执行文件，数据） 属性attribute（如系统，隐含等） 文件组织（如顺序，索引等） 按组织形式分：目录文件、特殊文件、普通文件,目录的内容是文件属性信息(properties),1、基本信息,8.5.1 目录内容,2、地址信息,存放位置：包括哪个设备或文件卷volume，以及各个存储块位置；文件长度（当前和上限）：以字节、字或存储块为单位。,3、访问控制信息,文件所有者（属主）：通常是创建文件的用户，或者改变已有文件的属主；访问权限（控制各用户可使用的访问方式）：如读、写、执行、删除等；,8.5.1 目录内容（续）,4、 使用信息,创建时间 最后一次读访问的时间和用户 最后一次写访问的时间和用户,8.5.2 文件目录类型,目录结构讨论目录的组织结构 设计目标是提高检索效率。,1、单级目录,整个目录组织是一个线性结构，系统中的所有文件都建立在一张目录表中。它主要用于单用户操作系统。它具有如下的特点：结构简单；文件多时，目录检索时间长；有命名冲突：如重名(多个文件有相同的文件名) 或别名(一个文件有多个不同的文件名),单级目录的读写处理过程,在根目录下，每个用户对应一个目录称为第二级目录；在用户目录下是该用户的文件，而不再有下级目录。不同用户的目录的有关信息存放在主目录中MFD，用户文件的说明信息所组成的目录文件被称为用户文件目录（UFD）,2、 二级目录,二级目录结构图,二级目录特点,适用于多用户系统，各用户可有自己的专用目录。 提高了文件的检索速度 部分的允许文件名重名便于文件共享思考题：说说二级目录为什么比单级目录有更高的搜索速度？,一级目录,根目录,ZImage,bash,more,root,zhao,Qian,readme,Z1.c,Z2.c,二级目录,2. 二级目录,3、多级目录,也称为树状目录(tree-like)。目录名：可以修改。目录树：中间结点是目录，叶子结点是目录或文件。目录的上下级关系：当前目录(current directory, working directory)、父目录(parent directory)、子目录(subdirectory)、根目录(root directory)等；路径(path)：绝对路径，相对路径,文件系统的多级目录树形结构,多级目录特点,适用于较大的文件系统管理。目录级别太多时，会增加路径检索时间。既能方便用户查找文件，又可以将不同类型和不同用途的文件分类允许文件重名查找速度加快（比单级、二级查找速度都快）,目录查询速度对比,假如有一个文件系统有1000个文件，系统中有10个用户，假定平均每个用户100个文件，问一级索引和二级索引平均查找时间复杂度为多少？,3、 多级目录,8.5.3 便于共享的文件目录,文件共享：多个用户可以访问同一个文件副本，而一个被共享的文件只需要在存储设备中只要保持一个副本即可。文件共享方法绕道法链接法基本文件目录表,1、绕道法,用户文件固有名：由用户当前目录到信息文件通路上所有各级目录的目录名加上该信息文件的符号名组成。共享实现原理：用户从当前目录出发向上返回到与所要共享文件所在路径的交叉点，再顺序下放到共享文件；另外需要用户指定所要共享文件的逻辑位置。,1、绕道法（续）,2、链接法（文件别名法）,提供文件共享的方法有两种：各用户通过唯一的共享文件的路径名访问共享文件；如：C:WINDOWSSYSTEMEDIT.EXE该方法的访问速度慢，适用于不经常访问的文件共享；利用多个目录中的不同文件名来描述同一共享文件，即文件别名，该方法的访问速度快，但会影响文件系统的树状结构，适用于经常访问的文件共享，同时存在一定的限制。 文件别名的实现方法有以下两种：,2、链接法（文件别名法）,链接（一处存储而多处出现）： 指一个文件或目录在目录树中多处出现，但实际在外存介质上只有一份物理存储。Unix下，建立链接的命令是ln。如：ln /usr/lib/mad /lib：含义是：使/usr/lib下的mad文件在/usr/lib 和/lib下都出现，但实际上mad文件在盘上只有一份物理存储。,（1）. 基于索引结点(index node)的文件别名,UNIX举例：ln source target,硬链接（hard link）的方法；硬链接允许从多个路径来指向同一个文件和目录。如果已有一个文件为C:HomeDocNtBookChap5.doc，且为其创建一个硬链接为C:chap5.doc，那么这两个路径指向同一文件.基于改进的多级目录结构，将目录内容分为两部分：文件名和索引结点。通过多个文件名链接(link)到同一个索引结点. 别名的数目记录在索引结点的链接计数中，若其减至0，则文件被删除。,（2）. 基于符号链接(symbolic link, shortcut)的文件别名,UNIX举例：ln -s a b ; rm a则文件a不存在，b能被控制但无法访问。若a是目录，ln -s /user/a /tmp/b则cd /tmp/b ; cd .是进入目录/user而不是/tmp；Windows的快捷方式缺点：空间和时间开销更大。如果设置不当，上下级目录关系可能会形成环状。,它是一种特殊类型的文件，其内容是到另一个目录或文件路径的链接。建立符号链接文件，并不影响原文件，实际上它们各是一个文件。可以建立任意的别名关系，甚至原文件是在其他计算机上。,8.3.3 文件别名的实现,（3）、硬链接与符号链接的比较,硬链接只允许文件链接，不允许目录链接；只允许在同一个文件系统范围内进行，不允许跨文件系统。删除文件时，如果还有其他链接链至该文件，则该文件不能被删除。符号链接虽然实现起来相对麻烦一些，访问速度相对慢一些，但适用范围和灵活性要大一些。允许目录链接，运行在不同的文件系统间进行链接，这两个文件系统可以在同一个计算机上，也可以在不同的计算机上。被链接文件的删除和符号链接的删除是完全相互独立的（返回“被链接文件不存在”的错误）,3、基本文件目录表,为了便于目录文件共享，可把目录中的文件说明（文件描述符）信息分成两个部分，形成分体式目录结构：符号文件目录（SFD）：由文件名和文件内部标识组成的树状结构，按文件名排序；基本文件目录（BFD，索引节点目录）：由其余文件说明信息组成的线性结构，按文件内部标识排序；,采用基本文件目录和符号文件目录的多级目录结构,文件系统中预设目录,基本文件目录空白文件目录主目录（MFD)：内容主要是用户信息符号文件目录：每个用户都有一个,基于BFD和SFD多级目录文件打开步骤,（1）把主目录MFD中的相应表目，也就是与待打开文件相关系的有关表目复制到内存；（2）根据（1）所复制得到的标识符，再复制此标识符所指明的基本文件目录表BFD的有关表目；（3）根据（2）所得到的子目录说明信息搜索SFD，以找到与待打开相对应的目录表项；（4）根据（3）所搜索到的文件名所对应的内部标识符id，把相应的BFD的表目项复制到内存,8.5.4 目录管理,目录文件：由文件说明信息或目录管理说明信息组成目录存放位置对查找文件的影响全部存放在外存全部存放在内存部分在内存，部分在外存需要两种操作，将需要的文件目录调入内存，将用户不再需要的文件目录移到外存,文件目录的打开和关闭,文件目录打开（fopen） 把文件存储设备上的目录文件复制到内存的操作文件目录关闭（fclose） 删除文件的内存副本的操作,常见目录管理操作,进行文件访问和控制时，由操作系统自动更新目录内容目录创建mkdir，删除rmdir，修改目录名rename。只适用于超级用户：mknod（建立文件目录项）和unlink（删除目录项）修改当前目录chdir；,目录管理是指目录访问和目录属性控制。,4. 文件系统实现时的相关表目,内存中所需的表目系统打开文件表：放在内存，用于保存已打开文件的FCB。此外，文件号，共享计数，修改标志；用户打开文件表：每个进程一个，包括文件描述符，打开方式，读写指针，系统打开文件表入口；而且，进程的PCB中，记录了用户打开文件表的位置,用户打开文件表与系统打开文件表之间的关系： 用户打开文件表指向系统打开文件表。 如果多个进程共享同一个文件，则多个用户打开文件表目对应系统打开文件表的同一入口,4. 文件系统实现时的相关表目,8.6 文件存取控制,文件的访问控制文件的访问权限 文件的并发访问,与文件共享、文件保护、文件保密有关。文件共享:不同的用户共同使用一个文件文件保护:防止文件内容被破坏文件保密:未经文件拥有者许可，任何用户不得访问该文件文件系统应作到：对拥有权限的用户，应该让其进行相应操作，否则，应禁止防止其他用户冒充对文件进行操作由存取验证模块来实现,1、文件存取控制相关概念,分三步来实现：审定用户的存取权限比较用户权限的本次存取要求是否一致将存取权限和访问文件的保密性比较，看是否有冲突,2、存取验证模块实现步骤,3、文件存取控制方法,一般有4种方法来验证存取控制矩阵存取控制表口令密码术,特点：简单；但当文件和用户较多时，存取控制矩阵变大，增加占用空间和扫描时间开销,（1）存取控制矩阵,特点：以文件为单位，把用户按某种关系划分为若干组，同时规定每组的存取权限。实现时，该表放在文件说明中，打开文件时，被复制在内存中；效率高；,（2）存取控制表,（3）口令方式,类型 1）系统口令 分为超级用户和普通用户，超级用户拥有完全权限，普通用户只能操作属于自己的文件，一个用户只需要一个口令 2）文件口令 为每个用户文件设置口令，需要多个口令进行文件信息保护，能做到文件共享和保密特点 1）占用内存少，验证口令时间短 2）保密性差 3）不太容易管理口令，特别是文件口令,（4）密码方式,1）工作方式 在用户创建源文件并将其写入存储设备是对文件进行编码，在读出文件时对其进行译码解密。2）代码键（KEY)在加解密时需要该代码。,图8.22加密解密过程,3）特点保密性强，代码键由用户指定，在存取需要耗费一定时间,8.6.2 文件的共享,定义:一个文件被多个用户或程序使用。三种共享形式： 被多个用户使用，由存取权限控制 被多个程序使用，但各用自己的读写指针 被多个程序使用，但共享读写指针目的 节省时间和存储空间，减少了用户工作量； 进程间通过文件交换信息,文件访问 文件控制,这一部分讨论操作系统提供的与文件系统相关的API。,8.7 文件的使用,1. 打开文件-Open,为文件读写所进行的准备。给出文件路径，获得文件句柄(file handle)，或文件描述符(file descriptor)。需将该文件的目录项读入到内存中。这样的文件称为活动文件或打开的文件内存中存放打开文件的SFD表目的表称为活动名字表，每个用户一张，把内存中存放活动文件的BFD表目的表称为活动文件表，这个表整个系统一张。,文件访问是指围绕文件内容读写进行的文件操作,1. 打开文件-Open,使用文件的第一步，任何一个文件使用前都要先打开，即把FCB送到内存（如：fd=open（文件路径名，打开方式）（1）根据文件路径名查目录，找到FCB主部；（2）根据打开方式、共享说明和用户身份检查访问合法性；（3）根据文件号查系统打开文件表，看文件是否已被打开； 是，则共享计数加1 否则将外存中的FCB主部等信息填入系统打开文件表空表项，共享计数置为1；（4）在用户打开文件表中取一空表项，填写打开方式等，并指向系统打开文件表对应表项。返回信息：fd：文件描述符，是一个非负整数，用于以后读写文件。,2. 关闭文件-Close,释放文件描述符，把该文件在内存缓冲区的内容更新到外存上。,3. 其它文件访问,复制文件句柄dup：用于子进程与父进程间的文件共享，复制前后的文件句柄有相同的文件名、文件指针和访问权限；读read、写write和移动文件读写指针lseek：系统为每个打开文件维护一个读写指针(read-write pointer)，它是相对于文件开头的偏移地址(offset)。读写指针指向每次文件读写的开始位置，在每次读写完成后，读写指针按照读写的数据量自动后移相应数值。执行exec：执行一个可执行文件；修改文件的访问模式（fcntl和ioctl）：提供对打开文件的控制，如：文件句柄复制、读写文件句柄标志、读写文件状态标志、文件锁定控制、流（stream）的控制；,文件控制,创建（creat和open）：给出文件路径，获得新文件的文件句柄；删除unlink：对于symbolic link和hard link，删除效果是不同的；获取文件属性（stat和fstat）：stat的参数为文件名，fstat的参数为文件句柄；修改文件名rename；修改文件属主chown，修改访问权限chmod：与相应系统命令类似；文件别名控制：创建symlink或link，读取链接路径readlink；,文件控制是指围绕文件属性控制进行的文件操作。,文件控制,例：create（文件名，访问权限，最大长度）检查参数的合法性：文件名是否符合命名规则 是，继续；否则错误返回检查同一目录下有无重名文件：无则继续；有则错误返回在目录中有无空闲位置:有则继续，否则不成功返回;(有的系统可能要为此文件申请数据块空间,申请一部分或一次性全部申请）填写目录项内容： 文件名，用户名等，存取权限，长度置零，（，首址）返回,建立文件：实质是建立文件的FCB，并建立必要的存储空间，分配空FCB，根据提供的参数及需要填写有关内容，返回一个文件描述；,3 文件的访问权限,文件访问类型读read：可读出文件内容写write（修改update或添加append）：可把数据写入文件执行execute：可由系统读出文件内容，作为代码执行删除delete：可删除文件修改访问权限change protection：修改文件属主或访问权限,设置文件访问权限的目的是为了在多个用户间提供有效的文件共享机制,4 文件的并发访问,访问文件之前，必须先打开文件如果文件的目录内容不在内存，则将其从外存读入，否则，仍使用已在内存的目录内容。多个进程访问同一个文件都使用内存中同一个目录内容，保证了文件系统的一致性。文件锁定(file lock)：可以协调对文件指定区域的互斥访问。利用进程间通信，协调对文件的访问；,文件并发访问控制的目的是提供多个进程并发访问同一文件的机制。,回答,用户存取请求,read(sqrt,7,1500),Call sfs(read,sqrt,7,1500),Call bfs(read,5,7,1500),Call acv(read,10,7,1500),Call lfs(read,10,7,1500),Call lfs(read,10,3,1500),Call pfs(read,10,3, 500),