电子科技大学计算机操作系统―第六章 文件管理

第六章许家珆关于本章学习方式《文件管理》这章的学习采用自学为主方式，这里给出各节的学习内容提纲及思考题。许家珆本章讨论的主要问题信息文件是计算机的重要软件资源，对信息的组织、存取和保存，是由文件系统实现的。文件系统是OS的重要组成部分。本章主要讨论以下问题：信息的组织形式文件的结构信息的存取目录结构信息的存储磁盘的存储管理信息的共享与保护文件的共享与保护文件系统的构成文件的结构目录结构文件的共享与保护许家珆6.1文件的基本概念一、文件管理五大功能：完成文件存储空间的管理。实现文件名到物理地址的映射。实现文件和目录的操作管理。提供文件的共享和保护。提供用户的接口。问题什么是文件系统？有何功能？文件系统的三层结构各有何作用？文件系统接口控制管理对象的软件集合对象及其属性文件系统的模型用户（程序）许家珆6.1文件的基本概念二、文件系统模型文件系统接口对象及其属性说明（文件、目录、磁盘）对对象操纵和管理的软件集合逻辑文件系统基本I/O管理程序（文件组织模块）基本文件系统（物理I/O层）I/O控制层（设备驱动程序）许家珆文件管理思考题1.文件的逻辑结构与物理结构有何区别与联系？2.磁盘空间的分配方式有哪几种？各有何特点？3.为什么通常采用多级目录结构？目录项包括哪些内容？如何通过目录实现文件的按名存取？4.有哪些文件共享方式？各有何特点？5.文件系统的保护措施有哪些？6.提高文件系统的性能可采取哪些措施？许家珆6.2文件的结构文件的逻辑结构是从用户的观点讨论文件的组织形式，即逻辑文件。文件结构分为逻辑结构和物理结构。文件结构决定了对文件的访问方式及检索速度。文件的物理结构是从存储的观点讨论文件在外存上的组织形式,即文件的物理结构或存储结构。主要考虑存储效率。许家珆6.2文件的结构一、逻辑文件1.无结构的字符流文件（如程序、文本文件）2.有结构的记录式文件（如数据库文件）按照记录长度定长记录变长记录按照存取方式顺序文件索引文件顺序索引文件Hash文件*串结构（按照时间顺序）顺序结构（按照键值）许家珆文件的存取方式1.顺序访问按照文件的逻辑地址顺序对文件记录（字符）进行读写操作。2.随机访问也称为直接访问，可按照任意的记录次序对文件进行读写操作。3.索引访问也称为按键值（或记录名）访问。文件记录按某个数据项（通常称为键值）排列。许家珆搜索记录Ri的过程由关键字查找含Ri记录队列找到了吗？由记录队列查找Ri找到了吗？返回Ri的逻辑地址返回空返回空是否是否许家珆对文件记录的搜索算法：1.线性搜索法（linearsearch）按记录排列顺序搜索。特点：简单直观、效率低。2.二分搜索法（binarysearchalgorithm）要求文件记录按关键字排列，不断对分，直到搜索到关键位置为止。特点：搜索效率高。3.散列法（hashcoding)也称为hash法。建立hash函数，即散列函数h（k）。是一种直接查找方式，hash函数将直接转换关键字K所对应的逻辑地址。特点：高效，但要解决hash函数的构造和冲突问题。许家珆㈡物理文件顺序(连续）文件链接(串联）文件索引(随机）文件从存储的观点讨论文件在外存上的组织形式，即文件的物理结构或存储结构。主要考虑存储效率。磁盘（块）分配方式不同，可分为3类文件：许家珆⑴顺序文件的存储结构将逻辑文件中的记录顺序地存储在连续的物理盘块中。⑵优缺点优点：实现简单，根据FCB中的物理块号，顺序访问较容易。缺点：存储效率低（连续存放），文件长度固定，修改记录困难。1.顺序文件(连续）文件的物理块号文件长度记录0记录1记录2记录3110#111#112#113#FCB许家珆2.链接文件(串联）（1）链接文件的存储结构将逻辑文件分散存放在不连续的物理盘块中。根据链接方式不同，分为：隐式链接将一个逻辑文件分为若干逻辑块，链接指针包含在物理块内。显式链接将链接各物理块的指针显式存放在“链接表”中。整个盘一张，又称为文件分配表FAT。（2）优缺点优点：存储空间利用率高，增、删修改方便。缺点：。。。。。？文件的物理块号文件长度FCB隐式FCB0123450451物理块号显式2许家珆3.索引文件是一种非连续分配的文件结构。基本思想是访问文件时，只调入FAT的部分（文件的盘块号）。（1）单级索引（稠密索引）为每个文件建立一张索引表，每个记录在表中占一个表项。检索过程：从FCB索引表始址按照关键字索引记录的物理地址许家珆（1）单级索引表主索引表指针FCB逻辑记录号物理盘块号024127231340记录0记录1记录2记录324#27#31#40#索引表许家珆（2）多级索引文件主索引表指针FCB键值物理地址ABC主索引表键值物理地址AA...AZBA..BZCA许家珆4.Hash文件Hash文件是一种最常用的直接文件，不是通过记录键值先对索引表等进行检索，再获得物理地址，而是直接由：记录键值物理地址。称为键址转换（Keytoaddresstransformation）(2)Hash文件的键址转换利用Hash函数（散列函数）将键值转换为记录在目录表中的索引（表项的位置）来实现键址转换。例如：将文件符号名的字符的ASCII码进行“异或”运算，所得的Hash值作为符号文件目录的索引值。(1)直接文件许家珆(3)Hash文件的冲突问题利用Hash技术，可能出现多个符号名被转换为同一个Hash索引—Hash冲突。解决办法：将符号文件目录作成二维表给Hash索引加上一个位移常数采用溢出处理技术许家珆存储设备磁盘、磁鼓磁带文件类型连续文件串联文件索引文件Hash文件连续文件文件长度固定固定、可变固定、可变固定、可变固定存取方法直接、顺序顺序直接、顺序直接、顺序顺序存储设备、文件类型与存取方式的关系许家珆6.3目录管理文件目录也是一种数据结构，用于标识文件及其物理地址，实现对文件的检索、访问。目录管理的功能：1.实现文件的“按名存取”2.提高对目录的检索速度3.实现文件共享4.实现文件重名问题1.为什么要建立多级目录?2.目录项包括哪些内容？3.如何实现文件的按名存取？即目录查询技术。许家珆6.3目录管理一、文件控制块和索引结点1.文件控制块（FCB）是用于控制和描述文件的数据结构，包括三类信息：基本信息：文件名、文件类型、文件物理位置、文件的逻辑结构、文件的物理结构。存取控制信息：用户的存取控制权(S、O、G、W)。使用信息：文件建立、修改的日期时间，当前使用信息。许家珆6.3目录管理2.索引结点如目录文件所占的盘块数为N，则查找一个目录项平均需要调入盘块（N+1）/2次。为了提高检索的速度，减少所需内存空间，考虑到检索文件时只用到文件名，在UNIX中，将文件FCB的描述信息单独构成一个数据结构—索引结点（i结点）。目录项仅由文件名和指向i结点的指针构成。许家珆6.3目录管理三、目录查询技术1.查询文件过程根据文件名查找文件目录，找出FCB或索引结点。由FCB或索引结点得到文件在磁盘上的物理位置，将文件读入内存。2.文件查询方式线性检索法Hash法*二、目录结构1.两级目录结构及其特点2.树型（多级）目录及其特点3.路径名与当前目录许家珆硬盘的数据结构按照其不同的特点和作用大致可分为5部分：MBR区、DBR区、FAT区、DIR区和DATA区。1.MBR区（MainBootRecord）为主引导记录区，位于整个硬盘的0磁道0柱面1扇区，共512字节。其中：MBR只占446个字节，另外的64个字节为硬盘分区表DPT(DiskPartitionTable)。最后两个字节是分区的结束标志。主引导记录中包含了硬盘的系列参数和一段引导程序。例：800101000BFEBFFC3F0000007E86BB00分区的激活标志，表示系统可引导6.4文件的存储设备许家珆硬盘的数据结构按照其不同的特点和作用大致可分为5部分：MBR区、DBR区、FAT区、DIR区和DATA区。1.MBR区（MainBootRecord）为主引导记录区，位于整个硬盘的0磁道0柱面1扇区，共512字节。其中：MBR只占446个字节，另外的64个字节为硬盘分区表DPT(DiskPartitionTable)。最后两个字节“55，AA”是分区的结束标志。主引导记录中包含了硬盘的系列参数和一段引导程序。例：800101000BFEBFFC3F0000007E86BB00分区开始的磁头号开始的扇区号开始的柱面号分区类型FAT3204（FAT16）07（NTFS）许家珆硬盘的数据结构按照其不同的特点和作用大致可分为5部分：MBR区、DBR区、FAT区、DIR区和DATA区。1.MBR区（MainBootRecord）为主引导记录区，位于整个硬盘的0磁道0柱面1扇区，共512字节。其中：MBR只占446个字节，另外的64个字节为硬盘分区表DPT(DiskPartitionTable)。最后两个字节“55，AA”是分区的结束标志。主引导记录中包含了硬盘的系列参数和一段引导程序。例：800101000BFEBFFC3F0000007E86BB00结束的磁头号结束的扇区号结束的柱面号相对扇区号总扇区数许家珆2.DBR区（DosBootRecord）操作系统引导记录区。通常位于硬盘的0磁道1柱面1扇区，是操作系统可以直接访问的第一个扇区，包括一个引导程序和一个被称为BPB（BiosParameterBlock）的本分区参数记录表。3.FAT区（FileAllocationTable）文件分配表区。文件占用磁盘空间的基本单位不是字节而是簇(cluster)。簇的大小与磁盘的规格有关。4.DIR区（Directory）根目录，记录着根目录下每个文件（目录）的起始单元，文件的属性等。5.数据区（DATA）数据区是真正意义上的数据存储的地方，位于DIR区之后，占据硬盘上的大部分数据空间。许家珆分区大小FAT16簇大小FAT32簇32MB2KB——128MB2KB——256MB4KB——512MB8KB4KB1GB16KB4KB2GB32KB4KB3-7GB——4KB8-16GB——8KB16-32GB——16KB大于32GB——32KB磁盘文件按簇存放，而簇的大小与分区大小有关。许家珆6.5文件的存储空间管理一、空闲表法为外存上的所有空闲区建立一张“空闲区表”,其分配算法与回收,与内存管理类似，是一种连续分配方式。二、空闲链表法空闲盘块链（结点为盘块）空闲盘区链（结点为盘区）序号第一空闲盘块号空闲盘块数1242933145讨论对文件的存储空间的管理：分配、回收与访问。许家珆6.5文件的存储空间管理0空闲1已分配三、位示图法利用二进制位表示磁盘中每个块的使用情况{将位示图定义为一个M*N的二维数组：Varmap:array[1..m,1..n]ofbit;位示图与盘块号b之间的对应关系为：b=n(i-1)+j其中：i—行j—列n—每行的位数回收时，要将盘块号转换为行、列号，再将相应位置为0。许家珆6.5文件的存储空间管理四、成组链法（UNIX）将空闲盘块分为若干组，每组盘块总数、该组所有盘块号记入前一组的第一个盘块中，各组的第一个盘块构成链。所有盘块号记入空闲盘块号栈。最后一组中放入结束标志。将其块号与总数放入管理文件存储设备的文件资源表中。第一组第一组的块号与总块号空闲盘块号栈第二组第三组最后组…文件资源表最后组的块号与总块号倒数第二组的块号与总块号文件存储设备第二组的块号与总块号第二组第三组最后组…文件资源表最后组的块号与总块号倒数第二组的块号与总块号文件存储设备第二组的块号与总块号许家珆许家珆6.6文件的共享与保护文件共享1.绕弯路法2.链接法3.利用基本文件目录表*4.基于索引结点的共享*5.用符号链实现文件共享许家珆Zhang用户文件目录TestrLiu用户文件目录TestrCount=2文件物理地址test索引结点基于索引结点的共享方式许家珆Zhang用户文件目录TestrLiu用户文件目录Testr基于索引结点的共享方式许家珆Zhang用户文件目录TestrLiu用户文件目录TestrC