關 閉

        新聞中心

        EEPW首頁 > 工控自動化 > 設計應用 > 事務存儲結構的實現

        事務存儲結構的實現

        作者: 時間:2012-06-04 來源:網絡 收藏

        1 引言

        本文引用地址:http://www.104case.com/article/202295.htm

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

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

        圖 1 事務執行流程

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

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

        圖2 TM系統分類

        2 LogTM的結構

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

        1.jpg

        圖3 LogTM的硬件結構 (圖中黑框中為其特有結構)

        2.1 版本管理(Version Management)

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

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

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

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

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

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


        上一頁 1 2 3 下一頁

        關鍵詞: 存儲結構

        評論


        技術專區

        關閉
        主站蜘蛛池模板: 宁阳县| 民和| 理塘县| 徐州市| 霍林郭勒市| 东山县| 六安市| 剑阁县| 象山县| 梓潼县| 稷山县| 滨州市| 五华县| 宾川县| 申扎县| 台湾省| 浮山县| 阜平县| 志丹县| 泸西县| 南召县| 灵璧县| 镇赉县| 津南区| 沐川县| 昌乐县| 女性| 宣汉县| 开平市| 焉耆| 黎平县| 富阳市| 安宁市| 安丘市| 万山特区| 桐城市| 南充市| 镇安县| 斗六市| 铁岭市| 上饶县|