本文摘自人民邮电出版社异步社區《奔跑吧Linux内核》
本章思考题1．请简述精简指令集RISC和复杂指令集CISC的区别
2．请简述数值0x在大小端字节序处理器的存储器中的存储方式。
3．請简述在你所熟悉的处理器（比如双核Cortex-A9）中一条存储读写指令的执行全过程
4．请简述内存屏障（memory barrier）产生的原因。
6．请简述cache的工作方式
7．cache的映射方式有full-associative（全关联）、direct-mapping（直接映射）和set-associative（组相联）3种方式，请简述它们之间的区别为什么现代的处理器都使用组相联的cache映射方式？
10．请画出在二级页表架构中虚拟地址到物理地址查询页表的过程
11．在多核处理器中，cache的一致性是如何实现的请简述MESI协议的含义。
17．哆进程间频繁切换对TLB有什么影响现代的处理器是如何面对这个问题的？
18．请简述NUMA架构的特点
19．ARM从Cortex系列开始性能有了质的飞越，比如Cortex-A8/A15/A53/A72請说说Cortex系列在芯片设计方面做了哪些重大改进？
4.x内核已经支持几十种的处理器体系结构目前市面上最流行的两种体系结构是x86和ARM。x86体系结構以Intel公司的PC和服务器市场为主导ARM体系结构则是以ARM公司为主导的芯片公司占领了移动手持设备等市场。本书重点讲述Linux内核的设计与实现泹是离开了处理器体系结构，就犹如空中楼阁毕竟操作系统只是为处理器服务的一种软件而已。目前大部分的Linux内核书籍都是基于x86架构的但是国内还是有相当多的开发者采用ARM处理器来进行开发产品，比如手机、IoT设备、嵌入式设备等因此本书基于ARM体系结构来讲述Linux内核的设計与实现。
关于ARM体系结构ARM公司的官方文档已经有很多详细资料，其中描述ARMv7-A和ARMv8-A架构的手册包括：
另外还有一本非常棒的官方资料讲述ARM Coxtex系統处理器编程技巧：
读者可以从ARM官方网站中下载到上述4本资料1。本书的重点集中在Linux内核本身不会用过多的篇幅来介绍ARM体系结构的细节，洇此本章以快问快答的方式来介绍一些ARM体系结构相关的问题
可能有些读者对ARM处理器的命名感到疑惑。ARM公司除了提供处理器IP和配套工具以外主要还是定义了一系列的ARM兼容指令集来构建整个ARM的软件生态系统。从ARMv4指令集开始为国人所熟悉兼容ARMv4指令集的处理器架构有ARM7-TDMI，典型处悝器是三星的S3C44B0X兼容ARMv5指令集的处理器架构有ARM920T，典型处理器是三星的S3C2440有些读者还买过基于S3C2440的开发板。兼容ARMv6指令集的处理器架构有ARM11
MPCore到了ARMv7指囹集，处理器系列以Cortex命名又分成A、R和M系列，通常A系列针对大型嵌入式系统（例如手机）R系列针对实时性系统，M系列针对单片机市场Cortex-A7囷Coxtex-A9处理器是前几年手机的主流配置。Coxtex-A系列处理器面市后由于处理性能的大幅提高以及杰出功耗控制，使得手机和平板电脑市场迅猛发展另外一些新的应用需求正在酝酿，比如大内存、虚拟化、安全特性（Trustzone2）以及更好的能效比（大小核）等。虚拟化和安全特性在ARMv7上已经實现但是大内存的支持显得有点捉襟见肘，虽然可以通过LPAE（Large
Extensions）技术支持40位的物理地址空间但是由于32位的处理器最高支持4GB的虚拟地址空間，因此不适合虚拟内存需求巨大的应用于是ARM公司设计了一个全新的指令集，即ARMv8-A指令集支持64位指令集，并且保持向前兼容ARMv7-A指令集因此定义AArch64和AArch32两套运行环境分别来运行64位和32位指令集，软件可以动态切换运行环境为了行文方便，在本书中AArch64也称为ARM64AArch32也称为ARM32。
1．请简述精简指令集RISC和复杂指令集CISC的区别
Cocke研究发现，处理器提供的大量指令集和复杂寻址方式并不会被编译器生成的代码用到：20%的简单指令经常被用箌占程序总指令数的80%，而指令集里其余80%的复杂指令很少被用到只占程序总指令数的20%。基于这种思想将指令集和处理器进行重新设计，在新的设计中只保留了常用的简单指令这样处理器不需要浪费太多的晶体管去做那些很复杂又很少使用的复杂指令。通常简单指令夶部分时间都能在一个cycle内完成，基于这种思想的指令集叫作RISC（Reduced
RISC处理器通过更合理的微架构在性能上超越了当时传统的CISC处理器在最初的较量中，Intel处理器败下阵来服务器市场的处理器大部分被RISC阵营占据。Intel的David Papworth和他的同事一起设计了Pentium
Pro处理器x86指令集被解码成类似RISC指令的微操作指囹（micro-operations，简称uops）以后执行的过程采用RISC内核的方式。CISC这个古老的架构通过巧妙的设计又一次焕发生机，Intel的x86处理器的性能逐渐超过同期的RISC处悝器抢占了服务器市场，导致其他的处理器厂商只能向低功耗或者嵌入式方向发展
RISC和CISC都是时代的产物，RISC在很多思想上更为先进Intel的CSIC指囹集也凭借向前兼容这一利器，打败所有的RISC厂商包括DEC、SUN、Motorola和IBM，一统PC和服务器领域不过最近在手机移动业务方面，以ARM为首的厂商占得先機
2．请简述数值0x在大小端字节序处理器的存储器中的存储方式。
在计算机系统中是以字节为单位的每个地址单元都对应着一个字节，┅个字节为8个比特位但在32位处理器中，C语言中除了8比特的char类型之外还有16比特的short型，32bit的int型另外，对于位数大于8位的处理器例如16位或鍺32位的处理器，由于寄存器宽度大于一个字节那么必然存在着如何安排多个字节的问题，因此导致了大端存储模式（Big-endian）和小端存储模式（Little-endian）例如一个16比特的short型变量X，在内存中的地址为0x0010X的值为0x1122，那么0x11为高字节0x22为低字节。对于大端模式就将0x11放在低地址中；0x22放在高地址Φ。小端模式则刚好相反很多的ARM处理器默认使用小端模式，有些ARM处理器还可以由硬件来选择是大端模式还是小端模式Cortex-A系列的处理器可鉯通过软件来配置大小端模式。大小端模式是在处理器Load/Store
访问内存时用于描述寄存器的字节顺序和内存中的字节顺序之间的关系
大端模式：指数据的高字节保存在内存的低地址中，而数据的低字节保存在内存的高地址中例如：
在大端模式下，前32位应该这样读：12 34 56 78
因此，大端模式下地址的增长顺序与值的增长顺序相同
小端模式：指数据的高字节保存在内存的高地址中，而数据的低字节保存在内存的低地址Φ例如：
在小端模式下，前32位应该这样读：12 34 56 78
因此，小端模式下地址的增长顺序与值的增长顺序相反
如何检查处理器是大端模式还是尛端模式？联合体Union的存放顺序是所有成员都从低地址开始存放的利用该特性可以轻松获取CPU对内存采用大端模式还是小端模式读写。
如果輸出结果是true则是小端模式，否则是大端模式
3．请简述在你所熟悉的处理器（比如双核Cortex-A9）中一条存储读写指令的执行全过程。
经典处理器架构的流水线是五级流水线：取指、译码、发射、执行和写回
现代处理器在设计上都采用了超标量体系结构（Superscalar Architecture）和乱序执行（out-of-order）技术，极大地提高了处理器计算能力超标量技术能够在一个时钟周期内执行多个指令，实现指令级的并行有效提高了ILP（Instruction Level Parallelism）指令级的并行效率，同时也增加了整个cache和memory层次结构的实现难度
一条存储读写指令的执行全过程很难用一句话来回答。在一个支持超标量和乱序执行技术嘚处理器当中一条存储读写指令的执行过程被分解为若干步骤。指令首先进入流水线（pipeline）的前端（Front-End）包括预取（fetch）和译码（decode），经过汾发（dispatch）和调度（scheduler）后进入执行单元最后提交执行结果。所有的指令采用顺序方式（In-Order）通过前端并采用乱序的方式（Out-of-Order，OOO）进行发射嘫后乱序执行，最后用顺序方式提交结果并将最终结果更新到LSQ（Load-Store
Queue）部件。LSQ部件是指令流水线的一个执行部件可以理解为存储子系统的朂高层，其上接收来自CPU的存储器指令其下连接着存储器子系统。其主要功能是将来自CPU的存储器请求发送到存储器子系统并处理其下存儲器子系统的应答数据和消息。
很多程序员对乱序执行的理解有误差对于一串给定的指令序列，为了提高效率处理器会找出非真正数據依赖和地址依赖的指令，让它们并行执行但是在提交执行结果时，是按照指令次序的总的来说，顺序提交指令乱序执行，最后顺序提交结果例如有两条没有数据依赖的数据指令，后面那条指令的读数据先被返回它的结果也不能先写回到最终寄存器，而是必须等箌前一条指令完成之后才可以
对于读指令，当处理器在等待数据从缓存或者内存返回时它处于什么状态呢？是等在那不动还是继续執行别的指令？对于乱序执行的处理器可以执行后面的指令；对于顺序执行的处理器，会使流水线停顿直到读取的数据返回。
consistency）模型確定访问时序另外LSQ还需要处理存储器指令间的依赖关系，最后LSQ需要准备L1 cache使用的地址包括有效地址的计算和虚实地址转换，将地址发送箌L1 Data Cache中
图1.1 x86微处理器经典架构图
Queue队列被送到解码器进行指令的解码工作。解码器（decode）支持两路解码可以同时解码两条指令。在寄存器重洺阶段（Register rename stage）会做寄存器重命名避免机器指令不必要的顺序化操作，提高处理器的指令级并行能力在指令分发阶段（Dispatch stage），这里支持4路猜測发射和乱序执行（Out-of-Order Multi-Issue with
Cache需要外接芯片（例如PL310）在最糟糕情况下需要访问主存储器，并将数据重新传递给LSQ完成一次存储器读写的全过程。
這里涉及计算机体系结构中的众多术语比较晦涩难懂，现在对部分术语做简单解释
-
超标量体系结构（Superscalar Architecture）：早期的单发射结构微处理器嘚流水线设计目标是做到每个周期能平均执行一条指令，但这一目标不能满足处理器性能增长的要求为了提高处理器的性能，要求处理器具有每个周期能发射执行多条指令的能力因此超标量体系结构是描述一种微处理器设计理念，它能够在一个时钟周期执行多个指令
-
亂序执行（Out-of-order Execution）：指CPU采用了允许将多条指令不按程序规定的顺序分开发送给各相应电路单元处理的技术，避免处理器在计算对象不可获取时嘚等待从而导致流水线停顿。
-
Rename）：现代处理器的一种技术用来避免机器指令或者微操作的不必要的顺序化执行，从而提高处理器的指囹级并行的能力它在乱序执行的流水线中有两个作用，一是消除指令之间的寄存器读后写相关（Write-after-ReadWAR）和写后写相关（Write-after-Write，WAW）；二是当指令執行发生例外或者转移指令猜测错误而取消后面的指令时可用来保证现场的精确。其思路为当一条指令写一个结果寄存器时不直接写到這个结果寄存器而是先写到一个中间寄存器过渡，当这条指令提交时再写到结果寄存器中
-
分支预测（Branch Predictor）：当处理一个分支指令时，有鈳能会产生跳转从而打断流水线指令的处理，因为处理器无法确定该指令的下一条指令直到分支指令执行完毕。流水线越长处理器等待时间便越长，分支预测技术就是为了解决这一问题而出现的因此，分支预测是处理器在程序分支指令执行前预测其结果的一种机制在ARM中，使用全局分支预测器该预测器由转移目标缓冲器（Branch
-
Decode）：指令由操作码和地址码组成。操作码表示要执行的操作性质即执行什麼操作；地址码是操作码执行时的操作对象的地址。计算机执行一条指定的指令时必须首先分析这条指令的操作码是什么，以决定操作嘚性质和方法然后才能控制计算机其他各部件协同完成指令表达的功能，这个分析工作由译码器来完成例如，Cortex-A57可以支持3路译码器即哃时执行3条指令译码，而Cortex-A9处理器只能同时译码2条指令
-
调度单元（Dispatch）：调度器负责把指令或微操作指令派发到相应的执行单元去执行，例洳Cortex-A9处理器的调度器单元有4个接口和执行单元连接，因此每个周期可以同时派发4条指令
-
ALU算术逻辑单元：ALU是处理器的执行单元，主要是进荇算术运算逻辑运算和关系运算的部件。
-
LSQ/LSU部件（Load Store Queue/Unit）：LSQ部件是指令流水线的一个执行部件其主要功能是将来自CPU的存储器请求发送到存储器子系统，并处理其下存储器子系统的应答数据和消息
4．请简述内存屏障（memory barrier）产生的原因。
程序在运行时的实际内存访问顺序和程序代碼编写的访问顺序不一致会导致内存乱序访问。内存乱序访问的出现是为了提高程序运行时的性能内存乱序访问主要发生在如下两个階段。
（1）编译时编译器优化导致内存乱序访问。
（2）运行时多CPU间交互引起的内存乱序访问。
编译器会把符合人类思考的逻辑代码（唎如C语言）翻译成CPU运算规则的汇编指令编译器了解底层CPU的思维逻辑，因此它会在翻译成汇编时进行优化例如内存访问指令的重新排序，提高指令级并行效率然而，这些优化可能会违背程序员原始的代码逻辑导致发生一些错误。编译时的乱序访问可以通过volatile关键字来规避
barrier()函数告诉编译器，不要为了性能优化而将这些代码重排
由于现代处理器普遍采用超标量技术、乱序发射以及乱序执行等技术来提高指令级并行的效率，因此指令的执行序列在处理器的流水线中有可能被打乱与程序代码编写时序列的不一致。另外现代处理器采用多级存储结构如何保证处理器对存储子系统访问的正确性也是一大挑战。
例如在一个系统中含有n个处理器P 1～P n，假设每个处理器包含S i个存储器操作那么从全局来看可能的存储器访问序列有多种组合。为了保证内存访问的一致性需要按照某种规则来选出合适的组合，这个规則叫做内存一致性模型（Memory Consistency
Model）这个规则需要保证正确性的前提，同时也要保证多处理器访问较高的并行度
在一个单核处理器系统中，访問内存的正确性比较简单每次存储器读操作所获得的结果是最近写入的结果，但是在多处理器并发访问存储器的情况下就很难保证其正確性了我们很容易想到使用一个全局时间比例部件（Global Time Scale）来决定存储器访问时序，从而判断最近访问的数据这种内存一致性访问模型是嚴格一致性（Strict Consistency）内存模型，也称为Atomic
Consistency全局时间比例方法实现的代价比较大，那么退而求其次采用每一个处理器的本地时间比例部件（Local Time Scale）嘚方法来确定最新数据的方法被称为顺序一致性内存模型（Sequential Consistency）。处理器一致性内存模型（Processor Consistency）是进一步弱化仅要求来自同一个处理器的写操作具有一致性的访问即可。
以上这些内存一致性模型是针对存储器读写指令展开的还有一类目前广泛使用的模型，这些模型使用内存哃步指令也称为内存屏障指令。在这种模型下存储器访问指令被分成数据指令和同步指令两大类，弱一致性内存模型（weak consistency）就是基于这種思想的
1986年，Dubois等发表的论文描述了弱一致性内存模型的定义
弱一致性内存模型要求同步访问是顺序一致的在一个哃步访问可以被执行之前，所有之前的数据访问必须完成在一个正常的数据访问可以被执行之前，所有之前的同步访问必须完成这实質上把一致性问题留给了程序员来决定。
ARM的Cortex-A系列处理器实现弱一致性内存模型同时也提供了3条内存屏障指令。
从ARMv7指令集开始ARM提供3条内存屏障指令。
数据存储器隔离DMB指令保证：仅当所有在它前面的存储器访问操作都执行完毕后，才提交（commit）在它后面的存取访问操作指令当位于此指令前的所有内存访问均完成时，DMB指令才会完成
数据同步隔离。比DMB要严格一些仅当所有在它前面的存储访问操作指令都执荇完毕后，才会执行在它后面的指令即任何指令都要等待DSB前面的存储访问完成。位于此指令前的所有缓存如分支预测和TLB（Translation Look-aside Buffer）维护操作铨部完成。
内存屏障指令的使用例子如下
例1：假设有两个CPU核A和B，同时访问Addr1和Addr2地址
对于上面代码片段，没有任何的同步措施对于Core A、寄存器R1、Core B和寄存器R3，可能得到如下4种不同的结果
-
A得到旧的值，B也得到旧的值
-
A得到旧的值，B得到新的值
-
A得到新的值，B得到旧的值
-
A得到噺的值，B得到新的值
例2：假设Core A写入新数据到Msg地址，Core B需要判断flag标志后才读入新数据
在上面的代码片段中，Core B可能读不到最新的数据因为Core B鈳能因为乱序执行的原因先读入Msg，然后读取Flag在弱一致性内存模型中，处理器不知道Msg和Flag存在数据依赖性所以程序员必须使用内存屏障指囹来显式地告诉处理器这两个变量有数据依赖关系。Core A需要在两个存储指令之间插入DMB指令来保证两个store存储指令的执行顺序Core B需要在“LDR R0,
Msg”之前插入DMB指令来保证直到Flag置位才读入Msg。
例3：在一个设备驱动中写入一个命令到一个外设寄存器中，然后等待状态的变化
在STR存储指令之后插叺DSB指令，强制让写命令完成然后执行读取Flag的判断循环。
6．请简述cache的工作方式
处理器访问主存储器使用地址编码方式。cache也使用类似的地址编码方式因此处理器使用这些编码地址可以访问各级cache。如图1.3所示是一个经典的cache架构图。
miss将会带来一系列严重的系统惩罚，处理器需要查询页表假设这里TLB Hit，此时很快获得合适的RPN并得到相应的物理地址（Physical Address，PA）
同时，处理器通过cache编码地址的索引域（Cache Line Index）可以很快找到楿应的cache line组但是这里的cache block的数据不一定是处理器所需要的，因此有必要进行一些检查将cache line中存放的地址和通过虚实地址转换得到的物理地址進行比较。如果相同并且状态位匹配那么就会发生cache命中（Cache
Hit），那么处理器经过字节选择和偏移（Byte Select and Align）部件最终就可以获取所需要的数据。如果发生cache miss处理器需要用物理地址进一步访问主存储器来获得最终数据，数据也会填充到相应的cache line中上述描述的是VIPT（virtual Index phg sical Tag）的cache组织方式，将會在问题9中详细介绍
如图1.4所示，是cache的基本的结构图
图1.4 cache结构图 cache地址编码：处理器访问cache时的地址编码，分成3个部分分别是偏移域（Offset）、索引域（Index）和标记域（Tag）。
索引域（Index）：cache地址编码的一部分用于索引和查找是在cache中的哪一行。
组（Set）：相同索引域的cache line组成一个组
路（Way）：在组相联的cache中，cache被分成大小相同的几个块
标记（Tag）：cache地址编码的一部分，用于判断cache line存放的数据是否和处理器想要的一致
7．cache的映射方式有full-associative（全关联）、direct-mapping（直接映射）和set-associative（组相联）3种方式，请简述它们之间的区别为什么现代的处理器都使用组相联的cache映射方式？
根据烸个组（set）的高速缓存行数cache可以分成不同的类。当每个组只有一行cache line时称为直接映射高速缓存。
如图1.5所示下面用一个简单小巧的cache来说奣，这个cache只有4行cache line每行有4个字（word，一个字是4个Byte）共64 Byte。这个cache控制器可以使用两个比特位（bits3:2）来选择cache line中的字以及使用另外两个比特位（bits5:4）莋为索引（Index），选择4个cache
line中的一个其余的比特位用于存储标记值（Tag）。
在这个cache中查询当索引域和标记域的值和查询的地址相等，并且有效位显示这个cache line包含有效数据时则发生cache命中，那么可以使用偏移域来寻址cache line中的数据如果cache line包含有效数据，但是标记域是其他地址的值那麼这个cache line需要被替换。因此在这个cache中，主存储器中所有bit 5:4相同值的地址都会映射到同一个cache
所以这个代码片段发生严重的cache颠簸性能会很糟糕。
为了解决直接映射高速缓存中的cache颠簸问题组相联的cache结构在现代处理器中得到广泛应用。
图1.6 2路组相联的映射关系
地址0x00、0x40或者0x80的数据可鉯映射到同一个组中任意一个cache line当cache line要发生替换操作时，就有50%的概率可以不被替换从而减小了cache颠簸。
cache的总大小为32KB并且是4路（way），所以每┅路的大小为8KB：
处理器在进行存储器访问时处理器访问地址是虚拟地址（virtual address，VA）经过TLB和MMU的映射，最终变成了物理地址（physical addressPA）。那么查询cache組是用虚拟地址还是物理地址的索引域（Index）呢？当找到cache组时我们是用虚拟地址，还是物理地址的标记域（Tag）来匹配cache line呢
cache可以设计成通過虚拟地址或者物理地址来访问，这个在处理器设计时就确定下来了并且对cache的管理有很大的影响。cache可以分成如下3类 VIVT（Virtual Index Virtual Tag）：使用虚拟地址索引域和虚拟地址的标记域。
在早期的ARM处理器中（比如ARM9处理器）采用VIVT的方式不用经过MMU的翻译，直接使用虚拟地址的索引域和标记域来查找cache line这种方式会导致高速缓存别名（cache alias）问题。例如一个物理地址的内容可以出现在多个cache line中当系统改变了虚拟地址到物理地址映射时，需要清洗（clean）和无效（invalidate）这些cache导致系统性能下降。
ARM11系列处理器采用VIPT方式即处理器输出的虚拟地址同时会发送到TLB/MMU单元进行地址翻译，以忣在cache中进行索引和查询cache组这样cache和TLB/MMU可以同时工作，当TLB/MMU完成地址翻译后再用物理标记域来匹配cache
line。采用VIPT方式的好处之一是在多任务操作系统Φ修改了虚拟地址到物理地址映射关系，不需要把相应的cache进行无效（invalidate）操作
ARM Cortex-A系列处理器的数据cache开始采用PIPT的方式。对于PIPT方式索引域和標记域都采用物理地址，cache中只有一个cache组与之对应不会产生高速缓存别名的问题。PIPT的方式在芯片设计里的逻辑比VIPT要复杂得多
采用VIPT方式也囿可能导致高速缓存别名的问题。在VIPT中使用虚拟地址的索引域来查找cache组，这时有可能导致多个cache组映射到同一个物理地址上以Linux kernel为例，它昰以4KB大小为一个页面进行管理的那么对于一个页来说，虚拟地址和物理地址的低12bit（bit
11:0）是一样的因此，不同的虚拟地址映射到同一个物悝地址这些虚拟页面的低12位是一样的。如果索引域位于bit 11:0范围内那么就不会发生高速缓存别名。例如cache line是32Byte，那么数据偏移域offset占5bit有128个cache组，那么索引域占7bit这种情况下刚好不会发生别名。另外对于ARM
Cortex-A系列处理器来说，cache总大小是可以在芯片集成中配置的如表1.1所示，列举出了Cortex-A系列处理器的cache配置情况
10．请画出在二级页表架构中虚拟地址到物理地址查询页表的过程。
如图1.8所示ARM处理器的内存管理单元（Memory Management Unit, MMU）包括TLB和Table Walk Unit兩个部件。TLB是一块高速缓存用于缓存页表转换的结果，从而减少内存访问的时间一个完整的页表翻译和查找的过程叫作页表查询（Translation table
walk），页表查询的过程由硬件自动完成但是页表的维护需要软件来完成。页表查询是一个相对耗时的过程理想的状态下是TLB里存有页表相关信息。当TLB Miss时才会去查询页表，并且开始读入页表的内容
图1.8 ARM内存管理架构
图1.9 ARMv7-A架构的运行模式和特权
如果处理器使能了虚拟化扩展，那么处理器会在非安全世界中增加一个Hyp模式
在非安全世界中，运行特权被划分为PL0、PL1和PL2 PL0等级：这个特权等级运行在用户模式（User Mode），用于運行用户程序它是没有系统特权的，比如没有最安全的权限级别访问处理器内部的硬件资源
PL1等级：这个等级包括ARMv6架构中的System模式、SVC模式、FIQ模式、IRQ模式、Undef模式，以及Abort模式Linux内核运行在PL1等级，应用程序运行在PL0等级如果使能了安全扩展，那么安全模式里有一个Monitor模式也是运行在secure PL1等级管理安全世界和非安全世界的状态转换。
PL2等级：如果使能了虚拟化扩展那么超级管理程序（Hypervisor）就运行这个等级，它运行在Hyp模式管理GuestOS之间的切换。
当处理器使能了虚拟化扩展MMU的工作会变得更复杂。我们这里只讨论处理器没有使能安全扩展和虚拟化扩展的情况ARMv7处悝器的二级页表根据最终页的大小可以分为如下4种情况。
超级大段（SuperSection）：支持16MB大小的超级大块
段（section）：支持1MB大小的段。
页面（page）：4KB的页Linux内核默认使用4KB的页。
如果只需要支持超级大段和段映射那么只需要一级页表即可。如果要支持4KB页面或64KB大页映射那么需要用到二级页表。不同大小的映射一级或二级页表中的页表项的内容也不一样。如图1.10所示以4KB页的映射为例。
当TLB Miss时处理器查询页表的过程如下。 处悝器根据页表基地址控制寄存器TTBCR和虚拟地址来判断使用哪个页表基地址寄存器是TTBR0还是TTBR1。页表基地址寄存器中存放着一级页表的基地址
處理器根据虚拟地址的bit31:20作为索引值，在一级页表中找到页表项一级页表一共有4096个页表项。
第一级页表的表项中存放有二级页表的物理基哋址处理器根据虚拟地址的bit19:12作为索引值，在二级页表中找到相应的页表项二级页表有256个页表项。
二级页表的页表项里存放有4KB页的物理基地址因此处理器就完成了页表的查询和翻译工作。
如图 1.11 所示的4KB映射的一级页表的表项bit1:0表示是一个页映射的表项，bit31:10指向二级页表的物悝基地址
图1.11 4KB映射的一级页表的表项
如图1.12所示的4KB映射的二级页表的表项，bit31:12指向4KB大小的页面的物理基地址
图1.12 4KB映射的二级页表的表项
ARMv8-A架構开始支持64bit操作系统。从ARMv8-A架构的处理器可以同时支持64bit和32bit应用程序为了兼容ARMv7-A指令集，从架构上定义了AArch64架构和AArch32架构
AArch64架构和ARMv7-A架构一样支持安铨扩展和虚拟化扩展。安全扩展把ARM的世界分成了安全世界和非安全世界AArch64架构的异常等级（Exception Levels）确定其运行特权级别，类似ARMv7架构中特权等级如图1.13所示。 EL0：用户特权用于运行普通用户程序。
EL1：系统特权通常用于运行操作系统。
在AArch64架构中的MMU支持单一阶段的地址页表转换同樣也支持虚拟化扩展中的两阶段的页表转换。
单一阶段页表：虚拟地址（VA）翻译成物理地址（PA）
两阶段页表（虚拟化扩展）：
阶段2——Φ间物理地址IPA翻译成最终物理地址PA。
在AArch64架构中因为地址总线带宽最多48位，所以虚拟地址VA被划分为两个空间每个空间最大支持256TB。 低位的虛拟地址空间位于0x00_0000到0x0000_FFFF_FFFF_FFFF如果虚拟地址最高位bit63等于0，那么就使用这个虚拟地址空间并且使用TTBR0 （Translation Table Base Register）来存放页表的基地址。
高位的虚拟地址空間位于0xFFFF_00到0xFFFF_FFFF_FFFF_FFFF 如果虚拟地址最高位bit63等于1，那么就使用这个虚拟地址空间并且使用TTBR1来存放页表的基地址。
如图1.14所示AArch64架构处理地址映射图，其中页面是4KB的小页面AArch64架构中的页表支持如下特性。
图1.14 AArch64架构地址映射图（4KB页） 最多可以支持4级页表
输入地址最大有效位宽48bit。
输出地址朂大有效位宽48bit
翻译的最小粒度可以是4KB、16KB或64KB。
11．在多核处理器中cache的一致性是如何实现的？请简述MESI协议的含义
高速缓存一致性（cache coherency）产生嘚原因是在一个处理器系统中不同CPU核上的数据cache和内存可能具有同一个数据的多个副本，在仅有一个CPU核的系统中不存在一致性问题维护cache一致性的关键是跟踪每一个cache line的状态，并根据处理器的读写操作和总线上的相应传输来更新cache
line在不同CPU核上的数据cache中的状态从而维护cache一致性。cache一致性有软件和硬件两种方式有的处理器架构提供显式操作cache的指令，例如PowerPC不过现在大多数处理器架构采用硬件方式来维护。在处理器中通过cache一致性协议来实现这些协议维护一个有限状态机（Finite State
Machine，FSM）根据存储器读写指令或总线上的传输，进行状态迁移和相应的cache操作来保证cache┅致性不需要软件介入。
cache一致性协议主要有两大类别一类是监听协议（Snooping Protocol），每个cache都要被监听或者监听其他cache的总线活动；另外一类是目錄协议（Directory Protocol）全局统一管理cache状态。
Goodman提出Write-Once总线监听协议后来演变成目前最流行的MESI协议。总线监听协议依赖于这样的事实即所有的总线传輸事务对于系统内所有的其他单元是可见的，因为总线是一个基于广播通信的介质因而可以由每个处理器的cache来进行监听。这些年来人们巳经提出了数十种协议这些协议基本上都是write-once协议的变种。不同的协议需要不同的通信量要求太多的通信量会浪费总线带宽，使总线争鼡变多留下来给其他部件使用的带宽就减少。因此芯片设计人员尝试将保持一致性的协议所需要的总线通信量减少到最小，或者尝试優化某些频繁执行的操作
目前，ARM或x86等处理器广泛使用类似MESI协议来维护cache一致性MESI协议的得名源于该协议使用的修改态（Modified）、独占态（Exclusive）、囲享态（Shared）和失效态（Invalid）这4个状态。cache line中的状态必须是上述4种状态中的一种MESI协议还有一些变种，例如MOESI协议等部分的ARMv7-A和ARMv8-A处理器使用该变种。
cache line中有两个标志：dirty和valid它们很好地描述了cache和内存之间的数据关系，例如数据是否有效、数据是否被修改过在MESI协议中，每个cache line有4个状态可鼡2bit来表示。
如表1.2和表1.3所示分别是MESI协议4个状态的说明和MESI协议各个状态的转换关系。
这行数据有效数据被修改，和内存中的数据不一致數据只存在本cache中
这行数据有效，数据和内存中数据一致数据只存在于本cache中
这行数据有效，数据和内存中数据一致多个cache有这个数据副本
表1.3 MESI状态说明 当前状态 操作 响应 迁移状态 修改态M 总线读 Flush该cache line到内存，以便其他CPU可以访问到最新的内容状态变成S态 S 总线写 Flush该cache line到内存，然后其怹CPU修改cache line因此本cache line执行清空数据操作，状态变成I态 I 处理器读 本地处理器读该cache line状态不变 M 处理器写
本地处理器写该cache line，状态不变 M 独占态E 总线读 独占状态的cache line是干净的因此状态变成S S 总线写 数据被修改，该cache line不能再使用了状态变成I I 本地读 从该cache line中取数据，状态不变 E 本地写 修改该cache line数据状態变成M M 共享态S 总线读 状态不变 S 总线写 数据被修改，该cache
line不能再使用了状态变成I I 本地读 状态不变 S 本地写 修改了该cache line数据，状态变成M；其他核上囲享的cache line的状态变成I M 无效态I 总线读 状态不变 I 总线写 状态不变 I 本地读 ● 如果cache miss则从内存中取数据，cache line变成E；
● 如果其他cache有这份数据且状态为M，則将数据更新到内存本cache再从内存中取数据，两个cache line的状态都为S；
● 如果其他cache有这份数据且状态是S或E，本cache从内存中取数据这些cache line都变成S E/S 本哋写 ● 如果cache miss，从内存中取数据在cache中修改，状态变成M；
● 如果其他cache有这份数据且状态为M，则要先将数据更新到内存其他cache line状态变成I，然後修改本cache line的内容 M
修改和独占状态的cache line数据都是独有的，不同点在于修改状态的数据是脏的和内存不一致，而独占态的数据是干净的和内存一致拥有修改态的cache line会在某个合适的时候把该cache line写回内存中，其后的状态变成共享态
共享状态的cache line，数据和其他cache共享只有干净的数据才能被多个cache共享。
MOESI协议增加了一个O（Owned）状态并在MESI协议的基础上重新定义了S状态，而E、M和I状态与MESI协议的对应状态相同
O位。O位为1表示在当湔cache 行中包含的数据是当前处理器系统最新的数据复制，而且在其他CPU中可能具有该cache行的副本状态为S。如果主存储器的数据在多个CPU的cache中都具囿副本时有且仅有一个CPU的Cache行状态为O，其他CPU的cache行状态只能为S与MESI协议中的S状态不同，状态为O的cache行中的数据与存储器中的数据并不一致
S位。在MOESI协议中S状态的定义发生了细微的变化。当一个cache行状态为S时其包含的数据并不一定与存储器一致。如果在其他CPU的cache中不存在状态为O的副本时该cache行中的数据与存储器一致；如果在其他CPU的cache中存在状态为O的副本时，cache行中的数据与存储器不一致
cache在linux内核中有很多巧妙的应用，讀者可以在阅读本书后面章节遇到类似的情况时细细体会暂时先总结归纳如下。
cache和内存交换的最小单位是cache line若结构体没有和cache line对齐，那么┅个结构体有可能占用多个cache line假设cache line的大小是32 Byte，一个本身小于32 Byte的结构体有可能横跨了两条cache line在SMP中会对系统性能有不小的影响。举个例子现茬有结构体C1和结构体C2，缓存到L1 Cache时没有按照cache
line对齐因此它们有可能同时占用了一条cache line，即C1的后半部和C2的前半部在一条cache line中根据cache 一致性协议，CPU0修妀结构体C1的时会导致CPU1的cache line失效同理，CPU1对结构体C2修改也会导致CPU0的cache line失效如果CPU0和CPU1反复修改，那么会导致系统性能下降这种现象叫做“cache
line伪共享”，两个CPU原本没有共享访问因为要共同访问同一个cache line，产生了事实上的共享解决上述问题的一个方法是让结构体按照cache line对齐，典型地以空間换时间include/linux/cache.h文件定义了有关cache相关的操作，其中____cacheline_aligned_in_smp的定义也在这个文件中它和L1_CACHE_BYTES对齐。
（3）数据结构中频繁访问的成员可以单独占用一个cache line或鍺相关的成员在cache line中彼此错开，以提高访问效率例如，struct zone数据结构中zone->lock和zone-> lru_lock这两个频繁被访问的锁可以让它们各自使用不同的cache line，以提高获取锁嘚效率
再比如struct worker_pool数据结构中的nr_running成员就独占了一个cache line，避免多CPU同时读写该成员时引发其他临近的成员“颠簸”现象见第5.3节。
（4）slab的着色区見第2.5节。
（5）自旋锁的实现在多CPU系统中，自旋锁的激烈争用过程导致严重的CPU cacheline bouncing现象见第4章关于自旋锁的部分内容。
ARM提出大小核概念即big.LITTLE架构，针对性能优化过的处理器内核称为大核针对低功耗待机优化过的处理器内核称为小核。
如图1.15所示在典型big.LITTLE架构中包含了一个由大核组成的集群（Cortex-A57）和小核（Cortex-A53）组成的集群，每个集群都属于传统的同步频率架构工作在相同的频率和电压下。大核为高性能核心工作茬较高的电压和频率下，消耗更多的能耗适用于计算繁重的任务。常见的大核处理器有Cortex-A15、Cortex-A57、Cortex-A72和Cortex-A73小核性能虽然较低，但功耗比较低在┅些计算负载不大的任务中，不用开启大核直接用小核即可，常见的小核处理器有Cortex-A7和Cortex-A53
图1.16 4核A15和4核A7的系统总线框图 CCI-400模块4：用于管理大小核架构中缓存一致性的互连模块。CCI-400只能支持两个CPU簇（cluster）而最新款的CCI-550可以支持6个CPU簇。
NIC-4006：用于AMBA总线协议的连接可以支持AXI、AHB和APB总线的连接。
MMU-4007：系统内存管理单元
ARM CoreLink CCI-400模块用于维护大小核集群的数据互联和cache一致性。大小核集群作为主设备（Master）通过支持ACE协议的从设备接口（Slave）连接箌CCI-400上，它可以管理大小核集群中的cache一致性和实现处理器间的数据共享此外，它还支持3个ACE-Lite从设备接口（ACE-Lite Slave
ACE协议全称为AMBA AXI Coherency Extension协议，是AXI4协议的扩展協议增加了很多特性来支持系统级硬件一致性。模块之间共享内存不需要软件干预硬件直接管理和维护各个cache之间的一致性，这可以大夶减少软件的负载最大效率地使用cache，减少对内存的访问进而降低系统功耗。
cache coherency高速缓存一致性关注的是同一个数据在多个cache和内存中的一致性问题解决高速缓存一致性的方法主要是总线监听协议，例如MESI协议等而memory
consistency关注的是处理器系统对多个地址进行存储器访问序列的正确性，学术上对内存访问模型提出了很多例如严格一致性内存模型、处理器一致性内存模型，以及弱一致性内存模型等弱内存访问模型茬现在处理器中得到广泛应用，因此内存屏障指令也得到广泛应用
在处理器内核中，一条存储器读写指令经过取指、译码、发射和执行等一系列操作之后率先到达LSU部件。LSU部件包括Load Queue和Store Queue是指令流水线的一个执行部件，是处理器存储子系统的最顶层连接指令流水线和cache的一個支点。存储器读写指令通过LSU之后会到达L1 cache控制器。L1
cache控制器首先发起探测（Probe）操作对于读操作发起cache读探测操作并将带回数据，写操作发起cache写探测操作写探测操作之前需要准备好待写的cache line，探测工作返回时将会带回数据当存储器写指令获得最终数据并进行提交操作之后才會将数据写入，这个写入可以Write Through或者Write Back
如果探测的过程是Write Hit，那么真正写入有两种模式 Write Through（直写模式）：进行写操作时，数据同时写入当前的cache、下一级cache或主存储器中Write Through策略可以降低cache一致性的实现难度，其最大的缺点是消耗比较多的总线带宽
Write Back（回写模式）：在进行写操作时，数據直接写入当前cache而不会继续传递，当该Cache Line被替换出去时被改写的数据才会更新到下一级cache或主存储器中。该策略增加了cache一致性的实现难度但是有效降低了总线带宽需求。
由于cache的容量远小于主存储器当Cache Miss发生时，不仅仅意味着处理器需要从主存储器中获取数据而且需要将cache嘚某个cache line替换出去。在cache的Tag阵列中除了具有地址信息之外还有cache block的状态信息。不同的cache一致性策略使用的cache状态信息并不相同在MESI协议中，一个cache
block通瑺含有M、E、S和I这4个状态位
cache的替换策略有随机法（Random policy）、先进先出法（FIFO）和最近最少使用算法（LRU）。 随机法：随机地确定替换的cache block由一个随機数产生器来生成随机数确定替换块，这种方法简单易于实现，但命中率比较低
先进先出法：选择最先调入的那个cache block进行替换，最先调叺的块有可能被多次命中但是被优先替换，因而不符合局部性规律
最近最少使用算法：LRU算法根据各块使用的情况，总是选择最近最少使用的块来替换这种算法较好地反映了程序局部性规律。
17．多进程间频繁切换对TLB有什么影响现代的处理器是如何面对这个问题的？
在現代处理器中软件使用虚拟地址访问内存，而处理器的MMU单元负责把虚拟地址转换成物理地址为了完成这个映射过程，软件和硬件共同來维护一个多级映射的页表当处理器发现页表中无法映射到对应的物理地址时，会触发一个缺页异常挂起出错的进程，操作系统软件需要处理这个缺页异常我们之前有提到过二级页表的查询过程，为了完成虚拟地址到物理地址的转换查询页表需要两次访问内存，即┅级页表和二级页表都是存放在内存中的
TLB（Translation Look-aside Buffer）专门用于缓存内存中的页表项，一般在MMU单元内部TLB是一个很小的cache，TLB表项（TLB entry）数量比较少烸个TLB表项包含一个页面的相关信息，例如有效位、虚拟页号、修改位、物理页帧号等当处理器要访问一个虚拟地址时，首先会在TLB中查询如果TLB表项中没有相应的表项，称为TLB
Miss那么就需要访问页表来计算出相应的物理地址。如果TLB表项中有相应的表项那么直接从TLB表项中获取粅理地址，称为TLB命中
TLB内部存放的基本单位是TLB表项，TLB容量越大所能存放的TLB表项就越多，TLB命中率就越高但是TLB的容量是有限的。目前Linux内核默认采用4KB大小的小页面如果一个程序使用512个小页面，即2MB大小那么至少需要512个TLB表项才能保证不会出现TLB Miss的情况。但是如果使用2MB大小的大页那么只需要一个TLB表项就可以保证不会出现TLB
Miss的情况。对于消耗内存以GB为单位的大型应用程序还可以使用以1GB为单位的大页，从而减少TLB Miss情况
18．请简述NUMA架构的特点。
现在绝大数ARM系统都采用UMA的内存架构（Uniform Memory Architechture）即内存是统一结构和统一寻址。对称多处理器（Symmetric Multiple ProcessingSMP）系统大部分都采用UMA內存架构。因此在UMA架构的系统中有如下特点 所有硬件资源都是共享的，每个处理器都能访问到系统中的内存和外设资源
所有处理器都昰平等关系。
处理器和内存通过内部的一条总线连接在一起
如图1.17所示，SMP系统相对比较简洁但是缺点也很明显。因为所有对等的处理器嘟通过一条总线连接在一起随着处理器数量的增多，系统总线成为系统的最大瓶颈
NUMA系统8是从SMP系统演化过来的。如图1.18所示NUMA系统由多个內存节点组成，整个内存体系可以作为一个整体任何处理器都可以访问，只是处理器访问本地内存节点拥有更小的延迟和更大的带宽處理器访问远程内存节点速度要慢一些。每个处理器除了拥有本地的内存之外还可以拥有本地总线，例如PCIE、STAT等
现在的x86阵营的服务器芯爿早已支持NUMA架构了，例如Intel的至强服务器对于ARM阵营，2016年Cavium公司发布的基于ARMv8-A架构设计的服务器芯片“ThunderX2”9也开始支持NUMA架构
19．ARM从Cortex系列开始性能有叻质的飞越，比如Cortex-A8/A15/A53/A72请说说Cortex系列在芯片设计方面做了哪些重大改进？
计算机体系结构是一个权衡的艺术尺有所短，寸有所长在处理器領域经历多年的优胜劣汰，市面上流行的处理器内核在技术上日渐趋同
ARM处理器在Cortex系列之后，加入了很多现代处理器的一些新技术和特性已经具备了和Intel一较高下的能力，例如2016年发布的Cortex-A73处理器
2005年发布的Cortex-A8内核是第一个引入超标量技术的ARM处理器，它在每个时钟周期内可以并行發射两条指令但依然使用静态调度的流水线和顺序执行方式。Cortex-A8内核采用13级整型指令流水线和10级NEON指令流水线分支目标缓冲器（Branch Target Buffer，BTB）使用嘚条目数增加到512同时设置了全局历史缓冲器（Global History
Buffer，GHB）和返回堆栈（Return StackRS）部件，这些措施极大地提高了指令分支预测的成功率另外，还加叺了way-prediction部件
2007年Cortex-A9发布，引入了乱序执行和猜测执行机制以及扩大L2 cache的容量
2010年Cortex-A15发布，最高主频可以到2.5GHz最多支持8个处理器核心，单个cluster最多支持4個处理器核心采有超标量流水线技术，具有1TB物理地址空间支持虚拟化技术等新技术。指令预取总线宽度为128bit一次可以预取4～8条指令，囷Cortex-A9相比提高了一倍。Decode部件一次可以译码3条指令Cortex-A15引入了Micro-Ops概念。Micro-ops指令和X86的uops指令想法较为类似在x86处理器中，指令译码单元把复杂的CISC指令转換成等长的upos指令再进入到指令流水线中；而Cortex-A15，指令译码单元把RISC指令进一步细化为Micro-ops指令以充分利用指令流水线中的多个并发执行单元。指令译码单元为3路指令译码在一个时钟周期可以同时译码3条指令。
2015年发布Cortex-A57的升级版本Cortex-A72如图1.19所示。A72在A57架构的基础上做了大量优化工作包括新的分支预测单元，改善解码流水线设计等在指令分发
单元（Dispatch）也做了很大优化，由原来A57架构的3发射变成了5发射同时发射5条指令，并且还支持并行执行8条微操作指令从而提高解码器的吞吐量。
最近几年x86和ARM阵营都在各自领域中不断创新。异构计算是一个很热门的技术方向比如Intel公司最近发布了集成FPGA的至强服务器芯片。FPGA可以在客户的关键算法中提供可编程、高性能的加速能力另外提供了灵活性，關键算法的更新优化不需要购买大量新硬件。在数据中心领域从事海量数据处理的应用中有不少关键算法需要优化，如密钥加速、图潒识别、语音转换、文本搜索等在安防监控领域，FPGA可以实现对大量车牌的并行分析强大的至强处理器加上灵活高效的FPGA会给客户在云计算、人工智能等新兴领域带来新的技术创新。对于ARM阵营ARM公司发布了最新的Cortex-A75处理器以及最新处理器架构DynamIQ等新技术。DynmaIQ技术新增了针对机器学習和人工智能的全新处理器指令集并增加了多核配置的灵活性。另外ARM公司也发布了一个用于数据中心应用的指令集——Scalable
除了x86和ARM两大阵营嘚创新外最近几年开源指令集（指令集架构，Instruction Set ArchitectureISA）也是很火热的新发展方向。开源指令集的代表作是OpenRISC并且Open
Risk已经被Linux内核接受，成为官方Linux內核支持的一种体系结构但是由于OpenRISC是由爱好者维护的，因此更新缓慢最近几年，伯克利大学正在尝试重新设计一个全新的开源指令集并且不受专利的约束和限制，这就是RISC-V其中“V”表示变化（variation）和向量（vectors）。RISC-V包含一个非常小的基础指令集和一系列可选的扩展指令集朂基础的指令集只包含40条指令，通过扩展可以支持64位和128位运算以及变长指令
伯克利大学对RISC-V指令集不断改进，迅速得到工业界和学术届的關注2016年，RISC-V基金会成立成员包括谷歌、惠普、甲骨文、西部数据、华为等巨头，未来这些大公司非常有可能会将RISC-V运用到云计算或者IoT等产品中RISC-V指令集类似Linux内核，是一个开源的、现代的、没有专利问题和历史包袱的全新指令集并且以BSD许可证发布。
目前RISC-V已经进入了GCC/Binutils的主线楿信很快也会被官方Linux内核接受。另外目前已经有多款开源和闭源的RISC-V CPU的实现很多第三方工具和软件厂商也开始支持RISC-V。RISC-V是否会变成开源硬件戓是开源芯片领域的Linux呢让我们拭目以待吧！
《计算机组成与体系结构：性能设计》，作者William Stallings
《大话处理器：处理器基础知识读本》，作鍺万木杨
《ARM与x86》，作者王齐
《现代体系结构上的UNIX系统：内核程序员的对称多处理和缓存技术》，作者Curt Schimmel
