[發明專利]事務存儲器中的并行嵌套事務

有效

• 申請號: 201210399252.7
• 申請日: 2008-09-16
• 公開（公告）號: CN102929702A
• 公開（公告）日: 2013-02-13
• 發明（設計）人: M·M·馬格魯德;D·德特勒夫;J·J·達菲;G·格雷費;V·K·格羅弗
• 申請（專利權）人: 微軟公司
• 主分類號: G06F9/46
• 分類號: G06F9/46;G06F17/30
• 代理公司: 上海專利商標事務所有限公司 31100
• 代理人: 顧嘉運

本申請是申請日：2008.09.16，申請號為200880107300.2（國際申請號為PCT//US2008/076563），名稱為“事務存儲器中的并行嵌套事務”的申請的分案申請。

背景

軟件事務存儲器（STM）是類似于數據庫事務的、用于在并發計算中控制對共享存儲器的訪問的并發控制機制。事務存儲器的上下文中的事務是對共享存儲器執行一系列讀取和寫入的一段代碼。換言之，事務訪問一個或多個對象中的數據。事務存儲器的上下文中的對象是作為一個實體來鎖定的一組連接的存儲單元。該上下文中的對象也可能是靜態變量，或一組這樣的變量，或者該對象可能是一組高速緩存線。

STM用作傳統鎖定機制的替換。STM允許更簡單地編寫并發程序。事務指定應當如同其隔離執行一樣地執行的代碼序列。這一隔離錯覺可以通過對象的細粒度鎖定，以及通過以在發現事務與某一其它事務相沖突的情況下允許回退該事務的副作用的模式執行來實現。如果對于數據訪問所生成的代碼被修改成包括對這些鎖定和回退機制的支持，則可以說該訪問被“事務化”。

事務可以進行嵌套，并且可被分類為開放或封閉嵌套。如果一線程當前正在執行一事務并且到達一新原子塊的開頭，則該原子塊作為當前執行的父事務的封閉嵌套子事務來執行。該嵌套事務與封閉事務在同一隔離邊界內執行，并且就像封閉事務中所訪問的其他存儲器那樣，嵌套事務的影響將只在該封閉事務提交時變得可見。換言之，有效地掛起父事務，并且允許封閉嵌套事務運行至在繼續父事務中的處理之前完成。在嵌套事務回退時，其臨時影響被撤消并且父事務的狀態恢復到該嵌套事務開始的點處。

給定線程正在執行的“最外面的”事務是不嵌套的；稱之為頂層事務。該頂層事務必須原子地執行，因此嵌套事務變成其一部分。如果某些抽象A和B各自具有即使在由并發線程使用時它們也想要維護的內部表示不變量，則可能引發嵌套，并且這些抽象由此在實現其方法時使用原子塊以確保并發訪問不違反這些不變量?，F在假設某一更高級的抽象C在其實現時使用A和B的實例，并且具有使這些A和B實例相關的某些不變量。C的方法可能使用事務來確保不違反該不變量。如果在C的事務內部使用A和B方法，則A和B方法中的事務將進行嵌套（在這種情況下）。

現有事務存儲器系統不允許將在一個事務的隔離邊界內執行的工作分布在多個并發執行線程之間。在現有系統中，事務只可具有一個嵌套子事務。這些系統的語義簡單地不允許事務內的這樣的并行性，并且一次執行不止一個嵌套事務的嘗試將導致嵌套事務日志條目在父事務的日志中無序混合和其他錯誤，以及用于提供隔離錯覺的基本的底層細粒度鎖定協議的崩潰。

概述

公開了用于支持事務存儲器系統中的并行嵌套事務的各種技術和方法。為單個父事務創建多個封閉嵌套事務，并且將這些封閉嵌套事務作為并行嵌套事務來并發執行。使用各種技術來確保對父事務之外的其他事務隱藏并行嵌套事務的影響直到該父事務提交。

在一個實現中，就并行嵌套事務使用版本化寫鎖。當事務存儲器字從寫鎖變為版本化寫鎖時，在全局版本化寫鎖映射中形成一條目以存儲指向該版本化寫鎖所替換的寫日志條目的指針。當在事務處理期間遇到該版本化寫鎖時，咨詢全局版本化寫鎖映射以便將該版本化寫鎖轉換成指向寫日志條目的指針。

在另一實現中，對于并行事務支持釋放重復寫鎖以便回退。在并行嵌套事務的回退處理期間，遇到表示寫鎖的第一寫日志條目。如果該寫鎖被確定為是重復的，則獲取全局鎖并使用該全局鎖來同步對全局版本化寫鎖映射的訪問。

在又一實現中，對并行嵌套事務支持樂觀讀取確認。在樂觀讀取確認期間，如果版本化寫鎖指示來自兄弟并行嵌套事務的沖突，則咨詢信息以確定是否應破壞并行嵌套事務。在一個實現中，該信息被包含在版本化寫鎖和全局版本化寫鎖映射中。

在又一其他實現中，對并行嵌套事務支持寫鎖獲取。在試圖獲取并行嵌套事務的寫鎖時，讀取并分析事務存儲器字以確定是否能夠獲取該寫鎖。如果事務存儲器字指示版本化寫鎖，則訪問全局版本化寫鎖映射以取回指向第一寫日志條目的寫日志條目指針。

在又一實現中，對并行嵌套事務支持悲觀讀取。為并行嵌套事務創建悲觀重復檢測數據結構。將對應于并行嵌套事務中的每一悲觀讀取的條目形成到該數據結構中。在提交并行嵌套事務時，將新的悲觀讀鎖傳遞給直接父事務，并且在兄弟事務之間同步的情況下將一條目形成到直接父事務的單獨的悲觀重復檢測數據結構中。該悲觀重復檢測數據結構還可用于從悲觀讀取到寫鎖的升級。