(一)计算机系统基础知识
1 计算机硬件组成
计算机的基本硬件系统由运算器、控制器、存储器、输入设备 和 输出设备 5大部件组成。
1 运算器、控制器等部件被集成在一起统称为中央处理单元(CPU) 。CPU是硬件系统的核心，用于数据的加工处理，能完成各种算术、逻辑运算及控制功能。
2 存储器是计算机系统中的记忆设备，分为内部存储器 和 外部存储器。前者速度高、容量小，一般用于临时存放程序、数据及中间结果。而后者容量大、速度慢，可以长期保存程序和数据。
3 输入设备、输出设备合称为外部设备（简称外设），输入设备用于输入原始数据及各种命令，而输出设备则用于输出计算机运行的结果。
2 中央处理单元
2-1CPU的功能
(1）程序控制: CPU通过执行指令来控制程序的执行顺序，这是CPU的重要功能。
(2）操作控制: 一条指令功能的实现需要若干操作信号配合来完成，CPU产生每条指令的操作信号并将操作信号送往对应的部件，控制相应的部件按指令的功能要求进行操作。
(3）时间控制: CPU对各种操作进行时间上的控制，即指令执行过程中操作信号的出现时间、持续时间及出现的时间顺序都需要进行严格控制。
(4）数据处理: CPU通过对数据进行算术运算及逻辑运算等方式进行加工处理，数据加工处理的结果被人们所利用。所以，对数据的加工处理也是CPU最根本的任务。
此外，CPU还需要对系统内部和外部的中断（异常）做出响应，进行相应的处理。
2-1CPU的组成
CPU主要由运算器、控制器、寄存器组 和 内部总线 等部件组成
运算器:由算术逻辑单元ALU（实现对数据的算术和逻辑运算）、累加寄存器AC（运算结果或源操作数的存放区)、数据缓冲寄存器DR（暂时存放内存的指令或数据)、和状态条件寄存器PSW（保存指令运行结果的条件码内容，如溢出标志等）组成。
执行所有的算术运算，如加减乘除等;
执行所有的逻辑运算并进行逻辑测试，如与、或、非、比较等。
控制器:由指令寄存器R（暂存CPU执行指令）、程序计数器PC（存放指令执行地址)、地址寄存器AR（保存当前CPU所访问的内存地址)、指令译码器ID(分析指令操作码）等组成。
CPU依据指令周期的不同阶段来区分二进制的指令和数据，因为在指令周期的不同阶段，指令会命令CPU分别去取指令或者数据。
3 数据表示
3-1 进制的表示
二进制、十六进制，一般在题目中会给出中文说明，如果没给出，(注意二进制符号为0b，一般表示为0b0011，十六进制符号为0x或H，可表示为0x18F或18FH)
3-2进制的转化
R进制整数转十进制 : 位权展开法，用R进制数的每一位乘以R的n次方，n是变量,从R进制数的整数最低位开始,依次为0,1,2,3…累加
十进制转R进制 : 除余法,十进制整数（除以R倒取余数），用十进制整数除以R，记录每次所得余数，若商不为0，则继续除以R，直至商为0，而后将所有余数从下至上记录，排列成从左至右顺序，即为转换后的R进制数
m进制转n进制:中转十进制法,法先将m进制转化为十进制数，再将十进制数转化为n进制数，中间需要通过十进制中转,但下面两种进制间可以直接转化
二进制转八进制:每3位二进制数转换为1位八进制数，二进制数位个数不是三的倍数，则在前面补0
二进制转十六进制:每4位二进制数转换为1位十六进制数，二进制数位个数不是四的倍数，则在前面补0
3-3 机器数 定点表示 和 真值
◆机器数:各种数值在计算机中表示的形式，其特点是使用二进制计数制，数的符号用0和1表示，小数点则隐含，不占位置。
机器数有无符号数和带符号数之分。无符号数表示正数，没有符号位。带符号数最高位为符号位，正数符号位为0，负数符号位为1。
◆定点表示分为纯小数和纯整数两种，其中小数点不占存储位，而是按照以下约定:
纯小数:约定小数点的位置在机器数的最高数值位之前。
纯整数:约定小数点的位置在机器数的最低数值位之后。
◆真值:机器数对应的实际数值。
3-4 码制(以-45为例)
原码:一个数的正常二进制表示，最高位表示符号，数值o的源码有两种形式:+0 (0 0000000）和-0 (1 0000000)。-45对应原码为(1 0101101)
反码:正数的反码即原码;负数的反码是在原码的基础上，除符号位外，其他各位按位取反。数值0的反码也有两种形式:+0 (0 0000000），-0 (1 1111111）。-45对应反码为(1 1010010)
补码:正数的补码即原码;负数的补码是在原码的基础上，除符号位外，其他各位按位取反，而后末位+1，若有进位则产生进位。因此数值0的补码只有一种形式+0= -0=0 0000000。-45对应补码为(1 1010011)
移码:用作浮点运算的阶码，无论正数负数，都是将该原码的补码的首位（符号位)取反得到移码。-45对应移码为(0 1010011)
3-5 码制对应的取值范围
3-6 浮点数表示 与 浮点数运算
浮点数表示:
表示方法为N=F*2^E
E称为阶码
F称为尾数
二进制表示如101.001=0.101001*2^3.
在浮点数的表示中，阶码为带符号的纯整数，尾数为带符号的纯小数，要注意符号占最高位（正数0 负数1），其表示格式如下:
很明显，与科学计数法类似，一个浮点数的表示方法不是唯一的
浮点数所能表示的 数值范围 由 阶码 确定的
浮点数所能表示的 数值精度 由 尾数 确定的
尾数的表示采用规格化方法，也即带符号尾数的补码必须为1.0xxxx(负数)或者0.1xxxx（正数），其中x可为0或1.
浮点数运算:
1 对阶（使两个数的阶码相同，小阶向大阶看齐，较小阶码增加几位，尾数就右移几位)
2 尾数计算（相加，若是减运算，则加负数)
3 结果规格化 (即尾数表示规格化，带符号尾数转换为1.0xxxx或0.1xxxx)
4校验码
码距:就单个编码A:00而言，其码距为1，因为其只需要改变一位就变成另一个编码。在两个编码中，从A码到B码转换所需要改变的位数称为码距，如A:00要转换为B:11，码距为2。一般来说，码距越大，越利于纠错和检错。
4-1 校验码分类
● 奇偶校验码:在编码中增加1位校验位来使编码中1的个数为奇数（奇校验)或者偶数（偶校验），从而使码距变为2。
奇校验:编码中，含有奇数个1，发送给接收方，接收方收到后，会计算收到的编码有多少个1，如果是奇数个，则无误，是偶数个，则有误。这里是引用偶校验同理，只是编码中有偶数个1，由上述，奇偶校验只能检1位错，并且无法纠错。
● CRC循环冗余校验码: 只能检错，不能纠错。使用CRC编码，需要先约定一个生成多项式G(x)。生成多项式的最高位和最低位必须是1。假设原始信息有m位，则对应多项式M(x)。生成校验码思想就是在原始信息位后追加若干校验位，使得追加的信息能被G(x)整除。接收方接收到带校验位的信息，然后用G(x)整除。余数为0，则没有错误;反之则发生错误。
● 海明码:本质也是利用奇偶性来检错和纠错的检验方法，构成方法是在数据位之间的确定位置上插入k个校验位，通过扩大码距实现检错和纠错。设数据位是n位，校验位是k位，则n和k必须满足以下关系:2^k-1>=n+k。
例:求信息1011的海明码
校验位的位数和具体的数据位的位数之间的关系 所有位都编号，从最低位编号，从1开始递增，校验位处于2的n (n=012.….次方中，即处于第1,2,4,8,16,32，…位上，其余位才能填充真正的数据位，若信息数据为1011，则可知，第1,2,4位为校验位，第3,5,6,7位为数据位，用来从低位开始存放1011,得出信息位和校验位分布如下:
| 位数 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|---|---|---|---|
| 信息位 | b4 | b3 | b2 | b1 | |||
| 校验位 | r2 | r1 | r0 |
(二)计算机体系结构
1体系结构分类
| 体系结构类型 | 结构 | 关键特性 | 代表 |
|---|---|---|---|
| 单指令流单数据流SISD | 控制部分:一个 处理器:一个 主存模块:一个 | 单处理器系统 | |
| 单指令流多数据流SIMD | 控制部分:一个 处理器:多个 主存模块:多个 | 各处理器以异步形式执行同一条指令 | 并行处理机 |
| 多指令流单数据流MlSD | 控制部分:多个 处理器:一个 主存模块:多个 | 此类计算机不可能的 | 目前没有此类计算机 |
| 多指令流多数据流MIMD | 控制部分:多个 处理器:多个 主存模块:多个 | 作业、任务、指令各级全面并行 | 多处理机系统 多计算机 |
按处理机的数量进行分类
单处理系统（一个处理单元和其他设备集成)
并行处理系统（两个以上的处理机互联）
分布式处理系统（物理上远距离且松耦合的多计算机系统）
按Flynn分类:分类有两个因素，即指令流和数据流
指令流由控制部分处理，每一个控制部分处理一条指令流，多指令流就有多个控制部分;
数据流由处理器来处理，每一个处理器处理一条数据流，多数据流就有多个处理器;
至于主存模块，是用来存储的，存储指令流或者数据流，因此，无论是多指令流还是多数据流，都需要多个主存模块来存储，对于主存模块，指令和数据都一样。
按计算机特性是由指令来控制数据的传输，因此，一条指令可以控制一条或多条数据流，但一条数据流不能被多条指令控制，否则会出错，就如同上级命令太多还互相冲突，不知道该执行哪个，因此多指令单数据MISD不可能。
2指令系统
2-1 计算机指令的组成 :
一条指令由操作码和操作数两部分组成，操作码决定要完成的操作，操作数指参加运算的数据及其所在的单元地址。
在计算机中，操作码和操作数地址都由二进制数码表示，分别称作操作码和地址码，整条指令以二进制编码的形式存放在存储器中。
2-2 计算机指令执行过程:
取指令 ―> 分析指令 ―> 执行指令三个步骤，首先将程序计数器PC中的指令地址取出，送入地址总线，CPU依据指令地址去内存中取出指令内容存入指令寄存器IR;而后由指令译码器进行分析，分析指令操作码;最后执行指令，取出指令执行所需的源操作数。
2-3 指令寻址方式:
顺序寻址方式:当执行一段程序时，是一条指令接着一条指令地顺序执行。
跳跃寻址方式:指下一条指令的地址码不是由程序计数器给出，而是由本条指令直接给出。
程序跳跃后，按新的指令地址开始顺序执行。因此，程序计数器的内容也必须相应改变，以便及时跟踪新的指令地址。
2-4 指令操作数的寻址方式:
立即寻址方式 : 指令的地址码字段指出的不是地址，而是操作数本身。直接寻址方式:在指令的地址字段中直接指出操作数在主存中的地址。
间接寻址方式 : 指令地址码字段所指向的存储单元中存储的是操作数的地址。寄存器寻址方式:指令中的地址码是寄存器的编号。
基址寻址方式 : 将基址寄存器的内容加上指令中的形式地址而形成操作数的有效地址，其优点是可以扩大寻址能力。
变址寻址方式 : 变址寻址方式计算有效地址的方法与基址寻址方式很相似，它是将变址寄存器的内容加上指令中的形式地址而形成操作数的有效地址。
CISC是复杂指令系统，兼容性强，指令繁多、长度可变，由微程序实现;
RISC是精简指令系统，指令少，使用频率接近，主要依靠硬件实现（通用寄存器、硬布线逻辑控制)。
区别:
| 指令系统类型 | 指令 | 寻址方式 | 实现方式 | 其它 |
|---|---|---|---|---|
| CISC 复杂指令系统 | 数量多,使用频率差别大,可变长格式 | 支持多种 | 微程序控制技术(微码) | 研制周期长 |
| RISC 精简指令系统 | 数量少，使用频率接近,定长格式,大部分为单周期指令,操作寄存器，只有Load/Store操作内存 | 支持方式少 | 增加了通用寄存器;硬布线逻辑控制为主;适合采用流水线 | 优化编译,有效支持高级语言 |
2-5 流水线技术
指令流水线原理: 将指令分成不同段，每段由不同的部分去处理，因此可以产生叠加的效果，所有的部件去处理指令的不同段
RISC中的流水线技术:
(1) 超流水线技术。它通过细化流水、增加级数和提高主频，使得在每个机器周期内能完成一个甚至两个浮点操作。其实质是以时间换取空间。
(2) 超标量技术。它通过内装多条流水线来同时执行多个处理，其时钟频率虽然与一般流水接近，却有更小的CPI。其实质是以空间换取时间。
(3) 超长指令字技术(VLIW) 。VLIW和超标量都是20世纪80年代出现的概念，其共同点是要同时执行多条指令，其不同在于超标量依靠硬件来实现并行处理的调度，VLIW则充分发挥软件的作用，而使硬件简化，性能提高。
流水线时间计算:
流水线周期: 指令分成不同执行段，其中执行时间最长的段为流水线周期。
流水线执行时间: 1条指令总执行时间+（总指令条数-1）*流水线周期。
流水线吞吐率计算: 吞吐率即单位时间内执行的指令条数。
公式: 指令条数/流水线执行时间。
流水线的加速比计算: 加速比即使用流水线后的效率提升度，即比不使用流水线快了多少倍，越高表明流水线效率越高，
公式: 不使用流水线执行时间/使用流水线执行时间。
3存储系统
3-1 分级存储体系目的
计算机采用分级存储体系的主要目的是为了解决存储容量、成本和速度之间的矛盾问题。
3-2 两级存储:
Cache-主存
主存-辅存（虚拟存储体系）
3-3 局部性原理:
总的来说，在CPU运行时，所访问的数据会趋向于一个较小的局部空间地址内，包括下面两个方面:
时间局部性原理:如果一个数据项正在被访问，那么在近期它很可能会被再次访问，即在相邻的时间里会访问同一个数据项。
空间局部性原理:在最近的将来会用到的数据的地址和现在正在访问的数据地址很可能是相近的，即相邻的空间地址会被连续访问。
●高速缓存Cache用来存储当前最活跃的程序和数据，直接与CPU交互，位于CPU和主存之间，容量小，速度为内存的5-10倍，由半导体材料构成。其内容是主存内存的副本拷贝，对于程序员来说是透明的。
●Cache由控制部分和存储器组成，存储器存储数据，控制部分判断CPU要访问的数据是否在cache中，在则命中，不在则依据一定的算法从主存中替换。
●地址映射:在CPU工作时，送出的是主存单元的地址，而应从Cache存储器中读/写信息。这就需要将主存地址转换为Cache存储器地址，这种地址的转换称为地址映像，由硬件自动完成映射，分为下列三种方法:
1直接映像
2全相联映像
3组组相连映像
1直接映像:将Cache存储器等分成块，主存也等分成块并编号。主存中的块与Cache中的块的对应关系是固定的，也即二者块号相同才能命中。地址变换简单但不灵活，容易造成资源浪费。
2全相联映像:同样都等分成块并编号。主存中任意一块都与Cache中任意一块对应。因此可以随意调入Cache任意位置，但地址变换复杂，速度较慢。因为主存可以随意调入Cache任意块，只有当cache满了才会发生块冲突，是最不容易发生块冲突的映像方式。
3组组相连映像:前面两种方式的结合，将cache存储器先分块再分组，主存也同样先分块再分组，组间采用直接映像，即主存中组号与Cache中组号相同的组才能命中，但是组内全相联映像，也即组号相同的两个组内的所有块可以任意调换。
替换算法的目标就是使Cache获得尽可能高的命中率。常用算法有如下几种:
(1）随机替换算法。就是用随机数发生器产生一个要替换的块号，将该块替换出去。 (2）先进先出算法。就是将最先进入Cache的信息块替换出去。
(3）近期最少使用算法。这种方法是将近期最少使用的Cache中的信息块替换出去。
(4）优化替换算法。这种方法必须先执行一次程序，统计Cache的替换情况。有了这样的先验信息，在第二次执行该程序时便可以用最有效的方式来替换。
命中率及平均时间
Cache有一个命中率的概念，即当CPU所访问的数据在Cache中时，命中，直接从Cache中读取数据，设读取一次Cache时间为1ns，若CPU访问的数据不在Cache中，则需要从内存中读取，设读取一次内存的时间为1000ns，若在cPU多次读取数据过程中，有90%命中Cache，则CPU读取一次的平均时间为(90%*1+10%*1000)ns
3-4 磁盘存储
◆磁盘结构和参数
磁盘有正反两个盘面，每个盘面有多个同心圆，每个同心圆是一个磁道，每个同心圆又被划分为多个扇区，数据就被存放在一个个扇区中。
磁头首先要寻找到对应的磁道，然后等待磁盘进行周期旋转，旋转到指定的扇区，才能读取到对应的数据，因此，会产生寻道时间和等待时间。公式为:存取时间=寻道时间+等待时间（平均定位时间+转动延迟)。
注意:
寻道时间是指磁头移动到磁道所需的时间;
等待时间为等待读写的扇区转到磁头下方所用的时间。
◆磁盘调度算法
磁盘数据的读取时间分为寻道时间+旋转时间，也即先找到对应的磁道，而后再旋转到对应的扇区才能读取数据，其中寻道时间耗时最长，需要重点调度，有如下调度算法:
先来先服务FCFS:根据进程请求访问磁盘的先后顺序进行调度。
最短寻道时间优先SSTF:请求访问的磁道与当前磁道最近的进程优先调度，使得每次的寻道时间最短。会产生“饥饿”现象，即远处进程可能永远无法访问。
扫描算法SCAN:又称“电梯算法”，磁头在磁盘上双向移动，其会选择离磁头当前所在磁道最近的请求访问的磁道，并且与磁头移动方向一致，磁头永远都是从里向外或者从外向里一直移动完才掉头，与电梯类似。
单向扫描调度算法CSCAN:与SCAN不同的是，其只做单向移动，即只能从里向外或者从外向里。
4输入输出技术
4-1 内存与接口地址的编址方法，常见的是下面两种:
(1)内存与接口地址独立编址方法
内存地址和接口地址是完全独立的两个地址空间。访问数据时所使用的指令也完全不同，用于接口的指令只用于接口的读/写，其余的指令全都是用于内存的。因此，在编程序或读程序时很易使用和辨认。这种编址方法的缺点是用于接口的指令太少、功能太弱。
(2)内存与接口地址统一编址方法
内存地址和接口地址统一在一个公共的地址空间里，即内存单元和接口共用地址空间。优点是原则上用于内存的指令全都可以用于接口，这就大大地增强了对接口的操作功能，而且在指令上也不再区分内存或接口指令。该编址方法的缺点就在于整个地址空间被分成两部分，其中一部分分配给接口使用，剩余的为内存所用，这经常会导致内存地址不连续。
4-2 计算机和外设间的数据交互方式:
程序控制（查询）方式:CPU主动查询外设是否完成数据传输，效率极低。
程序中断方式:外设完成数据传输后，向CPU发送中断，等待CPU处理数据，效率相对较高。中断响应时间指的是从发出中断请求到开始进入中断处理程序;中断处理时间指的是从中断处理开始到中断处理结束。中断向量提供中断服务程序的入口地址。多级中断嵌套，使用堆栈来保护断点和现场。
DMA方式(直接主存存取):CPU只需完成必要的初始化等操作，数据传输的整个过程都由DMA控制器来完成，在主存和外设之间建立直接的数据通路，效率很高。
在一个总线周期结束后，CPU会响应DMA请求开始读取数据;CPU响应程序中断方式请求是在一条指令执行结束时。
5总线结构
总线（Bus），是指计算机设备和设备之间传输信息的公共数据通道。总线是连接计算机硬件系统内多种设备的通信线路，它的一个重要特征是由总线上的所有设备共享，因此可以将计算机系统内的多种设备连接到总线上。
从广义上讲，任何连接两个以上电子元器件的导线都可以称为总线，通常分为以下三类:
内部总线:内部芯片级别的总线，芯片与处理器之间通信的总线。
系统总线:是板级总线，用于计算机内各部分之间的连接，具体分为数据总线(并行数据传输位数）、地址总线（系统可管理的内存空间的大小）、控制总线（传送控制命令)。代表的有ISA总线、EISA总线、PCI总线。
外部总线:设备级的总线，微机和外部设备的总线。代表的有RS232(串行总线)、SCsI(并行总线)、uSB（通用串行总线，即插即用，支持热插拔〉。
(三)可靠性
可靠性指标
平均无故障时间MTTF=1/失效率。平均故障修复时间MTTR=1/修复率。平均故障间隔时间MTBF=MTTF+MTTR。系统可用性=MTTF/(MTTF+MTTR)*100%。
串并联系统可靠性
无论什么系统，都是由多个设备组成的，协同工作，而这多个设备的组合方式可以是串联、并联，也可以是混合模式，假设每个设备的可靠性为R1，R2.….….Rn，则不同的系统的可靠性公式如下:
串联系统 一个设备不可靠，整个系统崩溃，整个系统可靠性R=R1*R2*…*Rn
并联系统 所有设备都不可靠，整个系统才崩溃，整个系统可靠性R=1-(1-R1)*(1-R2)*…*(1-Rn)。
N模冗余系统:N模冗余系统由N个(N=2n+1）相同的子系统和一个表决器组成，表决器把N个子系统中占多数相同结果的输出作为输出系统的输出。在N个子系统中，只要有n+1个或n＋1个以上子系统能正常工作，系统就能正常工作，输出正确的结果。
