《第一章》 计算机组成与解构

计算机系统基础知识

计算机基本硬件系统由

* 运算器
* 控制器
    以上集成在一起，统称为CPU (Central Processing Unit), 完成算数、逻辑运算和控制功能。
* 存储器
    分为内部存储器和外部存储器。 内部存储器速度高，容量小。 外部存储器速度慢，容量大。
* 输入系统
* 输出系统
    统称外部设备。 输入原始数据和指令，输出运行结果。

CPU的功能

* 程序控制
* 操作控制
* 时间控制
* 数据处理
* 中断处理

运算器由 算术逻辑单元ALU，累加寄存器AC，数据缓冲寄存器DR，状态寄存器PSW 组成
    运算器：由算术逻辑单元ALU（实现对数据的算术和逻辑运算）、 累加寄存器AC(运算结果或源操作数的存放区）、
        数据缓冲寄存器DR(暂时存放内存的指令或数据）、和状态条件寄存器PSW（保存指令运行结果的条件码内容，如溢出标志等）组成。
    执行所有的算术运算，如加减乘除等；执行所有的逻辑运算并进行逻辑测试，如与、或、非、比较等。
控制器由 指令寄存器IR，程序计数器PC，地址寄存器， 指令译码器ID 组合
    控制器：由指令寄存器IR（暂存CPU执行指令）、程序计数器PC（存放指令执行地址）、
    地址寄存器AR(保存当前CPU所访问的内存地址）、指令译码器ID（分析指令操作码）等组成。
        控制整个CPU的工作，最为重要。
CPU根据 指令周期的不同阶段 分别去取指令或者数据来区分指令和数据。

一条指令的执行步骤:
    取指: PC (程序计数器) -> AR (地址寄存器) -> M存储器 -> DR数据寄存器 -> IR指令寄存器
    分析: OP -> ID -> CU控制器
    执行: Ad -> AR (地址寄存器) -M存储器 -> DR数据寄存器 -> AC累加器

数据的表示

进制转换

* R进制转十进制   从低位到高位依次乘以R的n次方(从0递增)，求和
    > 1011011 转 10进制 => 1*10^0^+1*10^1^+0*10^2^+1*10^3^+1*10^4^+0*10^5^+1*10^6^
* 十进制转R进制   数据除R的余数倒排，直到商为0.
    > 456 转 7进制 =》 
    > 456/7 = 65 ... 1
    > 65/7  = 9 ... 2
    > 9/7   = 1 ... 2
    > 1/7   = 0 ... 1
    > 转换结果 = 1221 从下往上排序余数

数的表示

* 数值在机器中的表示形式为机器数，二进制。
* 分为 有符号数和无符号数
    - 无符号数表示正数， 没有符号位。
    - 有符号数最高位为符号位， 0为正数， 1为负数。    

算数运算、逻辑运算

* 算术运算包括 加减乘除
* 逻辑运算包括 
    - 逻辑与 一个为0结果就为0
    - 逻辑或 一个为1结果就为1
    - 异或 相同为0 不同为1
    - 逻辑非 取反
    - 逻辑左移右移

检验码

* 奇偶校验码
    - 奇校验码  检查数据1的个数 如果奇数就前面加0， 偶数就前面加1， 使得1的个数保持奇数
    - 偶校验码  同上相反
* 循环冗余校验码 **重要**
    > 预先约定一个多项式，最高位和最低位必须为1 如 原始信息： 10110 多项式 fn=x^4+x^1+1
    > 多项式最高阶为4， 则原始数据后面补上 4个 0 为： 10110 0000
    > 有多项式的指数存在为1，不存在为0， 得到 10011
    > 10110 0000 / 10011 -> 余数 1111，  如果余数不足4(阶数) 则前面补0 如 0011
    > 将原始信息+余数 发送： 10110 1111
* 海明校验码 **重要**
    > 原始数据 1011，  校验位处于 1,2,4,8,16,32位置上
    > 1 0 1 x 1 x x  原始数据位置 3,5,6,7位置上
    > x x x m x m m  校验位在 1,2,4位置上
    > 7位置上的拆解为 7=2^2+2^1+2^0,  6=2^2+2^1, 5=2^2+2^0, 3=2^1+2^0        
    > 即 7位置需要 2,1,0, 6位置需要 2,1 5位置需要2,0 3位置需要1,0 校验位
    > 同理 2校验位可校验 7,6,5三个原始数据位， 1校验位可校验 7,6,3三个原始数据位 0校验位可校验 7,5,3 三个原始数据位
    >  校验位的值等于可校验的原始数据异或结果

计算机的体系结构

按处理机

* 单处理系统 一个处理单元
* 并行处理系统 两个以上的处理机互联
* 分布式处理系统 远距离的多计算机系统

按指令流和数据流

* 单指令流单数据流SISD  1个控制器 1个处理器 1个存储器    
* 单指令流多数据流SIMD  1个控制器 多个处理器 多个存储器
* 多指令流单数据流MISD  多个控制器 1个处理器 多个存储器  不现实
* 多指令流多数据流MIMD  多个控制器 多个处理器 多个存储器

指令系统

计算机指令

* 计算机指令有操作码和操作数组成
* 指令执行分为 取指令，分析指令，执行指令
* 寻址方式
    - 顺序寻址  一条指令接着一条指令地顺序执行
    - 跳跃寻址  下一条指令的地址码不是由程序计数器给出，而是由本条指令直接给出
    - 指令操作数寻址
        * 立即寻址  指令的地址码字段指出的不是地址，而是操作数本身
        * 直接寻址  指令的地址字段中直接指出操作数在主存中的地址
        * 间接寻址  指令地址码字段所指向的存储单元中存储的是操作数的地址
    - 寄存器寻址
    - 基址寻址
    - 变址寻址
    - 寻对寻址

指令系统 重要

* 复杂指令系统 CISC
    - 指令数量多，使用频率大，可变长指令
    - 支持多种寻址方式
    - 微程序控制
    - 研制周期长
* 精简指令系统 RISC        
    - 指令数量少， 使用频率接近， 定长指令， 单周期指令
    - 支持寻址方式少
    - 增加通用寄存器，硬布线逻辑控制， 使用流水线
    - 优化编译，支持高级语言

RISC中的流水线技术：
（1)超流水线（Super Pipe Line)技术。它通过细化流水、增加级数和提高主频，使得在每个机器周期内能完成一个甚至两个浮点操作。其实质是以时间换取空间。
（2)超标量（Super Scalar)技术。它通过内装多条流水线来同时执行多个处理，其时钟频率虽然与一般流水接近，却有更小的CPI.其实质是以空间换取时间。
（3) 超长指令字（Very Long Instruction Word,VLIW)技术。VLIW和超标量都是20世纪80年代出现的概念，其共同点是要同时执行多条指令，
    其不同在于超标量依靠硬件来实现并行处理的调度，VLIW 则充分发挥软件的作用而使硬件简化，性能提高。

流水线时间计算 重要

* 流水线周期： 指令分成不同的执行阶段， 执行时间最长的段为 流水线周期
* 流水线执行时间： 1条指令的执行时间 + (总指令条数-1)*流水线周期
* 流水线的吞吐率： 单位时间内执行的指令条数， = 指令条数/流水线执行时间
* 流水线的加速比： 使用流水线后比不适用流水线快了多少倍。 = 不使用流水线时间/使用流水线时间

某计算机系统采用5级流水线结构， 每条指令分 取指令2t， 分析指令1t， 去操作数3t， 运算1t， 写回结果2t，分别用5个部件完成。

流水线周期： 5个阶段的执行时间最长的 3t
流水线执行时间： (2t+1t+3t+1t+2t)+(n-1)*3t
流水线吞吐率： n/(2t+1t+3t+1t+2t)+(n-1)*3t ~~~ n无限大时候  1/3t
10条指令的时候， 流水线加速比 = (2t+1t+3t+1t+2t)*10/(2t+1t+3t+1t+2t)+(10-1)*3t = 5/2

单缓冲区、双缓冲区

* 有三个阶段 读入缓冲区， 送入用户去， 处理数据
    > 单缓冲区中： 缓冲区和用户区都只有一个，一块数据必须读入+送出才算完成。 因此单缓冲区中这两个阶段合并， 处理数据独立 
    > 结果是 单缓冲区最终为 读取送出 + 处理数据 两个阶段

    > 双缓冲区中： 由于两个缓冲区读入可以交替进行，但是用户区只有一个， 不能合并， 再加上数据处理， 最终为 读入缓冲区 + 送入用户区 + 处理数据 三个阶段

假设计算机输入、输出采用双缓冲区工作，磁盘块与缓冲区大小相等。 每个磁盘块读入10ms， 缓冲区送入用户区6ms， 数据处理用时2ms。 
如果想要将10块磁盘块大小的文档从磁盘读入给用户处理
采用单缓冲区时， 读入数据送出到用户可以看做一个阶段16ms， 数据处理一个阶段2ms
即流水线执行时间 (16ms+2ms)*(10-1)*16ms = 162ms

采用双缓冲区时，读入数据10ms 送出到用户6ms 不能合并 数据处理单独2ms
即流水线执行时间 (10ms+6ms+2ms)+(10-1)*10ms = 108ms

存储系统

计算机存储解构

计算机采用分级存储体系的主要目的是为了解决存储容量、成本和速度之间的矛盾问题。
局部性原理：总的来说，在CPU运行时，所访问的数据会趋向于一个较小的局部空间地址内，包括下面两个方面：
> 时间局部性原理：如果一个数据项正在被访问，那么在近期它很可能会被再次访问，即在相邻的时间里会访问同一个数据项。
> 空间局部性原理：在最近的将来会用到的数据的地址和现在正在访问的数据地址很可能是相近的，即相邻的空间地址会被连续访问。

* cpu内部寄存器 -》 高速缓存cache -》 主存储器DRAM -》 联机磁盘 -》 脱机存盘、光盘

Cache

地址映射：在CPU工作时，送出的是主存单元的地址，而应从Cache存储器中读／写信息。这就需要将主存地址转换为Cache存储器地址，
    这种地址的转换称为地址映像，由硬件自动完成映射
> 直接映像：将Cache存储器等分成块，主存也等分成块并编号。主存中的块与Cache中的块的对应关系是固定的，
    也即二者块号相同才能命中。地址变换简单，但不灵活，容易造成资源浪费。
> 全相联映像：同样都等分成块并编号。主存中任意一块主存块号都与Cache中任意一块对应。因此可以随意调入Cache任意位置，
    但地址变换复杂，速度较慢。因为主存可以随意调主存块号入Cache任意块，只有当Cache满了才会发生块冲突，是最不容易发生块冲突的映像方式（考点）。
> 组组相连映像：前面两种方式的结合，将Cache存储器先分块再分组，主存也同样先分块再分组，组间采用直接映像，即主存中组号与Cache中组号相同的组才能命中，
    但是组内全相联映像，也即组号相同的两个组内的所有块可以任意调换    

Cache替换算法（cache满了就要替换）

替换算法的目标就是使Cache 获得尽可能高的命中率。常用算法有如下几种：
（a)随机替换算法：就是用随机数发生器产生一个要替换的块号，将该块替换出去。
（b)先进先出算法：就是将最先进入Cache的信息块替换出去。
（c)近期最少使用算法：这种方法是将近期最少使用的Cache中的信息块替换出去。
（d)优化替换算法：这种方法必须先执行一次程序，统计Cache的替换情况。有了这样的先验信息，在第二次执行该程序时便可以用最有效的方式来替换。

地址编号从80000H到BFFFFH且按字节编址的内存容量为（）KB,若用16K*4bit的存储器芯片构成该内存，共需（）片
A.128 B.256 C.512 D.1024
A.8 B.16 C.32 D.64
内存容量=BFFFFH-80000H+1=C0000H-80000H=4*16^4=4*2^16bit = 4*2^6KB = 2^8KB = 256KB
单片存储器 16K*4bit=8K*8bit=8KB   256/8=32片

若用256K×8bit的存储器芯片，构成地址40000000H到400FFFFFH且按字节编址的内存区域，则需（）片芯片。
A.4 B.8 C.16 D.32
内存容量= 400FFFFFH-40000000H+1=40100000H-40000000H=1*16^5H=2^20B
单片=256K*8bit=2^8*2^10*2^3bit=2^18B  
需要使用： 2^20B/2^18B = 4片

内存按字节编址从B3000H到DABFFH的区域，其存储容量为（）。
A.123KB B.159KB C.163KB D.194KB
内存容量=DABFFH-B3000H+1=DAC00H-B3000H=27C00H=2*16^4+7*16^3+C*16^2=162816=159KB

内存按字节编址，从A1000H到B13FFH的区域的存储容量为（1）KB。
A.32 B.34 C.65 D.67
内存容量=B13FFH+1-A1000H=B1400H-A1000H=10400H=16^4+4*16^2=2^16+2^2*2^8=2^16+2^10bit/2^10=2^6+1=65KB

若某计算机字长为32位，内存容量为2GB，按字编址，则可寻址范围为（4）。
A.1024M B.1GB C.512M D.2GB
字长32bit/字8bit=4
可寻址范围=2GB/4=512Mb
内存容量2GB=2*1024*1024*1024*8位，按字编址时，存储单元的个数为2*1024*1024*1024*8/32=512*1024*1024,即可寻址范围为512MB。

存储系统-磁盘

* 磁盘
    - 磁盘有两个盘面， 每个盘面有多个同心圆（磁道）， 每个磁道划分多个扇区
    - 磁盘存取时间 = 寻道时间 + 等待时间(转动延迟)
* 磁盘调度
    - 先来先服务 FIFS    按照进程要求顺序读取
    - 最短寻道时间优先 SSTF     每次访问与当前磁道最近的磁道
    - 扫描算法 SCAN     先寻找最近的磁道， 然后同方向读取完毕， 再回头反方向读取
    - 单向扫描算法 CSCAN   永远只单向移动

磁盘调度先进行移臂调度， 再进行旋转调度。  假设磁盘移动臂目前在21号柱面。
有一下调度请求
柱面    磁头    扇区
17      8       9
23      6       3
23      9       6
32      10      5
17      8       4
32      3       10
17      7       9
23      10      4
38      10      8
采用最短移臂调度算法请求顺序
当前在21号柱面， 移动最近柱面 17号， 然后移动到 23号柱面， 然后 32号柱面， 然后 38号柱面

磁盘上存储数据的排列方式影响I/O效率， 假设一个磁道分为10个扇区， 每个扇区1个逻辑记录，
假设磁盘转速 30ms/周， 磁头当前在 1号数据处， 当使用单缓冲区时， 处理数据时间为 6ms。 
处理所有数据最长时间为：  需要转10圈 30ms*10 = 300ms  加最后一个数据处理时间 6ms  总计 306ms
优化数据存储后最少时间为： 读取第1块数据后，处理6ms，间隔两个数据块正好读 第2块， 依次类推 即每个数据块需要9ms * 10块 = 90ms

    - RAID0 没有提供冗余， 数据分成多个块， 同时写入每个磁盘， 同时读或者同时写 效率为单块磁盘的N倍    
    - RAID1 数据同时写入成对的磁盘互为备份， 提高读取性能 读快写慢    
    - RAID2 数据条块化存储到不同的磁盘， 使用海明码校验    
    - RAID3 使用奇偶校验， 单块磁盘存储校验码    
    - RAID5 至少3块磁盘 数据和校验交叉存储到所有磁盘， 总校验数据量为1块磁盘    

输入输出设备

输入输出设备的编址方式

常见的编址方式有两种：

- I/O端口和存储器分开编址，又被称为I/O映像的方式
    内存地址和接口地址是完全独立的两个地址空间。访问数据时所使用的指令也完全不同，用于接口的指令只用于接口的读／写，
    其余的指令全都是用于内存的。因此，在编程序或读程序时很易使用和辨认。这种编址方法的缺点是用于接口的指令太少、功能太弱。
- I/O端口和存储器统一编址，又称为存储器映像的I/O方式（常见）
    内存地址和接口地址统一在一个公共的地址空间里，即内存单元和接口共用地址空间。优点是原则上用于内存的指令全都可以用于接口，
    这就大大地增强了对接口的操作功能，而且在指令上也不再区分内存或接口指令。该编址方法的缺点就在于整个地址空间被分成两部分，
    其中一部分分配给接口使用，剩余的为内存所用，这经常会导致内存地址不连续。

计算机与外设的数据交换方式

- 查询方式
    CPU主动查询外设是否完成数据传输，效率极低。
- 中断方式
    外设完成数据传输后，向CPU发送中断，等待CPU处理数据，效率对较高
    中断响应时间: 从发出中断请求到开始进入中断处理程序；
    中断处理时间: 从中断处理开始到中断处理结束。
    中断向量提供中断服务程序的入口地址。
    多级中断嵌套，使用堆栈来保护断点和现场
- DMA方式（direct memory access）
    CPU只需完成必要的初始化等操作，数据传输的整个过程由DMA控制器来完成（CPU让出对总线的控制权），在主存和外设之间建立直接的数据通路，效率很高
    在一个总线周期结束后，CPU会响应DMA请求开始读取数据；CPU响应程序中断方式请求是在一条指令执行结束时

总线

总线（Bus),是指计算机设备和设备之间传输信息的公共数据通道
- 内部总线：内部芯片级别的总线，芯片与处理器之间通信的总线。
- 系统总线：是板级总线，用于计算机内各部分之间的连接，具体分为数据总线（并行数据传输位数）、地址总线（系统可管理的内存空间的大小）、控制总线（传送控制命令）。
    代表的有ISA总线、EISA总线、PCI总线。（考试主要考计算机内部的三个总线）
- 外部总线：设备一级的总线，微机和外部设备的总线。代表的有RS232(串行总线）、SCSI(并行总线）、USB(通用串行总线，即插即用，支持热插拔）

- 单工数据传输：一般用在只向一个方向传输数据的场合
- 半双工数据传输：允许数据在两个方向上传输,但是,在某一时刻,只允许数据在一个方向上传输,它实际上是一种切换方向的单工通信
- 全双工数据通信：允许数据在同一时刻同时在两个方向上传输,因此,全双工通信是两个单工通信方式的结合,它要求发送设备和接收设备都有独立的接收和发送能力

系统可靠性

系统可靠性指标

* 平均无故障时间 MTTF = 1/失效率
* 平均故障修复时间  MTTR = 1/修复率
* 平均故障间隔时间  MTBF = MTTF+MTTR
* 系统可用性 = MTTF/(MTTF+MTTR)*100%

- 串联系统，一个设备不可靠，整个系统崩溃，整个系统可靠性R=R1*R2*...*Rn！
- 并联系统，所有设备都不可靠，整个系统才崩溃，整个系统可靠性R=1-(1-R1)＊（1-R2)*...*(1-Rn).