相关名词解释:
文件管理:把所管理的程序和数据组织成一系列的文件,并能进行合理的存储、使用等操作。
数据项:描述对象某种属性的字符集;是数据组织中可以命名的最小逻辑数据单位。
记录:一组相关数据项集合,描述对象某方面的属性。
关键字:一个记录中的一个或几个数据项的集合,用于唯一的标识一个记录。
文件:由创建者定义的、具有文件名的一组相关元素的集合。
1 文件、文件系统
文件管理:把所管理的程序和数据组织成一系列的文件,并能进行合理的存储、使用等操作。
1 )基本概念
数据项:描述对象某种属性的字符集;是数据组织中可以命名的最小逻辑数据单位。
记录:一组相关数据项集合,描述对象某方面的属性;
关键字:一个记录中的一个或几个数据项的集合,用于唯一的标识一个记录。
文件:由创建者定义的、具有文件名的一组相关元素的集合。
有结构:由相关记录组成
无结构:字符流的形式
属性:类型、长度、物理位置、创建时间
2 )文件类型
不同的系统对文件的管理方式不同,大多用扩展名标志文件类型,按如下几种方式分类文件:
按用途:系统、用户、库文件
按数据形式:源文件、目标文件、可执行文件
按存取控制属性:只执行、只读、读写
按组织和处理方式:普通文件、目录文件、特殊(设备)文件
3)文件系统模型
系统管理文件模型
4)文件操作
最基本的操作
创建/删除文件:分空间,形成FCB及目录(名,地址)
读、写:按名检索目录,找到文件地址,开始读、写
设置文件读写位置,实现随机存取(尤其适用于记录文件)
还需要:“打开”与“关闭”:
文件读/写操作 = 检索 + 读/写。
每次读写前都要重复检索增大开销。所以为了方便对同一文件的多次读写,一次检索到文件后就在内存中记录其位置,避免重复检索。被记录下位置的文件就是“打开”文件;
不需要再操作文件时,通过“关闭”这个系统调用关闭文件——即从打开文件表上删除其路径信息即可。
其他操作:改名、改所属用户、改访问权限等属性的操作。
2 文件结构、外存分配
文件系统设计的关键要素:
文件结构:文件的逻辑结构file logical structure:按用户观点如何组织数据;又称文件组织file organization
基本要求:检索速度高、方便修改、降低存储空间费用(不连续)
文件的物理结构:根据外存上的物理块的分配机制,记录文件外存的存储结构。用户感知不到的。
1)文件逻辑结构的类型
有结构文件(记录式)
①定长记录
②变长记录
如何组织记录:
顺序文件。系统需按该类型记录“长度”,通常定长。
索引文件。系统需为文件建立索引表。
索引顺序文件。建索引表,记录每组记录的第一个记录位置。
无结构文件(字符流式),字节为单位,利用读写指针依次访问。系统对该类文件不需格式处理。
目标:有效利用外存空间,提高文件访问速度
常用三种方式:
连续分配
链接分配(不连续)
索引分配
通常一个系统中仅采用一种方式
采用的磁盘分配方式决定了文件的“物理结构”顺序结构;链接式结构;索引式结构。
*** FAT表的相关计算
MS-DOS文件分配结构为例:
一个1.2M的磁盘,盘块512B大小;若文件系统采用FAT格式,则FAT表大小如何?
表项个数 = 盘块个数
= 容量 / 盘块大小 = 1.2 *220 / 29 = 1.2 *211 个
表项大小,决定于盘块数量编号需要的位数=12 位;
FAT表大小 = 表项个数 * 表项大小
= 1.2 *211 * 12 bit
= 1.2 *211 * 1.5B = 3.6KB
以半字节(0.5B=4b)为基本单位,表项需12位(1.5B)
由上述公式,若容量为200M的磁盘,盘块仍为512B,FAT表大小如何?
FAT表表项有200K≈218 (个)
表项需20位,即2*8+4,2.5字节
FAT表需内存大小为200*2.5=500KB
***多级索引下的文件大小
若两级索引,盘块1KB,盘块号占4字节
一个盘块可存放的盘块号数有多少个
1KB/4B = 210/4 = 28 = 256(个)
二级索引下的文件可分配的最大盘块数
256 * 256 =26×210=64 K(个)
文件最大长度为
64K(个)*1KB=64MB
若盘块大小为4KB,单级索引允许文件最大长度为4MB(4K/4*4KB),二级索引则文件最大可达4GB(1K*1K*4KB)。
3 目录、存储空间管理
为实现存储空间分配,系统需要:
记住空闲存储空间使用情况;为空间设置相应的数据结构;
提供对存储空间分配、回收的操作手段。
典型的管理方法:
1)空闲表和空闲链表法
2)位示图法
3)成组链接法
1)空闲表法和空闲链表法
空闲表法
常用于连续分配管理方式
1.数据结构
系统为外存上的所有空闲区建立一张空闲表
每个空闲区对应一个空闲表项
(表项包括序号、空闲区的第一个盘块号、空闲盘块数等。)
将所有空闲区按其起始盘块号递增的次序排列,如右图。
2.存储空间的分配与回收操作
与内存的动态分配类似,同样可采用首次适应算法、循环首次适应算法等。
回收主要解决对数据结构的数据修改。
应该说明,虽然很少采用连续分配方式,然而在外存的管理中,由于它具有较高的分配速度,可减少访问磁盘的I/O频率,故它在诸多分配方式中仍占有一席之地。(如实现虚拟用的部分外存就是连续分配方式)
空闲链表法
将所有空闲盘区拉成一条空闲链。
1).数据结构:链
根据构成链所用基本元素的不同,可把链表分成两种形式:
空闲盘块链
空闲盘区链
2)位示图法——位示图
利用二进制的一位来表示一个盘块的使用情况。
值为0表示对应的盘块空闲,为1表示已分配。有的系统则相反。
磁盘上的所有盘块都有一个二进制位与之对应,这样由所有盘块所对应的位构成一个集合,称为位示图。
总块数=m*n。可用m*n个位数来构成位示图,可看成是二维数组(数据结构)。
根据位示图进行盘块分配:
顺序扫描位示图。找到为0的二进制位。
将所找到的一个或一组二进制位,转换成与之对应的盘块号。进行分配操作。
盘块号计算公式为:盘块号 = 列总数*(i-1)+ j;(注意下标i,j从1开始)
修改位示图。
根据位示图进行盘块回收:
将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为:i=(盘块号-1)div列数+1;j=(盘块号-1)mod列数+1
Div 求商,mod 取余,公式中的i、j都是从1开始的
(如12号盘块转换后为1,12)
修改位示图。
3)成组链接法
大型文件系统,空闲表或空闲链表太长不方便管理操作。
UNIX系统中采用成组链接法,这是将两种方法结合而形成的一种空闲盘块管理方法。
中心思想:
所有盘块按规定大小划分为组;
组间建立链接;
组内的盘块借助一个系统栈可快速处理,且支持离散分配回收。
文件控制块—FCB
在文件控制块中,通常含有以下三类信息。
基本信息类包括:
文件名、文件物理位置、文件逻辑结构、文件的物理结构
存取控制信息类:包括文件主的存取权限,核准用户的存取权限和一般用户的存取权限。
使用信息类:建立日期和时间、文件上次修改的日期和时间
当前使用信息:打开该文件的进程数、是否被进程锁住、是否已修改等。
目录管理
对文件实施有效的管理,必须对它们加以妥善组织,主要是两大操作:
基本信息记录(FCB,目录项)
方便检索、管理(目录操作)
目录管理的要求如下:实现“按名存取”;(最基本功能)提高对目录的检索速度;文件共享;允许文件重名。
4 共享、保护、一致性
1)文件共享
多个用户共享一份文件,只保留文件的一份副本,节约存储空间
共享范围:单机系统/多主机系统/网络范围
20世纪六七十年代,出现了若干文件早期共享方法,绕弯路法、连访法等,逐渐发展为现代一些共享方式
索引结点、符号链。
2)磁盘容错
SFT,system fault tolerance:防止磁盘故障造成的文件不安全
SFT I:磁盘表面故障
双目录、双文件分配表(空间冗余)
写后读校验、热修复重定向(时间操作冗余)
写入磁盘后再读回内存做一致性校验
热修复写过程:从坏道重定向到专区并记录
SFT II:磁盘驱动器、控制器故障
驱动器故障:磁盘镜像
控制器故障:磁盘双工——并行控制器,分离搜索加快读取