3.3.3 寫入時的行為

在我們開始研究多個線程或進程同時使用相同內存之前，先來看一下緩存實現的一些細節。我們要求緩存是一致的，而且這種一致性必須對用戶級代碼完全透明。而內核代碼則有所不同，它有時候需要對緩存進行轉儲(flush)。

這意味著，如果對緩存線進行了修改，那么在這個時間點之后，系統的結果應該是與沒有緩存的情況下是相同的，即主存的對應位置也已經被修改的狀態。這種要求可以通過兩種方式或策略實現：

• 寫通(write-through)
• 寫回(write-back)

寫通比較簡單。當修改緩存線時，處理器立即將它寫入主存。這樣可以保證主存與緩存的內容永遠保持一致。當緩存線被替代時，只需要簡單地將它丟棄即可。這種策略很簡單，但是速度比較慢。如果某個程序反復修改一個本地變量，可能導致FSB上產生大量數據流，而不管這個變量是不是有人在用，或者是不是短期變量。

寫回比較復雜。當修改緩存線時，處理器不再馬上將它寫入主存，而是打上已弄臟(dirty)的標記。當以后某個時間點緩存線被丟棄時，這個已弄臟標記會通知處理器把數據寫回到主存中，而不是簡單地扔掉。

寫回有時候會有非常不錯的性能，因此較好的系統大多采用這種方式。采用寫回時，處理器們甚至可以利用FSB的空閑容量來存儲緩存線。這樣一來，當需要緩存空間時，處理器只需清除臟標記，丟棄緩存線即可。

但寫回也有一個很大的問題。當有多個處理器(或核心、超線程)訪問同一塊內存時，必須確保它們在任何時候看到的都是相同的內容。如果緩存線在其中一個處理器上弄臟了(修改了，但還沒寫回主存)，而第二個處理器剛好要讀取同一個內存地址，那么這個讀操作不能去讀主存，而需要讀第一個處理器的緩存線。在下一節中，我們將研究如何實現這種需求。

在此之前，還有其它兩種緩存策略需要提一下:

• 寫入合并
• 不可緩存

這兩種策略用于真實內存不支持的特殊地址區，內核為地址區設置這些策略(x86處理器利用內存類型范圍寄存器MTRR)，余下的部分自動進行。MTRR還可用于寫通和寫回策略的選擇。

寫入合并是一種有限的緩存優化策略，更多地用于顯卡等設備之上的內存。由于設備的傳輸開銷比本地內存要高的多，因此避免進行過多的傳輸顯得尤為重要。如果僅僅因為修改了緩存線上的一個字，就傳輸整條線，而下個操作剛好是修改線上的下一個字，那么這次傳輸就過于浪費了。而這恰恰對于顯卡來說是比較常見的情形——屏幕上水平鄰接的像素往往在內存中也是靠在一起的。顧名思義，寫入合并是在寫出緩存線前，先將多個寫入訪問合并起來。在理想的情況下，緩存線被逐字逐字地修改，只有當寫入最后一個字時，才將整條線寫入內存，從而極大地加速內存的訪問。

最后來講一下不可緩存的內存。一般指的是不被RAM支持的內存位置，它可以是硬編碼的特殊地址，承擔CPU以外的某些功能。對于商用硬件來說，比較常見的是映射到外部卡或設備的地址。在嵌入式主板上，有時也有類似的地址，用來開關LED。對這些地址進行緩存顯然沒有什么意義。比如上述的LED，一般是用來調試或報告狀態，顯然應該盡快點亮或關閉。而對于那些PCI卡上的內存，由于不需要CPU的干涉即可更改，也不該緩存。

3.3.4 多處理器支持

在上節中我們已經指出當多處理器開始發揮作用的時候所遇到的問題。甚至對于那些不共享的高速級別的緩存（至少在L1d級別）的多核處理器也有問題。

直接提供從一個處理器到另一處理器的高速訪問，這是完全不切實際的。從一開始，連接速度根本就不夠快。實際的選擇是，在其需要的情況下，轉移到其他處理器。需要注意的是，這同樣應用在相同處理器上無需共享的高速緩存。

現在的問題是，當該高速緩存線轉移的時候會發生什么？這個問題回答起來相當容易：當一個處理器需要在另一個處理器的高速緩存中讀或者寫的臟的高速緩存線的時候。但怎樣處理器怎樣確定在另一個處理器的緩存中的高速緩存線是臟的？假設它僅僅是因為一個高速緩存線被另一個處理器加載將是次優的（最好的）。通常情況下，大多數的內存訪問是只讀的訪問和產生高速緩存線，并不臟。在高速緩存線上處理器頻繁的操作（當然，否則為什么我們有這樣的文件呢？），也就意味著每一次寫訪問后，都要廣播關于高速緩存線的改變將變得不切實際。

多年來，人們開發除了MESI緩存一致性協議(MESI=Modified, Exclusive, Shared, Invalid，變更的、獨占的、共享的、無效的)。協議的名稱來自協議中緩存線可以進入的四種狀態:

• 變更的: 本地處理器修改了緩存線。同時暗示，它是所有緩存中唯一的拷貝。
• 獨占的: 緩存線沒有被修改，而且沒有被裝入其它處理器緩存。
• 共享的: 緩存線沒有被修改，但可能已被裝入其它處理器緩存。
• 無效的: 緩存線無效，即，未被使用。

MESI協議開發了很多年，最初的版本比較簡單，但是效率也比較差。現在的版本通過以上4個狀態可以有效地實現寫回式緩存，同時支持不同處理器對只讀數據的并發訪問。

在協議中，通過處理器監聽其它處理器的活動，不需太多努力即可實現狀態變更。處理器將操作發布在外部引腳上，使外部可以了解到處理過程。目標的緩存線地址則可以在地址總線上看到。在下文講述狀態時，我們將介紹總線參與的時機。

一開始，所有緩存線都是空的，緩存為無效(Invalid)狀態。當有數據裝進緩存供寫入時，緩存變為變更(Modified)狀態。如果有數據裝進緩存供讀取，那么新狀態取決于其它處理器是否已經狀態了同一條緩存線。如果是，那么新狀態變成共享(Shared)狀態，否則變成獨占(Exclusive)狀態。

如果本地處理器對某條Modified緩存線進行讀寫，那么直接使用緩存內容，狀態保持不變。如果另一個處理器希望讀它，那么第一個處理器將內容發給第一個處理器，然后可以將緩存狀態置為Shared。而發給第二個處理器的數據由內存控制器接收，并放入內存中。如果這一步沒有發生，就不能將這條線置為Shared。如果第二個處理器希望的是寫，那么第一個處理器將內容發給它后，將緩存置為Invalid。這就是臭名昭著的”請求所有權(Request For Ownership,RFO)”操作。在末級緩存執行RFO操作的代價比較高。如果是寫通式緩存，還要加上將內容寫入上一層緩存或主存的時間，進一步提升了代價。 對于Shared緩存線，本地處理器的讀取操作并不需要修改狀態，而且可以直接從緩存滿足。而本地處理器的寫入操作則需要將狀態置為Modified，而且需要將緩存線在其它處理器的所有拷貝置為Invalid。因此，這個寫入操作需要通過RFO消息發通知其它處理器。如果第二個處理器請求讀取，無事發生。因為主存已經包含了當前數據，而且狀態已經為Shared。如果第二個處理器需要寫入，則將緩存線置為Invalid。不需要總線操作。

Exclusive狀態與Shared狀態很像，只有一個不同之處: 在Exclusive狀態時，本地寫入操作不需要在總線上聲明，因為本地的緩存是系統中唯一的拷貝。這是一個巨大的優勢，所以處理器會盡量將緩存線保留在Exclusive狀態，而不是Shared狀態。只有在信息不可用時，才退而求其次選擇shared。放棄Exclusive不會引起任何功能缺失，但會導致性能下降，因為E→M要遠遠快于S→M。

從以上的說明中應該已經可以看出，在多處理器環境下，哪一步的代價比較大了。填充緩存的代價當然還是很高，但我們還需要留意RFO消息。一旦涉及RFO，操作就快不起來了。

RFO在兩種情況下是必需的:

• 線程從一個處理器遷移到另一個處理器，需要將所有緩存線移到新處理器。
• 某條緩存線確實需要被兩個處理器使用。{對于同一處理器的兩個核心，也有同樣的情況，只是代價稍低。RFO消息可能會被發送多次。}

多線程或多進程的程序總是需要同步，而這種同步依賴內存來實現。因此，有些RFO消息是合理的，但仍然需要盡量降低發送頻率。除此以外，還有其它來源的RFO。在第6節中，我們將解釋這些場景。緩存一致性協議的消息必須發給系統中所有處理器。只有當協議確定已經給過所有處理器響應機會之后，才能進行狀態躍遷。也就是說，協議的速度取決于最長響應時間。{這也是現在能看到三插槽AMD Opteron系統的原因。這類系統只有三個超級鏈路(hyperlink)，其中一個連接南橋，每個處理器之間都只有一跳的距離。}總線上可能會發生沖突，NUMA系統的延時很大，突發的流量會拖慢通信。這些都是讓我們避免無謂流量的充足理由。

此外，關于多處理器還有一個問題。雖然它的影響與具體機器密切相關，但根源是唯一的——FSB是共享的。在大多數情況下，所有處理器通過唯一的總線連接到內存控制器(參見圖2.1)。如果一個處理器就能占滿總線(十分常見)，那么共享總線的兩個或四個處理器顯然只會得到更有限的帶寬。

即使每個處理器有自己連接內存控制器的總線，如圖2.2，但還需要通往內存模塊的總線。一般情況下，這種總線只有一條。退一步說，即使像圖2.2那樣不止一條，對同一個內存模塊的并發訪問也會限制它的帶寬。

對于每個處理器擁有本地內存的AMD模型來說，也是同樣的問題。的確，所有處理器可以非常快速地同時訪問它們自己的內存。但是，多線程呢？多進程呢？它們仍然需要通過訪問同一塊內存來進行同步。

對同步來說，有限的帶寬嚴重地制約著并發度。程序需要更加謹慎的設計，將不同處理器訪問同一塊內存的機會降到最低。以下的測試展示了這一點，還展示了與多線程代碼相關的其它效果。

多線程測量

為了幫助大家理解問題的嚴重性，我們來看一些曲線圖，主角也是前文的那個程序。只不過這一次，我們運行多個線程，并測量這些線程中最快那個的運行時間。也就是說，等它們全部運行完是需要更長時間的。我們用的機器有4個處理器，而測試是做多跑4個線程。所有處理器共享同一條通往內存控制器的總線，另外，通往內存模塊的總線也只有一條。

圖3.19展示了順序讀訪問時的性能，元素為128字節長(64位計算機，NPAD=15)。對于單線程的曲線，我們預計是與圖3.11相似，只不過是換了一臺機器，所以實際的數字會有些小差別。

更重要的部分當然是多線程的環節。由于是只讀，不會去修改內存，不會嘗試同步。但即使不需要RFO，而且所有緩存線都可共享，性能仍然分別下降了18%(雙線程)和34%(四線程)。由于不需要在處理器之間傳輸緩存，因此這里的性能下降完全由以下兩個瓶頸之一或同時引起: 一是從處理器到內存控制器的共享總線，二是從內存控制器到內存模塊的共享總線。當工作集超過L3后，三種情況下都要預取新元素，而即使是雙線程，可用的帶寬也無法滿足線性擴展(無懲罰)。

當加入修改之后，場面更加難看了。圖3.20展示了順序遞增測試的結果。

圖中Y軸采用的是對數刻度，不要被看起來很小的差值欺騙了。現在，雙線程的性能懲罰仍然是18%，但四線程的懲罰飆升到了93%！原因在于，采用四線程時，預取的流量與寫回的流量加在一起，占滿了整個總線。

我們用對數刻度來展示L1d范圍的結果。可以發現，當超過一個線程后，L1d就無力了。單線程時，僅當工作集超過L1d時訪問時間才會超過20個周期，而多線程時，即使在很小的工作集情況下，訪問時間也達到了那個水平。

這里并沒有揭示問題的另一方面，主要是用這個程序很難進行測量。問題是這樣的，我們的測試程序修改了內存，所以本應看到RFO的影響，但在結果中，我們并沒有在L2階段看到更大的開銷。原因在于，要看到RFO的影響，程序必須使用大量內存，而且所有線程必須同時訪問同一塊內存。如果沒有大量的同步，這是很難實現的，而如果加入同步，則會占滿執行時間。

最后，在圖3.21中，我們展示了隨機訪問的Addnextlast測試的結果。這里主要是為了讓大家感受一下這些巨大到爆的數字。極端情況下，甚至用了1500個周期才處理完一個元素。如果加入更多線程，真是不可想象哪。我們把多線程的效能總結了一下:

這個表展示了圖3.21中多線程運行大工作集時的效能。表中的數字表示測試程序在使用多線程處理大工作集時可能達到的最大加速因子。雙線程和四線程的理論最大加速因子分別是2和4。從表中數據來看，雙線程的結果還能接受，但四線程的結果表明，擴展到雙線程以上是沒有什么意義的，帶來的收益可以忽略不計。只要我們把圖3.21換個方式呈現，就可以很容易看清這一點。

圖3.22中的曲線展示了加速因子，即多線程相對于單線程所能獲取的性能加成值。測量值的精確度有限，因此我們需要忽略比較小的那些數字。可以看到，在L2與L3范圍內，多線程基本可以做到線性加速，雙線程和四線程分別達到了2和4的加速因子。但是，一旦工作集的大小超出L3，曲線就崩塌了，雙線程和四線程降到了基本相同的數值(參見表3.3中第4列)。也是部分由于這個原因，我們很少看到4CPU以上的主板共享同一個內存控制器。如果需要配置更多處理器，我們只能選擇其它的實現方式(參見第5節)。

可惜，上圖中的數據并不是普遍情況。在某些情況下，即使工作集能夠放入末級緩存，也無法實現線性加速。實際上，這反而是正常的，因為普通的線程都有一定的耦合關系，不會像我們的測試程序這樣完全獨立。而反過來說，即使是很大的工作集，即使是兩個以上的線程，也是可以通過并行化受益的，但是需要程序員的聰明才智。我們會在第6節進行一些介紹。

特例: 超線程

由CPU實現的超線程(有時又叫對稱多線程，SMT)是一種比較特殊的情況，每個線程并不能真正并發地運行。它們共享著除寄存器外的絕大多數處理資源。每個核心和CPU仍然是并行工作的，但核心上的線程則受到這個限制。理論上，每個核心可以有大量線程，不過到目前為止，Intel的CPU最多只有兩個線程。CPU負責對各線程進行時分復用，但這種復用本身并沒有多少厲害。它真正的優勢在于，CPU可以在當前運行的超線程發生延遲時，調度另一個線程。這種延遲一般由內存訪問引起。

如果兩個線程運行在一個超線程核心上，那么只有當兩個線程合起來的運行時間少于單線程運行時間時，效率才會比較高。我們可以將通常先后發生的內存訪問疊合在一起，以實現這個目標。有一個簡單的計算公式，可以幫助我們計算如果需要某個加速因子，最少需要多少的緩存命中率。

程序的執行時間可以通過一個只有一級緩存的簡單模型來進行估算(參見[htimpact]):

各變量的含義如下:

為了讓任何判讀使用雙線程，兩個線程之中任一線程的執行時間最多為單線程指令的一半。兩者都有一個唯一的變量緩存命中數。 如果我們要解決最小緩存命中率相等的問題需要使我們獲得的線程的執行率不少于50%或更多，如圖 3.23.

X軸表示單線程指令的緩存命中率G_hit，Y軸表示多線程指令所需的緩存命中率。這個值永遠不能高于單線程命中率，否則，單線程指令也會使用改良的指令。為了使單線程的命中率在低于55%的所有情況下優于使用多線程，cup要或多或少的足夠空閑因為緩存丟失會運行另外一個超線程。

綠色區域是我們的目標。如果線程的速度沒有慢過50%，而每個線程的工作量只有原來的一半，那么它們合起來的耗時應該會少于單線程的耗時。對我們用的示例系統來說(使用超線程的P4機器)，如果單線程代碼的命中率為60%，那么多線程代碼至少要達到10%才能獲得收益。這個要求一般來說還是可以做到的。但是，如果單線程代碼的命中率達到了95%，那么多線程代碼要做到80%才行。這就很難了。而且，這里還涉及到超線程，在兩個超線程的情況下，每個超線程只能分到一半的有效緩存。因為所有超線程是使用同一個緩存來裝載數據的，如果兩個超線程的工作集沒有重疊，那么原始的95%也會被打對折——47%，遠低于80%。

因此，超線程只在某些情況下才比較有用。單線程代碼的緩存命中率必須低到一定程度，從而使緩存容量變小時新的命中率仍能滿足要求。只有在這種情況下，超線程才是有意義的。在實踐中，采用超線程能否獲得更快的結果，取決于處理器能否有效地將每個進程的等待時間與其它進程的執行時間重疊在一起。并行化也需要一定的開銷，需要加到總的運行時間里，這個開銷往往是不能忽略的。

在6.3.4節中，我們會介紹一種技術，它將多個線程通過公用緩存緊密地耦合起來。這種技術適用于許多場合，前提是程序員們樂意花費時間和精力擴展自己的代碼。

如果兩個超線程執行完全不同的代碼(兩個線程就像被當成兩個處理器，分別執行不同進程)，那么緩存容量就真的會降為一半，導致緩沖未命中率大為攀升，這一點應該是很清楚的。這樣的調度機制是很有問題的，除非你的緩存足夠大。所以，除非程序的工作集設計得比較合理，能夠確實從超線程獲益，否則還是建議在BIOS中把超線程功能關掉。{我們可能會因為另一個原因?開啟?超線程，那就是調試，因為SMT在查找并行代碼的問題方面真的非常好用。}

3.3.5 其它細節

我們已經介紹了地址的組成，即標簽、集合索引和偏移三個部分。那么，實際會用到什么樣的地址呢？目前，處理器一般都向進程提供虛擬地址空間，意味著我們有兩種不同的地址: 虛擬地址和物理地址。

虛擬地址有個問題——并不唯一。隨著時間的變化，虛擬地址可以變化，指向不同的物理地址。同一個地址在不同的進程里也可以表示不同的物理地址。那么，是不是用物理地址會比較好呢？

問題是，處理器指令用的虛擬地址，而且需要在內存管理單元(MMU)的協助下將它們翻譯成物理地址。這并不是一個很小的操作。在執行指令的管線(pipeline)中，物理地址只能在很后面的階段才能得到。這意味著，緩存邏輯需要在很短的時間里判斷地址是否已被緩存過。而如果可以使用虛擬地址，緩存查找操作就可以更早地發生，一旦命中，就可以馬上使用內存的內容。結果就是，使用虛擬內存后，可以讓管線把更多內存訪問的開銷隱藏起來。

處理器的設計人員們現在使用虛擬地址來標記第一級緩存。這些緩存很小，很容易被清空。在進程頁表樹發生變更的情況下，至少是需要清空部分緩存的。如果處理器擁有指定變更地址范圍的指令，那么可以避免緩存的完全刷新。由于一級緩存L1i及L1d的時延都很小(~3周期)，基本上必須使用虛擬地址。

對于更大的緩存，包括L2和L3等，則需要以物理地址作為標簽。因為這些緩存的時延比較大，虛擬到物理地址的映射可以在允許的時間里完成，而且由于主存時延的存在，重新填充這些緩存會消耗比較長的時間，刷新的代價比較昂貴。

一般來說，我們并不需要了解這些緩存處理地址的細節。我們不能更改它們，而那些可能影響性能的因素，要么是應該避免的，要么是有很高代價的。填滿緩存是不好的行為，緩存線都落入同一個集合，也會讓緩存早早地出問題。對于后一個問題，可以通過緩存虛擬地址來避免，但作為一個用戶級程序，是不可能避免緩存物理地址的。我們唯一可以做的，是盡最大努力不要在同一個進程里用多個虛擬地址映射同一個物理地址。

另一個細節對程序員們來說比較乏味，那就是緩存的替換策略。大多數緩存會優先逐出最近最少使用(Least Recently Used,LRU)的元素。這往往是一個效果比較好的策略。在關聯性很大的情況下(隨著以后核心數的增加，關聯性勢必會變得越來越大)，維護LRU列表變得越來越昂貴，于是我們開始看到其它的一些策略。

在緩存的替換策略方面，程序員可以做的事情不多。如果緩存使用物理地址作為標簽，我們是無法找出虛擬地址與緩存集之間關聯的。有可能會出現這樣的情形: 所有邏輯頁中的緩存線都映射到同一個緩存集，而其它大部分緩存卻空閑著。即使有這種情況，也只能依靠OS進行合理安排，避免頻繁出現。

虛擬化的出現使得這一切變得更加復雜。現在不僅操作系統可以控制物理內存的分配。虛擬機監視器（VMM，也稱為?hypervisor）也負責分配內存。

對程序員來說，最好 a) 完全使用邏輯內存頁面?b) 在有意義的情況下，使用盡可能大的頁面大小來分散物理地址。更大的頁面大小也有其他好處，不過這是另一個話題（見第4節）。

總結

以上是生活随笔為你收集整理的产生线程安全的原因（3）（操作系统）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。