操作系统第六章文件管理一

第六章文件管理

信息是计算机系统中的重要资源。操作系统中的一个重要组成部分——文件系统，就负责信息的组织、存储和访问。

本章的主要内容就是文件的组织结构、存取方法、保护以及文件系统空间管理等问题。考研大纲（一）文件系统基础1.文件概念2.文件结构（2分）（2分）(7分)3.目录结构（2分）（2分）4.文件共享（2分）5.文件保护（二）文件系统实现

1.文件系统层次结构2.目录实现3.文件实现（三）磁盘组织与管理（7分）1.磁盘的结构2.磁盘调度算法（2分）3.磁盘的管理6.1文件系统的概念6.2文件的组织结构6.3

文件存储空间的管理6.4

文件目录的管理6.5

文件存取控制6.6

文件的使用本章的主要内容是：

学习目标：

1.掌握：文件的逻辑组织和物理组织的概念及不同的组织形式，文件存储空间的管理，文件的目录结构，文件和目录的主要操作。

2.理解：文件的分类、文件的存取控制。

3.了解：文件系统的功能、文件系统的层次模型。学习要点：大家对文件并不陌生，经常要建文件、删文件、读写文件等。那么什么是文件呢？怎样看待文件？系统内部如何对文件进行管理？文件怎样在目录中登记？有些文件可以共享，而另外一些需要保护起来，应采取什么控制？6.1文件系统的概念返回1.文件和文件系统2.文件的类型3.文件系统的功能

文件系统是OS与用户关系最紧密的一部分，对用户来说，它是OS中最直观的部分，能否方便使用OS，以及OS的可信赖程度往往取决于文件系统的功能和性能。1.文件和文件系统

大容量磁盘、磁带等的出现，为程序和数据等软件资源的透明存取提供了物质基础。这导致了对软件资源管理质的飞跃——文件系统的出现。对计算机资源管理硬件资源软件资源CPU存储器设备……系统程序系统应用程序函数库用户应用程序……透明存放协调工作

文件文件是一段程序或数据的集合。在计算机系统中，文件被解释为一组赋名的相关联字符流的集合，或是相关联记录的集合。

文件系统操作系统中与管理文件有关的软件和数据称为文件系统。文件系统负责为用户建立、撤消、读写、修改和复制文件；还负责完成对文件的按名存取和存取控制2.文件的类型为便于管理和控制文件，常将文件分成若干类型。

按文件性质和用途分类系统文件：OS及有关系统程序的信息所组成的文件。用户文件：如源程序文件等。

库文件：标准子程序及常用应用程序组成的文件，允许用户使用但不能修改。

按文件组织和处理方式分类

普通文件：包含的是用户的信息，一般为ASCII或二进制文件。

目录文件：管理文件系统的系统文件

特殊文件：在linux系统中，所有输入输出设备都被看作特殊文件。

按文件的保护方式分类

只读文件、读写文件、可执行文件

按信息流分类

输入文件：如读卡机或键盘上的文件，只能读入。

输出文件：如打印机上的文件，只能写出。

输入/输出文件：如磁盘、磁带上的文件，既可读又可写。

按文件中的数据形式分类

源文件：指从终端或输入设备输入的源程序和数据所构成的文件。

目标文件：指源程序经过相应语言的编译程序进行编译后，但尚未经过链接处理的目标代码形成的文件，属于二进制文件。

可执行文件：经过编译、连接之后所形成的可执行目标文件。分类的目的：对不同文件进行相应的管理,提高系统效率。3.文件系统的功能用户的角度：

按名存取系统的角度：

文件空间管理为合理地存放文件，必须对文件空间进行统一管理。

逻辑结构为了实现按名存取，需要有一个用户可见的文件逻辑结构，用户按照文件逻辑结构所给定的方式进行信息存取和加工。

物理结构为了便于存放和加工信息，文件在存储设备上应按一定的顺序存放。这种存放方式被称为文件的物理结构。

信息查找完成对存放在存储设备上的文件信息的查找。

信息共享与保护6.2文件的组织结构返回1.文件的逻辑结构和存取方法2.

文件物理结构与存储设备3.

文件物理结构、文件存取方式与存储设备的关系4.磁盘调度算法

从用户观点出发，所看到的文件组织形式称为文件的逻辑结构。

从实现观点出发，文件在外存上的存放组织形式称为文件的物理结构。

文件的逻辑结构与存储设备的特性无关，但文件的物理结构与存储设备的特性有很大关系。1.文件的逻辑结构和存取方法

(1)文件的逻辑结构：是用户的可见结构，它独立于在外存上的物理存储。

文件的逻辑结构有两种形式：字符流式的无结构文件记录式的有结构文件①字符流式文件：一个无结构字节序列文件体为字节流（不划分记录，构成文件的基本单位是字符），是无结构的、一串相关的有序字符的集合。文件的长度为所含字符数。

优点：管理简单、操作方便缺点：查找文件中的基本信息单位较困难是当前操作系统中常用的文件逻辑结构，

如UNIX、DOS、WINDOWS系统中的普通文件都是流式文件。②记录式文件：一种结构式文件，是记录的集合可以把文件中的记录按各种不同的方式排列，构成不同的逻辑结构每条记录由彼此相关的域构成每个记录有一个键，可按键进行查找如果文件中所有记录的长度都相同，则这种文件为定长记录文件

定长记录文件的长度=记录个数x记录长度变长记录文件的长度为各记录长度之和

例如:学生登记表文件xsdjb.dbf姓名学号籍贯通信地址邮政编码李铭925678武昌武昌关山街125号430074司马乐925679北京北京海军路88号100034NEXT

根据用户和系统管理上的需要，可以采用多种方式来组织这些记录，形成以下几种文件：顺序文件：记录按某种顺序（按时间的先后顺序或者按关键字排序）排列所形成的文件。索引文件：为记录建立一张索引表，并为每个记录设置一个表项，以加快对记录检索的速度。索引顺序文件：将顺序文件中的记录分组，为顺序文件建立一张索引表，每组中的第一个记录建立一个索引项。选取文件的逻辑结构遵循下述原则：给定的逻辑结构应能尽量减少对已存储好的文件信息的变动。——便于修改给定的逻辑结构应使文件在尽可能短的时间内查找到记录或基本信息单位。——便于查找文件信息占据最小的存储空间。——便于存储便于用户进行操作。——便于操作文件逻辑结构的选择对基本信息单位操作不多的文件较适合于采用字符流的无结构文件例如：源程序文件、目标代码文件等需要对基本信息单位进行修改、追加、查找和管理等操作较多的文件较适合于采用记录的有结构文件例如：数据库文件1.文件的逻辑结构和存取方法

(2)文件的存取方法：指用户读写文件的方法。用户通过对文件的存取来完成对文件的修改、追加和搜索等操作。

通常有三种存取方法：

顺序存取方式

随机(直接)存取方式

按键存取方式

无论是采用哪种存取方法，都是首先查找出操作对象的逻辑地址，然后由逻辑地址映射到对应的物理地址，再对物理地址的有关信息进行操作。顺序存取

按照文件的逻辑地址顺序存取在记录式文件中，按记录的排列顺序来存取，例如：

当前记录为Ri，下一条记录为Ri+1

在字符流文件中，反映为当前读写指针的变化，例如：

当前指针为rPtr，下一存取位置的指针为

rPtr

+

该段的信息长度随机存取（直接存取）

按照文件的记录号，字符序号直接存取在字符流文件中，根据字符的序号来存取文件的任一信息。在记录式文件中，根据存取命令把读写指针移动到欲读写处来读写。

定长记录的文件，只要给出记录号就能求出该记录的首地址。

变长记录的文件，直接存取将是非常困难的。按键存取根据给定的关键字或记录名进行存取首先搜索到要进行存取的记录的逻辑位置，再将其转换到相应的物理地址后进行存取用在复杂的文件系统中，特别是数据库管理系统中2.文件的物理结构和存储设备

(1)文件的物理结构：指文件在外存上的存储结构。它依赖于外存的物理存储介质。文件的物理结构决定了文件信息在存储设备上的存储位置。因此，文件信息的逻辑地址到物理地址的变换也是由文件的物理结构决定的。

在文件系统中，文件的存储设备通常划分成若干个大小相等的物理块（如块长为512B或1024B）。一般把文件信息也划分为与物理存储设备的物理块大小相等的逻辑块。从而，以块作为分配和传送信息的基本单位。

常见的文件物理结构：顺序结构（连续文件）链接结构（串联文件）索引结构（索引文件）连续文件连续文件把一个逻辑上连续的文件信息依次存放到物理块中。连续文件结构图示说明：连续文件示意图文件名始址块数count02tr143mail196list284f62文件目录012345678910111213141516171819202122232425262728293031countftrmaillist连续文件的特点：优点：结构简单存取速度快缺点：不能动态增长部分删除后会有“零头”不适于存放用户文件、数据文件等经常被修改的文件。串联文件串联文件结构用非连续的物理块来存放文件信息。这些非连续的物理块之间没有顺序关系。其中每个物理块设有一个指针，指向其后续连接的另一个物理块，从而使得存放同一文件的物理块链接成一个串联队列。串联文件示意图文件名始址末址jeep925文件目录01234567891011121314151617181920212223242526272829303111016-125串联文件特点：特点：文件长度可动态地增长（只需调整连接指针）搜索效率较低（只能按串联指针顺序搜索）一般只适用于逻辑上连续的文件，且存取方法应该是顺序存取的。不适宜随机存取索引文件系统为每个文件建立一张索引表，表中每一栏目指出文件信息所在的逻辑块号及与之对应的物理块号。索引表的物理地址则由文件说明信息项给出。索引文件示意图012345678910111213141516171819202122232425262728293031文件名索引表地址文件目录Jeep1991611025-1-1-119返回索引文件特点：既可以满足文件动态增长的要求，又可以较为方便和迅速地实现随机存取。使用索引表增加了存储空间的开销。至少二次访问存储器，多级索引访问次数更多。索引表组织:链接模式:一个盘块一个索引表。直接寻址当文件很大时,一个盘块放不下一个索引表，则需要多个盘块来存放索引表，若也按串联方式存放，则增加了存取索引表的时间开销。一种较好的方法是采用多级索引。多级索引:索引表所指的物理块中存放的不是文件信息，而是装有这些信息的物理块的地址。间接寻址综合模式：将索引表的头几项设计成直接寻址方式，也就是这几项所指的物理块号中存放的是文件信息，而索引表的后几项设计成多重索引，也就是间接寻址方式。混合寻址多级索引两级索引分配返回

混合索引方式(综合模式)混合索引方式

UNIX文件系统采用的是综合模式。每个文件的索引表为13个索引项，每项2个字节。最前面10项直接登记存放文件信息的物理块号（直接寻址）如果文件大于10块，则利用第11项指向一个物理块，该块中最多可放256个文件物理块的块号（一次间接寻址）。对于更大的文件还可利用第12和第13项作为二次和三次间接寻址

UNIX中采用了三级索引结构后，文件最大可达16兆个物理块（28，216，224）UNIX文件系统的物理结构1028216224文件物理结构的比较连续文件优点：不需要额外的空间开销，只要在文件目录中指出文件的大小和首块的块号即可，对顺序的访问效率很高。顺序存取、直接存取。缺点：不适合动态地增长，部分删除后会有存储空间浪费；文件创建时要求用户提供文件的大小。串联文件克服了连续文件的不足之处，但文件的随机访问系统开销较大。顺序存取。索引文件既适应于顺序存取，也适应于直接存取，是一种比较好的文件物理结构，但要有用于索引表的空间开销和文件索引的时间开销。09年考研题28.下列文件物理结构中，适合随机访问且易于文件扩展的是（）

A.连续结构

B.索引结构

C.链式结构且磁盘块定长

D.链式结构且磁盘块变长10年考研题30、设文件索引节点中有7个地址项，其中4个地址项为直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4字节，若磁盘索引块和磁盘数据块大小均为256字节，则可表示的单个文件的最大长度是（）A：33kbB：519kbC：1057kbD：16513kb2.文件的物理结构和存储设备

(2)文件存储设备：常用的存储设备有磁盘、光盘和磁带等。存储设备的特性决定了文件的存取设备和方法。

顺序存取设备（如磁带）

直接存取设备（如磁盘）顺序存取设备只有在前面的物理块被存取之后，才能存取后续的物理块的内容为了加速和停转，在物理块前后留有间隙磁带是一种典型的顺序存取设备第i-1块间隙第i块间隙第i+1块…………磁带的特点：磁带适合于顺序存取方式，不适合于随机存取方式和按键存取方式。磁带设备的存取速度或数据传输率与下列因素有关信息密度磁带带速块间间隙带速高、信息密度大、且间隙小，则存取速度高文件存储设备例题——磁带假定磁带记录密度为800字符/英寸，每一逻辑记录为160字符，块间隙为0.6英寸。存储1500个逻辑记录需要多少磁带，并计算磁带利用率？若要使磁带空间利用率不少于50%，至少应为多少个逻辑记录为一组？第i-1块间隙第i块间隙第i+1块…………直接存取设备磁盘是一种典型的直接存取设备。磁盘设备允许文件系统直接存取磁盘上的任意物理块。为了存取一个特定的物理块，磁头将直接移动到所要求的位置上，而不需要像顺序存取那样事先存取其他的物理块。磁盘结构图磁道0磁道1扇区0扇区1每个盘片分为多个扇区，磁盘转动时经过读写磁头形成磁道，磁头臂可由半径方向移动形成多条磁道。柱面扇区磁臂磁头信息记录在磁道上，多个盘片，正反两面都用来记录信息，每面一个磁头所有盘面中处于同一磁道号上的所有磁道组成一个柱面物理地址形式：磁头号（盘面号）柱面号（磁道号）扇区号访盘请求完成过程一次访盘请求（读/写）完成过程由三个动作组成：寻道（时间）：磁头移动定位到指定磁道旋转延迟（时间）：等待指定扇区旋转到磁头下数据传输（时间）：数据在磁盘与内存之间的传输文件存储设备例题——磁盘某软盘有40个磁道，磁头从一个磁道移动到另一个磁道需要6ms。文件在磁盘上非连续存放，逻辑上相邻数据块的平均距离为13磁道，每块的旋转延迟时间和传输时间分别为100ms、25ms，问读取一个100块的文件需要多少时间？解：逻辑上相邻数据块的平均距离为13磁道，读一块数据需要的时间为：

13×6+100+25=203ms（6分）因此，读取一个100块的文件需要的时间：

203×100=20300ms（2分）3.文件物理结构、文件存取方式与文件存储设备的关系返回存取设备磁盘磁带物理结构连续文件串联文件索引文件连续文件文件长度固定

固定、可变

固定、可变固定存取方法

直接、顺序

顺序

直接、顺序顺序4.磁盘调度算法(1)磁盘调度

磁盘是可被多个进程共享的设备。当有多个进程都请求访问磁盘时，应采用一种适当的调度算法，对这些请求的服务顺序调整安排，旨在降低平均磁盘服务时间，达到公平、高效。

公平：一个I/O请求在有限时间内满足高效：减少设备机械运动所带来的时间浪费(2)磁盘调度算法先来先服务（FCFS）：按访问请求到达的先后次序服务优点：简单，公平；缺点：效率不高，相临两次请求可能会造成最内到最外的柱面寻道，使磁头反复移动，增加了服务时间，对机械也不利先来先服务磁盘调度举例

假设磁盘访问序列：98，183，37，122，14，124，65，67。读写头起始位置：53磁道处向外磁道移动，按先来先服务进行磁盘调度98，183，37，122，14，124，65，67磁头走过的总道数：640

最短寻道时间优先（SSTF）：优先选择距当前磁头最近的访问请求进行服务，主要考虑寻道优先。优点：改善了磁盘平均服务时间；缺点：造成某些访问请求长期等待得不到服务。最短寻道时间优先磁盘调度举例

假设磁盘访问序列：98，183，37，122，14，124，65，67。读写头起始位置：53磁道处向外磁道移动，按最短寻道时间优先进行磁盘调度65，67，37，14，98，122，124，183磁头走过的总道数：236

扫描算法（SCAN，电梯算法）

克服了最短寻道优先的缺点，既考虑了距离，同时又考虑了方向。(先方向后距离)

具体做法：当设备无访问请求时，磁头不动当有访问请求时，磁头按一个方向移动，在移动过程中对遇到的访问请求进行服务，然后判断该方向上是否还有访问请求，如果有则继续扫描否则改变移动方向，并为经过的访问请求服务如此反复扫描算法磁盘调度举例

假设磁盘访问序列：98，183，37，122，14，124，65，67。读写头起始位置：53磁道处向外磁道移动，按扫描算法进行磁盘调度走道顺序：53，

37，14，65，67，98，122，124，183磁头走过的总道数：＝(53－14)＋(183－14)＝20809年考研题29.假设磁头当前在第