软件设计师 - 第1章计算机网络概论

计算机系统硬件基本组成

输入设备：键盘，鼠标
输出设备：显示器，打印机...
存储器：主存储器，如内存；辅助存储器，如外存
运算器：与控制器一同集成在CPU中
控制器：与运算器一同集成在CPU中

中央处理单元 CPU

运算器

算术逻辑单元 ALU：数据的算术运算和逻辑运算
累加寄存器 AC：通用寄存器，为ALU提供工作区，用来暂存数据
数据缓冲寄存器 DR：写内存时，暂存指令或数据
状态条件寄存器 PSW：存状态标志余控制标志，归属于运算器还是控制器存在争议

控制器

程序计数器 PC：存储下一条要执行的指令地址
指令寄存器 IR：存储即将执行的指令
地址寄存器 AC：保存当前CPU访问的内存地址
指令译码器 ID：对指令中的操作码字段进行解析
时序部件：提供时序控制信号

寄存器组

专用寄存器：运算器和控制器中的寄存器都是专用寄存器
通用寄存器

数据表示

进制

常用进制

2进制（使用B表示），如10011B，表示19
8进制（使用O表示），如23O，表示19
16进制（使用H表示），如13H，表示19
10进制（使用D表示），如19D，表示19

使用场景

主存编址计算
段页式存储地址转换
IP地址转换

进制转换

其他进制 -> 10进制

小数点左右两侧处理逻辑相同，左侧位权从0开始，右侧位权从-1开始，位权...(4)(3)(2)(1)(0).(-1)(-2)(-3)(-4)...，举两个整数的例子：

如23O，表示2*8^1+3*8^0=19D，2是最高位数值，8是进制，^1是最高位位权，最低位同理
如1234H，表示1*16^3+2*16^2+3*16^1+4*16^0=4660D

10进制 -> 其他进制

除基取余法，直到商为0，基就是进制数，例子：

如34H转8进制，34/8=4...2，则42O

其他算法

10进制 -> 2进制：减法，记录2的各个位权值，然后计算
10进制 -> 8或16进制：(8)421法，每3/4位作为一个数值

定点小数

一般指的是(-1,1)区间的数值，位权(-1)(-2)(-3)(-4)...，例子：

如011B，表示0*2^(-1)+1*2^(-2)+1*2^(-3)=0*1/2+1*1/4+1*1/8=3/8=0.375

码制

原码 Sign-Magnitude Representation

通常最高位是符号为，0表示整数，1表示负数，其余位表示该数值

由于0的表示数有两个（000...0和100...0），所以原码可表示数值个数，2 ^ n - 1
定点整数表示范围，[-2^(n-1)-1,+2^(n-1)-1]
定点小数表示范围，[-(1-2^-(n-1)),1-2^-(n-1)]

反码 Ones’ Complement

符号位同原码。当为正时，同原码；当为负数时，其余各位取反表示该数值

由于0的表示数有两个（000...0和111...1），所以反码可表示数值个数，2 ^ n - 1
定点整数表示范围，[-2^(n-1)-1,+2^(n-1)-1]
定点小数表示范围，[-(1-2^-(n-1)),1-2^-(n-1)]

补码 Two’s Complement

符号位同原码。当为正时，同原码；当为负数时，其余各位取反后整体+1表示该数值

由于0的表示数只有一个（000...0），所以补码可表示数值个数，2 ^ n
定点整数表示范围，[-2^(n-1),+2^(n-1)-1]
定点小数表示范围，[-1,1-2^-(n-1)]

移码 Excess-K or Offset Binary

补码的符号位取反，所以移码可表示数值个数，2 ^ n

定点整数，[-2^(n-1),+2^(n-1)-1]
定点小数，[-1,1-2^-(n-1)]

浮点数表示

表示格式：N = R ^ e * M

M表示尾数，使用定点小数
- 位数越多表示精度越高，一般使用补码表示，IEEE754标准中使用使用原码书写尾数
- 尾数中一般包含数符，表示尾数的符号位
e表示阶码，使用定点整数
- 位数越多表示范围越大，一般使用移码表示
- 阶码中一般包含阶符，表示阶码的符号位
R表示基数，固定为2

浮点数运算

对阶：小数向大数看齐，通过较小数的尾数右移实现阶码相同
尾数计算
结果格式化

校验码

奇偶校验码

可检查奇数位的错误，不可纠错，码距2

校验位：1bit，一般在头部，尾部也行
奇校验：信息位+校验位 "1" 的个数是奇数
偶校验：信息位+校验位 "1" 的个数是偶数

循环冗余校验码 CRC（Cyclic Redundancy Check）

可检错，不可纠错

校验位：生成多项式决定，余数0表示正确，一般在尾部
模2除法（异或运算——不同为1，不进位，不借位）求余，将余数拼接在信息位后

若信息码字为 111000110，生成多项式 G(x)=x^5+x^3+x+1，则计算出的 CRC 校验码为(11001)，步骤如下：

将生成多项式的系数作为除数(101011);
生成多项式的最高幂次数(5)作为检验码的位数。
将信息码左移生成多项式的最高幂次数(5)位，作为被除数。
执行模 2 除法，即异或操作。
等到(5 位)余数即为校验码，不足左侧补0。

海明校验码

可检错，可纠错

公式：2^r -1 >= m + r
m：信息位的个数，求 r 的最小值
校验码位置：1 2 4 8 16 ...
采用分组奇偶校验，分组交叉可确定出错位置

以10位数据为例，其海明码表示D9D8D7D6D5D4P4D3D2D1P3D0P2P1中,其中Di(0≤i≤9)表示数据位，P(1≤j≤4)表示校验位，数据位D9由P4、P3和P2进行校验(从右至左D9的位序为14，即等于8+4+2，因此用第8位的P4、第4位的P3和第2位的P2校验)，数据位D5由()进行校验。

共14位，D9，14=8+4+2，D5, 10=8+2

Flynn分类

根据指令流、数据流的多倍性特征对计算机系统进行分类，通常称为Flynn分类法

SISD：单指令单数据
SIMD：单指令多数据
MISD：多指令单数据，很少见
MIMD：多指令多数据

CISC与RISC

指令系统类型	指令	寻址方式	实现方式	其他
CISC	数量多，使用频率差别大，可变长格式	支持多种	微程序控制技术	研制周期长
RISC	数量少，使用频率接近，定长格式，大部分为单周期指令，操作寄存器，只有Load/Store操作内存	支持方式少	增加了通用寄存器，硬布线逻辑控制为主，适合采用流水线	优化编译，有效支持高级语言

复杂指令集 CISC（Complex Instruction Set Computing）

指令数量多，使用频率差别大，可变长格式
支持多种寻址方式
微程序控制技术(微码)
研制周期长

精简指令集 RISC（Reduced Instruction Set Computing）

指令数量少，使用频率接近，定长格式，大部分为单周期指令
操作寄存器，只有Load/Store 操作内存
支持方式少量寻址方式，以寄存器寻址为主
增加了通用寄存器;硬布线逻辑制为主;适合采用流水线
优化编译，有效支持高级语言

流水线技术

流水线技术的前提是个操作可并行，如某条指令的取指不影响其他指令的分析与执行，并且每条指令相同阶段耗时一致，下面介绍流水线技术中的一些概念

流水线建立时间：第一条执行执行时间长度

流水线周期：后续的指令完成时间长度，执行时间最长的一段

流水线执行时间：第一条指令时长 + (n - 1) * 流水线周期

理论公式：(t1 + t2 + ... + tk) + (n - 1) * t，没有答案时使用实践公式
实践公式：k * t + (n - 1) * t
k：每条指令操段数量，例如上面的取址、分析、执行，k=3
t：流水线周期，执行时间最长的一段

流水线吞吐率：单位时间内流水线完成任务量，TP=指令条数/流水线执行时间

流水最大吞吐率：TP=lim(n/(k * t + (n - 1) * t))=1/t

流水线加速比：需要固定执行指令条数，不用流水线时长/使用流水线时长

超流水线技术：细化流水线，增加级数和提供主频。以时间换去空间。

超标量技术：内装多条流水线来同时执行多个处理。以空间换时间。

超长指令技术：提高软件的作用，简化硬件设计，性能提高。

寻址

指令寻址方式

顺序：地址顺序执行
跳跃：由本条指令指出下一条指令地址
指令格式：操作码字段 + 地址码字段
操作码：MOV ADD JMP

操作数寻址方式

立即寻址方式：操作数直接在指令中，速度快，灵活性差
直接寻址方式：指令中存放的是操作数的地址
间接寻址方式：指令中存放了一个地址，这个地址对应的内容是操作数的地址
寄存器寻址方式：寄存器存放操作数
寄存器间接寻址方式：寄存器内存放的是操作数的地址
隐含寻址方式：操作数存放在累加器AC中

？？？有没有一种方式寄存器中存放了一个地址，这个地址对应的内容是操作数的地址

存储系统

层次化存储体系

辅助存储器，外存：硬盘，光盘，U盘等，其容量能达到TB级别
内存：随机存储器RAM，只读存储器ROM，其容量能达到GB级别
Cache：按内容存取，其容量能达到MB级别
CPU中寄存器：最快，容量小，成本高，其容量能达到B级别
虚拟存储体系：内存+外存
三级存储体系：Cache+内存+外存

局部性原理

局部性原理是层次化存储结构的支撑

时间局部性：刚被访问的内容，立即被访问，循环的体现
空间局部性：刚被访问的内容，临近的空间很快被访问，顺序的体现，数组

存储器分类

按存储器位置分类：

内存
外存

按存取方式分类：

按内容存取：
- 相联存储器
- Cache
按地址存取：
- 随机存取存储器：内容
- 顺序存取存储器：磁带
- 直接存取存储器：磁盘

按工作方式分类：

随机存取存储器RAM，内存DRAM，掉电内容丢失，定时刷新
只读存储器ROM，BIOS

其他概念

SRAM：静态随机存取存储器，不需要定时刷新
EEPROM：电可擦可编程只读存储器

Cache

命中率

命中率会随着容量的扩大而提高，但并非线性的，命中率主要由映射方式决定

平均访问时间

=命中率*Cache访问时间+非命中率*主存访问时间（默认包含了访问Cache不命中的时间）

主存与Cache之间的地址映射有硬件直接完成，映射方式如下：

直接相联映像：硬件电路简单，冲突率很高，cache内分块，主存中分区，区内分块，cache内的块只与主存中块号相同的块相联。
全相联映像：冲突率低，cache内分块，主存中分块，cache内的块可以和主存中任意块相联。
组相联映像：前两者折中，cache内分组，组内分页，主存中分区，区内分组，组内分页，cache内的页只与主存中与其组号相同的组内任意页相连，组间使用直接相联，组内使用全相联。

替换算法

LRU（Least Recently Used）
LFU（Least Frequently Used）
FIFO（First-In, First-Out）
Random Replacement
MRU（Most Recently Used）
ARC（Adaptive Replacement Cache）
2Q
Clock Algorithm

主存编址计算

存储单元：一般是8bit，每个存储单元都有一个地址
存储单元个数：最大地址-最小地址+1
按字编址：这个和系统位数有关
按字节编址：8bit一个存储单元
总容量：存储单元个数*编址内容
总片数：总容量/每片容量

磁盘调度

概述

磁盘中有多个盘面，盘面两面都可存储信息，使用磁头从盘面读取信息；每个盘面可分成多个扇区，每个盘面可分成多个圆形磁道；在不同盘面上的相同位置的扇区成为柱面；读信息时由多个磁头同时读，就会读取同一柱面信息；为什么要有扇区，扇区将磁道分块？应该是读块信息，传输块信息，处理块信息...

调度操作

移臂调度：寻找柱面（磁道），按照调度算法调度
旋转调度：寻找扇区，按照单向循环寻找

调度算法

先来先服务，FCFS
最短寻道时间优先，SSTF，可能产生“饥饿”现象
扫描算法，SCAN，双向扫描，又称“电梯算法”
循环扫描，CSCAN，单向扫描

时间

寻道时间：移动到磁道时长，移臂调度
旋转延迟时间：移动到扇区时长，旋转调度
数据传输时间：读扇区时长

磁盘阵列技术

RAID-0

是一种不具备容错能力的磁盘阵列，由N个磁盘组成的0级阵列，数据均匀存储在N各磁盘中。其平均故障间隔时间(MTBF)是单个磁盘的1/N，数据传输率是单个磁盘的N倍。

RAID-1

将数据完全一致地分别写到工作磁盘和镜像磁盘，它的磁盘空间利用率为50%。

RAID-2

纠错海明码磁盘阵列，其设计思想是利用海明码实现数据校验冗余并存在校验磁盘中。磁盘数量取决于所设定的数据存储宽度，可由用户设定。数据宽度为4的RAID2 ，它需要4块数据磁盘和3块校验磁盘。如果是64位数据宽度，则需要64块数据磁盘和7块校验磁盘。2^(n-1)>=数据宽度。

RAID-3

使用专用校验盘的并行访问阵列，它采用一个专用的磁盘作为校验盘，其余磁盘作为数据盘，数据按位可字节的方式交叉存储到各个数据盘中。至少需要三块磁盘，不同磁盘上同一带区的数据作 XOR 校验，校验值写入校验盘中。

RAID-4

RAID-4 与 RAID-3 的原理大致相同，区别在于条带化的方式不同，也是采用一个专用的磁盘作为校验盘。

RAID-5

原理与 RAID-4 相似，是RAID-4 的改进，对区别在于校验数据分布在阵列中的所有磁盘上。至少需要3个磁盘。N+1方案，N份数据+1份校验。当盘容量不同以最小容量为准。

RAID-6

前面所述的各个 RAID 等级都只能保护因单个磁盘失效而造成的数据丢失。如果两个磁盘同时发生故障，数据将无法恢复。 RAID-6 引入双重校验的概念，它可以保护阵列中同时出现两个磁盘失效时，阵列仍能够继续工作，不会发生数据丢失。 RAID-6 等级是在 RAID-5 的基础上为了进一步增强数据保护而设计的一种 RAID 方式，它可以看作是一种扩展的 RAID-5 等级。至少需要 4 个磁盘。

输入/输出技术

数据传输控制方式

程序控制（查询）方式：CPU主动查询外设是否完成数据传输，影响CPU效率
程序中断方式：CPU无需等待，数据传输完成后进行中断，CPU响应中断。中断请求信号，保存现场，断点，中断向量表
- 中断响应时间：从发出中断请求到进入中断程序间的时长
- 中段处理时间：中断开始处理到中断处理结束的时长
DMA：直接内存访问，CPU处理初始化后将总线控制权交给DMAC，DMAC进行高速、批量的数据交换，DMAC完成后将总线交给CPU。CPU完成一个总线周期后才会响应DMA请求

编址方式

内存与接口地址独立编址方法：指令也不同，用于接口的指令太少，功能太弱
内存与接口地址统一编址方法：用于内存的指令也可用于接口

总线结构

通信类型

分时双工（半双工）：在同一时刻仅允许一个设备发送，同时允许多个设备接收
单工：只能是一个方向上传输信息
全双工：任意时刻都可双向通信，一般为一条线发，一条线收

加密技术和认证技术

加密技术

对称加密

数据加密标准，DES，56位
三重DES，112位
RC-5
国际数据加密算法，IDEA，128位
高级加密标准，AES
Kerberos，鉴定身份的协议
- 秘钥分发中心，KDC：AS（认证服务器），TGS（票据授予服务器）
- 访问流程：客户端想KDC请求所要访问目标服务器的服务访问票据；客户端拿着票据访问目标服务器。

非对称加密