下次埋

前言收获

并行和并发的区别

• 并发：面对多个任务同时存在的情况下，能够处理它，不用管如何执行（可以交替执行、可以并行执行）
• 并行：面对多个任务同时存在的情况下，能够处理它，任务和任务间互不影响，一起执行

并行概念是并发概念的一个子集，如下图所示

并行架构：

• 位级并行
• 指令级并行
• 数据集并行
• 任务级并行

全书要讲解的7个模型：

• 线程与锁：其他模型的技术基础，虽然存在不足但仍是众多软件的首选
• 函数式编程：消除了可变状态，根本上是线程安全的，易于并行执行
• Clojure之道——分离标识与状态：命令式编程和函数式编程混搭的方案，在两种编程方式中取得平衡来发挥两者的优势
• actor: 适用于共享内存模型和分布式内存模型，也适合解决地理分布型问题，能够提供强大的容错
• 通信顺序进程（Communicating Sequential Processes ，CSP）: 该模型和actor很类似，两者都基于消息传递。不过CSP侧重于传递信息的通道，而actor模型侧重于通道两端的实体，使用CSP模型的代码会有明显不同的风格
• 数据级并行：GPU，如果要进行有限元分析、流体力学计算或其他的大量数字计算，GPU的性能将是不二选择
• Lambda: 综合了MapReduce和流式处理的特点，是一种可以处理多种大数据问题的架构

后续学习要带上以下几个问题：

• 这个模型适用于解决并发问题、并行问题还是两者皆可？
• 这个模型适合哪种并行架构
• 这个模型是否有利于我们写出容错性强的代码，或用于解决分布式问题的代码？

互斥和内存模型

因为该部分讲的不深，而且经过两本并发书籍的洗礼，理解起来较为简单，就将总结的话记一下：

• 对共享变量的所有访问都需要被同步化
• 读线程和写线程都需要同步化
• 按照约定的全局顺序来获取多吧锁
• 当持有锁时不要访问外星方法（不了解的方法，里面可能会对部分资源加锁）
• 持有锁的时间尽可能短

自学篇之JMM

自学篇之JSR-133的FAQ

原文出自(http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html)

究竟什么是内存模型？

在现代处理器系统里，通常会划分几个内存缓冲层。它们能够提高访问数据的速度并且降低共享内存总线的流量（因为缓存层就直接可以满足处理器需求），它们的结构示意图如下所示。那么两个处理器在同一时间查看同个内存地址时，什么情况下能看到一样的值。这就是内存可见性问题

第一个影响可见性的原因是，强内存模型能直接保证 对同一个内存地址在任何时候都能看到相同的值；弱内存模型需要 内存屏障(memory barriers)，这些指令会要求处理器刷新或无效化本地缓冲区，所以就能看到其他处理器的写入。因为强内存模型对内存指令的需求较少（注意，不是不需要，只是需求少），所以强内存模型易于编程。然而近代处理器都是鼓励往弱内存模型发展，由于弱内存模型对缓存一致性比较放松，跨多处理器和大量内存会有更好的扩展性。

第二个影响可见性的原因就是重排序，在内存模型给定的边界里任由编译器、内存、处理器优化。

所以Java内存模型主要描述了程序中的变量和物理机中内存、寄存器间的关系，JMM尽可能让编译器、硬件可以执行优化。

其他语言有内存模型吗

很多编程语言，像C、C++，就没有直接支持多线程。如果想避免所有重排序发生在编译器里，整个架构都需要依赖线程库、依赖编译器、系统

JSR-133讲了什么

JSR-133 为Java定义了一个新的内存模型，修复了早期的内存模型问题。为了实现它，final、volatile的语义均得到改变。通过完整的JSR-133语义可以了解到JSR-133的全貌

JSR-133的目的包含以下几点：

• 保持已存在的安全保证，加强其他安全，比如变量值不能凭空出现，每个变量值的出现都应该有理有据
• 正确同步的程序语义应该尽可能简单、直观
• 对于不正确同步的程序语义，应尽可能的减小风险。
• 对于每个程序员来说，都应该能正确推导多线程和内存间的交互关系
• JVM应该被设计为：能为大部分主流的硬件架构提供高性能
• 应该保证初始化安全。如果一个对象被正确的构造（没有发生this逸出），就算没有同步，所有引用该对象的线程都将看到该构造器设置的final变量的值。
• 对现有代码造成最小的影响

重排序意味着什么

当访问某个变量时，可能出现它的值和预期指定的值不一样。编译器会重排序指令，处理器也可能会重排序指令。数据在寄存器、缓冲、内存间移动的顺序不按程序指定的来。
尽管如此，单线程程序是看不到重排序的影响的，即中途发生重排序，结果仍然不会改变。然而重排序会在多线程中起到作用：由于一个线程的修改可以被另外一个线程观察到，所以重排序中途修改的值会被另一个线程观测到。

旧的内存模型有什么问题

难理解，出现范围广。具体表现在以下两个例子里：

• final变量被一个线程读时可能出现默认值，另一个线程读时可能出现构造值。这就意味着不可变对象发生变化了。
• volatile写会和普通读/写发生重排序。

什么是不正确的同步

1. 一个线程对一个变量执行写入
2. 另一个线程对同一个变量执行读取
3. 写入和读取没有用同步排序
   当发生这种情况时，都可以认为是发生了“数据竞争”

同步做了什么

• 排斥：一个线程获取了管程，另一个线程只能等到第一个线程释放后才能获取
• 可见性：在我们释放管程时，同步块会将本地内存刷新到主内存；获取管程之后，同步块会使本地缓存失效，重新去主内存中加载。
• happens-before：当一个操作happens-before另一个操作，那么就能向程序员保证JMM会让第一个先于第二个发生并对第二个可见

术语科普

• 机器数：在计算机里表示的方法，即正负不再是用 -，+来表示，而是采用0表示正数，1表示负数
• 真数：相对机器数，用-，+来表示正负的数就叫真数

原码

原码即最原始的二进制表示法，这种方法简单直观。
比如 +11，通常表示为 0000 1011
比如 -11，通常表示为 1000 1011

不知道小伙伴会不会有疑问，那8位可以表示的范围不久小了吗？
答：是的，小了一半。而且 [+0]_原 != [-0]_原

定义

整数

计算机规定，任何正数的原码都是其本身。而对于负数来说，需要把最高位变为“1”，所以需要 2ⁿ - x，由于负负得正，其实是 2ⁿ + |x|，其示意图如下所示

其中x为真值，n为整数的位数

比如：
当x = -1011 时，[x]_原 = 2⁴（即1 0000） - (-1011) = 1 1011，即1, 1011

2⁴是指16，16即10000，如果是2³，那么就是8，即1000

注意，这里记得用逗号分隔 符号位和数值位

小数

正的小数都是其本身。而对于负数来说，需要把最高位变成“1”，所以需要1 - x，由于负负得正，其实是 1 + |x|，其示意图如下所示

其中x为真值，n为整数的位数

比如：
当x = -0.1011 时，[x]_原 = 1 - (-0.1011) = 1.1011

注意，这里记得用点号分隔 符号位和数值位

优点

简单直观

缺点

进行加减运算会带来许多麻烦，比如一个正数和负数相加（注意，这里进行运算时都要采用机器数，不能使用真数）

补码

由于原码在进行四则运算时，总需要判断正负号，所以科学家想到了一种用正数代替负数的方法，即补码

补码的原理类似于 mod(即取余)。比如有一个时钟，现在指向6点，如果想拨到8点钟，我们可以顺时针拨2个小时（可以理解为(6 + 2) mod 12 = 8），也可以逆时针拨10个小时（可以理解为 (12 + (6 - 10)) mod 12 = 8）。这说明了可以用加法代替减法，只要限定最大值，然后不断循环即可。

##定义

整数

计算机规定，正数的补码是其本身；负数的补码要取模 + 真值（为负数）。

其中x为真值，n为整数的位数

比如：
当 x = -1010 时，[x]_补 = 2⁴ + (-1010) = 10000 + (-1010) = 0110

小数

计算机规定，正数的补码是其本身；负数的补码要取2 + 真值（为负数）。

比如：
当 x = -0.1010 时，[x]_补 = 2 + (-0.1010) = 10.0000 + (-0.1010) = 1.0110

对于补码来说，由于经常会出现进位的算法，计算时很麻烦，所以这里给出一个简单的算法：

优化

除原码符号位，将其他数值为取反（相当于减），最后加一即可。

反码

反码其实是补码的一个过渡表示法。将除符号位以外的数值位取反，就可以得到反码（这是我们最直观的做法，但是计算机没那么聪明，需要通过数学公式得到）。

可以很明显发现反码其实就是在补码的基础上减去了一个“1”，就得到了反码。

2^-n 代表前面有n个0，比如 2 ^-4，即为0.0001

同理，也是在求补码的基础上减去了一个“1”（这里的“1”对于小数来说是最小的n位）

移码

待我学习一波定点和浮点。

概述

DMA方式是IO接口的控制方式之一。DMA和其他控制方式相比，它拥有专门的数据通路，所 以主存和设备交换信息时，可以不经过CPU，也不需要CPU参与数据交换（程序中断需要CPU参与中断服务），那么就省去了 保护现场、恢复现场的流程。

由于DMA接口的速度很快，所以经常用于高速IO设备，因为高速IO设备如果不及时交互信息，很可能产生数据丢失。

上面所有的优势均建立在 主存和IO设备直接交换信息，不需要经过CPU这个条件之上，而当CPU和IO设备同时访问主存时，就会发生冲突。为了解决冲突，通常会采用以下几个方法：

• 停止CPU访存
• 周期挪用（又称周期窃取）
• 交替访问

停止CPU访存

假设IO设备要发送一些数据，DMA接口会向CPU发出一个停止信号，要求CPU放弃总线控制前，DMA接口获得总线控制权后，开始进行数据传送，在数据传输结束后，DMA接口通知CPU可以使用主存，并把总线使用权交给CPU。其时序图如下所示

这种方式的缺陷主要在于 CPU失去总线控制权的这段时间里，DMA接口也并不是百分百利用这段时间，因为IO设备传输数据给接口的数据缓冲器这段时间也总大于一个存期周期。换句话来说，当IO设备还在准备数据的时候，CPU也仍然处于空闲状态。

周期挪用（周期窃取）

当IO设备发出DMA请求时，IO设备便挪用或窃取总线占用权一个或几个周期，而DMA不请求时，CPU仍可继续访问。

而IO设备请求DMA时，会有三种状况：

1. CPU不访问主存，那么DMA接口和CPU不会发生主存
2. CPU正在访问主存，那么DMA接口需要等待该次存储周期结束
3. DMA和CPU同时要访问主存时，DMA接口发出请求占用几个存取周期（即在CPU执行访存指令过程中插入DMA请求，使CPU延迟了几个周期再访问）

IO设备每挪用一个主存周期都要申请总线控制权、建立总线控制权和归还总线控制权。因此，对于主存来说，虽然只传一个字只占用一个周期，但对DMA接口来说，要处理包括申请、建立、传输、归还等阶段，实质上DMA接口要占好几个周期。

因此周期挪用适合IO设备的读/写周期大于主存周期的情况。

DMA与CPU交替执行

这种方式不需要总线使用权的申请、建立、归还过程，总线使用权分别由C₁、C₂控制的。CPU和DMA接口各自有独立的访存地址寄存器、数据寄存器、读写信号。实际上总线变成了C₁、C₂控制下的多路转换器，其总线控制权的转移几乎不需要时间，具有很高的DMA传送速率。

DMA接口的功能和组成

DMA接口应该具有以下几个功能：

1. 向CPU申请DMA传送
2. 在CPU允许DMA工作时，处理总线控制权的转交，避免引起总线竞争
3. 在DMA期间管理系统总线，控制数据传输
4. 确定数据传送的起始地址和数据长度，更新数据传输过程中的数据地址和数据长度
5. 在数据块传输结束时，给出DMA操作完成的信号

DMA接口的组成原理如下图所示

DMA数据传输的流程

DMA的数据传送过程分为 预处理、数据传送、后处理三个阶段。
其示意图如下所示：

预处理

在DMA接口开始工作之前，CPU必须给它预置如下信息：

• 给DMA控制逻辑指明数据传送方向
• 给设备地址寄存器（DAR）送入设备信号
• 向主存地址寄存器（AR）送入交换数据的起始地址
• 对字计数器赋予交换数据的个数

当这些工作完成后，程序初始化结束。

数据传输

等IO设备准备好数据 或 处理完输出的数据后，就让DMA接口向CPU提出总线获取控制权，如果有多个DMA请求，则按轻重缓急排队等待。当IO设备获取到总线控制权后，数据的传输就由DMA进行管理。

数据读取过程：

1. IO设备发送数据到数据缓冲区内
2. IO设备发送DREQ请求给DMA控制逻辑
3. DMA控制逻辑发送HRQ给总线申请获取总线控制权
4. 获取成功后，DMA控制逻辑收到HLDA响应，将总线控制权交给DMA接口
5. 将DMA主存地址寄存器的主存地址送到地址总线，并命令存储器写
6. 通知设备已被授予一个DMA周期（DACK），并为下一个字做准备
7. 将DMA数据缓存寄存器的内容送至数据总线
8. 主存将数据总线上的信息写到地址总线指定的存储单元
9. 修改AR和WC
10. 判断数据块是否结束，若未结束继续传输；否则向CPU申请程序中断，标志数据传输完毕

输出数据过程：

1. 当DMA的BR已将数据送至IO设备后，表示BR已空
2. 设备向DMA接口发请求DREQ
3. DMA接口向CPU申请总线控制权HRQ
4. CPU发回HLDA信号，允许交出总线控制权
5. 将DMA主存地址寄存器中的主存地址送到地址总线，并命令存储器读
6. 通知设备已经被授予一个DMA周期（DACK），并为交换下一个字做准备
7. 主存将相应地址单元的内容通过数据总线读入DMA的BR中
8. 将BR的内容送到输出设备
9. 修改AR和WC
10. 判断数据块是否结束，若未结束继续传输；否则向CPU申请程序中断，标志数据传输完毕

后处理

当DMA的中断请求得到响应后，CPU停止原程序的执行，转去执行中断服务程序，做一些DMA的结束工作，包括校验数据的正确性、决定是否继续用DMA传送其他数据块、测试传输过程中是否发生错误。

概述

计算机在执行程序得过程中，当出现异常情况或特殊请求时，计算机停止现行程序（（正在运行的程序）），转向对这些异常情况或特殊请求得处理，处理后再返回到现行程序的间断处。

由于CPU和IO设备速度的不匹配，CPU通常要等待一段时间，才能实现主机与IO设备之间的信息交换。所以当CPU启动了IO设备之后，就转去执行现行程序，让IO设备准备好后主动通知（中断）CPU，CPU转去执行中断程序，进行数据交换。这就是IO中断。

中断方式的电路

中断请求触发器和中断屏蔽触发器

每台外部设备都必须配置一个中断请求触发器INTR，当其为“1”时，表示该设备向CPU提出中断请求。同时也需要一个配对的 中断屏蔽器，用于屏蔽一些低优先级的中断请求（面对多个中断请求时），当它为“1”时，表示封锁其中断源。其电路逻辑图如下所示

当设备准备就绪D为“1”、且该设备MASK不为“0”时，由CPU在指令执行结束阶段时，由CPU发出中断查询信号，将INTR设置为“1”

排队器

当多个中断源同时向CPU发出请求时，CPU会根据中断源的不同性质对其排队，给予不同等级的优先权，并按优先级等级给予响应。

通常来说速度越快的IO设备，优先级越高，因为不及时响应高速的IO请求，信息可能会发生丢失。

排队器分为硬件排队器和软件排队器：这里只介绍硬件排队器，下图是硬件排队器的电路

当各个中断源无请求时，各个INTR^-均为高电平。一旦某个中断源提出中断请求时，就会让优先级低的中断源变为低电平，封锁其中的中断请求。比如当2、3号中断源同时有请求时（INTR2^-、INTR3^-均为0），流程如图所示

INTR_i^- 没有提出请求时均为高电平，根据例子，二、三号中断源提出请求，二、三号输入低电压，由于二号经过与非门输出高电压，经过三号的非门，输出低电压，让三号无法被选。此时因为INTP₁^‘和INTP₂^‘输出都为高电压，又通过INTP_i来和输出信号进行与运算，最终输出INTP₂

中断向量地址形成部件（设备编址器）

CPU一旦响应了IO中断，就要暂停现行程序，转去执行该设备的中断服务程序。不同的设备有不同的中断服务程序，每个服务程序都有一个入口，而CPU需要通过设备编址码找到中断服务程序实际所在的位置。

设备编址码的输入是来自排队器的输出INTP_i，它的输出是中断源的位置

比如编址器输出12H，CPU就能从主存的12H的位置查找（假设是统一编址），找到对应的中断服务程序的入口地址

IO中断处理过程

中断的条件和时间

1. CPU中的EINT(允许中断触发器)为“1”，该触发器用开中断置位，用关中断使其复位
2. CPU响应中断的时间一定是在每条指令执行阶段的结束时刻

接下来以输入设备为例，结合流程示意图进行讲解，流程图如下所示

当选中设备后，设备选择电路发出SEL信号

1. CPU发出启动命令，将触发器B置为“1”，D为“0”
2. 接口启动输入设备，设备开始工作
3. IO设备将数据送入数据缓冲寄存器
4. 当输入设备发出设备工作结束信号后，D被置为“1”，B被置为“0”，标志设备准备就绪
5. 当设备准备就绪，且本设备未被屏蔽时，在指令执行结束阶段，CPU会发出中断查询信号
6. 设备中断请请求触发器INTR被置为“1”，向CPU提出中断请求，INTR送至排队器，进行中断判优
7. 若CPU允许中断（ENIT=1），设备又被排队选中，即进入中断响应阶段，由中断响应信号INTA将排队器输出送至编码器形成的向量地址
8. 向量地址送至CPU，作为下一条指令的地址
9. 向量地址里存放的是无条件转移指令（看中断流程图），待转移指令执行完毕，就转去对应设备的服务程序入口地址，开始执行中断服务程序，通过输入指令将数据缓冲寄存器的输入数据送至CPU的通用寄存器，再存入主存相关单元
10. 中断服务程序的最后一条指令是中断返回指令，当其执行结束时，中断返回至原程序的断点处。

中断服务程序的流程

总共分为四个阶段

1. 保护现场
2. 中断服务
3. 恢复现场
4. 中断返回

保护现场

其一是保存程序的断点，其二是保存通用寄存器和状态寄存器的内容。前者涉及到中断隐指令，后者由中断服务程序完成。中断服务程序会在程序的起始部分安排若干条存数指令，将寄存器的内容存至存储器中保存；或者用进栈指令将各个寄存器的内容压入堆栈中保存。

中断服务

不同的设备中断服务不一样，比如打印机要求CPU将需要打印的字符代码送入打印机的缓冲器内；显示器设备要求CPU将需要显示的字符代码送入显示存储器中

恢复现场

在中断服务程序退出前，将中断的现行程序恢复回来。通常可用取数指令或出栈指令，将保存在存储器中的信息送回到原来的寄存器中

中断返回

中断服务程序的最后一条指令通常是一条中断返回指令，使其返回到原程序的断点处

单重中断和多重中断

当CPU响应了一个中断源的中断请求后，EINT会被置为“0”，无法让其他中断源继续请求。对于单重中断，在保护完现场后，即刻去执行设备服务，直到恢复完现场后，才将EINT置为“1”并返回。而对于多重中断来说，在保护完现场后，就立刻将EINT设置为“1”，允许其他中断源插入中断请求。示意图如下所示

多重中断就和方法里面再调用其他方法一样，如下图所示

总结

从宏观上看，中断方式克服了程序查询方式的原地踏步，CPU和IO设备是并行操作的，提高了CPU的资源利用率

从微观上看，CPU在处理中断服务程序时仍然需要暂停原程序的运行，尤其是当高速IO或辅助存储器频繁地与主存交换信息时，需要不断打断CPU执行主程序而执行中断服务程序。

为了完善中断程序，人们提出了DMA控制方式。

概述

程序查询方式的核心问题在于 每时每刻不断查询IO设备是否准备就绪，查询流程图如下所示

当IO设备比较多的时候，CPU会按照各个IO设备的优先级逐个查询，流程图如下所示

程序查询流程

1. CPU先保存自己的寄存器情况
2. 设置计数器，即要读取多少次
3. 设置要存放的位置的起始位置
4. 启动IO设备
5. 获取IO设备状态标志到CPU，检查IO设备是否准备就绪：如果准备就绪，开始读取数据，反之原地踏步
6. CPU执行IO指令，或从IO接口中的数据缓冲寄存器中读取一个数据，或者写入数据到IO接口的数据缓冲寄存器内
7. 修改主存地址
8. 修改计数器（比如从正数递减到0，或从负数递增到0）
9. 结束IO传输

I/O设备的发展

第一阶段

早期计算机采用 分散连接(指计算机各个部件间相连的方式) 的结构，如下图所示。每一个部件之间都需要连接。

以下是分散连接的抽象图

缺点：

1. 由于一个I/O设备需要一个专用的逻辑控制电路才能连接使用，所以线路会很多很繁琐。
2. 该结构下对I/O设备的读写基本都是串行的，会严重影响CPU的运行速度
3. 由于I/O设备和CPU之间的耦合性过于紧密，所以对于设备的增减过于麻烦

第二阶段

这个阶段计算机采用 总线连接的结构，(这里关注点在于I/O设备，所以拿单总线结构距离)。如下图所示

这个阶段I/O设备通过 接口 挂在在总线上与CPU相连。I/O接口通常包含 数据通路、 控制通路 两个部分：

• 数据通路：用于缓冲数据，可以进行串-并转换，匹配I/O设备和CPU的速度。
• 控制通路：用于接收I/O指令

这个阶段相比第一阶段，补足了缺点，并让CPU和I/O设备并发处理的时间更多，但是还不能做到完全的并发处理

第三阶段

这个阶段更适用于I/O设备数量繁多的大型计算机，即在CPU和I/O接口之间又加入了 通道，通道用于负责管理整个I/O过程。当通道接收到CPU的指令后，先从主存中取出通道程序，然后单独执行，直至I/O设备输入或输出完毕，再通知CPU完成。这个过程不需要CPU参与，就大大提高了CPU和I/O设备的并行能力。

第四阶段

采用I/O处理机，I/O处理机又称 外围处理机，其相当于一个小型CPU，基本是独立于CPU进行工作的

输入输出系统的组成

输入输出系统主要包含两个部分：I/O软件、I/O硬件

I/O软件

I/O指令

I/O指令时CPU指令集的一部分，如下图所示

• 操作码：标明该指令是 I/O指令还是其他指令
• 命令码： 标明该指令具体做什么事，比如从I/O设备取出数据到CPU里、或者将数据送到I/O设备里
• 设备码：标明要处理的目标对象

通道指令

通道指令不是CPU指令集的一部分，通道指令是为拥有通道的I/O系统专门设置的指令，这类指令结构通常如下图所示

该指令通常存放再主存中，当需要运行时，由通道从主存中取出并执行。通道程序即由通道指令组成，它完成了某种外围设备与主存之间传送信息的操作。

区别

通道是通道自身的指令，用来执行I/O操作；
I/O指令是CPU指令系统的一部分，是CPU用来控制输入输出的操作命令。
在有通道结构的计算机中，I/O指令不实现I/O数据传输，主要是用于启动、暂停I/O设备；或者查询通道和I/O设备的状态及控制通道所做的其他操作。

一旦CPU启动了I/O设备后，就由通道接管CPU对I/O设备的管理。

I/O硬件

通常包括接口模块和I/O设备两大部分

I/O设备与主机的联系方式

这个部分主要解决三个部分：

• 设备地址
• 设备选择
• 传送方式
• CPU和设备间的传输方式

设备地址

• 统一编址：
  将主存划分一部分地址出来作为设备地址，比如在64K地址的存储空间中，划出8K地址作为I/O设备的地址，只要访问的地址在这8K范围内，就是对I/O设备的访问。

• 单独编址
  单独设置一个存储空间作为I/O设备的地址，使用专用的指令来存储。

设备选择

用设备选择电路识别是否被选中

传送方式

• 串行
• 并行

联络方式

立即响应

信号一到，立即响应

异步工作 + 应答信号

1. 在读过程中，I/O接口发送 READY 信号 给 I/O设备
2. I/O设备收到信号后，从I/O接口中取出数据，并回应一个 Strobe 信号给I/O接口

1. 在写过程中，I/O设备发送数据到I/O接口中，并发送信号Strobe
2. I/O接口收到信号后，通知CPU中断处理，然后返回READY信号给I/O设备

同步工作采用同步时钟

I/O设备的控制方式

程序查询控制

该方式主要在于CPU读I/O设备状态，然后检查状态是否就绪，如果没有就绪就循环查询。该查询方式会消耗很多时间在状态检查上（一直检查），同时还会花费部分时间在数据交互上。

程序中断控制

当CPU执行原程序时，如果遇到了I/O指令启动了I/O设备后，等待I/O接口数据缓冲区满了后，再通知CPU中断，执行中断服务程序

这个控制方式相比中断方式，CPU不需要长时间轮询状态，只需要启动I/O设备后，就能转头去做其他事情。直到I/O设备发回中断请求，CPU停止做事情，转去执行中断服务程序（交换信息）。

DMA控制

由于程序中断在数据交换过程仍然要CPU参与，会在一定程度上影响CPU速度。

DMA控制主要通过以下三个手段实现：

1. 主存和I/O之间架一条通路
2. 不中断现行程序
3. 周期挪用

接口可以是两个部件之间连接的电路，IO接口通常是指CPU和IO设备间的硬件电路和控制软件，而不同的IO设备通常都通过IO接口和CPU取得联系的。

IO接口的功能有如下几个：

1. 实现IO设备的选择
2. 匹配IO设备和CPU的速度
3. 实现数据的串-并转换
4. 实现电平的转换
5. 发送控制信号
6. 保存状态信息，供CPU进行查询

这里举个四功能的接口，看看它的功能和组成

组成介绍

设备选择线：
该线是用于传输设备码的，它的根数取决于I/O指令设备码的位数。

命令线：
该线是单项的，通常由CPU发出，用于传输CPU的I/O指令

状态线：
反馈IO设备的状态，该线也是单项的，通常

数据线：
双向的，用于传输数据，其根数一般等于存储字长的长度

功能介绍

选址功能

IO总线与所有设备的接口相连，但CPU究竟选择哪台设备，还得通过设备选择线上的设备码来确定。

每个接口会带有选址功能，当设备线上的设备码与I/O设备的设备码一致时，应发出设备选中信号SEL。

传送命令功能

当CPU向IO设备发出命令时，要求IO设备能做出响应。如果设备不具备传送命令的信息功能，设备将无法响应。所以通常在IO接口中设有存放命令的寄存器以及命令译码器。

命令寄存器用来存放IO指令中的指令码，只有当设备选择电路有效，SEL信号有效，才能存放命令道寄存器中。

传送数据的功能

IO设备和CPU之间通过接口的数据通路进行数据交互，接口还会有数据缓冲的功能，它用来暂存IO设备和CPU间要交换的数据。数据通路的位数取决于设备的种类。

IO设备工作状态

为了使CPU能时刻了解IO设备的运行状况，接口通常会设置一些反映设备状态的触发器。
比如工作触发器B、完成触发器D、中断触发器INTR，屏蔽触发器MASK

• D = 0, B = 0时，表示设备处于暂停
• D = 1, B = 0时，表示设备已准备就绪
• D = 0, B = 1时，表示设备处于准备状态

概要

CPU将主存地址 转换成 Cache地址时，需要经过 地址映射变换机构。不同层级的Cache 对 地址映射的算法方案 有不同的要求。

主存Cache地址映射变换机构

该机构主要是 将主存地址 按一定算法映射到 Cache地址

直接映射

映射算法

假设主存的块数为 m，Cache的块数为 c。那么通常会按 c个块为一组划分主存，每组的块编号依次按 0,1,2,...,c进行编号。假设m为16，c为2，其示意图如下所示

每组的编号（每组都从0开始计算），组0的块0、组1的块0（整体来看即块2）都对应着Cache的块0。也就是说，每组的第一个块 都必须存放在 Cache的第一个块里，同理 每组的第二块 都必须存放在 Cache第二个块里。示意图如下所示

用数学来表示映射算法即 z = i % c，i表示块编号，c表示cache的总块数（每组的块数）

比如：

1. 3 % 2 = 1
2. 2 % 2 = 0

映射流程

CPU发送来一个主存地址，该地址会分为三部分，一部分是主存组号，一部分是组内编号，一部分是块内地址，主存组号和组内编号共同组成块号。 如下图所示

1. 当Cache收到CPU发送的主存地址时，提取组内编号
2. 查找Cache中 组内编号指示 的块
3. 将块中的标识提取出来（此处的标识保存着主存的组号）
4. 比较Cache块提供的标识 和 主存提供的组号
5. 如果组号一致，则进入下个判断；否则不命中
6. 判断该块的有效位是否为“1”，如果为“1”，则命中；反之不命中
7. 如果判断为不命中，Cache就从主存里取出新的字块，并替换旧字块，最后将该块的有效位置为“1”

总结

直接映射的缺点就是不够灵活，因为每个主存块都对应着唯一的Cache块，如果CPU频繁访问 不同组的同编号块，那么Cache就经常会发生替换，影响速度，空间利用率不高

全相联映射

映射算法

主存内每个字块都可以被存储到Cache的任意字块内。

映射流程

当CPU发出如下图所示的地址时，

1. CPU通过主存块编号遍历Cache，查找Cache的标记是否和该主存编号相同
2. 如果找到则命中，未找到则未命中

总结

全相联映射更加灵活，主存块可以保存到Cache的任意块中。Cache的利用率就会高，但是由于遍历，速度往往较低。

组相联映射

映射算法

主存划分为多个组，缓存也划分为多个组，每个组里的块编号都对应着缓存里的组编号。简而言之，原来的直接映射只能一个缓存块对应多个主存块，为了提高空间利用率，允许一个多个同组的缓存块对应多个主存块。示意图如下所示

每个组的第一个块都对应着缓存的第一个组。同理，每个组的第二块都对应着缓存的第二块。

映射流程

每个组的第一块 都能放到缓存的第一个组内的任意位置。一方面，主存的块可以放在对应组内的任意一个位置，体现出了全相联的思想；另一方面，主存的每个块都对应着唯一一个组，这是直接映射的思想。

该方案是直接映射和全相联映射的折中方案。

替换机构

替换就是指 Cache满了之后，如果要存放新的主存块，就需要将某个Cache块取出，并替换新的主存块进入

主存块就像是放在书架上的书，缓存块就像是放在床头的书，如果床头的书满了，就需要找个方案取出一本书，然后将想看的书加进去

替换机构就是做了 如何取书 这件事

目前有两种方案：

• 先进先出FIFO
• 近期最少使用(Least Recently Used)
  LRU算法比较好的利用访存局部性原理，替换出近期用的最少的字块。通常是只记录每个快最近一次使用的时间。
• 随机法
  取一个随机数，没有根据访存的局部性原理。

注意，这里讲到的访存局部性原理是指 只访问某个块的内容，而不是全部的内容，即局部性

概要

目前CPU遇到以下两个问题：

1. 当 I/O设备向主存请求时，CPU无法访问主存，只能空等着
2. 主存速度的提高 始终跟不上 CPU的发展

为了避免CPU和I/O设备争抢方寸，可在CPU与主存之间加一级Cache，此时CPU只需要跟Cache交互即可；另一方面，添加Cache还能解决主存与CPU速度的不匹配。

问题的提出

1. 为什么添加一个Cache可以解决主存与CPU速度的不匹配问题？
2. 既然Cache速度这么快，为什么不用 Cache 替换 主存？
3. Cache的工作原理？
4. 如何判断Cache的性能？
5. Cache的性能由哪些方面决定？
6. CPU、Cache、主存间是如何进行交互的？

为什么添加一个Cache可以解决主存与CPU速度的不匹配问题

因为经过数据分析，发现代码执行时是存在 局部性的。
局部性主要分成两部分：时间局部性、空间局部性。

• 时间局部性：CPU从主存取指令或取数据时，在一定时间内，可能会对同个块重复访问。
• 空间局部性：由于数据在主存内都是连续存放的，所以很可能下一个即将访问的指令也在同一个区域内。

根据以上两点，只要将CPU近期要用到的程序和数据提前存到Cache中，那么CPU在一定时间内，只需要访问Cache即可。

既然Cache速度这么快，为什么不用 Cache 替换 主存

因为Cache一般采用SRAM制作，其价格比主存昂贵。

Cache的工作原理

主存由2ⁿ个可编址的字组成，每个字有惟一的n位地址。
为了与Cache映射，将主存与缓存都分成若干 块，每个块内又包含多个 字，并使他们的块大小相同（即块内字数相同）。

这就将主存的地址分成了两端：主存块号、块内地址。主存块号的位数 + 块内地址的位数 = 一个字的位数。

除此之外，Cache中有一个“标记”。标记是用来表示当前存放的是 哪一块主存块。设置这个标记是因为 Cache块 远比 主存块 少，所以Cache里停留的内容不会是固定的，需要一个东西标志 某个缓存块对应的主存块。

不是主存地址可以通过转换获取缓存地址吗，为什么还需要标志位？因为Map需要的时间是最少的。

Cache的性能指标

判断Cache好坏的指标有三个：

• Cache的命中率
• Cache的平均访问时间
• Cache的访问效率

Cache的命中率

Cache命中率 = 命中数 / (命中数 + 未命中数)

当CPU欲访问主存中的某块数据时，Cache中正好存在，则称为 缓存命中
当CPU欲访问主存中的某块数据时，Cache中不存在，则称为 缓存不命中

平均访问时间

平均访问时间 = 命中时访问时间 * 命中率 + (1 - 命中率) * 未命中时间

平均访问时间 越接近 命中时访问时间越好

访问效率

在平均访问时间的基础上，扩充出访问效率，即访问效率 = 平均访问时间 / 命中时访问时间

Cache的性能由哪些方面决定

通常来说，Cache 由 块的数量、块的长度决定的。

Cache块的数量

因为Cache的块数量够多，达到主存的块数量，那么Cache除了第一次不命中，后面都是100%命中的。

Cache块的长度

Cache的块长则需要具体情况具体分析，因为Cache块过短，保存的数据量不够多，可以被命中的字少了，那么命中率就下降了；而Cache块过长，缓存中块数减少，可装入的块就少了，很容易出现新块 覆盖 旧块，然后因为新块被使用次数不够多，最终导致命中率下讲；另外块过长，可能会导致一些不相关的数据保存进来，白白浪费空间。

总结

一般来说Cache块通常取4~8个字或字节，也可以取 一个主存周期所能获得的主存信息长度。

CPU、Cache和主存间的交互

Cache存储体

Cache存储体以块为单位与主存交换信息，为了加速主存和Cache之间的调用速度，主存通常采用多体结构，且Cache访存的优先级最高。

主存Cache地址映射变换机构

该机构是将CPU送来的主存地址转换为Cache地址。由于主存和Cache的块内地址都是一样的长度，因此地址映射变换机构主要是将 主存块号 转换成 Cache块号。如果Cache命中，则CPU可以直接访问Cache存储体；如果Cache未命中，CPU会直接访问主存，不仅将该字从主存中取出，同时将它（代指字）所在的主存块一并存入Cache内。如果Cache不可装进，就得采用替换策略；反正，可以直接装入Cache。

替换机构

当Cache内容已满时，需要根据一定的替换算法将Cache内的某个块移除，从而装入新的主存块。

注意：Cache对用户是透明得，用户编程时用到的地址是主存地址，用户根本不知道这些主存是否已调入Cache内。因为将主存块调入Cache的任务全由机器硬件自动完成。

Cache的读写操作

Cache读

Cache读如下图所示

当CPU发出主存地址后，先判断该字是否在Cache中。若命中，直接访问Cache，并将该字送至CPU；若未命中，一方面要访问主存，将该字传送给CPU，与此同时，要将该字所在的主存块装入Cache。

Cache写分为 写通 和 回写两种方法

当CPU对某个Cache块内的数据进行修改时，也将对应的主存块的内容进行修改。

当CPU对某个Cache块内的数据进行修改后，该块被标记为 浊。当Cache发生替换时，将浊的块写回主存中去。

注意，上述的写操作都只针对于单核处理去，对于多核处理器，需要考虑Cache一致性问题

Cache的改进

改进方法有以下两种：

• 增加Cache级数
• 将统一的Cache变成分立的Cache

增加Cache级数

一开始CPU的Cache是直接集成在芯片内部的，这种Cache称为片内Cache(又或是L1 Cache)。片内Cache离CPU近，CPU也不需要占用系统总线就可以直接访问，速度极快。但是片内Cache没有相应数据块时，CPU被迫要访问主存内的信息，访问次数多了，速度相比直接访问Cache就慢下来很多。

所以为了解决CPU与主存间通讯占用总线的问题：在主存与片内缓存之间再加一级缓存，称为 片外缓存，片外缓存不使用系统总线而是 使用一个独立的数据路径。那么从片外缓存调入片内缓存的速度就得到了提高。

所以增加一个层次，即 片外Cache，该Cache置于L1与主存之间，当CPU要获取数据，先访问L1 Cache，如果L1 Cache没有，则访问L2 Cache。

将统一的Cache变成分立的Cache

统一缓存是将数据、指令都存放在同一缓存内；分立缓存是将指令和数据分别存放在指令Cache、数据Cache内。

两种方案如何选择是由 存储结构、指令控制方式两个方面决定的。

如果存储结构是统一的（指令和数据存储在同一主存内），则相应的Cache采用统一缓存；如果主存采用指令、数据分开存储的方案，则相应的Cache采用分立缓存

如果指令控制方式是超前控制或流水控制，一般采用分立缓存。

超前控制指在当前指令执行过程尚未结束时，就提前将下一条准备执行的指令取出，称为 超前取指 或 指令预取；流水线控制指多条指令同时执行，又可视为指令流水。