事務(wù)存儲結(jié)構(gòu)的實現(xiàn)

1  引言

隨著多核處理器技術(shù)的不斷更新和發(fā)展，傳統(tǒng)的串行程序不論在效率上還是性能上都已經(jīng)跟不上信息高速發(fā)展的腳步了，程序員不得不開發(fā)線程級并行以提高片上計算資源的使用效率，但也帶來了新的挑戰(zhàn)和問題。目前不同線程間的同步、對共享資源的訪問等都是通過鎖和信號量機制完成的。然而，這種傳統(tǒng)的基于鎖和信號量的并發(fā)系統(tǒng)存在明顯的局限性。粗粒度的鎖對大量的共享數(shù)據(jù)做了保護，但是可擴展性不好，因為即使在線程間不存在對共享數(shù)據(jù)的訪問的情況下也可能會出現(xiàn)沖突阻塞現(xiàn)象；細粒度的鎖雖然比粗粒度的鎖擴展性能好，但由于算法設(shè)計的復雜性，普通程序員很難借助細力度的鎖實現(xiàn)高效的應用。同時使用鎖機制還會帶來諸多問題，比如：死鎖、優(yōu)先級反轉(zhuǎn)等，極大地影響了并行應用的效率和性能。

事務(wù)存儲(Transactional Memory，TM)的使用是解決上述存在問題一個很好的辦法[1]。通過將不同并行執(zhí)行的線程事務(wù)化，用事務(wù)操作來代替鎖機制能降低編程的復雜性。事務(wù)是被單線程執(zhí)行的對內(nèi)存進行讀寫的有序操作序列，其特性包括：原子性、隔離性、一致性和持久性。通常事務(wù)的執(zhí)行過程為：調(diào)用事務(wù)入口函數(shù)(begin_transaction)開始執(zhí)行事務(wù)，當事務(wù)執(zhí)行完畢后調(diào)用提交函數(shù)(commit_transaction)開始提交工作，提交過程分為三個階段(請求提交、開始提交和完成提交)，執(zhí)行完提交后此事務(wù)也就執(zhí)行完畢，從而繼續(xù)執(zhí)行下面的事務(wù)。但如果事務(wù)在執(zhí)行或提交過程中發(fā)生沖突或者錯誤，則通過其特有的回滾機制 (rollback)返回到此事務(wù)入口繼續(xù)執(zhí)行。事務(wù)的執(zhí)行流程圖如圖 1所示。

圖 1  事務(wù)執(zhí)行流程

為了實現(xiàn)事務(wù)的這些特性，需有一個很好的TM系統(tǒng)來支持事務(wù)數(shù)據(jù)的版本管理(Version Management)和事務(wù)的沖突管理(Contention Management)。版本管理同時對新值(事務(wù)提交后可見)和原始的舊值(事務(wù)執(zhí)行過程中發(fā)生了回滾的恢復數(shù)據(jù))進行管理。根據(jù)數(shù)據(jù)存放方式的不同TM系統(tǒng)區(qū)分版本管理為：積極版本管理(Eager Version Management)和懶惰版本管理(Lazy Version Management)。積極版本管理是將新值置于目標存儲區(qū)中，這樣在提交時新值能夠很快的得到執(zhí)行，極大地降低了提交的時延；而懶惰版本管理是將原始的舊值置于目標存儲區(qū)，雖然會增加提交的延時但是降低了當事務(wù)發(fā)生回滾后執(zhí)行的延時。沖突管理是不同事務(wù)執(zhí)行過程中對共享資源訪問引發(fā)沖突而進行的沖突檢測以及管理的機制。沖突管理有積極的(Eager)和懶惰的(Lazy)兩種策略，如果沖突在讀數(shù)據(jù)或?qū)憯?shù)據(jù)時立刻被發(fā)現(xiàn)而進行仲裁，這種沖突檢測是積極的；如果沖突是在事務(wù)進行提交時才發(fā)現(xiàn)并仲裁的，這種沖突檢測則是懶惰的。

目前，基于TM的硬件結(jié)構(gòu)有很多種，圖2中列出了目前幾種流行的硬件結(jié)構(gòu)根據(jù)版本管理和沖突管理而進行的分類。本文將介紹其中的一種結(jié)構(gòu)——LogTM(日志事務(wù)存儲)，通過對其硬件結(jié)構(gòu)（參見圖3）、版本管理、沖突管理的實現(xiàn)，展現(xiàn)了此結(jié)構(gòu)的優(yōu)越性，并給后續(xù)研究提供參考和幫助。

圖2  TM系統(tǒng)分類

2  LogTM的結(jié)構(gòu)

LogTM是建立在多機系統(tǒng)中基于日志的TM實現(xiàn)，每個核都有獨自的私有cache，并通過目錄協(xié)議來維持數(shù)據(jù)的一致性。它采用的是積極的版本管理策略和積極的沖突管理策略。圖3給出了LogTM的硬件結(jié)構(gòu)，它通過增加一些寄存器和cache中的讀/寫位很好地完成了對事務(wù)的操作。

圖3  LogTM的硬件結(jié)構(gòu) (圖中黑框中為其特有結(jié)構(gòu))

2.1  版本管理(Version Management)

LogTM使用積極的版本管理，將新的執(zhí)行數(shù)據(jù)存儲在目標區(qū)域(目標地址)中，而將舊的數(shù)據(jù)存儲在其它緩沖區(qū)。它通過在內(nèi)存中開辟一塊事務(wù)日志區(qū)域存儲事務(wù)執(zhí)行過程中被修改的數(shù)據(jù)(上文中提到的原始數(shù)據(jù))和這些數(shù)據(jù)所對應的地址，新的執(zhí)行數(shù)據(jù)則被保存在目標存儲區(qū)(目標地址)，當執(zhí)行完成提交時，這些新數(shù)據(jù)將會立即生效；當事務(wù)執(zhí)行過程中或提交時發(fā)生沖突或錯誤需要回滾時，則通過事務(wù)日志中記錄的信息恢復出事務(wù)執(zhí)行前的初始狀態(tài)。

剛開始創(chuàng)建線程時，每一個線程對應著一個日志而且為日志分配一塊虛擬存儲區(qū)域，并將該日志基地址寫入Log Base寄存器，當舊數(shù)據(jù)需要存儲到日志時，LogTM通過Log Base寄存器中的值定位到日志的入口然后將舊數(shù)據(jù)的虛擬地址和值一同保存在日志中以便恢復時使用。為了減少冗余日志，LogTM為每一個cache塊添加了對應的寫(W)位，用此來標識該cache塊在日志中的記錄情況。當事務(wù)提交成功后，LogTM將對應cache塊的寫(W)標志位清0并將Log Pointer(日志指針)重新指向日志的入口處，以便處理后續(xù)事務(wù)。

LogTM也為每個cache塊設(shè)置了一個讀(R)標志位，就像上面我們討論的寫(W)標志位一樣。在每個事務(wù)操作過程中LogTM同樣將讀標志位設(shè)置用于表示讀操作的執(zhí)行(如圖4所示)，而且在事務(wù)結(jié)束后，讀標志位也清0。

這種積極的版本管理模式的缺點就是在事務(wù)發(fā)生沖突或錯誤需要回滾時執(zhí)行比較慢，在回滾時，LogTM為了完成恢復必須將原始數(shù)據(jù)從日志中讀到合適的目標地址中然后重置寫(W)位，同時因為有很多數(shù)據(jù)記錄在日志中，所以恢復過程必須按照由后向前(后進先出)的順序進行。但在事務(wù)沖突比較少的情況下，這種模式能夠帶來高效的執(zhí)行效率。

為了能更好的理解LogTM版本管理過程，圖4通過一個例子進行了很好的分析。

(1)事務(wù)執(zhí)行開始前的狀態(tài)——cache數(shù)據(jù)塊中存放著原始數(shù)據(jù)，每塊的讀(R)、寫(W)位置0，LogBase(日志基址寄存器)指向日志入口地址，LogPtr(日志偏移指針)指向日志入口地址同時TMcount(事務(wù)計數(shù)器)置1代表正準備執(zhí)行一個事務(wù)。

(2) 讀00地址(十六進制地址)中的數(shù)據(jù)到寄存器r1中，00地址對應數(shù)據(jù)塊的讀(R)標志位置1表示此數(shù)據(jù)被讀。

(3) 將寄存器r2中數(shù)據(jù)(這里假設(shè)為56)存入c0地址中，由于c0地址中存在原始數(shù)據(jù)34，將c0地址和該原始數(shù)據(jù)一起根據(jù)LogBase中的日志入口地址存入日志中，并將LogPtr指針后移，指向用于存放下個數(shù)據(jù)的地址位，同時將c0地址對應塊的寫(W)標志位置1，代表一次寫操作的完成，其他的狀態(tài)不變。

(4) 讀取40地址中數(shù)據(jù)到寄存器r3中，然后r3中數(shù)據(jù)加1，并將執(zhí)行后的r3數(shù)據(jù)存回40地址中，該操作對40地址對應塊執(zhí)行了一次讀操作和一次寫操作，將讀(R)和寫(W)標志位置1，然后將原始40地址對應塊中數(shù)據(jù)存入日志中，存入LogPtr指向的地址中，同時將LogPtr指針后移。

(5) 事務(wù)提交后狀態(tài)——將與本事務(wù)相關(guān)的各個數(shù)據(jù)塊對應讀寫標志位清0，將LogPtr置位到LogBase，TMcount置0。(本例僅針對單事務(wù)執(zhí)行，如果是嵌套事務(wù)的執(zhí)行，LogTM結(jié)構(gòu)會更加復雜，具體支持嵌套事務(wù)的LogTM實現(xiàn)，請參考[2])

(6) 事務(wù)回滾后狀態(tài)——事務(wù)在執(zhí)行或提交過程中如果出錯需要回滾，則將日志中記錄的原始數(shù)據(jù)按照地址映射關(guān)系重新加載到對應cache數(shù)據(jù)塊中，同時將各個塊對應讀寫標志位清0，LogPtr重置并且TMcount置0。

圖 4 事務(wù)版本管理過程——成功提交和回滾

2.2  沖突管理(Contention Management)

LogTM采用積極的沖突管理模式，而沖突管理中的一個重要概念目錄，就是在內(nèi)存中開辟的一片用來記錄共享數(shù)據(jù)索引和相關(guān)狀態(tài)信息的區(qū)域，也稱為目錄表。此沖突管理以目錄為橋梁，通過目錄的分析和消息轉(zhuǎn)發(fā)機制來完成多處理機間的沖突檢測。具體的實現(xiàn)步驟概括起來為：①請求操作的處理機發(fā)出一致性請求到目錄；②目錄響應請求并可能將請求轉(zhuǎn)發(fā)到其他一個或多個處理機上；③每個響應請求的處理機檢查自身狀態(tài)看是否發(fā)生沖突；④每個響應請求的處理機給出應答信號，包括沖突應答(nack)和非沖突應答(ack)；⑤發(fā)出請求的處理機解決沖突。

事務(wù)發(fā)生沖突后的替換行為須依據(jù)目錄中有效的MOESI狀態(tài)(MOESI 狀態(tài)：Modified(M)，Owned(O)， Exclusive(E)，Shared(S) or Invalidate(I))而定。

下面結(jié)合圖5中的沖突檢測實例對沖突管理的具體行為進行說明。

圖 5  LogTM沖突檢測實例

(1)事務(wù)開始——處理機P開始執(zhí)行事務(wù)，TMcount增1；此時僅目錄中存放的cache塊信息有效。

(2)處理機P向目錄請求數(shù)據(jù)信息——步驟①：P在自身的cache中找不到某數(shù)據(jù)，馬上發(fā)送獨占請求(GETX)到目錄。步驟②：目錄收到請求后根據(jù)相應數(shù)據(jù)的索引找到“老”版本數(shù)據(jù)傳給處理機P，當“老”版本數(shù)據(jù)達到P時，P將此數(shù)據(jù)更為“新”版本數(shù)據(jù)同時將本機此數(shù)據(jù)塊對應讀/寫標志位置1。步驟③：P接受數(shù)據(jù)完畢后，發(fā)送應答信號給目錄表示已經(jīng)成功接受數(shù)據(jù)。與此同時目錄中的狀態(tài)信息為M@P(Modified by P)，表示此數(shù)據(jù)正在被處理機P更改。

(3)檢測到事務(wù)沖突——步驟①：處理機Q發(fā)出請求某共享數(shù)據(jù)的信號(GETS)給目錄。步驟②：由于目錄中此數(shù)據(jù)的狀態(tài)為M@P，目錄則根據(jù)請求轉(zhuǎn)發(fā)給處理機P。步驟③：P接受到請求后檢查自己的狀態(tài)，由于P中相應數(shù)據(jù)塊的寫標志位已置，表明P正在修改此數(shù)據(jù)，不能滿足Q的請求，發(fā)生沖突。這時處理機P直接發(fā)送沖突信號給Q，當Q接受到?jīng)_突信號后進行沖突處理。步驟④：處理機Q同時將沖突信號發(fā)送給目錄，表明此次請求失敗。

(4)事務(wù)溢出的處理——處理機P通知目錄要將修改后的數(shù)據(jù)存到內(nèi)存中(目前，內(nèi)存中存在的是對應數(shù)據(jù)修改前的“臟”數(shù)據(jù))。步驟①：P發(fā)出PUTX請求給目錄。步驟②：目錄認可后發(fā)送應答信號給P，通知P可以發(fā)送。步驟③：P接收到此信號后將數(shù)據(jù)寫回內(nèi)存(WB_XACT)同時將溢出位置1(表明此數(shù)據(jù)已經(jīng)不在cache中)。這樣在寫回操作完成后，P中相關(guān)數(shù)據(jù)塊信息已置為無效，但是目錄中仍然保持著原先P持有數(shù)據(jù)時的狀態(tài)，內(nèi)存中對應區(qū)域已為修改后的“干凈”數(shù)據(jù)，目錄中該數(shù)據(jù)相應的狀態(tài)也由“老”變成了“新”，表明內(nèi)存中此數(shù)據(jù)已為更新后的數(shù)據(jù)。

(5)溢出數(shù)據(jù)的事務(wù)沖突檢測——步驟①：處理機Q重新發(fā)出請求數(shù)據(jù)信號給目錄，由于目錄中的狀態(tài)還沒有改變。步驟②：目錄根據(jù)當前狀態(tài)再次將請求轉(zhuǎn)發(fā)給處理機P，而此時Q請求的數(shù)據(jù)塊已經(jīng)寫回內(nèi)存中去了，并不在P的cache中，P收到請求信號后檢查到自身的溢出位已經(jīng)置位，它認為此數(shù)據(jù)可能由于某種原因不在cache中，但是仍然與它相關(guān)。比如：由于此數(shù)據(jù)塊大小大于cache規(guī)定塊大小而不能放下，但仍需操作。步驟③：P發(fā)出沖突信號(NACK)給Q，但是這個沖突并不是真正意義上的沖突，而是P假設(shè)的沖突。步驟④：Q收到?jīng)_突信號后處理沖突同時發(fā)送信號給目錄，表明此次請求再次失敗。

(6)目錄中數(shù)據(jù)狀態(tài)的懶惰(Lazy)更新——處理機P提交事務(wù)后將TMcount減1，將對應cache塊的讀/寫標志位和溢出標志位清零，但此時目錄中的狀態(tài)仍然為M@P。步驟①：此時一旦處理機Q重新發(fā)出請求此數(shù)據(jù)信號。步驟②：該信號會再一次通過目錄轉(zhuǎn)發(fā)給處理機P，但此時P的溢出位已經(jīng)被清空。步驟③：P通過發(fā)送清除信息(CLEAN)給目錄通知目錄不必再轉(zhuǎn)發(fā)請求信息，目錄中的數(shù)據(jù)信息有效可以直接發(fā)送給請求的處理機Q。步驟④：目錄根據(jù)索引關(guān)系找到相關(guān)數(shù)據(jù)發(fā)送給處理機Q。步驟⑤：Q收到數(shù)據(jù)后進行處理同時將應答信號發(fā)送給目錄，表明請求成功同時將目錄對應數(shù)據(jù)項狀態(tài)置E@Q，表示此時處理機Q獨占此數(shù)據(jù)資源。

但在執(zhí)行沖突檢測的過程中也會存在錯誤的沖突，比如：當處理機Q請求訪問一個數(shù)據(jù)塊，該數(shù)據(jù)塊在目錄中的狀態(tài)為M@P，而處理機P已經(jīng)執(zhí)行到后續(xù)事務(wù)，同時也置了溢出位。P發(fā)送沖突信號給Q，但這個沖突并不是因處理機Q請求的數(shù)據(jù)正被其他占有而產(chǎn)生的沖突，是一種無關(guān)的沖突。所以必須采取一種機制將目錄狀態(tài)及時更新。

2.3  操作系統(tǒng)對LogTM的支持

由于事務(wù)的引入，傳統(tǒng)操作系統(tǒng)已經(jīng)不能滿足要求，必須更改或擴展操作系統(tǒng)使事務(wù)能穩(wěn)定高效的執(zhí)行。

首先，基于LogTM系統(tǒng)，操作系統(tǒng)負責對日志進行創(chuàng)建和維護。它為每一個執(zhí)行線程開辟一片日志區(qū)域，并將該區(qū)域入口地址寫到Log Base寄存器中，同時當某數(shù)據(jù)存入日志后使Log Pointer指針后移，用來存放新數(shù)據(jù)。當發(fā)生回滾，操作系統(tǒng)根據(jù)目前Log Pointer指針從后向前恢復數(shù)據(jù)直到Log Pointer與Log Base指向相同為止。

其次，當執(zhí)行事務(wù)發(fā)生切換時，操作系統(tǒng)可以通過擴展目前的TCB(線程控制塊)來對事務(wù)相關(guān)寄存器內(nèi)容等信息進行保存。

再次，當發(fā)生事務(wù)級線程切換時，操作系統(tǒng)判斷切換原因(包括其他線程搶占、時間片到達、事務(wù)之間沖突等而執(zhí)行的切換)，通知調(diào)度器采取不同的切換策略或沖突策略來完成切換。

最后，由于中斷內(nèi)新創(chuàng)建的事務(wù)和被中斷事務(wù)沖突而導致活鎖(被中斷事務(wù)掛起得不到執(zhí)行，中斷內(nèi)新創(chuàng)建事務(wù)由于沖突策略一直回滾——重新執(zhí)行——回滾，也得不到執(zhí)行)，操作系統(tǒng)必須能夠記錄回滾次數(shù)并設(shè)定一個門限值，如果同一事務(wù)回滾數(shù)超過此門限，操作系統(tǒng)可以強行中止該事務(wù)而調(diào)度其他事務(wù)。

3  結(jié)論及展望

本文介紹TM的基本原理，并對當前主流TM系統(tǒng)LogTM進行分析實現(xiàn)，得出以下結(jié)論：

⑴要實現(xiàn)高效的事務(wù)處理必須要有一個很好的基于事務(wù)模型的硬件結(jié)構(gòu)。比如：LogTM，硬件專門為TM添加了LogBase、LogPointer等寄存器并改變了cache的結(jié)構(gòu)，在cache中加入了讀(R)和寫(W)標志位；這樣對事務(wù)版本管理以及沖突管理都帶來了前所未有的作用，這也是此TM結(jié)構(gòu)優(yōu)越性的體現(xiàn)。

⑵要高效的進行事務(wù)處理必須要有TM操作系統(tǒng)的支持，上文中提到了一些操作系統(tǒng)對LogTM的相關(guān)支持，但如果要完美的支持事務(wù)還需要不斷更改和優(yōu)化已有的操作系統(tǒng)，最終的目的是將操作系統(tǒng)事務(wù)化，并能很好的處理事務(wù)化的用戶級應用。

⑶目前TM系統(tǒng)(包括LogTM)雖然通過一些特有的結(jié)構(gòu)和機制解決了事務(wù)處理的一些問題，但是面對今后的發(fā)展，像多級嵌套事務(wù)的復雜應用、中斷事務(wù)化(特別是外部設(shè)備的中斷)、掛起事物與執(zhí)行事務(wù)沖突問題、被切換事務(wù)的執(zhí)行選擇(重新調(diào)度后，被切換事務(wù)可能回滾也可能繼續(xù)接著執(zhí)行)等問題都需要我們不斷的去研究，去尋找最優(yōu)的解決辦法一一攻克，所以對TM的研究任重而道遠。

參考文獻

[1]Yen， L. and J. Bobba， et al. LogTM-SE：Decoupling Hardware Transactional Memory from Caches. In Proc. of Thirteenth Annual International Symp. on High-Performance Computer Architecture.Feb.2007

[2]Moravan， M. J. and J. Bobba， et al. Supporting Nested Transactional Memory in LogTM. In Proc. of the Twelfth International Conference on Architectural Support for Programming Languages and Operating Systems， pages 359-370，Oct.2006

[3]Moore， K. E. and J. Bobba， et al. LogTM： Log_based Transactional Memory. In Proc. of the Twelfth IEEE Symp. on High-Performance Computer Architecture， pages 258–269， Feb. 2006

[4]Herlihy， M. and J. E. B. Moss . Transactional Memory：Architectural Support for Lock-Free Data Structures. In Proc. of the 20th Annual International Symp. on Computer Architecture， pages 289–300， May 1993

[5]Hammond， L. and V. Wong， et al. Transactional Memory Coherence and Consistency. In Proc. of the 31st Annual Intl. Symp. on Computer Architecture， June 2004

[6]Hammond， L. and B. D. Carlstrom， et al. Programming with Transactional Coherence and Consistency(TCC)， ASPLOS.04， October 7–13， 2004

更多計算機與外設(shè)信息請關(guān)注：21ic計算機與外設(shè)頻道