前置知识: C语言, 电路基础, 微积分, 代数学, 概率论.
*号章节为私货内容.
补充材料: C语言参考手册

信息表示和处理

*信息论

无损压缩: 游程, Haufmann

纠错码: Hamming, CRC

*数字逻辑

$\bar{ }$ 逻辑/按位非, $+$ 逻辑/按位或, $\cdot$ 逻辑/按位与, $\oplus$ 逻辑/按位异或;
$\ll^L_{(n)}$ 逻辑左移 $n$ 位, $\ll_{(n)}$ 算术/按位左移 $n$ 位, $\lll_{(n)}$ 逻辑循环左移 $n$ 位, $\lll^\alpha_{(n)}$ 算术/按位循环左移 $n$ 位.

平凡 Bool 代数: $\mathcal{B}=(\{0,1\},+,\cdot)$, $b,c,d\in \{0,1\}$.
恒等律: $b+0=b$, $b\cdot 1=b$.
0-1 律: $b+1=1$, $b\cdot 0=0$.
互补律: $b+\overline{b}=1$, $b\cdot\overline{b}=0$.
交换律: $b+c=c+b$, $b\cdot c=c\cdot b$.
结合律: $b +(c+d)=(b+c)+d$, $b\cdot (c\cdot d)=(b\cdot c)\cdot d$.
分配律: $b\cdot(c+d)=(b\cdot c)+(b\cdot d)$, $b+(c\cdot d)=(b+c)\cdot(b+d)$.
DeMorgan 律: $\overline{b+c}=\overline{b}\cdot\overline{c}$, $\overline{b\cdot c}=\overline{b}+\overline{c}$.
反演律 (广义 DeMorgan 律): 反演式等于原逻辑式; 交换 $+$ 和 $\cdot$, 所有变量取非.
对偶律: 相等逻辑式的对偶也相等; 交换 $+$ 和 $\cdot$, 交换 $0$ 和 $1$.
不难发现 $b\oplus c=(\overline{b}\cdot c)+(b\cdot\overline{c})$.

有限域 ${\rm GF}(2) = ({0,1},\oplus, \cdot)$, $a,b\in GF(2)$.
注意到 $a+b=(a\oplus b)\oplus(a\cdot b)$.
${\rm GF}(2)^n = \{(b_{n-1},…,b_1,b_0)\ |\ b_i\in GF(2)\}$.
${\rm GF}(2)[x]/\langle p(x)\rangle: ({\rm deg}p=n)=\{\sum_{i=0}^{n-1}b_ix^i\ |\ b_i\in GF(2)\}$.
类似可将 Bool 代数扩展到 $n$ 位, 继而有逻辑函数 $f: \mathcal{B}^n\to \mathcal{B}^m$.

组合逻辑(combinational): 不包含存储器件, 对于相同的输入总能得到相同的输出. (assign 模块)
时序逻辑(sequential): 包含存储器件, 输出取决于输入和当前存储内容. (always 模块)
门电路: 实现逻辑函数的电路设备.

译码器(decoder): $\mathcal{B}^n\to \mathcal{B}^{2^n}$, $(x_{n-1},…,x_1,x_0)\mapsto (0,0,…,0,y_{\sum_{i=0}^{n-1} b_i2^i}=1,0,…,0,0)$; 逆函数为解码器(encoder).
选择器(mux, Multiplexer): $\mathcal{B}^{nm+\lceil\log_2 n\rceil}\to \mathcal{B}^m$, $(X_{n-1},…,X_1,X_0,S)\mapsto X_{S\ (2)}$.
三态缓冲器: 使能状态时, 输出等同于输入; 否则输出高阻态, 等效于断路.
PLA(Programmable Logic Array): 只有一级与门和一级或门(非门位置任意); 析取(sum of product)-对与求或, 合取(product of sum)-对或求与.
无关项: 通过去除输出无关项和输出无关项简化逻辑式.

锁存器(latch): 使能状态时(${\rm OE}=1$ 即 $\overline{\rm OE}=0$), 输出随输入改变; 否则输出不变.
触发器(filp-flop): 时钟上升或下降边沿的瞬间(脉冲, ${\rm CLK}$), 输出随输入改变; 否则输出不变.
建立时间 - 时钟边沿前保持有效输入最短时间; 保持时间 - 时钟边沿后保持有效输入时间.
寄存器堆(register file): D触发器为基本单元; 地址(Addr), 写入使能(WE), 读出使能(OE), 数据(Data).

定点数

十进制转换: $b_n…b_1b_0.b_{-1}…b_{-m}\ (R)=\sum_{i=-m}^n b_iR^i\ (10)$.

二进制编码(BCD, Binary Coded Decimal): $\{0,1\}^n\to \{x\in \mathbb{Z}\ |\ T_{\min}\leq x\leq T_{\max}\}$.
原码($n$ bit): $b_{n-1}b_{n-2}…b_1b_0\mapsto (-1)^{b_{n-1}}\sum_{i=0}^{n-2} b_i2^i$; $\ T_{\min}=1-2^{n-1}$; $\ T_{\max}=2^{n-1}-1$; $\ 00…0\mapsto +0$, $10…0\mapsto -0$.
补码: $0b_{n-2}…b_1b_0\mapsto \sum_{i=0}^{n-2} b_i2^i$, $\ 1b_{n-2}…b_1b_0\mapsto\sum_{i=0}^{n-2} b_i2^i -2^n$; $\ T_{\min}=-2^{n-1}$; $\ T_{\max}=2^{n-1}-1$; $\ 00…0\mapsto +0$, $11…1\mapsto -1$, $10…0\mapsto -2^{n-1}$; 双射.
反码: $0b_{n-2}…b_1b_0\mapsto \sum_{i=0}^{n-2} b_i2^i$, $\ 1b_{n-2}…b_1b_0\mapsto\sum_{i=0}^{n-2} b_i2^i-2^n+1$; $\ T_{\min}=1-2^{n-1}$; $\ T_{\max}=2^{n-1}-1$; $\ 00…0\mapsto +0$, $11…1\mapsto -0$.
移码: $b_{n-1}b_{n-1}…b_1b_0\mapsto \sum_{i=0}^{n-1} b_i2^i -(2^{n-1}-1)$; $\ T_{\min}=-2^{n-1}+1$; $\ T_{\max}=2^{n-1}$; $\ 01…1\mapsto 0$; 双射.
左移补 $0$; 逻辑右移补 $0$; 算术右移(按位右移)补最高位.
补码(C): $x\gets \sim x+1 \iff x\gets -x$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// 无符号型与带符号型转换
#include <stdio.h>

int main() {
    printf("-1U = %u\n", -1);
    printf("(int)2147483648U = %d\n", (int)2147483648U);
    printf("-2147483647U = %u\n", -2147483647);
    printf("-2147483647-1U = %u\n", -2147483647-1);
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// 扩展, 提升, 截断
#include <stdio.h>

int main() {
    signed char a = -97;
    signed char b = -34;
    signed char c = a + b;
    int d = a + b;
    printf("c=%d, d=%d\n", c, d);
    printf("c=0x%x, d=0x%x\n", c, d);
    return 0;
}

小端序(small-end): 字节低位在低地址, 高位在高地址; 绝大多数CPU采用.
大端序(big-end): 字节低位在高地址, 高位在低地址; 网络传输.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

// 测试字节序模式
#include <stdio.h>

typedef union {
    int num;
    unsigned char ch;
} End;

int main() {
    End test = {0};
    test.num = 0x12345678;
    printf("%X\n", test.ch);
    return 0;
}

异号相加, 同号相减, 永不溢出.
正溢: 正数相加为负, 即正数减负数为负.
负溢: 负数相加为正, 即负数减正数为正.

半加器(HA, half adder): ${\rm sum}=a\oplus b$, $c=a\cdot b$.
全加器(FA, full adder): ${\rm sum}_{i}=a_i\oplus b_i\oplus c_i, {\rm c_i}=(a_i\oplus b_i)\cdot c_{i-1}+a_i\cdot b_i$.
带标志加法器: $(a,b,{\rm SUB})\mapsto ({\rm sum}, {\rm ZF}, {\rm OF}, {\rm SF}, {\rm CF})$; ${\rm SUB}=1$ 时为减法.
进位保留加法器(CSA, carry save adder): $(a,b,c)\mapsto ({\rm sum}, {\rm carry})$, ${\rm sum}=a\oplus b\oplus c$, ${\rm carry}$, ${\rm carry}=(a\cdot b+b\cdot c+c\cdot a)\ll_{(1)}$.
并行进位加法器: 记 $g_i=a_i\cdot b_i$, $p_i=a_i\oplus b_i$, 则 $c_i=g_i+p_ic_{i-1}$, 将 $c_{i-1}$ 依次展开.
分组跳跃加法器(并行串行相结合): 每 4bit 为一小组串行, 每 4 小组为一大组串行.

乘法: 补码 $x\mapsto x({\rm mod}\ 2^n)$, 显然 $x({\rm mod}\ 2^n)\times y({\rm mod}\ 2^n)=xy({\rm mod}\ 2^n)$.
短常数乘法: $a=\sum_{i=0}^w b_i2^i$, 则 $ax=\sum_{b_i \ne 0}x\ll_{(i)}$.
Booth 乘法: 乘法中累加次数取决于乘数中 $1$ 的数量, 考虑到 $…01…10…=…10…00…-…00…01…$ 可将任意连续 $w$ 次连续累加变为 2 数相减.
4-Booth 编码: 不妨设 $b=b_{2n-1}…b_1b_0$, 有扩展 $\dot{b}=b_{2n+1}b_{2n}b_{2n-1}…b_1b_0b_{-1}$ 其中 $b_{2n+1}=b_{2n}=b_{2n-1},b_{-1}=0$, 则 $a\times b=a\times\dot{b}=a\times[\sum_{i=0}^n(b_{2i-1}+b_{2i}-2b_{2i+1})]$.
Wallace 树压缩: 多个 CSA 组成为树型结构, 三数一组并行迭代计算多个数相加.
Booth 乘法器(muliplier): 乘数 4-Booth 编码 $\to$ 生成部分积 $\to$ Wallace 数压缩 $\to$ 最后的 ${\rm carry}$ 与 ${\rm sum}$ 全加.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

// 串行乘法
int Multi(int n, int m) {
    int sum = 0, c = 31;
    while (n && s) {
        if (n & 1) sum += m;
        m <<= 1, n >>= 1, --c;
    }
    return c;
}

// 短常数乘法
int Multi15(int n) {
    return (n << 4) + ~n + 1;
}

除法溢出 $T_{\min}/(-1)\to T_{\min}$; 除 $0$ 异常.
无符号恢复余数除法 (restoring remainder): $a=qb+r$: 除数 $t\gets b«_{({\rm count})}$, 被除数 $a\gets a-t$: $a\geq 0$, $q_i=1$; $a<0$, 恢复余数 $a\gets a+t$; $n\gets n-1$$ 直至 $t=0$, 此时 $r=a$.
不恢复余数除法: 在前者基础上, 改为判断余数与除数符号, 同号相减取 $1$, 异号相加取 $0$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

// 恢复余数除法
unsigned DivR(unsigned m, unsigned n, unsigned cnt) {
    unsigned tmp, quot = 0;
    while(cnt >= 0) {
        tmp = n << cnt, m -= tmp;
        if (m >= 0) quot += 0B01 << cnt;
        if (m < 0) m += tmp;
        --cnt;
    }
    return quot;
}

// 不恢复余数除法
int Div(int m, int n, int cnt) {
    int tmp, quot = 0;
    while(cnt >= 0) {
        tmp = n << cnt;
        if ((m & tmp) >> 31) m -= tmp, quot += 0B01 << cnt;
        else m += tmp;
        --cnt;
    }
    return quot;
}

// 模 2 幂
int rempwr2(int x, int n) {
  int s = x >> 31;
  x = (x + s) ^ s;
  x &= ((~0) + (1 << n));
  return (x ^ s)+ ~s + 1;
}

补充材料: 位运算妙用

浮点数

浮点数: $\mathbb{R}\mapsto \{0,1\}^w$, $x\mapsto (s,e,d,R)\mapsto s\times\sum_{i=-m}^0 d_iR^i\times R^e=\hat{x}$.
加法及乘法满足交换律, 但不满足结合律.
ULP(units in last place): ${\rm err}=|\hat{x}-x/R^e|/R^m$.

IEEE754: FP16 - $n=5$, $m=10$; FP32 - $n=8$, $m=23$; ${\rm err}<1/2 {\rm ULP}$.
Google: BF16 - $n=8$, $m=7$; 可视为 FP32 尾数直接截断得到, 牺牲精度以扩大范围.

加减法: 对阶(小阶向大阶对齐) $\to$ 尾数加减 $\to$ 左规(阶码递减; 下溢)/右规(阶码递增; 上溢; 舍入) $\to$ 尾数舍入($0$ 舍 $1$ 入; 向 $+\infty$ 舍入; 向 $-\infty$ 舍入; 向 $0$ 舍入; 置 $1$; 截断) - 保护位(guard), 警戒位(round), 粘位(sticky); 溢出判断.
乘除法: 阶码加减(可能溢出) $\to$ 尾数乘除 $\to$ 规格化 $\to$ 尾数舍入.
Newton-Rahpson 方法: $f(x)=\sum_{i=0}^{\infty}f^i(x_0)(x-x_0)^i/i!=0$, 有迭代式 $x_{n+1}=x_n-f(x_n)/f’(x_n)$.
确保操作数均为规格化浮点数; 除 $0$ 得到无穷.

*补充材料: COMPUTER ARITHMETIC: Algorithms and Hardware Designs

程序机器级表示

汇编基础

以 IA-32 为例, 比较 AT&T 和 Intel 风格.

汇编指令: “[标签: ]指令助记符 [操作数助记符1] [操作数助记符2]”
指令类型: 传送(数据/地址/标志/IO); 定点算术运算(加减乘除/自增自减/取负/比较); 按位运算(逻辑/移位); 控制转移(无条件转移/条件转移/条件设置/条件传送/中断); x87 浮点数处理; MMX/SSE.
操作数类型: 立即数; 寄存器; 主存地址.
寄存器类型: 定点(通用; 指针指令; 标志/状态; 段); 浮点; MMX; x86-64(调试; 控制; 系统表指针; 特殊模块).
实模式寻址(兼容 8086/8088): (CS) $\ll 4+$ (IP), 代码段寄存器, 偏移地址.
保护模式寻址(80286 及以上): 立即寻址; 寄存器寻址; 相对寻址 (PC) $+$ X, 程序计数器, 位移; 复杂寻址 (SR) $+$ (B) $+$ (I) $\times$ S $+$ X, 段寄存器, 基址寄存器, 变址寄存器, 比例系数, 位移.

通用数据传送: MOV, MOVS(符号扩展), MOVZ(零扩展), XCHG(数据交换), PUSH(压栈), POP(出栈).
地址传送: LEA(Load Effect Address), LDS, LSS.
标志传送: PUSHF, POPF.
IO: IN, OUT.
定点算术运算: ADD, SUB, MUL, IMUL(带符号), DIV, IDIV(带符号), INC, DEC, NEG, CMP.
逻辑运算: NOT, AND, OR, XOR, TEST.
移位: SHL(逻辑), SHR(逻辑), SAL(算术), SAR(算术), ROL(循环), ROR(循环), RCL(带循环), RCR(带循环).
无条件转移: JMP(SHORT, NEAR, WORD, FAR, DWORD), CALL(NEAR, WORD, FAR, DWORD), RET.
条件设置: SET<flag>.
条件传送: CMOV<flag>.
中断: INT.
空操作: NOP.

过程: 每个未运行完函数在内存中对应一个栈帧, 保存栈底, 栈顶, (被)调用者保存寄存器, (传入参数), (返回地址), (局部变量).
准备: 形成新栈底 (PUSH, MOV); 生成栈帧 (SUB; AND); 保存现场 (PUSH).
过程: 分配局部变量 (auto); 处理具体逻辑; 发生新调用时(准备参数, CALL); 准备返回值 (EAX).
结束: 出栈/销毁 (LEAVE; POP); 取返回地址返回 (RET).

分支: 条件传送实现(避免跳转导致的流水线预测低效); jump-table 实现(switch-case); 条件转移实现.
循环: jump-to-middle 实现; guarded-do 实现.
数组/字符串/结构体/联合体: 连续内存, 首地址确定.
地址传参: 保存地址, 再由地址传值.
内存对齐: 结构体对齐到 4bytes; 堆栈边界对齐到 16bytes; 便于寻址和正确运行.

越界访问: 数组越界; 野指针.
缓冲区溢出: 堆溢出(篡改 hook); 栈溢出(不安全的读写函数); 内核.
避免缓冲区溢出: 避免使用不安全的函数; 启用 ASLR(Address Space Layout Randomization); 堆栈权限保护(读, 写, 执行权限分离); 溢出检测(canary).
反调试: 调试痕迹识别; 识别调试器行为; 干扰调试器功能.

补充材料: GDB Documentation
*补充材料: Intel 64 and IA-32 Manuals

目标文件 (未完)

源文件(.c) $-$ 预处理(prepress) $\to$ (.i) $-$ 编译(compile) $\to$ (.s) $-$ 汇编(assemble) $\to$ 目标文件(.o) $-$ 链接(link) $\to$ 可执行文件.
目标文件类型: PE-COFF(Portable Executable-Common File Formart) - Windows; ELF(Executable Linkable Format) - Linux.

*补充资料: PE Format

链接与装载

(elf)
静态链接: 地址和空间分配, 符号决议, 重定位
装载
动态链接

编译基础

硬件体系结构

CPU

单周期: CPU结构图; 指令周期, 流程, 信号; 微操作序列; 数据通路

控制器: 结构图, 硬布线设计表/组合逻辑(RISC), 微指令编码/下地址确定/补充(CISC)

流水线: 性能(TP/S/E)，流水线三大冒险(数据/结构/控制)时空图，流水线分类/多发/多线程, 执行过程举例(MISP)

存储器

性能评价: 存储容量, 单位成本, 存储速度(读/写时间, 读/写周期, 带宽).
层次结构: 越上层速度越快, 容量越小, 位价越贵; 上层可作为下层的 Cache.
寄存器 - 多级高速缓存(SRAM) - 主存/内存(DRAM, ROM) - 本地二级存储/外存/辅存(SSD, HDD, Flash, 光盘, 软盘, 磁带) - 远程二级存储(分布式文件系统, web服务器).

RAM(Random Access Memory): 二维阵列, 行列地址分别传入以定位超单元(supercell), 地址译码器实现片选 - 地址线(片选线), 容量扩展; 并列模块和数据字长一致 - 数据线, 字长扩展; 读出/写入使能信号 - 控制线, 存储时序及周期; 易失(断电后信息消失).
SRAM(Static): 双稳态触发器实现(如寄存器堆).
DRAM(Dynamic): 栅极电容实现; 读出具有破坏性, 电容本身漏电 - 刷新策略(集中 - 逐行; 分散 - 每行单独; 异步 - 前两者结合); 行列地址先后传送 - 地址线复用.
双端: 不同地址可同时读写; 同地址仅可同时读出 - “读者-写者问题”.
多体并行(多通道): 低位编址效率更高(空间局部性); 流水线方式并行(体数 $=$ 存储周期 $/$ 存储时间或总线传输周期); 控制器 - 排队器 - 存控标记触发器 - 节拍发生器.
SDRAM(Synchronous): 与CPU数据交换同步于系统时钟信号; 突发/猝发(Burst), 同一行中相邻数据连续访问, 一个地址可连续访问一个数据块 - 预加载(Prefetch)实现.
DDR(Double Data Rate SDRAM): 在一个时钟周期内的上升沿和下降沿各传一次数据.

ROM(Read Only Memory): 非易失性(nonvolatile); 系统固件 (firmware).
MROM(Mask-programmed): 掩膜生产时直接写入, 无法修改.
PROM(Programmable): 熔丝烧断型, PN结击穿型; 仅能写入一次.
EPROM(Erasable Programmble): 紫外线擦除型, 电擦除型; 修改次数有限, 写入速度慢.
Flash: 写入速度快; 以block为单位擦除(全部设为 “1”), 以page为单位读写(只能将"1"修改为"0"); 擦除会造成磨损 - 平均磨损算法(动态; 静态); package - target - lun(logical unit) - plane(面) - block(块) - page(页) - cell(单元).
SSD(Solid State Drive): 转换层及Flash; 随机访问性能高, 读写速度快, 电路控制访问位置, 安静无噪音, 耐摔抗震; chip(芯片) - die(颗粒) - plane - block - page - cell.

磁记录: 归零制(RZ), 不归零制(NRZ), 1翻不归零制(NRZ1), 调相制(PM), 调频制(FM), 改进调频制(MFM); 编码效率, 自同步能力(从读出的脉冲序列提取同步时钟脉冲; 最小磁化翻转间隔与最大之比).
HDD(Hard Disk Drive): 旋转结构(rotating); platter(盘片) - surface(盘面) - spindle(主轴) - track(磁道) - sector(扇区) - gap(间隔) - read/write heads(读写头) - arm(传动臂力).
读写时序: 寻道(seek), 读写头找到磁道 $\to$ 旋转(rotation), 主轴旋转盘片将扇区送到读写头下 $\to$ 传送(transfer).
RAID(Redundant Array of Independetn Disks): 0 - 数据置于统一条带, 一块损坏则数据全部丢失; 1 - 互相备份; 3 - 0 $+$ 奇偶检验; 5 - 数据和奇偶校验置于同一条带; 6 - 双重奇偶校验; 01 - 内层0, 外层1; 10 - 内层1, 外层 0.

局部性(locality): 时间(temporal), 访问内存位置在短期内将重复访问; 空间(spatial), 附近内存位置在短期内将访问.
缓存命中(hit): 需要 $k+1$ 层的数据 $d$ 恰好缓存在第 $k$ 层中.
缓存不命中(miss): 强制/冷不命中(compulsory/cold), 缓存为空时; 冲突不命中(conflict), 缓存不为空时.
替换/驱逐策略(replacement/eviction): 随机(RAND); 先进先出(FIFO); 近期最少使用(LRU) - 符合局部性原理; 最不经常使用(LFU).
通用组织: 四元组 $(S,E,B,m)$; $S$ 组(set), 每组 $E$ 行(line), 每行包括 $1$ 个有效位(valid), $t$ 个标记位(tag), $B$ 字节数据块(block); $m$ 位地址被划分为 $t$ 个标记位, $s$ 个组索引位, $b$ 个块偏移位.
地址映射(mapped): 直接映射(direct), $E=1$, $m=t||s||b$; 全相联(fully associative), $S=1$, $m=t||b$; 组相连(set), $S>1$, $E>1$, $m=t||s||b$.
写策略/一致性: 写命中时, 写穿透/全写/直写(write through), 立即将缓存写主存到中, 增加FIFO写缓冲(buffer)来减少时间损耗; 写回/回写(back), 发生替换时才写到主存中, 需额外维护修改位/脏位(dirty). 写不命中时, 写分配(allocate), 将主存块调入缓存; 非写分配, 只更新主存. 写分配 $+$ 写回; 非写分配 $+$ 写穿透.
CPU的L1缓存将指令与数据分离, 利用不同局部性优化性能.

总线及I/O

总线(bus): 分时, 同时刻只允许一个部件发送信息; 共享, 多个部件均可通过同组线路交换信息.
层次: 片内总线 - 寄存器与ALU; 系统总线 - 数据, 地址, 控制(时钟, 复位, 总线请求, 总线允许, 总线忙碌, 中断请求, 中断响应, 存储器读/写, I/O读/写, 传输相应); I/O总线 - 中低速I/O设备; 通信总线.
性能评价: 时钟周期/频率, 传输周期/工作频率, 宽度, 带宽, 复用, 信号线数, 同步/异步, 串行/并行; 带宽 $=$ 工作频率 $\times$ 宽度.
结构: 单总线 - 系统总线; 双总线 - 主存总线 $+$ I/O总线; 三总线 - 主存总线 $+$ I/O总线 $+$ DMA总线.
事务/操作周期: 请求/申请 $\to$ 仲裁/分配 $\to$ 寻址 $\to$ 传输 $\to$ 释放/结束.
仲裁/判优: 链式查询, 按离控制器远近顺序依次查询请求, 仅需 $2$ 根控制线; 计数器定时查询, 计数器循环自增直至地址信号与设备地址线一致, 需 $\log_{2}{n}$ 根控制线; 独立请求方式, 根据请求优先次序排队, 需 $2n$ 根控制线.
定时/通信: 同步, 统一时钟协调发收双方; 异步, 不互锁(“请求"和"回答"均一段时间后撤销), 半互锁(“请求"在发出"回答"后撤销, “回答"一段时间后撤销), 全互锁(“请求"在收到"回答"后撤销, “回答"在"请求"撤销后撤销); 半同步, 增设"等待”(wait)响应信号线, 时钟前沿发送, 时钟后沿接收判别.

输入设备: 键盘; 鼠标.
输出设备: 显示器, CRT(阴极射线管), LCD(液晶), LED(发光二极管); 屏幕大小, 分辨率, 灰度级, 刷新率, VRAM(显示存储器; 容量 $=$ 分辨率 $\times$ 灰度级位数; 带宽 $=$ 容量 $\times$ 帧率). 打印机, 针式, 喷墨式, 激光.
外部存储器: 磁表面, HDD, 磁带; Flash, SSD; 光盘.

I/O接口/控制器: 设备控制器; 数据缓冲寄存器, 控制寄存器, 状态寄存器; 数据格式转换(串行转并行, 并行转串行).
编址: 统一编址, 统一访存指令(存储器映射方式), 不同地址码区分内存和I/O设备; 独立编址, 设置专门I/O指令/(I/O映射方式), 不同指令区分内存和I/O设备.
查询: CPU轮询检查I/O状态寄存器; 独占查询(完全串行), 定时查询(保证数据不丢失).
中断(外中断): I/O完成后向CPU发出中断请求.
DMA(Direct Memory Access): 直接内存访问; CPU通过I/O总线发送读写参数 - 预处理, 高速外设和主存直接数据读写 - 数据传送, 读写完成后向CPU发出中断请求 - 后处理; DMA请求触发器, 主存地址计数器(AR), 传送长度计数器(WC), 设备请求寄存器(DAR), 中断机构; MDA独占主存, DMA和CPU交替访存, 周期挪用/窃取(CPU访问间隔优先DMA).
通道: CPU向通道发出I/O指令, 通道控制并完成一系列I/O指令后向CPU发出中断请求(如南桥).

中断系统: 请求 $\to$ 响应(关中断; 判优) $\to$ 处理(隐指令; 服务程序).
内中断/异常/例外/陷阱(exception/fault/trap): 自愿, 陷阱指令(trap); 强迫, 硬件(abort, 如缺页), 软件(fault, 如整数除 $0$).
外中断/中断(interrupt): I/O请求.
关中断: 标志位 ${\rm IF}=0$ 时, 不允许中断, 实现原子操作.
非屏蔽中断: 关中断时也会被响应(如掉电).
优先级: 硬件故障最高级; 非屏蔽优于可屏蔽; DMA优于I/O设备; 高速优于低速; 输入优于输出; 实时优于普通.
判优实现: 硬件排队器(向量地址), 屏蔽字(多重中断中屏蔽优先级更低者); 软件查询程序.
隐指令: 关中断 $\to$ 保存断点(保存原PC) $\to$ 引出服务程序(修改PC).
服务程序: 保护现场(保存通用寄存器和状态寄存器值) $\to$ 设备服务 $\to$ 恢复现场.

系统层级抽象

进程

虚拟内存

并发

系统级I/O

*补充材料: The Linux Programming Interface: A Linux and UNIX System Programming Handbook

网络通信

概述

网络构成
节点: 主机及进程(端系统, host/end system), 交换设备(路由器/交换机, switch).
边: 通信链路; 接入网链路(主机接入), 主干链路(交换设备间); 传输速率=带宽(bps).
协议(protocol): 对等层实体通信中遵循的规则集合; 格式(语法, 语义), 次序, 动作; TCP/IP(Transmission Control Protocol/Internet Protocol).
服务描述: 分布式应用进程; 提供接口(面向连接服务/无连接服务)的通信基础设施; 嵌套字接口(socket interface).
结构: 网络边缘(edge, 主机及进程); 网络核心(core, 交换设备及主干链路); 接入网及物理媒体(接入网链路).
Internet: 网络的网络; 端系统经由ISP(Internet Service provider)接入, PoP(Point of Presence)接入上层ISP, IXP(Internet Exchange Point)ISP对等连接; 内容提供网络(content provider network); 局域网(LAN, Local Area Network), 城域网(MAN, Metropolitan), 广域网(WAN, Wide).
Internet标准: IETF(Internet Engineering Task Force)-RFC(Request for comments).

网络边缘
客户端-服务器模式(client-service, C/S); 对等模式(peer-peer, P2P).
面向连接服务(connection-oriented): TCP(Transmission Control Protocol)[RFC 793]: 握手(数据传输前建立连接); 可靠保序(确认和重传), 流量控制(发送方不会淹没接收方), 拥塞控制(网络拥塞时发送方降低发送效率); HTTP(Web), FTP(文件传输), Talnet(远程登录), SMTP(E-mail).
无连接服务(connectionless): UDP(User Datagram Protocol)[RFC 768]; 流媒体, 远程会议, DNS, Internet电话.

网络核心-电路交换(circuit switching)
为呼叫预留端-端资源: 带宽(band-width)分片, 频分复用(Frequency-division multiplexing, FDM), 时分复用(TDM), 波分复用(WDM), 码分(CDM).
资源专用不共享, 呼叫无数据则资源片空闲(silent period), 呼叫要建立连接, 性能有保证.
不合适计算机间通信: 连接建立时间长, 共用时间 $=$ 建立连接时间 $+$ 传输时间; 通信有突发性, 资源浪费较多; 可靠性不高, 单点故障影响范围大.

网络核心-分组交换(packet)
以分组为单位存储-转发: 传输数据分组; 传输时使用全部带宽; 统计多路复用, 不固定的时分.
资源共享, 按需使用: 分组延时; 节点总时延(total nodal delay) $=$ 处理时延(processing) $+$ 传输(transmission) $+$ 排队(queuing) $+$ 传播(propagation).
处理时延: 分组每次移动称为一跳(hop), 转发前节点收到整个分组.
传输时延: 速率 $R$ bps 链路, 长度 $L$ bits 分组, 存储-转发延时为 $L/R$ s.
排队时延: 到达速率 $>$ 输出速率, 缓存用完时新到达分组被丢弃(drop)即丢包(loss); 链路宽度 $R$ bps, 分组长度 $L$ bits, 分组到达队列平均速率 $a$, 流量强度为 $0<La/R<1$.
传播时延: 物理链路长度 $d$ m, 物理媒体传播速度 $s$ mps, 传播延时为 $d/s$ s.
关键功能: 路由, 决定分组采用的源到目标的路径(路由算法-路由表); 转发.
同样网络资源(带宽)支持更多用户使用: 总用户数 $M$, 最大同时用户数 $N$, 排队延时发生概率 $1-\sum_{i=0}^N\tbinom{M}{i} p^i(1-p)^{M-i}$; 但过度使用会造成拥塞(congestion).
数据报(datagram): 目标地址决定下一跳, 路由无状态.
虚电路(virtual circuit): 呼叫时决定路径, 信令(Signaling)控制, 路由维持通信状态.
吞吐量(throughput): 瞬时(instantaneous), 平均; 取决于瓶颈链路(bottleneck link).

1
2
3
4

# ICMP(Internet Control Message Protocol): Head-目标IP地址, TTL(Time To Live, 生存时间);
# Body-RTT(Round Trip Time, 往返时间), 目标端口不可达(destination port unreachable, 结束测试标识).
traceroute target_name # linux
tracert [-d] [-h maximum_hops] [-j computer-list] [-w timeout] target_name # windows

接入网: 接入带宽; 共享/独享.
调制解调器(modem, 电话线): 调制加载到音频信号上, 音频信号解调; 调频, 调幅, 调相位, 综合调制; 拨号(带宽最高56 Kpbs, 不能同时在线), DLS(Didital Subcriber Line, 上行最高 1Mbps, 下行最高 10Mbps).
同轴线缆(有线电视): FDM, 共享带宽, HFC(Hybrid Fiber Coax, 上行最高 2Mbps, 下行最高 30Mbps).
电缆(Cable Internet Access). 光纤到户(FTTH, Fiber To The Home).
无线: 无线LANs; 广域无线(Wide-Area), 电信运营商提供(cellular).

物理媒体: 传输Bit; 物理链路.
导引型媒体: 双绞线(TP, 5类 100Mbps, 6类 10Gbps), 同轴电缆(双向; 基带 Ethernet, 宽带 HFC), 光缆(光脉冲, 高速, 低误码率, 安全).
非导引型媒体: 开放空间传播, 环境效应(反射, 吸收, 干扰); 地面微波, LAN(WiFi), 广域(3G, LTE, 4G, 5G), 卫星.

协议层次
复杂网络分层, 通过接口利用下层提供的服务 SAP(Service Access Point), 层间交互形式为原语(primitive, 如Socket函数), 对等层交互为协议; 本层协议通过下层提供服务实现, 为上层协议提供更高级服务.
数据单元(DU, Data Unit): $n+1$ 层 IDU(Interface) $=$ ICI(Interface Control Information) + SDU(service), $n$ 层 PDU(protocol) $=$ Header $+$ SDU.
Internet协议栈(TCP/IP模型): 应用层(报文, message, 主机到主机), 传输层(段, segment, 进程到进程, 可靠通信服务), 网络层(分组/数据报, packet, 端到端), 链路层(帧, frame, 点到点), 物理层(bit).
ISO-OSI参考模型: 应用层, 表示层(解释数据, 表示转换), 会话层(同步, 检查, 恢复, 会话管理), 传输层, 网络层, 链路层, 物理层.
封装(encapsulation): 源主机封装, 交换设备解封装再封装, 目标主机解封装.

应用层

网络应用运行在端系统上, 网络核心没有应用层软件.
C-S: 服务器, 固定IP地址与端口号(port), 持续运行, 等待连接进程(响应报文), 扩展性差(服务器场); 客户端, 可以为动态IP, 间歇性连接, 发起通信进程(请求报文), 不与其他客户端通信.
P2P: 任意端系统间可进行通信; 每个结点既是客户端又是服务器(自扩展性); 参与主机间歇性连接, 可以为动态IP; 难以管理.

进程表示和寻址依据: IP+port.
Socket API(套接字): 为使层间传输信息最小, 用整数代表通信双方或单方.
TCP socket: 四元组, 源IP, 源port, 目标IP, 目标port.
UDP socket: 二元组, 源IP, 源port.
传输层提供服务的指标: 数据丢失率, 延迟, 吞吐, 安全性(机密, 完整, 可认证).

Web: 页面由对象组成; 通过URL(Uniform Resource Locator)引用对象.
URL格式: <协议名>://<用户名>:<口令>@<主机名>/<路径名>:<端口>.
RRT(round-trip time): 信息从客户端到服务器再返回的时间.
HTTP1.0(Hyper Text Transfer Protocol)[RFC 1945]: 无状态(服务器不维护客户端历史信息), 非持久(最多只有一个对象在连接上发送)连接.
HTTP1.1[RFC 2068]: 无状态, 流水线式(客户端遇到引用对象立刻产生请求, 所有引用对象开销1RRT是可能的), 持久性(服务端响应后保持连接)连接.
请求方法: Post, 表单提交; Get, URL字段上截取; DELETE, 删除URL字段文件; HEAD, URL字段上截取, 只获取元数据(文件属性信息).
Cookie: 浏览器第一次访问时, 服务端创建并保存Cookie $\to$ 客户端接收Cookie信息, 再次访问时携带Cookie, 实现状态维护.
Session: 浏览器第一次访问时, 服务端创建并保存Session, 生成相应的Cookie $\to$ 客户端接收Cookie信息, 再次访问时携带Cookie $\to$ 服务端根据Cookie匹配Session, 实现状态维护.
缓存/代理服务器: 客户端通过缓存访问Web; 缓存中存在对象时直接返回, 不存在时从原始服务器拉取(缓存更新).

FTP(File Transfer Protocol)[RFC 959]: 客户端通过控制连接(带外, out of band)身份认证, 浏览远程目录; 服务器开启数据连接传输文件; 有状态连接.

EMail: 用户代理(邮件阅读编辑器); 邮件服务器(报文队列保持待发送邮件); 邮件传输.
邮件报文格式: 一般标准[RFC 822]; 多媒体扩展 MIME[RFC 2045, 2056].
SMTP(Simple Mail Transfer Protocol)[RFC 2821]: 持久性连接; 7bits ASCII编码报文; 发送邮件到服务器, 服务器间传送邮件.
POP3(Post Office Protocol)[RFC 1939]: 用户身份认证, 并从服务端下载邮件; 无状态连接
IMAP(Internet Mail Access Protocol)[RFC 1730]: Internet 邮件访问; 服务器上处理存储的报文; 有状态连接.

DNS(Domain Name System): 分布式数据库完成域名到IP地址的转换, 基于域的分层命名机制, 网络核心功能但以应用层实现; 附带实现别名到正规名的转换, 负载均衡(Load Distribution).
命名空间: 倒序生长的树; 根下顶级域(通用: com, edu, gov, int, mil, net, org, firm, hsop, web, arts, rec; 国家: cn, us, nl, jp), 域下划分子域(subdomain), 叶子结点为主机; 遵从组织界限, 与物理网络无关.

非结构化 集中目录/完全分布(泛洪)/混合式, DHT

P2P

CDN

socket

传输层

多路复用 - 解复用: 引入 port

UDP - 校验和

RDT(可靠数据传输)原理: FSM(有限状态自动机); 可靠信道 $\to$ 比特差错, ACK/NAK出错, NAK free $\to$ 分组丢失 $\to$ 流水线, 滑动窗口, GBN/SN协议

TCP: 段结构; 可靠性(重发, 快速重发), 流量控制, 连接建立(三次握手, 四次挥手), 拥塞控制

QUIC

网络层

数据平面: 转发

路由器: 结构, 匹配转发, 交换结构, 调度策略

IP: 数据报格式, 分片, IPv4(子网掩码, CIDR, DHCP), NAT(网络地址转换), IPv6

链路层