操作系统基本概念

操作系统是计算机科学研究基石之一。

功能

• 管理硬件（如设备驱动：实现用户提出的I/O操作请求，完成数据的输入输出）
• 管理内存：物理内存/虚拟内存
• 处理中断

内核特征

• 并发：一段时间内多个程序执行
• 共享(资源)：“同时”访问，互斥共享
• 虚拟：将硬件虚拟化(CPU->进程，磁盘->文件，内存->地址)
• 异步：程序走走停停，但保证程序结果一致

操作系统启动过程

• OS存放在硬盘上

BIOS：基本I/O处理系统

• 早期的 BIOS 存储在 ROM 中，并且其大小不会超过 64KB；而目前的 BIOS 大多有1MB 到 2MB，所以会被存储在闪存（Flash Memory）中

ROM是只读存储器，存在里面的东西不能删除和修改，只能读取、复制等；
闪存是在断电以后不丢失数据的存储器，不能以字节的方式擦除信息，只能以区域/块的方式擦除(如U盘)

• PSOT(Power-On Self-Test)：加电自检，主要是对 CPU、内存等硬件设备进行检测和初始化，执行BIOS；
• 启动顺序：硬件自检完成后，BIOS需要知道"下一阶段的启动程序"具体存放在哪一个设备。也就是说，BIOS需要有一个外部储存设备的排序，排在前面的设备就是优先转交控制权的设备；
• 主引导记录：BIOS按照"启动顺序"，把控制权转交给排在第一位的储存设备，将BootLoader从磁盘的引导扇区加载到内存的0x7c00处；跳转到CS：IP = 0000:7c00处开始执行BootLoader

CS为代码段寄存器，IP为指令指针寄存器，任意时刻，CPU将CS:IP指向的内容当作指令执行。
在8086系统中，访问存储器的地址码由段地址(CS)和段内偏移地址(IP)两部分组成段寄存器用来存放各分段的逻辑基值。

BootLoader：加载OS

• 存放在硬盘第一个引导扇区，512个字节
• 将操作系统的代码和数据从硬盘加载到内存
• 跳转到操作系统的起始地址

总结上述流程如下图所示：

操作系统启动示意图

中断、异常、系统调用

操作系统的交互

• 面向外设：中断和I/O
• 面向应用程序：异常和系统调用

中断(来源于外设)：来自不同的硬件设备的计时器和网络的中断

• 引入中断技术的初衷是提高多道程序运行环境中CPU的利用率，而且主要是针对外部设备的。后来逐步得到发展，形成了多种类型，成为操作系统各项操作的基础。例如，键盘或鼠标信息的输入、进程的管理和调度、系统功能的调用、设备驱动、文件访问等，无不依赖于中断机制。可以说，现代操作系统是靠中断驱动的软件。

特点

• 异步
• 持续的，对用户应用程序是透明的，用户感知不到中断
• 常见中断类型：程序中断，时钟中断，I/O中断，硬件中断

相关术语

• 中断源 ：引起中断发生的事件
• 中断请求：中断源向CPU发出的请求中断处理信号
• 中断响应：CPU收到中断请求后转去执行相应的事件处理程序
• 中断屏蔽：在中断请求产生后，系统用软件方式有选择的封锁中断，而允许其他中断仍能得到响应
• 关中断：又称禁止中断，CPU内部处理机状态字（PSW）中断允许位被清除，不允许CPU响应中断
• 开中断：与关中断相反，CPU内部处理机状态字（PSW）中断允许位被恢复，允许CPU响应中断

中断分类

• 硬中断

1. 外中断：来自CPU外部和内存外部的中断（如I/O中断和外部信号中断，其实就是我们一般上说的，狭义上的中断）
2. 内中断：来自CPU内部和内存内部产生的中断，也称为陷入（trap）或者异常，（比如常见的算术溢出，除数为0，地址非法，缺页等等）

• 软中断：是一条CPU指令，主要用于执行系统调用（int 0x80汇编指令）以及给调试程序通报一个特定的事件，属于同步中断

所有的硬中断的优先级都高于软中断，各中断的优先级在系统设计初期给出，在运行过程中是不变的。

中断优先级

• 说明：在实际系统中，常常遇到多个中断源同时请求中断的情况，这时CPU必须确定首先为哪一个中断源服务，以及服务的次序
• 优先级：解决的方法是中断优先排队，即根据中断源请求的轻重缓急，排好中断处理的优先次序即优先级，先响应优先级最高的中断请求
• 中断嵌套：当CPU正在处理某一中断时，要能响应另一个优先级更高的中断请求，而屏蔽掉同级或较低级的中断请求，形成中断嵌套

中断处理过程

• 硬件：设置中断标记[CPU初始化]

1. 将内部、外部事件设置中断标记
2. 生成中断事件的ID

• 软件

1. 保存当前处理状态 [保护现场]
2. 中断服务程序处理(中断向量表) [中断服务]
3. 清除中断标记 [恢复现场]
4. 恢复之前保存的状态 [中断返回]

中断向量与中断向量表

• 中断向量：Intel x86系列微机共支持256种向量中断，为使处理器较容易地识别每种中断源，将它们从0～255 编号，即赋予一个中断类型码n，这个8位的无符号整数叫做一个向量，也叫中断向量。

• 中断向量表：在实地址模式中，CPU 把内存中从0 开始的1K 字节作为一个中断向量表；表中的每个表项占4个字节，由两个字节的段基址和两个字节的偏移量组成，这样构成的地址便是相应中断处理程序的入口地址。

Linux 对256 个中断向量的分配如下：

• 从 0~31 的向量对应于异常（不能被屏蔽）和非屏蔽中断；
• 从 32~47 的向量分配给屏蔽中断（即由I/O 设备引起的中断）；
• 从 48~255 的向量用来标识软中断。Linux 只用了其中的一个（即128 或0x80向量）用来实现系统调用。当用户态下的进程执行一条int 0x80汇编指令时，CPU 就切换到内核态，并开始执行 system_call() 内核函数。

参考中断向量表 中断描述符

异常：非法指令或其他坏的处理状态(如内存出错)

特点

• 同步
• 杀死或重新执行意想不到的的程序指令（此时操作系统可能支持此指令了）

异常分类

• 故障（Fault）：如缺页中断
• 陷阱（Trap）：调用某些系统函数，如打开文件的时候，触发陷阱，进行系统调用
• 夭折（Abort）：发生严重错误，无法恢复运行

异常处理过程

• 保存现场
• 异常处理

1. 杀死异常程序
2. 重新执行异常指令

• 恢复现场

系统调用：应用程序主动向操作系统发出服务请求

特点

• 同步或异步
• 等待和持续（系统返回数据后继续执行）

系统调用处理过程

• 应用程序访问高层次API接口而实现

1. Win32 API
2. POSIX API（通用可移植系统调用接口，UNIX Linux）
3. Java API（非系统调用接口）

• 触发用户态到内核态的转换

内核态：CPU可以访问内存的所有数据，包括外围设备，例如硬盘、网卡，CPU也可以将自己从一个程序切换到另一个程序。
用户态：只能受限的访问内存，且不允许访问外围设备，占用CPU的能力被剥夺，CPU资源可以被其他程序获取。
参考内核态与用户态

• 函数调用/系统调用区别

1. 函数调用在同一个堆栈内完成
2. 系统调用存在用户态栈和内核态栈的切换

中断 异常 系统调用

跨越操作系统边界的开销

1. 建立中断/异常/系统调用号与对应服务例程映射关系的初始化开销
2. 建立内核堆栈
3. 参数传递：把一些参数从用户空间传给内核，再进行验证参数（安全性）：检查所有的参数是否合法有效
4. 内核态映射到用户态的地址空间，更新页面映射权限
5. 内核态独立地址空间

内存管理

内存是一个计算机最重要的部分之一，程序只有被加载到内存中才可以运行，CPU所需要的指令和数据也都是来自于内存。

计算机体系结构/内存分层结构

• 计算机基本硬件结构：CPU(寄存器，运算器，控制器，缓存，存储管理单元)；内存；设备(I/O)

计算机体系结构

• 内存分层结构：金字塔结构

1. CPU寄存器
2. cache(L1缓存 L2缓存...)
3. 主存
4. 硬盘(虚拟内存)

主存与硬盘之间存在交换/分页

内存金字塔

操作系统内存管理目标

• 抽象：逻辑地址空间（应用程序不用考虑底层）
• 保护：独立地址空间（同时运行多个程序，进程进程间隔离）
• 共享：访问相同内存（进程间通信）
• 虚拟化：更多的内存空间

内存抽象

没有内存抽象的年代

早期的操作系统中，并没有引入内存抽象的概念。程序直接访问和操作的都是物理内存，内存的管理也非常简单，除去操作系统所用的内存之外，其余全部给用户程序使用。

但是这种无内存抽象存在一些问题：

比如当执行如下指令时：mov reg1，1000

这条指令会将物理地址1000中的内容赋值给寄存器。这种内存操作方式使得操作系统中存在多进程变得完全不可能，必须执行完一条指令后才能接着执行下一条。如果是多进程的话，由于直接操作物理内存地址，当一个进程给内存地址1000赋值后，另一个进程也同样给内存地址赋值，那么第二个进程对内存的赋值会覆盖第一个进程所赋的值，这回造成两条进程同时崩溃。

因此无内存抽象存在以下问题：

1. 用户程序可以访问任意内存，容易破坏操作系统，造成崩溃
2. 同时运行多个程序特别困难

参考操作系统内存管理

内存抽象：地址空间

如何做到进程的地址受保护
操作系统对物理内存做了一层抽象，也就是地址空间(AddressSpace)，一个进程的地址空间包含了该进程所有相关内存，如下图所示：

AddressSpace

从低地址到高地址分别内存区分别为：代码段，数据段（初始化），数据段（未初始化）（BSS），堆，栈，命令行参数和环境变量。（堆向高内存地址生长，栈向低内存地址生长）

• 代码段：存放全局常量（const）、字符串常量、程序代码
• 数据段（初始化）：存放初始化的全局变量、初始化的静态变量（全局的和局部的）
• 数据段（未初始化）（BSS）：存放未初始化的全局变量、未初始化的静态变量（全局的和局部的）
• 堆：存放动态分配的区域（malloc、new等）
• 栈：存放局部变量（初始化以及未初始化的，但不包含静态变量）、局部常量（const）
• 命令行参数和环境变量：存放命令行参数和环境变量

参考进程实体 内存划分

真实地址生成过程

地址空间分为以下两种：

• 物理地址空间：硬件支持的地址空间(内存条/硬盘)，从0开始，如一个内存条的大小4GB
• 逻辑地址空间：一个运行程序所拥有的内存范围，如一个进程占用的内存范围16KB

从进程的角度看待内存其范围是0-X，但是其对应的真实物理内存地址应该是base——base+X，数值base称为进程的基址，存放在基址寄存器中。每个内存地址送到内存之前，都会自动加上基址寄存器的内容。

CPU 上用来做内存地址转换的叫做内存管理单元（MMU），其完成逻辑地址到物理地址的映射。

逻辑地址生成过程

逻辑地址生成的过程就是将一行行代码转变成内存中具体的逻辑地址，使得CPU运行程序时能"按图索骥"。
高级语言编写出来的程序逻辑地址生成一般步骤为：编译->汇编->链接->载入

1. 编译：对源代码进行编译，成为汇编源代码，此时仍然用符号来指代函数
2. 汇编：汇编成二进制代码，用具体地址来代替符号了，但是有一些函数还没有找到（此函数在别的程序文件中）
3. 链接：加入函数库，找到库函数的地址，把多个小程序组装成一个可执行文件
4. 载入：程序加载时进行，视程序实际位置改变符号地址

链接分为两种方式：

• 静态链接：在程序执行之前完成所有的组装工作，生成一个可执行的目标文件（EXE文件）。
• 动态链接：在程序已经为了执行被装入内存之后完成链接工作，并且在内存中一般只保留该编译单元的一份拷贝。

延伸知识：静态链接库与动态链接库都是共享代码的方式，如果采用静态链接库，lib文件(静态链接的函数库)中的指令都被直接包含在最终生成的EXE文件中了。但是若使用DLL文件（动态链接的函数库），该DLL不必被包含在最终的EXE文件中，EXE文件执行时可以“动态”地引用和卸载这个与EXE独立的DLL文件。

• 参考动态链接和静态链接的区别

逻辑地址生成过程

地址安全检查

• 程序逻辑地址空间的范围，基址与界限
• CPU检查逻辑地址是否合理

CPU 生成的地址通常称为逻辑地址，而内存单元看到的地址（即加载到内存地址寄存器的地址）通常称为物理地址。
参考逻辑地址空间和物理地址空间

总结一下，物理地址生成过程如下图所示：

物理地址生成过程

连续内存分配

连续分配是指为一个用户程序分配连续的内存空间。连续分配有单一连续存储管理和分区式储管理两种方式。

单一连续内存分配

内存被分为两个区域：系统区和用户区。应用程序装入到用户区，可使用用户区全部空间。其特点是，最简单，适用于单用户、单任务的操作系统。

分区式内存分配

内存碎片

• 定义：内存的空闲空间不能被利用
• 外部碎片：在分配单元间的未使用内存
• 内部碎片：在分配单元内的未使用内存

固定分区

• 特点：把内存划分为若干个固定大小的连续分区，分区大小可以相等也可以不等
• 优点：易于实现，开销小
• 缺点：分区总数固定，限制了并发执行的程序数目；内部碎片造成浪费

动态分区

• 特点：分区大小最初并未声明，它在进程加载时声明。分区大小根据进程的需要而变化，以避免内部碎片。
• 优点：

1. 没有内部碎片
2. 进程大小无限制
3. 多程序的程度是动态的，可以同时将更多的进程加载到内存中

• 缺点：

1. 存在外部碎片
2. 复杂的内存分配，动态分区中，分配和释放非常复杂，分配和取消分配的操作非常频繁，因为每次分配给新进程时分区大小都会发生变化，操作系统必须跟踪所有的分区

• 分配策略

1. 首次适配：找到第一个可用空闲块(空闲块空间大于应用程序所需大小)[优势：简单，易产生更大空闲块][缺点：易产生外碎片]

按地址排序的空闲块列表
分配需要寻找一个合适的分区
重分需要检查相邻空闲分区是否可以合并

2. 最优适配：按分区在内存的先后次序从头查找，找到其大小与要求相差最小的空闲分区进行分配 [优势：避免分割大空间][缺点：外部碎片，重分配慢，易产生微小碎片]

按尺寸排序的空闲块列表
分配需要寻找一个合适的分区
重分需要检查相邻空闲分区是否可以合并

3. 最差适配：按分区在内存的先后次序从头查找，找到最大的空闲分区进行分配 [优势：中等尺寸分配效果最好][缺点：重分配慢，大分区可能无法被分配]

按地址排序的空闲块列表
分配很快
重分需要检查相邻空闲分区是否可以合并

压缩式与交换式碎片整理

• 压缩式：

1. 重置程序合并孔洞，压缩后，所有的空闲分区都是连续的，所有已被使用的分区也都集中在一起
2. 要求所有程序是动态可重置的
3. 开销大，系统的效率会降低

• 交换式：

1. 情形描述：运行程序需要更多的内存
2. 抢占等待的程序的内存，回收它们的内存，将其数据存放到硬盘上

非连续内存分配

在前面的几种存储管理方法中，为进程分配的空间是连续的，使用的地址都是物理地址。如果允许将一个进程分散到许多不连续的空间，就可以避免内存紧缩，减少碎片。

• 连续内存非配缺点：

1. 分配给一个程序的物理内存是连续的
2. 内存利用率低
3. 有外、内碎片问题

• 非连续内存非配优点：

1. 一个程序的物理内存是非连续的
2. 更好的内存利用和管理
3. 允许共享代码和数据(共享库等...)
4. 支持动态加载和动态链接

• 非连续内存非配缺点：如何建立虚拟地址和物理地址之间的关系？

1. 软件：开销大
2. 硬件：分段/分页

分段式存储管理

• 进程的段地址空间由多个段组成：代码段；数据段；堆；栈；命令行数据段
• 目标：更好的分离和共享

image.png

• 分段的概念：

1. 段表示访问方式和存储数据等属性相同的一段地址空间
2. 上图可以看出段对应一个连续的内存“块”
3. 若干个段组成进程逻辑地址空间

• 段访问机制：

1. 逻辑地址由二元组(s，addr)表示
2. s：段号；addr：段内偏移
3. 实现方案：段寄存器+地址寄存器方案；单地址实现方案
4. 硬件实现机制：操作系统需要设置段表

段访问硬件实现机制

• 首先从逻辑地址中得到段号和偏移量
• 在段表中查找段号，得到段基址和段长度范围
• 由MMU来判断偏移量是否合法（偏移量是否大于段长度）
• 得到物理地址，在物理内存中查找相应内容

分页式存储管理

• 基本原理：将程序的逻辑地址空间划分为固定大小的页(page)，而物理内存划分为同样大小的帧(page frame)。程序加载时，可将任意一页放入内存中任意一个帧，这些帧不必连续，从而实现了离散内存分配。再建立逻辑地址到物理地址映射关系。[页表/MMU(内存管理单元)/TLB(快表)]

划分物理内存至固定大小的帧(Frame)，大小是2的幂；划分逻辑地址空间至相同大小的页(Page)，大小是2的幂

帧（物理地址）

• 物理内存被分割为大小相等的帧
• 一个内存物理地址是一个二元数组(f, o)

f：帧号(F位，共有2^F个帧)
o：帧内偏移(S位，每帧有2^S个字节)
物理地址 = [2^Sxf + o]

帧

物理地址计算例子

页（逻辑地址）

• 一个程序的逻辑地址空间被划分为大小相等的页

页内偏移的大小 = 帧内偏移的大小; 页号大小 ≠ 帧号大小

• 一个逻辑地址是一个二元数组(p, o)

p：页号(P位，共有2^P个帧)
o：页内偏移(S位，每页有2^S个字节)
逻辑地址 = [2^Sxp + o]

页寻址机制

页寻址机制.jpg

• 首先从逻辑地址中得到页号和页内偏移
• 在页表中由页号查找帧号，页表保存了逻辑地址->物理地址的映射关系
• 由帧号和帧内偏移(页内偏移)得到物理地址，在物理内存中查找相应内容

• 本质是页映射到帧的过程
• 页表由操作系统初始化时建立
• 页是连续的虚拟内存
• 帧是非连续的物理内存
• 不是所有的页都有对应的帧！！！

页表

• 页表保存了逻辑地址（页号）——物理地址（帧号）之间的映射关系
• 本质是个大数组
• 逻辑地址页号+PTBR（页表基址寄存器）得到页号
• 页表项标志：

1. 修改位（dirty bit）：对应的页面中的内容是否被修改了
2. 存在位（resident bit）：逻辑页面是否存在与之对应的物理帧，有些逻辑页没有对应的物理帧
3. 引用位（clock/reference bit）：在过去一段时间内是否访问过页中的某一个存储单元

页表结构

• 地址转换实例：

地址转换实例

• 分页机制性能问题：

1. 时间性能问题：访问一个内存单元需要两次内存访问(一次用于获取页表项，一次用于访问数据)
2. 空间性能问题：页表可能非常大
3. 解决方法(缓存，间接访问方式)

快表（TLB）

• 功能：用来解决分页机制时间性能问题
• 目标：缓存近期访问的页表项
• 实现：TLB使用关联存储器实现，具备快速访问性能

关联存储器：有一组key，可以并行地查找所有表项，得到匹配项

• 参考计算机关联内存

• 特点：快表位于CPU中，所以它的速度快、成本高、功耗大

• 如果TLB命中，物理页号可以很快被获取
• 如果TLB未命中，对应的表项被更新到TLB中

快表

多级页表

• 快表从速度上解决问题，但空间上还存在缺点
• 多级页表：解决分页机制空间性能问题
• 实现：把页号分为k个部分，建立页表“树”
• 优点：可以有效减少每级页表的长度，但是如果所有的页表项都存在，则多级页表并没有减少存储量，不过大部分进程并不会用到所有的逻辑地址空间

在x86架构中，CR3寄存器用于存储PTBR（页表基址）

多级页表

反向页表

• 定义：用来解决页表占用的空间的一种方案。
• 普通页表问题：

1. 大地址空间问题，对于大地址空间（64-bits）系统，多级页表变得繁琐；比如：5级页表
2. 不让页表与逻辑地址空间的大小相对应，让页表与物理地址空间的大小相对应，逻辑（虚拟）地址空间增长速度快于物理地址空间

• 基于页寄存器的方案：

基于页寄存器方案

1. 页寄存器思路：不让页表与逻辑地址空间的大小相对应，让页表与物理地址空间的大小相对应，以帧号为索引去寻找页号，这样反向页表大小最大就为物理地址的容量
2. 页寄存器（Page Registers）：每个帧与一个页寄存器（Page Register）关联，寄存器内容包括：

• 使用位（Residence bit）：此帧是否被进程占用
• 占用页号（Occupier）：对应的页号p
• 保护位（Protection bits）：约定这一页的访问方式，可读 or 可写

3. 页寄存器方案资源消耗举例：

页寄存器方案举例

4. 页寄存器方案优点

• 页表大小相对于物理内存而言很小
• 页表大小与逻辑地址空间大小无关

5. 页寄存器方案缺点

• 页表信息对调后，需要根据帧号可找页号
• 在页寄存器中搜索逻辑地址中的页号

• 基于关联内存的方案：

基于关联内存方案

1. 如果帧数较少， 页寄存器可以被放置在关联内存中
2. 在关联内存中查找逻辑页号

• 成功： 帧号被提取
• 失败： 页错误异常(pagefault)

3. 限制因素：

• 大量的关联内存非常昂贵
• 到难以在单个时钟周期内完成
• 耗电

• 基于hash查找的方案

基于hash方案

1. 在反向页表中通过哈希算法查找对应页表项中的帧号
2. 查找过程：

• 从逻辑地址中得到页号
• 根据页号和PID计算出Hash值
• 在反向页表中查找对应的页表项，核对页号是否一致，从中找出相应的物理帧号

虚拟内存

简单介绍

• 虚拟内存是一种存储方案，为用户提供了一个拥有非常大的主内存的幻觉
• 用户可以加载比可用主存更大的进程，用磁盘空间来扩展物理内存
• 操作系统不是在主内存中加载一个大进程，而是在主内存中加载多个进程的不同部分

虚拟内存

• 思考一个问题：在计算机系统中， 尤其是在多道程序运行的环境下，可能会出现内存不够用的情况， 怎么办？

• 如果是程序太大， 超过了内存的容量， 可以采用手动的覆盖(overlay)技术， 只把需要的指令和数据保存在内存当中：
• 如果是程序太多， 超过了内存的容量， 可以采用自动的交换(swapping)技术， 把暂时不能执行的程序送到外存中：
• 如果想要在有限容量的内存中， 以更小的页粒度为单位装入更多更大的程序， 可以采用自动的虚拟存储技术。

覆盖技术

• 目标：用较小的内存运行较大的程序，与分区存储管理配合使用
• 原理：把程序按照自身逻辑结构划分为若干个功能上相对独立的程序模块，不会同时执行的模块共享同一块内存区域，按时间先后运行

1. 必要部分（常用功能）的代码和数据常驻内存；
2. 可选部分（不常用功能）在其他程序模块中实现，平时存放在外存中，在需要用到时才装入内存；
3. 不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖，即这些模块共用一个分区。

覆盖技术举例

• 缺点：

1. 由程序员来把一个大的程序划分为若干个小的能模块；并确定各个模块之间的覆盖关系，增加了程序复杂度，费时费力；
2. 覆盖模块从外存装入内存， 实际上是以时间延长换取空间。

交换技术

• 目标：多道程序在内存中，让正在运行或需要运行的程序获取更多的内存资源
• 原理：将暂时不能运行的程序送到外存，操作系统将一个进程的整个地址空间的内容保存到外存，将外存的某个进程的地址空间读入到内存中

交换技术

• 几个问题：

1. 交换时机的确定（何时发生交换？只有当内存空间不够时交换）；
2. 交换区的大小（必须足够大以存放所有用户进程的所有内存映像的拷贝；必须能对这些内存映像直接存取）；
3. 程序换入时的重定位（换出后再换入的内存位置一定要在原来的位置上吗？最好采用动态地址映射的方式）。

• 覆盖与交换的比较：

1. 覆盖只能发生在那些相互之间没有调用关系的程序模块之间，因此程序员必须给出程序内的各个模块之间的逻辑覆盖结构。
2. 交换技术是以在内存中的程序大小为单位来进行的， 它不需要程序员给出各个模块之间的逻辑覆盖结构;
3. 交换发生在内存中程序与管理程序或操作系统之间， 而覆盖则发生在运行程序的内部。

• 缺点：增加了处理器的负担

虚存技术

• 目标：像覆盖技术那样，但由操作系统自动来完成，无需增加程序员负担；像交换技术那样，但只对进程的部分内容进行交换；综合了两者的优点。

image

• 程序局部性原理：指程序在执行过程中的一个较短时期， 所执行的指令地址和指令的操作数地址， 分别局限于一定区域。局部性通常有两种形式：时间局部性和空间局部性。

1. 时间局部性：一条指令的一次执行和下次执行， 一个数据的一次访问和下次访问都集中在一个较短时期内；
2. 空间局部性：当前指令和邻近的几条指令， 当前访问的数据和邻近的几个数据都集中在一个较小区域内。

• 基本概念：可以在页式或段式内存管理的基础上实现

1. 在装入程序时，不必将其全部装入内存中，只需装入部分执行的页或段；
2. 程序执行过程中，如果需执行的指令或访问的数据尚未在内存中（称为缺页或缺段），则由处理器通知操作系统将相应页面或段调入到内存中，再继续执行程序；
3. 操作系统将内存中暂时不使用的页面或段调出保存在外存中，从而腾出更多空闲空间。

• 基本特征：

1. 大的用户空间：虚拟地址可以远远大于物理地址，32位系统虚拟地址理论上可以访问4GB
2. 部分交换：与交换技术相比，虚拟存储的调入调出是对部分虚拟地址空间进行的
3. 不连续性：物理内存分配的不连续性，虚拟地址空间使用的不连续性

虚拟页式内存管理

虚拟页式内存管理

• 基本思想：在页式存储管理的基础上，增加请求调页和页面置换功能
• 基本思路：

1. 当一个用户程序要调入内存运行时，不是将该程序的所有页面都装入内存，而是只装入部分的页面，就可启动程序运行；
2. 在运行的过程中，如果发现要运行的程序或要访问数据不在内存，则向系统发出缺页中断请求，系统在处理这个中断时，将外存中相应的页面调入内存，使得该程序能继续运行。

• 页表表项：

页表表项

1. 页号：虚拟地址空间中的页号
2. 访问位：如果该页面被访问过（ 包括读操作或写操作），则设置此位。用于页面換算法。
3. 修改位：表示此页在内存中是否被修改过。当系统回收该物理页面时，根据此位来决定是否把它的内容写回外存；0 表示页面在内存时数据未被修改，1 表示被修改过。
4. 保护位：表示允许对该页做何种类型的访问，如只读、可读写、可执行等.
5. 驻留位：表示该页是在内存还是在外存。1 表示在内存中，0 表示不在内存中，为 0 时会发生“缺页”中断信号，请求系统处理
6. 帧号：物理地址空间的帧号

• 缺页中断

缺页中断

后备存储：

后备存储

页面置换算法

• 功能：当缺页中断发生时，需要调入新的页面而内存已满，则选取物理内存中相关页面进行置换
• 目标：尽可能减少页面的换进换出次数（即缺页中断的次数）
• 页面锁定：用于描述必须常驻内存的操作系统的关键部分或时间关键的应用进程，在页表中添加锁定标志位。

最优页面置换算法（OPT）

• 设计思想：置换以后不再需要的或最远的将来才会用到的页面。
• 实现：这种算法要基于程序的走向和未来实现，实际操作系统中无法实现，更多的是作为一种标准来衡量其他算法的性能。

先进先出算法（FIFO）

• 设计思想：选择在内存中驻留时间最长的页并置换它
• 实现：系统维护着一个链表，记录了所有位于内存当中的逻辑页面。从链表的排列顺序来看，链首页面的驻留时间最长， 链尾页面的驻留时间最短。当发生一个缺页中断时， 把链首页面淘汰出局， 并把新的页面添加到链表的未尾。
• 性能：性能较差，调出的页面可能是经常要访问的页面，并且有Belady现象，很少单独使用

最近最少使用算法（LRU）

• 设计思想：置换最久未被使用的页
• 实现：需要记录各个页面使用时间先后顺序，两种方案，链表实现（首节点是最近使用），或堆栈实现（栈顶是最近使用）

链表实现：系统维护一个页面链表， 最近刚刚使用过的页面作为首结点， 最久未使用的页面作为尾结点。每一次访问内存时， 找到相应的页面． 把它从链表中摘下来， 再移动到链表之首。每次缺页中断发生时， 淘汰链表末尾的页面。

堆栈实现：设置一个活动页面栈． 当访问某页肘， 将此页号压入栈顶， 然后， 考察栈内是否有与此页面相同页号， 若有则抽出。当需要淘汰一个页面时，总是选择栈底的页面， 它就是最久未使用的。

• 性能：最佳页面置换算法的近似

时钟算法（CLOCK）

• 设计思想：

1. 需要用到页表项当中的访问位，当一个页面被装入内存时，把该位初始化为0。然后如果这个页面被访问（读/写），把该位置为1
2. 把各个页面组织成环形链表（类似钟表面），把指针指向最老页面（最先进来）
3. 当发生缺页中断时，考察指针是否指向最老页面，若它的访问位为0，则立即淘汰；若访问位为1，则把该位置0，然后指针指向下一个，直到找到淘汰页面，然后把指针移动到它的下一格。

• 性能：LRU的近似，FIFO的改进算法

第二次机会算法（SCR）

• 设计思想：修改CLOCK算法，同时使用脏位和访问位来指导置换，使它允许脏页再第一次时钟头扫描中保存下来

第二次机会算法

最不常用算法（LFU）

• 设计思想：当一个缺页中断发生时，选择访问次数最少的那个页面淘汰
• 实现方法：对每个页面设置一个访问计数器，每当一个页面被访问时，该页的访问计数器加1。在发生缺页中断时， 淘汰计数值最小的那个页面。

进程及线程

进程基本概念

进程定义

• 一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程

进程示意图

进程组成

• 程序的代码；
• 程序处理的数据；
• 程序计数器中的值，指示下一条将运行的指今；
• 一组通用寄存器的当前值，堆、栈；
• 一组系统资源（如打开的文件）。

总之，进程包含正在运行的一个程序的所有状态信息

进程特点

• 动态性：可动态创建、结束进程
• 并发性：进程可以被独立调度并占用处理机运行；并发运行
• 独立性：页表保证进程独立，不同进程不同页表，不同进程不同地址空间
• 制约性：因访问相同数据/资源或进程间同步而产生制约

进程管理

进程控制结构（PCB）

• 进程控制块：描述进程的数据结构，操作系统为每个进程都维护一个PCB，用来保存与该进程有关信息，PCB是进程存在的唯一标识。
• PCB与进程关系：

1. 进程的创建：为该进程生成一个PCB；
2. 进程的终止：回收它的PCB；
3. 进程的组织管理：通过对PCB的组织管理来实现。

• 包含信息：

pcb进程标识和状态信息

• pcb组织方式：

1. 链表：同一状态的进程其PCB成一链表，多个状态对应多个不同的链表

各状态的进程形成不同的链表：就绪链表，阻塞链表

2. 索引表：同一状态的进程归入一个index表(由index指向PCB)，多个状态对应多个不同的index表

各状态的进程形成不同的索引表：就绪索引表、阻塞索引表

pcb组织方式

进程生命周期

• 进程生命周期：创建，就绪，运行，等待（进程只能自己阻塞自己），唤醒（进程只能被其他进程或操作系统唤醒），结束

进程等待（阻塞）情况：

1. 请求并等待系统服务，无法马上完成
2. 启动某种操作，无法马上完成
3. 需要的数据没有到达

• 进程状态变化模型：
  进程的三种基本状态：就绪状态，等待状态，阻塞状态。

进程状态变化

• 进程挂起：此时进程没有占用内存空间，进程映像在磁盘中，不同于进程阻塞

进程挂起

1. 阻塞挂起状态：进程在外存并等待某事件出现
2. 就绪挂起状态：进程在外存，但只要进入内存便可运行
3. 挂起状态变化：

挂起状态变化

OS进程调度

OS进程调度

• 状态队列：

1. 由操作系统来维护一组队列，用来表示系统当中所有进程的当前状态；
2. 不同的状态分别用不同的队列来表示（就绪队列、各种类型的阻塞队列）；
3. 每个进程的PCB都根据它的状态加入到相应的队列当中，当一个进程的状态发生变化时肘，它的PCB 从一个状态队中脱离出来，加入到另外一个队列。

状态队列

线程基本概念

线程定义

• 进程当中的一条执行流程
• 进程与线程的理解：

1. 从资源组合角度：进程是把一组相关的资源组合起来，构成了一个资源平台，包括地址空间、打开的文件等各种资源
2. 从运行的角度：线程是代码在这个资源平台上的一条执行流程
3. 线程 = 进程 - 共享资源

进程中的线程

• 线程优点：

1. 一个进程中可以同时存在多个线程；
2. 各个线程之间可以并发地执行；
3. 各个线程之间可以共享地址空间和文件等资源。

• 线程缺点：

1. 一个线程崩溃， 会导致其所属进程的所有线程崩溃。

线程与进程区别

1. 进程是资源分配单位，线程是CPU调度单位；
2. 进程拥有一个完整的资源平台，而线程只独享必不可少的资源，如寄存器和栈；
3. 线程同样具有就绪、阻塞和执行三种基本状态，同样具有状态之间的转换关系；
4. 线程能减少并发执行的间和空间开销：

• 线程的创建时间比进程短；
• 线程的终止时间比进程短；
• 同一进程内的线程切换时间比进程短；
• 由于同一进程的各线程间只享内存和文件资源，可直接进行不通过内核的通信。

进程线程区别

线程实现

用户线程

• 基本概念：
  
  用户线程

1. 在用户空间实现，它不依赖于操作系统的内核，由一组用户级的线程库函数来完成线程的管理，包括进程的创建、终止、同步和调度等
2. 由于用户线程的维护由相应进程来完成（通过线程库函数），不需要操作系统内核了解用户线程的存在，可用于不支持线程技术的多进程操作系统；
3. 每个进程都需要它自己私有的线程控制块(TCB)列表，用来跟踪记录它的各个线程的状态信息（PC、栈指针、寄存器），TCB 由线程库函数来维护；
4. 用户线程的切换也是由线程库函来完成，无需用户态/核心态切换，所以速度特别快；
5. 允许每个进程拥有自定义的线程调度算法。

• 用户线程缺点：

用户线程缺点

内核线程

内核线程示意图

1. 在操作系统的内核当中实现的一种线程机制，由操作系统的内核来完成线程的创建、终止和管理。
2. 内核来维护进程和线程的上下文信息(PCB 和TCB)；
3. 线程的创建、终止和切换都是通过系统调用/内核函数的方式来进行，由内核来完成，因此系统开销较大；
4. 在一个进程当中，如果某个内核线程发起系统调用而被阻塞，并不会影响其他内核线程的运行；
5. 时间片分配给线程，多线程的进程获得更多CPU时间。

轻量级线程

内核支持的用户线程，一个进程可以有多个轻量级进程，每个轻量级进程由一个单独的内核线程来支持。

轻量级进程

上下文切换

• 定义：停止当前运行进程，并且调度其他进程

1. 在切换之前，存储许多部分的进程上下文
2. 能够在之后恢复他们
3. 必须快速，因为上下文切换十分频繁

• 需要存储信息：

1. 寄存器(PC、SP...)，CPU状态，...

上下文切换

进程控制

• 创建：系统调用fork()父进程创建子进程

1. 调用fork创建一个继承的子进程
2. 复制父进程的所有变量和内存
3. 复制父程的所有CPU寄存器（有一个寄存器例外）

fork

• 加载：系统调用exec()加载程序取代当前运行进程

exec示意图

• 等待：系统调用wait()父进程用来等待子进程结束

1. 一个子进程向父进程返回一个值，所以父进程须接受这个值并处理
2. 它使父进程去睡眠来等待子进程的结果
3. 当一个子进程调用exit()的时候，操作系统解锁父进程，并且通过exit()传递得到的返回值作为wait()调用的一个结果，如果这里没有子进程存活，wait()立引返回
4. 当然，如果这里有父进程的僵尸等待，wait()立即返回其中一个值（并解除僵尸状态）
5. 父进程可以帮助子进程清除所有资源

• 结束：进程结束后调用exit()

1. 将这程序“ 结果” 作为一个参数
2. 关闭所有打开的文件，连接等等
3. 释放内存
4. 释放大部分支持进程的操作系统结构
5. 检查父进程是否存活：

• 如果是活，它保留的结果直到父进程需要它；进程没有真正死亡，但是它进入了僵尸状态
• 如果是死，它释放所有数据结构，这个进程死亡

6. 清理所有等待的僵尸进程

CPU调度

调度背景

• 定义：从就绪队列中挑选一个进程/线程作为CPU将要运行的下一个进程/线程
• 内核运行调度程序的条件：

1. 一个进程从运行状态切换到等待状态
2. 一个进程被终结

• 调度策略

1. 非抢占式：调度程序必须等待事件结束
2. 抢占式：

• 调度程序在中断被响应后执行；
• 当前进程从运行切换到就绪，或一个进程从等待切换到就绪；
• 当前运行的进程可以被换出。

调度原则

• 一些基本概念：

基本概念

• CPU调度目标：

CPU调度目标

调度算法

先来先服务（FCFS）

1. 根据就绪队列的到达时间来排序，此时就绪队列是一个FIFO队列，先到先服务，算法简单
2. 缺点：

• CPU进程区间变化很大时，平均等待时间会变化很大；
• 可能导致I/O和CPU之间的重叠处理，CPU密集型进程会导致I/O设备闲置时，I/O密集型进程也在等待。

最短作业优先调度（SJF）

1. 按照预测的完成时间来将任务入队
2. 可以是可抢占的或不可抢占的
3. 可能导致饥饿

• 连续的短任务流会使长任务饥饿
• 短任务可用时的任何长任务的CPU时间都会增加平均等待时间

最高响应比优先（HRRN）

1. 在SPN调度的基础上改进
2. 不可抢占
3. 关注进程等待了多长时间
4. 防止无限期推迟

响应比：R = (w + s)/s ，选择R值最高的进程

• w: waiting time 等待时间
• s：service time 执行时间

轮转法调度（RR）

1. 选择固定时间片，时间片到了则切换进程运行
2. 时间片太大：

• 等待时间过长
• 极限情况退化成FCFS

3. 时间片太小：

• 反应迅速，但是切换上下文频繁
• 吞吐量由于大量的上下文切换开销受到影响

4. 目标：

• 选择一个合适的时间片
• 经验规则： 维持上下文切换开销处于1%以内

多级反馈队列调度

1. 实现思路：

• 就绪队列被划分成独立的队列：如前台（交互），后台（批处理）
• 每个队列拥有自己的调度策略：如前台一RR，后台——FCFS
• 调度必须在队列间进行：固定优先级或时间片轮转

2. 具体方案举例：

• 一个进程可以在不同的队列中移动
• 例如：有n 级优先级（优先级调度在所有级别中，RR在每个级别中），时间片大小随优先级级别增加而增加，如果任务在当前的时间片中没有完成， 则降到下一个优先级

多级调度

公平共享调度（FFS）

1. 一些用户组比其他用户组更重要
2. 保证不重要的组无法垄断资源
3. 未使用的资源按照每个组所分配的资源的比例来分配
4. 没有达到资源用率目标的组获得更高的优先级

实时调度

实时系统

• 定义：正确性依赖于其时间和功能两方面的一种操作系统
• 性能指标：

1. 时间约束的及时性
2. 速度和平均性能相对不重要

• 主要特性：

1. 时间约束的可预测性

• 分类：强实时系统；软实时系统

多处理器调度

1. 多处理器的CPU调度更加复杂

• 多个相同的单处理器组成一个另处理器
• 优点：负载共享

2. 多对称处理器(SMP)

• 每个处理器运行自己的调度程序
• 需要在调度程序中同步

多处理器

优先级反转

1. 可以发生在任何基于优先级的可抢占的调度机制中
2. 当系统内的环境强制使高优先级任务等待低优先级任务时发生

进程/线程同步

背景知识

• 独立线程：不和其他线程共享资源和状态，确定性，可重现性
• 合作线程：在多个线程中共享状态，不确定性，不可重现性

1. 资源共享
2. 加速：CPU计算和I/O操作可以重叠
3. 模块化：将大程序拆分为小程序，使系统易于扩展

• 竞态条件：结果依赖于并发执行或者事件的顺序/时间（让指令不被打断可避免竞态条件）；当两个或多个线程竞争同一资源时，如果对资源的访问顺序敏感，即存在竞态条件。

• 原子操作：指一次不存在任何中断或失败的执行

1. 该执行成功结束
2. 或者根不没有执行
3. 并且不应该发现任何部分执行的状态
4. i++，java new一个对象都不是原子操作

临界区

• 定义：导致竞态条件发生的代码区称作临界区
• 互斥：当一个进程处于临界区并访问共享资源时，没有其他讲程会处于临界区并且访问任何相同的共享资源
• 有限等待：如果一个线程i处于入囗区，那么在i的请求被接受之前，其他线程进入临界区的时间是有限制的
• 无忙等待（可选）：如果一个进程在等待进入临界区，那么在它可以进入之前会被挂起

实现方案

• 基于硬件中断

1. 没有中断，没有上下文切换，因此没有并发

• 硬件将中断处理延迟到中断被启用之后
• 大多数现代计算机结构体系都提供指令来完成

2. 进入临界区：禁止中断
3. 离开临界区：开启中断
4. 缺点：

• 一旦中断停用，线程无法停止，整个系统停止，其他线程可能处于饥饿状态
• 如果临界区任意长，无法限制响应中断所需时间
• 要小心使用

基于软件解决方案

• 线程可能共享一些共有的变量来同步他们的行为
• 使用一些标志位来解决线程间同步
• 满足进程Pi和Pj之间互斥的经典的基于软件的解决方法（1981年）：

• 使用两个共享数据项：

基于软件互斥方法

• 一些著名算法：

• Dekker算法（1965）：第一个针对双线程例子的正确解决万案
• Bakery算法（Lamport 1979）：针对n线程的临界区问题解决方案

• 缺点：

1. 复杂：需要两个进程间的共享数据顷
2. 需要忙等待：浪费CPU 时间
3. 没有硬件保证的情况下无真正的软件解决方案：原子操作都需要硬件支持

更高级的抽象

1. 硬件提供了一些原语（中断禁用，原子操作指令），大多数现代体系结构都这样
2. 操作系统提供更高级的编程抽象来简化并行编程（锁，信号量），从硬件原语中构建

锁

1. 定义：锁是一个抽象的数据结构

• 一个二进制状态（锁定/ 解锁），两种方法
• Lock::Acquire() 一 锁被释放前一直等待，然后得到锁
• Lock::Release() 一 释放锁，唤醒任何等待的进程

2. 应用：编写临界区

• lock_next_pid->Acquire();
• new_pid = next_pid++;
• lock_next_pid->Release();

3. 原子操作指令

• 大多现代体系结构都提供特殊原子操作指令，通过特殊的内存访问电路，针对单处理器和多处理器
• Test-And-Set：从内存中读值，测试该值是否为1并返回真或假，内存值设置为1
• 交换：交换两个内存中值

原子操作指令

• 用TestAndSet实现Lock:

TestAndSet

忙等和无忙等待对比：

忙等和无忙等待对比

• 用Exchange实现Lock：

Exchange

优点：

• 适用于单处理器或者共享主存的多处理器中任意数量的进程
• 筒单并且容易证明
• 可以用于支持多临界区

缺点：

• 忙等待消耗处理器时间
• 当进程离开临界区并且多个进程在等待的时候能导致饥哦

信号量

1. 定义：一个抽象数据类型，在早期的操作系统是主要的同步原语

• 一个整型（sem），两个原子操作
• P()：sem减1，如果sem<0，等待，否则继续
• V()：sem加1，如果sem<=0，唤醒一个等待的P

2. 一些基本概念：

• 信号量是整数，信号量是被保护的变量，初始化完成后，唯一改变信号量的是P和V操作
• P能够阻塞，V不会阻塞
• 两种类型：二进制信号量，一般/计数信号量

3. 用途：可以用在互斥，同步

信号量实现互斥

信号量实现同步

4. 信号量实现：

• 使用硬件原语：禁用中断，原子指令（TestAndSet）

信号量的实现

5. 信号量实现生产者消费者模型：

• 生产者消费者模型：一个线程等待另一个线程处理事情，比如生产东西或消费东西

生产者消费者模型

• 正确性要求：

• 在任何一个时间只能有一个线程操作缓冲区（互斥）
• 当缓冲区为空，消费者必须等待生产者（调度/同步约束）
• 当缓存区满，生产者必须等待消费者（调度/同步约束）

信号量实现生产者消费者模型

6. 缺点：

• 读/开发代码十分困难，程序员必须精通信号量
• 容易出错：忘记释放信号量
• 不能处理死锁问题

管程

1. 目的：分离互斥和条件同步的关注，封装了同步操作，对进程隐蔽了同步细节，简化了同步功能的调用
2. 定义：包含若干共享变量及其说明和所有访问这些共享变量的函数所组成的软件模块

管程

3. 实现：

• Condition Variable

• Wait() operation：释放锁，睡眠，重新获得锁返回后
• Signal() operation：唤醒等待者（或者所有等待者）

管程实现

4. 管程实现生产者消费者模型：

image

IPC

• 概述：两个进程或线程间传送数据或信号的一些技术或方法

1. 如果P和Q想通信，需要在他们之间建立通信链路（共享内存，硬件总线，逻辑属性等），通过send/receive交换消息
2. 存在直接通信，间接通信两种方式

进程间通信

3. 直接通信：

进程必须正确的命名对方：

• send(P, message)：发送信息到进程P
• receive(Q，message)：从进程Q接受消息

通启链路的属性:

• 自动建立链路
• 每一条链路恰好对应一对通信进程
• 每对进程之间只有一个链接存在
• 链接可以是单向的，但通常为双向的

4. 间接通信：

定向从消息队列接收消息:

• 每个消息队列都有一个唯一的ID
• 只有它们共享了一个消息队列，进程才能够通信

通信链路的属性:

• 只有进程共享一个相同的消息队列，才建立链路
• 链接可以与许多进程相关联
• 每对进程可以共享多个通信链路
• 链接可以是单向或双向

5. 消息传递分为阻塞和非阻塞两种

• 阻塞：同步
• 非阻塞：异步

6. 通信链路缓冲：

• 0容量：发送方必须等待接收方
• 有限容量(n)：如果队列满，发送方必须等待
• 无限容量：发送方不需要等待

信号(Signal)

1. 定义：软件中断通知事件处理（如SIGFPE, SIGKILL...）
2. 接收到信号时会发生什么：

• Catch: 指定信号处理函数被调用
• Ignore: 依靠操作系统默认操作（如: Abort, memory dump, suspend or resume process）
• Mask：闭塞信号因此不会传送（可能是暂时的）

3. 不足：

• 不能传输要交换的任何数据

信号实现机制

管道（Pipe）

1. 定义：是一系列将标准输入输出链接起来的进程，其中每一个进程的输出被直接作为下一个进程的输入
2. 原理：每创建一个管道，就有两个文件描述符，一个是负责读管道的，一个是负责写管道的。所以，使用管道通信时，可以看作是两个文件描述符加一段内核空间中的内存。
3. 管道只能协调有亲缘关系的进程间通信，所谓亲缘，比如父子进程、兄弟进程。当某进程创建一个管道后，它就拥有了这个管道的两个文件描述符，它的子进程会继承这两个文件描述符，所以子进程也能读写这个管道。
4. 示意图：

管道示意图

消息队列

1. 定义：一个消息的链表，是一系列保存在内核中消息的列表，由消息队列标识符标识
2. 优点：

• 传递消息多，克服了信号传递信息少缺点
• 克服了管道只能承载无格式字节流以及缓冲区大小受限的缺点

消息队列

共享内存

1. 定义：映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问
2. 优点：

• 通信速度最快的 IPC 方式，针对其他进程间通信方式运行效率低而专门设计的
• 进程可以直接读写内存，而不需要任何数据的拷贝

3. 缺点：必须同步数据访问
4. 实现方式：内存映射和共享内存机制两种方式

• 内存映射：==内存映射 memory map机制使进程之间通过映射同一个普通文件实现共享内存，通过mmap()系统调用实现。普通文件被映射到进程地址空间后，进程可以像访问普通内存一样对文件进行访问，不必再调用read/write等文件操作函数== ；
• 共享内存机制：==把所有的共享数据放在共享内存区域（IPC shared memory region），任何想要访问该数据的进程都必须在本进程的地址空间新增一块内存区域，用来映射存放共享数据的物理内存页面==。

5. 原理：

共享内存示意图

死锁

1. 定义：一个进程集合中的多个进程因为竞争资源，而造成的互相等待现象
2. 死锁原因：

• 因为系统资源不足；
• 进程运行推进的顺序不合适；
• 资源分配不当等。

3. 死锁的必要条件：

• 互斥条件（Mutual exclusion）：资源不能被共享，只能由一个进程使用。
• 请求与保持条件（Hold and wait）：已经得到资源的进程可以再次申请新的资源。
• 非剥夺条件（No pre-emption）：已经分配的资源不能从相应的进程中被强制地剥夺。
• 循环等待条件（Circular wait）：系统中若干进程组成环路，该环路中每个进程都在等待相邻进程正占用的资源。

4. 死锁预防：保证系统不进入死锁状态的一种策略。基本思想是要求进程申请资源时遵循某种协议，从而打破产生死锁的四个必要条件中的一个或几个，保证系统不会进入死锁状态。

• 破坏互斥条件。即允许进程同时访问某些资源。但是，有的资源是不允许被同时访问的，像打印机。
• 破坏不可剥夺条件。即允许进程强行从占有者那里夺取某些资源。
• 破坏请求与保持条件。可以实行资源预先分配策略。即进程在运行前一次性地向系统申请它所需要的全部资源。但是此方法有缺点：

a. 一个进程在执行之前不可能知道它所需要的全部资源。这是由于进程在执行时是动态的，不可预测的

b. 资源利用率低。无论所分资源何时用到，一个进程只有在占有所需的全部资源后才能执行

c. 降低了进程的并发性。因为资源有限，又加上存在浪费，能分配到所需全部资源的进程个数就必然少了

• 破坏循环等待条件，实行资源有序分配策略。把资源事先分类编号，按号分配，使进程在申请，占用资源时不会形成环路。此方法也有如下缺点：

a. 限制了进程对资源的请求，同时给系统中所有资源合理编号也是件困难事，并增加了系统开销

b. 为了遵循按编号申请的次序，暂不使用的资源也需要提前申请，从而增加了进程对资源的占用时间

5. 死锁避免：

• 安全序列：系统中的所有进程能够按照某一种次序分配资源，并且依次地运行完毕，这种进程序列{P1，P2，...，Pn}就是安全序列。如果存在这样一个安全序列，则系统是安全的；如果系统不存在这样一个安全序列，则系统是不安全的。

安全序列{P1，P2，...，Pn}是这样组成的：若对于每一个进程Pi，它需要的附加资源可以被系统中当前可用资源加上所有进程Pj当前占有资源之和所满足（其中j<i），则{P1，P2，...，Pn}为一个安全序列，这时系统处于安全状态，不会进入死锁状态。

• 银行家算法：通过先试探分配给该进程资源，然后通过安全性算法判断分配后的系统是否处于安全状态，若不安全则试探分配作废，让该进程继续等待。

6. 死锁的检测与恢复:

• 由于操作系统有并发，共享以及随机性等特点，通过预防和避免的手段达到排除死锁的目的是很困难的。这需要较大的系统开销，而且不能充分利用资源。为此，一种简便的方法是系统为进程分配资源时，不采取任何限制性措施，但是提供了检测和解脱死锁的手段：能发现死锁并从死锁状态中恢复出来
• 死锁检测与恢复是指系统设有专门的机构，当死锁发生时，该机构能够检测到死锁发生的位置和原因，并能通过外力破坏死锁发生的必要条件，从而使得并发进程从死锁状态中恢复出来

a. 最常用的方法就是进行系统的重新启动，不过这种方法代价很大

b. 撤消进程，剥夺资源。终止参与死锁的进程，收回它们占有的资源，从而解除死锁

文件系统

基本概念

• 文件：文件系统中一个单元的相关数据在操作系统中的抽象，一个存储记录序列的数据结构

• 文件属性：名称、类型、位置、大小、保沪、创建者、创建时间、最近修改时间、....
• 文件头：在存储元数据中保存了每个文件的信息，保存文件属性，跟踪哪一块存储块属于逻辑上文件结构的哪个偏移。

• 文件系统：一种用于持久性存储的系统抽象
• 文件系统功能：

1. 分配文件磁盘空间（管理文件块，管理空闲空间，分配算法）
2. 管理文件集合（定位文件及其内容，命名，最常见：分层文件系统）
3. 提供的便利及特征（保护作用：分层来保证安全，可靠性，持久性）

• 文件系统种类：

1. 磁盘文件系统：文件存储在数据存储设备上，如FAT、NTFS、ext2/3
2. 数据库文件系统：文件根据其特征是可被寻址的，如WinFS
3. 日志文件系统：记录文件系统的修改/事件
4. 分布式文件系统：如NFS、SMB、AFS

文件描述符

• 定义：操作系统为每个进程维护一个打开文件表，一个打开文件描述符是这个表中的索引
• 元数据管理打开文件：

1. 文件指针：指向最近的一次读写位置，每个打开了这个文件的进程都这个指計
2. 文件打开计数：记录文件打开次数一当最后一个进程关闭了文件时，允许将其从打开文件表中移除
3. 文件磁盘位置：缓存数据访问信息
4. 访问权限：每个程序访问模式信息

• 在文件系统中的所有操作都是在整个块空间上进行的

• 块是逻辑转换单元，unix中块大小是4KB
• 即使每次只访问1字节数据，也会缓存目标数据4096字节

文件目录

• 定义：磁盘上相关文件的列表，文件以目录方式组织起来的
• 典型操作：文件创建，搜索文件，文件删除，重命名文件，遍历文件，文件列表
• 操作系统只允许内核模式修改文件目录：确保映射完整性
• 目录中文件存储方式：

1. 文件名的线性列表，包含了指向数据块的指针

• 编程简单
• 执行耗时

2. Hash数据结构的线性表

• 减少目录搜索时间
• 碰撞，两个文件名的hash值相同
• 固定大小

• 目录解析过程，以/bin/ls为例：

解析目录

• 挂载点：实际上就是linux中的磁盘文件系统的入口目录，类似于windows中的用来访问不同分区的C:、D:、E:等盘符

挂载点

虚拟文件系统

1. 文件系统分层结构：

文件系统分层结构

2. 目的：对所有不同文件系统的抽象
3. 功能：

• 提供相同的文件和文件系统接口
• 管理所有文件和文件系统关联的数据结构
• 高效查询例程，遍历文件系统
• 与特定文件系统模块的交互

4. 文件系统数据：

• 卷控制块（每个文件系统一个）：文件系统详细信息，块、块人小、空余块、计数/指针等
• 文件控制块（每个文件一个）：文件详细信息，许可、拥有者、大小、数据库位置
• 目录节点（每个目录一个）：将目录项数据结构及树型布局编码成树型数据结构，指向文件控制块、父节点、项目列表等

文件系统数据结构

数据块缓存

• 数据块按需读入内存
• 数据块使用后被缓存，写操作可能被缓存和延迟写入(假设数据将会被再次使用)

磁盘缓存

• 两种缓冲方式：

1. 普通缓冲区缓存
2. 页缓存：统一数据块和内存项

一个页可以映射到一个本地文件中
数据块被映射成页
文件的读/写转换成对内存的操作
可能导致缺页

页缓存

打开文件数据结构

• 打开文件描述符：

1. 每个被打开的文件一个
2. 文件状态信息
3. 目录顶、当前文件指针、文件操作设置等

• 打开文件表

1. 一个进程一个
2. 一个系统级的
3. 每个卷控制块也会保存一个列表
4. 所以如果有文件被打开将不能被卸载

打开文件表

文件分配(数据块)

• 大数文件都很小

1. 需要对小文件提供强力的支持
2. 块空间不能太大

• 一些文件非常大

1. 必须支持大文件(64-bit 文件偏移）
2. 大文件访问需要相当高效

• 分配方式：

1. 连续分配

文件头指定起始块和长度，优势：文件读取表现好，高效的顺序和随机访问，缺点：碎片，文件增长问题（对文件扩容麻烦）

连续分配

2. 链式分配

文件以数据块链表方式存储，文件头包含了第一块和最后一块的指针，优点：创建，增大，缩小很容易，没有碎片；缺点：不可能真正的随机访问，可靠性差

链式分配

3. 索引分配

为每个文件创建索引数据块，文件头包含了数据索引块，优点：创建，增大，缩小很容易，没有碎片，可随机访问；缺点：文件小时存储索引冗余，文件大时索引数据块有容量限制(采用分级索引解决大文件问题，链式索引/多级索引)

索引分配

4. 多级索引

多级索引

• 多级索引存储文件示意图(对大小文件都适用):

多级索引

文件头包含13个指针

• 10个指针指向数据块；
• 第11个指针指向间接接据块；
• 第12个指针指向二级间接接据块；
• 第13个指针指向三级间接接据块。

• 优势/缺点

• 提高了文件大小限制阈值
• 动态分配数据块，文件扩展很容易
• 小文件开销小
• 只为大文件分配间接数据块，大文件在访问间接数据块是需要大量的查询

• 指标：

1. 高效：存储利用（外部碎片）
2. 表现：访问速度

空闲空间列表

• 跟踪在存储中的所有未分配的数据块
• 用位图代表空闲数据块列表：如果该块为空，则该位为1，否则为0

1. 使用简单，但位图会是个大向量，160GB硬盘需要5M位图数据量
2. 需要保证其一致性

• 链式列表/分组列表：

链式/分组列表

多磁盘管理-RAID

• 通常磁盘通过分区来最大限度减小寻道时间

1. 一个分区是一个柱面集合
2. 每个分区都是逻辑上独立的磁盘

磁盘示意图

• 分区：硬件磁盘的一种适合操作系统指定格式的划分
• 卷：一个拥有一个文件系统实例的可访问的存储空间
• 使用多个并行磁盘来增加：吞吐量（通过并行）；可靠性和可用性（通过冗余）
• RAID技术：独立磁盘的冗余阵列

1. 它是一种用于连接多个辅助存储设备以提高性能，数据冗余或两者兼备的技术
2. RAID技术有7个级别的RAID方案。这些模式为：RAID 0，RAID 1，....，RAID 6

• RAID实现:

1. 在操作系统内核：存储/卷管理
2. RAID硬件控制器（I/O）

多磁盘

磁盘调度

• 一个进程需要两种类型的时间，CPU时间和I/O时间；对于I/O，它请求操作系统访问磁盘
• 磁盘访问时间 = 寻道时间 + 旋转延迟 + 传输时间

1. 寻道时间：是将磁盘臂定位到满足读/写请求的指定磁道所用的时间，寻道时间是性能上的区别本质
2. 旋转延迟：期望的扇区将自己倒换到可以访问R / W磁头的位置
3. 传输时间: 传输数据所需的时间

I/O访问时间

• 调度目的：从I/O请求队列中选择一个磁盘请求，并决定处理该请求的时间表，以优化I/O访问时间
• 调度算法：

1. FCFS调度算法（先来先服务）
2. SSTF算法(最短寻找时间优先)
3. SCAN调度

磁臂在一个方向上移动，满足所有未完成的请求，直到磁臂达到该方向上最后的磁道

4. C-SCAN调度：

限制在一个方向上移动，磁臂在一个方向上移动，满足所有未完成的请求，直到磁臂达到该方向上最后的磁道

5. C-LOOK调度：

C-SCAN的改进版，达到该方向最后一个请求处立即停止

6. N-Step-Scan算法：

• 在SSTF、SCAN 及C-SCAN这几种调度算法中，都可能出现磁臂停留在某处不动的情况，例如进程反复请求对某一磁道的I/O操作。我们把这一现象称为“磁臂粘着”。
• N-Step-Scan算法是将磁盘请求队列分成若干个长度为N的子队列，磁盘调度将按FCFS算法依次处理这些子队列。而处理每一个队列又是SCAN算法，对一个队处理完后，再处理其他队列。

6. FSCASN算法:

• 实质上是N 步SCAN 算法的筒化，只将磁盘请求队列分成两个子队列。