计算机操作系统第六章

长期存储信息的三个基本要求：1)要能够存储大量的信息。2)长期保存信息。3)可以共享信息。

通常要解决所有这些问题的方法是：把信息以文件(file)为单位，存储在磁盘或其他外部介质上。通过操作系统来管理文件的结构，命名，存取使用，保护和实现方法

文件

记录

主存缓冲区

辅存（磁盘）

结构

访问

中的物理块

中的物理块

目录管理

方法

组块

磁盘调度

用户和程序

命令

操作

文件操作

文件名

函数

I/O

自由空间

管理

文件分配

用户访问控制

文件系统功能文件系统功能1.统一管理文件的存储空间，实施存储空间的分配与回收2.实现文件的按名存取名字空间映射存储空间3.实现文件信息的共享，并提供文件的保护和保密措施4.向用户提供一个方便使用的接口（提供对文件系统操作命令，以及提供对文件的操作命令：信息存取、加工等）5.系统维护及向用户提供有关信息6.文件系统的执行效率7.提供与I/O的统一接口看待文件系统的两种观点用户观点：文件系统如何呈现在其面前：一个文件由什么组成，如何命名，如何保护文件，可以进行何种操作等等。操作系统观点：文件目录怎样实现，怎样管理存储空间，文件存储位置，磁盘实际运作方式(与设备管理的接口)等等。第六章文件管理文件和文件系统文件的逻辑结构外存分配方式目录管理文件存储空间的管理文件的共享与文件保护数据一致性第六章文件管理6.1文件和文件系统

文件系统的管理功能，是通过把它所管理的程序和数据组织成一系列文件的方法来实现的。文件系统是操作系统中统一管理信息资源的一种软件，管理文件的存储、检索、更新，提供安全可靠的共享和保护手段，并且方便用户使用。记录n数据项n文件记录2记录1数据项1数据项2……文件、记录和数据项之间的层次关系6.1.1文件、记录和数据项6.1.1文件、记录和数据项一.数据项1.基本数据项。

用于描述一个对象的某种属性的字符集，是数据组织中可以命名的最小逻辑数据单位，即原子数据，又称为数据元素或字段。学号、姓名、性别、年龄、专业、所在系班等描述一个学生的基本数据项数据项的名字和类型定义了一个数据项的“型”表征一个实体在数据项上的数据称为数据项的“值”2.组合数据项。是由若干个基本数据项组成的，简称组项。工资基本工资工龄工资奖励工资二.记录

记录是一组相关数据项的集合，用于描述一个对象在某方面的属性。

关键字是唯一能标识一个记录的数据项。一个记录应包含哪些数据项，取决于需要描述对象的哪个方面。三.文件

文件是由创建者所定义的、具有文件名的一组相关元素的集合。有结构文件：文件由若干个相关记录组成无结构文件：被看成是一个字符流。文件在文件系统中是一个最大的数据单位，它描述了一个对象集。文件具有文件名，用户利用文件名来访问文件文件属性：3.文件类型4.文件长度5.文件的物理位置6.文件的建立时间1.文件名称2.文件标识符：标识文件系统内文件的惟一标签6.1.2文件类型和文件系统模型一.文件类型1.按用途分类

系统文件由系统软件构成的文件，只允许用户通过系统调用或系统提供的专用命今来执行它们，不允许对其进行读写和修改主要有操作系统核心和各种系统应用程序或实用工具程序和数据组成例如：,,

库文件文件允许用户对其进行读取和执行，但不允许对其进行修改主要由各种标准子程序库组成例如：C语言、FORTRAN子程序库存放在子目录下*.LIB,/lib/,/usr/lib/

用户文件是用户通过操作系统保存的用户文件，由文件的所有者或所有者授权的用户才能使用主要由用户的源程序源代码、可执行目标程序的文件和用户数据库数据等组成例如：*.c,*.DBF,*.OBJ2.按文件中数据的形式分类（1）源文件由源程序和数据构成的文件。（2）目标文件

源程序经过编译，但未链接的目标代码构成的文件。（3）可执行文件

把编译后产生的目标代码再经过链接后形成的文件。3.按存取控制属性分类只读文件：只允许文件主及被核准的用户去读文件，而不允许写文件。标记为：-r-----可读可写文件：允许文件主及被核准的用户去读和写文件。标记为：-rw----可执行文件：允许文件主及被核准的用户去调用执行该文件而不允许读和写文件，标记为：---x---

各个操作系统的保护方法和级别有所不同DOS操作系统三种保护：系统、隐藏、可写UNIX或Linux操作系统有九个级别的保护4.UNIX系统将文件分为三类普通文件(regular)

包含的是用户的信息，一般为ASCII或二进制文件目录文件(directory)

管理文件系统的系统文件特殊文件(specialfile)

设备文件，把外部设备也看作文件。

字符设备文件：和输入输出有关，用于模仿串行I/O设备，例如终端，打印机，网络等块设备文件：模仿磁盘5.按使用情况分类临时文件：用于系统在工作过程中产生的中间文件，一般有暂存的目录，正常工作情况下，工作完毕会自动删除，一旦有异常情况往往会残留不少临时文件永久文件:

指一般受系统管理的各种系统和用户文件，经过安装或编辑、编译生成的文件，存放在软盘、硬盘或光盘等外存上档案文件:

系统或一些实用工具软件包在工作过程中记录在案的文挡资料文件，以便查阅历史挡案6.按存取的物理结构分类顺序（连续）文件文件中的记录，顺序地存储到连续的物理盘块中，顺序文件中所记录的次序，与它们存储在物理介质上存放的次序是一致的链接文件文件中的记录可存储在并不相邻接的各个物理块中，通过物理块中的链接指针组成一个链表管理，形成一个完整的文件,又称指针串连文件或直接存取文件索引文件文件中的记录可存储在并不相邻接的各个物理块中，记录和物理块之间通过索引表项按关键字存取文件，通过物理块中的索引表管理，形成一个完整的文件7.按文件的逻辑存储结构分类有结构文件由若干个记录所构成的文件，故又称为记录式文件无结构文件这是直接由字符序列所构成的文件，故又祢为流式文件二.文件系统模型用户（程序）对象及其属性对对象操纵和管理的软件集合文件系统接口1.对象及其属性文件管理系统管理的对象有：文件目录磁盘（磁带）存储空间用户（程序）对象及其属性对对象操纵和管理的软件集合文件系统接口2.对对象操纵和管理的软件集合

这是文件管理系统的核心部分。用户（程序）对象及其属性对对象操纵和管理的软件集合文件系统接口3.文件系统的接口（1）命令接口。用户与文件系统交互的接口。（2）程序接口用户程序与文件系统的接口。用户（程序）对象及其属性对对象操纵和管理的软件集合文件系统接口堆

顺序

索引顺序

索引

散列

逻辑I/O

基本I/O管理程序

基本文件系统

磁盘设备驱动器

磁带设备驱动器

用户程序

最底层的设备驱动器直接和外围设备控制器或通道进行通信。三、文件系统结构举例堆

顺序

索引顺序

索引

散列

逻辑I/O

基本I/O管理器

基本文件系统

磁盘设备驱动器

磁带设备驱动器

用户程序

基本文件系统(BasicFileSystem)，或物理I/O层(physicalI/Olevel)，它是与计算机系统外部环境的主要接口。它处理磁盘或磁带间交换的数据块。堆

顺序

索引顺序

索引

散列

逻辑I/O

基本I/O管理器

基本文件系统

磁盘设备驱动器

磁带设备驱动器

用户程序

基本I/O管理器(BasicI/OSupervisor)，负责所有文件I/O的初始化和终止。堆

顺序

索引顺序

索引

散列

逻辑I/O

基本I/O管理器

基本文件系统

磁盘设备驱动器

磁带设备驱动器

用户程序

逻辑I/O(LogicalI/O)作为文件系统的一部分，允许用户和应用程序访问记录。堆

顺序

索引顺序

索引

散列

逻辑I/O

基本I/O管理器

基本文件系统

磁盘设备驱动器

磁带设备驱动器

用户程序

文件系统中与用户最接近的层是访问方法层，也称为存取方法(AccessMethod)层。6.1.3文件操作

用户通过文件系统所提供的系统调用实施对文件的操作。一.最基本的文件操作创建文件删除文件读文件写文件截断文件设置文件的读/写位置1、创建文件：

分配外存空间，在目录中建立一个目录项：文件名称、位置等。2、删除文件：

使目录项成为空项，回收存储空间。3、读文件：

文件名和内存目标地址，目录项中的指针用于对文件的读写。4、写文件：

文件名及在内存中的源地址，用目录中的写指针进行写。5、截断文件：

将原有文件的长度设置为0。6、设置文件的读/写位置：

设置文件读／写指针的位置。

文件系统调用的一个UNIX示例程序：把文件从源文件处复制到目标文件处/*cpsrcdest复制文件，src'到'dest'．*/#include<sys/types.h>/*包含一些类型说明*/#include<fcntl.h>/*说明0_RDONLY等*/#include<stdlib.h>/*包含系统调用原型*/#include<unistd.h>/*包含系统调用原型*/copyfileabcxyzvoidmain(intargc，char*argv[])；

/*ANSIC原型*/#defineBUF_SIZE4096/*说明读写单位*/#defineMODE0666/*文件方式(rw-rw-rw-)*/voidmain(intargc，char*argv[])／*argc：参数个数，argv：参数指针*/3argv[0]:“copyfile“argv[1]:”abc‘argv[2]:"xyz"{intsrc，dst，in，out；

charbuf[BUF_SIZE];if(argc！=3)exit(1)；

/*参数个数错*//*打开源文件：，建立目标文件*/src=open(argvt[l]，O_RDONLY)；

/*只读打开源文件*/if(src<0)exit(2)；

/*不能打开源文件*/dst=creat(argv[2]，MODE)；

/*试图建立目标文件*/if(dst<0)exit(3)；

/*不能建立目标文件*//*Everythingworked．DOthecopy．*/while(1){/*无限循环*/in=read(src，buf，BUF_SIZE)；/*从源文件读*/if(in<=0)break；/*文件结尾终止循环*/out=write(dst，buf，in)；/*往目标文件写字节*/if(out<=0)break；*由于出错结束循环*/}close(src)；/*关闭源文件*/close(dst)；/*关闭新创建的文件*/exit(0)；/*退出*/}二.文件的“打开”和“关闭”操作OS对文件的操作，其过程有两步：通过检索文件目录来找到指定文件的属性及其在外存上的位置。对文件实施相应的操作，如读文件或写文件。为避免重复地检索目录，引入了“open”系统调用

是指系统将指名文件的属性（包括该文件在外存上的物理位置）从外存拷贝到内存打开文件表的一个表目中，并将该表目的编号（或称为索引）返回给用户。会把该文件在打开文件表中的表目删除掉。打开：（Open）关闭：（Close）通过使用该编号而不是真实文件名称，进行I/O操作，避免进一步搜索和简化系统调用接口。三.其他文件操作常用的一类是有关对文件属性进行操作的；另一类是有关目录的；用于实现文件共享的系统调用用于对文件系统进行操作的系统调用第六章

文件管理

6．2文件逻辑结构

文件结构的两种观点用户观点（逻辑结构）：研究的是用户思维中的抽象文件，也叫逻辑文件（文件组织）。其目的是为用户提供一种结构清晰、使用简便的逻辑组织。用户按此去存储、检索和加工处理有关文件信息。实现观点（物理结构）：研究的是存储在物理设备介质上的实际文件，即物理文件。其目的是选择一些性能良好、设备利用率高的物理结构。系统按此和外部设备打交道，控制信息的传输。文件的逻辑结构：从用户观点出发，是用户可以直接处理的数据及其结构，独立于文件的物理特性，又称为文件组织。文件的物理结构：又称为文件的存储结构，文件在外存上的存储组织形式。存储性能有关，与外存分配方式有关影响文件的检索速度

文件组织的两种观点一条记录一个字节字节序列记录序列树

对文件逻辑结构的要求：提高检索速度便于修改降低文件的存储费用便于用户进行操作磁盘，磁带，光盘（1）物理块(块)

在文件系统中，文件的存储设备常常划分为若干大小相等的物理块。同时也将文件信息划分成相同大小的逻辑块（块），所有块统一编号

以块为单位进行信息的存储、传输、分配实现的观点：存储介质（2）磁带：永久保存大容量数据顺序存取设备：前面的物理块被存取访问之后，才能存取后续的物理块的内容存取速度较慢，主要用于后备存储，或存储不经常用的信息，或用于传递数据的介质第i块间隙第i+1块（3）磁盘

直接（随机）存取设备：

存取磁盘上任一物理块的时间不依赖于该物理块所处的位置磁道扇区柱面扇区磁臂磁头

物理地址形式：磁头号（盘面号）磁道号（柱面号）扇区号

信息记录在磁道上，多个盘片，正反两面都用来记录信息，每面一个磁头所有盘面中处于同一磁道号上的所有磁道组成一个柱面

磁盘系统由磁盘本身和驱动控制设备组成，实际存取读写的动作过程是由磁盘驱动控制设备按照主机要求完成的一次访盘请求：读/写，磁盘地址（设备号，柱面号，磁头号，扇区号），内存地址（源/目）（4）光盘

光盘容量大，速度快，价格便宜，但一般不可写可读写光盘驱动器价格贵，写过程很麻烦光盘的空间结构与磁盘类似（5）外存的特点容量大，断电后仍可保存信息，速度较慢，成本较低由两部分组成：驱动部分+存储介质种类很多外存空间组织与地址与存取方式非常复杂I/O过程方式非常复杂（6）用户对外存的要求

用户对外存的使用：读写外存数据用户对外存的要求：方便、效率、安全在读写外存时不涉及硬件细节，使用逻辑地址和逻辑操作(方便)存取速度尽可能快，容量大且空间利用率高（效率）外存上存放的信息安全可靠，防止来自硬件的故障和他人的侵权（安全）可以方便地共享，动态扩缩，携带拆卸，了解存储情况和使用情况以尽可能小的代价完成上述要求6.2.1文件逻辑结构的类型（1）有结构文件（2）无结构文件记录式文件流式文件一.有结构文件定长记录。文件中所有记录的长度都是相同的。变长记录。文件中各记录的长度不相同。文件的存取方法顺序文件。由一系列记录按某种顺序排列所形成的文件。索引文件。记录为可变长度，为之建立一张索引表，为每个记录设置一个表项。索引顺序文件。上述两种文件构成方式的结合。它为文件建立一张索引表，为每一组记录中的第一个记录设置一个表项。二.无结构文件

其长度以字节为单位。对流式文件的访问，则是采用读写指针来指出下一个要访问的字符。6.2.2顺序文件一.逻辑记录的排序

第一种是串结构，各记录之间的顺序与关键字无关。按存入时间的先后排列。

第二种情况是顺序结构，指文件中的所有记录按关键字排列。当读完一个记录时，便执行Rptr：=Rptr+LRiR3R2R1R0……0L2L3L4LL（i+1）LLLLLLRptr定长记录文件二.对顺序文件（SequentialFile）的读/写操作读指针，指向下一个记录的首地址记录长度RiR3R2R1R0……0L2L3L4LL（i+1）LLLLLLWptr定长记录文件

每写完一个记录时，又需执行以下操作:Wptr：=Wptr+L写指针，指向要写的记录的首地址

变长记录的顺序文件，读或写指针加上Li+1。变长记录文件LiRiR1L1R0L0……L0+1L0+L1+2Σ（Lk+1）L0L1LiWptrk=0i-1Σ（Lk+1）k=0i0Li是刚读或刚写完的记录的长度。每个记录长度存于记录前的单元中三.顺序文件的优缺点

优点：对诸记录进行批量存取，顺序文件的存取效率是所有逻辑文件中最高的；此外，也只有顺序文件才能存储在磁带上，并能有效地工作。缺点：在交互应用的场合，顺序文件所表现出来的性能就可能更差。顺序文件的另一个缺点是，如果想增加或删除一个记录，都比较困难。6.2.3索引文件

对于定长记录文件，要查找第i个记录，第i个记录相对于第一个记录首址的地址：

对于可变长度记录的文件，要查找其第i个记录时，顺序地查找每个记录，计算得到地址：Ai=ΣLi+ii=0i-1Ai=i×L……索引表RiR1R0……逻辑文件索引文件的组织

利用关键字进行折半查找索引表是一个定长记录的顺序文件，可以方便地实现直接存取索引号长度m指针ptr0m01m1imi使用索引文件的主要问题是须配置一张索引表，提高了存储费用。

索引文件有较快的检索速度，用于对信息处理的及时性要求较高的场合。索引文件的优缺点6.2.4索引顺序文件ChenLinBaoRongAnQi逻辑地址键BaoRongAnKangAnQi其他属性姓名…逻辑文件

在一个顺序文件中所含有的记录数为N，平均须查找N/2个记录。

索引顺序文件，只要查找N1/2

个记录数。含有106

个记录的顺序文件平均查找1000个记录

多级索引，为索引文件再建立一张索引表。

例如：有106

个，每100个记录为一组，有104

个索引表项。每100个索引表项为一组，故具有102

个表项。平均查找50+50+50个记录6.2.5直接文件和哈希文件1.直接文件

可根据给定的记录键值，直接获得指定记录的物理地址。这种由记录键值到记录物理地址的转换称为键值转换。关键：用什么方法进行从记录键值到物理地址的转换2.哈希（Hash）文件

它利用Hash函数，可将记录键值转换为相应记录的地址。为实现文件存储空间的动态分配，由Hash函数所求得的是指向一目录表相应表目的指针，该表目的内容指向相应记录所在的物理块。键值fHash函数目录表Hash文件的逻辑结构引起地址冲突6.3外存分配方式怎样才能有效利用外存空间？如何提高对文件的访问速度？文件的物理结构主要问题：6.3.1连续分配一.连续分配方式

连续分配要求为每一个文件分配一组相邻接的盘块。filestartlengthcount02tr143mail196list284f62目录048121620242815913172125292610141822263037111519232731countmaillisttrf此时的物理文件称为顺序文件

顺序文件由一组相邻的物理块组成，是对记录式文件取连续区分配而构成的文件。当文件逻辑记录和物理块大小相等时；假设，第i个逻辑记录对应第m块，则第i+n个记录对应==>m+n

当记录与块不等时。则记录i所在的块号＝[i*l/块长]取整例：逻辑记录l=256物理块n=512

存取i=3的记录块号＝[256*3/512]=1余0.5

同内存的动态分区分配一样，随着文件建立时空间的分配和文件删除时空间的回收，形成外存的碎片。可利用紧凑的方法顺序存取设备：磁带磁带：不适合于随机存取二.连续分配的主要优缺点主要优点：顺序访问容易顺序访问速度快主要缺点：要求有连续的存储空间必须事先知道文件的长度文件不能动态增长

连续分配所存在的问题就在于：必须为一个文件分配连续的磁盘空间。6.3.2链接分配（链表分配）

采用链接分配方式时，可通过在每个盘块上的链接指针，将同属于一个文件的盘块链接成一个链表，称为链接文件。

隐式链接显式链接链接分配的形式11016-125048121620242815913172125292610141822263037111519232731filestartendjeep925

目录一.隐式链接如果指针占用4字节，若盘块为512字节，每个盘块只有508个字节供用户使用。

只适用于顺序访问，它对随机访问是极其低效的。

为了提高检索速度和减小指针所占用的存储空间，可以将几个盘块组成一个簇。以簇为单位进行分配隐式链接分配方式的缺点二.显式链接21540物理块号

012345FATFCB

每个表项中存放链接指针，即下一个盘块号。某一文件的第一个盘块号，作为文件地址被填入相应文件的FCB的“物理地址”字段中。该表称为文件分配表FAT。49EOF51011EOF60123456789FCBAFCBBFATMS-DOS的文件物理结构

对于1.2MB的软盘，盘块大小为1KB。每个FAT中含有1.2K个表项，每个FAT表项占12位，故共须1.8KB。

200MB的硬盘，盘块大小为1KB，有200K个盘块。

FAT的每个表项需2.5个字节，故共须占用500KB。链接分配方式的问题:不能支持高效的直接存取FAT需占用较大的内存空间6.3.3索引分配一.单级索引分配

索引分配方式支持直接访问。

索引分配方式的主要问题是：可能要花费较多的外存空间。目录048121620242815913172125292610141822263037111519232731countfile块序号jeep1991611025-1-1-119二.多级索引分配

当文件太大，其索引块太多时，这种方法是低效的。应为这些索引块再建立一级索引，称为第一级索引，即系统再分配一个索引块，将第一块、第二块等索引块的盘块号填入到此索引表中。两级索引分配方式1125740360254106105357356985主索引第二级索引360磁盘空间740……1125012105106254356357985……………两级索引分配

每个盘块的大小为1KB，每个盘块号占4个字节，一个索引块中可存放256个盘块号。盘块号总数N=256×256=64K个盘块号

有此可得出结论：采用两级索引时，所允许的文件最大长度为64MB。两级索引分配

每个盘块号占4个字节倘若盘块的大小为4KB，在采用单级索引时所允许的文件最大长度为；而在采用两级索引时所允许的文件最大长度可达。4MB4GB思考题

一个文件系统中有一个20MB大文件和一个20KB小文件,当分别采用连续、隐式链接、链接索引、二级索引(和LINUX)分配方案时，每块大小为4096B,每块地址用4B表示，问:（1）各文件系统管理的最大的文件是多少?（2）每种方案对大、小两文件各需要多少专用块来记录文件的物理地址(说明各块的用途)?（3）如需要读大文件前面第5.5KB的信息和后面第（16M＋5.5KB）的信息，则每个方案各需要多少次盘I/O操作?

以多级索引为例记录数为K，物理块长度为N，满足N<K<=N2，可采用二级索引。设K=N2，需N+1索引块，每个索引中有N个表目设：N=10

，K=86要存取i=74的记录，可通过：

1.确定第一级索引（主索引）的表目

[i/N]取整=[74/10]取整=7；

2.确定在二级索引i=7的表目中的位置:

Imod

N==>74mod

10=4多级索引

索引结构优缺点优点：

保持了链接结构的优点,又解决了其缺点：即能顺序存取,又能随机存取，满足了文件动态增长、插入删除的要求，也能充分利用外存空间缺点：

较多的寻道次数和寻道时间，索引表本身带来了系统开销，如：内外存空间，存取时间三.混合索引分配方式

指将多种索引分配方式相结合而形成的一种分配方式。在UNIX系统中采用。tripleindirectdoubleindirectsingleindirecti.addr(0)i.addr(1)directblocksblockcountsizetimestamps(3)owners(2)modedatadatadatadatadatadata……………datadatadatadata混合索引方式

在BSDUNIX的索引结点中，设置了13个地址项，把所有的地址分成两类，直接地址和间接地址。1.直接地址

设置10个直接地址项。假如每个盘块的大小为4KB，文件不大于40KB时，可直接从索引结点中读出该文件的全部盘块号。2.一次间接地址文件长度大于40KB时，用一次间接分配方式，地址项iaddr(10)来提供。实质上是一级索引分配方式。允许文件长达4MB。3.多次间接地址

文件长度大于4MB+40KB时，用二次间接分配方式。文件长度可达4GB。iaddr（12）作为三次间接地址，可达4TB。每个盘块号为4字节文件类型与文件存取器、存取方法的关系

存取设备磁盘、磁鼓磁带文件类型连续文件链接文件索引文件Hash文件连续文件文件长度固定固定、可变固定、可变固定、可变固定存取方法直接、顺序顺序直接、顺序直接、顺序顺序思考题

一个文件系统中有一个20MB大文件和一个20KB小文件,当分别采用连续、隐式链接、链接索引、二级索引和LINUX

分配方案时，每块大小为4096B,每块地址用4B表示，问:（1）各文件系统管理的最大的文件是多少?（2）每种方案对大、小两文件各需要多少专用块来记录文件的物理地址(说明各块的用途)?（3）如需要读大文件前面第5.5KB的信息和后面第（16M＋5.5KB）的信息，则每个方案各需要多少次盘I/O操作?6.4目录管理要求：实现“按名存取”提高对目录的检索速度文件共享允许文件重名文件目录：是文件系统中主要数据结构之一,文件存储后用户通过用户文件逻辑结构的索引链接找到对应的物理结构按文件符号名把文件信息的逻辑结构映象设备介质的物理结构，由文件目录实现把文件操作命令转换相应I/O指令。需要文件目录6.4.1文件控制块和索引结点文件与文件控制块一一对应。用于描述和控制文件的数据结构(FCB）文件目录文件控制块的有序集合文件目录项一个文件控制块就是一个文件目录项目录文件一个文件目录也被看作是一个文件一.文件控制块1.基本信息类文件名文件物理位置文件逻辑结构文件的物理结构2.存取控制信息类

文件主的存取权限、核准用户的存取权限以及一般用户的存取权限。3.使用信息类

文件的建立日期和时间、文件上一次修改的日期和时间及当前使用信息。MS-DOS中的文件控制块，FCB的长度为32个字节，对360KB的软盘，总共可包含112个FCB，共占4KB的存储空间。文件名扩展名属性备用时间日期第一块号盘块数

FCB的创建过程用户进程请求打开文件；文件系统读出有关目录信息；如有误，返回状态信息；生成新的FCB；在FCB中设置有关信息；更新目录信息；将FCB挂到调用进程的PCB上；向用户进程返回状态信息。二.索引结点1.索引结点的引入

设目录文件所占用的盘块数为N。假如一个FCB为64B，盘块大小为1KB，则每个盘块中只能存放16个FCB；若一个文件目录中共有640个FCB，需占用40个盘块，故平均查找一个文件需启动磁盘次。UNIX系统把文件名与文件描述信息分开20

把文件描述信息单独形成一个称为索引结点的数据结构，简称为i结点。

一个目录项仅占16个字节，其中14个字节是文件名，2个字节为i结点指针。……文件名2文件名1索引结点编号文件名0131415UNIX的文件目录2.磁盘索引结点

每个文件有唯一的一个磁盘索引结点。文件主标识符文件类型文件存取权限文件物理地址文件长度文件连接计数文件存取时间-普通文件

d目录文件

b块设备文件

c字符设备文件

l链接文件所有者组其他RWERWERWE3.内存索引结点存放在内存中的索引结点索引结点编号:用于标识内存索引结点。状态:指示i结点是否上锁或被修改。

访问计数:每当有一进程要访问此i结点时，将该访问计数加1，访问完再减1。文件所属文件系统的逻辑设备号链接指针:设置有分别指向空闲链表和散列队列的指针。6.4.2目录结构

目录结构是指专门的目录文件的组织形式。文件名2文件名1状态位文件说明物理地址文件名…一.单级目录结构

优点：简单且能实现目录管理的基本功能——按名存取

缺点：查找速度慢不允许重名不便于实现文件共享单级目录的优缺点二.两级目录第一级为系统目录MFD

：第二级为用户目录UFD

：GaoZhangWang指向子目录指针用户名TestAlphaMisxDeviceBetaTestReportWang用户目录Zhang用户目录Gao用户目录AlphaTestReportTestBetaDeviceMisx

1.提高了检索目录的速度。2.在不同的用户目录中，可以使用相同的文件名。3.不同用户还可使用不同的文件名来访问系统中的同一个共享文件。主目录中有n个子目录，每个用户目录最多为m个目录项，最多只检索n+m个目录项。采用单级目录结构，最多需检索n×m个目录项。两级目录的优点三.多级目录结构1.目录结构

多级目录结构又称为树型目录结构，主目录在这里被称为根目录，把数据文件称为树叶，其它的目录均作为树的结点。任何一级目录中的FCB既可以描述次一级的子目录，又可以描述一个数据文件。10CBA1DBADEFKNJAGFHAKMJCA234567891112131415161718192021ba多级目录结构2.路径名

从根目录到任何数据文件，都只有一条惟一的数据通路。在该路径上从树的根（即主目录）开始，把全部目录文件名与数据文件名，依次地用“/”连接起来，即构成该数据文件的路径名。3.当前目录“工作目录”相对路径名:从当前目录开始直到数据文件为止所构成的路径名。绝对路径名:从树根开始的路径名称加速文件FCB的查找，进程控制块存有当前目录信息4.增加和删除目录如果要删除的目录不空，可采取下述两种方法：（1）不删除非空目录（2）可删除非空目录6.4.3目录查询技术一.线性检索法（顺序检索法）

首先，系统应读入第一个文件分量名usr，用它与根目录文件中各目录项中的文件名顺序地进行比较，找到匹配者，得到匹配项的索引结点号6。tmp8usr6etc9lib14dev7bin4 ··1 ·1根目录查找/usr/ast/mbox的步骤当前工作目录当前工作目录的父目录

从6号索引结点中得知usr目录文件放在132号盘块中，将该盘块内容读入内存。tmp8usr6etc9lib14dev7bin4 ··1 ·1根目录132结点6是/usr的目录查找/usr/ast/mbox的步骤文件主标识符文件类型文件存取权限文件物理地址文件长度文件连接计数文件存取时间

系统再将路径名中的第二个分量名ast读入，用它与放在132号盘块中的第二级目录文件中各目录项的文件名顺序进行比较，又找到匹配项，从中得到ast的目录文件放在26号索引结点中。tmp8usr6etc9lib14dev7bin4 ··1 ·1根目录132结点6是/usr的信息bal45ast26jim51erik30dick19··1·6132号盘块是/usr的目录查找/usr/ast/mbox的步骤

从26号索引结点中得知/user/ast是存放在496号盘块中，再读入496号盘块。tmp8usr6etc9lib14dev7bin4 ··1 ·1根目录132结点6是/user的目录bal45ast26jim51erik30dick19··1·6132号盘块是/user的目录496结点26是/user/ast的目录查找/usr/ast/mbox的步骤

系统又将该文件的第三分量名mbox读入，用它与第三级目录文件/usr/ast中各目录项中的文件名进行比较，得到/usr/ast/mbox的索引结点号为60，在60号索引结点中存放了指定文件的物理地址。tmp8usr6etc9lib14dev7bin4 ··1 ·1根目录132结点6是/usr的目录bal45ast26jim51erik30dick19··1·6132号盘块是/usr的目录496结点26是/usr/ast的目录src17minik81mbox60books92grants64··6·26496号盘块是/usr/ast的目录tmp8user6etc9lib14dev7bin4 ··1 ·1根目录132结点6是/usr的目录bal45ast26jim51erik30dick19··1·6132号盘块是/usr的目录496结点26是/usr/ast的目录src17minik81mbox60books92grants64··6·26496号盘块是/usr/ast的目录查找/usr/ast/mbox的步骤二.Hash方法

用Hash方法查询，即系统利用用户提供的文件名并将它变换为文件目录的索引值，再利用该索引值到目录中去查找。

在进行文件名的转换时，有可能把n个不同的文件名转换为相同的Hash值，出现了“冲突”。处理“冲突”的有效规则是：（1）在利用Hash法索引查找目录时，如果目录表中相应的目录项是空的，则表示系统中并无指定文件。（2）如果目录项中的文件名与指定文件名相匹配，则表示该目录项正是所要寻找是文件所对应的目录项，故而可从中找到该文件所在的物理地址。（3）如果在目录表的相应目录项中的文件名与指定文件名并不匹配，则表示发生了“冲突”，此时须将其Hash值再加上一个常数。形成新的索引值，再返回到第一步重新开始查找。操作系统是如何引导的呢？引导扇区FAT1FAT2(重复的)根文件夹其他文件夹及所有文件剩余扇区MBR(masterbootrecord),即主引导记录DBR区(DOSBOOTRECORD)即操作系统引导记录区FAT16文件系统布局MBR指的是硬盘的第0个柱面(cylinder)的第0磁道(track)的第0扇区(sector)。目录区文件区目录区文件区目录区文件区卷1卷2盘1卷3盘2盘3

文件存储于文件卷中，文件卷可以是一个物理盘，也可以是一个物理盘的一部分，一个支持超大型文件的文件卷也可以由多个物理盘组成。参见下图：6.5文件存储空间的管理

文件管理要解决的重要问题之一是:如何为新创建的文件分配存储空间。6.5.1空闲表法和空闲链表法一.空闲表法1.空闲表。连续分配方式

它为每个文件分配一块连续的存储空间。系统为外存上的所有空闲区建立一张空闲表，每个空闲区对应一个空闲表项。

序号第一空闲盘块号

空闲盘块数12429331554——2.存储空间的分配和回收与内存相似二.空闲链表法将所有空闲盘区拉成一条空闲链1.空闲盘块链将磁盘上的所有空闲空间，以盘块为单位拉成一条链。2.空闲盘区链将磁盘上的所有空闲盘区拉成一条链。6.5.2位示图法一.位示图

11100011100100110

12345678910111213141516

20001111110000111

311100011111110004…16

申请物理块时，可以在位示图中查找为0的位，返回对应物理块号。

归还时；将对应位转置0。

描述能力强，适合各种物理结构。二.盘块的分配1.顺序扫描位示图2.将所找到的一个或一组二进制位，转换成与之相应的盘块号。

b=n(i-1)+j3.修改位示图

map(i,j)=1三.盘块的回收盘块的回收分为两步：1.将回收盘块的盘块号转换成位示图中的行号和列号。2.修改位示图。i=(b-1)DIVn+1j=(b-1)MODn+1令map[i，j]=06.5.3成组链接法空闲表法和空闲链表法，都不适用于大型文件系统。一.空闲盘块的组织1.空闲盘块号栈。用来存放当前可用的一组空闲盘块的盘块号以及栈中尚有的空闲盘块号数N。N还兼作栈顶指针用。栈是临界资源，系统为栈设置了一把锁。100300299202201s.free019899……79997901…2.文件区中的所有空闲盘块，被分成若干个组。299201…

300399301…

40078997801…

79003.将每一组含有的盘块总数N和该组所有的盘块号，记入其前一组的第一个盘块的S.free（0）~S.free（99）中。……79997901…299201…100400399301300399301…10050049940140078997801…990799979017900100300299202201s.free0198994.将第一组的盘块总数和所有的盘块号，记入空闲盘块号栈中。……79997901…299201…100400399301300399301…10050049940140078997801…990799979017900最末一组只有99个盘块，在S.free（0）中则存放“0”100300299202201s.free01989979997901…299201…100400399301300399301…10050049940140078997801…9907999790179002、空闲盘块的分配与回收100300299202201s.free01989979997901…299201…100400399301300399301…10050049940140078997801…99079997901790099300299202

s.free0198

79997901…299201…100400399301300399301…10050049940140078997801…9907999790179001300

s.free0

79997901…299201…100400399301300399301…10050049940140078997801…990799979017900100400399302301s.free01989979997901…299201…

300399301…10050049940140078997801…990799979017900

在系统回收空闲盘块时，须调用盘块回收过程进行回收。它是将回收盘块的盘块号记入空闲盘块号栈的顶部，并执行空闲盘块数加1操作。当栈中空闲盘块号数目已达100时，表示栈已满，便将现有栈中的100个盘块号，记入新回收的盘块中，再将其盘块号作为新栈底。100400399302301s.free01989979997901…299201…

300399301…10050049940140078997801…9907999790179001300

s.free0

79997901…299201…100400399301300399301…10050049940140078997801…9907999790179006.6文件共享与文件保护

在现代计算机系统中，必须提供文件共享手段，即指系统应允许许多用户（进程）共享同一文件。

文件共享形式与目的1）定义:一个文件被多个用户或程序使用2）共享形式：被多个用户使用，由存取权限控制被多个程序使用，但各用自己的读写指针被多个程序使用，但共享读写指针多个用户用相同或不同的名字来访问同一文件。3）目的:节省时间和存储空间，减少了用户工作量；进程间通过文件交换信息6.6.1基于索引节点的共享方式

在树型结构的目录中，当有两个（或多个）用户要共享一个子目录或文件时，必须将共享文件或子目录链接到两个（或多个）用户的目录中，才能方便地找到该文件。ABCBCCBCAC

？BBCCC根目录包含有共享文件的文件系统如何建立B目录与共享文件之间的链接呢？

如果在文件目录中包含了文件的物理地址，即文件所在盘块的盘块号，则在链接时，必须将文件的物理地址拷贝到B目录中去。而新增加的部分内容已不能共享

为解决这个问题，可引用索引节点。在文件目录中只设置文件名及指向相应索引节点的指针。索引节点还应有一个链接计数count，用于表示链接到本索引节点上的用户目录项的数目。

Testr

TestrWang用户文件目录Lee用户文件目录Count=2文件物理地址索引节点Test基于索引节点的共享方式C的目录owner=ccount=1链接前B的目录C的目录owner=ccount=2建立链接后B的目录拥有者删除文件后进程B链接前后的情况如果用户C不再需要此文件，是否能将此文件删除呢？不能6.6.2利用符号链实现文件共享

为使B能共享C的一个文件F，可以由系统创建一个LINK类型的新文件，也取名为F，并将F写入B的目录中，以实现B的目录与文件F的链接。在新文件中只包含被链接文件F的路径名。这样的链接方法被称为符号链接（SymbolicLinking）。

只是文件主才拥有指向其索引节点的指针；而共享该文件的其他用户，则只有该文件的路径名，并不拥有指向其索引节点的指针。

然而符号链的共享方式也存在自己的问题：当其他用户去读共享文件时，系统是根据给定的文件路径名，逐个分量（名）地去查找目录，直至找到该文件的索引节点。每次访问共享文件时，都可能要多次地读硬盘。优点：方便地链接任一文件（用路径名）缺点：访问共享文件时开销大（多次读盘，消费盘空间），每一共享文件都要增加一文件名（因路径名各不相同）符号链实现文件共享优缺点

两种链接方式的共同问题：每一个共享文件都有几个文件名。文件共享的实现1)基于索引结点的共享方式

Unix/Linux硬链接2)利用符号链实现文件共享

Unix/linux软连接

Windows快捷方式文件的保护机制文件保护用于提供安全性的特定的操作系统机制。对拥有权限的用户，应该让其进行相应操作，否则，应禁止防止其他用户冒充对文件进行操作实现：*用户验证*存取控制6.6.3磁盘容错技术影响文件安全性的主要因素：人为因素系统因素自然因素措施：通过存取控制机制来防止由人为因素所造成的文件不安全性。通过磁盘容错技术，来防止由磁盘部分的故障所造成的文件不安全性。通过“后备系统”来防止由自然因素所造成的不安全性。

容错技术是通过在系统中设置冗余部件的办法，来提高系统可靠性的一种技术。磁盘容错技术则是通过增加冗余的磁盘驱动器、磁盘控制器等方法，来提高磁盘系统可靠性的一种技术。

磁盘容错技术也被称为系统容错技术SFT（SystemFaultTolerance）可分为三个级别：SFT-Ⅰ：用于防止磁盘表面发生缺陷所引起的数据丢失SFT-Ⅱ：SFT-Ⅲ：用于防止由磁盘驱动器和磁盘控制器的故障所导致的系统不能正常工作高级系统容错技术一.第一级容错技术SFT-Ⅰ1.双份目录和双份文件分配表

在磁盘上存放的文件目录和文件分配表FAT被破坏等效于文件的丢失。可在不同的磁盘上或在磁盘的不同区域中，分别建立（双份）目录表和FAT。一份被称为主目录及主FAT；另一份称为备份目录及备份FAT。2.热修复重定向和写后读校验（1）热修复重定向。系统将磁盘容量的一部分作为热修复重定向区，用于存放当发现磁盘有缺陷时的待写数据，并对写入该区的所有数据进行登记，以便于以后对数据进行访问。对磁盘表面有少量缺陷的情况采取某种补救措施后继续使用。（2）写后读校验。应该在每次从内存缓冲区中向磁盘中写入一个数据块后，又立即从磁盘上读出该数据块，并立即送至另一缓冲区中，再将该缓冲区内容与内存缓冲区中在写后仍保留的数据进行比较，若两者一致，写入成功，可继续；否则，再重写。二.第二级容错技术SFT-Ⅱ1.磁盘镜像。如果磁盘驱动器发生故障，SFT-Ⅰ无能为力，仍可能造成数据丢失。主机磁盘控制器通道磁盘驱动器磁盘镜像示意

在每次向主磁盘写入数据后，都需要采用写后校验方式，将数据再同样写到备份磁盘上。

磁盘镜像虽然实现了容错功能，但并未能使服务器的磁盘I/O速度得到提高，相应地，却使磁盘的利用率降至仅为50%。

磁盘镜像功能解决了在一台磁盘机故障时的数据保护问题，但若控制这两台磁盘驱动器的磁盘控制器发生故障，或主机到磁盘控制器之间的通道发生了故障，则此时将使这两台磁盘机同时失效。故增加磁盘双工功能。2.磁盘双工

所谓磁盘双工，是指将两台磁盘驱动器分别接到两个磁盘控制器上，同样使这两台磁盘机镜像成对。主机通道磁盘驱动器通道磁盘控制器磁盘控制器磁盘双工示意主机通道磁盘驱动器通道磁盘控制器磁盘控制器

在磁盘双工时，文件服务器同时将数据写到两个处于不同控制器下的磁盘上，使两者有完全相同的位像图。

由于每一个磁盘都有自己的独立通道，故可同时（并行）将数据写入磁盘。在读数据时，可采用分离搜索（SplitSeek）技术。主机通道磁盘驱动器通道磁盘控制器磁盘控制器6.7数据一致性控制

当我们发现某种商品的进价有错时，除须修改流水帐外，还要对付费帐、分类帐及总帐等一系列文件修改，方能保证数据的一致性。但如果在修改进行到中途时，系统突然发生故障，就会造成各个帐目中该数据的不一致性，进而使多个帐目不一致。

为了保证在不同文件中存储的同一个数据相一致，在现代操作系统乃至数据库系统中，都配置了能保证数据一致性的软件，以及相应的支持硬件。硬件支持主要是配置一个高度可靠的存储器系统，或称为稳定存储器。用磁盘双工方式来实现稳定存储器6.7.1事务一.事务的定义事务是用于访问和修改各种数据项的一个程序单位。

只有对分布在不同位置的同一数据所进行的读和写操作全部完成时，才能再以托付操作（CommitOperation）来终止事务。只要有一个读、写操作或修改操作失败，便须执行夭折操作（AbortOperation）。

为使夭折的事务不会引起数据的不一致性，须将该事务内刚被修改的数据项恢复成原来的情况，使系统中各数据项与该事务未执行时的数据项内容完全相同。

一个事务在对一批数据执行修改操作时，要么全部完成，并用修改后的数据去代替原来的数据，要么一个也不修改。二.事务记录

为了实现上述的原子修改，通常须借助于称为事务记录的数据结构来实现，这些数据结构被放在稳定存储器中，用来记录在事务运行时数据项修改的全部信息，故又称为运行记录。该记录中包含有下列字段：事务名数据项名旧值新值三.恢复算法

由于一组被事务Ti修改的数据以及它们被修改前和被修改后的值，都能在事务记录表中找到，因此，利用事务记录表，系统能处理任何故障而不致使故障造成非易失性存储器中的信息丢失。恢复算法可利用以下两个过程：1.undo〈Ti〉。2.redo〈Ti〉。

一类是其所包含的各类操作都已完成的事务：既包含了〈Ti开始〉记录，又包含了〈Ti托付

〉记录。利用redo〈Ti〉过程。如果系统发生故障，系统应对以前所发生的事务进行清理。通过查找事务记录表，可以把尚未清理的事务分为两类。

另一类是其所包含的各个操作并未全部完成的事务：在Log表中只有〈Ti开始〉记录而无〈Ti托付

〉记录。利用undo〈Ti〉过程。6.7.2检查点

系统中可能存在着许多并发执行的事务，一旦系统发生故障，在事务记录表中的记录，清理起来就非常费时。一.检查点（CheckPoint）的作用引入的目的是使对事务记录表中事务记录的清理工作经常化每隔一定时间便做一次下述工作：内存中的当前事务记录表中的所有记录内存中的所有已修改数据将事务记录表中的〈检查点〉记录

最后是每当出现一个〈检查点〉记录时，系统便执行上小节所介绍的恢复操作，利用redo和undo过程实现恢复功能。稳定存储器输出二.新的恢复算法

在引入检查点后，大大减少恢复处理的开销。因为在发生故障后，只需对最后一个检查点之后的事务记录进行处理。

恢复例程首先查找事务记录表，确定在最近检查点以前开始执行的最后的事务Ti。找到这样的事务以后，再返回去搜索事务记录表，便可找到第一个检查点记录，恢复例程便从该检查点开始，返回搜索各个事务的记录，并利用redo和undo过程对它们进行处理。

在事务Ti以后开始执行的事务表示为事务集T，则新的恢复操作要求是：对所有在T中的事务Tk，如果在事务记录中出现了〈Tk托付

〉记录，则执行redo〈Tk〉操作；反之，如果在事务记录表中并未出现〈Tk托付

〉记录，则执行undo〈Tk托付

〉操作。6.7.3并发控制

可能有多个用户在同时执行事务，由于事务具有原子性，这使各个事务的执行必然是按某种次序依次执行的，只有在一个事务执行完后，才允许另一事务执行，即各事务对数据项的修改是互斥的。人们把这种特性称为顺序性。把用于实现事务顺序性的技术称为并发控制。一.利用互斥锁实现“顺序性”

设置一种用于实现互斥的锁，简称为互斥锁（ExclusiveLock）。应为每一个共享对象设置一把互斥锁。当一事务Ti要去访问某对象时，应先获得该对象的互斥锁。二.利用互斥锁和共享锁实现顺序性

利用互斥锁实现顺序性的方法简单易行，但效率不高。因为一个共享文件虽然只允许一个事务去写，但却允许多个事务同时去读；而在利用互斥锁来锁住文件后，则只允许一个事务去读。——引入“共享锁”共享锁和互斥锁的主要区别：

互斥锁仅允许一个事务对相应对象执行读或写操作，而共享锁则允许多个事务对相应对象执行读操作，不允许其中任何一个事务对对象执行写操作。

如果事务Ti要对Q执行读操作，只需去获得对象Q的共享锁。如果对象Q已被互斥锁锁住，则Ti必须等待；否则，便