FOUNDATIONS OF COMPUTER SCIENCE 5TH EDITION计算机科学道理学习:第五章：计算机组织（Computer Organization）

虾球xz

403人浏览 · 2026-05-25 11:40:35

虾球xz · 2026-05-25 11:40:35 发布

一、整体架构概览

一台计算机由三个大"部门"组成，就像一家公司有三个部门各司其职：

+--------------------------------------------------+
|                   计算机硬件                      |
|                                                  |
|  +------------+  +----------+  +-------------+  |
|  |  CPU       |  |  主内存  |  | 输入/输出   |  |
|  | (大脑/运算)|  | (工作台) |  | 子系统(手脚)|  |
|  +------------+  +----------+  +-------------+  |
+--------------------------------------------------+

CPU（中央处理器）：负责"思考"和"计算"，是计算机的大脑
主内存（Main Memory）：负责"暂时存放"正在用的数据和程序，像办公桌
输入/输出子系统（I/O Subsystem）：负责和外界沟通，像人的手和眼睛

二、CPU（中央处理器）

CPU 内部又分三个小部件：

+---------------------------------------------+
|               CPU                           |
|                                             |
|  +----------+  +---------+  +-----------+  |
|  |  ALU     |  | 寄存器  |  |  控制单元 |  |
|  | (计算器) |  | (便条纸)|  |  (指挥官) |  |
|  +----------+  +---------+  +-----------+  |
|               R0, R1, ..., Rn               |
|               PC (程序计数器)               |
|               IR (指令寄存器)               |
+---------------------------------------------+

2.1 ALU（算术逻辑单元）

ALU 是真正做计算的地方，能做三类操作：

操作类型	举例	说明
逻辑操作	NOT、AND、OR、XOR	对位（0和1）进行逻辑运算
移位操作	左移、右移	把二进制位向左或向右挪动
算术操作	加、减、乘、除	普通数学运算

移位操作的妙用： 把一个整数的二进制位向左移1位，等于乘以2；向右移1位，等于除以2。比 $\times 2$ 或 $\div 2$ 用硬件做更快。

2.2 寄存器（Registers）

寄存器就是 CPU 内部的"便条纸"，速度极快但数量有限。
三种主要寄存器：

数据寄存器（R0 ~ Rn）：存放运算用的数据，CPU 只能对寄存器里的数据做运算
指令寄存器（IR, Instruction Register）：存放当前正在执行的那条指令
程序计数器（PC, Program Counter）：记录"下一条要执行的指令在内存的哪个地址"，每执行完一条指令就自动加1

2.3 控制单元（Control Unit）

控制单元是"指挥官"，不做具体计算，只负责：

告诉 ALU 该做什么运算
告诉内存该读还是该写
协调整个 CPU 的工作节奏

三、主内存（Main Memory）

主内存就像一排有编号的格子，每个格子存一个"字（word）"的数据。

地址（Address）      内容（Contents）
  0000 0000    →   [ 0 0 1 0 0 0 0 0 0 0 0 1 ]
  0000 0001    →   [ 1 1 0 1 1 1 1 1 0 0 1 0 ]
  0000 0010    →   [ 0 0 0 0 1 1 0 0 1 1 0 1 ]
     ...              ...
  1111 1111    →   [ 1 0 1 1 0 0 1 1 1 1 0 0 ]

3.1 地址空间（Address Space）

字（Word）：内存每次存取的最小单位，可以是 8位、16位、32位、64位。
8位的字 = 1字节（byte）
地址空间：内存里所有格子的总数。
地址用二进制表示，所以需要多少位取决于有多少个格子：
若内存有 $N$ 个字，则需要 $log_2 N$ 位来表示地址。
例1：计算机有 32MB 内存，需要多少位表示一个字节地址？
$32\text{MB} = 2^5 \times 2^{20} = 2^{25} \text{ 字节}$
需要 $log_2 2^{25} = 25$ 位。
例2：计算机有 128MB 内存，每个字 = 8字节，需要多少位表示一个字地址？
$128\text{MB} = 2^{27} \text{ 字节，每字} = 2^3 \text{ 字节}$
$\text{字数} = \frac{2^{27}}{2^3} = 2^{24}$
$\text{需要} \log_2 2^{24} = 24 \text{ 位}$

内存单位对照表：

单位	精确字节数	近似值
千字节 (KB)	$2^{10} = 1024$ 字节	$10^3$ 字节
兆字节 (MB)	$2^{20} \approx 100$ 万字节	$10^6$ 字节
吉字节 (GB)	$2^{30} \approx 10$ 亿字节	$10^9$ 字节
太字节 (TB)	$2^{40} \approx 1$ 万亿字节	$10^{12}$ 字节

3.2 内存类型

各类型特点汇总：

类型	可读	可写	断电丢失	特点
SRAM	是	是	是	最快，最贵，用于缓存
DRAM	是	是	是	较慢，便宜，用于主内存
ROM	是	否	否	出厂时写入，不可更改
PROM	是	一次	否	用户可烧录一次
EPROM	是	可	否	紫外线照射可擦除重写
EEPROM	是	可	否	电信号即可擦除，最方便

3.3 内存层次结构（Memory Hierarchy）

速度越快的内存越贵，所以计算机用"分层"策略：

        速度最快，最贵，最小
           +----------+
           | 寄存器   |   ← CPU内部，极少量
           +----------+
          +------------+
          | 缓存内存   |   ← Cache，KB~MB级
          +------------+
         +--------------+
         |   主内存     |   ← RAM，GB级
         +--------------+
        速度最慢，最便宜，最大

3.4 缓存内存（Cache Memory）

缓存是夹在 CPU 和主内存之间的"中转站"，比主内存快但比寄存器慢。
工作流程：

CPU 需要某个数据
      |
      v
  检查缓存中有没有？
      |
   有（命中）          没有（未命中）
      |                    |
      v                    v
直接从缓存读取      从主内存读取整块数据
                    同时复制到缓存
                         |
                         v
                   从缓存读取所需数据

为什么缓存很有效？ 依据"80-20法则"：程序运行时，80% 的时间都在访问同一批 20% 的数据。把这 20% 的热门数据放进缓存，大多数时候直接命中，速度飞快。

四、输入/输出（I/O）子系统

I/O 子系统让计算机和"外部世界"交流，分两大类：

4.1 非存储设备（Nonstorage Devices）

只负责"输入"或"输出"，不存数据：

键盘：输入文字
显示器：输出画面
打印机：输出纸质内容（打出去的字不能直接再输回电脑，所以是非存储）

4.2 存储设备（Storage Devices）

能长期保存数据，断电不丢失：

磁性存储（Magnetic Storage）

利用磁化方向表示0和1：磁化=1，未磁化=0。
磁盘（Magnetic Disk）：

           磁盘表面（俯视图）
    +----------------------------------+
    |    轨道（Track）                 |
    |  +----------------------------+  |
    |  | 扇区  | 扇区  | 扇区  |   |  |
    |  | Sector| Sector| Sector|   |  |
    |  +----------------------------+  |
    |      <- 轨道间隙（Gap）->        |
    +----------------------------------+
              读写头在此滑动

磁盘是随机访问设备（可以直接跳到任何位置读取），最小存取单位是"扇区"。
性能三要素：

旋转速度：盘片转多快
寻道时间：读写头移到目标轨道要多长时间
传输时间：数据从磁盘传到 CPU 要多长时间
磁带（Magnetic Tape）：
顺序访问设备（必须从头到尾依次读，不能跳着读）
速度慢，但便宜，适合备份大量数据

光学存储（Optical Storage）

用激光读写数据：
CD-ROM（只读光盘）：
光盘上有两种物理结构：

凹坑（Pit）：代表0
平地（Land）：代表1
读取时低功率激光照射：照到平地反射强（检测到1），照到凹坑因为深度恰好是光波长的 $\frac{1}{4}$ ，两次反射相消干涉，反射弱（检测到0）。

CD-ROM、CD-R、CD-RW、DVD 对比：

类型	可读	可写	可擦除	反射层	备注
CD-ROM	是	否	否	铝	批量生产，用模具压制
CD-R	是	一次	否	金	用染料模拟坑/地，写一次
CD-RW	是	多次	是	合金	合金有晶态/非晶态两种状态
DVD	是	否	否	铝	坑更小，容量更大

DVD 容量（比 CD 大得多）：

配置	容量
单面单层	4.7 GB
单面双层	8.5 GB
双面单层	9.4 GB
双面双层	17 GB

相比之下，普通 CD-ROM 只有约 650 MB。

五、子系统互连（Subsystem Interconnection）

三个子系统需要用"总线（Bus）"互相传递信息。

5.1 CPU 与内存的连接

三条总线：

+-------+   数据总线（Data Bus）    +--------+
|       | <-----------------------> |        |
|  CPU  |   地址总线（Address Bus） | 内存   |
|       | -----------------------> |        |
|       |   控制总线（Control Bus） |        |
|       | <-----------------------> |        |
+-------+                          +--------+

数据总线：传输实际数据，宽度 = 字长（如32位字 → 32根线）
地址总线：告诉内存"要读/写哪个地址"，宽度 = $\log_2(\text{内存字数})$ 位
控制总线：传递控制信号（如"读"还是"写"），宽度 = $\log_2(\text{控制命令数})$ 位

5.2 I/O 设备的连接

I/O 设备不能直接连总线（速度差太多、性质不同），必须通过**控制器（Controller）**作中介：

CPU ←→ 总线 ←→ 键盘控制器 ←→ 键盘
              ←→ 显示器控制器 ←→ 显示器
              ←→ 磁盘控制器 ←→ 磁盘
              ←→ 打印机控制器 ←→ 打印机

三种常见控制器对比：

控制器	类型	连接方式	最大设备数	备注
SCSI	并行	菊花链	受限于ID数	两端需终结器
FireWire	串行	菊花链/树形	63	无需终结器，高速
USB	串行	树形（Hub）	127	支持热插拔，最普及

USB 特点补充：

4根线：2根供电（+5V和地），2根传数据
支持热插拔（Hot-swappable）：不用关机就能插拔设备
USB 2.0 三种速率：1.5 Mbps（低速）、12 Mbps（全速）、480 Mbps（高速）
USB 3.0 超速模式：最高 4.8 Gbit/s

5.3 I/O 寻址方式

CPU 怎么区分"访问内存"和"访问I/O设备"？两种方法：
方法一：独立 I/O（Isolated I/O）
内存和 I/O 用不同的指令：

读内存：READ 101
读I/O设备101：INPUT 101
地址可以重叠，指令不同所以不混淆。
方法二：内存映射 I/O（Memory-mapped I/O）
把 I/O 设备的寄存器"伪装成"内存地址，CPU 用同一套指令访问一切：
读内存101：READ 101
读I/O设备（映射到地址64001）：READ 64001
优点：指令集更简洁。缺点：占用了一部分内存地址空间。

六、程序执行（Program Execution）

6.1 机器周期（Machine Cycle）

CPU 不停地循环执行三个步骤，每个循环叫一个"机器周期"：

6.2 I/O 同步方法

CPU 速度远快于 I/O 设备，三种同步方式：
方法一：程序控制 I/O（Programmed I/O）

CPU 发出 I/O 指令后，一直等待，不断查询设备是否准备好
缺点：浪费 CPU 时间（在那傻等）
方法二：中断驱动 I/O（Interrupt-driven I/O）
CPU 发出 I/O 指令后，去做别的事
设备准备好了，主动中断通知 CPU
优点：CPU 不浪费时间等待
方法三：直接内存访问（DMA, Direct Memory Access）
引入专门的 DMA 控制器，CPU 只需告诉 DMA"搬哪里的数据、搬多少"
DMA 直接在内存和 I/O 设备之间搬数据，CPU 去干其他事
传输完毕 DMA 再中断通知 CPU
适合大块数据传输（如磁盘读写）

三种方法对比：

方法	CPU 利用率	适用场景	数据路径
程序控制 I/O	最低（一直等）	极少量数据	设备→CPU→内存
中断驱动 I/O	中等	少量数据	设备→CPU→内存
DMA	最高	大块数据（磁盘）	设备→内存（直接）

七、计算机架构（Different Architectures）

7.1 CISC vs RISC

特性	CISC（复杂指令集）	RISC（精简指令集）
指令数量	多，包含复杂指令	少，只有简单指令
编程难度	简单（一条指令可做复杂事）	较难（需多条指令组合）
硬件复杂度	高（需要微程序）	低
代表	Intel Pentium 系列	ARM、MIPS

CISC 内部有一层"微程序（microprogramming）"：复杂指令先被拆解成一系列简单"微操作"再执行。

7.2 流水线（Pipelining）

没有流水线时： 一条指令必须完成取指-解码-执行三步后，下一条才能开始：

时间 →  1  2  3  4  5  6  7  8  9
指令1   取  解  执
指令2            取  解  执
指令3                     取  解  执

9个时间单元完成3条指令。
有流水线时： 三个阶段可以重叠进行（像工厂流水线）：

时间 →  1  2  3  4  5  6  7  8
指令1   取  解  执
指令2       取  解  执
指令3           取  解  执
指令4               取  解  执
指令5                   取  解  执

8个时间单元完成更多指令，**吞吐量（Throughput）**大幅提升！
按照书中计算：不用流水线 9 个时间单元完成 3 条指令，用流水线 24 个时间单元完成 8 条指令，提升约 266%。

7.3 并行处理（Parallel Processing）

Flynn 分类法把计算机组织分为四类：

类型	说明	实际应用
SISD	1个控制单元，1个ALU，顺序执行	普通单核CPU
SIMD	1个控制单元，多个ALU，同一指令操作不同数据	GPU、向量处理器
MISD	多指令同时操作同一数据	理论模型，未实现
MIMD	多指令流操作多数据流，真正并行	多核CPU、超级计算机

八、一个简单计算机的完整示例

8.1 简单计算机结构

这台假想计算机的规格：

组件	规格
数据寄存器	16个，R0~R15，每个16位
程序计数器PC	8位（最多指向256个地址）
指令寄存器IR	16位
主内存	256个16位存储单元（地址00~FF，十六进制）
程序区	地址 00~3F（前64个）存指令
数据区	地址 40~FD 存数据
键盘（输入）	映射到地址 FE
显示器（输出）	映射到地址 FF

8.2 指令格式

每条指令 16 位，分成 4 个 4 位字段：

+--------+--------+--------+--------+
|  操作码|  操作数1|  操作数2|  操作数3|
| 4 bits | 4 bits | 4 bits | 4 bits |
+--------+--------+--------+--------+

8.3 指令集（14条指令）

指令	代码	操作说明
HALT	0	停止程序
LOAD	1	从内存地址读数据到寄存器：RD ← 内存[MS]
STORE	2	从寄存器写数据到内存：内存[MD] ← RS
ADDI	3	整数加法：RD ← RS1 + RS2
ADDF	4	浮点加法：RD ← RS1 + RS2
MOVE	5	寄存器间复制：RD ← RS
NOT	6	按位取反：RD ← NOT RS
AND	7	按位与：RD ← RS1 AND RS2
OR	8	按位或：RD ← RS1 OR RS2
XOR	9	按位异或：RD ← RS1 XOR RS2
INC	A	自增：R ← R + 1
DEC	B	自减：R ← R - 1
ROTATE	C	循环移位：n位，方向0=右1=左
JUMP	D	条件跳转：若 R0 ≠ R，则 PC ← n

8.4 完整执行示例：计算 A + B = C

目标： 将内存地址 40 和 41 中的两个整数相加，结果存入地址 42。
实际数值： $161 + 254 = 415$ ，十六进制为 $00A1)_{16} + (00FE)_{16} = (019F)_{16}$
程序（5条指令）：

地址  机器码    含义
00    1040     LOAD  R0 ← 内存[40]
01    1141     LOAD  R1 ← 内存[41]
02    3201     ADDI  R2 ← R0 + R1
03    2422     STORE 内存[42] ← R2
04    0000     HALT  停止

内存布局：

地址  内容
00    1040   ← 第1条指令
01    1141   ← 第2条指令
02    3201   ← 第3条指令
03    2422   ← 第4条指令
04    0000   ← 第5条指令（HALT）
...
40    00A1   ← 数据 A = 161
41    00FE   ← 数据 B = 254
42    ????   ← 结果 C（待写入）

五个周期的执行过程：
周期1（Cycle 1）：执行 LOAD R0 ← 内存[40]

PC = 00 → 取出指令 1040 → PC变为 01
解码：1 = LOAD，0 = R0，40 = 内存地址
执行：R0 ← 00A1

周期2（Cycle 2）：执行 LOAD R1 ← 内存[41]

PC = 01 → 取出指令 1141 → PC变为 02
解码：1 = LOAD，1 = R1，41 = 内存地址
执行：R1 ← 00FE

周期3（Cycle 3）：执行 ADDI R2 ← R0 + R1

PC = 02 → 取出指令 3201 → PC变为 03
解码：3 = ADDI，2 = R2（目标），0 = R0，1 = R1（源）
执行：R2 ← 00A1 + 00FE = 019F

周期4（Cycle 4）：执行 STORE 内存[42] ← R2

PC = 03 → 取出指令 2422 → PC变为 04
解码：2 = STORE，42 = 内存地址，2 = R2（源）
执行：内存[42] ← 019F

周期5（Cycle 5）：执行 HALT

PC = 04 → 取出指令 0000 → PC变为 05
解码：0 = HALT
执行：停止

8.5 带输入输出的完整程序

从键盘读两个数相加，把结果显示到屏幕：

地址  机器码    含义
00    1FFE     LOAD  R15 ← 键盘（读第1个数到R15）
01    240F     STORE 内存[40] ← R15（存入内存）
02    1FFE     LOAD  R15 ← 键盘（读第2个数）
03    241F     STORE 内存[41] ← R15
04    1040     LOAD  R0 ← 内存[40]
05    1141     LOAD  R1 ← 内存[41]
06    3201     ADDI  R2 ← R0 + R1
07    2422     STORE 内存[42] ← R2
08    1F42     LOAD  R15 ← 内存[42]（取出结果）
09    2FFF     STORE 显示器[FF] ← R15（输出到屏幕）
0A    0000     HALT

关键规则：

键盘映射地址 = $FE)_{16}$ ，读键盘 = 用 LOAD 从地址 FE 读
显示器映射地址 = $FF)_{16}$ ，写屏幕 = 用 STORE 写到地址 FF
输入数据必须先存入内存，输出数据必须从内存读取

九、对应的 C++ 代码：简单计算机模拟器

#include <iostream>
#include <iomanip>
#include <cstdint>
#include <string>
// ============================================================
// 简单计算机模拟器
// 模拟第五章描述的假想计算机：
//   - 16个16位数据寄存器 R0~R15
//   - 8位程序计数器 PC
//   - 16位指令寄存器 IR
//   - 256个16位内存单元（地址 0x00~0xFF）
//   - 键盘映射到地址 0xFE，显示器映射到 0xFF
// ============================================================
// 内存大小（256个格子，每格16位）
const int MEM_SIZE = 256;
// 寄存器数量（16个）
const int REG_COUNT = 16;
// 键盘和显示器的映射地址
const int KEYBOARD_ADDR = 0xFE;  // 键盘：内存地址 0xFE
const int MONITOR_ADDR  = 0xFF;  // 显示器：内存地址 0xFF
// ============================================================
// 计算机状态结构体：存放所有硬件状态
// ============================================================
struct Computer {
    uint16_t memory[MEM_SIZE]; // 主内存，每个元素16位
    uint16_t reg[REG_COUNT];   // 16个数据寄存器 R0~R15
    uint8_t  PC;               // 程序计数器（8位，最多256个地址）
    uint16_t IR;               // 指令寄存器（16位）
    bool     running;          // 计算机是否还在运行
};
// ============================================================
// 初始化计算机：所有内存和寄存器清零，PC从0开始
// ============================================================
void initComputer(Computer& cpu) {
    for (int i = 0; i < MEM_SIZE; i++) cpu.memory[i] = 0;
    for (int i = 0; i < REG_COUNT; i++) cpu.reg[i] = 0;
    cpu.PC = 0;
    cpu.IR = 0;
    cpu.running = true;
}
// ============================================================
// 执行一个机器周期（取指 → 解码 → 执行）
// ============================================================
void machineCycle(Computer& cpu) {
    // ── 阶段1：取指（Fetch）──────────────────────────────────
    // 从 PC 指向的内存地址取出指令，放入 IR
    cpu.IR = cpu.memory[cpu.PC];
    cpu.PC++;  // PC 自动加1，指向下一条指令
    // ── 阶段2：解码（Decode）────────────────────────────────
    // 把16位指令拆成4个4位字段
    // 指令格式：[操作码4位][字段2:4位][字段3:4位][字段4:4位]
    uint8_t opcode = (cpu.IR >> 12) & 0xF; // 最高4位 = 操作码
    uint8_t d2     = (cpu.IR >> 8)  & 0xF; // 次高4位
    uint8_t d3     = (cpu.IR >> 4)  & 0xF; // 次低4位
    uint8_t d4     = (cpu.IR)       & 0xF; // 最低4位
    // 某些指令用 d3+d4 组合成8位内存地址
    uint8_t memAddr = (d3 << 4) | d4;
    // ── 阶段3：执行（Execute）────────────────────────────────
    switch (opcode) {
        case 0x0: // HALT：停止
            cpu.running = false;
            break;
        case 0x1: { // LOAD：RD ← 内存[MS]
            // d2 = 目标寄存器地址, memAddr = 源内存地址
            if (memAddr == KEYBOARD_ADDR) {
                // 从键盘读取输入（模拟：让用户输入一个整数）
                std::cout << "请输入一个整数（键盘输入）: ";
                int input;
                std::cin >> input;
                cpu.reg[d2] = (uint16_t)input;
            } else {
                cpu.reg[d2] = cpu.memory[memAddr];
            }
            break;
        }
        case 0x2: { // STORE：内存[MD] ← RS
            // d2+d3 组合成内存地址, d4 = 源寄存器
            // 注意：STORE 指令格式是 [2][addr_high][addr_low][RS]
            uint8_t storeAddr = (d2 << 4) | d3; // 用 d2+d3 做地址
            uint8_t srcReg    = d4;              // d4 是源寄存器
            if (storeAddr == MONITOR_ADDR) {
                // 写入显示器（模拟：打印到屏幕）
                std::cout << "显示器输出: " << cpu.reg[srcReg] << std::endl;
            } else {
                cpu.memory[storeAddr] = cpu.reg[srcReg];
            }
            break;
        }
        case 0x3: // ADDI：整数加法 RD ← RS1 + RS2
            // d2=目标, d3=源1, d4=源2（有符号16位相加）
            cpu.reg[d2] = (int16_t)cpu.reg[d3] + (int16_t)cpu.reg[d4];
            break;
        case 0x5: // MOVE：寄存器间复制 RD ← RS
            cpu.reg[d2] = cpu.reg[d3];
            break;
        case 0x6: // NOT：按位取反
            cpu.reg[d2] = ~cpu.reg[d3];
            break;
        case 0x7: // AND：按位与
            cpu.reg[d2] = cpu.reg[d3] & cpu.reg[d4];
            break;
        case 0x8: // OR：按位或
            cpu.reg[d2] = cpu.reg[d3] | cpu.reg[d4];
            break;
        case 0x9: // XOR：按位异或
            cpu.reg[d2] = cpu.reg[d3] ^ cpu.reg[d4];
            break;
        case 0xA: // INC：自增 R ← R + 1
            cpu.reg[d2]++;
            break;
        case 0xB: // DEC：自减 R ← R - 1
            cpu.reg[d2]--;
            break;
        case 0xC: { // ROTATE：循环移位
            // d2=寄存器, d3=移位位数n, d4=方向(0=右,1=左)
            uint16_t val = cpu.reg[d2];
            int n = d3 % 16; // 移位数取模防止溢出
            if (d4 == 0) {
                // 右循环移位：低n位移到高位
                cpu.reg[d2] = (val >> n) | (val << (16 - n));
            } else {
                // 左循环移位：高n位移到低位
                cpu.reg[d2] = (val << n) | (val >> (16 - n));
            }
            break;
        }
        case 0xD: { // JUMP：条件跳转
            // 若 R0 ≠ R[d2]，则 PC ← memAddr
            if (cpu.reg[0] != cpu.reg[d2]) {
                cpu.PC = memAddr; // 跳转到目标地址
            }
            // 否则继续（PC已在取指时自增，不做任何处理）
            break;
        }
        default:
            std::cout << "未知操作码: 0x" << std::hex << (int)opcode << std::endl;
            cpu.running = false;
            break;
    }
}
// ============================================================
// 打印当前 CPU 状态（调试用）
// ============================================================
void printState(const Computer& cpu) {
    std::cout << "\n=== CPU 状态 ===" << std::endl;
    std::cout << "PC = 0x" << std::hex << std::setw(2) << std::setfill('0')
              << (int)cpu.PC << std::dec << std::endl;
    std::cout << "IR = 0x" << std::hex << std::setw(4) << std::setfill('0')
              << cpu.IR << std::dec << std::endl;
    for (int i = 0; i < 4; i++) {
        std::cout << "R" << i << " = 0x" << std::hex << std::setw(4)
                  << std::setfill('0') << cpu.reg[i] << std::dec;
        std::cout << " (" << (int16_t)cpu.reg[i] << ")  ";
    }
    std::cout << std::endl;
    std::cout << "================" << std::endl;
}
// ============================================================
// 主程序：演示"161 + 254 = 415"的5条指令程序
// ============================================================
int main() {
    Computer cpu;
    initComputer(cpu);
    // ── 加载程序到内存 ──────────────────────────────────────
    // 程序：从内存[40]和[41]读取两个整数，相加，结果存入内存[42]
    //
    // 指令编码格式（十六进制）：
    //   1040 = LOAD R0 ← 内存[0x40]
    //   1141 = LOAD R1 ← 内存[0x41]
    //   3201 = ADDI R2 ← R0 + R1
    //   2422 = STORE 内存[0x42] ← R2
    //   0000 = HALT
    cpu.memory[0x00] = 0x1040; // 指令1：LOAD R0 ← M[40]
    cpu.memory[0x01] = 0x1141; // 指令2：LOAD R1 ← M[41]
    cpu.memory[0x02] = 0x3201; // 指令3：ADDI R2 ← R0+R1
    cpu.memory[0x03] = 0x2422; // 指令4：STORE M[42] ← R2
    cpu.memory[0x04] = 0x0000; // 指令5：HALT
    // ── 加载数据到内存 ──────────────────────────────────────
    // 161 的十六进制 = 0x00A1
    // 254 的十六进制 = 0x00FE
    cpu.memory[0x40] = 0x00A1; // A = 161
    cpu.memory[0x41] = 0x00FE; // B = 254
    std::cout << "=== 简单计算机模拟器 ===" << std::endl;
    std::cout << "程序：计算 161 + 254" << std::endl;
    std::cout << "初始数据：M[40]=" << cpu.memory[0x40]
              << "，M[41]=" << cpu.memory[0x41] << std::endl << std::endl;
    // ── 运行：每个周期打印状态 ─────────────────────────────
    int cycle = 0;
    while (cpu.running) {
        cycle++;
        std::cout << "--- 周期 " << cycle << " ---" << std::endl;
        machineCycle(cpu);
        printState(cpu);
    }
    // ── 打印结果 ────────────────────────────────────────────
    std::cout << "\n计算结果：M[42] = " << cpu.memory[0x42]
              << " (十进制 = " << (int16_t)cpu.memory[0x42] << ")" << std::endl;
    std::cout << "预期结果：161 + 254 = 415" << std::endl;
    return 0;
}

编译和运行：

g++ -o simple_computer simple_computer.cpp
./simple_computer

预期输出：

=== 简单计算机模拟器 ===
程序：计算 161 + 254
初始数据：M[40]=161，M[41]=254
--- 周期 1 ---
=== CPU 状态 ===
PC = 0x01  IR = 0x1040
R0 = 0x00a1 (161)  R1 = 0x0000 (0)  R2 = 0x0000 (0)  ...
...
计算结果：M[42] = 415 (十进制 = 415)
预期结果：161 + 254 = 415

十、核心概念速查表

概念	一句话解释
CPU	计算机大脑，负责计算和控制
ALU	做算术和逻辑运算的部件
寄存器	CPU内部的临时存储"便条纸"
PC	记住"下一条指令在哪里"
IR	存放当前正在执行的指令
主内存	程序和数据的"工作台"
缓存	主内存和CPU之间的"高速中转站"
RAM	可读写但断电丢失
ROM	只读不可写，断电不丢失
总线	子系统之间传递信息的"高速公路"
流水线	让多条指令的不同阶段同时进行
DMA	I/O设备直接和内存通信，不经过CPU
CISC	指令复杂、数量多
RISC	指令简单、数量少
MIMD	真正的多核并行处理

第六章：计算机网络（Computer Networks）从零理解

一、什么是网络？

网络（Network） 就是把多台设备用线（或无线）连起来，让它们可以互相传递数据的系统。
网络由两部分组成：

硬件：物理设备，如网线、路由器、交换机等，负责实际传输信号
软件：控制传输的规则（协议），让数据能正确到达目的地

1.1 网络的三个标准

标准	含义	衡量方式
性能（Performance）	网络传数据有多快	传输时间、响应时间
可靠性（Reliability）	网络多久出一次故障	故障频率、恢复时间
安全性（Security）	数据是否被保护	防未授权访问、防篡改

传输时间（Transit time）：一条消息从发出到到达目的地所需时间
响应时间（Response time）：从发出请求到收到回应的时间

二、物理结构（Physical Structures）

2.1 连接类型

两种设备之间的连接方式：

点对点连接（Point-to-Point）
  设备A ————————— 设备B
  （线路全部给这两个设备专用）
多点连接（Multipoint / Multidrop）
  设备A ——+—— 设备B
          |
        设备C
  （多台设备共享同一条线路）

2.2 四种物理拓扑（Topology）

"拓扑"就是网络里设备和线路的几何连接方式，共有四种：

网状拓扑（Mesh）

每台设备和其他所有设备都有专线相连：

   A ——— B
   |\ /|
   | X |
   |/ \|
   C ——— D

优点：一条线坏了不影响其他路径，非常可靠
缺点：需要大量线缆，成本高

星型拓扑（Star）

所有设备都连到中央Hub（集线器），互相不直接连：

      A
      |
  B —Hub— C
      |
      D

优点：便宜，容易安装，某台设备坏了不影响其他
缺点：Hub坏了整个网络瘫痪（单点故障）
今天最常见的局域网拓扑

总线拓扑（Bus）

所有设备连在同一根主干线上：

EC——T——T——T——T——EC
   |  |  |  |
   A  B  C  D

EC=末端帽，T=分支接口
优点：容易安装
缺点：主干线任何位置断了，全网瘫痪

环形拓扑（Ring）

设备首尾相连形成一个环，数据单方向流动：

  A
 / \
D   B
 \ /
  C

优点：容易安装和故障隔离
缺点：一台设备坏了可能断环（需要双环或交换机补救）

三、网络分类（Categories）

按照覆盖范围分三类：

类型	全称	覆盖范围	典型例子
LAN	局域网	几公里以内	家庭/办公室/学校网络
MAN	城域网	一个城市	DSL宽带、有线电视网
WAN	广域网	国家/洲际/全球	互联网骨干网、企业专线

internet（互联网）vs Internet（因特网）

internet（小写i）：泛指任意多个网络连在一起形成的互联网络
Internet（大写I）：特指全球那个最大的互联网，由数十万个网络互联组成

LAN1 ——路由器—— WAN —— 路由器 ——LAN2
             ↑
        这整体就是一个 internet

路由器（Router）：负责在不同网络之间转发数据包的设备。
ISP（Internet Service Provider，互联网服务提供商）：提供上网服务的公司，有国际、国家、地区、本地四个层级。

四、TCP/IP 协议栈（Protocol Suite）

"协议"就像人与人之间说话的规则（比如约定用中文交流），计算机之间也需要一套规则才能通信。
TCP/IP 协议栈把通信任务分成5层，每层负责一部分工作，层层叠加：

数据传输方向：发送时从第5层向下到第1层，接收时从第1层向上到第5层。
路由器只用前3层（物理层、数据链路层、网络层），因为它只负责转发，不需要理解应用内容。

封装（Encapsulation）

每向下传一层，都会在数据前面加一个"信封头（Header）“，到第2层还会加"尾部（Trailer）”：

应用层：  [消息 M]
传输层：  [传输头 H4][M]
网络层：  [网络头 H3][H4][M]
数据链路：[链路头 H2][H3][H4][M][链路尾 T2]
物理层：  01001010101010... (变成电信号)

接收方反向拆信封，每层去掉自己那层的头。

五、五层详解

5.1 应用层（Application Layer）

作用：直接为用户服务，用户能看到的那一层。
提供：电子邮件、网页浏览、文件传输、远程登录等服务。

客户端-服务器架构（Client-Server Architecture）

用户电脑（客户端）          远程服务器
  [客户进程]  ——请求——>  [服务器进程]
             <——响应——

服务器进程：必须一直运行等待请求
客户进程：需要时才启动

应用层地址（URL）

用户要访问某个服务，需要知道服务器的"应用层地址"：
URL（统一资源定位符） 格式：

方法://主机名:端口/路径
例如：https://www.cengage.com/books/intro

但 URL 只是人类好记的名字，不能直接用来发送数据。
DNS（域名服务器）：把 URL 中的域名翻译成 IP 地址：

客户端 ——查询 www.example.com——> DNS服务器
客户端 <——返回 IP: 93.184.216.34——

类比：知道某人名字（域名），问电话本（DNS）查他的地址（IP），然后再寄信。

5.2 传输层（Transport Layer）

作用：负责"进程到进程"的完整消息传递。
一台服务器可能同时运行多个服务（FTP、HTTP等），端口号（Port Number）用来区分是哪个服务：
类比：IP地址是公寓楼的地址，端口号是具体哪个房间号。

端口号	对应服务
21	FTP（文件传输）
25	SMTP（邮件发送）
80	HTTP（网页）
443	HTTPS（加密网页）

传输层的主要工作

多路复用（Multiplexing）：把多个进程的数据合并发出（像门卫帮所有住户交信给邮差）
多路分解（Demultiplexing）：把收到的数据分发给对应进程（像门卫把邮件分给各住户）
流量控制（Flow Control）：防止发太快把接收方淹没
拥塞控制（Congestion Control）：网络拥堵时减慢发送速度（像高速公路匝道灯）
错误控制（Error Control）：检测丢包、乱序、损坏，必要时重发

三种传输层协议对比

协议	全称	特点	适用场景
UDP	用户数据报协议	快，无连接，不保证到达	视频直播、DNS查询、实时游戏
TCP	传输控制协议	可靠，有连接，保证顺序和到达	网页、文件下载、电子邮件
SCTP	流控制传输协议	兼顾UDP的速度和TCP的可靠性	网络电话、视频流

UDP 像普通邮件：发出去不管到没到，速度快
TCP 像挂号信：每个包都要确认收到，丢了就补发
SCTP 两者结合：既有确认机制，又适合实时传输

5.3 网络层（Network Layer）

作用：负责把数据包从源主机路由到目标主机，可能途经多个网络。

IP 地址（IP Address）

每台联网设备都有一个 IP 地址，相当于网络世界的"门牌号"。
IPv4 地址：32位二进制，写成"点分十进制"格式：
$\underbrace{00001010}_{10}.\underbrace{00011001}_{25}.\underbrace{10101100}_{172}.\underbrace{00001111}_{15} \rightarrow 10.25.172.15$
IPv4 最多支持 $2^{32} \approx 43$ 亿个地址，已接近耗尽。
IPv6：128位，可支持 $2^{128}$ 个地址，从根本上解决地址耗尽问题。

路由（Routing）

数据包不知道目的地怎么走，路由器帮它找路：

A ——> R1 ——> R4 ——> R5 ——> D
（R1查路由表，选最优下一跳R4，
 R4再查，选R5，R5直接到目的地D）

类比：从加州小镇寄信到佛罗里达小镇，经过多个邮局中转，每个邮局决定下一步怎么转。
IP 的特点：只提供"尽力而为（Best-effort）"服务，不保证数据包一定到达，不保证顺序，需要 TCP 在上层弥补。

辅助协议

ICMP：报告错误（如"路由器丢包了"的通知）
IGMP：支持组播（一对多发送）
ARP：根据 IP 地址找 MAC 地址（数据链路层地址）

5.4 数据链路层（Data Link Layer）

作用：负责节点到节点（相邻两台设备之间）的帧传输。
网络层负责端到端（源到目的），数据链路层只负责相邻两跳之间的一段。

MAC 地址（物理地址）

数据链路层用 MAC 地址 标识设备：

以太网 MAC 地址：48位，6组16进制
格式：07:01:02:11:2C:5B

帧的传递过程

A ——(帧1: A->R1)——> R1 ——(帧2: R1->R4)——> R4 ——(帧3: R4->D)——> D

每一跳的帧头（源/目标MAC地址）都不同，但里面包的 IP 包（源/目标IP）全程不变。
类比：寄信时，外面的信封（MAC）每经过一个邮局换一个，但信里的内容（IP层）始终是同一封信。

5.5 物理层（Physical Layer）

作用：把一串比特（0和1）转化成电信号/光信号/无线电波在物理介质上传输。

传输单位：比特（bit）
不需要地址（信号会广播到所有连接的设备，由上层过滤）

5.6 五层地址汇总

层	传输单位	地址类型	负责范围
应用层	消息（Message）	URL / 域名	进程间
传输层	段/数据报（Segment/Datagram）	端口号	进程到进程
网络层	数据包（Datagram/Packet）	IP地址	主机到主机
数据链路层	帧（Frame）	MAC地址	节点到节点
物理层	比特（Bit）	无	物理信号

六、互联网应用

6.1 电子邮件（Email）

电子邮件系统比想象中复杂，因为发送方和接收方不需要同时在线（存储转发机制）。

邮件系统架构

关键角色：

UA（用户代理）：邮件客户端软件（如 Outlook、Thunderbird）
MTA（消息传输代理）：负责发送和路由邮件，协议是 SMTP
MAA（消息访问代理）：负责从服务器下载邮件，协议是 POP3 或 IMAP
SMTP是"推"协议：Alice主动把邮件推送到服务器
POP3/IMAP是"拉"协议：Bob主动去服务器拉取邮件

邮件地址格式

alice@example.com
  |         |
本地部分  域名部分
（邮箱名）（邮件服务器域名）

两种收件协议对比

协议	全称	特点
POP3	邮局协议第3版	简单，只能下载到本地，服务器上删除
IMAP	互联网邮件访问协议	功能强，支持服务器文件夹管理、预览、搜索、部分下载

MIME（多用途互联网邮件扩展）

SMTP 只支持 7位 ASCII 文本，不能发图片、音频、中文等。
MIME 是一个"翻译器"，把非ASCII内容编码成ASCII发出去，收到后再解码回来：

用户写信（含图片）
    ↓
MIME 编码：图片→ASCII文本
    ↓
SMTP 发送纯ASCII
    ↓
对方 MIME 解码：ASCII文本→图片
    ↓
用户看到完整邮件

6.2 文件传输协议（FTP）

FTP 用于在两台电脑之间复制文件，特点是建立两条连接：

客户端                          服务器
用户界面
   |
控制进程 ——控制连接（命令通道）——> 控制进程
   |                              |
数据传输进程 ——数据连接（文件）——> 数据传输进程

控制连接：全程保持打开，传输命令（如"列目录"、“上传”、“下载”）
数据连接：每次传文件时打开，传完关闭
两种访问方式：
封闭 FTP：需要账号密码，只有授权用户才能访问
匿名 FTP：用户名填 anonymous，密码填 guest，公众可访问

6.3 远程登录（TELNET）

TELNET 允许用户登录到远程电脑，像在本地操作一样使用远程计算机的所有功能。
工作原理：

用户键盘输入
    ↓
本地终端驱动（不做解释）
    ↓
TELNET 客户端（转成 NVT 通用字符集）
    ↓
          ————网络————
    ↓
TELNET 服务器（NVT转回ASCII）
    ↓
伪终端驱动
    ↓
远程应用程序执行，结果原路返回

NVT（网络虚拟终端）：为了屏蔽不同操作系统的差异，所有键盘输入先统一转成 NVT 格式传输，到达服务器后再转成本地格式。

6.4 万维网（World Wide Web / WWW）

WWW 诞生于1989年，由蒂姆·伯纳斯-李（Tim Berners-Lee）在欧洲粒子物理实验室发明。
1993年，马克·安德森（Marc Andreessen）在伊利诺伊大学开发了第一个图形浏览器 Mosaic。
WWW 的核心思想：超文本（Hypertext），用链接把分散在全球各地的文档连在一起。

WWW 的三个核心组件

浏览器（Browser）：解析并显示网页
Web服务器（Web Server）：存储和提供网页
HTTP协议：浏览器和服务器之间的通信规则

浏览器结构

      用户操作（鼠标/键盘）
            |
         控制器
        /        \
   客户程序      解释器
  (HTTP/FTP)  (HTML/Java)
        \        /
        网络 / 文档显示

HTTP（超文本传输协议）

HTTP 是浏览器和服务器对话的语言：

浏览器 ——[GET /index.html]——> 服务器
浏览器 <——[200 OK + 网页内容]—— 服务器

URL 格式

方法 :// 主机名 : 端口 / 路径
http  ://  www.example.com : 80 / index.html

字段	含义	示例
方法	使用的协议	http, https, ftp
主机名	服务器名称	www.example.com
端口	可选，默认80	8080
路径	文件在服务器上的位置	/docs/page.html

三种网页文档类型

静态文档：事先写好，像一张印好的传单，人人看到一样的
动态文档：每次请求时服务器现生成，像点餐系统根据库存实时生成菜单
活动文档：下载一段程序在你的浏览器里跑，像下载一个小游戏在本地玩

HTML 简介

HTML（超文本标记语言）用"标签"控制格式：

<HTML>
  <HEAD>
    <TITLE>页面标题</TITLE>

  </HEAD>

  <BODY>
    <H1>这是大标题</H1>

    <H2>这是二级标题</H2>

    <LI>列表项目1</LI>

    <A HREF="other.html">这是超链接，点击跳转</A>

  </BODY>

</HTML>

为什么用 HTML 而不用 Word？ 因为不同系统的 Word 格式不兼容，而 HTML 是纯 ASCII 文本，任何系统都能读取和显示。

XML vs HTML 对比

对比项	HTML	XML
标签来源	预定义固定标签	用户自己定义标签
标签含义	定义格式（如"这是列表项"）	定义内容类型（如"这是课程名"）
用途	控制网页显示外观	描述数据含义，方便搜索和处理
示例	`<LI>Computer Science</LI>`	`<Course>Computer Science</Course>`

6.5 其他互联网应用

视频会议（Videoconferencing）

参与者A ——视频音频——> 视频会议服务器 ——> 参与者B
参与者C <—————————————————————————————————

服务器接收所有参与者的视频音频，再分发给所有人。

列表服务器（Listserv / 群组讨论）

服务器上运行两个程序：

订阅服务器（Subscriber Server）：管理成员加入/退出
邮件服务器（Mailer Server）：把任意成员发来的邮件转发给所有成员

订阅：发 SUBSCRIBE 邮件到订阅服务器
发帖：发邮件到邮件服务器（自动转发给所有成员）
退订：发 UNSUBSCRIBE 邮件到订阅服务器

聊天（Chat）

实时文字（可含音视频）交流，和视频会议原理相似但规模更小，数据通过服务器中转，延迟很小。

七、一封邮件从发送到接收的完整旅程

下面用邮件"Alice发给Bob"来串联所有五层：

Alice写邮件：
  "Hi Bob, 明天开会"
[应用层] SMTP客户端把邮件格式化
          + 添加 To: Bob@bob.com  From: Alice@alice.com
[传输层] TCP 把邮件分段
          + 源端口(临时) 目标端口25(SMTP)
          + 序号、确认号、校验和
[网络层] IP 封装
          + 源IP: Alice的电脑IP
          + 目标IP: Bob邮件服务器IP
[数据链路层] 以太网帧封装
          + 源MAC: Alice的网卡地址
          + 目标MAC: 本地路由器的MAC地址
[物理层] 转成电信号，通过网线传到路由器
路由器收到后：
  去掉帧头（数据链路层）→ 查路由表 → 换上新帧头 → 继续发
最终到达Bob的邮件服务器，逆向拆包
Bob用POP3/IMAP取信阅读

八、C++ 代码示例：IP 地址转换工具

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <bitset>
#include <stdexcept>
// ============================================================
// IP地址转换工具（教学演示）
// 功能：
//   1. 点分十进制 → 32位二进制字符串
//   2. 32位二进制字符串 → 点分十进制
//   3. 验证 IP 地址格式合法性
// ============================================================
// ------------------------------------------------------------
// 把一个十进制整数转成8位二进制字符串
// 例如：10 → "00001010"
// ------------------------------------------------------------
std::string decToBin8(int decimal) {
    // bitset<8> 自动转成8位二进制
    return std::bitset<8>(decimal).to_string();
}
// ------------------------------------------------------------
// 把8位二进制字符串转成十进制整数
// 例如："00001010" → 10
// ------------------------------------------------------------
int bin8ToDec(const std::string& bin) {
    return std::bitset<8>(bin).to_ulong();
}
// ------------------------------------------------------------
// 把点分十进制 IP 地址 → 32位二进制字符串
// 例如："10.25.172.15" → "00001010000110011010110000001111"
// ------------------------------------------------------------
std::string ipDottedToBinary(const std::string& ip) {
    std::istringstream ss(ip);
    std::string segment;
    std::string result = "";
    while (std::getline(ss, segment, '.')) {
        int value = std::stoi(segment);
        // 验证每段在 0~255 之间
        if (value < 0 || value > 255) {
            throw std::invalid_argument("IP段超出范围 0-255: " + segment);
        }
        result += decToBin8(value); // 每段转成8位二进制拼接
    }
    return result;
}
// ------------------------------------------------------------
// 把32位二进制字符串 → 点分十进制 IP 地址
// 例如："00001010000110011010110000001111" → "10.25.172.15"
// ------------------------------------------------------------
std::string ipBinaryToDotted(const std::string& binary) {
    if (binary.length() != 32) {
        throw std::invalid_argument("二进制字符串必须是32位");
    }
    std::string result = "";
    for (int i = 0; i < 4; i++) {
        // 每8位切一段
        std::string octet = binary.substr(i * 8, 8);
        int value = bin8ToDec(octet);
        result += std::to_string(value);
        if (i < 3) result += "."; // 中间加点，最后一段不加
    }
    return result;
}
// ------------------------------------------------------------
// 把32位二进制字符串以分组形式打印（每8位一组）
// "00001010000110011010110000001111"
// → "00001010 00011001 10101100 00001111"
// ------------------------------------------------------------
std::string formatBinary(const std::string& binary) {
    std::string result = "";
    for (int i = 0; i < 4; i++) {
        result += binary.substr(i * 8, 8);
        if (i < 3) result += " ";
    }
    return result;
}
// ------------------------------------------------------------
// 验证点分十进制格式是否合法（4段，每段0-255）
// ------------------------------------------------------------
bool isValidIP(const std::string& ip) {
    std::istringstream ss(ip);
    std::string segment;
    int count = 0;
    while (std::getline(ss, segment, '.')) {
        count++;
        if (count > 4) return false;
        // 检查是否为数字
        for (char c : segment) {
            if (!isdigit(c)) return false;
        }
        int value = std::stoi(segment);
        if (value < 0 || value > 255) return false;
    }
    return count == 4; // 必须恰好4段
}
int main() {
    std::cout << "=== IP 地址转换工具（TCP/IP 教学演示）===" << std::endl;
    std::cout << std::endl;
    // ── 演示1：点分十进制 → 二进制 ─────────────────────────
    std::vector<std::string> ips = {
        "10.25.172.15",   // 书中例子
        "192.168.1.1",    // 常见局域网地址
        "255.255.255.255" // 广播地址
    };
    std::cout << "【点分十进制 → 32位二进制】" << std::endl;
    std::cout << "--------------------------------------------" << std::endl;
    for (const auto& ip : ips) {
        std::string binary = ipDottedToBinary(ip);
        std::cout << "IP  : " << ip << std::endl;
        std::cout << "二进制: " << formatBinary(binary) << std::endl;
        std::cout << "原始: " << binary << std::endl;
        std::cout << std::endl;
    }
    // ── 演示2：二进制 → 点分十进制 ─────────────────────────
    std::cout << "【32位二进制 → 点分十进制】" << std::endl;
    std::cout << "--------------------------------------------" << std::endl;
    // 对应书中 P6-10 的题目
    std::vector<std::string> binaries = {
        "01111110111100010110011101111111",   // a
        "10111111110111001110000000000101",   // b
        "00011111111100000011111111011101"    // c
    };
    for (const auto& bin : binaries) {
        std::cout << "二进制: " << formatBinary(bin) << std::endl;
        std::cout << "IP  : " << ipBinaryToDotted(bin) << std::endl;
        std::cout << std::endl;
    }
    // ── 演示3：计算子网地址数量 ────────────────────────────
    // IPv4 的最大地址数 = 2^32
    // IPv6 的最大地址数 = 2^128（极大，无法穷举）
    std::cout << "【IPv4 vs IPv6 地址容量】" << std::endl;
    std::cout << "--------------------------------------------" << std::endl;
    // IPv4：32位，最多 2^32 个地址
    // 用 unsigned long long 计算（64位整数）
    unsigned long long ipv4Max = 1ULL << 32; // 即 4,294,967,296 ≈ 43亿
    std::cout << "IPv4 (32位) 最大地址数 = 2^32 = "
              << ipv4Max << " 约 43亿" << std::endl;
    std::cout << "IPv6 (128位) 最大地址数 = 2^128，"
              << "约 3.4 × 10^38，实际无法穷举" << std::endl;
    std::cout << std::endl;
    // ── 演示4：用户交互 ─────────────────────────────────────
    std::cout << "【自行测试】" << std::endl;
    std::cout << "请输入一个点分十进制 IP 地址（如 192.168.1.1）: ";
    std::string userIP;
    std::cin >> userIP;
    if (isValidIP(userIP)) {
        std::string binary = ipDottedToBinary(userIP);
        std::cout << "二进制: " << formatBinary(binary) << std::endl;
        // 验证反向转换
        std::string back = ipBinaryToDotted(binary);
        std::cout << "反向验证: " << back << std::endl;
    } else {
        std::cout << "输入的 IP 地址格式不合法，请检查。" << std::endl;
    }
    return 0;
}

编译和运行：

g++ -o ip_tool ip_tool.cpp
./ip_tool

预期输出（部分）：

=== IP 地址转换工具（TCP/IP 教学演示）===
【点分十进制 → 32位二进制】
--------------------------------------------
IP  : 10.25.172.15
二进制: 00001010 00011001 10101100 00001111
原始: 00001010000110011010110000001111
IP  : 192.168.1.1
二进制: 11000000 10101000 00000001 00000001
【IPv4 vs IPv6 地址容量】
IPv4 (32位) 最大地址数 = 2^32 = 4294967296 约 43亿
IPv6 (128位) 最大地址数 = 2^128，约 3.4 × 10^38，实际无法穷举

九、核心概念速查表

概念	一句话解释
网络（Network）	多台设备用线连起来共享资源
LAN	局域网，一栋楼/校园内
WAN	广域网，跨国跨洲
MAN	城域网，城市范围
internet（小写）	多个网络互连
Internet（大写）	全球那个互联网
ISP	互联网服务提供商
路由器	在不同网络之间转发数据包
TCP/IP	控制互联网的协议套件，5层结构
IP地址	网络层的设备地址，32位（IPv4）
端口号	传输层区分不同服务，如80=HTTP
MAC地址	数据链路层的硬件地址，48位
URL	统一资源定位符，网页地址
DNS	把域名翻译成IP地址
HTTP	浏览器和服务器通信的协议
SMTP	发送邮件的协议（推）
POP3/IMAP	接收邮件的协议（拉）
MIME	让邮件能发非ASCII内容（图片等）
FTP	文件传输协议，两条连接
TELNET	远程登录协议
HTML	制作网页的标记语言
XML	描述数据类型的标记语言
静态文档	提前写好的网页
动态文档	服务器请求时生成的网页
活动文档	在客户端运行的程序（如JavaScript）
UDP	快但不可靠的传输协议
TCP	可靠但稍慢的传输协议
封装	每层给数据加信封头

第七章：操作系统（Operating Systems）从零理解

一、什么是操作系统？

计算机软件分两大类：

计算机软件
├── 操作系统（Operating System）
│     管理硬件，为其他程序服务
└── 应用程序（Application Programs）
      解决用户具体问题（Word、游戏、浏览器…）

操作系统可以从三个角度理解：

接口视角：操作系统是硬件和用户之间的"翻译官"，用户不用直接和硬件打交道
服务视角：操作系统是一个"管家"，帮助其他程序顺利运行
管理视角：操作系统是"总经理"，监督并协调所有硬件和软件资源的使用，发生冲突时进行仲裁
操作系统的两大设计目标：

高效利用硬件（让 CPU、内存、磁盘不闲着）
方便用户使用资源（用户不必了解底层细节）

二、引导过程（Bootstrap）

问题： 操作系统是程序，程序要运行必须先加载进内存。但谁来加载操作系统呢？
解决方案：两阶段引导

电源接通
    |
    v
CPU 自动读取 ROM 中的引导程序（Bootstrap Program）
    |
    v
引导程序把操作系统从磁盘加载到 RAM
    |
    v
CPU 跳转到操作系统的第一条指令，开始运行

ROM：存放引导程序，小而固定，不会因断电丢失
RAM：存放操作系统主体，断电清空，但速度快
类比：引导程序就像一把"钥匙"，开机时用它把操作系统这个"主人"请进来，之后主人接管一切。

三、操作系统的发展历史

时代	名称	特点	代表
1950s	批处理系统	一次只跑一个程序，穿孔卡片输入	早期大型机
1960s	分时系统	多程序共享CPU，每人感觉独占	UNIX
1970-80s	个人系统	单用户，个人电脑	DOS
1980s	并行系统	多个CPU同时工作	多处理器服务器
1990s	分布式系统	多台电脑联网协同工作	互联网服务
任意	实时系统	必须在规定时间内完成任务	汽车控制、医疗监控

关键概念区别：

作业（Job）：被选中等待运行的程序
进程（Process）：已加载进内存、正在运行或等待CPU的程序
时间共享（Time Sharing）：CPU轮流给每个程序一小段时间，切换足够快时每个用户感觉自己独占

四、操作系统的四大组件

五、内存管理器（Memory Manager）

5.1 单道程序（Monoprogramming）

内存里同时只有一个程序：

+--------------------+
|    操作系统        |
+--------------------+
|                    |
|    当前程序        |
|                    |
+--------------------+

缺点：

程序必须完整放入内存，大程序无法运行
程序做 I/O 时 CPU 空闲，极大浪费
CPU 利用率计算（P7-3 类型题）：
若程序平均需要 $10\mu s$ 的 CPU 时间， $70\mu s$ 的 I/O 时间，则：
$\text{CPU利用率} = \frac{10}{10+70} = \frac{10}{80} = 12.5\%$
$\text{CPU空闲率} = \frac{70}{80} = 87.5\%$

5.2 多道程序（Multiprogramming）

内存里同时放多个程序，CPU 在它们之间快速切换：

+--------------------+
|    操作系统        |
+--------------------+
|    程序 1          |
+--------------------+
|    程序 2          |
+--------------------+
|    程序 3          |
+--------------------+

多道程序的演进路线：

5.2.1 分区（Partitioning）

把内存切成若干块，每块放一个程序：

+--------------------+
|    操作系统        |
+--------------------+  ← 分区1（10MB）
|    程序 1（9MB）   |
+--------------------+  ← 分区2（12MB）
|    程序 2（10MB）  |
| [空洞 2MB]         |
+--------------------+  ← 分区3（20MB）
|    程序 3（17MB）  |
| [空洞 3MB]         |
+--------------------+

缺点：

分区大小难以预设（太小放不下、太大有空洞）
运行一段时间后会出现很多碎片空洞
内存压缩（消除空洞）需要额外开销
分区浪费计算（P7-4 类型题）：
设分区大小为 $P_i$ ，程序实际需要 $R_i$ ，则：
$\text{浪费} = \sum_{i}(P_i - R_i)$
$\text{浪费百分比} = \frac{\text{总浪费}}{\text{总内存}} \times 100\%$

5.2.2 分页（Paging）

把内存分成等大的帧（Frame），程序也分成等大的页（Page），页装入帧，不必连续：

程序A：页1 页2 页3        内存：
程序B：页1 页2      →    帧1: 程序B的页2
程序C：页1 页2            帧2: 程序A的页1
                          帧3: 程序C的页1
                          帧4: 程序A的页3
                          帧5: 程序A的页2
                          帧6: 程序C的页2
                          帧7: 程序B的页1

优点：不需要连续内存，消除了大空洞
缺点：整个程序必须全部在内存才能执行
帧使用计算（P7-6 类型题）：
设帧大小为 $F$ ，程序大小为 $S$ ，则需要的帧数：
$\text{帧数} = \lceil S / F \rceil \quad \text{（向上取整）}$
最后一帧可能未完全用满，浪费：
$\text{最后一帧浪费} = \lceil S/F \rceil \times F - S$

5.2.3 请求分页（Demand Paging）

不需要把整个程序加载进内存，用哪页调哪页，其余页留在磁盘：

程序A的全部页（磁盘）：页1 页2 页3 页4 页5 页6
                              ↓ 按需加载
内存中：帧1[A-页2]  帧2[B-页1]  帧3[A-页5]  帧4[C-页1]

这是**虚拟内存（Virtual Memory）**的基础。

5.2.4 请求分段（Demand Segmentation）

按程序的逻辑模块（主程序、子程序）分段，按需加载：

程序A结构：         内存中的段：
  主程序             段1: A的主程序
  子程序1            段2: A的子程序1（部分空）
  子程序2            段3: B的主程序

5.2.5 虚拟内存（Virtual Memory）

请求分页和请求分段实现了虚拟内存：物理内存有限，但程序"感觉"内存很大。
举例：
$\text{物理内存} = 10\text{MB}，\text{同时运行10个各}3\text{MB的程序}$
$\text{虚拟内存} = 10 \times 3 = 30\text{MB}$
任意时刻只有 10MB 在物理内存，另外 20MB 在磁盘上"待命"。

虚拟内存（30MB）：
[程序1全部][程序2全部][程序3全部]...[程序10全部]
      ↕ 按需换入换出
物理内存（10MB）：
[程序1的部分页][程序3的部分页][程序7的部分页]...

六、进程管理器（Process Manager）

6.1 程序、作业、进程的区别

概念	位置	状态	说明
程序（Program）	磁盘	静止	存储在磁盘上的指令集合
作业（Job）	磁盘或内存	等待被处理	被OS选中后成为作业
进程（Process）	内存	运行或等待CPU	已加载进内存的作业

关系：每个进程都是作业，每个作业都是程序，反过来不一定。

6.2 进程状态图

五种状态详解：

挂起（Hold）：被选中但还没进内存，在磁盘等候区排队
就绪（Ready）：已在内存，等 CPU 来执行
运行（Running）：CPU 正在执行它的指令
等待（Waiting）：请求了 I/O，CPU 去执行别的程序，等 I/O 结束后重回就绪
终止（Terminated）：执行完毕，退出进程状态，回到磁盘变回程序

6.3 调度器（Schedulers）

两种调度器分工明确：

作业调度器（Job Scheduler）：
  Hold ──────────────────────> Ready  （把程序装进内存）
  Running ────────────────────> Terminated  （执行完，清理内存）
进程调度器（Process Scheduler）：
  Ready ──────────────────────> Running  （分配CPU）
  Running ────────────────────> Waiting  （等I/O）
  Waiting ────────────────────> Ready   （I/O完成）
  Running ────────────────────> Ready   （时间片到期）

6.4 队列（Queues）

多个进程竞争资源时，用队列管理等待顺序：

新作业
  |
  v
[作业队列] ──> 作业调度器 ──> [就绪队列] ──> 进程调度器 ──> CPU执行
                                  ^                              |
                                  |         时间片到期          |
                                  +<────────────────────────────+
                                  |         I/O完成             |
                                  +<────────────────────────────+
                                                                 |
                                                          请求I/O|
                                                                 v
                                                          [I/O队列] ──> I/O设备

队列调度策略：

FIFO：先来先服务
最短作业优先：预计运行时间短的先跑
优先级调度：级别高的先跑

6.5 死锁（Deadlock）

什么是死锁？ 两个或多个进程互相持有对方需要的资源，谁都不肯先放手，导致永远无法推进。
经典例子：

进程A 持有 File1，需要 File2
进程B 持有 File2，需要 File1
  File1
  ↑被A持有    ↖A请求
   A ────────────> File2
   ↑                ↑被B持有
   B请求           B
   ↓                |
  File2 <───────── B

类比：两辆车在单车道桥上相遇，谁都不肯后退，永远堵死。
死锁发生的四个必要条件（四个条件同时满足才会发生）：

预防死锁：破坏任意一个条件即可。常见方法：

限制进程持有资源的时间
要求进程运行前一次性获取所有需要的资源

6.6 饥饿（Starvation）

什么是饥饿？ 死锁的反面——OS 对进程限制过多，导致某个进程一直无法获取所需资源，永远等待。
经典例子（哲学家就餐问题）：
5位哲学家围坐一桌，每人需要左右两根筷子才能吃饭，但筷子是共享的：

          哲学家A
         /      \
      筷子1    筷子5
      /              \
哲学家E              哲学家B
      \              /
      筷子4    筷子2
         \      /
          哲学家D ── 筷子3 ── 哲学家C

若每位哲学家同时拿起左边的筷子，就没有人能拿到右边的筷子，所有人都在等待，发生饥饿（或死锁）。

死锁 vs 饥饿对比：

对比项	死锁（Deadlock）	饥饿（Starvation）
原因	OS 对资源限制太少，进程互相等待	OS 对资源限制太多，进程一直无法启动
涉及进程数	至少2个相互等待	可以只有1个受害者
是否能自行解决	不能，需要外部干预	可能随时间自行解决，也可能永久等待
解决思路	破坏四个必要条件之一	给等待进程设置优先级或超时

七、设备管理器（Device Manager）

设备管理器（也叫 I/O 管理器）负责管理键盘、鼠标、打印机、磁盘等 I/O 设备。
主要职责：

监控：持续检查设备工作状态，知道设备何时空闲
维护队列：每个设备维护一个等待队列
调度策略：决定哪个进程先用设备（FIFO、最短作业优先等）
类比：打印机队列——多人同时发送打印任务，设备管理器按规则排队处理，而不是乱成一团。

八、文件管理器（File Manager）

文件管理器控制文件的一切：

访问控制：谁能读？谁能写？谁能执行？
文件生命周期：创建、修改、删除
命名管理：文件名规则
存储管理：文件存在磁盘哪里，怎么存
备份归档：定期备份重要数据
类比：公司的档案室管理员，负责文件的出借、归还、新建、销毁，并记录谁有权限查阅哪些文件。

九、三大操作系统简介

9.1 UNIX

诞生时间：1969年，Bell 实验室，Thomson 和 Ritchie 开发
主要用 C 语言编写（而非机器语言），因此可移植到不同硬件平台
UNIX 三大特点：

可移植：用 C 写的，换平台改动很少
强大的工具集：数百个小命令可组合成脚本解决复杂任务
设备无关：内置设备驱动，容易支持新硬件
UNIX 结构（从外到内）：

用户
  |
Shell（命令行界面，接受并解释用户命令）
  |
工具集 Utilities（ls、vi、emacs、email等标准程序）
  |
应用程序 Applications（非标准的第三方程序）
  |
Kernel（内核：内存/进程/设备/文件管理的核心）
  |
硬件

9.2 Linux

诞生时间：1991年，芬兰学生 Linus Torvalds 开发
基于 UNIX 思想，完全开源免费
Linux 组件：

组件	作用
内核（Kernel）	内存/进程/设备/文件管理
系统库（System Libraries）	应用程序调用内核的接口函数
系统工具（System Utilities）	各种管理工具程序
网络支持	内置 TCP/IP 等网络协议
安全机制	认证和访问控制

9.3 Windows NT/2000/XP

诞生时间：1980年代末，微软 Dave Cutler 主导开发
NT = New Technology
设计目标： 可扩展性、可移植性、可靠性、兼容性、高性能
Windows NT 分层架构（从下到上）：

+------------------------------------------+
|     应用程序  环境子系统（用户模式）       |
|     （Win32 / 其他OS兼容子系统）           |
+------------------------------------------+
|              执行体 Executive             |
|  [对象管理] [安全监控] [进程管理]         |
|  [虚拟内存] [本地调用] [I/O管理]          |
+------------------------------------------+
|            内核 Kernel（核心模式）        |
+------------------------------------------+
|   硬件抽象层 HAL（Hardware Abstraction）  |
+------------------------------------------+
|                  硬件                    |
+------------------------------------------+

HAL（硬件抽象层）：把硬件差异隐藏起来，上层软件不用关心具体是哪种 CPU 或主板。

三大OS对比：

对比项	UNIX	Linux	Windows NT
诞生时间	1969	1991	1980s末
开发者	Bell Labs	Linus Torvalds	微软
开源	否（多版本）	是	否
编写语言	C	C	C/C++
多用户	是	是	是
内核类型	宏内核	宏内核	分层内核
主要用途	服务器/工作站	服务器/个人	个人/企业桌面

十、习题解析

P7-1：单道程序最大程序大小

内存 64MB，OS 占 4MB：
$\text{最大程序大小} = 64 - 4 = 60\text{ MB}$

P7-2：OS 额外分配 10MB 给数据

$\text{最大程序大小} = 64 - 4 - 10 = 50\text{ MB}$

P7-3：单道程序 CPU 空闲率

程序需要 CPU $10\mu s$ ，I/O $70\mu s$ ：
$\text{CPU空闲率} = \frac{70}{10+70} = \frac{70}{80} = 87.5\%$

P7-4：分区方案浪费计算

60MB 内存分4个分区：10MB、12MB、18MB、20MB

分区	大小	程序需求	浪费
分区1	10MB	8MB	2MB
分区2	12MB	10.5MB	1.5MB
分区3	18MB	17MB	1MB
分区4	20MB	20MB	0MB
合计	60MB	55.5MB	4.5MB

$\text{浪费百分比} = \frac{4.5}{60} \times 100\% = 7.5\%$

P7-6：分页帧使用计算

60MB 内存，15个帧，每帧 4MB：
程序1需 13MB： $\lceil 13/4 \rceil = 4$ 帧，浪费 $\times 4 - 13 = 3$ MB
程序2需 12MB： $\lceil 12/4 \rceil = 3$ 帧，浪费 $0$ MB
程序3需 27MB： $\lceil 27/4 \rceil = 7$ 帧，浪费 $\times 4 - 27 = 1$ MB
合计： $4 + 3 + 7 = 14$ 帧，剩余 $15 - 14 = 1$ 帧未用，总浪费 $3 + 0 + 1 = 4$ MB
$\text{浪费百分比} = \frac{4}{60} \times 100\% \approx 6.67\%$

P7-9：三进程死锁判断

进程A持有File1，需要File2；进程B持有File3，需要File1；进程C持有File2，需要File3：

A ─持有─> File1 <─需要─ B
A ─需要─> File2 <─持有─ C
B ─需要─> File3 <─持有─ C
（C 需要 File3？不，C持有File2，需要File3... 等等）

重新整理：

进程A：持有File1 → 需要File2
进程B：持有File3 → 需要File1
进程C：持有File2 → 需要File3
循环：A等C(File2)，C等B(File3)，B等A(File1)
         ↑___________________________|

这是一个环形等待，发生死锁。

P7-10：三进程是否死锁

进程A持有File1（不需要其他）；进程B持有File2，需要File1；进程C持有File3，需要File2：

A ─持有─> File1 <─需要─ B
B ─持有─> File2 <─需要─ C
C ─持有─> File3
（A不需要任何其他资源）

没有死锁，因为没有形成循环：

A执行完，释放File1
B获得File1，执行完，释放File1和File2
C获得File2，执行完，释放所有

十一、C++ 代码：进程状态模拟器

#include <iostream>
#include <string>
#include <queue>
#include <vector>
// ============================================================
// 进程状态模拟器
// 模拟第七章描述的进程状态转换：
//   Hold -> Ready -> Running -> (Waiting/Terminated)
//   Waiting -> Ready
// ============================================================
// ------------------------------------------------------------
// 进程状态枚举
// ------------------------------------------------------------
enum class State {
    HOLD,       // 挂起：被选中但还没进内存
    READY,      // 就绪：在内存中等待CPU
    RUNNING,    // 运行：CPU正在执行
    WAITING,    // 等待：正在等待I/O
    TERMINATED  // 终止：执行完毕
};
// ------------------------------------------------------------
// 把状态枚举转成中文字符串（方便打印）
// ------------------------------------------------------------
std::string stateToString(State s) {
    switch (s) {
        case State::HOLD:       return "挂起(Hold)";
        case State::READY:      return "就绪(Ready)";
        case State::RUNNING:    return "运行(Running)";
        case State::WAITING:    return "等待(Waiting)";
        case State::TERMINATED: return "终止(Terminated)";
        default:                return "未知";
    }
}
// ------------------------------------------------------------
// 进程控制块（PCB, Process Control Block）
// 操作系统用它记录每个进程的信息
// ------------------------------------------------------------
struct Process {
    int id;             // 进程唯一编号
    std::string name;   // 进程名称
    State state;        // 当前状态
    int cpuBurst;       // 还需要多少个CPU时间片
    int ioBurst;        // 还需要等多少个I/O时间单位
    int waitCount;      // 已等待的时间片数（用于分析饥饿）
    // 构造函数
    Process(int i, const std::string& n, int cpu, int io)
        : id(i), name(n), state(State::HOLD),
          cpuBurst(cpu), ioBurst(io), waitCount(0) {}
};
// ------------------------------------------------------------
// 打印进程当前状态
// ------------------------------------------------------------
void printProcess(const Process& p) {
    std::cout << "  进程[" << p.id << "] " << p.name
              << "  状态: " << stateToString(p.state)
              << "  剩余CPU时间: " << p.cpuBurst
              << "  剩余I/O等待: " << p.ioBurst
              << "  已等待: " << p.waitCount
              << std::endl;
}
// ------------------------------------------------------------
// 简单进程调度器模拟
// 演示进程在各状态之间的转换
// ------------------------------------------------------------
void simulate(std::vector<Process>& processes) {
    // 用队列管理各状态的进程
    std::queue<int> holdQueue;   // 挂起队列（存进程id）
    std::queue<int> readyQueue;  // 就绪队列
    std::queue<int> waitQueue;   // 等待I/O队列
    int runningId = -1; // 当前正在运行的进程id，-1表示CPU空闲
    // 所有进程初始在Hold状态，加入挂起队列
    for (auto& p : processes) {
        holdQueue.push(p.id);
    }
    std::cout << "\n=== 开始模拟进程调度 ===" << std::endl;
    // 模拟最多30个时间步
    for (int tick = 1; tick <= 30; tick++) {
        std::cout << "\n--- 时间步 " << tick << " ---" << std::endl;
        // ── 步骤1：作业调度器：Hold -> Ready（每步最多1个进入内存）──
        if (!holdQueue.empty()) {
            int pid = holdQueue.front();
            holdQueue.pop();
            processes[pid].state = State::READY;
            readyQueue.push(pid);
            std::cout << "  [作业调度] 进程[" << pid << "]"
                      << processes[pid].name
                      << " 加载进内存 -> 就绪" << std::endl;
        }
        // ── 步骤2：等待队列 -> 就绪（I/O完成） ────────────────────
        // 简化：等待1步后I/O完成
        std::queue<int> stillWaiting;
        while (!waitQueue.empty()) {
            int pid = waitQueue.front();
            waitQueue.pop();
            processes[pid].ioBurst--;
            if (processes[pid].ioBurst <= 0) {
                // I/O完成，移回就绪队列
                processes[pid].state = State::READY;
                readyQueue.push(pid);
                std::cout << "  [I/O完成] 进程[" << pid << "]"
                          << processes[pid].name
                          << " I/O结束 -> 就绪" << std::endl;
            } else {
                stillWaiting.push(pid); // 继续等待
            }
        }
        waitQueue = stillWaiting;
        // ── 步骤3：进程调度器：Running -> Waiting/Terminated/Ready ─
        if (runningId != -1) {
            Process& rp = processes[runningId];
            rp.cpuBurst--;
            if (rp.cpuBurst <= 0) {
                // CPU时间用完，检查是否需要I/O
                if (rp.ioBurst > 0) {
                    // 还有I/O需求 -> 等待状态
                    rp.state = State::WAITING;
                    waitQueue.push(runningId);
                    std::cout << "  [进程调度] 进程[" << runningId << "]"
                              << rp.name << " CPU完成，需要I/O -> 等待"
                              << std::endl;
                } else {
                    // 全部完成 -> 终止
                    rp.state = State::TERMINATED;
                    std::cout << "  [进程调度] 进程[" << runningId << "]"
                              << rp.name << " 执行完毕 -> 终止"
                              << std::endl;
                }
                runningId = -1; // CPU空闲
            } else {
                // 时间片到期（简化：每步给一个时间片）
                rp.state = State::READY;
                readyQueue.push(runningId);
                std::cout << "  [进程调度] 进程[" << runningId << "]"
                          << rp.name << " 时间片到期 -> 就绪"
                          << std::endl;
                runningId = -1;
            }
        }
        // ── 步骤4：进程调度器：Ready -> Running ─────────────────────
        if (runningId == -1 && !readyQueue.empty()) {
            runningId = readyQueue.front();
            readyQueue.pop();
            processes[runningId].state = State::RUNNING;
            std::cout << "  [进程调度] 进程[" << runningId << "]"
                      << processes[runningId].name
                      << " 获得CPU -> 运行" << std::endl;
        }
        // ── 显示所有进程当前状态 ─────────────────────────────────────
        std::cout << "  当前所有进程状态：" << std::endl;
        for (const auto& p : processes) {
            printProcess(p);
        }
        // ── 检查是否所有进程都终止了 ─────────────────────────────────
        bool allDone = true;
        for (const auto& p : processes) {
            if (p.state != State::TERMINATED) {
                allDone = false;
                break;
            }
        }
        if (allDone) {
            std::cout << "\n所有进程执行完毕！共用 "
                      << tick << " 个时间步。" << std::endl;
            return;
        }
    }
    std::cout << "\n模拟结束（达到最大时间步30）。" << std::endl;
}
// ------------------------------------------------------------
// 演示死锁检测（简化版）
// 判断进程和资源是否形成循环等待
// ------------------------------------------------------------
void demonstrateDeadlock() {
    std::cout << "\n=== 死锁演示（P7-9：三进程A/B/C）===" << std::endl;
    std::cout << "进程A：持有File1，需要File2" << std::endl;
    std::cout << "进程B：持有File3，需要File1" << std::endl;
    std::cout << "进程C：持有File2，需要File3" << std::endl;
    std::cout << std::endl;
    std::cout << "等待关系图：" << std::endl;
    std::cout << "  A ─等待─> C（需要File2，C持有File2）" << std::endl;
    std::cout << "  C ─等待─> B（需要File3，B持有File3）" << std::endl;
    std::cout << "  B ─等待─> A（需要File1，A持有File1）" << std::endl;
    std::cout << "  形成环路：A -> C -> B -> A" << std::endl;
    std::cout << "  结论：发生死锁！" << std::endl;
    std::cout << "\n=== P7-10：三进程A/B/C ===" << std::endl;
    std::cout << "进程A：持有File1（不需要其他资源）" << std::endl;
    std::cout << "进程B：持有File2，需要File1" << std::endl;
    std::cout << "进程C：持有File3，需要File2" << std::endl;
    std::cout << std::endl;
    std::cout << "等待关系图：" << std::endl;
    std::cout << "  B ─等待─> A（需要File1）" << std::endl;
    std::cout << "  C ─等待─> B（需要File2）" << std::endl;
    std::cout << "  A 不等待任何人" << std::endl;
    std::cout << "  无环路，结论：没有死锁！" << std::endl;
    std::cout << "  执行顺序：A完成 -> B获得File1完成 -> C获得File2完成" << std::endl;
}
int main() {
    std::cout << "=== 操作系统：进程状态模拟器 ===" << std::endl;
    std::cout << "(模拟第七章进程管理概念)" << std::endl;
    // 创建3个进程：
    // id, 名称, CPU时间片需求, I/O等待步数
    std::vector<Process> processes = {
        {0, "浏览器", 3, 2},  // 浏览器：需要3步CPU，2步I/O
        {1, "文本编辑", 2, 0}, // 文本编辑：需要2步CPU，无I/O
        {2, "文件下载", 2, 3}  // 文件下载：需要2步CPU，3步I/O
    };
    std::cout << "\n初始进程列表：" << std::endl;
    for (const auto& p : processes) {
        printProcess(p);
    }
    // 运行调度模拟
    simulate(processes);
    // 演示死锁
    demonstrateDeadlock();
    return 0;
}

编译和运行：

g++ -o os_sim os_sim.cpp
./os_sim

十二、核心概念速查表

概念	一句话解释
操作系统	硬件和用户之间的"管家"，管理所有资源
引导程序（Bootstrap）	开机时从ROM读取，把OS加载进RAM
批处理系统	1950年代，一次一个程序，穿孔卡片输入
分时系统	CPU轮流给多个程序，每人感觉独占
单道程序	内存同时只有一个程序，CPU利用率低
多道程序	内存同时多个程序，CPU切换执行
分区	内存分若干块，每块一个程序
分页	内存和程序都切成等大的帧/页，不要求连续
请求分页	按需调页，实现虚拟内存
虚拟内存	物理内存有限但程序感觉内存更大
程序	静止在磁盘上的指令集合
作业（Job）	被OS选中、待运行的程序
进程（Process）	在内存中正在执行或等待CPU的程序
就绪状态	在内存中，等CPU来执行
运行状态	CPU正在执行这个进程
等待状态	进程在等I/O，CPU去干别的
作业调度器	把程序从磁盘装进内存（Hold→Ready）
进程调度器	在就绪/运行/等待状态之间切换
死锁	进程互相持有对方需要的资源，永远等待
饥饿	进程始终无法获取资源而永远等待
哲学家就餐问题	经典饥饿/死锁演示
设备管理器	负责I/O设备的分配和调度
文件管理器	控制文件的访问权限和存储
UNIX	1969年，Bell Labs，多用户可移植OS
Linux	1991年，Torvalds，开源UNIX类OS
Windows NT	微软，分层架构，HAL隔离硬件
HAL	硬件抽象层，隐藏硬件差异
Shell	OS的命令行界面，解释用户命令
Kernel	OS的核心，管理内存/进程/设备/文件

第8章：算法（Algorithms）— 从零理解

8.1 算法的概念

8.1.1 什么是算法？

通俗定义：

算法就是"解决某个问题的一步一步的方法"。
就像你做菜需要按照菜谱一步步来，程序解决问题也需要按照固定步骤来。
算法有输入，有输出：

输入数据 → [算法：解决问题的步骤] → 输出数据

8.1.2 例子：找最大整数

目标： 在一堆正整数里，找出最大的那个。
思路： 挨个看每个数，随时记住"目前为止最大的数"。
比如有这5个数：12 8 13 9 11
步骤拆解：

初始：设 Largest = -∞（负无穷，比任何数都小）
第1步：看到 12，12 > -∞，所以 Largest = 12
第2步：看到 8， 8 < 12，Largest 不变，还是 12
第3步：看到 13，13 > 12，所以 Largest = 13
第4步：看到 9， 9 < 13，Largest 不变，还是 13
第5步：看到 11，11 < 13，Largest 不变，还是 13
最终输出：13

流程图（ASCII演示）：

开始
  |
  v
Largest = -∞
  |
  v
还有数字吗？ --否--> 输出 Largest --> 结束
  |
  是
  v
取下一个数 current
  |
  v
current > Largest？
  |是           |否
  v             v
Largest=current 不变
  |             |
  +------+------+
         |
         v
      (循环回去)

推广到 n 个数：
只需把"重复5次"改为"重复 n 次"，算法就通用了。

8.2 三种基本构造

计算机科学家证明，任何程序只需要用这三种结构组合，就能解决所有可解的问题。

8.2.1 顺序（Sequence）

就是一行一行按顺序执行，没有跳转。

执行动作1
执行动作2
执行动作3
...

8.2.2 判断/选择（Decision / Selection）

根据条件选择走哪条路。

如果 条件为真：
    执行一组动作A
否则：
    执行一组动作B

8.2.3 重复/循环（Repetition / Loop）

同一组动作重复执行，直到条件不满足为止。

当 条件为真 时：
    执行一组动作
    （执行完再检查条件，继续或退出）

三种结构总览（Mermaid图）：

8.3 算法的两种表示方式

8.3.1 UML图（统一建模语言）

UML是用图形来表示算法的方法，直观展示流程走向。

矩形框 = 动作
菱形框 = 判断（条件）
箭头 = 流程方向

8.3.2 伪代码（Pseudocode）

伪代码是介于自然语言和程序代码之间的一种写法，不是真正的代码，但结构像代码。
三种结构的伪代码写法：

// 顺序
动作1
动作2
动作n
// 判断
if (条件)
{
    为真时的动作
}
else
{
    为假时的动作
}
// 循环
while (条件)
{
    重复执行的动作
}

例题详解

例题8.1：求两个整数之和

只需要用"顺序"结构：

算法：SumOfTwo(first, second)
目的：求两个整数之和
输入：两个整数 first 和 second
返回：它们的和
{
    sum ← first + second   // 把两数相加，存入sum
    return sum              // 返回sum
}

C++ 完整代码：

#include <iostream>
using namespace std;
// 求两个整数之和
int SumOfTwo(int first, int second) {
    int sum = first + second;  // 相加
    return sum;                // 返回结果
}
int main() {
    int a, b;
    cout << "请输入两个整数：";
    cin >> a >> b;
    cout << "它们的和是：" << SumOfTwo(a, b) << endl;
    return 0;
}

例题8.2：判断是否及格

需要用"判断"结构：

算法：Pass/NoPass(score)
目的：把数字分数转成及格/不及格
{
    if (score >= 70)
        grade ← "pass"     // 70分及以上：及格
    else
        grade ← "nopass"   // 70分以下：不及格
    return grade
}

C++ 完整代码：

#include <iostream>
#include <string>
using namespace std;
// 判断是否及格
string PassOrNoPass(int score) {
    if (score >= 70)
        return "pass";    // 及格
    else
        return "nopass";  // 不及格
}
int main() {
    int score;
    cout << "请输入分数（0-100）：";
    cin >> score;
    cout << "结果：" << PassOrNoPass(score) << endl;
    return 0;
}

例题8.3：转换字母等级

需要多个判断：

算法：LetterGrade(score)
目的：把数字分数转成字母等级 A/B/C/D/F
{
    if (100 >= score >= 90)  grade ← 'A'
    if (89 >= score >= 80)   grade ← 'B'
    if (79 >= score >= 70)   grade ← 'C'
    if (69 >= score >= 60)   grade ← 'D'
    if (59 >= score >= 0)    grade ← 'F'
    return grade
}

C++ 完整代码：

#include <iostream>
using namespace std;
// 将数字分数转换为字母等级
char LetterGrade(int score) {
    if (score >= 90 && score <= 100) return 'A';
    if (score >= 80 && score <= 89)  return 'B';
    if (score >= 70 && score <= 79)  return 'C';
    if (score >= 60 && score <= 69)  return 'D';
    return 'F';  // 60分以下
}
int main() {
    int score;
    cout << "请输入分数（0-100）：";
    cin >> score;
    cout << "字母等级：" << LetterGrade(score) << endl;
    return 0;
}

例题8.4：找一组整数中的最大值（数量未知）

算法：FindLargest(list)
目的：找出整数列表中的最大值
{
    largest ← -∞              // 初始化为负无穷
    while (还有整数没处理)
    {
        current ← 下一个整数   // 取出当前整数
        if (current > largest)
            largest ← current  // 更新最大值
    }
    return largest
}

C++ 完整代码：

#include <iostream>
#include <climits>  // 提供 INT_MIN（最小整数，模拟负无穷）
using namespace std;
int main() {
    int n;
    cout << "请输入整数个数：";
    cin >> n;
    int largest = INT_MIN;  // 初始化为最小值（相当于 -∞）
    for (int i = 0; i < n; i++) {
        int current;
        cin >> current;            // 读入当前整数
        if (current > largest)
            largest = current;     // 更新最大值
    }
    cout << "最大值是：" << largest << endl;
    return 0;
}

8.4 算法的正式定义

算法：一个有序的、无歧义的步骤集合，能在有限时间内产生结果并终止。
四个关键要素：

要素	含义
有序性	步骤必须有明确的先后顺序
无歧义性	每一步的含义必须清晰，不能模糊
产生结果	算法必须有输出，否则没意义
有限终止	算法必须在有限步骤内结束，不能死循环

8.5 基本算法

8.5.1 求和（Summation）

思路： 用一个变量 sum 累加，初始为0，每次加一个新数。
$\text{sum} = \sum_{i=1}^{n} a_i$
C++ 完整代码：

#include <iostream>
using namespace std;
int main() {
    int n;
    cout << "请输入整数个数：";
    cin >> n;
    int sum = 0;  // 初始化和为0
    for (int i = 0; i < n; i++) {
        int current;
        cin >> current;
        sum += current;  // 累加每个数
    }
    cout << "总和：" << sum << endl;
    return 0;
}

8.5.2 求积（Product）

思路： 用一个变量 product 累乘，初始为1，每次乘一个新数。
$\text{product} = \prod_{i=1}^{n} a_i$
C++ 完整代码：

#include <iostream>
using namespace std;
int main() {
    int n;
    cout << "请输入整数个数：";
    cin >> n;
    long long product = 1;  // 初始化积为1（注意用long long防溢出）
    for (int i = 0; i < n; i++) {
        int current;
        cin >> current;
        product *= current;  // 累乘每个数
    }
    cout << "乘积：" << product << endl;
    return 0;
}

8.5.3 排序（Sorting）

排序是把数据按值的大小重新排列。生活中的电话本、字典都是排过序的数据，否则查找会极其困难。
下面介绍三种基础排序算法，以 [78, 45, 23, 32, 56, 8] 为例。

选择排序（Selection Sort）

核心思想：

把列表分成"已排序"和"未排序"两部分
每次从未排序部分找出最小值，放到未排序部分的最前面
重复 $n - 1$ 次
演示过程：

原始：  78  45  23  32  56  8
        |<-------- 未排序 -------->|
第1轮：找最小值 8，与第1位(78)交换
        8  | 45  23  32  56  78
        已排序|<--- 未排序 ------>|
第2轮：找最小值 23，与第2位(45)交换
        8  23 | 32  45  56  78
        已排序 |<-- 未排序 ----->|
第3轮：找最小值 32，与第3位(32)交换（原地不动）
        8  23  32 | 45  56  78
              已排序|<- 未排序 ->|
第4轮：找最小值 45，与第4位(45)交换（原地不动）
        8  23  32  45 | 56  78
                 已排序|<未排序>|
第5轮：找最小值 56，与第5位(56)交换（原地不动）
        8  23  32  45  56  78   ← 排序完成！

C++ 完整代码：

#include <iostream>
using namespace std;
// 选择排序（升序）
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // 找未排序部分（从i到n-1）中的最小值下标
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex])
                minIndex = j;  // 更新最小值位置
        }
        // 把最小值交换到未排序部分的起始位置
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}
int main() {
    int arr[] = {78, 45, 23, 32, 56, 8};
    int n = 6;
    cout << "排序前：";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    selectionSort(arr, n);
    cout << "排序后：";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    return 0;
}

冒泡排序（Bubble Sort）

核心思想：

把最小的数像气泡一样"浮"到最前面
相邻两个数比较，小的往前换
每轮完成后，最小的数就到位了
重复 $n - 1$ 次
演示过程（第1轮，找最小值8）：

78  45  23  32  56  8
 ^-- 比较相邻 --^
56 vs 8 → 8更小，交换：78  45  23  32  8  56
32 vs 8 → 8更小，交换：78  45  23  8  32  56
23 vs 8 → 8更小，交换：78  45  8  23  32  56
45 vs 8 → 8更小，交换：78  8  45  23  32  56
78 vs 8 → 8更小，交换：8  78  45  23  32  56
第1轮结束：8 已浮到最前 ✓

C++ 完整代码：

#include <iostream>
using namespace std;
// 冒泡排序（升序，小的"冒"到前面）
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // 每轮从末尾往前，把最小值冒泡到位置 i
        bool swapped = false;  // 优化：如果没有交换，说明已排好
        for (int j = n - 1; j > i; j--) {
            if (arr[j] < arr[j - 1]) {
                // 相邻元素比较，小的往前移
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break;  // 没有发生交换，提前结束
    }
}
int main() {
    int arr[] = {78, 45, 23, 32, 56, 8};
    int n = 6;
    cout << "排序前：";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    bubbleSort(arr, n);
    cout << "排序后：";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    return 0;
}

插入排序（Insertion Sort）

核心思想：

就像打扑克牌时，每摸一张牌就插入到手牌中合适的位置
从第2个元素开始，每次把当前元素插入到前面已排好序的部分中正确的位置
演示过程：

原始：  78  45  23  32  56  8
        ^-- 初始已排序部分（只有1个元素）
第1轮：取45，插入到 [78] 中 → [45, 78]
        45  78  |  23  32  56  8
第2轮：取23，插入到 [45, 78] 中 → [23, 45, 78]
        23  45  78  |  32  56  8
第3轮：取32，插入到 [23, 45, 78] 中 → [23, 32, 45, 78]
        23  32  45  78  |  56  8
第4轮：取56，插入到 [23,32,45,78] 中 → [23,32,45,56,78]
        23  32  45  56  78  |  8
第5轮：取8，插入到最前 → [8,23,32,45,56,78]
        8  23  32  45  56  78  ← 完成！

C++ 完整代码：

#include <iostream>
using namespace std;
// 插入排序（升序）
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];  // 当前要插入的元素
        int j = i - 1;
        // 把比key大的元素都往右移一位
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;  // 把key插入到正确位置
    }
}
int main() {
    int arr[] = {78, 45, 23, 32, 56, 8};
    int n = 6;
    cout << "排序前：";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    insertionSort(arr, n);
    cout << "排序后：";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    return 0;
}

三种排序对比

算法	核心操作	每轮结果	适合场景
选择排序	找最小值，放到最前	最小值归位	简单易懂
冒泡排序	相邻比较，小的往前冒	最小值浮到最前	已部分排好时效率高
插入排序	取元素，插入已排序部分	已排序部分增1	数据量小或接近有序时

这三种算法都需要 $n - 1$ 轮（n为元素个数）。

8.5.4 查找（Searching）

查找就是在一堆数据里找到目标值的位置。

顺序查找（Sequential Search）

适用： 无序列表，或小列表。
思路： 从头到尾逐个比对，找到就停，找不到就继续直到末尾。
演示（在列表中找62）：

列表：4  21  36  14  62  91  8  22  7  81  77  10
目标：62
第1步：4  vs 62 → 不等，继续
第2步：21 vs 62 → 不等，继续
第3步：36 vs 62 → 不等，继续
第4步：14 vs 62 → 不等，继续
第5步：62 vs 62 → 相等！找到了，位置是第5个

C++ 完整代码：

#include <iostream>
using namespace std;
// 顺序查找，返回目标值的下标，找不到返回-1
int sequentialSearch(int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == target)
            return i;  // 找到，返回下标
    }
    return -1;  // 没找到
}
int main() {
    int arr[] = {4, 21, 36, 14, 62, 91, 8, 22, 7, 81, 77, 10};
    int n = 12;
    int target;
    cout << "请输入要查找的数：";
    cin >> target;
    int result = sequentialSearch(arr, n, target);
    if (result != -1)
        cout << "找到了！在第 " << result + 1 << " 个位置（下标" << result << "）" << endl;
    else
        cout << "没有找到 " << target << endl;
    return 0;
}

二分查找（Binary Search）

前提： 列表必须已经排好序！
核心思想： 每次对半切，排除掉一半不可能的区域。
演示（在有序列表中找22）：

有序列表（下标1到12）：
位置： 1   2   3   4   5   6   7   8   9  10  11  12
数值： 4   7   8  10  14  21  22  36  62  77  81  91
目标：22
第1轮：
  first=1, last=12, mid=(1+12)/2=6 → 列表[6]=21
  21 < 22，目标在右半边，first 移到 mid+1=7
第2轮：
  first=7, last=12, mid=(7+12)/2=9 → 列表[9]=62
  62 > 22，目标在左半边，last 移到 mid-1=8
第3轮：
  first=7, last=8, mid=(7+8)/2=7 → 列表[7]=22
  22 == 22，找到了！位置是7

图示（Mermaid）：

C++ 完整代码：

#include <iostream>
using namespace std;
// 二分查找（列表必须已排序），返回下标，找不到返回-1
int binarySearch(int arr[], int n, int target) {
    int first = 0;        // 搜索区间左边界（下标从0开始）
    int last = n - 1;     // 搜索区间右边界
    while (first <= last) {
        int mid = (first + last) / 2;  // 中间位置
        if (arr[mid] == target)
            return mid;          // 找到目标
        else if (arr[mid] < target)
            first = mid + 1;     // 目标在右半边
        else
            last = mid - 1;      // 目标在左半边
    }
    return -1;  // 找不到
}
int main() {
    int arr[] = {4, 7, 8, 10, 14, 21, 22, 36, 62, 77, 81, 91};
    int n = 12;
    int target;
    cout << "请输入要查找的数：";
    cin >> target;
    int result = binarySearch(arr, n, target);
    if (result != -1)
        cout << "找到了！在下标 " << result << "（第 " << result + 1 << " 个）" << endl;
    else
        cout << "没有找到 " << target << endl;
    return 0;
}

两种查找对比：

对比项	顺序查找	二分查找
前提条件	无（任意列表）	列表必须已排序
最坏情况	比较 $n$ 次	比较 $log_2 n$ 次
适用场景	小列表、不常查找	大列表、频繁查找

例如列表有 $1, 000, 000$ 个元素：

顺序查找最坏需要 $1, 000, 000$ 次比较
二分查找最坏只需要约 $\log_2(1000000) \approx 20$ 次比较

8.6 子算法（Subalgorithms）

什么是子算法？
把大算法拆分成小的独立模块，每个模块就是一个子算法。就像一个公司分成多个部门，每个部门专注自己的职责。
例子：选择排序中的子算法
选择排序需要反复"找最小值"，我们把这个操作单独提取出来，成为子算法 FindSmallest：

子算法的优点：

可读性好：主算法更简洁清晰，一眼能看出做了什么
可复用：同一个子算法可以在不同地方调用，不用重写

8.7 递归（Recursion）

什么是递归？

递归是指一个算法调用自身来解决问题。
解决问题的方式分两种：

迭代（Iteration）：用循环重复执行
递归（Recursion）：把大问题变成小问题，小问题再调用自己解决

以阶乘为例

阶乘的定义： $\times 2 \times 3 \times \cdots \times n$
$\begin{cases} 1 & \text{如果 } n = 0 \\ n \times (n-1)! & \text{如果 } n > 0 \end{cases}$

迭代方式（用循环）

$\times (n-1) \times (n-2) \times \cdots \times 2 \times 1$

算法：Factorial_迭代(n)
{
    F ← 1
    i ← 1
    while (i <= n)
    {
        F ← F × i    // 累乘
        i ← i + 1    // 计数器加1
    }
    return F
}

递归方式（调用自身）

算法：Factorial_递归(n)
{
    if (n = 0)
        return 1               // 基础情况：0! = 1
    else
        return n × Factorial(n-1)  // 递归调用：n! = n × (n-1)!
}

递归的执行过程（以 Factorial(3) 为例）：

分解过程（向下展开 + 向上回收）：

Factorial(3)
  = 3 × Factorial(2)
           = 2 × Factorial(1)
                    = 1 × Factorial(0)
                               = 1      ← 触底（基础情况）
                    = 1 × 1 = 1
           = 2 × 1 = 2
  = 3 × 2 = 6

C++ 完整代码（迭代 + 递归对比）：

#include <iostream>
using namespace std;
// 迭代版阶乘
long long factorialIterative(int n) {
    long long F = 1;  // 初始化为1（因为乘法单位元是1）
    for (int i = 1; i <= n; i++) {
        F = F * i;    // 累乘：F = 1×2×3×...×n
    }
    return F;
}
// 递归版阶乘
long long factorialRecursive(int n) {
    if (n == 0)
        return 1;                         // 基础情况：0! = 1
    else
        return n * factorialRecursive(n - 1);  // 递归：n! = n × (n-1)!
}
int main() {
    int n;
    cout << "请输入一个非负整数 n：";
    cin >> n;
    cout << n << "! (迭代) = " << factorialIterative(n) << endl;
    cout << n << "! (递归) = " << factorialRecursive(n) << endl;
    return 0;
}

迭代 vs 递归对比

对比项	迭代	递归
实现方式	循环（while/for）	函数调用自身
代码长度	通常稍长	通常更简洁优雅
理解难度	直观易懂	需要理解调用栈
内存使用	较少	每次调用占用栈空间
适用场景	简单重复操作	问题本身有递归结构（树、阶乘等）

总结

本章核心内容回顾：

算法
├── 定义：有序、无歧义、有结果、有限终止的步骤集合
│
├── 三种基本结构
│   ├── 顺序（Sequence）：按顺序执行
│   ├── 判断（Decision）：条件分支
│   └── 循环（Repetition）：重复执行
│
├── 表示方式
│   ├── UML图：图形化
│   └── 伪代码：文字化
│
├── 基本算法
│   ├── 求和、求积
│   ├── 找最大/最小值
│   ├── 排序
│   │   ├── 选择排序：每轮找最小放到前面
│   │   ├── 冒泡排序：相邻比较，小的冒泡
│   │   └── 插入排序：每次插入已排序部分
│   └── 查找
│       ├── 顺序查找：逐个比对（无需排序）
│       └── 二分查找：折半查找（需已排序）
│
├── 子算法：把大算法拆成可复用的小模块
│
└── 递归 vs 迭代
    ├── 迭代：用循环
    └── 递归：函数调用自身，分解问题

AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

Ollama 本地大模型部署与运行深度评测

AtomGit开源社区

OpenClaw实操指南42｜安全边界2：提示词注入与沙箱防护

AtomGit开源社区

LLMLingua：用小型模型“剪枝”大语言模型提示词，让长文本不再昂贵

LLMLingua是一种创新技术，利用小型模型（如GPT-2或LLaMA-7B）对大语言模型的提示词进行"剪枝"压缩。它通过计算每个token的信息熵和困惑度，识别并剔除冗余token，在保持语义完整性的同时实现高达20倍的压缩率。该方法采用预算控制器动态分配压缩率，结合迭代压缩算法处理长距离依赖关系。实际应用中，LLMLingua能显著降低API调用成本、减少延迟，同时避免引入噪声干扰。评估显示

AtomGit开源社区

所有评论(0)

查看更多评论

虾球xz

@TM1695648164

已为社区贡献64条内容

FOUNDATIONS OF COMPUTER SCIENCE 5TH EDITION计算机科学道理学习:第五章：计算机组织（Computer Organization）

虾球xz

一、整体架构概览

二、CPU（中央处理器）

2.1 ALU（算术逻辑单元）

ALU 是真正做计算的地方，能做三类操作：

2.2 寄存器（Registers）

2.3 控制单元（Control Unit）

三、主内存（Main Memory）

3.1 地址空间（Address Space）

3.2 内存类型

各类型特点汇总：

3.3 内存层次结构（Memory Hierarchy）

3.4 缓存内存（Cache Memory）

四、输入/输出（I/O）子系统

4.1 非存储设备（Nonstorage Devices）

4.2 存储设备（Storage Devices）

磁性存储（Magnetic Storage）

光学存储（Optical Storage）

CD-ROM、CD-R、CD-RW、DVD 对比：

DVD 容量（比 CD 大得多）：

五、子系统互连（Subsystem Interconnection）

5.1 CPU 与内存的连接

5.2 I/O 设备的连接

5.3 I/O 寻址方式

六、程序执行（Program Execution）

6.1 机器周期（Machine Cycle）

6.2 I/O 同步方法

七、计算机架构（Different Architectures）

7.1 CISC vs RISC

7.2 流水线（Pipelining）

7.3 并行处理（Parallel Processing）

八、一个简单计算机的完整示例

8.1 简单计算机结构

这台假想计算机的规格：

8.2 指令格式

8.3 指令集（14条指令）

8.4 完整执行示例：计算 A + B = C

8.5 带输入输出的完整程序

九、对应的 C++ 代码：简单计算机模拟器

十、核心概念速查表

第六章：计算机网络（Computer Networks）从零理解

一、什么是网络？

1.1 网络的三个标准

二、物理结构（Physical Structures）

2.1 连接类型

2.2 四种物理拓扑（Topology）

网状拓扑（Mesh）

星型拓扑（Star）

总线拓扑（Bus）

环形拓扑（Ring）

三、网络分类（Categories）

internet（互联网）vs Internet（因特网）

四、TCP/IP 协议栈（Protocol Suite）

封装（Encapsulation）

五、五层详解

5.1 应用层（Application Layer）

客户端-服务器架构（Client-Server Architecture）

应用层地址（URL）

5.2 传输层（Transport Layer）

作用：负责"进程到进程"的完整消息传递。 一台服务器可能同时运行多个服务（FTP、HTTP等），端口号（Port Number） 用来区分是哪个服务： 类比：IP地址是公寓楼的地址，端口号是具体哪个房间号。

传输层的主要工作

三种传输层协议对比

5.3 网络层（Network Layer）

IP 地址（IP Address）

路由（Routing）

辅助协议

5.4 数据链路层（Data Link Layer）

MAC 地址（物理地址）

帧的传递过程

5.5 物理层（Physical Layer）

5.6 五层地址汇总

六、互联网应用

6.1 电子邮件（Email）

邮件系统架构

邮件地址格式

两种收件协议对比

MIME（多用途互联网邮件扩展）

6.2 文件传输协议（FTP）

6.3 远程登录（TELNET）

作用：负责"进程到进程"的完整消息传递。
一台服务器可能同时运行多个服务（FTP、HTTP等），端口号（Port Number）用来区分是哪个服务：
类比：IP地址是公寓楼的地址，端口号是具体哪个房间号。