彭茜珍，胡 莉

(湖北科技學(xué)院 學(xué)報(bào)編輯部,湖北 咸寧 437100)

并發(fā)程序設(shè)計(jì)中經(jīng)常利用事務(wù)內(nèi)存(Transactional Memory，TM)技術(shù)簡化程序的編寫。TM技術(shù)源于數(shù)據(jù)庫社區(qū)最先提出和發(fā)展起來的概念[1]，其主要思想是把一段任務(wù)代碼定義為一個(gè)事務(wù)(Transaction )。借助事務(wù)的原子執(zhí)行提交任務(wù)的所有結(jié)果到內(nèi)存(當(dāng)這個(gè)事務(wù)成功)，或中止并取消任務(wù)所有的結(jié)果(當(dāng)這個(gè)事務(wù)失敗)。TM的關(guān)鍵是保證原子性(Atomicity)，一致性(Consistency )和隔離性(Isolation )這些要素，這樣利用事務(wù)內(nèi)存技術(shù)，多線程設(shè)計(jì)人員可以消除現(xiàn)有的開發(fā)難度和容易犯錯(cuò)誤的技術(shù)，使程序可以安全地并行執(zhí)行。本文給出了一種基于Intel TSX指令集的硬件監(jiān)控多個(gè)線程運(yùn)行中出現(xiàn)的沖突內(nèi)存訪問的功能，實(shí)現(xiàn)一種TM技術(shù)的模式。

一、引言

Intel TSX(Intel Transactional Synchronization Extensions)是X86指令集架構(gòu)(ISA)的擴(kuò)展，它提供了硬件事務(wù)內(nèi)存支持，對(duì)粗細(xì)粒度線程進(jìn)行鎖定。通常在多核多線程CPU中，當(dāng)多個(gè)線程對(duì)某一共享數(shù)據(jù)都需要訪問時(shí)，需要做出某種仲裁。當(dāng)一個(gè)線程訪問該共享數(shù)據(jù)時(shí)，另一線程就無法訪問，否則就會(huì)發(fā)生錯(cuò)誤。一般的程序設(shè)計(jì)者，為了預(yù)防線程間的競爭，阻止錯(cuò)誤發(fā)生，都使用粗粒度的鎖，這導(dǎo)致該線程占用很多的共享數(shù)據(jù)，使其他線程都不能爭搶。這樣也使一些本不需鎖定的共享數(shù)據(jù)也都被鎖定了，其他線程無法利用，從而降低了多核CPU的多線程性能，增加了開發(fā)難度。TSX指令就是要讓程序設(shè)計(jì)者能夠更方便、更精準(zhǔn)地做細(xì)粒度鎖定，讓這些共享數(shù)據(jù)更充分有效地運(yùn)用。

2013年6月，Intel TSX指令首次在基于Haswell微架構(gòu)的Intel微處理器中引入，隨后經(jīng)過Intel公司幾年的不斷的完善和更新，如今已成為Intel微處理器的標(biāo)配指令集擴(kuò)展[2]。

使用Intel TSX，程序設(shè)計(jì)者通過指定的代碼臨界區(qū)域(也稱為事務(wù)區(qū)域)使整個(gè)臨界區(qū)以事務(wù)方式執(zhí)行。如果事務(wù)的運(yùn)行成功地完成，這樣在從其他邏輯處理器查看時(shí)，這個(gè)事務(wù)臨界區(qū)內(nèi)執(zhí)行的所有內(nèi)存訪問都會(huì)立即發(fā)生。處理器僅在成功提交時(shí)才會(huì)對(duì)其他邏輯處理器可見的區(qū)域內(nèi)執(zhí)行架構(gòu)更新，這個(gè)過程即為原子提交。

成功的事務(wù)執(zhí)行確保了原子提交，因此CPU在沒有顯式同步的情況下就會(huì)樂觀地執(zhí)行臨界區(qū)代碼。如果這個(gè)特定的執(zhí)行無需同步，則該執(zhí)行就在沒有任何跨線程串行化的情況下提交。如果CPU無法進(jìn)行原子提交，則此次樂觀執(zhí)行失敗。當(dāng)發(fā)生這種情況時(shí)，CPU回滾該執(zhí)行，這個(gè)過程即為事務(wù)中止。進(jìn)行事務(wù)中止時(shí)，CPU放棄在該臨界區(qū)中執(zhí)行的所有更新，恢復(fù)CPU架構(gòu)狀態(tài)到未發(fā)生過樂觀執(zhí)行之前的情形，同時(shí)做非事務(wù)性地恢復(fù)執(zhí)行。

Intel TSX提供了兩個(gè)特殊軟件接口，用于指定事務(wù)運(yùn)行的代碼臨界區(qū)。硬件鎖定省略(Hardware Lock Elision，HLE)接口指定的事務(wù)代碼臨界區(qū)用于傳統(tǒng)的兼容指令集擴(kuò)展。受限事務(wù)存儲(chǔ)器(Restricted Transactional Memory，RTM)接口是一種新的指令集接口，它給程序員提供比HLE更有彈性的方式定義事務(wù)代碼臨界區(qū)。此外，Intel TSX還提供允許軟件查詢邏輯處理器是否處在由HLE或RTM標(biāo)識(shí)的事務(wù)代碼臨界區(qū)中做事務(wù)執(zhí)行。

二、 Intel TSX指令簡述

為了支持硬件事務(wù)內(nèi)存，并向程序設(shè)計(jì)者提供細(xì)粒度鎖，Intel TSX引入了兩類新的軟件接口，硬件鎖定省略和受限事務(wù)存儲(chǔ)器，以及和它們相關(guān)聯(lián)的指令[3，4]。

(一)硬件鎖定省略相關(guān)聯(lián)的指令

提供兩個(gè)新的指令前綴XACQUIRE和XRELEASE。這兩個(gè)前綴可以重用現(xiàn)有REPNE/REPE前綴(F2H/F3H)的操作碼。在不支持TSX的處理器上，在XACQUIRE/XRELEASE有效的指令中忽略REPNE/REPE前綴，從而實(shí)現(xiàn)向后兼容性。

(1)XACQUIRE前綴，格式：XACQUIRE，它向處理器提供一個(gè)帶有“XACQUIR開啟”的指令的提示，用于在指令存儲(chǔ)器操作數(shù)地址上啟動(dòng)鎖省略。

(2)XRELEASE前綴，格式：XRELEASE，它向處理器提供一個(gè)帶有“XRELEASE開啟”的指令的提示，用于在指令存儲(chǔ)器操作數(shù)地址上結(jié)束鎖省略。

HLE允許通過省略對(duì)鎖的寫入來樂觀地執(zhí)行代碼臨界區(qū)，從而使鎖看起來對(duì)其他線程是自由的。

(二)受限事務(wù)存儲(chǔ)器相關(guān)聯(lián)的指令

提供了三條新指令：XBEGIN，XEND和XABORT。 XBEGIN和XEND指令標(biāo)記事務(wù)臨界代碼區(qū)的開始和結(jié)束; XABORT指令顯式地中止一個(gè)事務(wù)。事務(wù)失敗會(huì)將處理器重定向到由XBEGIN指令指定的回退代碼路徑，并在EAX寄存器中返回中止?fàn)顟B(tài)。

(1)XBEGIN指令，格式：XBEGIN rel16/ rel32，它指定RTM區(qū)域的開始，指令操作數(shù)相對(duì)偏移量，以計(jì)算在RTM中止后執(zhí)行恢復(fù)的回退指令地址的地址。如果邏輯處理器尚未處于事務(wù)執(zhí)行中，則XBEGIN指令會(huì)使邏輯處理器轉(zhuǎn)換為事務(wù)執(zhí)行。這時(shí)將邏輯處理器轉(zhuǎn)換為事務(wù)執(zhí)行的XBEGIN指令稱為最外層的XBEGIN指令。在RTM中止時(shí)，邏輯處理器丟棄在RTM執(zhí)行期間執(zhí)行的所有架構(gòu)寄存器和更新的內(nèi)存，并將架構(gòu)狀態(tài)恢復(fù)為與最外層的XBEGIN指令相對(duì)應(yīng)的架構(gòu)狀態(tài)。中止后的回退地址是由最外層XBEGIN指令計(jì)算的。

(2)XEND指令，格式：XEND，它指定RTM區(qū)域的結(jié)尾。如果這對(duì)應(yīng)于最外層范圍(即，包括此XEND指令，XBEGIN指令的數(shù)量與XEND指令的數(shù)量相同)，則邏輯處理器將嘗試以原子方式提交邏輯處理器狀態(tài)。如果提交失敗，邏輯處理器將回滾在RTM執(zhí)行期間執(zhí)行的所有架構(gòu)寄存器和內(nèi)存更新。邏輯處理器將從最外面的XBEGIN指令計(jì)算的回退地址處恢復(fù)執(zhí)行。

(3)XABORT指令，格式：XABORT imm8，它強(qiáng)制RTM中止。在RTM中止之后，邏輯處理器通過最外面的XBEGIN指令計(jì)算的回退地址處恢復(fù)執(zhí)行，同時(shí)更新EAX寄存器以反映導(dǎo)致中止的XABORT指令，并且將在EAX的位31∶24中提供imm8參數(shù)。

RTM可以對(duì)HLE進(jìn)行替代實(shí)現(xiàn)，它使程序設(shè)計(jì)者可以靈活地指定在無法成功執(zhí)行事務(wù)時(shí)執(zhí)行的回退代碼路徑。

(三)事務(wù)代碼臨界區(qū)測試指令

提供一條新的XTEST指令，用于確定處理器是否正處在一個(gè)事務(wù)區(qū)域中。

XTEST指令，格式：XTEST，它查詢事務(wù)執(zhí)行狀態(tài)，并通過ZF標(biāo)志中反映查詢結(jié)果。如果指令在事務(wù)執(zhí)行的RTM區(qū)域或事務(wù)執(zhí)行的HLE區(qū)域內(nèi)執(zhí)行，則清除ZF標(biāo)志，否則設(shè)置。

借助于這套TSX指令的方案，在高度并發(fā)操作下，應(yīng)用性能提升明顯，能夠達(dá)到接近線性的擴(kuò)展；相對(duì)于其他細(xì)粒度鎖的方案，TSX在高度并發(fā)操作下的性能也很有優(yōu)勢(shì)(通常TSX的開銷比其他細(xì)粒度鎖的開銷小)。與無鎖編程相比，TSX也有很明顯的優(yōu)勢(shì)[4]。

三、Intel TSX事務(wù)內(nèi)存實(shí)現(xiàn)的關(guān)鍵原理探究[4，5]

支持Intel TSX擴(kuò)展的Intel CPU架構(gòu)提供了一個(gè)無序、單一版本、強(qiáng)隔離的可嵌套TM。這個(gè)TM以一個(gè)Cache行為粒度，跟蹤read-set和 write-set。

在Intel CPU架構(gòu)中，每個(gè)核都有L1和L2兩級(jí)Cache(由此核線程共享)，以及一個(gè)統(tǒng)一的L3(3級(jí)Cache)由CPU內(nèi)所有核共享的。TM的一致性的變化僅限制在L1D和L2中，并且嚴(yán)格限于核內(nèi)。同時(shí)擴(kuò)展了CPU架構(gòu)中已有的Cache行為和MESIF一致性協(xié)議 ，以其增加支持TM的語義。

基于上述結(jié)論，可以探究支持Intel TSX擴(kuò)展的Intel CPU架構(gòu)的事務(wù)內(nèi)存的關(guān)鍵原理，其中最重要的關(guān)鍵細(xì)節(jié)包括TM單一版本管理、沖突處理以及提交/中止操作三個(gè)方面。

(一)TM單一版本管理

這種架構(gòu)的TM最終采用是延遲更新系統(tǒng)，使用CPU中每個(gè)核的cache作為事務(wù)數(shù)據(jù)和寄存器檢查點(diǎn)。具體的做法是，L1D和L2的每個(gè)cache行中的標(biāo)記增加一些比特位，記載該行是否屬于可以在CPU核上執(zhí)行的線程的read-set(RS)或write-set(WS)。事務(wù)中的一個(gè)存儲(chǔ)操作只是寫cache行，而共享的L3保存原始數(shù)據(jù)(對(duì)于事務(wù)中的第一次存儲(chǔ)，還需要把L3更新為Modified )。這與Intel自從推出Nehalem以來一直沿用至今的共享和包容性的L3緩存是一致的。為了避免數(shù)據(jù)出錯(cuò)，任何事務(wù)性數(shù)據(jù)(即標(biāo)記有RS或WS的緩存行)必須保留在L1D或L2中，而不能被替換到L3或內(nèi)存。屬于體系結(jié)構(gòu)的寄存器應(yīng)被設(shè)置成檢查點(diǎn)，并存儲(chǔ)在CPU芯片中，并且事務(wù)可以隨機(jī)地讀取和寫入寄存器。

因此，這種架構(gòu)的事務(wù)內(nèi)存是將事務(wù)的write-set 和 read-set維護(hù)在L1D中的。L2是非事務(wù)性的，所以，當(dāng)一個(gè)write-set的cache行被替換出時(shí)，事務(wù)就會(huì)中止。在一些情形下， read-set的cache行可以被安全地替換出L1D，同時(shí)利用另一個(gè)硬件機(jī)制進(jìn)行跟蹤。在發(fā)生中止時(shí)，所有標(biāo)記為write-set的cache行都會(huì)從LD1中清除，而提交使得標(biāo)記為write-set的cache行原子可見。這樣，得益于TSX的吞吐量，可以使CPU的最小鎖延遲足夠小。

(二)沖突檢測

這種架構(gòu)的沖突檢測使用現(xiàn)有的MESIF一致性協(xié)議處理，它通過對(duì)內(nèi)存的排序緩沖、L1D和L2高速緩存做一些調(diào)整和增強(qiáng)來實(shí)現(xiàn)。發(fā)生沖突只能有三種方式，它們都能很輕易地被檢測到。

第一種情況是，一個(gè)標(biāo)記為RS的cache行被另一個(gè)核寫。借助于MESIF協(xié)議，寫一個(gè)共享cache行，就會(huì)無效任何其他私有cache的副本。另一個(gè)核會(huì)發(fā)出一個(gè)read-for-ownership請(qǐng)求給共享的L3，這導(dǎo)致檢查嗅探過濾器，同時(shí)發(fā)出一個(gè)無效命令給具有該cache行副本的任何cache。如果L1D和L2接收到對(duì)一個(gè)標(biāo)記為RS的cache行無效的命令，這表明有另一個(gè)線程試圖在寫，這時(shí)發(fā)生了沖突。

第二種情況是，另有一個(gè)核訪問標(biāo)記為WS的cache行。為使事務(wù)能在第一時(shí)間寫cache行，其他核不能夠緩存該副本，這是Modified狀態(tài)一致性的標(biāo)準(zhǔn)語義。然而，包容性的L3會(huì)保留事務(wù)之前的已過時(shí)原始版本。所以，當(dāng)有另一個(gè)核企圖訪問標(biāo)記為WS的cache行時(shí)，它就會(huì)在其本地的L1D和L2中產(chǎn)生缺失，進(jìn)而會(huì)探測L3。之后，L3將訪問嗅探過濾器，接著發(fā)出read(或read-for-ownership)請(qǐng)求給帶有標(biāo)記為WS的該cache行的核。因此，如果L1D和L2中標(biāo)記為WS的一個(gè)cache行收到了任何讀請(qǐng)求(或無效請(qǐng)求)，這時(shí)就發(fā)生了沖突。

第三種情況是，在同一個(gè)CPU內(nèi)核中，共享該內(nèi)核的L1D和L2的另一個(gè)線程會(huì)對(duì)事務(wù)進(jìn)行干擾。此時(shí)，另一個(gè)線程將命中共享的L1D和L2，但不對(duì)L3觸發(fā)任何一致性通信。因此，可通過檢查cache行是否被另一個(gè)線程做了WS標(biāo)記，放置在加載流水線中處理；還可檢查cache行是否在被另一個(gè)線程做了RS或WS標(biāo)記，使其在存儲(chǔ)流水線中處理。

最后的注意是，當(dāng)標(biāo)記為RS或WS的cache行被替換到L3或內(nèi)存中，應(yīng)立即中止事務(wù)。這樣做會(huì)使得有關(guān)問題容易處理。Intel修改了L2行的替換和驅(qū)逐策略，以防止替換出事務(wù)性數(shù)據(jù)。將L2用于事務(wù)還有一個(gè)優(yōu)點(diǎn)是，與L1D相比，L2替換策略能夠容忍更多延遲，這是出現(xiàn)在任何L1D缺失的關(guān)鍵路徑上。

(三)提交和中止

在支持的Intel TSX擴(kuò)展的CPU架構(gòu)中，提交事務(wù)是一個(gè)簡單的問題。L1D和L2的控制器，確保在WS中的任何Cache行處于Modified 狀態(tài)，并將WS位清0。并且任何帶有RS的Cache行必須是在Shared狀態(tài)，RS位同樣被清零。舊的寄存器文件檢查點(diǎn)應(yīng)刪除，把寄存器文件的現(xiàn)有內(nèi)容變?yōu)轶w系結(jié)構(gòu)狀態(tài)。

基于一致性的沖突檢測方案可以在沖突發(fā)生時(shí)盡早識(shí)別到，而不必等到提交時(shí)。沖突被發(fā)現(xiàn)的早，就會(huì)立即終止該事務(wù)。

中止事務(wù)，比提交事務(wù)更簡單。Cache控制器確定所有WS的緩存行為Invalid狀態(tài)，并將WS位清0?？刂破鬟€必須將RS位清0，但不需無效Cache行。最后，從先前的檢查點(diǎn)恢復(fù)體系結(jié)構(gòu)寄存器文件。

四、Intel TSX指令在并發(fā)程序設(shè)計(jì)中的應(yīng)用

Intel TSX指令基于處理器硬件設(shè)施，使用之前需要做3項(xiàng)檢測[2]：HLE 支持的檢測、RTM 支持的檢測、XTEST指令的檢測，檢測通過后方可使用，否則會(huì)產(chǎn)生#UD 異常。另外，還需要注意的是在某些CPU實(shí)現(xiàn)中，一些特別的指令可能總是導(dǎo)致事務(wù)中止，對(duì)于這些指令不要在代碼臨界事務(wù)區(qū)內(nèi)使用。下面給出Intel TSX指令應(yīng)用舉例及指導(dǎo)[6]。

(一)通常加鎖的代碼臨界區(qū)的流程是這樣的：

acq_lock(lock) ；請(qǐng)求鎖并且成功

; 臨界區(qū)代碼

re_lock(lock) ；釋放請(qǐng)求的鎖

(二)一般的匯編實(shí)現(xiàn)流程如下：

mov eax, 1

ReTry: lock xchg lock, eax

cmp eax, 0

jz Success ；成功獲取鎖轉(zhuǎn)到臨界區(qū)代碼

Spin: pause ；不成功鎖自旋

cmp lock, 1

jz Spin

jmp ReTry ；重新獲取鎖

Success：

… ；這里是臨界區(qū)代碼

mov lock, 0 ；釋放鎖

(三)使用Intel TSX指令HLE接口的匯編流程如下：

mov eax, 1

ReTry: xacquire xchg lock, eax

cmp eax, 0

jz Success

Spin: pause

cmp lock, 1

jz Spin

jmp ReTry

Success：

… ；這里是臨界區(qū)代碼

xrelease mov lock, 0 ；釋放鎖提交HLE執(zhí)行

(四)使用Intel TSX指令RTM接口的匯編流程如下：

ReTry: xbegin Abort ；開始一個(gè)RTM

cmp lock, 0 jz Success

xabort $0xff

Abort:

… ；檢測EAX

… ；根據(jù)檢測結(jié)果或回滾重新開始一個(gè)RTM；或重新請(qǐng)求lock

Success：

… ；這里是臨界區(qū)代碼

cmp lock, 0

jnz Release_lock

jmp Endd

Release_lock：

mov lock, 0 ；釋放鎖

Endd：xend ；提交RTM執(zhí)行

(五)很多C++編譯器軟件都對(duì)Intel TSX指令進(jìn)行包裝，方便設(shè)計(jì)者使用，下面是GCC編譯器對(duì)RTM的包裝及其用法[7]：

#include

if ((status = _xbegin ()) == _XBEGIN_STARTED) {

... transaction code...

_xend ();

} else {

... non transactional fallback path...

}

注意：對(duì)在事務(wù)代碼臨界區(qū)內(nèi)訪問的高速緩存行的沖突請(qǐng)求可能會(huì)阻止事務(wù)區(qū)成功執(zhí)行。此外，其他一致性流量有時(shí)可能會(huì)顯示為沖突請(qǐng)求并可能導(dǎo)致中止。雖然這些非真正沖突可能會(huì)發(fā)生，只是它們并不常見，設(shè)計(jì)者還需留意。

五、結(jié)語

多線程應(yīng)用程序設(shè)計(jì)越來越多地利用CPU多核來提高性能。但是，編寫多線程應(yīng)用程序會(huì)要求開發(fā)者實(shí)現(xiàn)多個(gè)線程之間的數(shù)據(jù)共享。訪問共享數(shù)據(jù)經(jīng)常使用同步機(jī)制—鎖。這些同步機(jī)制多半采用串行化進(jìn)行共享數(shù)據(jù)的操作，以確保多個(gè)線程安全地使用共享數(shù)據(jù)，一般使用鎖保護(hù)的臨界區(qū)實(shí)現(xiàn)更新共享數(shù)據(jù)操作。串行化的缺點(diǎn)是大量使用鎖機(jī)制保護(hù)不同的共享數(shù)據(jù)，限制了并發(fā)性，增加了開發(fā)難度并且容易出錯(cuò)。Intel TSX 指令的突出特點(diǎn)是很大程度降低這類開發(fā)的難度，為多核程序設(shè)計(jì)者帶來了一項(xiàng)新的多線程開發(fā)手段。