06文件管理课件

第第6章章 文件管理文件管理计算机操作系统计算机操作系统四川师范大学：高四川师范大学：高 悦悦 翔翔2023/5/28文件管理文件管理第六章第六章 文件管理文件管理v所有的计算机应用程序都要：存储信息，检索信息所有的计算机应用程序都要：存储信息，检索信息v三个基本要求：三个基本要求：能够存储大量的信息能够存储大量的信息长期保存信息长期保存信息可以共享信息可以共享信息v解决方法：解决方法：把信息以一种单元，即把信息以一种单元，即文件文件的形式存储在磁盘或其他外部介质上的形式存储在磁盘或其他外部介质上v文件是通过操作系统来管理的，包括：文件是通过操作系统来管理的，包括：文件的结构，命名，存取，使用，保护和实现方法文件的结构，命名，存取，使用，保护和实现方法06文件管理文件管理文件管理文件管理第六章第六章 文件管理文件管理v文件管理的目的文件管理的目的方便的文件访问和控制方便的文件访问和控制：以符号名称作为文件标识，便于用户使用：以符号名称作为文件标识，便于用户使用并发文件访问和控制并发文件访问和控制：多道程系统中支持对文件的并发访问和控制：多道程系统中支持对文件的并发访问和控制统一的用户接口统一的用户接口：在不同设备上提供同样的接口，方便用户操作和：在不同设备上提供同样的接口，方便用户操作和编程编程多种文件访问权限多种文件访问权限：在多用户系统中的不同用户对同一文件会有不：在多用户系统中的不同用户对同一文件会有不同的访问权限同的访问权限优化性能优化性能：存储效率、检索性能、读写性能：存储效率、检索性能、读写性能差错恢复差错恢复：能够验证文件的正确性，并具有一定的差错恢复能力：能够验证文件的正确性，并具有一定的差错恢复能力06文件管理文件管理文件管理文件管理第六章第六章 文件管理文件管理v文件管理的功能文件管理的功能1)统一管理文件的存储空间，实施存储空间的分配与回收统一管理文件的存储空间，实施存储空间的分配与回收2)实现文件的按名存取：实现文件的按名存取：名字空间名字空间存储空间存储空间3)实现文件信息的共享，并提供文件的保护和保密措施实现文件信息的共享，并提供文件的保护和保密措施4)向用户提供一个方便使用的接口（提供对文件系统操作命令，以向用户提供一个方便使用的接口（提供对文件系统操作命令，以及提供对文件的操作命令：信息存取、加工等）及提供对文件的操作命令：信息存取、加工等）5)文件系统的执行效率：文件系统在操作系统接口中占的比例最大文件系统的执行效率：文件系统在操作系统接口中占的比例最大6)提供与提供与I/O的统一接口的统一接口06文件管理文件管理文件管理文件管理6.1 文件和文件系统文件和文件系统v文件系统的管理功能，是通过把它所管理的程序和数据组织成一系列文件系统的管理功能，是通过把它所管理的程序和数据组织成一系列文件的方法来实现的。文件的方法来实现的。v文件是指具有文件名的若干元素的集合。元素通常是记录，记录又是文件是指具有文件名的若干元素的集合。元素通常是记录，记录又是一组有意义的数据项的集合一组有意义的数据项的集合v基于文件系统的概念，可以把数据组成分为数据项、记录和文件三级。基于文件系统的概念，可以把数据组成分为数据项、记录和文件三级。06文件管理文件管理文件管理文件管理6.1.1 文件、记录和数据项文件、记录和数据项v数据项数据项基本数据项：描述一个对象的某种属性的字符集，是数据组织中可基本数据项：描述一个对象的某种属性的字符集，是数据组织中可以命名的最小逻辑数据单位，以命名的最小逻辑数据单位，即原子数据，又称为数据元素或字段。即原子数据，又称为数据元素或字段。它的命名往往与其属性一致。例如，用于描述一个学生的基本数据它的命名往往与其属性一致。例如，用于描述一个学生的基本数据项有：项有：学号、学号、姓名、姓名、年龄、年龄、所在班级等。所在班级等。组合数据项。它是由若干个基本数据项组成的，简称组项。例如，组合数据项。它是由若干个基本数据项组成的，简称组项。例如，经理便是个组项，它由正经理和副经理两个基本项组成。又如，工经理便是个组项，它由正经理和副经理两个基本项组成。又如，工资也是个组项，它可由基本工资、工龄工资和奖励工资等基本项所资也是个组项，它可由基本工资、工龄工资和奖励工资等基本项所组成。组成。06文件管理文件管理文件管理文件管理6.1.1 文件、记录和数据项文件、记录和数据项v数据项数据项基本数据项除了数据名外，还应有数据类型。基本数据项除了数据名外，还应有数据类型。基本项仅是描述某个对象的属性，根据属性的不同，需要用不同的基本项仅是描述某个对象的属性，根据属性的不同，需要用不同的数据类型来描述。例如，在描述学生的学号时，应使用整数；数据类型来描述。例如，在描述学生的学号时，应使用整数；描述描述学生的姓名则应使用字符串学生的姓名则应使用字符串(含汉字含汉字)；描述性别时，可用逻辑变量；描述性别时，可用逻辑变量或汉字。或汉字。由数据项的名字和类型两者共同定义了一个数据项的由数据项的名字和类型两者共同定义了一个数据项的“型型”。而表而表征一个实体在数据项上的数据则称为征一个实体在数据项上的数据则称为“值值”。例如，学号。例如，学号/30211、姓名姓名/王有年、性别王有年、性别/男等。男等。06文件管理文件管理文件管理文件管理6.1.1 文件、记录和数据项文件、记录和数据项v记录记录记录是一组相关数据项的集合，用于描述一个对象在某方面的属性。记录是一组相关数据项的集合，用于描述一个对象在某方面的属性。一个记录应包含哪些数据项，取决于需要描述对象的哪个方面。而一一个记录应包含哪些数据项，取决于需要描述对象的哪个方面。而一个对象，由于他所处的环境不同可把他作为不同的对象。个对象，由于他所处的环境不同可把他作为不同的对象。例如，一个学生，当把他作为班上的一名学生时与把学生作为一例如，一个学生，当把他作为班上的一名学生时与把学生作为一个医疗对象时不同的处理方式个医疗对象时不同的处理方式在诸多记录中，为了唯一地标识一个记录，必须在一个记录的各个数在诸多记录中，为了唯一地标识一个记录，必须在一个记录的各个数据项中，确定出一个或几个数据项。把它们的集合称为据项中，确定出一个或几个数据项。把它们的集合称为关键字关键字。06文件管理文件管理文件管理文件管理6.1.1 文件、记录和数据项文件、记录和数据项v文件文件文件是指由创建者所定义的、文件是指由创建者所定义的、具有文件名的一组相关元素的集合，可具有文件名的一组相关元素的集合，可分为有结构文件和无结构文件两种。分为有结构文件和无结构文件两种。有结构的文件中，文件由若干个相关记录组成；有结构的文件中，文件由若干个相关记录组成；无结构文件则被看成是一个字符流。无结构文件则被看成是一个字符流。文件在文件系统中是一个最大的数据单位，它描述了一个对象集。一文件在文件系统中是一个最大的数据单位，它描述了一个对象集。一个文件必须要有一个文件名。个文件必须要有一个文件名。06文件管理文件管理文件管理文件管理6.1.1 文件、记录和数据项文件、记录和数据项v文件文件文件应具有自己的属性，包括：文件应具有自己的属性，包括：文件类型。文件类型。文件长度。文件长度。文件的物理位置。文件的物理位置。文件的建立时间。文件的建立时间。文件文件记录记录1记录记录2记录记录n数据项数据项 1数据项数据项 2数据项数据项n06文件管理文件管理文件管理文件管理6.1.2 文件类型和文件系统模型文件类型和文件系统模型v文件的分类文件的分类按文件性质和用途分类按文件性质和用途分类系统文件：系统文件：OS及有关系统程序的信息所组成的文件及有关系统程序的信息所组成的文件用户文件：如源程序文件等用户文件：如源程序文件等库文件：标准子程序及常用应用程库文件：标准子程序及常用应用程 序组成的文件，允许用户使用序组成的文件，允许用户使用但不能修改但不能修改v按信息保存期限分类按信息保存期限分类临时文件；永久文件；档案文件临时文件；永久文件；档案文件06文件管理文件管理文件管理文件管理6.1.2 文件类型和文件系统模型文件类型和文件系统模型v文件的分类文件的分类按文件的保护方式分类按文件的保护方式分类只读文件；读写文件；可执行文件只读文件；读写文件；可执行文件按文件的逻辑结构分类按文件的逻辑结构分类流式文件（无结构文件）；记录式文件（有结构文件）流式文件（无结构文件）；记录式文件（有结构文件）按文件的物理结构分类按文件的物理结构分类顺序（连续）文件；链接文件；索引文件顺序（连续）文件；链接文件；索引文件06文件管理文件管理文件管理文件管理6.1.2 文件类型和文件系统模型文件类型和文件系统模型v文件系统模型文件系统模型文件系统是操作系统中以文件方式管理计算机软件资源的软件和被文件系统是操作系统中以文件方式管理计算机软件资源的软件和被管理的文件和数据结构（如目录和索引表等）的集合。管理的文件和数据结构（如目录和索引表等）的集合。文件系统接口文件系统接口对对象操对对象操纵纵和管理的和管理的软软件集合件集合逻辑文件系统逻辑文件系统基本基本I/O管理程序（文件组织模块）管理程序（文件组织模块）基本文件系统（物理基本文件系统（物理I/O层）层）I/O控制层（设备驱动程序）控制层（设备驱动程序）对象及其属性对象及其属性06文件管理文件管理文件管理文件管理6.1.2 文件类型和文件系统模型文件类型和文件系统模型v文件系统模型文件系统模型文件管理系统管理的对象有：文件管理系统管理的对象有：文件文件：作为文件管理的直接对象作为文件管理的直接对象目录目录：方便用户对文件的存取和检索方便用户对文件的存取和检索磁盘磁盘(磁带磁带)存储空间存储空间：文件和目录必定占用存储空间文件和目录必定占用存储空间文件系统的接口文件系统的接口命令接口命令接口：用户与文件系统交互的接口。用户可通过键盘终端：用户与文件系统交互的接口。用户可通过键盘终端键入命令，取得文件系统的服务。键入命令，取得文件系统的服务。程序接口程序接口：用户程序与文件系统的接口。用户程序可通过系统：用户程序与文件系统的接口。用户程序可通过系统调用来取得文件系统的服务。调用来取得文件系统的服务。06文件管理文件管理文件管理文件管理6.1.2 文件类型和文件系统模型文件类型和文件系统模型v文件系统模型文件系统模型对对象操纵和管理的软件集合对对象操纵和管理的软件集合：这是文件管理系统的核心部分。包括：这是文件管理系统的核心部分。包括：对文件存储空间的管理对文件存储空间的管理地址映射：对文件目录的管理、用于将文件的逻辑地址转换地址映射：对文件目录的管理、用于将文件的逻辑地址转换为物理地址的机制为物理地址的机制对文件读和写的管理对文件读和写的管理对文件的共享与保护对文件的共享与保护06文件管理文件管理文件管理文件管理6.1.3 文件操作文件操作v最基本的文件操作最基本的文件操作创建文件创建文件删除文件删除文件 读文件读文件 写文件写文件 截断文件截断文件 设置文件的读设置文件的读/写位置。写位置。06文件管理文件管理文件管理文件管理6.1.3 文件操作文件操作v文件的文件的“打开打开”和和“关闭关闭”操作操作“打开打开”，是指系统将指名文件的属性，是指系统将指名文件的属性(包括该文件在外存上的物理包括该文件在外存上的物理位置位置)从外存拷贝到内存打开文件表的一个表目中，并将该表目的编从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号号(或称为索引或称为索引)返回给用户。返回给用户。当用户再要求对该文件进行相应的操作时，便可利用系统所返回的当用户再要求对该文件进行相应的操作时，便可利用系统所返回的索引号向系统提出操作请求。系统这时便可直接利用该索引号到打索引号向系统提出操作请求。系统这时便可直接利用该索引号到打开文件表中去查找，从而避免了对该文件的再次检索。开文件表中去查找，从而避免了对该文件的再次检索。如果用户已不再需要对该文件实施相应的操作时，可利用如果用户已不再需要对该文件实施相应的操作时，可利用“关闭关闭”系统调用来关闭此文件，系统调用来关闭此文件，OS将会把该文件从打开文件表中的表目上将会把该文件从打开文件表中的表目上删除掉。删除掉。06文件管理文件管理文件管理文件管理6.1.3 文件操作文件操作v其它文件操作其它文件操作为了方便用户使用文件，通常，为了方便用户使用文件，通常，OS都提供了数条有关文件操作的系都提供了数条有关文件操作的系统调用，可将这些调用分成若干类：统调用，可将这些调用分成若干类：最常用的一类是有关对文件属性进行操作的，即允许用户直接最常用的一类是有关对文件属性进行操作的，即允许用户直接设置和获得文件的属性设置和获得文件的属性另一类是有关目录的，如创建一个目录，删除一个目录，改变另一类是有关目录的，如创建一个目录，删除一个目录，改变当前目录和工作目录等；此外，还有用于实现文件共享的系统当前目录和工作目录等；此外，还有用于实现文件共享的系统调用和用于对文件系统进行操作的系统调用等。调用和用于对文件系统进行操作的系统调用等。06文件管理文件管理文件管理文件管理6.2 文件的逻辑结构文件的逻辑结构v文件组织：文件中记录的逻辑结构，由用户访问记录的方文件组织：文件中记录的逻辑结构，由用户访问记录的方式确定。式确定。文件的逻辑结构：从用户观点出发，是用户可以直接处理的数据及文件的逻辑结构：从用户观点出发，是用户可以直接处理的数据及其结构，独立于文件的物理特性，又称为文件组织其结构，独立于文件的物理特性，又称为文件组织文件的物理结构：又称为文件的存储结构，文件在外存上的存储组文件的物理结构：又称为文件的存储结构，文件在外存上的存储组织形式。织形式。存储性能有关，存储性能有关，与外存分配方式与外存分配方式有关有关06文件管理文件管理文件管理文件管理6.2 文件的逻辑结构文件的逻辑结构v文件逻辑结构所提出的要求文件逻辑结构所提出的要求:首先是指提高检索速度首先是指提高检索速度其次是便于修改其次是便于修改第三是降低文件的存储费用第三是降低文件的存储费用5种基本组织：种基本组织：堆堆顺序文件顺序文件索引顺序文件索引顺序文件索引文件索引文件直接或散列文件直接或散列文件06文件管理文件管理文件管理文件管理6.2.1 文件逻辑结构的类型文件逻辑结构的类型v有结构文件有结构文件:定长记录：文件中所有记录的长度都是相同的。定长记录：文件中所有记录的长度都是相同的。变长记录：文件中各记录的长度不相同。变长记录：文件中各记录的长度不相同。v采用多种方式来组织这些记录：采用多种方式来组织这些记录：顺序文件：由一系列记录按某种顺序排列所形成的文件。顺序文件：由一系列记录按某种顺序排列所形成的文件。索引文件：记录为可变长度。索引文件：记录为可变长度。索引顺序文件：上述两种文件构成方式的结合。它为文件建立一张索引顺序文件：上述两种文件构成方式的结合。它为文件建立一张索引表，为每一组记录中的第一个记录设置一个表项。索引表，为每一组记录中的第一个记录设置一个表项。06文件管理文件管理文件管理文件管理6.2.1 文件逻辑结构的类型文件逻辑结构的类型v无结构文件无结构文件：大量的源程序、大量的源程序、可执行文件、可执行文件、库函数等，库函数等，所采用的就是无结构的所采用的就是无结构的文件形式，即流式文件。文件形式，即流式文件。其长度以字节为单位。对流式文件的访问，则是采用读写指针来指其长度以字节为单位。对流式文件的访问，则是采用读写指针来指出下一个要访问的字符。可以把流式文件看作是记录式文件的一个出下一个要访问的字符。可以把流式文件看作是记录式文件的一个特例。特例。在在UNIX系统中，所有的文件都被看作是流式文件；即使是有结构文系统中，所有的文件都被看作是流式文件；即使是有结构文件，也被视为流式文件；系统不对文件进行格式处理。件，也被视为流式文件；系统不对文件进行格式处理。06文件管理文件管理文件管理文件管理6.2.2 顺序文件顺序文件v逻辑记录的排序逻辑记录的排序：第一种是串结构，第一种是串结构，各记录之间的顺序与关键字无关。各记录之间的顺序与关键字无关。通常的办法通常的办法是由时间来决定，即按存入时间的先后排列，是由时间来决定，即按存入时间的先后排列，最先存入的记录作最先存入的记录作为第一个记录，其次存入的为第二个记录，为第一个记录，其次存入的为第二个记录，依此类推。依此类推。第二种情况是顺序结构，指文件中的所有记录按关键字第二种情况是顺序结构，指文件中的所有记录按关键字(词词)排列。排列。可以按关键词的长短从小到大排序，也可以从大到小排序；或按其可以按关键词的长短从小到大排序，也可以从大到小排序；或按其英文字母顺序排序。英文字母顺序排序。顺序结构文件可有更高的检索效率，串结构只能顺序查找，顺序结顺序结构文件可有更高的检索效率，串结构只能顺序查找，顺序结构可采用折半查找等。构可采用折半查找等。06文件管理文件管理文件管理文件管理6.2.2 顺序文件顺序文件v对顺序文件对顺序文件(Sequential File)的的读读/写操作写操作：定长记录的顺序文件：定长记录的顺序文件：读指针读指针Rptr，指向下一个记，指向下一个记录的首地址，当读完一个记录的首地址，当读完一个记录时，便执行录时，便执行Rptr:=Rptr+L为记录长度，在写一个文件为记录长度，在写一个文件时，写指针时，写指针Wptr指向要写的指向要写的记录的首地址。每写完一个记录的首地址。每写完一个记录时，又需执行以下操作记录时，又需执行以下操作Wptr:=Wptr+L06文件管理文件管理文件管理文件管理6.2.2 顺序文件顺序文件v对顺序文件对顺序文件(Sequential File)的的读读/写操作写操作：变长记录的顺序文件：变长记录的顺序文件：读或写指针加上读或写指针加上Li。Li是刚读或刚写完的记录的是刚读或刚写完的记录的长度。长度。06文件管理文件管理文件管理文件管理6.2.2 顺序文件顺序文件v顺序文件顺序文件(Sequential File)的优缺点：的优缺点：顺序文件的最佳应用场合，是在对诸记录进行批量存取时，顺序文件的最佳应用场合，是在对诸记录进行批量存取时，即每次即每次要读或写一大批记录。要读或写一大批记录。在交互应用的场合，如果用户在交互应用的场合，如果用户(程序程序)要求查找或修改单个记录，为此要求查找或修改单个记录，为此系统便要去逐个地查找诸记录。系统便要去逐个地查找诸记录。这时，这时，顺序文件所表现出来的性能顺序文件所表现出来的性能就可能很差，就可能很差，尤其是当文件较大时，尤其是当文件较大时，情况更为严重。情况更为严重。如果想增加或删除一个记录，都比较困难。为了解决这一问题，可以如果想增加或删除一个记录，都比较困难。为了解决这一问题，可以为顺序文件配置一个运行记录文件或称为事务文件为顺序文件配置一个运行记录文件或称为事务文件(Transaction File)，把试图增加、把试图增加、删除或修改的信息记录于其中，规定每隔一定时间，删除或修改的信息记录于其中，规定每隔一定时间，将运行记录文件与原来的主文件加以合并，将运行记录文件与原来的主文件加以合并，产生一个按关键字排序产生一个按关键字排序的新文件。的新文件。06文件管理文件管理文件管理文件管理6.2.3 索引文件索引文件v索引文件索引文件(Sequential File)：对于定长记录文件，要查找第对于定长记录文件，要查找第i个记录，第个记录，第i个记录相对于第一个记录个记录相对于第一个记录首址的地址：首址的地址：Ai=iL对于可变长度记录的文件，要查找其第对于可变长度记录的文件，要查找其第i个记录时，先要顺序的查找个记录时，先要顺序的查找每个记录，获得相应记录的长度，然后，按下式计算第每个记录，获得相应记录的长度，然后，按下式计算第i个记录的首个记录的首地址：地址：06文件管理文件管理文件管理文件管理6.2.3 索引文件索引文件v索引文件索引文件(Sequential File)：变长记录：较难实现直接存取，为了解决这一问题，可为变长记录文变长记录：较难实现直接存取，为了解决这一问题，可为变长记录文件建立一张索引表，索引表本身是一个定长记录的顺序文件，可以方件建立一张索引表，索引表本身是一个定长记录的顺序文件，可以方便地实现直接存取。便地实现直接存取。06文件管理文件管理文件管理文件管理6.2.3 索引文件索引文件v索引文件索引文件(Sequential File)：首先，用折半查找法的首先，用折半查找法的MID 指针，作为索引文件的记录号，去检索索指针，作为索引文件的记录号，去检索索引表，根据索引表中的指向记录的指针值，得到主文件的记录的关键引表，根据索引表中的指向记录的指针值，得到主文件的记录的关键字，如果和用户给出的关键字匹配则检索到所需的记录。否则修改字，如果和用户给出的关键字匹配则检索到所需的记录。否则修改low和和high指针，继续检索。指针，继续检索。优点：将检索不定长文件改为检索定长的索引文件，具有较快的检索优点：将检索不定长文件改为检索定长的索引文件，具有较快的检索速度；速度；缺点：除主文件外，还须配置一张索引表，而且每个记录都要有一个缺点：除主文件外，还须配置一张索引表，而且每个记录都要有一个索引项，提高了存储费用。索引项，提高了存储费用。06文件管理文件管理文件管理文件管理6.2.4 索引顺序文件索引顺序文件v索引顺序文件：索引顺序文件：克服了变长记录文件不便于直接存取的缺点。将顺序文件中的所有记克服了变长记录文件不便于直接存取的缺点。将顺序文件中的所有记录分为若干个组，为每组中的第一个记录建立一个索引项。录分为若干个组，为每组中的第一个记录建立一个索引项。06文件管理文件管理文件管理文件管理6.2.4 索引顺序文件索引顺序文件v索引顺序文件：索引顺序文件：设在一个顺序文件中所含有的记录数为设在一个顺序文件中所含有的记录数为N，为检索到具有指定关为检索到具有指定关键字的记录，平均须查找键字的记录，平均须查找N/2个记录；如为索引顺序文件，平均个记录；如为索引顺序文件，平均只要查找只要查找 个记录数。个记录数。比较：设文件含有比较：设文件含有10 000个记录个记录顺序文件查找：顺序文件查找：5000（记录）（记录）索引顺序文件查找：索引顺序文件查找：100（记录（记录)06文件管理文件管理文件管理文件管理6.2.3 索引文件索引文件v索引顺序文件：索引顺序文件：但若文件很大，设含有但若文件很大，设含有106个记录个记录,索引顺序文件查找：索引顺序文件查找：平均平均1000个记录（太多）个记录（太多）引入多级索引，为索引文件再建立一张索引表。引入多级索引，为索引文件再建立一张索引表。例如：有例如：有106个记录，每个记录，每100个记录为一组，一级索引有个记录为一组，一级索引有104个表项。将个表项。将每每100个索引表项分为一组，故二级索引有个索引表项分为一组，故二级索引有102个表项。平均只要查找个表项。平均只要查找505050150 个记录。个记录。顺序文件：顺序文件：50万个记录万个记录(一级一级)索引顺序文件：索引顺序文件：1000个记录个记录 二级索引顺序文件：二级索引顺序文件：3/2*100=150个记录个记录06文件管理文件管理文件管理文件管理6.2.5 直接文件和哈希文件直接文件和哈希文件v直接文件直接文件：前面几种文件结构对记录进行存取时，都需利用给定的记录键值，前面几种文件结构对记录进行存取时，都需利用给定的记录键值，先对线性表或链表进行检索，以找到指定记录的物理地址。先对线性表或链表进行检索，以找到指定记录的物理地址。对于直接文件，可根据给定的记录键值，直接获得指定记录的物理对于直接文件，可根据给定的记录键值，直接获得指定记录的物理地址。地址。键值转换：键值转换：由记录键值到记录物理地址的转换。由记录键值到记录物理地址的转换。关键：用什么方关键：用什么方法进行从记录值法进行从记录值到物理地址的转到物理地址的转换换06文件管理文件管理文件管理文件管理6.2.5 直接文件和哈希文件直接文件和哈希文件v哈希哈希(Hash)文件文件：最为广泛的一种直接文件。最为广泛的一种直接文件。它利用它利用Hash函数，可将记录函数，可将记录键值转换为相应记录的地址。键值转换为相应记录的地址。由由Hash函数所求得，指向一函数所求得，指向一目录表相应表目的指针，该目录表相应表目的指针，该表目的内容指向相应记录所表目的内容指向相应记录所在的物理块。在的物理块。06文件管理文件管理文件管理文件管理6.2 文件的逻辑结构文件的逻辑结构文件逻辑结构文件逻辑结构无结构文件无结构文件有结构文件有结构文件定长记录定长记录变长记录变长记录顺序文件顺序文件索引顺序文件索引顺序文件索引文件索引文件流式文件流式文件按组织方式分按组织方式分按记录长度分按记录长度分06文件管理文件管理文件管理文件管理6.3 外存分配方式外存分配方式v为文件分配外存空间时所要考虑的问题：为文件分配外存空间时所要考虑的问题：1)怎样才能有效利用外存空间；怎样才能有效利用外存空间；2)如何提高对文件的访问速度。如何提高对文件的访问速度。常用的外存分配方法：连续、链接和索引分配。分配方案负责将文常用的外存分配方法：连续、链接和索引分配。分配方案负责将文件的逻辑块映射到存储设备的物理块上。件的逻辑块映射到存储设备的物理块上。文件的物理结构直接与外存分配方式有关。在采用连续分配方式时文件的物理结构直接与外存分配方式有关。在采用连续分配方式时的文件物理结构，是顺序式的文件结构；链接分配方式将形成链接的文件物理结构，是顺序式的文件结构；链接分配方式将形成链接式文件结构；索引分配方式形成索引式文件结构。式文件结构；索引分配方式形成索引式文件结构。一个系统仅采用一个系统仅采用一种分配方式一种分配方式06文件管理文件管理文件管理文件管理6.3.1 连续分配连续分配v连续分配：连续分配：连续分配要求为每一个文件分配一组相邻接的盘块。连续分配要求为每一个文件分配一组相邻接的盘块。在采用连续分配方式时，可把逻辑文件中的记录顺序地存储到邻接在采用连续分配方式时，可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中，这样所形成的文件结构称为顺序文件结构，此时的各物理盘块中，这样所形成的文件结构称为顺序文件结构，此时的物理文件称为顺序文件。的物理文件称为顺序文件。保证了逻辑文件中的记录顺序与存储器中文件占用盘块中的顺序的保证了逻辑文件中的记录顺序与存储器中文件占用盘块中的顺序的一致性。使系统能找到文件存放的地址，目录项的一致性。使系统能找到文件存放的地址，目录项的“文件物理地址文件物理地址”字段，记录该文件第一个记录所在的盘块号和文件长度。字段，记录该文件第一个记录所在的盘块号和文件长度。同内存的动态分区分配一样，随着文件建立时空间的分配和文件删同内存的动态分区分配一样，随着文件建立时空间的分配和文件删除时空间的回收，即外存的碎片。除时空间的回收，即外存的碎片。06文件管理文件管理文件管理文件管理6.3.1 连续分配连续分配v连续分配：连续分配：06文件管理文件管理文件管理文件管理6.3.1 连续分配连续分配v连续分配：连续分配：连续分配的主要优点如下：连续分配的主要优点如下：顺序访问容易。顺序访问容易。顺序访问速度快。顺序访问速度快。连续分配的主要缺点如下：连续分配的主要缺点如下：要求有连续的存储空间。要求有连续的存储空间。必须事先知道文件的长度。必须事先知道文件的长度。06文件管理文件管理文件管理文件管理6.3.2 链接分配链接分配v链接分配：链接分配：连续分配所存在的问题：必须为一个文件分配连续的磁盘空间。连续分配所存在的问题：必须为一个文件分配连续的磁盘空间。如果将一个逻辑文件存储到外存上时，不要求为整个文件分配一块如果将一个逻辑文件存储到外存上时，不要求为整个文件分配一块连续的空间，而是可以将文件装到多个离散的盘块，就可以消除上连续的空间，而是可以将文件装到多个离散的盘块，就可以消除上述的缺点。述的缺点。采用链接分配方式时，可通过在每个盘块上采用链接分配方式时，可通过在每个盘块上 的链接指针，将同属于的链接指针，将同属于一个文件的盘块链接成一个链表，称为链接文件。一个文件的盘块链接成一个链表，称为链接文件。06文件管理文件管理文件管理文件管理6.3.2 链接分配链接分配v链接分配：链接分配：特点：特点：采用离散方式分配，消除了外部碎片提高外存的利用率；采用离散方式分配，消除了外部碎片提高外存的利用率；根据文件的需要，可动态地为它分配必须的盘块无须事先根据文件的需要，可动态地为它分配必须的盘块无须事先 知道文件的大小。知道文件的大小。对文件的增、删、改十分方便；对文件的增、删、改十分方便；链接方式分为：隐式链接和显式链接两种形式。链接方式分为：隐式链接和显式链接两种形式。06文件管理文件管理文件管理文件管理6.3.2 链接分配链接分配v隐式链接：隐式链接：在文件目录的每个目录项中，都须含有指向链接文件第一个盘块和在文件目录的每个目录项中，都须含有指向链接文件第一个盘块和最后一个盘块的指针。如下例，在该文件相应的目录项中，指示其最后一个盘块的指针。如下例，在该文件相应的目录项中，指示其第一个盘块号：第一个盘块号：9，最后一个盘块号：，最后一个盘块号：25；同时在每个盘块号中都含有一个指向下一个物理块的指针。同时在每个盘块号中都含有一个指向下一个物理块的指针。06文件管理文件管理文件管理文件管理6.3.2 链接分配链接分配v隐式链接：隐式链接：只适合顺序访问只适合顺序访问06文件管理文件管理文件管理文件管理6.3.2 链接分配链接分配v显式链接：显式链接：把用于链接文件各物理块的指针，显式地存放在内存的一张链接表把用于链接文件各物理块的指针，显式地存放在内存的一张链接表中。该表在整个磁盘仅设置一张，表的序号是物理盘块号，每个表中。该表在整个磁盘仅设置一张，表的序号是物理盘块号，每个表项中的链接指针即是下一个盘块号。该表称为文件分配表项中的链接指针即是下一个盘块号。该表称为文件分配表FAT。某一文件的第一个盘块号，作为文件地址被填入相应文件的某一文件的第一个盘块号，作为文件地址被填入相应文件的FCB的的“物理地址物理地址”字段中。字段中。查找记录的过程在内存中进行，因此能显著提高检索速度，减少访查找记录的过程在内存中进行，因此能显著提高检索速度，减少访问磁盘次数。问磁盘次数。06文件管理文件管理文件管理文件管理6.3.2 链接分配链接分配v显式链接：显式链接：06文件管理文件管理文件管理文件管理6.3.2 链接分配链接分配v显式链接：显式链接：MSDOS物理结构物理结构06文件管理文件管理文件管理文件管理6.4.1 文件控制块和索引结点文件控制块和索引结点v假定磁盘块的大小为假定磁盘块的大小为1K，对于，对于800M的硬盘，其文件分配表的硬盘，其文件分配表FAT需要占用需要占用多少存储空间？多少存储空间？由题目条件可知，硬盘大小为由题目条件可知，硬盘大小为800M，磁盘块的大小为，磁盘块的大小为1K，所以该硬，所以该硬盘共有盘块：盘共有盘块：800M/1K=800K(个个)又又512K800K1024K，故，故800K个盘块号要用个盘块号要用20位二进制表示，即文件位二进制表示，即文件分配表的每个表目为分配表的每个表目为2.5字节。字节。FAT要占用的存储空间总数为：要占用的存储空间总数为：2.5*800K=2000K06文件管理文件管理文件管理文件管理6.3.3 索引分配索引分配v单级索引分配单级索引分配链接分配方式虽然解决了连续分配方式所存在的问题，链接分配方式虽然解决了连续分配方式所存在的问题，但又出现了但又出现了另外两个问题，另外两个问题，即：即：1)不能支持高效的直接存取。要对一个较大的文件进行直接存不能支持高效的直接存取。要对一个较大的文件进行直接存取，须首先在取，须首先在FAT中顺序地查找许多盘块号。中顺序地查找许多盘块号。2)FAT需占用较大的内存空间。需占用较大的内存空间。实际上在打开某个文件时，只需把该文件占用的盘块的编号调入内实际上在打开某个文件时，只需把该文件占用的盘块的编号调入内存即可，完全没有必要将整个存即可，完全没有必要将整个FAT调入内存。调入内存。06文件管理文件管理文件管理文件管理6.3.3 索引分配索引分配v单级索引分配单级索引分配索引分配方法，为每个文件分配一个索引块（表），再把分配给该索引分配方法，为每个文件分配一个索引块（表），再把分配给该文件的所有盘块号，都记录在该索引块中，因而该索引块就是一个文件的所有盘块号，都记录在该索引块中，因而该索引块就是一个含有许多盘块号的数组，在建文件时，便在相应的文件目录项中，含有许多盘块号的数组，在建文件时，便在相应的文件目录项中，填上指向该索引块的指针。填上指向该索引块的指针。索引分配方式支持直接访问。索引分配方式支持直接访问。索引分配方式的主要问题是：可能要花费较多的外存空间，小文件索引分配方式的主要问题是：可能要花费较多的外存空间，小文件的索引块的利用率是极低的。的索引块的利用率是极低的。06文件管理文件管理文件管理文件管理6.3.3 索引分配索引分配v单级索引分配单级索引分配06文件管理文件管理文件管理文件管理6.3.3 索引分配索引分配v多级索引分配多级索引分配如文件很大，一个索引块已满，则如文件很大，一个索引块已满，则OS便再为该文件分配新的索引块，便再为该文件分配新的索引块，各索引块按序连接。显然索引块太多时，这种方法是低效的。各索引块按序连接。显然索引块太多时，这种方法是低效的。解决办法：为这些索引块再建立一级索引，形成称二级索引。解决办法：为这些索引块再建立一级索引，形成称二级索引。06文件管理文件管理文件管理文件管理6.3.3 索引分配索引分配v多级索引分配多级索引分配06文件管理文件管理文件管理文件管理6.3.3 索引分配索引分配v多级索引分配多级索引分配假设：每个盘块的大小为假设：每个盘块的大小为1KB，每个盘块号占，每个盘块号占4个字节，则一个索引个字节，则一个索引块中可存放块中可存放256个盘块号。所允许的文件最大长度为个盘块号。所允许的文件最大长度为256K(2561K)二级索引最多盘块号总数二级索引最多盘块号总数N：=256256=64K个盘块号，有此可得出结个盘块号，有此可得出结论：采用两级索引时，所允许的文件最大长度为论：采用两级索引时，所允许的文件最大长度为64MB(64K1K)倘若盘块的大小为倘若盘块的大小为4KB，单级索引，一个索引块中可存放，单级索引，一个索引块中可存放1024个盘个盘块号，所允许的文件最大长度为块号，所允许的文件最大长度为4MB(10244K)采用两级索引时所允许的文件最大长度可达采用两级索引时所允许的文件最大长度可达4GB(102410244K)06文件管理文件管理文件管理文件管理6.3.3 索引分配索引分配v混合索引分配方式混合索引分配方式 n 指将多种分配方式相结合而指将多种分配方式相结合而 形成的一种分配方式。如系形成的一种分配方式。如系 统既采用直接地址，又采用统既采用直接地址，又采用 一级索引、二级索引、甚至一级索引、二级索引、甚至 三级索引的分配方式。三级索引的分配方式。06文件管理文件管理文件管理文件管理6.4 目录管理目录管理v目录管理目录管理对目录管理的要求如下：对目录管理的要求如下：实现实现“按名存取按名存取”。提高对目录的检索速度。提高对目录的检索速度。文件共享。文件共享。允许文件重名。允许文件重名。06文件管理文件管理文件管理文件管理6.4.1 文件控制块和索引结点文件控制块和索引结点v目录管理目录管理为了能对一个文件进行正确的存取，必须为文件设置用于描述和控为了能对一个文件进行正确的存取，必须为文件设置用于描述和控制文件的数据结构，称为制文件的数据结构，称为“文件控制块文件控制块(FCB)”。文件控制块文件控制块(FCB)存放了管理文件所需的所有信息存放了管理文件所需的所有信息(文件名，文件属文件名，文件属性性)一个文件有一个文件控制块。文件控制块的有序集合称为文件目录。一个文件有一个文件控制块。文件控制块的有序集合称为文件目录。06文件管理文件管理文件管理文件管理6.4.1 文件控制块和索引结点文件控制块和索引结点v文件控制块文件控制块基本信息类基本信息类 文件名文件名；文件物理位置文件物理位置；文件逻辑结构文件逻辑结构；文件的物理结构文件的物理结构存取控制信息类存取控制信息类文件主的存取权限、核准用户的存取权限以及一般用户的存取文件主的存取权限、核准用户的存取权限以及一般用户的存取权限。权限。使用信息类使用信息类文件的建立日期和时间、文件上一次修改的日期和时间及当前文件的建立日期和时间、文件上一次修改的日期和时间及当前使用信息。使用信息。06文件管理文件管理文件管理文件管理6.4.1 文件控制块和索引结点文件控制块和索引结点v文件控制块文件控制块MS-DOS中的文件控制块，中的文件控制块，FCB的长度为的长度为32个字节，对个字节，对360KB的软盘，的软盘，总共可包含总共可包含112个个FCB，共占，共占4KB的存储空间的存储空间06文件管理文件管理文件管理文件管理6.4.1 文件控制块和索引结点文件控制块和索引结点v索引结点索引结点引入：引入：文件目录通常存放在磁盘上，当文件很多时，文件目录可能要文件目录通常存放在磁盘上，当文件很多时，文件目录可能要占用大量的盘块占用大量的盘块过程：先将存放目录文件的第一个盘块中的目录调入内存，然过程：先将存放目录文件的第一个盘块中的目录调入内存，然后把用户所给定的文件名与目录项中的文件名逐一比较。若未后把用户所给定的文件名与目录项中的文件名逐一比较。若未找到指定文件，便将下一个盘块中的目录项调入内存。找到指定文件，便将下一个盘块中的目录项调入内存。若目录文件所占用的盘块数为若目录文件所占用的盘块数为N，按此方法查找，则查找一个目，按此方法查找，则查找一个目录项平均需要调入盘块录项平均需要调入盘块(N+1)/2次。次。06文件管理文件管理文件管理文件管理6.4.1 文件控制块和索引结点文件控制块和索引结点v索引结点索引结点引入：引入：设一个设一个FCB为为64B，盘块大小为，盘块大小为1KB，则每个盘块中只能存放，则每个盘块中只能存放16个个FCB；若一个文件目录中共有；若一个文件目录中共有640个个FCB，需占用，需占用40个盘块，个盘块，平均查找一个文件需要启动磁盘平均查找一个文件需要启动磁盘20次。次。检索目录文件时，目录项的所有内容都必须吗？检索目录文件时，目录项的所有内容都必须吗？在检索目录文件的过程中，只用到了文件名在检索目录文件的过程中，只用到了文件名解决：把解决：把FCB分成两部分分成两部分文件名和文件属性（文件名和文件属性（i结点）结点）06文件管理文件管理文件管理文件管理6.4.1 文件控制块和索引结点文件控制块和索引结点UNIX的文件目录的文件目录 一个一个FCB占占16B，1KB盘块存放盘块存放64个目录项，若一个文件目录中共个目录项，若一个文件目录中共有有640个个FCB，需占用，需占用10个盘块。平均查找一个文件需启动磁盘个盘块。平均查找一个文件需启动磁盘5次次(原原来来40个盘块，个盘块，20次）。次）。文件名文件名索引节点编号索引节点编号文件名文件名1文件名文件名2.14字节字节2字节字节06文件管理文件管理文件管理文件管理6.4.1 文件控制块和索引结点文件控制块和索引结点v磁盘索引结点磁盘索引结点(i 结点结点)文件所有者标识文件所有者标识：i-uid,i-gid文件类型：文件类型：i_type文件存取许可权：文件存取许可权：i_mode文件联结数目：文件联结数目：i_ilink文件存取时间：文件存取时间：i_time文件长度：文件长度：i_size地址索引表：地址索引表：i_addr13UNIX中磁盘索引结点放入磁盘中约中磁盘索引结点放入磁盘中约定的位置，在物理上连续存放，并定的位置，在物理上连续存放，并顺序编号。顺序编号。所有者：所有者：mjb 用户组：用户组：os类型：类型：普通文件普通文件许可权：许可权：rw 文件联结数目：文件联结数目：1最后一次读文件：最后一次读文件：2003.3.16 下午下午1:45最后一次写文件：最后一次写文件：2003.3.8上午上午10:20最后一次改变：最后一次改变：2003.3.9上午上午11:06文件长度：文件长度：9000B磁盘地址：磁盘地址：10,1,2,3,5,6,7,20,906文件管理文件管理文件管理文件管理6.4.1 文件控制块和索引结点文件控制块和索引结点v内存索引结点内存索引结点文件被打开时，要将磁盘索引结点拷贝到内存的索引结点中：文件被打开时，要将磁盘索引结点拷贝到内存的索引结点中：1)索引结点编号。索引结点编号。用于标识内存索引结点。用于标识内存索引结点。2)状态。状态。指示指示i结点是否上锁或被修改。结点是否上锁或被修改。3)访问计数。访问计数。每当有一进程要访问此每当有一进程要访问此i结点时，结点时，将该访问计数将该访问计数加加1，访问完再减访问完再减1。4)文件所属文件系统的逻辑设备号。文件所属文件系统的逻辑设备号。5)链接指针。链接指针。设置有分别指向空闲链表和散列队列的指针。设置有分别指向空闲链表和散列队列的指针。06文件管理文件管理文件管理文件管理6.4.2 目录结构目录结构v目录结构目录结构目录结构关系到文件系统的存取速度、文件的共享性和安全性。目录结构关系到文件系统的存取速度、文件的共享性和安全性。单级目录结构单级目录结构两级目录两级目录多级目录多级目录增加和删除目录增加和删除目录06文件管理文件管理文件管理文件管理6.4.2 目录结构目录结构v单级目录结构单级目录结构整个文件系统中只建立一张文件目录，包含了所有文件的文件控制整个文件系统中只建立一张文件目录，包含了所有文件的文件控制块，每个块，每个FCB指向一个普通文件。指向一个普通文件。FCB2文件名文件名2FCB1文件名文件名1物理地址物理地址文件说明文件说明文件名文件名文件文件1文件文件2如何实现如何实现“按名存取按名存取”？效率如何？效率如何？06文件管理文件管理文件管理文件管理6.4.2 目录结构目录结构v单级目录结构单级目录结构单级目录的优点是简单且能实现目录管理的基本功能单级目录的优点是简单且能实现目录管理的基本功能按名存取，按名存取，但却存在下述缺点：但却存在下述缺点：查找速度慢：查找速度慢：N个目录项，平均查个目录项，平均查N/2个目录项个目录项不允许重名不允许重名不便于实现文件共享：因为要求所有用户都用同一个文件名来不便于实现文件共享：因为要求所有用户都用同一个文件名来访问同一个文件。访问同一个文件。06文件管理文件管理文件管理文件管理6.4.2 目录结构目录结构v两级目录两级目录为了克服单级目录所存在的缺点，可以为每一个用户建立一个单独为了克服单级目录所存在的缺点，可以为每一个用户建立一个单独的用户文件目录的用户文件目录UFD（User)。在系统再建立一个主文件目录在系统再建立一个主文件目录MFD（Master File Directory）；每个）；每个用户目录文件都占有一个目录项，包括用户名和指向该用户目录文用户目录文件都占有一个目录项，包括用户名和指向该用户目录文件的指针。件的指针。06文件管理文件管理文件管理文件管理6.4.2 目录结构目录结构v两级目录两级目录06文件管理文件管理文件管理文件管理6.4.2 目录结构目录结构v两级目录两级目录两级目录结构上基本上克服了单级目录的缺点，并具有以下优点：两级目录结构上基本上克服了单级目录的缺点，并具有以下优点：提高了检索目录的速度提高了检索目录的速度主目录中有主目录中有n个子目录，每个用户目录最多为个子目录，每个用户目录最多为m个目录项，最多个目录项，最多只检索只检索n+m个目录项。采用单级目录结构，最多需检索个目录项。采用单级目录结构，最多需检索nm个目个目录项。录项。在不同的用户目录中，在不同的用户目录中，可以使用相同的文件名。可以使用相同的文件名。不同用户还可使用不同的文件名来访问系统中的同一个共享文件不同用户还可使用不同的文件名来访问系统中的同一个共享文件 06文件管理文件管理文件管理文件管理6.4.2 目录结构目录结构v多级目录结构多级目录结构目录结构目录结构对大型文件系统采用三级或以上的目录结构对大型文件系统采用三级或以上的目录结构多级目录结构是二级目录的扩充。多级目录结构又称树型目录多级目录结构是二级目录的扩充。多级目录结构又称树型目录结构，主目录被称为根目录结构，主目录被称为根目录多级目录结构中，除了最低一级的物理块中含装有文件具体内多级目录结构中，除了最低一级的物理块中含装有文件具体内容外，其它每一级目录中存放的都是下一级目录或文件的说明容外，其它每一级目录中存放的都是下一级目录或文件的说明信息。信息。根目录是唯一的，一般放在内存。根目录是唯一的，一般放在内存。06文件管理文件管理文件管理文件管理6.4.2 目录结构目录结构CB A1DB ADE FKN JAGFH AKM JCA234567891112131415161718192021ba06文件管理文件管理文件管理文件管理6.4.2 目录结构目录结构v多级目录结构多级目录结构路径名路径名从根目录到任何数据文件，从根目录到任何数据文件，都只有一条惟一的通路。都只有一条惟一的通路。在该路径在该路径上从树的根上从树的根(即主目录即主目录)开始，开始，把全部目录文件名与数据文件名，把全部目录文件名与数据文件名，依次地用依次地用“/”连接起来，连接起来，即构成该数据文件的路径名即构成该数据文件的路径名(path name)。系统中的每一个文件都有惟一的路径名。系统中的每一个文件都有惟一的路径名。06文件管理文件管理文件管理文件管理6.4.2 目录结构目录结构v多级目录结构多级目录结构当前目录当前目录(Current Directory)为每个进程设置一个为每个进程设置一个“当前目录当前目录”，又称为，又称为“工作目录工作目录”。进。进程对各文件的访问都相对于程对各文件的访问都相对于“当前目录当前目录”而进行。此时各文件而进行。此时各文件所使用的路径名，所使用的路径名，只需从当前目录开始，只需从当前目录开始，逐级经过中间的目录逐级经过中间的目录文件，最后到达要访问的数据文件。文件，最后到达要访问的数据文件。从当前目录开始直到数据文件为止所构成的路径名，称为相对从当前目录开始直到数据文件为止所构成的路径名，称为相对路径名路径名从树根开始的路径名称为绝对路径名从树根开始的路径名称为绝对路径名(absolute path name)。06文件管理文件管理文件管理文件管理6.4.2 目录结构目录结构v增加和删除目录增加和删除目录在用户要创建一个新文件时，只需查看在自己的在用户要创建一个新文件时，只需查看在自己的UFD及其子目录中，及其子目录中，有无与新建文件相同的文件名。有无与新建文件相同的文件名。如果要删除的目录是空的，将该目录项删除，使它在其上一级目录如果要删除的目录是空的，将该目录项删除，使它在其上一级目录中对应的目录项为空；如果要删除的目录不空，可采取下述两种方中对应的目录项为空；如果要删除的目录不空，可采取下述两种方法：法：1)不删除非空目录不删除非空目录2)可删除非空目录可删除非空目录06文件管理文件管理文件管理文件管理6.4.2 目录结构目录结构v增加和删除目录增加和删除目录 1)不删除非空目录。不删除非空目录。当目录当目录(文件文件)不空时，不空时，不能将其删除，而为了删除一个非空目不能将其删除，而为了删除一个非空目录，必须先删除目录中的所有文件，使之先成为空目录，录，必须先删除目录中的所有文件，使之先成为空目录，后再后再予以删除。如果目录中还包含有子目录，还必须采取递归调用予以删除。如果目录中还包含有子目录，还必