索引顺序文件PPT课件

-,1,第七章文件管理,-,2,目标：掌握文件系统的基本概念和实现过程顺序文件、索引文件和索引顺序文件顺序文件：什么是顺序文件？如何对定长记录的顺序文件进行读/写操作？这种文件形式有何优缺点，它主要用于何种场合？索引文件：什么是索引文件？为什么要引入索引文件？索引文件采用何种文件组织形式？索引文件的优缺点是什么？索引顺序文件：什么是索引顺序文件？索引顺序文件是为了解决什么样的问题而引入的，如何对索引顺序文件进行检索？当文件非常大时又应如何处理？,本章要点（1/4）,-,3,目录管理文件控制块（FCB）：什么是FCB，什么是文件目录？FCB通常应包含哪些内容，它与文件之间存在着什么样的关系？索引结点：磁盘索引结点是为了解决什么问题而引入的，它与FCB、目录项之间存在着什么样的关系？为什么要引入内存索引结点，以及在内存索引结点中还应增加哪些数据项，原因是什么？单级目录和两级目录结构：在单级目录结构中应如何创建或删除文件，它在哪些地方无法满足对目录管理的要求，而两级文件目录是如何解决这些问题的？,本章要点（2/4）,-,4,目录管理多级目录结构：目录结构由单级发展为两级、并进一步发展为多级带来了哪些好处？应如何根据绝对路径名或相对路径名在多级目录结构中线性地检索一个文件或子目录，要创建或删除一个文件或子目录时应如何进行处理？,本章要点（3/4）,-,5,文件共享方式文件共享的主要目的是什么？基于索引结点的共享方式：是何种文件共享方式？如果不引入索引结点，而直接通过FCB来共享文件会产生什么问题？这种共享方式应如何进行文件的删除操作，它有何优缺点？利用符号链实现文件共享：是何种文件共享方式？当用户访问LINK类型的文件时，系统应如何进行处理，通过这种方式共享文件有何优缺点？,本章要点（4/4）,-,6,7.1文件和文件系统7.2文件的逻辑结构7.3文件目录7.4文件共享7.5文件保护,本章内容,-,7,概述,所有的计算机应用程序都要：存储信息，检索信息三个基本要求：能够存储大量的信息长期保存信息可以共享信息解决方法：把信息以一种单元即文件的形式存储在磁盘或其他介质上文件是通过操作系统来管理的包括：文件的结构，命名，存取，使用，保护和实现方法,-,8,用户观点：文件系统如何呈现在其面前：一个文件由什么组成，如何命名，如何保护文件，可以进行何种操作等等。操作系统观点：文件目录怎样实现，怎样管理存储空间，文件存储位置，磁盘实际运作方式(与设备管理的接口)等等。,概述,-,9,-,10,7.1文件和文件系统,-,11,7.1.1数据项、记录和文件,1、数据项基本数据项：是用于描述一个对象的某种属性的字符集数据名数据类型组合数据项：由若干个基本数据项组成2、记录一组相关数据项的集合关键字：能唯一地标识出记录的基本/组合数据项,-,12,3、文件文件系统：对文件进行操纵和管理的软件集合。文件：由创建者定义的、具有文件名的一组相关信息的集合。文件组成：文件体：文件本身的信息有结构文件（由若干相关记录组成）无结构文件（字符流）文件属性：文件存储和管理信息文件类型文件长度文件的物理位置文件的存取控制文件的建立时间,-,13,图7-1文件、记录和数据项之间的层次关系,-,14,7.1.2文件名和类型,1、文件名和扩展名,典型文件扩展名表,-,15,按用途分类系统文件：指由系统软件构成的文件，一般只允许用户调用，不允许用户读和写。用户文件：由用户的源代码、目标文件、可执行文件或数据等所构成的文件。库文件：指由标准子例程及常用的例程等所构成的文件。按存取控制属性分类只执行文件：只允许被核准的用户调用执行。只读文件：仅允许文件主及被核准用户对其进行读操作的文件，不允许写。读写文件：允许文件主及被核准用户对其进行读或写操作的文件。,2、文件类型,-,16,按文件中的数据形式分类源文件：是指从终端或输入设备输入的源程序和数据。目标文件（相对地址形式文件）：是指把源程序经过编译程序编译，但尚未经过链接程序链接的目标代码所构成的文件。可执行文件：是指由链接装配程序链接后所生成的可执行目标程序文件（用在非动态链接系统中）。按组织形式和处理方式分类普通文件：由ASCII码或二进制码组成的字符文件。目录文件：由文件目录组成的文件。特殊文件：特指系统中的各类I/O设备。,2、文件类型,-,17,文件管理系统管理的对象包括：文件目录磁盘（磁带）存储空间,7.1.3系统的层次结构,1、对象及其属性,-,18,该层实现的功能包括：对文件存储空间的管理对文件目录的管理将文件的逻辑地址转换为物理地址对文件读和写的管理对文件的共享与保护等四个软件层次：I/O控制层（设备驱动程序层）：主要由磁盘驱动程序组成基本文件系统：用于处理内存与磁盘之间数据块的交换基本I/O管理程序：用于完成与磁盘I/O有关的事务，如将文件逻辑块号转换为物理块号、管理磁盘中的空闲盘块等逻辑文件系统：用于处理与记录、文件相关的操作,2、对对象操纵和管理的软件集合,-,19,文件系统以接口的形式向上层用户一组对文件和记录操作的方法和手段：命令接口：用户与文件系统直接交互的接口，用户可以通过键盘终端输入命令取得文件系统的服务。程序接口：用户程序与文件系统的接口，用户程序通过系统调用取得文件系统的服务。,3、文件系统的接口,-,20,7.1.4文件操作,文件操作的典型功能，对整体文件而言：创建文件删除文件读文件写文件设置文件的读写位置,1、最基本的文件操作,-,21,2、文件的“打开”和“关闭”操作,“打开”：是指系统将指名文件的属性(包括该文件在外存上的物理位置)，从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号(或称为索引)返回给用户。“关闭”：是指把该文件从打开文件表中的表目上删除掉。对文件属性的操作有关目录的操作实现文件共享的系统调用对文件系统进行操作的系统调用,3、其他文件操作,-,22,7.2文件的逻辑结构,-,23,7.2文件的逻辑结构,文件的逻辑结构是从用户的观点出发，所观察到的文件组织形式，是用户可以直接处理的数据及其结构，它独立于物理特性，又称文件组织。文件的物理结构又称为文件的存储结构，是指文件在外存上的存储组织形式，与存储介质的存储性能、所采用的外存分配方式有关。对文件逻辑结构的要求访问性能：便于检索；便于修改存储性能：向物理存储转换方便，节省空间,-,24,7.2.1文件逻辑结构的类型,1、按文件是否有结构分类有结构文件（记录式文件）定长记录变长记录无结构文件（流式文件）以字节为单位，利用读/写指针进行访问。,-,25,2、按文件的组织方式分类顺序文件：由一系列记录按某种顺序排列所形成的文件，其中的记录可以是定长或变长记录，通常采用定长记录。（为何？因变长采用此方式查询速度慢）索引文件：为可变长记录文件建立一张索引表，为每个记录设置一个表项，以加速对记录的检索速度。索引顺序文件：为每个文件建立一张索引表时，按组对记录进行组织，只为每组记录中的第一条记录设置一索引项。,-,26,7.2.2顺序文件,1、顺序文件的排列方式串结构：按记录存入时间先后进行排列。检索时每次必须从头开始顺序结构：按关键字排序。有利于提高检索速度和效率，可用折半查找等方法检索。2、顺序文件的优缺点优点：批量存取时效率最高；顺序存储设备只能存储顺序文件。缺点：当文件很大时，查找和修改效率低；增加和修改记录困难、要求连续存储空间、必须事先知道文件的长度。,-,27,1、隐式寻址方式,7.2.3记录寻址,图7-3定长和变长记录文件,-,28,2、显式寻址方式这种方式可用于对定长记录的文件实现直接或随机访问通过文件中记录的位置对于定长记录：Ai=A0+iL对于变长记录：其中Li为第i条记录的长度，Ai为第i条记录的首址利用关键字通过指定关键字来查找记录,-,29,7.2.4索引文件,索引文件由变长记录组成的顺序文件不容易实现直接存取，因此，为其建立一有序的索引表，为主文件中的每条记录在索引表中分别设置一个表项，记录指向该记录的指针（即记录在逻辑地址空间的首址）以及记录的长度L。索引表按关键字排序，是一个定长记录的顺序文件对索引表可采用折半查找等方法，检索速度更快。特点：提高了速度，增加了存储开销放索引文件。增、删记录时，对索引表要作相应的修改。,1、按关键字建立索引,-,30,2、具有多个索引表的索引文件,图7-4索引文件的组织,为每种可能成为检索条件的域都配置一张索引表每一个索引表都按相应的一种属性或关键字进行排序,索引文件的优点：可直接存取，有较快的检索速度；文件的增删方便。索引文件的缺点：除主文件外，还需配置一张索引表，而且每一记录都要有一索引项，增加了存储费用。增加删除记录时，也需要修改索引表。,-,31,7.2.5索引顺序文件,克服了变长记录的顺序文件不能随机访问，以及不便于记录的删除和插入。记录是按关键字的顺序组织起来的引入了文件索引表：实现对索引顺序文件的随机访问增加了溢出文件：用于记录新增加、删除和修改的记录。,1、索引顺序文件的特征,-,32,索引顺序文件将顺序文件中若干记录分为一组；为顺序文件建立一张索引表，表中记录每个组的第一个记录，该索引项包含记录的键值和指向该记录的指针；为该组的其它记录设置了溢出区域，在溢出区域内记录按顺序文件方式组织。是顺序文件和索引文件的结合。索引顺序文件既适用于交互方式应用，也适用于批处理方式应用。检索方法：先根据关键字去检索索引表，找到该记录所在组的第一个记录的位置，然后再利用顺序查找法去查找主文件，找到所需记录。平均检索效率为,2、一级索引顺序文件,-,33,图7-5索引顺序文件,-,34,对于一个非常大的文件，检索时查找记录仍然很多，为了进一步提高检索效率，可以为顺序文件建立多级索引。平均检索效率为(3/2)。,3、两级索引顺序文件,-,35,7.2.6直接文件和哈希文件,键值转换：由记录键值到记录物理地址的转换。哈希文件是直接文件的一种。哈希函数：A=H(k）,1、直接文件,2、哈希(Hash)文件,图7-6Hash文件的逻辑结构,-,36,7.3文件目录,-,37,7.3文件目录,在现代计算机系统中，主要依赖于文件目录对文件实现快速、准确地查找。具有将文件名转换为该文件在外存的物理位置的功能。对目录管理的要求如下：实现“按名存取”。提高对目录的检索速度。文件共享。允许文件重名。,最基本的功能,大中型文件系统追求的主要目标,多用户系统的目标,-,38,7.3.1文件控制块和索引结点,定义：用于描述和控制文件的数据结构称之为文件控制块（FCB）；作用：文件管理程序借助于文件控制块中的信息，实现对文件的各种操作；目录：文件与文件控制块一一对应，而把文件控制块的有序集合称之为文件目录：目录文件：一个文件控制块就是一个文件目录项，通常一个文件目录也被看做是一个文件，称为目录文件；,-,39,基本信息文件名：文件物理位置：（设备号，盘块号，盘块数/文件长度）文件逻辑结构：流式记录式：定长、变长文件物理结构：顺序存储离散存储：链式、索引式,1、文件控制块FCB,-,40,存取控制信息类(安全性)文件主/核准用户/一般用户存取权限。使用信息类文件的建立日期/时间；文件上一次修改时间；当前使用信息。例：DOS,1、文件控制块FCB,图7-7MS-DOS的文件控制块,-,41,索引结点的引入：为何引入：文件多时，文件目录占用大量盘块（FCB太大），检索文件时只需用到文件名。解决方案：将文件名与文件信息分开。索引结点：含文件描述信息的数据结构。例：一个FCB为64B，一个盘块为1KB，假设文件系统中有3200个文件，文件目录需要多少个盘块存放？当要访问某文件时平均调度块数为多少？,2、索引结点,一个盘块能存放：1024/64=16个FCB,文件目录占据：3200/16=200个盘块,平均调度块数：(1+200)/2=100.5次,-,42,UNIX系统中将FCB分为文件名、i（index)节点指针和相应的i节点，其中文件名和i节点指针占16字节（14+2）离散存放目录结构查询时只调入文件名部分，找到后才调入相应节点。,2、索引结点,图6-15UNIX的文件目录,-,43,磁盘索引结点：文件主标识符：拥有文件的人或小组的标识符文件类型：_、d、c、b、p、l、s等文件存取权限：rwx文件物理地址：含有13个地址项，iaddr(0)iaddr(12)文件长度：以字节为单位文件连接计数：所有指向该文件名的指针计数文件存取时间：文件最近被访问、修改等的时间,2、索引结点,-,44,内存索引结点：文件打开后，将磁盘索引结点的内容部分或全部子集拷贝到内存，并增加以下内容：索引结点编号：用于标识内存索引结点；状态：指示i结点是否上锁或被修改；访问计数：每当有一进程要访问此i结点时，将该访问计数加1，访问完再减1；文件所属文件系统的逻辑设备号；链接指针：设置有分别指向空闲链表和散列队列的指针。,2、索引结点,-,45,图7-9单级文件目录,7.3.2简单的文件目录,新建文件：有无同名；加入目录表；状态位置1。删除文件：从目录中查找文件目录项；回收块；清除占用目录项。特点：简单速度慢；不允许重名；不便于共享。,1、单级目录结构,-,46,MFD+UFD新建与删除文件特点：提高了检索目录的速度：如n个用户，每用户最多m个文件，则最坏速度为n+m而非n*m在不同的用户目录中，可以使用相同的文件名不同用户还可使用不同的文件名来访问系统中的同一个共享文件缺点：不方便共享,2、两级文件目录,-,47,图7-10两级目录结构,2、两级目录,MFD,UFD,-,48,1、树形目录,7.3.3树形结构目录,图7-11多级目录结构,主目录(根目录),数据文件(树叶),其它目录(树的结点),-,49,在树形目录结构中，每一个文件都有一个从根到叶的路径。路径名：从根目录出发到某个文件的通路上所有各级子目录名和该文件名的顺序组合称为文件的路径名，在各级子目录名和文件名之间可用“/”隔开。,相对路径名：从当前目录开始直到数据文件为止所构成的路径名称。绝对路径名：从树根开始的路径名称MSDOS系统中文件路径名ARTBIUIDBPUNIX系统中文件路径名/A/R/T/B/IU/I/D/B/P,允许重名,2、路径名和当前目录,-,50,由于查找文件总是从根目录开始，因而查找的时间较长。事实上，用户在一段时间内会经常访问一个子目录下的文件。为了提高效率和方便用户，文件系统引进了“当前目录”的概念。系统初始启动后，当前目录就是根目录。当前目录可根据需要任意改变，用户可以用“改变当前目录”命令指定自己当前的工作目录。查找一个文件可从当前目录开始，使用相对路径名；当前目录一般存放在内存。,当前目录,-,51,创建目录删除目录不删除非空目录可删除非空目录改变目录移动目录链接操作查找,3、目录操作,-,52,7.3.4目录查询技术,实现按名存取用户文件的步骤：文件名目录项（FCB）或索引结点盘块号启动磁盘驱动程序首先，系统利用用户提供的文件名，找出该文件的文件控制块或索引结点；其次，根据查到的FCB或索引结点中所记录的文件物理地址（盘块号），换算出文件在磁盘上的物理位置；最后，启动磁盘驱动程序，将所需文件读到内存中。目前对目录的查询技术有线性检索法和HASH方法,-,53,线性检索法又称为顺序检索法在单级目录中，利用用户提供的文件名，用顺序查找法直接从文件目录中找到指名文件的目录项。在树型目录中，用户提供的文件名是由多个文件分量名组成的路径名，此时须对多级目录进行查找。,1、线性检索法,-,54,图7-12查找/usr/ast/mbox的步骤,实现按名存取用户文件的步骤：/usr/ast/mbox,1、线性检索法,-,55,2、Hash方法,哈希表算法：目录项信息存在一哈希表中，搜索时根据文件名计算哈希值，得到一个指向表中文件的指针处理此Hash转换中“冲突”的有效规则是：(1)在利用Hash法索引查找目录时，如果目录表中相应的目录项是空的，则表示系统中并无指定文件。(2)如果目录项中的文件名与指定文件名相匹配，则表示该目录项正是所要寻找的文件所对应的目录项，故而可从中找到该文件所在的物理地址。(3)如果在目录表的相应目录项中的文件名与指定文件名并不匹配，则表示发生了“冲突”，此时须将其Hash值再加上一个常数(该常数应与目录的长度值互质)，形成新的索引值，再返回到第一步重新开始查找。,-,56,7.4文件共享,-,57,7.4文件共享,文件共享与文件系统的保护（安全性）是文件系统中的一个重要问题，共享与安全性是一个问题的两方面。共享：一个文件被多个用户或程序使用，能节省大量辅存空间和主存空间，减少输入输出操作。文件共享应注意的问题：对各类欲共享文件的用户进行存取控制系统如何实现共享,-,58,7.4.1基于有向无循环图实现文件共享,1、有向无循环图DAG,如何建立D5、D3与共享文件F8之间的链接？,文件目录D6中包含文件的物理地址（即文件所在盘块的盘块号）。,进行共享文件链接时，必须将文件的物理地址拷贝到D5和D3的目录中去。,这样实现会有什么问题呢？,链接之后如果对文件F9添加了新内容，只有执行操作的目录才能看到改变，其他的目录对改动将不可见。,图7-13有向无循环图目录层次,-,59,图7-14基于索引结点的共享方式,引入索引结点，将文件的物理地址及其它的文件属性等信息存放在索引结点中。在文件目录中只设置文件名及指向相应索引结点的指针。索引结点中还有一个链接计数count，用于表示链接到本索引结点上的用户目录项的数目。,2、利用索引结点,-,60,图7-15进程B链接前后的情况,这种实现方式会存在什么问题呢？,计账系统对用户C将不公平！,-,61,7.4.2利用符号链接实现文件共享,1、利用符号链接的基本思想,图7-16使用符号链接的目录层次,文件F8有三个父目录，只有D6是它的主父目录。,属主结构是仍然简单树！方便对文件的删除、查找等。,-,62,建立一种特殊类型（Link）的文件，其内容是到另一个目录或文件路径的链接（建立符号链接文件，并不影响原文件，可以建立任意的别名关系，甚至原文件是在其他计算机上）3、利用符号链实现共享的优点文件主拥有指向索引结点的指针；共享该文件的其他用户只有该文件的路径(符号链接文件)用户访问被删除的共享文件时会导致访问失败，系统会将符号链接删除；计算机网络环境下可用：HTML文件中有许多链接符。,2、如何利用符号链实现共享,-,63,访问共享文件时，可能需要多次读盘，系统开销大；每个共享用户建立一个符号链（符号链接文件），需要配置一个索引结点，也需要耗费一定的磁盘空间。每一个共享文件都会有几个文件名，每个用户都使用自己的路径名访问共享文件。当遍历整个文件系统时，将会多次遍历到该共享文件。,4、利用符号链的共享方式存在的问题,-,64,7.5文件保护,-,65,7.5文件保护,影响文件安全性的主要因素：人为因素系统因素自然因素确保文件安全性的三方面措施：通过存取控制机制，防止人为因素造成的文件不安全性采取系统容错技术，防止系统部分的故障造成的文件不安全性；建立后备系统，防止自然因素造成的文件不安全性,-,66,7.5.1保护域,每一个进程仅能在保护域内执行操作，只允许进程访问它们具有“访问权”的对象。1、访问权为了保护系统中对象，由系统控制进程对对象的访问。访问权：一个进程能对某对象执行操作的权利。每个访问权可以用一个有序对（对象名，权集）表示。,-,67,2、保护域保护域：简称域，是进程对一组对象访问权的集合，进程只能在指定域内执行操作。域规定了进程能访问的对象和能执行的操作。,域1,F1R,F2RW,域2,域3,Printer1,F3R,F4RWE,F5RW,F6RWE,lW,Plotter2W,图7-17三个保护域,-,68,3、进程和域间的静态联系静态域：进程与域间一一对应，一个进程只联系一个域，在进程整个生命期中，其可用资源是固定的，这种域就叫“静态域”。特点：进程运行的全过程都受限于同一个域，这会使赋予进程的访问权超过了实际需要。4、进程和域间的动态联系方式动态域：进程与域间可以一对多，一个进程可以联系多个域，将进程的运行分为若干个阶段，每个阶段联系一个域，可以根据运行的实际需要规定，在进程每个阶段中所能访问的对象。动态联系方式：一对多的联系方式应增设保护域切换功能，使进行能在不同的运行阶段从一个保护域切换到另一个保护域。,比对预先静态分配法（AND型信号量）,比对动态申请资源（按需分配）,-,69,7.5.2访问矩阵,1、基本的访问矩阵访问矩阵：用一个矩阵描述系统的访问控制