登录
Hello Tools
  默认分类   工具

Hello Tools

网站正在更新中，以往博客暂时不可查看。

 次点击
 294 分钟阅读

Anki已完成进度: "197" tags: - review - 重点

408大纲重要考点

数据结构

计组

  • 补码加减运算器标志位生成
  • 乘除法电路
  • 固态硬盘（去年考选择题）
    • 固态硬盘的读写以页为单位，以块为单位进行擦除（写页擦块）

$$ \text{\color{blue}固态硬盘 SSD} \begin{cases} \text{原理}: \begin{cases} \colorbox{#70ad47}{\textcolor{white}{\textbf{基于闪存技术 Flash Memory}}} \ \text{属于电可擦除 ROM，即 EEPROM} \end{cases} \\ \text{组成}: \begin{cases} \text{闪存翻译层（FTL）}: \begin{cases} \colorbox{#5b9bd5}{\textcolor{white}{\textbf{负责逻辑块地址到物理页的映射}}} \ \text{实现地址翻译与写优化} \end{cases} \\ \text{存储介质}: \begin{cases} \colorbox{#70ad47}{\textcolor{white}{\textbf{多个闪存芯片（Flash Chip）}}} \ \text{每个芯片包含多个}: \begin{cases} \colorbox{#ff0000}{\textcolor{white}{\textbf{块（Block）}}} \ \text{每个块包含多个}: \begin{cases} \colorbox{#ff0000}{\textcolor{white}{\textbf{页（Page）}}} \end{cases} \end{cases} \end{cases} \end{cases} \\ \text{读写性能特性}: \begin{cases} \text{读/写单位}: \begin{cases} \colorbox{#70ad47}{\textcolor{white}{\textbf{以页为单位读写}}} \ \text{类似机械硬盘的“扇区”} \end{cases} \\ \text{擦除单位}: \begin{cases} \colorbox{#ff0000}{\textcolor{white}{\textbf{以块为单位擦除}}} \ \text{必须先擦除才能写入新数据} \end{cases} \\ \text{访问方式}: \begin{cases} \colorbox{#70ad47}{\textcolor{white}{\textbf{支持随机访问}}} \ \text{通过电路直接定位物理地址，无机械延迟} \end{cases} \\ \text{性能特点}: \begin{cases} \colorbox{#70ad47}{\textcolor{white}{\textbf{读快、写慢}}} \ \text{若页已占用，需：} \ \quad\text{1. 复制同块其他页} \ \quad\text{2. 擦除整个块} \ \quad\text{3. 写入新页} \ \Rightarrow \text{产生“写放大”现象} \end{cases} \end{cases} \\ \text{与机械硬盘对比}: \begin{cases} \text{速度}: \begin{cases} \colorbox{#70ad47}{\textcolor{white}{\textbf{SSD 快}}}：\text{无寻道时间与旋转延迟} \ \text{HDD 慢}：\text{依赖磁臂移动和盘片旋转} \end{cases} \\ \text{物理特性}: \begin{cases} \colorbox{#70ad47}{\textcolor{white}{\textbf{SSD：静音、抗震、低功耗}}} \ \colorbox{#ff0000}{\textcolor{white}{\textbf{HDD：有噪音、怕震动}}} \end{cases} \\ \text{成本与寿命}: \begin{cases} \colorbox{#ff0000}{\textcolor{white}{\textbf{SSD 更贵}}}，\text{且有写入寿命限制} \ \quad\text{（每块约 }10^3 \sim 10^5\text{ 次擦除）} \ \colorbox{#70ad47}{\textcolor{white}{\textbf{HDD 便宜}}}，\text{扇区无写入寿命问题} \end{cases} \end{cases} \\ \text{磨损均衡技术}: \begin{cases} \text{目标}: \begin{cases} \colorbox{#7030a0}{\textcolor{white}{\textbf{均衡擦除次数，延长 SSD 寿命}}} \end{cases} \\ \text{动态磨损均衡}: \begin{cases} \colorbox{#5b9bd5}{\textcolor{white}{\textbf{优先写入擦除次数少的块}}} \ \text{避免热点区域过度磨损} \end{cases} \\ \text{静态磨损均衡}: \begin{cases} \colorbox{#5b9bd5}{\textcolor{white}{\textbf{定期迁移冷数据}}} \ \text{释放老旧块，让新块承担更多写操作} \end{cases} \end{cases} \end{cases} $$

  • 高级语言与机器代码对应关系
  • 多处理器/SMP基本概念

$$ \text{多处理机调度} \begin{cases} \text{对称多处理机(SMP)} \xrightarrow[]{} \begin{aligned} &\colorbox{#70ad47}{\textcolor{white}{\textbf{多个CPU平等地共享同一个内存和资源}}}，\text{每个处理器的工作能力一样} \ &\colorbox{#70ad47}{\textcolor{white}{\textbf{负载可迁移}}}：\text{一个CPU忙时，其他CPU可以分担工作，提升整体效率} \ &\colorbox{#5b9bd5}{\textcolor{white}{\textbf{现代多核处理器 = SMP架构}}} \end{aligned} \\

\text{非对称多处理机} \xrightarrow[]{\color{red}\textbf{主从架构}} \begin{aligned} &\colorbox{#ffc000}{\textcolor{black}{\textbf{多个CPU但地位不平等}}} \ &\color{red}\textbf{主处理器}：\text{负责核心调度、内核访问和任务分配} \ &\color{red}\textbf{从处理器}：\text{仅执行特定任务或用户进程，受主处理器控制} \ &\colorbox{#ff0000}{\textcolor{white}{\textbf{仅主处理器可访问内核区}}}，\text{安全性与控制集中化} \ &\colorbox{#7030a0}{\textcolor{white}{\textbf{适用场景}}}：\text{任务不均衡系统（如早期嵌入式系统）} \end{aligned} \end{cases} $$

$$ \text{\color{blue}对称多处理机} \begin{cases} \text{\color{blue}公共就绪队列} \begin{cases} \text{方式：} \colorbox{#70ad47}{\textcolor{white}{\textbf{所有处理机共享一个全局就绪队列}}} \[5pt]

\text{优点：} \begin{aligned} &\colorbox{#5b9bd5}{\textcolor{white}{\textbf{任务分配灵活，天然支持负载均衡}}} \end{aligned} \[5pt]

\text{缺点：} \begin{aligned} &\colorbox{#ff0000}{\textcolor{white}{\textbf{高并发下争用严重，需加锁同步，影响性能}}} \end{aligned} \end{cases} \\

\text{\color{blue}私有就绪队列} \begin{cases} \text{方式：} \colorbox{#70ad47}{\textcolor{white}{\textbf{每个处理机拥有独立的私有就绪队列}}} \[10pt]

\text{\color{purple}处理机亲和性} \begin{cases} \text{含义：} \begin{aligned} &\colorbox{#7030a0}{\textcolor{white}{\textbf{将进程/线程绑定到指定CPU上运行}}} \ &\text{优先在指定CPU执行，即使其他CPU空闲} \ &\colorbox{#70ad47}{\textcolor{white}{\textbf{提高Cache命中率，减少上下文切换开销}}} \end{aligned} \[5pt]

\text{策略} \begin{cases} \colorbox{#5b9bd5}{\textcolor{white}{\textbf{软亲和}}}：\text{操作系统尽量保持进程在同一个CPU，但不强制} \ \colorbox{#ff0000}{\textcolor{white}{\textbf{硬亲和}}}：\text{通过系统调用（如}\texttt{sched_setaffinity}\text{）强制绑定} \end{cases} \end{cases} \\[10pt]

\text{\color{purple}负载均衡} \begin{cases} \text{含义：} \begin{aligned} &\colorbox{#7030a0}{\textcolor{white}{\textbf{将任务均匀分配到各处理器，使负载大致相等}}} \ &\text{优化系统性能与资源利用率} \end{aligned} \[5pt]

\text{\color{green}动态负载均衡策略} \begin{cases} \text{最小负载优先} \xrightarrow[]{} \begin{aligned} &\colorbox{#70ad47}{\textcolor{white}{\textbf{新任务分配给当前负载最轻的处理器}}} \ &\text{负载变化时可触发任务迁移} \end{aligned} \[8pt]

\text{任务迁移（推迁移 Push）} \xrightarrow[]{} \begin{aligned} &\colorbox{#ffc000}{\textcolor{black}{\textbf{主动策略}}}：\text{系统周期性检查负载} \ &\text{从}\colorbox{#ff0000}{\textcolor{white}{\textbf{忙碌CPU}}}\text{的队列}\colorbox{#ff0000}{\textcolor{white}{\textbf{“推”}}}\text{进程到}\colorbox{#70ad47}{\textcolor{white}{\textbf{空闲CPU}}}\text{队列} \end{aligned} \[8pt]

\text{工作窃取（拉迁移 Pull）} \xrightarrow[]{\color{red}\textbf{主流方式}} \color{#5b9bd5} \begin{aligned} &\color{red}\textbf{被动策略}：\colorbox{#70ad47}{\textcolor{white}{\textbf{空闲CPU主动“拉”任务}}} \ &\text{从高负载CPU的队列中窃取进程} \ &\color{red}\textbf{现代多核系统常用}，\text{推拉可结合使用} \end{aligned} \end{cases} \end{cases} \end{cases} \end{cases} $$

操作系统

  • 多处理器调度（22年新增，预计3年内必考）
    • UMA 结构中每个处理器对所有存储单元的访问时间一致
    • NUMA 结构中处理器对不同存储单元的访问时间可能不一致，取决于存储单元的位置。
  • 多核处理器概念
    • 双端口RAM：优化多核CPU访问一根内存条的速度
  • 多级队列调度算法（22年新增，未考过）
  • 同步互斥三方式（锁/条件变量/信号）

$$ \text{信号} \begin{cases} \text{作用：}\text{一种最简单和基础的进程间通信方式，主要用于进程之间或进程与操作系统之间的}\colorbox{#70ad47}{\textcolor{white}{\textbf{异步通知机制}}} \[10pt]

\text{特点：} \begin{cases} \colorbox{#70ad47}{\textcolor{white}{\textbf{异步性}}} \xrightarrow{}\ \begin{aligned} \text{信号可以在任何时刻发送给进程，而无需进程处于某个特定的状态} \end{aligned} \[8pt] \colorbox{#70ad47}{\textcolor{white}{\textbf{轻量级通信}}} \xrightarrow{}\ \begin{aligned} \text{信号}\colorbox{#ffc000}{\textcolor{black}{\textbf{不携带具体数据}}}，\text{仅通知事件发生，只有标识符表示类型} \end{aligned} \[8pt] \colorbox{#ffc000}{\textcolor{white}{\textbf{有限数量}}} \xrightarrow{}\ \begin{aligned} \text{操作系统定义的信号类型有限（如SIGINT、SIGTERM等），每种有}\colorbox{#7030a0}{\textcolor{white}{\textbf{特定用途}}} \end{aligned} \end{cases} \[15pt]

\text{分类：} \begin{cases} \colorbox{#7030a0}{\textcolor{white}{\textbf{同步信号}}} \xrightarrow{}\ \begin{aligned} &\text{由进程自身操作触发（如除零、非法内存访问）} \ &\text{与执行流}\colorbox{#7030a0}{\textcolor{white}{\textbf{同步}}}，通常是错误或异常导致 \end{aligned} \[10pt] \colorbox{#7030a0}{\textcolor{white}{\textbf{异步信号}}} \xrightarrow{}\ \begin{aligned} &\text{由外部事件或其他进程触发（如Ctrl+C → SIGINT）} \ &\text{产生时机}\colorbox{#7030a0}{\textcolor{white}{\textbf{不可预测}}}，与当前进程无关 \end{aligned} \end{cases} \[15pt]

\color{#5b9bd5}\text{处理：} \begin{cases} \color{red}\text{默认处理方式} \xrightarrow{}\color{#5b9bd5} \begin{aligned} &\text{若未注册自定义处理函数，系统按信号类型执行}\colorbox{#ff0000}{\textcolor{white}{\textbf{默认动作}}} \ &\text{如：}\texttt{SIGTERM}→\colorbox{#ff0000}{\textcolor{white}{\textbf{终止}}}，\texttt{SIGCHLD}→\colorbox{#ff0000}{\textcolor{white}{\textbf{忽略}}} \end{aligned} \[10pt]

\color{red}\text{信号处理函数} \xrightarrow{}\color{#5b9bd5} \begin{aligned} &\text{通过}\texttt{signal()} \text{或} \texttt{sigaction()} \colorbox{#ff0000}{\textcolor{white}{\textbf{注册回调函数}}} \ &\text{信号到达时，中断主流程执行}\colorbox{#ff0000}{\textcolor{white}{\textbf{用户自定义逻辑}}} \end{aligned} \[10pt]

\color{red}\text{信号屏蔽} \xrightarrow{}\color{#5b9bd5} \begin{aligned} &\text{使用信号屏蔽字}\texttt{sigprocmask()} \colorbox{#ffc000}{\textcolor{black}{\textbf{阻塞某些信号}}}，防止其被立即处理 \ &\text{用于保护临界区或延迟处理} \end{aligned} \[10pt]

\color{red}\text{信号挂起} \xrightarrow{}\color{#5b9bd5} \begin{aligned} &\text{已被发送但}\colorbox{#ffc000}{\textcolor{black}{\textbf{被屏蔽}}} \text{或未处理的信号} \ &\text{保留在}\colorbox{#7030a0}{\textcolor{white}{\textbf{挂起队列}}} \text{中，待解除屏蔽后处理} \end{aligned} \end{cases} \end{cases} $$

  • 内存映射文件（去年考过）
    • 操作系统在进程的虚拟内存地址空间中分配一块连续的区域作为映射区域，并将该区域与文件在磁盘上的内容建立映射关系。进程可以通过该虚拟地址直接访问文件内容。
    • 内存映射文件避免了频繁的系统调用，通过将文件内容映射到内存中，程序可以像操作内存一样直接访问文件内容，从而减少I/O开销，提升访问速度。
    • 只在初次访问和缺页中断时需要系统参与。
    • 常用于大文件处理、进程间通信和数据库系统
  • 文件全局结构（引导块） ![[Snipaste_2023-08-11_17-00-53.png]]
  • 输入输出应用程序接口（22年新增）
  • 设备驱动程序接口
  • 外核（了解即可） $$ \color{#5b9bd5}\text{外核} \begin{cases} \text{特性：} \color{red} \begin{cases} \colorbox{#70ad47}{\textcolor{white}{\textbf{内核}}} \text{负责} \colorbox{#70ad47}{\textcolor{white}{\textbf{进程调度、进程通信}}} \text{等核心管理功能} \ \colorbox{#ff0000}{\textcolor{white}{\textbf{外核}}} \text{负责} \colorbox{#ff0000}{\textcolor{white}{\textbf{直接分配物理硬件资源}}} \text{（如内存页、磁盘块、CPU时间）} \ \text{并确保资源使用的} \colorbox{#7030a0}{\textcolor{white}{\textbf{安全性与隔离性}}} \end{cases} \\ \text{优点：} \color{red} \begin{cases} 1.\ \colorbox{#5b9bd5}{\textcolor{white}{\textbf{硬件资源不虚拟、不抽象}}}, \text{直接分配给用户进程} \ \quad\Rightarrow \colorbox{#70ad47}{\textcolor{white}{\textbf{减少映射开销，提升性能和灵活性}}} \ \ 2.\ \colorbox{#70ad47}{\textcolor{white}{\textbf{应用程序可自定义资源管理策略}}} \ \quad\text{（如专用文件系统或内存管理器）} \end{cases} \\ \text{缺点：} \begin{cases} 1.\ \colorbox{#ff0000}{\textcolor{white}{\textbf{降低系统一致性}}}, \text{不同进程可能以不同方式访问硬件} \ \ 2.\ \colorbox{#ff0000}{\textcolor{white}{\textbf{系统复杂性增加}}}, \text{外核需精细控制资源安全，开发难度高} \end{cases} \end{cases} $$
  • 闲逛进程
    • 操作系统内核创建的第一个进程（在某些系统中是进程号为 0 的进程），它是一个 永远不会终止的低优先级系统进程
    • 当 CPU 没有其他进程可运行时，就运行闲逛进程，避免 CPU 空转或陷入未知状态
    • 所以处理机永远不会空闲
  • 操作系统引导虚拟机

计算机网络

  • VLAN（已考过）

  • SDN软件定义网络（22年新增）

    • 控制平面：由 SDN 控制器实现，负责决策“数据包该如何转发”。

    • 数据平面：由交换机/路由器实现，负责实际的数据包转发。

    • 控制器通过标准接口与交换机通信，实现集中式网络管理。

接口类型 通信双方 作用 所属平面 典型协议/形式
南向接口 控制器 ↔ 交换机/设备 下发流表、收集状态 控制平面 ↔ 数据平面 OpenFlow、NETCONF、OVSDB
北向接口 应用 ↔ 控制器 提供网络抽象，支持应用开发 应用平面 ↔ 控制平面 RESTful API、gRPC
东西向接口 控制器 ↔ 控制器 控制器间同步与协作 控制平面 ↔ 控制平面 Paxos、Raft、Gossip、集群通信协议

![[tmpzizx78tu.jpg]]

数据结构

基础

  • 斐波那契的朴素递归算法时间复杂度为$O(2^n)$

  • 若同时有无符号数和有符号数参与运算，则C语言标准规定按无符号数进行运算

  • 结构体按边界对齐

    • 结构体总大小为最大成员的整数倍
    • 每个成员的起始地址是自身大小的整数倍

  • IEEE754

    • IEEE 754 阶码差（ΔE）与尾数位数的关系

    • 对阶 $\in$ 右规

    • 阶码的规范->左减右加

    • 尾数溢出时可能产生误差，结果不一定溢出

    • 规格化阶码 $\in [1,254]$->$2^{[－126，127]}$

    • 非规格化阶码全0->$2^{-126}$

    • 最简单的舍入->直接截断法

    • 乘法运算不需要左规，可能需要右规（规格化数尾数永远有1兜底，不需要左规格化）

    • 最接近 0 的负数->$-2^{-(126+23)}$

    • 阶码只有加减运算，没有乘除运算

    • 任何情况下 右规只进行一次

# 假设简化浮点数格式
# 最大正数: 1.111 × 2^3 = 15
# 计算: 7 + 7 = 14

7 = 1.110 × 2^2
7 = 1.110 × 2^2
----------------
尾数相加: 1.110 + 1.110 = 11.100 (尾数溢出!)
规格化: 11.100 × 2^2 = 1.110 × 2^3 = 14 (结果正常)
精度 存储尾数位数 有效尾数位数（$p$） 安全忽略阈值->直接视为0 说明
单精度 23 位 24 位 $ΔE ≥ 25$ 有效位数 = 存储位数 + 1（隐含的 1）
双精度 52 位 53 位 $ΔE ≥ 54$ 有效位数 = 存储位数 + 1（隐含的 1）
  • 基数为$r$的浮点数尾数$M$规格化判断 $$ \frac{1}{r} \le |M| \le 1 $$
  • 无符号整数通常用来表示地址/指针，当两地址相加结果大于最大地址而丢掉最高位进位时，相当于取模运算。
  • 时间复杂度
    • i=i*a的时间复杂度为 $log_an$，对数的数量级与底数无关，因此＝ $log_2n$
  • 时空局部性
    • 空间局部性（Spatial Locality）：当一个内存位置被访问后，其附近的内存位置很可能在不久的将来被访问。数组是连续存储的，按顺序访问（无论正序还是逆序）都具有良好的空间局部性。
    • 时间局部性（Temporal Locality）：如果一个内存位置被访问了，那么它在不久的将来很可能再次被访问。通常出现在循环中重复使用某个变量、缓存命中等情况。
    • 循环体内的一个数组
      • 有时间局部性
      • 如果没有重复使用的元素，则 无空间局部性
  • 补码表示的尾数最小值为-1（无论位数）
  • C语言运算符的优先级
优先级 运算符 名称/含义 结合性
1 () [] . -> 函数调用、数组下标、成员访问 左到右
2 ++ -- + - ! ~ * & (type) sizeof 自增/自减、正负号、逻辑非、取地址、类型转换等 右到左
3 * / % 乘、除、取模 左到右
4 + - 加、减 左到右
5 << >> 位移运算 左到右
6 < <= > >= 关系比较 左到右
7 == != 等于/不等于 左到右
8 & 按位与 左到右
9 ^ 按位异或 左到右
10 ` ` 按位或
11 && 逻辑与 左到右
12 ` `
13 ?: 条件运算符 右到左
14 = += -= 等赋值运算符 赋值 右到左
15 , 逗号运算符 左到右

各种意义上的表

  • 双向链表->数据的插入和删除更加快捷
  • 查找的 $ASL$->$ASL_{成功}+ASL_{失败}$
  • 散列表的二次探测法->$addr(n\pm a^2)$，$a$为1，2，3，4---

各种意义上的树

  • AVL树

    • AVL树中的两个叶结点的层次差可以超过1
    • 从平衡因子的角度看，完全二叉树肯定是一颗AVL树
    • 折半查找判定树最小高度为 $\lceil log_2(n+1) \rceil$，叶结点高度为 $h-1$ 或 $h$

  • B树插入一个新结点最多可能生成 $2h+1$ 个结点，高度的增加发生在顶部，最多读写硬盘 ![[25王道8套模拟题-答案.pdf#page=63&rect=36,216,494,308|25王道8套模拟题-答案, p.63]]

  • 二叉堆用于排序，查找效率低

  • 严格 $k$ 叉树需要补充的 虚叶结点 个数计算公式为 $$ u=(n-1)%(k-1) $$ $$ 需要补充k-u-1个虚叶结点 $$

  • 二叉排序树的比较次数的最大次数

    • 最好时 $$ \lceil log_2(n+1)\rceil+1(平衡二叉树AVL) $$

    • 最坏时 $$ n+1(退化为一条长虫) $$

  • $n$个结点的树转换为二叉树的形态数量

    • 转换后二叉树的根节点必定只有左孩子（树不是森林，只有一个根节点，根节点无兄弟），因此转换为 $n-1$的卡特兰数
    • 先序和中序遍历->合法的进栈和出栈顺序 $$ Catlan＝\frac{1}{n+1}C_{2n}^n $$

  • $n$个节点组成二叉树的形态数=>卡特兰数

  • B树

    • B+树->叶结点之间存在指针链接->有利于进行 范围查找->数据库索引
    • B树的结点可以同时存关键字和数据，B+树仅 非叶结点 可以存储关键字
    • B树进行范围查找->中序遍历
    • B树的删除最终都会转化为对叶结点的修改
    • B树与B+树均可以 随机索引

  • 线索二叉树

    • 中序线索树中，从最左边的结点开始查找后继结点，一定能遍历完所有结点

  • 直插二路冒归基

项目 前序线索树 中序线索树 后序线索树
是否支持线索化？ ✅ 是 ✅ 是 ✅ 理论上是
是否能通过后继线索遍历？ ✅ 可以 ✅ 完全可以 ❌ 几乎不能
起始节点 根节点 最左下节点 最左下叶子
结束节点 最右下节点 最右下节点 根节点
后继是否局部？ 是 是 否（依赖全局）
是否需要栈？ 否 否 是（隐式需要）
是否需要父指针？ 否 否 是（通常需要）
实现难度 中等 简单 高
实用性 中 高 低

$$ \begin{cases} 前序+中序＝唯一二叉树 \ 前序＝入栈 \ 中序＝出栈 \end{cases}\xrightarrow{卡特兰数}二叉树的个数 $$

  • 败者树
    • 树高为 $\lceil log_2k \rceil+1$，$k$为归并段数
    • 以完全二叉树计算，归并段数量为其叶结点数量$\xrightarrow{总比较次数}归并段数量\cdot \lceil log_2路数\rceil$
    • 减少元素之间的比较次数
  • 折半查找树的判断->每一个非叶结点要么左右子树结点数相等，要么都是左比右多或者右比左多。
  • 编译器的词法分析->有穷自动机、语法树
  • 哈夫曼树
    • 高度不唯一
    • 均匀分布时哈夫曼编码无效
  • 红黑树
    • 若所有结点为黑结点，一定是满二叉树
情况 条件 处理方法 时间复杂度
1 P为黑色 无需处理 O(1)
2.1 P为红色，U为红色 P、U变黑，G变红，向上检查 O(log n)
2.2.1 LL情况 G右旋，P变黑，G变红 O(1)
2.2.2 LR情况 P左旋，转为LL情况 O(1)
2.2.3 RR情况 G左旋，P变黑，G变红 O(1)
2.2.4 RL情况 P右旋，转为RR情况 O(1)
  • 任何二叉树的论断需要考虑->空二叉树的情况
  • 二叉树的左右子树有顺序
  • 高度为$h$的$m$阶B树的关键字个数

$$最多 = m^h - 1$$

$$最少 = 2 \left\lceil \frac{m}{2} \right\rceil^{h-1} - 1$$

  • 二叉树遍历中前驱与后继结点查找
遍历方式 前驱节点位置 后继节点位置
前序遍历 1. 左子树最右下节点
2. 父节点（无左子树时）
3. 右兄弟节点（当前为左子节点时） 1. 左子节点
2. 右子节点
3. 父节点的右子节点（当前为左子节点且父节点有右子树时）
4. 祖父节点（当前为右子节点且无右子树时）
中序遍历 1. 左子树的最右节点
2. 父节点（无左子树时） 1. 右子树的最左节点
2. 父节点（无右子树且为左孩子时）
3.祖先中第一个是父节点左孩子的节点（无右子树且为左孩子时）
后序遍历 1. 右子树的根节点
2. 父节点（当前为右子节点时）
3. 兄弟节点的最深后代（当前为左子节点时） 1. 父节点
2. 兄弟节点（父节点无其他子树时）
  • DFS生成树的高度 $\ge$ BFS生成树高度
  • 三叉链表->左右孩子+双亲

栈和队列

  • 单个队列实现栈
    • push时将新元素入队，然后将队列中所有元素出队后入队

图

  • 并查集

    • 并查集中，路径压缩就是 小树并大树。
    • 并查集可以用于验证树—数量关系 + 结构验证 = 完整判定

  • Floyd算法中 $path^{k-1}[i,j]$不是 $path^{k}[i,j]$的子集。

    • $A^{(k)}[i][j]$=>顶点 $v_i$ 到 $v_j$ ，中间顶点序号不大于 $k$ 的最短路径长度，$A^{－1}$为初始矩阵

    • “以k为中转点，更新所有i到j的最短距离”

    • $d[i][j] = min(d[i][j], d[i][k] + d[k][j])$

    • 其中 k 是中间顶点，i 和 j 是任意两个顶点。

  • 拓扑排序

    • 很难唯一，只有在图中任意两个顶点之间都仅存在唯一一条路径的时候拓扑排序唯一。
    • 拓扑序列中，结点 $v_i$ 在 $v_j$ 前面只能说明没有 $v_j$ 到 $v_i$ 的路径，不能说明有 $v_i$ 到 $v_j$ 的路径。
    • 上三角矩阵或下三角矩阵对应的有向图一定存在拓扑排序序列
    • 拓扑排序就是找入度为0

  • $A^n$中的$a_{ij}$非零元素表示从$i$到$j$长度为$n$的路径条数

  • 关键路径

    • 缩短 非关键路径 上的活动的时间不可能对工程整体时间有影响
    • 关键路径上的活动延长->整体就延
边上活动a1 边上活动a2
$e(k)$
起点最早
$l(k)$
终点最晚-自身耗时
$d(k)$
  • MST唯一->所有环中所包含的边的权值不全一样
  • DFS遍历->来一个就往下走，回溯回刚才
  • 邻接矩阵不存在的边必须使用$\infty$
  • 若图所有边权重为正数（负数不行），则任一连接所有结点且总权重最小的一个边集合必为一棵树

排序

  • 两有序数组A B归并为一个有序序列，最大比较次数为$A+B-1$

  • 归并排序用于单链表上效果最好排序算法在单链表上的实现

  • 堆排序在升序中使用 大根堆，初始堆建好后反复交换堆顶与堆尾。

  • 堆的次大值一定在根的下一层

  • 快速排序

    • 最小比较次数计算（eg.以8为例)
      • 8＝（3｜4）->共3+4=7次
      • 3＝（1｜1）->共1+1=2次
      • 4＝（1｜2）->共1+2=3次
      • 2＝（1｜）->共1次
      • 综上，共13次
    • 实现空间复杂度严格 $O(log_2n)$->枢轴元素采用三数取中法（首、中、尾三个数据选择中等大小）

  • 可以并行的排序算法

    • 快速排序
    • 归并排序
    • 堆排序
    • 希尔排序 $\in$ 直接插入排序

  • 大量数中找 前$k$个最小->大根堆

  • 外部排序

    • 归并趟数$t$：每趟将$k$个段合并为 1 个段，因此归并趟数为： $$ 归并趟数t = \left\lceil \log_{路数m} 初始归并段的数量R \right\rceil $$
    • 一个缓冲区对应一个文件，$m$路归并对应 $m$个输入缓冲区+1个输出缓冲区
    • 生成初始归并段->在WA（内存工作区）中选择MINIMAX记录
    • 初始归并段长度与内存容量无关，平均长度为WA的两倍
    • 置换－选择排序=>增加初始归并段长度、减少初始归并段数量
    • 最佳归并树是严格$k$叉树$\ne$二叉哈夫曼树
    • $m$路平衡归并->每趟归并剩下的记录数为$\frac{1}{m}$ $$ \lceil \frac{元素数量n}{m^{趟数}} \rceil =1即完成 $$
排序算法 时间复杂度（平均） 时间复杂度（最坏） 时间复杂度（最好） 空间复杂度 稳定性
冒泡排序 $O(n^2)$ $O(n^2)$ $O(n)$ $O(1)$ 稳定
选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ 不稳定
插入排序 $O(n^2)$ $O(n^2)$ $O(n)$ $O(1)$ 稳定
希尔排序 $O(n \log n)$ ~ $O(n^2)$ $O(n^2)$ $O(n \log n)$ $O(1)$ 不稳定
归并排序 $O(n \log n)$ $O(n \log n)$ $O(n \log n)$ $O(n)$ 稳定
快速排序 $O(n \log n)$ $O(n^2)$ $O(n \log n)$ $O(\log n)$ 不稳定
堆排序 $O(n \log n)$ $O(n \log n)$ $O(n \log n)$ $O(1)$ 不稳定
计数排序 $O(n + k)$ $O(n + k)$ $O(n + k)$ $O(k)$ 稳定
基数排序 $O(d(n + k))$ $O(d(n + k))$ $O(d(n + k))$ $O(n + k)$ 稳定

注：$d$ 为位数，$k$ 为基数（如十进制下 $k=10$）。

查找

查找方法 时间复杂度 备注 成功ASL 失败ASL
顺序查找 $O(n)$ 适用于无序表 有序表$\dfrac{n+1}2$ 有序表$\dfrac n2+\dfrac n{n+1}$
折半查找 $O(log₂n)$ 要求有序表，顺序存储
树高$h=\lceil log_2(n+1)-1$
成功$ASL=log_2(n+1)-1$ $log_2(n+1) - 1$
分块查找 $O(log_2m+\frac{n}{m})$ 块内无序，块间有序
$n$个结点，$m$个组
树形查找 $O(log₂n)$ 退化为长虫时为$O(n)$

注：分块查找的时间复杂度取决于块的划分方式和块内查找方法，典型情况下接近 O(√n)。

  • $ASL_{散列表－成功}$与装填因子$\alpha$有关

算法思路积累

  • 图的最长路径问题
    • 将图中所有边的权重值取反，利用Floyd的最短路径求出最小的值的绝对值就是最长路径值
  • 单字符匹配可以使用ASCII码，定义int ASCIIArray[128]可包含所有数字与大小写字母
  • 拓扑排序可用DFS得到的逆拓扑排序（在DFS回溯时的到的序列）

计算机组成原理

  • 冯诺依曼机
    • 基本工作方式->控制流驱动
    • 基本特点->按地址访问并顺序执行指令
    • 指令流＝主存->控制器
  • 软件的功能与硬件的功能在 逻辑 上是等效的

数据表示与运算

  • 有符号数和无符号数的加减运算是如何利用同一个加法器的？（列原理）

    • $n$ 位加法器实现的是模 $2^n$ 无符号整数加法运算。对于无符号整数 $a$ 和 $b$，$a + b$ 可以直接用加法器实现，而 $a - b$ 可用 $a$ 加 $b$ 的补数实现，即 $a - b = a + [-b]_{补} \pmod{2^n}$，所以 $n$ 位无符号整数加/减运算都可在 $n$ 位加法器中实现。
    • 由于带符号整数用补码表示，补码加/减运算公式为 $[a + b]{补} = [a]{补} + [b]{补} \pmod{2^n}$，$[a - b]{补} = [a]{补} + [-b]{补} \pmod{2^n}$，所以 $n$ 位带符号整数加/减运算都可在 $n$ 位加法器中实现。

  • 小端：低位字节放到低地址（小弟弟）

  • 条件跳转比较条件

比较条件 无符号数标志位状态 有符号数标志位状态
A == B ZF = 1 ZF = 1
A != B ZF = 0 ZF = 0
A >= B CF = 0 SF = OF
A <= B CF = 1 或 ZF = 1 SF ≠ OF 或 ZF = 1
A > B CF = 0 且 ZF = 0 SF = OF 且 ZF = 0
A < B CF = 1 SF ≠ OF 且 ZF = 0

^6b267f

运算种类 符号位处理 核心规则（简化+准确）
原码乘法 符号位异或
（0同号，1异号） 1. 取两数绝对值进行无符号乘法，均为逻辑移位
2. 乘数从低位开始逐位判断：
- 若当前位为 1：部分积 + 被乘数绝对值，再右移1位
- 若当前位为 0：直接右移1位
3. 最终结果符号 = 被乘数 ⊕ 乘数
原码除法
（加减交替法） 符号位异或 1. 取被除数、除数绝对值
2. 初始化：余数 = 被除数绝对值
3. 每步操作：
- 余数 ← 余数 - 除数绝对值（即 +$[-y^*]_{\text{补}}$）
- 若 ≥0：上商 1，左移，继续减除数
- 若 <0：上商 0，恢复余数（+除数），左移，再减除数
（改进版：用“不恢复余数法”替代）
补码乘法
（Booth算法） 不单独处理
（符号参与运算） 使用 Booth一位乘法：
1. 被乘数$x$、乘数$y$均为补码
2. 扩展乘数一位附加位$y_{n+1} = 0$
3. 从右到左扫描$y_i y_{i+1}$：
- 00 / 11 → 右移1位
- 01 → +$[x]_{\text{补}}$，再右移
- 10 → +$[-x]_{\text{补}}$，再右移
4. 共n+1次加法，n次移位
补码除法
（加减交替法） 不单独处理
（符号参与运算） 1. 被除数$[x]$、除数$[y]$均为补码
2. 首次操作：
- 若$[x]$与$[y]$同号 → +$[-y]_{\text{补}}$
- 若 异号 → +$[y]_{\text{补}}$
3. 之后每步：
- 若余数与除数同号 → 上商 1，左移，+$[-y]_{\text{补}}$
- 若异号 → 上商 0，左移，+$[y]_{\text{补}}$
4. 共n步，最后一步不左移
5. 余数可能需校正（与被除数同号）

$$ n位有符号数乘法未溢出判断＝\frac{n}{2}+1位为{\color{red}全0或全1} $$

  • 常见指令的判断模式
指令 同义名 跳转条件 描述
jmp 无 直接跳转
je jz ZF = 1 相等
jre jnz ZF = 0 不相等
js SF = 1 负数
jns SF = 0 非负数
jg jnle SF=OF AND ZF=0 有符号大于
jge jnl SF=OF OR ZF=1 有符号大于或等于
jl jnge SF≠OF AND ZF=0 有符号小于
jle jng SF≠OF OR ZF=1 有符号小于或等于
ja jnbe CF=0 AND ZF=0 无符号大于
jae jnb CF=0 OR ZF=1 无符号大于或等于
jb jane CF=1 AND ZF=0 无符号小于
jbe jna CF=1 OR ZF=1 无符号小于或等于
  • 在补码表示中， 对于同号的负数，其二进制位模式（当作无符号整数）越大，其实际数值也越大。最好还是换成十进制数验算。
  • 补码左移->符号位也参与移动->若左移前，符号位与原次高位不同，则左移后会溢出->一次溢出全部溢出

主存、Chche与存储器

  • TLB、Cache使用SRAM（S更稀有），TLB在MMU中。
  • 主存＝ROM+RAM
  • 微指令
    • 控制存储器（CS）按微指令的地址访问，存储微指令 $$ 单个水平段＝\lceil log_2(一类互斥微指令数+1) \rceil $$
    • 断定法->下地址字段
    • 增量计数法->CMAR/μPC
    • 字段直接编码$微命令数量＝2^{字段长度n}-1$<=>直接控制法＝$1bit一条微命令$
    • 字段直接编码电路更复杂更慢
    • 首条微指令地址$\xrightarrow{来自}$指令操作码OP
微指令编码方式 速度 CM占用
直接编码 快 占用大
字段直接编码 慢 占用小
微指令格式 特点
水平 能平行，指令长
垂直 单条单功能，适合人民群众的编写
  • Cache
    • Cache关联度->Cache中每个组（set）可以容纳的缓存行（cache line）数量
    • 提高Cache的关联度能够一定程度上降低Cache的缺失，但不绝对。
    • 直接映射和组相联映射都有可能缺失率100％
    • Cache缺失与本身结构、替换算法都有关
    • 效率＝$\frac{单次Cache访问耗费时间}{实际平均访问时间}$
Tag 有效位 修改位*(回写法) 替换信息位*($n=log_2路数$) Cache块

  • DRAM使用 地址复用技术（SDRAM $\in$ DRAM）->需要行/列地址选通引脚->刷新使用一个存储周期

  • CDROM为串行存取，快速随机播放->连续结构

  • 链接完成重定位->逻辑地址

  • 装入或程序运行时->物理地址

  • M[Imm16]为 直接寻址

  • 存储器的扩展

    • 字扩展->高地址产生片选信号
    • 位扩展->低地址产生片选信号

  • 每次传输$n$位数据=采用$n$位预取技术

  • IF和MEM段访存

  • 改进型CLOCK置换算法（访问位，修改位）

  • 工作集合->之前访问过的$k$个页面。

$$ \begin{cases} \text{先来先服务算法 FCFS} \begin{cases} \text{规则：根据进程请求访问磁盘的先后顺序进行调度} \ \text{优点：公平，简单} \ \text{缺点：如果进程过多则访问的磁道很分散，性能差，寻道时间长} \end{cases} \[10pt] \text{最短寻找时间优先算法 SSTF} \begin{cases} \text{规则：} \begin{aligned} &\text{优先处理的磁道是与当前磁头最近的磁道} \ &\text{可以保证每次的寻道时间最短，但是并不能保证总的寻道时间最短} \end{aligned} \ \text{优点：性能较好，平均寻道时间短} \ \text{缺点：可能产生“饥饿”现象} \end{cases} \[10pt] \text{扫描算法 SCAN} \begin{cases} \text{规则：} \begin{aligned} &\text{只有磁头移动到最外侧磁道的时候才能往内移动} \ &\text{移动到最内侧磁道的时候才能往外移动} \end{aligned} \[5pt] \text{优点：性能较好，平均寻道时间较短，不会产生饥饿现象} \[5pt] \text{缺点：} \begin{aligned} &①\text{只有到达最边上的磁道时才能改变磁头移动方向} \ &②\text{对最近扫描过的区域不公平，访问局部性方面不如 FCFS 和 SSTF} \end{aligned} \end{cases} \[10pt] \text{循环扫描算法 C-SCAN} \begin{cases} \text{规则：} \begin{aligned} &\text{规定只有磁头朝某个特定方向移动时才处理磁道访问请求} \ &\text{而返回时直接快速移动至起始端而不处理任何请求} \end{aligned} \[5pt] \text{优点：比起 SCAN 来，对于各个位置磁道的响应频率很平均} \[5pt] \text{缺点：} \begin{aligned} &①\text{只有到达最边上的磁道时才能改变磁头移动方向} \ &②\text{比起 SCAN 算法来，平均寻道时间更长} \end{aligned} \end{cases} \[10pt] \text{LOOK 调度算法} \begin{cases} \text{规则：} \begin{aligned} &\text{相比 SCAN，如果在磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向} \end{aligned} \[5pt] \text{优点：比起 SCAN 来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进一步缩短} \end{cases} \[10pt] \text{C-LOOK 调度算法} \begin{cases} \text{规则：} \begin{aligned} &\text{相比 LOOK，规定只有磁头朝某个特定方向移动时才处理磁道访问请求} \ &\text{而返回时直接快速移动至起始端而不处理任何请求} \end{aligned} \[5pt] \text{优点：比起 C-SCAN 来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进一步缩短} \end{cases} \end{cases} $$

  • 随机存取存储器特指RAM，随机存取功能是功能，存储器是存储器！
  • 低位交叉-满足程序的局部性原理
  • 双端口存储器->两套独立的读写端口、MAR、译码电路，但写操作互斥
  • Cache中比较器的个数＝比较次数=> $n路组相联$，位数=> $Tag位$
  • $n$体低位交叉编址周期 $$ 有效存储周期=\frac{单个存储体的存储周期}{n体低位交叉} $$
  • PROM是一次性的
  • 缺页中断与一般中断的区别
    • 产生和处理中断信号的时机不同：
      • 一般中断：CPU通常在一条指令执行完后检查是否有中断请求
      • 缺页中断：在指令执行期间，如果发现所要访问的指令或数据不在内存中，就会立即产生和处理中断信号。
    • 中断发生的次数不同：
      • 一般中断：一条指令在执行期间通常只产生一次中断。
      • 缺页中断：一条指令在执行期间可能产生多次缺页中断。例如，如果一条读取数据的多字节指令本身跨越两个页面，且这两个页面均不在内存中，则该指令的执行至少产生两次缺页中断。

指令执行与CPU

  • 区分RISC与CISC
    • RISC指令长短统一，CISC不统一
    • RISC寄存器数字化命名R0、R1，CISC有含义ebp、edx、eda
    • RISC寄存器多
    • RISC硬布线<=>CISC微程序控制器
    • 硬布线与微程序控制器在一个时钟周期内均不能发生变化=>单周期处理器不适用
  • 多处理器对内存的访问
    • 单一地址空间
特性 UMA (Uniform Memory Access) NUMA (Non-Uniform Memory Access)
内存访问时间 所有处理器访问内存时间相同 访问本地内存快，远程内存慢
架构特点 对称多处理（SMP） 非对称内存访问
扩展性 较差（通常≤8核） 优秀（可支持数百核）

  • 资源虚拟化

    • 时间片轮转->使得每个进程看似独占CPU->绝对可抢占
    • 内存分区->使得每个进程看似拥有整块内存
    • SPOOLing技术->需要多道程序设计技术->设备独立性软件

  • 缓冲区$\in$设备独立性软件

  • SPOOLing技术

    • 输出进程所需设备驱动程序 $\ge$ 2＝磁盘＋外设
    • 用户的输出数据先放入输出井$\in$硬盘
    • 输入输出进程只运行在内核态

  • 中断处理优先级 $\subset$中断屏蔽字寄存器->可软件修改

  • 单周期CPU的$CPI＝1$

  • 指令与数据Cache分离->减少了流水线的冲突

  • 多核处理器

    • 单芯片处理器，多核心
    • 技术＝维持Cache一致性、核间通信技术、对软件设计的挑战
    • 多个CPU共享统一地址空间，又各自拥有私有 $L_1 Cache$

  • 只使用Load/Store指令访存能够简化流水线复杂度

  • 单周期数据通路

    • 每个部件在一条指令的执行过程中只能使用一次。
    • 控制信号取值在一条指令执行过程中一直不变
    • 以 取数 指令所用时间为时钟周期＝取指令+寄存器读+ALU运算+存储器取数+寄存器写

  • 数据通路不包含控制器 $\xrightarrow{大体上}$寄存器＋ALU+MMU、Cache、中断与异常处理、浮点运算

  • $分支延迟槽数量 = 分支判断级数 - 1$

  • 异常（CPU内部/内中断）->由CPU内部检测，与当前指令有关

    • 故障Fault（在当条指令的执行过程中发生）->恢复后执行 原指令
      • 缺页异常（MMU $\in$ CPU）
      • 除0异常、非法操作码（指令译码阶段）
    • 自陷Trap（在 当条指令执行完后）->恢复后执行 下一条指令
      • debug打断点
      • 系统调用
      • 性能监控
    • 终止Abort
      • 随机发生的、不可恢复的、硬件故障

  • 中断

    • 发生于一条指令结束时/结束后
    • 硬件完成->关中断、保存断点$(PC+PSW)$、识别中断源
    • 中断服务程序完成（软件）->保存现场$(包括中断屏蔽字)$、中断事件处理、恢复现场、开中断、中断返回
    • 时钟中断 $\in$ 外部中断｜时钟管理->需要保护！
    • 访管中断、缺页中断 $\in$ 内部中断

  • 结构冒险

    • 硬件阻塞
    • 设置多个独立功能部件（指令Cache与数据Cache）
    • 功能段划分

  • 任何冒险的产生使用A与B

  • 预测错误->冲刷流水线上错误执行的指令

  • 保存PC仅能由硬件完成

  • 流水线的指标 $$ 吞吐率＝\frac{任务数}{完成任务所用时间}＝\frac{指令条数}{完成这些指令所用时间} $$ $$ 加速比＝\frac{不使用流水线时依次执行所有指令的时间}{使用流水线完成所有指令的时间} $$

  • 指令译码的控制信号只向流水线发送一次，然后通过流水线的方式向后传送，一个周期传送一段

  • 数组循环->变址寻址

  • 指令字长必须为编码单位的整数倍

  • 超标量流水线

    • CPU中有多条流水线
    • 单个时钟周期可以完成多条指令
    • 多个功能部件
    • 空间换时间
    • 流水线功能段的处理时间不变

  • 超流水线

    • 分成更多的段
    • 提升主频

  • CPU根据 总线的类型 区分数据与指令

  • 子函数调用中，与SP有关的指令，一般是取压入栈的形参，往上找push

  • CPU时钟周期与流水线之间的关系 $$ CPU周期＝max{单个功能部件}+流水段寄存器延时 $$

  • LFU与LRU

特性 LRU LFU
淘汰依据 最久未访问时间 访问频率统计
核心思想 "最近不用，以后也不用" "最少使用，最不需要"
适用场景 访问模式具有时间局部性 访问模式具有频率差异
  • 运算器＝ALU、累加器、暂存寄存器、通用寄存器组、PSW、移位器
  • 机器字长
    • 等于CPU内部整数运算部件与通用Register
    • 不一定等于指令寄存器（IR, Instruction Register）的位宽
      • 因为 机器字长反映的是数据处理能力，而 指令寄存器的位宽取决于ISA的设计
  • 直接寻址的寻址范围 $\ge 0$，因为主存地址没有负数
  • ALU位宽＝字长
  • CPI与ISA（指令集、传统结构）有关，与时钟频率等无关
  • 通用寄存器的个数与位数=>ISA
  • 零地址指令->操作数的地址隐含在堆栈指针中，无需给出
  • 一地址指令的运行中也可以涉及两个操作数（ACC提供隐含操作数）
  • 指令周期
flowchart LR
    subgraph 指令周期
        A[取指周期] --> B[间址周期]
        B --> C[执行周期]
        C --> D[中断周期]
        D --> A
    end

    %% 添加注释（使用虚线连接到主流程，提升美观性）
    style A fill:#f0f8ff,stroke:#333
    style B fill:#e6f7e6,stroke:#333
    style C fill:#fff8e6,stroke:#333
    style D fill:#ffe6e6,stroke:#333

    %% 注释节点（右对齐，使用更清晰的样式）
    FA[从主存中取出指令代码]:::noteStyle
    FB[取操作数有效地址]:::noteStyle
    FC[取操作数]:::noteStyle
    FD[先修改栈顶指针，后存入数据]:::noteStyle

    %% 连接注释（虚线）
    A -->| | FA
    B -->| | FB
    C -->| | FC
    D -->| | FD

    %% 样式定义
    classDef noteStyle fill:#d0ebff,stroke:#666,stroke-dasharray:4,stroke-width:1px,font-size:12px;
  • SM->GPU｜MM->现代CPU
  • 流水段寄存器
    • 指令译码得到的控制信号通过流水段寄存器传递给下一段
    • 各流水段间的流水段寄存器长度不同
  • 流水线阻塞
    • Cache缺失
    • 访存冲突
    • 外部中断
    • 空nop指令不会阻塞
  • 数组下标->非负->使用逻辑左移
  • 取指令阶段的控制信号
时钟 功能(按照功能写信号) 有效控制信号
C1 MAR←(PC) PCout, MARin
C2 MDR←M(MAR)，PC←(PC)+1 MemR,PC+1
C3 IR←(MDR) MDROut, IRin
C4 指令译码 无
  • 周期关系 $$ CPU周期＝机器周期＝n\cdot时钟周期 $$
  • 中断字寄存器对汇编程序员可见
  • 转移条件有$n$位=>$2^n-1$个转移条件
  • 时钟周期＝数据从状态逻辑单元经过组合逻辑到达另一个状态元件（R1＋暂存器$\xrightarrow{ALU}$R2 为一个周期）
  • ISA 只关注指令集本身所呈现的东西，即指令的功能与格式，并不关注与之无关的底层实现方式
  • 时钟中断
    • CPU时钟是硬件固有属性<=>系统时钟由OS设置
    • 时钟中断＝系统时钟->与CPU时钟无关
  • 指令字长度
    • 变长需要专门的PC自增器<=>定长不需要
    • 变长指令字每次可以按照最长的长度读取
  • 注意题目的 操作码字段不含寻址方式
  • 内核空间读数据/指令->静态操作，无需保护

总线与IO

  • IO总线

    • 命令字、状态字、中断类型号走数据线。
    • 操作类型（读操作、写操作、DMA使能、中断请求、复位）走控制线。

  • 具有存储功能->状态元件；否则为操作元件

  • IO端口与接口

    • 一个IO端口对应一个地址
    • 一个IO接口对应多个地址
    • 数据端口和命令端口都属于IO端口
    • 独立编址方式下需要设置专门的设备指令，地址可能与主存地址相同
    • 状态端口与 控制端口 可以合用同一个寄存器 $$ I/O端口\begin{cases} 含义：接口电路中可被CPU直接访问的寄存器\\ \color{#5b9bd5}分类：\begin{cases} 数据端口\xrightarrow[]{允许CPU读&写?}\color{red}允许读和写操作\ 状态端口\xrightarrow[]{允许CPU读&写?}\color{red}只能执行读操作\ 控制端口\xrightarrow[]{允许CPU读&写?}\color{red}只能执行写操作 \end{cases} \end{cases} $$

  • 设备与设备之间可以通过DMA直接通信，不经过处理机

  • 链式请求方式需要三根控制线（请求、忙、同意），与设备数量无关。

  • 单周期处理器

    • 不能使用单总线结构->把CPU、主存、IO都挂在一条线上，不支持并发传送，不适用于CPI＝1
    • 指令执行过程中控制信号不变
    • 处理器时钟频率较低

  • 分离事务的通信方式可以提高总线利用率

  • MDR位宽＝存储器总线宽度 -> 与存储单元的位宽无关

  • MDR不一定等于数据字长->数据字长是存取一次数据的数据宽度，可以不等于MDR

  • 通信方式

graph TD
    A[通信方式] --> B[同步]
    A --> C[异步]
    A --> D[半同步]
    C --> E[全互锁]
    C --> F[半互锁]
    C --> G[非互锁]
连接方式 时钟信号提供方 可靠性 速度 握手信号
同步 主机提供统一时钟 高 中等 无专门握手信号，依靠时钟同步
异步 各自独立时钟 低 快
半同步 主机提供时钟，外设有等待能力 较高 较快 由同步时钟控制
全互锁 双方互相确认 最高 慢 完整双向握手信号
半互锁 单向确认 中等 中等 单向握手信号
非互锁 无确认机制 最低 最快 无握手信号

  • 三态门控制连接与断开

  • 一条总线可以异步+同步同时支持

  • 单个总线时钟周期可以实现多次数据传输（上升沿一次＋下降沿一次）

  • 信号复用技术（地址线与数据线复用）不能提高总线带宽，甚至会降低。

  • PCI-E为串行总线

  • 多道程序可以提高IO设备使用率

  • 数据传送由DMA 直接控制总线完成

  • 有效带宽与工作方式 $$ 有效带宽＝纯数据速率\times工作方式(全双工为2) $$

  • 可编程中断控制器 $\in$ IO接口

  • 总线仲裁

    • 计数器定时查询
      • $log_2N$根线路
      • 从0开始->设备号小的优先级高
      • 从当前设备开始->各设备优先级相同
      • 从某个数$n$开始->$优先级_{设备号\ge n} >优先级_{设备号<n}$
    • 分布式仲裁不需要中央仲裁器

$$ \begin{cases} \text{\color{blue}单总线结构} \begin{cases} \text{结构：}\colorbox{#70ad47}{\textcolor{white}{\textbf{CPU、主存、I/O设备（通过I/O接口）共用一组总线}}} \ \text{优点：}\colorbox{#5b9bd5}{\textcolor{white}{\textbf{结构简单、成本低、易于扩展新设备}}} \ \text{缺点：}\colorbox{#ff0000}{\textcolor{white}{\textbf{带宽低、负载重、总线争用、不支持并发传输}}} \end{cases} \\ \text{\color{blue}双总线结构} \begin{cases} \text{结构：} \begin{cases} \colorbox{#70ad47}{\textcolor{white}{\textbf{主存总线}}}：\text{CPU、主存、通道间数据传送} \ \colorbox{#70ad47}{\textcolor{white}{\textbf{I/O总线}}}：\text{多个外设与通道间数据传送} \end{cases} \ \text{优点：}\colorbox{#70ad47}{\textcolor{white}{\textbf{分离I/O设备，减轻主总线负载，提升系统效率}}} \ \text{缺点：}\colorbox{#ffc000}{\textcolor{black}{\textbf{需增加通道等硬件，成本提高}}} \end{cases} \\ \text{\color{blue}三总线结构} \begin{cases} \text{结构：} \color{red} \begin{cases} \colorbox{#70ad47}{\textcolor{white}{\textbf{主存总线}}}：\text{CPU ↔ 内存，传地址/数据/控制} \ \colorbox{#70ad47}{\textcolor{white}{\textbf{I/O总线}}}：\text{CPU ↔ 各类外设通信} \ \colorbox{#70ad47}{\textcolor{white}{\textbf{DMA总线}}}：\text{内存 ↔ 高速外设，直接数据传送} \end{cases} \ \text{优点：}\color{red}\colorbox{#70ad47}{\textcolor{white}{\textbf{提升I/O性能，响应更快，系统吞吐量高}}} \ \text{缺点：}\color{red}\colorbox{#ff0000}{\textcolor{white}{\textbf{总线控制复杂，工作效率低，资源冲突风险高}}} \end{cases} \end{cases} $$

  • 中断是IO中最低的一层
  • 总线宽度＝数据线宽度
  • 总线事务分离会提高总线的利用率
    • 采用总线事务分离后，CPU 通过 MAR 将地址 给到主存后就放弃总线控制权。当主存准备好数据后，主存申请总线控制权将数据传输到 MDR。在准备数据的这段时间内总线可以被其他部件使用。
    • 若不采用事务分离策略，CPU 在给出地址后会一直占据着总线控制权，直到主存准备好数据，将数据送到 MDR 后才会释放 总线。
  • DMA 响应需要在总线事务后，而间址周期是根据指令的形式地址取出其有效地址， 也就是说间址周期本身就是一次总线事务。而不能在总线事务(间址周期)期间立刻响应 DMA 请求。
  • 通道
    • 次序
      • 编制通道程序（由通道指令组成，存放在主存中）
      • 启动通道
      • 组织IO操作
      • 通道程序结束后给CPU发中断
    • 用于内存与IO的交换

操作系统

基础

  • 编译程序->将高级语言源程序一次全部翻译成目标程序（目标代码文件）
  • 汇编程序->把汇编语言翻译为机器语言程序
  • MBR＝主引导技术<->引导扇区＝分区内OS
  • 操作系统＝实时＋分时＋批处理
  • OS的基本特征＝并发+共享，能使系统资源提高效率，中断是OS必须提供的
  • 实时操作系统的主要追求目标
    • 安全可靠
    • 及时响应
    • 快速处理
    • 不追求资源利用率
    • 在 被控对象规定时间 内处理来自外部的事件
  • 模块化操作系统
    • 动态加载新模块
    • 内核 外 的某个功能模块出错不会导致系统崩溃
    • 内核中的各个模块可相互调用
    • 难以调试和验证
  • 用户、交互、时间片->分时操作系统
    • 优先级(重要作业尽快)＋非抢占(不重要的作业也要继续，防止饥饿)
  • 微内核性能差，大内核性能好
  • 微内核
    • 内核足够小
    • 基于C/S模式
    • 策略与机制分离
    • 面向对象
    • 无文件系统服务
  • 分层式架构
    • 结构清晰、易于调试
    • 各层之间单向依赖、调用
    • 系统效率低（自上而下穿越多层）
    • 依赖关系不可变
    • 增加或替换一层不影响其他层
  • 批处理系统
    • 无交互能力，作业执行时用户无法干预
    • 单道批处理（主存只放一个作业）
    • 多道批处理（外存有作业队列，当前作业因IO暂停时切换）
  • 上电后启动过程
    • 上电->进BIOS->POST自检->中断向量表->OS引导
  • 外核
    • 未经抽象的硬件资源
    • 用户进程调用 库 请求OS外核的服务
    • 外核只管 硬件资源
  • 第一类VMM直接运行在 硬件 上，第二类VMM运行在较低的 用户态
  • OS命令接口＝联机用户接口（包括GUI）＋脱机用户接口
  • Unix $\in$ 宏内核
  • 程序存储结构 ![[Screenshot_20251102-204246.png]]
内存段 存储数据类型 特点
正文段(Text Segment) 程序代码(函数体)、字符串常量 只读区域，程序执行期间大小固定
数据堆段(Heap Segment) 动态分配的内存(malloc/calloc/realloc) 运行时动态增长，由程序员管理内存释放
数据栈段(Stack Segment) 局部变量、函数参数、返回地址、临时数据 自动管理内存，先进后出，函数调用时分配和释放
R/W 读/写数据段（Data Segment） 已初始化的全局变量和静态变量 程序启动时分配，属于静态内存区域
BSS段（Block Started by Symbol） 未初始化的全局变量和静态变量 程序启动时自动清零，不占用可执行文件空间

💡 说明：全局变量存储在 数据段（Data Segment） 或 BSS段，不属于堆或栈。

  • 已初始化的全局变量 → Data Segment
  • 未初始化的全局变量 → BSS Segment
    （BSS段常被归入广义的“数据段”范畴）

进程与线程

  • 进程的执行时间实际上是无法预知的，也并不能纳入到对调度算法的调整考量因素中。
  • OS根据PCB管理并发进程->CPU状态 $\in$ PCB
  • 处于临界区（访问临界资源）的进程也可以被抢占/中断，只是不解锁罢了
  • 各种调度级别
级别 进程状态 数据流 别称 备注
低级 就绪->运行 内存->CPU 进程调度 最基本
中级 挂起（阻塞）->就绪 外存->内存 内存调度 存储器管理中的对换功能，为了节省内存
高级 创建->就绪 外存->内存 作业调度（启动程序的计划） 每个作业只调入一次，调出一次
  • Peterson算法
    • $turn$变量表示轮到谁
    • 我想去，但你先（$turn$）
  • 哲学家问题
    • 破坏 循环等待
  • 程序的顺序执行具有可再现性<->多道程序并发执行无可再现性
  • 管道
    • 大小通常为一个页面
    • 半双工通信
    • 读写操作都有可能阻塞进程
    • 匿名管道->有血缘关系的进程｜命名通道->任何进程之间
    • 本质上是存在于内核空间的环形数组，没有磁盘文件实体
  • 除 $trap$ 指令外，所有只能都能在内核态执行
  • 中断
    • 是用户态转内核态的唯一途径
    • 用户程序、低级中断的处理程序可被中断
    • 中断处理程序 $\in$ OS程序
    • 中断允许的延迟时长不计入考量，用户IO设备的CPU时间为 $$ CPU用于I/O设备的占比=\frac{中断请求的相应和处理时间}{发出中断请求的间隔+中断请求的响应和处理时间} $$
    • 中断响应->中断周期->中断返回后执行下一条指令
    • 中断服务程序->中断周期结束后
    • 进入中断周期时=>一定处于 开中断 状态
中断类型 来源分类 触发原因 是否可屏蔽 典型响应处理 所属类别
缺页中断 内部中断 访问虚拟内存时页面不在物理内存中 否 操作系统调入所需页面 异常-故障
时钟中断 外部中断 系统定时器（如 PIT、HPET）到期 可屏蔽 操作系统进行时间片调度、更新时间 异常/中断请求
网络数据包到达中断 外部中断 网卡接收到数据包并通知 CPU 可屏蔽 操作系统读取数据包并交上层协议处理 硬件中断
DMA 中断 外部中断 DMA 控制器完成数据传输（如磁盘读写完毕） 可屏蔽 CPU 接管数据、通知进程 I/O 完成 硬件中断
系统调用中断 内部中断 用户程序执行 syscall 或 int 指令 否 内核执行请求的服务（如文件读写） 陷阱（Trap）
硬件故障中断 外部中断 如电源故障、内存校验错误（ECC） 不可屏蔽 系统紧急处理或关机 不可屏蔽中断（NMI）
断点中断 内部中断 执行 INT3 指令或调试断点触发 否 调试器暂停程序并显示状态 陷阱（Trap）
溢出中断 内部中断 算术运算结果溢出（如 x86 INTO 指令） 否 异常处理或错误报告 陷阱（Trap）
I/O 设备中断 外部中断 键盘、鼠标、磁盘等设备完成操作 可屏蔽 驱动程序读取数据或确认操作完成 硬件中断
除零异常 内部中断 执行除法运算时除数为零 否 操作系统终止进程或抛出异常 故障（Fault）
非法指令异常 内部中断 CPU 遇到无法识别或无权限执行的指令 否 操作系统终止进程或模拟指令 陷阱（Trap）或故障（Fault）

  • 用户态

    • 命令解释程序
    • 数据处理（寄存器清零指令）
    • 流程控制（设置断点）
    • 读操作

  • 特权指令

    • 直接管理与系统资源（IO指令只能在内核态运行）
    • 状态修改
    • 系统控制（停机指令）
    • 读取PSW
    • 写程序指针
    • 写IR

  • 多道程序系统

    • 进程并发
    • 不支持虚拟存储
    • 对共享资源管理
    • IO设备利用率高
    • 系统吞吐量大，开销大
    • 失去 封闭性和顺序性->封闭性＝进程的执行结果只取决于进程本身
    • 提高单击资源利用率的关键技术

  • 并发->同一时间间隔

  • 并行->同一时刻

  • 系统调用

    • 判别在于用户想 ，发出请求主体是用户的意愿， 发生在用户态，执行在内核态，目的是 请求系统服务
    • 每个系统调用都有对应的 内核服务例程
    • 传参->执行$trap$->执行内核服务例程->返回用户态
    • 进程切换属于系统调用过程中的事件，不发生在用户态，只发生在核心态。
    • 系统调用命令->若干参数+ 陷入指令
    • 是OS提供给程序员的 接口
    • 保存 PSW＋PC

  • 一般调用（子程序调用）

    • 保存 PC
    • 与 调用者 在同一状态，也可以发生在内核态

  • 批处理系统的最主要缺点是 缺乏交互性，可以并发执行多个程序。

  • 子程序调用只保存PC；中断保存PC和PSW

  • 硬实时操作系统中，任务必须在约定的时间内完成

  • 高响应比优先满足短任务优先+无饥饿， FCFS最不利于短任务 $$ 相应比＝\frac{t_{等待}+t_{运行}}{t_{运行}} $$

  • 间接消息通信通过 邮箱

  • 进程通信速度->需要中介和复制数据的速度最慢->共享内存速度最快

  • 互斥区必须遵守的准则

    • 空闲让进
    • 忙则等待
    • 有限等待

  • 互斥锁只能由对其加锁的进程或线程来解锁

  • 内存越界与内存泄漏

特性 内存泄漏 内存越界访问
本质 未释放已分配内存 访问非法内存地址
发生时机 malloc 后未 free 数组/指针操作越界
典型代码 忘记 free arr[n]、strcpy、p[-1]
后果 内存耗尽、性能下降 程序崩溃、数据损坏、安全漏洞
危险等级 中（长期运行问题） 高（立即崩溃或被攻击）
检测难度 较难（需工具） 较难，但 ASan 可有效捕获
是否 UB 否（只是浪费） 是！未定义行为（Undefined Behavior）
  • 调度算法与进程类型之间的关系
CPU繁忙（长作业） IO繁忙
FCFS SPF（平均周转时间最短）
  • 死锁
    • 避免＝银行家算法->没有使用任何一种死锁预防的一条，有就描述错误 $$ \sum_{i-1}^{n}Max_i各进程最大需求量 \lt 资源总数+进程数 $$
    • 破坏死锁的任一条件=死锁预防
    • 资源分配图出现环路 不能说明 发生了死锁，因为其他进程还有可能推进
    • 如果资源 只有一个，并且发生了环路，才说明发生了死锁
    • 本质＝系统资源分配不足+进程推进顺序非法
    • 判断死锁->化简后的资源分配图出现环路->死锁定理
特性 死锁预防 死锁避免 死锁检测与恢复
目标 完全防止死锁发生 避免进入不安全状态 检测并解决已发生的死锁
实现方式 破坏死锁四个必要条件之一 动态安全性检查 周期性检测+恢复机制
资源利用率 低（限制过多） 高（充分利用资源） 高（无限制分配）
系统复杂度 低（策略简单） 高（需预知需求+安全检查） 中等（需检测算法+恢复策略）
实时性 好（无需检查） 一般（需安全检查） 差（需检测周期）
典型算法 资源有序分配、一次性分配 银行家算法 资源分配图检测、进程终止
适用场景 对安全性要求极高的系统 资源需求可预测的批处理系统 死锁概率低或恢复代价可接受的系统
算法/策略 破坏的条件 原理
一次性资源分配 持有并等待 要求进程一次性申请所有所需资源，否则不分配任何资源，消除“等待时保持资源”的情况。
资源有序分配（按编号顺序） 循环等待 要求所有资源按固定顺序申请，破坏循环等待链。
资源抢占 不可抢占 强制回收某些进程的资源（可能导致计算状态丢失，需回滚）。
银行家算法 请求和保持（间接）或循环等待 通过预分配检查安全状态，避免进入不安全的“请求和保持”状态。
检测与恢复 不可抢占或循环等待 通过终止进程或回滚打破循环等待链，或强制释放资源。
  • 父进程与子进程可以同时使用同一个临界资源->临界资源分配给 进程，但 不共享虚拟地址空间
  • PV操作本质是一种低级进程通信原语（不可分割的指令序列），可以解决一切互斥问题
  • 线程
    • 不共享栈指针、寄存器
    • 共享进程代码段、打开的文件、全局变量、地址空间
    • 切换时需要更新PC+栈基址寄存器
    • 减少了程序执行时的时空开销
    • 同一进程/不同进程 内的线程都可以并发
    • 线程的一个 系统调用可以阻塞整个进程
    • 共享所属进程的地址空间->PDBR页目录基地址寄存器
    • 包含CPU现场，可以独立执行程序
    • 每一个线程相当于一个指令序列
  • 进程
    • (进程＝程序代码+数据+状态)->同一程序多次创建，运行在不同的数据集上->不同进程
    • 一个进程在其生命周期中可执行多个程序，但是同一时刻只能执行一个程序
    • 进程间通信＝共享内存+消息传递+管道+文件映射+套接字
    • 共享内存＝共享内存不是直接共享进程自身的内存空间，而是通过操作系统将同一块物理内存映射到多个进程的虚拟地址空间中。
  • 进程与线程的资源共享差异
资源类别 是否共享（父子进程） 是否共享（同进程线程） 说明
🖥️ 虚拟地址空间 ❌ ✅ 父子进程有独立地址空间；线程共享同一地址空间
🌐 全局变量 ❌（初始相同，后独立） ✅ 线程共享堆和全局数据；父子进程各自独立
🧱 堆（Heap） ❌ ✅ 线程共享堆；进程间堆不共享
📦 栈（Stack） ❌ ❌（每个线程独立栈） 每个线程有私有栈；父子进程栈完全独立
📄 代码段（Text Segment） ✅（只读） ✅ 可执行代码共享，通常只读
🔗 打开的文件描述符 ✅（继承后共享） ✅ 子进程继承父进程文件描述符；线程天然共享
🧩 环境变量 ✅（继承） ✅ 子进程继承；线程共享
🛑 信号掩码 ✅（继承） ✅ 但线程可单独设置屏蔽
🧮 寄存器状态 ❌ ❌ 每个执行上下文独立
📥 信号挂起集 ❌ ✅ 线程间共享挂起信号；父子进程独立处理
🤝 互斥锁、条件变量 ❌ ✅ 线程共享同步机制；进程需使用进程间同步
🗺️ 内存映射区 ❌ ✅ 线程共享 mmap 区域；进程不共享除非显式共享内存
  • 进程与线程的切换差异
切换类型 保存的寄存器 关键差异
进程切换 通用寄存器、PC、SP、BP、段寄存器、EFLAGS、CR3、浮点/向量寄存器 需切换地址空间（CR3），TLB 刷新，开销大
线程切换 通用寄存器、PC、SP、BP、EFLAGS、浮点/向量寄存器（按需） 共享地址空间（CR3 不变），TLB 保留，开销小
  • 进程数量受 内存大小 的限制
  • 降低进程优先级的时机->时间片用完
  • 提高进程优先级的时机
    • 进程长期处于就绪队列
    • 进程完成IO操作，进入就绪队列 $$ 单CPU有n个进程\begin{cases}n-1就绪+1运行 \ n阻塞 \end{cases} $$
  • 管程
    • 编程语言支持，是语法范围，无法创建和撤销
    • 只能有一个进程在其中运行
    • 条件变量只能在管程内的过程中访问
    • 实现互斥和同步
    • 定义了共享数据结构和各种进程在改数据结构上的全部操作
    • 包含
      • 管程名
      • 局部于管程的共享数据结构说明
      • 对该数据结构进行操作的一组过程
      • 对局部于管程的共享数据设置初值的语句
    • 条件变量本身是管程的局部数据，其操作（wait/signal）必须由管程内部定义的过程封装调用
    • 条件变量没有值->不需要初始化
操作 含义
wait() 当前线程释放管程，进入该条件变量的等待队列，直到被唤醒->阻塞该进程，并进入阻塞队列（一定）
signal() / notify() 唤醒一个在该条件变量上等待的线程（若存在，即不一定）
broadcast() / notifyAll() 唤醒所有在该条件变量上等待的线程

  • 信号

    • OS对每种信号都有默认处理程序
    • 进程可以给自己发信号
    • 内核可以给进程发信号
    • 内核态转用户态时会检查信号
    • 可以通过系统调用自定义信号处理程序 $$ 周转时间＝\frac{sum(每一个进程的:结束时间-提交时间)}{进程数量} $$ $$ 带权周转时间＝\frac{周转时间}{CPU时间} $$

  • 等待时间 $$ 等待时间＝周转时间-运行时间 $$

  • 响应时间＝进程从提交到首次产生第一个响应的时长->在RR中需要完成第一个响应的时间片才算

  • 短作业优先->平均等待时间、平均周转时间最短

  • TSL、Swap指令是硬件级别原子操作，不需要关中断，但不能实现让权等待

  • 时间片轮转

    • 调度对象为 内核级别线程，多少个内核级线程多少倍时间片。

  • 进程上下文 = 硬件上下文 + 软件上下文 + 地址空间上下文->代码+数据+所有运行环境

  • 过程调用只需要保存PC的值

  • 缺页中断处理过程中进程为阻塞态

  • 访问越界时进程被撤销

  • 实现临界区互斥的基本方法

算法名称 关键缺点
单标志法 严格交替进入临界区，导致进程可能长时间阻塞，即使另一个进程不在临界区也无法进入，**违背“空闲让进”**原则
双标志先检查法 两个进程可能同时进入临界区，因为都先检查对方标志后才设置自己的标志，导致“同时进入”，**违背“互斥”**原则
双标志后检查法 可能导致死锁，两个进程都设置自己的标志并等待对方退出，陷入无限等待，**违背“有限等待”、“空闲让进”**原则
Peterson算法 仅适用于两个进程，扩展性差；依赖严格交替和标志位，多进程场景无法直接使用，违背"让权等待"
  • 系统调用->内核态 <=> 调用系统调用->用户态
  • PCB中没有进程地址空间大小
  • 一个进程的所有线程
    • 只要有一个是运行态=>整个进程都是运行态
    • 只要有一个是就绪态=>整个进程都是就绪态（无运行态进程）
    • 全都阻塞=>整个进程是阻塞态
  • 获取pid->系统调用
  • 信号量作为资源本身破坏 循环等待
  • 中断处理程序只能是系统程序

内存管理

  • 紧凑技术-> 动态重定位分区
  • 地址映射由谁来完成
    • 虚拟存储器->操作系统
    • Cache与主存->硬件自动完成
  • 访问TLB缺页时，处理完缺页中断后会再访问一次TLB，所以共两次
  • 共享段表
    • 存在共享技术变量$count$，记录正在使用的进程数量，计数为0时回收共享段
    • 有存取控制字段，管理进程存取权限
    • 整个系统只有一张共享段表
    • 对于同一共享段，不同进程中可以用不同的段号标识
  • 固定分配 $\nrightarrow$ 全局替换
  • 最佳适应算法->产生小到难以利用的碎片
  • Belady异常->页帧数 $\uparrow$=>缺页中断 $\uparrow$
  • 所有策略都会抖动->减少抖动 $\xrightarrow{最终解决方案}$ 关进程
  • 分段式管理
    • 有利于程序动态链接
    • 分段方式对低级程序员、编译器不透明
存储管理方式 段表数量 页表数量 段表与页表数量关系 说明
段式管理 1 个/进程 0 —— 每个进程一个段表，每段对应一个连续的逻辑地址空间，无需页表
页式管理 0 1 个/进程 —— 每个进程一个页表（或多层次页表），逻辑地址空间整体分页
段页式管理 1 个/进程 多个（每段一个页表） 页表数 = 段数 进程有一个段表，每段有自己的页表，即“段表项指向该段的页表”
  • 虚存需要MMU的支持
  • 页缓冲队列是内核维护的一个链表或队列结构，指向那些已被换出但尚未释放或写回的物理页框，存放在主存中。 使得操作系统有机会“后悔”——若这些页被再次访问，可直接重新使用，避免磁盘IO。
  • 重定位寄存器仅有一个，根据PCB中的值切换。
  • 每次回收分区时仅合并同大小空闲分区->BuddySystem
  • 首次适应算法->按照地址升序排列
  • 对主存的访问最终还是以字节为单位
  • 请求、虚存 $\xrightarrow{根本}$ 不必将作业全装入内存（作业运行前、中）->扩充了内存
  • 内存保护 $\xrightarrow{软硬结合}$ OS+界地址寄存器
  • 内存映射文件
    • 按需加载
    • 修改内存实现写操作
    • 支持多进程映射同一文件
对比项 静态装入（Static Loading） 可重定位装入（Relocatable Loading） 动态重定位（Dynamic Relocation）
装入时机 程序运行前一次性完成 程序运行前装入 程序运行时动态完成
地址转换时机 装入时完成逻辑地址→物理地址转换 装入时完成重定位 运行时由MMU动态转换
是否支持多道程序 ❌ 不支持 ✅ 支持（但程序运行期间不能移动） ✅ 支持，且内存中可移动
重定位方式 固定地址装入，无重定位 装入时根据起始地址调整所有地址 使用重定位寄存器（基址寄存器）
地址修改位置 目标代码中直接修改地址 修改装入模块的地址（生成物理地址） 不修改代码，运行时加基址
灵活性 最低 中等 最高
是否需要硬件支持 ❌ 否 ❌ 否 ✅ 是（需要基址寄存器/MMU）
典型应用场景 单道程序系统 早期多道程序系统 现代操作系统（支持虚拟内存）
  • 页表基址寄存器->物理地址
  • 驻留集是指当前时刻，一个进程实际驻留在物理内存中的页面集合。
  • 工作集是指在最近一段时间内，进程实际访问过的页面集合->影响缺页率
  • 虚拟存储系统别忘了 访问页表＋访问主存内容
  • 请求分页存储$\ne$分页存储
    • 分页存储只是分页
    • 请求分页＝分页+虚拟内存
    • 存取方式字段$\in${只执行、只读、读写}
装入方式 VA->PA阶段 适用
绝对装入 编译 单道
静态重定位 装入 多道批处理
动态重定位 运行时（重定位寄存器） 现代OS
  • 动态、固定分区都是连续分配

文件管理

  • 一个 簇 应当包含的扇区数量与磁盘容量大小有关

  • 自举程序 $\in$ 主板BIOS

  • OS的引导程序 $\in$ 硬盘

  • 文件缓冲区的首地址指针的传递方向与形式

  • 文件IO $\in$ 系统调用

  • MBR（主引导记录）

    • 检查分区表是否正确
    • 确定活动分区
    • 结束时启动活动分区的启动程序（OS引导扇区）

  • 缓冲池

    • 空白缓冲队列
    • 插入队列
    • 输出队列

  • 目录文件由多个目录项组成，每个目录项记录文件名并指向描述文件属性的数据结构（FCB本身 或 inode编号），其中 inode 是现代文件系统中对 FCB 的进化形式，实现了文件名与元数据的解耦。

    • FCB 模式：文件的控制信息（元数据）随目录项存放 → 紧耦合
    • inode 模式：元数据独立存放，目录项只负责“名字 → inode 号”映射 → 解耦
    • 文件控制快在创建文件时创建，与文件一一对应

  • 数据块组织方式答题要点

    • 文件随机访问效率
    • 磁盘寻道时间
    • 减少磁头移动
    • 减少硬盘IO访存次数

  • 成组分解技术‘

  • 新硬盘->低级格式化->分区->逻辑格式化（创建文件系统）

  • 用户文件打开表=进程文件描述符表->进程独有

  • 硬链接共享同一个 内存索引节点

  • 连续分配、索引分配、散列分配 都有随机存取能力，唯独链接分配不具有

  • 绝对路径以根目录 / 开头

  • 磁盘最小读写单位->扇区

  • 磁盘存储器＝磁盘控制器+磁盘驱动器+盘片

RAID 中文名 最少磁盘数 容量利用率 冗余性 读性能 写性能 容错能力 适用场景
RAID 0 条带化（Striping） 2 100% ❌ 无 ⬆️⬆️ 高 ⬆️ 高 0块磁盘 高性能、无容错要求
RAID 1 镜像（Mirroring） 2 50% ✅ 有 ⬆️ 提升 ➖ 一般 1块磁盘 高可靠性、小容量
RAID 5 分布式奇偶校验 3 (n-1)/n ✅ 有 ⬆️ 高 ➖ 中等 1块磁盘 通用、性价比高
RAID 6 双重奇偶校验 4 (n-2)/n ✅✅ 强 ⬆️ 高 ⬇️ 较低 2块磁盘 高可靠性、大容量
RAID 10（1+0） 镜像+条带 4 50% ✅✅ 强 ⬆️⬆️ 高 ⬆️ 高 每组1块 高性能+高可靠
  • 磁道半径 $\uparrow$，位密度 $\downarrow$，道密度不变
  • 磁盘控制器（IO接口） 与磁盘驱动器
graph LR
    CPU -->|指令| Controller[磁盘控制器]
    Controller -->|控制信号| Drive[磁盘驱动器]
    Drive -->|数据| Controller
    Controller -->|数据| CPU

graph TD
    A[CPU] -->|发送I/O指令| B[磁盘控制器]
    B -->|解析指令,发送控制信号| C[磁盘驱动器]
    C -->|机械定位| D[磁头组件]
    D -->|读/写数据| E[磁盘表面]
    
    subgraph "数据流"
        F[内存] <-->|DMA传输| B
        B <-->|数据传输| C
        C <-->|电信号转换| D
    end
    
    style A fill:#e1f5fe
    style B fill:#f3e5f5
    style C fill:#e8f5e8
    style D fill:#fff3e0
    style E fill:#ffebee
  • 找到柱面->启动磁头->找到扇区
  • 软硬链接的共同问题->将目录中所有文件转移时，可能对同一个共享文件产生多份副本。
  • 混合索引的便捷计算方法->使用逻辑块号，对应简单
  • 多个进程可以同时读写一个文件
  • 网络硬盘->软链接
  • 文件访问控制＝用户访问权限+文件属性
  • close系统调用不会立即将文件的控制信息写回外存->因为说不定还有其他进程在用
  • inode
    • 文件逻辑结构与inode无关
    • 文件与硬链接指向inode
    • 存放存取控制权限
  • 逻辑记录是对文件存取的基本单位 $$ 平均启动磁盘次数＝\frac{盘块数量+1}{2} $$

设备管理

  • 驱动程序
    • 驱动程序与硬件密切相关->其中一部分必须使用 汇编语言 编写，可以固化在ROM中
    • 允许可重入->多进程同时访问，但不允许任何进程修改->共享程序段->减少对换次数
    • 不允许系统调用->驱动程序本身就运行在内核态
  • 处理机与核心的关系
    • 处理机＝CPU $\supseteq$ 单/多核
    • 单处理机 $\neq$ 单核
    • 多核CPU $\in$ 处理机的一种实现方式
  • 中断处理过程由 驱动程序完成
  • 时钟中断服务程序处理与时间有关的所有信息
    • 内核中时钟变量的值
    • 当前进程占用的CPU时间
    • 当前进程在时间片内的剩余执行时间
  • 中断或异常发生 后 CPU处于 内核态
  • 系统添加新类型设备时，需要注册相应的中断服务例程
  • 字符设备＝流设备，不可随机访问
  • 网络设备->描述具体网络设备属性和操作
  • 块设备->将抽象命令映射为底层操作

$$ \text{顺道出车} \begin{cases} \text{系统设备表（SDT）} \begin{cases} \text{记录整个系统中所有设备的情况，每个设备对应一个表目} \ \text{关键字段：} \text{设备类型 / 标识符 / } \color{red}{\text{DCT}} \text{ / } \color{red}{\text{驱动程序入口}} \end{cases} \[10pt] \text{设备控制表（DCT）} \begin{cases} \text{每个设备对应一张 } \text{DCT} \ \text{关键字段：} \text{类型 / 标识符 / 状态 / 指向 DCT 的指针 / 等待队列指针} \end{cases} \[10pt] \text{控制器控制表（COCT）} \begin{cases} \text{每个设备控制器对应一张 } \text{COCT}，\ \text{COCT 与 DCT 的关系是一对一} \ \text{关键字段：} \text{状态 / 指向 CHCT 的指针 / 等待队列指针} \end{cases} \[10pt] \text{通道控制表（CHCT）} \begin{cases} \text{每个通道对应一张 } \text{CHCT}，\ \text{CHCT 与 COCT 的关系是一对多} \ \text{关键字段：} \text{状态 / 等待队列指针} \end{cases} \end{cases} $$

^fd3597

  • 图形用户界面下，鼠标也需要缓冲->高优先级操作产生时需要在缓冲中记录鼠标活动情况
  • 单双缓冲区的理想效果（有限任务需要按照流水线完成）
    • $$IO设备 \xrightarrow{输入T} 缓冲区 \xrightarrow{传送M}工作区$$
    • 单缓大传统，再加一M$$Max(C,T)+M$$
    • 双缓只最大，充满一个T$$Max(C+M,T)$$

计算机网络

协议 字段名称 含义 单位 数值范围 说明
IP首部 首部长度(IHL) IP首部长度 4字节 5-15 最小20字节，最大60字节
IP首部 总长度 整个IP数据报长度 1字节 0-65535 包含首部和数据，不可能为0
IP首部 片偏移 分片在原数据报中的位置 8字节 0-8191 相对于原始数据部分
TCP首部 数据偏移 TCP首部长度 4字节 5-15 最小20字节，最大60字节
UDP首部 长度 UDP首部+数据长度 1字节 8-65535 包含8字节首部
以太网 长度/类型 数据长度或协议类型 1字节 0-1500或>1536 <1518为长度，>1536为类型
TCP/IP参考模型 对应的OSI七层模型
应用层 应用层、表示层、会话层
传输层 传输层
网络层 网络层
网络接口层（或主机-网络层） 数据链路层、物理层

$$ PDU本层封装整体=PCI本层控制信息+SDU上层数据 $$

OSI 层 层名 本层的 SDU 本层的 PDU 名称 服务访问点SAP 对等性
7 应用层 用户数据（如 HTTP 请求体） 应用层 PDU（数据） 用户界面
6 表示层 应用层 PDU 表示层 PDU（数据）
5 会话层 表示层 PDU 会话层 PDU（数据）
4 传输层 会话层 PDU 段（Segment）（TCP）
数据报（Datagram）（UDP） 端口号 端到端
3 网络层 传输层 PDU（段或数据报） 包（Packet） 协议 主机到主机
2 数据链路层 网络层 PDU（包） 帧（Frame） 类型 点对点
1 物理层 数据链路层 PDU（帧） 比特（Bit）流
OSI 层 拥塞控制 流量控制 差错控制 主要协议/方法
物理层 ❌ ❌ ❌ 无
数据链路层 ❌ ✅ ✅ 滑动窗口、ARQ、CRC
网络层 ✅（有限） ❌ ⚠️（检测，错误时丢弃包） ICMP源抑制、ECN、IP校验和
传输层 ✅ ✅ ✅ TCP：慢启动、滑动窗口（流量控制）、拥塞窗口（拥塞控制）、重传
  • 资源子网＝应用＋表示＋会话
  • 通信子网＝网络＋数据链路＋物理

物理层

  • T同轴电缆最长500m
  • 2.5Gbps及以上才需要严格全双工
  • 中曼起差，差看变化曼方向，中间跳变为时钟
  • 信号传播速度（例如光速）与数据传输速度无关
  • 香农公式的意义->只要信息传输速率低于信道的极限信息传输速率，就一定能找到某种办法实现无差错传输。
  • NRZ是最简单的串行编码技术，电平表示两个二进制数
    • NRZI用跳变沿的方向表示两个二进制数
编码类型 英文简称 数据表示（电平） 电平变化特点 是否需要同步 优点 缺点
不归零码 NRZ 1: 高电平
0: 低电平 整个位周期保持电平不变 ❌ 不自带时钟 简单、效率高 长串相同数据无跳变，难以同步
不归零反码 NRZI 1: 电平翻转
0: 电平不变 仅在发送“1”时翻转 ❌ 不自带时钟 抗干扰好，用于USB等 仍可能长串0无跳变
归零码 RZ 1: 前半周期高，后半归零
0: 始终低电平 每位中间都回到零电平 ✅ 部分同步 有明确时序边界 占用带宽大，效率低
反向归零码（曼彻斯特编码） Manchester 1: 高→低跳变（前高后低）
0: 低→高跳变（前低后高） 每位中间都有跳变 ✅ 自同步 自带时钟，抗干扰强 带宽是NRZ的2倍
差分曼彻斯特编码 Diff-Manchester 0: 位开始时跳变
1: 位开始时不跳变
（中间必跳变） 每位中间必跳变，起始跳变表示数据 ✅ 自同步 抗干扰强，用于令牌环网 编码复杂，带宽高

$$ \begin{cases} 奈式准则\xrightarrow[]{内容}\begin{cases} 理想低通条件下的极限{\color{red}码元}传输率为2W\ \text{Baud}\text{（W是带宽，单位是Hz）}\ 理想低通条件下的极限{\color{red}数据}传输率为2W\log_2V相位数\ \text{(b/s)} \end{cases}\\ 香农定理\xrightarrow[]{内容}\begin{cases} \text{求的是：}带宽受限且有高斯白噪声干扰的信道的{\color{red}极限数据传输率}\ \color{red}信道的极限传输率=W\log_2(1+\dfrac{S}{N})\text{（单位为b/s）} \ \dfrac{S}{N}为信噪比，即\dfrac{信号的平均功率}{噪声的平均功率}，单位为分贝\text{（dB）} \end{cases} \end{cases} $$

  • 香农公式->数据速率(bps)且用不到电平数量｜奈氏准则->码元速率（Baud）
  • 数据速率＝码元速率$\times$离散电平数（信号状态数）
  • 信噪比、码元离散电平数同时给定->全部计算，取 最小值 $$ 以太网电缆带宽＝2\times 数据速率 (曼彻斯特编码1bit信号需要两个信号) $$
  • 最小帧长根据RTT计算，是一个来回 $$ 以太网线路最大长度＝\frac{64B}{数据传输速率}\times 信号传播速度\times \frac{1}{2} $$
  • 需要考虑比特含义、引脚含义，不需要考录具体的传输媒体->传输媒体是第0层

数据链路层

CSMA/CD（数据链路层协议代表）

  • 有线网
  • 边发边检测
  • 信号传播延迟->0时，信道利用率->100%
特性 非坚持 CSMA 1-坚持 CSMA p-坚持 CSMA
信道空闲时行为 立即发送数据 立即发送数据 以概率 p 发送，以概率 1-p 推迟到下一个时隙
信道忙时行为 放弃监听，等待一个随机时间后重新检测 持续监听，一旦空闲立即发送 持续监听，一旦空闲按概率 p 决定是否发送
延迟与冲突权衡 冲突较少，但延迟较高（因放弃监听） 冲突较多（多个站点同时发送），延迟较低 可调节 p 来平衡冲突与信道利用率
适用场景 负载较重的网络，减少冲突 轻负载、对延迟敏感的环境 介于两者之间，适用于时分信道（如无线）
优点 减少冲突，网络较稳定 响应快，信道利用率高 灵活控制发送概率，适合高负载调节
缺点 信道可能空闲（因随机延迟），利用率低 高冲突概率（尤其高负载时） 需要合理选择 p，否则性能下降
备注 只适用于 划分时隙 的信道

  • 非坚持：听不到就走，随机再回头 → 低冲突，高延迟

  • 1-坚持：听到空就发，听到忙就等 → 高利用率，高冲突

  • p-坚持：听到空，以概率 p 发 → 可调平衡点

  • 二进制指数退避算法的第$k$次重传成功概率 $$ p_{成功}=1-(0.5)^k $$ $$ r=random[0,2^k-1],k=min[重传次数,10] $$ $$ 等待时间＝争用期(512比特时间)\times r $$

  • 转发16次后返回原点抑制的ICMP

  • 退避结束后还需要等9.6微秒（以太网帧间最小间隔）

CSMA/CA

  • 必须采用退避算法的几种情况
      1. 要发送数据时检测到信道忙
      1. 上一次发送失败（未收到ACK）
      1. 接着发送后续的数据帧
  • 不需要退避的情况
    • 若信道一直空闲，且站点有数据要发，在等待一个 DIFS 后可直接发送
  • NAV值（均以SIFS起手，ACK结束）
帧 值
RTS SIFS + CTS+ SIFS + 数据帧传输时间 + SIFS + ACK
CTS SIFS + 数据帧传输时间 + SIFS + ACK
  • 退避算法
    • 争用窗口$CW＝2^k-1$为自定义
    • 第$i$次重传的争用窗口 $$ CW＝2^{k+i}-1 $$
    • 退避时隙数$\in [0,CW]$

时延计算->流水线思想

所有条件

数据共$x$位，经过$k$段链路($k-1$个路由器)，每段链路的传播时延为$d$秒，数据传输速率为$b\space b/s$

  • 电路交换（建立连接的时间为$c$）->不需要预分配带宽 $$ 电路交换时延＝建立连接+总传播时延+发送时延=c+kd+\frac{x}{b} $$
  • 分组交换（分组长度为$p$） $$ 分组交换时延＝第一个分组的整体时间+剩余分组的传送＝k(d+\frac{p}{b})+(\frac{x}{p}-1)\frac{p}{b} $$
部分条件（崔锴华公式）

分组长$L$，传输速率$R$，总共有$n$个分组，中间有$k$个路由器 $$ T=(n+k)\frac{L}{R} $$

CDMA

  • 如果内积为0，则未发送数据

ARQ

  • GBN可以达到的最大平均数据传输速率 $$ GBN最大平均数据传输速率＝\frac{数据帧长\times窗口尺寸}{RTT} $$

  • ARQ利用率通用公式 $$ ARQ利用率＝\frac{t_{数据}\times W_T}{t_{数据}+RTT+t_{ACK}} $$

    $t_{数据}$->传输一个帧的时长＝发送时延

    $W_T$->发送窗口大小

    $t_{ACK}$->捎带确认时 $t_D=t_{ACK}$，S-W中 $t_{ACK}=0$

  • JB累计1接收

特性 🟥 Stop-and-Wait 🟨 Go-Back-N 🟩 Selective Repeat
ACK类型 单独ACK 累计ACK 逐帧ACK
失序帧处理 丢弃 丢弃 ✅ 缓存
是否使用NAK ❌ 否 ❌ 否 ✅ 是
NAK类型 无 无 逐帧NAK
ACK编号含义 "已收帧n" "0~n全收" "帧n已收"
NAK编号含义 无 无 "帧n出错，请重传"
重复ACK产生原因 无 接收失序帧时提示缺失帧 无
重发触发条件 超时 最早未确认帧超时 NAK或超时
重发范围 帧n 帧n及之后所有未确认帧 仅帧n
发送窗口大小$W_{send}$ $1$ $≤ 2^k - 1$ $≤ 2^{k-1}$
接收窗口大小$W_{recv}$ $1$ $1$ $≤ 2^{k-1}$
窗口约束公式 无 $W_{send} ≤ 2^k - 1$ $W_{send} + W_{recv} ≤ 2^k$
定时器 每帧一个 一个（最早未确认） 每帧独立（备用）
缓存需求 无 无 接收方需缓存
响应延迟 高（需超时） 高（需超时） 低（NAK即时）
适用场景 简单链路 低误码率网络 高误码率、无线

令牌环网

  • 令牌环网无数据传输直接传给下一个不等待，有数据传输也是到固定时间就给下一个，不一定传完
  • $Max(时间)=sum(站点传送令牌+发送帧)$

设备

  • 网桥也是数据链路层，用于连接不同网段。交换机本质上就是一个多端口网桥

  • 网桥MAC地址表

    • 源站MAC
    • 端口号
    • 帧到达时间

  • 交换机各端口独享带宽

  • 直通交换 $$ 转发延迟＝\frac{目的MAC(6B)}{网络速率} $$

  • 最远距离 $$ 最远距离＝(\frac{以太网最小帧长64B}{网络速率}-直通交换转发延迟)\times 信号传播速度 $$

  • 交换机 即使知道某个端口的MAC，ARP广播帧依旧会广播

    • ARP广播会无脑转发除来源端口外的所有端口

  • 802.1Q ^8592a1

端口类型 英文名称 主要用途 数据帧处理方式 典型应用场景
接入端口 Access Port 连接终端设备（如PC、打印机） - 只属于一个VLAN（PVID）
- 发送时不带标签（Untagged）
- 接收无标签帧时自动打上PVID标签 接入层连接用户设备
中继端口 Trunk Port 连接交换机、路由器或服务器（需支持VLAN） - 可VLAN
- 发送和接收时通常带标签（Tagged）
- 允许的VLAN列表可配置
- 本征VLAN（Native VLAN）可不打标签 交换机之间互联，传递多VLAN信息
混合端口 Hybrid Port 灵活连接终端或交换机（华为/华三特有） - 可同时传输多个VLAN
- 可配置哪些VLAN打标签，哪些不打标签
- 灵活性最高 复杂网络环境，如服务器需接入多个VLAN但部分不打标签

PPP

  • 差错检测不纠正
  • 动态IP
  • 多种协议（NCP）
  • 身份验证（LCP）
  • 有连接不可靠
  • 支持多种网络层、数据链路层协议
  • 无确认机制
  • 转义
项目 内容
转义字符 0x7D
转义方法 0x7D + (原字节 XOR 0x20)
必须转义的字节 0x7E, 0x7D,小于0X20的ASCII控制字符
转义结果 - 0x7E → 0x7D 0x5E
- 0x7D → 0x7D 0x5D
可选转义的字节 0x00 ~ 0x1F（控制字符）
解码方式 遇 0x7D，下一字节 XOR 0x20
目的 保证数据透明性，避免与控制字符冲突

MAC与LLC

  • MAC地址

    • 每次转发源目都以实际为准
    • 以太网MAC无连接不可靠

  • MAC与LLC子层

MAC LLC
介质访问控制 流量控制、差错控制

以太网

  • 无确认无连接
对最短时延与距离的计算
  • 前提：以太网规定的最短帧长＝$64B$；争用期＝$51.2\mu s$ $$ 最短帧长＝RTT\times 数据速率 $$
  • eg.两主机中间多出来 $1.535\mu s$，信号传播速度为 $200m/\mu s$ $$ 最大距离＝(原有最大单程传播时延-多余时延)\times 信号传播速度 $$ $$ 原有最大单程传播时延＝\frac{RTT}{2}=\frac{最短帧长}{数据速率}\times \frac{1}{2} $$

校验与纠错

  • 海明码的手算与公式（纠错一位） $$ 2^r -1\geq k + r $$
  • 校验字段与反码求和
  • CRC的冗余码位数与生成式最高次数，不够的在前面补0
  • UDP校验全0为不校验｜计算结果为全0时设置为全1｜计算结果不可能全1
  • IP首部校验使用二进制反码求和取反，是为了节省时间

802.11

地址类型 四地址模式AP to AP 速记 三地址模式 速记
Address 1 RA (Receiver Address) 直接发 RA (Receiver Address) 直接发
Address 2 TA (Transmitter Address) 直接收 TA (Transmitter Address) 直接收
Address 3 DA (Destination Address) 本质发 DA/SA (Destination/Source Address) 本质
Address 4 SA (Source Address) 本质收 不使用 －

网络层

  • TTL先减一再判断，为0就丢弃+超时
  • ICMP
    • ICMP在网络层的IP数据报中
    • Ping是询问报文，tracert是超时报文
类型（Type） 代码（Code） 报文名称 功能描述 出现时机
0 0 Echo Reply 回显应答（ping响应） 收到Echo Request后，目标主机回复ping响应
3 0-15 Destination Unreachable 目的不可达 路由器或主机无法交付数据包时（如网络不可达、主机不可达、端口不可达等）
5 0-3 Redirect 重定向 路由器发现主机使用了非最优路径，通知主机改用更好的下一跳
8 0 Echo Request 回显请求（ping请求） 执行ping命令时，源主机发送探测报文
11 0-1 Time Exceeded 超时（TTL过期） IP数据包TTL减为0时由路由器丢弃并发送；或分片重组超时
12 0-1 Parameter Problem 参数问题 IP头部存在错误字段或缺失必需选项时
13 0 Timestamp Request 时间戳请求 请求获取目标主机的当前时间
14 0 Timestamp Reply 时间戳应答 收到时间戳请求后，目标主机返回当前时间
17 0 Address Mask Request 地址掩码请求 无盘工作站启动时请求子网掩码
18 0 Address Mask Reply 地址掩码应答 收到地址掩码请求后，本地路由器返回子网掩码
  • 路由器不会将数据包从来源端口转发回去
  • 不被互联网路由器转发的私有IP地址范围私有地址
地址范围 前缀 子网掩码 速记
10.0.0.0 ~ 10.255.255.255 10.0.0.0/8 255.0.0.0 10开头
172.16.0.0 ~ 172.31.255.255 172.16.0.0/12 255.240.0.0 172.16-31
192.168.0.0 ~ 192.168.255.255 192.168.0.0/16 255.255.0.0 192.158开头
  • 默认路由0.0.0.0/0
  • 静态路由x.x.x.x/32
  • 子网地址无子网掩码
  • RIP、BGP是应用层，OSPF是网络层
RIP跳数计算规则 说明
直连网络 跳数为 0
每经过一台路由器转发 跳数 +1
最大跳数 15（16表示不可达）
  • BGP路径向量
  • 路由表中最长匹配原则使其不影响小包大
  • TTL减一，IP校验和重算
  • ARP工作在网络层
  • 路由器检测到拥塞时可以合理丢弃IP分组
  • 路由器对收到的IP分组进行差错检验，丢弃出错报文，但不保证不丢失。
  • 本地广播地址表示本网段的所有主机，仅限当前 广播域
  • IP协议字段
协议字段值 协议名称 说明
1 ICMP 网络控制消息协议，用于ping、traceroute等
2 IGMP 组播管理协议
6 TCP 面向连接的可靠传输协议
17 UDP 无连接的不可靠传输协议
41 IPv6 IPv6封装
47 GRE 通用路由封装协议
50 ESP IPSec封装安全载荷
51 AH IPSec认证头
89 OSPF 开放最短路径优先路由协议
103 PIM 协议无关组播
112 VRRP 虚拟路由器冗余协议
  • IPv6
    • 地址省略方法->前省后不省，双冒就一次
    • 通信量类->优先级（越高越牛逼）
    • 跳数限制＝TTL
    • 取消了首部校验
    • 数据载荷中可以包含扩展首部＝IPv4首部中的可选字段
    • 仅在源主机端可以分片，中间不可分
  • IGMP组播
    • 01-00-5E+一位0+IP地址后23位
    • 交换机只检查MAC，MAC一致就能收到，例如224.128.64.32与224.0.64.32
    • 主机接收到后根据IP丢弃
  • TCP/IP参考模型中网络层无连接=>无流量控制
  • 流量控制与拥塞控制的区别
  • IPv6的数据流＝源目地址+流标号
  • SDN
    • 控制平面（上北）
    • 数据平面（下南）
  • 0.0.0.0可以作为目的地址->默认路由

传输层

  • UDP校验和按照2B对齐，不足补0。若结果全0，字段全1。

  • UDP出错，可丢可交付。

  • UDP 检验和段的使用是可选的，若源主机不想计算检验和，则该检验和段应为全 0。

  • 吞吐率 $$ 吞吐率＝\frac{发送窗口大小}{RTT＋发送时延} $$

  • 分组交换的分组与MTU的分片

    • 分组的排序->传输层
    • 分片的重组->网络层

  • TCP的四种计时器

计时器 功能 启用时机 超时动作
1. 重传计时器（Retransmission Timer） 超时重发未确认的报文 发送数据/ACK/FIN/SYN 后等待确认 重传该报文
2. 坚持计时器（Persist Timer） 防止零窗口死锁 接收到对方窗口为 0 的 ACK 定期探测窗口是否恢复
3. 保活计时器（Keepalive Timer） 检测空闲连接是否存活 连接长期无数据传输（可选启用） 发送探测包，判断对方是否宕机
4. 时间等待计时器（TIME-WAIT Timer） 等待足够时间关闭连接 第四次挥手完成后进入 TIME_WAIT 状态 超时后关闭连接
5. 保活探测计时器（Keepalive Probe Timer） 控制保活探测间隔 保活计时器超时后开始探测 每隔一段时间发一次探测
  • 四次挥手中的客户端与服务器状态转换
    • 2MSL
      • 保证最后一个ACK到达
      • 防止旧TCP报文段对后续连接产生干扰
stateDiagram-v2
    [*] --> ESTABLISHED : Active Open

    ESTABLISHED --> FIN_WAIT_1 : 发送 FIN
    FIN_WAIT_1 --> FIN_WAIT_2 : 收到服务器ACK
    FIN_WAIT_2 --> TIME_WAIT : 收到服务器FIN，发送ACK
    TIME_WAIT --> CLOSED : 等待 2MSL（计时器超时）
    
    note right of TIME_WAIT
      计时器：2MSL（通常为60秒）
      防止旧连接报文干扰新连接
    end note

stateDiagram-v2
    [*] --> ESTABLISHED : 接收SYN, 完成三次握手

    ESTABLISHED --> CLOSE_WAIT : 收到客户端FIN，发送ACK
    CLOSE_WAIT --> LAST_ACK : 发送自己的FIN
    LAST_ACK --> CLOSED : 收到客户端ACK
    
    note right of CLOSE_WAIT
      服务器等待应用关闭连接
      无固定计时器，由应用控制
    end note

    note right of LAST_ACK
      等待客户端ACK
      若未收到，可能重传FIN（有重传计时器）
    end note

  • TCP握手1中的ACK无效，对对方下次发送的数据无要求。

  • TCP在连接建立之后所有报文ACK均需要置为1，握手1的ACK不置1

  • TCP特殊情况的窗口处理

    • 超时（发送方未收到确认，发送方判断网络出现拥塞） $$ ssthresh=\frac{当前拥塞窗口cwnd}{2} \geq 2，拥塞窗口cwnd＝1 $$
    • 快恢复（接收方发送三个冗余ACK，接收方判断网络出现拥塞） $$ ssthresh=\frac{当前拥塞窗口cwnd}{2} \geq 2，拥塞窗口cwnd＝\frac{当前拥塞窗口cwnd}{2} $$

  • 接上分，发下复

    • 复用：发送端向下发到传输层使用同一个协议
    • 分用：接收端向上交付给进程用端口

  • 慢开始阶段->$\times2$阶段

  • 拥塞避免阶段->$+1$阶段

  • 当 TCP 发生 超时 时， 在超时发生的那一刻（当前 RTT 内）就立即将 cwnd 设置为 1 MSS，并进入慢启动阶段。

  • TCP将收到的报文段组成字节流交给上层

  • 仅TCP有序号

    应用层

  • DHCP为应用层UDP协议

报文 源IP 目的IP 源MAC 目的MAC
Discover发现 0.0.0.0 255.255.255.255 客户端MAC FF:FF:FF:FF:FF:FF
Offer提供 DHCP服务器IP 255.255.255.255 服务器MAC 客户端MAC
Request请求 0.0.0.0 255.255.255.255 客户端MAC FF:FF:FF:FF:FF:FF
ACK确认 DHCP服务器IP 255.255.255.255 服务器MAC 客户端MAC
  • 移动IP为网络层协议
    • 外部代理转发给漫游移动站的数据报目的IP为 归属地址＝永久地址
  • SMTP
    • 用户代理->邮件服务器
    • 邮件服务器<->邮件服务器
    • 只能传输7bit的ASCII码
  • BGP<->TCP
  • EGP<->IP
  • DNS
    • 域名空间＋ 联机分布式数据库系统＋ 域名服务器
    • DNS最大查询次数＝段的个数
    • 本地域名服务器->根域名服务器->顶级域名服务器->权限域名服务器
    • 最开始的 主机名不需要查DNS
    • DNS报文->UDP数据报->IP数据报->以太网帧
  • HTTP响应报文不一定需要实体主体字段
  • BGP报文
报文类型 发送频率 典型场景
OPEN 每次会话建立时1次 初始连接
UPDATE 变化时发送 路由变更
NOTIFICATION 错误时发送 故障处理
KEEPALIVE 周期性（约1-2分钟） 会话维持
ROUTE-REFRESH 按需发送 路由策略调整
  • OSPF报文
类型 报文名称 主要功能
1 Hello 发现和维护邻居关系
2 DBD 交换链路状态数据库摘要
3 LSR 请求具体的LSA信息
4 LSU 发送LSA更新信息
5 LSAck 确认收到的LSA
  • HTTP报文
    • Connection
      • Close非持续连接
      • keep-alive持续连接
  • 224.0.0.2 是所有路由器的多播地址，用于局域网内路由器之间的通信。常用于路由协议（如 OSPF 和 RIP）之间的路由更新和多播路由同步，确保路由器共享最新的路由信息。
特性 主动模式 (Active) 被动模式 (Passive)
控制连接端口 客户端任意端口 → 服务器21 客户端任意端口 → 服务器21
数据连接建立 服务器20 → 客户端指定端口 服务器随机端口 → 客户端任意端口
客户端防火墙 需开放指定端口范围 仅需允许出站连接
服务器防火墙 仅需开放20、21端口 需开放大量随机端口
NAT环境适应性 ❌ 差 ✅ 好
协议名称 端口号 类型 说明
HTTP 80 TCP 超文本传输协议
HTTPS 443 TCP 安全超文本传输协议
FTP 20, 21 TCP 文件传输协议(20-数据, 21-控制)
SSH 22 TCP 安全外壳协议
Telnet 23 TCP 远程登录协议
SMTP 25 TCP 简单邮件传输协议－发送
DNS 53 UDP 域名系统
DHCP 67, 68 UDP 动态主机配置协议(67-服务器, 68-客户端)
TFTP 69 UDP 简单文件传输协议
POP3 110 TCP 邮局协议版本3－收
  • FTP
特性 主动模式 (Active Mode) 被动模式 (Passive Mode)
连接建立方式 客户端打开控制端口，服务器主动连接客户端的数据端口 客户端打开控制端口，客户端主动连接服务器的数据端口
数据连接发起方 服务器 客户端
服务器行为 服务器从20端口主动连接到客户端指定端口 服务器打开随机端口等待客户端连接
防火墙兼容性 客户端需开放端口，可能被防火墙阻止 客户端主动连接，通常不受防火墙影响
NAT环境支持 不友好，容易失败 友好，适用于NAT环境
安全性 较低，服务器主动连接客户端 较高，客户端控制连接
网络配置要求 客户端需允许外部连接 无特殊要求
典型应用场景 传统网络环境 现代网络环境，有防火墙/NAT

© 本文著作权归作者所有，未经许可不得转载使用。