操作系统复习

1引论

中断是异步异常，可能随时发生（IO、始终信号）

软件和硬件都可以产生中断。

同步异常是相同条件下可重现的一场（内存错误，调试，被零除）

系统调用也视作同步异常，或trap（陷阱）

系统

把用户提交的作业成批送入计算机，由作业调度程序自动选择运行。

缩短作业交接时间、减少处理机空闲等待

联机批处理系统在作业输入输出时，CPU忙等

多道程序系统：允许多个程序同时进入内存，在CPU交替运行

多道批处理系统：多道+成批；系统吞吐量大，资源利用率高；平均周转时间长，不能提供交互能力。成批：作业一旦进入系统，用户就不能直接干预其作业的运行

分时系统：CPU处理时间分为时间片，多用户，可交互，用户间相互独立，可对用户输入及时响应

分布式系统：一体化系统，由网络底层支持，多台机器统一管理形成的单一透明系统

实时系统：及时响应，安全可靠，整体性强

2启动

BootLoader

开机第一个程序

常用U-Boot

分为两部分，

stage1：依赖于cpu体系结构的代码，用汇编语言来实现

stage2：更多复杂功能，可读性、可移植性好，用C语言实现

MIPS，启动！

地址空间4G

kuseg：2G用户态可用地址，需要被MMU转化

kseg0：512M，对于无MMU的系统，用于存程序和数据，对于有MMU的系统，用于存操作系统核心，几乎全部kseg0都需要通过cache存取

kesg1：512M，唯一能在系统启动时工作的地址空间，不需要cache

kesg2：1G，需要MMU转换，只能在核心态使用

启动1

启动2

调用board.c初始化

内存划分、堆栈初始化，把代码从flash搬到ram上

引导Linux系统

linux 内核启动的第一个阶段从 /arch/mips/kernel/head.s文件开始的

内核入口kernel_entry()，先初始化内核堆栈，把内核映像的未初始化数据清零，跳转到**start_kernel()**启动

X86，启动！

比MIPS麻烦很多

▪ 第一步——加载BIOS：硬件自检，读取启动顺序，

▪ 第二步——读取MBR：主引导记录，在磁盘0磁头0磁道第一个扇区，包含了已安装的操作系统的启动加载器(BootLoader)和驱动器的逻辑分区信息

▪ 第三步——Boot Loader：操作系统内核运行之前运行的一段小程序，初始化硬件，建立内存空间映射图

▪ 第四步——加载内核：根据grab设定的路径读取内存映像并存在内存，初始化硬件设备，为内核程序执行建立环境

▪ 第五步——用户层init依据inittab文件来设定运行等级：0，关机；1，单用户；2，无网络多用户；3，有网络多用户；4，保留未使用；5，有网络有X-Window支持的多用户；6，重启

▪ 第六步－－init进程执行rc.sysinit：设定PATH、网络配置、启动swap分区，设定/proc

▪ 第七步－－启动内核模块

▪ 第八步－－执行不同运行级别的脚本程序

▪ 第九步－－执行/etc/rc.d/rc.local：Linux留给用户自己个性化设置和启动的地方

▪ 第十步－－执行/bin/login程序，进入登录状态

3内存

Elf头

e_ident Elf标志

e_type 文件类型

e_phoff:程序表头

e_shoff节表头

栈：存放、交换临时数据

堆：存放进程运行中动态分配的内存段

地址空间：逻辑地址的集合

存储空间：物理地址的集合

内存分配

顺序搜索

FitrstFit

空白区域按地址递增顺序连接，查找时选择第一块满足需求的块

NextFit

空白区域构成循环链，每次查找从上次查找结束的块开始，找到足够大的停

BestFit

选择大小满足要求且最接近于需求的存储

WorstFit

寻找最大空白区

索引搜索

快速适应算法（分类搜索法）

把空闲区按照容量大小分类，经常用到长度的空闲区设立单独的空闲区链表

内部碎片

分配给作业存储空间的没利用部分。入固定分区中的碎片。无法被整理，作业完成后释放

出现原因：单一连续区存储管理、固定分区存储管理

外部碎片

无法利用的小的空闲分区。需要用紧凑技术整理

紧凑技术

需要使用动态重定位

覆盖

把程序划分一系列功能相对独立的程序，执行时不要求装入一块内存

部分程序跑完再被下一部分覆盖

交换

把暂时不用的程序和数据从主存放到辅存，再把要用到移到主存

页式内存管理

页：把作业的地址空间分成大小相同的片

页框Frame：与页面相同大小的片，是主存的存储空间

逻辑地址32位

物理地址22位

一块4KB（12位块地址）

纯分页系统

必须把所有页一次撞到主存页框，如果页框不足，等待。

TLB

CPU 产生逻辑地址的页号，首先在快表中寻找若命中就找出其对应的物理块；若未命中，再到页表中找其对应的物理块，并将之复制到快表。若快表中内容满，则按某种算法淘汰某些页

每个TLB条目中还保存地址空间标识码ASID用于辨识进程

有效内存访问时间 = （TLB查询时间+单次内存访问时间） TLB命中率 + （TLB查询时间 + 2 * 单次内存访问时间） （1 - TLB命中率）**

哈希页表

虚拟页码作为哈希值，用虚拟页号与哈希链表每个元素第一个域比较，如果匹配则与相应帧号形成层物理地址

段式内存管理

一个作业的地址空间分段，每一段都连续，首地址为0

段表寄存器内容：段表始值、段表长度

1. 根据指令的性质来确定应该使用哪一个段寄存器（Segment Selector），例如转移指令中的地址在代码段，而取数据指令中的地址在数据段；

2. 根据段存器的内容，找到相应的“地址段描述结构“（Segment Descriptor），段描述结构都放在一个表（Descriptor Table）中（GDT或LDT等），而表的起始地址保存在GDTR、LDTR等寄存器中。

3. 从地址段描述结构中找到基地址（Base Address）；

4. 将指令发出的地址作为位移，与段描述结构中规定的段长度相比，看看是否越界；

5. 根据指令的性质和段描述符中的访问权限来确定是否越权；

6. 将指令中发出的地址作为位移，与基地址相加而得出线性地址（Linear Address）。

虚拟存储

为每个进程提供了一个大的、一致的、连续可用的和私有的地址空间

用户可执行文件、共享库的类型是file backed，磁盘上有记录

堆栈的类型是anonymous，磁盘上没记录

FIFO

先进的先被替换

Second Chance

被访问过会被移到FIFO的队列头

Clock

缺页时先检查指针指向的元素，若被访问过，删除访问标志，指针指向下一个；若未被访问过，换掉当前元素，设置访问标志，指针指向下一个

若不缺页，访问的页面访问位置1，指针不动

LRU

每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。栈底始终是最近最少使用页面的页面号

若换出页面是file backed类型：

1.且未被修改，则直接丢弃，因为磁盘上保存有相同的副本

2.被修改，直接写回原有位置

若换出页面是anonymous类型：

1.第一次换出/被修改写入Swap区，

2.若不是第一次且没被修改，丢弃

进程

进程时分配资源的基本单位

由进程控制块（PCB）、程序、数据构成

进程控制块包括：进程标识符、程序和数据地址、当前状态、现场保护区、同步与同步机制（信号量），优先级，资源清单，链接字

进程特征

并发：体现在进程的执行是间断性的

共享：体现在进程/线程之间的制约性

不确定性：进程执行的结果与其执行的相对速度有关，是不确定的

并发/并行

并发是一起执行

并行要求再不同处理器上一起执行

作业

是用户需要完成某项任务，要求计算机做的工作的集合

一个作业可以多个进程

由程序、数据、操作说明构成

原语

由若干条指令所组成的指令序列，来实现某个特定的操作功能

状态

进程上下文切换

通常由调度器执行，保存进程执行断点，切换内存映射

陷入/退出内核

CPU改变状态，由中断、异常、Trap引起，需要保存执行现场

线程

进程包含了两个概念：资源拥有者和可执行单元

现代操作系统将资源拥有者称为进程

可执行单元称为线程

线程是进程中的一个实体，是一个CPU调度和分派的单位，只有少量资源，与其他进程共享资源

一个进程可以拥有多个线程，而一个线程同时只能被一个进程所拥有

进程是资源分配的基本单位，

线程是处理机调度的基本单位，所有的线程共享其所属进程的所有资源与代码

用户级线程

线程在用户空间，内核不可感知，线程切换与内核无关，线程调度由应用决定，可运行在任何操作系统

内核级线程

内核可感知，可以在多个树立起上调度一个进程的多个线程，阻塞发生在线程级别，效率较低

混合线程

管道

对于管道两端的进程，管道就是一个文件

只存在在内存

无名管道

半双工，数据单向流动，只能用于父子进程或者兄弟进程

单独构成一种独立文件系统，只存在在内存中

有名管道

有名字，没亲缘关系的进程也能用

FIFO

不同于管道之处在于它提供一个路径名与之关联以FIFO的文件形式存在于文件系统中，调用路径就能用

先进先出

消息传递

seed(destination,&msg) receive(source,&msg)

调度

进程切换：

1. 保存处理器上下文
2. 用新状态和其他相关信息更新正在运行进程的PCB
3. 把进程移到合适的队列-就绪、阻塞
4. 选择另一个要执行的进程
5. 更新选中进程的PCB
6. 从选中进程重装入CPU上下文

高级调度：从用户工作流的角度，对作业的调度，时间上通常是分钟

中级调度：内外存交换，从存储器资源的角度，将当前需要的部分换到内存

低级调度：从CPU资源的角度，执行的单位，时间上通常是毫秒

关键术语

周转时间：作业从提交到完成所经历的时间

响应时间：用户输入请求到系统首次响应的时间

吞吐量：单位时间内所完成的作业数

批处理进程：无需与用户交互，无需很快的响应

**交互式进程：**与用户交互频繁，响应时间短

实时进程：有实施要求，不能被低优先级进程阻塞，响应时间短且稳定

吞吐量、平均等待时间和平均周转时间

吞吐量 = 作业数 / 总执行时间，（单位时间CPU完成作业数）

周转时间 = 完成时刻 - 提交时刻

带权周转时间 = 周转时间 / 服务时间（执行时间）

平均周转时间= 总周转时间 / 作业数量

平均带权周转时间 = 总带权周转时间 / 作业数量

批处理系统的调度算法

先来先服务FCFS

顾名思义，利于长作业，不利于短作业；利于CPU繁忙的作业，不利于I/O繁忙的作业

短作业优先SJF

先把短的优先处理，后来的短作业不抢占正在执行的。提高系统的吞吐量，但对长作业非常不利

最短剩余时间优先FRTF

抢占式，一个新旧徐的进程如果比当前进程完成时间更短，直接抢占。可能使长任务长时间得不到运行

最高响应比优先HRRF

每次选择作业投入运行时，先计算后备作业队列每个作业的响应比RP，选择最大的执行。

RP = ( 已等待时间+要求运行时间 ) / 要求运行时间

交互式系统的调度算法

时间片轮转RR

所有的就绪进程按照FCFS原则，排成1个队列；从受进程开始执行1个时间片，1个时间片结束时钟中断，将其送到就绪队列末尾

T(响应时间) = N(进程数目) * q(时间片)

多级队列MQ

根据作业或进程的性质或类型的不同，将就绪队列再分为若干个子队列。不同队列优先级、时间片长度、调度策略等都可不同

多级反馈队列MFQ

设置多个就绪队列，分别赋予不同的优先级（逐级降低）

新进程进入内存后，先投入队列1的末尾，按FCFS算法调度

若按队列1一个时间片未能执行完，则降低投入到队列2的末尾

仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行

如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾

优先级置顶

进入临界区的进程给予最高优先级

优先级继承

高优先级A进入临界区发现资源被低优先级的C占用，可以将A阻塞，并把A的优先级先继承给C，直到C退出临界区

实时系统的调度算法

静态表调度

通过对所有周期性任务分析，事先确定的固定调度方案。不灵活。

单调速率调度

单处理器下的最优静态调度算法

任务的周期越小，其优先级越高。优先级最高的任务最先被调度，优先级一样随机选择

最早截止时间优先算法

任务的绝对截止时间越早，其优先级越高。

多处理机调度

非对称式多处理系统：主－从处理机系统，由主处理机管理一个公共就绪队列

对称式多处理系统

多处理器系统中，各个处理器的地位相同。

静态分配：每个CPU设立一个就绪队列

动态分配：公共就绪队列

自调度：各个CPU采用公共就绪队列，每个处理及选择最适合的进程执行

成组调度：将一个进程中的一组线程，每次分派时同时到一组处理机上执行

专用处理机调度：为进程中的每个线程都固定分配一个CPU，直到该线程执行完成

死锁

发生的四个条件

• **互斥条件：**指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。
• **请求和保持条件：**指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。
• **不剥夺条件：**指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
• **环路等待条件：**指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。

活锁

执行者没被阻塞，但忧郁某些条件没满足，一直重复尝试。有可能自行解开

饥饿

某些资源分配策略不公平导致部分进程长时间等待。

处理死锁

死锁预防（静态）

打破互斥条件（无法实现）、打破占有申请条件（不太好）

打破不可剥夺条件（降低性能），

打破循环等待条件：事先编好号，进程占用了大号资源禁止申请小号资源，但可以申请更大号

死锁避免（动态）

判断操作是否会死锁，如果会则加以避免

银行家算法

n为进程数量，m为资源类型数量

可用资源矩阵Available ：m维

最大需求矩阵Max ：n x m维 最大需求

分配矩阵Allocation ： n x m 已分配的资源数量

需求矩阵Need ： n x m 进程尚需的资源数

设Request式进程P[j] 的请求向量

1.若Request[i] >= Need[i] ，出错

2.若Request[i] >= Available[i] ，出错

3.分配，Available -= Request; Allocation += Request; Need -= Request;

4.执行安全性算法，检查是否安全，如果不安全则不分配，安全就分配

安全性算法

1.设置向量Work = Available；设置向量Finish[i] = false，当有足够资源可以分配被该进程，Finish[i] = true;

2.从进程集合中找到Finish[i] = false,Need[i]<=Work[i],如果找到,执行3;找不到,执行4

3.释放进程资源：Work+=Allocation；Finish[i] = true；重复2.

4.如果所有Finish[i] = true,安全；否则不安全

死锁检测

资源分配图

化简：把请求边改为分配边，删除已经能运行的节点的所有边

死锁定理：如果t时刻资源分配图不可完全化简，则会死锁

解除死锁

1.撤销进程：逐个撤销进程，知道有足够资源解锁死锁

2.剥夺资源：挂起某些进程，剥夺其资源

IO管理

IO端口每个寄存器有唯一地址

内存映射编址：控制器内存/寄存器作为物理内存空间的一部分

IO独立编址：编址在内存地址外

IO控制技术

程序控制IO

轮询、查询方式IO；CPU代表进程向I/O模块发出指令，然后进入轮询状态。直到操作完成之后进程才能够继续执行

中断驱动

IO操作结束后，由设备控制器主动通知CPU结束。

DMA（直接存储器访问）

由专门的控制器来完成数据从内存到设备或是从设备到内存的直接传输工作

由程序设置DMA控制器中的若干寄存器值然后发起I/O操作;DMA控制器完成内存与外设的成批数据交换;在操作完成时由DMA控制器向CPU发出中断

CR(命令/状态寄存器)：用于接受从CPU发送来的IO指令

MAR（内存地址寄存器）：在输入时，它存放的数据从设备传送到内存的其实目标地址

DR（数据寄存器）：用于暂存从设备到内存

DC（数据计数器）：存放本次CPU要读或写的字节数

通道

通道是一个特殊功能的处理器，有自己的指令和程序专门负责数据传输

CPU将传输控制的功能下放给通道后，只负责数据处理。

DMA要由CPU控制数据的传送方向、存放数据的内存起始地址和数据块长度

但是通道自己就能处理

设备分类

按照数据组织：

块设备：数据块为单位，传输速率高，可寻址；

字符设备：字符为单位传输速率低，不可寻址

按照速度：低速（键鼠）、中速（打印机）、高速（磁盘）

IO管理目标和任务

1. 按照用户请求，控制设备操作，完成I/O设备与内存间的数据交换，最终完成用户的I/O请求
2. 建立方便、统一的独立于设备的接口
3. 充分利用各种技术提高CPU与设备、设备与设备之间的并行工作能力，充分利用资源
4. 保护

LUT

逻辑设备表：逻辑设备名、物理设备名、设备驱动程序入口地址

设备驱动程序

内核的一部分，为内核和文件提供接口

设备分配

DCT（设备控制表），每个设备一张，记录类型、标识符、状态、只想控制器的指针、重复执行次数、设备请求队列头指针

控制器控制表（COCT）描述IO控制器配置和状态，通道控制表（CHCT）

系统设备表（SDT），反应资源状态

SPOOLing技术

假脱机技术，专门利用一道程序完成IO操作。虚拟IO。

SPOOLing程序预先从外设读取数据并加以缓冲，在以后需要的时候输入到应用程序；接受应用程序的输出数据并加以缓冲，在以后适当的时候输出到外设

程序虚拟IO操作与实际IO操作分离，可共享原本独享设备

缓冲

输出：T ；传送：M ；处理：C

单缓冲

T和C可以并行

处理一块数据的时间约为Max（C，T）+M

双缓冲

T和M、C可以并行

有俩缓冲，处理一块数据的时间约为Max（C+M，T）

环形缓冲

多个缓冲区，缓冲区分为空缓冲区R，装满的缓冲区G，正在使用的工作缓冲区C

多个指针，计算进程下一个可用缓冲区Nextg，输入进程下次可用缓冲区Nexti，计算进程正在使用缓冲区Current

缓冲池

包含空缓冲区，装满输入缓冲区，装满输出缓冲区

相同类型缓冲区连成链表，emq、inq、outq

IO性能

使CPU利用率尽可能不被I/O降低；使CPU尽可能摆脱I/O

磁盘管理

磁盘是块设备

扇区，磁道，柱面

磁盘扇区一部分存储硬盘固件，剩下的是工作区（硬盘标定容量的扇区）和保留区（剩下的）

MBR

硬盘的0柱面、0磁头、1扇区称为主引导扇区（MBR），512字节

前446字节为启动代码及数据

之后则是分区表（DPT）：分区表由四个分区项组成，每个分区项数据为16字节录了启动时需要的分区参数

后面紧接着两个字节AA和55被称为幻数。BOIS读取MBR的时候总是检查最后是不是有这两个幻数,如果没有就被认为是一个没有被分区的硬盘

一个硬盘主分区至少有1个，最多4个，扩展分区可以没有，最多1个

主分区只能有一个是激活的

时间计算

寻道时间Ts = mn + s；m是常熟，n是移动了n条磁道，s是启动时间

旋转延迟 Tr = 1 / 2r；r是转速

传输时间 Tt = b/rN ；b是读写的字节数，r是转速，N是磁道上字节数

访问时间 Ta = Ts + Tr + Tt

调度算法

FCFS：先来先服务：公平、简单，寻道距离大

SSTF：最短寻道时间优先；优先选择距离当前磁头最近的：可能饥饿

SCAN：扫描算法；按一个方向到头，然后调转继续（入50→0→67→199）不利于远离磁头一端的访问

CSCAN：循环扫描，按一个方向到头，立刻跳到0继续同方向扫

CLOOK：类似CSCAN，但是到最外侧的请求后就立刻返回，而不是到最外侧柱面

磁盘空间管理

位图：每个物理块对应一位，返回对应物理块号。0为分配的，1为空闲

空闲表：所有空闲块记录在一个表。记录起始块号、空闲块数量

成组链接法：空闲块链表

RAID

NOR Flash比NAND Flash快，单连续大数据传输二者差别不大，但是NOR贵

RAID：廉价冗余磁盘阵列

RAID0

条带化存储，N个磁盘组成的RAID0理论上读写速度是N倍

RAID1

镜像存储。通过磁盘数据镜像实现数据冗余。在原始数据繁忙时，可以从镜像中拷贝，可以提高性能。成本最高。安全性高。可以通过镜像恢复丢失的数据

RAID2

海明码校验条带存储

将数据条块化地分布在不同硬盘，条块单位为位或字节，使用海明码提供错误检查和恢复

并行存取，各个驱动器同步工作，数据传输率高

需要多个磁盘来存放海明校验码信息多磁盘易出错环境中的有效选择，并未被广泛应用

RAID3

奇偶校验条带存储，共享校验盘，数据条带存储单位为**字节**

类似RAAID2，但是使用奇偶校验。对于大量的连续数据可提供很好的传输率。但对于随机数据来说，奇偶盘会成为写操作的瓶颈

读写要访问组中所有盘

先将分布在各个数据盘上的一组数据加起来，将和存放在冗余盘上。只要将冗余盘上的和减去所有正确盘上的数据，得到的差就是出错的盘上的数据

缺点：恢复时间较长

RAID4

奇偶校验条带存储，共享校验盘，数据条带存储单位为**块**

冗余代价与RAID3相同，访问数据的方法与RAID3不同

RAID5

奇偶校验条带存储，校验数据分布式存储，数据条带存储单位为**块**

所有盘上交叉存取数据和奇偶校验信息。读/写指针可同时对阵列设备进行操作，提供了更高的数据流量

写损失：每次写都要产生四次读写操作：读取旧的数据和奇偶信息；写新的数据和奇偶信息

当两块盘坏掉的时候，整个RAID的数据失效

RAID6

奇偶校验条带存储，两个分布式存储的校验数据，数据条带存储单位为**块**

数据可靠性高，但是要更多冗余空间，更大的写损失

1. 条带化：一个字节块可能存放在多个数据盘上

   • 优点：并行存取，性能好，磁盘负载均衡

   • 缺点：可靠性、不同IO请求需要排队

2. 镜像：数据完全拷贝一份

   • 优点：可靠性

   • 缺点：存储开销

3. 校验：数据通过某种运算（异或）得出，用以检验该组数字的正确性

   • 优点：可靠性，快速恢复

   • 缺点：开销

提高IO速度

提前读取、延迟写

虚拟盘（RAM）

磁盘管理实例

WINDOWS 2000 把基于MS—DOS分区方式的盘称为基本盘

动态盘支持创建新的多分区卷

基本盘的多分区卷的配置信息保存在注册表中。动态盘的多分区卷的配置信息保存在磁盘中

系统卷是WINDOWS2000存放引导文件的地方，包括引导程序（NTLDR）和NTDETECT

引 导 卷 是 WINDOWS2000 存 放 系 统 文 件 ， 如NTOSKRNL.EXE核心内核文件的地方

文件系统

操作系统中与文件管理有关的那部分软件和被管理的文件以及实施管理所需要的数据结构的总体

为了对系统管理者和用户提供透明存取

文件系统接口：命令行接口、程序接口

对象操作管理的软件集合：对存储空间、目录的管理、逻辑地址物理地址转换、读写管理、共享保护功能

管理对象：文件、目录、磁盘存储空间

流式文件：构成文件基本单位为字符

记录式文件：由若干记录组成，按照记录读写、查找

目录内容：文件名、别名、文件类型、地址星系、访问控制信息、使用信息

文件系统实现

文件

文件控制块FCB内容

基本信息：文件名、物理位置、文件逻辑结构、文件物理结构

访问控制信息：文件所有者（创建文件的用户）、访问权限

使用信息：创建时间，上一次修改时间、当前使用信息

连续结构

优点：结构简单，不需要额外空间开销，支持顺序和随机存取，连续存取速度快

缺点：文件长度一经笃定不易改变，不利于文件动态增加修改

串联结构

优点：空间利用率高，文件动态扩充容易，顺序存取效率高

缺点：随机存取效率低。有可靠性问题，指针耗费空间

索引结构

优点：能顺序存取、随机存取、动态增长

缺点：额外空间开销

目录

根据用户给出路径名，迅速定位到文件控制块

目录项= 文件名+（FCB或FCB的地址）

长文件名：固定目录项，长度可变的文件名放在目录文件末尾

硬链接软连接

硬链接：俩都指向同一个Inode

软连接：重定向到对应Inode

文件保护

建立副本：简单、开销大

定时转储

磁盘块一致性检查：检查记录在文件和空闲块中出现的次数，计数器

文件一致性：检查记录在i节点和文件目录中引用的次数

提高性能

目录项（FCB）分解、当前目录、磁盘碎片整理、块高速缓存、磁盘调度、提前读取、合理分配磁盘空间、信息的优化分布、RAID技术等

基于日志的文件系统

数据结构：inode、inode map、段（包含数据块、元数据、日志）、段摘要（每一个数据块的信息）、段使用情况表（段数据块中有效数据量）

写操作会在内存段segment缓冲区加入新数据快，segment写满后把数据写到磁盘

失效恢复：回滚恢复到最后一个检查点

清理：整理碎片

文件系统实例

FAT系统

簇：若干个扇区组成，从0编号

文件系统数据记录在引导扇区中。文件分配表（FAT）用于描述簇的分配和下一簇号

FAT表项2字节，目录项32字节

UFS系统

多级文件目录，有常规文件、目录文件、特殊文件

EXT2

磁盘划分成相同大小的块，组成若干块组，每个块组有一个inode

VFS

虚拟文件系统：设备、索引节点编号、模式、用户标识符、块大小、时间

1.寻找对应的文件系统信息。VFS 通过 file_systems在 file_system_type 组成的链表中根据指定的文件系统名称搜索文件系统类型信息

2.如果在上述链表中找到匹配的文件系统，则说明内核具有对该文件系统的内建支持。否则，说明该文件系统可能由可装载模块支持，VFS 会请求内核装入相应的文件系统模块，此时，该文件系统在 VFS 中注册并初始化。

3.看不懂