计算机系统是由CPU, 内存, 磁盘以及大量外部设备组成的复杂系统. 为了简化应用程序开发的难度, 计算机安装了一层称为操作系统的软件. 操作系统作为硬件的抽象, 为上层的应用程序提供更容易使用的接口; 操作系统同时也作为资源管理者, 管理底层的硬件, 并为上层的多个用户/程序提供资源.

而在另一本计算机书籍<<操作系统导论>>中, 作者认为操作系统的核心特点是虚拟化, 并发和持久性. 这三个特性解释了如何使用CPU和内存, 如何管理磁盘数据等操作系统的核心功能.

第一章绪论

计算机系统的历史

真空管与穿孔卡带阶段(1945 ~ 1955)
- 通过硬连接线路&打孔纸带进行编程, 并不存在操作系统
- 由一道程序独占机器, 需要人工进行操作
晶体管和批处理系统(1955 ~ 1965)
- 将一批任务收集起来提交给计算机进行执行. 计算机执行完一个任务后切换到下一个任务
- 使用不和主机直接相连的专用输入输出设备(卫星机)
- 卫星机将数据转入速度较快的磁带机中, 主机与磁带机交换数据
- 解决了作业自动转接的问题, 输入和计算可以并行, 提高了CPU的利用率
集成电路与多道程序设计(1965 ~ 1980)
- 计算机的内存中可以同时存在多道程序
- 宏观上这些程序并行, 微观上这些程序交替执行
- 处理机的时间分成时间片, 按照时间片轮流将处理机分配给各个作业
- 由于时间片很短, 因此每个用户都感觉自己独占计算机
- 由各个程序自行决定是否放弃CPU, 从而让其他程序执行
个人计算机(1980 ~ 至今)
- 在个人计算机上运行的Linux, Windows和Unix等系统
移动计算机(1990 ~ 至今)
- 在移动设备上运行的Android等系统

x86-64 Core体系结构历史

x86-64处理器是对x86-32处理器的扩展. 第一个支持x86-32的处理器是1985年推出的Intel 80386微处理器. 80386是对16位体系的80286的扩展, 具有32位寄存器和4GB虚拟地址空间, 使用一个独立的, 称为80387的浮点单元进行浮点运算.

1993年推出的奔腾CPU基于P5架构, 支持MMX技术, 能够对64位大小的寄存处执行单指令多数据(SIMD)操作. 1995年推出P6架构, 并在1997年推出的奔腾II中引入三路超标量设计, 使得CPU能够平均在每个周期内解码, 分派和执行三条不同的指令. 此外还引入了无序指令执行, 改进的分支预测等优化.

1999年推出的奔腾III也基于P6架构, 并且支持一种称为 Streaming SIMD Extension, SSE的指令集, 从而能够对8个128位的寄存处进行操作. 2006年, Intel推出Core架构, 支持SSE3和SSE4.1指令集. 2008年推出Nehalem架构, 再次引入超线程技术并支持SSE4.2指令集. 2011年推出Sandy Bridge架构, 引入一种新得SIMD技术, 称为Advanced Vector Extension, AVX. 2013年推出Haswell架构, 支持AVX2指令集和FMA(乘法加法融合)操作. 2017年推出的Skylake-X架构支持了AVX-512指令集, 能够操作512位的寄存器.

与此同期, AMD在2003推出一系列基于K8架构的CPU, 能够支持MMX, SSE和SSE2指令集. 2007年推出K10架构, 支持一种对SSE的扩展指令集SSE4a. 2011年推出Bulldozer架构, 支持SSE3, SSE4.1, SSE4.2, SSE4a和AVX指令集.2017年推出Zen架构, 支持AVX2指令集.

The History Of Intel CPUs: Updated!

操作系统的功能

处理机管理
存储管理
设备管理
文件系统管理
用户接口

操作系统内核架构

简要结构: 应用程序和操作系统位于同一个地址空间, 不实现内存管理, 特权级隔离等功能, 例如MS-DOS系统.
宏内核:操作系统的所有模块(进程调度,内存管理,文件系统,设备驱动等)都运行在内核态, 例如Linux系统.
微内核:内核仅保持最基础的功能,其他模块作为独立的服务, 例如Mach系统.
外核架构: 由应用程序控制硬件资源, 对硬件的抽象封装到LibOS,与应用程序之间链接.
多内核架构: 解决CPU核数越来越多, 使用异构CPU的场景. 对每个核抽象一个节点.
混合内核架构: 由于发展的需要, 各种架构之间存在一些混合使用的情况.

宏内核由于集成了所有的功能, 因此对于不同架构的扩展性较低; 由于代码量更大, 因此安全性方面无法有效的保证, 且大量功能运行在内核空间, 容易出现单点故障. 微内核功能精简, 更容易保证安全性, 但进程间通信开销更大, 容易造成性能低下.

Amdahl定理

当我们对系统中的某个部分进行加速时, 假定该部分占整个系统的比例为$\alpha$, 该部分的提升比例为$k$, 则可知加速后的时间为

$$
T_{new} = (1 - \alpha) T_{old} + \alpha T_{old} / k
$$

则可以计算出加速比为:

$$
S = \frac{1}{(1-\alpha) + \alpha / k}
$$

通过该公式可以容易的知道, 对某个部分进行提升后, 从总体上看的提升效果是小于单独一个部分的. 因此如果想使整个系统加速, 则需要在相当大的部分进行加速.

并发与并行

线程级并发

在单核处理器的情况下, 操作系统通过在多个线程间快速切换, 实现一种似乎所有线程均在同时执行的感觉. 但在微观层次, 每次依然只有1个线程在执行.

在引入多核处理器后, 每个处理器均可执行一个线程, 此时就实现了多个线程的并行.

超线程技术. 在传统的CPU执行模式下, CPU并不是所有部件都在工作, 很多时候一些部件处于闲置状态. 因此在其他硬件(例如浮点运算单元)仅存在一份的同时, 对CPU的某些硬件进行冗余(例如程序计数器和寄存器), 通过合适的调度可以使CPU同时执行两个不同的指令, 就好像这个物理上的核心具有两个逻辑上的核心.

处理器可在单个时钟周期内切换线程, 而常规的处理器线程切换大约需要20000时钟周期

因此超线程技术可以提高CPU的性能, 但相较于两个物理上的核心, 超线程技术模拟的逻辑核心性能还是更低一些.

超线程无用论？超线程有没有用，看完你就懂了。_哔哩哔哩_bilibili

指令级并行

在1978年的 Intel 8086 处理器上, 执行一条指令需要3~~10个时钟周期. 而现在的处理器可以在每个时钟周期执行2~~4条指令. 可在一个时钟周期内执行超过1条指令的处理器也被称为超标量(super-scalar)处理器.

处理器通过流水线技术实现并行, 虽然一条指令可能需要几十个时钟周期, 但通过设置多级流水线, 依然可使得每个时钟周期都可以完成一条指令.

处理器通过超标量技术实现在一个时钟周期内同时发射（issue）和执行多条指令. 其核心是原理是在CPU中内置多个译码和计算模块, 使得一个时钟周期内可以译码多条指令并且根据数据的依赖关系重排执行顺序. 以苹果的M2芯片为例, 其具备6个译码器和12个ALU. 超标量的实现有点类似多核CPU, 但层次更低, 与底层实现结合更紧密.

单指令多数据并行

现代处理器提供了一类特殊指令, 该指令可并行的对多个数据进行处理. 因此该方式被称为单指令多数据(SIMD)并行.

扩展: 常见操作系统与指令集

以下简要介绍一下不同的操作系统和指令集的含义:

常见的操作系统类型有windows, linux和darwin, 其中darwin是苹果公司Mac OS X操作系统的核心部分, 该名称来自于19世纪的英国自然学家查尔斯达尔文(Charles Darwin)

常见的指令集有x86_64, armv6, armv7和aarch64. 其中aarch64(也称为AArch64)是一种64位的指令集架构, 是armv8架构的一部分. 实际上, armv7和以前的版本都是32位架构, 从armv8开始进入64位架构. 苹果的M1系列芯片也属于aarch64架构.

第二章用户界面

系统调用

设备管理, 用于请求和释放相关的设备, 以及启动设备操作等
文件管理, 包括对文件的读, 写, 创建和删除等
进程管理, 包括进程的创建, 执行, 撤销, 等待, 执行优先级控制等
进程通信, 用于在进程之间传递消息或信号
存储管理, 包括检查作业占据的内存大小, 获得作业内存地址等
线程管理, 包括线程的创建, 调度, 执行和撤销等

陷阱机构与陷阱指令

在系统中为控制系统调用服务的处理机构称为陷阱处理机构
由于系统调用因此处理机中断的指令称为陷阱指令(或访管指令)
陷阱指令传递参数有三种方法
1. 陷阱指令自带的参数
2. 专用的寄存器
3. 内存中专门开辟的堆栈区

第三章进程管理

进程与线程

进程是并发执行的程序在执行过程中分配和管理资源的基本单位, 具有以下特点

进程是一个动态概念, 而程序是一个静态概念
进程具有并发特性, 而程序没有
进程是竞争计算机系统资源的基本单位, 并发受到系统约束
不同的进程可以包含同一程序, 只要该程序对应的数据集不同

进程是资源的拥有者, 也是调度单位, 但是线程不拥有资源, 只是一个调度单位, 从而能更加方便的进行调度.

进程控制块

进程的静态描述由三部分组成, 进程控制块(PCB), 有关程序段, 该程序段操作的数据集, 进程控制块具有如下结构

描述信息
- 包括进程名, 用户名和进程家族关系等
控制信息
- 包括进程的当前状态, 进程优先级, 程序开始地址, 各种计数信息, 通讯信息
资源管理信息
1. 占用内存大小以及管理数据的指针
2. 对换或覆盖的有关信息
3. 共享程序段大小以及起始位置
4. 输入输出设备的设备号
5. 指向文件系统的指针以及有关标识
CPU现场保护结构
- 一个专门的用于保存CPU数据的结构, 可以用于进程中断后的恢复

总之, PCB是系统感知进程的唯一实体, 通过对PCB的操作, 系统为有关进程分配资源从而使的有关进程得以被调度和执行, 执行结束后, 也通过释放PCB来释放进程所占有的各种资源.

进程上下文

进程上下文是进程执行过程中顺序关联的静态描述
已执行过的进程指令和数据在相关寄存器中的内容称为上文
正在执行的指令和数据在寄存器中的内容称为正文
待执行的指令和数据在寄存器中的内容称为下文

进程上下文切换

进程上下文的切换一般分为三个部分

保护被切换进程的正文部分至有关存储区
操作系统进程中, 有关调度和资源分配的程序执行, 并选择新的进程
将被选中的进程的正文部分从有关存储区恢复到有关寄存器和堆栈, 激活被选中进程执行

进程状态和转换

进程至少可以分成五个状态：初始状态, 执行状态, 等待状态, 就绪状态, 终止状态
一个进程被创建后, 处于初始状态
处于就绪状态的进程得到了除CPU以外的所有资源, 只要被调度就可以立即执行, 进入执行状态
处于执行状态的进程有三种转移状态
1. 时间片到达, 回到就绪状态
2. 由于某些事件, 进入等待状态
3. 完成程序, 进入终止状态
处于等待状态的程序在某些事件的唤醒下, 进入就绪状态

进程控制

1. 进程创建

查询PCB总链,是否有同名进程
如果有,则报错,否则向PCB资源池申请一个空PCB结构
如果不能获得申请,报错,否则填写PCB有关内容
将PCB放入就绪队列和PCB总链

2. 进程撤销

查询进程链表或进程家族
如果没有查到此进程,报错,否则查询该进程是否有子进程
如果有,递归的撤销子进程
释放该进程占用的资源
释放PCB结构本身

3. 进程阻塞

保存当前进程的CPU现场
设置该进程状态
该进程进入等待队列
转进程调度

4. 进程唤醒

从等待队列取出进程
将此进程置为就绪态
将进程送入就绪队列
转进程调度或返回

进程互斥

不允许多个并发程序交叉执行的一段程序称为临界区
由共享公共资源而造成的对并发进程执行速度的间接制约, 简称间接制约
一组并发进程中的一个或多个程序段, 因共享某一共有资源而导致它们必须以一个不允许交叉执行的顺序执行, 称为互斥

信号量和PV原语

信号量sem是一个整数, 当sem大于零时, 表示并发进程可以使用的实体数量, 当sem小于零时, 表示正在等待使用临界资源的进程数.

原语是在系统态下执行的, 完成系统特定功能的程序段. 是一个不可分割的操作,不允许被中断,不能并发执行.

P原语操作主要动作如下
1. --sem
2. 若sem仍大于等于零, 则P原语返回, 该进程继续执行
3. 若sem小于零, 则该进程被阻塞后, 进入该信号量的等待队列, 然后转进程调度
V原语操作的主要动作如下
1. ++sem
2. 若sem仍大于零, 则V原语返回, 该进程继续执行
3. 若sem小于等于零, 则从该信号的等待队列中唤醒一个进程, 然后返回原进程执行或转入进程调度
遇到临界区的时候, 在临界区的两端分别加上P原语和V原语即可完成互斥操作

进程同步

建立两个互补的私有信号量, 通过交叉判断进行同步操作

S1()
{
	...
	P(empty)
	写入数据
	V(full)
	...
}

S2()
{
	...
	P(full)
	取出数据
	V(empty)
	...
}

其中Sa和Sb一个置为0,一个置为1
S1进程执行之前, 会先判断缓冲区是否为空, 确定为空后写入数据, 最后使用V原语唤醒可能等待的S2进程
S2进程执行之前, 会先判断缓冲区是否已满, 确定已满后取出数据, 最后使用V原语唤醒可能等待的S1进程

进程的一般模型

1.生产者-消费者模型

进程之间的资源申请和释放问题可以看作一个生产者-消费者问题, 使用资源的进程可以看为消费者, 而释放资源的进程可以看为生产者, 一般而言这些进程的代码具有如下的结构

deposit(data)
{
	P(avail)
	P(mutex)
	写入数据
	V(full)
	V(mutex)
}

remove(data)
{
	P(full)
	P(mutex)
	取出数据
	V(avail)
	V(mutex)
}

其中avail和full信号量是私有信号量, 用于两个不同进程的同步
mutex信号量是共有信号量, 用于各个进程之间的互斥
V原语因为是释放操作, 因此通常没有顺序要求
注意:要先执行同步P操作, 再进程互斥P操作, 从而确保互斥锁定之前, 获得执行机会的进程一定可以执行完毕, 避免进程死锁

2.读者-写者模型

有两组并发的进程：读者和写者, 其中要求任何时刻, 写者之间互斥, 读者与写者互斥, 读者之间可以同时读取

writer(data)
{
	P(w);
	写入数据
	V(w);
}


reader(data)
{
	P(R);
	++Rcount;
	if (Rcount == 1){
		P(w);
	}
	V(R);
	...
	读取数据
	...
	P(R);
	--Rcount;
	if(Rcount == 0){
		V(w);
	}
	V(R);
}

对于写者, 只要开始访问数据, 就可以直接锁定
对于读者, 只有第一个需要互斥写者, 只有最后一个需要释放锁定, 因此需要使用一个计数器
因为多个进程访问计数器, 因此计数器的读写需要锁定

3.哲学家吃饭模型

一共有5个哲学家, 每个哲学家之间有一个筷子
哲学家拿到两个筷子时才能开始进餐
当一个哲学家拿到一个筷子以后, 除非拿到另外一个筷子并完成进餐, 否在绝对不会放下手中的筷子
实际上, 进一步分析可知, 如果限制最大吃饭人数, 即限制最多4人同时吃饭, 则可以保证4人中, 至少有一人可以获得两个筷子, 从而完成吃饭

main()
{
	int chopstick[5] = {1};
	int count = 4;
	cobegin
		eat[0]();
		eat[1]();
		...
		eat[4]();
	coend
}


eat[i]()
{
	think;
	P(count);
	P(chopstick[i]);
	P(chopstick[(i+1) mod 5]);
	eat;
	V(chopstick[i]);
	V(chopstick[(i+1) mod 5]);
	V(count);
	think;
}

4.理发问题

有一个理发师, 一把理发椅和n把供等待客户坐的椅子
如果没有顾客, 理发师在理发椅上休息
当有一个顾客到来时, 唤醒理发师进行理发
当理发师在理发的时候, 如果有新顾客到来, 则判断等待区是否有空闲, 如果有则等待, 否在离开

main()
{
	int customers = 0;
	int barbers = 1;
	int wait = 0;

	cobegin
		Barber();
		Customer();
	coend
}

Barber()
{
	while()
	{
		P(customers);
		wait = wait - 1;
		理发;
		V(barbers);
	}
}

Customer()
{
	if(wait<n)
	{
		wait = wait + 1;
		V(customers);
		P(barbers);
		理发;
	}
	else
	{
		离开理发店;
	}
}

扩展:多核CPU如何实现锁

对于单核CPU, 在必要时, 可通过关中断使CPU不再响应时钟中断, 从而使当前线程不会被切换. 此时可以直接执行任意访问临界区的操作.

但对于多核CPU, 关闭一个CPU的中断并不能保证其他CPU对临界区的访问. 因此现代操作系统通常使用硬件提供的Compare-and-Swap(CAS)指令实现原子操作.

在x86和x86-64架构中，CAS操作对应的汇编指令是CMPXCHG（Compare and Exchange）。CMPXCHG指令接受两个操作数：一个是内存操作数，另一个是寄存器操作数。指令将内存操作数与寄存器操作数进行比较，如果相等，则将另一个寄存器操作数写入内存；如果不相等，则将内存操作数的值加载到寄存器操作数中。

1	cmpxchg eax, [ebx] ; 比较eax和内存地址ebx处的值，如果相等，则将ecx的值写入ebx处的内存

在ARM架构中，CAS操作对应的汇编指令是LDREX（Load Exclusive）和STREX（Store Exclusive）。LDREX指令用于原子地加载内存值到寄存器，而STREX指令用于原子地将寄存器值存储到内存。STREX指令会返回一个状态值，指示存储操作是否成功。如果在LDREX和STREX之间有其他操作修改了内存值，STREX将失败。

ldrex r3, [r0]  	; Load the value from the shared memory location 
cmp r3, r1 			; Compare the loaded value with the expected value
bne cas_fail 		; If the values are not equal, exit
strex r3, r2, [r0]	; Attempt to store the new value to the shared memory location
cmp r3, #0			; Check if the store was successful (r3 == 0)
bne cas_operation	; If the store was not successful, retry the operation
bx lr				; CAS operation was successful, return

LDREX指令在读取内存后还会写入一个独占标记, 如果其他线程修改了此内存, 将导致独占标记失效, 并最终导致STREX失败

在MIPS架构中，CAS操作对应的汇编指令是LL（Load Linked）和SC（Store Conditional）。LL指令用于原子地加载内存值到寄存器，而SC指令用于原子地将寄存器值存储到内存。SC指令会返回一个状态值，指示存储操作是否成功。如果在LL和SC之间有其他操作修改了内存值，SC将失败。

1
2
3

ll    $t1, 0($t0) ; 原子地加载内存地址$t0处的值到寄存器$t1
addi  $t1, $t1, 1 ; 将寄存器$t1的值加1
sc    $t1, 0($t0) ; 原子地将寄存器$t1的值写入内存地址$t0处，并将状态值存储到寄存器$t1

基于以上知识, 现在就不难理解Java为什么要重新使用CAS指令实现锁机制了. 与其使用操作系统在CAS指令的基础上封装的锁, 不如直接使用CAS指令实现需要的数据结构.

进程通信

直接通信
- 在发送和接受时, 都需要制定双方的标识
间接通信
- 借助共享的数据结构进行通信

进程间的通信方式

主从式
- 主进程可以自由的使用从进程的资源或数据
- 从进程的受到主进程的控制
- 实际上是一种控制关系
会话式
- 使用进程在使用服务进程提供的服务以前, 必须获得服务进程的同意
- 服务进程根据使用进程的要求提供服务, 但所提供的服务的控制由服务进程完成
- 实际上是一种调用关系
消息或邮箱机制
- 只要存在空缓冲区或邮箱, 发送进程就可以发送消息
- 发送进程和接受进程之间没有直接的联系
- 实际上是一种平等的关系
共享存储区方式
- 共享存储区不需要移动数据
- 两个进程通过对同一共享存储区进行操作实现互相通信
- 这个共享区是每个互相通信的进程的一个组成部分
文件共享方式
- 借助文件系统原有机制进行通信

消息的结构

发送进程名
接受进程名
数据
数据的相关操作

消息缓冲机制

在发送进程把消息写入缓冲区和把换从区挂入消息队列时, 应禁止其他进程对该缓冲区消息队列的访问
缓冲区中无消息存在时, 接受进程不能收到任何消息

Send(B,m)
{
	向系统申请一个缓冲区;
	P(mutex);
	将发送区消息m送入新申请的消息缓冲区;
	把消息缓冲区挂入接收进程的消息队列;
	V(mutex);
	V(SM);
}

Receive(A,n)
{
	P(SM);
	P(mutex);
	摘下消息队列中的消息n;
	将消息n冲缓冲区复制到接收区;
	释放缓冲区;
	V(mutex);
}

邮箱通信

邮箱由邮箱头和邮箱体组成, 邮箱头总包含相关的身份信息, 邮箱体中是需要传输的数据
两个进程之间是简单的同步问题, 按照同步问题加锁即可

死锁的必要条件

互斥条件：进程要求对所分配的资源进行排他性控制, 即在一段时间之内某资源仅为一一个进程占有
部分分配, 进程每次申请它所需要的一部分资源, 在等待新资源的时候, 不释放已经占有的资源
不剥夺条件：进程已经获得的资源, 在没有使用完毕之前, 不能被剥夺
环路条件, 存在进程链循环, 循环中每个进程已经获得的资源被下一个进程请求

死锁的排除方法

预防死锁：采取某种措施, 限制并发进程对资源的请求, 从而破坏产生死锁的必要条件中的一个或几个来防止死锁
- 互斥条件是设备的固有特性, 不仅不能改变, 而且还应该加以保护
- 摒弃”请求和保持”条件：资源预分配策略：运行前一次性分配给进程所有需要的资源
  - 优点：简单易行且安全
  - 缺点：资源浪费, 进程延时运行
- 摒弃”不可剥夺”条件
  - 缺点：实现复杂, 系统代价很高
- 摒弃”环路等待”条件：把系统资源按照类型排序, 进程要按照资源的序号递增的次序提出资源申请
  - 优点：比上述两种方法的综合性能要好
  - 缺点：限制了进程对资源的请求, 同时给系统中所有资源编号增加来系统开销
避免死锁：系统在分配资源时, 根据资源的使用情况预测是否会产生死锁
- 银行家算法
  1. 判断分配条件, 并尝试分配
  2. 分配后进行安全性检测, 如果安全则接受分配, 否则撤销分配
  3. 安全性检测即在当前分配完成后,是否存在方案可以使后续进程都能分配需要的资源并完成
- 银行家算法数据结构
  - Available m元素的数组,表示资源可用总数
  - Max[i,j] 进程i对资源j的最大使用量
  - Allocation[i,j] 进程i当前已经获得的资源j的数量
  - Need[i,j] 进程i还需要的资源j的数量
  - Request 当前请求分配的资源数组
- 安全性检测数据结构
  - Work m元素向量,表示当前可以分配的资源,初始值Word = Available
  - Finish n元素向量,表示任务是否可完成
死锁的检测和恢复
- 通过死锁检测算法检测系统中是否有死锁
- 通过中止进程, 强制剥夺资源等方法解除死锁

第四章处理机调度

调度层次

作业调度：宏观调度, 高级调度
- 按一定原则选择外存后备队列中的作业, 为其分配内存等资源, 并建立进程
- 在作业执行完毕后, 回收系统资源
交换调度：内外存交换, 中级调度
- 按给定的策略, 将外存中处于就绪状态或等待状态的进程调入内存, 或将内存中暂时不使用的进程调至外存
- 提高内存利用率和系统吞吐量
进程调度：微观调度, 低级调度
- 决定就绪队列中那个进程获得处理机
线程调度
- 可有OS内核完成, 也可由用户程序进行

作业的状态

提交状态
- 一个作业处于从输入设备进入外存的过程时处于的状态
后备状态
- 作业的全部内容都通过输入设备输入到外存输入井中, 等待进入内存
执行状态
- 作业一旦被作业调度程序选中, 则为其分配所需的资源, 并创建进程, 送入内存中投入运行
完成状态
- 作业运行完毕, 准备退出系统时的状态（所占用的资源尚未全部被系统回收）

面向用户的性能指标

周转时期
- 作业从提交到完成所用的时间
- 包括平均周转时间和平均带权周转时间
- 平均带权周转时间的权值为 1/运行时间
响应时间
- 用户发出命令(例如键盘按键)到系统给出响应的时间(例如屏幕输出字符)

面向系统的性能指标

吞吐量
设备利用率
设备均衡利用
公平性
优先级

调度算法的衡量

易于实现
运行开销小

进程调度功能

记录所有进程的执行情况（静态和动态）
按一定策略, 选择一个就绪进程
完成进程上下文切换

进程上下文切换步骤

检查是否可以进行进程切换
保存被切换进程现场
选择一个新进程
恢复被选中进程现场

引起进程调度的原因

正在执行的进程执行完毕, 或由于某种错误而中止
执行中的进程自己调用阻塞原语, 将自己阻塞进入等待
执行P原语
执行V原语, 激活
提出I/O请求后被阻塞
执行完系统调用后
分时系统中时间片到
一个高优先级的进程就绪（可抢占式系统）

进程调度方式

非抢占式
- 某一进程被调度后, 将一直执行到完成或者被阻塞
- 即是由于自身的原因而让出CPU
抢占式
- 由于优先权, 短作业优先或时间片到等原因, 系统强制剥夺正在执行的进程的CPU

进程调度性能衡量

定性衡量
1. 公平性
2. 可靠性
3. 简洁性
定量评价
1. CPU利用率
2. 响应时间
3. 吞吐量

调度算法

先来先服务
短作业优先
- 每次一个任务执行完毕后,从当前等待的队列中选择耗时最短的作业
最高响应比法
- 响应比 = 响应时间 / 运行时间
- 响应时间 = 作业等待时间+预计执行时间
- 响应比 = 1 + 作业等待时间 / 运行时间
- 每次一个任务执行完毕后,从当前等待队列中选择响应比最高的作业
时间片轮转法
- 所有作业排成一个FIFO队列
- 依次选择队首进程执行一个时间片,时间片到后回到队尾
- 在执行过程中,如果任务结束,可以提前结束时间片,开始下一个作业的调度
多级队列法
- 可以设置多个队列,每个队列可采取不同的调度算法
优先级算法
1. 静态优先级
  - 所有进程根据各种因素确定一个优先级,在执行过程中始终不变
2. 动态优先级
  - 在执行过程中动态改变优先级,从而获得更好的调度效果
  - 例如,等待时间越长,优先级越高
  - 例如,每执行一个时间片,降低一个优先级
多级反馈轮转法
- 设置多个队列,赋予不同优先级
- 优先级越低,时间片越长
- 新进入的进程首先进入优先级最高的等待队列
- 如果一个时间片内进程未能执行完毕,则降级到下一个优先级队列(直到最低一级)
- 高优先级队列为空是,才调度低优先级的进程

扩展:多核CPU的缓存

通常CPU内会设置多级缓存以加速对内存的读写. 缓存的读写速度远高于内存, 并且可以按块从内存读取数据或者将数据写入内存.

对于单核CPU, 由于仅1个CPU访问缓存, 因此不存在一致性问题. 但对于多核CPU, 每个CPU除了共享一个公共的缓存以外, 还各自具有一个独立的缓存. 一个CPU读写自己独立的缓存后, 需要通过一种同步机制使其他CPU能感知改变换, 并主动废弃或刷新自己的缓存, 才能保证最终的数据一致性.

扩展:多处理器调度

与单核CPU的调度算法相比, 多核CPU主要需要考虑2个问题

如何使某个任务尽可能保持在1个CPU上执行, 从而尽可能的利用缓存数据
如何平衡不同CPU上执行的任务, 使得每个核心上的负载尽可能接近

相较于单核CPU的调度算法, 多核CPU通常仅需要对每个核心维持一个队列, 即可较好的复用原有算法, 并且避免产生较大的锁开销.

由于每个CPU核心都具有独立的缓存, 因此一个任务在一个核心上运行比在多个核心上运行更容易命中缓存. 良好的调度算法应该使一个任务尽可能只在一个核心上运行, 该特性通常称为缓存亲和性.

在保持缓存亲和性的情况下, 容易造成各个CPU的负载不均衡. 针对此问题, 通常可以采取对工作窃取机制, 即处于空闲的CPU从其他CPU的队列中获取一个或多个任务. 然而以多大的频率进行检查是一个尚无定论的参数. 频率过高将产生较大的开销, 而频率过低又会导致负载不均和的问题较为严重.

工作窃取机制在各类语言的并发模型中均有涉及, 是保证任务均衡的一种常见思路.

扩展:NUMA非统一内存访问

在PC中, 通常只有1颗CPU, 虽然其内部具有多个核心, 但本质上还是使用同一个内存控制器访问内存. 而在服务器领域, 为了进一步提升性能, 通常会使用多路CPU架构. 此时在一个设备上具有多个CPU, 每个CPU都具有独立的内存控制器. 在CPU数量较多的情况下, 全部通过同一根总线访问数据会产生非常激烈的总线竞争问题. 为了解决这一问题, 引入了NUMA架构.

NUMA架构将多个 CPU 和与之直接相连的内存组合成一个独立的单元, 这个单元就叫 NUMA 节点. 每个 NUMA 节点内部有自己本地的 CPU 和内存, 多个 NUMA 节点之间通过一条高速互联链路连接起来. 当一个 CPU 核心要访问它所在 NUMA 节点的本地内存时, 路径非常短, 速度非常快. 而当一个 CPU 核心需要访问另一个 NUMA 节点的内存时, 它必须通过节点间的互联链路, 路径更长, 速度更慢.

因此操作系统在进行任务调度时, 需要对NUMA节点进行特殊处理, 确保CPU和相应的内存在同一个节点. 否则由于内存访问的耗时增加, 在计算密集型场景中会出现显著的速度降低.

扩展:Linux多核调度算法

在Linux中，多核调度算法是用于在多核处理器上分配任务的重要机制。以下是一些常见的多核调度算法及其主要思想：

完全公平调度器（CFS, Completely Fair Scheduler）
- 主要思想：CFS旨在为每个进程提供公平的CPU时间。它通过红黑树来管理进程队列，根据进程的虚拟运行时间（vruntime）来决定下一个要运行的进程。vruntime是实际运行时间与进程权重的比值，权重高的进程会获得更多的CPU时间。
- 优点：能够有效地防止饥饿现象，确保每个进程都能得到合理的CPU时间。
- 缺点：在高负载情况下，可能会有较高的调度开销。
多处理器调度（MP-Scheduler）
- 主要思想：MP-Scheduler是为多处理器系统设计的调度器，它将任务分配到不同的CPU核心上，以最大化系统的整体性能。它使用负载均衡算法来确保各个核心的负载尽可能均匀。
- 优点：能够有效地利用多核处理器的并行处理能力。
- 缺点：在核心间迁移任务时可能会引入额外的开销。

第五章存储管理

程序逻辑结构

程序地址:用户编程时使用的地址
程序地址空间:用户的程序地址集合,总是从0开始编制,但既可以是一维空间也可以是多维空间

逻辑地址,物理地址与地址映射

逻辑地址(相对地址,虚地址): 用户的程序编译后使用的地址,通常是相对地址,且假设首地址是0,并且相对此地址进行编址
物理地址(绝对地址,实地址): 内存中存储单元的地址
地址映射:将逻辑地址转化为物理地址

虚拟存储器

为用户提供一种不受物理存储器结构和容量的限制的存储技术
使得用户编程时不需要考虑物理存储器的结构和容量
每个进程都有自己的虚存,且虚存大小不受物理存储器容量的限制

虚拟存储器物质基础

两级存储结构: 内存与外存储器
地址变化机构: 实现逻辑地址与物理地址的转化

虚拟存储器原理

程序运行时,不将全部的数据调入内存,只调入当前需要的部分
在程序执行过程中,如果需要访问的部分不再内存中,处理器通知操作系统将相应的程序或数据调入内存,然后继续执行
将内存中暂时不使用的数据移出内存,保存到外层,从而腾出内存空间

存储管理功能

存储分配与回收
地址变换
- 程序加载时的重定位技术
- 程序运行时的地址变换机构和技术
存储共享与保护
- 代码和数据的共享,提高内存利用率
- 限制在各自的内存区域内操作,互不干扰
存储器扩充方式
- 覆盖
- 交换
- 请求调入 / 预调入

重定位

在可执行文件装入时需要解决可执行文件中地址(包含指令和数据的地址)和内存地址的对应. 有三种重定位方式

绝对装入:编程或编译时确定绝对地址
静态地址重定位: 程序执行前,由装入程序完成地址映射,程序执行过程中,映射关系始终不变
动态地址重定位: 处理机执行程序时,由地址映射机构动态的完成地址映射

存储保护方法

界限保护(上界/下界寄存器或基址/限长寄存器)
- 所有访问都限定在指定的范围中,否在产生越界错误
- 由硬件判断是否允许访问,如果不允许则产生越界中断,由操作系统进行处理
访问方式保护(保护键)
- 对于允许多个进程共享的存储区域,每个进程都有自己的访问权限
- 如果一个进程对共享区域的访问违反了权限规定,则发生操作越权 (即读写保护)
- 为每一个被保护内存区域指定保护键和若干禁止的访问方式,同时进程指定保护键开关
- 如果访问时键值不匹配而且是被禁止的访问方式,则产生访问出错中断

内外存数据传输控制

由应用程序控制
- 覆盖
由OS控制
- 交换(整个进程空间)
- 虚拟存储(部分进程空间)
  - 请求调入
  - 预调入

页式存储管理

目标是解决分区管理内存利用率不高的问题
将逻辑空间分页和内存空间分块,页和块大小相等
当用户程序装入内存时,以页为单位装入
逻辑上连续的页可以装入物理上不连续的块中

地址映射方式

以2进制来看,低位部分是页类位移,高位即为页号

联想存储器

在页式存储技术中,每次都需要访问内存两次,严重影响系统效率(一次访问页表,一次访问内存)
因此使用联想存储器来加速查询速度
类似与Cache,但联想存储器和页表是并行查询

请求页式存储管理

纯页式管理提高了内存利用率,但还是不能为用户提供虚存
当用户程序页面数大于当前空闲内存块数时,系统还是不能装入此程序
用户程序依然受到物理内存大小限制
请求时页式存储管理技术的目标即解决上述问题

请求页式管理的区别

当用户程序要调入内存时,不是全部装入,而是只装入部分页
在程序运行过程中,如果发现需要访问的数据不在内存,则向系统发出缺页中断
系统将相应的页调入内存,程序继续运行

请求页式管理的数据结构变化

从调入角度,需要添加标志位,用于判断是否已经调入
从调出角度,需要添加标志位,用于判断最近是否访问,是否修改等
此外还需要记录有关数据在外存中的地址,以便以后续的调入

调度策略

预调入
请求调入

淘汰(置换)算法

随机淘汰法
- 随机选择一个页换出
轮转法和先进先出法
- 轮转法循环的换出内存中的某些块,这些块可能已经驻留很长时间,也可能刚刚调入
- 先进先出法每次淘汰内存中驻留时间最长的页
最近最久未使用算法
- 当淘汰一个页时,选择里当前时间最近的一段时间内,最长时间没有被使用的页
- 在表格中,向左寻找当前的项中最近一次出现的距离,选择距离最远的项淘汰
- 有两个近似算法
  1. 最不经常使用页面淘汰算法
    - 淘汰到淘汰时间为止,访问次数最少的那一页
    - 淘汰后,所有计数器清零,开始下一轮统计
  2. 最近没有使用页面淘汰算法
    - 淘汰当淘汰时间为止,没有被访问的也
    - 只用设置标志位,不用设置计数器
理想淘汰算法
- 淘汰以后不再使用或最长时间不再使用的页
- 在表格中,向右寻找当前项中最近一次出现的距离,选择距离最远的项淘汰
  注意: 第一次调入时也是缺页

Belady现象

使用FIFO算法时,在给进程分配内存块时,有时会出现分配的块越多,缺页次数反而增加的现象

页式管理优缺点

有效的解决了碎片问题
支持虚存
但是需要响应的硬件支持
增加了系统开销
如果调入算法不当,可能产生抖动
内碎片问题无法解决
不利于程序和数据共享

段式管理

一个程序按照其逻辑,分成若干段
每一段都从0开始编址
段长不固定,可根据需要动态增长
各段之间不需要连续

分页与分段的异同点

在内存中都不是整体连续,都使用地址映射机构进行转换
页时信息的物理单位,用户不需要处理. 段是信息的逻辑单位,分段可以更好的满足用户需求
页的大小是固定的,段的大小是可以变化的
分页的作业地址空间是一维的,分段的作业地址空间是二维的

段页式存储管理

结合分段的逻辑优势和分页的空间管理优势
将程序在逻辑上分段,在每段上分页
每段的页都从0开始依次变址
由此分段大小不再受内存可用区域的限制
内存分页不就够了？为什么还要分段？还有段页式？

扩展: 内存分配算法

在C语言中, 经典的内存分配方式是调用malloc函数, 向操作系统申请内存. 为了提高内存分配效率, malloc函数并不会直接执行分配内存的系统调用, 而是先向操作系统申请一大块内存, 然后每次程序需要内存时, 从这一大块内存中进行分割. 采用这一方案可以减少系统调用的次数, 降低内存分配的开销.

由于上述间接分配内存的逻辑, 实际上存在多种不同的内存分配算法. 常见的算法如下

分配器	主要优势	适用场景	缺点
ptmalloc	兼容性好	通用Linux程序	碎片问题
tcmalloc	多线程性能	高并发服务器	内存占用稍高
jemalloc	低碎片	长期运行服务	配置复杂
mimalloc	安全+性能	安全敏感应用	相对较新
slab	固定大小快	内核、数据库	不灵活

一个有些反直觉(或者说符合知觉)的例子是Redis默认使用jemalloc作为内存分配器. 因为Redis几乎是纯内存操作, 大量的新增和删除对象容易产生许多内存碎片. jemalloc针对内存分配问题做了许多优化, 包括:

多 arena 减少锁竞争：
jemalloc 使用多个 arena 来管理内存，每个 arena 独立管理自己的内存区域，并拥有自己的锁。默认情况下，arena 的数量是处理器核心数的四倍。当线程分配内存时，jemalloc 会通过轮询或哈希策略将线程绑定到特定的 arena，这样大部分分配操作只需要锁定该线程绑定的 arena，从而大大减少了锁竞争。
细粒度的大小分类（size classes）：
jemalloc 将对象大小划分为多个类别（size classes），每个 size class 对应一个特定的内存块大小。这样，当申请内存时，jemalloc 会向上取整到最近的 size class，然后从对应的空闲列表中分配。这种策略减少了内部碎片，并且由于每个 size class 都有自己的空闲列表，分配和释放速度很快。
slab 分配器用于小对象：
对于小对象（通常是小于等于一个页面大小的对象），jemalloc 使用 slab 分配器。每个 slab 是一个连续的内存块，被分割成多个相同大小的对象。slab 可以处于已分配或空闲状态，并且每个 arena 为每个 size class 维护一个 slab 列表。这样可以快速分配和释放小对象。
tcache（线程本地缓存）：
每个线程都有一个线程本地缓存（tcache），用于缓存一些小对象。当线程需要分配小对象时，首先检查 tcache 是否有可用的内存块。如果有，则直接从 tcache 分配，无需加锁。同样，释放小对象时，也先放入 tcache，直到 tcache 满或空时，才与 arena 进行批量交换。这大大减少了锁的争用。
内存回收和碎片整理：
jemalloc 会定期进行内存回收，将不再使用的内存归还给操作系统。同时，它通过延迟合并（将相邻的空闲内存块合并）来减少外部碎片。jemalloc 还提供了显式的内存整理（purge）机制，可以手动触发。
支持大内存页（huge pages）：
jemalloc 支持使用大内存页来减少 TLB 缺失，提高大内存工作负载的性能。
统计和调试支持：
jemalloc 提供了丰富的统计信息，包括内存分配、碎片、缓存使用情况等。这些信息对于调试内存问题和性能优化非常有帮助。
可扩展的元数据：
jemalloc 的元数据结构设计得很灵活，可以适应不同的工作负载和系统配置。

扩展: 为什么有虚拟内存还是会出现内存耗尽

操作系统的虚拟内存虽能将内存数据置换到硬盘的交换分区/文件，看似扩展了内存容量，但应用程序仍会出现malloc分配失败、Java OOM等内存耗尽错误，核心原因是虚拟内存并非无限制的内存扩展方案，且内存的使用还受系统层面保护策略、应用及运行时独立规则的多重约束，并非单一的虚拟内存机制可解决。

从虚拟内存本身来看，其存在两大硬限制：一是进程的虚拟地址空间由CPU架构决定，32位系统用户态仅2-3GB，64位系统也有操作系统的实际限制，地址空间耗尽后内存分配会直接失败；二是虚拟内存依赖的交换分区/文件容量固定，并非占用硬盘全部空间，当物理内存加交换分区被占满，操作系统便无法再分配新内存。同时操作系统为避免性能灾难，不会无限制换页，当检测到换页频率过高引发系统抖动时，会直接拒绝新的内存分配请求，且部分内存数据因特性必须驻留物理内存，无法置换到硬盘，这部分内存耗尽也会导致分配失败。

应用程序及运行时层面的独立限制，是内存耗尽的重要原因，且与系统虚拟内存关联较小。C语言中，即便进程总虚拟地址空间有剩余，虚拟地址空间碎片化会导致无法分配连续大块内存，加上操作系统对单个进程的内存资源限制，都会让malloc分配失败；Java的OOM则主要源于JVM自身的内存模型，堆、栈、元空间等分区均有独立大小限制，只要某一分区被占满且垃圾回收无法释放，就会触发OOM，而应用的内存泄漏会让堆内存持续被占用，进一步加剧这一问题，这些限制均与系统虚拟内存无关。此外，操作系统会通过ulimit、cgroup等机制对进程做权限和资源管控，限制单个进程的最大内存使用量，进程一旦超出该限制，内存分配请求就会被直接拒绝。

第六章文件管理

文件是一段程序或数据的集合, 是一组赋名的相关联字符流的集合或相关联记录的集合. 文件系统负责为用户建立,撤销,读写,修改和复制文件, 完成对文件的按名存取和存取控制.

文件类型

按性质和用途分类
- 系统文件(可执行)
- 用户文件(可读可写可执行)
- 库文件(可读可执行)
按文件保护方式
- 只读文件
- 读写文件
- 可执行文件
- 不保护文件
按文件注释和处理方式
- 普通文件:一般的文本文件和二进制文件
- 目录文件:包含文件目录信息的文件,用于检索普通文件
- 特殊文件:输入输出设备可以看做特殊文件
按信息流
- 输入文件: 如读卡机或键盘,只能读入
- 输出文件: 如打印机,只能写出
- 输入/输出文件:如磁盘,既可读又可写
按文件的数据形式
- 源文件
- 目标文件
- 可执行文件

文件的组织结构

逻辑结构
- 字符流式无结构文件
- 记录式有结构文件

记录式结构文件种类

连续结构:把记录按照先后顺序排列
- 适用性强
- 排列顺序与内容无关(便于记录的追加)
- 搜索性能较差
多重结构:一个包含n个记录吗,m个键的文件构成一个mn的矩阵
- 如果矩阵i行j列值为1,则说明记录键k[i]在记录R[j]中
- 同一键可以同时属于不同的记录
- 以键k[i]为队首,以包含k[i]的记录为队列元素构成队列
- 此结构搜索效率高于连续结构,但必须先找到对应的键,并在其队列中顺序查找
转置结构:把含有相同键的记录指针全部指向该键
-把所有与同一键对应的记录的指针连续地置于目录中该键的位置下
顺序结构:把文件的键按照规定的顺序,如字母顺序排列
- 适合与按某种顺序来搜索,追加,删除记录

文件物理结构

顺序结构
- 把逻辑上连续的文件依次存放在连续的物理块上
- 结构简单,存取速度快
- 不能动态增长, 部分删除会有零头
链接结构
- 类似链表结构,每个块的末尾有指向下一块的指针
  -文件可以动态增长
- 不适合随机访问,一般只用于逻辑上连续且顺序访问的情景
索引结构
- 为每个文件建立一个索引表,从表中可以直接查询到指定块的物理块号(类似页表)
- 即可满足动态增长又可实现随机存取
- 使用索引表增加了存储空间开销,且需要至少访问两次存储器

索引表组织

连接模式:索引表占满一块就用指针链接下一块
多级索引:存放的不是索引,而是存索引块的地址
综合模式:索引表的头几项设置为直接寻址,后的设置为多重索引

磁盘调度算法

先到先服务
- 简单公平
- 效率不高,可能导致磁头反复移动
最短寻道时间优先
- 优先选择距离当前磁头最近的访问请求进行服务
- 改善了磁盘的平均服务时间
- 可能造成某些访问长时间得不到服务
扫描算法(电梯算法)
- 无访问时,磁头位置不动
- 有访问时,磁头按一个方向移动,依次处理经过的请求
- 如果到达边缘就转换方向

文件存储空间管理

空闲文件目录法: 所有空闲块记录在一个表中
- 适合仅有少量空白区域的情况
- 适合连续文件
空闲块链法: 所有块链接成一个链表
- 只需要一个头结点保存空闲区信息
- 效率低
成组链接法: 把文件存储设备的所有空闲块按组保存
- 例如见空闲块每50块分成一组
- 每组第一块存放前一组的总块数和各块块号,后面的块为空,作为空闲块等待分配
- 第一组只有49块,最后一组可能不足50块
- 将最后一组调入内存,并维持成栈结构
- 分配空间时,进行出栈操作,如果只剩下一块,就从此块中取出前一组地址,载入新的组,并将此块分配给请求进程
- 释放空间时,进行入栈操作,如果到达50块,就将所有块号存入,并清空栈,将栈的第一块链接到此组
位示图法: 使用一串二进制位反应空间分配情况

文件目录管理

文件组成
- 文件体: 文件本身的信息
- 文件说明(文件控制块FCB)
  - 存放为了管理文件所需要的信息
  - 包括文件名,起始物理位置,存取控制信息等
文件目录
- 单级目录
  - 系统为所有存入系统的文件建立一张表
  - 每个文件有一个表目
  - 各个文件处于平等地位
  - 简单且能够按名存取
  - 不允许重名,且文件多时,查找速度慢
- 二级目录
  - 主目录文件(MFD Main File Directory)
    - 存放不同组名的有关存取控制信息
    - 包括用户名,用户子目录所在文件物理地址等
  - 用户文件目录(UFD User File Directory)
    - 存放用户文件的文件说明
    - 即该用户的FCB
  - 文件名 <==> 用户名/文件名
  - 解决了文件重名和文件共享的问题
    - 由于有用户名,所以可以同名
    - 由于UFD可以指定地址,所以可以在物理层面是上共享文件
  - 不适合大量用户和大量文件的系统
- 多级目录结构
  - 产生于Unix系统,已被现代操作系统广泛采用
  - 多级目录中,处理最低一级的物理块总有文件信息,其他没记目录中都是存放下一级目录或文件说明信息
  - 通过路径名解决了重名问题
  - 查找速度快

文件共享

绕道法
- 要求用户处于当前目录下工作
- 所有的文件访问都是相对当前目录进行
- 当前目录一般存放在内存中
- 依次向上回溯到需要访问的节点与当前目录的公共节点,再从公共节点依次向下找到目标节点
- 效率低
链接法
- 将一个链接指针直接指向共享文件所在的目录
基本文件目录表
- 基本文件目录BFD(Basic File Directory)
  - 包括文件的结构信息,物理块号,存取控制等信息
  - 有系统赋予唯一的内部标识符来标识
  - 此目录以连续文件的形式存于卷头部,此长度决定了卷内最大文件数
- 符号文件目录SFD(Symbol File Directory)
  - 有用户给出文件名和文件内部标识符组成
  - 用于建立文件名和文件内部标识符对应关系

扩展: 日志结构文件系统

日志结构文件系统（Log-Structured File System，简称LFS）是一种特殊的文件系统，它通过将所有的修改以顺序的方式写入一个类似日志的结构中，从而提高了写入速度和崩溃恢复速度。

在LFS中，所有的数据修改都被记录在日志中，而不是像传统文件系统那样直接写入磁盘。这样做的好处是，LFS可以一次将一大批写入数据落盘，从而减少了随机IO，提高了写入性能。同时，由于日志是顺序写入的，所以在崩溃恢复时，LFS只需要检查日志中的最新部分，而不需要扫描整个磁盘，这大大加快了恢复速度。

LFS的设计还假设文件会被缓存在主内存中，因此增加内存大小会增加缓存在满足读请求方面的能力。这意味着，写请求成为磁盘的主要负载，而读请求则主要依赖于内存缓存。

LFS的一个重要概念是段（Segment），它是一次写入的大块更新。段的大小决定了LFS的性能，因为一次写入的段越长，就有越多的数据可以被打包到一次顺序IO写入中。为了提供快速写入所需要的“大块”空闲磁盘空间，LFS会把日志分成段，并用段清理器来对分片严重的段中的有用信息进行压缩。

总之，日志结构文件系统通过将数据修改顺序写入日志，减少了随机IO，提高了写入性能和崩溃恢复速度。

扩展: 固态硬盘的磨损负载均衡算法

固态硬盘的 NAND 闪存单元的擦写次数存在限制, 而文件生命周期差异显著, 因此算法需要智能地将写入操作均匀分布到所有物理块上, 避免部分块过早损坏.

为了达到上述目的, 算法不仅需要动态的确定新写入的数据的位置, 还需要定期将冷数据迁移到磨损程度较高的块, 腾出低磨损块供新数据写入. 额外的数据迁移产生了写入放大(例如为了写入1GB数据, 实际底层进行迁移产生了2GB数据写入)

第七章设备管理

设备管理的任务

选择和分配IO设备以进行数据传输操作
控制IO设备和内存数据之间交换数据
为用户提供友好的透明接口
提高并行操作度

设备管理的功能

提供和进程管理系统的接口
进行设备分配
实现设备和设备,设备和CPU之间的并行操作
进行缓冲区的分配,释放以及相关的管理

数据传送控制方式

程序直接控制
- 由用户进程直接控制
- 控制简单,不需要硬件支持
- CPU和外围设备只能串行工作
- 无法发现和处理由于硬件产生的错误
中断方式
- CPU利用率大大提高
- 支持多道程序与设备并行操作
- 一次数据传输可能需要多次中断,会消耗大量CPU时间
- 可能造成CPU无法响应中断和出现数据丢失的问题
DMA方式
- 在外围设备和内存之间开辟直接的数据交换通路
- DMA通过挪用CPU的一个工作周期把数据送入内存
- 除了数据开始传送时需要CPU的启动指令,以及传送结束后CPU进行中断处理以外,不再需要CPU频繁干预
- CPU中断处理次数大大减少
- 排除了数据丢失的问题
- 由于MDA方式对外围设备的某些操作还是需要CPU控制,且配备多个DMA是不经济的,因此DMA方式也存在一定的局限性
通道方式
- 一个独立于CPU的专门负责I/O控制的处理机
- 有自己的指令系统,通道指令受CPU启动,并在操作结束后向CPU发出中断信号
- 与DMA方式的区别
  - DMA方式中,数据的传输有CPU控制,通道中有专门的硬件控制
  - DMA方式中,每台设备至少一个DMA控制器,通道中一个通道可以控制多态设备与内存进行数据交换

缓冲技术

引入缓冲的目的
- 缓和CPU和I/O设备间速度不匹配的矛盾
- 减少CPU中断次数
- 解决DMA或或通道方式时的瓶颈问题
缓冲区种类
- 按照缓冲器个数
  - 单缓冲
    - CPU与外设之间只设立一个缓冲区
    - 共用资源需要互斥使用
  - 双缓冲
    - 设置两个缓冲区
    - 实际很少使用此方案
  - 多缓冲/缓冲池
    - 把主存的多个缓冲区分为两个部分
    - 输入缓冲区和输出缓冲区
    - 每个缓冲区依然是临界资源,必须互斥使用
- 按照I/O控制
  - 专用硬件
  - 软件缓冲
缓冲区管理
1. 用于收容输入数据的工作缓冲区(hin): 输入设备-> 缓冲区
2. 用于提取输入数据的工作缓冲区(sin): 缓冲区->CPU
3. 用于收容输出数据的工作缓冲区(hout): CPU->缓冲区
4. 用于提取输出数据的工作缓冲区(sout): 缓冲区->输出设备

设备分配技术

数据结构
1. 系统设备表SDT(System Device Table)
  - 记录所有I/O设备信息
  - 包括设备类型,设备标识符,进程标识符,DCT指针等
2. 设备控制表DCT(Device Control Table)
  - 系统中的每台设备都有一张设备控制表
  - 记录设备各方面特征,以及与设备相联的设备控制器入口位置
3. 设备控制器表COCT(COntroller Control Table)
  - 每个控制器有一张控制器控制表
  - 包含控制器号,控制器状态,通道指针等
4. 通道控制表CHCT(CHannel Control Table)
  - 每个通道都有一张通道控制表
  - 包括通道号,通道状态,等待队列指针等
设备分配方式
1. 静态分配
  - 在作业执行前,由系统一次性分配给该作业所需的全部设备,控制器和通道
  - 在作业进行过程中,不再改变
  - 不会死锁
  - 设备利用率低
  - 适用于独占型的设备
2. 动态分配
  - 在进行需要设备时,通过系统调用项系统提出请求,一旦使用个完毕,立即释放
  - 提高了设备利用率
  - 分配不当会引起死锁
  - 适用于共享型的设备
设备独立性
- 指应用程序独立于具体使用的物理设备
- 用户编制程序使用的设备与实际使用的设备无关
设备分配策略
- 先请求先分配
- 优先级高者先分配
设备分配顺序
1. 分配设备
2. 分配控制器
3. 分配通道
虚拟设备和假脱机技术
1. 虚拟设备
  - 虚拟设备是指代替独享设备的那部分存储空间以及有关的控制结构
2. SPOOLING系统(Simultaneous Peripheral
  Operation On Line)
  - 同时联机的外围操作或假脱机操作
  - 利用一台高速共享设备,将一台独享设备模拟成多台可并行操作的虚拟设备
  - 提高了I/O速度
  - 设备并没有分配给任何进程
  - 实现了虚拟设备功能

I/O进程控制

从用户进程的I/O请求开始,给用户进程分配设备,启动有关设备进行I/O操作,以及在I/O在I/O操作之后响应中断,进行善后处理为止的整个系统控制过程
模块功能说明
- I/O请求处理模块
  - 将用户进程的I/O请求变换为设备管理程序所能接受的信息,并将I/O请求命令插入指向的相应DCT的I/O请求队列
- 设备分配程序
  - 为I/O请求分配相应的设备,控制器和通道
- 缓冲区管理模块
  为I/O传送申请必要的缓冲区,以及保证I/O传送的顺利完成
- 中断处理
  - 数据传输结束后,外设发出中断请求,I/O控制过程根据中断原因调用中断处理程序,并作出中断响应
I/O控制的实现方式
- 作为请求I/O操作的进程的一部分实现
- 作为当前进程的一部分实现
  - 当前进程处理中断
  - 剩余部分有I/O进程控制
- 作为专门的系统进程
  - 由系统进行I/O调度
I/O进程的实现方式
- 每个设备设置一个专门的I/O进程
  - 该进程只能在系统态下执行
- 整个系统设置一个I/O进程
- 每类设备设置一个I/O进程
  - 该进程既可在系统态也可在用户态执行

设备驱动程序

是驱动物理设备和DMA控制器或I/O控制器等直接进行I/O操作的子程序的集合
设备驱动程序负责设置相应设备有关寄存器的值,启动设备进行I/O操作,指定操作的类型和数据流向等
设备开关表(Device Switch Table, DST)对驱动程序进行管理
- 给出相应设备的各种操作子程序的入口地址
- 一般是二维的,行和列分别是设备类型和驱动程序类型
- 设备开关表也是I/O进程的一个数据结构

第八章虚拟化

虚拟化是一种在一台物理机上同时运行多种操作系统的技术. 虚拟化的主要思想是虚拟机监控程序(Virtual Machine Monitor, VMM), 有时也称为虚拟机管理程序(hypervisor).

VMM需要在以下三个维度具有良好的表现

安全性: VMM应该完全掌握虚拟资源
保真性: 程序在虚拟机上执行的行为应该与裸机相同
高效性: 虚拟机中运行的大部分代码应该不受VMM干涉

最近这些年, CPU硬件和操作系统均针对虚拟化进行了大量的工作, 因此虚拟化技术也是操作系统相当重要的主题之一

敏感指令与特权指令

在x86体系结构中, 有两类执行. 第一类是敏感指令, 该指令在用户态和内核态执行的效果不同. 第二类是特权指令, 该指令在用户态执行会导致陷入.

实现虚拟化的必要条件是敏感指令是特权指令的子集, 即用户态执行一个不应该在用户态执行的操作时能够陷入. 从而使VMM能感知并处理这一指令.

但早期的Intel CPU并不满足这一特点, 因此难以被虚拟化. 直到Intel引入VT(Virtualization Technology), 才解决这一问题.

VT/AMD-V

VT 是英特尔对其 硬件辅助虚拟化 技术系列的总称（AMD的对应技术称为 AMD-V）。它的出现是为了解决早期纯软件虚拟化（如二进制翻译）性能开销大、且在某些场景下无法实现的问题。核心思想是让硬件直接支持虚拟化。通过在CPU、芯片组等硬件层面增加专门的指令集和运行模式，让虚拟机监控器能够更高效、更安全地管理和隔离多个客户操作系统。

这也是现代虚拟机与早期的虚拟机的一个显著区别, 现在的虚拟机大部分时候CPU在直接执行虚拟机内的指令, 而无需虚拟机软件进行翻译.

它创建了一个新的、权限级别高于操作系统内核的“根模式”，供VMM（虚拟机监控器，如Hypervisor）运行。客户操作系统则运行在权限稍低的“非根模式”下。新增了VMXON、VMXOFF、VMLAUNCH、VMRESUME、VMCALL等指令，用于进入/退出虚拟化模式、启动/恢复虚拟机以及从Guest内发起对VMM的调用。

此方案的优点: 敏感指令由硬件自动截获，上下文切换由硬件优化，速度远超软件模拟。硬件强制的内存和I/O隔离，虚拟机之间、虚拟机与宿主机之间界限清晰。客户操作系统几乎无需修改就能直接运行（这正是“完全虚拟化”的目标）。VMM无需再使用复杂、易错的二进制翻译或半虚拟化技术来处理所有敏感指令。

此方案的缺点: 需要CPU支持VT-x/AMD-V，在老旧的硬件上无法使用。早期VT技术对I/O虚拟化的支持仍不够高效，后来通过VT-d（芯片组直接I/O虚拟化）和SR-IOV（网卡虚拟化）等技术来补充。

二进制翻译

二进制翻译（Binary Translation）是一种经典的软件虚拟化技术，它允许虚拟机监控器（如Hypervisor）将一个架构的机器代码（二进制代码）转换为另一个架构的机器代码，而无需修改原始代码。在硬件辅助虚拟化普及之前，它是实现完全虚拟化（无需修改Guest OS）的主要手段。VMware Workstation早期版本和QEMU的用户模式模拟是其典型代表。

具体执行流程包括:

指令扫描与翻译：VMM拦截客户机的代码执行。它将客户机的二进制代码（如x86指令）按基本块进行解码，识别其中的“敏感指令”（如POPF、LMSW、MOV to CR3等，这些指令在非特权下行为会改变或产生异常）。
重写：将这些敏感指令替换为对VMM运行时函数的调用，或者替换为一组能模拟其预期行为的、安全的指令序列。
执行与缓存：执行翻译后的、安全的“影子代码”，并将结果存回客户机的虚拟状态中。翻译后的代码块被缓存，下次执行相同代码时可直接跳转，无需再次翻译。
处理异常与中断：所有外部中断和异常都由VMM统一捕获，并模拟给相应的客户机。

此方案的优点: 无需CPU的虚拟化扩展，可以在任何硬件上运行。可以实现跨架构虚拟化（例如，在x86宿主机上运行为ARM编译的程序，QEMU的系统模式就是如此）。VMM对客户机的每一条指令都有完全的控制力和可见性，便于实现调试、分析、安全监控等高级功能。

此方案的缺点: 动态翻译、缓存管理、上下文切换都会带来显著的性能损耗，尤其在执行大量特权指令的I/O密集型工作负载中。需要精确模拟整个CPU的行为，处理各种指令边界情况和自修改代码，极易引入错误。完美模拟所有硬件行为（尤其是带bug的行为）以保证所有操作系统都能运行，是一项艰巨的任务。

硬件辅助虚拟化与二进制翻译对比

特性	VT（硬件辅助虚拟化）	二进制翻译
本质	硬件扩展，提供新的CPU执行模式	软件技术，动态重写二进制代码
性能	高，接近原生性能	较低，有显著的翻译开销
兼容性	兼容大多数主流OS	理论上兼容性更广，可实现跨架构
安全性/隔离	硬件强制，非常强	依赖软件正确性，相对较弱
硬件依赖	必须	无需
主要用途	服务器/数据中心虚拟化、主流桌面虚拟化	遗留系统支持、跨架构模拟、动态分析、安全沙箱
代表产品	VMware ESXi, KVM, Hyper-V, Xen（带HVM）	早期VMware Workstation, QEMU（用户模式），Bochs

扩展: KVM

KVM（Kernel-based Virtual Machine）是一种基于Linux内核的开源虚拟化技术，将Linux内核转变为虚拟化监控器（Hypervisor），允许在物理主机上运行多个隔离的虚拟机（VM）。直接复用Linux内核的进程调度、内存管理等核心功能，无需独立虚拟化层。

内存虚拟化

内存虚拟化的目标与CPU虚拟化类似：为每个虚拟机提供独立、连续、从零开始的私有物理内存空间的抽象，同时保证隔离性（一个虚拟机不能访问其他虚拟机或宿主机指定的内存）和效率。

核心矛盾在于：客户操作系统（Guest OS）管理的是它自以为的“物理内存”，而虚拟机监控器（VMM）管理的是真实的机器物理内存。 这两者之间需要一个翻译层。

客户机虚拟地址：Guest OS提供给应用程序的地址。
客户机物理地址：Guest OS的页表认为的“物理地址”，但对宿主机来说，这只是伪物理地址。
宿主机物理地址：真实的机器物理地址。

传统的单次地址转换流程是：VA -> (通过进程页表) -> PA。
在虚拟化环境下，这个流程必须变为：GVA -> (通过Guest OS页表) -> GPA -> (通过VMM映射) -> HPA。

如何高效地实现 GPA -> HPA 的转换，是问题的关键。其解决方案经历了两个阶段：

阶段一：软件方案 - 影子页表

VMM为每个虚拟机的每个进程维护一套“影子页表”。这套页表直接安装在CPU的MMU中，它的“翻译结果”是宿主机物理地址。

换言之，VMM“劫持”了Guest OS的页表维护工作：

Guest OS仍然正常创建和维护自己的页表，但这份页表（负责 GVA -> GPA）永远不会被真正加载到CPU的MMU中。
VMM动态地监听Guest OS对页表的修改。
VMM将Guest OS的页表项与自己维护的 GPA -> HPA 映射关系相结合，生成一个“合并”的、可以直接被CPU使用的页表项（即 GVA -> HPA），写入到“影子页表”中。

工作流程简化如下：

当Guest OS修改其页表（如发生缺页异常、切换进程）时，会触发一次VM-Exit，控制权交给VMM。
VMM捕获这一修改，并同步更新对应的“影子页表”项。
CPU MMU使用“影子页表”进行地址翻译，一次查表即可得到HPA。

优点: 性能优于纯软件模拟，因为它最终只做了一次页表查找。实现了内存的完全虚拟化和隔离。
缺点: 需要跟踪Guest OS的所有页表操作，处理各种边界情况（如自引用页表、TLB刷新指令）。需要为每个虚拟机的每个进程维护一套完整的影子页表。每次Guest OS页表更新（如TLB刷新、进程切换）都会引发大量VM-Exit和VMM干预，上下文切换成本高。

阶段二：硬件方案 - 扩展页表 / 嵌套页表

为了从根本上解决影子页表的性能问题，Intel和AMD分别推出了EPT和NPT技术。这是硬件辅助虚拟化在内存领域的直接体现。在CPU的MMU中增加第二层硬件翻译单元，专门负责 GPA -> HPA 的转换。这样，完整的地址转换就由硬件并行或流水线化完成。

关键变化：

Guest OS页表：被允许直接加载到MMU中，它负责 GVA -> GPA 的转换。Guest OS可以像在物理机上一样自由地管理自己的页表，无需VMM干预。
EPT/NPT 页表：由VMM为每个虚拟机单独设置的一份页表，负责 GPA -> HPA 的转换。Guest OS对此完全无感知。
硬件并行查找：CPU的MMU硬件会自动、并行地查找这两套页表，最终得到HPA。

工作流程：

Guest OS正常处理缺页异常，更新自己的页表，无任何VM-Exit。
当CPU需要将GVA转换为HPA时，硬件先查找Guest页表得到GPA，紧接着用这个GPA作为输入，去查找EPT页表得到最终的HPA。
如果查找Guest页表缺页，产生的是#PF异常，由Guest OS自己处理。
如果查找EPT页表缺页，产生的是EPT Violation，这会触发VM-Exit，由VMM处理（例如，分配真实的物理页面、建立映射、或模拟一个设备MMIO访问）。

优点: 消除了绝大多数因内存管理而产生的VM-Exit（如TLB刷新、页表更新）。两次查找由硬件并行/流水线完成，开销远低于两次软件查找。TLB可以缓存最终翻译结果，效率极高。VMM无需再处理复杂的影子页表同步问题，只需管理相对简单的EPT页表。

EPT/NPT已成为现代虚拟化的绝对标准。所有主流Hypervisor（VMware vSphere, Microsoft Hyper-V, KVM, Xen）在支持硬件虚拟化的CPU上都会默认启用此功能。影子页表已成为历史，仅在需要模拟不支持EPT的老硬件，或进行特定调试时才会被用到。

I/O虚拟化

它负责将物理硬件设备（如网卡、磁盘控制器、GPU）安全、高效地分配给多个虚拟机，是决定虚拟机整体性能和可用性的核心。与CPU和内存虚拟化不同，I/O虚拟化的挑战更复杂，因为它涉及大量、异步的数据移动和复杂设备状态的管理。其演进路径清晰地体现了在兼容性、性能、隔离性和复杂性之间的权衡。

I/O虚拟化的核心挑战

隔离性：必须阻止虚拟机直接访问或干扰物理设备及其他虚拟机的I/O操作。
设备模拟：如何让虚拟机看到一个“完整、标准”的硬件设备（如Intel E1000网卡）？
性能：在虚拟机、VMM、物理驱动之间传递数据和中断，会带来巨大开销。如何最小化？
兼容性：虚拟机内的通用操作系统（如Windows）通常自带标准设备驱动。虚拟化方案需要兼容它们。

方案一：全虚拟化（设备模拟）

这是最传统、兼容性最好的方法，由QEMU这类软件完美实现。VMM（或其中的设备模型，如QEMU）用纯软件完整地模拟一个众所周知的物理设备。

Guest OS中的通用驱动程序向虚拟设备的“I/O端口”或“MMIO区域”发出命令。
这触发一次VM-Exit，陷入VMM。
VMM的设备模拟器解析命令，将I/O请求（如“发送网络包”）转换为对宿主机物理设备驱动程序的调用。
数据需要在Guest内存和VMM/宿主机内存之间进行拷贝。
完成操作后，VMM模拟一个“中断注入”回Guest OS，通知其操作完成。

优点: 兼容性极佳
缺点: 性能极差

方案二：半虚拟化

为了解决全虚拟化的性能瓶颈，半虚拟化另辟蹊径，其代表是Xen的前端/后端驱动模型和后来成为行业事实标准的Virtio。核心思想是“让Guest OS知道自己在虚拟化环境中”。通过修改Guest OS，安装一个特殊的、优化的驱动程序（称为前端驱动），与VMM中对应的后端驱动按照一个高效、精简的协议进行协作，完全绕过复杂的硬件模拟。

Guest OS中安装virtio-net前端驱动，VMM中实现virtio后端驱动。
双方通过共享的环形缓冲区进行通信。前端驱动将待发送的数据包描述符放入“发送环”，后端驱动直接从环中取走并发送，反之亦然。
使用事件机制（如Linux的eventfd）或轻量级中断代替昂贵的VM-Exit来通知对方。

优点: 高性能
缺点: 需要Guest内安装特定驱动

方案三：硬件辅助I/O虚拟化

设备直通: 借助VT-d（Intel）或AMD-Vi技术，可以将一个物理I/O设备（如一块高性能网卡或一个GPU）直接、排他地分配给一个虚拟机。设备的所有权和控制权完全移交给Guest OS。VMM配置IOMMU，建立GPA -> HPA的DMA重映射，并将设备的PCI功能“透传”给虚拟机。此后，该设备的访问和中断将直接指向目标虚拟机，完全绕过VMM。

优点: 极致性能
缺点: 失去灵活性，一个设备只能被一个VM使用，无法共享。

SR-IOV（单根I/O虚拟化）: 在物理网卡等设备上实现一个硬件特性，使其能在硬件层面虚拟出多个独立的“虚拟功能”。一块支持SR-IOV的物理网卡呈现为一个物理功能和多个虚拟功能。每个VF都是一个轻量级的、功能完整的PCIe设备，可以通过VT-d/AMD-Vi直接分配给一个虚拟机。每个VF拥有独立的DMA引擎、队列和中断，硬件负责在多个VF间交换数据。

优点: 兼具接近原生的性能和良好的可扩展性
缺点: 需要设备和主板芯片组的双重硬件支持。

扩展: VT-d与DMA外挂

一种称为 DMA（直接内存访问）攻击 的硬件作弊方式因其极高的隐蔽性一度成为反作弊系统的噩梦. 作弊者通过在主板 PCIe 插槽上接入特制硬件(如魔改的采集卡或网卡), 即可绕过操作系统监控直接读取和修改游戏内存数据. 然而Intel 的 VT-d 技术意外的成为遏制这种高级攻击的核心技术. 其核心逻辑是硬件级的”权限最小化”

使用DMA可以读取任意内存, 是一种听起来不太合理, 但仔细想想又确实是合理的的设计.

VT-d 技术的核心在于 IOMMU（输入输出内存管理单元） 组件. 为每个连接到系统的 PCIe 设备维护独立的 DMA 访问策略, 实施严格的”权限最小化”原则. 在没有 VT-d 的环境中, PCIe 设备默认具备对整个物理内存的 DMA 访问能力. 启用 VT-d 后, 系统仅为设备分配其驱动正常运行所必需的内存区域访问权限. 任何试图越权访问的 DMA 操作都会被 IOMMU 在硬件层面实时拦截和拒绝.

VT-d 的设计初衷本是为了解决虚拟化环境中的设备安全分配问题. 只有通过 IOMMU 对 DMA 实施精细控制, 才能确保虚拟机在直接访问硬件时不会相互干扰或攻击 Hypervisor.

使用DMA外挂依然需要在游戏所在的机器中注入”内应”程序, 该程序需要分析出游戏内特定目标(例如敌人的坐标位置)的内存的虚拟地址, 然后使用DMA设备直接读取目标地址, 实现数据窃取. 因此反作弊系统的首要目标还是找出”内应”程序, 而使用 VT-d 技术相当于提供一道”终极防线”

GPU虚拟化

GPU虚拟化是I/O虚拟化的一个高度专业化子集，其目标是实现GPU计算与图形资源的安全隔离、高性能共享与灵活分配。GPU虚拟化的核心挑战：

极高性能要求：GPU用于图形渲染和并行计算（如AI、科学计算），对延迟和吞吐量极为敏感。任何虚拟化开销都会被显著放大。
极度复杂的内部状态：GPU并非简单的命令响应设备，它拥有巨大的专用显存、复杂的上下文（Context）、流水线状态、寄存器和命令队列。捕获、保存/恢复和隔离这些状态非常困难。
庞大的驱动生态：CUDA、OpenCL、DirectX等API和驱动栈极其厚重，且由厂商（主要是NVIDIA）深度控制和优化。虚拟化层必须完美兼容现有生态，不能要求应用重写代码。
多租户与安全隔离：必须确保多个虚拟机（或容器）的GPU工作负载完全隔离，一个虚拟机的崩溃或恶意操作不能影响其他用户，且无法访问他人的数据。

目前主流的、成熟的GPU虚拟化方案是中介直通。在VMM中嵌入一个特权驱动，由它来“中介”所有虚拟机对GPU的访问。物理GPU被虚拟化成多个虚拟GPU，每个vGPU分配给一个VM。硬件层面需要特定的GPU硬件支持（如NVIDIA的数据中心级GPU，如A100、V100的vGPU版本）。GPU内部有硬件调度单元。Hypervisor层安装厂商提供的VGPU管理器。它负责将物理GPU的计算核心、显存、编码器等资源按配置（如1/2, 1/4, 1/8）划分为多个vGPU。

Guest VM层安装与vGPU型号对应的标准GPU驱动（无需特殊修改）。VM看到的是一个“真实的”NVIDIA GPU（如vGPU A100-40C），可以运行完整的CUDA、OpenGL等应用。

最后更新： 2026年03月14日 15:20

原始链接： https://lizec.top/2017/09/23/%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%E7%AC%94%E8%AE%B0/

第一章 绪论