操作系统第6章文件管理资料

1、2022/9/111操作系统第六章 文件管理2022/9/112在现代计算机系统中,用到大量的程序和数据,由于内存容量和存储特性的限制,这些内容必须以文件的形式保存在外存操作系统必须提供对外存的文件管理的功能,即构成文件系统操作系统中包括文件管理、文件存取、共享和文件保护文件是具有文件名的若干相关元素的集合文件系统的管理功能是通过把它所管理的程序和数据组织成一系列文件的方法来实现的2022/9/113内容概述6.1 文件和文件系统 6.2 文件的逻辑结构 6.3 外存分配方式 6.4 目录管理 6.5 文件存储空间的管理 6.6 文件共享与文件保护 6.7 数据一致性控制(了解) 2022/9

2、/1146.1 文件和文件系统6.1.1 文件、记录和数据项6.1.2 文件类型和文件系统模型6.1.3 文件操作2022/9/115图6-1 文件、记录和数据项之间的层次关系 2022/9/1166.1.1 文件、记录和数据项 1.数据项(1)基本数据项用于描述一个对象的属性的字符集,是数据组织中可以命名的最小逻辑数据单位,即原子数据,又称为数据元素或字段如描述一个学生:学号、姓名、年龄、班级(2)组合数据项由若干个基本数据项组成,简称组项如工资包括基本工资、工龄工资、奖金等基本数据项除数据名外,还应有数据类型2022/9/117学号姓名性别生日家庭住址语文数学英语总分平均分学生整数字符字符

3、日期字符实数实数实数实数 总分=语文+数学+英语实数 平均分=总分/32022/9/1182.记录记录是一组相关数据项的集合,用于描述一个对象在某方面的属性一个记录应包含哪些数据项,取决于需要描述对象的哪个方面一个对象,由于他所处的环境不同可把他作为不同的对象一个学生,当把他作为班上的一名学生时,对他的描述应使用学号、姓名、年龄及所在系班,也可能还包括他所学过的课程的名称、成绩等数据项若把学生作为一个医疗对象时,对他描述的数据项则应使用诸如病历号、姓名、性别、出生年月、身高、体重、血压及病史等项能惟一标识一个记录的数据项称为关键字(key)2022/9/119学号姓名性别出生时间家庭住址身份证

4、号1张男1980.1哈尔滨23102王女3李男4赵女5X 班学生名单关键字关键字记录2022/9/11103.文件文件是指由创建者所定义的、具有文件名的一组相关元素的集合可分为有结构文件和无结构文件有结构文件由若干个相关记录组成,如上例中学生文件无结构文件则被看成是一个字符流,如C语言源程序文件在文件系统中是一个最大的数据单位,它描述了一个对象集例如,可以将一个班的学生记录作为一个文件一个文件必须要有一个文件名,它通常是由一串ASCII码或(和)汉字构成2022/9/1111图6-1 文件、记录和数据项之间的层次关系 文件属性(1)文件类型(2)文件长度(3)文件的物理位置(4)文件的建立时间

5、2022/9/11126.1 文件和文件系统6.1.1 文件、记录和数据项6.1.2 文件类型和文件系统模型6.1.3 文件操作2022/9/11136.1.2 文件类型和文件系统模型 1.文件类型(1)按用途分类系统文件有关操作系统及其它系统程序的信息所组成的文件。这类文件对用户不直接开放,只能通过系统调用为用户服务。用户文件由用户委托操作系统保存的文件,如源程序文件,目标程序文件,以及由原始数据、计算结果等组成的文件。库文件由标准子程序及常用的应用程序组成的文件。 这类文件允许用户调用,但不允许用户修改。2022/9/11146.1.2 文件类型和文件系统模型 1.文件类型(1)(2)按文

6、件中数据的形式分类源文件目标文件可执行文件(3)按存取控制属性分类只执行文件只读文件允许文件主及核准的用户读,但不允许写的文件。读写文件允许文件主及核准的用户读、写,但禁止未核准的用户读、写的文件。2022/9/11156.1.2 文件类型和文件系统模型 1.文件类型(1)(2)(3)(4)按组织形式和处理方式分类普通文件目录文件由文件目录组成的，用于管理和实现文件系统功能的系统文件。特殊文件特指系统中的各类I/O设备。2022/9/11162.文件系统模型 图6-2 文件系统模型 对象及其属性(对象:文件、目录、磁盘存储空间)对对象操纵和管理的软件集合文件系统接口用户(程序)命令接口、程序接

7、口2022/9/1117(1)对象及其属性文件管理系统管理的对象有: 文件。 它作为文件管理的直接对象。 目录。 为了方便用户对文件的存取和检索,在文件系统中必须配置目录。对目录的组织和管理是方便用户和提高对文件存取速度的关键。 磁盘(磁带)存储空间。 文件和目录必定占用存储空间,对这部分空间的有效管理,不仅能提高外存的利用率,而且能提高对文件的存取速度。2022/9/1118 (1)(2)对对象操纵和管理的软件集合 这是文件管理系统的核心部分。文件系统的功能大多是在这一层实现的,完成:对文件存储空间的管理对文件目录的管理用于将文件的逻辑地址转换为物理地址的机制对文件读和写的管理对文件的共享与

8、保护等功能2022/9/1119 (3)文件系统的接口 为方便用户使用文件系统,文件系统通常向用户提供两种类型的接口: 命令接口。这是指作为用户与文件系统交互的接口。 用户可通过键盘终端键入命令,取得文件系统的服务。 程序接口。这是指作为用户程序与文件系统的接口。 用户程序可通过系统调用来取得文件系统的服务。 2022/9/11206.1 文件和文件系统6.1.1 文件、记录和数据项6.1.2 文件类型和文件系统模型6.1.3 文件操作2022/9/11216.1.3 文件操作 最基本的文件操作(1)创建文件。分配必要的外存空间,在文件系统的目录中建立一个目录项。 (2)删除文件。从目录中删除

9、该目录项,回收存储空间。(3)读文件。查找到指定的目录项,从外存读文件到内存。(4)写文件。 查找到指定的目录项,进行写操作。(5)截断文件。文件内容陈旧要更新,一:删除,重新建立。二:文件长度设成0。(6)设置文件的读/写位置。用于设置指针位置。2022/9/11222.文件的“打开”和“关闭”操作所谓“打开”OPEN,是指系统将指名文件的属性从外存拷贝到内存打开文件表的一个表目中,并将该表目的编号(或称为索引)返回给用户当用户再要求对该文件进行相应的操作时,便可利用系统所返回的索引号向系统提出操作请求。系统这时便可直接利用该索引号到打开文件表中去查找,从而避免了对该文件的再次检索“关闭”(

10、CLOSE)系统调用来关闭此文件,OS将会把该文件从打开文件表中的表目上删除掉2022/9/11233.其它文件操作(1)文件属性操作改变文件名改变拥有者修改权限查询状态(2)有关目录操作创建目录删除目录改变当前目录(3)实现文件共享的系统调用(4)用于对文件系统进行操作的系统调用2022/9/1124内容概述6.1 文件和文件系统 6.2 文件的逻辑结构 6.3 外存分配方式 6.4 目录管理 6.5 文件存储空间的管理 6.6 文件共享与文件保护 6.7 数据一致性控制(了解)2022/9/11256.2 文件的逻辑结构6.2.1 文件逻辑结构的类型6.2.2 顺序文件6.2.3 索引文件

11、6.2.4 索引顺序文件6.2.5 直接文件和哈希文件2022/9/1126对于一个文件存在着以下两种形式的结构(1)文件的逻辑结构(File Logical Structure)从用户观点看到的文件组织形式,独立于文件的物理特性又称为文件组织(File Organization)(2)文件的物理结构又称为文件的存储结构,指文件在外存上的存储组织形式对逻辑结构的基本要求提高检索速度便于修改降低文件的存储费用2022/9/11276.2.1 文件逻辑结构的类型 1.有结构文件(又称记录式文件)按记录长度分(1)定长记录(2)变长记录根据用户和系统管理需要分(1)顺序文件(2)索引文件(3)索引顺

12、序文件2.无结构文件流式文件其长度以字节为单位采用读写指针来指出下一个要访问的字符如源程序、可执行文件、库函数等2022/9/1128图 记录式文件(a)定长记录文件; (b)变长记录文件 2022/9/1129文件逻辑结构有结构文件(记录式)无结构文件(流式)定长记录变长记录顺序文件索引文件索引顺序文件定长记录文件的长度=记录个数记录长度变长记录文件的长度=各记录长度之和2022/9/11303、两种文件的比较流式文件就像给一张白纸给用户,用户可将他的信息任意地写到纸上,没有任何格式上的限制。记录式文件就像给一张表格给用户,用户要按表规定的格式填信息。显然,有结构式文件对用户的限制很大,使用

13、起来就不方便,在UNIX系统中,所有的文件都被看作是流式文件,即使是有结构文件,也被视为流式文件。2022/9/11316.2 文件的逻辑结构6.2.1 文件逻辑结构的类型6.2.2 顺序文件6.2.3 索引文件6.2.4 索引顺序文件6.2.5 直接文件和哈希文件2022/9/11326.2.2 顺序文件1.逻辑记录的排序(1)串结构各记录之间的顺序与关键字无关通常由时间来决定存在问题(2)顺序结构文件中的所有记录按关键字(词)排列记录号学号姓名性别出生时间1001赵男1965.8.12003钱女1971.6.173004孙男1980.12.114005李男1983.4.155006周女19

14、76.2.106007吴男1977.11.122022/9/1133图6-3 定长和变长记录文件 2.对顺序文件(Sequential File)的读/写操作记录长度记录起始地址2022/9/11343.顺序文件的优缺点优点顺序文件的最佳应用场合,是在对诸记录进行批量存取时, 即每次要读或写一大批记录只有顺序文件才能存储在磁带上, 并能有效地工作缺点如果用户(程序)要求查找或修改单个记录, 顺序文件所表现出来的性能就可能很差(顺序查找的ASL很大)(串结构)如果想增加或删除一个记录, 都比较困难(需移动大量数据,顺序结构(排序)2022/9/11356.2 文件的逻辑结构6.2.1 文件逻辑结

15、构的类型6.2.2 顺序文件6.2.3 索引文件6.2.4 索引顺序文件6.2.5 直接文件和哈希文件2022/9/11366.2.3 索引文件 对定长记录文件,如果要查找第i个记录, 可直接根据下式计算来获得第i个记录相对于第一个记录首址的地址Ai=iL对于可变长度记录的文件,要查找其第i个记录时,须首先计算出该记录的首地址,Li为第i个记录长度2022/9/1137图6-4 索引文件的组织 索引本身是一个定长记录的顺序文件,主文件中每个记录在索引表中占一个表项,可采用快速查找算法,如字典可以是变长记录,又实现随机访问(给出索引号)折半查找(给出关键字)2022/9/11382022/9/1

16、139可以对索引表采用折半查找法优点:有较快的检索速度缺点:(1)增加了索引表,增加存储费用 (2)增加了对索引表维护工作适合场合:主要用于对信息处理的及时性要求较高的场合。2022/9/11406.2 文件的逻辑结构6.2.1 文件逻辑结构的类型6.2.2 顺序文件6.2.3 索引文件6.2.4 索引顺序文件6.2.5 直接文件和哈希文件2022/9/1141索引顺序文件(Index Sequential File)是最常见的一种逻辑文件组织形式,是顺序文件与索引文件的结合克服了变长记录文件不便于直接存取的缺点,代价也不太大将顺序文件中的所有记录分为若干个组,为每组中的第一个记录建立索引项,

17、其中含有该记录的键值及指向该记录的指针6.2.4 索引顺序文件 2022/9/1142图6-5 索引顺序文件 2022/9/11432022/9/1144文件检索速度对顺序文件检索若记录数据为N,则检索一条记录时,最好的情况是第一条记录即为所求;最坏的情况是最后一条记录为所求;平均检索N/2条记录对索引文件检索可采用折半查找等方法快速对索引顺序文件检索索引文件与顺序文件的结合2022/9/11456.2 文件的逻辑结构6.2.1 文件逻辑结构的类型6.2.2 顺序文件6.2.3 索引文件6.2.4 索引顺序文件6.2.5 直接文件和哈希文件2022/9/1146 文件的另一种组织方式是采用计算

18、寻址结构。在这种方式中,把记录中的键值通过某种计算,转换为相应记录的相应地址。一般说来,由于地址的总数比可能的键值总数(范围)要少得多,也就是不会出现一一对应的关系。因此,不同键值在计算之后,可能会得到相同的地址,这种现象称为“地址冲突”。所谓计算寻址,最常用的就是Hash方法,或称散列法,杂凑法。利用这种方法所建立的文件称为Hash文件。这种物理结构用在不宜采用连续结构、记录次序较乱、又需在极短时间内存取的场合,如用在实时处理文件、操作系统目录文件、编译程序变量名表等方面特别有效。此外,又不需索引,从而节省了索引表所占的空间和索引表的查找时间。 解决地址冲突,这是设计Hash文件需要考虑的主

19、要内容,用的冲突处理技术有:线性探测再散列、二次探测再散列、再哈希法、链地址法等。2022/9/11476.2.5 直接文件和哈希文件键值转换(Key to address transformation)由记录键值到记录物理地址的转换直接文件 根据给定的记录键值,直接获得指定记录的物理地址哈希(Hash)文件 利用哈希函数将记录键值转换为相应记录的地址2022/9/11481.直接文件 对于直接文件,则可根据给定的记录键值,直接获得指定记录的物理地址。换言之,记录键值本身就决定了记录的物理地址。这种由记录键值到记录物理地址的转换被称为键值转换(Key to address transforma

20、tion)。组织直接文件的关键,在于用什么方法进行从记录值到物理地址的转换。 2022/9/11492.哈希(Hash)文件 图6-6 Hash文件的逻辑结构一种特殊的直接文件2022/9/1150内容概述6.1 文件和文件系统 6.2 文件的逻辑结构 6.3 外存分配方式 6.4 目录管理 6.5 文件存储空间的管理 6.6 文件共享与文件保护 6.7 数据一致性控制(了解)2022/9/1151如何才能有效地利用外存空间?如何提高对文件的访问速度?2022/9/1152文件的物理结构文件的物理结构是指逻辑文件在存储设备(外存)上的存储组织形式,它与存储介质的存储特性有关,还与所采用的外存分

21、配方式有关物理块是分配和传输信息的基本单位,物理块与外存设备有关文件在逻辑上都可看作是连续的,但在物理设备上存放时却有不同的方式,如连续分配、链接分配、索引分配等2022/9/11536.3 外存分配方式6.3.1 连续分配6.3.2 链接分配6.3.3 索引分配2022/9/11546.3.1 连续分配连续分配(Continuous Allocation)要求为每一个文件分配一组相邻接的盘块。一组盘块定义了磁盘上的一段线性地址在采用连续分配方式时,可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中,这样所形成的文件结构称为顺序文件结构,此时的物理文件称为顺序文件2022/9/11552022

22、/9/11566.3.1 连续分配 图6-7 磁盘空间的连续分配 图中假设记录和盘块大小相同与内存可重定位分区分配一样有紧凑2022/9/11572022/9/11582.连续分配的主要优缺点 连续分配的主要优点如下:(1)顺序访问容易。 (2)顺序访问速度快。(都存放在相邻的盘块上,磁头移动距离少) 连续分配的主要缺点如下:(1)要求有连续的存储空间。(有外碎片,紧凑要大量时间) (2)必须事先知道文件的长度。(根据大小找连续存储空间,存在多次拷贝现象)2022/9/11596.3 外存分配方式6.3.1 连续分配6.3.2 链接分配6.3.3 索引分配2022/9/11606.3.2 链接

23、分配链接分配(Chained Allocation)可通过在每个盘块上的链接指针,将同属于一个文件的多个离散的盘块链接成一个链表,把这样形成的物理文件称为链接文件消除了外部碎片,提高外存利用率文件动态增长时,可动态地为它分配盘块文件的增删改方便(这种文件结构不要求连续存放)文件创建时用户不必指出文件的大小缺点只适用于顺序存取,若查找文件中的某一块必须从头开始,随机存取效率太低,如果访问文件的最后的内容,实际上是要访问整个文件可靠性差,若某一块出错,则链断开,文件不完整增加一个链接指针2022/9/1161链接方式又分为两种形式:1.隐式链接2.显示链接2022/9/1162图6-8 磁盘空间的

24、链接式分配 1.隐式链接指针放在盘块中几个盘块一簇2022/9/11632.显式链接(解决查找时多次访问磁盘的问题) 图6-9 显式链接结构 整个磁盘就一张文件分配表(在内存中)2022/9/1164图6-10 MS-DOS的文件物理结构2022/9/1165链接分配显式链接文件分配表(File Allocation Table, FAT)用于记录外存分配状况,每个盘块占一项,放在内存中(提高查找速度)表的序号为物理盘块号,从0至N-1分配给一个文件的所有物理块都在该表中标出,文件的第一个盘块号记入文件的FCB中实例对于1.2MB软盘,每个物理块大小为1KB,则共有1.2K个FAT表项,若每个

25、表项占12位(1.5B),则共需1.2K*1.5B=1.8KB 的空间来保存FAT。对于12GB软盘,每个物理块大小为4KB,则共有3M个FAT表项,若每个表项占3B,则共需3M*3B=9MB 的空间来保存FAT。很大内存2022/9/11666.3 外存分配方式6.3.1 连续分配6.3.2 链接分配6.3.3 索引分配2022/9/11676.3.3 索引分配 1.单级索引分配 链接分配方式虽然解决了连续分配方式所存在的问题,但又出现了另外两个问题, 即: (1) 不能支持高效的直接存取。要对一个较大的文件进行直接存取,须首先在FAT中顺序地查找许多盘块号。 (2) FAT需占用较大的内存

26、空间。需要把整个FAT都调入内存。 索引分配为每个文件分配一个索引块,把分配给该文件的所有盘块号都记录在该索引块中在建立一个文件时,便为之建立的目录项中填上指向该索引块的指针2022/9/1168图6-12 索引分配方式 2022/9/1169若每个盘块大小为1KB,每个盘块号占4B,则索引块中可存放256个盘块号,用一个索引块只支持256K大小文件可能要花费较多的外存空间。当文件小时,索引块利用率低。文件太大时,需要多个索引块,通过指针链接起来,效率低。2022/9/11702.多级索引分配图6-12 两级索引分配2022/9/1171若每个盘块大小为1KB,每个盘块号占4B,则一级索引块中

27、可存放28=256个盘块号每个二级索引块可对应256个物理磁盘块,采用这种索引方式时每个文件大小不能超过256*256*1KB=64MB(只用一个二级索引块时)若每个盘块大小为4KB,每个盘块号占4B,则最大文件大小为1K*1K*4K=4GB2022/9/1172图6-13 混合索引方式 直接地址物理盘块索引块3.混合索引分配方式已用在UNIX系统2022/9/1173(1)直接地址为了提高对文件的检索速度,在索引结点中可设置10个直接地址项,即用iaddr(0)iaddr(9)来存放直接地址(盘块4KB,共40KB)(2)一次间接地址对于大、中型文件,可再利用索引结点中的地址项iaddr(1

28、0)来提供一次间接地址。这种方式的实质就是一级索引分配方式(盘块4KB,共4MB)(3)多次间接地址当文件长度大于4MB+40KB时(一次间址与10个直接地址项),系统还须采用二次间址分配方式。这时,用地址项iaddr(11)提供二次间接地址。该方式的实质是两级索引分配方式(共4GB),还可以提供三次间址iaddr(12) (共4TB)2022/9/1174索引分配的主要问题需要较多外存空间来建立索引块对于小文件,空间浪费严重2022/9/1175内容概述6.1 文件和文件系统 6.2 文件的逻辑结构 6.3 外存分配方式 6.4 目录管理 6.5 文件存储空间的管理 6.6 文件共享与文件保

29、护 6.7 数据一致性控制(了解)2022/9/1176目录管理要求(1)实现“按名存取”文件系统最基本的功能为实现文件的按名存取,每个文件首先应该具有一个文件名与之对应。(2)提高对目录的检索速度加快目录检索速度,从而提高文件存取速度,追求的主要目标。(3)文件共享一份文件副本供不同用户使用(4)允许文件重名允许不同用户对不同文件取相同的名字2022/9/11776.4 目录管理6.4.1 文件控制块和索引结点6.4.2 目录结构6.4.3 目录查询技术目录管理的任务是为每个文件建立目录项,并对众多的目录加以组织,以实现方便的按名存取,实现文件的共享,提供快速的目录查询手段,提高文件的检索速

30、度。2022/9/11786.4.1 文件控制块和索引结点1.文件控制块(FCB)是用于描述和控制文件的数据结构文件管理程序可借助FCB中的信息对文件施以各种操作文件控制块的有序集合称为文件目录,即一个文件控制块就是一个文件目录项通常,一个文件目录本身也被看作是一个文件,称为目录文件2022/9/11796.4.1 文件控制块和索引结点 文件控制块中的信息(1)基本信息类文件名文件物理位置 文件逻辑结构 文件的物理结构 (2)文件控制信息类文件拥有者权限核准用户权限一般用户权限(3)使用信息类文件建立日期文件修改日期2022/9/1180图6-15 MS-DOS的文件控制块 2022/9/11

31、812.索引结点(1)索引结点的引入文件目录通常放在磁盘上,当文件很多时,占用大量磁盘空间检索文件过程中,只需使用文件名,而不用其他信息将文件描述信息单独形成一个数据结构,称为索引结点,也称为i结点在文件目录中的每个目录项,仅包含文件名和指向索引结点的指针引入索引结点后,使文件的目录项更小,占用磁盘空间少,检索速度加快2022/9/1182图6-16 UNIX的文件目录 文件名索引结点编号文件名1文件名214B2B2022/9/1183若每个FCB为64B,盘块大小为1KB,则每盘块可存放1024/64=16个FCB,若某文件系统有640个FCB,需占用640/16=40个盘块若按前述方法只存

32、文件名和索引节点号,每个目录项占16B,每盘块可存1024/16=64个目录项,640个FCB只占640/64=10个盘块,查找目录时间大大缩短2022/9/1184(2)磁盘索引结点 文件主标识符拥有该文件的个人或小组的标识符 文件类型正规文件、目录文件或特别文件文件存取权限各类用户对该文件的存取权限文件物理地址13个地址项,给出文件所在盘块编号文件长度 以字节为单位的文件长度文件连接计数 指向该文件的指针的个数文件存取时间 指出最近被进程存取的时间、最近被修改的时间及索引结点最近被修改的时间存放在磁盘上的索引结点2022/9/1185(3)内存索引结点:文件打开时调入内存的,增加了:索引结

33、点编号。用于标识内存索引结点。状态。指示i结点是否上锁或被修改。访问计数。每当有一进程要访问此i结点时,将该访问计数加1,访问完再减1。文件所属文件系统的逻辑设备号。链接指针。设置有分别指向空闲链表和散列队列的指针。 2022/9/11866.4 目录管理6.4.1 文件控制块和索引结点6.4.2 目录结构6.4.3 目录查询技术2022/9/11876.4.2 目录结构目前常用的目录结构有:1.单级目录2.两级目录3.多级目录2022/9/11886.4.2 目录结构 图6-17 单级目录 1.单级目录结构整个系统只建立一张目录表,每个文件占一个目录项文件名物理地址文件说明状态位文件名1文件

34、名22022/9/1189单级目录优点(1)易于实现,管理简单(2)能实现按名存取单级目录缺点(1)查找速度慢(顺序查找,N/2) (2)不允许重名(在多道程序设计下,很难保证)(3)不便于实现文件共享(所有用户必须用同一个名字共享一个文件)单级目录只实现了目录管理的第一项功能 ,即“按名存取”,只能适用于单用户环境2022/9/11902.两级目录为每个用户建立一个单独的用户文件目录UFD(User File Directory),由用户所有文件的FCB组成在系统中建立主文件目录MFD(Master File Directory),每个用户目录文件在主文件目录中占一个目录项2022/9/11

35、91图6-18 两级目录结构 索引主文件目录MFD用户文件目录UFD2022/9/1192两级目录具有以下特点:(1)提高了检索目录的速度(n+m,n*m) (2)在不同的用户目录中,可以使用相同的文件名。 (3)不同用户还可使用不同的文件名来访问系统中的同一个共享文件(4)可实现对文件的保护和保密作用。 (5)两级文件目录虽然解决了不同用户之间文件同名的问题,但同一用户的文件不能同名。2022/9/11933.多级目录结构(1)目录结构多级目录结构又称为树形目录结构主目录称为根目录,数据文件称为树叶,其他目录作为树的结点为提高文件系统的灵活性,允许一个目录文件中的目录项既作为目录文件的FCB

36、,又是数据文件的FCB2022/9/1194图6-19 多级目录结构 方块代表目录文件圆圈代表数据文件2022/9/1195(2)路径名在树形目录结构中,从根目录到任何数据文件,都只有一条惟一的通路。在该路径上从树的根(即主目录)开始,把全部目录文件名与数据文件名,依次地用“/”连接起来,即构成该数据文件的路径名(path name)系统中的每一个文件都有惟一的路径名例如,在图6-19中用户B为访问文件J(15),应使用其路径名/B/F/J来访问。2022/9/1196图6-19 多级目录结构 /B/F/J2022/9/1197(3)当前目录为每个进程设置一个“当前目录”,又称为“工作目录”。

37、进程对各文件的访问都相对于“当前目录”而进行把从当前目录开始直到数据文件为止所构成的路径名,称为相对路径名(relative path name)把从树根开始的路径名称为绝对路径名(absolute path name)2022/9/11984.增加和删除目录删除目录的两种处理方法:(1)不删除非空目录当目录(文件)不空时,不能将其删除,而为了删除一个非空目录,必须先删除目录中的所有文件,使之先成为空目录,后再予以删除。在MS-DOS中就是采用这种删除方式。(2)可删除非空目录当要删除一目录时,如果在该目录中还包含有文件,则目录中的所有文件和子目录也同时被删除在Windows中就是采用这种删除

38、方式。不重名2022/9/1199特点 (1)层次清楚 (2)解决了用户文件重名问题 (3)搜索速度快 2022/9/111006.4 目录管理6.4.1 文件控制块和索引结点6.4.2 目录结构6.4.3 目录查询技术2022/9/111016.4.3 目录查询技术 1.线性检索法(顺序检索法)图6-20 查找/usr/ast/mbox的步骤 索引结点2022/9/111022.Hash方法 系统利用用户提供的文件名并将它变换为文件目录的索引值,再利用该索引值到目录中去查找,提高检索速度。一种处理此“冲突”的有效规则是: (1)在利用Hash法索引查找目录时,如果目录表中相应的目录项是空的,

39、则表示系统中并无指定文件。 (2)如果目录项中的文件名与指定文件名相匹配, 则表示该目录项正是所要寻找的文件所对应的目录项,故而可从中找到该文件所在的物理地址。 (3)如果在目录表的相应目录项中的文件名与指定文件名并不匹配,则表示发生了“冲突”,此时须将其Hash值再加上一个常数(该常数应与目录的长度值互质),形成新的索引值,再返回到第一步重新开始查找。 2022/9/11103内容概述6.1 文件和文件系统 6.2 文件的逻辑结构 6.3 外存分配方式 6.4 目录管理 6.5 文件存储空间的管理 6.6 文件共享与文件保护 6.7 数据一致性控制(了解)2022/9/111046.5 文件

40、存储空间的管理6.5.1 空闲表法和空闲链表法6.5.2 位示图法6.5.3 成组链接法存储管理的任务是为每个文件分配必要的外存空间,提高外存的利用率,并能有助于提高文件系统的工作速度。由于文件存储设备是以块为单位进行管理的,因此,文件存储空间的管理实质上是一个空闲块的组织和管理问题,它包括空闲块的组织,空闲块的分配与空闲块的回收。 2022/9/111056.5.1 空闲表法和空闲链表法1.空闲表法 图6-21 空闲盘块表 序号第一空闲盘块号空闲盘块数12429331554可以采用连续分配方式2022/9/11106文件存储空间管理的基本分配单位是盘块空闲表法空闲表属于连续分配方式,与内存的

41、动态分配方式雷同,为每个文件分配一个连续的存储空间为外存上的所有空闲区建立一张空闲表,每个空闲区对应于一个闲表项,将所有空闲区按起始盘块号递增的顺序排列存储空间的分配与回收可采用首次适应算法、循环首次适应算法等如对换方式中对对换空间的分配就采用连续分配,主要目的是提高速度系统中内存很少用连续分配,而外存为了提高分配速度,减少访问磁盘的I/O频度,也采用连续分配方式2022/9/111072.空闲链表法(1)空闲盘块链将磁盘上的所有空闲空间以盘块为单位拉成一条链用户请求分配时,系统从链首开始依次摘下适当数目的空闲盘块分配给用户。回收放回末尾。优点:分配和回收一个盘块简单缺点:链表可能很长(2)空

42、闲盘区链将磁盘上的所有空闲盘区(每区可有若干个盘块)拉成一条链每个盘区上除含有用于指示下一个空闲盘区的指针外,还应有能指明本盘区大小的信息分配方法与内存的动态分配类似优点:链表较短缺点:分配回收复杂。注意盘块数2022/9/111086.5 文件存储空间的管理6.5.1 空闲表法和空闲链表法6.5.2 位示图法6.5.3 成组链接法2022/9/111096.5.2 位示图法 1.位示图用二进制的一位来表示磁盘中一个盘块的使用情况0表示盘块空闲,1表示盘块已分配由所有盘块所对应的二进制位构成的一个集合称为位示图,通常可用m*n个位数来构成位示图,并使m*n等于磁盘总块数2022/9/11110

43、图6-22 位示图 假定磁盘的块长为1KB,对于200MB的磁盘需有200K位来映射,即需要2001024/8=51200字节,即51200/1024=25个物理块来构成一个位示图。 2022/9/111112.盘块的分配 (1)顺序扫描位示图,从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。 (2)将所找到的一个或一组二进制位,转换成与之相应的盘块号。假定找到的其值为“0”的二进制位,位于位示图的第i行、第j列,则其相应的盘块号应按下式计算:b=n(i-1)+j式中,n代表每行的位数。 (3)修改位示图, 令mapi,j=1。 2022/9/111123.盘块的回收(1)将回收

44、盘块的盘块号转换成位示图中的行号和列号。 转换公式为i=(b-1)DIV n+1j=(b-1)MOD n+1(2)修改位示图, 令mapi,j=0 (当“0”表示盘块空闲时)如上例中,第16号物理块,可计算得i=(16-1) DIV 16 + 1=1j=(16-1) MOD 16 +1=16同理,第17块可计算得i=(17-1)DIV 16 +1 =2j=(17-1) MOD 16+1=1 书P207错了第三版对了P2332022/9/11113优点:(1)很容易找到一个或一组相邻的空闲盘块,即找一组连续的0(2)位示图占用空间少,可放在内存,可省掉许多启动磁盘操作。2022/9/111146

45、.5 文件存储空间的管理6.5.1 空闲表法和空闲链表法6.5.2 位示图法6.5.3 成组链接法2022/9/111156.5.3 成组链接法在大型文件系统中,空闲表或空闲链表太长,在UNIX系统中,两种方法结合形成成组链接法1.空闲盘块的组织将空闲表和空闲链表结合形成的空闲盘块管理方法空闲盘块号栈:用来存放当前可用的一组空闲盘块号以及栈中尚有的空闲盘块数N文件区中的所有空闲盘块被分成若干个组,如100块/组将每组含的有盘块数和该组所有盘块号记入前一组第一个盘块中将第一组的空闲盘块数和所有盘块号记入空闲盘块号栈2022/9/11116图6-23 空闲盘块的成组链接法 栈顶指针栈临界资源互斥访

46、问2022/9/11117说明:设每100盘块为1组,系统共10000个盘块,每块大小为1KB,从201至7999用于文件区,则第1组为盘块号201-300,第2组为301-400,.,最后一组为7901-7999每一组的盘块总数N和盘块号记入前一组的第一个盘块的S.free(0)S.free(99)将第一组盘块总数和盘块号记入空闲盘块号栈最末一组的S.free(0)为“0”,表示空闲盘块链结束2022/9/111182.空闲盘块的分配与回收(1)分配检查空闲盘块号栈是否上锁,如未上锁,便从栈顶取出一空闲盘块号,将与之对应的盘块分配给用户,然后将栈顶指针下移一格若该盘块号已是栈底,即S.fre

47、e(0),这是当前栈中最后一个可分配的盘块号调用磁盘读过程,将栈底盘块号所对应盘块的内容读入栈中,作为新的盘块号栈的内容,并把原栈底对应的盘块分配出去分配一相应的缓冲区把栈中的空闲盘块数减1并返回2022/9/111192.空闲盘块的分配与回收 (1)分配(2)回收将回收盘块的盘块号记入空闲盘块号栈的顶部,并执行空闲盘块数加1操作当栈已满时(数目已达100时),记入新回收的盘块中,再将其盘块号作为新栈底2022/9/11120内容概述6.1 文件和文件系统 6.2 文件的逻辑结构 6.3 外存分配方式 6.4 目录管理 6.5 文件存储空间的管理 6.6 文件共享与文件保护 6.7 数据一致性

48、控制(了解)2022/9/111216.6 文件共享与文件保护6.6.1 基于索引结点的共享方式6.6.2 利用符号链实现文件共享6.6.3 磁盘容错技术(了解)2022/9/111221.基本概念文件共享是指一个文件可以被多个授权的用户共同使用。 文件的共享要解决两个问题。一是如何实现共享,二是对各类共享文件的用户进行存取控制。 2.实现文件共享的方法 (1)绕弯路法 (2)连访法 (3)利用基本文件目录实现文件共享(4)基于索引结点的共享方式(5)利用符号链实现文件共享2022/9/11123(1)绕弯路法用“*”表示一个目录的父目录。假定当前目录为F(12),那么可用*/E/J访问文件J

49、(17) */*/C/A访问文件A(9)2022/9/11124(2)连访法在相应的目录项之间进行虚线链接虚线1:用户B的作业F能访问作业E的文件J(17)虚线2:用户B的作业D能访问用户C的文件A(9)2022/9/11125连访法说明:(1)文件说明中加一项“连访”属性,指明物理地址部分是指向文件,还是共享文件的目录表目。(2)撤销一个表目时,必须判别是否有共享用户还要使用,所以增加“用户计数”一项。2022/9/11126(3)利用基本文件目录实现文件共享 如果一个用户想共享另一个用户的文件,只需在自己的目录文件中增加一个目录项,填上他为该文件所起的符号名及该共享文件的唯一标识符即可。2

50、022/9/11127图6-24 包含有共享文件的文件系统 文件共享 指系统应允许多个用户共享同一份文件,在系统中只保留一份共享文件的备份2022/9/11128图6-25 基于索引结点的共享方式 将诸如文件的物理地址和其它文件属性等信息放在索引结点中,文件目录中只设置文件名及指向相应索引结点的指针链接用户数6.6.1基于索引结点共享2022/9/11129图6-26 进程B链接前后的情况 C还要为用户B使用文件交钱2022/9/111306.6 文件共享与文件保护6.6.1 基于索引结点的共享方式6.6.2 利用符号链实现文件共享6.6.3 磁盘容错技术(了解)2022/9/111316.6

51、.2 利用符号链实现文件共享 为使B能共享C的一个文件F,可以由系统创建一个LINK类型的新文件,也取名为F,以实现B的目录中与文件F的链接。在新文件中只包含被链接文件F的路径名。这种链接方法称为符号链接(Symbolic Linking)在利用符号链方式实现文件共享时, 只是文件主才拥有指向其索引结点的指针;而共享该文件的其他用户,则只有该文件的路径名,并不拥有指向其索引结点的指针可用于计算机网络上共享文件2022/9/11132图 利用符号链实现文件共享2022/9/11133优点:(1)当C用户删除F时,B用户LINK类型文件也找不到文件,不会像以前留下悬空指针。(2)能用于链接世界上任

52、何地方文件,加上机器名的文件路径缺点:(1)LINK类型文件中放路径名,系统逐个分量去查目录,找索引结点,慢,需要多次地启动磁盘。(2)符号链是一个文件,该文件非常简单,却要配置一个索引结点,耗费一定的磁盘空间。2022/9/111346.6 文件共享与文件保护6.6.1 基于索引结点的共享方式6.6.2 利用符号链实现文件共享6.6.3 磁盘容错技术(了解)2022/9/11135文件的保护存取控制矩阵(如表6.1所示)存取控制表(如表6.2所示 )2022/9/11136表6.1 存取控制矩阵 文件用户12345678101001001210100100300010010401010100510101001600011100701100010文件的保护2022/9/11137表6.2 存取控制表文件用户WWadmin RWEA组 RB组 WC组 E其他 NONE2022/9/11138口令使用口令的优点是: 简便。节省空间。使用口令缺点是: 可靠性差。口令易被窃取。2022/9/11139加密 为防止文件内容泄密,用户在创建文件时对其编码加密,成为密码文件。合法授权用户得到该文件的密钥后,才可对文件解码解密。加密方法很多,但都要以牺牲系统效率为代价。2022/9/11140内容概述6.1 文件和文件系统 6.2 文件的逻辑结构 6.3 外存分配方式 6.4 目