计算机操作系统课件(第四版)第7.8章

第七章文件管理第一节文件和文件系统第二节文件的逻辑结构第三节文件目录第四节文件共享17.1文件和文件系统OS通过文件系统来组织和管理计算机中存储的大量数据和程序。7.1.1文件、记录和数据项7.1.2文件类型和文件系统模型7.1.3文件操作27.1.1、文件、记录和数据项基于文件系统的概念，可以把数据组成分为数据项、记录和文件三级文件记录1记录2记录n数据项1…………数据项2数据项n3例1：学生成绩单学号姓名语文数学英语物理化学001张三9085799278002李四8691869082003王五8887848975004赵六7892958791005周七8588969090数据项文件记录41.数据项基本数据项：描述一个对象的某种属性的字符集组合数据项：由若干个基本数据项组成2.记录记录是一组相关数据项的集合，用于描述一个对象的某些属性。关键字：能够唯一标识一个记录的数据项53.文件是指由创建者所定义的、具有文件名的一组相关数据元素的集合；文件的属性：文件类型、文件长度、文件的物理位置、文件的建立时间等。61、文件的类型1）按文件的性质和用途分：系统文件：由系统软件构成的文件，只允许调用执行，不允许用户读和修改。用户文件：只允许文件的授权者使用。库文件：允许用户调用不允许修改。7.1.2、文件类型和文件系统模型72）按文件中数据的形式分：源文件、目标文件、可执行文件3）按存取控制属性分：只执行文件、只读文件、读写文件4）按组织形式和处理方式分：普通文件：ASCII码或二进制码组成的字符文件目录文件：由文件目录组成特殊文件：系统中的各类I/O设备82、文件系统模型1)对象及其属性文件：文件管理的直接对象目录：方便用户对文件的存取和检索磁盘（磁带）存储空间对象及其属性对对象操纵和管理的软件集合文件系统接口用户（程序）9例：MS-DOS的目录结构盘块数首盘块号日期时间备用属性扩展名文件名f1exe只读……………f2…………………f3f4103)文件系统的接口命令接口：用户与文件系统的接口程序接口：用户程序与文件系统的接口2)对对象操纵和管理的软件集合（核心）功能：对文件存储空间、文件目录的管理、地址转换机制、文件读写、文件的共享与保护。对象及其属性对对象操纵和管理的软件集合文件系统接口117.1.3、文件操作用户通过文件系统提供的系统调用实施对文件的操作1、最基本的文件操作1）创建文件：分配外存空间建立目录项2）删除文件：删除目录项回收外存空间3）读文件：文件名、内存目标地址、目录项、读指针4）写文件：文件名、内存中源地址、目录项、写指针122、文件的打开与关闭打开：系统将指名文件的属性（包括文件在外存的物理位置）从外存拷贝到内存打开文件表的一个表目中，将表目编号返回用户关闭：将文件从打开文件表的表目上删除，释放表目空间3、其它操作对文件属性的操作：改变文件名、文件主、访问权对文件目录的操作：创建、删除目录等137.2文件的逻辑结构文件逻辑结构是从用户角度观察到的文件组织形式文件物理结构是文件在外存上的存储组织形式文件逻辑结构的类型顺序文件索引文件索引顺序文件14提高检索速度便于修改减少文件占用的存储空间对文件逻辑结构提出的基本要求：157.2.1、文件逻辑结构的类型1、有结构文件（记录式文件）1）定义：由一个以上的记录构成的文件2）基本分类：定长记录、变长记录3）文件的组织：顺序文件：一系列记录按某种顺序排列形成索引文件：记录为变长，每个记录一个索引表项索引顺序文件：每组记录的第一个记录设一表项162、无结构文件（流式文件）定义：由字符流构成的文件大量的源程序、可执行文件、库函数等文件长度以字节为单位对流式文件的访问采用读写指针指出下一个要访问的字符UNIX系统中所有文件都被看作是流式文件177.2.2、顺序文件1、逻辑记录的排序串结构(以时间排序)、顺序结构（按关键字排序）2、对顺序文件的读/写操作1）定长记录：Rptr:=Rptr+L2）变长记录：Rptr:=Rptr+LiR0R1R2…Ri-----0-----L-----2L-----3L-----iLLRptr-----0L0R0…LiRi-----L0+1-----(L0+1)+…+(Li-1+1)-----(L0+1)+…+(Li+1)L0Rptr-----1183、顺序文件的优缺点：1）优点：适于批量存取、能用于磁带存储2）缺点：查找/修改/增/删单个记录效率低，系统开销大R0R1R2…Ri-----L-----2L-----3L-----iLLRptr顺序文件197.2.3、索引文件2、索引表本身是一个定长记录的顺序文件索引号（记录键或关键字）长度指针索引号长度指针0m0xx1m1xx2m2xx………imixx………………………索引表R0R1R2…Ri………逻辑文件1、利用定长记录的顺序文件访问变长记录的文件检索时，利用用户程序提供的关键字和查找算法，检索索引表，访问主文件的记录。向索引文件中增加新记录时，需修改索引表。207.2.4、索引顺序文件索引顺序文件是顺序文件和索引文件的结合，是最常见的一种逻辑文件形式。原理：1）顺序文件中的所有记录分为若干个组；2）为顺序文件建立一张索引表，在索引表中为每组中的第一个记录建立一个索引项；21索引键逻辑地址AAABAAACAA……………………………………………………索引表AAAAABDAAC…………BAAA…………CAA…………逻辑文件主键其它属性检索时，利用用户程序提供的关键字和查找算法，检索索引表，….，利用顺序查找法查找主文件227.2.5、直接文件和哈希文件1、直接文件前述文件结构对记录进行存取时，都需利用给定的记录键值（关键字），对线性表或链表进行建设，以找到指定记录的物理地址。直接文件：根据给定的记录键值，直接获得物理地址。即记录键值本身决定了记录的物理地址键值转换——由记录键值到记录物理地址的转换232、哈希文件是目前应用最广泛的一种直接文件。利用hash函数，将记录键值转换为相应记录的地址。为了能实现文件存储空间的动态分配，由Hash函数所求得的并非是相应记录的地址，而是指向一目录表相应表目的指针，该表目的内容指向相应记录所在的物理块。例如，Hash函数A=H(K)K:记录键值A：该记录在目录表中对应表目的位置键值Hash函数f247.3文件目录目录管理的要求文件控制块和索引结点目录结构目录查询技术25目录管理的要求目录：用于标识系统中文件及其物理地址的一种数据结构，供检索使用。目录管理的要求：实现“按名存取”——最基本的功能提高对目录的检索速度文件共享允许文件重名267.3.1、文件控制块和索引结点1、文件控制块（FCB）定义：描述和控制文件的数据结构FCB的有序集合称为文件目录（或目录文件）FCB包含的信息项基本信息：文件名/物理位置/逻辑结构/物理结构存取控制信息：不同用户存取权限不同使用信息：建立/修改的日期、时间等盘块数第一块号日期时间备用属性扩展名文件名MS-DOS的FCB272、索引结点1）索引结点的引入：文件很多时，目录文件占用大量盘块。查找目录时要多次启动磁盘，顺序读取存放目录文件的盘块。实际上，检索目录文件时，只需要利用文件名进行查找，所以可以给文件目录瘦身。UNIX系统中，把文件名和文件描述信息分开，由文件描述信息单独构成索引结点（简称i结点）FCB改变为：文件名＋指向i结点的指针28文件名索引结点编号文件名1文件名2……0131415UNIX的文件目录292）磁盘索引结点：（每个文件唯一）文件主标识符：标识文件拥有者文件类型文件存取权限文件物理地址：每个索引结点有13个地址项，直接或间接给出盘块号文件长度文件连接计数：所有指向该文件的文件名的指针计数文件存取时间：文件最近被存取修改的时间和索引结点被修改的时间。303）内存索引结点：存放在内存中的索引结点。当文件被打开时，要将磁盘的索引结点拷贝到内存的索引结点中。增加了以下内容：索引结点编号、状态、访问计数、文件所属文件系统的逻辑设备号、链接指针317.3.2、目录结构1、单级目录结构在整个文件系统中建立一张目录表，每个文件占一个目录项。目录项包括：文件名、扩展名、长度、类型、物理地址及其它文件属性。……………………xxxxxxxxxxxx文件名2xxxxxxxxxxxx文件名1状态位文件说明物理地址文件名表明目录项是否空闲32•单级目录结构新建文件时，要检索所有目录项，保证新文件名唯一。建立新表项，置状态位为1。删除文件时，找到目录项，回收空间，清除目录项优点：简单、能实现按名存取缺点：查找速度慢；不允许重名；不便于文件共享，只能适用于单用户环境。……………………xxxxxxxxxxxx文件名2xxxxxxxxxxxx文件名1状态位文件说明物理地址文件名表明目录项是否空闲332、两级目录结构为每个用户建立一个单独的用户文件目录，由用户的所有FCB组成。系统中再建立一个主文件目录。每个用户的目录文件占一个目录项。xxxxSun…………xxxxWangxxxxZhang指向子目录指针用户名TestAlphaTestReportmisxDeviceBetaAlphaTestReportTestDeviceBetaMisxMFDUFD34•两级目录结构用户可请求系统为自己建立UFD，也可请求系统将其撤消。新建用户文件时，OS检查用户UFD—文件名，建立新表项。删除用户文件时，OS查找用户UFD—文件目录项，回收存储空间，删除目录项。优点：提高检索目录的速度不同的用户目录中文件可以同名35•3、多级目录结构（树型目录结构）1）目录结构：大型文件系统采用三级或三级以上的目录结构。CBADBADEFAGCAKNJKMJFHA123456789101112131415161718192021ab36•多级目录结构2）路径名：从根目录到任何数据文件，都有一条唯一的通路，把全部目录文件名和数据文件名，依次用“/”链接起来，构成该数据文件的路径名（绝对路径）。如：B/E/J•3）当前目录：进程在一定时间内所访的文件仅限于某个文件目录之下，该文件目录可设置为当前目录。把从当前目录开始直到数据文件为止构成的路径名叫做相对路径。例如：用户B的当前目录是E，则可使用相对路径名“J”来访问自己的J文件。37•4）增加和删除目录增加目录：用户可为自己建立UFD，并可再创建子目录。创建文件时，先查看自己的UFD及其子目录，无重名文件则在UFD或某子目录中增加一个新目录项。删除目录：若为空目录，可直接删除目录项。若非空目录，则：a、不删除非空目录。采用递规方式删除。b、可删除非空目录。所有文件/子目录同时删除。MS-DOS38•目录查询技术一线性检索法（顺序检索）：a.单级目录中，利用用户提供的文件名，利用顺序查找法，从文件目录中找到指名文件的目录项。b.在树型目录中，用户提供的文件名是由多个文件分量名组成的路径名，此时须对多级目录进行查找7.3.3、目录查询技术391.1..4Bin7Dev14Lib9Etc6Usr8tmp根目录文件1326.1..19dick30Erik51Jim26Ast45bal49626.6..64grant92book60mbox81minik17src假定用户给定的文件路径名是/usr/ast/mbox，则查找过程如下：/usr的目录文件/usr/ast的目录文件40•目录查询技术二Hash方法：建立一张Hash索引文件目录后，便可利用Hash方法进行查询。即系统利用用户提供的文件名并将它变换为文件目录的索引值，再利用该索引值到目录中去查找。Hash冲突——n个不同的文件名有可能转换为相同的Hash值41一种处理冲突的有效规则：（1）利用Hash法索引查找目录时，目录项空，表示无文件（2）如果目录项中的文件名与指定文件名匹配，表示找到文件，并找出