文件系统基础
文件是以计算机硬盘为载体的存储在计算机上的信息的集合,在系统运行时,计算机以进程为资源分配的基本单位,而在用户进行的输入输出中,以文件为基本单位。操作系统中的文件系统实现对文件的维护管理。文件的结构:
- 数据项:数据项是文件系统中最低级的数据组织形式,有两种类型。基本数据项用于描述一个对象的某种属性的一个值,是数据中可命名的最小逻辑数据单位,即原子数据。组合数据项由多个基本数据项组成。
- 记录:记录是一组相关的数据项的集合,用于描述一个对象在某方面的属性。
- 文件:文件是指由创建者所定义的一组相关信息的集合,逻辑上可分为有结构文件和无结构文件两种。
文件控制块和索引结点
文件的属性(文件元数据):
- 文件名:同一目录下不允许有重名文件。
- 标识符:一个系统内的各文件标识符唯一,对用户来说毫无可读性。只是操作系统用于区分各个文件的一种内部名称。
- 类型:指明文件的类型。
- 位置:文件存放的路径(让用户使用)、在外存中的地址(操作系统使用,对用户不可见)。
- 大小:指明文件大小。
- 保护信息:对文件进行保护的访问控制信息。
- 时间、日期和用户标识符:创建时间、上次修改时间、文件所有者信息。
操作系统通过文件控制块(FCB)来维护文件元数据。
文件控制块(FCB):文件控制块是用来存放控制文件需要的各种信息的数据结构,以实现“按名存取”。FCB的有序集合称为文件目录,一个FCB就是一个文件目录项。FCB主要包含以下信息:
- 基本信息,如文件名、文件的物理位置、文件的逻辑结构、文件的物理结构等。
- 存取控制信息,包括文件主的存取权限、核准用户的存取权限以及一般用户的存取权限。
- 使用信息,如文件建立时间、上次修改时间等。
一个文件目录也被视为一个文件,称为目录文件。
对
- 搜索:当用户要使用一个文件时,系统要根据文件名搜索目录,找到该文件对应的目录项。
- 创建文件:创建一个新文件时,系统将分配一个
并在其所属的目录中添加一个目录项。 - 删除文件:当删除一个文件时,需要在目录中删除相应的目录项。
- 显示目录:用户可以请求显示目录的内容,如显示该目录中的所有文件及相应属性。
- 修改目录:某些文件属性保存在目录中,因此这些属性变化时需要修改相应的目录项(如:文件重命名)。
索引结点(FCB的改进):在查找各级目录的过程中只需要用到“文件名”这个信息,只有文件名匹配时,才需要读出文件的其他信息。因此有些系统采用了文件名和文件描述信息分开的方法,文件描述信息单独形成一个称为索引结点的数据结构,简称
当找到文件名对应的目录项时,才需要将索引结点调入内存,索引结点中记录了文件的各种信息,包括文件在外存中的存放位置,根据“存放位置”即可找到文件。存放在外存中的索引结点称为“磁盘索引结点”,当索引结点放入内存后称为“内存索引结点”。相比之下内存索引结点中需要增加一些信息,比如:文件是否被修改、此时有几个进程正在访问该文件等。
磁盘索引结点包括以下内容:
- 文件主标识符:拥有该文件的个人或小组的标识符。
- 文件类型:普通文件、目录文件或特别文件。
- 文件存取权限:各类用户对该文件的存取权限。
- 文件物理地址:每个索引结点中含有
个地址项,它们以直接或间接方式给出数据文件所在盘块的编号。 - 文件长度:以字节为单位。
- 文件链接计数:所有指向该文件的文件名的指针计数。
- 文件存取时间:本文件最近被进程存取的时间、最近被修改的时间,及索引节点最近被修改的时间。
内存索引结点除了磁盘索引结点所包含的内容外,还拥有:
- 索引结点编号:用于标识内存索引节点。
- 状态:指示
结点是否上锁或被修改。 - 访问计数:每当有进程访问此节点时,计数加一,访问结束减一。
- 逻辑设备号:文件所属文件系统的逻辑设备号。
- 链接指针:设置分别指向空闲链表和散列队列的指针。
文件的操作
文件的基本操作:
创建文件:“
系统调用”,有两个必要的步骤:第一步,在文件系统中为文件找到空间;第二步,在目录中为新文件创建对应的目录项,目录项中记录文件名称、在文件系统中的位置及其他可能的信息。该系统调用需要几个主要参数:所需的外存空间大小、文件存放路径、文件名。 删除文件:"
系统调用",根据文件存放路径找到对应的目录文件,从目录中找到文件名对应的目录项,然后回收该文件所占用的磁盘块,将文件数据从外存中删除,最后从目录表中删除文件对应的目录项。该系统调用需要几个主要参数:文件存放路径、文件名。 读文件:"
系统调用",指明文件名称和要读入文件块的内存位置。需要搜索目录以找到相关目录项,系统维护一个读位置的指针。每当发生读操作时,更新读指针。将文件数据从外存读入内存。该系统调用需要几个主要参数:文件在打开文件表中的编号(文件描述符)、要读入的数据大小(传送的字节数)、读入的数据放在内存的位置( 缓冲区首址)。 写文件:"
系统调用",指明文件名称和要写入文件的内存。对于给定文件名称,系统搜索目录以查找文件位置。系统维护一个写位置的指针。每当发生写操作时,更新写指针。将文件数据从内存写回外存。 一个进程通常只对一个文件读或写,因此当前操作位置可作为每个进程当前文件位置的指针。由于读/写操作都使用同一指针,因此节省了空间,降低了系统复杂度。
重新定位文件(文件定位):搜索目录以找到适当的条目,并将当前文件位置指针重新定位到给定值。重新定位文件不涉及读、写文件。
截断文件:允许文件所有属性不变,并删除文件内容,即将其长度设为
并释放其空间。
打开/关闭文件:"
在首次使用文件时,使用系统调用
当文件不再使用时,进程可以关闭它,操作系统从该进程的打开文件表中删除这一条目,回收分配给该文件的内存空间等资源,将系统打开文件表中该文件的打开计数器减一,若计数等于零,则删除对应表项。
文件名不必是打开文件表的一部分,因为一旦完成对FCB在磁盘上的定位,系统就不再使用文件名。对于访问打开文件表的索引,UNIX称之为文件描述符,而Windows称之为文件句柄。因此,只要文件未被关闭,所有文件操作就通过打开文件表来进行。
每个打开文件都有如下关联信息:
- 文件指针:系统跟踪上次的读写位置作为当前文件位置的指针,这种指针对打开文件的某个进程来说是唯一的,因此必须与磁盘文件属性分开保存。
- 文件打开计数:多个进程可能打开同一个文件,用文件打开计数器记录多少进程打开了该文件。每个关闭操作使计数递减,当打开计数器为
时,表示该文件不再被使用,系统将回收分配给该文件的内存空间等资源。若文件被修改过,则将文件写回外存,并将系统打开文件表中的相应条目删除,最后释放文件的文件控制块( )。 - 文件磁盘位置:该信息保存在内存中,以免为每个操作都从磁盘中读取。
- 访问权限:每个进程打开文件都需要有一个访问模式。该信息保存在进程的打开文件表中,以便操作系统能够允许或拒绝之后的
操作。
整个系统只有一张系统的打开文件表,记录全部进程打开的文件。每个进程有自己的打开文件表,记录自己打开的文件,进程的打开文件表有一个“系统表索引号”,指向系统的打开文件表中这个文件对应的条目。
文件保护
口令和加密是为了防止用户文件被他人存取或窃取,而访问控制则用于控制用户对文件的访问方式。
口令保护:为文件设置一个“口令”,用户请求访问该文件时必须提供“口令”。口令一般存放在文件对应的
或索引结点中。用户访问文件前需要先输入“口令”,操作系统会将用户提供的口令与 中存储的口令进行对比,如果正确,则允许该用户访问文件。 优点:保存口令的空间开销不多,验证口令的时间开销也很小。
缺点:口令直接存放在系统内部,不够安全。
加密保护:使用某个“密码”对文件进行加密,在访问文件时需要提供正确的“密码”才能对文件进行正确的解密。
优点:保密性强,不需要在系统中存储“密码”。
缺点:编码/译码,或者说加密/解密要花费一定时间。
访问控制:访问控制机制由系统实现,对一个文件的访问由用户访问权限和文件属性共同限制。在每个文件的
(或索引结点)中增加一个访问控制列表( ),该表中记录了各个用户名及其所允许的访问类型: - 读:从文件中读数据;
- 写:向文件中写数据;
- 执行:将文件装入内存并执行;
- 添加:将新信息添加到文件结尾部分;
- 删除:删除文件,释放空间;
- 列表清单:列出文件名和文件属性;
有的计算机可能会有很多个用户,访问控制列表可能会很太,可以用精简的访问列表解决这个问题。精简的访问列表采用拥有者(创建文件的用户)、组(一组需要共享文件且具有类似访问的用户)和其他(系统内的所有其他用户)三种用户类型。以“组”为单位,标记各“组”用户可以对文件执行哪些操作。当某用户想要访问文件时,系统会检查该用户所属的分组是否有相应的访问权限。若想要让某个用户能够读取文件,只需要把该用户放入相应分组即可。
若文件控制块中用二进制位串表示文件权限,描述文件权限的位数至少为:用户类别
访问权限。
现代操作系统常用的文件保护方法是,将访问控制列表与用户、组和其他成员访问控制方案一起组合使用。
对于多级目录结构而言,不仅需要保护单个文件,而且需要保护子目录内的文件,即需要提供目录保护机制。
文件的逻辑结构
文件的“逻辑结构”是从用户观点出发看到的文件的组织形式。而文件的“物理结构”(文件的存储结构)是从实现观点出发看到的文件在外存上的存储组织形式。文件的逻辑结构与存储介质特性无关,但文件的物理结构与存储介质的特性有很大关系。按照逻辑结构,文件可划分为:
无结构文件(流式文件):文件内部的数据就是一系列二进制流或字符流组成,如
文件。无结构文件是最简单的文件组织形式,它将数据按顺序组织成记录并积累、保存,是有序相关信息项的集合,以字节为单位。 优点:管理简单,用户方便操作。
缺点:只能使用穷举搜索方式访问记录。
有结构文件(记录式文件):由一组相似的记录组成,每条记录由若干个数据项组成,如数据库表文件。一般来说,每条记录有一个数据项可作为关键字。根据各条记录的长度(占用的存储空间)是否相等,又可分为定长记录和可变长记录两种。按记录的组织形式可分为:
顺序文件:文件中的记录一个接一个地顺序排列(逻辑上),记录可以是定长的或可变长的。各个记录在物理上可以顺序存储或链式存储。
顺序存储:逻辑上相邻的记录物理上也相邻;
可变长记录:无法实现随机存取,每次只能从第一个记录开始依次往后查找;
定长记录:可实现随机存取。记录长度为
,则第 个记录存放的相对位置是 。有两种结构: 串结构,记录之间的顺序与关键字无关,通常按照记录存入的时间决定记录的顺序;
顺序结构,记录之间的顺序按关键字顺序排列。可实现快速检索(根据关键字快速找到对应记录)。考试一般默认顺序文件为这种结构。
优点:大量读写记录时,顺序文件的效率最高;只有顺序文件才能存储在磁带上。
缺点:对删除或增加单条记录的操作比较困难。
链式存储:逻辑上相邻的记录物理上不一定相邻。无论是定长/可变长记录,都无法实现随机存取。
索引文件:索引文件由逻辑文件和索引表组成。建立一张索引表以加快文件检索速度,每条记录对应一个索引项(索引号,记录的长度,逻辑文件中的起始位置)。索引表本身是定长记录的顺序文件。因此可以快速找到第
个记录对应的索引项。而文件中的记录在物理上可以离散的存放。可以用不同的数据项建立多个索引表。 可将关键字作为索引号内容,若按关键字顺序排列,则还可以支持按照关键字折半查找。每当要增加/删除一个记录时,需要对索引表进行修改。由于索引文件有很快的检索速度,因此主要用于对信息处理的及时性要求比较高的场合。
优点:通过索引可以极大的提高访问速度。
缺点:每个记录对应一个索引表项,因此索引表可能会很大。
索引顺序文件:将顺序文件中的所有记录分为若干组,一组记录对应一个索引表项,为顺序文件建立一张索引表,在索引表中为每组中的第一条记录建立一个索引项(关键字,逻辑地址),其中含有该记录的关键字值和指向该记录的指针。索引顺序文件的索引项也不需要按关键字顺序排列,这样可以极大地方便新表项的插入。
如果记录数很多,为了进一步提高检索效率,可以为顺序文件建立多级索引表。
直接文件或散列文件:给定记录的键值或通过散列函数转换的键值直接决定记录的物理地址。这种映射结构不同于顺序文件或索引文件,没有顺序的特性。散列文件有很高的存取速度,但是会引起冲突,即不同的关键字的散列函数值相同。
文件的物理结构
与内存一样,外存也是由一个个存储单元组成的,每个存储单元可以存储一定量的数据。每个存储单元对应一个物理地址。操作系统以“块”为单位为文件分配存储空间,因此即使一个文件大小只有
文件分配对应于文件的物理结构,是指如何为文件分配磁盘块。常用的磁盘空间分配方法有三种:连续分配、链接分配和索引分配。
连续分配:文件目录中记录存放的起始块号和长度(总共占用几个块)。连续分配方式要求每个文件在磁盘上占有一组连续的块。
物理块号
优点:可以直接算出逻辑块号对应的物理块号,因此连续分配支持顺序访问和直接访间(即随机访问);作业访问磁盘时需要的寻道数和寻道时间最小,连续分配的文件在顺序访问时速度最快。
缺点:物理上采用连续分配的文件不方便拓展;存储空间利用率低,会产生外部碎片,可以用紧凑技术处理碎片,但是耗费的时间代价大。
链接分配:链接分配采取离散分配的方式,可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种:
隐式链接:目录中记录了文件存放的起始块号和结束块号。除文件的最后一个磁盘块之外,每个磁盘块中都会保存指向下一个盘块的指针,这些指针对用户是透明的。考试中未指明的链接分配,默认指的是隐式链接的链接分配。
优点:方便文件拓展,没有外部碎片,外存利用率高。
缺点:只支持顺序访问,不支持随机访问,查找效率低,指向下一个盘块的指针也需要耗费少量的存储空间。
显式连接:目录中只需记录文件的起始块号。把用于链接文件各物理块的指针显式地存放在一张表中,即文件分配表(
),一个磁盘仅设置一张 。开机时,将 读入内存,并常驻内存。 的各个表项(物理块号,下一块)在物理上连续存储,且每一个表项长度相同,因此“物理块号”字段可以是隐含的。因为 常驻内存,所以逻辑块号转换成物理块号的过程不需要读磁盘操作。 不仅记录了文件中各个块的先后链接顺序,还标记了空闲的磁盘块,操作系统可以通过 对文件存储空间进行管理。 优点:支持顺序访问和随机访问,访问速度比隐式链接快。方便文件拓展,没有外部碎片。
缺点:
需要占用一定的存储空间。
索引分配:目录中需要记录文件的索引块是几号磁盘块。索引分配允许文件离散地分配在各个磁盘块中,系统会为每个文件建立一张索引表,索引表中(逻辑块号,物理块号)记录了文件的各个逻辑块对应的物理块,可以用固定的长度表示物理块号,因此索引表中的“逻辑块号”字段可以是隐含的。索引表存放的磁盘块称为索引块,文件数据存放的磁盘块称为数据块。
逻辑块号到物理块号的转变,操作系统首先找到该文件对应的目录项(
优点:支持顺序访问和随机访问;方便文件拓展,没有外部碎片。
缺点:索引表需要占用一定的存储空间。
当索引表项太多,一个索引块装不下的时候,有以下机制处理这个问题:
- 链接方案:将多个索引块链接起来存放。在前面的索引块中存放一个指向后一个索引块的指针。当索引块过多时,访问后面的逻辑块,需要顺序读入前面的索引块,效率低下。
- 多层索引:原理类似于多级页表,使前一层索引块指向后一层的索引块集合。若采用多层索引,则各层索引表大小不能超过一个磁盘块。采用
层索引结构,且顶级索引表未调入内存,则访问一个数据块只需要 次读磁盘操作。 - 混合索引:多种索引分配方式的结合。例如,一个文件的顶级索引表中,既包含直接地址索引(直接指向数据块),又包含一级间接索引(指向单层索引表)、还包含两级间接索引(指向两层索引表)。对于小文件,只需较少的读磁盘次数就可以访问目标数据块。
目录
目录本身就是一种有结构文件,由一条条记录组成。每条记录对应一个放在该目录下的文件。目录在用户所需要的文件名和文件之间提供一种映射(
FCB的有序集合称为文件目录,一个FCB就是一个文件目录项。与文件管理系统和文件集合相关联的是文件目录,它包含有关文件的属性、位置和所有权等。
目录管理的基本要求:从用户的角度看,目录在用户(应用程序)所需要的文件名和文件之间提供一种映射,所以目录管理要实现“按名存取";目录存取的效率直接影响到系统的性能,所以要提高对目录的检索速度;在多用户系统中,应允许多个用户共享一个文件,因此目录还需要提供用于控制访问文件的信息。此外,应允许不同用户对不同文件采用相同的名字,以便于用户按自己的习惯给文件命名,目录管理通过树形结构来解决和实现。
目录结构
单级目录结构:整个系统中只建立一张目录表,每个文件占一个目录项。单级目录实现了“按名存取”,但是不允许文件重名。在建立一个新文件时,必须先检索所有目录项以确保没有重名的情况。(早期操作系统)
缺点:查找速度慢、文件不允许重名、不便于文件共享。对于多用户操作系统不适用。
两级目录结构:将文件目录分成主文件目录(
)和用户文件目录( )。主文件目录项记录用户名及相应用户文件目录所在的存储位置,用户文件目录项记录该用户文件的 信息。(早期多用户操作系统) 优点:允许不同用户的文件重名;在目录上实现访问限制。
缺点:缺乏灵活性;不能对文件分类。
多级目录结构(树形目录结构):用户(或用户进程)要访问某个文件时要用文件路径名标识文件,文件路径名是个字符串。各级目录之间用“/”隔开。从根目录出发的路径称为绝对路径。系统根据绝对路径一层一层地找到下一级目录。当层次较多时,每次从根目录查询会浪费时间,于是加入了当前目录(工作目录),进程对各文件的访问都是相对于当前目录进行的。当用户想要访问某个文件时,可以使用从当前目录出发的“相对路径”。
优点:很方便地对文件进行分类;层次结构清晰;有效地进行文件的管理和保护。
缺点:不便于实现文件的共享;查找文件时需要按照路径名逐级访问中间节点,增加了磁盘访问次数。
无环图目录结构:在树形目录结构的基础上,增加一些指向同一节点的有向边,使整个目录成为一个有向无环图。目的是为了实现多个用户间的文件共享。
可以用不同的文件名指向同一个文件,甚至可以指向同一个目录(共享同一目录下的所有内容)。需要为每个共享结点设置一个共享计数器,用于记录此时有多少个地方在共享该结点。用户提出删除结点的请求时,只是删除该用户的
并使共享计数器减 ,并不会直接删除共享结点。只有共享计数器减为 时,才删除结点。 共享文件不同于复制文件。在共享文件中,由于各用户指向的是同一个文件,因此只要其中一个用户修改了文件数据,那么所有用户都可以看到文件数据的变化。
目录的操作
系统调用,创建目录:创建一个新目录文件,为之分配磁盘空间,并在其父目录中创建一个指向该目录的 。 任何一个目录被创建后,都会存在两个默认的
:一个是" "指的是当前目录,另一个是" "指的是父目录。 系统调用,删除目录和指向该目录的 :只有空目录可以删除 系统调用,打开目录:和打开普通文件一样,只是将指向该目录文件的 读入内存而已,并不是把目录文件的数据全部读入内存 系统调用,读目录:必须在打开目录后才能读目录,返回目录文件中的下一个目录项 系统调用,重命名:给目录重命名,本质上是修改指向该目录文件的 系统调用,建立硬链接:将指定的文件与目录建立硬链接,该系统调用导致指定目录中多了一个 ,而指定文件的 共享计数器 系统调用,解除硬链接,指定文件的 共享计数器 ,若计数器 ,则删除文件数据
目录实现(X)
考纲已删
目录也是一种文件。在读文件前,必须先打开文件。打开文件时,操作系统利用路径名找到相应目录项,目录项中提供了查找文件磁盘块所需要的信息。目录实现的基本方法有两种:
- 线性列表:实现线性查找,最简单的实现方法是使用存储文件名和数据块指针的线性表。采用链表结构可以减少删除文件的时间,其优点在于实现简单,但是比较费时。
- 哈希表:根据文件名得到一个值,并返回一个指向线性列表中元素的指针。优点在于查找迅速,插入和删除简单。但是要采取一些措施避免冲突,最大的困难是哈希表长度固定以及哈希函数对表长的依赖性。
文件共享
操作系统为用户提供文件共享功能,可以让多个用户共享地使用同一个文件,系统中只需要保留该文件的一个副本。硬链接和软链接都是文件系统中的静态共享方法,每个共享文件都有几个文件名,即每增加一条链接就增加一个文件名。这实质上是每个用户都使用自己的路径名去访问共享文件,当遍历整个文件系统时,将会多次遍历到该共享文件。
多个用户共享同一个文件,意味着系统中只有“一份”文件数据。并且只要某个用户修改了该文件的数据,其他用户也可以看到文件数据的变化。
如果是多个用户都“复制”了同一个文件,那么系统中会有“好几份”文件数据。其中一个用户修改了自己的那份文件数据,对其他用户的文件数据并没有影响。
文件系统中还有一种共享:动态共享,即两个进程同时对同一个文件进行操作。
基于索引结点的共享方式(硬链接)
在树形结构的目录中,但有多个用户要共享一个子目录或文件时,将共享文件或子目录链接到多个用户的目录中(多个指针指向一个索引结点)。索引结点中设置一个链接计数变量
若某个用户决定“删除”该文件,则只是要把用户目录中与该文件对应的目录项删除,且索引结点的
基于符号链的共享方式(软链接)
为了使用户
新的
只有文件拥有者才拥有指向其索引结点的指针,而共享该文件的其他用户只有该文件的路径名。当文件的拥有者把共享文件删除后,其他用户通过符号链去访问时,会出现访问失败,删除符号链。
因为用软链接的方式访问共享文件时要查询多级目录,会有多次磁盘
优点:网络共享只需提供该文件所在机器的网络地址及该机器中的文件路径。
文件系统
文件系统结构
用户调用接口:文件系统为用户提供与文件及目录有关的调用,此层由若干程序模块组成,每个模块对应一条系统调用,用户发出系统调用时,控制即转入相应的模块。主要为文件的基本操作中的内容。
文件目录系统:主要功能是管理文件目录,任务有:管理活跃文件目录表、管理读写状态信息表、管理用户进程的打开文件表、管理与组织存储设备上的文件目录结构、调用下一级存取控制模块。主要为文件目录中的内容。
存取控制验证模块:由该级软件完成文件保护,它把用户的访问要求与
逻辑文件系统与文件信息缓冲区:根据文件的逻辑结构将用户要读写的逻辑记录转换成文件逻辑结构内的相应块号。主要为文件的逻辑结构中的内容。
物理文件系统:把逻辑记录所在的相对块号转换成实际的物理地址。主要为文件的物理结构中的内容。
辅助分配模块:管理辅存空间,负责分配和回收辅存空间。主要为文件存储空间管理中的内容。
设备管理程序模块:分配设备、分配设备读写用缓冲区、磁盘调度、启动设备、处理设备中断、释放设备读写缓冲区、释放设备等。主要为磁盘管理中的内容。
文件系统布局
文件系统在磁盘中的结构:
文件系统存放在磁盘上,多数磁盘划分为一个或多个分区,每个分区中有一个独立的文件系统。文件系统可能包括如下信息:启动存储在那里的操作系统的方式、总的块数、空闲块的数量和位置、目录结构以及各个具体文件等。
主引导记录MBR,位于磁盘的0号扇区,用来引导计算机,MBR后面是分区表,该表给出每个分区的起始和结束地址。表中的一个分区被标记为活动分区,当计算机启动时,BIOS读入并执行MBR。MBR做的第一件事是确定活动分区,读入它的第一块,即引导块。
引导块,MBR执行引导块中的程序后,该程序负责启动该分区中的操作系统。为统一起见,每个分区都从一个引导块开始,即使它不含有一个可启动的操作系统,也不排除以后会在该分区安装一个操作系统。Windows系统称之为分区引导扇区。除了从引导块开始,磁盘分区的布局是随着文件系统的不同而变化的。
超级块,包含文件系统的所有关键信息,在计算机启动时,或者在该文件系统首次使用时,超级块会被载入内存。超级块中的典型信息包括分区的块的数量、块的大小、空闲块的数量和指针、空闲的FCB数量和FCB指针等。
文件系统中空闲块的信息,可以使用位示图或指针链接的形式给出。后面也许跟的是一组i结点,每个文件对应一个结点,i结点说明了文件的方方面面。接着可能是根目录,它存放文件系统目录树的根部。最后,磁盘的其他部分存放了其他所有的目录和文件。
文件系统在内存中的结构:
内存中的信息用于管理文件系统并通过缓存来提高性能。这些数据在安装文件系统时被加载,在文件系统操作期间被更新,在卸载时被丢弃。这些结构的类型可能包括:
- 内存中的安装表,包含每个已安装文件系统分区的有关信息。
- 内存中的目录结构的缓存包含最近访问目录的信息。对安装分区的目录,它可以包括一个指向分区表的指针。
- 整个系统的打开文件表,包含每个打开文件的FCB副本及其他信息。
- 每个进程的打开文件表,包含一个指向整个系统的打开文件表中的适当条目的指针,以及其他信息。
为了创建新的文件,应用程序调用逻辑文件系统。逻辑文件系统知道目录结构的格式,它将为文件分配一个新的FCB。然后,系统将相应的目录读入内存,使用新的文件名和FCB进行更新,并将它写回磁盘。
外存空闲空间管理
一个存储设备可以按整体用于文件系统,也可以细分。包含文件系统的分区通常称为卷。卷可以是磁盘的一部分,也可以是整个磁盘,还可以是多个磁盘组成RAID集。
一般来说,一个文件存储在一个文件卷中。在一个文件卷中,文件数据信息的空间(文件区)和存放文件控制信息
逻辑卷在提供文件服务前,必须由对应的文件程序进行初始化,划分好目录区和文件区,建立空闲空间管理表格及存放逻辑卷信息的超级块。
文件存储设备分成许多大小相同的物理块,并以块为单位交换信息,因此文件存储设备的管理实质上是对空闲块的组织和管理,包括空闲块的组织、分配与回收。
存储空间管理的方法有:
空闲表法:属于连续分配方式,与内存的动态分配方式类似,为每个文件分配一块连续的存储空间。系统为外存上的所有空闲区建立一张空闲盘块表,每个空闲区对应于一个空闲表项(表项序号,空闲区第一个盘块号,空闲盘块数),再将所有空闲区按其起始盘块号递增的次序排列。
回收时需要注意表项的合并问题。
空闲链表法:将所有空闲盘区拉成一条空闲链,根据构成链所用的基本元素的不同,分为两种:空闲盘块链和空闲盘区链。
空闲盘块链:以盘块为单位组成一条空闲链,空闲盘块中存储着下一个空闲盘块的指针。操作系统保存着链头、链尾指针。分配存储空间时,从链首开始分配;释放存储空间时,从将回收的盘块依次插入链尾。(适用于离散分配的物理结构)
优点:分配和回收简单。缺点:在为一个文件分配盘块时,可能要重复多次操作。
空闲盘区链:以盘区为单位组成一条空闲链,连续的空闲盘块组成一个空闲盘区,空闲盘区中的第一个盘块内记录了盘区的长度、下一个盘区的指针。离散分配、连续分配都适用。为一个文件分配多个盘块时效率更高。
分配盘区的方法与内存的动态分配方式类似。若没有合适的连续空闲块,也可以将不同盘区的盘块同时分配给一个文件,分配后可能要修改相应的链指针、盘区大小等数据。
若回收区和某个空闲盘区相邻,则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻,将回收区作为单独的一个空闲盘区挂到链尾。
位示图法:每个二进制位对应一个盘块。“
”代表盘块空闲,“ ”代表盘块已分配。位示图一般用连续的“字”来表示,如果一个字的字长是16位,字中的每一位对应一个盘块。因此可以用(字号,位号)对应一个盘块号。当然有的题目中也描述为(行号,列号)。(离散分配、连续分配都适用) 若文件需要
个块,分配步骤: - 顺序扫描位示图,找到
个相邻或不相邻的“ ”; - 根据字号、位号算出对应的盘块号,将相应盘块分配给文件:盘块号
每行的位数 行号 列号;(计算方法前提为行列号从 开始) - 将相应位设置为“
”。
回收步骤:
- 根据回收的盘块号计算出对应的字号=(盘块号-1)/每行的位数+1、位号=(盘块号-1)%每行的位数+1;(计算方法前提为行列号从
开始) - 将相应二进制位设为“
”。
做题时,注意题目条件中,盘块号、字号、位号到底是从
开始还是从 开始。 - 顺序扫描位示图,找到
成组链接法:空闲表法、空闲链表法不适用于大型文件系统,因为空闲表或空闲链表可能过大。
系统中采用了成组链接法对磁盘空闲块进行管理。 文件卷的目录区中专门用一个磁盘块作为“超级块”,当系统启动时需要将超级块读入内存。并且要保证内存与外存中的“超级块”数据一致。
超级块由空闲盘块数和空闲块号组成,每个超级块第一个空闲块号指向另一个超级块,其他空闲块号指向空闲块。空闲块号数量不超过该超级块的空闲盘块数,若已经没有下一组空闲块,则第一个空闲块号设为特殊值。一个超级块中空闲块号分组中,块号不需要连续。超级块相当于一个链头的作用,保存了指向下一个超级块的地址信息。
每个超级块第一个空闲块号指向的另一个超级块号同时也是一个空闲块,也可以用来分配出去,但是要修改超级块信息
分配步骤:
- 检测第一个分组的块数是否足够,足够的话就用第一个超级块中的空闲盘块分配,将分配出去的空闲盘块号删除并修改超级块的空闲盘块数。
- 如果第一个分组的空闲盘块号用完了,将下一个超级块分组信息复制到第一个分组中,然后删除下一个超级块分组。
- 如果第一个分组的块数不够,就按照步骤二依次向后分配。
回收步骤:
- 如果第一个分组没满,可以将回收的空闲块插入第一个分组中。
- 如果第一个分组满了,需要将超级块中的数据复制到新回收的块中,并修改超级块的内容,让新回收的块成为第一个分组。
虚拟文件系统(VFS)
虚拟文件系统(VFS)为用户程序提供了文件系统操作的统一接口,屏蔽了不同文件系统的差异和操作细节。用户程序可以通过VFS提供的统一调用函数来操作不同文件系统的文件,而无须考虑具体的文件系统和实际的存储介质。
为了实现VFS,Linux主要抽象了四种对象类型。每个VFS对象都存放在一个适当的数据结构中,其中包括对象的属性和指向对象方法(函数)表的指针。
- 超级块对象:表示一个已安装(或称挂载)的特定文件系统。
- 索引结点对象:表示一个特定的文件。
- 目录项对象:表示一个特定的目录项。
- 文件对象:表示一个与进程相关的已打开文件。
Linux将目录当作文件对象来处理,文件操作能同时应用于文件或目录。文件系统是由层次目录组成的,一个目录项可能包含文件名和其他目录名。目录项作为单独抽象的对象,是因为目录可以层层嵌套,以便于形成文件路径,而路径中的每一部分其实就是目录项。
- 超级块对象。超级块对象对应于磁盘上特定扇区的文件系统超级块,用于存储已安装文件系统的元信息,元信息中包含文件系统的基本属性信息,如文件系统类型、文件系统基本块的大小、文件系统所挂载的设备、操作方法(函数)指针等。其中操作方法(函数)指针指向该超级块的操作方法表,包含一系列可在超级块对象上调用的操作函数,主要有分配inode、销毁inode、读inode、写inode、文件同步等。
- 索引结点对象。文件系统处理文件所需要的所有信息,都放在一个称为索引结点的数据结构中,索引结点对文件是唯一的。只有当文件被访问时,才在内存中创建索引结点对象,每个索引结点对象都会复制磁盘索引结点包含的一些数据。该对象中有一个状态字段表示是否被修改,其值为“脏”时,说明对应的磁盘索引结点必须被更新。索引结点对象还提供许多操作接口,如创建新索引结点、创建硬链接、创建新目录等。
- 目录项对象。由于VFS经常执行切换到某个目录这种操作,为了提高效率,便引入了目录项的概念。目录项对象是一个路径的组成部分,它要么是目录名,要么是文件名。目录项对象包含指向关联索引结点的指针,还包含指向父目录和指向子目录的指针。不同于前面两个对象,目录项对象在磁盘上没有对应的数据结构,而是VFS在遍历路径的过程中,将它们逐个解析成目录项对象的。
- 文件对象。文件对象代表进程打开的一个文件。文件对象和物理文件的关系类似于进程和程序的关系。由于多个进程可以打开和操作同一文件,所以同一文件在内存中可能存在多个对应的文件对象,但对应的索引结点和目录项是唯一的。文件对象仅在进程观点上代表已经打开的文件,它反过来指向其索引结点。文件对象包含与该文件相关联的目录项对象,包含该文件的文件系统、文件指针等,还包含在该文件对象上调用的一系列操作函数。
VFS还有另一个重要作用,即提高系统性能。最近最常使用的目录项对象被放在目录项高速缓存的磁盘缓存中,以加速从文件路径名到最后一个路径分量的索引结点的转换过程。
对用户来说,不需要关心不同文件系统的具体实现细节,只需要对一个虚拟的文件操作界面进行操作。VFS对每个文件系统的所有细节进行抽象,使得不同的文件系统在系统中运行的其他进程看来都是相同的。严格来说,VFS并不是一种实际的文件系统,它只存在于内存中,不存在于任何外存空间中。VFS在系统启动时建立,在系统关闭时消亡。
虚拟文件系统的特点:
向上层用户进程提供统一标准的系统调用接口,屏蔽底层具体文件系统的实现差异。
要求下层的文件系统必须实现某些规定的函数功能,如: 。一个新的文件系统想要在某操作系统上被使用,就必须满足该操作系统 的要求。 每打开一个文件,
就在主存中新建一个 ,用统一的数据结构表示文件,无论该文件存储在哪个文件系统。 解决的问题:不同的文件系统,表示文件数据结构各不相同。打开文件后,其在内存中的表示就不同。
文件系统的目录项只有"文件名"和" 结点号" 文件系统的目录项有"文件名"、"文件类型"、"文件大小"、"起始块号"、等等
因此在虚拟文件系统中,每当我们使用
打开了一个文件后,虚拟文件系统就会给这个文件在主存中创建了一个虚拟结点 ,将这个文件的 的各种信息复制到 中, 的函数功能指针指向具体文件所属的文件系统提供的函数功能列表。 只存在于主存中,而 既会被调入主存,也会在外存中存储。
分区和安装
一个磁盘可以划分为多个分区,每个分区都可以用于创建单独的文件系统,每个分区还可以包含不同的操作系统。分区可以是原始的,没有文件系统,当没有合适的文件系统时,可以使用原始磁盘。
Linux启动后,首先载入MBR,随后MBR识别活动分区,并且加载活动分区中的引导程序。
分区的第一部分是引导块,里面存储着引导信息,它有自身的格式,因为在引导时系统并未加载文件系统代码,因此不能解释文件系统的格式。引导信息是一系列可以加载到内存中的连续块,加载到内存后从其第一条代码开始执行,引导程序便启动一个具体的操作系统。引导块之后是超级块,它存储文件系统的有关信息,包括文件系统的类型、i结点的数目、数据块的数目。随后是多个索引结点,它们是实现文件存储的关键,每个文件对应一个索引结点,索引结点中包含多个指针,指向属于该文件的各个数据块。最后是文件数据块。
如文件在使用前必须打开一样,文件系统在进程使用前必须先安装,也称挂载。
文件系统挂载(
- 在
中注册新挂载的文件系统。内存中的挂载表( )包含每个文件系统的相关信息,包括文件系统类型、容量大小等。 - 新挂载的文件系统,要向
提供一个函数地址列表 - 将新文件系统加到挂载点(
),也就是将新文件系统挂载在某个父目录下。
Windows系统维护一个扩展的两级目录结构,用驱动器字母表示设备和卷。卷具有常规树结构的目录,与驱动器号相关联,还含有指向已安装文件系统的指针。操作系统找到相应文件系统的指针,并且遍历该设备的目录结构,以查找指定的文件。新版本的Windows允许文件系统安装在目录树下的任意位置,就像UNIX一样。在启动时,Windows操作系统自动发现所有设备,并且安装所有找到的文件系统。
UNIX使用系统的根文件系统,由内核在引导阶段直接安装,其他文件系统要么由初始化脚本安装,要么由用户安装在己安装文件系统的目录下。作为一个目录树,每个文件系统都拥有自己的根目录。安装文件系统的这个目录称为安装点,安装就是将磁盘分区挂载到该安装点下,进入该目录就可以读取该分区的数据。已安装文件系统属于安装点目录的一个子文件系统。安装的实现是在目录inode的内存副本上加上一个标志,表示该目录是安装点。还有一个域指向安装表的条目,表示哪个设备安装在哪里,这个条目还包括该设备的文件系统超级块的一个指针。
我们可以这么理解:UNIX本身是一个固定的目录树,只要安装就有,但是如果不给它分配存储空间,就不能对它进行操作,所以首先要给根目录分配空间,这样才能操作这个目录树。