第 1 章 计算机网络概论

1.1 计算机系统基础知识

1.1.1 计算机系统硬件基本组成

计算机系统是由硬件和软件组成的，它们协同工作来运行程序。计算机的基本硬件系统由运算器、控制器、存储器、输入设备和输出设备 5 大部件组成。运算器、控制器等部件被集成在一起统称为中央处理单元（Central Processing Unit，CPU）。CPU 是硬件系统的核心，用于数据的加工处理，能完成各种算术、逻辑运算及控制功能。存储器是计算机系统中的记忆设备，分为内部存储器和外部存储器。前者速度高、容量小，一般用于临时存放程序、数据及中间结果。而后者容量大、速度慢，可以长期保存程序和数据。输入设备和输出设备合称为外部设备（简称外设），输入设备用于输入原始数据及各种命令，而输出设备则用于输出计算机运行的结果。

1.1.2 中央处理单元

中央处理单元（CPU）是计算机系统的核心部件，它负责获取程序指令、对指令进行译码并加以执行。

1. CPU 的功能

（1）程序控制。CPU 通过执行指令来控制程序的执行顺序，这是 CPU 的重要功能。

（2）操作控制。一条指令功能的实现需要若干操作信号配合来完成，CPU 产生每条指令的操作信号并将操作信号送往对应的部件，控制相应的部件按指令的功能要求进行操作。

（3）时间控制。CPU 对各种操作进行时间上的控制，即指令执行过程中操作信号的出现时间、持续时间及出现的时间顺序都需要进行严格控制。

（4）数据处理。CPU 通过对数据进行算术运算及逻辑运算等方式进行加工处理，数据加工处理的结果被人们所利用。所以，对数据的加工处理也是 CPU 最根本的任务。

此外，CPU 还需要对系统内部和外部的中断（异常）做出响应，进行相应的处理。

2. CPU 的组成

CPU 主要由运算器、控制器、寄存器组和内部总线等部件组成。

（1）运算器

运算器由算术逻辑单元（Arithmetic and Logic Unit，ALU）、累加寄存器、数据缓冲寄存器和状态条件寄存器等组成，它是数据加工处理部件，用于完成计算机的各种算术和逻辑运算。相对控制器而言，运算器接受控制器的命令而进行动作，即运算器所进行的全部操作都是由控制器发出的控制信号来指挥的，所以它是执行部件。运算器有如下两个主要功能：

• 执行所有的算术运算，例如加、减、乘、除等基本运算及附加运算。
• 执行所有的逻辑运算并进行逻辑测试，例如与、或、非、零值测试或两个值的比较等。

运算器中各组成部件的功能如下：

• 算术逻辑单元（ALU）。ALU 是运算器的重要组成部件，负责处理数据，实现对数据的算术运算和逻辑运算。
• 累加寄存器（AC）。AC 通常简称为累加器，它是一个通用寄存器，其功能是当运算器的算术逻辑单元执行算术或逻辑运算时，为 ALU 提供一个工作区。例如，在执行一个减法运算前，先将被减数取出暂存在 AC 中，再从内存储器中取出减数，然后同 AC 的内容相减，将所得的结果送回 AC 中。运算的结果是放在累加器中的，运算器中至少要有一个累加寄存器。
• 数据缓冲寄存器（DR）。在对内存储器进行读/写操作时，用 DR 暂时存放由内存储器读/写的一条指令或一个数据字，将不同时间段内读/写的数据隔离开来。DR 的主要作用为：作为 CPU 和内存、外部设备之间数据传送的中转站；作为 CPU 和内存、外围设备之间在操作速度上的缓冲；在单累加器结构的运算器中，数据缓冲寄存器还可兼作为操作数寄存器。
• 状态条件寄存器（PSW）。PSW 保存由算术指令和逻辑指令运行或测试的结果建立的各种条件码内容，主要分为状态标志和控制标志，例如运算结果进位标志（C）、运算结果溢出标志（V）、运算结果为 0 标志（Z）、运算结果为负标志（N）、中断标志（I）、方向标志（D）和单步标志等。这些标志通常分别由 1 位触发器保存，保存了当前指令执行完成之后的状态。通常，一个算术操作产生一个运算结果，而一个逻辑操作产生一个判决。

（2）控制器

运算器只能完成运算，而控制器用于控制整个 CPU 的工作，它决定了计算机运行过程的自动化。它不仅要保证程序的正确执行，而且要能够处理异常事件。控制器一般包括指令控制逻辑、时序控制逻辑、总线控制逻辑和中断控制逻辑等几个部分。

指令控制逻辑要完成取指令、分析指令和执行指令的操作，其过程分为取指令、指令译码、按指令操作码执行、形成下一条指令地址等步骤。

• 指令寄存器（IR）。当 CPU 执行一条指令时，先把它从内存储器取到缓冲寄存器中，再送入 IR 暂存，指令译码器根据 IR 的内容产生各种微操作指令，控制其他的组成部件工作，完成所需的功能。
• 程序计数器（PC）。PC 具有寄存信息和计数两种功能，又称为指令计数器。程序的执行分两种情况，一是顺序执行，二是转移执行。在程序开始执行前，将程序的起始地址送入 PC，该地址在程序加载到内存时确定，因此 PC 的内容即是程序第一条指令的地址。执行指令时，CPU 自动修改 PC 的内容，以便使其保持的总是将要执行的下一条指令的地址。由于大多数指令都是按顺序来执行的，所以修改的过程通常只是简单地对 PC 加 1。当遇到转移指令时，后继指令的地址根据当前指令的地址加上一个向前或向后转移的位移量得到，或者根据转移指令给出的直接转移的地址得到。
• 地址寄存器（AR）。AR 保存当前 CPU 所访问的内存单元的地址。由于内存和 CPU 存在着操作速度上的差异，所以需要使用 AR 保持地址信息，直到内存的读/写操作完成为止。
• 指令译码器（ID）。指令包含操作码和地址码两部分，为了能执行任何给定的指令，必须对操作码进行分析，以便识别所完成的操作。指令译码器就是对指令中的操作码字段进行分析解释，识别该指令规定的操作，向操作控制器发出具体的控制信号，控制各部件工作，完成所需的功能。

时序控制逻辑要为每条指令按时间顺序提供应有的控制信号。总线逻辑是为多个功能部件服务的信息通路的控制电路。中断控制逻辑用于控制各种中断请求，并根据优先级的高低对中断请求进行排队，逐个交给 CPU 处理。

（3）寄存器组

寄存器组可分为专用寄存器和通用寄存器。运算器和控制器中的寄存器是专用寄存器，其作用是固定的。通用寄存器用途广泛并可由程序员规定其用途，其数目因处理器不同有所差异。

3. 多核 CPU

核心又称为内核，是 CPU 最重要的组成部分。CPU 中心那块隆起的芯片就是核心，是由单晶硅以一定的生产工艺制造出来的，CPU 所有的计算、接收/存储命令、处理数据都由核心执行。各种 CPU 核心都具有固定的逻辑结构，一级缓存、二级缓存、执行单元、指令级单元和总线接口等逻辑单元都会有合理的布局。

多核即在一个单芯片上面集成两个甚至更多个处理器内核，其中，每个内核都有自己的逻辑单元、控制单元、中断处理器、运算单元，一级 Cache、二级 Cache 共享或独有，其部件的完整性和单核处理器内核相比完全一致。

CPU 的主要厂商 AMD 和 Intel 的双核技术在物理结构上有所不同。AMD 将两个内核做在一个 Die（晶元）上，通过直连架构连接起来，集成度更高。Intel 则是将放在不同核心上的两个内核封装在一起，因此将 Intel 的方案称为”双芯”，将 AMD 的方案称为”双核”。从用户端的角度来看，AMD 的方案能够使双核 CPU 的管脚、功耗等指标跟单核 CPU 保持一致，从单核升级到双核，不需要更换电源、芯片组、散热系统和主板，只需要刷新 BIOS 软件即可。

多核 CPU 系统最大的优点（也是开发的最主要目的）是可满足用户同时进行多任务处理的要求。

单核多线程 CPU 是交替地转换执行多个任务，只不过交替转换的时间很短，用户一般感觉不出来。如果同时执行的任务太多，就会感觉到”慢”或者”卡”。而多核在理论上则是在任何时间内每个核执行各自的任务，不存在交替问题。因此，单核多线程和多核（一般每核也是多线程的）虽然都可以执行多任务，但多核的速度更快。

虽然采用了 Intel 超线程技术的单核可以视为是双核，4 核可以视为是 8 核。然而，视为是 8 核一般比不上实际是 8 核的 CPU 性能。

要发挥 CPU 的多核性能，就需要操作系统能够及时、合理地给各个核分配任务和资源（如缓存、总线、内存等），也需要应用软件在运行时可以把并行的线程同时交付给多个核心分别处理。

1.1.3 数据表示

各种数值在计算机中表示的形式称为机器数，其特点是采用二进制计数制，数的符号用 0 和 1 表示，小数点则隐含，表示不占位置。机器数对应的实际数值称为数的真值。机器数有无符号数和带符号数之分。无符号数表示正数，在机器数中没有符号位。对于无符号数，若约定小数点的位置在机器数的最低位之后，则是纯整数；若约定小数点的位置在机器数的最高位之前，则是纯小数。对于带符号数，机器数的最高位是表示正、负的符号位，其余位则表示数值。

为了便于运算，带符号的机器数可采用原码、反码和补码等不同的编码方法，机器数的这些编码方法称为码制。

1）原码、反码、补码和移码

（1）原码表示法

数值 $X$ 的原码记为 $[X]_原$，如果机器字长为 $n$（即采用 $n$ 个二进制位表示数据），则原码的定义如下：

若 $X$ 是纯整数，则

$$ [X]_原 = \begin{cases} X & 0 \leqslant X \leqslant 2^{n-1} - 1 \ 2^{n-1} + |X| & -(2^{n-1} - 1) \leqslant X \leqslant 0 \end{cases} $$

若 $X$ 是纯小数，则

$$ [X]_原 = \begin{cases} X & 0 \leqslant X < 1 \ 2^0 + |X| & -1 < X \leqslant 0 \end{cases} $$

【例 1.1】 若机器字长 $n$ 等于 8，分别给出 $+1,\ -1,\ +127,\ -127,\ +45,\ -45,\ +0.5,\ -0.5$ 的原码表示。

$[+1]原 = 0\ 0000001$；$[-1]原 = 1\ 0000001$

$[+127]原 = 0\ 1111111$；$[-127]原 = 1\ 1111111$

$[+45]原 = 0\ 0101101$；$[-45]原 = 1\ 0101101$

$[+0.5]原 = 0\ \diamond\ 1000000$；$[-0.5]原 = 1\ \diamond\ 1000000$（其中，$\diamond$ 是小数点的位置）

在原码表示法中，最高位是符号位，0 表示正号，1 表示负号，其余的 $n-1$ 位表示数值的绝对值。数值 0 的原码表示有两种形式：$[+0]原 = 0\ 0000000$，$[-0]原 = 1\ 0000000$。

（2）反码表示法

数值 $X$ 的反码记作 $[X]_反$，如果机器字长为 $n$，则反码的定义如下：

若 $X$ 是纯整数，则

$$ [X]_反 = \begin{cases} X & 0 \leqslant X \leqslant 2^{n-1} - 1 \ 2^n - 1 + X & -(2^{n-1} - 1) \leqslant X \leqslant 0 \end{cases} $$

若 $X$ 是纯小数，则

$$ [X]_反 = \begin{cases} X & 0 \leqslant X < 1 \ 2 - 2^{-(n-1)} + X & -1 < X \leqslant 0 \end{cases} $$

【例 1.2】 若机器字长 $n$ 等于 8，分别给出 $+1,\ -1,\ +127,\ -127,\ +45,\ -45,\ +0.5,\ -0.5$ 的反码表示。

$[+1]反 = 0\ 0000001$；$[-1]反 = 1\ 1111110$

$[+127]反 = 0\ 1111111$；$[-127]反 = 1\ 0000000$

$[+45]反 = 0\ 0101101$；$[-45]反 = 1\ 1010010$

$[+0.5]反 = 0\ \diamond\ 1000000$；$[-0.5]反 = 1\ \diamond\ 0111111$（其中，$\diamond$ 是小数点的位置）

在反码表示中，最高位是符号位，0 表示正号，1 表示负号，正数的反码与原码相同，负数的反码则是其绝对值按位求反。数值 0 的反码表示有两种形式：$[+0]反 = 0\ 0000000$，$[-0]反 = 1\ 1111111$。

（3）补码表示法

数值 $X$ 的补码记作 $[X]_补$，如果机器字长为 $n$，则补码的定义如下：

若 $X$ 是纯整数，则

$$ [X]_补 = \begin{cases} X & 0 \leqslant X \leqslant 2^{n-1} - 1 \ 2^n + X & -2^{n-1} \leqslant X \leqslant 0 \end{cases} $$

若 $X$ 是纯小数，则

$$ [X]_补 = \begin{cases} X & 0 \leqslant X < 1 \ 2 + X & -1 \leqslant X < 0 \end{cases} $$

【例 1.3】 若机器字长 $n$ 等于 8，分别给出 $+1,\ -1,\ +127,\ -127,\ +45,\ -45,\ +0.5,\ -0.5$ 的补码表示。

$[+1]补 = 0\ 0000001$；$[-1]补 = 1\ 1111111$

$[+127]补 = 0\ 1111111$；$[-127]补 = 1\ 0000001$

$[+45]补 = 0\ 0101101$；$[-45]补 = 1\ 1010011$

$[+0.5]补 = 0\ \diamond\ 1000000$；$[-0.5]补 = 1\ \diamond\ 1000000$（其中，$\diamond$ 是小数点的位置）

在补码表示中，最高位为符号位，0 表示正号，1 表示负号，正数的补码与其原码和反码相同，负数的补码则等于其反码的末位加 1。在补码表示中，0 有唯一的编码：$[+0]补 = 0\ 0000000$，$[-0]补 = 0\ 0000000$。

（4）移码表示法

移码表示法是在数 $X$ 上增加一个偏移量来定义的，常用于表示浮点数中的阶码。如果机器字长为 $n$，规定偏移量为 $2^{n-1}$，则移码的定义如下：

若 $X$ 是纯整数，则 $[X]移 = 2^{n-1} + X$（$-2^{n-1} \leqslant X < 2^{n-1}$）；若 $X$ 是纯小数，则 $[X]移 = 1 + X$（$-1 \leqslant X < 1$）。

【例 1.4】 若机器字长 $n$ 等于 8，分别给出 $+1,\ -1,\ +127,\ -127,\ +45,\ -45,\ +0,\ -0$ 的移码表示。

$[+1]移 = 1\ 0000001$；$[-1]移 = 0\ 1111111$

$[+127]移 = 1\ 1111111$；$[-127]移 = 0\ 0000001$

$[+45]移 = 1\ 0101101$；$[-45]移 = 0\ 1010011$

$[+0]移 = 1\ 0000000$；$[-0]移 = 1\ 0000000$

实际上，在偏移 $2^{n-1}$ 的情况下，只要将补码的符号位取反便可获得相应的移码表示。

2）定点数和浮点数

（1）定点数

所谓定点数，就是小数点的位置固定不变的数。小数点的位置通常有两种约定方式：定点整数（纯整数，小数点在最低有效数值位之后）和定点小数（纯小数，小数点在最高有效数值位之前）。

设机器字长为 $n$，各种码制下带符号数的范围如表 1-1 所示。

表 1-1 机器字长为 $n$ 时各种码制表示的带符号数的范围

（2）浮点数

当机器字长为 $n$ 时，定点数的补码和移码可表示 $2^n$ 个数，而其原码和反码只能表示 $2^n-1$ 个数（0 的表示占用了两个编码），因此，定点数所能表示的数值范围比较小，在运算中很容易因结果超出范围而溢出。浮点数是小数点位置不固定的数，它能表示更大范围的数。

在十进制中，一个数可以写成多种表示形式。例如，$83.125$ 可写成 $10^3 \times 0.083125$ 或 $10^4 \times 0.0083125$ 等。同样，一个二进制数也可以写成多种表示形式。例如，二进制数 $1011.10101$ 可以写成 $2^4 \times 0.101110101$、$2^5 \times 0.0101110101$ 或 $2^6 \times 0.00101110101$ 等。由此可知，一个二进制数 $N$ 可以表示为更一般的形式 $N = 2^E \times F$，其中 $E$ 称为阶码，$F$ 称为尾数。用阶码和尾数表示的数称为浮点数，这种表示数的方法称为浮点表示法。

在浮点表示法中，阶码为带符号的纯整数，尾数为带符号的纯小数。浮点数的表示格式如下：

很明显，一个数的浮点表示不是唯一的。当小数点的位置改变时，阶码也随着相应改变，因此可以用多个浮点形式表示同一个数。

浮点数所能表示的数值范围主要由阶码决定，所表示数值的精度则由尾数决定。为了充分利用尾数来表示更多的有效数字，通常采用规格化浮点数。规格化就是将尾数的绝对值限定在区间 $[0.5, 1)$。当尾数用补码表示时，需要注意如下问题：

① 若尾数 $M \geqslant 0$，则其规格化的尾数形式为 $M = 0.1 \times \times \cdots \times$，其中，$\times$ 可为 0，也可为 1，即将尾数限定在区间 $[0.5, 1)$。

② 若尾数 $M < 0$，则其规格化的尾数形式为 $M = 1.0 \times \times \cdots \times$，其中，$\times$ 可为 0，也可为 1，即将尾数 $M$ 的范围限定在区间 $[-1, -0.5]$。

如果浮点数的阶码（包括 1 位阶符）用 $R$ 位的移码表示，尾数（包括 1 位数符）用 $M$ 位的补码表示，则这种浮点数所能表示的数值范围如下。

最大的正数：$(1-2^{-M+1}) \times 2^{(2^{R-1}-1)}$，最小的负数：$-1 \times 2^{(2^{R-1}-1)}$。

（3）工业标准 IEEE 754

IEEE 754 是由 IEEE 制定的有关浮点数的工业标准，被广泛采用。该标准的表示形式如下：

$$ (-1)^S \cdot 2^E \cdot (b0 b_1 b_2 \cdots b{p-1}) $$

其中，$(-1)^S$ 为该浮点数的数符，当 $S$ 为 0 时表示正数，$S$ 为 1 时表示负数；$E$ 为指数（阶码），用移码表示；$(b0 b_1 b_2 \cdots b{p-1})$ 为尾数，其长度为 $P$ 位，用原码表示。

目前，计算机中主要使用 3 种形式的 IEEE 754 浮点数，如表 1-2 所示。

表 1-2 3 种形式的 IEEE 754 浮点数格式

根据 IEEE 754 标准，被编码的值分为 3 种不同的情况：规格化的值、非规格化的值和特殊值，规格化的值为最普遍的情形。

① 规格化的值。当阶码部分的二进制值不全为 0 也不全为 1 时，所表示的是规格化的值。例如，在单精度浮点格式下，阶码为 10110011 时，偏移量为 +127，则其表示的真值为 $10110011 - 01111111 = 00110100$，转换为十进制后为 52。

对于尾数部分，由于约定小数点左边隐含有一位，通常这位数就是 1，因此单精度浮点数尾数的有效位数为 24 位，即尾数为 $1.\times\times\cdots\times$。也就是说，不溢出的情况下尾数 $M$ 的值在 $1 \leqslant M < 2$ 之中。

【例 1.5】 利用 IEEE 754 标准将数 $176.0625$ 表示为单精度浮点数。

解： 首先将该十进制转换成二进制数： $(176.0625)_{10} = (10110000.0001)_2$

其次对二进制数进行规格化处理：$10110000.0001 = 1\diamondsuit01100000001 \times 2^7$。将 $b_0$ 去掉并扩展为单精度浮点数所规定的 23 位尾数：$01100000001000000000000$。

然后求阶码，指数为 7，单精度浮点数规定指数的偏移量为 127，即 $E = 7 + 127 = 134$，则指数的移码表示为 $10000110$。

最后，可得到 $(176.0625)_{10}$ 的单精度浮点数表示形式：

0 10000110 01100000001000000000000

② 非规格化的值。当阶码部分的二进制值全为 0 时，所表示的数是非规格化的。在这种情况下，指数的真值为 $1 - $ 偏移量（对于单精度浮点数为 -126），尾数的值就是二进制形式对应的小数，不包含隐含的 1。

非规格化数有两个用途：一是用来表示数值 0，二是表示那些非常接近于 0 的数。因为在规格化表示方式下，必须使尾数大于等于 1，因此不能表示出 0。实际上，+0.0 的浮点表示是符号、阶码和尾数的二进制表示都全为 0。需要注意的是，符号位为 1 而阶码和尾数部分全为 0 时表示 -0.0。

③ 特殊值。当阶码部分的二进制值全为 1 时，表示特殊的值。当尾数部分全部为 0 时表示无穷大，当符号位为 0 时表示 $+\infty$，当符号位为 1 时表示 $-\infty$。当浮点运算溢出时，用无穷来表示。当尾数部分不全为 0 时，称为”NaN”，即”不是一个数”。

（4）浮点数的运算

设有浮点数 $X = M \times 2^i$，$Y = N \times 2^j$，求 $X \pm Y$ 的运算过程要经过对阶、求尾数和（差）、结果规格化并判溢出、舍入处理和溢出判别等步骤。

① 对阶。使两个数的阶码相同。令 $K = |i - j|$，把阶码小的数的尾数右移 $K$ 位，使其阶码加上 $K$。

② 求尾数和（差）。

③ 结果规格化并判溢出。若运算结果所得的尾数不是规格化的数，则需要进行规格化处理。当尾数溢出时，需要调整阶码。

④ 舍入处理。在对结果右规时，尾数的最低位将因移出而丢掉。另外，在对阶过程中也会将尾数右移使最低位丢掉。这就需要进行舍入处理，以求得最小的运算误差。

⑤ 溢出判别。以阶码为准，若阶码溢出，则运算结果溢出；若阶码下溢（小于最小值），则结果为 0；否则结果正确，无溢出。

浮点数相乘，其积的阶码等于两乘数的阶码相加，积的尾数等于两乘数的尾数相乘。浮点数相除，其商的阶码等于被除数的阶码减去除数的阶码，商的尾数等于被除数的尾数除以除数的尾数。乘除运算的结果都需要进行规格化处理并判断阶码是否溢出。

1.1.4 校验码

计算机系统运行时，为了确保数据在传送过程中正确无误，一是提高硬件电路的可靠性，二是提高代码的校验能力，包括查错和纠错。通常使用校验码的方法来检测传送的数据是否出错。其基本思想是把数据可能出现的编码分为两类：合法编码和错误编码。合法编码用于传送数据，错误编码是不允许在数据中出现的编码。合理地设计错误编码以及编码规则，使得数据在传送中出现某种错误时会变成错误编码，这样就可以检测出接收到的数据是否有错。

所谓码距，是指一个编码系统中任意两个合法编码之间至少有多少个二进制位不同。例如，4 位 8421 码的码距为 1，在传输过程中，该代码的一位或多位发生错误，都将变成另外一个合法的编码，因此这种代码无检错能力。下面简要介绍常用的 3 种校验码：奇偶校验码、海明码和循环冗余校验码。

1. 奇偶校验码

奇偶校验（Parity Codes）是一种简单有效的校验方法。这种方法通过在编码中增加一位校验位来使编码中 1 的个数为奇数（奇校验）或者为偶数（偶校验），从而使码距变为 2。对于奇校验，它可以检测代码中奇数位出错的编码，但不能发现偶数位出错的情况。

常用的奇偶校验码有 3 种：水平奇偶校验码、垂直奇偶校验码和水平垂直校验码。

2. 海明码

海明码（Hamming Code）是由贝尔实验室的 Richard Hamming 设计的，是一种利用奇偶性来检错和纠错的校验方法。海明码的构成方法是在数据位之间的特定位置上插入 $k$ 个校验位，通过扩大码距来实现检错和纠错。

设数据位是 $n$ 位，校验位是 $k$ 位，则 $n$ 和 $k$ 必须满足以下关系：

$$ 2^k - 1 \geqslant n + k $$

海明码的编码规则如下：

设 $k$ 个校验位为 $Pk, P{k-1}, \cdots, P1$，$n$ 个数据位为 $D{n-1}, D{n-2}, \cdots, D_1, D_0$，对应的海明码为 $H{n+k}, H_{n+k-1}, \cdots, H_1$，那么：

（1）$P_i$ 在海明码的第 $2^{i-1}$ 位置，即 $H_j = P_i$，且 $j = 2^{i-1}$，数据位则依序从低到高占据海明码中剩下的位置。

（2）海明码中的任何一位都是由若干个校验位来校验的。其对应关系如下：被校验的海明位的下标等于所有参与校验该位的校验位的下标之和，而校验位由自身校验。

对于 8 位的数据位，进行海明校验需要 4 个校验位（$2^3-1=7,\ 2^4-1=15>8+4$）。令数据位为 $D7, D_6, D_5, D_4, D_3, D_2, D_1, D_0$，校验位为 $P_4, P_3, P_2, P_1$，形成的海明码为 $H{12}, H_{11}, \cdots, H_3, H_2, H_1$，则编码过程如下：

① 确定 D 与 P 在海明码中的位置：

② 确定校验关系，如表 1-3 所示。

表 1-3 海明码的校验关系表

若采用奇校验，则将各校验位的偶校验值取反即可。

③ 检测错误。对使用海明编码的数据进行差错检测很简单，只需做以下计算：

$$ G_1 = P_1 \oplus D_0 \oplus D_1 \oplus D_3 \oplus D_4 \oplus D_6 $$ $$ G_2 = P_2 \oplus D_0 \oplus D_2 \oplus D_3 \oplus D_5 \oplus D_6 $$ $$ G_3 = P_3 \oplus D_1 \oplus D_2 \oplus D_3 \oplus D_7 $$ $$ G_4 = P_4 \oplus D_4 \oplus D_5 \oplus D_6 \oplus D_7 $$

若采用偶校验，则 $G_4 G_3 G_2 G_1$ 全为 0 时表示接收到的数据无错误（奇校验应全为 1）。当 $G_4 G_3 G_2 G_1$ 不全为 0 时说明发生了差错，而且 $G_4 G_3 G_2 G_1$ 的十进制值指出了发生错误的位置。

【例 1.6】 设数据为 $01101001$，试采用 4 个校验位求其偶校验方式的海明码。

解： $D_7 D_6 D_5 D_4 D_3 D_2 D_1 D_0 = 01101001$，根据公式：

$P_1 = D_0 \oplus D_1 \oplus D_3 \oplus D_4 \oplus D_6 = 1 \oplus 0 \oplus 1 \oplus 0 \oplus 1 = 1$

$P_2 = D_0 \oplus D_2 \oplus D_3 \oplus D_5 \oplus D_6 = 1 \oplus 0 \oplus 1 \oplus 1 \oplus 1 = 0$

$P_3 = D_1 \oplus D_2 \oplus D_3 \oplus D_7 = 0 \oplus 0 \oplus 1 \oplus 0 = 1$

$P_4 = D_4 \oplus D_5 \oplus D_6 \oplus D_7 = 0 \oplus 1 \oplus 1 \oplus 0 = 0$

求得的海明码为：

3. 循环冗余校验码

循环冗余校验码（Cyclic Redundancy Check，CRC）广泛应用于数据通信领域和磁介质存储系统中。它利用生成多项式为 $k$ 个数据位产生 $r$ 个校验位来进行编码，其编码长度为 $k + r$。CRC 的代码格式为：

┌─────────────── 数据位 ──────────────┬─────────────── 校验位 ──────────────┐
│  n      n-1              r+1   r  │  r-1              2      1          │
└───────────────────────────────────┴──────────────────────────────────────┘

由此可知，循环冗余校验码是由两部分组成的，左边为信息码（数据），右边为校验码。若信息码占 $k$ 位，则校验码就占 $n - k$ 位。其中，$n$ 为 CRC 码的字长，所以又称为（$n$，$k$）码。校验码是由信息码产生的，校验码位数越多，该代码的校验能力就越强。在求 CRC 编码时，采用的是模 2 运算。模 2 加减运算的规则是按位运算，不发生借位和进位。

1.2 计算机体系结构

1.2.1 计算机体系结构的发展

1. 计算机系统结构概述

1964 年，阿姆达尔（G.M.Amdahl）在介绍 IBM360 系统时指出：计算机体系结构是站在程序员的角度所看到的计算机属性，即程序员要能编写出可在机器上正确运行的程序所必须了解的概念性结构和功能特性。

1982 年，梅尔斯（G.J.Myers）在其所著的《计算机体系结构的进展》（Advances in Computer Architecture）一书中定义了组成计算机系统的若干层次，每一层都提供一定的功能支持它上面的一层，并把不同层之间的界面定义为某种类型的体系结构。Myers 的定义发展了 Amdahl 的概念性结构思想，明确了传统体系结构就是指硬件与软件之间的界面，即指令集体系结构。

1984 年，拜尔（J.L.Baer）在一篇题为”计算机体系结构（Computer Architecture）”的文章中给出了一个含义更加广泛的定义：体系结构由结构、组织、实现、性能 4 个基本方面组成。其中，结构指计算机系统各种硬件的互连，组织指各种部件的动态联系与管理，实现指各模块设计的组装完成，性能指计算机系统的行为表现。

计算机体系结构、计算机组织和计算机实现三者的关系如下：

（1）计算机体系结构（Computer Architecture）是指计算机的概念性结构和功能属性。

（2）计算机组织（Computer Organization）是指计算机体系结构的逻辑实现，包括机器内的数据流和控制流的组成以及逻辑设计等（常称为计算机组成原理）。

（3）计算机实现（Computer Implementation）是指计算机组织的物理实现。

2. 计算机体系结构分类

（1）从宏观上按处理机的数量进行分类

• 单处理系统（Uni-processing System）。利用一个处理单元与其他外部设备结合起来，实现存储、计算、通信、输入与输出等功能的系统。
• 并行处理与多处理系统（Parallel Processing and Multiprocessing System）。为了充分发挥问题求解过程中处理的并行性，将两个以上的处理机互连起来，彼此进行通信协调，以便共同求解一个大问题的计算机系统。
• 分布式处理系统（Distributed Processing System）。指物理上远距离而松耦合的多计算机系统。

（2）从微观上按并行程度分类

• Flynn 分类法。1966 年，M.J.Flynn 提出按指令流和数据流的多少进行分类。Flynn 把计算机系统的结构分为以下 4 类：
  • SISD：单指令流、单数据流（Single Instruction stream Single Data stream）
  • SIMD：单指令流、多数据流（Single Instruction stream Multiple Data stream）
  • MISD：多指令流、单数据流（Multiple Instruction stream Single Data stream）
  • MIMD：多指令流、多数据流（Multiple Instruction stream Multiple Data stream）
• 冯泽云分类法。1972 年，美籍华人冯泽云（Tse-yun Feng）提出按并行度对各种计算机系统进行结构分类。冯泽云把计算机系统分成 WSBS（字串行位串行）、WPBS（字并行位串行）、WSBP（字串行位并行）和 WPBP（字并行位并行）计算机 4 类。
• Handler 分类法。1977 年，德国的汉德勒（Wolfgang Handler）提出一个基于硬件并行程度计算并行度的方法，把计算机的硬件结构分为 3 个层次：处理机级、每个处理机中的算逻单元级、每个算逻单元中的逻辑门电路级。
• Kuck 分类法。1978 年，美国的库克（David J.Kuck）提出与 Flynn 分类法类似的方法，用指令流和执行流（Execution Stream）及其多重性来描述计算机系统控制结构的特征。Kuck 把系统结构分为 SISE、SIME、MISE 和 MIME 4 类。

3. 指令系统

一个处理器支持的指令和指令的字节级编码称为其指令集体系结构（Instruction Set Architecture，ISA）。

1）指令集体系结构的分类

从体系结构的观点对指令集进行分类，可以根据下述 5 个方面：

（1）操作数在 CPU 中的存储方式。 （2）显式操作数的数量。 （3）操作数的位置。 （4）指令的操作。 （5）操作数的类型与大小。

按暂存机制分类，根据在 CPU 内部存储操作数的区别，可以把指令集体系分为 3 类：堆栈（Stack）、累加器（Accumulator）和寄存器组（a set of Registers）。

通用寄存器（General-Purpose Register Machines，GPR）的关键性优点是编译程序能有效地使用寄存器。用户可以用指令集的两个主要特征来区分 GPR 体系结构：第一个是 ALU 指令有两个或 3 个操作数；第二个是 ALU 指令中有几个操作数是存储器地址。

2）CISC 和 RISC

（1）CISC（Complex Instruction Set Computer，复杂指令集计算机）的基本思想是进一步增强原有指令的功能，用更为复杂的新指令取代原先由软件子程序完成的功能，实现软件功能的硬化。

CISC 的主要弊端如下：

① 指令集过分庞杂。 ② 微程序技术是 CISC 的重要支柱，每条复杂指令都要通过执行一段解释性微程序才能完成。 ③ 编译程序本身冗长、复杂，难以优化编译使之生成真正高效的目标代码。 ④ CISC 强调完善的中断控制，导致设计复杂。 ⑤ CISC 给芯片设计带来很多困难，使芯片种类增多，出错几率增大。

（2）RISC（Reduced Instruction Set Computer，精简指令集计算机）的基本思想是通过减少指令总数和简化指令功能降低硬件设计的复杂度，使指令能单周期执行，并通过优化编译提高指令的执行速度，采用硬布线控制逻辑优化编译程序。RISC 在 20 世纪 70 年代末开始兴起。

RISC 的关键技术如下：

① 重叠寄存器窗口技术。在伯克利的 RISC 项目中首先采用了重叠寄存器窗口（Overlapping Register Windows）技术。其基本思想是在处理机中设置一个数量比较大的寄存器堆，并把它划分成很多个窗口。 ② 优化编译技术。RISC 使用了大量的寄存器，如何合理地分配寄存器、提高寄存器的使用效率等，都应通过编译技术的优化来实现。 ③ 超流水及超标量技术。为了进一步提高流水线速度而采用的技术。 ④ 硬布线逻辑与微程序相结合。

（3）优化。面向高级程序语言的优化思路是尽可能缩小高级语言与机器语言之间的语义差距。面向操作系统的优化思路是进一步缩小操作系统与体系结构之间的语义差距。

3）指令的流水处理

（1）指令控制方式。指令控制方式有顺序方式、重叠方式和流水方式 3 种。

① 顺序方式。顺序方式是指各条机器指令之间顺序串行地执行，执行完一条指令后才取下一条指令。优点是控制简单，缺点是速度慢。

② 重叠方式。重叠方式是指在解释第 $K$ 条指令的操作完成之前就可以开始解释第 $K+1$ 条指令。通常采用的是一次重叠，即在任何时候，指令分析部件和指令执行部件都只有相邻两条指令在重叠解释。

[分析指令 K] [执行指令 K]
            [分析指令 K+1] [执行指令 K+1]

③ 流水方式。流水方式是模仿工业生产过程的流水线而提出的一种指令控制方式。流水（Pipelining）技术是把并行性或并发性嵌入到计算机系统里的一种形式，它把重复的顺序处理过程分解为若干子过程，每个子过程能在专用的独立模块上有效地并发工作。

（2）流水线的种类：

• 从流水的级别上，可分为部件级、处理机级以及系统级的流水。
• 从流水的功能上，可分为单功能流水线和多功能流水线。
• 从流水的连接上，可分为静态流水线和动态流水线。
• 从流水是否有反馈回路，可分为线性流水线和非线性流水线。
• 从流水的流动顺序上，可分为同步流水线和异步流水线。
• 从流水线的数据表示上，可分为标量流水线和向量流水线。

（3）流水的相关处理：

由于流水时机器同时解释多条指令，这些指令可能有对同一主存单元或同一寄存器的”先写后读”的要求，这时就出现了相关。这种相关包括指令相关、访存操作数相关以及通用寄存器组相关等，影响是局部的，所以称为局部性相关。解决局部性相关有两种方法：推后法和通路法。

转移指令（尤其是条件转移指令）与它后面的指令之间存在关联，执行转移指令时可能会改动指令缓冲器中预取到的指令内容，从而会造成流水线吞吐率和效率下降，比局部性相关的影响要严重得多，所以称为全局性相关。

解决全局性相关有 3 种方法：猜测转移分支、加快和提前形成条件码、加快缩短循环程序的处理。

条件转移指令有两个分支，一个分支是按原来的顺序继续执行下去，称为转移不成功分支；另一个分支是按转移后的新指令序列执行，称为转移成功分支。许多流水机器都猜测转移不成功分支。

RISC 中采用的流水技术有 3 种：超流水线、超标量以及超长指令字。

• 超流水线（Super Pipe Line）技术通过细化流水、增加级数和提高主频，使得在每个机器周期内能完成一个甚至两个浮点操作。其实质是以时间换取空间。
• 超标量（Super Scalar）技术通过内装多条流水线来同时执行多个处理。其实质是以空间换取时间。
• 超长指令字（Very Long Instruction Word，VLIW）技术充分发挥软件的作用，使硬件简化、性能提高。VLIW 有更小的 CPI 值，但需要有足够高的时钟频率。

（4）吞吐率和流水建立时间：

吞吐率是指单位时间内流水线处理机流出的结果数。如果流水线的子过程所用时间不一样，则吞吐率 $p$ 应为最长子过程的倒数，即

$$ p = 1 / \max{\Delta t_1, \Delta t_2, \cdots, \Delta t_m} $$

流水线开始工作，需经过一定时间才能达到最大吞吐率，这就是建立时间。若 $m$ 个子过程所用时间一样，均为 $\Delta t_0$，则建立时间 $T_0 = m \Delta t_0$。

4. 阵列处理机、并行处理机和多处理机

并行性包括同时性和并发性。其中，同时性是指两个或两个以上的事件在同一时刻发生，并发性是指两个或两个以上的事件在同一时间间隔内连续发生。

1）阵列处理机

阵列处理机将重复设置的多个处理单元（PU）按一定方式连成阵列，在单个控制部件（CU）控制下，对分配给自己的数据进行处理，并行地完成一条指令所规定的操作。这是一种单指令流多数据流计算机，通过资源重复实现并行性。

2）并行处理机

SIMD 和 MIMD 是典型的并行计算机，SIMD 有共享存储器和分布存储器两种形式。

在具有共享存储器的 SIMD 结构中，将若干个存储器构成统一的并行处理机存储器，通过互联网络 ICN 为整个并行系统的所有处理单元共享。其中，PE 为处理单元，CU 为控制部件，M 为共享存储器，ICN 为互联网络。

分布式存储器的 SIMD 结构中，有两类存储器：一类是存储器附属于主处理机；另一类是分布在各个处理单元上的存储器（PEM），这类存储器用来保存程序和数据。

3）多处理机

多处理机系统是由多台处理机组成的系统，每台处理机有属于自己的控制部件，可以执行独立的程序，共享一个主存储器和所有的外部设备。它是多指令流多数据流计算机。在多处理机系统中，机间的互连技术决定了多处理机的性能。

4）其他计算机

集群一般是指连接在一起的两个或多个计算机（结点）。集群计算机是一种并行或分布式处理系统，由很多连接在一起的独立计算机组成，像一个单集成的计算机资源一样协同工作。

1.2.2 存储系统

1. 存储器的层次结构

计算机系统中可能包括各种存储器，不同特点的存储器通过适当的硬件、软件有机地组合在一起形成计算机的存储体系结构。其中，Cache 和主存之间的交互功能全部由硬件实现，而主存与辅存之间的交互功能可由硬件和软件结合起来实现。

2. 存储器的分类

1）按存储器所处的位置分类

• 内存。也称为主存，设在主机内或主机板上，用来存放机器当前运行所需要的程序和数据，以便向 CPU 提供信息。特点是容量小、速度快。
• 外存。也称为辅存，如磁盘、磁带和光盘等，用来存放当前不参加运行的大量信息，而在需要时调入内存。

2）按存储器的构成材料分类

• 磁存储器。磁存储器是用磁性介质做成的，如磁芯、磁泡、磁膜、磁鼓、磁带及磁盘等。
• 半导体存储器。根据所用元件又可分为双极型和 MOS 型；根据数据是否需要刷新又可分为静态（Static Memory）和动态（Dynamic Memory）两类。
• 光存储器。利用光学方法读/写数据的存储器，如光盘（Optical Disk）。

3）按存储器的工作方式分类

• 读/写存储器（Random Access Memory，RAM）。既能读取数据也能存入数据的存储器。
• 只读存储器。工作过程中仅能读取的存储器，细分为以下几类：
  • ROM（Read Only Memory）：厂家生产时就写好数据，只能读出，不能改变。
  • PROM（Programmable ROM）：内容可由用户一次性写入，写入后不能再修改。
  • EPROM（Erasable PROM）：内容既可以读出，也可以由用户写入，写入后还可以修改。
  • EEPROM（Electrically EPROM）：用电擦除的方法进行数据的改写。
  • Flash Memory（闪速存储器）：特性介于 EPROM 和 EEPROM 之间，整块闪存可以在数秒内删除。

4）按访问方式分类

按访问方式可分为按地址访问的存储器和按内容访问的存储器。

5）按寻址方式分类

• 随机存储器（RAM）。可对任何存储单元存入或读取数据，访问任何一个存储单元所需的时间相同。
• 顺序存储器（SAM）。访问数据所需要的时间与数据所在的存储位置相关，磁带是典型的顺序存储器。
• 直接存储器（DAM）。介于随机存取和顺序存取之间的一种寻址方式。磁盘是一种直接存取存储器。

3. 相联存储器

相联存储器是一种按内容访问的存储器。其工作原理就是把数据或数据的某一部分作为关键字，按顺序写入信息，读出时并行地将该关键字与存储器中的每一单元进行比较，找出存储器中所有与关键字相同的数据字。

相联存储器的组成：输入检索寄存器（存放要检索的关键字）、屏蔽寄存器（屏蔽不参与检索的字段）、比较器、存储体、匹配寄存器和数据寄存器。

相联存储器可用在高速缓冲存储器中，在虚拟存储器中用来作为段表、页表或快表存储器，用在数据库和知识库中。

4. 高速缓存

高速缓存用来存放当前最活跃的程序和数据，其特点是：位于 CPU 与主存之间；容量一般在几千字节到几兆字节之间；速度一般比主存快 5～10 倍；其内容是主存局部域的副本，对程序员来说是透明的。

1）高速缓存的组成

Cache 存储器部分用来存放主存的部分拷贝信息。控制部分的功能是判断 CPU 要访问的信息是否在 Cache 存储器中，若在即为命中，若不在则没有命中。

现代 CPU 中 Cache 分为了多个层级：L1 指令 Cache、L1 数据 Cache、L2 Cache、L3 Cache 等。

2）高速缓存中的地址映像方法

Cache 的地址映像有如下 3 种方法：

（1）直接映像。主存的块与 Cache 块的对应关系是固定的。由于主存中的块只能存放在 Cache 存储器的相同块号中，因此，只要主存地址中的主存区号与 Cache 中记录的主存区号相同，则表明访问 Cache 命中。优点是地址变换很简单，缺点是灵活性差。

主存地址格式：[ 主存区号 | 区内块号 | 块内地址 ]

（2）全相联映像。主存与 Cache 存储器均分成大小相同的块。这种映像方式允许主存的任一块可以调入 Cache 存储器的任何一个块的空间中。主要优点是主存的块调入 Cache 的位置不受限制，十分灵活。主要缺点是无法从主存块号中直接获得 Cache 的块号，变换比较复杂。

主存地址格式：[ 主存块号 | 块内地址 ]

（3）组相联映像。这种方式是前面两种方式的折中。具体方法是将 Cache 中的块再分成组，组采用直接映像方式而块采用全相联映像方式。

3）替换算法

替换算法的目标就是使 Cache 获得尽可能高的命中率。常用算法有：

• 随机替换算法：用随机数发生器产生一个要替换的块号。
• 先进先出算法：将最先进入 Cache 的信息块替换出去。
• 近期最少使用算法：将近期最少使用的 Cache 中的信息块替换出去。
• 优化替换算法：必须先执行一次程序，统计 Cache 的替换情况，再以此优化第二次执行。

4）Cache 的性能分析

Cache 的性能是计算机系统性能的重要方面。设 $H_c$ 为 Cache 的命中率，$t_c$ 为 Cache 的存取时间，$t_m$ 为主存的访问时间，则 Cache 存储器的等效加权平均访问时间 $t_a$ 为：

$$ t_a = H_c t_c + (1 - H_c) t_m = t_c + (1 - H_c)(t_m - t_c) $$

如果 Cache 不命中时才启动主存，则 $t_a = t_c + (1 - H_c) t_m$。

降低 Cache 失效率的方法主要有选择恰当的块容量、提高 Cache 的容量和提高 Cache 的相联度等。

5）多级 Cache

在多级 Cache 的计算机中，Cache 分为 L1 Cache、L2 Cache、L3 Cache 等，CPU 访存时首先查找 L1 Cache，如果不命中，则访问 L2 Cache，直到所有级别的 Cache 都不命中，才访问主存。

5. 虚拟存储器

现代系统提供了一种对主存的抽象，称为虚拟存储（Virtual Memory），使用虚拟地址（Virtual Address，由 CPU 生成）来访问主存，使用专门的 MMU（Memory Management Unit）将虚拟地址转换为物理地址后访问主存。

虚拟存储器实际上是一种逻辑存储器，实质是对物理存储设备进行逻辑化的处理，并将统一的逻辑视图呈现给用户。

6. 外存储器

外存储器用来存放暂时不用的程序和数据，并且以文件的形式存储。CPU 不能直接访问外存中的程序和数据，只有将其以文件为单位调入主存才可访问。

1）磁表面存储器

在磁表面存储器中，磁盘的存取速度较快，且具有较大的存储容量，是目前广泛使用的外存储器。磁盘存储器由盘片、驱动器、控制器和接口组成。

将文件存储在硬盘上时尽可能放在同一圆柱面上，或者放在相邻柱面上，这样可以缩短寻道时间。

硬盘的寻址信息由硬盘驱动号、圆柱面号、磁头号（记录面号）、数据块号（或扇区号）以及交换量组成。

磁盘容量有两种指标：

• 非格式化容量 = 面数 ×（磁道数/面）× 内圆周长 × 最大位密度
• 格式化容量 = 面数 ×（磁道数/面）×（扇区数/道）×（字节数/扇区）

2）光盘存储器

光盘存储器是一种采用聚焦激光束在盘式介质上非接触地记录高密度信息的新型存储装置。根据性能和用途可分为：CD-ROM（只读型）、WORM（只写一次型）和可擦除型光盘。

3）固态硬盘

固态硬盘的存储介质分为两种：一种采用闪存（FLASH 芯片）作为存储介质，另一种采用 DRAM 作为存储介质。固态硬盘具有读写快速、质量轻、能耗低以及体积小等特点，但其价格仍较为昂贵，容量较低，一旦硬件损坏，数据较难恢复。

7. 磁盘阵列技术

磁盘阵列是由多台磁盘存储器组成的一个快速、大容量、高可靠的外存子系统。现在常见的磁盘阵列称为廉价冗余磁盘阵列（Redundant Array of Independent Disk，RAID），如表 1-4 所示。

表 1-4 廉价冗余磁盘阵列

8. 存储域网络

存储域网络（Storage Area Network，SAN）把一个或多个服务器与多个存储设备连接起来，构成了存储域网络。这样的网络不仅解决了服务器对存储容量的要求，还可以使多个服务器之间共享文件系统和辅助存储空间。

1.2.3 输入/输出接口

1. 微型计算机中最常用的内存与接口的编址方法

1）内存与接口独立编址方法

在内存与接口地址独立编址方法下，内存地址和接口地址是完全独立的两个地址空间。用于接口的指令只用于接口的读/写，其余的指令全都是用于内存的。编程序时很容易使用和辨认，但缺点是用于接口的指令太少、功能太弱。

2）内存与接口地址统一编址方法

在这种编址方法中，内存地址和接口地址统一在一个公共的地址空间里。优点是用于内存的指令全都可以用于接口，大大增强了对接口的操作功能。缺点在于整个地址空间被分成两部分，经常会导致内存地址不连续。

2. 直接程序控制

直接程序控制是指外设数据的输入/输出过程是在 CPU 执行程序的控制下完成的。这种方式分为无条件传送和程序查询方式两种情况。

1）无条件传送

外设总是准备好的，可以无条件地随时接收 CPU 发来的输出数据，也能够无条件地随时向 CPU 提供需要输入的数据。

2）程序查询方式

通过 CPU 执行程序来查询外设的状态，判断外设是否准备好接收数据或准备好了向 CPU 输入的数据。

这种工作方式的缺点：

• 降低了 CPU 的效率。CPU 不做别的事，只是不停地对外设的状态进行查询。
• 对外部的突发事件无法做出实时响应。

3. 中断方式

利用中断方式完成数据的输入/输出过程为：当 I/O 系统与外设交换数据时，CPU 无须等待也不必去查询 I/O 的状态，而可以抽身出来处理其他任务。当 I/O 系统准备好以后，则发出中断请求信号通知 CPU，CPU 接到中断请求信号后，保存正在执行程序的现场，转入 I/O 中断服务程序的执行，完成与 I/O 系统的数据交换，然后再返回被打断的程序继续执行。

1）中断处理方法

在系统中具有多个中断源的情况下，常用的处理方法有：

• 多中断信号线法：每个中断源都有属于自己的一根中断请求信号线向 CPU 提出中断请求。
• 中断软件查询法：当 CPU 检测到一个中断请求信号以后，即转入到中断服务程序去轮询每个中断源以确定是谁发出了中断请求信号。
• 菊花链法：一种硬件查询法，所有的 I/O 模块共享一根共同的中断请求线，而中断确认信号则以链式在各模块间相连。
• 总线仲裁法：一个 I/O 设备在发出中断请求之前，必须先获得总线控制权。
• 中断向量表法：中断向量表用来保存各个中断源的中断服务程序的入口地址。当外设发出中断请求信号（INTR）以后，由中断控制器（INTC）确定其中断号，并根据中断号查找中断向量表来取得其中断服务程序的入口地址。

2）中断优先级控制

在中断优先级控制系统中，解决以下两种情况：

（1）当不同优先级的多个中断源同时提出中断请求时，CPU 应优先响应优先级最高的中断源。

（2）当 CPU 正在对某一个中断源服务时，又有比它优先级更高的中断源提出中断请求，CPU 应能暂时中断正在执行的中断服务程序而转去对优先级更高的中断源服务，这种情况称为中断嵌套。

4. 直接存储器存取方式

直接内存存取（Direct Memory Access，DMA）是指数据在内存与 I/O 设备间的直接成块传送，即在内存与 I/O 设备间传送一个数据块的过程中，不需要 CPU 的任何干涉，只需要 CPU 在过程开始启动与过程结束时的处理，实际操作由 DMA 硬件直接执行完成。

DMA 传送的一般过程：

（1）外设向 DMA 控制器（DMAC）提出 DMA 传送的请求。 （2）DMA 控制器向 CPU 提出请求，其请求信号通常加到 CPU 的保持请求输入端 HOLD 上。 （3）CPU 在完成当前的总线周期后立即对此请求作出响应。 （4）DMAC 获得了对系统总线的控制权，开始实施对系统总线的控制。 （5）DMAC 送出地址信号和控制信号，实现数据的高速传送。 （6）当 DMAC 将规定的字节数传送完时，它就将 HOLD 信号变为无效，CPU 重新获得系统总线的控制权。

根据占用总线方法的不同，DMA 可以分为中央处理器停止法、总线周期分时法和总线周期挪用法等。

5. 输入/输出处理机（IOP）

通道是一个具有特殊功能的处理器，又称为输入输出处理器（Input/Output Processor，IOP），它分担了 CPU 的一部分功能，可以实现对外围设备的统一管理，完成外围设备与主存之间的数据传送。

外围处理机（Peripheral Processor Unit，PPU）方式是通道方式的进一步发展。PPU 是专用处理机，它根据主机的 I/O 命令，完成对外设数据的输入输出。

1.2.4 总线结构

总线（Bus）是指计算机设备和设备之间传输信息的公共数据通道。总线是连接计算机硬件系统内多种设备的通信线路，它的一个重要特征是由总线上的所有设备共享。

1. 总线的分类

微机中的总线分为数据总线、地址总线和控制总线 3 类：

• 数据总线（Data Bus，DB）用来传送数据信息，是双向的。DB 的宽度决定了 CPU 和计算机其他设备之间每次交换数据的位数。
• 地址总线（Address Bus，AB）用于传送 CPU 发出的地址信息，是单向的。地址总线的宽度决定了 CPU 的最大寻址能力。
• 控制总线（Control Bus，CB）用来传送控制信号、时序信号和状态信息等。

2. 常见总线

1.3 安全性、可靠性与系统性能评测基础知识

1.3.1 计算机安全概述

计算机安全可包括安全管理、通信与网络安全、密码学、安全体系及模型、容错与容灾、涉及安全的应用程序及系统开发、法律、犯罪及道德规范等领域。

1. 计算机的安全等级

计算机系统中的三类安全性是指技术安全性、管理安全性和政策法律安全性。

一些重要的安全评估准则：

• 《可信计算机系统评估准则》（TCSEC），由美国国防部和国家标准局推出。
• 加拿大的《可信计算机产品评估准则》（CTCPEC）。
• 美国的《联邦（最低安全要求）评估准则》（FC）。
• 欧洲的《信息技术安全评估准则》（ITSEC）。
• 美国的《信息技术安全通用评估准则》（CC 标准），ISO 于 1996 年以 ISO/IEC 15408—1999 名称正式列入国际标准系列。

美国国防部和国家标准局的《可信计算机系统评测标准》TCSEC/TDI 将系统划分为 4 组 7 个等级，如表 1-5 所示。

表 1-5 安全性的级别

2. 安全威胁

安全威胁分为两类：故意（如黑客渗透）和偶然（如信息发往错误的地址）。典型的安全威胁举例如表 1-6 所示。

表 1-6 典型的安全威胁

3. 影响数据安全的因素

（1）内部因素：可采用多种技术对数据加密；制定数据安全规划；建立安全存储体系；建立事故应急计划和容灾措施；重视安全管理。

（2）外部因素：将数据分成不同的密级；设置身份认证、密码、口令等多种认证；设置防火墙；建立入侵检测、审计和追踪；物理环境保护等。

1.3.2 加密技术和认证技术

1. 加密技术

数据加密的基本过程就是对原来为明文的文件或数据按某种加密算法进行处理，使其成为不可读的一段代码，通常称为”密文”。

数据加密是用加密算法 $E$ 和加密密钥 $K_1$ 将明文 $P$ 变换成密文 $C$：

$$ C = E_{K_1}(P) $$

数据解密是数据加密的逆过程，解密算法 $D$ 和解密密钥 $K_2$ 将密文 $C$ 变换成明文 $P$：

$$ P = D_{K_2}(C) $$

密钥加密技术的密码体制分为对称密码体制和非对称密码体制两种。

1）对称加密技术

对称加密采用了对称密码编码技术，其特点是文件加密和解密使用相同的密钥。常用的对称加密算法有：

• DES（Digital Encryption Standard）算法：用 56 位密钥对 64 位二进制数据块进行加密，每次加密可对 64 位的输入数据进行 16 轮编码。
• 三重 DES（3DES，或称 TDEA）：用两个 56 位的密钥 K1 和 K2，发送方用 K1 加密，K2 解密，再使用 K1 加密。
• RC-5（Rivest Cipher 5）：由 Ron Rivest 在 1994 年开发出来。
• IDEA（International Data Encryption Adleman）：密钥为 128 位。由 PGP 系统使用。
• AES（Advanced Encryption Standard）算法：基于排列和置换运算，可以使用 128、192 和 256 位密钥，用 128 位分组加密和解密数据。

2）非对称加密技术

非对称加密算法需要两个密钥：公开密钥（Publickey）和私有密钥（Privatekey）。公开密钥与私有密钥是一对，如果用公开密钥对数据进行加密，只有用对应的私有密钥才能解密。

非对称加密算法实现机密信息交换的基本过程是：甲方生成一对密钥并将其中的一把作为公用密钥向其他方公开；乙方使用该密钥对机密信息进行加密后再发送给甲方；甲方再用自己保存的另一把专用密钥对加密后的信息进行解密。

RSA（Rivest, Shamir and Adleman）算法是一种公钥加密算法，它按照下面的要求选择公钥和密钥：

（1）选择两个大素数 $p$ 和 $q$（大于 $10^{100}$）。 （2）令 $n = p \times q$ 和 $z = (p-1) \times (q-1)$。 （3）选择 $d$ 与 $z$ 互质。 （4）选择 $e$，使 $e \times d = 1 \pmod{z}$。

明文 $P$ 被分成 $k$ 位的块，$k$ 是满足 $2^k < n$ 的最大整数。加密时计算：

$$ C = P^e \pmod{n} $$

解密时计算：

$$ P = C^d \pmod{n} $$

公钥为 $(e, n)$，私钥为 $(d, n)$。

RSA 算法的安全性是基于大素数分解的困难性。

3）密钥管理

密钥是有生命周期的，密钥管理主要是指密钥对的安全管理，包括密钥产生、密钥备份、密钥恢复、密钥更新等。

（1）密钥产生：密钥对的产生是证书申请过程中重要的一步。私钥由用户保留，公钥和其他信息交给 CA 中心进行签名。 （2）密钥备份和恢复：在一个 PKI（Public Key Infrastructure，公开密钥体系）系统中，维护密钥对的备份至关重要。 （3）密钥更新：当用户的私钥被泄漏或证书的有效期快到时，用户应该更新私钥。 （4）多密钥的管理：Kerberos 提供了一种解决大量密钥管理问题的方案。Kerberos 建立了一个安全的、可信任的密钥分发中心（Key Distribution Center，KDC）。

2. 认证技术

认证技术主要解决网络通信过程中通信双方的身份认可。认证方法一般有账户名/口令认证、使用摘要算法认证和基于 PKI 的认证。

PKI（Public Key Infrastructure）是遵循既定标准的密钥管理平台，能够为所有网络应用提供加密和数字签名等密码服务及所必需的密钥和证书管理体系。

完整的 PKI 系统必须具有以下基本构成部分：

（1）认证机构（CA）：即数字证书的申请及签发机关，CA 必须具备权威性的特征。 （2）数字证书库：用于存储已签发的数字证书及公钥，用户可由此获得所需的其他用户的证书及公钥。 （3）密钥备份及恢复系统：但须注意，密钥的备份与恢复必须由可信的机构来完成。签名私钥为确保其唯一性而不能够作备份。 （4）证书作废系统：证书作废处理系统是 PKI 的一个必备组件。 （5）应用接口（API）：PKI 的价值在于使用户能够方便地使用加密、数字签名等安全服务。

1）Hash 函数与信息摘要

Hash（哈希）函数提供了这样一种计算过程：输入一个长度不固定的字符串，返回一串固定长度的字符串，又称 Hash 值。

MD5（MD 表示信息摘要）是由 Ron Rivest 设计的专门用于加密处理的并被广泛使用的 Hash 函数。MD5 以 512 位分组来处理输入的信息，且每一分组又被划分为 16 个 32 位子分组，经过了一系列的处理后，算法的输出由四个 32 位分组组成，将这四个 32 位分组级联后将生成一个 128 位散列值。

MD5 算法具有以下特点：

（1）压缩性：任意长度的数据，算出的 MD5 值长度都是固定的。 （2）容易计算：从原数据计算出 MD5 值很容易。 （3）抗修改性：对原数据进行任何改动，即使只修改 1 个字节，所得到的 MD5 值都有很大区别。 （4）强抗碰撞：已知原数据和其 MD5 值，想找到一个具有相同 MD5 值的数据是非常困难的。

2）数字签名

数字签名主要经过以下几个过程：

（1）信息发送者使用一个单向散列函数（Hash 函数）对信息生成信息摘要。 （2）信息发送者使用自己的私钥签名信息摘要。 （3）信息发送者把信息本身和已签名的信息摘要一起发送出去。 （4）信息接收者通过使用与信息发送者使用的同一个单向散列函数对接收的信息本身生成新的信息摘要，再使用信息发送者的公钥对信息摘要进行验证。

3）SSL 协议

SSL（Secure Sockets Layer，安全套接层）协议主要用于提高应用程序之间数据的安全系数。SSL 协议主要提供如下三方面的服务：

（1）用户和服务器的合法性认证：使得它们能够确信数据将被发送到正确的客户端和服务器上。 （2）加密数据以隐藏被传送的数据：安全套接层协议所采用的加密技术既有对称密钥技术，也有公开密钥技术。 （3）保护数据的完整性：采用 Hash 函数和机密共享的方法来提供信息的完整性服务。

安全套接层协议的实现过程主要经过如下几个阶段：接通阶段 → 密码交换阶段 → 会谈密码阶段 → 检验阶段 → 客户认证阶段 → 结束阶段。

4）数字时间戳技术

数字时间戳服务（Digital Time Stamp Service，DTS）是网上电子商务安全服务项目之一，能提供电子文件的日期和时间信息的安全保护。

时间戳是一个经加密后形成的凭证文档，包括如下 3 个部分：

（1）需加时间戳的文件的摘要（Digest）。 （2）DTS 收到文件的日期和时间。 （3）DTS 的数字签名。

1.3.3 计算机可靠性

1. 计算机可靠性概述

计算机系统的硬件故障通常是由元器件的失效引起的。元器件的可靠性可分成 3 个阶段：不稳定期（失效率较高）、正常工作期（失效率最低，基本保持常数）和老化期（失效率又重新提高），这就是所谓的”浴盆曲线“。

计算机系统的可靠性是指从它开始运行（$t=0$）到某时刻 $t$ 这段时间内能正常运行的概率，用 $R(t)$ 表示。所谓失效率，是指单位时间内失效的元件数与元件总数的比例，用 $\lambda$ 表示，当 $\lambda$ 为常数时，可靠性与失效率的关系为：

$$ R(t) = e^{-\lambda t} $$

两次故障之间系统能正常工作的时间的平均值称为平均无故障时间（MTBF），即：

$$ MTBF = 1 / \lambda $$

通常用平均修复时间（MTRF）来表示计算机的可维修性，即计算机的维修效率，指从故障发生到机器修复平均所需要的时间。

计算机的可用性是指计算机的使用效率，它以系统在执行任务的任意时刻能正常工作的概率 $A$ 来表示，即：

$$ A = \frac{MTBF}{MTBF + MTRF} $$

计算机的 RAS 是指用可靠性 $R$、可用性 $A$ 和可维修性 $S$ 这 3 个指标衡量一个计算机系统。

2. 计算机可靠性模型

常见的系统可靠性数学模型有以下 3 种。

（1）串联系统

假设一个系统由 $N$ 个子系统组成，当且仅当所有的子系统都能正常工作时系统才能正常工作，这种系统称为串联系统。

设系统中各个子系统的可靠性分别用 $R_1, R_2, \cdots, R_N$ 来表示，则系统的可靠性 $R$ 可由下式求得：

$$ R = R_1 R_2 \cdots R_N $$

如果系统的各个子系统的失效率分别用 $\lambda_1, \lambda_2, \cdots, \lambda_N$ 来表示，则系统的失效率 $\lambda$ 可由下式求得：

$$ \lambda = \lambda_1 + \lambda_2 + \cdots + \lambda_N $$

【例 1.7】 设计计算机系统由 CPU、存储器、I/O 三部分组成，其可靠性分别为 0.95、0.90 和 0.85，求计算机系统的可靠性。

解： $R = R_1 \cdot R_2 \cdot R_3 = 0.95 \times 0.90 \times 0.85 = 0.73$

计算机系统的可靠性为 0.73。

（2）并联系统

假如一个系统由 $N$ 个子系统组成，只要有一个子系统正常工作，系统就能正常工作，这样的系统称为并联系统。

整个系统的可靠性可由下式求得：

$$ R = 1 - (1 - R_1)(1 - R_2) \cdots (1 - R_N) $$

假如所有子系统的失效率均为 $\lambda$，则系统的失效率 $\mu$ 为：

$$ \mu = \frac{1}{\frac{1}{\lambda} \sum_{j=1}^N \frac{1}{j}} $$

在并联系统中只有一个子系统是真正需要的，其余 $N-1$ 个子系统称为冗余子系统。

【例 1.8】 设一个系统由 3 个相同的子系统构成，其可靠性为 0.9，平均无故障时间为 10,000 小时，求系统的可靠性和平均无故障时间。

解： $R_1 = R_2 = R_3 = 0.9$，$\lambda_1 = \lambda_2 = \lambda_3 = 1 / 10000 = 1 \times 10^{-4}$（小时）

系统可靠性 $R = 1 - (1 - R_1)^3 = 1 - 0.1^3 = 0.999$

系统平均无故障时间：

$$ MTBF = \frac{1}{\mu} = \frac{1}{\lambda} \sum_{j=1}^3 \frac{1}{j} = \frac{1}{\lambda} \times \left(1 + \frac{1}{2} + \frac{1}{3}\right) = 10{,}000 \times \frac{11}{6} \approx 18{,}333 \text{（小时）} $$

（3）$N$ 模冗余系统

$N$ 模冗余系统由 $N$ 个（$N = 2n + 1$）相同的子系统和一个表决器组成，表决器把 $N$ 个子系统中占多数相同结果的输出作为系统的输出。

在 $N$ 个子系统中，只要有 $n + 1$ 个或 $n + 1$ 个以上的子系统能正常工作，系统就能正常工作。假设表决器是完全可靠的，每个子系统的可靠性为 $R_0$，则 $N$ 模冗余系统的可靠性为：

$$ R = \sum_{i=n+1}^{N} \binom{N}{i} \times R_0^i (1 - R_0)^{N-i} $$

其中，$\binom{N}{i}$ 表示从 $N$ 个元素中取 $i$ 个元素的组合数。

提高计算机的可靠性一般采取如下两项措施：

（1）提高元器件质量，改进加工工艺与工艺结构，完善电路设计。 （2）发展容错技术，使得在计算机硬件有故障的情况下，计算机仍能继续运行，得出正确的结果。

1.3.4 计算机系统的性能评价

1. 性能评测的常用方法

（1）时钟频率。计算机的时钟频率在一定程度上反映了机器速度，一般来讲，主频越高，速度越快。但是，相同频率、不同体系结构的机器，其速度可能会相差很多。

（2）指令执行速度。当时表征机器运算速度的单位是 KIPS（每秒千条指令），后来随着机器运算速度的提高，计量单位发展到 MIPS（每秒百万条指令）。另一种描述计算机指令执行速度的指标是每秒钟执行浮点数的百万次操作的数量 MFLOPS。

（3）等效指令速度法。设某类指令 $i$ 在程序中所占的比例为 $w_i$，执行时间为 $t_i$，则等效指令的执行时间为：

$$ T = \sum_{i=1}^{n} (w_i \times t_i) $$

其中，$n$ 为指令的种类数。

（4）数据处理速率（Processing Data Rate，PDR）法。PDR 值越大，机器性能越好：

$$ PDR = \frac{L}{R} $$

其中，$L = 0.85G + 0.15H + 0.4J + 0.15K$，$R = 0.85M + 0.09N + 0.06P$。

• $G$：每条定点指令的位数；$M$：平均定点加法时间
• $H$：每条浮点指令的位数；$N$：平均浮点加法时间
• $J$：定点操作数的位数；$P$：平均浮点乘法时间
• $K$：浮点操作数的位数

（5）核心程序法。把应用程序中用得最频繁的那部分核心程序作为评价计算机性能的标准程序，在不同的机器上运行，测得其执行时间，作为各类机器性能评价的依据。

2. 基准测试程序

基准程序法（Benchmark）是目前被用户一致承认的测试性能的较好方法。

（1）整数测试程序

Dhrystone 是一个综合性的基准测试程序。Dhrystone 程序测试的结果由每秒多少个 Dhrystones 来表示机器的性能，这个数值越大，性能越好。VAX11/780 的测试结果为每秒 1757 Dhrystones。

（2）浮点测试程序

• Linpack 基准测试程序：主要测试向量性能和高速缓存性能。在测量计算机系统的 Linpack 性能时，让机器运行 Linpack 程序，测量运行时间，将结果用 MFLOPS 表示。

  矩阵的向量化程度如表 1-7 所示。

  表 1-7 矩阵的向量化程度

  | 矩阵规模 | 100×100 | 300×300 | 1000×1000 | | :—- | :—-: | :—-: | :—-: | | 向量化百分比 | 80% | 95% | 98% |

• Whetstone 基准测试程序：用 FORTRAN 语言编写的综合性测试程序，主要由执行浮点运算、整数算术运算、功能调用、数组变址、条件转移和超越函数的程序组成。Whetstone 的测试结果用 Kwips 表示，1Kwips 表示机器每秒钟能执行 1000 条 Whetstone 指令。

• 理论峰值浮点速度：巨型机和小巨型机在说明书中经常给出”理论峰值速度”的 MFLOPS 值。

（3）SPEC 基准程序

SPEC（System Performance Evaluation Cooperation）是由几十家世界知名的计算机厂商所支持的非盈利的合作组织。SPEC CPU2006 包括 12 个整数基准程序集（CINT2006）和 17 个浮点基准程序集（CFP2006）。

为了简化测试结果，SPEC 使用单一的数字 SPECratio 来归纳 12 种整数基准程序：将被测计算机的执行时间标准化，即将被测计算机的执行时间除以一个参考处理器的执行时间。SPECratio 值越大，表示性能越快。

（4）TPC 基准程序

TPC（Transaction Processing Council，事务处理委员会）基准程序是由 TPC 开发的评价计算机事务处理性能的测试程序。

• TPC-C：在线事务处理（OLTP）的基准程序。
• TPC-D：决策支持的基准程序。
• TPC-E：大型企业信息服务的基准程序。

TPC 测试结果主要有两个指标：性能指标（tpsE）和性价比（美元/tpsE），前者值越大越好，后者数值越小越好。