操作系统基本概念回顾笔记
存储器的层次结构
分如下几个级别:
- 寄存器;
- CPU Cache;
- L1-Cache;
- L2-Cache;
- L3-Cahce;
- 内存;
- SSD/HDD 硬盘
对于存储器,它的速度越快、能耗会越高、而且材料的成本也是越贵的,以至于速度快的存储器的容量都比较小。
寄存器
最靠近 CPU 的控制单元和逻辑计算单元的存储器,就是寄存器了,它使用的材料速度也是最快的,因此价格也是最贵的,那么数量不能很多。
存储器的数量通常在几十到几百之间,每个寄存器可以用来存储一定的字节(byte)的数据。比如:
- 32 位 CPU 中大多数寄存器可以存储
4
个字节; - 64 位 CPU 中大多数寄存器可以存储
8
个字节。
寄存器的访问速度非常快,一般要求在半个 CPU 时钟周期内完成读写,CPU 时钟周期跟 CPU 主频息息相关,比如 2 GHz 主频的 CPU,那么它的时钟周期就是 1/2G,也就是 0.5ns(纳秒)。
CPU Cache
CPU Cache 用的是一种叫 SRAM(*Static Random-Access* Memory,静态随机存储器) 的芯片。
SRAM 之所以叫「静态」存储器,是因为只要有电,数据就可以保持存在,而一旦断电,数据就会丢失了。
CPU 的高速缓存,通常可以分为 L1、L2、L3 这样的三层高速缓存,也称为一级缓存、二级缓存、三级缓存。
L1-Cache
L1 高速缓存的访问速度几乎和寄存器一样快,通常只需要 2~4
个时钟周期,而大小在几十 KB 到几百 KB 不等。
每个 CPU 核心都有一块属于自己的 L1 高速缓存,指令和数据在 L1 是分开存放的,所以 L1 高速缓存通常分成指令缓存和数据缓存。
L2-Cache
L2 高速缓存同样每个 CPU 核心都有,但是 L2 高速缓存位置比 L1 高速缓存距离 CPU 核心 更远,它大小比 L1 高速缓存更大,CPU 型号不同大小也就不同,通常大小在几百 KB 到几 MB 不等,访问速度则更慢,速度在 10~20
个时钟周期。
L3-Cache
L3 高速缓存通常是多个 CPU 核心共用的,位置比 L2 高速缓存距离 CPU 核心 更远,大小也会更大些,通常大小在几 MB 到几十 MB 不等,具体值根据 CPU 型号而定。
访问速度相对也比较慢一些,访问速度在 20~60
个时钟周期。
内存
内存用的芯片和 CPU Cache 有所不同,它使用的是一种叫作 DRAM (*Dynamic Random Access Memory*,动态随机存取存储器) 的芯片。
相比 SRAM,DRAM 的密度更高,功耗更低,有更大的容量,而且造价比 SRAM 芯片便宜很多。
DRAM 存储一个 bit 数据,只需要一个晶体管和一个电容就能存储,但是因为数据会被存储在电容里,电容会不断漏电,所以需要「定时刷新」电容,才能保证数据不会被丢失,这就是 DRAM 之所以被称为「动态」存储器的原因,只有不断刷新,数据才能被存储起来。
DRAM 的数据访问电路和刷新电路都比 SRAM 更复杂,所以访问的速度会更慢,内存速度大概在 200~300
个 时钟周期之间。
SSD/HDD硬盘
SSD(Solid-state disk) 就是我们常说的固体硬盘,结构和内存类似,但是它相比内存的优点是断电后数据还是存在的,而内存、寄存器、高速缓存断电后数据都会丢失。内存的读写速度比 SSD 大概快 10~1000
倍。
当然,还有一款传统的硬盘,也就是机械硬盘(Hard Disk Drive, HDD),它是通过物理读写的方式来访问数据的,因此它访问速度是非常慢的,它的速度比内存慢 10W
倍左右。
CPU Cache 的数据结构和读取过程是什么样的
CPU Cache 的数据是从内存中读取过来的,它是以一小块一小块读取数据的,而不是按照单个数组元素来读取数据的,在 CPU Cache 中的,这样一小块一小块的数据,称为 Cache Line(缓存块)。
比如,有一个 int array[100]
的数组,当载入 array[0]
时,由于这个数组元素的大小在内存只占 4 字节,不足 64 字节,CPU 就会顺序加载数组元素到 array[15]
,意味着 array[0]~array[15]
数组元素都会被缓存在 CPU Cache 中了,因此当下次访问这些数组元素时,会直接从 CPU Cache 读取,而不用再从内存中读取,大大提高了 CPU 读取数据的性能。
事实上,CPU 读取数据的时候,无论数据是否存放到 Cache 中,CPU 都是先访问 Cache,只有当 Cache 中找不到数据时,才会去访问内存,并把内存中的数据读入到 Cache 中,CPU 再从 CPU Cache 读取数据。
这样的访问机制,跟我们使用「内存作为硬盘的缓存」的逻辑是一样的,如果内存有缓存的数据,则直接返回,否则要访问龟速一般的硬盘。
那 CPU 怎么知道要访问的内存数据,是否在 Cache 里?如果在的话,如何找到 Cache 对应的数据呢?我们从最简单、基础的直接映射 Cache(*Direct Mapped Cache*) 说起,来看看整个 CPU Cache 的数据结构和访问逻辑。
前面,我们提到 CPU 访问内存数据时,是一小块一小块数据读取的,具体这一小块数据的大小,取决于 coherency_line_size
的值,一般 64 字节。在内存中,这一块的数据我们称为内存块(*Block*),读取的时候我们要拿到数据所在内存块的地址。
对于直接映射 Cache 采用的策略,就是把内存块的地址始终「映射」在一个 CPU Line(缓存块) 的地址,至于映射关系实现方式,则是使用「取模运算」,取模运算的结果就是内存块地址对应的 CPU Line(缓存块) 的地址。
举个例子,内存共被划分为 32 个内存块,CPU Cache 共有 8 个 CPU Line,假设 CPU 想要访问第 15 号内存块,如果 15 号内存块中的数据已经缓存在 CPU Line 中的话,则是一定映射在 7 号 CPU Line 中,因为 15 % 8
的值是 7。
机智的你肯定发现了,使用取模方式映射的话,就会出现多个内存块对应同一个 CPU Line,比如上面的例子,除了 15 号内存块是映射在 7 号 CPU Line 中,还有 7 号、23 号、31 号内存块都是映射到 7 号 CPU Line 中。
因此,为了区别不同的内存块,在对应的 CPU Line 中我们还会存储一个组标记(Tag)。这个组标记会记录当前 CPU Line 中存储的数据对应的内存块,我们可以用这个组标记来区分不同的内存块。
除了组标记信息外,CPU Line 还有两个信息:
- 一个是,从内存加载过来的实际存放数据(*Data*)。
- 另一个是,有效位(*Valid bit*),它是用来标记对应的 CPU Line 中的数据是否是有效的,如果有效位是 0,无论 CPU Line 中是否有数据,CPU 都会直接访问内存,重新加载数据。
CPU 在从 CPU Cache 读取数据的时候,并不是读取 CPU Line 中的整个数据块,而是读取 CPU 所需要的一个数据片段,这样的数据统称为一个字(*Word*)。那怎么在对应的 CPU Line 中数据块中找到所需的字呢?答案是,需要一个偏移量(Offset)。
因此,一个内存的访问地址,包括组标记、CPU Line 索引、偏移量这三种信息,于是 CPU 就能通过这些信息,在 CPU Cache 中找到缓存的数据。而对于 CPU Cache 里的数据结构,则是由索引 + 有效位 + 组标记 + 数据块组成。
如果内存中的数据已经在 CPU Cahe 中了,那 CPU 访问一个内存地址的时候,会经历这 4 个步骤:
- 根据内存地址中索引信息,计算在 CPU Cahe 中的索引,也就是找出对应的 CPU Line 的地址;
- 找到对应 CPU Line 后,判断 CPU Line 中的有效位,确认 CPU Line 中数据是否是有效的,如果是无效的,CPU 就会直接访问内存,并重新加载数据,如果数据有效,则往下执行;
- 对比内存地址中组标记和 CPU Line 中的组标记,确认 CPU Line 中的数据是我们要访问的内存数据,如果不是的话,CPU 就会直接访问内存,并重新加载数据,如果是的话,则往下执行;
- 根据内存地址中偏移量信息,从 CPU Line 的数据块中,读取对应的字。
到这里,相信你对直接映射 Cache 有了一定认识,但其实除了直接映射 Cache 之外,还有其他通过内存地址找到 CPU Cache 中的数据的策略,比如**全相连 Cache (Fully Associative Cache)、组相连 Cache (Set Associative Cache)**等.
如何写出让CPU执行更快的代码?
对于提升数据缓存命中率:
遇到遍历数组的情况时,按照内存布局顺序访问
对于提升指令缓存命中率:
有一个元素为 0 到 100 之间随机数字组成的一维数组, 接下来,对这个数组做两个操作:
- 第一个操作,循环遍历数组,把小于 50 的数组元素置为 0;
- 第二个操作,将数组排序;
那么问题来了,你觉得先遍历再排序速度快,还是先排序再遍历速度快呢?
在回答这个问题之前,我们先了解 CPU 的分支预测器。对于 if 条件语句,意味着此时至少可以选择跳转到两段不同的指令执行,也就是 if 还是 else 中的指令。那么,如果分支预测可以预测到接下来要执行 if 里的指令,还是 else 指令的话,就可以「提前」把这些指令放在指令缓存中,这样 CPU 可以直接从 Cache 读取到指令,于是执行速度就会很快。
当数组中的元素是随机的,分支预测就无法有效工作,而当数组元素都是是顺序的,分支预测器会动态地根据历史命中数据对未来进行预测,这样命中率就会很高。
因此,先排序再遍历速度会更快,这是因为排序之后,数字是从小到大的,那么前几次循环命中 if < 50
的次数会比较多,于是分支预测就会缓存 if
里的 array[i] = 0
指令到 Cache 中,后续 CPU 执行该指令就只需要从 Cache 读取就好了。
对于提升多核 CPU 的缓存命中率:
在单核 CPU,虽然只能执行一个线程,但是操作系统给每个线程分配了一个时间片,时间片用完了,就调度下一个线程,于是各个线程就按时间片交替地占用 CPU,从宏观上看起来各个线程同时在执行。
而现代 CPU 都是多核心的,线程可能在不同 CPU 核心来回切换执行,这对 CPU Cache 不是有利的,虽然 L3 Cache 是多核心之间共享的,但是 L1 和 L2 Cache 都是每个核心独有的,如果一个线程在不同核心来回切换,各个核心的缓存命中率就会受到影响,相反如果线程都在同一个核心上执行,那么其数据的 L1 和 L2 Cache 的缓存命中率可以得到有效提高,缓存命中率高就意味着 CPU 可以减少访问 内存的频率。
当有多个同时执行「计算密集型」的线程,为了防止因为切换到不同的核心,而导致缓存命中率下降的问题,我们可以把线程绑定在某一个 CPU 核心上,这样性能可以得到非常可观的提升。
总结
当 CPU 访问数据的时候,先是访问 CPU Cache,如果缓存命中的话,则直接返回数据,就不用每次都从内存读取速度了。因此,缓存命中率越高,代码的性能越好。
但需要注意的是,当 CPU 访问数据时,如果 CPU Cache 没有缓存该数据,则会从内存读取数据,但是并不是只读一个数据,而是一次性读取一块一块的数据存放到 CPU Cache 中,之后才会被 CPU 读取。
内存地址映射到 CPU Cache 地址里的策略有很多种,其中比较简单是直接映射 Cache,它巧妙的把内存地址拆分成「索引 + 组标记 + 偏移量」的方式,使得我们可以将很大的内存地址,映射到很小的 CPU Cache 地址里。
要想写出让 CPU 跑得更快的代码,就需要写出缓存命中率高的代码,CPU L1 Cache 分为数据缓存和指令缓存,因而需要分别提高它们的缓存命中率:
- 对于数据缓存,我们在遍历数据的时候,应该按照内存布局的顺序操作,这是因为 CPU Cache 是根据 CPU Cache Line 批量操作数据的,所以顺序地操作连续内存数据时,性能能得到有效的提升;
- 对于指令缓存,有规律的条件分支语句能够让 CPU 的分支预测器发挥作用,进一步提高执行的效率;
另外,对于多核 CPU 系统,线程可能在不同 CPU 核心来回切换,这样各个核心的缓存命中率就会受到影响,于是要想提高线程的缓存命中率,可以考虑把线程绑定 CPU 到某一个 CPU 核心。