CPU緩存一致性原理

cpu速度和內(nèi)存速度比值，目前比值是100:1的關(guān)系，一個(gè)做計(jì)算的，一個(gè)做存儲(chǔ)，相互之間怎么比速度？

這個(gè)速度是指：cpu內(nèi)部的ALU計(jì)算單元訪問(wèn)內(nèi)部的寄存器，如果耗時(shí)是1個(gè)納秒，計(jì)算單元通過(guò)數(shù)據(jù)總線去訪問(wèn)內(nèi)存需要100納秒，這個(gè)速度是指訪問(wèn)某個(gè)寄存器的速度并不是計(jì)算的速度，ALU訪問(wèn)寄存器的速度比訪問(wèn)內(nèi)存的速度快100倍。

為什么ALU訪問(wèn)寄存器的速度快，因?yàn)锳LU和寄存器離的近。

內(nèi)存中有一個(gè)數(shù)組，訪問(wèn)數(shù)組中第一個(gè)元素?cái)?shù)據(jù)需要100納秒，訪問(wèn)第二個(gè)數(shù)據(jù)100納秒，所以cpu至少有99個(gè)時(shí)間單元都得等著從內(nèi)存中返回?cái)?shù)據(jù)給ALU使用。

為了充分利用cpu的速度，一般往往在中間設(shè)計(jì)緩存的存在，cpu訪問(wèn)緩存的速度比訪問(wèn)內(nèi)存的速度要快。

訪問(wèn)數(shù)組中第一個(gè)數(shù)據(jù)的時(shí)候，把整個(gè)數(shù)組放到緩存中來(lái)，下次cpu訪問(wèn)的時(shí)候從緩存中訪問(wèn)。

不要內(nèi)存完全可以，但工業(yè)上需要考慮一個(gè)性價(jià)比，數(shù)據(jù)都放在寄存器中太貴了，8個(gè)G的內(nèi)存400塊錢，8個(gè)G的寄存器40萬(wàn)，寄存器稍微貴一點(diǎn)點(diǎn)的、容量稍微小一點(diǎn)的還可以承受，比如8個(gè)G的內(nèi)存，1個(gè)G的寄存器。

不是所有的數(shù)據(jù)都放在寄存器中，在這里有專門的算法LRU(Least Recently Used 淘汰最近未使用的)或LFU（least frequently used淘汰不經(jīng)常使用的），這個(gè)算法決定著什么樣的數(shù)據(jù)挪過(guò)來(lái)，什么樣的數(shù)據(jù)挪出去。

緩存是均衡的設(shè)計(jì)，在省錢和讀取、寫入的效率之間均衡。加了一層緩存之后，發(fā)現(xiàn)cpu到這個(gè)緩存之間的速度還是慢很多，再加一層，

三級(jí)緩存是工業(yè)實(shí)現(xiàn)中的一個(gè)妥協(xié)，也許不久的將來(lái)，cpu的速度超級(jí)快，可能需要四層緩存或內(nèi)存的速度快很多，也許就一層緩存，目前的工業(yè)實(shí)踐，多采用三級(jí)緩存的結(jié)構(gòu)。

線程和cpu之間的關(guān)系密不可分，一顆cpu在同一個(gè)時(shí)間只能執(zhí)行一個(gè)線程，cpu的計(jì)算也代表著線程的計(jì)算。

多核CPU

這是一顆cpu，在cpu內(nèi)部往往有多個(gè)核存在，每一個(gè)核都有自己的ALU、寄存器、程序計(jì)數(shù)器，一級(jí)緩存和二級(jí)緩存都在這個(gè)核里，三級(jí)緩存是多個(gè)核共享。

ALU的計(jì)算單元需要把讀到的數(shù)據(jù)放到寄存器，寄存器會(huì)去尋找想要的數(shù)據(jù)，首先去一級(jí)緩存找，沒有的話，再去二級(jí)緩存找，還沒有的話，再去三級(jí)緩存找，三級(jí)緩存把數(shù)據(jù)傳給二級(jí)緩存，二級(jí)緩存把數(shù)據(jù)傳給一級(jí)緩存，一級(jí)緩存把數(shù)據(jù)傳給寄存器，下一次再訪問(wèn)數(shù)據(jù)的時(shí)候直接去一級(jí)緩存中拿。

超線程

雖然只有一個(gè)計(jì)算單元ALU，但是有2套存儲(chǔ)單元、2套寄存器、2套程序計(jì)數(shù)器，一個(gè)核可以裝2個(gè)線程的數(shù)據(jù)進(jìn)來(lái)，計(jì)算單元輪著計(jì)算，2個(gè)線程就不需要來(lái)回切換了，即一個(gè)核2個(gè)線程，2個(gè)核4個(gè)線程，4個(gè)核8個(gè)線程。

需要訪問(wèn)內(nèi)存中某個(gè)數(shù)組中的第一個(gè)元素?cái)?shù)據(jù)，先在一級(jí)緩存找，再找二級(jí)、三級(jí)，都沒有的話，去內(nèi)存中找，內(nèi)存中找到之后，返回給三級(jí)緩存、二級(jí)緩存、一級(jí)緩存，最后再給到寄存器， ALU做計(jì)算的時(shí)候就可以直接訪問(wèn)寄存器獲取數(shù)據(jù)了。

站在計(jì)算單元的角度，訪問(wèn)數(shù)組中第一個(gè)元素?cái)?shù)據(jù)很可能會(huì)訪問(wèn)第二個(gè)元素?cái)?shù)據(jù)，如果第二個(gè)元素?cái)?shù)據(jù)也沒有，同樣的方式又得來(lái)一遍，那這樣的話還不如直接從內(nèi)存讀呢！

緩存行

當(dāng)要訪問(wèn)一個(gè)數(shù)據(jù)的時(shí)候，干脆每一次緩存一小塊的數(shù)據(jù)，這一小塊數(shù)據(jù)里面包含了整個(gè)數(shù)組的數(shù)據(jù)，當(dāng)訪問(wèn)數(shù)組中的任意元素?cái)?shù)據(jù)的時(shí)候，就可以直接從緩存中讀取到了，這一塊的數(shù)據(jù)被稱為緩存行。

這個(gè)理論被稱為程序的局部性原理，而局部性原理分為空間局部性和時(shí)間局部性。

根據(jù)大多數(shù)工業(yè)證明，在訪問(wèn)局部數(shù)據(jù)的時(shí)候，會(huì)很快的訪問(wèn)相鄰的數(shù)據(jù)，這就是空間局部性。

時(shí)間局部性是執(zhí)行完這條指令之后，很可能執(zhí)行和它挨著的下一條指令，如果指令也看做是一份二進(jìn)制0101數(shù)據(jù)的話，也可以一次性的把很多指令讀取過(guò)來(lái)。

緩存行數(shù)據(jù)是大了好還是小了好？

如果這一行數(shù)據(jù)特別大，一次性可以放好多數(shù)據(jù)過(guò)來(lái)，好處就是訪問(wèn)的時(shí)候命中率會(huì)更高，但是每讀一塊數(shù)據(jù)過(guò)來(lái)效率會(huì)很低；數(shù)據(jù)小的話，讀起來(lái)速度會(huì)很快但命中率會(huì)較低。

目前計(jì)算機(jī)多采用64個(gè)字節(jié)（64*8bit）為一緩存行數(shù)據(jù)。

緩存行對(duì)齊，偽共享

創(chuàng)建一個(gè)數(shù)組，里面存放了2個(gè)T類對(duì)象元素，T類中有一個(gè)long類型的x字段，long類型長(zhǎng)度是8個(gè)bytes。

2個(gè)線程，意味著有2顆cpu在同時(shí)運(yùn)行，第一個(gè)線程玩命的修改數(shù)組中的第一個(gè)元素t1，改了10億次，第二個(gè)線程玩命的修改數(shù)組中的第二個(gè)元素t2，也改了10億次，總共耗時(shí)700多毫秒。

對(duì)T類做了修改，

因?yàn)橐粋€(gè)緩存行大小為64字節(jié)，所以在屬性x前面加了7個(gè)屬性（7*8字節(jié)=56個(gè)字節(jié)），加上x共64個(gè)字節(jié)，x后面也加了56個(gè)字節(jié)，正好將一個(gè)x值，放在一個(gè)緩存行里，計(jì)算結(jié)果耗時(shí)240多毫秒，數(shù)據(jù)越多執(zhí)行效率反而越高了。在介紹原理之前，先介紹下緩存一致性協(xié)議，

緩存一致性協(xié)議

假設(shè)有2個(gè)數(shù)據(jù)x、y位于同一緩存行，在第一個(gè)計(jì)算單元（cpu或線程）里面只使用了x，第二個(gè)線程里面只使用了y，雖然在內(nèi)存中是同一份數(shù)據(jù)，但是到緩存之后，是2份拷貝數(shù)據(jù)，每一個(gè)用到它的cpu都會(huì)有它的一份拷貝存在，一個(gè)cpu對(duì)這份數(shù)據(jù)做了修改之后，另外cpu也需要同步到最新的數(shù)據(jù)。

有了緩存的概念，必須要保證緩存的數(shù)據(jù)一致性即緩存一致性協(xié)議，每種cpu廠商都有自己完全不同的緩存一致性協(xié)議，常見的是MESI（因特爾的緩存一致性協(xié)議），這是緩存一致性協(xié)議的一種實(shí)現(xiàn)。

cpu每個(gè)緩存行標(biāo)記有4種狀態(tài)：Modified(被修改)，Exclusive（獨(dú)占）、Shared(共享)、Invalid(無(wú)效)。

一個(gè)cpu將一個(gè)緩存行中的數(shù)據(jù)修改了，需要一種機(jī)制：通知使用該緩存行的其他cpu數(shù)據(jù)已失效，需要重新再讀取一遍，獲取最新修改的數(shù)據(jù)。

有些無(wú)法被緩存的數(shù)據(jù)，比如一份的數(shù)據(jù)超過(guò)了64個(gè)字節(jié)，則需要使用總線鎖。

再回到上面的那個(gè)問(wèn)題，為什么數(shù)據(jù)越多執(zhí)行效率反而越高了？

一個(gè)long類型的x是8個(gè)字節(jié)，這2個(gè)x位于同一個(gè)緩存行的概率極大（尤其這2個(gè)x位于同一個(gè)數(shù)組，在內(nèi)存中是挨著的），2個(gè)cpu分別修改一個(gè)x，2個(gè)x在一方cpu都有緩存，修改了其中一個(gè)需要通知另外一個(gè)，每改一次通知一下，總之在修改的時(shí)候需要觸發(fā)一種機(jī)制需要另外的cpu跟我保持一致，如果這樣的話，耗時(shí)當(dāng)然會(huì)比較長(zhǎng)。

在x前后加56個(gè)字節(jié)，無(wú)論怎么刷新緩存，這個(gè)x都不會(huì)和另外一個(gè)x位于同一緩存行，這意味著這個(gè)cpu修改了第一個(gè)x的時(shí)候，是不需要通知任何其他cpu的，第二個(gè)cpu修改第二個(gè)x的時(shí)候，也是不需要通知第一個(gè)cpu的，速度一定會(huì)很快。

jdk 7寫的LinkedBlockQueue也是這種寫法或者獲得杜克獎(jiǎng)的開源軟件Disruptor中的環(huán)形隊(duì)列也是這種寫法，

Disruptor（環(huán)形隊(duì)列）號(hào)稱是最快的單機(jī)mq；實(shí)現(xiàn)鏈表一般需要2個(gè)指針，一個(gè)是頭指針，一個(gè)是尾指針，而這個(gè)環(huán)形隊(duì)列，只要有一個(gè)指針就可以了，

指針指向這個(gè)位置就往這存，指向下個(gè)位置就往下一個(gè)位置存，什么時(shí)候存滿了，就等著最開始存的那個(gè)被消費(fèi)走，消費(fèi)走了繼續(xù)往這里存，一個(gè)指針來(lái)回轉(zhuǎn)，速度非常快。

由于有多個(gè)生產(chǎn)者和多個(gè)消費(fèi)者，在多線程的情況下這個(gè)環(huán)形的指針就會(huì)被多個(gè)線程讀到自己的緩存里，

第一個(gè)屬性是起始值，后面是7個(gè)無(wú)業(yè)務(wù)含義的數(shù)據(jù)，其存在的目的是可以保證p1屬性往后組合的時(shí)候不會(huì)和別的p1屬性位于同一個(gè)緩存行。

但是說(shuō)不準(zhǔn)會(huì)往前面組合呢即為什么沒有前面的7個(gè)呢？也是有的，在父類的父類中定義的，

數(shù)組中前連續(xù)的2個(gè)元素是2個(gè)RingBuffer對(duì)象，一個(gè)對(duì)象所占用的字節(jié)57+8+56，所以可以確保一個(gè)緩存行中只有一個(gè)元素，那么在多線程的情況下對(duì)不同元素的修改不會(huì)互相通知，互相影響。

以上便是cpu級(jí)別的并發(fā)控制之緩存一致性的描述。

審核編輯：湯梓紅