第六章计算机操作系统文件管理课件

学院:计算机与信息技术学院教师:刘贤梅第六章文件管理1/10/20231学院:计算机与信息技术学院第六章文件管理1/9/202在现代计算机系统中,用到大量的程序和数据,由于内存容量和存储特性的限制,这些内容必须以文件的形式保存在外存操作系统必须提供对外存的文件管理的功能,即构成文件系统操作系统中包括文件管理、文件存取、共享和文件保护文件是具有文件名的若干相关元素的集合文件系统的管理功能是通过把它所管理的程序和数据组织成一系列文件的方法来实现的1/10/20232在现代计算机系统中,用到大量的程序和数据,由于内存容量和存储内容概述6.1文件和文件系统6.2文件的逻辑结构6.3外存分配方式6.4目录管理6.5文件存储空间的管理6.6文件共享与文件保护6.7数据一致性控制(了解)1/10/20233内容概述6.1文件和文件系统1/9/202336.1文件和文件系统6.1.1文件、记录和数据项6.1.2文件类型和文件系统模型6.1.3文件操作1/10/202346.1文件和文件系统6.1.1文件、记录和数据项1/9/6.1.1文件、记录和数据项

1.数据项(1)基本数据项用于描述一个对象的属性的字符集,是数据组织中可以命名的最小逻辑数据单位,即原子数据,又称为数据元素或字段如描述一个学生:学号、姓名、年龄、班级(2)组合数据项由若干个基本数据项组成,简称组项如工资包括基本工资、工龄工资、奖金等基本数据项除数据名外,还应有数据类型1/10/202356.1.1文件、记录和数据项1.数据项1/9/202352.记录记录是一组相关数据项的集合,用于描述一个对象在某方面的属性一个记录应包含哪些数据项,取决于需要描述对象的哪个方面一个对象,由于他所处的环境不同可把他作为不同的对象一个学生,当把他作为班上的一名学生时,对他的描述应使用学号、姓名、年龄及所在系班,也可能还包括他所学过的课程的名称、成绩等数据项若把学生作为一个医疗对象时,对他描述的数据项则应使用诸如病历号、姓名、性别、出生年月、身高、体重、血压及病史等项能惟一标识一个记录的数据项称为关键字(key)1/10/202362.记录1/9/202363.文件文件是指由创建者所定义的、具有文件名的一组相关元素的集合可分为有结构文件和无结构文件有结构文件由若干个相关记录组成,如上例中学生文件无结构文件则被看成是一个字符流,如C语言源程序文件在文件系统中是一个最大的数据单位,它描述了一个对象集例如,可以将一个班的学生记录作为一个文件一个文件必须要有一个文件名,它通常是由一串ASCII码或(和)汉字构成1/10/202373.文件1/9/202376.1文件和文件系统6.1.1文件、记录和数据项6.1.2文件类型和文件系统模型6.1.3文件操作1/10/202386.1文件和文件系统6.1.1文件、记录和数据项1/9/6.1.2文件类型和文件系统模型1.文件类型(1)按用途分类系统文件

有关操作系统及其它系统程序的信息所组成的文件。这类文件对用户不直接开放,只能通过系统调用为用户服务。用户文件 由用户委托操作系统保存的文件,如源程序文件,目标程序文件,以及由原始数据、计算结果等组成的文件。库文件 由标准子程序及常用的应用程序组成的文件。这类文件允许用户调用,但不允许用户修改。1/10/202396.1.2文件类型和文件系统模型1.文件类型1/9/206.1.2文件类型和文件系统模型1.文件类型(1)…(2)按文件中数据的形式分类源文件目标文件可执行文件(3)按存取控制属性分类只执行文件只读文件

允许文件主及核准的用户读,但不允许写的文件。读写文件 允许文件主及核准的用户读、写,但禁止未核准的用户读、写的文件。1/10/2023106.1.2文件类型和文件系统模型1.文件类型1/9/202.文件系统模型图6-2文件系统模型对象及其属性(对象:文件、目录、磁盘存储空间)对对象操纵和管理的软件集合文件系统接口用户(程序)1/10/2023112.文件系统模型图6-2文件系统模型对象及其属性(对象(1)对象及其属性文件管理系统管理的对象有:①文件。它作为文件管理的直接对象。②目录。为了方便用户对文件的存取和检索,在文件系统中必须配置目录。对目录的组织和管理是方便用户和提高对文件存取速度的关键。③磁盘(磁带)存储空间。 文件和目录必定占用存储空间,对这部分空间的有效管理,不仅能提高外存的利用率,而且能提高对文件的存取速度。1/10/202312(1)对象及其属性1/9/202312 (1)…(2)对对象操纵和管理的软件集合 这是文件管理系统的核心部分。文件系统的功能大多是在这一层实现的,完成:对文件存储空间的管理对文件目录的管理用于将文件的逻辑地址转换为物理地址的机制对文件读和写的管理对文件的共享与保护等功能1/10/202313 (1)…1/9/202313(3)文件系统的接口为方便用户使用文件系统,文件系统通常向用户提供两种类型的接口:

①命令接口。这是指作为用户与文件系统交互的接口。用户可通过键盘终端键入命令,取得文件系统的服务。

②程序接口。这是指作为用户程序与文件系统的接口。用户程序可通过系统调用来取得文件系统的服务。1/10/202314(3)文件系统的接口1/9/2023146.1文件和文件系统6.1.1文件、记录和数据项6.1.2文件类型和文件系统模型6.1.3文件操作1/10/2023156.1文件和文件系统6.1.1文件、记录和数据项1/9/6.1.3文件操作最基本的文件操作(1)创建文件。分配必要的外存空间,在文件系统的目录中建立一个目录项。(2)删除文件。从目录中删除该目录项,回收存储空间。(3)读文件。查找到指定的目录项,从外存读文件到内存。(4)写文件。查找到指定的目录项,进行写操作。(5)截断文件。文件内容陈旧要更新,一:删除,重新建立。二:文件长度设成0。(6)设置文件的读/写位置。用于设置指针位置。1/10/2023166.1.3文件操作最基本的文件操作1/9/2023162.文件的“打开”和“关闭”操作所谓“打开”OPEN,是指系统将指名文件的属性从外存拷贝到内存打开文件表的一个表目中,并将该表目的编号(或称为索引)返回给用户当用户再要求对该文件进行相应的操作时,便可利用系统所返回的索引号向系统提出操作请求。系统这时便可直接利用该索引号到打开文件表中去查找,从而避免了对该文件的再次检索“关闭”(CLOSE)系统调用来关闭此文件,OS将会把该文件从打开文件表中的表目上删除掉1/10/2023172.文件的“打开”和“关闭”操作1/9/2023173.其它文件操作(1)文件属性操作改变文件名改变拥有者修改权限查询状态(2)有关目录操作创建目录删除目录改变当前目录(3)实现文件共享的系统调用(4)用于对文件系统进行操作的系统调用1/10/2023183.其它文件操作1/9/202318内容概述6.1文件和文件系统6.2文件的逻辑结构6.3外存分配方式6.4目录管理6.5文件存储空间的管理6.6文件共享与文件保护6.7数据一致性控制(了解)1/10/202319内容概述6.1文件和文件系统1/9/2023196.2文件的逻辑结构6.2.1文件逻辑结构的类型6.2.2顺序文件6.2.3索引文件6.2.4索引顺序文件6.2.5直接文件和哈希文件1/10/2023206.2文件的逻辑结构6.2.1文件逻辑结构的类型1/9/对于一个文件存在着以下两种形式的结构(1)文件的逻辑结构(FileLogicalStructure)从用户观点看到的文件组织形式,独立于文件的物理特性又称为文件组织(FileOrganization)(2)文件的物理结构又称为文件的存储结构,指文件在外存上的存储组织形式对逻辑结构的基本要求提高检索速度便于修改降低文件的存储费用1/10/202321对于一个文件存在着以下两种形式的结构1/9/2023216.2.1文件逻辑结构的类型1.有结构文件(又称记录式文件)按记录长度分(1)定长记录(2)变长记录根据用户和系统管理需要分(1)顺序文件(2)索引文件(3)索引顺序文件2.无结构文件流式文件其长度以字节为单位采用读写指针来指出下一个要访问的字符如源程序、可执行文件、库函数等1/10/2023226.2.1文件逻辑结构的类型1.有结构文件(又称记录式文图记录式文件(a)定长记录文件;(b)变长记录文件1/10/202323图记录式文件1/9/2023233、两种文件的比较流式文件就像给一张白纸给用户,用户可将他的信息任意地写到纸上,没有任何格式上的限制。记录式文件就像给一张表格给用户,用户要按表规定的格式填信息。显然,有结构式文件对用户的限制很大,使用起来就不方便,在UNIX系统中,所有的文件都被看作是流式文件,即使是有结构文件,也被视为流式文件。1/10/2023243、两种文件的比较1/9/2023246.2文件的逻辑结构6.2.1文件逻辑结构的类型6.2.2顺序文件6.2.3索引文件6.2.4索引顺序文件6.2.5直接文件和哈希文件1/10/2023256.2文件的逻辑结构6.2.1文件逻辑结构的类型1/9/6.2.2顺序文件1.逻辑记录的排序(1)串结构

各记录之间的顺序与关键字无关通常由时间来决定存在问题(2)顺序结构文件中的所有记录按关键字(词)排列记录号学号姓名性别出生时间1001赵男1965.8.12003钱女1971.6.173004孙男1980.12.114005李男1983.4.155006周女1976.2.106007吴男1977.11.121/10/2023266.2.2顺序文件1.逻辑记录的排序记录号学号姓名性别出生图6-3定长和变长记录文件2.对顺序文件(SequentialFile)的读/写操作1/10/202327图6-3定长和变长记录文件2.对顺序文件(Sequent3.顺序文件的优缺点优点顺序文件的最佳应用场合,是在对诸记录进行批量存取时,即每次要读或写一大批记录只有顺序文件才能存储在磁带上,并能有效地工作缺点如果用户(程序)要求查找或修改单个记录,顺序文件所表现出来的性能就可能很差(顺序查找的ASL很大)(串结构)如果想增加或删除一个记录,都比较困难(需移动大量数据,顺序结构(排序))1/10/2023283.顺序文件的优缺点1/9/2023286.2文件的逻辑结构6.2.1文件逻辑结构的类型6.2.2顺序文件6.2.3索引文件6.2.4索引顺序文件6.2.5直接文件和哈希文件1/10/2023296.2文件的逻辑结构6.2.1文件逻辑结构的类型1/9/6.2.3索引文件对定长记录文件,如果要查找第i个记录,可直接根据下式计算来获得第i个记录相对于第一个记录首址的地址Ai=i×L对于可变长度记录的文件,要查找其第i个记录时,须首先计算出该记录的首地址,Li为第i个记录长度1/10/2023306.2.3索引文件对定长记录文件,如果要查找第i个记录,图6-4索引文件的组织1/10/202331图6-4索引文件的组织1/9/2023316.2文件的逻辑结构6.2.1文件逻辑结构的类型6.2.2顺序文件6.2.3索引文件6.2.4索引顺序文件6.2.5直接文件和哈希文件1/10/2023326.2文件的逻辑结构6.2.1文件逻辑结构的类型1/9/索引顺序文件(IndexSequentialFile)是最常见的一种逻辑文件组织形式,是顺序文件与索引文件的结合克服了变长记录文件不便于直接存取的缺点,代价也不太大将顺序文件中的所有记录分为若干个组,为每组中的第一个记录建立索引项,其中含有该记录的键值及指向该记录的指针6.2.4索引顺序文件1/10/202333索引顺序文件(IndexSequentialFile)是图6-5索引顺序文件1/10/202334图6-5索引顺序文件1/9/2023346.2文件的逻辑结构6.2.1文件逻辑结构的类型6.2.2顺序文件6.2.3索引文件6.2.4索引顺序文件6.2.5直接文件和哈希文件1/10/2023356.2文件的逻辑结构6.2.1文件逻辑结构的类型1/9/6.2.5直接文件和哈希文件键值转换(Keytoaddresstransformation)由记录键值到记录物理地址的转换直接文件根据给定的记录键值,直接获得指定记录的物理地址哈希(Hash)文件利用哈希函数将记录键值转换为相应记录的地址1/10/2023366.2.5直接文件和哈希文件键值转换(Keytoadd1.直接文件对于直接文件,则可根据给定的记录键值,直接获得指定记录的物理地址。换言之,记录键值本身就决定了记录的物理地址。这种由记录键值到记录物理地址的转换被称为键值转换(Keytoaddresstransformation)。组织直接文件的关键,在于用什么方法进行从记录值到物理地址的转换。1/10/2023371.直接文件对于直接文件,则可根据给定的记录键值,2.哈希(Hash)文件图6-6Hash文件的逻辑结构1/10/2023382.哈希(Hash)文件图6-6Hash文件的逻辑结构1内容概述6.1文件和文件系统6.2文件的逻辑结构6.3外存分配方式

6.4目录管理6.5文件存储空间的管理6.6文件共享与文件保护6.7数据一致性控制(了解)1/10/202339内容概述6.1文件和文件系统1/9/202339如何才能有效地利用外存空间?如何提高对文件的访问速度?1/10/202340如何才能有效地利用外存空间?1/9/202340文件的物理结构文件的物理结构是指逻辑文件在存储设备(外存)上的存储组织形式,它与存储介质的存储特性有关,还与所采用的外存分配方式有关物理块是分配和传输信息的基本单位,物理块与外存设备有关文件在逻辑上都可看作是连续的,但在物理设备上存放时却有不同的方式,如连续分配、链接分配、索引分配等1/10/202341文件的物理结构文件的物理结构是指逻辑文件在存储设备(外存)上6.3外存分配方式6.3.1连续分配6.3.2链接分配6.3.3索引分配1/10/2023426.3外存分配方式6.3.1连续分配1/9/2023426.3.1连续分配连续分配(ContinuousAllocation)要求为每一个文件分配一组相邻接的盘块。一组盘块定义了磁盘上的一段线性地址在采用连续分配方式时,可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中,这样所形成的文件结构称为顺序文件结构,此时的物理文件称为顺序文件1/10/2023436.3.1连续分配连续分配(ContinuousAllo6.3.1连续分配图6-7磁盘空间的连续分配图中假设记录和盘块大小相同1/10/2023446.3.1连续分配图6-7磁盘空间的连续分配图中假设1/10/2023451/9/2023456.3外存分配方式6.3.1连续分配6.3.2链接分配6.3.3索引分配1/10/2023466.3外存分配方式6.3.1连续分配1/9/2023466.3.2链接分配链接分配(ChainedAllocation)可通过在每个盘块上的链接指针,将同属于一个文件的多个离散的盘块链接成一个链表,把这样形成的物理文件称为链接文件消除了外部碎片,提高外存利用率文件动态增长时,可动态地为它分配盘块文件的增删改方便(这种文件结构不要求连续存放)文件创建时用户不必指出文件的大小缺点只适用于顺序存取,若查找文件中的某一块必须从头开始,随机存取效率太低,如果访问文件的最后的内容,实际上是要访问整个文件可靠性差,若某一块出错,则链断开,文件不完整增加一个链接指针1/10/2023476.3.2链接分配链接分配(ChainedAllocat链接方式又分为两种形式: 1.隐式链接 2.显示链接1/10/202348链接方式又分为两种形式:1/9/202348图6-8磁盘空间的链接式分配1.隐式链接1/10/202349图6-8磁盘空间的链接式分配1.隐式链接1/9/20232.显式链接(解决查找时多次访 问磁盘的问题)图6-9显式链接结构1/10/2023502.显式链接(解决查找时多次访 问磁盘的问题)图6-9图6-10MS-DOS的文件物理结构1/10/202351图6-10MS-DOS的文件物理结构1/9/202351链接分配——显式链接文件分配表(FileAllocationTable,FAT)用于记录外存分配状况,每个盘块占一项,放在内存中(提高查找速度)表的序号为物理盘块号,从0至N-1分配给一个文件的所有物理块都在该表中标出,文件的第一个盘块号记入文件的FCB中1/10/202352链接分配——显式链接文件分配表(FileAllocatio6.3外存分配方式6.3.1连续分配6.3.2链接分配6.3.3索引分配1/10/2023536.3外存分配方式6.3.1连续分配1/9/2023536.3.3索引分配1.单级索引分配

链接分配方式虽然解决了连续分配方式所存在的问题,但又出现了另外两个问题,即:(1)不能支持高效的直接存取。要对一个较大的文件进行直接存取,须首先在FAT中顺序地查找许多盘块号。(2)FAT需占用较大的内存空间。需要把整个FAT都调入内存。索引分配为每个文件分配一个索引块,把分配给该文件的所有盘块号都记录在该索引块中在建立一个文件时,便为之建立的目录项中填上指向该索引块的指针1/10/2023546.3.3索引分配1.单级索引分配索引分配1/9/20图6-11索引分配方式1/10/202355图6-11索引分配方式1/9/202355若每个盘块大小为1KB,每个盘块号占4B,则索引块中可存放256个盘块号,用一个索引块只支持256K大小文件可能要花费较多的外存空间。当文件小时,索引块利用率低。文件太大时,需要多个索引块,通过指针链接起来,效率低。1/10/202356若每个盘块大小为1KB,每个盘块号占4B,则索引块中可存放22.多级索引分配图6-12两级索引分配1/10/2023572.多级索引分配图6-12两级索引分配1/9/202357图6-13混合索引方式直接地址物理盘块索引块3.混合索引分配方式1/10/202358图6-13混合索引方式直接地址物理盘块索引块3.混合索引(1)直接地址为了提高对文件的检索速度,在索引结点中可设置10个直接地址项,即用iaddr(0)~iaddr(9)来存放直接地址(盘块4KB,共40KB)(2)一次间接地址对于大、中型文件,可再利用索引结点中的地址项iaddr(10)来提供一次间接地址。这种方式的实质就是一级索引分配方式(盘块4KB,共4MB)(3)多次间接地址当文件长度大于4MB+40KB时(一次间址与10个直接地址项),系统还须采用二次间址分配方式。这时,用地址项iaddr(11)提供二次间接地址。该方式的实质是两级索引分配方式(共4GB),还可以提供三次间址iaddr(12)(共4TB)1/10/202359(1)直接地址1/9/202359内容概述6.1文件和文件系统6.2文件的逻辑结构6.3外存分配方式6.4目录管理

6.5文件存储空间的管理6.6文件共享与文件保护6.7数据一致性控制(了解)1/10/202360内容概述6.1文件和文件系统1/9/202360目录管理要求(1)实现“按名存取”文件系统最基本的功能为实现文件的按名存取,每个文件首先应该具有一个文件名与之对应。(2)提高对目录的检索速度加快目录检索速度,从而提高文件存取速度,追求的主要目标。(3)文件共享一份文件副本供不同用户使用(4)允许文件重名允许不同用户对不同文件取相同的名字1/10/202361目录管理要求(1)实现“按名存取”1/9/2023616.4目录管理6.4.1文件控制块和索引结点6.4.2目录结构6.4.3目录查询技术 目录管理的任务是为每个文件建立目录项,并对众多的目录加以组织,以实现方便的按名存取,实现文件的共享,提供快速的目录查询手段,提高文件的检索速度。1/10/2023626.4目录管理6.4.1文件控制块和索引结点 目录管理6.4.1文件控制块和索引结点1.文件控制块(FCB)是用于描述和控制文件的数据结构文件管理程序可借助FCB中的信息对文件施以各种操作文件控制块的有序集合称为文件目录,即一个文件控制块就是一个文件目录项通常,一个文件目录本身也被看作是一个文件,称为目录文件1/10/2023636.4.1文件控制块和索引结点1.文件控制块(FCB)1/6.4.1文件控制块和索引结点文件控制块中的信息(1)基本信息类文件名文件物理位置文件逻辑结构文件的物理结构(2)文件控制信息类文件拥有者权限核准用户权限一般用户权限(3)使用信息类文件建立日期文件修改日期1/10/2023646.4.1文件控制块和索引结点文件控制块中的信息1/9/图6-14MS-DOS的文件控制块1/10/202365图6-14MS-DOS的文件控制块1/9/2023652.索引结点(1)索引结点的引入文件目录通常放在磁盘上,当文件很多时,占用大量磁盘空间检索文件过程中,只需使用文件名,而不用其他信息将文件描述信息单独形成一个数据结构,称为索引结点,也称为i结点在文件目录中的每个目录项,仅包含文件名和指向索引结点的指针引入索引结点后,使文件的目录项更小,占用磁盘空间少,检索速度加快1/10/2023662.索引结点1/9/202366(2)磁盘索引结点①文件主标识符拥有该文件的个人或小组的标识符②文件类型正规文件、目录文件或特别文件③文件存取权限各类用户对该文件的存取权限④文件物理地址13个地址项,给出文件所在盘块编号⑤文件长度以字节为单位的文件长度⑥文件连接计数指向该文件的指针的个数⑦文件存取时间指出最近被进程存取的时间、最近被修改的时间及索引结点最近被修改的时间1/10/202367(2)磁盘索引结点1/9/202367(3)内存索引结点:文件打开时调入内存的,增加了:①索引结点编号。用于标识内存索引结点。②状态。指示i结点是否上锁或被修改。③访问计数。每当有一进程要访问此i结点时,将该访问计数加1,访问完再减1。④文件所属文件系统的逻辑设备号。⑤链接指针。设置有分别指向空闲链表和散列队列的指针。1/10/202368(3)内存索引结点:文件打开时调入内存的,增加了:1/9/26.4目录管理6.4.1文件控制块和索引结点6.4.2目录结构6.4.3目录查询技术1/10/2023696.4目录管理6.4.1文件控制块和索引结点1/9/206.4.2目录结构目前常用的目录结构有:1.单级目录2.两级目录3.多级目录1/10/2023706.4.2目录结构目前常用的目录结构有:1/9/202376.4.2目录结构图6-16单级目录1.单级目录结构整个系统只建立一张目录表,每个文件占一个目录项文件名物理地址文件说明状态位文件名1文件名2…1/10/2023716.4.2目录结构图6-16单级目录1.单级目录结构单级目录优点(1)易于实现,管理简单(2)能实现按名存取单级目录缺点(1)查找速度慢(顺序查找,N/2)(2)不允许重名(在多道程序设计下,很难保证)(3)不便于实现文件共享(所有用户必须用同一个名字共享一个文件)单级目录只实现了目录管理的第一项功能,即“按名存取”,只能适用于单用户环境1/10/202372单级目录优点1/9/2023722.两级目录为每个用户建立一个单独的用户文件目录UFD(UserFileDirectory),由用户所有文件的FCB组成在系统中建立主文件目录MFD(MasterFileDirectory),每个用户目录文件在主文件目录中占一个目录项1/10/2023732.两级目录1/9/202373图6-17两级目录结构主文件目录MFD用户文件目录UFD1/10/202374图6-17两级目录结构主文件目录MFD用户文件目录UFD3.多级目录结构(1)目录结构多级目录结构又称为树形目录结构主目录称为根目录,数据文件称为树叶,其他目录作为树的结点为提高文件系统的灵活性,允许一个目录文件中的目录项既作为目录文件的FCB,又是数据文件的FCB1/10/2023753.多级目录结构1/9/202375图6-18多级目录结构1/10/202376图6-18多级目录结构1/9/202376(2)路径名在树形目录结构中,从根目录到任何数据文件,都只有一条惟一的通路。在该路径上从树的根(即主目录)开始,把全部目录文件名与数据文件名,依次地用“/”连接起来,即构成该数据文件的路径名(pathname)系统中的每一个文件都有惟一的路径名例如,在图6-18中用户B为访问文件J(15),应使用其路径名/B/F/J来访问。1/10/202377(2)路径名1/9/202377(3)当前目录为每个进程设置一个“当前目录”,又称为“工作目录”。进程对各文件的访问都相对于“当前目录”而进行把从当前目录开始直到数据文件为止所构成的路径名,称为相对路径名(relativepathname)把从树根开始的路径名称为绝对路径名(absolutepathname)1/10/202378(3)当前目录1/9/2023784.增加和删除目录删除目录的两种处理方法:(1)不删除非空目录当目录(文件)不空时,不能将其删除,而为了删除一个非空目录,必须先删除目录中的所有文件,使之先成为空目录,后再予以删除。在MS-DOS中就是采用这种删除方式。(2)可删除非空目录当要删除一目录时,如果在该目录中还包含有文件,则目录中的所有文件和子目录也同时被删除在Windows中就是采用这种删除方式。1/10/2023794.增加和删除目录1/9/202379特点

(1)层次清楚(2)解决了用户文件重名问题(3)搜索速度快1/10/202380特点1/9/2023806.4目录管理6.4.1文件控制块和索引结点6.4.2目录结构6.4.3目录查询技术1/10/2023816.4目录管理6.4.1文件控制块和索引结点1/9/206.4.3目录查询技术1.线性检索法(顺序检索法)图6-19查找/usr/ast/mbox的步骤1/10/2023826.4.3目录查询技术1.线性检索法(顺序检索法)图6-2.Hash方法系统利用用户提供的文件名并将它变换为文件目录的索引值,再利用该索引值到目录中去查找,提高检索速度。一种处理此“冲突”的有效规则是:(1)在利用Hash法索引查找目录时,如果目录表中相应的目录项是空的,则表示系统中并无指定文件。(2)如果目录项中的文件名与指定文件名相匹配,则表示该目录项正是所要寻找的文件所对应的目录项,故而可从中找到该文件所在的物理地址。(3)如果在目录表的相应目录项中的文件名与指定文件名并不匹配,则表示发生了“冲突”,此时须将其Hash值再加上一个常数(该常数应与目录的长度值互质),形成新的索引值,再返回到第一步重新开始查找。1/10/2023832.Hash方法一种处理此“冲突”的有效规则是:1/9/2内容概述6.1文件和文件系统6.2文件的逻辑结构6.3外存分配方式6.4目录管理6.5文件存储空间的管理

6.6文件共享与文件保护6.7数据一致性控制(了解)1/10/202384内容概述6.1文件和文件系统1/9/2023846.5文件存储空间的管理6.5.1空闲表法和空闲链表法6.5.2位示图法6.5.3成组链接法存储管理的任务是为每个文件分配必要的外存空间,提高外存的利用率,并能有助于提高文件系统的工作速度。由于文件存储设备是以块为单位进行管理的,因此,文件存储空间的管理实质上是一个空闲块的组织和管理问题,它包括空闲块的组织,空闲块的分配与空闲块的回收。1/10/2023856.5文件存储空间的管理6.5.1空闲表法和空闲链表法存6.5.1空闲表法和空闲链表法1.空闲表法

图6-20空闲盘块表序号第一空闲盘块号空闲盘块数12429331554——1/10/2023866.5.1空闲表法和空闲链表法1.空闲表法图6-20空文件存储空间管理的基本分配单位是盘块空闲表法空闲表属于连续分配方式,与内存的动态分配方式雷同,为每个文件分配一个连续的存储空间为外存上的所有空闲区建立一张空闲表,每个空闲区对应于一个闲表项,将所有空闲区按起始盘块号递增的顺序排列存储空间的分配与回收可采用首次适应算法、循环首次适应算法等如对换方式中对对换空间的分配就采用连续分配,主要目的是提高速度,P113系统中内存很少用连续分配,而外存为了提高分配速度,减少访问磁盘的I/O频度,也采用连续分配方式1/10/202387文件存储空间管理的基本分配单位是盘块1/9/2023872.空闲链表法(1)空闲盘块链将磁盘上的所有空闲空间以盘块为单位拉成一条链用户请求分配时,系统从链首开始依次摘下适当数目的空闲盘块分配给用户。回收放回末尾。优点:分配和回收一个盘块简单缺点:链表可能很长(2)空闲盘区链将磁盘上的所有空闲盘区(每区可有若干个盘块)拉成一条链每个盘区上除含有用于指示下一个空闲盘区的指针外,还应有能指明本盘区大小的信息分配方法与内存的动态分配类似优点:链表较短缺点:分配回收复杂。注意盘块数1/10/2023882.空闲链表法1/9/2023886.5文件存储空间的管理6.5.1空闲表法和空闲链表法6.5.2位示图法6.5.3成组链接法1/10/2023896.5文件存储空间的管理6.5.1空闲表法和空闲链表法16.5.2位示图法1.位示图用二进制的一位来表示磁盘中一个盘块的使用情况"0"表示盘块空闲,"1"表示盘块已分配由所有盘块所对应的二进制位构成的一个集合称为位示图,通常可用m*n个位数来构成位示图,并使m*n等于磁盘总块数1/10/2023906.5.2位示图法1.位示图1/9/202390图6-21位示图假定磁盘的块长为1KB,对于200MB的磁盘需有200K位来映射,即需要200×1024/8=51200字节,即51200/1024=25个物理块来构成一个位示图。1/10/202391图6-21位示图假定磁盘的块长为1KB,对于22.盘块的分配(1)顺序扫描位示图,从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。(2)将所找到的一个或一组二进制位,转换成与之相应的盘块号。假定找到的其值为“0”的二进制位,位于位示图的第i行、第j列,则其相应的盘块号应按下式计算:b=n(i-1)+j式中,n代表每行的位数。(3)修改位示图,令map［i,j］=1。1/10/2023922.盘块的分配(1)顺序扫描位示图,从中找出一个或3.盘块的回收(1)将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为i=(b-1)DIVn+1j=(b-1)MODn+1(2)修改位示图,令map［i,j］=0(当“0”表示盘块空闲时)如上例中,第16号物理块,可计算得i=(16-1)DIV16+1=1j=(16-1)MOD16+1=16同理,第17块可计算得i=(17-1)DIV16+1=2j=(17-1)MOD16+1=11/10/2023933.盘块的回收1/9/2023936.5文件存储空间的管理6.5.1空闲表法和空闲链表法6.5.2位示图法6.5.3成组链接法1/10/2023946.5文件存储空间的管理6.5.1空闲表法和空闲链表法16.5.3成组链接法在大型文件系统中,空闲表或空闲链表太长,在UNIX系统中,两种方法结合形成成组链接法1.空闲盘块的组织将空闲表和空闲链表结合形成的空闲盘块管理方法空闲盘块号栈:用来存放当前可用的一组空闲盘块号以及栈中尚有的空闲盘块数N文件区中的所有空闲盘块被分成若干个组,如100块/组将每组含的有盘块数和该组所有盘块号记入前一组第一个盘块中将第一组的空闲盘块数和所有盘块号记入空闲盘块号栈1/10/2023956.5.3成组链接法在大型文件系统中,空闲表或空闲链表太长图6-22空闲盘块的成组链接法1/10/202396图6-22空闲盘块的成组链接法1/9/202396内容概述6.1文件和文件系统6.2文件的逻辑结构6.3外存分配方式6.4目录管理6.5文件存储空间的管理6.6文件共享与文件保护

6.7数据一致性控制(了解)1/10/202397内容概述6.1文件和文件系统1/9/2023976.6文件共享与文件保护6.6.1基于索引结点的共享方式6.6.2利用符号链实现文件共享6.6.3磁盘容错技术(了解)1/10/2023986.6文件共享与文件保护6.6.1基于索引结点的共享方式1.基本概念文件共享是指一个文件可以被多个授权的用户共同使用。文件的共享要解决两个问题。一是如何实现共享,二是对各类共享文件的用户进行存取控制。2.实现文件共享的方法(1)绕弯路法(2)连访法(3)利用基本文件目录实现文件共享(4)基于索引结点的共享方式(5)利用符号链实现文件共享1/10/2023991.基本概念1/9/202399图6-24基于索引结点的共享方式将诸如文件的物理地址和其它文件属性等信息放在索引结点中,文件目录中只设置文件名及指向相应索引结点的指针6.6.1基于索引结点共享1/10/2023100图6-24基于索引结点的共享方式将诸如文件的物理地址和其图6-25进程B链接前后的情况1/10/2023101图6-25进程B链接前后的情况1/9/20231016.6文件共享与文件保护6.6.1基于索引结点的共享方式6.6.2利用符号链实现文件共享6.6.3磁盘容错技术(了解)1/10/20231026.6文件共享与文件保护6.6.1基于索引结点的共享方式6.6.2利用符号链实现文件共享为使B能共享C的一个文件F,可以由系统创建一个LINK类型的新文件,也取名为F,以实现B的目录中与文件F的链接。在新文件中只包含被链接文件F的路径名。这种链接方法称为符号链接(SymbolicLinking)在利用符号链方式实现文件共享时,只是文件主才拥有指向其索引结点的指针;而共享该文件的其他用户,则只有该文件的路径名,并不拥有指向其索引结点的指针可用于计算机网络上共享文件1/10/20231036.6.2利用符号链实现文件共享为使B能共享C的一个文件图利用符号链实现文件共享1/10/2023104图利用符号链实现文件共享1/9/20231046.6文件共享与文件保护6.6.1基于索引结点的共享方式6.6.2利用符号链实现文件共享6.6.3磁盘容错技术(了解)1/10/20231056.6文件共享与文件保护6.6.1基于索引结点的共享方式文件的保护存取控制矩阵(如表6.1所示)存取控制表(如表6.2所示)1/10/2023106文件的保护存取控制矩阵(如表6.1所示)1/9/202310表6.1存取控制矩阵

文件用户12345678101001001210100100300010010401010100510101001600011100701100010文件的保护1/10/2023107表6.1存取控制矩阵文件1234567810100100表6.2存取控制表文件用户WW文件名RWEB组RB组WC组E其他NONE1/10/2023108表6.2存取控制表文件WW文件名RWEB组RB组口令使用口令的优点是:简便。节省空间。使用口令缺点是: 可靠性差。口令易被窃取。1/10/2023109口令使用口令的优点是:1/9/2023109加密为防止文件内容泄密,用户在创建文件时对其编码加密,成为密码文件。合法授权用户得到该文件的密钥后,才可对文件解码解密。加密方法很多,但都要以牺牲系统效率为代价。1/10/2023110加密为防止文件内容泄密,用户在创建文件时对其编码加密内容概述6.1文件和文件系统6.2文件的逻辑结构6.3外存分配方式6.4目录管理6.5文件存储空间的管理6.6文件共享与文件保护6.7数据一致性控制(了解)1/10/2023111内容概述6.1文件和文件系统1/9/2023111本章小结文件管理的主要任务是分配外存空间,对用户文件和系统文件进行管理,方便用户使用,并保证文件的安全性。主要目的是提高外存的使用效率和方便用户读文件的使用。主要功能是文件存储空间的管理、目录的管理、文件读/写的管理、文件共享和保护。熟悉和掌握内容:文件、记录、数据项、文件分类、文件的组织(逻辑和物理结构)

文件存储空间的管理熟悉文件目录的管理(单级、两级、多级目录结构)、文件的共享与保护作业：P246，1/10/2023112本章小结文件管理的主要任务是分配外存空间,对用户文件和系统第六章授课结束，欢迎讨论!1/10/2023113第六章授课结束，欢迎讨论!1/9/2023113学院:计算机与信息技术学院教师:刘贤梅第六章文件管理1/10/2023114学院:计算机与信息技术学院第六章文件管理1/9/202在现代计算机系统中,用到大量的程序和数据,由于内存容量和存储特性的限制,这些内容必须以文件的形式保存在外存操作系统必须提供对外存的文件管理的功能,即构成文件系统操作系统中包括文件管理、文件存取、共享和文件保护文件是具有文件名的若干相关元素的集合文件系统的管理功能是通过把它所管理的程序和数据组织成一系列文件的方法来实现的1/10/2023115在现代计算机系统中,用到大量的程序和数据,由于内存容量和存储内容概述6.1文件和文件系统6.2文件的逻辑结构6.3外存分配方式6.4目录管理6.5文件存储空间的管理6.6文件共享与文件保护6.7数据一致性控制(了解)1/10/2023116内容概述6.1文件和文件系统1/9/202336.1文件和文件系统6.1.1文件、记录和数据项6.1.2文件类型和文件系统模型6.1.3文件操作1/10/20231176.1文件和文件系统6.1.1文件、记录和数据项1/9/6.1.1文件、记录和数据项

1.数据项(1)基本数据项用于描述一个对象的属性的字符集,是数据组织中可以命名的最小逻辑数据单位,即原子数据,又称为数据元素或字段如描述一个学生:学号、姓名、年龄、班级(2)组合数据项由若干个基本数据项组成,简称组项如工资包括基本工资、工龄工资、奖金等基本数据项除数据名外,还应有数据类型1/10/20231186.1.1文件、记录和数据项1.数据项1/9/202352.记录记录是一组相关数据项的集合,用于描述一个对象在某方面的属性一个记录应包含哪些数据项,取决于需要描述对象的哪个方面一个对象,由于他所处的环境不同可把他作为不同的对象一个学生,当把他作为班上的一名学生时,对他的描述应使用学号、姓名、年龄及所在系班,也可能还包括他所学过的课程的名称、成绩等数据项若把学生作为一个医疗对象时,对他描述的数据项则应使用诸如病历号、姓名、性别、出生年月、身高、体重、血压及病史等项能惟一标识一个记录的数据项称为关键字(key)1/10/20231192.记录1/9/202363.文件文件是指由创建者所定义的、具有文件名的一组相关元素的集合可分为有结构文件和无结构文件有结构文件由若干个相关记录组成,如上例中学生文件无结构文件则被看成是一个字符流,如C语言源程序文件在文件系统中是一个最大的数据单位,它描述了一个对象集例如,可以将一个班的学生记录作为一个文件一个文件必须要有一个文件名,它通常是由一串ASCII码或(和)汉字构成1/10/20231203.文件1/9/202376.1文件和文件系统6.1.1文件、记录和数据项6.1.2文件类型和文件系统模型6.1.3文件操作1/10/20231216.1文件和文件系统6.1.1文件、记录和数据项1/9/6.1.2文件类型和文件系统模型1.文件类型(1)按用途分类系统文件

有关操作系统及其它系统程序的信息所组成的文件。这类文件对用户不直接开放,只能通过系统调用为用户服务。用户文件 由用户委托操作系统保存的文件,如源程序文件,目标程序文件,以及由原始数据、计算结果等组成的文件。库文件 由标准子程序及常用的应用程序组成的文件。这类文件允许用户调用,但不允许用户修改。1/10/20231226.1.2文件类型和文件系统模型1.文件类型1/9/206.1.2文件类型和文件系统模型1.文件类型(1)…(2)按文件中数据的形式分类源文件目标文件可执行文件(3)按存取控制属性分类只执行文件只读文件

允许文件主及核准的用户读,但不允许写的文件。读写文件 允许文件主及核准的用户读、写,但禁止未核准的用户读、写的文件。1/10/20231236.1.2文件类型和文件系统模型1.文件类型1/9/202.文件系统模型图6-2文件系统模型对象及其属性(对象:文件、目录、磁盘存储空间)对对象操纵和管理的软件集合文件系统接口用户(程序)1/10/20231242.文件系统模型图6-2文件系统模型对象及其属性(对象(1)对象及其属性文件管理系统管理的对象有:①文件。它作为文件管理的直接对象。②目录。为了方便用户对文件的存取和检索,在文件系统中必须配置目录。对目录的组织和管理是方便用户和提高对文件存取速度的关键。③磁盘(磁带)存储空间。 文件和目录必定占用存储空间,对这部分空间的有效管理,不仅能提高外存的利用率,而且能提高对文件的存取速度。1/10/2023125(1)对象及其属性1/9/202312 (1)…(2)对对象操纵和管理的软件集合 这是文件管理系统的核心部分。文件系统的功能大多是在这一层实现的,完成:对文件存储空间的管理对文件目录的管理用于将文件的逻辑地址转换为物理地址的机制对文件读和写的管理对文件的共享与保护等功能1/10/2023126 (1)…1/9/202313(3)文件系统的接口为方便用户使用文件系统,文件系统通常向用户提供两种类型的接口:

①命令接口。这是指作为用户与文件系统交互的接口。用户可通过键盘终端键入命令,取得文件系统的服务。

②程序接口。这是指作为用户程序与文件系统的接口。用户程序可通过系统调用来取得文件系统的服务。1/10/2023127(3)文件系统的接口1/9/2023146.1文件和文件系统6.1.1文件、记录和数据项6.1.2文件类型和文件系统模型6.1.3文件操作1/10/20231286.1文件和文件系统6.1.1文件、记录和数据项1/9/6.1.3文件操作最基本的文件操作(1)创建文件。分配必要的外存空间,在文件系统的目录中建立一个目录项。(2)删除文件。从目录中删除该目录项,回收存储空间。(3)读文件。查找到指定的目录项,从外存读文件到内存。(4)写文件。查找到指定的目录项,进行写操作。(5)截断文件。文件内容陈旧要更新,一:删除,重新建立。二:文件长度设成0。(6)设置文件的读/写位置。用于设置指针位置。1/10/20231296.1.3文件操作最基本的文件操作1/9/2023162.文件的“打开”和“关闭”操作所谓“打开”OPEN,是指系统将指名文件的属性从外存拷贝到内存打开文件表的一个表目中,并将该表目的编号(或称为索引)返回给用户当用户再要求对该文件进行相应的操作时,便可利用系统所返回的索引号向系统提出操作请求。系统这时便可直接利用该索引号到打开文件表中去查找,从而避免了对该文件的再次检索“关闭”(CLOSE)系统调用来关闭此文件,OS将会把该文件从打开文件表中的表目上删除掉1/10/20231302.文件的“打开”和“关闭”操作1/9/2023173.其它文件操作(1)文件属性操作改变文件名改变拥有者修改权限查询状态(2)有关目录操作创建目录删除目录改变当前目录(3)实现文件共享的系统调用(4)用于对文件系统进行操作的系统调用1/10/20231313.其它文件操作1/9/202318内容概述6.1文件和文件系统6.2文件的逻辑结构6.3外存分配方式6.4目录管理6.5文件存储空间的管理6.6文件共享与文件保护6.7数据一致性控制(了解)1/10/2023132内容概述6.1文件和文件系统1/9/2023196.2文件的逻辑结构6.2.1文件逻辑结构的类型6.2.2顺序文件6.2.3索引文件6.2.4索引顺序文件6.2.5直接文件和哈希文件1/10/20231336.2文件的逻辑结构6.2.1文件逻辑结构的类型1/9/对于一个文件存在着以下两种形式的结构(1)文件的逻辑结构(FileLogicalStructure)从用户观点看到的文件组织形式,独立于文件的物理特性又称为文件组织(FileOrganization)(2)文件的物理结构又称为文件的存储结构,指文件在外存上的存储组织形式对逻辑结构的基本要求提高检索速度便于修改降低文件的存储费用1/10/2023134对于一个文件存在着以下两种形式的结构1/9/2023216.2.1文件逻辑结构的类型1.有结构文件(又称记录式文件)按记录长度分(1)定长记录(2)变长记录根据用户和系统管理需要分(1)顺序文件(2)索引文件(3)索引顺序文件2.无结构文件流式文件其长度以字节为单位采用读写指针来指出下一个要访问的字符如源程序、可执行文件、库函数等1/10/20231356.2.1文件逻辑结构的类型1.有结构文件(又称记录式文图记录式文件(a)定长记录文件;(b)变长记录文件1/10/2023136图记录式文件1/9/2023233、两种文件的比较流式文件就像给一张白纸给用户,用户可将他的信息任意地写到纸上,没有任何格式上的限制。记录式文件就像给一张表格给用户,用户要按表规定的格式填信息。显然,有结构式文件对用户的限制很大,使用起来就不方便,在UNIX系统中,所有的文件都被看作是流式文件,即使是有结构文件,也被视为流式文件。1/10/20231373、两种文件的比较1/9/2023246.2文件的逻辑结构6.2.1文件逻辑结构的类型6.2.2顺序文件6.2.3索引文件6.2.4索引顺序文件6.2.5直接文件和哈希文件1/10/20231386.2文件的逻辑结构6.2.1文件逻辑结构的类型1/9/6.2.2顺序文件1.逻辑记录的排序(1)串结构

各记录之间的顺序与关键字无关通常由时间来决定存在问题(2)顺序结构文件中的所有记录按关键字(词)排列记录号学号姓名性别出生时间1001赵男1965.8.12003钱女1971.6.173004孙男1980.12.114005李男1983.4.155006周女1976.2.106007吴男1977.11.121/10/20231396.2.2顺序文件1.逻辑记录的排序记录号学号姓名性别出生图6-3定长和变长记录文件2.对顺序文件(SequentialFile)的读/写操作1/10/2023140图6-3定长和变长记录文件2.对顺序文件(Sequent3.顺序文件的优缺点优点顺序文件的最佳应用场合,是在对诸记录进行批量存取时,即每次要读或写一大批记录只有顺序文件才能存储在磁带上,并能有效地工作缺点如果用户(程序)要求查找或修改单个记录,顺序文件所表现出来的性能就可能很差(顺序查找的ASL很大)(串结构)如果想增加或删除一个记录,都比较困难(需移动大量数据,顺序结构(排序))1/10/20231413.顺序文件的优缺点1/9/2023286.2文件的逻辑结构6.2.1文件逻辑结构的类型6.2.2顺序文件6.2.3索引文件6.2.4索引顺序文件6.2.5直接文件和哈希文件1/10/20231426.2文件的逻辑结构6.2.1文件逻辑结构的类型1/9/6.2.3索引文件对定长记录文件,如果要查找第i个记录,可直接根据下式计算来获得第i个记录相对于第一个记录首址的地址Ai=i×L对于可变长度记录的文件,要查找其第i个记录时,须首先计算出该记录的首地址,Li为第i个记录长度1/10/20231436.2.3索引文件对定长记录文件,如果要查找第i个记录,图6-4索引文件的组织1/10/2023144图6-4索引文件的组织1/9/2023316.2文件的逻辑结构6.2.1文件逻辑结构的类型6.2.2顺序文件6.2.3索引文件6.2.4索引顺序文件6.2.5直接文件和哈希文件1/10/20231456.2文件的逻辑结构6.2.1文件逻辑结构的类型1/9/索引顺序文件(IndexSequentialFile)是最常见的一种逻辑文件组织形式,是顺序文件与索引文件的结合克服了变长记录文件不便于直接存取的缺点,代价也不太大将顺序文件中的所有记录分为若干个组,为每组中的第一个记录建立索引项,其中含有该记录的键值及指向该记录的指针6.2.4索引顺序文件1/10/2023146索引顺序文件(IndexSequentialFile)是图6-5索引顺序文件1/10/2023147图6-5索引顺序文件1/9/2023346.2文件的逻辑结构6.2.1文件逻辑结构的类型6.2.2顺序文件6.2.3索引文件6.2.4索引顺序文件6.2.5直接文件和哈希文件1/10/20231486.2文件的逻辑结构6.2.1文件逻辑结构的类型1/9/6.2.5直接文件和哈希文件键值转换(Keytoaddresstransformation)由记录键值到记录物理地址的转换直接文件根据给定的记录键值,直接获得指定记录的物理地址哈希(Hash)文件利用哈希函数将记录键值转换为相应记录的地址1/10/20231496.2.5直接文件和哈希文件键值转换(Keytoadd1.直接文件对于直接文件,则可根据给定的记录键值,直接获得指定记录的物理地址。换言之,记录键值本身就决定了记录的物理地址。这种由记录键值到记录物理地址的转换被称为键值转换(Keytoaddresstransformation)。组织直接文件的关键,在于用什么方法进行从记录值到物理地址的转换。1/10/20231501.直接文件对于直接文件,则可根据给定的记录键值,2.哈希(Hash)文件图6-6Hash文件的逻辑结构1/10/20231512.哈希(Hash)文件图6-6Hash文件的逻辑结构1内容概述6.1文件和文件系统6.2文件的逻辑结构6.3外存分配方式

6.4目录管理6.5文件存储空间的管理6.6文件共享与文件保护6.7数据一致性控制(了解)1/10/2023152内容概述6.1文件和文件系统1/9/202339如何才能有效地利用外存空间?如何提高对文件的访问速度?1/10/2023153如何才能有效地利用外存空间?1/9/202340文件的物理结构文件的物理结构是指逻辑文件在存储设备(外存)上的存储组织形式,它与存储介质的存储特性有关,还与所采用的外存分配方式有关物理块是分配和传输信息的基本单位,物理块与外存设备有关文件在逻辑上都可看作是连续的,但在物理设备上存放时却有不同的方式,如连续分配、链接分配、索引分配等1/10/2023154文件的物理结构文件的物理结构是指逻辑文件在存储设备(外存)上6.3外存分配方式6.3.1连续分配6.3.2链接分配6.3.3索引分配1/10/20231556.3外存分配方式6.3.1连续分配1/9/2023426.3.1连续分配连续分配(ContinuousAllocation)要求为每一个文件分配一组相邻接的盘块。一组盘块定义了磁盘上的一段线性地址在采用连续分配方式时,可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中,这样所形成的文件结构称为顺序文件结构,此时的物理文件称为顺序文件1/10/20231566.3.1连续分配连续分配(ContinuousAllo6.3.1连续分配图6-7磁盘空间的连续分配图中假设记录和盘块大小相同1/10/20231576.3.1连续分配图6-7磁盘空间的连续分配图中假设1/10/20231581/9/2023456.3外存分配方式6.3.1连续分配6.3.2链接分配6.3.3索引分配1/10/20231596.3外存分配方式6.3.1连续分配1/9/2023466.3.2链接分配链接分配(ChainedAllocation)可通过在每个盘块上的链接指针,将同属于一个文件的多个离散的盘块链接成一个链表,把这样形成的物理文件称为链接文件消除了外部碎片,提高外存利用率文件动态增长时,可动态地为它分配盘块文件的增删改方便(这种文件结构不要求连续存放)文件创建时用户不必指出文件的大小缺点只适用于顺序存取,若查找文件中的某一块必须从头开始,随机存取效率太低,如果访问文件的最后的内容,实际上是要访问整个文件可靠性差,若某一块出错,则链断开,文件不完整增加一个链接指针1/10/20231606.3.2链接分配链接分配(ChainedAllocat链接方式又分为两种形式: 1.隐式链接 2.显示链接1/10/2023161链接方式又分为两种形式:1/9/202348图6-8磁盘空间的链接式分配1.隐式链接1/10/2023162图6-8磁盘空间的链接式分配1.隐式链接1/9/20232.显式链接(解决查找时多次访 问磁盘的问题)图6-9显式链接结构1/10/20231632.显式链接(解决查找时多次访 问磁盘的问题)图6-9图6-10MS-DOS的文件物理结构1/10/2023164图6-10MS-DOS的文件物理结构1/9/202351链接分配——显式链接文件分配表(FileAllocationTable,FAT)用于记录外存分配状况,每个盘块占一项,放在内存中(提高查找速度)表的序号为物理盘块号,从0至N-1分配给一个文件的所有物理块都在该表中标出,文件的第一个盘块号记入文件的FCB中1/10/2023165链接分配——显式链接文件分配表(FileAllocatio6.3外存分配方式6.3.1连续分配6.3.2链接分配6.3.3索引分配1/10/20231666.3外存分配方式6.3.1连续分配1/9/2023536.3.3索引分配1.单级索引分配

链接分配方式虽然解决了连续分配方式所存在的问题,但又出现了另外两个问题,即:(1)不能支持高效的直接存取。要对一个较大的文件进行直接存取,须首先在FAT中顺序地查找许多盘块号。(2)FAT需占用较大的内存空间。需要把整个FAT都调入内存。索引分配为每个文件分配一个索引块,把分配给该文件的所有盘块号都记录在该索引块中在建立一个文件时,便为之建立的目录项中填上指向该索引块的指针1/10/20231676.3.3索引分配1.单级索引分配索引分配1/9/20图6-11索引分配方式1/10/2023168图6-11索引分配方式1/9/202355若每个盘块大小为1KB,每个盘块号占4B,则索引块中可存放256个盘块号,用一个索引块只支持256K大小文件可能要花费较多的外存空间。当文件小时,索引块利用率低。文件太大时,需要多个索引块,通过指针链接起来,效率低。1/10/2023169若每个盘块大小为1KB,每个盘块号占4B,则索引块中可存放22.多级索引分配图6-12两级索引分配1/10/20231702.多级索引分配图6-12两级索引分配1/9/202357图6-13混合索引方式直接地址物理盘块索引块3.混合索引分配方式1/10/2023171图6-13混合索引方式直接地址物理盘块索引块3.混合索引(1)直接地址为了提高对文件的检索速度,在索引结点中可设置10个直接地址项,即用iaddr(0)~iaddr(9)来存放直接地址(盘块4KB,共40KB)(2)一次间接地址对于大、中型文件,可再利用索引结点中的地址项iaddr(10)来提供一次间接地址。这种方式的实质就是一级索引分配方式(盘块4KB,共4MB)(3)多次间接地址当文件长度大于4MB+40KB时(一次间址与10个直接地址项),系统还须采用二次间址分配方式。这时,用地址项iaddr(11)提供二次间接地址。该方式的实质是两级索引分配方式(共4GB),还可以提供三次间址iaddr(12)(共4TB)1/10/2023172(1)直接地址1/9/202359内容概述6.1文件和文件系统6.2文件的逻辑结构6.3外存分配方式6.4目录管理

6.5文件存储空间的管理6.6文件共享与文件保护6.7数据一致性控制(了解)1/10/2023173内容概述6.1文件和文件系统1/9/202360目录管理要求(1)实现“按名存取”文件系统最基本的功能为实现文件的按名存取,每个文件首先应该具有一个文件名与之对应。(2)提高对目录的检索速度加快目录检索速度,从而提高文件存取速度,追求的主要目标。(3)文件共享一份文件副本供不同用户使用(4)允许文件重名允许不同用户对不同文件取相同的名字1/10/2023174目录管理要求(1)实现“按名存取”1/9/2023616.4目录管理6.4.1文件控制块和索引结点6.4.2目录结构6.4.3目录查询技术 目录管理的任务是为每个文件建立目录项,并对众多的目录加以组织,以实现方便的按名存取,实现文件的共享,提供快速的目录查询手段,提高文件的检索速度。1/10/20231756.4目录管理6.4.1文件控制块和索引结点 目录管理6.4.1文件控制块和索引结点1.文件控制块(FCB)是用于描述和控制文件的数据结构文件管理程序可借助FCB中的信息对文件施以各种操作文件控制块的有序集合称为文件目录,即一个文件控制块就是一个文件目录项通常,一个文件目录本身也被看作是一个文件,称为目录文件1/10/20