索引节点 文件系统 软件设计 文件系统索引节点法

文章目录

• 4.1 文件系统基础

• 4.1.1 文件的基本概念
• 4.1.2 文件控制块和索引节点

• 1. 文件的属性
• 2. 文件控制块
• 3. 索引节点

• 4.1.3 文件的操作

• 1. 文件的基本操作
• 2. 文件打开和关闭

• 4.1.4 文件保护

• 1. 访问类型
• 2. 访问控制

• 4.1.5 文件的逻辑结构（用户看到的文件组织形式）

• 1. 无结构文件（流式文件
• 2. 有结构文件（记录式文件

• 1. 顺序文件
• 2. 索引文件
• 3. 索引顺序文件
• 4. 直接文件/散列文件

• 4.1.6 文件的物理结构（文件数据在存储设备上如何分布组织）

• 1. 连续分配
• 2. 链接分配

• 1. 隐式链接
• 2. 显式链接
• 4. 索引分配
• 4. 混合索引分配

• 4.2 目录

• 4.2.1 目录的基本概念
• 4.2.2 目录结构

• 1. 单级目录结构
• 2. 两级目录结构
• 3. 树形目录结构
• 4. 无环图目录结构

• 4.2.3 目录的操作
• 4.2.4 目录的实现*
• 4.2.5 文件共享

• 1. 基于索引节点的共享方式（硬链接
• 2. 利用符号链实现文件共享（软链接

• 4.3 文件系统

• 4.3.1 文件系统结构
• 4.3.2 文件系统布局

• 1. 文件系统在磁盘中的结构
• 2. 文件系统在内存中的结构

• 4.3.3 外存空闲空间管理

• 1. 空闲表法
• 2. 空闲链表法
• 3. 位示图法
• 4. 成组链接法（UNIX系统采用

• 4.3.4 虚拟文件系统（VFS
• 4.3.5 分区和安装

• 408真题

1. 文件是以硬盘为载体的存储在计算机上的信息集合，文件可以是文本文档、图片、程序等
2. 系统运行时，计算机以进程为基本单位进行资源调度和分配；而用户进行输入、输出时，以文件为基本单位

文件的结构，通过自底向上的方式定义：

1. 数据项。文件系统中最低级的数据组织形式，可以分为

• 基本数据项：描述一个对象或某种属性的一个值，是数据中的最小逻辑单位
• 组合数据项：多个基本数据项组成

2. 记录：一组相关的数据项的集合，描述一个对象在某方面的属性
3. 文件：创建者定义的，具有文件名的一组相关元素的集合，分为

• 有结构文件：由若干个相似的记录组成
• 无结构文件：被视为字符流

与进程管理类似，为了便于文件管理，操作系统引入文件控制块的数据结构

1. 文件的属性

文件属性/文件元数据：操作系统保存的与文件相关的信息

1. 名称。文件名称唯一，以容易读取的形式保存
2. 类型。被支持不同类型的文件系统使用
3. 创建者。文件创建者的ID
4. 所有者。文件所有者的ID
5. 位置。指向设备和设备上文件的指针
6. 大小。文件当前大小（字节、字或块表示）
7. 保护。对文件进行保护的访问控制信息
8. 创建时间、最后修改时间、最后存取时间。用于保护和跟踪文件

操作系统通过文件控制块FCB来维护文件元数据

2. 文件控制块

1. FCB存放控制文件需要的各种信息，实现按名存取
2. FCB的有序集合称为文件目录，一个FCB文件就是一个文件目录项
3. 一个文件目录也被视为一个文件，称为目录文件

FCB主要包含：

1. 基本信息：文件名、文件物理位置、逻辑结构、物理结构等等
2. 存取控制信息：存取权限等
3. 使用信息：建立时间等

3. 索引节点

1. 文件目录一般放在磁盘，查找文件时需要将目录调入内存，付出开销
2. 在检索目录时，文件名以外的描述信息不会使用到，也就不需要调入内存。因此有的系统（例如UNIX）采用文件名和文件描述信息分开的方法。
3. 文件描述信息单独形成一个数据结构，称为索引节点，简称i节点（inode）。文件目录中的每个目录项由文件名和指向i节点的指针组成

索引节点分为：

1. 磁盘索引节点：存放在磁盘中的索引节点。每个文件有一个唯一的磁盘索引节点
   
   2.内存索引节点：存放在内存中的索引节点。文件被打开时，需要将磁盘索引节点复制到内存索引节点中

1 . UNIX操作系统中，IO设备视为：特殊文件
2. （13 408）某文件系统索引节点中包含直接地址项和间接地址项，与单个文件长度无关的因素：索引节点的总数。一个索引节点（inode）对应一个文件，索引节点总数对应文件的数量

1. 文件的基本操作

2. 文件打开和关闭

文件打开：

1. 调用open根据文件名搜索目录，将指明文件的属性（包括文件在外存的物理位置），从外存复制到内存打开文件表的一个表目中，并将该表目的编号（索引）返回给用户
2. 用户再次向系统发出文件操作请求时，可通过索引在打开文件表中查询到该文件的信息，节省搜索目录的开销

文件关闭：

1. 文件不在使用时，利用系统调用close关闭，操作系统会从打开文件表中删除这一条目

在多个进程可以同时打开文件的操作系统中，通常采用两级表

1. 进程打开表：根据进程打开的所有文件，存储进程对文件的使用信息
2. 系统打开表：包含打开的文件相关信息

• 一旦有进程打开文件，系统表就包含该文件的条目
• 另一个进程对已经打开的文件进行open，只需在其进程表中增加一个条目，并指向系统表中该文件的条目
• 通常系统表为每个文件关联一个计数器count，open使count+1，close使count-1。count=0时可以从系统打开表中删除该文件条目

• 文件名不必是文件打开表的一部分，一旦完成对FCB在磁盘上的定位，系统就不再使用文件名，而是采用文件标识符
• 只要文件未关闭，所有文件操作就通过文件打开表来进行

1. (2012 408) read系统调用不需要提供文件名（要先open调用，之后就不用文件名了，用文件标识符

打开文件关联信息：

1. 文件指针：跟踪上次读写位置作为当前文件位置的指针，该指针对打开文件的某个进程是唯一的
2. 文件打开计数：计数器跟踪当前文件打开和关闭的数量。多个进程可能打开同一个文件，系统在删除打开文件条目之前必须等待最后一个进程关闭文件
3. 文件磁盘位置：文件在磁盘上的位置，存储在内存中，减少系统修改文件开销
4. 访问权限：每个进程打开文件都需要有访问模式（创建、只读、读写、添加等），一边操作系统允许或拒绝后续IO请求

1. 打开文件的主要工作：把指定文件的目录复制到内存指定的区域

分为：

1. 口令保护
2. 加密保护
3. 访问控制

口令和加密是为了访问用户文件别他人存取或窃取；访问控制用于控制用户对文件的访问方式

1. 对一个文件的访问，通常由：用户访问权限和文件属性共同限制
2. 任何一个用户在进入系统时都需要进行注册，这一级安全管理属于：系统级

1. 访问类型

对文件的保护可以从限制对文件的访问类型出发，可以加以控制的访问类型：

1. 读：从文件中读
2. 写：向文件中写
3. 执行：将文件装入内存执行
4. 添加：将新信息添加到文件结尾位置
5. 删除：删除文件，释放空间
6. 列表清单：列出文件名和属性

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

例如复制文件可以通过一系列读请求完成，这样，具有读访问权限的用户也就具有复制和打印权限

2. 访问控制

1. 根据用户身份进行控制
2. 为每个文件和目录增加一个访问控制表（ACL），规定每个用户名以及允许的访问类型

精简的访问列表采用拥有者、组和其他用户三种类型（UNIX操作系统采用这种方法）

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

口令

1. 用户在创建文件时提供一个口令，系统为其创建PCB时附上相应口令，同时告知允许共享该文件的所有用户
2. 用户请求访问时必须提供相应口令

密码

1. 对文件进行加密，文件被访问时需要使用密钥

1. 现代操作系统常采用方法是：将访问控制列表与用户、组和其他成员访问控制方案一起使用
2. 对于多级目录结构，不仅需要保护单个文件，还需要保护子目录内的文件，即提供目录保护机制。目录操作和文件操作不同，因此需要不同的保护机制

1. (17 408) 某个文件系统中，针对每个文件分为4类用户，访问权限分5种，使用二进制位串表示文件权限，至少需要：4*5=20位（注意二进制位串

按照逻辑结构，文件可分为无结构文件和有结构文件两大类

1. 文件逻辑结构是为了方便用户而设计的

1. 无结构文件（流式文件

1. 将数据按照顺序组织成记录并积累、保存
2. 是有序相关项的集合，以字节为单位
3. 对记录的访问只能通过穷举搜索的方法
4. 管理简单，适合源程序文件、目标代码文件等

2. 有结构文件（记录式文件

按照记录的组织形式可以分为

1. 顺序文件

1. 文件中的记录按照顺序一个个排列，可以顺序存储或链表存储
2. 记录通常是定长的
3. 分为串结构（按照先后存储，查找需要从头开始）和顺序结构（关键字顺序排列，可以折半查找）
4. 顺序文件适合需要对记录进行批量操作的场合
5. 顺序文件不适合经常需要查找、修改或删除单个记录的场合

2. 索引文件

为了提高变长记录文件的查找速度

1. 建立一张索引表，为主文件的每个记录在索引表中分别设置一个表项
2. 表项包含：指向变长记录的指针（⚠️逻辑起始地址）和记录长度
3. 索引表按照关键字排序，其本身也是一个定长记录的顺序文件

3. 索引顺序文件

1. 将顺序文件中的所有记录分为若干组，为顺序文件建立一张索引表
2. 索引表中为每一组的第一条记录建立一个索引项，包含该记录的关键字值和指向该记录的指针
3. 同一个组中的关键字可以无序，但组之间的关键字必须有序
4. 先查找组关键字，再在组内顺序查找

（11 408）

2. 链接分配

离散分配，消除磁盘外部碎片，适合文件插入删除修改

1. 隐式链接

1. 目录项包含文件第一块的指针和最后一块的指针
2. 每个文件对应一个磁盘块的链表
3. 除了最后一个盘块，每个盘块都含有指向文件下一个盘块的指针，这些指针对用户透明
4. 只适合顺序访问，必须从链表头开始查找；可以几个盘块组合成簇，连接起来，但会增加内部碎片
5. 隐式链接稳定性不好，一个指针丢失或损坏就会导致文件数据丢失

2. 显式链接

1. 将用于链接文件各个物理块的指针，从每个物理块的末尾提取出来，显示存放在内存的一张链接表里，称为文件分配表（FAT
2. FAT在整个磁盘中仅设置一张
3. FAT表在系统启动时就会读入内存，因此查找记录过程在内存中进行，提高检索速度，减少磁盘访问次数
   缺点：
4. FAT占据内存空间较大
5. 打开某个文件时只需要相应盘块，没必要调入整个FAT

1. FAT32的文件目录项包括：文件名、文件访问权限、文件所在的物理位置；不包含：文件控制块的物理位置

4. 索引分配

每个文件都有索引块，是一个磁盘块地址的数组

1. 解决FAT的缺点
2. 支持直接访问，没有外部碎片

缺点：索引块太小无法支持大文件，可以通过以下机制解决

• 链接方案：将多个索引块连接起来
• 多层索引
• 混合索引（重点：既采用直接地址，又采用单级索引和多级索引

4. 混合索引分配

1. 对于小文件：将每个盘块地址直接放入FCB，为直接寻址
2. 对于中文件：采用单级索引，先从FCB得到该文件的盘块地址，即为一次间址
3. 对于大型文件：采用多级索引。UNIX系统采用这种分配方式，设置13个地址项

1. （20 408）某文件系统目录项由文件名和索引节点组成，每个目录项长度64字节，4字节存储索引节点号，60字节存储文件名，则该文件系统能创建的文件数量上限：2^32，文件名可以重复，考虑索引节点号即可

1. 文件目录：FCB的有序集合
2. 一个FCB就是一个文件目录项

目录管理的基本要求

1. 从用户角度来看，目录在用户（应用程序）所需要的文件名和文件之间提供一种映射，因此目录需要实现“按名存取”
2. 目录存取的效率直接影响到系统性能，因此需要提高对目录的检索速度
3. 多用户系统允许多个用户共享一个文件，因此目录需要提供用于控制访问文件的信息
4. 允许不同用户对不同文件采用相同的名字

目录管理通过树形结构来解决和实现

1. 单级目录结构

整个文件系统只建立一张目录表，每个文件占一个目录项

1. 访问一个文件时，按照文件名查找FCB
2. 建立新文件时，必须检索所有目录项，确保没有重名
3. 删除一个文件时，按文件名找到目录项，回收空间，清除目录项

实现了按名存取，但是查找速度慢、文件不允许重名、不便于文件共享

2. 两级目录结构

将文件目录分为**主文件目录（MFD）和用户文件目录（UFD）**两级

1. 主文件目录项记录用户吗和相应用户文件目录所在的存储位置
2. 用户文件目录项记录该用户文件的FCB信息
3. 某用户欲对文件进行访问，先搜索该用户对应UFD，解决了不同用户文件重名的问题

提高检索速度，解决了多用户之间文件重名问题，可以在目录上实现访问限制，但是缺乏灵活性，不能对文件分类

3. 树形目录结构

1. 用文件路径名标识文件，文件路径名是一个字符串，由从根目录出发到所找文件通路上所有目录名与数据文件名用’/'分割组成
2. 绝对路径：从根目录出发的路径，例如 /dev/fd0
3. 相对路径：从当前目录（工作目录）出发。例如当前正在/bin目录，则https://blog.51cto.com/u_16213599/ls表示/bin/ls

在树形目录中查找文件需要按照路径名逐级访问中间节点，增加了磁盘访问次数

UNIX、Linux、Windows系统都采用树形文件目录

4. 无环图目录结构

• 搜索：用户使用文件时需要搜索目录，找到文件的对应目录项
• 创建文件：创建一个新文件，需要在目录中增加一个目录项
• 删除文件：删除一个文件，需要在目录中删除对应的目录项
• 创建目录：树形目录结构中，用户可以创建自己的用户文件目录，并可再创建子目录
• 删除目录：删除空目录/非空目录
• 移动目录：文件或子目录再不同父目录中移动，此时文件路径名也会随之改变
• 显示目录：用户请求显示目录的内容
• 修改目录

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

硬链接速度快于软链接

1. 基于索引节点的共享方式（硬链接

1. 文件的物理地址及其他文件属性等信息不再放在目录项中，而是放在索引节点中
2. 文件目录中只设置文件名及指向相应索引节点的指针
3. 索引节点中还有计数器count，表示共享用户目录项的数目。删除文件需要count==0

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

1. (09 408) 文件F1当前引用计数值为1，先建立F1的符号链接文件F2.在建立F1的
   硬链接文件F3，然后删除F1，此时F2引用计数为：1，F3引用计数为：1
2. (17 408) 文件f1硬链接f2，两个进程分别打开f1和f2，那么f1和f2的读写指针位置不相同

文件系统提供高效和便捷的磁盘访问，以便允许存储、定位、提取数据

• I/O控制
• 基本文件系统
• 文件组织模块
• 逻辑文件系统

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

文件系统存放在磁盘上。多数磁盘划分为一个或多个分区，每个分区中有一个独立的文件系统

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

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

1. 内存中的安装表：包含每个已安装文件系统分区的有关信息
2. 内存中的目录结构的缓存：包含最近访问目录的信息
3. 整个系统的打开文件表：包含每个打开文件的FCB副本及其他信息
4. 每个进程的打开文件表：包含一个只想整个系统的打开文件表中的适当条目的指针，以及其他信息

1. 一个存储设备可以按整体用于文件系统，也可以细分，例如一个磁盘可以划分为4个分区，每个分区都有单独的文件系统
2. 包含文件系统的分区通常称为卷（volume），卷可以是磁盘的一部分，也可以是整个磁盘，还可以是多个磁盘组成RAID集

3. 在一个卷中，存放文件数据的空间（文件区）和FCB的空间（目录区）是分开的

4. 文件存储设备划分为许多大小相同的物理块，以块为单位交换信息，因此文件存储设备的管理实质上是对空闲块的组织和管理，包括空闲块的组织、分配和回收等

1. 空闲表法

1. 属于连续分配方式。为每个文件分配一块连续的存储空间
2. 系统为外存上的所有空闲区建立一张空闲盘块表，每个空闲区对应一个空闲表项
3. 空闲盘区的分配和内存动态分配类似，采用最佳适应算法和首次适应算法
4. 回收存储空间时，需要考虑是否合并

2. 空闲链表法

将所有空闲盘区拉成一条空闲链表。根据构成链表的基本元素的不同，分为：

• 空闲盘块链
• 空闲盘区链

3. 位示图法

4. 成组链接法（UNIX系统采用

（12 408）

• 直接索引分配
• 寻址

（14 408）

• 磁盘连续分配、连接分配
• FCB
• （18 408）
• 混合索引分配
• 簇