第一章：引言

计算

什么是计算？

计算（Calculation）是将“单一或多个输入值”变换为“单一或多个结果”的过程。

关键特征：

输入数据：数字、文本、声音……
算法或规则
数据处理：数学运算、逻辑操作、数据转换……
输出结果

计算机中的计算任务：数学计算科学模拟数据分析图像处理

计算机

基本概念

什么是计算机？

“计算机”指的是“现代计算机”,全称为“通用电子数字计算机(General Purpose Electronic Digital Computer)”。世界上第一台通用电子数字计算机是 1946 年在美国宾夕法尼亚大学研制成功的 ENIAC(Electronic Numerical Integrator and Calculator,电子数字积分器和计算器)。

核心特征

通用设备：

区别于专用设备：加法器、乘法器等
加、减、乘、除、排序等样样精通
阿兰·图灵1936年“论可计算数及其在判定问题中的应用”
- 所有计算机都可以做相同计算，只是在计算速度上有差别
- 新的计算形式，只需安装合适的软件，无需新计算机

电子设备：

区别于机械设备：手摇机械计算机
“电子”，计算机硬件实现的物理基础
计算最终是通过电子电路中的电流、电位等实现的

数字设备：

区别于模拟设备：通过测量物理量（距离或电压）计算
“数字”是其基本特征，也是计算机通用性的重要基础
所有信息都是采用数字化的形式表示

理论模型

计算机理论模型：图灵机

图灵：

图灵机：

1937年，《论可计算数及其在判定问题中的应用》，

有限状态自动机/图灵机，冯·诺依曼根据其设计出历史上第一台电子计算机
描述和分析计算与计算问题的本质
模拟任何计算设备
对计算机科学和理论计算机科学产生深远影响
计算机编程语言和算法设计的理论基础

图灵机可以解决一切可计算问题

图灵机模型：

思想模型，对应一个抽象的机器
无限长的纸带（Tape），由一个个小方格（Cell）组成,包含有限符号集（0/1/其他字符）
一个可在纸带上左右移动的机器/读写头（Head）
一组状态（State）:机器内部状态，确定下一动作
转移函数（Transition Function）：定义了在给定状态和读取头上的符号情况下，图灵机应采取什么行动（操作）：写入新符号、移动读写头（左或右），并切换到新状态

运行过程：

从初始状态开始，读写头位于纸带上的某个位置。
根据当前状态和读写头所在的单元格上的符号，图灵机通过转移函数来确定下一步的动作：读取当前符号、写入新符号、移动头的位置，并切换到新状态。
图灵机根据转移函数执行相应的操作，然后进入新的状态。
步骤2和步骤3重复进行，直到图灵机进入一个特定的**停机状态（Halt State）**或者永远不停机。

状态转移函数：

程序表，五元组

<q,b,a,m,q’>

q——当前状态
b——当前方格原符号
a——修改后符号
m——机器头移动方向（R/L/N）
q’——下一状态

发展历史

计算机系统

计算机系统组成

存储程序控制原理

现代计算机构建思想：“存储程序控制原理”

美籍匈牙利科学家冯·诺依曼提出

CPU的工作

“指挥信息的处理”，从存储器/内存（memory）里读取下一条指令；
“执行信息的实际处理”，执行该指令，即进行加法、乘法等计算工作；
这两项工作循环进行，即读取指令，执行指令……

程序/指令

指令（instruction），计算机执行的一件明确定义的工作
计算机程序（program），由一组指令组成，指令是计算机程序中规定的可执行的最小的工作单位

hello程序的执行

计算系统

抽象层级

问题

自然语言描述
不能直接作为计算机的指令
- “歧义性”,如羽毛球拍卖完了
计算机是电子设备，只能机械执行明确的指令
如“Add A, B” ，将两个数A和B相加

算法

将自然语言描述的问题转换成一个无歧义的操作步骤，即算法（Algorithm）
特征：
- “有限性”（Finiteness）：程序最终能够结束。
- “确定性”（Definiteness）：每个步骤都必须是明确的，不应存在歧义性。例如，“A与一个数相加”就是“不确定”的，因为不知道A与哪一个数相加。
- “有效可计算性”（Effective Computability）：每个步骤都能被计算机执行， “A除以0”就缺乏可计算性。

程序

使用程序设计语言把算法转换为程序 C/C++、Java、Python、Golang等
程序设计语言与自然语言不同，它是用于表达计算机指令的语言，不存在歧义性

指令集结构

高级语言程序翻译成机器语言的依据
目标机器的指令集结构（Instruction Set Architecture，ISA）
是程序和底层计算机硬件之间的接口（Interface）的完整定义
计算机能够执行的指令集，即计算机能够执行的操作和每一步操作所需的数据
- 1979年，Intel公司设计的IA-32指令集结构
- 1986年发布的MIPS指令集结构
- PowerPC（IBM和Motorola），Alpha（COPMPAQ）， PA-RISC（HP），SPARC（SUN和HAL）以及最新的 IA-64(Intel)等
- ARM指令集，由Berkeley RISC演变而来
  - 低功耗，且能满足性能
  - ARM公司自己不制造芯片，只将芯片的设计方案授权（licensing）给其他公司，由他们来生产软硬件接口

微处理器

IA-32指令集结构
- 1985年Intel实现的80386微处理器
- 之后的80486、80586微处理器 1998年推出的Pentium（奔腾）微处理器
MIPS指令集结构
- Cisco、Nintendo、Sony和SGI等公司生产，实现了不同的微处理器，
- 用于Sony、Nintendo的游戏机，Cisco的路由器

逻辑电路

组成微处理器的每一个组件的逻辑电路也有很多选择，因为设计者也需要考虑如何尽量平衡成本和性能
例如，对于组成微处理器的加法器的实现，选择超前进位逻辑电路，比选择行波进位电路，计算速度更高

元件

每一种基本的逻辑电路都由特定的物理元件实现
- CMOS（Complementary Metal Oxide Semiconductor，互补金属氧化物半导体）逻辑电路采用金属氧化物半导体晶体管制造
- 双极型逻辑电路则采用双极型晶体管构成

第六章：数据的机器级表示

前导

数据和信息

计算机的信息存储

在计算机中，所有信息都是采用数字化形式存储和表示的

字节&比特

1字节（byte）=8比特（bit）

比特又叫位(bit)(b)

字节(Byte)(B)

字长

计算机CPU一次能并行处理的二进制位数被称为计算机的字长（word length）

每一个元素被称为一个字(word)

字长w位

最大$2^w-1$

进位制

一种计数方式
使用有限种数字符号来表示所有的数值
可以使用的数字符号的数目n成为基数或底数

二进制

二进制是计算机编码存储和操作信息的核心

十六进制

解决二进制占位多，容易出错，方便人们处理二进制数

数据类型

基本概念

定义数据的性质和操作规则

大端法和小端法

两种不同的字节序 (Byte Order) 表示方式，用于确定在多字节数据存储时哪个字节位于起始地址
影响的不同计算系统的数据交换和通信
大端法 (Big Endian，BE)
- 最高有效字节位于最低的内存地址
- 最低有效字节位于最高的内存地址
- PowerPC、SPARC、Motorola 68k等处理器架构
小端法 (Little Endian，LE)
- 最低有效字节(LSB)位于最低的内存地址
- 最高有效字节(MSB)位于最高的内存地址
- x86、ARM、MIPS等常见的体系结构

字符型

ASCII码

美国信息交换标准码

8个二进制位

Printable Ascii Chart

整型

无符号整数：

字长位k，可表示从0到$2^k-1$共$2^k$个整数

正数：

原码、反码、补码三码合一

负数：

原码：机器数，最高位为符号位正数0，负数1

反码：正数原码各位”按位取反“

补码：正数原码取反（反码）加1

二进制补码转十进制：

一个8位的二进制补码数采取如下格式：
a7 a6 a5 a4 a3 a2 a1 a0
1. 检查最前面的a7 0
  - 如果是0, 该整数是正数，可直接计算其数值
  - 如果是1 该整数是负数，权重位为－1
2. 计算：
  a6 x2 6+ a5 x2 5+ a4x2 4+ a3 x2 3+ a2 x2 2+ a1 x2 1 + a0x2 0
3. 如果是负数，需要再加(-1) a7x27

十进制转二进制：

十进制数N通过以下步骤可得其k位补码表示

将N 的绝对值“ 除2取余” 得到二进制表示；
若为正十进制数，则在二进制数前加0，得到K位结果；
若为负十进制数，计算负数的补码
- 正数的原码按位取反加1
- 负数的反码加1

恰当的位数：

为减少占用空间，会采用恰当的位数来表示数值

符号扩展：

如果用0来扩展一个正数的左端，它的值不会改变
如果用1来扩展一个负数的左端，其值亦不会改变
在这两种情况中扩展的都是符号位，这种运算被称为符号扩展（Sign-EXTension , SEXT )
用于对不同长度的数值之间的运算

溢出

溢出的判断方法：

两个数的符号相同，和的符号不同->溢出

一个负数和一个正数的和永远不会出现溢出

浮点型

十进制，小数点，定点表示法( fixed po in t )

定点小数算术运算：

没有新的运算一补码整数算术运算
小数点对齐

十进制数转换成二进制数
• ( 1) 整数部分，采用除2取余法（倒除法）先除出来是低位
• ( 2) 小数部分，采用乘2取整法先乘出来是高位

IEEE浮点数

I EEE （国际电气和电子工程师协会）浮点数算术运算标准

两种主要的浮点数格式：单精度(32位）和双精度(64位）

C语言中的数据类型

char , ASC I I 码
int，二进制补码整数类型
f I oat ，单精度浮点数
doubIe，双精度浮点数
每种类型采用多少位二进制来表示，与具体计算机的指令集结构和编译器有关

第七章：数字逻辑电路

二进制逻辑运算

逻辑运算概念

位组合

计算机要解决一个真正的问题，必须能唯一的识别出许多不同的数值，而不仅仅是0和1
唯一的识别多个数值，必须对多个位进行组合
如果用8位（对应8根线路上的电压）
- 0100 1110，1110 0111……
- 最多能区分出256（即$2^8$）个不同的值
如果有k位，最多能区分出$2^k$个不同的值
- 每一种组合都是一个编码，对应着某个特定的值

英国数学家乔治·布尔在1854年给出了二进制的逻辑运算，布尔代数即由此得名

逻辑运算又称布尔运算，用数学方法研究逻辑问题，等式表示判断，推理表示等式的变换
- 布尔代数：变换的有效性依赖于符号的组合规律
- 20世纪30年代，逻辑运算在电路系统上获得应用
- 复杂电子计算机系统遵从布尔代数的变换规律
逻辑表达式：用逻辑运算符将关系表达式或逻辑量连接起来的有意义的式子
- 运算结果是一个逻辑值，即“true”或“false”
- C语言编译系统逻辑运算结果对应二进制的1和0

基本运算符

三种典型的运算符，分别表示与、或、非函数：
- “与(AND)”运算符使用符号“•”表示
- A•B，即A AND B，当且仅当二者取值都为1时，结果才为1
- “或(OR)”运算符使用符号“+”表示
- A+B，即A OR B，当其中至少有一个变量取值为1时，结果为1
- “非(NOT)”运算符使用符号“¯”表示
- $\overline{A}$，即NOT A，当A取值为1时，结果为0；当A取值为0时，结果为1
其他两种常用的运算符，分别表示异或、同或函数：
“异或(XOR)”运算符“⨁”表示
* A⨁B，相异为1，相同为0
“同或(XNOR)”运算符“⊙”表示
* A⊙B，相同为1，相异为0

真值表

表示逻辑运算的简便方法
n+1列
前n列对应n个源操作数
最后一列表示每种组合的输出
$2^n$行
每个源操作数0或1，源操作数组合有$2^n$种可能
每组值组合（输入组合）：真值表中的一行

布尔代数的基本公式、定律

按位运算

对两个m位的位组合对应位上的数字按位运算
位组合的编号规则
自右向左，顺序编号，最右边的一位是[0]，最左边是[m-1]
32位组合A
0001 0010 0011 0100 0101 0110 0111 1000
- [31]位是0，[30]位是0，[29]位是0，[28]位是1
- 记为A[31：0]

按位与的应用：位屏蔽/掩码

假设有一个8位的位组合，称为A，最右边的两位有特殊的重要性
- 位屏蔽为00000011

C的按位运算符

C语言的低级语言特征之一
对数值进行位（布尔）运算的运算符集合
“&”：按位“与”运算
“|” ：按位“或”运算
“~” ：按位“非”
“^” ：按位“异或”
“<<” ：执行左移
“>>” ：执行右移

* 第一个操作数是被移位的数值 

* 第二个操作数是移动的位数 

* 有符号数**算术移位**，无符号数**逻辑移位** 

*  算术/逻辑左移，零填充，不考虑符号 

*  逻辑右移，零填充，不考虑符号

*  算术右移，符号扩展

  ![image-20240107192801160](https://img.czruby.eu.org/imgs/计算系统基础期末复习/image-20240107192801160.png)

优先级
1. 非(~)
2. 左移(<<) = 右移(>>)
3. 与(&) > 异或(^) > 或(|)
自左向右

C的逻辑运算符

与位运算不同
所有非零的参数都为True，只有参数0为False
- 位运算只有在特殊的数值条件下才得到0或1
逻辑运算的运算符集合
- “&&” ：“与”（AND）
- “||” ：“或”(OR)
- “！” ：“非”(NOT)

集成电路

采用一定工艺，把一个电路中所需的晶体管、二极管、电阻、电容和电感等元件及布线互连一起
制作在一/几小块半导体（硅）晶片/介质基片上
封装在一个管壳内，使其具有所需电路功能

✓ 小体积 ✓ 低功耗 ✓ 高可靠

摩尔定律

集成电路上的元器件集成度每隔18-24个月便会增加一倍, 成本保持不变
揭示了信息技术进步的速度

晶体管

MOS晶体管

1960年发明
MOSFET（Metal-Oxide-Semiconductor Field Effect Transister，金属氧化物半导体场效应晶体管)
占据半导体市场的极大份额
广泛应用于各种电子器件
数以百亿计的晶体管集成度（摩尔定律）
推动现代电子产业的高密度高集成化发展
原理：依靠输入回路的电场效应来控制输出回路电流的半导体元件
与机械开关不同：用电压控制电路开关
三个端口：源极（S）、栅极（G）、漏极（D）

N型半导体
- 纯硅中掺入5价磷元素
- 原本四价稳定的硅元素多一个电子
- 自由电子带负电，N型半导体
P型半导体
纯硅中掺入3价硼元素
缺少电子，产生空穴
吸引电子，对外显正电，P型半导体

NMOS晶体管

P型半导体打底
两块N型半导体（源极S和漏极D）
中间二氧化硅+金属板，引出栅极G
栅极施加正电压，金属板电场吸引P型半导体中的电子到绝缘层附近，形成全部是电子的N沟道，N型半导体联通，电路闭合

PMOS晶体管

N型半导体打底
两块P型半导体（源极S和漏极D）
中间二氧化硅+金属板，引出栅极G
栅极施加负电压，N型半导体的负电子被排斥，远离绝缘层，空穴被吸引，形成P沟道，P型半导体联通，电路闭合

CMOS电路

NMOS晶体管用于源极接地、栅极施加正电压的 低端驱动，要求漏极接电源正极
PMOS晶体管用于源极接电源正极、栅极施加负电压的高端驱动，要求漏极接地
P型和N型晶体管以互补的方式工作
CMOS（Complementary MOS）电路
既包含PMOS晶体管又包含NMOS晶体管的电路
互补金属氧化物半导体电路

门电路

不管多复杂的芯片都是由不同的逻辑门电路组成
三种基本类型：与门、或门、非门
- 实现与、或、非逻辑运算的晶体管电路
- 在此基础上的与非门、或非门
构建门电路最基本的元器件是MOS晶体管

非门

非门电路图	ANSI/IEEE Std	IEC 60617-12

PMOS（上）和NMOS（下）接在一起
栅极连在一起，作为输入端；
漏极连在一起，作为输出端；
注意
- PMOS管的源极（上）接电源正极；
- NMOS管的源极（下）接地

或门、或非门

或非门电路图	ANSI/IEEE Std	IEC 60617-12

顶部两个PMOS管，串联
底部两个NMOS管，并联
编号从1-4
输入为A、B
A连接1和4的栅极
B连接2和3的栅极
输出为C，连接漏极
PMOS管1的源极接电源正极
NMOS管3、4的源极接地

或门电路图	ANSI/IEEE Std	IEC 60617-12

或门在或非门基础上加一个非门

与门、与非门

电路图（与非门/与门）	ANSI/IEEE Std	IEC 60617-12

有N个输入的与门

– 仅当所有的输入变量都为1时，输出才为1

– 只要有一个输入为0结果就为0
有N个输入的或门

– 只要任意一个输入变量为1输出就为1

– 仅当所有的输入变量都为0时输出才为0

组合逻辑电路

基本介绍

逻辑结构

连接门电路，构建逻辑结构
实现信息的运算和存储
两种基本类型
能够存储信息
不能存储信息

组合逻辑电路

不能存储信息的逻辑结构
“判定元件” 、组合逻辑结构/电路
输出在任何时刻只取决于同一时刻的输入状态
与电路过去的状态无关
输出和输入之间可用逻辑函数来描述
特点：
信息不能存储在组合逻辑电路中（无记忆功能）
输出、输入之间没有反馈延迟通路
应用：主要用于处理信息
译码器，多路选择器，全加法器等
逻辑电路（尽量采用与非门设计）（通用性简单性低功耗高集成度快速响应容易级联）

译码器

译码：将特定含义的二进制码转换成输出信号
- 输入少，输出多
- 编码的逆过程
- 编码：将信号转换成二进制代码，多对少
译码器：具有译码功能的逻辑电路
唯一地址译码器：一系列代码译成对应的有效信号
* 二进制译码器：存储器寻址（地址分配、单元选择）
* 二-十进制译码器：二进制转换为BCD格式(数字显示、计数器)
* 显示译码器：数码显示器（驱动信号可视化显示）
代码变换器：一种代码转换成另一种代码

二进制译码器

有使能端、n个输入，$2^n$个输出
只有一个输出为有效
有效输出对应于要被检测的输入组合
2-4线译码器
- n=2，1个使能端G，2个输入(A、B)，4个输出(Y0-Y3)
- 使用非门产生A和B的反变量$\overline{A}$和$\overline{B}$
- 信号送入4个不同的与非门
- 四种可能的输入组合中，仅有一个输出有效（低/高电平）
- 双2-4线译码器：2个独立的译码器
应用：进行地址分配和单元选择

多路选择器

又叫数据选择器、多路开关
功能：选择多路输入数据中的一路数据连接到输出线路，实现数据选择功能
类比：多个输入的单刀多掷开关
（总线）数据选择切换、多个输入源切换…
由选择信号S决定哪个输入连接到输出
一般由n条选择线和$2^n$个输入组成

全加法器

半加器

实现本位两个二进制数相加的逻辑电路
两个输入Ai和Bi
两个输出Si和Ci，分别表示“和”与“进位”
Si=Ai⨁ Bi=$\overline{A_i}·B_i+A_i·\overline{B_i}$
Ci=Ai ∙Bi

(=1是异或门的符号)

全加器

实现两个本位二进制数与来自低位来的进位相加的逻辑电路
三个输入Ai、Bi、Ci-1
两个输出Si与Ci表示“和” 与“进位”
Si=Ai⨁Bi⨁Ci-1
Ci=(Ai⨁Bi)∙Ci-1+Ai·Bi

数值比较器

可编程逻辑阵列

可编程逻辑阵列（PLA）,它由一组与门(称为与阵列)以及其后的一组或门(称为或阵列)组成。与门的数目对应于真值表中输入组合(行)的数目,对于有 n 个输人的逻辑函数,PLA 将包括2"个与门,每个与门有n个输入。或门的数目对应于真值表中输出的列数。对于真值表的输出列中产生输出1 的行,只需将 PLA 中该与门的输出与或门的输人相连,就可以实现该真值表,因此称之为可编程。也就是说,通过将与门的输出与或门的输入连接进行编程来实现希望实现的逻辑函数。

基本存储元件

双稳态电路：有两个稳定状态，稳定状态的翻转依赖于外加触发信号的作用

存储元件：能存储信息的逻辑结构
基本存储元件：存储1位二进制信息的逻辑结构
锁存器和触发器
- 共同点：都具有存储功能（1位信息），都是时序逻辑电路的基本逻辑单元
- 锁存器：对脉冲电平（0/1）敏感的存储电路
- 状态改变取决于特定的脉冲电平值
- 但当输入信号不稳定，输出会出现毛刺
- 消耗的门资源相对较少
- 触发器：对脉冲边沿（上升/下降沿）敏感的存储电路
- 状态只在时钟上升沿或下降沿到来的瞬间改变
- 不易产生毛刺
- 消耗的门资源相对于锁存器多
时钟脉冲
- 按一定电压幅度，以一定时间间隔连续发出的脉冲信号
- 时钟发生器（石英晶体振荡器）
- 信号值在0伏和某个特殊的固定的电压之间交替
- 时钟周期：重复的时间间隔序列中的一个时间间隔

锁存器

R-S锁存器

静态存储单元中最基本的、电路结构最简单
两个与非门（或者或非门）组成
工作原理：设置R和S来控制电路状态
R：“reset”，复位引脚
S： “set”，置位引脚
两输出a和b（重点看a)
应用：
缓存
数字系统中某些特定标志的设置
消除机械开关触点抖动引起的脉冲输出

S=1， R=1（保持状态）
S=0， R=1（置位/1状态）

a的值原本为0，置为1；原本为1，不变
S=1， R=0（复位/置0状态）

a的值原本为1，置为0；原本为0，不变
R = S = 0 ×

门控D锁存器

输入控制门电路（两个与非门）+ R-S锁存器
两个输入端: D(Data) 和 WE(Write Enable)
控制何时置位、何时复位、何时保持
工作中不存在非定义状态，即保证S、R不同时为0
WE = 1, 输出 = D
* S = NOT(D), R = D
* D=0，S=1，R=0，置0
* D=1，S=0，R=1，置1
WE = 0, 保持
* S = R = 1，输出状态保持不变

将多位数据存储于一个独立单元的结构
使用一组门控D锁存器，WE共享
WE=1, n位D的值被写入寄存器

触发器

主从D触发器

主从触发器，由2个门控D锁存器构成
A为主锁存器，B为从锁存器，使能信号相反
实现存储数据和输入信号之间的隔离

时钟信号为0，WEA=1，WEB=0，A锁存器原样输出数据D的值（门控D锁存器性质），B锁存器保持原来状态的值，输出不变
时钟信号由0变1瞬间（上升沿），WEA=0， WEB=1，A之前锁存的D值保持不变，B锁的输出相应变为A中锁存的D值
时钟信号为1，A锁保持，B锁输出也不变

时序逻辑电路

基本介绍

时序逻辑电路

既能处理信息，也能存储信息
任何时刻的电路输出不仅取决于当前时刻输入，还取决于电路原来的状态
由组合逻辑电路和存储电路组成
- 存储电路必不可少，由锁存器或触发器组成

时序逻辑电路按电路工作方式分为：

同步时序逻辑电路：所有触发器状态的变化都在同一时钟信号下同时发生

异步时序逻辑电路：没有统一时钟信号，触发器状态不是同时发生

同步时序电路一般由触发器组成，应用较广泛
- 寄存器、计数器、序列信号发生器等
异步时序电路可由锁存器或触发器组成
电平异步时序电路：锁存器
脉冲异步时序电路：触发器

按输出信号特点分为：

Mealy型：输出状态与存储电路的状态和外部输入均有关，𝑶 = 𝒉(𝑰, 𝑺)

Moore型：输出状态只与存储电路的状态有关，与外部输入无关，𝑶 = 𝒉(𝑺)

有限状态机

实现被称为有限状态机的机制
- 有限个状态以及状态之间的转移和动作等行为的数学模型
- 一个系统的状态，是在某一特定时刻，系统内所有相关部分的一个瞬态图
- 有限状态机可被用作电子系统、机械系统、航空系统等的控制器，如交通信号灯控制器
寄存器容量是有限的，状态的数目是有限的
有限状态机由5个元素组成：
- 有限数目的状态
- 有限数目的外部输入
- 有限数目的外部输出
- 明确定义的状态转换函数
- 明确定义的外部输出函数
可以用时序逻辑电路来实现

状态图

描述有限状态机的方法之一
- 其他：逻辑函数表达式、状态表等
一组圆：对应状态
一组有向弧线
每一条弧线确定一个状态的转换
箭头表示状态的转换方向
剪头起始状态称为当前状态，指向的状态称为下一状态/次态

时序逻辑电路设计

(交通信号灯控制器的设计)

第8章冯·诺依曼模型

基本结构

简介

冯·诺依曼

美籍匈牙利数学家
理论计算机科学与博弈论的奠基者
在泛函分析、遍历理论几何学、拓扑学和数值分析等众多数学领域及计算机科学、量子力学和经济学等领域都作过重大贡献

冯诺依曼模型

由指令组成的程序和程序所需的数据位于存储器中
指令的执行由运算器处理单元完成
指令执行的顺序由控制单元来控制
输入设备将程序和所需的数据送入计算机
输出设备将执行结果送出计算机之外
处理单元和控制单元是CPU的主要组成部分

存储器（RAM）

地址

和每一个单元联系在一起的唯一标识符
二进制地址
总数：地址空间

寻址能力

存储在每个单元中的位数
大多数的存储器，字节可寻址
- B（byte，字节），表示8位的信息量
- 原始操作数据，键盘上键入的某个字符
  - 对应的ASCII码在存储器中占一个单元
  - 访问一个存储单元即可读写一个字符
64位可寻址
用于科学计算的计算机

地址空间

唯一可识别的单元总数
$2^{32}$ X8 位，有$2^{32}$个不同存储单元的地址空间和8位的寻址能力， 4G 字节（缩写为GB) 的存储器
要确定$2^{32}$个地址，需使用32 位二进制数表示
- $2^{10}$, 1 024, 1 KB
- $2^{20}$, 1 MB
- $2^{30}$ 1 GB
- $2^{32}$ , 4GB, 4294967296（约40亿）

SRAM

SRAM（Static;Random;Access;Memory，静态随机访问存储器）
结构相对简单
“静态”：只要给它供电，其内部数据就不会丢失，可以一直保存
“随机访问”：可以以任意顺序访问，而不必关心前一次访问的是哪一个单元
存储元：可以用更少的晶体管实现

DRAM

DRAM（Dynamic;Random;Access;Memory，动态随机访问存储器）
“动态”：使用电容存储电荷fl存数据
必须隔一段时间刷新（refresh）一次，
如果存储单元没有被刷新，存储的信息就会丢失
关机也会丢失数据
“随机访问”：可以以任意顺序访问，而不必关心前一次访问的是哪一个单元
存储元：采用动态存储单元，最常见的系统内存

SRAM和DRAM区别对比

工作原理：
- SRAM：SRAM是一种基于触发器的存储器，使用稳定的存储电路来存储和保持数据。每个存储单元由一个存储器单元和控制电路组成，其中存储器单元由多个触发器构成，能够存储比特数据。由于采用了触发器结构，SRAM在不断刷新的过程中保持数据的稳定性。
- DRAM：DRAM是一种基于电容的存储器，使用电容来存储和表示数据。每个存储单元由一个电容和一个访问晶体管组成。电容在存储器中充电或放电来表示数据的0和1。由于电容会逐渐漏电，DRAM需要定期刷新以保持数据的正确性。
存储密度：
- SRAM：由于SRAM采用了稳定的存储电路，每个存储单元需要更多的晶体管来实现，因此SRAM的存储密度相对较低。每个存储单元通常需要6个晶体管。
- DRAM：由于DRAM采用了电容存储结构，每个存储单元只需要一个电容和一个访问晶体管，因此DRAM的存储密度较高。每个存储单元通常只需要1个晶体管和1个电容。
刷新需求：
- SRAM：由于SRAM的存储单元采用稳定的触发器结构，不需要进行定期刷新操作。数据可以一直保持稳定，无需周期性刷新。
- DRAM：由于DRAM的电容逐渐漏电，数据需要定期刷新以保持其正确性。DRAM需要通过刷新操作周期性地重新写入数据，否则数据会丢失。
访问速度：
- SRAM：SRAM的访问速度非常快，因为数据存储在触发器中，可以立即读取和写入。SRAM具有较低的访问延迟和高速的读写性能。
- DRAM：DRAM的访问速度相对较慢，因为数据存储在电容中，需要经过访问晶体管的操作。DRAM具有较高的访问延迟和相对较慢的读写性能。

处理单元（ALU）

算术和逻辑单元ALU
- Arithmetic and Logic Unit
- 最简单的处理单元
功能：“执行信息的实际处理”
现代计算机包含许多复杂功能的处理单元，执行一个特定的运算（除法，平方根等）

字

ALU一次正常处理的信息量大小通常被称为计算机的字长(word length)，每一次被处理的元素被称为一个字（word）
取决于计算机的不同用途，每一个指令集结构都拥有自己的字长
Intel的Pentium Ⅳ处理器，32位
Sun的SPARC-V9和Intel的Itanium处理器，64位

寄存器堆/文件Reg

位置：ALU附近
功能：临时存取数据
计算(A+B)×C，先在存储器中存储A+B的结果，随后读取出来，再和C相乘
访问存储器的时间远长于执行加法或乘法的时间
使用临时存储空间Reg存储A+B的结果
典型寄存器的大小等于ALU一次处理数据位数
每个寄存器都包含一个字

控制单元（PC）

功能：“指挥信息的处理”
其具体工作包括：
- 在执行程序的过程中，跟踪存储器中的指令
- 在处理指令的过程中，跟踪指令的处理阶段
控制单元可以是多个控制器，从属于各个部件
ALU控制器用于控制ALU执行何种运算
对于输入和输出则有专门的I/O控制器

程序计数器/指令指针
Program Counter，简称PC
控制单元中容纳下一条指令所在地址的寄存器
功能：跟踪存储器中的指令，确切地说是跟踪要处理的下一条指令

输入/输出设备（I/O）

要使计算机处理信息，信息必须被送入计算机中
为了能够使用处理后的结果，它必须能以某种形式显示在计算机以外
为输入和输出的目的而出现的设备在计算机术语中被称为外围设备（peripherals）
键盘——输入；监视器（显示器）——输出
输入：鼠标，数字扫描仪、磁盘
输出：打印机，磁盘

冯诺依曼模型示例——DLX

DLX方案：一个采用总线结构、多时钟周期的实现方案

数据通路：

寄存器（32位）
- 寄存器堆/文件
- 程序计数器PC
- 指令寄存器IR
多路选择器
- DRMUX提供一个5位的地址给寄存器堆
- AMUX和BMUX分别提供一个32位的数值给ALU
每根用交叉斜线标记32的线表示该线内共有32条线，每条用来传送1位的信息

总线:

两端都有箭头的粗黑线结构代表数据通路的总线（物理线或导线）
优点：功能多、成本低
缺点：性能和带宽对计算机性能有重要影响
DLX的总线由32根线和相关的电子元件组成
在总线上一次只可传输一个值
每一个提供数据给总线的组件在它的输入箭头后都有一个三角形（称为三态设备），使计算机的控制逻辑一次只允许一个提供者能提供信息给总线
从总线获得数据的组件通过将LD.x（加载使能）信号设为1（回忆门控锁存器），从而得到信息

存储器

主存地址寄存器(Memory;Address;Register,MAR)
- 保存数据传输目的位置或者数据来源位置的地址
- 32位，DLX的存储器的地址空间是232个存储单元
主存数据寄存器(Memory;Data;Register,;MDR)
保存要被写入地址单元或者从地址单元读入的数据
32位，DLX字节可寻址，即每个单元包含8位
在大多数情况下，MDR包含从MAR中的地址开始的4个连续单元的数据，有时包含的是MAR所指的单元中的数据（8位）符号扩展的结果（32位)
如果要读出某个存储单元中的内容，首先把它的地址存入地址寄存器（MAR），然后查询存储器，该地址所对应的存储单元的内容将会输出到数据寄存器（MDR）。
如果要写一个值到存储单元中，首先要把目的地址存入MAR，把值存入MDR中，然后设“写使能”信号为1，查询存储器，MDR里的信息就会被写到MAR中的地址所对应的存储单元里。

处理单元

ALU和寄存器堆
ALU可以做加法、减法、乘法、除法、与、或、异或、比较、移位等运算
32个整数寄存器、32个浮点寄存器
DLX子集
未包括整数乘法、除法及浮点数运算等操作
也未包括浮点寄存器

控制单元

所有管理计算机信息处理的组件
最重要是有限状态机，指挥所有行为
有限状态机的一个输入是CLK，它说明了每个时钟周期持续的时间
为了跟踪指令的处理阶段，控制单元还需要一个指令寄存器（Instruction Register，简称IR），用来保存正在处理的指令。IR也是有限状态机的一个输入，因为要处理的DLX指令决定了计算机要执行的行为。
程序计数器（PC）
记录下一条要被执行的指令所在的地址

箭头

实心箭头表示沿着相应通路流动的是数据元素
空心箭头表示控制数据元素处理的控制信号
有限状态机的所有输出都是空心箭头
控制了计算机的处理
LD.IR（1位），控制了当前时钟周期内，指令寄存器（IR）是否要从总线上加载新的指令
GateALU，决定ALUOut的值在当前时钟周期内是否被提供给总线

输入输出设备

由键盘和显示器组成
- 最简单的键盘需要两个寄存器，一个数据寄存器（KBDR），用来保存由键盘键入字符的ASCII码，和一个状态寄存器（KBSR），用来提供键盘键入字符的状态信息
- 最简单的显示器同样需要两个寄存器，一个用来保存那些将被显示在显示器上的内容的ASCII码（DDR），另一个用来提供相关的状态信息（DSR）

第九章：指令集结构

指令集结构ISA

概述

Instruction Set Architecture，ISA
定义计算机能执行的指令集合
计算机硬件和软件之间的接口
处理器（CPU）设计的第一步

ISA

计算机能够执行的指令集合
- 操作码：让计算机执行的操作
- 操作数：每一步操作所需的数据
  - “数据类型”：操作数在计算机中的表示方式
  - “寻址模式”：如何计算操作数在存储器中的地址
存储器
- 地址空间：计算机存储单元的数量（$2^n$）
- 寻址能力：每个存储单元存储信息的能力(m位)
寄存器集
分类：
- CISC
  - Complex Instruction Set Computer
  - 复杂指令集计算机
  - 功能强大的复杂指令
  - 开发程序比较容易
  - 指令执行效率较低
- RISC
- Reduced Instruction Set Computer
- 精简指令集计算机
- 指令集较小
- 开发程序有所欠缺
- 指令执行效率比CISC高

DLX指令操作类型

由指令的[31:26]位定义，64种指令类型
R类型
- 指令的[31:26]位为000000
- [5:0]位定义了函数，有64种可能的函数
只定义了91条指令

DLX指令表

算术/逻辑运算指令

对整数进行处理
37个算术逻辑运算指令：加、减、乘、除、与、或、异或、移位、比较、加载高位立即数等
除加载高位立即数指令（LHI）外，其他运算指令执行的都是二元运算
两个源操作数（即待运算的数据）
- 来自通用寄存器或从指令中直接获得
一个目标操作数（运算执行后的结果）
- 存储于通用寄存器中

第一个源操作数

来自寄存器
- 32个整数寄存器，5位编码标识
- [25:21]，SR1

第二个源操作数

目标操作数

注意在DLX中DR都是在源寄存器后边的，而在汇编中是写在前面的（除了sw/sb）,是从后面把数据保存到前面

I类型指令

第二个源操作数
- 来自于指令[15:0]进行符号扩展得到的32位整数，即立即数
目标操作数
来自于指令[20:16]所标识的寄存器中

ADDI：加
SUBI：减
ANDI：与
ORI：或
XORI：异或
SLEI：设置是否小于等于条件操作（SR<= IMM 1）
SLTI: 设置是否小于条件操作(SR < IMM 1)
SEQI: 设置是否相等条件操(SR = IMM 1)
SRAI: 算术右移立即数操作（Shift Right Arithmetic）(符号扩展，正数补0，负数补1)
SRLI：逻辑右移立即数操作（Shift Right Logical）（直接补0）
SLLI：左移立即数操作（Shift Left Logical）
LHI：加载高位立即数操作，将立即数左移 16位后，加载到目标操作数中

R类型与I类型相似

数据传送指令

存储器和通用寄存器之间：本章
寄存器和输入/输出设备之间：第12章
整数寄存器与特殊寄存器之间：第13章
还包括整数寄存器与浮点数寄存器之间，存储器和输入/输出设备之间传送数据

加载/存储

加载（load）：将数据从存储器移动到寄存器的过程
存储（store）：将数据从寄存器移动到存储器的过程
LB和SB：加载和存储一个8位的字节，在一个存储单元和一个寄存器之间传送数据
LW和SW：加载和存储一个32位的字，在4个连续的存储单元和一个寄存器之间传送数据

I-类型

指令的[25:21]位指明了源操作数SR1
[20:16]位指明了目标操作数DR
加载：DR寄存器将在从存储器读取数据之后，包含该数值（指令完成时）
存储：DR寄存器则包含了要被写到存储器中的数值
如何在32位的指令中声明一个32位的存储单元地址？
“基址寄存器+偏移量”的寻址模式

基址寄存器+偏移量

存储单元的地址：将16位的偏移量进行符号扩展后，与一个基址寄存器相加得到
- 16位的偏移量是从指令中得到的，是[15:0]位
- 偏移量值：在$-2^{15}$到$2^{15}-1$之间的二进制补码整数
- 基址寄存器则使用指令的[25:21]位来说明，即 SR1

LW：将（SR）+IMM开始的4个地址->DR
SW：将DR->（SR）+IMM开始的4个地址
LB：将（SR）+IMM地址的值进行符号扩展->DR
SB：将DR中数值低8位（最低有效字节）->（SR）+IMM

绝对地址
- 如果SR1为R0，由于R0=零，“基址+偏移量”的计算结果就是IR[15:0]经过符号扩展得到的值，该值就是访问存储器的地址
加载指令不可使用R0作为目标寄存器
存储指令使用R0作为DR
表示存储到存储单元的是数值0

边界对齐

LW/SW指令：加载/存储一个32位的字
- “基址+偏移量”的计算结果是4个连续的存储单元的低地址，必须是4的倍数

运算指令和数据传送指令不改变指令执行的顺序

控制器中的程序计数器PC
- 记录下一条要执行的指令的地址
- PC ← PC+4
- 一条指令占用连续的4个存储单元

控制指令

改变被执行的指令的顺序
DLX有10条指令能使顺序流被打破
条件分支
无条件跳转
子例程（有时称为函数）调用
TRAP
从异常/中断返回

条件分支

采用I-类型格式
使用[25:21]位的寄存器，决定是否改变指令流，即是否改变正常执行指令的顺序
BEQZ，等于零时分支（Branch on Equal to Zero）
* 取指令阶段：PC加4；
* 译码/取寄存器阶段：计算（加过4的）PC加 SEXT(IR[15:0])；
* 完成分支阶段：判断[25:21]位的SR1的值是否为0？
- 如果SR1的值为0，PC就被上一阶段得到的地址加载；
- PC ← PC + 4 + SEXT(Imm16)
- 如果SR1的值不为0，那么，直接进入下一取指令阶段，PC保持不变
- PC ← PC + 4
BNEZ，不等于零时分支（Branch on Not Equal to Zero）

地址限制

在加上偏移量之前，PC已经被增加4
计算出来的地址
只能在BEQZ或BNEZ这条指令的PC+4+($2^{15}$-1)或
PC+4-$2^{15}$的单元范围之中

无条件分支

如果[25:21]位全部是0，表明要判断的寄存器是R0
R0=0，PC被计算得到的地址加载
指令流无条件被改变

无条件跳转

JR指令:
- 寄存器跳转（Jump Register）
- I-类型
- [20：0]位未用，设为0
- [25:21]位的寄存器
- 包含下一条将要被执行的指令地址
- PC ← (R3)
J指令
- 跳转（Jump）
- J-类型
- PC ← PC+4+SEXT(PCOffset26)

若执行的下一条指令超出地址限制范围，如何实现？

JR指令

TRAP指令

用于输入和输出
TRAP指令（操作码是110000）
改变PC，使其指向属于操作系统的某部分的存储器地址
作用是为了让操作系统代表正在执行的程序执行一些任务
TRAP调用了一个操作系统的“服务例程”
TRAP指令的[25:0]位为“TRAP向量”，标明程序希望操作系统执行哪一个服务调用

DLX指令处理

数据的存储和排列顺序
大端，Big Endian,高位优先
字的高位字节存放在内存的低地址端
低位字节存放在高地址端
* x4000 0000~x4000 0003的4个存储单元存一个字
* 当访问这个字时，只需使用其起始地址x4000 0000即可
* 这个字是x1234 5678

寄存器-DLX

在一个时钟周期内访问的附加临时存储空间
DLX使用通用寄存器集（GPR）
每一个寄存器中的存储位数通常是32位的字
被唯一识别，同存储器的地址
32个通用寄存器
5位编码来识别
分别被标记为R0、R1……R31
注意，R0寄存器中的数据必须为零

(浮点寄存器)

32个浮点寄存器，用于单精度或双精度计算
- 使用5位编码来识别
- 分别被标记为F0、F1……F31
每个寄存器也是32位存储能力
单精度数只需1个浮点寄存器
双精度数则需要2个浮点寄存器

指令处理使用多时钟周期的实现方案，指令每一步占用一个时钟周期，不同的指令可能被分解为不同的步骤

DLX指令执行阶段

按照DLX指令执行的步骤，将处理指令所需的操作划分为以下阶段：
- 取指令（Instruction fetch）
- 译码/取寄存器（Instruction decode/Register fetc h）
- 执行/有效地址/完成分支(Execution/Effective address/Branch completion)
- 访问内存（Memory access）
- 存储结果（Write-back）
每条DLX指令需要其中的3到5个阶段

DLX的有限状态机

执行执行每一个阶段的每一步都是由控制单元的有限状态机控制的
状态在时钟控制下发生转换
接下来，针对不同的指令，将进入不同的状态，直到该指令执行完毕，下一个状态就是返回到有限状态机的状态1
有限状态机一个时钟周期接一个时钟周期，控制每条指令的执行
既然每条指令的执行都是以返回到状态1结束，有限状态机就可以一个周期接一个周期的，控制整个计算机程序的执行

停止时钟

如果运行锁在状态1（即Q=1），时钟电路的输出和时钟发生器的输出是一样的
如果运行锁在状态0（即Q=0），时钟电路的输出就为0
只需要把运行锁清0，就可以停止指令运行

以下图指令为例

1.取指令阶段

第一个时钟周期（状态1）
- PC中的内容通过总线被加载到MAR中
- 在ALU中执行PC+4的运算
下一个时钟周期（状态2）（如果存储器可以在一个时钟周期里提供信息）
存储器被读取，指令内容011100 00010 00001 0001 0010 0011 0100被加载到MDR
PC+4的结果加载到PC（x4000 0004）
再下一个时钟周期（状态3）
MDR中的值被加载到指令寄存器（IR）

2.译码/取寄存器阶段

下一周期（状态4）
- IR中指令操作码被译码：确定下一步要去做什么
- 取寄存器：为后面阶段获取操作数
- 读取IR[25:21]的内容(即R2)，写到寄存器A中
- 读取IR[20:16]的内容(即R1)，写到寄存器B中
- 在ALU中执行PC+SEXT(IR[15:0])，结果存储于 ALUOut中(可能是无意义的操作，但是同时进行不浪费时间)

3.执行/有效地址/完成分支

下一周期
根据译码产生的控制信号（空心箭头）执行算术或逻辑运算
或计算有效地址
* 有限状态机选择来自寄存器A（即基址寄存器R2）和来自IR[15:0]符号扩展的值
- 将AMUX和BMUX的选择信号A.S和B.S分别设为0和00，
- 将EXT.S设为0（SEXT逻辑将执行IR[15:0]的符号扩展操作）

* 将ALUOp设为0001(4位控制信号），在ALU中进行加法运算，即 计算“基址+偏移量”，形成有效地址
* 将LD.ALU设为1，结果存储于ALUOut寄存器中

或完成分支跳转

4.访问内存

下一周期（或多于一个，如果访问存储器需要多于一个时钟周期的话）
- 获取内存中的数据
- 有限状态机将GateALU和LD.MAR设为1，将ALUOut 中的值通过总线传给MAR；
- 将MEM.EN.R.W设为0（即读存储器模式），LD.MDR设为1，读取存储器的数据，将以该地址开头连续4个单元中的内容加载进MDR。

5.存储结果

最后一个周期
- 结果被写到指定的目标中
- 有限状态机将DR.S设为1，选择IR的目标寄存器（DR），即被加载的寄存器；
- LW指令：
  - 将GateMDR和LD.REG设为1，在时钟周期结束时，MDR中的值被加载到IR[20:16]的DR（R1）中
- ADD指令
- 将GateALU和LD.REG设为1,加法运算的ALUOut寄存器中的结果被写入IR[15:11]所指示的R1中

下一阶段

这五个阶段完成之后，控制单元就会从取指令阶段开始执行下一条指令
由于在取指令阶段PC被更新，包含了存储在存储单元中的下一条指令的地址
下一条指令接下来就会被读取，处理就这样持续下去直到被打断
不是所有的DLX指令都包括上述五个阶段
所有指令均需要取指令阶段和译码/取寄存器阶段
ADD指令，不需要访问内存阶段

I类型和R类型两种指令的对比

第十章：机器语言程序设计

机器语言程序设计

高级语言

与底层计算机指令集无关
“独立于机器”
不能直接被计算机执行
被翻译为目标机器ISA的二进制指令序列

低级语言

与执行程序的计算机指令集紧密相关
汇编语言
依据指令集的汇编语言格式编写，需经过语言处理，翻译为机器语言才能在计算机上执行
机器语言
依据指令集使用二进制编码，直接在计算机上执行，不需要经过语言处理

低级语言的作用

硬件控制：允许程序员直接控制计算机的硬件，如CPU 、内存、寄存器等，高度优化的性能关键应用程序和硬件驱动程序。
系统编程：操作系统、设备驱动程序、嵌入式系统等需要与底层硬件交互的领域，需要对计算机硬件有深刻的理解和控制。
性能优化：允许程序员更好地控制寄存器和内存使用，在某些情况下，使用低级语言可以比使用高级编程语言获得更高的性能。
调试和逆向工程：研究恶意软件、漏洞分析以及系统逆向工程等安全领域，允许深入分析和理解二进制代码的内部工作方式。

结构化程序设计

三种基本结构
- 顺序
- 选择
- 循环

第十一章：汇编语言

汇编语言

目的
- 程序设计的用户友好性比机器语言强
- 精确控制计算机能够执行的指令
便于记忆的符号
操作码，例如ADD和AND
存储单元，例如SUM和LOOP
* 符号地址
* 标记
在汇编语言程序执行之前，必须被翻译成机器语言
- 翻译程序，汇编器
- 翻译过程，汇编

标记和注释可选
不区分大小写
自由格式

标记

标识存储单元
命名
由字母、数字及下划线组成
以字母、下划线或*$*开头
以冒号结尾
指令操作码属于保留字，不能用做标记
例如，NOW:，_21:，R2D:和*$*3PO:

操作码和操作数

操作码：指令操作码的符号名
操作数
寄存器
* R0，R1，…，R31
立即数
* 包含一个表明该数的基的符号
- “#”,十进制
- “x”,十六进制
- “b”,二进制
标记，代表一个数据的地址

算术/逻辑运算指令

操作数数目为3个(LHI指令除外)
I-类型汇编指令格式
OPCODE DR, SR1, Imm16
* 立即数可以使用标记
* 立即数是16位补码整数
R-类型汇编指令格式
OPCODE DR, SR1, SR2
LHI指令格式
LHI DR, Imm16
* 立即数可以使用标记，如 LHI R1, A
- 将地址A的高16位值赋给R1
- 如A代表地址x3000 01A0，R1=x3000 0000

数据传送指令

加载指令汇编格式
LW/LB DR, Imm16(SR1)
存储指令汇编格式
SW/SB Imm16(SR1) , DR
立即数可以使用标记

控制指令

条件分支指令格式
- OPCODE SR1, LABEL
- 标记，条件分支指令的目标地址
J指令格式
- OPCODE LABEL
JR指令格式
OPCODE SR1
TRAP指令格式
- TRAP Imm16

注释

分号后面的部分
- 某行的第一个非空字符
- 一条指令之后
目的：提高可读性，不是重申显而易见的表象
注释为空行
- 程序对齐

伪操作

Directive
- 有助于汇编器实现翻译过程
以“点”作为第一个字符

数据区/代码区

汇编语言程序：指令和数据
数据和指令被加载到存储器中的不同区域
数据区：.data
代码区：.text

数据区

.data address
- 将数据放在数据区的某个地方
- 注意:
- x0000 600A不是4的倍数，不能作为字的起始地址
.align n (边界对齐)
- 将下面的数据或代码加载到以n个0结尾的地址中

数据区的数据

32位的字、8位的字节或字符串
.word、.space、.ascii、.asciiz、.byte
.word word1, word2, …
- 将字1、字2、……存储在连续的存储单元中
.byte byte1, byte2,…
- 将字节1、字节2、……存储在连续的单元之中
.ascii “string1”,“…”
- 将字符串1、字符串2、……存储于存储器中
.asciiz “string1”, “…”
- 在每一个字符串末尾，存储一个字节0

预留空间

.space size
- 在数据区中留出一定数目的连续的存储单元
  - 数目：size个字节
- 操作数的实际值未知

代码区

.text address
- 将指令放在存储器的某个地方
- 指令的起始地址必须是4的倍数
- .align的要求

全局标记

多个文件组成的汇编语言程序

.global label

全局标记
其他文件可以使用
先执行哪一个文件？
从标记为main:的指令开始
main是全局标记
单文件程序
从main:开始执行

汇编过程

汇编器
- 将汇编语言程序，翻译成机器语言程序
- 汇编语言指令和机器语言指令：“一一对应”

两趟扫描

“第一趟”扫描：
- 标识出符号地址（标记）对应的实际的二进制地址
- 建立符号表
- 如：numbers ——— x0000 600C
“第二趟”扫描：
把汇编语言指令翻译成机器语言指令
如：addi r1, r0, numbers

符号表

符号名和存储地址对应的关系
用分配的地址标识标记
使用地址计数器LC（Location Counter）,记录当前处理位置的地址，来辅助第一趟扫描建构符号表，辅助第二趟扫描计算地址偏移量
无法用16位立即数表示，翻译成多条指令，符号表和LC跟随进行相对应变换（第二趟扫描）

多文件程序地址链接问题

汇编器无法实现完全汇编
不报错，标记合法
解决方法
- 链接器
  - 管理“结合”过程的程序
  - 完成翻译
  - 为每个模块重新分配存储空间
  - address可选
  - 伪操作“.text/.data address”
  - address可选
  - “.text”/“.data”
  - 不必给出具体地址

总结

高级语言支持选择结构和循环结构，但是实现这些结构的计算机底层指令都是条件分支指令
变量个数多于寄存器数目时，需要使用存储器
- 编译器应尽量将最常用的变量保存在寄存器中，而将不常用的变量放到存储器中
- 为了实现寄存器和存储器之间的变量交换，需要使用一种被称为“栈”的存储结构，将变量的值存储于存储器之中

寄存器分配规则

在本章的示例中
- 将变量分配给寄存器R16~R23
- 将寄存器R8~R15和R24、R25用于存储临时产生的值

第十二章：输入和输出

概述

输入和输出
- 可以通过执行TRAP指令来完成输入和输出（第9章）
- TRAP指令调用的是操作系统的I/O设备管理例程（第12、13章）
冯·诺依曼模型的重要组成部分
通过总线与CPU、存储器进行通信

I/O控制器

一种电子设备
I/O设备与CPU通信的接口
以键盘控制器为例
状态机
解码器
数据寄存器：保存数据
状态寄存器：保存状态

I/O设备寄存器

最简单的I/O设备通常至少包含
保存在计算机和设备之间进行传输的数据的寄存器
- 键盘数据寄存器中存储的是用户输入的字符的ASCII码
保存设备的状态信息的寄存器
- 例如设备是处于可用的状态还是正忙于执行最近的I/O任务

DLX->KBDR KBSR DDR DSR

键盘设备寄存器

每一个寄存器32位（与DLX的通用寄存器一样），方便
KBDR，[7:0]位用来存放数据，[31:8]位包含x000000
KBSR，[0]位，就绪位

显示器设备寄存器

DDR，[7:0]位用于数据部分，[31:8]中包含x000000
DSR，[0]位，就绪位

内存映射I/O

如何读取I/O设备寄存器中的数据？
如何向I/O设备寄存器加载数据？
两种机制
专门的I/O指令
* Intel x86指令集，in/out
* 通用寄存器 ↔ I/O设备寄存器
数据传送指令
* 通用寄存器 ↔ 存储器
* 内存映射I/O
问题：如何表示I/O设备寄存器？
采用内存映射的方式
每一个I/O设备寄存器都被分配一个存储器地址空间中的地址
这些地址被分配给I/O设备寄存器，而不再是存储单元
地址xFFFF 0000到xFFFF 00FF被分配给I/O设备寄存器，其他地址分配给存储单元
- 每一个寄存器：32位（与通用寄存器一样）

内存映射I/O的DLX数据通路

地址控制逻辑
控制输入/输出操作
输入：MAR，R.W

读KBDR的指令序列：

KBDR: .word xFFFF0004 ; KBDR的起始地址 
……
	   lw r1, KBDR(r0) ; R1= xFFFF 0004 
	   lw r4, 0(r1) ;将KBDR中的数据加载到R4中

写DDR的指令序列

DDR: .word xFFFF000C ; DDR的起始地址 
……
	  lw r1, DDR(r0) ; R1= xFFFF 000C 
	  sw 0(r1) , r4 ;将R4中的数据写到DDR中

异步问题的解决

问题：如果执行这条指令时，用户还没有输入新的字符，会发生什么情况？将KBDR之前存储的数据读入R4中？
- I/O的执行与处理器的执行不同步
  - 微处理器：时钟控制下执行指令
  - 用户键盘输入：不受时钟控制
问题：如果执行该指令时，显示器还没有将上一个DDR中的字符显示完成，会发生什么情况？将DDR之前存储的数据覆盖？
- 处理异步问题
  - 协议/握手机制
  - 键盘，1位的标志
  - 是否输入一个字符
  - 显示器，1位的标志
  - 被送给显示器的字符是否已被显示
  - 设备状态寄存器 [0]位
  - KBSR[0]
  - DSR[0]
KBSR[0]
- 每当用户输入一个字符时，键盘控制器就将就绪位设为1
  - 键盘不能用
- 每当处理器读取该字符时，键盘控制器就将就绪位清空
  - 允许输入下一个字符
DSR[0]
- 每当显示器完成了一个字符的显示，显示器控制器就将DSR[0]设为1
- 每当处理器向DDR写字符时，显示器控制器就将DSR[0]清空

状态位的检查：轮询

周期性的检查状态位，判断是否执行I/O操作的方法
- 最简单的方式
- 由处理器完全控制和执行通信工作
缺点：
- 微处理器的时钟频率：300MHz
- 一个时钟周期：3.3纳秒
- 处理执行一条指令平均需要10个时钟周期
- 执行一条指令33纳秒
- 用户在1秒钟之后输入一个字符
- 重复指令序列10条指令
- 处理器执行指令序列300万次，才能读取到该字符
- 浪费了大量的处理器时间
解决方法：中断

第十三章：自陷例程和中断

自陷例程

如果允许应用程序员（用户程序员）直接访问KBDR和KBSR等来实现I/O的行为
- I/O行为包含了被许多程序所共享的设备寄存器的使用
- 用户程序员没有谨慎处理，给其他用户程序制造混乱
解决方法：特权——自陷（TRAP）指令
- 硬件寄存器是有特权的
- 不拥有适当特权级别的程序不能访问
- 让操作系统来完成
  - 拥有适当的特权级别
  - 用户程序员不需要在这个层面上理解I/O

TRAP机制

服务例程
操作系统的一部分，代表用户程序执行的一组程序
DLX：256个服务例程

TRAP向量表
- 包括了256个服务例程的起始地址的表，每个起始地址需要占用4个连续的存储单元
  - 256个服务例程需要256×4个单元
  - 这张表被存储在存储单元的x0000 0000到x0000 03FF中
- 命名：系统控制块或TRAP向量表
数据区/代码区
- 数据区的起始地址：代码区起始地址之前的x100 个单元
- trap每个服务例程的代码区之间差0x400，trap x00存储在xFFFE 0100，剩下的从x500（0-x3FF是表，x400是第一个的数据区）开始排
Trap机制
- 操作系统代表用户程序执行某一个服务例程，然后把控制权交还给用户程序
  - 根据TRAP向量，PC←相应服务例程首地址
  - 提供返回路径/“链接”
- 流程：
  - 取指令；
    - PC←PC+4
  - 译码；
  - 计算有效地址：
  - TRAP向量（ 26位）扩展到32位，再左移2位（即乘以4）
    * x06→x0000 0018
  - 访问内存
  - MAR← x0000 0018
  - 读取存储器
  - MDR←x0000 2500
  - 写回
  - R31←PC
    * 返回用户程序的“链接”
  - PC←MDR
    * x0000 2500，字符输入服务例程的起始地址
- TRAP服务例程执行结束
  - 在TRAP服务例程的最后执行一条JR R31指令，控制就可以返回到用户程序的正确位置
寄存器的保存与恢复
- 如果一个寄存器内的值在该寄存器被存储了其他值之后再次用到，必须在其他事情发生之前将其保存，在再次使用它之前将其恢复
- 两种形式：
  - 被调用者保存
    - callee-save
    - 由被用户程序调用的服务例程完成寄存器的保存与恢复
    - 被调用程序知道需要使用哪些寄存器，而调用者不知道哪些寄存器的值将被破坏
    - 例子：
  - 调用者保存
    - caller-save
    - 由调用程序完成寄存器的保存与恢复
    - 例子：
  - 区分：
    - 在TRAP执行之前由调用程序处理
    - 由调用程序处理这个问题，被称为caller-save（调用者保存）
    - 或者在TRAP指令执行之后由被调用的程序（例如，服务例程）处理
    - 由被调用的程序处理这个问题，被称为callee-save（被调用者保存）
  - 原则
    - 如果哪个程序知道哪些寄存器将被接下来的操作所破坏，处理保存/恢复问题的就应该是哪一个程序

停机服务例程

中断

本质

IO设备能够：
- （1）强制程序停止
- （2）让处理器执行I/O设备的请求
- （3）让停止的程序继续执行，好像什么都没发生过

机制

1、当I/O设备有输入要处理，或准备接受输出时，允许I/O设备中断处理器的机制
- I/O控制器：
- 生成中断信号INT
2、管理I/O数据传送的机制
处理器：
* 停止当前的执行过程
* 处理由该信号发出的请求

必须满足两个条件：

I/O设备必须需要服务
KBSR或DSR的就绪位，当相应的就绪位被设为1时，I/O设备就需要服务
设备必须有权去请求服务
中断允许位（IE）
* 可以被设置为1或清为0，取决于是否给I/O设备权利去请求服务
* 在大多数I/O设备里，中断允许位是设备状态寄存器的一部分

INT信号

KBSR和DSR ： IE位是[1]位
中断请求信号（Interrupt Request，IRQ）
- IE位[1]和、就绪位[0]的逻辑与
各中断设备发出的IRQ信号经过或门，产生INT信号

原因寄存器

如果某个设备发出IRQ信号，就会将一个被称为原因寄存器（CAUSE）的相应位设为1
- 记录哪些设备发出中断信号
- DLX的一个特殊寄存器，只有在特权模式下（操作系统），才能访问
- CAUSE[15:8]为中断未决位

状态寄存器

所有设备的IE位的信号可以被状态寄存器SR[0]同时改写
- DLX的一个特殊寄存器，只能在特权模式下访问
- SR[0]表示中断允许位，决定了谁能中断处理器
- 如果SR[0]为0，那么所有I/O设备都不能中断处理器，在这种情况下，只能采用轮询方式访问I/O设备
- 如果SR[0]位被设置为1，那么允许所有I/O设备中断

INT信号的处理

发出INT信号后，处理器如何发现这个信号？
- 指令执行按顺序为取指令、译码、执行、访问内存和写回5个阶段
- 为测试中断信号而增加逻辑
- 将总是从写回返回到取指令的最后一步取代为：写回，并检测INT信号
  * 如果INT信号为0，那么它与往常一样，控制单元将返回取指令阶段，开始下一条指令的处理
  * 如果INT信号为1，
  - 保存及改变程序状态
  - 那么控制单元将PC加载为x8000 1000，执行操作系统的中断服务例程, 处理由该信号发出的中断请求

保存及改变程序状态

中断服务例程类似于自陷服务例程
存储在存储器的一些预先分配的单元中的程序片段，为中断请求服务
在进入中断服务例程之前（PC加载为x8000 1000之前）
保存足够的正在运行的程序的状态信息，以便当I/O设备请求被满足之后，能够返回被中断的程序
改变程序状态，以便访问恰当的资源，以及避免各种I/O设备互相干扰
程序状态
- 程序影响的所有资源所包含的内容的瞬态图，包括
  - 作为程序一部分的存储单元的内容
  - 所有通用寄存器的内容
  - 寄存器：PC和SR
  - PC的保存：
    - 因为PC包含了下一条要执行的指令的地址，必须被保存起来，以便当被中断的程序重新执行时，可以正确的返回到下一条指令地址
    - DLX有一个特殊寄存器EPC，用于保存中断发生时PC中的值
  - SR[0]
    - 程序是否可以被I/O设备中断，应该被保存
    - 例如，用户程序允许被中断，而进入中断服务例程，为避免受到来自其他设备的中断信号的干扰，则应屏蔽所有中断，即SR[0]从1改变为0
    - 因此，SR[0]需要保存起来，以便返回到用户程序时，仍可被I/O设备中断
  - SR[1]
    - 程序的特权级别包含了被中断的程序能够访问哪些资源，禁止访问哪些资源，必须被保存
      - 如果从用户程序进入中断服务例程，SR[1]就从1改为0，因为中断服务例程需要访问SR、CAUSE、 EPC等寄存器，因此，SR[1]也需要保存起来
  - 当中断发生时，DLX使用SR[2]保存SR[0]的值，使用SR[3]保存SR[1]的值，即利用SR实现了一个硬件栈

中断优先级

处理器执行任务执行的紧急程度被称为优先级
为了让I/O设备成功的停止处理器，开始中断请求的处理，请求的优先级必须比它希望中断的程序更高
DLX有6个硬件优先级，PL0，… …，PL5 [15:10]
数字越高，优先级越高
速度越高的I/O设备，优先级也越高
* 例如，键盘优先级别为1，显示器级别为0
在最低的优先级下，允许所有中断，在最高的优先级下，则屏蔽所有中断
2个软件优先级[9,8]

SR[15:8]

DLX的中断优先级，采用状态寄存器SR[15:8]表示
SR[15:8]给出了中断阻塞方案，以决定系统响应哪些中断
与CAUSE[15:8]一一对应
左至右，优先级别依次降低
要允许某一级别的中断，屏蔽位必须为1
原因寄存器中的未决中断要等到相应的屏蔽位为1 时，才能引起处理器的处理

中断服务例程

第一项任务
- 对原因寄存器的中断未决位CAUSE[15:8]和状态寄存器的中断掩码位SR[15:8]做“逻辑与”运算，看发生了哪些允许的中断
- 如果有多于1个的允许中断发生，则选择优先级高的中断（左边的优先级更高）
- MOVI2S和MOVS2I
  - DLX的数据传送指令：整数寄存器和特殊寄存器之间进行数据传送
  - 汇编中顺序也是MOVI2S Rx special
    
    MOVS2I Rx special
第二将任务
- 服务中断

第三项任务
- 从中断返回
- 首先，清空CAUSE寄存器，表明处理完所有的中断
- 然后，使用RFE指令
- 将PC恢复为EPC中的值，即假设程序没有被中断的下一条执行的指令地址
- 将SR[0]恢复为SR[2]的值，将SR[1]恢复为SR[3]的值，即允许中断和返回用户模式

中断嵌套

在中断服务例程中执行键盘处理例程时，如果允许被比键盘优先级高的设备所中断
- 以键盘处理例程为例，在读取KBDR的值之前，要先执行：
- 1）保存SR和EPC的值
- 2）将SR[15:8]的值改为xF0，即SR[15:12]均为1， SR[11:8]均为0，也就是屏蔽比该设备优先级低（或相等）的其他设备的中断，允许优先级高的设备的中断
- 3）将SR[0]改为1，即允许中断。这样，就允许被其他优先级高的设备所中断。
因为改变了SR[15:8]和SR[0]的值，在结束键盘处理例程之前，应先将SR[0]改为0（因为接下来恢复SR和EPC的过程不能被中断），再恢复SR 和EPC的值
需要使用栈结构来存储程序状态

I/O流

现代程序设计语言为考虑I/O创造了一个有用的抽象：输入和输出发生在流上
输入流
- 键盘
- 一个字符被键入，添到流的结尾处
- 程序读取输入，从流的开头处读
输出流
打印机
* 程序打印的字符，添到输出流的结尾处
* 打印机，从输出流的开头处打印
使用流的原因
- I/O设备和CPU，两者通常以不同的速率运转
- 流，又称缓冲区，用于缓存数据
  - 如果一个程序想要执行某些输出，它把字符添加到输出流的结尾处即可，而不必等待输出设备结束前一个字符的输出
- 使低速的输入输出设备和高速的CPU能够协调工作，避免低速的输入输出设备占用CPU，解放出 CPU，使其能够高效率工作

第十四章：子例程

子例程

在一个程序中，多次执行某个程序片段
在程序内，不必每次说明其源程序段的全部细节
通过多次调用该程序片段实现
子例程/函数（C语言）
可以由不同的程序员分别实现

子例程机制

调用/返回机制

调用机制
计算子例程的起始地址，加载到PC，并保存返回地址
调用子例程指令
2种方法，计算子例程的起始地址
* JAL：Jump and Link
- PC ← PC + 4 + SEXT(PCOffset26)
- 与J指令相同
- R31← 返回地址

*  JALR：Jump and Link Register
  * PC ← (SR1)
    *  与JR指令相同
  *  R31← 返回地址

JAL和JALR指令
* 在R31中保存返回地址
- PC+4

*  计算子例程的起始地址并加载到PC

返回机制
使用返回地址加载PC
与TRAP指令相似
- 将PC加载为程序片段的起始地址，同时R31被加载返回地址
- 程序片段的最后一条指令
- JR R31
使用子例程必须知道
- 地址(或标记)
- 功能
  - 不需要知道如何实现
- 传给子例程的值
- 返回值

使用外部库例程：.extern

递归子例程

“栈”机制

造成错误的原因
- 递归调用子例程时，保存寄存器的指令将前一次保存的值覆盖了
如何解决？
采用“栈”机制

栈

栈是一种存储结构
- 可通过不同的方式实现
栈的概念
与实现无关
后进先出 (Last In, First Out)，LIFO
抽象数据类型
存储机制，由对它执行的操作所定义，而不是实现它的方式
压栈（push）
把一个元素插入栈
出栈（pop）
移出一个元素
由一组存储单元和被称为“栈指针” 的机制组成
- 栈指针
- 栈的栈顶
- 最后压入的元素的存储单元地址
- 栈中的数据不进行物理移动

C-DLX：为变量分配寄存器

寄存器的访问比存储器快得多
DLX算术/逻辑运算指令，对寄存器进行运算
应尽量多的使用寄存器

为变量分配存储空间

当寄存器数量不足时
例如，局部变量多于8个
将最常用的变量保存在寄存器中，不常用的变量放到存储器中
基于变量的特征，为它们分配存储空间

存储器组织

全局数据区

全局变量
静态存储类变量
关键字static声明
全局数据区
保持对它所在的块的私有性

运行时栈

局部变量(先使用寄存器，不够用再压栈)/自动存储类变量
函数的栈框架/活动记录
R29，栈指针

框架指针

更方便的访问运行时栈中的变量
框架指针/帧指针
作为基址
R30
R8 ← x9
假设x9距离R30的偏移量为-10，在R30和x9之间存储的都是整数类型的值：lw r8, -40(r30)
函数的活动记录——从帧指针所指的单元到栈指针所指的单元之间，除了局部变量，还存储了哪些内容？
- 与函数的编译过程有关

第十五章：函数

函数

函数声明
函数定义
函数调用
函数和变量命名
- 帕斯卡命名法
  - Pascal-case，大驼峰式命名法
  - 混合使用大小写字母来构成变量和函数的名字，首字母大写

编译

预处理

寻找以“#”开头的预处理指令，根据预处理指令执行
与DLX汇编语言中的伪操作相似

1 2	#define X Y #include <x.h>

编译

目标模块
一段机器代码
主要阶段
分析
* 读入、分析和构造原始程序的内部表示
* 源程序被分解或者分析为其组成部分
合成
* 生成机器代码
* 如果需要，进行代码优化

链接

库的目标代码
- 根据计算机系统被保存在一个特定地方
- 例如，在UNIX中，/usr/lib目录
动态链接
动态链接库[DLL]或共享库，根据需要被“链接

寄存器

函数调用机制

当一个函数被调用的时候，在机器层要进行很多工作
变元必须被传递，活动记录被压入、弹出，控制从一个函数转移到另一个
某些工作由调用函数完成，某些由被调用函数完成
第一，调用函数
使用参数寄存器R4~R7存储变元的值
如果需要（参数 > 4个），将变元分配到运行时栈（被调用函数可以访问的存储区域）中
第二，被调用函数
完成活动记录的分配
* 将一些寄存器的值保存到运行时栈中，使得当控制返回到调用函数时，调用者的寄存器看起来好像没被动过——寄存器的保存
- 被调用者把R31中的返回地址的一份副本压入栈中
- 被调用者把R30中的动态链接（调用者的框架指针）的一份副本压入栈中
- 调整R30指向被调用者的活动记录的最底部
- 被调用者将需要保存的其他寄存器压栈

*  如果需要（局部变量寄存器不足），将局部变量分配到运行时栈中，最后，R29指向栈的顶部

第三，被调用函数
执行任务
可以调用其它函数，或递归调用……
第四，被调用函数
当完成工作时，活动记录从栈中弹出，并且控制返回到调用函数
一旦被调用函数完成了它的工作，它在将控制权返还给调用函数之前，必须弹出当前的活动记录：
1. 将变元从栈中弹出（如果在此函数执行过程中，又存在函数调用，且有变元压栈）
2. 局部变量从栈中弹出（如果此函数有需要存储器保存的局部变量）
3. 恢复保存的寄存器
4. 恢复动态链接
5. 恢复返回地址
6. JR R31，将控制权返回给调用程序
最后，调用函数
一旦控制返回到调用函数，执行代码取回被调用函数的返回值

返回值的处理

在需要返回值的情况下
函数A使用R2保存返回值，代码如下：

1	addi r2, r17, #0 ; return y;

临时寄存器的保存和恢复

在一个函数的执行过程中，R8-R15和R24、R25作为临时寄存器，存储函数执行过程中用到的临时数据；R4~R7作为参数寄存器，是否也需要在运行时栈中保存？
在如下情况下，需要保存和恢复：
如果调用者在调用后还将用到临时寄存器（R8-R15和R24、R25）或参数寄存器（R4~R7）

第十六章：指针和数组

指针

一个存储对象（如，变量）的地址
使用指针，可以间接访问对象
如，修改调用者的局部变量的函数
变元以值的形式从调用函数传递到被调用函数
要修改变元，必须在调用函数的活动记录中为变元分配空间
通过访问存储它们的单元，修改变元
指针及其相关运算
空指针：不指向任何东西的指针
int *ptr;

ptr = NULL;
- NULL，特别定义的预处理宏
  - 如 0
函数指针
- int (*func) (int a); /* 声明一个函数指针 */
- 函数返回值类型（*指针变量名）(形参列表)；
- 函数指针不指向变量，而是指向函数
- 函数名和数组名一样，代表了函数代码的首地址
- 用途：调用函数和做函数的参数

数组

类型
int x[10];
类型：int
数组名：x
[ ]：数组
10：包含10个顺序排列的整数
* C89,不支持变量
数组的大小，使用预处理宏
增加数组的大小，只需改变宏的定义
在C语言中，一个数组的名字指的是数组的基址

第一章： 引言

计算

计算机

基本概念

核心特征

理论模型

发展历史

计算机系统

计算机系统组成

存储程序控制原理

hello程序的执行

计算系统

抽象层级

问题

算法

程序

指令集结构

微处理器

逻辑电路

元件

第六章： 数据的机器级表示

前导

数据和信息

计算机的信息存储

字节&比特

字长

进位制

二进制

十六进制

数据类型

基本概念

大端法和小端法

字符型

ASCII码

整型

浮点型

C语言中的数据类型

第七章：数字逻辑电路

二进制逻辑运算

逻辑运算概念

基本运算符

布尔代数的基本公式、定律

按位运算

C的按位运算符

C的逻辑运算符

集成电路

晶体管

MOS晶体管

NMOS晶体管

PMOS晶体管

CMOS电路

门电路

非门

或门、或非门

与门、与非门

组合逻辑电路

基本介绍

译码器

多路选择器

全加法器

数值比较器

可编程逻辑阵列

基本存储元件

锁存器

R-S锁存器

门控D锁存器

触发器

主从D触发器

时序逻辑电路

基本介绍

有限状态机

时序逻辑电路设计

第8章 冯·诺依曼模型

基本结构

简介

存储器（RAM）

处理单元（ALU）

控制单元（PC）

输入/输出设备（I/O）

冯诺依曼模型示例——DLX

第一章：引言

第六章：数据的机器级表示

第8章冯·诺依曼模型

第十五章：函数