计算机系统概论

计算机的基本组成

硬件部分

早期的计算机由运算器，控制器，存储器，输入设备，输出设备五大部分构成。
alt

软件组成与分类

系统软件
- 操作系统——最重要的系统软件，用于系统的管理与调度
- 语言处理系统——用于支持用户和编程
- 通用程序——例如window下的word等
- 各种服务支持软件——调试程序、诊断程序..
应用软件
- 用户为解决自己问题而编写的程序，计算器，信息管理..

冯·诺依曼计算机原理

冯·诺依曼计算机概念

是一种将程序指令存储器和数据存储器合并在一起的计算机设计概念结构。
alt

工作原理：

将计算机要完成的任务用指令描述,并编成程序。
将程序存放在存储器中
在控制器的控制下,从存储器中逐条取出指令并执行
程序执行的结果即实现了计算机所要完成的任务

冯·诺依曼计算机特点

指令与数据用二进制数字表示
程序存放在存储器中
系统中所有功能部件受控制器的控制
依据存储程序控制原理工作

计算机系统的层次结构

层次结构图

alt

各层的含义和界面定义

alt

计算机体系结构、组成和实现

计算机组成：
从计算机系统的内部来研究计算机的构成，主要内容包括：运算方法、CPU 组成、主存储器和输入输出设备、输入输出接口等。
计算机系统结构：
从外部研究计算机系统。它是使用者（机器语言、汇编语言、系统程序员）所看到的物理计算机的抽象，是编写出能够在机器上正确运行的程序所必须了解到的计算机的属性。
计算机组成的物理实现
集成电路芯片、电子元器件、部件、插头、插座
系统结构决定了计算机的总体属性，组成是体现这些属性的逻辑设计，而实现则是用具体的器件来实现逻辑功能。

计算机的分类和性能描述

Flynn分类法

前提知识：

CU：控制单元 CS：控制流 MM：存储单元 DS：数据流 PU：处理单元 IS：指令流

单指令流单数据流 SISD
单指令流多数据流 SIMD
多指令流单数据流 MISD
多指令流多数据流 MIMD

Amdahl定律和应用

定律内容：
计算机系统中某一部件由于采用某种更快的执行方式后，整个系统性能的提高与这种执行方式的使用频率或占总执行时间的比例有关。
加速比 = $\frac{改进后的系统性能}{改进前的系统性能}$ = $\frac{改进前的系统总执行时间}{改进后的系统总执行时间}$
可改进比例:f_e—-程序的总执行时间为100s，可改进的部分是其中的20s，则f_e＝0.2.可见，f_e总是小于或等1的。
部件加速比r_e—-例如，某部件改进后，执行时间由原来的20s减少到5s，则部件加速比r_e＝$\frac{20}{5}$＝4。可见，r_e一般是大于1的。

Amdahl公式：
若假设改进前的系统总执行时间为T₀，可以得出改进后的系统总执行时间T_n

若加速比用S_p表示，则加速比S_p可表示为：

计算机系统中的数据表示

数制与编码

进位计数制和相互转化

二进制：逢二进一
八进制：逢八进一
十进制：逢十进一
十六进制：逢F进一（16进制中，A表示十进制11，B表示十进制12..）

真值与机器数

各种数值数据在计算机中表示的形式称为机器数，采用二进制表示。机器数对应的实际数值称为数的真值。

BCD码

在计算机中，用4位二进制编码来表示二进制数据。4位编码有16种形式，从中选出10种来表示0~9十个数字。

有权码

十进制数	8421码	5421码	2421码	5211码	4311码
1	0001	0001	001	0001	0001

无权码
余三码： 8421码 + 3（0011）

字符与字符串

ASCII码：7位编码高3位是列编码，低四位是行编码，一共表示128个字符

汉字编码

定点数据表示

无符号数的表示与有符号数的表示

无符号数表示正数，在机器数中没有符号位；
有符号数用数字化的“0”表示“正”，“1”表示“负”，符号放在有效数字的最前面。

原码、反码、补码、移码

原码：
- 真值与原码之间的转换：
  真值转原码，符号位+/-转0/1，数值位照写；
  原码转真值，符号位0/1转+/-，数值位照写。
反码：
- 反码与原码之间的转换：
  真值X>=0,[X]_原=[X]_反
  真值X<0，原码->反码，符号位不变，反码数值部分是原码每位取反
补码：
- 补码与反码之间的转换：
  若真值X>=0,[X]_原=[X]_反=[X]_补
  真值X<0，反码->补码，符号位不变，补码数值部分是反码+1
移码：补码符号位取反
浮点数据表示

格式定义

F = M R^E (类比科学计数法： -2000 = -2 10³)
一般有两种形式：
| 阶符 | 阶码数值部分 | 数符 | 尾数数值部分 |
|-|-|-|-|

数符	阶符	阶码数值部分	尾数数值部分

规格化

当基值R = 2时，规格化浮点数的尾数绝对值应该在$\frac{1}{2}$-1之间

IEEE-754标准

单精度浮点数：
| 数符（1位）| 阶码=阶符+阶码数值（1+7 =8位） | 尾数数值部分（23位） |
|-|-|-|
|0/1|移码|原码|

纠错与校验

奇偶校验码

水平奇校验：当X内有奇数个1时，校验位C=0，接收方校验结果为1时，无错。
水平偶校验：当X内有偶数个1时，校验位C=0，接收方校验结果为0时，无错。
垂直奇偶校验
水平垂直奇偶校验：先垂直后水平

汉明码

网站

循环冗余校验(CRC)

CRC码是一种具有很强的检错和一定纠错能力的数据校验编码。常用于数据通信以及外部存储器的数据校验。
过程：
有已知有效信息X（n个数据位），一个构成多项式G(X)（k+1）位

将有效信息X左移K位，移空处填0，得到一个n+k位数据——M(X)
用M(X)除以G(X)得到一个k位余数，与M(X)相加得到CRC码
校验过程：CRC码除以G(X)，余数为0，没有出错

运算方法和运算器

原码的加减运算

[X+Y]_原 = [X]_原+[Y]_原
[X-Y]_原 = [X]_原-[Y]_原

补码的加减运算

运算定义

补码相加： [X+Y]_补 = [X]_补+[Y]_补
补码相减：减数连同符号位一起求补（取反+1）后，与被减数相加
[X-Y]_补 = [X]_补+[-Y]_补 = [X]_补+[[Y]_补]_求补
溢出：只有同符号相加/异符号相减才可能溢出

溢出判定

双符号位判断：用11表示负，用00表示正，一旦溢出，双符号位一定不一致
进位判决法：若Cn-1为最高数值位向符号位的进位，Cn表示符号位向更高位的进位，则判别溢出的逻辑表示式为：OF＝Cn-1⊕Cn
根据符号位和进位标志辨别：OF＝SF⊕CF——适用于同号相加或异号求差（SF符号位，CF进位标志）
设X_S,Y_S,Z_S分别是两个操作数和结果的符号位，则：OF = $X_SY_S\overline{Z_S}+\overline{X_S}\overline{Y_S}Z_S$

行波进位加法器、先行进位加法器

行波进位加法器
先行进位加法器

乘除运算

原码乘法，补码乘法

原码一位乘
原码两位乘
操作表：
计算过程：
补码一位乘
- 布斯法：
- 操作表：
- 计算过程：
补码二位乘
- 操作表：
- 计算过程：

阵列乘法

补码除法

阵列除法

浮点数

浮点数的加/减运算

对阶
尾数加减
规格化（是否溢出由阶码决定）
溢出处理：
- 上溢：结果记无穷
- 舍入：规格化右移导致会丢掉尾数的末尾，处理方法：①末尾置0 ②末尾置1 ③0舍1入

浮点数的乘法运算

判断是否规范化，若有浮点数为0，结果为0
求阶码：两阶码之和，上溢无法表示，下溢结果为0
两尾数相乘
规格化尾数

浮点数的除法运算

判断是否规范化，若有被除数为0，结果为0，除数不能为0
求阶码：阶码=被除数阶码-除数阶码，上溢无法表示，下溢结果为0
两尾数相除
规格化尾数
舍入处理

算术逻辑单元ALU

存储系统

存储器的分类

按照不同方式进行分类的方法

按存储信息的介质分类：半导存储器、磁带存储器、光盘存储器（半导体、磁性器件、光学器件及材料）
按计算机的用途分类：
- 内存：主存储器（储存正要执行或者刚执行的程序或数据）、高速缓冲存储器Cache;
- 控制存储器： CPU内放微程序
- 外部存储器：U盘..
存放信息的易失(挥发)性：
- 易失：RAM
- 非易失：ROM磁盘
存取方式
- 随机读写：RAM
- 顺序读写：磁带
读写功能：可读可写存储器、只读存储器

存储器容量、速度、可靠性

存储器的性能指标
1. 容量 = 存储字数 字长 = 存储单元数 单元位数
2. 速度：
  - 存取时间(访问时间)：对存储器中某一个单元的数据进行一次存(取)所需要的时间。
  - 存取周期：连续对存储器进行存(取)时，完成一次存(取)所需要的时间。
  - 存储器带宽：单位时间里存储器可以读出(或写入)的字节数。
3. 可靠性：
- 可维修部件的可靠性：平均故障间隔时间（MTBF）
- 不可维修部件的可靠性：平均无故障时间/平均故障前的时间（MTTF）

存储器的结构化层次

alt

半导体随机存取存储器

SRAM存储器的工作原理

alt

DRAM存储器的工作原理

只读存储器

特点：存储信息的非易失性。
脱机写入
主存储器和CPU的连接

字扩展方式

概念：当一个存储器芯片的字容量不够时，采取字扩展发法达到目的。

利用 8K×8bit 的 SRAM，构成 32KB 的内存（32KB = 32K * 8bit）

alt

位扩展方式

概念：当一个存储器芯片的位数不够时，采取位扩展发法达到目的。

利用 2K×8bit 的 SRAM， 2K×16bit 的内存。

alt

双口RAM和多模块存储器

多端口组织形式

双端口存储器读/写操作：
- 允许：
  - 对不同存储单元：
    - 同时读
    - 同时写
  - 对同一存储单元：
    - 同时读
    - 一个端口写，另一端口读
- 不允许：
  - 两个端口同时对同一存储单元写数据

交叉存储方式

并行主存系统：把主存储器分为多个存储体交叉或并行工作，在一个主存周期内能读写多个字。

按内容存储的存储器

相联存储器
原理：按内容访问
把存储单元所存内容的某一部分作为检索项(即关键字项)，去检索该存储器，并将存储器中与该检索项符合的存储单元内容进行读出或写入
用途
- Cache：Cache的目录表
- 虚拟存储器：页表 → 快表(TB)，变换旁视缓冲器(TLB)

高速缓冲存储器

Cache的基本工作原理

原理：将数据所在的主存地址通过映射模块转到Cahe中的地址，有（命中）改地址就读信息，没有（未命中）就从主存中获取，同时替换Cache中的信息。
值得注意的地方：Cache中存储的内容与主存中完全一致，只是为了提高运行速度，才将部分数据复制在Cache中，利用程序执行的局部合理性。

Cache和主存之间的映射方式

全相连方式（最复杂，因为主存块太多，导致相联存储器占用空间很大）
- 将主存与Cache分成大小相同数量不同的块，利用相联存储器，进行映射
- 映射过程：讲主存地址的主存块号与相联存储器地址相联表中主存块号比较，若存在就获取cache块号地址，与主存地址的后半块内地址拼接成cache地址
- 映射过程：
直接映射方式（效率低，适用于大容量Cache）
- 先将主存按Cache大小分区，再与Cache分成大小相同数量不同的块，利用相联存储器，进行映射
- 映射过程：讲主存地址的主存区号与相联存储器地址相联表中主存区号比较，若存在，就按主存地址的后半块号+块内地址组成成cache地址
- 映射过程：
组相连方式
- 在直接映射的基础上，对Cahe进行分组，因此主存的区号中也有分组
- 映射过程：讲主存地址的主存区号+块号与相联存储器地址相联表中主存区号+块号比较，若存在，就按主存地址的后半租号+块号+块内地址组成成cache地址

cache中主存快的替换算法

未命中时，更换cache内数据的算法

随机替换算法 (RAND)
先进先出算法 (FIFO）
最不经常使用算法 (LFU): 难以实现
近期最少使用算法 (LRU)
最佳替换算法 (OPT) (跑两次，看cache需要哪些数据，是最不实用的算法，通常作为衡量算法)

cache写策略
写回法：在替换时将cache写回去
全写法：写入cache的同时写入主存

cache性能分析

cache访问周期 T_c,主存访问周期T_m,cache命中率H
平均访问周期:$T = H T_c + ( 1 -H ) ( T_c + \frac{T_x}{n} )$

虚拟存储器

虚拟存储器的基本概念

虚拟存储器:主存储器＋联机工作的外部存储器＋辅助硬件＋系统软件

把当前要执行的程序或使用的数据驻留在高速主存中,暂时不用部分放在低速外存中;
主存中最近不常用的程序或数据作为替换对象,且修改的数据送回外存;
程序和数据在主存一外存间调入调出由硬件与操作系统共同完成,对用户是透明的;
速度接近高速主存,价格接近低速外存,容量是虚存空间

页式虚拟存储器

虚拟地址空间被划分成许多称作“页”的存储块
主存以同样大小存储块分成若干“页框”(主存页或实页)
页表记录虚存与主存的映射关系(全相联映射)

例： alt

段氏虚拟存储器

了解

优点
- 适合模块化程序设计。将每一功能独立的程序模块定义为一段,既便于程序的开发,又便于虚拟存储器的管理。
- 便于程序和数据的共享。此方式能将整段独立的程序和数据装入主存,起始地址、段长度均已知,易实现共享
- 便于信息保护,对装入段的属性进行设置,易实现对段的保护
缺点
- 由于各段的长度是不一样的,在装入主存中分配地址空间比较麻烦,段与段之间可能会产生比较大的空隙(段间的主存碎片),降低了主存储器的利用率
- 段页式虚拟存储器

结合段、页式的优点

TLB（快表）

页表在主存中，在页式虚存工作时，首先要访问主存中的页表，然后地址变换获得主存地址，再利用主存地址访问主存。即使主存命中，也需要两次访问主存。
为了提高访问速度，借鉴cache的思想，将页表最活跃的部分放在高速存储器中，构成快表，对快表的查询管理用硬件实现，达到快速的目的。
快表一般较小，只是慢表（主存中的页表）中的一小部分。快表中找不到的页才去访问慢表

硬盘存储器

磁记录方式基本原理

原理:当磁头和磁性记录介质间有相对运动时,通过电磁转换完成读/写操作。
编码方法:按某种方案(规律),把一连串的二进制信息变换成存储介质磁层中一个磁化翻转状态的序列并使读/写控制电路能容易、可靠地实现转换。如游程长度受限码( run-length limited code,RLLc)。
磁记录方式:有归零制(RZ)、不归零制NRZ)、调相制(PM)、调频制(FM)和改进调频制(MFM等不同的记录方式对磁表面设备的性能有重要的影响,主要表现在编码效率、自同步能力和可靠性方面。
磁盘的基本参数和计算

公式：

$非格式化容量 = 位密度 内圈磁道周长 每个记录面上的磁道数 *记录面数$
$格式化容量 = 每个扇区字节数 每道扇区数 每个记录面上的磁道数 *记录面数$
$数据传输率 = =每个扇区的字节数 每道扇区数 磁盘转速$
例题1：

例题2：

RAID

不太重要的亚子

指令系统

指令格式

指令的基本格式

为了使指令能够有效地指挥计算机完成各种操作,一条指令应包含两个基本要素:操作码和地址码,其基本格式为:
地址码字段为指令指定源操作数、目的操作数和下条指令地址等信息,格式如下:

定长操作码指令格式

用二进制数字串表示指令

扩展操作码指令格式

扩展操作码
哈夫曼编码
端序
小段存储：低位字节存入低地址，高位字节存入高地址
大端存储：高位字节存入低地址，低位字节存入高地址

alt

指令的寻址方式

有效地址的概念

有效地址$EA$是一个16位无符号数，表示操作数所在单元到段首的距离——即逻辑地址的偏移地址。

数据寻址和指令寻址

常见的寻址方式

隐含寻址：操作数的寻址由操作码决定
立即寻址：操作数在指令中
寄存器寻址：操作数在指令指定的寄存器中
直接寻址:特征:操作数地址在指令中,操作数在主存单元中,访问一次主存便可获得操作数。
(存储器)间接寻址：操作数地址的地址在指令中,操作数在主存单元中
寄存器间接寻址：操作数地址在指令指定的寄存器中,操作数在主存单元中,访问一次主存即可获得操作数。
相对寻址：操作数地址由程序计数器和指令提供的地址偏移量决定,操作数在主存单元中,访问一次主存即可获得操作数。
基址寻址：操作数地址由基址寄存器和指令提供的地址偏移量决定,操作数在主存单元中,访问一次主存即可获得操作数
变址寻址：操作数地址由变址寄存器和指令提供的地址偏移量决定,操作数在主存单元中
堆栈寻址

CISC和RISC的基本概念

RISC的发展历程

RISC的技术特点

中央处理器(CPU)

CPU的功能和基本结构

CPU的功能：执行存储在主存中的指令序列，即执行程序。

CPU的主要构成部件

alt

CPU内的常见寄存器

地址寄存器AR
数据寄存器DR
指令寄存器IR
程序计数器PC
堆栈指示器(堆栈指针寄存器)SP
状态(标志)寄存器——PSW、FR
累加器AC
通用寄存器(寄存器组寄存器文件)R0-Rn-1
CPU内部的数据通路
是一个利用内部专用连线或总线(具有将数据从一个地方移动到另一个地方的能力)将存储部件(寄存器组、Cache)和算术逻辑部件ALU(用于对数据完成各种操作)连接在一起的网络
是指令执行时数据经过的路径与路径上的部件之整体
指令执行过程
CPU执行指令的过程
- 取得指令：CPU从主存中取得指令，并将其暂存在CPU内部的指令寄存器IR中；
- 译码指令：CPU对取得的指令进行译码；
- 执行指令：CPU根据指令译码结果执行指令。
- 确定下条指令执行顺序：除指令顺序被分支跳转类指令改变之外，CPU主要依据指令在主存中的存储顺序执行指令。
CPU执行程序的过程：不断重复执行指令的过程

时序发生器

CPU内部时序概念

典型指令的执行过程

控制器的功能和工作原理

硬布线控制器

速度快
当计算机系统复杂时,设计困难旦实现,不可修改和扩充
常用于RISC处理器控制器的实现
微程序控制器
比硬布线控制器速度慢
设计简单化、规范化
功能可修改、可扩充
实现成本低,出错概率小
常用于CISC处理器控制器的实现
微操作、微命令、微指令、微程序

微操作：处理器（CPU）的基本或原子操作。
- CPU可以实现的、不可分解的操作动作
- 以含有一个寄存器传递（移进、移出）操作为标志

互斥相容原理

可以在同一个时间有效的控制信号称为相容信号，具有相容性；
不能在同一个时间有效的控制信号称为互斥信号，具有互斥性。
互斥的信号放在同一字段
相容的信号放在不同字段

性能分析

CPU时间

alt

CPI

alt
alt

MIPS

CPU每秒钟执行的百万指令数。
alt

流水线技术和指令级并

流水线概念

若将一重复的处理过程分解为若干子过程,每个子过程都可在专用设备构成的流水线功能段上实现,并可与其它子过程同时执行,这种技术称为流水技术

流水线分类

不同方式进行分类

静态多功能流水线

动态多功能流水线

流水线性能指标

alt

吞吐率

吞吐率：单位时间内流水线所完成的任务数或输出结果的数量。
最大吞吐率TPmax：流水线在达到稳定状态后所得到的吞吐率。
假设流水线各段运行时间相等，为1个时钟周期$T_{CLK}$，则：
- $TP{max} = \frac{1}{T{CLK}}$
假设流水线各段运行时间不等，第i 段时间为$τ_i$ ，则
- $TP_{max} = \frac{1}{max[τi]} = \frac{1}{τ}$
实际吞吐率：若流水线由m段组成，完成n个任务的吞吐率称为实际吞吐率，记作TP。
完成n个任务所用时间为
- $Tn(m) = (m＋(n－1))×τ = (m＋(n－1))×T{CLK}$
实际吞吐率为：
- $TP = \frac{n}{Tn(m)} = \frac{TP{max}}{1+\frac{m-1}{n}}$

效率

流水线的设备利用率。
由于流水线有通过（填充）时间和排空时间，还有各种引起断流的状况，所以流水线的各段并非一直满负荷工作，效率E＜1。
从时-空图上看，效率就是n个任务所占的时空区与m个段总的时空区之比。根据这个定义，可以计算流水线各段时间不等时的流水线效率为：
- $E = \frac{n个任务占用的时区}{m个段总的时区}$
效率是实际加速比S与最大加速比m之比。

加速比

若流水线为m段，加速比S定义为等功能的非流水线执行时间T(1) 与流水线执行时间T(m)之比，即
- $S=S_n(m) = \frac{T_n(1)}{T_n(m)}$
若非流水线的情况下，每段运行时间为τ，完成n个任务需要：
- $T_n(1) = nmτ$
在流水但不出现断流的情况下，完成n个任务所需时间为：
- $Tn(m)= mτ + (n-1)τ$
  时空图