【王道】操作系统 知识点总结4——文件管理

阅读: 评论:0

【王道】操作系统 知识点总结4——文件管理

【王道】操作系统 知识点总结4——文件管理

4 文件管理

4.1 文件系统基础

4.1.1 文件的基本概念

  1. 定义

    文件是以计算机硬盘为载体的存储在计算机上的信息集合在用户进行的输入、输出中,以文件位基本单位

    文件管理系统是实现的文件的访问、修改和保存,对文件维护管理的系统。

  2. 文件的组成

    • 存储空间:用于存储数据
    • 标签:便于对数据的分类和索引
    • 访问权限:不同用户对数据有不同的访问权限
  3. 文件的结构

    • 数据项:是文件系统中最低级的数据组织形式,可分为以下两种类型:
      • 基本数据项:用于描述一个对象的某种属性的一个值,是数据中的最小逻辑单位。
      • 组合数据项:由多个基本数据项组成。
    • 记录:是一组相关的数据项的集合,用于描述一个对象在某方面的属性。
    • 文件:是指由创建者所定义的、具有文件名的一组相关元素的集合,分为有结构文件和无结构文件两种。
      • 有结构的文件中,文件由若干个相似的记录组成,如一个班的学生记录;
      • 无结构文件则被视为一个字符流,比如一个二进制文件或字符文件。

4.1.2 文件控制块和索引结点

  1. 文件的属性

    • 文件名:由创建文件的用户决定文件名,主要是为了方便用户找到文件,同一目录下不允许有重名文件
    • 标识符:一个系统内的各文件标识符唯一,对用户来说毫无可读性,因此标识符只是操作系统用于区分各个文件的一种内部名称。
    • 类型:指明文件的类型
    • 位置:文件存放的路径(让用户使用)、在外存中的地址(操作系统使用,对用户不可见)
    • 大小:指明文件大小
    • 保护信息:对文件进行保护的访问控制信息
    • 创建时间、最后一次修改时间和最后一次存取时间:文件创建、上次修改和上次访问的相关信息,用于保护和跟踪文件的使用。
  2. 文件控制块FCB

    文件控制块(FCB)是用来存放控制文件需要的各种信息的数据结构,以实现“按名存取"。

    操作系统通过文件控制块(FCB)来维护文件元数据。FCB的有序集合称为文件目录,一个FCB就是一个文件目录项。下图为一个典型的FCB。

    FCB包含以下信息:

    • 基本信息:如文件名、文件的物理位置、文件的逻辑结构、文件的物理结构等。
    • 存取控制信息:包括文件主的存取权限、核准用户的存取权限以及一般用户的存取权限。
    • 使用信息:如文件建立时间、上次修改时间等。

    一个文件目录也被视为一个文件,称为目录文件。

  3. 索引结点

    ​ 在检索目录时,只用到了文件名,因此有的系统采用文件名与文件描述分开的方法,使文件描述信息单独形成一个称为索引结点的数据结构,简称 i 结点(inode)

    ​ 在文件目录中的每个目录项仅由文件名和指向该文件所对应的i结点的指针构成

    假设一个FCB为64B,盘块大小是1KB,则每个盘块中可以存放16个FCB(FCB必须连续存放),若一个文件目录共有640个FCB,则查找文件平均需要启动磁盘20次。

    而在UNIX系统中,一个目录项仅占16B,其中14B是文件名,2B是 i 结点指针。在1KB的盘块中可存放64个目录项。这样,可使查找文件的平均启动磁盘次数减少到原来的1/4,大大节省了系统开销。

    • 磁盘索引结点

      它是指存放在磁盘上的索引结点。每个文件有一个唯一的磁盘索引结点,主要包括以下内容:

      • 文件主标识符,拥有该文件的个人或小组的标识符。

      • 文件类型,包括普通文件、目录文件或特别文件。

      • 文件存取权限,各类用户对该文件的存取权限。

      • 文件物理地址,每个索引结点中含有13个地址项,即iaddr(0)~iaddr(12),它们以直接或间接方式给出数据文件所在盘块的编号。

      • 文件长度,指以字节为单位的文件长度。

      • 文件链接计教,在本文件系统中所有指向该文件的文件名的指针计数。

      • 文件存取时间,本文件最近被进程存取的时间、最近被修改的时间及索引结点最近被修改的时间。

    • 内存索引结点

      它是指存放在内存中的索引结点。当文件被打开时,要将磁盘索引结点复制到内存的索引结点中,便于以后使用。在内存索引结点中增加了以下内容:

      • 索引结点编号,用于标识内存索引结点。
      • 状态,指示 i 结点是否上锁或被修改。
      • 访问计数,每当有一进程要访问此 i 结点时,计数加1;访问结束减1。
      • 逻辑设备号,文件所属文件系统的逻辑设备号。
      • 链接指针,设置分别指向空闲链表和散列队列的指针。

4.1.3 文件的操作

  1. 文件的基本操作

    ​ 文件属于抽象数据类型。为了正确地定义文件,需要考虑可以对文件执行的操作。操作系统提供系统调用,它对文件进行创建、写、读、重定位、删除和截断等操作。

    • 创建文件(create系统调用)

      • 为新文件分配必要的外存空间;
      • 在目录 中为之创建一个目录项,目录项记录了新文件名、在外存中的地址及其他可能的信息。
    • 删除文件(delete系统调用)

      • 先从目录中检索指定文件名的目录项
      • 然后释放该文件所占的存储空间,以便可被其他文件重复使用,并删除目录条目。
    • 读文件(read系统调用)

      • 对于给定文件名,搜索目录以查找文件位置。
      • 系统维护一个读位置的指针。
      • 每当发生读操作时,更新读指针。
    • 写文件(write系统调用)

      • 对于给定文件名,搜索目录以查找文件位置。
      • 系统必须为该文件维护一个写位置的指针。
      • 每当发生写操作时,便更新写指针。

      一个进程通常只对一个文件读或写,因此当前操作位置可作为每个进程当前文件位置的指针。

      由于读和写操作都使用同一指针,因此节省了空间,也降低了系统复杂度。

    • 重新定位文件

      也称文件定位。搜索目录以找到适当的条目,并将当前文件位置指针重新定位到给定值。

      重新定位文件不涉及读、写文件。

    • 截断文件

      允许文件所有属性不变,并删除文件内容,将其长度置为0并释放其空间。

    这6个基本操作可以组合起来执行其他文件操作。例如,一个文件的复制,可以创建新文件、从旧文件读出并写入新文件。

  2. 文件的打开与关闭

    • 打开文件(open系统调用)

      • 过程:调用open根据文件名搜索目录,将指明文件的属性(包括该文件在外存上的物理位置),从外存复制到内存打开文件表的一个表目中,并将该表目的编号(也称索引)返回给用户

      打开文件时并不会把文件数据直接读入内存。“索引号”也称“文件描述符”

      打开文件之后,对文件的操作不再需要每次都查询目录,可以根据内存中的打开文件表进行操作。

      如上图所示,在多个不同进程同时打开文件的操作系统中,通常采用两级表:整个系统表和每个进程表。

      • 整个系统的打开文件表包含FCB的副本及其他信息。
      • 每个进程的打开文件表根据它打开的所有文件,包含指向系统表中适当条目的指针。

      一旦有进程打开了一个文件,系统表就包含该文件的条目。当另一个进程执行调用open时,只不过是在其文件打开表中增加一个条目,并指向系统表的相应条目

    • 关闭文件(close系统调用)

      • 1.将进程的打开文件表相应表项删除
      • 2.回收分配给该文件的内存空间等资源
      • 3.系统打开文件表的打开计数器count减1,若count=0,则删除对应表项。

    系统打开文件表为每个文件关联一个打开计数器(OpenCount),以记录多少进程打开了该文件。

    文件名不必是打开文件表的一部分,因为一且完成对FCB在磁盘上的定位,系统就不再使用文件名。对于访问打开文件表的索引,UNIX称之为文件描述符,而Windows称之为文件句柄
    因此,只要文件未被关闭,所有文件操作就通过打开文件表来进行。

    • 打开文件信息
      • 文件指针。系统跟踪上次的读写位置作为当前文件位置的指针,这种指针对打开文件的某个进程来说是唯一的,因此必须与磁盘文件属性分开保存。
      • 文件打开计数。计数器跟踪当前文件打开和关闭的数量。因为多个进程可能打开同一个文件,所以系统在删除打开文件条目之前,必须等待最后一个进程关闭文件。
      • 文件磁盘位置。大多数文件操作要求系统修改文件数据。查找磁盘上的文件所需的信息保存在内存中,以便系统不必为每个操作都从磁盘上读取该信息。
      • 访问权限。每个进程打开文件都需要有一个访问模式(创建、只读、读写、添加等)。该信息保存在进程的打开文件表中,以便操作系统能够允许或拒绝后续的I/O请求。

4.1.4 文件保护

​ 文件保护通过口令保护、加密保护和访问控制等方式实现。其中,口令和加密是为了防止用户文件被他人存取或窃取,而访问控制则用于控制用户对文件的访问方式。

  1. 口令保护

    为文件设置一个“口令”,用户想要访问文件时需要提供口令,由系统验证口令是否正确。

    实现开销小,但“口令”一般存放在FCB或索引结点中(也就是存放在系统中)因此不太安全

  2. 加密保护

    用一个“密码“对文件加密,用户想要访问文件时,需要提供相同的“密码“才能正确的解密

    安全性高,但加密解密需要耗费一定的时间(Eg:异或加密)

  3. 访问控制

    • 访问类型

      对文件的保护可从限制对文件的访问类型中出发。可加以控制的访问类型主要有以下几种。

      • 读。从文件中读。
      • 写。向文件中写。
      • 执行。将文件装入内存并执行。
      • 添加。将新信息添加到文件结尾部分。
      • 删除。删除文件,释放空间。
      • 列表清单。列出文件名和文件属性。

      此外还可以对文件的重命名、复制、编辑等加以控制。这些高层的功能可以通过系统程序调用低层系统调用来实现。保护可以只在低层提供。

    • 访问控制

      ​ 解决访问控制最常用的方法是根据用户身份进行控制。而实现基于身份访问的最为普通的方法是,为每个文件和目录增加一个访问控制列表(Access-Control List,ACL),以规定每个用户名及其所允许的访问类型。

      • 优点:可以使用复杂的访问方法,
      • 缺点:长度无法预计并且可能导致复杂的空间管理,

      使用精简的访问列表可以解决这个问题,精简的访问列表采用拥有者、组和其他三种用户类型。

      • 拥有者。创建文件的用户。
      • 组。一组需要共享文件且具有类似访问的用户。
      • 其他。系统内的所有其他用户。

      文件主在创建文件时,说明创建者用户名及所在的组名,系统在创建文件时也将文件主的名字、所属组名列在该文件的FCB中。用户访问该文件时,

      • 若用户是文件主,按照文件主所拥有的权限访问文件;
      • 用户和文件主在同一个用户组,则按照同组权限访问,
      • 否则只能按其他用户权限访问。

4.1.5 文件的逻辑结构

​ 文件的逻辑结构从用户观点出发看到的文件的组织形式。文件的物理结构(存储结构)是从实现观点出发看到的文件在外存上的存储组织形式。

​ 文件的逻辑结构与存储介质特性无关,它实际上是指在文件的内部,数据逻辑上是如何组织起来的

  1. 无结构文件(流式文件)

    无结构文件将数据按顺序组织成记录并积累、保存,它是有序相关信息项的集合,以字节(Byte)为单位

    • 只能通过穷举搜索的方式访问记录。

    • 其管理简单,用户操作方便。

    • 对基本信息单位操作不多的文件适于采用字符流的无结构文件。例如源程序文件、目标代码文件等。

  2. 有结构文件(记录式文件)

    • 顺序文件

      文件中的记录一个接一个地顺序排列(逻辑上),记录可以是定长的或可变长的。

      各个记录在物理上可以顺序存储或链式存储。

      • 链式存储:无论是定长何变长记录,都无法实现随机存取,每次只能从第一个记录开始依次往后查找

      • 顺序存储:

        可实现随机存取,记录长度为L,则第ⅰ个记录存放的相对位置是i*L

        若采用串结构,记录之间的顺序与关键字无关,无法快速找到某关键字对应的记录

        若采用顺序结构,可以快速找到某关键字对应的记录(如折半查找)

      定长记录的顺序文件,若物理上采用顺序存储,则可实现随机存取:若能再保证记录的顺序结构,则可实现快速检索(即根据关键字快速找到对应记录)

      优点:读写一大批文件时,效率最高。适用于顺序存储设备(磁带)

      缺点:不方便增加、删除记录

    • 索引文件

      • 索引表:高效查询变长记录文件。索引表本身是定长记录的顺序文件,因此可以快速找到第ⅰ个记录对应的索引项。

      • 方式:可将关键字作为索引号内容,若按关键字顺序排列,则还可以支持按照关键字折半查找

        每当要增加/删除一个记录时,需要对索引表进行修改。由于索引文件有很快的检索速度,因此主要用于对信息处理的及时性要求比较高的场合。

    • 索引顺序文件

      索引顺序文件是索引文件和顺序文件思想的结合。索引顺序文件中,同样会为文件建立一张索引表,但不同的是:并不是每个记录对应一个索引表项,而是一组记录对应一个索引表项

      • 将记录分组,每组对应一个素引表项
      • 检素记录时先顺序查索引表,找到分组,再顺序查找分组
      • 当记录过多时,可建立多级素引表

      如上图所示,主文件名包含姓名和其他数据项。

      • 姓名为关键字,索引表中为每组的第一条记录(不是每条记录)的关键字值,用指针指向主文件中该记录的起始位置。
      • 索引表只包含关键字和指针两个数据项,所有姓名关键字递增排列。
      • 主文件中记录分组排列,同一个组中的关键字可以无序,但组与组之间的关键字必须有序。
      • 查找一条记录时,首先通过索引表找到其所在的组,然后在该组中使用顺序查找,就能很快地找到记录。
    • 直接文件或散列文件(Hash File)

      ​ 给定记录的键值通过散列函数转换的键值直接决定记录的物理地址。这种映射结构不同于顺序文件或索引文件,没有顺序的特性。

      ​ 散列文件有很高的存取速度,但是会引起冲突,即不同关键字的散列函数值相同。

4.1.6 文件的物理结构

​ 文件的物理结构就是研究文件的实现,即文件数据在物理存储设备上是如何分布和组织的。

文件分配对应于文件的物理结构,是指如何为文件分配磁盘块。常用的磁盘空间分配方法有三种:连续分配、链接分配和索引分配。

  1. 连续分配

    连续分配方法要求每个文件在磁盘上占有一组连续的块。磁盘地址定义了磁盘上的一个线性排序,这种排序使作业访问磁盘时需要的寻道数和寻道时间最小。

    • 物理块号=起始块号+逻辑块号
    • 优点:支持顺序访问和直接访问(即随机访问);连续分配的文件在顺序访问时速度最快
    • 缺点:不方便文件拓展、存储空间利用率低、会产生磁盘碎片(外部碎片)。
      • ①文件长度不宜动态增加,因为一个文件末尾后的盘块可能已分配给其他文件,一旦需要增加,就需要大量移动盘块。
      • ②为保持文件的有序性,删除和插入记录时,需要对相邻的记录做物理上的移动,还会动态改变文件的长度。
      • ③反复增删文件后会产生外部碎片(与内存管理分配方式中的碎片相似)。
      • ④很难确定一个文件需要的空间大小,因而只适用于长度固定的文件。
    • 访存次数:访问第n条记录需访问磁盘1次
  2. 链接分配

    链接分配采取离散分配的方式,可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。

    访问第n条记录需访问磁盘n次

    • 隐式链接

      除文件的最后一个盘块之外,每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针

      • 优点:很方便文件拓展,不会有碎片问题,外存利用率高。
      • 缺点:只支持顺序访问,不支持随机访问,查找效率低,指向下一个盘块的指针也需要耗费少量的存储空间。
      • 结论:采用隐式链接的链接分配方式,很方便文件拓展。另外,所有的空闲磁盘块都可以被利用,不会有碎片问题,外存利用率高
    • 显式链接

      把用于链接文件各物理块的指针显式地存放在文件分配表(FAT)中。一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存,并常驻内存

      • 优点:很方便文件拓展,不会有碎片问题,外存利用率高,并且支持随机访问。相比于隐式链接来说,地址转换时不需要访问磁盘,因此文件的访问效率更高
      • 缺点:文件分配表的需要占用一定的存储空间。
      • 结论:采用链式分配(显式链接)方式的文件,支持顺序访问,也支持随机访问(想访问ⅰ号逻辑块时,并不需要依次访问之前的0~i-1号逻辑块),由于块号转换的过程不需要访问磁盘,因此相比于隐式链接来说,访问速度快很多。
    • 文件分配表:FAT不仅记录了文件分配信息(显示链接),还“兼职”做了空闲块管理

  3. 索引分配

    ​ 索引分配允许文件离散地分配在各个磁盘块中,系统会为每个文件建立一张索引表,索引表中记录了文件的各个逻辑块对应的物理块。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块

    索引表的 逻辑块号 可以是隐含的,进一步节约空间;

    • 链接方案

      如果索引表太大,一个索引块装不下,那么可以将多个索引块链接起来存放。

      缺点:需要顺序访问,当文件很大时,查我效率低下

    • 多层索引

      建立多层索引(原理类似于多级页表)。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。

      采用K层索引结构,且顶级索引表未调入内存,则访问一个数据块只需要K+1次读磁盘操作

      缺点:即使是小文件,访问数据块也需受K+1次读磁盘

    • 混合索引

      多种索引分配方式的结合。例如,一个文件的顶级索引表中,既包含直接地址索引(直接指向数据块),又包含一级间接索引(指向单层索引表)、还包含两级间接索引(指向两层索引表)。

      所允许的文件最大长度:设有N0个直接地址项;N1个一次间接地址项;N2个二次间接地址项;每个盘块大小M字节;盘块号占m个字节,公式如下:
      文件最大长度 = ( N 0 + N 1 ⋅ M m + N 2 ⋅ ( M m ) 2 ) ⋅ M 文件最大长度=(N_0 + N_1·frac{M}{m}+N_2·(frac{M}{m})^2)·M 文件最大长度=(N0​+N1​⋅mM​+N2​⋅(mM​)2)⋅M
      优点:对于小文件,只需较少的读磁盘次数就可以访问目标数据块。(一般计算机中小文件更多)

    • 总结

4.2 目录

4.2.1 目录的基本概念

文件目录FCB的有序集合一个FCB就是一个文件的目录项。与文件管理系统和文件集合相关联的是文件目录,它包含有关文件的属性、位置和所有权等。

  • 目录管理的基本要求:
    • 从用户的角度看,目录在用户(应用程序)所需要的文件名和文件之间提供一种映射,所以目录管理要实现“按名存取";
    • 目录存取的效率直接影响到系统的性能,所以要提高对目录的检索速度
    • 在多用户系统中,应允许多个用户共享一个文件,因此目录还需要提供用于控制访问文件的信息
    • 此外,应允许不同用户对不同文件采用相同的名字,以便于用户按自己的习惯给文件命名,目录管理通过树形结构来解决和实现。

4.2.2 目录结构

  1. 单级目录结构

    整个文件系统中只建立一张目录表,每个文件占一个目录项不允许文件重名,如下图所示。

    当访问一个文件时,先按文件名在该目录中查找到相应的FCB,经合法性检查后执行相应的操作。

    当建立一个新文件时,必须先检索所有目录项,以确保没有“重名”的情况,然后在该目录中增设一项,把新文件的属性信息填入到该项中。

  2. 两级目录结构

    ​ 将文件目录分成主文件目录(MFD)和用户文件目录(UFD)两级不同用户的文件可以重名,但不能对文件分类。

    主文件目录项记录用户名相应用户文件目录所在的存储位置

    用户文件目录项记录该用户文件的FCB信息。

  3. 树形目录结构

    不同目录下的文件可以重名,可以对文件进行分类,不方便共享。

    根据“文件路径”找到目标文件。用户(或用户进程)要访问某个文件时要用文件路径名标识文件,文件路径名是个字符串。各级日录之间用“/”隔开。从根目录出发的路径称为绝对路径

    例如:自拍.jpg的绝对路径是“/照片/2015-08/自拍jpg”

    系统根据绝对路径一层一层地找到下一级目录。刚开始从外存读入根目录的目录表;找到“照片”目录的存放位置后,从外存读入对应的目录表;再找到“2015-08”目录的存放位置,再从外存读入对应目录表;最后才找到文件“自拍Jpg”的存放位置。整个过程需要3次读磁盘I/O操作

    引入“当前目录”和“相对路径”后,磁盘I/O的次数减少了。这就提升了访问文件的效率。

    从根目录出发是绝对路径;从当前目录出发是相对路径

  4. 无环图目录结构

    在树形目录的基础上,增加一些指向同一结点的有向边,使整个目录成为一个有向无环图,实现文件的共享。

    为共享结点设置一个共享计数器计数器为0时才真正删除该结点

    对于共享文件,只存在一个真正的文件,任何改变都会为其他用户所见。

4.2.3 目录的操作

  • 搜索。当用户使用一个文件时,需要搜索目录,以找到该文件的对应目录项。
  • 创建文件。当创建一个新文件时,需要在目录中增加一个目录项。
  • 删除文件。当删除一个文件时,需要在目录中删除相应的目录项。
  • 创建目录。在树形目录结构中,用户可创建自己的用户文件目录,并可再创建子目录。
  • 删除目录。有两种方式:①不删除非空目录,删除时要先删除目录中的所有文件,并递归地删除子目录。②可删除非空目录,目录中的文件和子目录同时被删除。
  • 移动目录。将文件或子目录在不同的父目录之间移动,文件的路径名也会随之改变。
  • 显示目录。用户可以请求显示目录的内容,如显示该用户目录中的所有文件及属性。
  • 修改目录。某些文件属性保存在目录中,因而这些属性的变化需要改变相应的目录项。

4.2.4 目录实现

​ 目录实现有线性列表和哈希表两种方式,线性列表实现对应线性查找,哈希表的实现对应散列查找。

  1. 线性列表

    最简单的目录实现方法是,采用文件名和数据块指针的线性列表

    • 创建新文件时,必须首先搜索目录以确定没有同名的文件存在,然后在目录中增加一个新的目录项。
    • 删除文件时,则根据给定的文件名搜索目录,然后释放分配给它的空间。
    • 当要重用目录项时有许多种方法:
      • 可以将目录项标记为不再使用,或将它加到空闲目录项的列表上,
      • 还可以将目录的最后一个目录项复制到空闲位置,并减少目录的长度。

    采用链表结构可以减少删除文件的时间。

    线性列表的优点在于实现简单,不过由于线性表的特殊性,查我比较费时。

  2. 哈希表

    哈希表根据文件名得到一个值,并返回一个指向线性列表中元素的指针

    • 优点:查找非常迅速,插入和删除也较简单,
    • 问题:需要一些措施来避免冲突(两个文件名称哈希到同一位置)。

​ 为了减少I/O操作,把当前使用的文件目录复制到内存,以后要使用该文件时只需在内存中操作,因此降低了磁盘操作次数,提高了系统速度

4.2.5 文件共享

​ 文件共享使多个用户共享同一个文件,系统中只需保留该文件的一个副本

  1. 基于索引结点的共享方式(硬链接)

    各个用户的目录项指向同一个索引结点,索引结点中需要链接计数count,用于表示链接到本索引结点上的用户目录项数。

    某用户删除文件只是删除该用户的目录项,count–

    只有count==0才能真正删除文件数据和索引结点。

  2. 利用符号链实现文件共享(软链接)

    为使用户B能共享用户A的一个文件F,可以由系统创建一个LINK类型的新文件,也取名为F,并将该文件写入用户B的目录中,以实现用户B的目录与文件F的链接。

    在一个Link型的文件中记录共享文件的存放路径(Windows快捷方式),操作系统根据路径一层层查找目录,最终找到共享文件。

    当User3访问“ccc”时,操作系统判断文件“ccc”属于Link类型文件,于是会根据其中记录的路径层层查找目录,最终找到User1的目录表中的“aaa”表项,于是就找到了文件1的索引结点。

    即使软链接指向的共享文件已被删除,Link型文件依然存在,只是通过Link型文件中的路径去查找共享文件会失败(找不到对应目录项)。

    由于用软链接的方式访问共享文件时要查询多级目录,会有多次磁盘I/O,因此用软链接访问的速度要比硬链接更慢

​ 硬链接和软链接都是文件系统中的静态共享方法,在文件系统中还存在着另外的共享需求,即两个进程同时对同一个文件进行操作,这样的共享称为动态共享

4.3 文件系统

4.3.1 文件系统结构

文件系统(File system)提供高效和便捷的磁盘访问,以便允许存储、定位、提取数据。

用一个例子来辅助记忆文件系统的层次结构:
假设某用户请求删除文件"D:/工作目录/学生信息.xIsx"的最后100条记录。

  1. 用户需要通过操作系统提供的接口发出上述请求一一用户接口
  2. 由于用户提供的是文件的存放路径,因此需要操作系统一层一层地查找目录,找到对应的目录项一一文件目录系统
  3. 不同的用户对文件有不同的操作权限,因此为了保证安全,需要检查用户是否有访问权限一一存取控制模块(存取控制验证层)
  4. 验证了用户的访问权限之后,需要把用户提供的“记录号”转变为对应的逻辑地址一一逻辑文件系统与文件信息缓冲区
  5. 知道了标记录对应的逻辑地址后,还需要转换成实际的物理地址一一物理文件系统
  6. 要删除这条记录,必定要对磁盘设备发出请求一一设备管理程序模块
  7. 删除这些记录后,会有一些盘块空闲,因此要将这些空闲盘块回收一一辅助分配模块

4.3.2 文件系统布局

  1. 文件系统在磁盘中的结构

    ​ 文件系统存放在磁盘上,多数磁盘划分为一个或多个分区,每个分区中有一个独立的文件系统。文件系统可能包括如下信息:启动存储在那里的操作系统的方式、总的块数、空闲块的数量和位置、目录结构以及各个具体文件等。如下图所示。

    • 主引导记录(MasterBootRecord,MBR),位于磁盘的0号扇区,用来引导计算机,MBR后面是分区表,该表给出每个分区的起始和结束地址。表中的一个分区被标记为活动分区,当计算机启动时,BIOS读入并执行MBR。MBR做的第一件事是确定活动分区,读入它的第一块,即引导块

    • 引导块(bootblock),MBR执行引导块中的程序后,该程序负责启动该分区中的操作系统。为统一起见,每个分区都从一个引导块开始,即使它不含有一个可启动的操作系统,也不排除以后会在该分区安装一个操作系统。Windows系统称之为分区引导扇区

      除了从引导块开始,磁盘分区的布局是随着文件系统的不同而变化的。文件系统经常包含有如上图所列的一些项目。

    • 超级块(superblock),包含文件系统的所有关键信息,在计算机启动时,或者在该文件系统首次使用时,超级块会被读入内存。超级块中的典型信息包括分区的块的数量、块的大小、空闲块的数量和指针、空闲的FCB数量和FCB指针等

    • 文件系统中空闲块的信息,可以使用位示图或指针链接的形式给出。

    • i 结点。索引结点,连续存放,每个文件对应一个结点,可以把 i 结点区看成一个大数组;

    • 根目录,它存放文件系统目录树的根部。

    • 其他部分,存放了其他所有的目录和文件。

  2. 文件系统在内存中的结构

    ​ 内存中的信息用于管理文件系统并通过缓存来提高性能。这些数据在安装文件系统时被加载,在文件系统操作期间被更新,在卸载时被丢弃。这些结构的类型可能包括:

    • 内存中的安装表(mount table),包含每个己安装文件系统分区的有关信息。
    • 内存中的目录结构的缓存,包含最近访问目录的信息。对安装分区的目录,它可以包括一个指向分区表的指针。
    • 整个系统的打开文件表,包含每个打开文件的FCB副本及其他信息。
    • 每个进程的打开文件表,包含一个指向整个系统的打开文件表中的适当条目的指针,以及其他信息。

    进程创建:

    ​ 为了创建新的文件,应用程序调用逻辑文件系统。逻辑文件系统知道目录结构的格式,它将为文件分配一个新的FCB。然后,系统将相应的目录读入内存,使用新的文件名和FCB进行更新,并将它写回磁盘。

    一旦文件被创建,它就能用于I/O,不过,首先要打开文件。系统调用open()将文件名传递给逻辑文件系统。

    • 调用open()首先搜索整个系统的打开文件表,以确定这个文件是否已被其他进程使用。
      • 如果已被使用,则在单个进程的打开文件表中创建一个条目,让其指向现有整个系统的打开文件表的相应条目。该算法在文件已打开时,能节省大量开销。
      • 如果这个文件尚未打开,则根据给定文件名来搜索目录结构。部分目录结构通常缓存在内存中,以加快目录操作。
    • 找到文件后,它的FCB会复制到整个系统的打开文件表中;该表不但存储FCB,而且跟踪打开该文件的进程的数量
    • 然后,在单个进程的打开文件表中创建一个条目,并且通过指针将整个系统打开文件表的条目其他域(如文件当前位置的指针文件访问模式等)相连。
    • 调用open()返回的是一个指向单个进程的打开文件表中的适当条自的指针。以后,所有文件操作都通过该指针执行。
    • 一旦文件被打开,内核就不再使用文件名来访问文件,而使用文件描述符(Windows称之为文件句柄

    进程关闭:

    ​ 当进程关闭一个文件时,就会删除单个进程打开文件表中的相应条目,整个系统的打开文件表的文件打开数量也会递减。当所有打开某个文件的用户都关闭该文件后,任何更新的元数据将复制到磁盘的目录结构中,并且整个系统的打开文件表的对应条目也会被删除。

4.3.3 外存空闲空间管理

​ 一个存储设备可以按整体用于文件系统,也可以细分。例如,一个磁盘可以划分为4个分区,每个分区都可以有单独的文件系统。包含文件系统的分区通常称为卷(volumme)。卷可以是磁盘的一部分,也可以是整个磁盘,还可以是多个磁盘组成RAID集,如图所示。

​ 在一个卷中,存放文件数据的空间(文件区)和FCB的空间(目录区)是分离的。

​ 文件存储设备分成许多大小相同的物理块,并以块为单位交换信息,因此,文件存储设备的管理实质上是对空闲块的组织和管理,它包括空闲块的组织、分配与回收等问题

  1. 空闲表法

    空闲表法属于连续分配方式,它与内存的动态分配方式类似,为每个文件分配一块连续的存储空间。

    • 盘块的分配

      与内存管理中的动态分区分配很类似,为一个文件分配连续的存储空间

      同样可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。

    • 盘块的回收

      与内存管理中的动态分区分配很类似,当回收某个存储区时需要有四种情况:

      • ①回收区的前后都没有相邻空闲区

      • ②回收区的前后都是空闲区

      • ③回收区前面是空闲区

      • ④回收区后面是空闲区

      总之,回收时需要注意表项的合并问题

  2. 空闲链表法

    将所有空闲盘区拉成一条空闲链。根据构成链所用基本元素的不同,分为两种形式:

    • 空闲盘块链:将磁盘上的所有空闲空间以盘块为单位拉成一条链。

      操作系统保存着链头、链尾指针

      • 如何分配:若某文件申请K个盘块,则从链头开始依次摘下K个盘块分配,并修改空闲链的链头指针。
      • 如何回收:回收的盘块依次挂到链尾,并修改空闲链的链尾指针。

      适用于离散分配的物理结构。为文件分配多个盘块时可能要重复多次操作

    • 空闲盘区链:将磁盘上的所有空闲盘区(每个盘区可包含若干个盘块)拉成一条链。

      操作系统保存着链头、链尾指针

      • 如何分配:

        若某文件申请K个盘块,则可以采用首次适应、最佳适应等算法,从链头开始检索,按照算法规则找到一个大小符合要求的空闲盘区,分配给文件。

        没有合适的连续空闲块,也可以将不同盘区的盘块同时分配给一个文件,注意分配后可能要修改相应的链指针、盘区大小等数据。

      • 如何回收:若回收区和某个空闲盘区相邻,则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻,将回收区作为单独的一个空闲盘区挂到链尾

      离散分配、连续分配都适用。为一个文件分配多个盘块时效率更高。

  3. 位示图法

    位示图利用二进制的一位来表示磁盘中一个盘块的使用情况,磁盘上所有的盘块都有一个二进制位与之对应。当其值为“0”时,表示对应的盘块空闲;为“1”时,表示已分配。

    ​ 这样,一个m×n位组成的位示图就可用来表示m×n个盘块的使用情况,如图所示。行为位号,列为字号

    注意:盘块号、字号、位号到底是从0开始,还是从1开始。两者计算盘块号方式不同。

    • 盘块的分配

      • 顺序扫描位示图,从中找出一个或一组其值为“0”的二进制位。

      • 将找到的一个或一组二进制位,转换成与之对应的盘块号。若找到的其值为“0”的二进制位位于位示图的第i行、第j列,则其相应的盘块号应按下式计算(n为每行位数):
        { b = n ( i − 1 ) + j , 字、位、盘块号从1开始 b = n i + j 字、位、盘块号从0开始 begin{cases}b=n(i-1)+j, & text{字、位、盘块号从1开始}\ b=ni+j& text{字、位、盘块号从0开始}end{cases} {b=n(i−1)+j,b=ni+j​字、位、盘块号从1开始字、位、盘块号从0开始​

      • 修改位示图,令 m a p [ i , j ] = 1 map[i,j]=1 map[i,j]=1

    • 盘块的回收

      • 将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为
        { i = ( b − 1 ) / n + 1 ; j = ( b − 1 ) % n + 1 , 字、位、盘块号从1开始 i = b / n ; j = b % n , 字、位、盘块号从0开始 begin{cases}i=(b-1)/n+1;j=(b-1)% n+1, & text{字、位、盘块号从1开始}\ i=b/n;j=b% n, & text{字、位、盘块号从0开始}end{cases} {i=(b−1)/n+1;j=(b−1)%n+1,i=b/n;j=b%n,​字、位、盘块号从1开始字、位、盘块号从0开始​

      • 修改位示图,令 m a p [ i , j ] = 0 map[i,j]=0 map[i,j]=0。

    空闲表法和空闲链表法都不适用于大型文件系统,因为这会使空闲表或空闲链表太大。

  4. 成组链接法

    ​ 在UNIX系统中采用的是成组链接法,这种方法结合了空闲表和空闲链表两种方法,它具有上述两种方法的优点,克服了两种方法均有的表太长的缺点

    ​ 文件卷的目录区中专门用一个磁盘块作为“超级块”,当系统启动时需要将超级块读入内存。并且要保
    内存与外存中的“超级块”数据一致

    用来存放一组空闲盘块号(空闲盘块的块号)的盘块称为成组链块

    • 成组链接思想:把顺序的n个空闲盘块号保存在第一个成组链块中,其最后一个空闲盘块(作为成组链块)则用于保存另一组空闲盘块号,如此继续,直至所有空闲盘块均予以链接。

    • 盘块的分配

      分配1个空闲块

      • ①检查第一个分组的块数是否足够。1<100,是足够的。
      • ②分配第一个分组中的1个空闲块,并修改相应数据

      分配100个空闲块

      • ①检查第一个分组的块数是否足够。100=100,是足够的。
      • ②分配第一个分组中的100个空闲块。但是由于300号块内存放了再下一组的信息,因此300号块的数据需要复制到超级块中

    • 盘块的回收

      需要将超级块中的数据复制到新回收的块中,并修改超级块的内容,让新回收的块成为第一个分组。

4.3.4 虚拟文件系统

​ 虚拟文件系统(VFS)为用户程序提供了文件系统操作的统一接口,屏蔽了不同文件系统的差异和操作细节。

  1. 普通文件系统

    ​ 下图普通的文件系统,不同的外部存储设备,它的文件系统可能是不相同的,对于同一个操作的函数方法定义也许也各不相同;

  2. 虚拟文件系统

    ​ 下图为虚拟文件系统,用户程序可以通过VFS提供的统一调用函数(如open()等)来操作不同文件系统的文件,而无须考虑具体的文件系统和实际的存储介质。

    ​ 虚拟文件系统采用了面向对象的思想,它抽象出一个通用的文件系统模型,定义了通用文件系统都支持的接口。新的文件系统只要支持并实现这些接口,即可安装和使用。

    ​ 为了实现VFS,Linux主要抽象了四种对象类型。每个VFS对象都存放在一个适当的数据结构中,其中包括对象的属性和指向对象方法(函数)表的指针。

    • 超级块对象:表示一个已安装(或称挂载)的特定文件系统。
    • 索引结点对象:表示一个特定的文件。
    • 目录项对象:表示一个特定的目录项。
    • 文件对象:表示一个与进程相关的已打开文件。

    进程与VFS对象之间的交互如下图所示。

    三个不同的进程已打开了同一个文件,其中两个进程使用同一个硬链接。

    在这种情况下,每个进程都使用自己的文件对象,但只需要两个目录项对象,每个硬链接对应一个目录项对象。这两个目录项对象指向同一个索引结点对象, 这个索引结点对象标识的是超级块对象及随后的普通磁盘文件

    ​ 对于不同文件系统的数据结构,VFS 在每打开一个文件,就在主存建立一个vnode,用统一的数据结构表示文件;

    打开文件后,创建vnode,并将文件信息复制到vnode中,vnode的功能指针指向具体文件系统的函数功能

    vnode只存在于主存中,而inode既会被调入主存,也会在外存中存储

    特点:

    • ①向上层用户进程提供统一标准的系统调用接口,屏蔽底层具体文件系统的实现差异
    • ②VFS要求下层的文件系统必须实现某些规定的函数功能,如:open/read/write。一个新的文件系统想要在某操作系统上被使用,就必须满足该操作系统VFS的要求
    • 每打开一个文件,VFS就在主存中新建一个vnode,用统一的数据结构表示文件,无论该文件存储在哪个文件系统

4.3.5 分区和安装

  1. 分区

    • 物理格式化(低级格式化):划分扇区、检测坏扇区、用备用扇区替换坏扇区;当要访问某一块坏扇区时,会使用备用扇区,默默完成替换工作;

    • 逻辑格式化(高级格式化):磁盘分区;每个区的大小、地址范围等信息,会使用 分区表 来记录;

      在每个区里可以建立各自独立的文件系统 ,例如在C盘里建立UNIZX文件系统;

      分区的第一部分是引导块,里面存储着引导信息,它有自身的格式,因为在引导时系统并未 加载文件系统代码,因此不能解释文件系统的格式。下图为一个典型的Linux分区。

  2. 安装

    文件系统在进程使用前必须先安装,也称挂载,任务是将一个文件系统挂载到操作系统中。

    功能:

    • ①在VFS中注册新挂载的文件系统。内存中的挂载表(mount table)包含每个文件系统的相关信息,包括文件系统类型、容量大小等。
    • ②新挂载的文件系统,要向VFS提供一个函数地址列表
    • ③将新文件系统加到挂载点(mountpoint),也就是将新文件系统挂载在某个父目录下

    UNIX本身是一个固定的目录树,只要安装就有,但是如果不给它分配存储空间,就不能对它进行操作,所以首先要给根目录分配空间,这样才能操作这个目录树。

本文发布于:2024-01-29 17:46:30,感谢您对本站的认可!

本文链接:https://www.4u4v.net/it/170652159517192.html

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

留言与评论(共有 0 条评论)
   
验证码:

Copyright ©2019-2022 Comsenz Inc.Powered by ©

网站地图1 网站地图2 网站地图3 网站地图4 网站地图5 网站地图6 网站地图7 网站地图8 网站地图9 网站地图10 网站地图11 网站地图12 网站地图13 网站地图14 网站地图15 网站地图16 网站地图17 网站地图18 网站地图19 网站地图20 网站地图21 网站地图22/a> 网站地图23