Java 技术栈笔记 —— 计算机基础

Java Logo

序

本 Java 技术栈笔记系列文章，是读《JavaGuide（Java学习&面试指南）》这篇涵盖 Java 程序员需要掌握的核心知识的文章时的个人的摘录及补充笔记。未读此篇指南的读者请优先阅读，而本笔记仅针对个人情况做了筛选摘录与补充，留以自用，若同时也能您有所帮助深感荣幸。

在此感谢 JavaGuide 及开源社区，对本文有何建议欢迎补充。

《JavaGuide（Java学习&面试指南）》

计算机组成原理

本笔记源于《马士兵教育-MCA课程-计算机组成原理》

硬件基本组成

计算机硬件可以划分为主机与外设，其中主机包含：CPU（包含运算器、控制器）、存储器，外设包含：输入设备、输出设备。除这五大基本组成外，当然还包括将这些设备连接起来的主板，可以抽象为总线设备。

输入设备：键盘、鼠标，输入输出相对于 CPU/主机而言
输出设备：显示器、打印机，有些设备兼具输入输出功能：网卡、硬盘
存储器：分为主存与辅存，主存即内存条，辅存包含硬盘、闪存等
运算器：算数逻辑单元 ALU、通用寄存器，主要功能：算数、逻辑、移位运算
控制器：控制单元 CU、程序计数器 PC、指令寄存器 IR，主要功能：分析指令、给出控制信号

计算机结构

冯诺依曼计算机结构

五大单元：输入、输出、存储、运算和控制
采取二进制表示数据和指令

数据和指令同等地位在存储器中，并按地址寻访

指令由操作码、地址码组成，指令顺序存放和执行，可改变指令顺序
采用存储程序方式

事先编制好程序，并与所需数据预先存入主存

控制器自动地、连续地从存储器取出指令并执行
以运算器为核心

现代计算机结构

五大单元：输入、输出、存储、运算和控制
采用二进制表示数据和指令
采用存储程序方式
CPU：运算器与控制器合并到中央处理器
以存储器为核心，IO 设备尽可能绕过 CPU

计算机工作过程

预处理阶段：高级语言删除注释、引入包含文件
编译阶段：将高级语言转为汇编语言，指令代码
汇编阶段：将汇编语言转为二进制码，机器指令
链接阶段：将程序机器指令与库函数合并，装入内存

计算机性能指标

机器字长

基本字长，ALU 单次参与运算的二进制数据位数，决定了寄存器、ALU、数据总线位数，也代表运算精度（范围）。

易混淆的概念：

机器字长：一般等于基本字长，即内部寄存器的大小
指令字长：一个指令包含的二进制码的位数
存储字长：存储单元的二进制码的长度/位数

这三个字长彼此独立没有相关性，请注意区别。

主存容量

一般指主存最大容量，单位字节 Byte，运行时程序与数据都在主存中。主存容量越大，可运行的程序越多。

内存地址寄存器 MAR（Memory Address Register）的位数决定了最大可寻址范围。

运算速度

吞吐量和响应时间

吞吐量：单位时间处理的请求数量

信息输入内存速度、CPU 取指令速度、数据存/取的速度等等都会影响吞吐量

响应时间：用户发送请求到收到响应经过的时间

CPU 时间（运行程序花费的时间）、等待时间（磁盘/主存访问/IO操作/OS开销/网络传输）
CPU 时钟周期和主频

CPU 时钟周期：单个动作所花费的时间，单位：秒

CPU 最小的时间单位，每个动作至少一个时钟周期

节拍脉冲或 T 周期，为下方主频的倒数

主频（CPU 时钟频率）：单位时间完成基本动作的数量，单位：赫兹

机器内部主时钟的频率，主频越高花费时间越短，指令执行越快

赫兹 Hz，即： 次数/秒

时钟周期与主频关系：时钟周期 = 1 / 主频
CPI (Clock cycle Per Instruction)

执行一条指令所需的时钟周期数

CPU 执行时间

即 CPU 执行一个程序的全部指令所花费的时间，计算公式：

CPU 执行时间 = 程序全部指令所需时钟周期数 / 主频
            = (指令条数 * CPI) / 主频

其他

MIPS（Million Instructions Per Second）

百万条指令 / 秒，即每秒执行以百万条指令为单位的次数，即：
\[MIPS = 指令条数 \div \left( 执行时间 \times 10^6 \right)\]
MFLOPS（Mega Floating-point Operation Per Second）

百万浮点运算 / 秒，即每秒执行以百万条浮点运算的次数，即：
\[MFLOPS = 浮点运算次数 \div \left( 执行时间 \times 10^6 \right)\]
GFLOPS（Giga Floating-point Operation Per Second）

十亿浮点运算 / 秒，即每秒执行以十亿条浮点运算的次数，即：
\[GFLOPS = 浮点运算次数 \div \left( 执行时间 \times 10^9 \right)\]
TFLOPS（Tera Floating-point Operation Per Second）

万亿浮点运算 / 秒，即每秒执行以万亿条浮点运算的次数，即：
\[TFLOPS = 浮点运算次数 \div \left( 执行时间 \times 10^{12} \right)\]

数据表示及运算

数制与编码

进位计数制及相互转换

进位计数制，也称进位计数法，常见的进制：
- 二进制（Binary）：逢 2 进一
  
  字面量：0、1
  
  前缀表示法：0b、0B，例如：0b0001、0B0001
  
  后缀表示法：b、B，例如：0001b、0001B
- 八进制（Octal）：逢 8 进一
  
  字面量：0、1、2、3、4、5、6、7
  
  前缀表示法：0，例如：012
  
  后缀表示法：o、O 或 q、Q，例如：12o、12O
- 十进制（Decimal）：逢 10 进一
  
  字面量：0、1、2、3、4、5、6、7、8、9
- 十六进制（Hex）：逢 16 进一
  
  字面量：0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F
  
  前缀表示法：0x、0X，例如：0x0001、0X0001
  
  后缀表示法：h、H，例如：0001h、0001H
进制转换
- 任意进制转十进制
```
公式：
    (数码 * 权值) + (数码 * 权值) + ...
    
数码：当前进制的字面值
权值：以当前进制为底，当前数码所在位置（第一位为 0）为幂的计算结果
    
二进制转十进制：
----------------------------------------
    0B00010001
    (1 * 2^4) + (1 * 2^0) = 16 + 1 = 17
    
八进制转十进制：
-----------------------------------------
    O17
    (1 * 8^1) + (7 * 8^0) = 8 + 7 = 15
        
十六进制转十进制：
-----------------------------------------
    0X520
    (5 * 16^2) + (2 * 16^1) + (0 * 16^0) = 1280 + 32 + 0 = 1312
```
- 十进制转任意进制
  
  整数部分：除基取余，从下往上读作目标进制整数部分
  
  小数部分：乘基取整，从上往下读作目标进制小数部分
- 二进制与八、十六进制互转
真值和机器数

真值

日常用的数值，现阶段使用的十进制计数法，通常由符号位和绝对值组成，例如：-128

机器数

符号与数值一起编码，当取消符号位时即为无符号数。

目前的机器数采用二进制表示，因为二进制在目前电子计算机中最好表达（高低电平、开关电路）
- 无符号数
  
  每个 bit 位都是数值位时，称作无符号数。无符号数只有 0 和正数
- 有符号数
  
  最高位代表符号：0 表示正，1 表示负。正负数各占一半（包含：+0，-0）
- 原码
  
  真值直接转换后的机器数，称作原码
- 反码
  
  原码的符号位不变，数值位取反后的机器数，称作反码
  
  反码没有实际意义，只是原码求补码的中间过程，它不参与运算
- 补码
  
  反码 + 1 称作补码
  
  补码作用：
  - 消除 +0、-0 问题
  - 使 原码的减法运算 转变成 补码的加法运算
  规约：
  
  正数的原码、反码、补码都一样
  
  计算机中数的存储和运算都使用补码
字符与汉字编码

字符编码

ASCII：美国标准信息交换码，共计 128 字符（前 32 个为不可见字符）

汉字编码

GB2312、GB18030、GBK，一个字节占两个字节

UTF-8 国际通用字符集，兼容 ASCII 码，使用 1 ~ 4 个可变长度字节编码

详细 Unicode 介绍，参考：Unicode 简介

数的表示与运算

定点数的表示和运算

定点数：表示小数点位置固定，但不需点号（逻辑上有但无需存储）

定点运算简单易实现，但表示范围小、运算精度低，不适合科学运算

定点小数：即纯小数

小数点在符号位之后，有效数值位之前

范围（补码）：[-1, 1- 2^-n]
定点整数：即纯整数

小数点在有效数值之后

范围（补码）：[-2ⁿ, 2^n-1]
定点整数运算
- 算数运算
  
  加法：A+B
  
  减法：A-B = A+(-B)，补码世界中，一个数的相反数只需：取反加 1
  
  乘法：A*B = A + A + …，B 个 A 累加，实际 ALU 使用优化的 乘法器
  
  除法：A/B = [ (A - B) - B] - …，穷减至不够减，实际 ALU 使用优化的 除法器
- 逻辑运算
  
  与、或、非（参与运算的是逻辑值：真、假）
- 按位运算
  
  与、或、异或、取反（参与运算的是数值）
  
  左移、右移（左边补符号位）、无符号右移（左边补 0）
浮点数的表示和运算

浮点数：表示小数点位置不固定，根据需要浮动

任何 R 进制数 N，可表示为： \(N = \pm S \times R^{\pm e}\)

R 表示基值，即进制数，例如：2、8、16
S 表示尾数，N 的有效数字，反映了数的精度

常用补码形式的定点小数表示尾数

尽可能占满尾数，保留更多有效数字
e 表示阶码，小数点的实际位置，反映了表示范围

常用补码形式的定点整数表示阶码

阶码负数，定点尾数的小数点再向左浮动阶码大小的位数

阶码正数，定点尾数的小数点再向右浮动阶码大小的位数

浮点数两种表示法：

前一种方式：高位保存阶码符号位（阶符）

后一种方式：高位保存尾数符号位（数符）

浮点数的运算

运算步骤：
- 对阶，使两个浮点数阶码相等（小阶向大阶对阶）
- 尾数求和/差
- 规格化，把浮点数进行调整，确保尾数部分的最高位始终为 1
- 舍入，规格化尾数精度最大化后还是无法容纳原始精度时，舍去之后的值（包含：截断、横置等策略）
- 判断溢出 ，阶码上溢（异常）；阶码下溢（此时阶码认为是 0）

算数逻辑单元 ALU

ALU 功能：算数运算、逻辑运算、辅助功能（移位、求补）

所有算数运算归结为加法运算，即其他运算都可以转换成加法运算

ALU 结构：

A、B 为运算的操作数，控制信号 K 发出对操作数的运算类型，F 为运算结果输出，运算过程中产生的中间结果、过程数据保存在下面这些特定的寄存器中：

ACC（累加器 Accumulator）,用于存储运算结果的特殊寄存器，算数逻辑操作临时存储
MQ（乘法器寄存器 Multiplier Quotient），用于乘法、除法运算，存储乘法运算的中间结果或商
X（索引寄存器 Index Register），用于存储内存地址的偏移量或索引值以便访问数据结构的元素
PSW （程序状态字 Program Status Word），用于存储有关处理器状态和标志位的信息，如：条件码、中断状态
R₀ ~ Rⁿ（通用寄存器组），可以存储不同类型数据的通用寄存器

串行加法器：具有保存 进位位 的进位触发器，数据逐位送入运算，串行、逐位送回寄存器

并行加法器：将多个全加器串接起来，一次性将操作数的所有位采取组内并行、组间并行计算

存储系统

存储器层次结构

层次结构

高速缓冲存储器

CPU 内部的缓存（L₁ ~ L₃ 缓存），速度极快、容量小

主要用来缓解 CPU 与主存速度不匹配

使用 SRAM 静态随机访问存储，断电丢失数据（Volatile）

主存储器

内存条，CPU 可直接操作的存储器，速度快，容量大，程序运行必须先加载到主存储器

使用 DRAM 动态随机访问存储、SDRAM 同步动态随机访问存储，断电丢失数据

辅助存储器

也称外存，CPU 不直接操作的存储器，速度一般，容量很大

使用 ROM 只读存储器 (仅保留字面意思，其实可读可写)、NV-RAM （稳定随机访问存储器）（Not Volatile）

固定磁盘（硬盘、磁盘、闪存）

可移动存储介质（U 盘、光盘、磁带）

硬盘中有专门的一部分区域当做缓存来缓解与主存的速度不匹配

虚拟内存

操作系统层面从逻辑上扩充内存容量的存储器系统

局部性原理

时间局部性：刚操作的数据短时间内可能还会操作
空间局部性：刚操作的数据附近区域可能会被操作

根据局部性原理，设计出高速缓存、硬盘缓存来提高数据存取速度。

半导体存储器

主存储器模型

CPU 需要读取某地址数据时，将数据的地址放入 MAR（内存地址寄存器）由时序控制器向主存发读控制信号，主存获取地址总线所在位置的数据后，将其放入 MDR （内存数据寄存器）完成读操作。

数据总线
- 存取周期：两次连续存取的最小时间间隔
- 存储器总线宽度：其宽度为数据总线位数，同时也等同于存储字长
- 数据传输率：存储器总线宽度 / 存取周期，即：单位时间内存取二进制信息的位数
- 数据总线是双向的
地址总线
- 存储容量：半导体存储芯片所能存储二进制信息位数（单位：bit）
- 最大可寻址范围：2^k x n （单位：bit），k 地址总线位宽，n 数据总线位宽
- 地址总线是单向的
控制总线

CPU 与系统其他内部件（内存、输入、输出设备）之间传输控制信号的通道
半导体存储器

RAM（Random Access Memory）：随机存取存储器，可随机读写，断电易失
- 静态 Static-RAM：以触发器（flip-flop）存储二进制位（6 个 MOS 管），不刷新可维持存储状态（静态由来）
- 动态 Dynamic-RAM：一个/三个 MOS 管和一个电容存储二进制位，需不断刷新操作给电容补电（动态由来）
- 非易失性 Non-Volatile-RAM：采用 CMOS 管构成的低功耗 SRAM 存储单元，使用铝电池作后备电源
SRAM vs DRAM

DRAM 刷新几种方式：
- 集中刷新：2ms 内安排时间全部刷新（全部刷新，死区时间长）
- 分散刷新：每次读完就刷新（将存取周期加倍，吞吐量降低）
- 异步刷新：每间隔一段时间刷新一行
ROM（Read-Only Memory）：只读存储器，可随机读（现今只保留只读名称，都可以写）非易失性
- 可擦除可编程只读存储器（EPROM）
  - 紫外线擦除（UV-EPROM）
  - 电擦除（E-EPROM）：固态硬盘、闪速存储器
缓存 Cache

基本概念

高速缓存 Cache 是介于 CPU 和主存之间，利用局部性原理来缓解二者速度差异。CPU 可以同时操作缓存与主存，CPU 先访问缓存，若缓存中没有在去主存中获取数据放入缓存。缓存中存放主存部分数据的拷贝，缓存以缓存行或缓存块为基本单位与主存传送数据。

每一个缓存行对应一个缓存行地址，一个缓存行存储多个存储字（一般 64 字节）。缓存行被要求命中率至少 85% 以上，命中率跟缓存大小、缓存组织形式及程序特性相关。

组织结构
- Cache 存储体
  
  缓存存储体存放从主存调入的数据，假设主存的存储字长 1 Byte、分页大小为 1 KB，并以 64 Byte 划分字块，那么一块 64 KB 的内存将被划分成 64 个分页，每个分页 16 个字块，总计 1024 个字块。
  
  而每个缓存行大小同样为 64 Byte, 假设缓存大小为 512 Byte, 那么将包含 8 个缓存行，如上图所示，可以建立一个缓存字块编号（0 ~ 7）映射主存字块编号（0 ~ 1023）的关系。
- 地址转换机构/部件
  
  实现主存地址到缓存地址的转换
  
  目录表：记录地址映射关系
- 替换机构/部件
  
  按照一定策略（算法）进行数据块替换
  
  随机替换 Random：随机确定被替换的块，实现简单，但未遵循局部性原理
  
  先进先出 FIFO：始终选择最早调入 Cache 的块替换，实现简单，但未遵循局部性原理
  
  最近最少使用 LRU：随时记录每个块最近一次使用次数，命中清零，其他未命中都加 1，淘汰次数最大的块
Cache 与主存的映像
- 全相连映像，空位随意放，任意主存字块放到 Cache 任意位置
  
  被占用的缓存行会被记录在一张目录表，该表保存主存块地址、缓存块地址、有效位三个信息，其中有效位标识当前缓存行是否有效，0-无效，1-有效。像这样存放缓存与主存映射信息的缓存称为标识 Cache，而正常存放主存中数据拷贝的缓存行成为内容 Cache。标识 Cache 单独存放在由 CPU 硬件实现的存储结构中，缓存行由多少行，该物理目录表也相应有多少行。
  - 优点：命中率比较高，Cache 存储空间利用率高
  - 缺点：每次访问要与全部目录表中的内容比较，速度低、成本高，实际应用少
- 直接映像，主存分区，对号入座
  
  主存字块只能映射到 Cache 特定的块中。由于主存块号远大于缓存块号，将主块号以缓存大小分区，则每个区包含的块数与 Cache 块一致。分配时，某区某块只能存入 Cache 的相同块号中。由于来自不同分区的相同字块号的数据被分配在相同块号的缓存中，无法区分当前缓存行块号是来自于主存的哪个分区的，所以此时目录表变为保存主存快地址、主存区地址、有效位三个信息，其中主存区地址就用来标识当下块号来自于主存块哪个逻辑分区
  
  此种映射有个前提：主存容量是缓存容量的整数倍
  - 优点：数据访问时，只需检查区号是否相等即可
  - 缺点：替换操作频繁，命中率比较低
- 组相连映像，先分区再分组，组内随意放
  
  与直接映像一样将主存空间按 Cache 大小分区，每个区块数保持与缓存块数一致，然后主存每个区和 Cache 按照相同大小划分成组，则每区组数与 Cache 组数一致。某区某组块只能存入 Cache 中相同组号中，组内随意存放，即：组间直接映像，组内全相连映像。当然主存中不同分区具有很多相同组号，存在无法区分当前缓存行组号的数据来源于主存哪个分区的，所以此时目录表变为保存缓存块地址、主存块地址、主存组地址、主存区地址及有效位，其中主存区地址记录该组号来源于主存哪个分区。
  - 优点：块冲突概率低，块利用率大幅提高，块失效率降低
  - 缺点：实现难度和造价比直接映像方式高

指令系统

指令又称机器指令，指示计算机执行某种操作的命令。指令是机器语言的语句，是一组有意义的二进制代码，它是计算机运行的最小功能单位。

指令格式

一条指令一般由高位的操作码、低位的地址码 两部分组成，有些特殊的指令没有地址码：

操作码：指令要执行什么操作、功能
地址码：给出被操作信息或数据的地址
指令字长：一条指令包含的二进制代码的位数，它与机器字长无关（可能大于、等于、小于机器字长）

指令根据指令字长，可以分成：定长指令、变长指令，操作码之间不重复、不为前缀（哈夫曼编码）。

指定只能有一个操作码，但可以有不同数量的地址码：

零地址：指令不需要操作数，例如：信号指令、专用指令含默认操作数地址
一地址：单操作数/双操作数指令，例如：自增指令、ACC 双操作数但只需一个地址
二地址：目的操作数地址、源操作数地址
三地址：操作数地址 A、操作数地址 B、结果地址
四地址：操作数地址 A、操作数地址 B、结果地址、下条指令地址

指令寻址方式

指令寻址包含两个大类：指令寻址、数据寻址，指令本身也是存在主存中的数据，把取指令的操作叫做指令寻址，取操作数的操作叫做数据寻址。

指令寻址

顺序寻址：通过 PC 自动加 1（1 个指令字长）实现
跳跃寻找：通过转移类指令实现

本条指令给出下条指令的计算方式

本条指令修改 PC 值，由 PC 给出下条指令地址

数据寻址

寻址模式/特征：在地址码高位包含几个比特位（MOD），它包含描述地址的寻址模式和特征。
形式地址 A：地址码不是操作数真实地址，而是指向操作数地址的地址
有效地址 EA：形式地址结合寻址特征，计算出真实地址
数据寻址方式
- 隐含寻址：单地址指令，第二个操作数默认为 ACC (累加器)
- 立即寻址：
  
  形式地址 A，就是操作数本身，因此又称立即数（补码形式）
  
  特征位为 # 字符时，表示立即寻址特征
  
  优点：指令执行阶段不访存，执行时间短
  
  缺点：立即数 A 的位数限制了范围
- 直接寻址：形式地址 A 是操作数的真实地址，EA=A
  
  优点：简单，执行阶段仅需一次访存，不需要计算操作数的地址
  
  缺点：A 的位数决定了该操作数的寻址范围，操作数地址变化引起指定地址修改，编程不便
- 间接寻址：形式地址不是真实地址，而是有效地址所在存储单元地址，即操作数地址的地址，EA=(A)
  
  可以一次间址，也可多次：1开头-地址 0开头-EA
  
  优点：可扩大寻址范围（有效地址 EA 位数大于 A 位数）、便于编程
  
  缺点：要访存多次，访问速度慢
- 寄存器寻址：在指令中直接给出操作数的寄存器编号，EA=Ri
  
  优点：指令执行阶段不访存，只访问寄存器，速度快，支持向量 / 矩阵运算
  
  缺点：寄存器价格昂贵、个数有限
- 寄存器间接寻址：寄存器 Ri 给出操作数主存单元地址，EA=(Ri)
  
  优点：比一般间接寻址速度快
  
  缺点：但指令执行阶段需要访存（操作数在主存中）
- 基址寻址：将基址寄存器 BR（Base Register）内容加上指令中的形式地址 A 得到有效地址，EA=(BR)+A
  
  BR 可采用专用寄存器也可使用通用寄存器，基地址不变（BR 内容），偏移量可变（形式地址）
  
  优点：可扩大寻址范围、用户不必考虑自己程序存于主存哪个区域，利于多道程序、可用于浮动程序
  
  缺点：偏移量（形式地址 A）位数较短
- 变址寻址：有效地址 EA 等于形式地址 A 与变址寄存器 IX（Index Register）之和，EA=(IX) + A
  
  IX 可为专用寄存器，也可是通用寄存器，基地址不变（形式地址），偏移量可变（变址寄存器）
  
  优点：可扩大寻址范围（变址寄存器位数足以表示整个存储空间）
  
  便于处理数组（A 为数组首地址，不断改变 IX 内容，可得数组任意地址）
  
  缺点：基地址（形式地址 A）位数较短
- 相对寻找：把 PC 内容加上形式地址 A 得到操作数有效地址，EA=(PC) + A
  
  A 相对于当前地址的偏移量，可正可负，补码
  
  优点：操作数地址不固定的，随 PC 变化、操作数地址与指定定制相差一个固定值、便于程序浮动、转移指令
  
  缺点：没有明显缺点
- 堆栈寻址：存储器或专用寄存器组中一块特定的存储区（LIFO）
  
  读写地址由特定寄存器给出，该寄存器叫做堆栈指针 SP（Stack Pointer）
  
  适用于堆栈结构计算机，多用无操作数指令，因为操作数地址都隐含使用了 SP
  
  读写前后伴有自动完成对 SP 增量或减量操作
各种寻址对比

中央处理器

CPU 功能

指令控制

取指令、分析指令、执行指令、顺序控制
操作控制

产生操作信号，并将信号送往部件进行动作
时间控制

对各种操作加以时间上的控制
数据加工

CPU 的运算单元对数据进行加工
中断处理

中断不是 CPU 功能，但与 CPU 工作密不可分：进程切换、外设切换、程序发生内核调用时，都会引发中断。

内中断：当前指令引起

外中断：时钟、I/O 引发

CPU 基本结构

运算器

接收并执行从控制器发出的命令，对数据加工和处理。处理数据用到以下部件：
- ALU 算数逻辑单元
- Y、Z 暂存寄存器
- ACC/AC 累加寄存器/累加器
- GPR/GR 通用寄存器
- PSR/PSW 程序状态寄存器
- 移位寄存器/移位器
- 计数寄存器/计数器
单总线结构图：

所有部件通过一组总线传送数据，同一时间，总线上只能有一个操作数，速度慢。

图中 A、B 暂存器是为了解决单总线一次传送一个操作数，那先传送的就必须使用该暂存寄存器临时保存。

双总线结构图：

操作部件连接在两组总线，同时传送数据，运算结果需要利用缓冲暂存，速度快。

虽然双操作数可以分别在两条总线同时读取，但计算的结果输出并不能像单总线直接那样直接放入总线，单总线之所以可以是因为两次读入操作数后，都放入到暂存寄存器，此时总线可被用来接受传输结果数据。双总线时由于去掉了操作数的暂存寄存器，两个总线在计算时都各自保持持有两个输入的操作数，故而不能用来接受操作结果，此时得将结果输出到缓冲寄存器中。

三总线结构图：

三总线设计中，将总线 1、2 用于输入，总线 3 用于输出，相较双总线而言，仅需一步就能完成运算，速度更快，但控制也相对复杂。

此处的总线旁路器的作用是当操作数不需要 ALU 进行运算时，可以直接导通输入总线到输出总线，从而被通用寄存器保存进行后续处理
控制器

指挥中枢，根据指令要求指挥全机协调工作，控制器用到以下部件：
- IR 指令寄存器
  
  存放的是指令，指令经由下面的指令译码器翻译后交由控制信号产生控制信号
- PC 程序计数器
  
  存放当前正在执行的指令的地址，程序运行时通过 PC 将执行地址经由 IBus 内部总线存入 MAR 地址寄存器，然后由 ABus 地址总线传输给内存获得执行地址所存储的指令，指令通过 DBus 数据总线存入 MDR 数据寄存器，最后由 IBus 放入 IR
- ID 指令译码器
  
  ID 将存储在 IR 中的指令进行译码处理，
- MAR 存储器地址寄存器
- MDR（MBR）存储器数据寄存器
- CLOCK 时序系统
  
  时序信号发生器，本质是石英晶体的振荡器
- 微操作信号发生器
  
  在完成一条指令时所有做的每一步骤操作称为微操作
- PSR 程序状态记录器
  
  存放当前程序的工作状态
- 中断控制逻辑
  
  每个中断都有自己的中断处理逻辑
寄存器 CPU 中必须的寄存器：
- IR
- PC
- ACC/AC
  
  暂存寄存器：Y、Z
  
  通用寄存器：GPR/GR：
  
  AX（ACC 通用寄存器）、BX（基址通用寄存器）、CX（计数通用寄存器）、DX（数据通用寄存器）
  
  为了为兼容老的位宽低的 CPU，又将上面的四个寄存器已低位、高位划分为两个，H 为高，L 为底
  
  例如：AH、AL 即为 ACC 的高位寄存器和低位寄存器
- PSR/PSW：根据不同 CPU 架构含不同的比特位，规定每单个或多个位标识程序运行的状态信息
- MAR
- MDR (MBR)
下面是方框内是 Intel 8086/80386 的寄存器：

上图中，包含的段寄存器是给操作系统预留配合地址寄存器给进程分配内存，例如：代码段、数据段、堆栈段等。
单总线 CPU 结构
双总线 CPU 结构

指令执行过程

指令周期

指 CPU 从主存取出并执行完成一条指令的时间

指令周期通常包含若干机器周期

一个机器周期：若干时钟周期/节拍脉冲/T周期

包含四个阶段：
- 取指周期：取指令
- 间址周期：取有效地址
- 执行周期：执行指令
- 中断周期：响应中断
指令执行中的数据流向

取指周期：(PC) -> MAR -> MEM -> MDR -> IR

间址周期：Ad(IR) -> MAR -> MEM -> MDR

执行周期：

中断周期：

发生中断时，先保存当前指令在主存中所在的地址（就是当前 PC 的值，即当前断点），在中断过程完成后恢复断点时，将之前断点（原 PC 的值）从主存中取出放入 PC 继续中断前的逻辑。

（SP 堆栈指针）减 1 -> SP -> MAR ，将中断前 PC 的指令地址 所要存放的主存地址放入 MAR（保存现场）

(PC) -> MDR -> MEM，将 PC 的指令地址 当做数据放入 MDR，之后保存到上一步 MAR 中的主存地址里

向量地址 -> PC, 然后执行中断程序，它的入口地址被称作向量地址，把它放入 PC 中去执行中断逻辑
指令执行方式

顺序执行方式

各指令串行执行，控制简单，执行速度慢，机器效率低

重叠执行方式

指令的执行时间大大缩短，硬件开销大（预读取部件），控制逻辑更加复杂

指令流水方案

把指令执行过程划分成若干复杂度相当，耗时大致相等的子过程，每个子过程由一个独立的部件完成，流水线上各功能部件并行。

衡量流水线性能指标：

吞吐率：单位时间内完成任务量

加速比：同一批任务不使用流水线与使用流水线比

效率：流水线上设备利用率（装入时间、排空时间两个时间利用率不高，其他都很高）

总线

基本概念

是一组能为多个部件分时共享信息的公共传输线路，每条传输线传输一位二进制代码，若干条构成一组总线。

分时：同一时刻只允许一个部件向总线发送信息，多个部件分别在不同时段向总线发送信息

共享：总线上可以挂接多个部件，各个部件都可以通过这组线路交换信息

总线分类

主机之外的总线被称为外部总线，主机内的总线被称为系统总线。

系统总线根据连接各个功能模块信号的含义，被分成数据、地址、控制等功能组

数据总线：传输数据信息（双向总线、位数与机器字长、存储字长有关）

地址总线：指出数据所在的主存单元或 IO 端口的地址（单向总线、位数与主存地址空间大小有关）

控制总线：传输控制信息（CPU 送出的控制命令、主存或外设返回给 CPU 的反馈信号）

总线组成结构

逻辑构成

逻辑信号线：连接各个功能模块
总线控制器：管理总线
- 总线系统的资源分配与管理
- 提供总线定时信号脉冲
- 负责总线使用权的仲裁
- 负责实现不同总线协议的转换和不同总线之间传输数据的缓冲

物理构成

单总线结构：

便于增删 IO 设备、多部件都要占用总线时，发生冲突需要判断优先级
双总线结构：

为解决单总线冲突问题，再拆分出两个总线，这又分：

以 CPU 为核心：便于增删 IO 设备，IO 设备与主存交换信息时，占用 CPU、影响 CPU 效率

以存储器为核心：M总线速度高，减轻系统总线负担，IO 设备与主存交换信息无需经过 CPU，需要的布线空间大
三总线结构：

IO 总线、M总线外，增加 DMA （Direct Memory Accessor）总线，IO 设备可以直接通过 DMA 访问主存，而不经由低效的 IO 总线，提高了 IO 设备的性能，提升系统吞吐量，布线量大

总线传输周期

总线传输周期简称总线周期，表示一次总线操作所需的时间。单次传输周期内，包含以下四个阶段：

申请阶段：总线仲裁阶段

主设备提出申请，并经由仲裁电路授权使用总线的过程
寻址阶段：地址、命令阶段

主设备往总线上发地址信号和命令信号
传输阶段：数据传输阶段

主从设备进行数据交换，可能单向（写）或双向（度）
结束阶段：撤销状态阶段

主从设备撤销总线上的信号，让出总线使用权

总线仲裁

同一时刻，总线只能允许一个功能模块成为主控设备，为了避免多模块争用总线，必须要有总线仲裁电路。

集中仲裁：集中处理总线请求信号，确定主控设备
- 并行仲裁（独立请求方式）
- 串行仲裁（链式查询方式）
优缺点：模块化程度高、电路简单、可靠性差
分布式仲裁：仲裁处理分布在各总线设备中

优缺点：单个总线设备故障，不影响其他设备，电路复杂
并行仲裁（独立请求方式）

总线请求信号线（BR）：设备独立总线

总线允许信号线（BG）：设备独立总线

地址线和数据线：所有设备共享

优点：响应速度快，优先次序灵活（通过程序改变）

缺点：控制线数量多（2n），总线控制复杂

总线操作和定时

为了协调总线上发生的事件（操作），保持正确的时序

同步定时（同步总线）

所有总线事件都与一个时钟脉冲序列（时钟周期）同步

需要一条时钟信号线，传送一个固定频率的方波信号

所有的总线事件都从时钟周期的开始启动动作

异步定时（异步总线）

不需要对齐时钟脉冲，上一个总线事件是否发生，

依赖于前一个事件的执行情况

操作系统

本笔记源于《马士兵教育-MCA课程-计算机操作系统》

概述

基本概念

操作系统：管理计算机硬件与软件资源的计算机程序。
- 计算机系统构成：用户、应用程序、操作系统、硬件（裸机）
  
  操作系统隔离硬件，为应用程序提供统一硬件操作接口、为用户提供图形化、命令等的交互接口
  
  操作系统管理的硬件即裸机，管理的软件即应用程序。
- 系统软件：操作系统是一种系统软件，系统软件具备的功能
  - 与硬件交互
  - 对资源（硬件资源）共享进行调度管理
  - 解决并发操作处理中存在的协调问题
  - 数据结构复杂，外部接口多样化，便于用户反复使用
- 操作系统作为系统软件，主要负责：
  - 管理与配置内存
  - 决定系统资源供需的优先次序
  - 控制输入、输出设备
  - 操作网络与管理文件系统等基本事务
  - 提供一个让用户与系统交互的操作界面
操作系统目标与功能

目标：
- 有效性：提高资源利用率、提高系统吞吐量
- 方便性：方便用户使用
- 可扩充性：作为扩充机器
- 开放性：作为扩充机器
功能：
- 作为计算机系统资源的管理者
  - 处理机管理：进程的控制、进程同步、进程通信、调度
  - 存储器管理：内存分配、内存保护、地址映射、内存扩充
  - I/O 设备管理：缓冲管理、设备分配、设备处理
  - 文件管理：文件储存空间管理、目录管理、文件的读、写管理和保护
- 作为用户与计算机硬件系统之间的接口
  - 程序接口：给应用程序使用
  - 命令接口：给用户操作使用
  - GUI 图形用户接口：给用户操作使用
- 实现对计算机资源的抽象
  - 将具体计算机硬件资源抽象成软件资源，方便用户使用
  - 开放了简单的访问方式，隐藏了实现细节
操作系统特征
- 并发
  
  同一时间间隔内执行和调度多个程序的能力
  - 宏观：处理机同时执行多道程序
  - 微观：处理机在多道程序间高速切换（分时交替执行）
  - 关注单个处理机同一时间段内处理任务数量的能力
  - 与并行的区别：
    
    并行是同一时刻（时间点）发生事件的数量，物理极限明显
    
    并发是同一时间间隔（时间段）发生事件的数量，操作系统着重优化并发能力，来提系统高吞吐量
- 共享
  
  系统中的资源供多个并发执行的应用程序共同使用
  - 同时访问方式：同一时间段允许多个程序同时访问共享资源
  - 互斥共享方式：也叫独占式，允许多个程序在同一个共享资源上独立而互不干扰的工作
  - 常见共享设备：打印机、音频、视频
  - 与并发互为前提：
    
    共享要求 OS 运行多道程序，只存在一个程序就无共享可言
    
    并发则会存在多道程序同时访问一个资源，若资源无法共享，则并发无法实现
- 虚拟
  
  使用某种技术把一个物理实体变成多个逻辑上的对应物
  - 时分复用技术：TDM Time Division Multiplexing
    
    虚拟处理机技术、虚拟设备技术
  - 空分复用技术：SDM Space Division Multiplexing
    
    虚拟磁盘、虚拟存储技术
- 异步
  
  多道程序环境下，允许多个程序并发执行
  
  单处理机环境下，多个程序分时交替执行
  - 程序执行的不可预知性
    
    获得运行的时机、因何暂停、每道程序需要多少时间、不同程序的性能（计算型、I/O型）
  - 宏观上 “一气呵成” 微观上 “走走停停”

发展分类

手工操作->批处理->分时操作->实时操作->微机时代

运行环境

基本概念
- 内核程序 vs 应用程序
  
  操作系统中的非必须程序，称作非内核功能，也保护操作系统上的应用程序，它们运行在用户空间
  
  操作系统中的必须程序，称作内核程序，它们运行在内核空间
- 核心态 vs 用户态
  
  CPU 在执行时有两种状态，运行在用户空间时，称作用户态，运行在内核空间时，称作核心态
  
  CPU 是通过 程序状态字 PSW 的状态标识位控制，用户态时标识为 1，核心态时标识为 0
- 特权指令 vs 非特权指令
  
  CPU 在执行核心态时所执行的指令称作特权指令，执行用户态时所执行的指令称作非特权态指令
时钟管理
- 计时：提供系统时间
- 时钟中断：比如进程切换
中断机制
- 提高多道程序环境下 CPU 利用率
  
  多道程序时，某个程序等待 I/O 时，可以中断后执行其他程序
- 外中断：中断信号来源于外部设备
- 内中断：中断信号来源于当前指令，其又分三种情况：
  - 陷阱/陷入（Trap）：由应用程序主动引发（应用程序发生内核调用时，CPU 产生 陷入（防管）指令）
  - 故障（Fault）：由错误条件引发（例如：内存缺页故障，CPU 产生 故障中断）
  - 终止（Abort）：由致命错误引发
- 中断处理过程
  1. 关中断（CPU 不响应高级中断请求，由硬件中断隐指令实现）
  2. 保存断点（保存 PC 程序计数器）
  3. 引出中断服务程序（读取中断程序所在内存地址）
  4. 保存现场和屏蔽字（保存 CPU 中各种寄存器信息）
  5. 开中断（CPU 开启并发响应高级中断请求）
  6. 执行中断服务程序（没一种中断都对应一个中断服务程序）
  7. 关中断
  8. 恢复现场和屏蔽字
  9. 开中断
原语
- 由若干条指令组成（程序段）
- 用来完成某个特定功能
- 执行过程中不会被中断（原子性，底层就是由关中断与开中断实现）
系统数据结构（一般只涉及对数据结构的操作不涉及硬件）
- 进程管理：作业控制块、进程控制块
- 存储器管理：存储器分配与回收
- 设备管理：缓冲区、设备控制块
系统调用（系统调用的处理运行在核心态，但系统调用的陷入指令是在用户态执行）
- 由操作系统实现，给应用程序调用
- 是一套接口的集合
- 应用程序访问内核服务的方式

体系机构

传统操作系统结构（大内核）
- 一代：无结构 OS
  - 一系列过程（程序）集合
  - 过程间可相互调用，
  - 结构复杂、混乱，难维护
- 二代：模块化结构 OS
  - 基于“分解”和“模块化”的原则
  - 按照功能划分模块/子模块，规定模块间的接口
  - 独立性标准：高内聚、低耦合
  - 优点：提高 OS 设计的正确性、可理解性和可维护性、增强适应性、加速开发
  - 缺点：模块接口设计难以扩展后续需求、模块设计没有统一决策标准、导致模块接口设计不可靠
- 三代：分层式结构 OS
  - 有序分层法，自顶向下依次依赖
  - 设计时，自底向上：每一步建立在可靠的基础上
  - 优缺点：容易保证系统正确性、容易扩充和维护、自上而下的层次通信，导致系统效率降低
微内核结构
- 概念：
  - 足够小的内核，只实现 OS 核心功能与硬件处理紧密相关的部分，比如硬件处理、
    
    客户与服务器通信和其他基本功能。
  - 采用“机制与策略分离”原理
  - 采用面向对象技术
- 优点：提高 OS 的可扩展性、可靠性、可移植性、支持分布式系统、融入了面向对象的技术
- 缺点：相较早期 OS，降低了一定的效率

进程管理

什么是进程

概念

进程是一个具有独立功能的程序关于某个数据集合的一次运行活动，是系统进行资源分配和调度的一个独立单位。

进程是程序的一次执行
进程是一个程序及其数据在处理机上顺序执行时所发生的活动
进程是程序在一个数据集合上运行的过程
进程是系统进行资源分配和调度的一个独立（基本）单位

结构

控制块（PCB）：进程唯一标识
数据段：存放原始数据、中间数据
程序段：存放在文本区域，可被多个进程共享

特征

结构特征：
- 控制块 PCB：OS 根据此对进程进行控制管理，进程创建、撤销都是根据此来进行
  
  它存储：程序计数器、进程状态、CPU 暂存器等信息，
- 数据段：在数据区域，存储全局和静态变量和进程运行期间使用的动态分配的内存
  
  在堆栈区域，存储活动过程调用的指令和本地变量
- 程序段：存放在文本区域，存储处理器执行的代码，二进制格式，程序段可被多个进程共享
动态性：由创建而生，由撤销而亡
并发性：多个进程同时运行
独立性：独立资源分配
异步性：相互独立、互不干扰

线程

进程的轻型实体，也叫 “轻量级进程”，是一系列活动按事先设定好的顺序依次执行的过程，是一系列指令的集合
是一条执行路径，不能单独存在，必须包含在进程中
线程是 OS 中运算调度的最小单位
线程提高 OS 的并发性
线程属性
- 轻型实体
- 独立调度和分派的基本单位
- 可并发执行
- 共享进程资源

进程 vs 线程

调度：线程为最小调度单位，同进程中线程的切换不会引起进程的调度
拥有资源：进程拥有资源，线程是向进程申请
并发性：进程提高 OS 并发性，线程进一步提高 OS 并发性
系统开销：创建撤销进程开销大，线程的切换相对开销小
地址空间和其他资源：同一个进程中的线程共享当前进程的所有内存空间
通信：进程间通信相对线程间通信开销更大

线程的实现方式

用户级线程（ULT）：线程控制块在用户空间
内核级线程（KLT）：线程控制块在内核空间

进程是怎么运行的

进程的状态

进程的生命周期：从创建到终止的过程

创建 New：创建进程的结构，PCB、程序段、数据段
就绪 Ready：可运行未运行
执行 Running：调度获得 CPU 资源，执行
阻塞 Blocked：让出 CPU 资源
终止 Terminated：

进程的控制

进程控制是 OS 对进程实现有效的管理，包括创建、撤销、挂起、阻塞、唤醒和切换进程等多种操作。OS 通过原语（Primitive）操作实现进程控制。

原语：由若干指令组成，完成特定的功能，是一种原子操作。原子操作执行过程不会被中断，在管态（内核态）下执行，它常驻内存，是内核三大支持功能（中断、时钟管理、原语操作）之一。进程控制相关的原语：

创建原语 create：用户登录、作业调度、提供服务、应用请求等操作可以激发此原语执行
阻塞原语 block：请求某种服务、启动某种操作数据未到达五工作可做时激发此原语执行
唤醒原语 wakeup
撤销原语 destroy：正常结束、异常结束、外界干预可激发此原语执行
挂起原语 suspend：为了系统和用户观察和分析进程
- 静止就绪：进程从活动就绪状态转为静止就绪，放外存，不调度
- 静止阻塞：进程从活动阻塞状态转为静止阻塞，放外存，等待时间
激活原语 active：与挂起原语相反，让进程从静止变为活动
- 活动就绪：等待调度
- 活动阻塞：等待唤醒

进程切换，处理机从一个正在运行的进程上切换到另一个进程去执行

进程调度

进程调度即处理机调度，进程是被处理机调度。处理机根据一定算法和原则将处理机资源进行重新分配的过程。

前提：作业/进程数远远大于处理机数
目的：提高资源利用率，减少处理机空闲时间
调度程序：满足特定系统用户的需求（快速响应），考虑系统整体效率（系统平均周转时间）和调度算法本身的开销
调度层次
- 高级调度/作业调度（将磁盘应用程序转换成内存中的进程）
  - 把后背作业调入内存
  - 只调入一次，调出一次
- 中级调度/内存调度
  - 将进程调至外存，条件合适再调入内存
  - 在内、外存对换区进行进程兑换
- 低级调度/进程调度
  - 从就绪队列选取进程分配给处理机
  - 最基本的调度，频率非常高（相当于一个时间片完成）
调度方式
- 剥夺式/抢占式调度
  - 立即暂停当前进程
  - 分配处理机给另一个进程
  - 原则：优先权、短进程优先、时间片原则
- 非剥夺/非抢占调度
  - 若有进程请求执行，等待直到当前进程完成或阻塞
  - 缺点：适用于批处理系统，不适用分时、实时系统
调度时机
- 进程运行完毕
- 进程时间片用完
- 进程要求 I/O 操作
- 执行某种原语操作
- 高优先级进程申请运行
调度过程
1. 保存镜像：记录进程现场信息
2. 调度算法：确定分配处理机的原则
3. 进程切换：分配处理机给其他进程
  1. 检查是否允许上下文切换，可能某进程处于原语操作中
  2. 保存当前进程上下文、包括程序计数器、寄存器
  3. 更新 PCB 信息
  4. 将此进程的 PCB 移入队列（就绪队列、阻塞队列）
  5. 选择另一个就绪状态进程执行，更新 PCB
  6. 更新内存管理的数据结构
  7. 恢复所选进程的上下文，将 CPU 执行权交给所选进程
4. 处理机回收：从进程收回处理机
调度算法指标
- CPU 利用率：忙碌时间/总时间
- 系统吞吐量：完成作业数/总时间
- 周转时间：作业完成时间-提交时间
  - 带权周转时间：周转时间/实际运行时间
- 等待时间：作业等待处理机调度时间
  - 关注平均值
- 响应时间：提交请求到首次响应间隔
典型调度算法
- 作业调度（高级、中级调度）
  - 先来先服务 FCFS（First Come First Served）
    - 有利于 CPU 繁忙型作业，充分利用 CPU 资源，
    - 不利于 I/O 繁忙型作业，操作耗时，其他饥饿
  - 短作业优先 SJF（Shortest Job First）
    - 平均等待、周转时间最少
    - 长作业周转时间会增加或饥饿
    - 估计时间不准确，不能保证紧迫任务及时处理
  - 高响应比优先调度 HRRN（Highest Response Ratio Next）
    - 响应比=（等待时间+服务时间）/ 服务时间 ≥ 1
    - 只有当前进程放弃执行权（完成、阻塞）时，重新计算所有进程响应比
    - 长作业等待越久响应比越高，更容易获得处理机
  - 优先级调度 PSA（Priority Scheduling Algorithm）
    - 静态、动态优先级
    - 系统>用户；交互型>非交互型；I/O 型>计算型
    - 低优先级进程可能产生饥饿
- 进程调度（低级调度）
  - 时间片轮转调度 RR（Round-Robin）
    
    按进程到达就绪队列的顺序，轮流分配一个时间片去执行，时间用完则剥夺
    - 公平、响应快，适用于分时系统
    - 时间片决定因素：系统响应时间、就绪队列进程数、系统处理能力
    - 时间片太大，相当于 FCFS，太小，处理机切换频繁，开销增大
  - 多级反馈队列调度 MFQ（Multileveled Feedback Queue）
    
    设置多个按优先级排序的就绪队列，优先级从高到低，时间片从小到大。新进程采用队列降级法：
    - 进入第一级队列，按 FCFS 分布时间片（由于优先级高、时间片小，高响应）
    - 没有执行完，移到第二级、第三级
    当前面队列不为空，不执行后续队列进程。
    
    优缺点：
    - 对各类型相对公平、快速响应
    - 终端型作用用户：短作业优先
    - 批处理作用用户：周转时间短
    - 长批处理作业用户：在前几个队列部分执行

进程之间协作

进程通信

进程通信即进程间的信息交换。进程是资源分配的基本单位，各个进程内存空间彼此独立，一个进程不能随意访问其它进程的地址空间。

通信方式
- 共享存储 Shared Memory
  - 共享数据结构
    
    由 OS 创建一个数据结构，多个进程共用该结构，程序员负责同步处理。它可以传递少量数据，效率低。
    
    属于低级通信
  - 共享存储区
    
    多个进程共用内存中的一块存储区域，由进程控制数据的形式和方式，可以传递大量数据，效率高
    
    属于高级通信
- 消息传递 Message Passing
  - 直接通信，点到点发送
    
    发送、接收时，指明双方的进程 ID，每个进程维护一个消息缓冲队列
  - 间接通信，广播信箱
    
    以信箱为媒介，作为中间实体，发进程将消息发送到信息，收进程从信箱读取
    
    可以广播，容易建立双向通信链
- 管道通信 Pipe
  - 管道
    
    用于连接读、写的共享文件 pipe 文件，本质是内存中固定大小的缓冲区
    
    半双工通信，同一时间段只能单向通信，双工通信需要两个管道
    
    以先进先出方式组织数据传输
    
    通过系统调用 read()、write() 函数进行读写操作
    
    未满不读、已满不写、未空不写、已空不读、读后删除

进程同步

协调进程间的相互制约关系，使它们按照预期的方式执行的过程。需要进行进程同步的前提是：

进程是并发执行的，进程间存在着相互制约关系

相互制约两种形式：

间接相互制约关系（互斥）：进程排他性地访问共享资源

直接相互制约关系（同步）：进程间的合作，比如管道通信
并发的进程对系统共享资源进行竞争
进程间通信，过程中相互发送信号称为消息或事件

互斥方式访问临界资源，具体访问过程：

进入区：尝试进入临界区，成功则加锁 lock
临界区：访问共享资源
退出区：解锁 unlock，唤醒其他阻塞进程
剩余区：其他代码

互斥方式访问临界资源，访问原则：

空闲让进：临界区空闲，允许一个进程进入
忙则等待：临界区已有进程，其他进程等待（阻塞状态）
有限等待：处于等待的进程，等待时间有限
让权等待：等到时应该让出 CPU 执行权，防止“忙等待”

互斥方式访问临界资源，实现方法

软件实现方法
- 单标志法：违背空闲让进
- 双标志法先检查：违背忙则等待
- 双标志法后检查：违背空闲让进、有限等待
- 皮特森算法：违背让权等待、会发生忙等
硬件实现方法
- 中断屏蔽方法：不适用多处理机、只适用内核进程
- TestAndSet （TS指令、TSL指令）：违背让权等待，会忙等
- Swap 指令（XCHG指令）：交换两个变量值，是原子操作，违背让权等待
信号量

信号量基于 PV 操作，P 操作（wait 原语，进程等待）V 操作（signal 原语，唤醒等待进程）

整形信号量：违背让权等待，会发生忙等

记录型信号量：进程进入阻塞状态，不会忙等
管程（Monitor 监视器）

管程，即用于实现进程同步的工具，它由代表共享资源的数据结构和一组过程组成的管理程序。

特征：
- 模块化的基本程序单位，可单独编译
- 抽象数据类型，包含数据和操作
- 信息掩蔽，共享数据只能被管程内的过程访问
条件变量、条件对象
- 进入管程由于条件不满足导致阻塞被移入条件队列
- 条件队列可有很多个

如何处理死锁

概念

多进程由于竞争资源而造成阻塞现象，若无外力作用，这些进程将无法继续推进。

等待时间过长以致于给进程推进和响应带来明显影响的现象为饥饿。

死锁产生原因：系统资源的竞争、进程推进顺序非法

死锁产生必要条件：

互斥条件：共享资源的排他性访问
不剥夺条件：访问共享资源不会被剥夺
请求并保持条件：保持当前资源时请求另一个资源
循环等待条件：存在共享资源的循环等待链

死锁处理策略

破坏死锁产生的必要条件，既可预防死锁的产生。

破坏互斥条件

将互斥访问改为同时共享访问，独占锁改为共享锁，但不是所有资源都可以改成共享的
破坏不可剥夺、不可抢占条件

请求新资源无法满足时必须释放已有资源，由 OS 协助强制剥夺某进程持有的资源，实现复杂、代价高
破坏请求并保持条件

开始时一次性申请所有需要资源，资源浪费、进程饥饿

阶段性请求和释放资源
破坏循环等待

对所有资源排序，按序号请求资源，资源编号需稳定限制了新增资源，进程使用资源的顺序可能与资源编号不同

死锁的避免，与死锁预防不同，死锁的避免指的是在程序运行中，使用安全算法使系统处于安全状态。所谓的系统安全状态是指一定不会出现死锁，不安全状态可能出现死锁。

银行家算法 是被用来确保系统处于安全状态的典型算法，具体算法逻辑：

系统预判进程请求是否导致不安全状态
是则拒绝请求，否则答应请求

死锁检测：需要一种数据结构，保存有关资源的请求与分配信息，提供一种算法，利用这些信息检测是否形成死锁。

资源分配图（G=(N, E)）
- 两种资源
- 两种节点
死锁定理（死锁状态的充分条件）
- 当且仅当此状态下资源分配图是不可完全简化
- 简化过程类似拓扑排序算法

死锁解除：

资源剥夺：挂起死锁进程、剥夺其资源、将资源分配给其它死锁进程
撤销进程
进程回退：回退到足以避免死锁的地步，需要记录进程历史信息，设置还原点

内存管理

物理内存管理

连续分配

单一连续分配
- 实现简单，无外部碎片，不一定需要内存保护
- 只能用于单用户、单任务 OS；有内部碎片；存储器利用率低
固定分区分配
- 分区说明表，记录各个分区分配和回收状态
- 实现简单，无外部碎片
- 较大用户程序时，需要采用覆盖技术，降低了性能
- 会产生内部碎片，利用率低
动态分区分配
- 利用空闲分区表记录内存使用情况
- 新进程分配分区算法
  - 首次适应算法：从低地址查找合适空间
  - 最佳适应算法：优先使用最小空闲空间
  - 最坏适应算法：优先使用最大连续空间
  - 临近适应算法：从上次查找处向后查找

非连续分配

基本分页存储管理方式

将内存分为大小相等的分区：页框（页帧、内存块、物理块），OS 以页框为基本单位分配内存

在进程的 PCB 中以页表的格式记录逻辑地址与物理内存的对应关系

基本地址变换机构：物理地址 = （页号->块号）+ 偏移量

利用 CPU 高速缓存的快表加速页表的转换速度（局部性原理）

两级页表：页表项分组/分页离散存储，建立目录表管理离散页表
基本分段存储管理方式

将用户进程的逻辑地址分成段，每个段大小不确定，每个段以 0 为起始地址

这样进程中的子模块、子进程可以持有自身独立的一段内存空间

段表提供段长、基地址

地址转换机构

段的共享与保护
段页式管理方式

先分段后分页，1 个进程对应 1 个段表， 1 个段表项对应 1 个页表， 1 个页表对应多个物理块

虚拟内存管理

概念

具有请求调入和置换功能，从逻辑上对内存容量加以扩充的一种存储器系统。虚拟内存包含内存、外存。

请求分页管理方式

请求分页管理方式
- 页表机制
  
  页号：
  
  内存块号：
  
  状态位：表示当前内存是否调入内存
  
  访问字段：记录一段时间内被访问次数
  
  修改位：是否修改
  
  外存地址：块号在外存中的地址
- 缺页中断机构
  
  需要访问的内存块不在内存，发生缺页中断，调入内存
  
  页面置换算法淘汰页面，也由缺页中断机制
  
  页面置换：用来解决调入时发生内存不够用时，将不需的页面调出到外存
- 地址变换机构
  
  请求调页，判断是否在内存
  
  可能需要页面置换
  
  新增、修改页表项
  
  热点表项同步到快表

页面置换算法

OPT 最佳置换算法：每次淘汰最不可能再次被使用的页面，保证最低缺页率
LRU 最近最久算法：每次淘汰最久最近未使用页面，保障时间和距离上的公平
FIFO 先进线程算法：保障顺序上的公平，缺页率变大（Belady 异常），性能差
NRU 时钟置换算法：为页面设置访问位，并链接成循环队列，进程访问页面后置为 1 淘汰时置 0 淘汰
改进型时钟置换算法：额外考虑是否修改，保证最少 I/O 操作

增加修改位，第一轮找 (0, 0) 第二轮找 (0,1) 并修改访问位为 0，第三轮找（0,0）第四轮找（0,1）

尽可能保留访问位为 1 的页面，尽可能淘汰访问位为 0 的页面

页面分配策略

该策略要解决给进程分配多大的内存空间，分多少页，分多分少，何时分

驻留集：驻留在主存中页面数

分配空间小，进程数量多，CPU 时间利用率就高
进程在主存中页数少，错页率就高
进程在主存页数多，错页率并无明显改善

分配策略

固定分配局部置换
可变分配全局置换
可变分配局部置换

调入页面时机

预调页策略

一次性调入若干相邻页面，多用于进程首次调入
请求调页策略

运行时发现缺页时调入，I/O 开销大

从何处调页

系统拥有足够的对换区空间
系统缺少足够的对换区空间
UNIX 方式

文件管理

概念

定义：以计算机硬盘为载体的存储在计算机上的信息集合。
属性：描述文件状态的一组信息，比如：名称、标识符、类型、大小、位置等
基本操作：创建、读、写、重定位等

逻辑结构

无结构文件（流式文件）：以字节为单位、没有具体结构、采用穷举方式搜索
有结构文件（记录式文件）：
- 顺序文件
- 索引文件
- 索引顺序文件
- 直接文件或散列文件

目录结构

文件控制块 FCB
- 基本信息
- 存取控制信息
- 使用信息
索引节点
目录结构

文件共享

硬链接（索引节点）
软连接（符号链）

文件保护

口令保护：将索引节点使用口令保护
加密保护：将文件内容加密
访问控制：针对用户进行操作权限控制

文件系统层次结构

用户调用接口
文件目录系统
存取控制验证模块
逻辑文件系统与文件信息缓冲区
物理文件系统
辅助分配模块
设备管理程序模块

目录的实现

线性列表
哈希表

文件分配方式

连续分配
链接分配
索引分配

文件存储空间管理

空闲表法
空闲链表法
成组链接法
位示图法

I/O 管理

概念

输入输出，将数据输入到计算机，或接收计算机数据输出到外部设备

分类

按使用特性
- 人机交互类外部设备
- 存储设备
- 网络通信设备
按传输速率
- 低速设备
- 中速设备
- 高速设备
按信息交换单位
- 块设备
- 字符设备

I/O 设备由机械部件、电子部件构成：

机械部件：比如键盘、鼠标的按键和按钮，用来执行 I/O 操作
电子部件：I/O 控制器、设备控制器，是 CPU 与硬件设备之间的桥梁

I/O 控制器

作用

接收并识别 CPU 命令
向 CPU 报告设备状态
数据转换
地址识别

组成

CPU 与控制器间的接口
I/O 逻辑
控制器与设备间的接口

I/O 控制方式

程序直接控制方式

CPU 频繁干预、每次读写一个字节

读：设备 -> CPU -> 内存
中断驱动方式

解决 CPU 忙等，CPU 将此 I/O 进程阻塞

每次读写一个字节

读：设备 -> CPU -> 内存
DMA 方式

传输单位是块，块之间传输需要 CPU 干预

设备 <-> 内存，无需 CPU 干预

缺点：离散块需要频繁中断
通道控制方式

通道是专门负责 I/O 的处理机

每次读写一组数据块

设备 <-> 内存

I/O 软件层次结构

用户层软件

实现用户交互接口，通过库函数实现系统调用

设备独立性软件

向上一层提供调用接口、设备保护、容错处理、设备分配与回收

数据缓冲区管理、逻辑设备与物理设备映射

设备驱动程序

不同设备硬件特性不同，但 CPU 指令相同，负责控制硬件设备，将 CPU 指令转成设备操作

驱动程序会以独立进程的形式存在

中断处理程序

I/O 完成后发出中断信号，执行中断处理程序，会直接操作硬件

硬件

SPOOLing 技术（假脱机技术）

模拟脱机，加速输入、输出效率

设备分配与回收

设备分配应考虑的因素
静态分配与动态分配
设备管理中的数据结构
- 通道控制表 CHCT
- 控制器控制表 COCT
- 设备控制表 DCT
- 系统设备表 SDT
设备分配步骤

根据物理设备名查 SDT

查 DCT, 尝试分配给进程

查 COCT, 尝试分配给进程

查询 CHCT, 尝试分配给进程

缓冲区管理

为缓解 CPU 与 I/O 设备间速度不匹配的矛盾而建立的临时存储区域

单缓冲
双缓存
循环缓冲
缓存池

计算机网络

网络分层模型

OSI 七层
- 应用层
- 表示层
- 会话层
- 传输层
- 网络层
- 数据链路层
- 物理层
TCP/IP 四层
- 应用层
  
  常见协议：HTTP、SMTP、POP3/IMAP、FTP、Telnet、SSH、RTP、DNS
- 传输层
  
  常见协议：TCP、UDP
- 网络层
  
  常见协议：IP、ARP、NAT、ICMP、OSPF、RIP、BGP
- 网络接口层

HTTP

端口：默认 80

状态码

1xx 信息性状态码
2xx 成功状态码
3xx 重定向状态码
4xx 客户端错误状态码
5xx 服务器错误状态码

常见请求头

略

HTTP vs HTTPS

端口号：HTTP 80 HTTPS 443
协议前缀：http:// https://
安全性和资源消耗：
- HTTP 运行在 TCP 上，明文传输，无状态
- HTTPS 运行在 SSL/TLS 上的 HTTP 协议，SSL/TLS 运行在 TCP 上，加密传输

HTTP/1.0 vs HTTP/1.1

后者比前者增加了更多的状态码
缓存处理
- 1.0 通过 Expires、Last-Modified、If-Modified-Since 配合实现
- 1.1 新增 Cache-Control
连接方式
- 1.0 默认短连接，每次 HTTP 操作都需建立新连接
- 1.1 默认长连接，初次连接后不会关闭，后续请求都在此连接上进行通信
Host 头处理
- 1.0 没有此请求头，没有考虑多主机名绑定同一 IP 地址
- 1.1 添加此请求头，可以给多主机名的服务器指明想访问的具体是哪个主机名
带宽优化
- 1.1 支持 Range 头部请求文件的一部分内容
- 响应状态码 100 指示请求是否会被正常响应
压缩
- 1.0 不支持压缩细节选择，无法区分端到端压缩或逐跳压缩
- 1.1 对内容编码和传输编码做了区分，内容编码是端到端，传输编码是逐跳的

HTTP/1.1 vs HTTP/2.0

2.0 在同一连接上可以同时传输多个请求和响应，互不干扰，1.1 只能在同长连接上串行请求
2.0 使用二进制帧进行数据传输，1.1 使用文本格式报文
2.0 支持头部压缩 HPACK 算法，1.1 仅支持 Body 压缩
2.0 支持服务器推送，可以在客户端请求一个资源时，将其他相关资源一并推送给客户端

HTTP/2.0 vs HTTP/3.0

传输协议：2.0 TCP 3.0 QUIC (Quick UDP Internet Connections) 协议来实现可靠的传输，安全性与 TLS/SSL 相当，具备较低的连接和传输延迟。该协议可以看做是 UDP 的升级版本，新增了加密、重传等机制
建立连接：

2.0 需要三次握手（HTTS 还要额外 TLS 握手，总共 3 RTT）

3.0 的 QUIC 协议特性（TLS 1.3 总共 0 或 1 RTT）
队头阻塞：

2.0 多请求复用时，发生丢包将会阻塞所有 HTTP 请求

3.0 在一定程度上解决了队头阻塞问题，本质是多路复用+轮询
错误恢复：

2.0 依赖 TCP 的错误恢复机制

3.0 具备更好的错误恢复机制，可以更快地恢复和重传
安全性

2.0 使用 TLS 协议加密

3.0 QUIC 协议包含了内置的加密与身份验证机制

HTTP 无状态协议如何保存用户状态

Cookie
利用服务端 Session 机制
JWT

Cookie vs Session

前者是保存在客户端，后者保存在服务端

WebSocket

WebSocket 是一种基于 TCP 连接的全双工通信协议，即客户端和服务器可以同时发送和接收数据。

WebSocket 不只能在基于浏览器的应用程序中使用，很多编程语言、框架和服务器都提供了 WebSocket 支持。

WebSocket 协议本质上是应用层的协议，用于弥补 HTTP 协议在持久通信能力上的不足。客户端和服务器仅需一次握手，两者之间就直接可以创建持久性的连接，并进行双向数据传输。

应用场景
- 视频弹幕
- 实时消息推送
- 实时游戏对战
- 多用户协同编辑
- 社交聊天
与 HTTP 区别
- 双向实时通信协议，HTTP 是单向通信协议且只能由客户端发起
- 协议前缀 ws://、wss:// ，HTTP 前缀 http:// 、https://
- 可支持扩展协议，实现部分自定义子协议，HTTP 不行
- 通信数据格式化比较轻量，协议包头部相对较小
工作过程
- 客户端向服务器发送 HTTP 请求，头部包含 Upgrade:websocket 和 Sec-WebSocket-Key 等字段
- 服务端收到请求后，会进行升级协议操作，如果支持 WebSocket 它将回复一个 HTTP 101 状态码，响应头包含 Connection: Upgrade 和 Sec-WebSocket-Accept:xxx 等字段，表示成功升级到 WebSocket 协议
- 客户端与服务器之间建立一个 WebSocket 连接，可以进行双向的数据传输。数据以帧的形式进行传送，接收端接收消息帧，并将关联的帧重新组装成为完整的消息。
- 客户端或服务器可以主动发送一个关闭帧，表示要断开连接，另一方收到后，也会回复一个关闭帧，然后关闭 TCP 连接。此外，连接建立好，通过心跳机制来保持 WebSocket 连接的稳定性和活跃性。
与 SSE 区别
- SSE 基于 HTTP，WebSocket 需要支持该协议的服务器来处理协议
- SSE 单向通信，只由服务端向客户端通信；WebSocket 全双工通信，即双方可收发
- SSE 实现简单成本低、支持断线重连；WebSocket 需做二次解析，断线重连要自己实现
- SSE 只支持文本消息，二进制需编码后传送；WebSocket 默认支持二进制数据

PING

ping -c 4 www.baidu.com
PING www.a.shifen.com (183.2.172.42): 56 data bytes
64 bytes from 183.2.172.42: icmp_seq=0 ttl=52 time=14.485 ms
64 bytes from 183.2.172.42: icmp_seq=1 ttl=52 time=15.431 ms
64 bytes from 183.2.172.42: icmp_seq=2 ttl=52 time=15.842 ms
64 bytes from 183.2.172.42: icmp_seq=3 ttl=52 time=14.980 ms

--- www.a.shifen.com ping statistics ---
4 packets transmitted, 4 packets received, 0.0% packet loss
round-trip min/avg/max/stddev = 14.485/15.184/15.842/0.506 ms

ICMP Echo Request（请求报文）信息：序列号、TTL（Time to Live）值。
目标主机的域名或 IP 地址：输出结果的第一行。
往返时间（RTT，Round-Trip Time）：从发送 ICMP Echo Request（请求报文）到接收到 ICMP Echo Reply（响应报文）的总时间，用来衡量网络连接的延迟。
统计结果（Statistics）：包括发送的 ICMP 请求数据包数量、接收到的 ICMP 响应数据包数量、丢包率、往返时间（RTT）的最小、平均、最大和标准偏差值。
Ping 基于 ICMP (Internet Control Message Protocol 互联网控制报文协议)，通过在网络上发送和接收 ICMP 报文
ICMP 报文类型
- 查询报文：向目标主机发送并期望得到响应
- 差错报文：向源主机发送错误信息，用于报告网络中的错误情况

DNS

DNS 是应用层协议，它可以在 UDP 或 TCP 协议之上运行，端口为 53。DNS 包含以下类别：

根 DNS 服务器，13 组根服务器，提供 TLD 服务器的 IP 地址
顶级域 DNS 服务器（TLD），顶级域指域名后缀，如：com、org 等，提供权威 DNS 服务器的 IP 地址
权威 DNS 服务器，在因特网上具有公共可访问主机的每个组织机构必须提供公共可访问的 DNS 记录

这些记录将这些主机的名字映射为 IP 地址
本地 DNS 服务器，每个 ISP 都有一个自己的本地 DNS 服务器，当主机发出 DNS 请求时，该请求被发往

本地 DNS 服务器，它起代理作用，并将请求转发到 DNS 层次结构中

两种查询方式

迭代
递归
DNS 记录

DNS 服务器需要查询自己的数据库，数据库中的条目被称作资源记录 RR，它包含 name、value、type、TTL 四个字段的四元组，不同的 type对应不同的的 name、value。常见的类型：
- A，表示 IPv4 地址类型，name 为主机名，value 为 IPv4 主机地址
- AAAA，表示 IPv6 地址类型，name 为主机名，value 为 IPv6 主机地址
- CNAME，表示真实名称记录类型，name 为主机名，value 为主机对应的规范主机名
- NS，表示域名服务器记录类型，name为主机名，value 为知道解析这个主机名的权威 DNS 服务器主机名
- MX，表示邮件服务器记录类型，name 为主机名, value 为该主机名对应的邮件服务器规范主机名

dig 命令可以显示曾哥查询过程

dig www.github.com
    
; <<>> DiG 9.10.6 <<>> www.github.com
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 35968
;; flags: qr rd ra; QUERY: 1, ANSWER: 2, AUTHORITY: 8, ADDITIONAL: 11
    
;; QUESTION SECTION:
;www.github.com.			IN	A
    
;; ANSWER SECTION:
www.github.com.		600	IN	CNAME	github.com.
github.com.		600	IN	A	20.205.243.166
    
;; AUTHORITY SECTION:
github.com.		411	IN	NS	dns4.p08.nsone.net.
github.com.		411	IN	NS	dns1.p08.nsone.net.
github.com.		411	IN	NS	ns-1283.awsdns-32.org.
github.com.		411	IN	NS	dns3.p08.nsone.net.
github.com.		411	IN	NS	ns-421.awsdns-52.com.
github.com.		411	IN	NS	ns-520.awsdns-01.net.
github.com.		411	IN	NS	ns-1707.awsdns-21.co.uk.
github.com.		411	IN	NS	dns2.p08.nsone.net.
    
;; ADDITIONAL SECTION:
dns1.p08.nsone.net.	239	IN	A	198.51.44.8
dns2.p08.nsone.net.	492	IN	A	198.51.45.8
dns3.p08.nsone.net.	510	IN	A	198.51.44.72
dns4.p08.nsone.net.	143	IN	A	198.51.45.72
ns-1283.awsdns-32.org.	233	IN	A	205.251.197.3
ns-1707.awsdns-21.co.uk. 239	IN	A	205.251.198.171
ns-421.awsdns-52.com.	488	IN	A	205.251.193.165
ns-520.awsdns-01.net.	49	IN	A	205.251.194.8
dns1.p08.nsone.net.	239	IN	AAAA	2620:4d:4000:6259:7:8:0:1
dns2.p08.nsone.net.	492	IN	AAAA	2a00:edc0:6259:7:8::2
dns3.p08.nsone.net.	510	IN	AAAA	2620:4d:4000:6259:7:8:0:3
    
;; Query time: 53 msec
;; SERVER: 223.5.5.5#53(223.5.5.5)
;; WHEN: Fri Apr 19 10:38:47 CST 2024
;; MSG SIZE  rcvd: 497

TCP 与 UDP

	TCP	UDP
是否面向连接	是	否
是否可靠	是	否
是否有状态	是	否
传输效率	较慢	较快
传输形式	字节流	数据报文段
首部开销	20 ～ 60 bytes	8 bytes
是否提供广播或多播服务	否	是

运行在 TCP 上的协议
- HTTP（HTTP/3.0 之前）
- HTTPS
- FTP
- SMTP
- POP3/IMAP
- Telnet
- SSH
运行在 UDP 上的协议
- HTTP/3.0
- DHCP
- DNS
TCP 三次握手与四次挥手
- 三次握手作用
  - 一握：服务端确认客户端发送正常，自身接收正常
  - 二握：客户端确认服务端接收、发送正常，自身发送接收正常
  - 三握：服务端确认自身发送正常
- 四次挥手作用（哪方先发起，哪方进入 TIME-WAIT，本例使用客户端先发起举例）
  - 一挥：客户端发送 FIN 后，进入 FIN-WAIT-1，关闭客户端到服务器方向的数据发送
  - 二挥：服务端接收 FIN 后，发送 ACK 后，进入 CLOSE-WAIT，可继续未发完数据发送给客户端
    
    客户端接收 ACK，进入 FIN-WAIT-2，此时还可接收来自服务端的数据
  - 三挥：服务器发送 FIN 后，进入 LAST-ACK，表示剩余数据完全发完
  - 四挥：客户端接收 FIN 后，发送 ACK 后，进入 TIME_WAIT，等待 2*MSL 后进入 CLOSED
    
    服务端接收 ACK，进入 CLOSED
    
    （客户端等待 2*MSL，防止服务端未接收 ACK 时，要求客户端重传）

IP

属于网络层的协议，主要作用是定义数据包的格式，对数据包进行路由和寻址，以便它们可以跨网络传播并到达正确的目的地。IPv4 占用 32 bit，IPv4 占用 128 bit。

获取客户端真实 IP
- 应用层 X-Forwarded-For 请求获取，可能有多个值，只适用于 HTTP 和 SMTP
- 传输层 TCP Options 字段承载，需要收发双发具备操作 TCP Options 能力
- 网络层隧道 + DSR 模式（动态源路由
NAT 网络地址转换用于在不同网络之间转换 IP 地址，允许将私有 IP 地址映射为公有 IP 地址或者反向映射，从而实现局域网内多个设备通过单一公有 IP 地址访问互联网。原理是维护了一张 NAT 转换表，记载端口与局域网 IP 与端口的映射。

ARP

MAC 地址是媒体访问控制地址，它是网络设备的唯一标识。包含 48 bits，地址空间有 280 万亿之多，理论上不会重复，前 24 bits 由 IEEE 同一管理，确保不会重复，后 24 bits 由生产商自己管理，同样保证生产的两块网卡不重复。

ARP 地址解析协议，它解决网络层地址与链路层地址之间转换问题，即 IP 与 MAC 之间。IP 数据报在物理上传输过程中，总是需要知道下一跳该去何处，IP 地址属于逻辑地址，MAC 地址才是物理地址。

数据结构

线性数据结构

数组：内存连续、随机访问、容量有限
链表：非顺序存储、不具备随机访问
- 单链表
- 双向链表
- 循环链表
- 双向循环链表
栈：有序的线性数据集合idea一端进行加入或移除，后进先出

浏览器回退、前进功能；检查符号是否成对；反转字符串、维护函数调用；深度优先遍历
队列：先进先出的线性表，数组实现叫顺序队列，链表实现叫链式队列
- 单队列，会出现假溢出
- 循环队列，解决假溢出
- 双端队列，队列两端都可以插入删除
- 优先队列，底层一般由堆来实现
可实现阻塞队列；线程池的请求、任务队列；栈；广度优先搜索；内核进程队列；消息队列

图

图，非线性数据结构，没有明显的层次关系，它是由顶点的有穷非空集合和顶点之间的边组成的集合。

表示为：G(V, E) 其中，G 表示图， V 表示顶点集合，E 表示边的集合。

顶点：图中数据元素，称为顶点
边：顶点之间的关系用边表示
度：表示一个顶点包含多少条边
无向图与有向图

顶点之间的关系是双向的就是无向图，反之为有向图
无权图和带权图

对于一个关系，如果只关注关系的有无，而不关心关系的多强，就是无权图

如果既关心关系有无，也关心关系的强度，那就称为带权图
图的存储
- 领接矩阵存储，A[i][j]=n 表示顶点 i、顶点 j 之间关系权值为 n
  
  无向图的领接矩阵是一个对称矩阵
  
  领接矩阵表示法优点是简单直接，缺点是太浪费空间
- 领接表存储
  
  图中每个顶点，把所有邻接该顶点的其他顶点用单链表连接起来，称作领接表
  
  无向图中，邻接表的个数等于边的条数的两倍
  
  有向图中，邻接表的个数等于边的条数
图的搜索
- 广度优先搜索
  
  使用队列，每弹出一个元素，将其后继未访问过的顶点放入队尾
  
  广度搜索像水波纹一样一层一层向外扩展
- 深度优先搜索
  
  使用栈，每出栈，将其后继未访问的顶点压入栈内
  
  深度搜索就是一条路走到黑，一直到没有后继节点才回溯上一个顶点

堆

堆，堆中每一个节点值都大于等于（或小于等于）子树中所有节点的值。

当节点大于等于所有子节点时为最大堆，反之为最小堆。

用途

关心所有数据中的最大值、最小值，或存在多次获取最大值、最小值，多次插入或删除数据。
分类
- 最大堆
- 最小堆
存储
- 完全二叉树，利用数组存储二叉树既省时间，又方便索引
  
  根节点序号为 1，那么对于树中任意节点 i，左子节点序号 2*i，右子节点序号 2*i+1
  
  故为了方便存储和索引，二叉堆可以用完全二叉树形式进行存储
操作
- 插入
  1. 插入到最后
  2. 父节点比该元素小，节点与父节点交换，直到无法交换
- 删除堆顶元素
  
  删除堆顶元素后，为保持堆的性质，需要对堆的结构进行调整，称为堆化
  
  堆化方法有两种：
  - 自低向上的堆化，比较左右子节点，将大的填充到根节点，一直循环比较，直到堆的最底部（可能出现气泡）
  - 自顶向下的堆化，将最后一个元素移动到堆顶，然后不停左右子节点比较，和较大子节点交换，直到无法交换
- 插入元素：先将元素放至数组末尾，再自底向上堆化，将末尾元素上浮
- 删除元素：删除堆顶元素，将末尾元素放置堆顶，再自顶向下堆化，将堆顶元素下沉。
堆排序
- 建堆，将一个无序的数组建立为一个堆（对所有非叶节点的自顶向下堆化）
  
  非叶结点：最后一个节点的父节点及它之前的元素，即 n/2 ~ 1
- 排序，将堆顶元素取出，然后对剩下的元素进行堆化，反复迭代，直到所有元素被取出为止

树

树，是一种类似现实生活中的树的倒置结构，任何一颗非空树只有一个根节点。

树具有以下特点：

一棵树中的任意两个节点有且仅有唯一的一条路径连通
一棵树如果有 n 个结点，那么它一定恰好有 n-1 条边
一棵树不包含回路

树的常用概念
- 节点：树中的每个元素都可以统称为节点
- 根节点：顶层节点或者说没有父节点的节点
- 父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点。
- 子节点：一个节点含有的子树的根节点称为该节点的子节点
- 兄弟节点：具有相同父节点的节点互称为兄弟节点
- 叶子节点：没有子节点的节点
- 节点高度：该节点到叶子节点的最长路径所包含的边数
- 节点深度：根节点到该节点的路径所包含的边数
- 节点层数：节点的深度+1
- 树的高度：根节点的高度
二叉树的分类

二叉树是每个节点最多只有两个分支的树结构。二叉树分支通常称作左子树、右子树，具有左右次序，不随意颠倒。

二叉树的第 i 层至多拥有 2^(i-1) 个节点，深度为 k 的二叉树至多共有 2^(k+1)-1 个节点（即：满二叉树），至少有 2^k
- 满二叉树：每一层的节点数都达到最大值，则称这个数为满二叉树。节点总数 2^k-1，k 为层数
- 完全二叉树：除最后一层外，其余层都是满的，且最后一层或者是满的、或者是在右边缺少连续若干节点
  
  父节点、子节点的序号有对应关系，父节点序号是 i，那左子节点序号就是 2i, 右子节点序号是 2i+1
  
  这使得完全二叉树利用数组存储时可以极大节省空间，以及利用序号找到某个节点的父节点和子节点
- 平衡二叉树：二叉排序树，具有以下性质
  - 可以是一颗空树
  - 若非空树，它左右两个子树的高度差绝对不超过 1，且左右两个子树都是一颗平衡二叉树
    
    平衡二叉树常用实现方法有：红黑树、AVL 树、替罪羊树、加权平衡树、伸展树
二叉树的存储
- 链式存储，依靠指针将各个节点串联起来，不需要连续的存储空间
- 顺序存储，利用数组进行存储，数组中每一个位置仅存储节点的 data，不存储左右节点的指针，子节点的索引通过数组下标完成。根节点序号为 1，对于每个节点 Node, 假设它存储在数组中下标为 i, 那么它左子节点存储在 2i，右子节点存储在 2i+1 的位置。
二叉树的遍历
- 先序遍历，先输出根节点，再遍历左子树，最后遍历右子树，遍历左右子树时，同样遵循先序遍历规则。
- 中序遍历，先递归中序遍历的左子树，再输出根节点值，在递归中序遍历右子树，即一巴掌把树压扁，父节点拍到了左右子节点中间。
- 后续遍历，先递归左子树，再递归右子树，最后输出根节点的值

红黑树

红黑树是一种自平衡二叉查找树，也被称作平衡二叉 B 树。由于自平衡特性，保证最坏情况下在 O(logn) 时间复杂度完成查找、增加、删除等操作，性能表现稳定。JDK 的 TreeMap、TreeSet、HashMap 底层都用到了红黑树。

红黑树为了解决二叉查找树在按升序或降序插入的时候退化成一个线性结构而大大降低性能的问题。

特点
1. 每个节点非红即黑，黑色决定平衡，红色不决定平衡。
2. 根节点总是黑色的
3. 每个叶子节点都是黑色的空节点，指红黑树都会有一个空的叶子节点
4. 如果节点是红色的，则它的子节点必须是黑色的（反之不一定）
5. 从任意结点到它的叶子节点或空子节点的每条路径，必须包含相同数目的黑色节点（相同的黑色高度）

史上最好理解的红黑树讲解，让你彻底搞懂红黑树

布隆过滤器

布隆过滤器主要是为了解决海量数据的存在性问题，在海量数据中判定某个数据是否存在且容忍轻微误差这一场景（缓存穿透、海量数据去重）来说，非常合适。

单机，使用 Guava API

// 创建布隆过滤器对象
BloomFilter<Integer> filter = BloomFilter.create(
    Funnels.integerFunnel(),
    1500,
    0.01);
// 判断指定元素是否存在
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));
// 将元素添加进布隆过滤器
filter.put(1);
filter.put(2);
System.out.println(filter.mightContain(1));
System.out.println(filter.mightContain(2));

分布式，使用 Redis 提供的

算法

贪心算法

选择每一阶段的局部最优，从而达到全局最优。

典型题
- 455.分发饼干：https://leetcode.cn/problems/assign-cookies/open in new window
- 121.买卖股票的最佳时机：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/open in new window
- 122.买卖股票的最佳时机 II：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/open in new window
- 55.跳跃游戏：https://leetcode.cn/problems/jump-game/open in new window
- 45.跳跃游戏 II：https://leetcode.cn/problems/jump-game-ii/open in new window

动态规划

每一个状态一定由上一个状态推到出来，有别于贪心，贪心没有状态推导，而是从局部直接挑选最优。

解题步骤
- 确定 dp 数组以及下标含义
- 确定递推公式
- dp 数组如何初始化
- 确定遍历顺序
- 举例推到 dp 数组
典型题
- 509.斐波那契数：https://leetcode.cn/problems/fibonacci-number/open in new window
- 746.使用最小花费爬楼梯：https://leetcode.cn/problems/min-cost-climbing-stairs/open in new window
- 416.分割等和子集：https://leetcode.cn/problems/partition-equal-subset-sum/open in new window
- 518.零钱兑换：https://leetcode.cn/problems/coin-change-ii/open in new window
- 647.回文子串：https://leetcode.cn/problems/palindromic-substrings/open in new window
- 516.最长回文子序列：https://leetcode.cn/problems/longest-palindromic-subsequence/open in new window

回溯算法

实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就回溯返回，尝试别的路径，其本质就是穷举。典型题目：8 皇后

一般解题步骤
- 针对所给问题，定义问题的解题空间，至少包含问题的一个最优解
- 确定易于搜索的解题空间结构，使得能用回溯法方便地搜索整个解空间
- 以深度优先方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索
典型题
- 77.组合：https://leetcode.cn/problems/combinations/open in new window
- 39.组合总和：https://leetcode.cn/problems/combination-sum/open in new window
- 40.组合总和 II：https://leetcode.cn/problems/combination-sum-ii/open in new window
- 78.子集：https://leetcode.cn/problems/subsets/open in new window
- 90.子集 II：https://leetcode.cn/problems/subsets-ii/open in new window
- 51.N 皇后：https://leetcode.cn/problems/n-queens/open in new window

分治算法

将一个规模为 N 的问题分解为 K 个规模较小的子问题，这些子问题相互独立且与原问题性质相同，求出子问题的解，就可得到原问题的解。经典题目：二分查找、汉诺塔

解题步骤
- 将原问题分解为若干个规模较小、相互独立，与原问题形式相同的子问题
- 若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
- 将各个子问题的解合并为原问题的解
典型题
- 108.将有序数组转换成二叉搜索数：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/open in new window
- 148.排序列表：https://leetcode.cn/problems/sort-list/open in new window
- 23.合并 k 个升序链表：https://leetcode.cn/problems/merge-k-sorted-lists/