虽然无考研的准备，但还是看起了王道计算机考研的课程，那听这个课的目的主要是为了应付计算机组成原理、计算机操作系统原理、计算机网络这三门的课期末考试【一个学期开计算机四大件里的三门课，也是有了】，所以都是挑着看的，笔记内容不全也不会深入。

Linux 操作系统只记一些简单复习的内容。

本来想等听完课再发笔记，但想了想确实平时看笔记确实不方便，所以这篇笔记就是会到期末之前一直更新中的笔记，以方便我平时的查看【这也算是搭建博客的好处吧，可以无视设备平台限制随时看笔记】。

计算机组成原理

1.2.1 + 1.2.2 计算机硬件的基本组成

计算机硬件的基本组成：

• 早期冯诺依曼机的结构
• 现代计算机的结构

世界上第一台计算机 ENIAC，由于早期的计算机是手动接线来控制计算的，也就意味着对计算机每做一次操作就需要人工手动进行一次操作，效率很低。所以冯诺依曼提出“存储程序”的概念。

“存储程序” 的概念是指将以二进制代码的形式事先输入计算机的主存储器，然后按其在存储器中的首地址执行程序的第一条指令，以后就按该程序的规定顺序执行其他指令，直至程序执行结束。

于是就有了 EDVAC，世界上第一台采用冯诺依曼结构的计算机。

上图为早期冯诺依曼机的结构，数据通过输入设备进入，然后通过运算器的运算存放到存储器中，控制器可以指挥存储器中的程序数据运行，输出设备将运算的结果输出。

在计算机系统中，软件和硬件在逻辑上是等效的。

Eg：对于乘法运算，可以设计一个专门的硬件电路实现乘法运算。也可以用软件的方式，执行多次加法运算来实现。

冯·诺依曼计算机的特点：

1. 计算机由五大部件组成（计算器、控制器、存储器、输入设备、输出设备）
2. 指令和数据以同等地位存于存储器，可按地址寻访
3. 指令和数据用二进制表示
4. 指令由操作码和地址码组成
5. 存储程序
6. 以运算器为中心（输入/输出设备与存储器之间的数据传送通过运算器完成）

冯诺依曼机以运算器为中心，运算器是处理数据的核心部件，但是冯诺依曼结构中所有数据的中转还是需要运算器来完成，会导致数据计算的效率降低。

因此现代计算机以存储器为中心，也就是说输入的数据是直接放到存储器中的，然后运算器可以存储和读取存储器中的数据，存储器也可以直接将数据输出给输出设备，这样很多中转操作无需通过运算器，自然也就提高了效率。

以上便是现代计算机的结构。将运算器（算数/逻辑运算）和控制器（发出指令）整合便是 CPU。

所以：CPU = 运算器 + 控制器

于是将两个部件合并，下图为更简洁的表示：

需要注意的是，存储器又可以分为主存和辅存，主存就是内存（内存条），辅存就是外存（硬盘）。机组中的主机只包含 CPU 和主存，而辅存属于 I/O（输入/输出）设备。主机和 I/O 设备组成了计算机的硬件。

总结

1.2.2 各个硬件的工作原理

本节简单介绍了计算机主机（运算器、控制器、主存）的各个设备。

主存储器的基本组成

主存储器由：存储体、MAR（存储地址寄存器） 和 MDR（存储数据寄存器）组成。

CPU 在读取主存储器中的数据时，会告诉 MAR 需要数据的地址，然后 MAR 通过地址在存储体中找对应的数据，然后将找到的数据给 MDR，最后 CPU 会读取 MDR 中给的数据。

类似的，CPU 将数据存放到主存储器中时，会告诉 MAR 数据需要存放的地址，并且给 MDR 具体的数据，然后通过 MAR 和 MDR 将数据存放到存储体当中。

存储体的组成如下：

存储单元：每个存储单元存放一串二进制代码

存储字（word）：存储单元中二进制代码的组合

存储字长：存储单元中二进制代码的位数

存储元：即存储二进制的电子原件，每个存储元可存 1bit

重点：

• MAR 位数反映存储单元的个数
• MDR 位数 = 存储字长

例，加入某个计算机的MAR 和 MDR为：

• MAR = 4 位 -> 总共有 2⁴ 个存储单元
• MDR = 16 位 – > 每个存储单元可存放 16bit，此时一个字（word） = 16bit

这里容易混淆的是：上述的字（word）和字节（Byte）不是同一个东西。字节（Byte）是一个常量，1 个字节（Byte） = 8bit，也就是 1B = 1 个字节， 1b = 1 个 bit。而字（word）指的是存储字，根据每个计算机不同的设计结构，也就是 MDR 的位数而改变。

运算器的基本组成

运算器由 ACC、MQ、X 和 ALU 组成，其中的核心是 ALU。

ACC、MQ 和 X 本质上都是存取数据的寄存器，而只有 ALU 是做算术的算术逻辑单元。

控制器的基本组成

控制器由 CU、IR 和 PC 组成，其中的核心是 CU。

控制器完成一条指令的步骤为：

1. 通过 PC 告诉存放需要执行指令的地址。
2. 将当前的指令存放到 IR 中完成分析指令。
3. 通过 CU 完成指令的执行。

前两个步骤取指令和分析指令可以统称为取指。

计算机的工作过程

int a = 2, b = 3, c = 1, y = 0;
void main(){
    y = a * b + c;
}

总结

注：传统计算机中，MAR 和 MDR 属于主存，但是现代计算机中 MAR 和 MDR 通常会被集成在 CPU 中。

1.2.3 计算机软件

系统软件和应用软件

计算机软件可以分为：系统软件和应用软件。

应用软件是为了解决某个应用领域的问题而编制的程序。（面向用户）
系统软件负责管理硬件资源，并向上层应用程序提供基础服务。（面向硬件）

三种级别的语言

计算机中三种级别的语言从距离硬件距离近到远分别是：机器语言（二进制代码）、汇编语言（助记符）、高级语言（C/C++、Java、Python）

高级语言通过编译程序（编辑器），将高级语言翻译成汇编语言，然后汇编语言通过汇编程序（汇编器）将汇编语言翻译成机器语言执行。

高级语言 -> 汇编语言 -> 机器语言

有些高级语言会通过编译程序（编译器）直接跳过翻译成汇编语言，直接到机器语言。

如 JavaScript、Python、Shell 等语言，会通过解释程序（解释器），直接到机器语言。

编译程序：将高级语言编写的源程序全部语句一次全部翻译成机器语言程序，而后再执行机器语言程序（只需翻译一次）
解释程序：将源程序的一条语句翻译成对应于机器语言的语句，并立即执行。紧接着再翻译下一句（每次执行都要翻译）

因此解释程序的执行效率通常比较低下。

软件和硬件的逻辑功能等价性

软件和硬件的逻辑功能等价性：同一个功能，既可以用硬件实现（性能高、成本高），也可以用软件实现（性能低、成本低）

指令集体系结构（ISA）：软件和硬件之间的界面。设计计算机系统的ISA，就是要定义一台计算机可以支持哪些指令，以及每条指令的作用是什么、每条指令的用法是什么。

总结

1.2.4 计算机系统的层次结构

由最底层往上：微程序机器（微指令系统） -> 传统机器（用机器语言的机器） -> 虚拟机器（操作系统机器） -> 虚拟机器（汇编语言机器） -> 虚拟机器（高级语言机器）

1.2.5 计算机系统的工作原理

可执行文件被放在外存硬盘当中，当需要执行的时候，会将可执行文件调入存储器（内存）中进行执行，I/O 设备可以与程序进行交互。

1.3 计算机的性能指标

存储器的性能指标

主存储器分为：存储体、MAR 和 MDR。

• MAR 位数反映存储单元的个数（最多支持多少个地址）
• MDR 位数 = 存储字长 = 每个存储单元的大小

总容量 = 存储单元的个数 x 存储字长 (bit)
= 存储单元的个数 x 存储字长 / 8 (Byte)

1 Byte = 8 bit

Eg：MAR 为 32 位，MDR 为 8 位。
总容量 = 2³² * 8 bit = 4 GB

CPU 的性能指标

系统整体性能指标

数据通路带宽：数据总线一次所能并行传送信息的位数（各硬件部件通过数据总线传输数据）

吞吐量：指系统在单位时间内处理请求的数量。
它取决于信息能多快地输入内存，CPU 能多快地取指令，数据能多快地从内存取出或存入，以及所得结果能多快地从内存送给一台外部设备。这些步骤中的每一步都关系到主存，因此，系统吞吐量主要取决于主存的存取周期。

响应时间：指从用户向计算机发送一个请求，到系统对该请求做出响应并获得它所需要的结果的等待时间。
通常包括 CPU 时间（运行一个程序所花费的时间）与等待时间（用于磁盘访问、存储器访问、I/O 操作、操作系统开销等时间）。

系统整理的性能指标（动态测试）：基准程序（“跑分软件”）是用来测量计算机处理速度的一种实用程序，以便被测量的计算机性能可以与运行相同程序的其它计算机性能进行比较。

总结

2.1.1 进位计数制

其他进制 -> 十进制

二进制 < — > 八进制、十六进制

各种进制常见书写方式

• 二进制 —— B
• 八进制 —— O
• 十六进制 —— H
• 十进制 —— D

十进制 -> 任意进制

• 整数部分：除积取余
• 小数部分：乘积取整

拼凑法

真值和机器数

真值：符合人类习惯的数字

机器数：数字实际存到机器里的形式，正负号需要被“数字化”

总结

2.1.2 + 2.1.3 定点数的编码表示

定点数：小数点的位置固定
Eg：996.007 —— 常规计数

浮点数：小数点的位置不固定
Eg：9.96007 * 10² ——科学计数法

无符号数的表示

无符号数：整个机器字长的全部二进制位均为数值位，没有符号位，相当于数的绝对值。
通常只有无符号整数，而没有无符号小数。

有符号数的定点表示

可用原码、反码、补码三种方式来表示定点整数和定点小数。还可以用移码表示定点整数。

若真值为 x，则用[x]_原、[x]_反、[x]_补、[x]_移分别表示真值所对应的原码、反码、补码、移码。

原码

若机器字长为 n+1 位，原码整数的表示范围：
-(2ⁿ-1) ≤ x ≤ 2ⁿ-1 （关于原点对称）

若机器字长为 n+1 位，原码小数的表示范围：
-(1-2^-n) ≤ x ≤ 1-2^-n（关于原点对称）

真值 0 有 +0 和 -0 两种形式

反码

• 若符号位为 0，则反码与原码相同
• 若符号位为 1，则数值为全部取反

[+0]_原 = 00000000
[+0]_反 = 00000000

[-0]_原 = 10000000
[-0]_反 = 11111111

因为反码的表示与原码一一对应，所以反码与原码的表示范围都相同：

若机器字长为 n+1 位，反码整数的表示范围：
-(2ⁿ-1) ≤ x ≤ 2ⁿ-1 （关于原点对称）

若机器字长为 n+1 位，反码小数的表示范围：
-(1-2^-n) ≤ x ≤ 1-2^-n（关于原点对称）

真值 0 有 +0 和 -0 两种形式

“反码”只是“原码”转变为“补码”的一个中间态，实际中并没有什么卵用。

补码

• 正数的补码 = 原码
• 负数的补码 = 反码末尾 + 1（要考虑进位）、

原码 -> 补码：扫描法 —— 从右往左直到碰到第一个 1 都不变，再往前除了符号位全部取反。

因为 -0 的反码为 11111111，此时末尾加 1，-0 的补码为 00000000。（假设有 8 为固定机器字长）

注意：补码的真值 0 只有一种表示形式！
[+0]_补 = [-0]_补 = 00000000

定点整数补码 [x]_补 = 1,0000000 表示 x = -2⁷。因此若机器字长为 n+1 位，补码整数的表示范围：
-2ⁿ ≤ x ≤ 2ⁿ-1 （比原码多表示一个 -2ⁿ）

定点小数补码 [x]_补 = 1.0000000 表示 x = -1。因此若机器字长为 n+1 位，补码小数的表示范围：
-1 ≤ x ≤ 1-2^-n （比原码多表示一个 -1）

补码的补码为原码

移码

移码：补码的基础上符号位取反。
（注意：移码只能用于表示整数）

因为移码和补码的整数是一一对应的，因此移码整数表示范围和补码一样：
-2ⁿ ≤ x ≤ 2ⁿ-1

移码表示的整数可以让计算机硬件很方便比较大小：

练习

总结

2.1.2 + 2.1.3 各种码的作用

因为原码的第一位为符号位，在计算机中做运算非常不方便。
减法在计算机中不好实现（成本高），但是可以通过加法代替减法。

(mod 12)把所有整数分为 12 类（余数为 0 ~ 11）
mod 12 余数相同的数，都是同一类，都是等价的

即 10 + (-3)、10 + 9、10 + 21 … 在 (mod 12) 的条件下效果相同。
在 (mod m) 的条件下，若能找到负数的补数，就可以用正数的加法来等价替代减法。

模 – a 的绝对值 = a 的补数（正数）

结论：补码可以让减法操作转变为加法操作，节省硬件成本。

补码的作用：使用补码可将减法操作转变为等价的加法，ALU 中无需集成减法器。执行加法操作时，符号位一起参与运算。

移码的作用：移码表示的整数很方便比较大小。

2.2.1.1 加法器

如何用门电路实现一位加法？

一位全加器

n bit 加法器

不足之处：上述的 n bit 加法器，进位信息是串行产生的，计算速度取决于进位产生的传递速度。位数越多，运算速度越慢。（注 1：电信号到达稳态需要一定时间，因此进位产生速度会有延迟。注 2：串行进位又称为行波进位，每一级进位直接依赖于前一级的进位，即进位信号是逐级形成的。）

由于两个输入端允许并行输入 n bit，因此这种加法器属于：并行加法器
由于进位信息是串行产生的，因此从“进位方式”看，这种加法器属于：串行进位加法器

并行进位的并行加法器

基于上述串行加法器的不足之处，如果将低位向高位的进位改成并行运算，这样计算机的运算速度就会大大提高。

需要 n 位 CLA 部件来实现，这里不用知道电路是如何实现的，只需要关心加法器的逻辑功能即可。

进行进位的并行加法器：所有进位信息都是同时产生的，几乎没有延迟。
特点：运算速度比“串行进位的并行加法器”更快。

带标志位的加法器

加法器的输出结果 S，是我们需要关心的：

• 因为只有 n bit 位，计算的结果是否溢出？
• 计算的结果是否为 0？
• 计算结果的正/负？（比大小）

因此加法器还有 4 个输出位（OF、SF、ZF、CF）：

总结

2.2.1.2 并行进位加法器

上一小节介绍的并行进位加法器，更快产生进位的方法。（简单了解即可）

并行进位的并行加法器：各级欣慰信号同时形成，又称为先行进位、同时进位。

但是随着 C_i 数量的增加，继续套娃会导致电路越来越复杂。

所以一般套娃的 C₄，一般会设计 4 位 CLA 加法器（由 4 个和 FA 和一些新线路、运算逻辑组成）。

2.2.1.3 算数逻辑单元 ALU

CPU 由控制器、运算器组成

控制器负责解析指令，并根据指令功能发出相应的控制信号

运算器负责对数据进行处理，如：加减乘除等。

ALU 是一种组合逻辑电路，实现了加/减/乘/除、与/或/非等功能。因此 ALU 是运算器的核心。

由于加减乘除的等运算都要基于“加法”来实现，因此加法器是 ALU 的核心。

总结

2.2.2 定点数的移位运算

移位运算：通过改变各个数码位和小数点的相对位置，从而改变各数码位的位权。
应用：可以通过移位运算快速实现特殊数值的乘法、除法。

逻辑移位（常用于处理无符号整数）

逻辑左移，需要注意溢出的问题，导致运算错误。

逻辑右移需要注意丢失精度的问题。

逻辑移位：

• 逻辑左移：高位移出丢弃，低位补 0。
  • 需要注意溢出问题
• 逻辑右移：低位移出丢弃，高位补 0。
  • 需要注意丢失精度问题

算数移位（常用于处理带符号整数）

在现代计算机中，带符号整数都是用补码表示的。

算数移位：

• 逻辑左移：高位移出丢弃，低位补 0
  • 注意溢出问题
• 逻辑右移：低位移出丢弃，高位补符号位
  • 注意丢失精度问题

移位运算总结

• 逻辑/算数左移：高位移除丢弃，低位补 0
• 右移：
  • 逻辑右移：低位移出丢弃，高位补 0
  • 算数右移：低位移出丢弃，高位补符号位

除了算数右移，补符号位，其它都补 0

通常，逻辑移位是指原码移位；算数移位是指补码移位。
因此结论为：除了补码负数右移时补 1，其它全部通通补 0

总结

2.2.3.1 定点数的加减运算

原码的加减

原码的加法运算：

• 正 + 正 – > 绝对值做加法，结果为正（可能溢出）
• 负 + 负 – > 绝对值做加法，结果为负（可能溢出）
• 正 + 负 – > 绝对值大的减绝对值小的，符号同绝对值大的数
• 负 + 正 – > 绝对值大的减绝对值小的，符号同绝对值大的数

原码的减法运算，“减数”符号取反，转变为加法：

• 正 – 负 – > 正 + 正
• 负 – 正 – > 负 + 负
• 正 – 正 – > 正 + 负
• 负 + 正 – > 负 – 负

补码的加减运算

从上面原码加减的一堆规则中可以看出其复杂，对计算机来说更是如此。
所以计算机中的运算通常是补码来进行的。

[A + B]_补 = [A]_补 + [B]_补
[A – B]_补 = [A]_补 + [-B]_补

[-B]_补： [B]_补 连同符号位一起取反加 1

对于补码来说，无论加法还是减法，最后都会转变成加法，由加法器实现运算，符号位也参与运算。

溢出判断

计算机硬件判断是否溢出的方法之一，采用一位符号位不变，V 式子表示的意思就是如果两个符号相同的数与运算结果的符号不同，则表示溢出，采用一个新的变量 V 去记录。

第二种方法是也是采用一位符号位，根据数据位进位情况判断溢出。

第三种方法是用到最多的，采用双符号位。
正数符号为 00，负数符号为 11

• 结果的符号位为 01 表示上溢
• 结果的符号位为 10 表示下溢

双符号位补码又称：模 4 补码
单符号位补码又称：模 2 补码

双符号位补码实际在存储时只存储 1 个符号位，运算时会复制一个符号位。

总结

2.2.4.3 原码的除法运算

手算除法（二进制）

除法可以理解为：【被除数】%【除数】 = 【商】+【余数】

也可以理解为：【被除数】 = 【除数】*【商】+【余数】

之前在计算机基本组成中说到，运算器中的 ACC 在除法中用于存储被除数和余数，MQ 用于存储商，X 存储除数。

原码除法：恢复余数法

计算机中的除法方法其一：恢复余数法。

首先两个数相除，计算机会先不考虑其符号，而是取两个数的绝对值相除，最后的符号通过原数的符号做异或取得。因为其中有“减”的操作，也就是在取余操作的时候，会用除数去减被除数，因为减一个数就是加这个数的反，所以在操作之前要先对被除数的绝对值原码取补码，然后取被除数负数的补码。用[-|被除数|]_补去做操作。

恢复余数法的核心思想就是：因为计算机很傻，会先默认上商 1，如果搞错了再改成上商 0。并且“恢复余数”。实现方法就是上商 0 或 1，得到余数，最后在余数末尾补 0。

上图做商计算机的操作就是：

• 在 ACC 中存入被除数，在通用寄存器中存入除数。初始的商默认为 00000（图中深色的灰是当前要确定的一位商）。
• 然后计算机先默认在当前的商位置（深灰色部分）上 1，然后将通用寄存器中的数和 ACC 中的数放入 ALU 中，进行计算。
• ALU 中会将 ACC 中的被除数减去通用寄存器中的除数。然后将结果存到 ACC 中。
• 如果此时 ACC 中的数是负数，说明此时被除数小于除数，说明不应该商 1，而是商 0。（如果此时是正数，就跳过下面三条步骤）
• 所以 MQ 中的商从 1 改成 0。
• 然后将 ACC 中的数加上通用寄存器中的除数，恢复成原来的被除数。
• 继续之前的步骤，在 ALU 中计算被除数与除数相减的结果。
• 发现此时结果为正数，也就是上商是正确的。
• 然后进行下一位的商，此时将 ACC 中的除数和 MQ 中的商左移一位。
• 重复以上步骤，直至 MQ 中存放的商位存放满，除法结束。（若最后一步上商之后余数为负数，也需要恢复余数并商 0）

最后因为移位原因，余数的数值位需要对齐，所以余数应该为：ACC 中存放的数 * 2^-n（n 为移位次数，也就是商的位数）

原码除法的计算过程：

原码除法：加减交替法

前面的例子中，先默认上商 1，如果余数为负数，就加除数恢复余数，上商 0。观察这个步骤和下一步会做的事情，会发现上商 0 之后的下一个上商一定是 1。因此可以直接略过恢复余数的步骤，当余数为负的时候，可以直接将余数变成 0，然后让余数左移 1 位再加上除数。

加减交替法又可以称为不恢复余数法，其做法大致与恢复余数法相同，当遇到余数：

• 若余数为负，则可直接商 0，让余数左移 1 位再加上除数，得到下一个新的余数。
• 若余数为正，则商 1，让余数左移 1 位再减去除数，得到下应该新余数。

若最后遇到余数为负数，则也需要加除数恢复成正数。

加减交替法一共有 n + 1 次的加/减运算，每次加减确定一位商；左移 n 次（最后一次加减完不移位），最终可能还要再多一次加。

需要注意的是，因为这里讨论的是定点小数的除法，小数点的位置是确定的，所以这里被除数一定要小于除数，否则出来的结果大于 1，无法被定点数表示。因此计算机再判断这里的除法方法是否可行的时候，会判断商的第一位是否为 0，也就是一开始第一步被除数减除数时，第一次的余数一定是负数。

2.2.4.4 补码的除法运算

补码的除法类似原码除法的加减交替法。

补码除法的特点：

• 符号位参与运算
• 被除数/余数、除数采用双符号位

补码除法的规则：

1. 被除数与除数：
   • 被除数和除数同号，则被除数减去除数
   • 被除数和除数异号，则被除数加上除数
2. 余数与除数：
   • 余数和除数同号，商 1，余数左移一位减去除数
   • 余数和除数异号，商 0，余数左移一位加上除数
3. 重复 n 次
4. 商末尾恒置 1

3.1 存储系统基本概念

存储器的层次化结构

存储器的分类

存储器的分类（按层次）：

• 高速缓存（Cache） —— 可直接被 CPU 读写
• 主存储器（主存、内存） —— 可直接被 CPU 读写
• 辅助存储器（辅存、外存）

存储器的分类（按存储介质）：

• 半导体存储器（主存、Cache） —— 以半导体器件存储信息
• 磁表面存储器（磁带、磁盘） —— 以磁性材料存储信息
• 光存储器 —— 以光介质存储信息

存储器的分类（按存取方式）：

• 随机存取存储器（Random Access Memory, RAM）
  • 读写任何一个存储单元所需时间都相同，与存储单元所在的物理位置无关
• 顺序存取存储器（Sequential Access Memory, SAM）
  • 读写一个存储单元所需时间取决于存储单元所在的物理位置
• 直接存取存储器（Direct Access Memory, DAM）
  • 既有随机存取特性，也有顺序存取特性。先直接选取信息所在区域，然后按顺序方式存取
• 相联存储器（Associative Memory），即可以按内容访问的存储器（Content Addressed Memory, CAM）
  • 可以按照内容检索到存储位置进行读写，“快表”就是一种相联存储器

顺序存取寄存器（SAM）和直接存取存储器（DAM）也可以称为串行访问存储器：读写某个存储单元所需时间与存储单元的物理位置有关

存储器的分类（按信息的可更改性）：

• 读写存储器（Read/Write Memory） —— 既可读、也可写
  • 如：磁盘、内存、Cache
• 只读存储器（Read Only Memory） —— 只能读，不能写
  • 如：实体音乐专辑通常采用 CD-ROM，实体电影采用蓝光光碟，BIOS 通常写在 ROM 中
  • （实际上很多 ROM 也可多次读写，只是比较麻烦）

存储器的分类（按信息的可保存性）：

• 易失性存储器（主存、Cache）
  • 断电后，存储信息消失的存储器
• 非易性存储器（磁盘、光盘）
  • 断电后，存储信息依然保持的存储器
• 破坏性读出（如 DRAM 芯片，读出数据后要进行重写）
  • 信息读出后，原存储信息被破坏
• 非破坏性读出（如 SRAM 芯片、磁盘、光盘）
  • 信息读出后，原存储信息不被破坏

存储器的性能指标

总结

3.5.1 + 3.5.2 Cache 的基本原理

Cache 的工作原理

局部性原理

程序执行具有局部性。

• 空间局部性：在最近的未来要用到的信息（指令和数据），很可能与现在正在使用的信息在存储空间上是临近的
  • Eg：数组元素、顺序执行的指令代码
• 时间局部性：在最近的未来要用到的信息，很可能是现在正在使用的信息
  • Eg：循环结构的指令代码

基于局部性原理，不难想到，可以把 CPU 目前访问的地址“周围”的部分数据放到 Cache 中。

上图中的程序 B，由于按“列优先”访问二维数组，所以其空间局部性更差（Cache 没有按列优先保存数据），因此程序 B 的运行效率比程序 A 要差。

性能分析

设 t_c 为访问一次 Cache 所需时间，t_m 为访问一次主存所需时间

命中率 H：CPU 欲访问的信息已在 Cache 中的比率

缺失（未命中）率 M = 1 – H

Cache —— 主存 系统的平均访问时间 t 为：

• t = Ht_c + (1 – H)(t_c + t_m)
  • 先访问 Cache，若 Cache 未命中再访问主存
• t = Ht_c + (1 – H)t_m
  • 同时访问 Cache 和主存，若 Cache 命中则立即停止访问主存

有待解决的问题

总结

4.1.1 + 4.1.2 + 4.1.3 指令的基本格式

指令（又称机器指令）：是指计算机执行某种操作的命令，是计算机运行的最小功能单位。一台计算机的所有指令的集合构成该机的指令系统，也称为指令集。

注：一台计算机只能执行自己指令系统中的指令，不能执行其他系统的指令。（这也就是为什么 x86 架构的软件无法在 ARM 架构中运行，因为两边的指令集不同）

一条指令就是机器语言的一个语句，它是一组有意义的二进制代码。

一条指令可以分为操作码和地址码。

• 操作码（OP）：指明了“做什么”
• 地址码（A）：指明了“对谁动手”

有点指令不需要地址吗（如停机操作）

一条指令可能包含 0 个、1 个、2 个、3 个、4 个地址码。根据地址码数目不同，可以将指令分为零地址指令、一地址指令、二地址指令。

根据地址码不同分类

零地址指令

（|OP|）

零地址指令的使用情况，也就是不需要指明操作数的情况：

1. 不需要操作数，如空操作、停机、关中断等指令
2. 堆栈计算机，两个操作数隐含存放在栈顶和次栈顶，计算结果压回栈顶

一地址指令

（|OP|A₁|）

一地址指令的使用：

1. 只需要单操作数，如加 1、减 1、取反、求补等
   • 指令含义：OP(A₁) -> A₁
   • 完成一条指令需要 3 次访存：读取 -> 读 A₁ -> 写 A₁
2. 需要两个操作数，但其中一个操作数隐含在某个寄存器（如隐含在累加寄存器 ACC）
   • 指令含义：(ACC)OP(A₁) -> ACC
   • 完成一条指令需要 2 次访存：读取 -> 读 A₁

注：A₁ 指某个主存地址，(A₁)表示 A₁ 所指向的地址中的内容

二地址指令

（|OP|A₁（目的操作数）|A₂（源操作数）|）

二地址指令常用于需要两个操作数的算术运算、逻辑运算相关指令

指令含义：(A₁)OP(A₂) -> A₁

完成一条指令需要访存 4 次，读指 -> 读 A₁ -> 读 A₂ -> 写 A₁

默认将运算结果存到 A₁ 但是这样会使原本 A₁ 的数据丢失。

三地址指令

（|OP|A₁|A₂|A₃（结果）|）

常用于需要两个操作数的算术运算、逻辑运算相关指令

指令含义：(A1)OP(A2) -> A3

完成一条指令需要访存 4 次，取指 -> 读 A₁ -> 读 A₂ -> 写 A₃

将结果放到新的贮存单元，以保证原被操作数不会丢失。

四地址指令

（|OP|A₁|A₂|A₃（结果）|A₄（下址）|）

指令含义：(A₁)OP(A₂) -> A₃，A₄ = 下一条将要执行指令的地址

完成一条指令需要访存 4 次，取指 -> 读 A₁ -> 读 A₂ -> 写 A₃

正常情况下：取指令之后 PC + 1，指向下一条指令
四地址指令：执行指令后，将 PC 的值修改为 A₄ 所指的地址

地址码的位数有什么影响？

n 位地址码的直接寻址范围 = 2ⁿ

若指令总长度固定不变，则地址码数量越多，寻址能力越差。

按指令长度分类

指令字长：一条指令的总长度（可能会变）

机器字长：CPU 进行一次整数运算所能处理的二进制数据的位数（通常和 ALU 直接相关）

存储字长：一个存储单元中的二进制代码位数（通常和 MDR 位数相同）

半字长指令、单字长指令、双字长指令 —— 指令长度是机器字长的多少倍。

• 半字长指令：指令字长等于机器字长一半的指令
• 单字长指令：指令字长等于机器字长的指令
• 双字长指令：指令字长等于机器字长两倍的指令

指令字长会影响取指所需时间。

如：假设机器字长 = 存储字长 = 16bit，则取一条双字长指令需要两次访存

定长指令字结构：指令系统中所有指令的长度都相等

变长指令字结构：指令系统中各种指令的长度不等

按操作码长度分类

• 定长操作码：指令系统中所有指令的操作码长度都相同
  • n 位 -> 2ⁿ 条指令
  • 控制器的译码电路设计简单，但灵活性较低
• 可变长操作码：指令系统中各指令的操作码长度可变
  • 控制器的译码电路设计复杂，但灵活性较高

定长指令字结构 + 可变长操作码 -> 扩展操作码指令格式

按操作类型分类

总结

7.1.3 外部设备

输入设备

键盘是最常用的输入设备，通过它可发出命令或输入数据。每个键相当于一个开关，当按下键时，电信号连通。当松开键时，弹簧把键弹起，电信号断开。

键盘输入信息可分为 3 个步骤：

1. 查出按下的是哪个键；
2. 将该键翻译成能被主机接收的编码，如 ASCII 码；
3. 将编码传送给主机。

鼠标是常用的定位输入设备，它把用户的操作与计算机屏幕上的位置信息相联系。常用的鼠标有机械式和光电式两种。

工作原理：当鼠标在平面上移动时，其底部传感器把运动的方向和距离检测出来，从而控制光标做相应运动。

显示器

按显示设备所用的显示器件分类：

• 阴极射线管（CRT）显示器
• 液晶显示器（LCD）
• LED 显示器
• …

按所显示的信息内容分类：

• 字符显示器
• 图形显示器
• 图像显示器

比如一台显示器的分辨率为：1440 x 900，帧缓冲深度为 24 位彩色，则其 VRAM 最小（一帧的大小即为显存的理论最小值）为 1440 * 900 * 3 B ≈ 3.7 MB；如果显示器刷新率 = 60 Hz，则显存带宽至少要 3.7 * 60 = 222 MB/s。

注：现代计算机中，显存除了作为当前显示帧的缓存，还会用于保存即将渲染的图像数据。

集成显卡计算机中，通常分配一片内存作为显存。

打印机

总结

计算机操作系统

1.1.1 + 1.1.3 操作系统的概念、功能

操作系统（Operating System， OS）是指控制和管理整个计算机系统的硬件和软件资源【操作系统是系统资源的管理者】，并合理地组织调度计算机的工作和资源的分配；以提供给用户和其他软件方便的接口和环境【向上层提供方便易用的服务】；它是计算机系统中最基本的软件系统【是最接近硬件的一层软件】。

操作系统的功能和目标——作为系统资源的管理者

执行一个程序前需要先将该程序放到内存中，才能被 CPU 处理。

操作系统的功能和目标——向上层提供方便易用的服务

封装思想：操作系统把一些丑陋的硬件功能封装成简单易用的服务，使用户能更方便地使用计算机，用户无需关心底层硬件的原理，只需要对操作系统发出命令即可。

操作系统的功能和目标——作为最接近硬件的层次

操作系统是对硬件机器的拓展。

没有任何软件支持的计算机称为裸机。在裸机上安装的操作系统，可以提供资源管理功能和方便用户的服务功能，将裸机改造成功能更强、使用更方便的机器。

通常把覆盖了软件的机器称为扩充机器，又称之为虚拟机。

操作系统对硬件机器的拓展：将 CPU、内存、磁盘、显示器、键盘等硬件合理地组织起来，让各种硬件能够相互协调配合，实现更多更复杂的功能。

总结

1.1.2 操作系统的特征

操作系统的特征——并发

并发：指两个或多个事件在同一个时间间隔内发生。这些事件宏观上是同时发生的，但微观上是交替发生的。【易混淆概念——并行：指两个或多个事件在同一时刻同时发生。】

操作系统的并发性指计算机系统中“同时”运行多个程序，这些程序宏观上看是同时运行着的，而微观上看是交替运行的。
操作系统就是伴随着“多道程序技术”而出现的。因此，操作系统和程序并发是一起诞生的。

注意：
单核 CPU 同一时刻只能执行一个程序，各个程序只能并发地执行。
多核 CPU 同一时刻可以同时执行多个程序，多个程序可以并行地执行。

并发性是操作系统一个最基本的特性。

操作系统的特征——共享

共享即资源共享，是指系统中的资源可供内存中多个并发执行的进程共同使用。

如果失去并发性，则系统中只有一个程序正在运行，则共线性失去存在的意义。
如果失去共享性，则两个程序不能同时访问硬盘资源，就无法实现同时发送文件，也就无法并发。

所以共享性和并发性互为存在条件。

操作系统的特征——虚拟

虚拟是指把一个物理上的实体变为若干个逻辑上的对应物。物理实体（前者）是实际存在的，而逻辑上对应物（后者）是用户感受到的。

没有并发性，就谈不上虚拟性。

操作系统的特征——异步

异步是指，在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。

只有系统拥有并发性，才有可能导致异步性。

总结

1.2 操作系统的发展与分类

手工操作阶段

主要缺点：用户独占全机、人机速度矛盾导致资源利用率极低。

批处理阶段

单道批处理系统（操作系统的雏形）：引入脱机输入/输出技术，并由监督程序负责控制作业的输入/输出。

• 主要优点：缓解了一定程度的人机速度矛盾，资源利用率有所提升。
• 主要缺点：内存中仅能有一道程序运行，只有该程序运行结束之后才能调入下一道程序。CPU 有大量时间是在空闲等待 I/O 完成。资源利用率依然很低。

多道批处理系统（操作系统正式诞生，用于支持多道程序并发运行）：每次往内存中读入多道程序。

• 主要优点：多道程序并发执行，共享计算机资源。资源利用率大幅提升，CPU 和其他资源更能保持“忙碌”状态，系统吞吐量增大。
• 主要缺点：用户响应时间长，没有人机交互功能（用户提交自己的作业之后就只能等待计算机处理完成，中间不能控制自己的作业执行。eg：无法调试程序/无法在程序执行的过程中输入一些参数）

分时操作系统

分时操作系统：计算机以时间片为单位轮流为各个用户/作业服务，各个用户可通过终端与计算机进行交互。

• 主要优点：用户请求可以被即时响应，解决了人机交互问题。允许多个用户同时使用一台计算机，并且用户对计算机的操作相互独立，感受不到别人的存在。
• 主要缺点：不能优先处理一些紧急任务。操作系统对各个用户/作业都是完全公平的，循环地为每个用户/作业服务一个时间片，不区分任务和紧急性。

实时操作系统

主要优点：能够优先响应一些紧急任务，某些紧急任务不需时间片排队。在实时操作系统的控制下，计算机系统接收到外部信号后及时进行处理，并且要在严格的时限内处理完事件。实时操作系统的主要特点是及时性和可靠性。

实时操作系统还分为：硬实时系统和软实时系统。

总结

1.3.1 操作系统的运行机制

一条高级语言的代码翻译过来可能会对应多条机器指令。
程序运行的过程其实就是 CPU 执行一条一条的机器指令的过程。

我们普通程序员写的程序就是“应用程序”。
微软、苹果有一帮人负责实现操作系统，他们写的是“内核程序”。

由很多内核程序组成了“操作系统内核”，或简称“内核（Kernel）”。
内核是操作系统最重要最核心的部分，也是最接近硬件的部分。
甚至可以说，一个操作系统只要有一个内核就够了（eg：Docker -> 仅需 Linux 内核就能完成功能）
操作系统的功能未必都在内核中，如图形化用户界面 GUI

两种指令

操作系统内核作为“管理者”，有时会让 CPU 执行一些“特权指令”，如：内存清零指令。这些指令影响重大，只允许“管理者”——即操作系统内核来使用。

应用程序只能使用“非特权指令”，如：加法指令、减法指令等。

在 CPU 设计和生产的时候就划分了特权指令和非特权指令，因此 CPU 执行一条指令前就能判断出其指令类型。

两种处理器状态

CPU 能判断出指令类型，但是它是怎么区分此时正在运行的是内核程序 or 应用程序？

CPU 有两种状态：“内核态” 和 “用户态”

• 处于内核态时，说明此时正在运行的是内核程序，此时可以执行特权指令。
• 处于用户态时，说明此时正在运行的是应用程序，此时只能执行非特权指令。

拓展：CPU 中有一个寄存器叫程序状态字寄存器（PSW），其中有个二进制位，1 表示“内核态”，0 表示“用户态”。

总结

1.3.2 中断和异常

中断的作用

“中断”会使 CPU 由用户态变为内核态，使操作系统重新夺回对 CPU 的控制权。

CPU 上会运行两种程序，一种是操作系统内核程序（是整个系统的管理者），一种是应用程序。
在合适的情况下，操作系统内核会把 CPU 的使用权主动让给应用程序。

“中断”是让操作系统内核夺回 CPU 使用权的唯一途径。

如果没有“中断”机制，那么一旦应用程序上 CPU 运行，CPU 就会一直运行这个程序。这样也就失去了操作系统的并发性特征。

内核态 -> 用户态：执行一条特权指令——修改 PSW 的标志位为“用户态”，这个动作意味着操作系统将主动让出 CPU 使用权。
用户态 -> 内核态：由“中断”引发，硬件自动完成变态过程，触发中断信号意味着操作系统将强行夺回 CPU 使用权。

中断的类型

• 内中断：与当前执行的指令有关，中断信号来源于 CPU 内部。
• 外中断：与当前执行的指令无关，中断信号来源于 CPU 外部。

内中断的例子：

• 若当前执行的指令使非法的，则会引发一个中断信号。
  • 试图在用户态下执行特权指令
  • 执行除法指令时发现除数为 0
• 有时候应用程序想请求操作系统内核的服务，此时会执行一条特殊的指令——陷入指令，该指令会引发一个内部中断信号。（陷入指令不是一个特权指令。执行“陷入指令”，意味着应用程序主动地将 CPU 控制权还给操作系统内核。“系统调用”就是通过陷入指令完成的。）

外中断的例子：

• 时钟中断——由时钟部件发来的中断信号。【比如当前 CPU 正在处理应用程序 1 的任务，时钟部件每隔一个时间片（如 50ms）会给 CPU 发送一个时钟中断信号，此时 CPU 会处理时钟中断的内核程序，接着将 CPU 分配给应用程序 2 使用。】
• I/O 中断——由输入/输出设备发来的中断信号。【当输入输出任务完成时，向 CPU 发送中断信号来表示任务的完成。】

每一条指令执行结束时，CPU 都会例行检查是否有外中断信号。

中断机制的基本原理

总结

1.3.3 系统调用

操作系统作为用户和计算机硬件之间的接口，需要向上提供一些简单易用的服务。主要包括命令接口和程序接口。其中，程序接口由一组系统调用组成。

“系统调用”是操作系统提供给应用程序（程序员/编程人员）使用的接口，可以理解为一种可供应用程序调用的特殊函数，应用程序可以通过系统调用来请求获得操作系统内核的服务。

系统调用与库函数的区别

高级语言中，通过库函数调用系统调用，从而请求内核的服务。

为什么系统调用是必须的？

什么功能要用到系统调用？

应用程序通过系统调用请求操作系统的服务。而系统中的各种共享资源都由操作系统内核统一掌管，因此凡是与共享资源有关的操作（如存储分配、I/O 操作、文件管理等），都必须通过系统调用的方式向操作系统内核提出服务请求，由操作系统内核代为完成。这样可以保证系统的稳定性和安全性，防止用户进行非法操作。

系统调用的过程

传递系统调用参数 -> 执行陷入指令（用户态） -> 执行相应的内请求核程序处理系统调用（核心态） -> 返回应用程序

注意：

• 陷入指令是在用户态执行的，执行陷入指令之后立即引发一个内中断，使 CPU 进入核心态。
• 发出系统调用请求是在用户态，而对系统调用的相应处理在核心态下进行。

陷入指令 = trap 指令 = 访管指令

总结

2.1.1 + 2.1.2 进程的概念、组成、特征

进程的概念

程序：是静态的，就是个存放在磁盘里的可执行文件，就是一系列的指令集合。

进程（Process）：是动态的，是程序的一次执行过程。（同一个程序多次执行会对应多个进程）

操作系统作为进程的管理者，为了区分各个进程，当进程被创建时，操作系统会为该进程分配一个唯一的、不重复的”身份证号“——PID（Process ID，进程ID）。

操作系统要记录PID、进程所属用户ID（UID）【基本的进程描述信息，可以让操作系统区分各个进程】
还要记录给进程分配了哪些资源（如：分配了多少内存、正在使用哪些 I/O 设备、正在使用哪些文件）【可用于实现操作系统对资源的管理】
还要记录进程的运行情况（如：CPU 使用时间、磁盘使用情况、网络流量使用情况等）【可用于实现操作系统对进程的控制、调度】

这些信息都被保存在一个数据结构 PCB（Process Control Block）中，即进程控制块
操作系统需要对各个并发的进程进行管理，但凡管理时所需要的信息，都会被放在 PCB 中

PCB 是进程存在的唯一标志，当进程被创建时，操作系统为其创建 PCB，当进程结束时，会回收其 PCB。

进程的组成——程序段、数据段

PCB 是给操作系统用的。
程序段、数据段是给进程自己用的，与进程自身的运行逻辑有关。

一个程序开始运行前，需要创建对应的进程，也就是要创建相应的 PCB。

一个进程实体（进程映像）由 PCB、程序段、数据段组成。
进程是动态的，进程实体（进程映像）是静态的。
进程实体反应了进程在某一时刻的状态。

所以更准确的说，进程实体（进程映像）由 PCB、程序段、数据段组成的。
不过一般情况下不区分进程实体和进程的概念。所以粗略的说：进程就是由 PCB、程序段和数据段组成。

简单总结：
程序段、数据段、PCB 三部分组成了进程实体（进程映像）
引入进程实体感念后，可把进程定义为：
进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。
注意：PCB 是进程存在的唯一标志。

一个进程被“调度”，就是指操作系统决定让这个进程上 CPU 运行。

例子：同时挂三个 QQ 号，会对应三个 QQ 进程，它们的 PCB、数据段各不相同，但程序的内容都是相同的（都是运行着相同的 QQ 程序）

进程的特征

进程的特征：动态性、并发性、独立性、异步性、结构性。

总结

2.1.3 进程的状态与转换

进程的状态

进程正在被创建时，它的状态是“创建态”，在这个阶段操作系统会为进程分配资源、初始化 PCB。
当进程创建完成后，便进入“就绪态”，处于就绪态的进程已经具备运行条件，但由于没有空闲 CPU，就暂时不能运行。

系统中可能会有很多个进程都处于就绪态。当 CPU 空闲时，操作系统就会选择一个就绪进程，让它上处理机运行。如果一个进程此时正在 CPU 上运行，那么这个进程处于 “运行态”，CPU 会执行该进程对应的程序（执行指令序列）。

在进程运行过程中，可能会请求等待某个事件的发生（如等待某种系统资源的分配，或者等待其他进程的响应）。在这个事件发生之前，进程无法继续往下执行，此时操作系统会让这个进程下 CPU，并让它进入“阻塞态”。当 CPU 空闲时，又会选择另一个“就绪态”进程上 CPU 运行。

一个进程可以执行 exit 系统调用，请求操作系统终止该进程。此时该进程会进入“终止态”，操作系统会让该进程下 CPU，并回收内存空间等资源，最后还要回收该进程的 PCB。当终止进程的工作完成后，这个进程就彻底消失了。

进程状态的转换

进程的组织

进程的组织方式有两种：链式方式【用的多】和索引方式

链式方式：

索引方式：

总结

2.1.4 进程控制

基本概念

进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能。
简化理解：反正进程控制就是要实现进程状态转换

用“原语”实现进程控制。
原语是一种特殊的程序，它的执行具有原子性。也就是说，这段程序的运行必须是一气呵成，不可中断。

原语的执行具有原子性，即执行过程只能一气呵成，期间不允许被中断。
可以用“关中断指令”和“开中断指令”这两个特权指令实现原子性。

正常情况：CPU 每执行完成一条指令都会例行检查是否有中断信号需要处理，如果有，则暂停运行当前这段程序，转而执行相应的中断处理程序。
CPU 执行了关中断指令之后，就不再例行检查中断信号，直到执行开中断指令之后才会恢复检查。这样，关中断、开中断之间的这些指令序列就是不可被中断的，这就实现了“原子性”。

关中断指令和开中段指令都是特权指令，不允许用户进程使用。

进程控制相关的原语

进程的运行环境就是进程在运行时在 CPU 寄存器里存放的中间结果：
一个进程运行时，会将中间的运行结果存放到 CPU 的各个寄存器当中，以便 CPU 对这些操作进行处理，但是当进程切换的时候，存放在 CPU 寄存器里的数据就会被下一个进程的中间结果覆盖掉，所以切换进程的时候，会将上一个进程存放在 CPU 寄存器里的数据存放到 PCB 当中。PCB 可以保存当前进程的运行环境，而在之后这个进程再次被调入 CPU 运行时，将 PCB 中存放的数据放回 CPU 的寄存器中。

总结

2.1.5 进程通信

进程间通信（Inter-Process Communication, IPC）是指两个进程之间产生数据交互。

进程是分配系统资源的单位（包括内存地址空间），因此各进程拥有的内存地址空间相互独立。

为了保证安全，一个进程不能直接访问另一个进程的地址空间。

共享存储

因为两个进程间通信中，一个进程不能直接访问另一个进程的地址空间，因此两个进程通信时会申请一个共享存储区，这个共享存储区可以被两个进程共同存取。但为了避免两个进程同时存和同时取而出错，各个进程对共享空间的访问应该是互斥的。
各个进程可使用操作系统内核提供的同步互斥工具（如 P、V操作）

• 基于存储区的共享：操作系统在内存中划出一块共享存储区，数据的形式、存放位置都由通信进程控制，而不是操作系统。这种共享方式速度很快，是一种高级通信方式。
• 基于数据结构的共享：比如共享空间里只能放一个长度为 10 的数组。这种共享方式速度慢、限制多，是一种低级通信方式。不过这种共享方式的好处是：空间利用率高、数据一致性强、更高的并发性、更好的可维护性。

消息传递

进程间的数据交换以格式化的信息（Message）为单位。进程通过操作系统提供的“发送信息/接收信息”两个原语进行数据交换。

• 直接通信方式：点名道姓（进程）的消息传递
• 间接通信方式：以“信箱”作为中间实体进行消息传递。（可以多个进程往一个信箱发送消息，也可以多个进程从同一个信箱中 receive 消息）

管道通信

“管道”是一个特殊的共享文件，又名 pipe 文件。其实就是在内存中开辟一个大小固定的内存缓冲区。管道的结构类似循环队列，遵循先进先出。

1. 管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。
2. 各进程要互斥地访问管道（由操作系统实现）
3. 当管道写满时，写进程将阻塞，直到读进程将管道中的数据取走，即可唤醒写进程。
4. 当管道读空时，读进程将阻塞，直到写进程往管道中写入数据，即可唤醒读进程。
5. 管道中的数据一旦被读出，就彻底消失。因此，当多个进程读同一个管道时，可能会错乱。因此，通常有两种解决方案：A. 一个管道允许写多个进程，一个读进程；B. 允许有多个写进程，多个读进程，但系统会让各个读进程轮流从管道中读数据。

总结

2.1.6.1 线程的概念与特点

什么是线程

可以把线程理解为“轻量级进程”。

线程是一个基本的 CPU 执行单元，也是程序执行流的最小单位。
引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务（如 QQ 视频、文字聊天、传文件）

引入线程之后，进程只能作为除 CPU 之外的系统资源的分配单元（如打印机、内存地址空间等都是分配各进程的）。

引入线程后，有什么变化？

线程的属性

2.1.6.2 线程的实现方式和多线程模型

线程的实现方式

用户级线程（早期操作系统不支持线程这个概念的时候，通过程序的线程库实现线程的概念）：

内核级线程：

多线程模型

上述的线程实现方式，无论是用户级线程还是内核级线程都有自己的缺点，而多线程模型同时兼顾了前两个的优点。多线程模型在支持内核级线程的系统中，根据用户级线程和内核级线程的映射关系，可以划分为几种多线程模型。

总结

2.1.6.3 线程的状态与转换

状态与转换

与进程的状态转换基本一致，但线程的状态转换只关注就绪、运行、阻塞状态。

线程的组织与控制

一个进程叫 PCB。一个线程叫 TCB（线程控制块）。

2.2.1 调度的概念、层次

基本概念

当有一堆任务要处理，但由于资源有限，这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序，这就是“调度”研究的问题。

三个层次

作业：一个具体的任务
作业是还没跑的任务，进程是正在跑的程序。
用户向系统提交一个作业 ≈ 用户让操作系统启动一个程序（来处理一个具体的任务）

内存空间有限，有时无法将用户提交的作业全部放入内存。

• 高级调度（作业调度）。—— 按一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。
  • 每个作业只调入一次，调出一次。作业调入时会建立 PCB，调出时才撤销 PCB。
  • 高级调度（作业调度）简单理解：好几个程序需要启动，到底先启动哪个的问题。
• 低级调度（进程调度/处理机调度）—— 按照某种策略从就绪队列中选取一个进程，将处理机分配给它。
  • 进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。
  • 进程调度频率很高，一般几十毫秒一次。
• 中级调度（内存调度）—— 按照某种策略决定将哪个处于挂起状态的进程重新调度内存。
  • 内存不够时，可将某些进程的数据调出外存。等内存空闲或者进程需要运行时再重新调入内存。暂时调到外存等待的进程状态为挂起状态。被挂起的进程 PCB 会被组织成挂起队列。
  • 一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高。

挂起相关的补充与七状态模型：

总结

2.2.2.1 + 2.2.4 进程调度的时机、切换与过程、方式

进程调度的时机

进程调度（低级调度），就是按照某种算法从就绪队列中选择一个进程为其分配处理机。

进程在操作系统内核程序临界区中不能进行调度与切换。

进程调度的方式

• 非剥夺调度方式，又称非抢占方式。即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程任然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。
  • 实现简单，系统开销小但是无法及时处理紧急任务，适合于早期的批处理系统
• 剥夺调度方式，又称抢占方式。当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。
  • 可以优先处理更紧急的进程，也可实现让各种进程按时间片轮流执行的功能（通过时钟中断）。适合分时操作系统、实时操作系统

进程的切换与过程

“狭义的进程调度”与“进程切换”的区别：
狭义的进程调度指的是从就绪队列中选中一个要运行的进程。（这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程，后一种情况就需要进程切换）
进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。

广义的进程调度包含了选择一个进程和进程切换两个步骤。

进程切换的过程主要完成了：
1. 对原来运行进程各种数据的保存
2. 对新的进程各种数据的恢复
（如：程序计数器、程序恢复字、各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块）

注意：进程切换是有代价的，因此如果过于频繁的进行进程调度、切换，必然会使整个系统的效率降低，使系统大部分时间都花在了进程切换上，而真正用于执行进程的时间减少。

总结

2.2.2.2 调度器和闲逛进程

调度器

• 不支持内核级线程的操作系统，调度程序的处理对象是进程。
• 支持内核级线程的操作系统，调度程序的处理对象是内核线程。

闲逛进程

计算机启动后，CPU 永远都是在工作的。

闲逛进程就是调度程序的备胎，没有其他就绪进程时，运行闲逛进程（idle）。

闲逛进程的特性：

• 优先级最低
• 可以是 0 地址指令，占一个完整的指令周期（指令周期末尾例行检查中断）
• 能耗低

2.2.3 调度的目标（调度算法的评价指标）

CPU 利用率

系统吞吐量

周转时间

有的作业运行时间短，有的作业运行时间长，但是周转时间仅简单计算了作业提交到完成的时间，而作业在等待 CPU 运行的时间也是会被算到周转时间当中的。因此在周转时间相同的情况下，运行时间不同的作业，给用户的感觉肯定是不一样的。

因此为了衡量作业运行时间给用户的感受，需要移除作业等待时间，因此有了带权周转时间。

等待时间

响应时间

对于计算机用户来说，会希望自己提交的请求（比如通过键盘输入了一个调试命令）尽早地开始被系统服务、回应。

响应时间，指从用户提交请求到首次产生响应所用的时间。

总结

2.2.5.1 调度算法：先来先服务、最短作业优先、最高响应比优先

先来先服务

先来先服务（FCFS）：

• 算法思想
  • 主要从“公平”的角度考虑（类似于我们生活中排队买东西的例子）
• 算法规则
  • 按照作业/进程到达的先后顺序进行服务
• 用于作业/进程调度
  • 用于作业调度时，考虑的是哪个作业先到达后备队列；用于进程调度时，考虑的是哪个进程先到达就绪队列
• 是否可抢占？
  • 非抢占式的算法
• 优缺点
  • 优点：公平、算法实现简单
  • 缺点：排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。即，FCFS 算法对长作业有利，对短作业不利
• 是否会导致饥饿（某进程/作业长期得不到服务）
  • 不会

短作业优先

• 如果未特别说明，所提到的“短作业/进程优先算法”默认是非抢占式的
• 在所有进程同时可运行时，采用 SJF 调度算法的平均等待时间、平均周转时间最少
  或者说在所有进程都是几乎同时到达时，采用 SJF 调度算法的平均等待时间、平均周转时间最少
  如果不加上述前提条件，则应该说“抢占式的短作业/进程优先调度算法（最短剩余时间优先，SRNT 算法）的平均等待时间、平均周转时间最少”
• 虽然严格来说，SJF 的平均等待时间、平均周转时间并不一定最少，但相比于其他算法（如 FCFS），SJF 依然可以获得较少的平均等待时间、平均周转时间
• 如果遇到“SJF 算法的平均等待时间、平均周转时间最少”的选项，最好判断其它选项是不是有很明显的错误，如果没有更合适的选择，这个选项说法也应是对的

短作业优先（SJF）：

• 算法思想
  • 最求最少的平均等待时间，最少的平均周转时间、最少的平均带权周转时间
• 算法规则
  • 最短的作业/进程优先得到服务（所谓“最短”，是要求服务时间最短）
• 用于作业/进程调度
  • 既可用于作业调度，也可用于进程调度。用于进程调度时称为“短进程优先（SPF, Shortest Process First）算法”
• 是否可抢占？
  • SJF 和 SPF 是非抢占式的算法。但是也有抢占式的版本——最短剩余时间优先算法（SRTN, Shortest Remaining Time Next）
• 优缺点
  • 优点：“最短的”平均等待时间、平均周转时间
  • 缺点：不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先
• 是否会导致饥饿
  • 会。如果源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生“饥饿”现象。如果一直得不到服务，则称为“饿死”

高响应比优先

高响应比优先（HRRN）：

• 算法思想
  • 要综合考虑作业/进程的等待时间和要求服务的时间
• 算法规则
  • 在每次调度时先计算各个作业/进程的响应比，选择响应比高的作业/进程为其服务
  • 响应比 = （等待时间 + 要求服务时间） / 要求服务时间
  • （响应比 ≥ 1）
• 用于作业/进程调度
  • 既可用于作业调度，也可用于进程调度
• 是否可抢占？
  • 非抢占式的算法。因此只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比
• 优缺点
  • 综合考虑了等待时间和运行时间（要求服务时间）
  • 等待时间相同时，要求服务时间短的优先（SJF 的优点）
  • 要求服务时间相同时，等待时间长的优先（FCFS 的优点）
  • 对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题
• 是否会导致饥饿
  • 不会

总结

2.2.5.2 调度算法：时间片轮转、优先级、多级反馈队列

本章节的三种算法都常用于分时操作系统，更注重“响应时间”，因而这里不计算周转时间。

时间片轮转调度算法

如果时间片太大，使得每个进程都可以在一个时间片内完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。

另一方面，进程调度、切换是有时间代价的（保存、恢复运行环境），因此如果时间片太小，会导致进程切换过于频繁【一般来说，设计时间片时要让切换进程的开销占比不超过 1%】，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小。

时间片轮转（RR）：

• 算法思想
  • 公平地、轮流地为各个进程服务，让每个进程在一定时间内间隔内都可以得到响应
• 算法规则
  • 按照各个进程达到就绪队列的顺序，轮流让各个进程执行一个时间片（如 100 ms）。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队
• 用于作业/进程调度
  • 用于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间片）
• 是否可抢占？
  • 若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知 CPU 时间片已到
• 优缺点
  • 优点：公平；响应快，适用于分时操作系统；
  • 缺点：由于高频率的进程切换，因此有一定开销；不区分任务的紧急程度
• 是否会导致饥饿
  • 不会

优先级调度算法

优先级调度算法：

• 算法思想
  • 随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景都需要根据任务的紧急程度来决定处理顺序
• 算法规则
  • 调度时选择优先级最高的作业/进程
• 用于作业/进程
  • 既可用于作业调度，也可用于进程调度。甚至，还会用于 I/O 调度中
• 是否可抢占？
  • 抢占式、非抢占式都有。区别在于：非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占
• 优缺点
  • 优点：用优先级区分紧急程度、重要程度，适用于时候操作系统。可灵活地调整对各种作业/进程的偏好程度
  • 缺点：若源源不断地有高优先级进程到来，则可能导致饥饿
• 是否会导致饥饿
  • 会

多级反馈队列调度算法

多级反馈队列：

• 算法思想
  • 对其他调度算法的折中权衡
• 算法规则
  • 1. 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
  • 2. 新进程到达时先进入第 1 级队列，按 FCFS 原则排队等待被分配时间片，若用完成时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾
  • 3. 只有第 k 级队列为空时，才会为 k+1 级队头的进程分配时间片
• 用于作业/进程调度
  • 用于进程调度
• 是否可抢占？
  • 抢占式算法。在 k 级队列的进程运行过程中，若更上级的队列（1 ~ k-1 级别）中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回 k 级队列队尾
• 优缺点
  • 对各类型进程相对公平（FCFS 的优点）；每个新到达的进程都可以很快得到响应（RR 的优点）；短进程只用较少的时间就可以完成（SPF 的优点）；不必实现估计进程的运行时间（避免用户作假）；可灵活地调整对各类进程的偏好程度，比如 CPU 密集型进程、I/O 密集型进程（拓展：可以将因 I/O 而阻塞的进程重新放回原队列，这样 I/O 型进程就可以保持较高优先级）
• 是否会导致饥饿
  • 会

总结

2.2.5.3 调度算法：多级队列调度算法

2.3.1 同步与互斥的基本概念

什么是进程同步

进程具有异步性的特征。异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进。

同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

什么是进程互斥

我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备（比如摄像头、打印机）都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。

对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。

总结

2.3.2.1 进程互斥的软件实现方法

单标志法

因此，单标志法存在的主要问题是：违背“空闲让进”原则。

双标志先检查法

双标志后检查法

Peterson 算法

Peterson 算法进入区特点：1. 主动争取；2. 主动谦让；3. 检查对方是否也想使用，且对方最后一次是不是自己说了“客气话”。

Peterson 算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。Peterson 算法相较于之前三种软件解决方案来说，是最好的，但依然不够好。

总结

2.3.2.2 进程互斥的硬件实现方法

中断屏蔽方法

TestAndSet 指令

Swap 指令

总结

2.3.3 互斥锁

2.3.4.1 信号量机制

信号量机制

整形信号量

记录型信号量

总结

2.3.4.2 用信号量实现进程互斥、同步、前驱关系

信号量机制实现进程互斥

信号量机制实现进程同步

信号量机制实现前驱关系

总结

2.3.5.1 生产者-消费者问题

2.3.6 管程

为什么要引入管程

管程的定义和基本特征

用管程解决生产者消费者问题

总结

2.4.1 死锁的概念

什么是死锁

进程死锁、饥饿、死循环的区别

死锁产生的必要条件

什么时候会发生死锁

死锁的处理策略

总结

2.4.2 死锁的处理策略——预防死锁

破坏互斥条件

破坏不剥夺条件

破坏请求和保持条件

破坏循环等待条件

总结

2.4.3 死锁的处理策略——避免死锁

什么是安全序列

安全序列、不安全状态、死锁的联系

银行家算法

总结

2.4.4 死锁的处理策略——检测和解除

死锁的检测

总结

Linux 操作系统

期末再说吧~