第七章 文件管理
文章目录
7.1 文件和文件系统
7.1.1 数据项、记录和文件
1、数据项
📌 数据项(Data Item)
:文件系统中最低级的数据组织形式,用于**描述对象的属性或特征
**。可分为两种类型👇
基本数据项(字段)
🔹 定义:描述对象
单一属性
的最小逻辑单位,不可再分
。🔹 组成:
基本数据项的 “型” = 数据名 + 数据类型
数据名
(如“学号”、“姓名”)数据类型
(如整数、字符串、布尔值)
值
(如“30211”、“王有年”)
组合数据项(组项)
🔹 定义:由
多个基本数据项组合
而成的复合属性。🔹 特点:
可拆分。
逻辑上作为一个整体处理。
🔹 例子:
工资 { 基本工资: xxxx, 工龄工资: xxxx, 奖励工资: xxxx }
2、记录
记录 : 一组相关数据项的集合,用于描述对象的某方面属性。
1️⃣ 记录的数据项组成
记录包含哪些数据项,取决于对象的描述需求
👇
📝 示例1:学生作为“班级成员”
数据项 | 类型 | 示例值 |
---|---|---|
学号 | 整数 | 30211 |
姓名 | 字符串 | 王有年 |
年龄 | 整数 | 20 |
所在班级 | 字符串 | 计算机2023 |
课程成绩 | 组合数据项 | {数学:90, 英语:85} |
📝 示例2:学生作为“医疗对象”
数据项 | 类型 | 示例值 |
---|---|---|
病历号 | 字符串 | M20231105 |
身高 | 浮点数 | 175.5 |
体重 | 浮点数 | 65.2 |
病史 | 字符串列表 | [“过敏性鼻炎”] |
同一对象在不同场景下,记录的数据项可能完全不同!
2️⃣ 关键字(Key)
🔹 定义:能 唯一标识一条记录
的数据项(或数据项组合)。
🔹 作用:快速定位
、避免重复
(类似数据库的主键)。
🔑 关键字类型
- 单字段关键字(最常见)例如:
学号
、病历号
(保证不重复即可)。 - 复合关键字(多字段组合)当单个字段无法唯一标识时使用(如
姓名+出生日期
)。
⚠️ 关键字的选择原则
唯一性
:不能有两条记录的关键字相同。稳定性
:尽量选择不常变动的字段(如学号比年龄更适合作关键字)。简洁性
:优先用单个字段,实在不行再用组合。
3、文件
文件的定义与分类
🔹 文件 : 由 创建者定义
📌、具有 文件名
📁的 一组相关元素
的集合。
📂 文件的两种结构类型:
类型 | 特点 | 应用场景 | 典型应用 |
---|---|---|---|
有结构文件 |
由 若干个相关记录(Records) 组成 📊 |
适用于需要频繁查询/修改部分数据的场景 | 数据库表、学生档案 |
无结构文件 |
视为 字符流 (连续的字节序列)📜 |
适合整体读写(如照片、视频) | 文本文件、图像、二进制文件 |
文件属性(File Attributes)
属性 | 说明 | 示例 |
---|---|---|
文件类型 📝 |
用途或格式分类(如.txt 、.exe 、.mp4 ) |
.py (Python源码) |
文件长度 📏 |
当前大小(字节/KB/GB)或最大允许长度 | 1024 KB |
物理位置 📍 |
存储的设备和地址(如磁盘C:、扇区编号) | /dev/sda1, 块号2048 |
建立/修改时间 ⏰ |
创建时间、最后修改时间 | 2023-10-05 14:30:00 |
❗ 注意:
- 这些属性由
文件系统管理
(用户不可直接修改
,如物理位置)。 - 文件的类型和长度影响其存储和访问方式。
4、文件 vs 记录 vs 数据项 的层次关系
7.1.2 文件名和类型
1、文件名和扩展名
文件名:【同一目录下不允许有重名文件】
📌 1. 文件名长度限制
系统/文件系统 | 最大长度限制 | 特点 |
---|---|---|
MS-DOS | 8字符(短文件名) | 老系统,严格限制 |
旧版 UNIX | 14字符 | 早期标准 |
NTFS(Win NT+) | 255字符(长文件名)✅ | 现代系统支持长文件名 |
❗ 2. 禁用字符
- 常见禁用符号:
空格
、*/:<>?\|
(因用作命令分隔符或路径符) - 现代系统改进:NTFS/Linux 允许空格(需用引号或转义符包裹,如
"my file.txt"
)。
🔠 3. 大小写敏感性问题
系统类型 | 是否区分大小写? | 示例(是否相同文件?) |
---|---|---|
MS-DOS/Win95 | ❌ 不区分 | MYFILE = myfile |
UNIX/Linux | ✅ 严格区分 | MYFILE ≠ myfile |
扩展名:
📌 1. 扩展名的作用
- 标识文件类型🔍:通过扩展名(后缀)快速识别文件的格式和用途。
- 例如:
.txt
→ 文本文件,.jpg
→ 图片文件,.exe
→ 可执行程序。
- 例如:
- 关联打开程序 💻:操作系统用它匹配默认打开方式(如双击
.pdf
用 Adobe 打开)。
📌 2. 命名规则
规则 | 示例 | 说明 |
---|---|---|
分隔符 | 文件名.扩展名 |
用 . 分隔(如 docx ) |
长度 | 1~4个字符常见 | 少数扩展名更长(如 .jpeg ) |
大小写敏感 | 视操作系统而定 | Windows 通常不区分(.TXT = .txt ) |
📌 3. 常见扩展名一览
类型 | 典型扩展名 | 用途 |
---|---|---|
文本文件 | .txt , .md |
纯文本/标记语言 |
图片文件 | .jpg , .png |
图像存储 |
可执行文件 | .exe , .bin |
程序/二进制代码 |
文档文件 | .pdf , .docx |
格式化文档 |
压缩文件 | .zip , .rar |
打包压缩数据 |
2、文件类型
📝 文件按用途分类
📌 1、系统文件(System Files)
🔐 权限特点:
- 仅供系统使用,多数仅允许调用(
执行
),禁止读写✋。- 部分文件对用户完全隐藏(如 Windows 系统
C:\Windows\System32
)。
📌 2. 用户文件(User Files)
🎨 自由度高:
- 用户完全控制(可读、写、删、改)✅,用户将这些文件委托给系统保管。
- 包括源代码(
.c
/.py
)、文档(.docx
)、媒体(.mp4
)等。📂 分类:
子类型 典型扩展名 作用 源代码 .java
,.cpp
程序员编写的原始代码 可执行文件 .exe
,.app
直接运行的程序 数据文件 .xlsx
,.db
存储用户数据
📌 3. 库文件(Library Files)
📚 共享但保护:
- 允许调用(如数学库、图形库),但禁止修改🚫。
- 提供通用功能,避免重复造轮子。
📂 示例:
- 静态库(
.lib
/.a
):编译时绑定。- 动态库(
.dll
/.so
):运行时调用。
📝 文件按数据形式分类
📌 1. 源文件(Source Files)
💻 定义:
- 包含原始代码或数据的文本文件,由程序员/用户直接编写👩💻。
- 一般为ASCII/Unicode编码。
📂 特点:
- 扩展名:
.c
(C语言)、.py
(Python)、.txt
(纯数据)。
📌 2. 目标文件(Object Files)
🔧 定义:
- 源文件经编译生成的中间文件,包含机器码但未完整链接🔗。
- 不可直接执行,需进一步处理。
📂 特点:
- 扩展名:
.obj
(Windows)、.o
(Linux/macOS)。- 内容:二进制代码 + 符号表(函数/变量地址)。
📌 3. 可执行文件(Executable Files)
🚀 定义:
- 完全链接后的文件,可直接由操作系统运行✅。
- 包含机器指令 + 库依赖 + 资源。
📂 特点:
平台 扩展名 Windows .exe
Linux 无扩展名或 .bin
macOS .app
📝 文件存取控制属性分类
📌 1. 只执行文件(Execute-only File)
- 权限:🔒
- 允许:被核准的用户调用执行(如运行程序)
- 禁止:❌ 读内容、❌ 修改/写入
📌 2. 只读文件(Read-only File)
- 权限:📖
- 允许:文件主及授权用户读取内容
- 禁止:❌ 修改、删除或写入
📌 3. 读写文件(Read-Write File)
- 权限:✏️
- 允许:文件主及授权用户读取 + 修改(如编辑、保存)
- 注意:需谨慎设置权限,防止越权操作!
📝 文件组织形式和处理方式分类
📌 1、普通文件(Regular File)
- 内容:📄
ASCII码
(文本)或二进制码
(程序/数据)- 例子:
- 用户创建的:源代码(
.c
/.py
)、文档(.txt
)- 系统自带的:内核代码、实用工具(如
ls
命令)- 特点:最常见的文件类型,可直接读写内容!
📌 2、目录文件(Directory File)
- 本质:📂
文件目录的集合
(一种特殊文件)- 功能:
- 记录**
下属文件
的元信息
**(名称、权限等)支持文件检索
(如ls
)、操作(如cd
)- 权限控制:和普通文件类似(需
r
读目录、w
增删文件)- 举个栗子🌰:
/home/user/
是一个目录文件,存放下属文件列表。
📌 3、特殊文件(Special File / Device File)
- 代表对象:🖨️
I/O设备
(如键盘、打印机、磁盘)- 设计目的:统一用文件接口管理设备!
- 访问方式:
- 像操作文件一样
读/写设备
(如/dev/sda
代表磁盘)- 实际执行由
设备驱动程序完成
- 权限验证:与普通文件规则一致(但操作可能受限)
- 类型细分:
- 字符设备(如
/dev/tty
,按字符流传输)- 块设备(如
/dev/sda
,按数据块传输)
7.1.3 文件系统的层次结构
文件系统的模型可分为三个层次: 最底层是对象及其属性
,中间层是对对象进行操纵和管理的软件集合
,最高层是文件系统提供给用户的接口
。
1、对象及其属性
1️⃣ 文件(File) 📄
- 核心对象:文件是文件系统直接管理的
实体
。 - 多样性:包括 文本文件、二进制文件、可执行文件 等不同类型。
- 管理内容:
存储
(占用磁盘空间)读取/写入控制
(权限管理)元数据维护
(文件名、大小、修改时间等)
💡 关键作用:用户和程序操作的基本单位
!
2️⃣ 目录(Directory) 📂
- 功能:帮助用户
组织文件、快速检索
。 - 目录项包含:
文件名
(标识文件)文件属性
(如权限、类型、大小)物理地址 / 指针
(指向文件在磁盘的实际位置)
- 优化目标:
加快查找速度
(索引、哈希等优化方法)- 层级结构(如树形目录,
/home/user/docs/
)
⚡ 影响:目录设计直接影响 文件存取效率
!
3️⃣ 存储空间(Disk/Tape Storage) 💿
- 核心任务:高效管理文件和目录占用的
物理存储
。 - 管理方式:
空间分配
(如连续分配、链式分配、索引分配)碎片整理
(减少空间浪费)磁盘调度优化
(提高读写速度)
🔧 重要性:好的存储管理能 提升系统整体性能
!
2、对对象进行操纵和管理的软件集合
操纵对象
存储空间管理
💾 - 管理文件在磁盘上的存储分配 【对象:存储空间】目录管理
📁 - 组织文件和目录结构 【对象:目录】地址转换
🔄 - 逻辑地址↔物理地址转换【对象:文件】读写管理
✍️📖 - 控制文件读写操作【对象:文件】共享与保护
🔒 - 实现文件共享和安全机制【对象:文件】
与文件系统有关的软件分为四个层次(自底向上)👇
1️⃣ I/O控制层(设备驱动程序层)
- 功能:
- 最底层,
直接与硬件交互
🖥️⚡ - 通过
磁盘驱动程序
控制物理设备(如读写磁盘扇区)。
- 最底层,
2️⃣ 基本文件系统层(数据块交换层)
- 功能:
- 负责
内存
↔磁盘
的数据块传输
(如缓存块加载/写回)📦⇄💽 - 不关心内容含义,只处理原始块操作。
- 负责
3️⃣ 基本I/O管理程序(磁盘事务层)
- 核心任务:
逻辑块 → 物理块映射
🗺️(如文件第3块对应磁盘的哪个扇区?)空闲盘块管理
(标记哪些块可用/已占用)🔍I/O缓冲区分配
(优化读写速度)⏳→🚀
4️⃣ 逻辑文件系统(用户接口层)
- 功能:
- 处理
文件和记录
的高层操作 ✨ - 提供
符号文件名访问
(如/home/note.txt
)📂 - 实现
文件保护
(权限控制)和元数据管理
(创建时间、大小等)🔒
- 处理
- 用户视角:
- “右键属性”都来自这一层 🌳📋
3、文件系统提供给用户的接口
文件系统通过 标准化的接口 为用户和应用程序提供 文件和记录操作 的方法,使其无需关心底层存储细节。
📋 (1) 命令接口(Command Interface)
🔹 定义:用户通过 命令行终端(CLI)
输入指令与文件系统交互。
🔹 特点:
- ✅ 直接交互(如
ls
、cp
、rm
等命令)。 - ✅ 适用于管理员、开发者 或 需要手动操作文件的场景。
💻 (2) 程序接口(Program Interface / API)
🔹 定义:应用程序通过 系统调用(System Calls)
访问文件系统。
🔹 特点:
- ✅ 编程方式调用(如
open()
、read()
、write()
)。 - ✅ 适合软件开发
文件系统的层次结构详细版
7.1.4 文件操作
创建文件 🆕
- 功能:
建立新文件并分配存储空间
。【进行 Create 系统调用】 - 步骤:
- 为新文件
分配外存空间
(如磁盘)。 - 在
文件目录中创建目录项
,记录文件属性:- ✅ 文件名
- ✅ 外存地址(物理位置)
- ✅ 元数据(大小、权限、时间等)。
- 为新文件
删除文件 🗑️
- 功能:
释放文件占用的资源
。【进行 Delete 系统调用,参数文件名和文件路径】 - 步骤:
查找目录项
:根据文件名定位到对应条目。回收空间
:释放文件占用的外存(物理删除)。标记为空项
:删除目录中的记录(逻辑删除)
读文件 📖
- 功能:从
外存读取文件内容到内存
。【进程使用read系统调用】 - 步骤:
查找目录
:根据文件名找到目录项。获取位置
:从目录项中读取文件的外存地址
。移动指针
:通过目录项中的读指针定位读取位置
(默认从文件开头)。
写文件 ✍️
- 功能:将
内存中的数据写入外存文件
。【进程使用write系统调用】 - 步骤:
查找目录
:根据文件名找到对应的目录项。获取外存地址
:从目录项中读取文件的外存地址
。定位写指针
:根据目录项中的写指针(或当前文件偏移量)确定写入位置:- 如果写指针
默认在文件开头
(如新文件或覆盖写
),则从起始位置写入
。 - 如果写指针
在文件末尾
(追加模式
),则从结尾续写
。
- 如果写指针
执行写入
:将内存中的数据写入外存,并更新写指针的位置。
- 注意:写入可能覆盖原有内容!⚠️
设置读/写位置 🎯
- 功能:实现
随机存取
(非顺序操作)。 - 关键:通过调整
文件的读/写指针,直接跳转到指定位置
。- 顺序存取:每次操作必须从头开始。
- 随机存取:灵活定位。
当用户对文件进行多次操作(读/写)时,如果每次都要从目录检索开始(根据文件名找外存位置),会导致重复检索开销大,效率低下。
引入
open()
系统调用,提前加载文件信息到内存。避免重复目录检索,用空间换时间。
“打开文件” - open(文件路径,文件名,对文件的操作类型:只读r/读写rw) 🚪
判断权限
: 根据文件存放路径找到相应的目录文件,从目录中找到文件名对应的的目录项,并检查该用户是否有指定的操作权限。建立连接
:在用户和文件之间创建一个逻辑通道
(无需重复检索目录)。内存缓存
:将文件的属性(如外存地址、权限、大小等)
从目录项拷贝
到内存的打开文件表
。返回索引号
:系统为用户分配一个 文件描述符(File Descriptor)【也称索引号】,后续操作直接凭此索引访问文件。
“关闭文件” - close() ✖️
断开连接
:释放文件描述符(“退票”)。清理内存
:从打开文件表删除该文件的表目。同步数据
(可选):如果文件被修改,可能将缓冲区的数据写回磁盘💾。
文件属性操作 📂⚙️
功能:直接修改/查询文件的元数据(metadata)。
常用系统调用:
rename
:修改文件名 🔄chown
:改变文件所有者 👑chmod
:修改文件权限(读/写/执行)🔐stat
/fstat
:获取文件状态 ℹ️包括:大小、创建时间、类型、权限等。
目录操作 📁🔧
- 功能:管理文件系统的目录结构。
- 常用系统调用:
mkdir
:创建目录 🆕rmdir
:删除空目录 🗑️要求目录必须为空getcwd
:获取当前工作目录 🗺️chdir
:切换工作目录 🔄
- 注意:
- 删除非空目录需递归操作(如
rm -rf
命令💥)
- 删除非空目录需递归操作(如
文件共享与系统级操作 🤝💻
- 功能:实现多进程/用户共享文件或管理文件系统。
- 关键系统调用:
link
:创建硬链接(同一文件的多个入口)⛓️symlink
:创建软链接(快捷方式)🔗(删除原文件后失效💨)mount
/unmount
:挂载/卸载文件系统 🏗️
7.2 文件的逻辑结构
检索速度同时受以下两种结构影响
文件的逻辑结构(File Logical Structure) 🧠📄
定义:从 用户视角
看到的文件组织形式【在用户看来,文件内部的数据应该是如何组织起来的。】
核心特点:
用户可见
👀:用户直接操作。独立于物理存储
💾:与磁盘如何存放无关。- 组成单位:由
逻辑记录(Logical Record)构成
,用户可以直接处理的数据及其结构 - 又称为
文件组织(File Organization)
文件的物理结构(File Physical Structure)- 非空闲磁盘块管理 🖥️📦
定义:文件在 外存(磁盘)上的实际存储方式
,对用户透明。【在操作系统看来,文件的数据是如何存放在外存中的。】
核心特点:
用户不可见
🙈:由操作系统管理
。依赖存储介质
💽:与磁盘块大小、分配策略相关。
在外存管理中,为了方便对文件数据的管理,文件的逻辑地址空间也被分为了一个一个的文件“块”
。文件的逻辑地址表示为(逻辑块号,块内地址)
的形式,操作系统 为文件分配存储空间都是以块为单位
的。用户通过逻辑地址来操作自己的文件,操作系统要负责实现从逻缉地址到物理地址的映射
类型 | 描述 | 目录项内容 | 优点 | 缺点 |
---|---|---|---|---|
连续分配 | 文件占用的磁盘块物理相邻 📏 | 起始块号、文件长度 | 支持顺序访问和直接访问 (即随机访问)连续分配的文件在顺序访问时速度最快 |
不方便文件拓展 ;存储空间利用率低, 会产生磁盘碎片 (外部碎片) |
链式分配 | 隐式链接 :除文件的最后一个盘块之外,每个盘块中都存有指向下一个盘块的指针显式链接 :建立一张文件分配表(FAT)显式记录盘块的先后关系(开机后FAT常驻内存) |
隐式链接:起始块号、结束块号 显式链接:起始块号 |
隐式链接:很 方便文件拓展,不会有碎片问题 ,外存利用率高。显式链接:很 方便文件拓展,不会有碎片问题 ,外存利用率高,并且 支持随机访问 。相比于隐式链接来说,地址转换时不需要访问磁盘(文件分配表常驻内存) ,因此文件的访问效率更高。 |
隐式链接:只支持顺序访问,不支持随机访问 ,查找效率低,指向下一个盘块的指针也需要耗费少量的存储空间 。显式链接: 文件分配表的需要占用一定的存储空间 。 |
索引分配 | 为文件数据块建立索引表若文件太大,可采用链接方案、多层索引、混合索引📇 | 链接方案记录的是雪,全层准合案引记录的是顶级索引块的块号 | 支持随机访问 ,易于实现 文件的拓展 |
索引表需占用一定的存储空间 。访问数据块前需要先读入索引块 。若采用 链接方案 ,查找索引块时可能需要 很多次读磁盘操作 |
连续分配
:连续分配方式要求每个文件在磁盘上占有一组连续的块可以直接算出逻辑块号对应的物理块号,因此
连续分配支持顺序访问和直接访问(即随机访问)
链式分配
:考试题目中遇到未指明隐式/显式的“链接分配”,默认指的是隐式链接的链接分配隐式链接
:显式链接
:把用于链接文件各物理块的指针显式地存放在一张表中,即文件分配表(FAT, File Allocation Table )
索引分配
:索引分配允许文件离散地分配在各个磁盘块中,系统会为每个文件建立一张索引表
,索引表中记录了文件的各个逻辑块对应的物理块
。索引表存放的磁盘块称为索引块
。文件数据存放的磁盘块称为数据块
。超级超级超级重要考点
:①要会根据多层索引、混合索引的结构计算出 文件的最大长度(Key:
各级索引表最大不能超过一个块
);②要能自己分析 访问某个数据块所需要的读磁盘次数(Key: FCB中会存有指向顶级索引块的指针,因此可以根据FCB读入顶级索引块。
每次读入下一级的索引块都需要一次读磁盘操作
。另外,要注意题目条件--顶级索引块是否已调入内存
)
逻辑结构 vs 物理结构
文件内部各条记录链式存储
:由创建文件的用户
自己设计的
文件整体用链接分配
:由操作系统
决定
索引文件
的索引表:用户自己建立
的,映射:关键字→记录存放的逻辑地址
索引分配
的索引表:操作系统建立
的,映射:逻辑块号→物理块号
7.2.1 文件逻辑结构的类型
1、按文件是否有结构分类
有结构文件(记录式文件)📊
定义:像Excel表格一样按记录存储数据,每条记录描述一个实体(如学生信息表)。一般来说,每条记录有一个数据项可作为关键字(作为识别不同记录的ID)
1. 定长记录
🔢
- 特点:
✅所有记录长度相同
(如身份证号固定18位)
✅数据项位置固定
(类似表格列对齐)
✅高速访问
:直接计算偏移量定位(秒级跳转⚡)
2. 变长记录
🐍
- 特点:
🌟记录长度可变,但每个记录的长度都是可知的
(如病历摘要📝、商品评论💬)
⚠️需额外存储长度信息
(如开头2字节记录长度)
🐢访问速度较慢
(需顺序遍历)
无结构文件(流式文件)🌊
定义:字节流 形式存储(如MP3/EXE文件)
特点:
✅ 极致简单:仅按字节编号,以字节为单位的。
✅ 灵活通用:任何数据都可存储
✅ 访问方式:读写指针控制
应用场景:源程序、可执行文件、库函数等,所采用的就是无结构的文件形式
2、按有结构文件的组织方式分类
一、顺序文件(Sequential File)➡️📉
定义:指由一系列记录 按某种顺序排列
所形成的文件。【文件中的记录一个接一个地顺序排列(逻辑上)。】
核心特点:
存储方式:
定长记录
:直接物理连续存储(如数组🗃️)变长记录
:需用分隔符/长度前缀标记(如CSV📝)
物理上存储:
顺序存储
:逻辑上相邻的记录物理上也相邻(类似于顺序表)链式存储
:逻辑上相邻的记录物理上不一定相邻(类似于链表)
结构:
串结构
:记录之间的顺序与关键字无关。通常 按照记录存入的时间决定记录的顺序顺序结构
:记录之间的顺序 按关键字顺序排列。
访问特性:
- ✅
顺序访问极快
(适合磁带等顺序存储介质🎞️) - ❌
随机访问极慢
(平均需遍历n/2条记录🐢)
- ✅
二、索引文件(Indexed File)🔍📇
定义:为可变长记录文件建立 一张索引表
,为 每个记录设置一个表项
核心特点:
- 结构组成:
数据区
:原始变长记录索引区
:固定格式的〈key, 物理地址〉映射表(像字典📖)
- 访问特性:
✅随机访问极快
(O(1)时间复杂度⚡)
❌空间开销大
(需额外存储索引表)
三、索引顺序文件(Indexed Sequential File)🔄🚀
定义:分组建立索引
—— 为每个文件建立一张索引表时,并不是为每一个记录建立一个索引表项,而是为一组记录中的第一个记录建立一个索引表项。
核心特点:
- 分层结构:
数据分块
(如每100条记录为一组)只索引每组的第一个记录
(空间省50%+✨)
- 访问特性:
✅ 折中了顺序和索引的优点
✅ 适合超大规模文件
7.2.2 顺序文件(Sequential File)
1、顺序文件的排列方式
1. 串结构 ⏳(时间序列式)
特点:
- 无脑追加:
按存入时间的先后进行排序
的,各记录之间的顺序与关键字无关。 - 零排序:记录之间没有逻辑关联 →
纯线性结构
➖ - 检索代价:
🐢必须从头遍历,直到找到指定的记录或查完所有的记录为止。
(平均查找次数 = n/2)
😫 最坏情况查完全部记录
应用场景:系统日志文件🖥️、区块链交易记录(按时间戳追加⛓️)
2. 顺序结构 🔢(关键字排序式)
特点:
- 强制排序:用户指定
唯一关键字
(如学号/身份证号🆔), 可以是任意类型的变量
,每个记录的关键字值在文件中具有唯一性
。 - 有序:记录
按关键字严格排序
(像字典拼音排序📖) - 检索加速:
支持高效算法
→ 如折半查找法、插值查找法、跳步查找法等方法提高检索效率。
应用场景:学生信息表(按学号排序🎓)
链式存储
:无论是定长/可变长记录,都无法实现随机存取,每次只能从第一个记录开始依次往后查找顺序存储
:
可变长记录
:无法实现随机存取。每次只能从第一个记录开始依次往后查找定长记录
:可实现随机存取。记录长度为L,则第i个记录存放的相对位置是i*L
- 若采用
串结构
,无法快速找到某关键字对应的记录- 若采用
顺序结构
,可以快速找到某关键字对应的记录(如折半查找 - 快速检索)一般来说,考试题目中所说的“顺序文件”指的是物理上顺序存储的顺序文件。
2、顺序文件的优缺点
✅ 顺序文件的优点
1. 批量存取效率极高
🚀
- 最佳场景:需要大批量连续读写(如日志备份、数据导出)
2. 存储结构简单
📏
定长记录
:物理存储连续
,类似数组(访问简单高效🔢)变长记录
:利用分隔符
(CSV、JSON等)管理
3. 适合顺序存储设备
(磁带)🎞️
- 磁带只能顺序访问 → 顺序文件是唯一可行方案
❌ 顺序文件的缺点
1. 随机访问性能差
⏳
- 查找复杂度:
平均O(n/2),最差O(n)
(遍历全表😵) 变长记录更慢
:额外解析记录边界(加剧I/O开销📉)
2. 修改(增/删/改)困难
⚠️
插入/删除
:必须移动后续记录(类似数组操作,时间复杂度O(n))【如果是串结构则相对简单】扩容受限
:变长记录易导致存储碎片化
🔧
解决方案:日志文件(Log / Transaction File)
核心思想:避免实时修改主文件,采用批处理合并方式
实现方式:
主文件(Main File)
保持顺序结构(只读📖)操作日志(Log File)
记录增删改请求📝定期合并
(如4小时/每日)生成新主文件🔄
🚀 用顺序文件的场景:批量处理 + 顺序设备(如日志备份、ETL数据流)
🚫 避免使用的场景:高频随机读写 + 低延迟要求(如在线交易系统)
7.2.3 记录寻址
1、隐式寻址方式
隐式寻址(Implicit Addressing)是顺序文件访问记录的方式,通过读/写指针自动定位记录地址,适用于定长/变长记录的顺序文件。
定长记录
存储结构:所有记录固定长度(L),物理连续存储
(类似数组)
指针操作
读指针(Rptr)
:指向下一个待读取记录的首地址
// 每当读完一个记录时,便执行 Rptr = Rptr + L
示例:若
L=100B
,当前Rptr=0x1000
,读完后Rptr=0x1064
(0x1000 + 100)写指针(Wptr)
:指向下一个待写入位置
// 在每写完一个记录时,便执行 Wptr = Wptr + L
变长记录
存储结构:每个记录包含长度字段(Li),存储不连续
:
指针操作: 设置读或写指针,在每次读或写完个记录后,须将读或写指针加上Li,Li是刚读或刚写完的记录的长度。
Rptr = Rptr + Li + sizeof(Li)
关键问题
性能损失
:每次需解析长度字段 → 额外I/O开销📉随机访问低效
:必须顺序扫描前 i-1 个记录才能找到第 i 个(时间复杂度O(n)😵)
2、显式寻址方式
通过文件中记录的位置
定长记录文件
获得第i个记录相对于第一个记录首址的地址:
A i = i × L (首地址为 0 )。 A_i = i × L (首地址为 0)。 Ai=i×L(首地址为0)。由于获得任何记录地址的时间都非常短,故可利用这种方法对定长记录实现随机访问。
变长记录文件
记录长度不固定(
L1, L2, ...
),必须顺序解析前 i-1 个记录才能定位第 i 个,检索时间长很低效
A i = ∑ i = 0 i − 1 L i + 1 A_i = \sum_{i=0}^{i-1}L_i + 1 Ai=i=0∑i−1Li+1
利用关键字
定长记录文件
+ 变长记录文件
:用户必须指定一个字段作为关键字,系统将利用该关键字顺序地从第一个记录开始,与每一个记录的关键字进行比较,直到找到匹配的记录。
⚡ 隐式寻址 vs 显式寻址
特性 | 隐式寻址 | 显式寻址 |
---|---|---|
访问方式 | 指针自动移动📍 | 直接跳转(通过索引)🎯 |
适用记录 | 定长/变长 | 通常定长 |
随机访问 | ❌ 慢(O(n)) | ✅ 快(O(1)~O(log n)) |
存储开销 | 低 | 高 |
7.2.4 索引文件(Index File)
1、按关键字建立索引
📌 问题背景
定长记录文件
:可通过计算直接定位记录,支持高效随机访问
。🔢变长记录文件
:必须顺序查找,效率低
(O(n)时间)。⏳
💡 解决方案:索引表
索引表结构
- 每个表项包含:
指针
:记录在逻辑地址空间的首地址。📍长度
:记录的长度(L)。📏
- 索引表按
关键字排序
,本身是 定长记录的顺序文件。
- 每个表项包含:
检索流程
折半查找
:在索引表中 用关键字快速定位 记录(O(log n)时间)。🔍直接访问
:根据 指针和长度定位 主文件中的记录。🚀
更新操作
新增记录
:需同步 更新索引表(维护排序)。🔄删除/修改
:类似处理,可能 需调整索引表。⚠️
2、具有多个索引表的索引文件
🔍 背景问题
单索引表限制
:只能按一个关键字
检索。🔢实际需求
:不同用户希望按不同属性快速查找。🎯
💡 解决方案:多索引表
索引表结构
每个检索属性一个索引表
,例如:- 📖 图书编号索引(主键)
- 📚书名索引
- ✍️ 作者索引
- 📅 出版时间索引
- 🗂️
所有索引表按各自关键字排序
,仍是定长记录文件
。
检索流程
- 🔎用户选择检索条件(如
作者="鲁迅"
)→ 在对应索引表中折半查找→ 通过指针定位主文件记录。
- 🔎用户选择检索条件(如
更新操作
- ⚙️
增/删/改记录
:需同步更新所有相关索引表
,维护排序性。
- ⚙️
🎯 核心优势
多维度检索
:支持按任意关键字(属性)高效查询,适应不同需求。🌈高效随机访问
:索引表将O(n)顺序查找优化为O(log n)随机访问。⚡动态维护便捷
:记录增删仅需调整索引表,无需重组主文件。🔄
⚠️ 缺点
存储开销大
:每个记录需在多个索引表中保留条目,占用额外空间。💾更新代价高
:修改主文件需同步更新多个索引表。⏱️
7.2.5 索引顺序文件(Index Sequential File)
1、索引顺序文件的特征
📚 基本概念:索引顺序文件是 顺序文件的改进版
,在保留顺序文件核心特性的基础上,通过 引入索引表
和 溢出文件
,显著提升了文件操作的灵活性。
💡 核心特点
- 📌
记录按关键字顺序存储
(保留顺序文件的特性) - 🔍
支持随机访问
(通过索引表实现) - 🛠
增删改更高效
(利用溢出文件管理动态变更)
🎯 核心组件
文件索引表
:- 提供 随机访问能力(通过折半查找快速定位记录)。🔍⚡
- 将O(n)顺序检索优化为O(log n)。🎯
溢出区
(Overflow File):存储新增、删除或修改的记录
,避免频繁重组主文件。🔄- 类似数据库的“临时缓冲区”,
定期合并到主文件
。⏳
✅ 优势
随机+顺序双模式
:既可快速访问单条记录,又支持高效顺序扫描。🔀动态维护便捷
:溢出区减少插入/删除时的数据迁移开销。✨低成本升级
:在顺序文件基础上仅增加索引和溢出区,存储开销可控。💾
⚠️ 局限性
溢出区膨胀
:长期不合并可能导致检索性能下降(需定期维护)。⚠️不适合高频更新
:大量修改时溢出区管理复杂度增加。⏱️
2、一级索引顺序文件
📚 基本原理
- 首先将变长记录顺序文件中的
所有记录分为若干个组
,如50个记录为一个组。 - 然后为顺序文件
建立一张索引表
,并为每组中的第一个记录在索引表中建立一个索引项
,其中含有该记录的关键字和指向该记录的指针
。
🔍 检索流程详解(两步法)
1️⃣ 第一步:索引表查找(定位记录组)
- 输入:用户/程序提供的
目标关键字
🔑 - 查找算法:
- 二分查找(索引表有序时) ⚡
- 顺序查找(简单但略慢) 🐢
- 输出:
- 找到
目标记录所在分组
的首记录表项 - 提取该组的
起始位置指针
(指向主文件) 📌
- 找到
2️⃣ 第二步:主文件顺序查找(定位目标记录)
- 输入:索引表返回的
组起始位置
- 查找方法:
- 从起始位置开始,
顺序扫描
该组记录 📖 - 逐个比对关键字,直至命中目标(或失败) 🎯
- 从起始位置开始,
- 平均查找次数:
- 每组
k
条记录 → 平均需查k/2
次
- 每组
🎯 索引顺序文件的平均查找次数是√N
- 总记录数 =
N
- 每组记录数 ≈
√N
- 组数 ≈
√N
(组数 × 每组记录数 ≈ N)
1️⃣ 查索引表(定位组):
- 对
√N
个索引项进行二分查找 → 平均比较次数≈log₂(√N)
- 当
N
较大时,可近似为O(√N)
(例如顺序查找索引表时)。2️⃣ 查主文件(组内顺序查找):
- 每组
√N
条记录 → 平均查找√N/2
次总查找次数 ≈
√N(索引) + √N/2(组内) ≈ √N
3、两级索引顺序文件
为顺序文件建立多级索引,即为索引文件再建立一张索引表,从而形成两级索引表。
7.2.6 直接文件和哈希文件
1、直接文件
🎯 核心特点 :关键字(Key) → 物理地址(Address)的直接转换!
- 无需中间查找:跳过索引、链表或顺序扫描,一步到位!🚀
- 空间换时间:通过特定算法将键值转换为地址,实现
O(1)
访问(理想情况下)。
2、哈希文件
🎯 核心概念 :键值→地址的间接映射
:哈希文件是直接文件的经典实现,利用 哈希函数(Hash Function)
快速定位记录。但与纯直接文件不同,它采用 「间接寻址」:🔹 关键字(Key) → Hash值 → 目录表指针 → 物理块地址
🔍 哈希文件流程详解
1️⃣ Hash函数(H)
: 作为标准函数存于系统中,供存取文件时调用。
- 输入:记录的关键字
K
- 输出:目录表索引
A = H(K)
- 🌰 示例:
H("ID101") = 5
→ 指向目录表的第5项
2️⃣ 目录表(指针表)
:每个表项存储 物理块指针(如磁盘块地址)
3️⃣ 物理存储块
:实际存放记录的数据块
7.3 文件目录
文件目录是文件系统的“导航地图🗺️”,目录管理的核心要求如下:
1️⃣ 按名存取(Name-Based Access)
- 用户视角:只需输入
文件名
(如report.docx
),系统自动找到文件位置。 - 底层实现:目录中记录
文件名 → 物理地址
的映射。
2️⃣ 提高检索速度(Fast Lookup)
- 优化手段:
哈希目录
:用哈希表加速文件名查找。树形结构
:层级目录减少单层文件数。
- 关键目标:
减少磁盘I/O
,尤其在大中型文件系统中!
3️⃣ 文件共享(File Sharing)
- 多用户场景:
多个用户访问同一文件
。 - 实现方式:
硬链接
:多个目录项指向同一文件。符号链接
:快捷方式(记录目标文件路径)。
- 优势:节省存储空间 + 保证数据一致性! 💾
4️⃣ 允许重名(Name Reuse)
- 用户自由:不同用户可对不同文件使用相同名字。
- 实现原理:
目录隔离
:用户私有目录(如/home/user1/
vs/home/user2/
)。- 命名空间:通过路径全称区分(如
/home/user1/notes.txt
≠/home/user2/notes.txt
)。
7.3.1 文件控制块和索引结点
文件控制块(File Control Block, FCB)
是操作系统中用于 描述和控制文件
的数据结构,文件与文件控制块一一对应。
文件目录
:文件控制块的有序集合
,即 一个文件控制块就是一个文件目录项
。
目录文件
:一个文件目录也被看做是一个文件
1、文件控制块 FCB(File Control Block)
在文件控制块中,通常应含有三类信息,即基本信息、存取控制信息及使用信息。
- 基本信息类
文件名
,指用于标识一个文件的符号名,在每个系统中,每一个文件都必须有唯一的名字
,用户利用该名字进行存取。文件物理位置
,指文件在外存上的存储位置
,它包括:- 存放文件的设备名
- 文件在外存上的起始盘块号
- 指示文件所占用的盘块数,或字节数的文件长度。
文件逻辑结构
,指示文件是流式文件还是记录式文件
、记录数
,文件是定长记录还是变长记录
等。文件的物理结构
,指示文件是顺序文件,还是链接式文件或索引文件
。
- 存取控制信息类
文件主
的存取权限核准用户
的存取权限一般用户
的存取权限
- 使用信息类
- 文件的
建立日期和时间
- 文件
上一次修改的日期和时间
当前使用信息
。- 当前已打开该文件的进程数
- 是否被其它进程锁住
- 文件在内存中是否已被修改但尚未拷贝到盘上等。
- 文件的
2、索引结点
1️⃣ 问题背景:传统目录检索的瓶颈
🔍 传统FCB目录结构(如FAT):
每个FCB完整存储(文件名+文件描述信息),占用空间大。
例:FCB=64B,盘块=1KB → 每块仅存16个FCB。检索时需逐块调入内存,依次比对文件名。
⏳存在性能问题:若目录占用N
个盘块,平均需(N+1)/2
次磁盘I/O。
例:640个FCB → 40块 → 平均20次磁盘访问!🐢
2️⃣ 优化方案:UNIX的i-node设计
核心思想:
分离文件名与文件元数据
,减少目录检索时的磁盘I/O!📂
i-node(索引结点)结构
组成部分 作用 节省点 文件名
文件标识(短字符串) 仅存14B(UNIX为例) i-node指针
指向文件元数据
(物理地址/权限等)2B指针 → 取代完整FCB!✨ 文件元数据
存储在独立的i-node中(磁盘另存) 检索时不加载,按需读取
3️⃣ 磁盘索引结点
存放在磁盘上的索引结点。每个文件有唯一的一个磁盘索引结点
💾 磁盘i-node的七大核心字段
字段 | 作用 | 🌟 特别说明 |
---|---|---|
文件主标识符 |
记录文件所有者(用户/组) | ls -l 看到的user:group 就是它! |
文件类型 |
标明是普通文件、目录、设备文件等 | - 普通文件,d 目录,c 字符设备… |
文件存取权限 |
控制用户/组/其他用户的读(r)、写(w)、执行(x)权限 | chmod 755 修改的就是它 🔒 |
文件物理地址 |
13个地址项(iaddr(0)~iaddr(12) )以直接或间接方式给出数据文件所在盘块的编号 |
混合索引结构 → ⚡️ 支持大文件+高效访问 |
文件长度 |
文件实际大小(字节为单位) | du 和ls -l 显示的数据源 📏 |
文件连接计数 |
硬链接数量(多少目录项指向本i-node) | 为0时文件真正删除! ♻️ |
文件存取时间 |
记录最后访问、修改、i-node变更时间 | touch 命令会更新这些时间 ⏰ |
4️⃣ 内存索引结点
🏃 为什么需要内存i-node?
- 🐌 磁盘i-node存储在硬盘,每次访问都要读盘 → 慢!
- 🚀 内存i-node加载到RAM,减少磁盘I/O → 快!
💡 核心思想:高频访问的元数据 缓存在内存,避免重复读盘 ⚡
🔍 内存i-node五大新增字段
字段 | 用途 | 🌟 场景举例 |
---|---|---|
1. i-node编号 | 唯一标识内存中的i-node | 内核通过编号快速查找缓存 🔎 |
2. 状态标志 | 标记是否被 锁定(locked) 或 修改(dirty) | 写文件时加锁,防止并发冲突 🚧 |
3. 访问计数 | 记录多少进程正在使用此i-node(Open计数) | 计数=0时可安全释放缓存 ♻️ |
4. 设备号 | 指向文件所属的文件系统(如/dev/sda1 ) |
跨设备文件操作时定位磁盘位置 💾 |
5. 链接指针 | 维护空闲链表和哈希队列(加速i-node查找) | 内核通过哈希表快速定位内存i-node ⚡ |
🧠 内存i-node vs. 磁盘i-node
特性 | 磁盘i-node | 内存i-node(新增字段) |
---|---|---|
存储位置 | 磁盘 | 内存(进程打开文件时加载) |
核心作用 | 持久化存储元数据 | 加速访问 + 动态管理文件状态 |
生命周期 | 文件存在即存在 | 文件打开时创建,关闭后可能释放 |
7.3.2 简单的文件目录
1、单级文件目录
🧩 基本概念
单级文件目录(Single-Level Directory)
是最简单的文件目录结构,整个系统只有一张目录表
,每个文件占一个目录项
,包含:
- 📝 文件名(
如:report.txt
) - 🏷️ 文件扩展名(
如:.txt、.exe
) - 📏 文件长度(大小)
- 🏗️ 文件类型(文本、二进制、目录等)
- 🗺️ 文件物理地址(存储在磁盘的哪个位置)
- 🔒 其他属性(如只读、隐藏等)
- ✅ 状态位(1=已占用,0=空闲)
📌 特点:
- 每个文件
唯一对应
一个目录项 文件名必须唯一
(按名存取 - 不能有重名)- 查找方式:
线性扫描
全部目录项
⚡ 工作流程
创建文件(Create)
📂1️⃣ 检索全部目录项 → 检查文件名是否已存在(避免重名)
2️⃣ 找空白目录项(状态位=0)
3️⃣ 填入文件名、属性,并置状态位=1
删除文件(Delete)
🗑️1️⃣ 查找目标目录项
2️⃣ 释放文件占用的存储空间(如磁盘块)
3️⃣ 清空目录项,状态位=0
✅ 优点
- 简单易实现 🛠️
- 满足最基本功能:按名存取(
open("a.txt")
能定位到文件)
❌ 缺点
查找速度慢
🐌:平均需扫描 N/2 个目录项(N=文件总数)不允许重名
🔥:在多用户/多任务环境下难以避免冲突无法共享文件
🤝:所有用户必须用相同文件名访问同一文件,不能个性化命名
🚀 适用场景
单用户环境
(如早期DOS系统) 🖥️文件数量极少
📉
2、两级文件目录
🧩 基本概念
两级文件目录(Two-Level Directory) 是为了解决单级目录的缺点而设计的。它在 主目录(MFD)下为每个用户单独建立用户文件目录(UFD)
,形成两级结构:
主文件目录(MFD)
:记录所有用户信息(用户名 + 指向UFD的指针) 📁用户文件目录(UFD)
:用户自己的文件列表(类似单级目录,但只属于该用户) 🗂️
✅ 核心思想:用户隔离
→ 每个用户有自己的“私人文件夹”,互不干扰!
⚡ 工作流程
创建文件(Create)
📂1️⃣ 查MFD → 找到对应用户的UFD指针
2️⃣ 在UFD中检查文件名是否冲突(只需检查自己的文件,不用管其他用户)
3️⃣ 分配空白目录项,填入文件信息,状态位=1 ✅
删除文件(Delete)
🗑️1️⃣ 查MFD → 定位到UFD
2️⃣ 在UFD中找到目标文件,释放存储空间
3️⃣ 清除目录项,状态位=0
访问文件(Open)
🔍- 路径形式:
/用户名/文件名
- 路径形式:
✅ 优点(对比单级目录)
改进点 | 两级目录解决方案 | 实际效果 |
---|---|---|
查找速度快 |
只需查 n(MFD) + m(UFD) 次 | 从单级的 N=n×m → 降到 n+m |
允许用户重名 |
不同用户的UFD可含同名文件(如 A/test 和B/test ) |
用户A和B的 temp.txt 共存! |
支持基础共享 |
可通过系统链接【让不同用户的不同文件名指向同一个物理文件】 让不同用户访问同一物理文件 |
用户A的 data.txt → 用户B的 backup.txt |
❌ 缺点
用户隔离太强
🚧:合作开发时,跨用户访问文件需手动配置权限或链接,不够灵活。共享仍有限
🔗:需显式设置共享文件表或符号链接,天然不支持多级协作。
7.3.3 树形结构目录(Tree-Structured Directory)
1、树形目录
🧩 基本概念
树形目录(Tree-Structured Directory) 是现代OS最常用的文件组织方式,将文件系统组织为一棵倒置的树:
根目录(/)
🏠:最顶层的唯一目录(如Linux的/
、Windows的C:\
)节点(子目录)
📂:树的中间层(文件夹),可无限嵌套叶节点(文件)
📄:树的末端(实际数据文件)
⚡ 核心特性
单根唯一性
🎯- 全系统
只有一个根目录
,所有文件和目录都从根派生。 - 例如:Linux中绝对路径
/home/user/file.txt
必须从/
开始。
- 全系统
单父依赖
👨- 每个文件/目录
只能有一个父目录
,避免环路(类似单继承)。 - 例外:通过链接(硬链/软链)实现多路径访问。
- 每个文件/目录
混合存储能力
🔄- 目录项可以是:
- 子目录的FCB(📂 如
/home/user/Documents/
) - 数据文件的FCB(📄 如
/home/user/report.txt
)
- 子目录的FCB(📂 如
- 用
标志位
区分类型(如d
代表目录,-
代表文件)。
- 目录项可以是:
/ (根目录)
├── home/ (用户主目录)
│ ├── alice/ (子目录)
│ │ ├── Documents/ (子目录)
│ │ │ └── project.docx (数据文件)
│ │ └── notes.txt (数据文件)
│ └── bob/ (子目录)
│ └── Downloads/ (子目录)
└── etc/ (配置文件目录)
└── passwd
2、路径名和当前目录
🚩 路径名(Path Name)
在树形目录中,每个文件的绝对路径是从根目录(/
)出发的唯一访问路径,所有目录和文件名用 /
连接。
📌 当前目录/工作目录(Current Directory)
解决方案:为每个进程设置工作目录(Working Directory),默认从此目录出发解析路径。
路径类型 | 定义 | 示例(当前目录=/home/alice ) |
特点 |
---|---|---|---|
绝对路径 🔵 |
从根目录 / 开始的完整路径 |
/home/alice/Documents/notes.txt |
唯一但冗长 |
相对路径 🟢 |
从当前目录开始的缩写路径 | Documents/notes.txt 或 ../bob/file |
简洁需上下文 |
特殊符号:
.
:当前目录(如./file
= 当前目录下的file
)..
:父目录(如../file
= 上级目录中的file
)
⚖️ 树形目录的优缺点
🌟 优势
:
清晰层次
🗂️:不同用户/项目分属不同子树(如/home/user1/
vs/var/log/
)。权限隔离
🔐:可为每层目录设置不同访问权限(如chmod 750 /home/secret/
)。
⚠️ 缺点
:
逐级访问开销
⏳- 查找
/a/b/c/file
需读3次目录(a→b→c
),增加磁盘I/O。 - 解决方案:通过符号链接(
ln -s
)缩短访问路径。
- 查找
相对路径陷阱
🌀:若当前目录变化(如cd ..
),相同相对路径可能指向不同文件!- 树形结构不便于实现文件的共享
系统 | 根目录 | 用户目录范例 | 关键命令 |
---|---|---|---|
Linux | / |
/home/username/ |
pwd (显示当前目录) |
Windows | C:\ |
C:\Users\Username\ |
cd (切换目录) |
3、目录操作
📌 创建目录
作用:在用户目录(UFD)或其子目录中新建目录或文件。
规则:
检查当前目录下是否有同名文件/目录,避免冲突(❌
mkdir
或touch
重名会报错)。示例:
mkdir new_folder # 创建目录 touch new_file.txt # 创建文件
🗑️ **删除目录 **
情况 | 处理方法 | 示例命令 |
---|---|---|
空目录 | 直接删除(无风险✅) | rmdir empty_dir |
非空目录 | 两种方式: ① 递归删除所有子文件和目录( rm -r ) ② 禁止删除非空目录,如要删除必须采取递归调用方式来将其删除(如早期 MS-DOS) |
rm -r non_empty_dir (⚠️rm -rf / 危险!) |
🔄 改变当前目录
作用:切换工作目录,简化相对路径操作。
常用命令:
cd /home/user/Documents # 绝对路径切换 cd ../Downloads # 相对路径(返回上级再进入Downloads) cd ~ # 回到用户主目录(如 /home/username)
查看当前目录:
pwd # 输出:/home/user/Documents
➡️ 移动目录/文件
作用:调整目录结构,修改文件路径。
命令:
mv old_dir new_location/ # 移动目录(路径变化) mv file.txt ../new_name.txt # 移动并重命名
风险:移动系统关键目录(如
/usr/bin
)可能破坏依赖关系💥!
🔗 链接操作 (文件共享)
链接类型 | 特点 | 命令示例 |
---|---|---|
硬链接 | 共享 i-node,删除原文件不影响硬链接(⚠️ 不可跨文件系统) | ln source.txt hard_link |
软链接 | 类似快捷方式,存储目标路径(✅ 可跨文件系统,原文件删除后失效) | ln -s source.txt soft_link |
🔍 查找文件
精确匹配
(指定完整文件名):find /home -name "report.pdf" # 在 /home 下搜索 report.pdf
模糊匹配
(通配符*
或?
):find . -name "*.log" # 当前目录及其子目录中所有 .log 文件
按类型查找
(目录/文件/链接):find /var -type d # 查找 /var 下所有目录
7.3.4 目录查询技术
当用户请求访问文件时(如cat report.txt
),系统执行以下流程:
- 1️⃣
文件名解析
- 用户提供文件名 → 系统在目录结构中搜索该文件。
- 查找方式:
- 绝对路径:从根目录
/
逐级匹配(如/home/user/report.txt
)。 - 相对路径:基于当前目录检索(如
./docs/report.txt
)。
- 绝对路径:从根目录
- 🚦 关键目标:找到文件的控制块(FCB)或索引结点(i-node)。
- 2️⃣
获取文件元数据
- 通过FCB/i-node获取文件关键信息:📏 大小 | 🔒 权限 | 📅 时间戳 | 🧩 物理地址(磁盘块号)
- 3️⃣
定位磁盘数据
- 系统根据 FCB/i-node 中的物理地址,计算出文件在磁盘上的具体位置(柱面/扇区)。
- 4️⃣
读取文件到内存
- 磁盘驱动程序执行 I/O 操作:
- 🚀 寻道:磁头移动到目标位置(机械硬盘有延迟)。
- ⚡ 传输:数据从磁盘读入内存缓冲区。
- 用户态交付:最终将文件内容返回给用户程序(如
cat
显示内容)。
- 磁盘驱动程序执行 I/O 操作:
1、线性检索法
🔍 核心概念
线性检索法(顺序检索法)是最基础的目录搜索策略,通过逐级比较文件名在目录中查找目标文件,适用于单级目录和树形目录结构。
单级目录检索(简单但低效)
📌 流程:
- 输入:用户提供文件名(如
report.txt
)。 - 检索:系统依次遍历目录项,逐一比对文件名。
- 结果:
- ✅ 找到 → 返回文件控制块(FCB)或 i-node。
- ❌ 未找到 → 报错“文件不存在”。
📌 缺点:效率低:目录项多时耗时(O(n) 时间复杂度)。
🌳 树形目录检索(多级路径解析)
📌 示例路径:/usr/ast/mbox
1️⃣ 解析根目录
/
读入分量名
usr
→ 与根目录项顺序比较。匹配结果:找到
usr
目录项 → 获取其 i-node 号(如 6)。定位数据:根据 i-node 6 读取
usr
目录的物理盘块(如 132号)。
2️⃣ 解析第二级
/usr/ast
读入分量名
ast
→ 与 132 号盘块中的目录项顺序比较。匹配结果:找到
ast
→ 获取其 i-node 号(如 26)。定位数据:根据 i-node 26 读取
/usr/ast
的盘块(如 496号)。
3️⃣ 解析最终文件
/usr/ast/mbox
读入分量名
mbox
→ 与 496 号盘块中的目录项顺序比较。匹配结果:找到
mbox
→ 获取其 i-node 号(如 60)。成功:i-node 60 中存储了文件物理地址,检索完成!
⚠️ 中断条件:
任意一级匹配失败(如ast
不存在) → 立即终止并返回 “文件未找到”。
2、Hash 方法
🔍 核心思想
Hash 方法通过 文件名 → Hash值 → 快速定位目录项
,显著提升检索效率(理想情况下O(1)),适用于大目录场景。但需处理Hash冲突和通配符兼容性问题。
Hash 检索流程
📌 无冲突场景(理想情况)
输入文件名
:如report.txt
。计算Hash值
:通过Hash函数(如MD5、CRC32)转换为索引值。hash("report.txt") % 100 → 索引值=42
定位目录项
:直接访问目录表的第42项。- ✅ 匹配成功 → 获取文件物理地址。
- ❌ 目录项为空 → 文件不存在。
⚡ 优势:只需一次计算和访问,速度极快!
📌 冲突处理(关键难点)
当不同文件名计算出相同Hash值时,系统按以下规则解决:
检查目录项
:若已存文件名 ≠ 目标名 → 发生冲突!重新Hash
:新索引 = (原Hash值 + 常数) % 目录长度
(该 常数应与目录的长度值互质)。- 重复步骤1,直到找到匹配或空项。
🌰 举例:
report.txt
和data.log
的Hash值均为42:
- 第一轮查42 → 存的是
data.log
(不匹配)。- 第二轮查
(42+1)%100=43
→ 找到report.txt
(成功)!
限制与兼容性
场景 | 处理方法 | 原因 |
---|---|---|
文件名含通配符(如*.txt ) |
退化为线性检索 🔄 | Hash无法处理模糊匹配 |
目录动态扩容 | 需Rehash所有文件 🚧 | Hash值依赖目录长度 |
⚠️ 注意:Hash函数选择:应尽量均匀分布(如SHA-1),减少冲突概率。
性能对比
方法 | 时间复杂度 | 适用场景 |
---|---|---|
线性检索 | O(n) | 小目录/含通配符 |
Hash检索 | O(1)* | 大目录/精确文件名匹配 |
*注:O(1)为平均情况,冲突频繁时可能退化。
7.4 文件共享
7.4.1 基于有向无循环图实现文件共享
1、有向无循环图 DAG(Directed Acyclic Graph)
🔍 核心概念
有向无环图(DAG) 是一种允许文件/子目录被多个父目录引用的目录结构。
- 问题背景:树形目录中,文件共享必须通过属主目录(非对称共享❌)。
- DAG解决方案:文件可被多个目录直接链接
📌 如何建立共享链接?
硬链接(物理地址拷贝)
- 操作:将文件的
物理盘块号
复制到父目录项中。 - 风险:
- 若某个用户对文件
追加内容仅对操作者可见
,其他用户无法共享更新部分! - 数据不一致:多个父目录可能指向不同版本的文件内容。
- 若某个用户对文件
- 适用场景:适合
只读文件
💣 致命缺陷:硬链接破坏了共享文件的统一性!
- 操作:将文件的
符号链接(软链接)
- 操作:父目录中存储
文件的路径名
而非物理地址。 - 优势:所有父目录访问同一文件,
追加内容对所有用户可见
。 - 代价:需要额外解析路径,性能略低。
- 适用场景:适合
协作文件
- 操作:父目录中存储
2、利用索引结点 - 硬链接
📂 传统目录 vs 索引结点方案
传统目录 | 索引结点 | |
---|---|---|
存储内容 | 直接把文件地址、属性存目录里🗂️ | 目录只存文件名+i-node指针👉📍 |
共享问题 | 硬链接导致更新不同步🔀 | 所有人通过i-node访问同一文件🔗 |
🔑 核心结构
count计数器
:记录有多少目录指向该文件
如何解决共享问题
多用户的文件目录中都设置有指向共享文件的索引结点指针。此时,由任何用户对共享文件所进行的操作,都将引起其相应结点内容的改变
删除文件:通过
count
确保安全删除🔒,如何系统收费始终由创建者(count=1时)负责💰。【count=2时,创建者不能删除该文件, 因为若删除了该文件,也必然删除了该文件的索引结点,这样便会使另一个使用者的指针悬空
】
7.4.2 利用符号链接实现文件共享
1、利用符号链接(Symbolic Linking)的基本思想
符号链接允许 一个文件有多个“父目录
”,但 只有一个主父目录
,其他都是快捷方式
符号链接 = 创建“文件快捷方式”
📎,存储目标文件路径,访问时自动跳转!
传统树结构 | 符号链接结构 | |
---|---|---|
父目录类型 | 所有连接都是实线(真实父目录) 🏗️ | 1个实线(主父目录)+ N个虚线(符号链接) 🪢 |
2、如何利用符号链实现共享
📂 示例:让 D5 共享 D6 的文件 F8(实现符号链接)
创建符号链接文件
💻- 系统在目录
D5
下创建LINK 类型
文件,名称与原文件相同
(F8
)。 - 该文件**
内容
仅为真实文件路径
**(如/D6/F8
)。
# Linux命令行示例:ln -s ln -s /D6/F8 D5/F8 # 创建符号链接
- 系统在目录
文件结构变化
📝目录/文件 类型 存储内容 /D6/F8
真实文件 文件数据🔢 /D5/F8
符号链接 路径 /D6/F8
🛣️用户访问流程
🔄- 用户 B 打开
/D5/F8
→ 系统发现是符号链接(不是真实文件)。 - 操作系统自动解析路径
/D6/F8
,并访问真实文件。 - 最终读写操作 作用在
/D6/F8
上,实现共享!
- 用户 B 打开
即使软链接指向的共享文件已被删除,Link型文件依然存在,只是通过 Link 型文件中的路径去查找共享文件会失败(找不到对应目录项)
3、利用符号链实现共享的优点
1️⃣ 文件主(Owner)绝对掌控
👑
索引结点(i-node)指针
仅有**文件主
**持有,而共享用户只能通过路径访问
📌。- 文件主
删除文件
后🗑️:【无耦合,安全删除 🔒】- 其他用户的
符号链接自动失效
❌(不会出现“悬空指针”问题)。 - 系统检测到文件不存在,
自动删除无效符号链
,避免累积垃圾。
- 其他用户的
2️⃣ 支持跨系统/网络共享
🌐
- 符号链可指向任何有效路径,包括:
- 同一磁盘不同目录 📂
- 不同磁盘/分区 💾
- 网络文件(如 Web 链接🌍)
3️⃣ 灵活权限管理
🛡️
- 用户只需 路径访问权限,无需持有原文件的 i-node。
适合多用户环境
👥(如服务器共享文件)。
4、利用符号链的共享方式存在的问题
性能略低
🐢:每次访问需 解析路径(比硬链接多一次 I/O)。死链(Dangling Link)
:若原文件被删,需手动或定期清理无效符号链(可用find -xtype l
查找)。存储开销
💾:每个符号链占用 1 i-node + 少量空间(存路径字符串)。
7.5 文件保护
威胁类型 | 典型案例 | 防护措施 | 具体实现技术/工具 |
---|---|---|---|
1. 人为因素 👤 | - 误删文件 - 恶意篡改 - 越权访问 | 存取控制机制 🚪 | - 权限分档(rwx ) - ACL访问控制列表 - 多因素认证 |
2. 系统因素 💻 | - 磁盘故障 - 系统崩溃 - 软件漏洞 | 系统容错技术 ♻️ | - RAID磁盘阵列 - 事务日志(Journaling) - 热备组件 |
3. 自然因素 🌌 | - 磁盘老化 - 磁场干扰 - 物理损坏 | 后备系统 🗄️ | - 定期备份(全量/增量) - 异地容灾 - 数据校验 |
口令保护
口令一般
存放在文件对应的 FCB
或索引结点
中。用户访问文件前需要
先输入“口令”
,操作系统会将用户提供的口令与FCB中存储的口令进行对比
,如果正确,则允许该用户访问文件。优点: 保存口令的
空间开销不多
,验证口令的时间开销也很小
。缺点: 正确的“口令”存放在系统内部,
不够安全
。
密码保护
- 使用某个“密码”对文件进行加密,在访问文件时需要提供正确的“密码”才能对文件进行正确的解密。
- 优点: 保密性强,
不需要在系统中存储“密码”
- 缺点: 编码/译码,或者说
加密/解密要花费一定时间
7.5.1 保护域(Protection Domain)
1、访问权
1️⃣ 基本概念
- 定义:进程对某个对象(Object) 执行特定操作的权限。【由**系统控制**进程对对象的访问】
- 对象类型:
硬件对象
💻:磁盘、打印机、内存等。软件对象
📂:文件、程序、数据库等。
- 权限示例:文件 → 读(R)、写(W)、执行(X)。
2️⃣ 访问权的表示方法
🧮 例子:进程对文件 report.txt
有 读写权限 → (report.txt, {R, W})
📄✏️
2、保护域
1️⃣ 基本概念
- 定义:保护域(Domain)是
进程对一组对象访问权的集合
,规定了进程能访问的对象和操作范围。 - 核心规则:🔐
进程只能在指定的域内操作
,不能跨域越权!
2️⃣ 保护域的特性
特性 | 说明 | 例子 🖼️ |
---|---|---|
对象集合 📦 | 一个域包含一组可访问的对象(文件、打印机等)。 | 域1:文件F、打印机PR1 |
权限绑定 🔗 | 每个对象在域中有明确的权限(如读、写、执行)。 | 域1中:文件F1可读,文件F2可读写 |
跨域共享 🤝 | 同一对象可出现在多个域中(权限可能不同)。 | 打印机PR1同时属于域2和域3 |
3️⃣ 保护域的作用
最小权限原则
🎯:限制进程仅拥有必要权限,避免过度授权。隔离性
🧊:防止错误/恶意进程破坏其他域的资源。灵活共享
♻️:通过跨域分配对象,实现安全共享。
3、进程和域间的静态联系
- 静态域:进程
整个生命周期
仅绑定一个固定保护域
,权限无法动态调整
。 - 问题:🚨
权限过度分配
!进程可能获得实际不需要的访问权(如同时拥有磁带机和打印机权限)。 - 特性:
权限固定
:进程启动时就拥有域内所有对象的权限,无法中途释放/变更。资源浪费
:域需包含进程全程可能用到的所有对象(即使某阶段不需要, 存在闲置权限)。
4、进程和域间的动态联系方式
- 动态域:进程在不同的
运行阶段
可以关联不同的保护域
(一对多联系)。 - 核心优势:🎯
按需分配权限
!进程只在当前阶段拥有必要的最小权限。 - 特性:
阶段化权限
:进程生命周期被划分为多个阶段,每个阶段绑定一个域。最小权限
:域仅包含当前阶段所需的对象。
7.5.2 访问矩阵
1、基本的访问矩阵
🔹 基本概念
访问矩阵(Access Matrix)
是表示保护域(Domain)
和对象(Object)
之间权限关系的数据结构。行(Row) = 域(Domain)
:代表进程执行的权限环境(如D₁
,D₂
)。列(Column) = 对象(Object)
:代表系统中的资源(如文件F₁
、打印机Printer 1
)。矩阵项(Cell) = 访问权(Access Rights)
:access(i, j)
表示域Dᵢ
对对象Oⱼ
的操作权限(如R
-读,W
-写,E
-执行)。
访问矩阵示例
域\对象 | F₁ | F₂ | F₃ | F₄ | F₅ | F₆ | Printer 1 | Plotter 2 |
---|---|---|---|---|---|---|---|---|
D₁ | R | R, W | ||||||
D₂ | R | R,W,E | R, W | W | ||||
D₃ | R,W,E | W | W |
是由 三个域 和 8个对象 所组成的:
- 进程在域D1中运行时,它能读文件F1、读和写文件F2。
- 进程在域D2中运行时,它能读文件 F3、F4和F5,以及写文件F4、F5和执行文件F4,此外还可以使用打印机 1。
- 进程在域D3中运行时,才可使用绘图仪 2。
2、具有域切换权的访问矩阵
Switch 权限(S)
:在访问矩阵中新增一项,表示域间的切换权。
- 仅当
switch_access(i, j) = S
时,进程才能从 域Dᵢ
切换到Dⱼ
。 - 切换权**
由系统或管理员授予
**,避免进程随意越权。
具有域切换权的访问矩阵示例
域\对象 | F₁ | F₂ | F₃ | F₄ | F₅ | F₆ | Printer 1 | Plotter 2 | 域 D₁ | 域 D2 | 域 D3 |
---|---|---|---|---|---|---|---|---|---|---|---|
D₁ | R | R, W | S | ||||||||
D₂ | R | R,W,E | R, W | W | S | ||||||
D₃ | R,W,E | W | W |
允许在域D1中的进程切换到域D2中;允许在域D2中的进程切换到域D3中。
7.5.3 访问矩阵的修改
1、拷贝权(Copy Right)
拷贝权(Copy Right) 是一种 动态权限扩展机制
,允许进程将 某个域中对某对象的访问权复制到其他域
中,但会对权限的传播进行限制,以防止无限扩散风险。
关键点:
拷贝标记(*)
:在访问权(如R*
、W*
)中,*
表示该权限可被拷贝至其他域。限制拷贝
:拷贝后生成的权限不带*
(如R*
→R
),阻止进一步扩散。- 目的:实现权限的
可控共享
,避免权限滥用。
域\对象 F₁ F₂ F₃ D₁ E W* D₂ E R* E D₃ E 运行在D2域中的进程可以将其对文件F2的读访问权扩展到域 D3中去,使在域D3中运行的进程也具有对文件F2的读访问权。
运行在域D1中的进程可以将其对文件F3的写访问权扩展到域 D3中去,使在域D3中运行的进程也具有对文件F3的写访问权。
域\对象 F₁ F₂ F₃ D₁ E W* D₂ E R* E D₃ E R W
2、所有权(Owner Right)
所有权(Owner Right)
赋予进程对某对象 完整的控制权
,包括:
增删权限
:可以修改其他域对该对象的访问权。- 动态权限管理:无需管理员介入,拥有者可自主调整权限。
所有权用 O
标记在访问矩阵中(如 access(i,j) = O
),表示域 Dᵢ
对对象 Fⱼ
拥有所有权。
域\对象 F₁ F₂ F₃ D₁ O,E W D₂ R*,O R*,O,W D₃ E 在域 D1中运行的进程(用户)是文件F1的所有者,它能增加或删除在其它域中的运行进程对文件F1的访问权。
如下表:在域 D1中运行的进程删除了在域D3中运行的进程对文件F1的执行权;
在域 D2中运行的进程(用户)是文件F2和文件F3的拥有者, 该进程可以增加或删除在其它域中运行的进程对这两个文件的访问权。
如下表:在域 D2中运行的进程增加了在域D3中运行的进程对文件F2和F3的写访问权。
域\对象 F₁ F₂ F₃ D₁ O,E D₂ R*,O R*,O,W D₃ W W
3、控制权(Control Right)
拷贝权和所有权都是用于改变矩阵内同一列的各项访问权的,或者说,是用于改变在不同域中运行的进程对同一对象的访问权的。
控制权(Control Right)
可用于改变矩阵内同一行中(域中)的各项访问权,亦即,用于改变在某个域中运行的进程对不同对象或域的访问权的。
权限标记
:access(i,j) = Control
,表示域 Dᵢ
可以控制域 Dⱼ
的权限。
域\对象 | F₁ | F₂ | F₃ | F₄ | F₅ | F₆ | Printer 1 | Plotter 2 | 域 D₁ | 域 D2 | 域 D3 |
---|---|---|---|---|---|---|---|---|---|---|---|
D₁ | R | R, W | |||||||||
D₂ | R | R,W,E | R, W | W | Control | ||||||
D₃ | R,W,E | W | W |
在 access(D₂,D3)中包括了控制权,则一个在域 D2中运行的进程能够改变对域D3内各项的访问权。
7.5.4 访问矩阵的实现
1、访问控制表(Access Control List)
ACL
:对 访问矩阵按列(对象)划分
,为 每一列建立一张访问控制表 ACL
。在该表中,已把矩阵中属于该列的 所有空项删除
,此时的访问控制表是由一 有序对(域,权集)所组成的
。
ACL(F₁) = { (D₁, {R, W}), (D₂, {R}), (D₃, {W}) }
域的两种实现方式
域类型 | 说明 | 示例场景 |
---|---|---|
用户 作为域 |
每个用户是一个域,权限绑定用户身份 | 用户A可读文件F,用户B可写文件F。 |
进程 作为域 |
每个进程是一个域,权限绑定进程身份 | 进程P₁可执行程序,进程P₂不可。 |
ACL的存储与查询
存储位置
- 文件系统:ACL 常存放在
文件的控制块(FCB)或 i-node中
。 - 数据库:作为对象的元数据。
权限查询流程
缺省 ACL(Default ACL)
是一种 预先定义的权限模板
,用于在新建子对象(文件/目录)时自动继承权限。
- 核心功能:当在目录下创建新文件或子目录时,系统会
自动将缺省 ACL 的权限赋予新对象
,无需手动设置。
2、访问权限(Capabilities)表
访问权限表
:访问矩阵按行(即域)划分
,便可由 每一行构成一张访问权限表
。换言之,这是由一个域对每一个对象可以执行的一组操作所构成的表。表中的每一项即为该域对某对象的访问权限。
当域为用户(进程)、对象为文件时,访问权限表便可用来描述一个用户(进程) 对每一个文件所能执行的一组操作。
访问权限表的组成(三字段)
字段 | 说明 |
---|---|
类型 | 对象类型(如文件、打印机、目录)。 |
权力 | 域对该对象的操作权限(如 读 、写 、执行 )。 |
对象 | 指向对象的指针(如 UNIX 的 i-node 编号)。 |
🛡️ 安全性实现
禁止用户直接访问权限表
- 权限表存储在内核或受保护的
系统专用区
,用户进程无法直接修改。 - 只有通过
合法性检查的系统调用
才能查询或更新权限。
- 权限表存储在内核或受保护的
动态权限绑定流程
🚀 对比ACL与权限表(Capabilities)
特性 | 访问控制表(ACL) | 访问权限表(Capabilities) |
---|---|---|
视角 | 对象为中心(文件→用户权限) | 域为中心(进程→可访问对象) |
查询效率 | 对象被访问时需遍历ACL | 进程直接持有权限表,无需重复检查 |
7.6 文件存储空间管理 - 空闲磁盘块管理
7.6.1 存储空间的划分与初始化
7.6.2 存储空间管理
空闲表法
空闲链表法
位示图法
成组链接法
空闲表法、空闲链表法不适用于大型文件系统,因为空闲表或空闲链表可能过大。UNIX系统中采用了成组链接法对磁盘空闲块进行管理。
基本原理
空闲块
根据大小划分成若干个组
。【UNIX默认采用每组100个空闲块的配置】- 每个组的空闲块通过
链表进行连接
,链表中的每个节点表示一个空闲块。 - 当系统需要分配存储空间时,首先根据请求的大小选择合适的链表,然后从链表中分配空闲块。
- 当块被释放时,它会被返回到相应大小的链表中。
组的划分
:通常,有几种不同的划分策略:
按固定大小划分
:每个组管理固定大小的块。例如,组1管理1KB的块,组2管理2KB的块,组3管理4KB的块,以此类推。按块大小范围划分
:根据一定的大小范围进行划分,每个组管理一个大小范围内的块。例如,组1管理1KB到2KB的块,组2管理2KB到4KB的块等。按指数划分
:将空闲块的大小按照指数级别划分,比如2的倍数的块(2KB, 4KB, 8KB等)
7.7 虚拟文件系统和文件系统挂载
普通文件系统 vs 虚拟文件系统
文件系统挂载
文件系统挂载(mounting),即文件系统安装/装载–如何将一个文件系统挂载到操作系统中
?
① 在VFS中注册新挂载的文件系统
。内存中的挂载表(mount table)包含每个文件系统的相关信息,包括文件系统类型、容量大小等。
② 新挂载的文件系统,要向VFS提供一个函数地址列表
③ 将新文件系统加到挂载点(mountpoint)
,也就是将新文件系统挂载在某个父目录下
【windows 和C、D盘平级;Mac 在根目录下的Volumes文件夹下】
参考:
教材:
计算机操作系统(第四版) (汤小丹) (Z-Library).pdf
操作系统 (罗宇(清华大学出版社 2023年)) (Z-Library).pdf
视频: