操作系统-第七章-文件系统VIP

第七章文件系统,7.1文件系统概念,一.何谓文件管理系统1.什么是文件管理系统将信息以文件形式存放在计算机系统的外存，并设置一个统一的公共信息管理机构，负责管理外存文件的存贮空间、文件在外存的组织和存放以及对文件的存取，这样的系统称为文件管理系统,7.1文件系统概念,2.文件系统的任务(P180)合理存放文件按名存取文件文件物理结构完成对存储设备上文件信息查找共享与保护,7.1文件系统概念,二.文件系统概念1.记录:顺序排列且相关的一组最小信息项（字或字节）记录，它是对文件访问的基本逻辑单位有键记录:有标识无键记录:无标识OS的文件是一种赋名的字符流文件，也是一种无结构文件。,7.1文件系统概念,2.文件:具有符号名的有若干个记录组成的有序信息集合称为文件狭义:外存中信息集合广义:各种I/O设备与传输的信息集合称为特别文件，如打印机文件，显示器文件，纸带输入机文件等,7.1文件系统概念,三.文件系统特点（）友好的用户接口按名存取,对用户透明文件共享用磁盘、磁带、光盘等大容量存储器作为存储介质,7.1文件系统概念,四.文件系统分类1)按性质和用途区分系统文件用户文件库文件2)按组织形式划分普通文件目录文件特殊文件,7.1文件系统概念,)按保存信息期限分临时文件长期文件4)按文件逻辑结构分记录式文件流式文件5)根据文件物理结构即在存贮介质上的组织形式连续文件链接文件索引文件,7.1文件系统概念,6)根据文件存取方式顺序文件随机文件7)根据文件操作方式只读文件读写文件可执行文件,7.2文件逻辑结构与存取方式,一.文件逻辑结构1.何谓文件逻辑结构(用户可见结构)2.确定文件逻辑结构的原则P1824点3.形式：流式、记录式,7.2文件逻辑结构与存取方式,二.常用的记录式结构文件1.连续结构记录按生成先后顺序连续排列的逻辑结构优点适应性强，适于所有文件记录排列顺序与记录内容无关缺点搜索性能差(需连续搜索),7.2文件逻辑结构与存取方式,2.多重结构把键与记录按行,列排列，但去除值为0的项得到以Ki为队首，以包含Ki的记录为队列元素构成的记录队列（图）；特点:每个队列中键直接相连只有一个记录3.转置结构把所有与同一个键对应记录指针连续地置于目录中该键的位置上（图）；特点:适合于给定键的记录搜索4.顺序结构:把文件中键按规定顺序排列起来,7.2文件逻辑结构与存取方式,三.存取方式1.存取方法:顺序存取随机存取按键存取2.对文件搜索包括:键的搜索和指定记录搜索3.对指定记录的搜索过程P184图7.6,7.2文件逻辑结构与存取方式,四.搜索算法1.线性搜索P1842.散列法散列法：定义一个散列函数(Hash函数)h(k),使得对于给的键k,散列函数h(k)将其变换为k所对应的逻辑地址即把每个符号名唯一地变换成符号表的表目位置；a=H(k)本质:由关键字作某种运算后直接确定元素的地址符号表符号表目的:希望不经过比较,一次存取表目位置关键字即能找到所要查的元素位置,7.2文件逻辑结构与存取方式,例:将符号名各字符ASCII码异或(按位加)得该符号名的Hash函数值A.例:H(ANDING)=ANDINGA=41,N=4E,D=44,I=49,N=4E,G=47然后根据计算出值找到相应位置缺点:可能发生冲突(即几个不同名可能会有相同Hash值),0100000101001110,0000111101000100,0100101101001001,0000001001001110,0100110001000111,00001011,7.2文件逻辑结构与存取方式,冲突解决办法链地址法(建立溢流表)加入个记录时,用散列法计算出基本表上存储地址；如主表上已有信息发生冲突,将此记录键号存入溢流表中；如溢流表该单元已满,则指示其他单元；开地址法:查找和插入都在基本表上进行,当某个记录按其关键字求得散列地址,如果发生冲突,发现该地址已占,则在基本表中寻找下一个空元，如基本表满，再建溢流表；,7.2文件逻辑结构与存取方式,3.二分搜索采用二分搜索,预先把其按键或记录排列成顺结构与中值比，中值,取右；申请量，分配后要修改空闲文件目录项删除文件时，填写新的空闲文件目录项3.空闲块链1)空闲块链把文件存储设备所有空闲块链接起来，当申请空闲块时从链头摘取所需空闲块，修改链首指针，回收空闲块时，将释放空闲块指针逐个插入链尾;,7.4文件存储空间管理,2)空闲块链的链接方式按空间大小顺序链接按释放先后顺序链接成组链法3)成组链法(P191图7.14)分组结构分配,分配和释放时需对空闲块链作较大调整,7.4文件存储空间管理,回收分配与回收必须互斥;4.位示图利用内存若干字节建立存储设备的位示图,每1位对应存储设备的一个物理块.其值为1,表示已分配,为0表示未分配;分配时查找位示图0位,并将其置1,回收时将其清0;,7.5文件目录管理,一.概述1.文件的管理:文件系统通过文件目录这一数据结构来管理文件2.文件系统最大特点:按名存取3.文件系统功能4.文件说明5.文件组成文件说明文件体,7.5文件目录管理,6.文件管理内容文件存储及存储空间有效利用快速搜索文件命名冲突文件共享,7.5文件目录管理,二.文件控制块和目录文件1.所谓文件控制块FCB(FileControlBlock)描述文件有关的说明和控制信息的数据结构;2.FCB内容(文件名,设备类型和设备号,文件物理位置,文件长度,文件属性,文件主及其操作权限,共享者及其操作限制,文件建立日期);3.目录文件:文件体为文件控制块(FCB)集合的文件称为目录文件;目录文件也有对应的文件控制块;所有文件目录的集合组成一个目录文件;,7.5文件目录管理,三.一级目录结构1.何谓一级目录结构:一个文件卷只有一张目录表;2.建立文件时在目录表中寻找一个空表目,登录相应的FCB,撤销文件时删除相应的表目;用户访问文件执行读写操作时,先根据FCB的文件名及有关信息来访问磁盘目录,找到与文件名相符的文件,然后进行磁盘与内存之间的文件信息传递;,7.5文件目录管理,3.优点:简单缺点:目录表过于庞大,增加查找时间目录表过大,调入内存，占据过多内存资源用户命名不能重名限制了不同用户对同一文件的共享,7.5文件目录管理,四.二级目录结构把一个卷上的文件目录分成两级主文件目录(MFD):用户文件目录(UFD)(子目录)：该用户所有文件控制块的集合2.二级目录特点一个文件卷中主目录有唯一一个,存放在专用固定区;子目录有若干个,可动态建立或撤销;3.二级目录原理(P194图7.16),用户名用户子目录物理位置,7.5文件目录管理,五.多级目录结构树型目录结构(是二级目录结构的延伸)1.各级目录结构组成根目录-主目录,可为普通文件或分目录;分目录-可为普通文件或更次一级的分目录;2.多级目录特点结构特点:倒排的树结构;文件特点:同一目录的文件不能同名,不同目录文件可以同名且不会产生二义性;,7.5文件目录管理,3.多级目录优缺点优点:利用多级目录结构,系统可把系统内所有文件按性质依次建立多级分目录,构成一棵多层次文件树,用以按其任务需要建立一个多层次子树;缺点:查找文件要按路径名逐层查找;,7.5文件目录管理,六.目录检索1.文件检索两步骤:目录检索:根据文件名从文件目录中找出对应的FCB文件寻址:根据FCB物理位置求出文件中任一记录(或字符流)在存贮介质中的物理位置2.目录检索的方法目录项分解法逐项读入目录文件的物理块进入内存查找，其速度慢,故可引入目录项分解法;,7.5文件目录管理,何谓目录项分解法:目录项(FCB)基本目录项(索引节点)名号目录(SFD)文件基本目录(BFD)文件(定长,各FCB按其内部号顺序排列),目录文件,7.5文件目录管理,访问文件步骤:由文件名名号目录文件查相应文件号基本目录文件查相应BFCB在基本目录文件中相对位置和物理位置读文件,7.5文件目录管理,一般规律:n:某个目录文件使用盘块个数m:名号目录项个数分解前后访盘次数(n+1)/2(m+1)/2+1当nm2访问次数减少,n与m差越大,检索速度改进效果越显著nm=2访问次数相同nm2访问次数增多,7.5文件目录管理,七.便于共享的文件目录实现文件共享的三种方法:绕道法(P195图7.18)链接法基本文件目录表BFD八.活动文件表:内存中活动文件的SFD表目,7.6文件存取控制,一.文件控制存取1.二级控制:通过存取控制矩阵(P198图7.20)控制操作1)第一级:访问者识别(那些人参加共享)文件主,文件主同组用户(合作用户),其他用户2)第二级:存取权限识别(有权参与共享者可多文件作何操作)R:只读W:写E:只允许执行N:不允许作任何操作,7.6文件存取控制,2.存取控制表(P198图7.21)3.UNIX系统用9位二进制位表示:所有者同组人其他人rwxrwxrwx创建文件时默认存取权限为rw-r-r创建目录时默认存取权限为rwxr-xr-x二.口令:保护三.密码:写入时编码加密,读出时对其译码解密(P199图7.22),用户文件:置入文件说明中,7.7文件的使用,OS为用户提供一组专门的文件操作命令以方便用户使用文件1.建立文件功能:在指定设备(文件卷)上创建一个具有指定文件名文件属性的新文件工作:基本目录表中分配一个空表目,返回文件内部名名号目录表上填入文件名和内部名为文件分配存贮空间在基本目录项中填入文件属性,设备号,物理地址,即建立BFCB建立文件实质:建立文件FCB,分配存贮空间,7.7文件的使用,2.打开文件实质:将文件目录FCB(名号目录项和基本目录项)调入内存中的活动表(活动目录表),每次访问不用从外存调入;工作:在活动名号表和活动目录表中为该文件分配空间;将该文件名号目录与基本目录项从外存分别读到活动名号表和活动目录表;多道及多用户系统,活动目录表中增加当前共享用户数字段,如已有用户打开某一文件(其FCB驻留)则置当前共享用户数+1,其他用户再用时不用再打开;建立文件时自动打开文件,7.7文件的使用,3.关闭文件实质:将文件目录FCB退出活动表;工作:请除该文件在用户活动名号表中相应表目;查找活动目录表,将当前共享用户数-1,如果为0,则清除该表目;若曾被修改,则需将修改后BFCB写入外存;4.撤销文件实质:撤销文件FCB,释放文件内存空间;,7.7文件的使用,5.读写文件目的:实现文件在内外存储介质间传输读写方式:字符流读写,每次读写若干字符记录读写,每次读写一个记录随机读写,根据记录键,读写指定的记录顺序读