第1章 處理器體系結構

本章思考題

1．請簡述精簡指令集RISC和復雜指令集CISC的區(qū)別。

2．請簡述數值0x12345678在大小端字節(jié)序處理器的存儲器中的存儲方式。

3．請簡述在你所熟悉的處理器（比如雙核Cortex-A9）中一條存儲讀寫指令的執(zhí)行全過程。

4．請簡述內存屏障（memory barrier）產生的原因。

5．ARM有幾條memory barrier的指令？分別有什么區(qū)別？

6．請簡述cache的工作方式。

7．cache的映射方式有full-associative（全關聯(lián)）、direct-mapping（直接映射）和set-associative（組相聯(lián)）3種方式，請簡述它們之間的區(qū)別。為什么現代的處理器都使用組相聯(lián)的cache映射方式？

8．在一個32KB的4路組相聯(lián)的cache中，其中cache line為32Byte，請畫出這個cache的cache line、way和set的示意圖。

9．ARM9處理器的Data Cache組織方式使用的VIVT，即虛擬Index虛擬Tag，而在Cortex-A7處理器中使用PIPT，即物理Index物理Tag，請簡述PIPT比VIVT有什么優(yōu)勢？

10．請畫出在二級頁表架構中虛擬地址到物理地址查詢頁表的過程。

11．在多核處理器中，cache的一致性是如何實現的？請簡述MESI協(xié)議的含義。

12．cache在Linux內核中有哪些應用？

13．請簡述ARM big.LITTLE架構，包括總線連接和cache管理等。

14．cache coherency和memory consistency有什么區(qū)別？

15．請簡述cache的write back有哪些策略。

16．請簡述cache line的替換策略。

17．多進程間頻繁切換對TLB有什么影響？現代的處理器是如何面對這個問題的？

18．請簡述NUMA架構的特點。

19．ARM從Cortex系列開始性能有了質的飛越，比如Cortex-A8/A15/A53/A72，請說說Cortex系列在芯片設計方面做了哪些重大改進？

Linux 4.x內核已經支持幾十種的處理器體系結構，目前市面上最流行的兩種體系結構是x86和ARM。x86體系結構以Intel公司的PC和服務器市場為主導，ARM體系結構則是以ARM公司為主導的芯片公司占領了移動手持設備等市場。本書重點講述Linux內核的設計與實現，但是離開了處理器體系結構，就猶如空中樓閣，畢竟操作系統(tǒng)只是為處理器服務的一種軟件而已。目前大部分的Linux內核書籍都是基于x86架構的，但是國內還是有相當多的開發(fā)者采用ARM處理器來進行開發(fā)產品，比如手機、IoT設備、嵌入式設備等。因此本書基于ARM體系結構來講述Linux內核的設計與實現。

關于ARM體系結構，ARM公司的官方文檔已經有很多詳細資料，其中描述ARMv7-A和ARMv8-A架構的手冊包括：

? <ARM Architecture Reference Manual, ARMv7-A and ARMv7-R edition>

? <ARM Architecture Reference Manual, ARMv8, for ARMv8-A architecture profile>

另外還有一本非常棒的官方資料，講述ARM Coxtex系統(tǒng)處理器編程技巧：

? <ARM Coxtex-A Series Programmer's Guide, version 4.0>

? <ARM Coxtex-A Series Programmer's Guide for ARMv8-A, version 1.0>

讀者可以從ARM官方網站中下載到上述4本資料。本書的重點集中在Linux內核本身，不會用過多的篇幅來介紹ARM體系結構的細節(jié)，因此本章以快問快答的方式來介紹一些ARM體系結構相關的問題。

可能有些讀者對ARM處理器的命名感到疑惑。ARM公司除了提供處理器IP和配套工具以外，主要還是定義了一系列的ARM兼容指令集來構建整個ARM的軟件生態(tài)系統(tǒng)。從ARMv4指令集開始為國人所熟悉，兼容ARMv4指令集的處理器架構有ARM7-TDMI，典型處理器是三星的S3C44B0X。兼容ARMv5指令集的處理器架構有ARM920T，典型處理器是三星的S3C2440，有些讀者還買過基于S3C2440的開發(fā)板。兼容ARMv6指令集的處理器架構有ARM11 MPCore。到了ARMv7指令集，處理器系列以Cortex命名，又分成A、R和M系列，通常A系列針對大型嵌入式系統(tǒng)（例如手機）, R系列針對實時性系統(tǒng)， M系列針對單片機市場。Cortex-A7和Coxtex-A9處理器是前幾年手機的主流配置。Coxtex-A系列處理器面市后，由于處理性能的大幅提高以及杰出功耗控制，使得手機和平板電腦市場迅猛發(fā)展。另外一些新的應用需求正在醞釀，比如大內存、虛擬化、安全特性（Trustzone），以及更好的能效比（大小核）等。虛擬化和安全特性在\2RMv7上已經實現，但是大內存的支持顯得有點捉襟見肘，雖然可以通過LPAE（Large Physical Address Extensions）技術支持40位的物理地址空間，但是由于32位的處理器最高支持4GB的虛擬地址空間，因此不適合虛擬內存需求巨大的應用。于是ARM公司設計了一個全新的指令集，即ARMv8-A指令集，支持64位指令集，并且保持向前兼容ARMv7-A指令集。因此定義AArch64和AArch32兩套運行環(huán)境分別來運行64位和32位指令集，軟件可以動態(tài)切換運行環(huán)境。為了行文方便，在本書中AArch64也稱為ARM64, AArch32也稱為ARM32。

1．請簡述精簡指令集RISC和復雜指令集CISC的區(qū)別。

20世紀70年代，IBM的John Cocke研究發(fā)現，處理器提供的大量指令集和復雜尋址方式并不會被編譯器生成的代碼用到：20%的簡單指令經常被用到，占程序總指令數的80%，而指令集里其余80%的復雜指令很少被用到，只占程序總指令數的20%。基于這種思想，將指令集和處理器進行重新設計，在新的設計中只保留了常用的簡單指令，這樣處理器不需要浪費太多的晶體管去做那些很復雜又很少使用的復雜指令。通常，簡單指令大部分時間都能在一個cycle內完成，基于這種思想的指令集叫作RISC（Reduced Instruction Set Computer）指令集，以前的指令集叫作CISC（Complex Instruction Set Computer）指令集。

IBM和加州大學伯克利分校的David Patterson以及斯坦福大學的John Hennessy是RISC研究的先驅。Power處理器來自IBM, ARM/SPARC處理器受到伯克利RISC的影響， MIPS來自斯坦福。當下還在使用的最出名的CISC指令集是Intel/AMD的x86指令集。

RISC處理器通過更合理的微架構在性能上超越了當時傳統(tǒng)的CISC處理器，在最初的較量中，Intel處理器敗下陣來，服務器市場的處理器大部分被RISC陣營占據。Intel的David Papworth和他的同事一起設計了Pentium Pro處理器，x86指令集被解碼成類似RISC指令的微操作指令（micro-operations，簡稱uops），以后執(zhí)行的過程采用RISC內核的方式。CISC這個古老的架構通過巧妙的設計，又一次煥發(fā)生機，Intel的x86處理器的性能逐漸超過同期的RISC處理器，搶占了服務器市場，導致其他的處理器廠商只能向低功耗或者嵌入式方向發(fā)展。

RISC和CISC都是時代的產物，RISC在很多思想上更為先進。Intel的CSIC指令集也憑借向前兼容這一利器，打敗所有的RISC廠商，包括DEC、SUN、Motorola和IBM，一統(tǒng)PC和服務器領域。不過最近在手機移動業(yè)務方面，以ARM為首的廠商占得先機。

2．請簡述數值0x12345678在大小端字節(jié)序處理器的存儲器中的存儲方式。

在計算機系統(tǒng)中是以字節(jié)為單位的，每個地址單元都對應著一個字節(jié)，一個字節(jié)為8個比特位。但在32位處理器中，C語言中除了8比特的char類型之外，還有16比特的short型，32bit的int型。另外，對于位數大于8位的處理器，例如16位或者32位的處理器，由于寄存器寬度大于一個字節(jié)，那么必然存在著如何安排多個字節(jié)的問題，因此導致了大端存儲模式（Big-endian）和小端存儲模式（Little-endian）。例如一個16比特的short型變量X，在內存中的地址為0x0010, X的值為0x1122，那么0x11為高字節(jié)，0x22為低字節(jié)。對于大端模式，就將0x11放在低地址中；0x22放在高地址中。小端模式則剛好相反。很多的ARM處理器默認使用小端模式，有些ARM處理器還可以由硬件來選擇是大端模式還是小端模式。Cortex-A系列的處理器可以通過軟件來配置大小端模式。大小端模式是在處理器Load/Store訪問內存時用于描述寄存器的字節(jié)順序和內存中的字節(jié)順序之間的關系。

大端模式：指數據的高字節(jié)保存在內存的低地址中，而數據的低字節(jié)保存在內存的高地址中。例如：

      內存視圖：
      0000430: 1234 5678 0100 1800 53ef 0100 0100 0000
      0000440: c7b6 1100 0000 3400 0000 0000 0100 ffff

在大端模式下，前32位應該這樣讀：12 34 56 78。

因此，大端模式下地址的增長順序與值的增長順序相同。

小端模式：指數據的高字節(jié)保存在內存的高地址中，而數據的低字節(jié)保存在內存的低地址中。例如：

      內存視圖：
      0000430: 7856 3412 0100 1800 53ef 0100 0100 0000
      0000440: c7b6 1100 0000 3400 0000 0000 0100 ffff

在小端模式下，前32位應該這樣讀：12 34 56 78。

因此，小端模式下地址的增長順序與值的增長順序相反。

如何檢查處理器是大端模式還是小端模式？聯(lián)合體Union的存放順序是所有成員都從低地址開始存放的，利用該特性可以輕松獲取CPU對內存采用大端模式還是小端模式讀寫。

        int checkCPU(void)
        {
            union w
            {
                int  a;
                char b;
            } c;
            c.a = 1;
            return (c.b == 1);
        }

如果輸出結果是true，則是小端模式，否則是大端模式。

3．請簡述在你所熟悉的處理器（比如雙核Cortex-A9）中一條存儲讀寫指令的執(zhí)行全過程。

經典處理器架構的流水線是五級流水線：取指、譯碼、發(fā)射、執(zhí)行和寫回。

現代處理器在設計上都采用了超標量體系結構（Superscalar Architecture）和亂序執(zhí)行（out-of-order）技術，極大地提高了處理器計算能力。超標量技術能夠在一個時鐘周期內執(zhí)行多個指令，實現指令級的并行，有效提高了ILP（Instruction Level Parallelism）指令級的并行效率，同時也增加了整個cache和memory層次結構的實現難度。

一條存儲讀寫指令的執(zhí)行全過程很難用一句話來回答。在一個支持超標量和亂序執(zhí)行技術的處理器當中，一條存儲讀寫指令的執(zhí)行過程被分解為若干步驟。指令首先進入流水線（pipeline）的前端（Front-End），包括預取（fetch）和譯碼（decode），經過分發(fā)（dispatch）和調度（scheduler）后進入執(zhí)行單元，最后提交執(zhí)行結果。所有的指令采用順序方式（In-Order）通過前端，并采用亂序的方式（Out-of-Order, OOO）進行發(fā)射，然后亂序執(zhí)行，最后用順序方式提交結果，并將最終結果更新到LSQ（Load-Store Queue）部件。LSQ部件是指令流水線的一個執(zhí)行部件，可以理解為存儲子系統(tǒng)的最高層，其上接收來自CPU的存儲器指令，其下連接著存儲器子系統(tǒng)。其主要功能是將來自CPU的存儲器請求發(fā)送到存儲器子系統(tǒng)，并處理其下存儲器子系統(tǒng)的應答數據和消息。

很多程序員對亂序執(zhí)行的理解有誤差。對于一串給定的指令序列，為了提高效率，處理器會找出非真正數據依賴和地址依賴的指令，讓它們并行執(zhí)行。但是在提交執(zhí)行結果時，是按照指令次序的。總的來說，順序提交指令，亂序執(zhí)行，最后順序提交結果。例如有兩條沒有數據依賴的數據指令，后面那條指令的讀數據先被返回，它的結果也不能先寫回到最終寄存器，而是必須等到前一條指令完成之后才可以。

對于讀指令，當處理器在等待數據從緩存或者內存返回時，它處于什么狀態(tài)呢？是等在那不動，還是繼續(xù)執(zhí)行別的指令？對于亂序執(zhí)行的處理器，可以執(zhí)行后面的指令；對于順序執(zhí)行的處理器，會使流水線停頓，直到讀取的數據返回。

如圖1.1所示，在x86微處理器經典架構中，存儲指令從L1指令cache中讀取指令， L1指令cache會做指令加載、指令預取、指令預解碼，以及分支預測。然后進入Fetch &Decode單元，會把指令解碼成macro-ops微操作指令，然后由Dispatch部件分發(fā)到Integer Unit或者FloatPoint Unit。Integer Unit由Integer Scheduler和Execution Unit組成，Execution Unit包含算術邏輯單元（arithmetic-logic unit, ALU）和地址生成單元（address generation unit, AGU），在ALU計算完成之后進入AGU，計算有效地址完畢后，將結果發(fā)送到LSQ部件。LSQ部件首先根據處理器系統(tǒng)要求的內存一致性（memory consistency）模型確定訪問時序，另外LSQ還需要處理存儲器指令間的依賴關系，最后LSQ需要準備L1 cache使用的地址，包括有效地址的計算和虛實地址轉換，將地址發(fā)送到L1 Data Cache中。

圖1.1 x86微處理器經典架構圖

如圖1.2所示，在ARM Cortex-A9處理器中，存儲指令首先通過主存儲器或者L2 cache加載到L1指令cache中。在指令預取階段（instruction prefetch stage），主要是做指令預取和分支預測，然后指令通過Instruction Queue隊列被送到解碼器進行指令的解碼工作。解碼器（decode）支持兩路解碼，可以同時解碼兩條指令。在寄存器重名階段（Register rename stage）會做寄存器重命名，避免機器指令不必要的順序化操作，提高處理器的指令級并行能力。在指令分發(fā)階段（Dispatch stage），這里支持4路猜測發(fā)射和亂序執(zhí)行（Out-of-Order Multi-Issue with Speculation），然后在執(zhí)行單元（ALU/MUL/FPU/NEON）中亂序執(zhí)行。存儲指令會計算有效地址并發(fā)射到內存系統(tǒng)中的LSU部件（Load Store Unit），最終LSU部件會去訪問L1數據cache。在ARM中，只有cacheable的內存地址才需要訪問cache。

圖1.2 Cortex-A9結構框圖

在多處理器環(huán)境下，還需要考慮Cache的一致性問題。L1和L2 Cache控制器需要保證cache的一致性，在Cortex-A9中cache的一致性是由MESI協(xié)議來實現的。Cortex-A9處理器內置了L1 Cache模塊，由SCU（Snoop Control Unit）單元來實現Cache的一致性管理。L2 Cache需要外接芯片（例如PL310）。在最糟糕情況下需要訪問主存儲器，并將數據重新傳遞給LSQ，完成一次存儲器讀寫的全過程。

這里涉及計算機體系結構中的眾多術語，比較晦澀難懂，現在對部分術語做簡單解釋。

? 超標量體系結構（Superscalar Architecture）：早期的單發(fā)射結構微處理器的流水線設計目標是做到每個周期能平均執(zhí)行一條指令，但這一目標不能滿足處理器性能增長的要求，為了提高處理器的性能，要求處理器具有每個周期能發(fā)射執(zhí)行多條指令的能力。因此超標量體系結構是描述一種微處理器設計理念，它能夠在一個時鐘周期執(zhí)行多個指令。

? 亂序執(zhí)行（Out-of-order Execution）：指CPU采用了允許將多條指令不按程序規(guī)定的順序分開發(fā)送給各相應電路單元處理的技術，避免處理器在計算對象不可獲取時的等待，從而導致流水線停頓。

? 寄存器重命名（Register Rename）：現代處理器的一種技術，用來避免機器指令或者微操作的不必要的順序化執(zhí)行，從而提高處理器的指令級并行的能力。它在亂序執(zhí)行的流水線中有兩個作用，一是消除指令之間的寄存器讀后寫相關（Write-after-Read, WAR）和寫后寫相關（Write-after-Write, WAW）；二是當指令執(zhí)行發(fā)生例外或者轉移指令猜測錯誤而取消后面的指令時，可用來保證現場的精確。其思路為當一條指令寫一個結果寄存器時不直接寫到這個結果寄存器，而是先寫到一個中間寄存器過渡，當這條指令提交時再寫到結果寄存器中。

? 分支預測（Branch Predictor）：當處理一個分支指令時，有可能會產生跳轉，從而打斷流水線指令的處理，因為處理器無法確定該指令的下一條指令，直到分支指令執(zhí)行完畢。流水線越長，處理器等待時間便越長，分支預測技術就是為了解決這一問題而出現的。因此，分支預測是處理器在程序分支指令執(zhí)行前預測其結果的一種機制。在ARM中，使用全局分支預測器，該預測器由轉移目標緩沖器（Branch Target Buffer, BTB）、全局歷史緩沖器（Global History Buffer, GHB）、MicroBTB，以及Return Stack組成。

? 指令譯碼器（Instruction Decode）：指令由操作碼和地址碼組成。操作碼表示要執(zhí)行的操作性質，即執(zhí)行什么操作；地址碼是操作碼執(zhí)行時的操作對象的地址。計算機執(zhí)行一條指定的指令時，必須首先分析這條指令的操作碼是什么，以決定操作的性質和方法，然后才能控制計算機其他各部件協(xié)同完成指令表達的功能，這個分析工作由譯碼器來完成。例如，Cortex-A57可以支持3路譯碼器，即同時執(zhí)行3條指令譯碼，而Cortex-A9處理器只能同時譯碼2條指令。

? 調度單元（Dispatch）：調度器負責把指令或微操作指令派發(fā)到相應的執(zhí)行單元去執(zhí)行，例如，Cortex-A9處理器的調度器單元有4個接口和執(zhí)行單元連接，因此每個周期可以同時派發(fā)4條指令。

? ALU算術邏輯單元：ALU是處理器的執(zhí)行單元，主要是進行算術運算，邏輯運算和關系運算的部件。

? LSQ/LSU部件（Load Store Queue/Unit）:LSQ部件是指令流水線的一個執(zhí)行部件，其主要功能是將來自CPU的存儲器請求發(fā)送到存儲器子系統(tǒng)，并處理其下存儲器子系統(tǒng)的應答數據和消息。

4．請簡述內存屏障（memory barrier）產生的原因。

程序在運行時的實際內存訪問順序和程序代碼編寫的訪問順序不一致，會導致內存亂序訪問。內存亂序訪問的出現是為了提高程序運行時的性能。內存亂序訪問主要發(fā)生在如下兩個階段。

（1）編譯時，編譯器優(yōu)化導致內存亂序訪問。

（2）運行時，多CPU間交互引起的內存亂序訪問。

編譯器會把符合人類思考的邏輯代碼（例如C語言）翻譯成CPU運算規(guī)則的匯編指令，編譯器了解底層CPU的思維邏輯，因此它會在翻譯成匯編時進行優(yōu)化。例如內存訪問指令的重新排序，提高指令級并行效率。然而，這些優(yōu)化可能會違背程序員原始的代碼邏輯，導致發(fā)生一些錯誤。編譯時的亂序訪問可以通過volatile關鍵字來規(guī)避。

      #define barrier() __asm__ __volatile__ ("" ::: "memory")

barrier()函數告訴編譯器，不要為了性能優(yōu)化而將這些代碼重排。

由于現代處理器普遍采用超標量技術、亂序發(fā)射以及亂序執(zhí)行等技術來提高指令級并行的效率，因此指令的執(zhí)行序列在處理器的流水線中有可能被打亂，與程序代碼編寫時序列的不一致。另外現代處理器采用多級存儲結構，如何保證處理器對存儲子系統(tǒng)訪問的正確性也是一大挑戰(zhàn)。

例如，在一個系統(tǒng)中含有n個處理器P1～Pn，假設每個處理器包含Si個存儲器操作，那么從全局來看可能的存儲器訪問序列有多種組合。為了保證內存訪問的一致性，需要按照某種規(guī)則來選出合適的組合，這個規(guī)則叫做內存一致性模型（Memory Consistency Model）。這個規(guī)則需要保證正確性的前提，同時也要保證多處理器訪問較高的并行度。

在一個單核處理器系統(tǒng)中，訪問內存的正確性比較簡單。每次存儲器讀操作所獲得的結果是最近寫入的結果，但是在多處理器并發(fā)訪問存儲器的情況下就很難保證其正確性了。我們很容易想到使用一個全局時間比例部件（Global Time Scale）來決定存儲器訪問時序，從而判斷最近訪問的數據。這種內存一致性訪問模型是嚴格一致性（Strict Consistency）內存模型，也稱為Atomic Consistency。全局時間比例方法實現的代價比較大，那么退而求其次，采用每一個處理器的本地時間比例部件（Local Time Scale）的方法來確定最新數據的方法被稱為順序一致性內存模型（Sequential Consistency）。處理器一致性內存模型（Processor Consistency）是進一步弱化，僅要求來自同一個處理器的寫操作具有一致性的訪問即可。

以上這些內存一致性模型是針對存儲器讀寫指令展開的，還有一類目前廣泛使用的模型，這些模型使用內存同步指令，也稱為內存屏障指令。在這種模型下，存儲器訪問指令被分成數據指令和同步指令兩大類，弱一致性內存模型（weak consistency）就是基于這種思想的。

1986年，Dubois等發(fā)表的論文描述了弱一致性內存模型的定義。

? 對同步變量的訪問是順序一致的。

? 在所有之前的寫操作完成之前，不能訪問同步變量。

? 在所有之前同步變量的訪問完成之前，不能訪問（讀或者寫）數據。

弱一致性內存模型要求同步訪問是順序一致的，在一個同步訪問可以被執(zhí)行之前，所有之前的數據訪問必須完成。在一個正常的數據訪問可以被執(zhí)行之前，所有之前的同步訪問必須完成。這實質上把一致性問題留給了程序員來決定。

ARM的Cortex-A系列處理器實現弱一致性內存模型，同時也提供了3條內存屏障指令。

5.ARM有幾條memory barrier的指令？分別有什么區(qū)別？

從ARMv7指令集開始，ARM提供3條內存屏障指令。

（1）數據存儲屏障（Data Memory Barrier, DMB）

數據存儲器隔離。DMB指令保證：僅當所有在它前面的存儲器訪問操作都執(zhí)行完畢后，才提交（commit）在它后面的存取訪問操作指令。當位于此指令前的所有內存訪問均完成時，DMB指令才會完成。

（2）數據同步屏障（Data synchronization Barrier, DSB）

數據同步隔離。比DMB要嚴格一些，僅當所有在它前面的存儲訪問操作指令都執(zhí)行完畢后，才會執(zhí)行在它后面的指令，即任何指令都要等待DSB前面的存儲訪問完成。位于此指令前的所有緩存，如分支預測和TLB（Translation Look-aside Buffer）維護操作全部完成。

（3）指令同步屏障（Instruction synchronization Barrier, ISB）

指令同步隔離。它最嚴格，沖洗流水線（Flush Pipeline）和預取buffers（pretcLbuffers）后，才會從cache或者內存中預取ISB指令之后的指令。ISB通常用來保證上下文切換的效果，例如更改ASID（Address Space Identifier）、TLB維護操作和C15寄存器的修改等。

內存屏障指令的使用例子如下。

例1：假設有兩個CPU核A和B，同時訪問Addr1和Addr2地址。

      Core A:
          STR R0, [Addr1]
      LDR R1, [Addr2]

      Core B:
          STR R2, [Addr2]
          LDR R3, [Addr1]

對于上面代碼片段，沒有任何的同步措施。對于Core A、寄存器R1、Core B和寄存器R3，可能得到如下4種不同的結果。

? A得到舊的值，B也得到舊的值。

? A得到舊的值，B得到新的值。

? A得到新的值，B得到舊的值。

? A得到新的值，B得到新的值。

例2：假設Core A寫入新數據到Msg地址，Core B需要判斷flag標志后才讀入新數據。

      Core A:
              STR R0, [Msg] @ 寫新數據到Msg地址
              STR R1, [Flag] @ Flag標志新數據可以讀

      Core B:
          Poll_loop:
              LDR R1, [Flag]
              CMP R1, #0        @ 判斷flag有沒有置位
              BEQ Poll_loop
              LDR R0, [Msg]   @ 讀取新數據

在上面的代碼片段中，Core B可能讀不到最新的數據，因為Core B可能因為亂序執(zhí)行的原因先讀入Msg，然后讀取Flag。在弱一致性內存模型中，處理器不知道Msg和Flag存在數據依賴性，所以程序員必須使用內存屏障指令來顯式地告訴處理器這兩個變量有數據依賴關系。Core A需要在兩個存儲指令之間插入DMB指令來保證兩個store存儲指令的執(zhí)行順序。Core B需要在“LDR R0, [Msg]”之前插入DMB指令來保證直到Flag置位才讀入Msg。

例3：在一個設備驅動中，寫入一個命令到一個外設寄存器中，然后等待狀態(tài)的變化。

        STR R0, [Addr]          @ 寫一個命令到外設寄存器
        DSB
        Poll_loop:
            LDR R1, [Flag]
            CMP R1, #0           @ 等待狀態(tài)寄存器的變化
            BEQ Poll_loop

在STR存儲指令之后插入DSB指令，強制讓寫命令完成，然后執(zhí)行讀取Flag的判斷循環(huán)。

6．請簡述cache的工作方式。

處理器訪問主存儲器使用地址編碼方式。cache也使用類似的地址編碼方式，因此處理器使用這些編碼地址可以訪問各級cache。如圖1.3所示，是一個經典的cache架構圖。

圖1.3 經典cache架構

處理器在訪問存儲器時，會把地址同時傳遞給TLB（Translation Lookaside Buffer）和cache。TLB是一個用于存儲虛擬地址到物理地址轉換的小緩存，處理器先使用EPN （effective page number）在TLB中進行查找最終的RPN（Real Page Number）。如果這期間發(fā)生TLB miss，將會帶來一系列嚴重的系統(tǒng)懲罰，處理器需要查詢頁表。假設這里TLB Hit，此時很快獲得合適的RPN，并得到相應的物理地址（Physical Address, PA）。

同時，處理器通過cache編碼地址的索引域（Cache Line Index）可以很快找到相應的cache line組。但是這里的cache block的數據不一定是處理器所需要的，因此有必要進行一些檢查，將cache line中存放的地址和通過虛實地址轉換得到的物理地址進行比較。如果相同并且狀態(tài)位匹配，那么就會發(fā)生cache命中（Cache Hit），那么處理器經過字節(jié)選擇和偏移（Byte Select and Align）部件，最終就可以獲取所需要的數據。如果發(fā)生cache miss，處理器需要用物理地址進一步訪問主存儲器來獲得最終數據，數據也會填充到相應的cache line中。上述描述的是VIPT（virtual Index phg sical Tag）的cache組織方式，將會在問題9中詳細介紹。

如圖1.4所示，是cache的基本的結構圖。

圖1.4 cache結構圖

? cache地址編碼：處理器訪問cache時的地址編碼，分成3個部分，分別是偏移域（Offset）、索引域（Index）和標記域（Tag）。

? Cache Line:cache中最小的訪問單元，包含一小段主存儲器中的數據，常見的cache line大小是32Byte或64Byte等。

? 索引域（Index）:cache地址編碼的一部分，用于索引和查找是在cache中的哪一行。

? 組（Set）：相同索引域的cache line組成一個組。

? 路（Way）：在組相聯(lián)的cache中，cache被分成大小相同的幾個塊。

? 標記（Tag）:cache地址編碼的一部分，用于判斷cache line存放的數據是否和處理器想要的一致。

7.cache的映射方式有full-associative（全關聯(lián)）、direct-mapping（直接映射）和set-associative（組相聯(lián)）3種方式，請簡述它們之間的區(qū)別。為什么現代的處理器都使用組相聯(lián)的cache映射方式？

（1）直接映射（Direct-mapping）

根據每個組（set）的高速緩存行數，cache可以分成不同的類。當每個組只有一行cache line時，稱為直接映射高速緩存。

如圖1.5所示，下面用一個簡單小巧的cache來說明，這個cache只有4行cache line，每行有4個字（word，一個字是4個Byte），共64 Byte。這個cache控制器可以使用兩個比特位（bits[3:2]）來選擇cache line中的字，以及使用另外兩個比特位（bits[5:4]）作為索引（Index），選擇4個cache line中的一個，其余的比特位用于存儲標記值（Tag）。

在這個cache中查詢，當索引域和標記域的值和查詢的地址相等，并且有效位顯示這個cache line包含有效數據時，則發(fā)生cache命中，那么可以使用偏移域來尋址cache line中的數據。如果cache line包含有效數據，但是標記域是其他地址的值，那么這個cache line需要被替換。因此，在這個cache中，主存儲器中所有bit [5:4]相同值的地址都會映射到同一個cache line中，并且同一時刻只有一個cache line，因為cache line被頻繁換入換出，會導致嚴重的cache顛簸（cache thrashing）。

圖1.5 直接眏射的cache和cache地址

假設在下面的代碼片段中，result、data1和data2分別指向0x00、0x40和0x80地址，它們都會使用同一個cache line。

      void add_array(int *data1, int *data2, int *result, int size)
      {
          int i;
          for (i=0 ; i＜size ; i++) {
                result[i] = data1[i] + data2[i];
          }
      }

? 當第一次讀data1即0x40地址時，因為不在cache里面，所以讀取從0x40到0x4f地址的數據填充到cache line中。

? 當讀data2即0x80地址的數據時，數據不在cache line中，需要把從0x80到0x8f地址的數據填充到cache line中，因為地址0x80和0x40映射到同一個cache line，所以cache line發(fā)生替換操作。

? result寫入到0x00地址時，同樣發(fā)生了cache line替換操作。

? 所以這個代碼片段發(fā)生嚴重的cache顛簸，性能會很糟糕。

（2）組相聯(lián)（set associative）

為了解決直接映射高速緩存中的cache顛簸問題，組相聯(lián)的cache結構在現代處理器中得到廣泛應用。

如圖1.6所示，下面以一個2路組相聯(lián)的cache為例，每個路（way）包括4個cache line，那么每個組（set）有兩個cache line可以提供cache line替換。

圖1.6 2路組相聯(lián)的映射關系

地址0x00、0x40或者0x80的數據可以映射到同一個組中任意一個cache line。當cache line要發(fā)生替換操作時，就有50%的概率可以不被替換，從而減小了cache顛簸。

8．在一個32KB的4路組相聯(lián)的cache中，其中cache line為32Byte，請畫出這個cache的cache line、way和set的示意圖。

在Cortex-A7和Cortex-A9的處理器上可以看到32KB大小的4路組相聯(lián)cache。下面來分析這個cache的結構圖。

cache的總大小為32KB，并且是4路（way），所以每一路的大小為8KB：

way_size = 32 / 4 = 8（KB）

cache Line的大小為32Byte，所以每一路包含的cache line數量為：

num_cache_line = 8KB/32B = 256

所以在cache編碼地址Address中，bit[4:0]用于選擇cache line中的數據，其中bit [4:2]可以用于尋址8個字，bit [1:0]可以用于尋址每個字中的字節(jié)。bit [12:5]用于索引（Index）選擇每一路上cache line，其余的bit [31:13]用作標記位（Tag），如圖1.7所示。

9.ARM9處理器的Data Cache組織方式使用的VIVT，即虛擬Index虛擬Tag，而在Cortex-A7處理器中使用PIPT，即物理Index物理Tag，請簡述PIPT比VIVT有什么優(yōu)勢？

處理器在進行存儲器訪問時，處理器訪問地址是虛擬地址（virtual address, VA），經過TLB和MMU的映射，最終變成了物理地址（physical address, PA）。那么查詢cache組是用虛擬地址，還是物理地址的索引域（Index）呢？當找到cache組時，我們是用虛擬地址，還是物理地址的標記域（Tag）來匹配cache line呢？

cache可以設計成通過虛擬地址或者物理地址來訪問，這個在處理器設計時就確定下來了，并且對cache的管理有很大的影響。cache可以分成如下3類。

? VIVT（Virtual Index Virtual Tag）：使用虛擬地址索引域和虛擬地址的標記域。

? VIPT（Virtual Index Physical Tag）：使用虛擬地址索引域和物理地址的標記域。

圖1.7 32KB 4路組相聯(lián)cache結構圖

? PIPT（Physical Index Physical Tag）：使用物理地址索引域和物理地址的標記域。

在早期的ARM處理器中（比如ARM9處理器）采用VIVT的方式，不用經過MMU的翻譯，直接使用虛擬地址的索引域和標記域來查找cache line，這種方式會導致高速緩存別名（cache alias）問題。例如一個物理地址的內容可以出現在多個cache line中，當系統(tǒng)改變了虛擬地址到物理地址映射時，需要清洗（clean）和無效（invalidate）這些cache，導致系統(tǒng)性能下降。

ARM11系列處理器采用VIPT方式，即處理器輸出的虛擬地址同時會發(fā)送到TLB/MMU單元進行地址翻譯，以及在cache中進行索引和查詢cache組。這樣cache和TLB/MMU可以同時工作，當TLB/MMU完成地址翻譯后，再用物理標記域來匹配cache line。采用VIPT方式的好處之一是在多任務操作系統(tǒng)中，修改了虛擬地址到物理地址映射關系，不需要把相應的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]范圍內，那么就不會發(fā)生高速緩存別名。例如，cache line是32Byte，那么數據偏移域offset占5bit，有128個cache組，那么索引域占7bit，這種情況下剛好不會發(fā)生別名。另外，對于ARM Cortex-A系列處理器來說，cache總大小是可以在芯片集成中配置的。如表1.1所示，列舉出了Cortex-A系列處理器的cache配置情況。

表1.1 ARM處理器的cache概況

10．請畫出在二級頁表架構中虛擬地址到物理地址查詢頁表的過程。

如圖1.8所示，ARM處理器的內存管理單元（Memory Management Unit, MMU）包括TLB和Table Walk Unit兩個部件。TLB是一塊高速緩存，用于緩存頁表轉換的結果，從而減少內存訪問的時間。一個完整的頁表翻譯和查找的過程叫作頁表查詢（Translation table walk），頁表查詢的過程由硬件自動完成，但是頁表的維護需要軟件來完成。頁表查詢是一個相對耗時的過程，理想的狀態(tài)下是TLB里存有頁表相關信息。當TLB Miss時，才會去查詢頁表，并且開始讀入頁表的內容。

圖1.8 ARM內存管理架構

（1）ARMv7-A架構的頁表

ARMv7-A架構支持安全擴展（Security Extensions），其中Cortex-A15開始支持大物理地址擴展Large Physical Address Extension, LPAE）和虛擬化擴展，使得MMU的實現比以前的ARM處理器要復雜得多。

如圖1.9所示，如果使能了安全擴展， ARMv7-A處理器分成安全世界（Secure World）和非安全世界（Non-secure World，也稱為Normal World）。

圖1.9 ARMv7-A架構的運行模式和特權

如果處理器使能了虛擬化擴展，那么處理器會在非安全世界中增加一個Hyp模式。

在非安全世界中，運行特權被劃分為PL0、PL1和PL2。

? PL0等級：這個特權等級運行在用戶模式（User Mode），用于運行用戶程序，它是沒有系統(tǒng)特權的，比如沒有權限訪問處理器內部的硬件資源。

? PL1等級：這個等級包括ARMv6架構中的System模式、SVC模式、FIQ模式、IRQ模式、Undef模式，以及Abort模式。Linux內核運行在PL1等級，應用程序運行在PL0等級。如果使能了安全擴展，那么安全模式里有一個Monitor模式也是運行在secure PL1等級，管理安全世界和非安全世界的狀態(tài)轉換。

? PL2等級：如果使能了虛擬化擴展，那么超級管理程序（Hypervisor）就運行這個等級，它運行在Hyp模式，管理GuestOS之間的切換。

當處理器使能了虛擬化擴展，MMU的工作會變得更復雜。我們這里只討論處理器沒有使能安全擴展和虛擬化擴展的情況。ARMv7處理器的二級頁表根據最終頁的大小可以分為如下4種情況。

? 超級大段（SuperSection）：支持16MB大小的超級大塊。

? 段（section）：支持1MB大小的段。

? 大頁面（Large page）：支持64KB大小的大頁。

? 頁面（page）:4KB的頁，Linux內核默認使用4KB的頁。

如果只需要支持超級大段和段映射，那么只需要一級頁表即可。如果要支持4KB頁面或64KB大頁映射，那么需要用到二級頁表。不同大小的映射，一級或二級頁表中的頁表項的內容也不一樣。如圖1.10所示，以4KB頁的映射為例。

圖1.10 ARMv7-A二級頁表查詢過程

當TLB Miss時，處理器查詢頁表的過程如下。

? 處理器根據頁表基地址控制寄存器TTBCR和虛擬地址來判斷使用哪個頁表基地址寄存器，是TTBR0還是TTBR1。頁表基地址寄存器中存放著一級頁表的基地址。

? 處理器根據虛擬地址的bit[31:20]作為索引值，在一級頁表中找到頁表項，一級頁表一共有4096個頁表項。

? 第一級頁表的表項中存放有二級頁表的物理基地址。處理器根據虛擬地址的bit[19:12]作為索引值，在二級頁表中找到相應的頁表項，二級頁表有256個頁表項。

? 二級頁表的頁表項里存放有4KB頁的物理基地址，因此處理器就完成了頁表的查詢和翻譯工作。

如圖1.11所示的4KB映射的一級頁表的表項，bit[1:0]表示是一個頁映射的表項， bit[31:10]指向二級頁表的物理基地址。

圖1.11 4KB映射的一級頁表的表項

如圖1.12所示的4KB映射的二級頁表的表項，bit[31:12]指向4KB大小的頁面的物理基地址。

圖1.12 4KB映射的二級頁表的表項

（2）ARMv8-A架構的頁表

ARMv8-A架構開始支持64bit操作系統(tǒng)。從ARMv8-A架構的處理器可以同時支持64bit和32bit應用程序，為了兼容ARMv7-A指令集，從架構上定義了AArch64架構和AArch32架構。

AArch64架構和ARMv7-A架構一樣支持安全擴展和虛擬化擴展。安全擴展把ARM的世界分成了安全世界和非安全世界。AArch64架構的異常等級（Exception Levels）確定其運行特權級別，類似ARMv7架構中特權等級，如圖1.13所示。

? EL0：用戶特權，用于運行普通用戶程序。

? EL1：系統(tǒng)特權，通常用于運行操作系統(tǒng)。

? EL2：運行虛擬化擴展的Hypervisor。

? EL3：運行安全世界中的Secure Monitor。

在AArch64架構中的MMU支持單一階段的地址頁表轉換，同樣也支持虛擬化擴展中的兩階段的頁表轉換。

? 單一階段頁表：虛擬地址（VA）翻譯成物理地址（PA）。

? 兩階段頁表（虛擬化擴展）：

圖1.13 AArch64架構的異常等級

階段1——虛擬地址翻譯成中間物理地址（Intermediate Physical Address, IPA）。

階段2——中間物理地址IPA翻譯成最終物理地址PA。

在AArch64架構中，因為地址總線帶寬最多48位，所以虛擬地址VA被劃分為兩個空間，每個空間最大支持256TB。

? 低位的虛擬地址空間位于0x0000_0000_0000_0000到0x0000_FFFF_FFFF_FFFF。如果虛擬地址最高位bit63等于0，那么就使用這個虛擬地址空間，并且使用TTBR0（Translation Table Base Register）來存放頁表的基地址。

? 高位的虛擬地址空間位于0xFFFF_0000_0000_0000到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協(xié)議的含義。

高速緩存一致性（cache coherency）產生的原因是在一個處理器系統(tǒng)中不同CPU核上的數據cache和內存可能具有同一個數據的多個副本，在僅有一個CPU核的系統(tǒng)中不存在一致性問題。維護cache一致性的關鍵是跟蹤每一個cache line的狀態(tài)，并根據處理器的讀寫操作和總線上的相應傳輸來更新cache line在不同CPU核上的數據cache中的狀態(tài)，從而維護cache一致性。cache一致性有軟件和硬件兩種方式，有的處理器架構提供顯式操作cache的指令，例如PowerPC，不過現在大多數處理器架構采用硬件方式來維護。在處理器中通過cache一致性協(xié)議來實現，這些協(xié)議維護一個有限狀態(tài)機（Finite State Machine, FSM），根據存儲器讀寫指令或總線上的傳輸，進行狀態(tài)遷移和相應的cache操作來保證cache一致性，不需要軟件介入。

cache一致性協(xié)議主要有兩大類別，一類是監(jiān)聽協(xié)議（Snooping Protocol），每個cache都要被監(jiān)聽或者監(jiān)聽其他cache的總線活動；另外一類是目錄協(xié)議（Directory Protocol），全局統(tǒng)一管理cache狀態(tài)。

1983年，James Goodman提出Write-Once總線監(jiān)聽協(xié)議，后來演變成目前最流行的MESI協(xié)議。總線監(jiān)聽協(xié)議依賴于這樣的事實，即所有的總線傳輸事務對于系統(tǒng)內所有的其他單元是可見的，因為總線是一個基于廣播通信的介質，因而可以由每個處理器的cache來進行監(jiān)聽。這些年來人們已經提出了數十種協(xié)議，這些協(xié)議基本上都是write-once協(xié)議的變種。不同的協(xié)議需要不同的通信量，要求太多的通信量會浪費總線帶寬，使總線爭用變多，留下來給其他部件使用的帶寬就減少。因此，芯片設計人員嘗試將保持一致性的協(xié)議所需要的總線通信量減少到最小，或者嘗試優(yōu)化某些頻繁執(zhí)行的操作。

目前，ARM或x86等處理器廣泛使用類似MESI協(xié)議來維護cache一致性。MESI協(xié)議的得名源于該協(xié)議使用的修改態(tài)（Modified）、獨占態(tài)（Exclusive）、共享態(tài)（Shared）和失效態(tài)（Invalid）這4個狀態(tài)。cache line中的狀態(tài)必須是上述4種狀態(tài)中的一種。MESI協(xié)議還有一些變種，例如MOESI協(xié)議等，部分的ARMv7-A和ARMv8-A處理器使用該變種。

cache line中有兩個標志：dirty和valid。它們很好地描述了cache和內存之間的數據關系，例如數據是否有效、數據是否被修改過。在MESI協(xié)議中，每個cache line有4個狀態(tài)，可用2bit來表示。

如表1.2和表1.3所示，分別是MESI協(xié)議4個狀態(tài)的說明和MESI協(xié)議各個狀態(tài)的轉換關系。

表1.2 MESI協(xié)議定義

表1.3 MESI狀態(tài)說明

? 修改和獨占狀態(tài)的cache line，數據都是獨有的，不同點在于修改狀態(tài)的數據是臟的，和內存不一致，而獨占態(tài)的數據是干凈的和內存一致。擁有修改態(tài)的cache line會在某個合適的時候把該cache line寫回內存中，其后的狀態(tài)變成共享態(tài)。

? 共享狀態(tài)的cache line，數據和其他cache共享，只有干凈的數據才能被多個cache共享。

? I的狀態(tài)表示這個cache line無效。

MOESI協(xié)議增加了一個O（Owned）狀態(tài)，并在MESI協(xié)議的基礎上重新定義了S狀態(tài)，而E、M和I狀態(tài)與MESI協(xié)議的對應狀態(tài)相同。

? O位。O位為1，表示在當前cache行中包含的數據是當前處理器系統(tǒng)最新的數據復制，而且在其他CPU中可能具有該cache行的副本，狀態(tài)為S。如果主存儲器的數據在多個CPU的cache中都具有副本時，有且僅有一個CPU的Cache行狀態(tài)為O，其他CPU的cache行狀態(tài)只能為S。與MESI協(xié)議中的S狀態(tài)不同，狀態(tài)為O的cache行中的數據與存儲器中的數據并不一致。

? S位。在MOESI協(xié)議中，S狀態(tài)的定義發(fā)生了細微的變化。當一個cache行狀態(tài)為S時，其包含的數據并不一定與存儲器一致。如果在其他CPU的cache中不存在狀態(tài)為O的副本時，該cache行中的數據與存儲器一致；如果在其他CPU的cache中存在狀態(tài)為O的副本時，cache行中的數據與存儲器不一致。

12.cache在Linux內核中有哪些應用？

cache line的空間都很小，一般也就32 Byte。CPU的cache是線性排列的，也就是說一個32 Byte的cache line與32 Byte的地址對齊，另外相鄰的地址會在不同的cache line中錯開，這里是指32*n的相鄰地址。

cache在linux內核中有很多巧妙的應用，讀者可以在閱讀本書后面章節(jié)遇到類似的情況時細細體會，暫時先總結歸納如下。

（1）內核中常用的數據結構通常是和L1 cache對齊的。例如，mm_struct、fs_cache等數據結構使用“SLAB_HWCACHE_ALIGN”標志位來創(chuàng)建slab緩存描述符，見proc_caches_ init()函數。

（2）一些常用的數據結構在定義時就約定數據結構以L1 Cache對齊，使用“____cacheline_internodealigned_in_smp”和“____cacheline_aligned_in_smp”等宏來定義數據結構，例如struct zone、struct irqaction、softirq_vec[ ]、irq_stat[ ]、struct worker_pool等。

cache和內存交換的最小單位是cache line，若結構體沒有和cache line對齊，那么一個結構體有可能占用多個cache line。假設cache line的大小是32 Byte，一個本身小于32 Byte的結構體有可能橫跨了兩條cache line，在SMP中會對系統(tǒng)性能有不小的影響。舉個例子，現在有結構體C1和結構體C2，緩存到L1 Cache時沒有按照cache line對齊，因此它們有可能同時占用了一條cache line，即C1的后半部和C2的前半部在一條cache line中。根據cache一致性協(xié)議，CPU0修改結構體C1的時會導致CPU1的cache line失效，同理，CPU1對結構體C2修改也會導致CPU0的cache line失效。如果CPU0和CPU1反復修改，那么會導致系統(tǒng)性能下降。這種現象叫做“cache line偽共享”，兩個CPU原本沒有共享訪問，因為要共同訪問同一個cache line，產生了事實上的共享。解決上述問題的一個方法是讓結構體按照cache line對齊，典型地以空間換時間。include/linux/cache.h文件定義了有關cache相關的操作，其中____cacheline_aligned_in_smp的定義也在這個文件中，它和L1_CACHE_BYTES對齊。

      [include/linux/cache.h]

      #define SMP_CACHE_BYTES L1_CACHE_BYTES

      #define ____cacheline_aligned __attribute__ ((__aligned__ (SMP_CACHE_BYTES)))
      #define ____cacheline_aligned_in_smp ____cacheline_aligned

      #ifndef __cacheline_aligned
      #define __cacheline_aligned    \
        __attribute__ ((__aligned__ (SMP_CACHE_BYTES),  \
                __section__ (".data..cacheline_aligned")))
      #endif /* __cacheline_aligned */

      #define __cacheline_aligned_in_smp __cacheline_aligned
      #define ____cacheline_internodealigned_in_smp \
          __attribute__ ((__aligned__ (1 ＜＜ (INTERNODE_CACHE_SHIFT))))

（3）數據結構中頻繁訪問的成員可以單獨占用一個cache line，或者相關的成員在cache line中彼此錯開，以提高訪問效率。例如，struct zone數據結構中zone->lock和zone->lru_lock這兩個頻繁被訪問的鎖，可以讓它們各自使用不同的cache line，以提高獲取鎖的效率。

再比如struct worker_pool數據結構中的nr_running成員就獨占了一個cache line，避免多CPU同時讀寫該成員時引發(fā)其他臨近的成員“顛簸”現象，見第5.3節(jié)。

（4）slab的著色區(qū)，見第2.5節(jié)。

（5）自旋鎖的實現。在多CPU系統(tǒng)中，自旋鎖的激烈爭用過程導致嚴重的CPU cacheline bouncing現象，見第4章關于自旋鎖的部分內容。

13．請簡述ARM big.LITTLE架構，包括總線連接和cache管理等。

ARM提出大小核概念，即big.LITTLE架構，針對性能優(yōu)化過的處理器內核稱為大核，針對低功耗待機優(yōu)化過的處理器內核稱為小核。

如圖1.15所示，在典型big.LITTLE架構中包含了一個由大核組成的集群（Cortex-A57）和小核（Cortex-A53）組成的集群，每個集群都屬于傳統(tǒng)的同步頻率架構，工作在相同的頻率和電壓下。大核為高性能核心，工作在較高的電壓和頻率下，消耗更多的能耗，適用于計算繁重的任務。常見的大核處理器有\(zhòng)2ortex-A15、Cortex-A57、Cortex-A72和Cortex-A73。小核性能雖然較低，但功耗比較低，在一些計算負載不大的任務中，不用開啟大核，直接用小核即可，常見的小核處理器有Cortex-A7和Cortex-A53。

圖1.15 典型的big.LITTLE架構

如圖1.16所示是4核Cortex-A15和4核Cortex-A7的系統(tǒng)總線框圖。

? Quad Cortex-A15：大核CPU簇。

? Quad Cortex-A7：小核CPU簇。

圖1.16 4核A15和4核A7的系統(tǒng)總線框圖

? CCI-400模塊：用于管理大小核架構中緩存一致性的互連模塊。CCI-400只能支持兩個CPU簇（cluster），而最新款的CCI-550可以支持6個CPU簇。

? DMC-400：內存控制器。

? NIC-400：用于AMBA總線協(xié)議的連接，可以支持AXI、AHB和APB總線的連接。

? MMU-400：系統(tǒng)內存管理單元。

? Mali-T604：圖形加速控制器。

? GIC-400：中斷控制器。

ARM CoreLink CCI-400模塊用于維護大小核集群的數據互聯(lián)和cache一致性。大小核集群作為主設備（Master），通過支持ACE協(xié)議的從設備接口（Slave）連接到CCI-400上，它可以管理大小核集群中的cache一致性和實現處理器間的數據共享。此外，它還支持3個ACE-Lite從設備接口（ACE-Lite Slave Interface），可以支持一些IO主設備，例如GPU Mali-T604。通過ACE-Lite協(xié)議，GPU可以監(jiān)聽處理器的cache。CCI-400還支持3個ACE-Lite主設備接口，例如通過DMC-400來連接LP-DDR2/3或DDR內存設備，以及通過NIC-400總線來連接一些外設，例如DMA設備和LCD等。

ACE協(xié)議，全稱為AMBA AXI Coherency Extension協(xié)議，是AXI4協(xié)議的擴展協(xié)議，增加了很多特性來支持系統(tǒng)級硬件一致性。模塊之間共享內存不需要軟件干預，硬件直接管理和維護各個cache之間的一致性，這可以大大減少軟件的負載，最大效率地使用cache，減少對內存的訪問，進而降低系統(tǒng)功耗。

14.cache coherency和memory consistency有什么區(qū)別？

cache coherency高速緩存一致性關注的是同一個數據在多個cache和內存中的一致性問題，解決高速緩存一致性的方法主要是總線監(jiān)聽協(xié)議，例如MESI協(xié)議等。而memory consistency關注的是處理器系統(tǒng)對多個地址進行存儲器訪問序列的正確性，學術上對內存訪問模型提出了很多，例如嚴格一致性內存模型、處理器一致性內存模型，以及弱一致性內存模型等。弱內存訪問模型在現在處理器中得到廣泛應用，因此內存屏障指令也得到廣泛應用。

15．請簡述cache的write back有哪些策略。

在處理器內核中，一條存儲器讀寫指令經過取指、譯碼、發(fā)射和執(zhí)行等一系列操作之后，率先到達LSU部件。LSU部件包括Load Queue和Store Queue，是指令流水線的一個執(zhí)行部件，是處理器存儲子系統(tǒng)的最頂層，連接指令流水線和cache的一個支點。存儲器讀寫指令通過LSU之后，會到達L1 cache控制器。L1 cache控制器首先發(fā)起探測（Probe）操作，對于讀操作發(fā)起cache讀探測操作并將帶回數據，寫操作發(fā)起cache寫探測操作。寫探測操作之前需要準備好待寫的cache line，探測工作返回時將會帶回數據。當存儲器寫指令獲得最終數據并進行提交操作之后才會將數據寫入，這個寫入可以Write Through或者Write Back。

對于寫操作，在上述的探測過程中，如果沒有找到相應的cache block，那么就是Write Miss，否則就是Write Hit。對于Write Miss的處理策略是Write-Allocate，即L1 cache控制器將分配一個新的cache line，之后和獲取的數據進行合并，然后寫入L1 cache中。

如果探測的過程是Write Hit，那么真正寫入有兩種模式。

? Write Through（直寫模式）：進行寫操作時，數據同時寫入當前的cache、下一級cache或主存儲器中。Write Through策略可以降低cache一致性的實現難度，其最大的缺點是消耗比較多的總線帶寬。

? Write Back（回寫模式）：在進行寫操作時，數據直接寫入當前cache，而不會繼續(xù)傳遞，當該Cache Line被替換出去時，被改寫的數據才會更新到下一級cache或主存儲器中。該策略增加了cache一致性的實現難度，但是有效降低了總線帶寬需求。

16．請簡述cache line的替換策略。

由于cache的容量遠小于主存儲器，當Cache Miss發(fā)生時，不僅僅意味著處理器需要從主存儲器中獲取數據，而且需要將cache的某個cache line替換出去。在cache的Tag陣列中，除了具有地址信息之外還有cache block的狀態(tài)信息。不同的cache一致性策略使用的cache狀態(tài)信息并不相同。在MESI協(xié)議中，一個cache block通常含有M、E、S和I這4個狀態(tài)位。

cache的替換策略有隨機法（Random policy）、先進先出法（FIFO）和最近最少使用算法（LRU）。

? 隨機法：隨機地確定替換的cache block，由一個隨機數產生器來生成隨機數確定替換塊，這種方法簡單，易于實現，但命中率比較低。

? 先進先出法：選擇最先調入的那個cache block進行替換，最先調入的塊有可能被多次命中，但是被優(yōu)先替換，因而不符合局部性規(guī)律。

? 最近最少使用算法：LRU算法根據各塊使用的情況，總是選擇最近最少使用的塊來替換，這種算法較好地反映了程序局部性規(guī)律。

在Cortex-A57處理器中，L1 cache采用LRU算法，而L2 cache采用隨機算法。在最新的Cortex-A72處理器中，L2 cache采有偽隨機算法（pseudo-random policy）或偽LRU算法（pseudo-least-recently-used policy）。

17．多進程間頻繁切換對TLB有什么影響？現代的處理器是如何面對這個問題的？

在現代處理器中，軟件使用虛擬地址訪問內存，而處理器的MMU單元負責把虛擬地址轉換成物理地址，為了完成這個映射過程，軟件和硬件共同來維護一個多級映射的頁表。當處理器發(fā)現頁表中無法映射到對應的物理地址時，會觸發(fā)一個缺頁異常，掛起出錯的進程，操作系統(tǒng)軟件需要處理這個缺頁異常。我們之前有提到過二級頁表的查詢過程，為了完成虛擬地址到物理地址的轉換，查詢頁表需要兩次訪問內存，即一級頁表和二級頁表都是存放在內存中的。

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系統(tǒng)都采用UMA的內存架構（Uniform Memory Architechture），即內存是統(tǒng)一結構和統(tǒng)一尋址。對稱多處理器（Symmetric Multiple Processing, SMP）系統(tǒng)大部分都采用UMA內存架構。因此在UMA架構的系統(tǒng)中有如下特點。

? 所有硬件資源都是共享的，每個處理器都能訪問到系統(tǒng)中的內存和外設資源。

? 所有處理器都是平等關系。

? 統(tǒng)一尋址訪問內存。

? 處理器和內存通過內部的一條總線連接在一起。

如圖1.17所示，SMP系統(tǒng)相對比較簡潔，但是缺點也很明顯。因為所有對等的處理器都通過一條總線連接在一起，隨著處理器數量的增多，系統(tǒng)總線成為系統(tǒng)的最大瓶頸。

圖1.17 SMP架構示意圖

NUMA系統(tǒng)是從SMP系統(tǒng)演化過來的。如圖1.18所示，NUMA系統(tǒng)由多個內存節(jié)點組成，整個內存體系可以作為一個整體，任何處理器都可以訪問，只是處理器訪問本地內存節(jié)點擁有更小的延遲和更大的帶寬，處理器訪問遠程內存節(jié)點速度要慢一些。每個處理器除了擁有本地的內存之外，還可以擁有本地總線，例如PCIE、STAT等。

圖1.18 NUMA架構示意圖

現在的x86陣營的服務器芯片早已支持NUMA架構了，例如Intel的至強服務器。對于ARM陣營，2016年Cavium公司發(fā)布的基于ARMv8-A架構設計的服務器芯片“ThunderX2”也開始支持NUMA架構。

19.ARM從Cortex系列開始性能有了質的飛越，比如Cortex-A8/A15/A53/A72，請說說Cortex系列在芯片設計方面做了哪些重大改進？

計算機體系結構是一個權衡的藝術，尺有所短，寸有所長。在處理器領域經歷多年的優(yōu)勝劣汰，市面上流行的處理器內核在技術上日漸趨同。

ARM處理器在Cortex系列之后，加入了很多現代處理器的一些新技術和特性，已經具備了和Intel一較高下的能力，例如2016年發(fā)布的Cortex-A73處理器。

2005年發(fā)布的Cortex-A8內核是第一個引入超標量技術的ARM處理器，它在每個時鐘周期內可以并行發(fā)射兩條指令，但依然使用靜態(tài)調度的流水線和順序執(zhí)行方式。Cortex-A8內核采用13級整型指令流水線和10級NEON指令流水線。分支目標緩沖器（Branch Target Buffer, BTB）使用的條目數增加到512，同時設置了全局歷史緩沖器（Global History Buffer, GHB）和返回堆棧（Return Stack, RS）部件，這些措施極大地提高了指令分支預測的成功率。另外，還加入了way-prediction部件。

2007年Cortex-A9發(fā)布，引入了亂序執(zhí)行和猜測執(zhí)行機制以及擴大L2 cache的容量。

2010年Cortex-A15發(fā)布，最高主頻可以到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指令，以充分利用指令流水線中的多個并發(fā)執(zhí)行單元。指令譯碼單元為3路指令譯碼，在一個時鐘周期可以同時譯碼3條指令。

2012年發(fā)布64位的Cortex-A53和Cortex-A57, ARM開始進軍服務器領域。Cortex-A57是首款支持64位的ARM處理器內核，采用3發(fā)亂序執(zhí)行流水線（Out-of-Order pipeline），并且增加數據預取功能。

2015年發(fā)布Cortex-A57的升級版本Cortex-A72，如圖1.19所示。A72在A57架構的基礎上做了大量優(yōu)化工作，包括新的分支預測單元，改善解碼流水線設計等。在指令分發(fā)單元（Dispatch）也做了很大優(yōu)化，由原來A57架構的3發(fā)射變成了5發(fā)射，同時發(fā)射5條指令，并且還支持并行執(zhí)行8條微操作指令，從而提高解碼器的吞吐量。

圖1.19 Cortex-A72處理器架構圖

最新近展

最近幾年，x86和ARM陣營都在各自領域中不斷創(chuàng)新。異構計算是一個很熱門的技術方向，比如Intel公司最近發(fā)布了集成FPGA的至強服務器芯片。FPGA可以在客戶的關鍵算法中提供可編程、高性能的加速能力，另外提供了靈活性，關鍵算法的更新優(yōu)化，不需要購買大量新硬件。在數據中心領域，從事海量數據處理的應用中有不少關鍵算法需要優(yōu)化，如密鑰加速、圖像識別、語音轉換、文本搜索等。在安防監(jiān)控領域，FPGA可以實現對大量車牌的并行分析。強大的至強處理器加上靈活高效的FPGA會給客戶在云計算、人工智能等新興領域帶來新的技術創(chuàng)新。對于ARM陣營，ARM公司發(fā)布了最新的Cortex-A75處理器以及最新處理器架構DynamIQ等新技術。DynmaIQ技術新增了針對機器學習和人工智能的全新處理器指令集，并增加了多核配置的靈活性。另外ARM公司也發(fā)布了一個用于數據中心應用的指令集——Scalable Vector Extensions，最高支持2048 bit可伸縮的矢量計算。

除了x86和ARM兩大陣營的創(chuàng)新外，最近幾年開源指令集（指令集架構，Instruction Set Architecture, ISA）也是很火熱的新發(fā)展方向。開源指令集的代表作是OpenRISC，并且Open Risk已經被Linux內核接受，成為官方Linux內核支持的一種體系結構。但是由于OpenRISC是由愛好者維護的，因此更新緩慢。最近幾年，伯克利大學正在嘗試重新設計一個全新的開源指令集，并且不受專利的約束和限制，這就是RISC-V，其中“V”表示變化（variation）和向量（vectors）。RISC-V包含一個非常小的基礎指令集和一系列可選的擴展指令集，最基礎的指令集只包含40條指令，通過擴展可以支持64位和128位運算以及變長指令。

伯克利大學對RISC-V指令集不斷改進，迅速得到工業(yè)界和學術屆的關注。2016年，RISC-V基金會成立，成員包括谷歌、惠普、甲骨文、西部數據、華為等巨頭，未來這些大公司非常有可能會將RISC-V運用到云計算或者IoT等產品中。RISC-V指令集類似Linux內核，是一個開源的、現代的、沒有專利問題和歷史包袱的全新指令集，并且以BSD許可證發(fā)布。

目前RISC-V已經進入了GCC/Binutils的主線，相信很快也會被官方Linux內核接受。另外目前已經有多款開源和閉源的RISC-V CPU的實現，很多第三方工具和軟件廠商也開始支持RISC-V。RISC-V是否會變成開源硬件或是開源芯片領域的Linux呢？讓我們拭目以待吧！

推薦書籍

計算機體系結構是一門計算機科學的基礎課程，除了閱讀ARM的芯片手冊以外，還可以閱讀一些經典的書籍和文章。

? 《計算機體系結構：量化研究方法》，英文版是《Computer Architecture : A Quantitative》，作者John L. Hennessy, David A. Patterson。

? 《計算機組成與體系結構：性能設計》，作者William Stallings。

? 《大話處理器：處理器基礎知識讀本》，作者萬木楊。

? 《淺談cache memory》，作者王齊。

? 《ARM與x86》，作者王齊。

? 《現代體系結構上的UNIX系統(tǒng)：內核程序員的對稱多處理和緩存技術》，作者Curt Schimmel。