TW200907816A - Handling falsely doomed parents of nested transactions - Google Patents

Description

200907816 九、發明說明： 【發明所屬之技術領域】 本發明是有關於巢狀交易令錯誤判定親代 【先前技術】 軟體交易式記憶體（STM)是一種共時控制 類比於資料庫交易，而為以在共時計算處理中 記憶體的存取。在交易式記憶體的情境裡，交 一系列對共享記憶體進行讀寫作業的程式碼片 用來作為一種對於傳統鎖定機制的替代方式。 簡易地撰寫出共時程式。一交易標定一經設以 離之方式而執行的程式碼序列。該隔離的幻覺 件鎖定加以細緻化，並藉由按一可供以若發現 一其他交易相衝突則對該交易進行退返之副作 所執行而達成。若對於一資料存取所產生之程 改以納入對於該等鎖定及退返機制的支援，則 料存取係經「交易」。 許多STM系統都支援巢狀交易，以供有效 用多項交易所撰作出的不同元件。一巢狀交易 與其含入，或親代，交易相同之隔離邊界的一 視為封閉。當一封閉巢狀交易涉行時，其效力 的其餘部分並不會成為可見。相反地，其效力 易的一部份而仍進行中，並且僅在當該親代交 時方才對於該系統的其餘部份成為可見。當一 之處理。 機制，此者 控制對共享 易是指執行 段。STM是 STM可供更 按照宛若隔 是藉由將物 該交易與某 用的模式下 式碼既經修 我們稱此資 率地組成利 若其效力為 部份，則被 對於該系統 變成親代交 易最終涉行 巢狀交易退 5 200907816 返時，其臨時效力會被退解，並且將該親代交易的狀態復 原至該巢狀交易開始時的點處。

運用當場寫入及樂觀讀取的 STM系統是利用一與各 個可鎖定記憶體範圍相關聯之版本編號，藉以表述何時對 共享資料進行變更。一讀取交易將樂觀地記錄該記憶體（物 件、快取線等等）的版本編號，然並未另對該資料加以鎖 定。若該版本編號在該交易之壽命上並未改變，則該交易 可涉行。而寫入交易在當為涉行或退返之目的而釋放其寫 入卡鎖時，會將該版本編號遞增。由於寫入交易已當場臨 時地更新資料，因此在退返期間必須遞增該版本編號。該 讀取交易可觀見這些更新，並因可能讀取到不一致資料故 必須獲得通知而無法涉行（c 〇 m m i t)。 寫入尚未被親代寫入之資料的巢狀交易在退返時必須 將版本編號遞增，即如非巢狀交易者（頂層）。然而，考量 到其中一親代交易樂觀地讀取一變數X，並且一巢狀子代 交易首次寫入至變數X的情況。該親代將在其日誌裡記錄 X的版本編號，例如版本V 1。該巢狀交易將開始進行’並 且取得一對於X的寫入卡鎖。若該巢狀交易涉行，則並不 會發生問題：該寫入卡鎖不會被釋放並且會被傳送至該親 代，同時該親代保持為一致而能夠涉行。但是，若該巢狀 交易無論基於任何原因而退返，則必須釋放該寫入卡鎖並 且將對於X的版本編號遞增為V 2。該親代在涉行時間處 將顯似為不一致。X的版本為 V 2，然該親代是在早前於 VI處讀取之，且並無由何者將該版本編號改變成V2的記 6

200907816 錄。所顯似者係該親代與另一交易相衝突，然事實是 一造成該版本編號增加的巢狀交易，而實際上並非衝 該親代既已由其子代之退返操作所判定。此問題會 STM系統體驗到親代交易的虛假再執行。 【發明内容】 在此揭示為以於交易式記憶體系統中偵測出巢狀 之錯誤判定親代交易的各式技術及技巧。當進行巢狀 退返時，在每次對於一給定巢狀交易而釋放一寫入卡 即追蹤一釋放計數值。例如，可利用一寫入取消補償胡 藉以針對各個退返之巢狀交易而釋放的各個卡鎖來追 釋放計數值。該巢狀交易釋放一寫入卡鎖的次數會被 在其個別的寫入取消補償映圖之中。可在一親代交易 核期間，利用該等釋放計數值來決定一顯見無效的樂 取實際上是否為有效。 在一實作裡，當處理一親代交易日誌時，可在該 裡將任何巢狀子代交易所觀見的寫入取消補償映圖累 為一累集寫入取消補償映圖。若該樂觀讀取因版本編 符之故而無法驗核，則會諮詢該累集寫入取消補償映 藉以針對於該巢狀子代交易擷取出一特定變數的寫入 釋放計數值。若在版本編號上的差異精確地符合對於 狀子代交易的寫入卡鎖釋放計數值，則該樂觀讀取為巧 本「概述」係經提供以介紹一種按一較簡化形式 在後文「詳細說明」所進一步描述的選擇概念。本「ί 此係 突。 造成 子代 交易 鎖時 :圖， 蹤該 記錄 之驗 觀讀 親代 集成 號不 圖， 卡鎖 該巢 Γ效。 ，而 无述_ 7 200907816 並非為以識別所主張之標的各項關鍵特點或基本特性，亦 非為以用於決定所主張標的之範圍的輔助。 【實施方式】

本揭技術及技巧雖按如交易式記憶體系統之一般情境 所描述，然該系統亦可用於除此之外的其他目的。在一實 作裡，本揭所示之技術的一或更多者可為按如在一像是 MICROSOFT® .NET Framework之框架程式内的多項特 性，或者自任何提供平台以供開發者開發出軟體應用程式 之其他類型的程式或服務，所實作。在另一實作裡，本揭 所示技術之一或更多者則可為按如藉處理開發在一共時環 境中執行之應用程式的其他應用程式之特性所實作。 在一實作裡，一交易式記憶體系統係經供置而可供以 偵測並避免巢狀子代交易的親代交易錯誤判定。如本揭所 使用之詞彙「判定（doomed )」是指包含因該等既已對一 或更多由其他交易而經後續寫入之變數執行一或更多樂觀 讀取而稍後被退返的交易。當嘗試涉行此一交易時’失敗 的樂觀讀取將造成該交易被退返且重新執行。如本揭所使 用之詞彙「經錯誤判定（falsely doomed)」是指包含任何 因失敗樂觀讀取而顯似為判定然實際上並非判定的交易， 其原因在於該樂觀讀取係因巢狀交易操作之故而實際上確 為有效。如本揭所使用之詞彙「巢狀交易（nested transaction)」是指包含任何其效力被涵蓋在另一交易之隔 離邊界内的交易。包封該巢狀交易之交易稱為該巢狀交易 8 200907816 的「親代」，並且該巢狀交易通常是稱為「子代」。各 狀子代釋放一寫入卡鎖的次數會在一逐卡鎖釋放計數 被追蹤。在一實作裡，是於一寫入取消補償映圖裡追 些計數值。如本揭所使用之詞彙「寫入取消補償映圖 指包含一資料結構，此者儲存對於各巢狀子代所釋放 個卡鎖的逐卡鎖釋放計數值。多個寫入取消補償映圖 交易驗核或退返期間累集為一累集映圖。 當驗核一親代交易時，若一樂觀讀取無法通過驗 則會諮詢該目前累集寫入取消補償映圖，藉以瞭解一 式記憶體字組内之版本編號的差值是否精確地符合對 物件或記憶體範圍之巢狀子代交易的累集釋放計數值 是，則該樂觀讀取實際上為有效，並且不應錯誤地判 親代。如本揭所述之交易式記憶體字組在此是指包含 對各交易而供置的資料結構，此者追蹤有關於該給定 的各種資訊，像是卡鎖狀態（lock status)及版本編 例如，該TM W可含有一版本編號以及一讀取器之列. 數值及/或指示器。在一實作裡，該讀取器之列表/計 及/或指示器可含有一在一給定時間點處讀取器存取 定值之次數的計數值。在另一實作裡，該讀取器之； 計數值及/或指示器可含有一在一給定時間點處存取 定值之特定讀取器（即如悲觀者）的列表。又在另一 裡，該讀取器列表/計數值及/或指示器係僅一旗標或 指示器，藉以表述在一給定時間點處有一或更多的讀 存取該特定值。此等僅為範例，並且如本揭使用該 個巢 值中 蹤這 」是 之各 可在 核， 交易 於該 。若 定該 一針 交易 號。 良/計 數值 該特 W表/ 該特 實作 其他 取器 詞彙 9 200907816 TMW係為以涵蓋各種用於追蹤交易狀態的機制。 即如第1圖所示，一為以實作該系統之一或更多部份 的示範性電腦系統含一計算裝置，像是該計算裝置100。 在其最基本組態裡，該計算裝置1 〇〇通常包含至少一處理 單元1 02及系統記憶體1 04。根據計算裝置的精確組態及 型式而定，該系統記憶體1 04可為揮發性（像是RAM)、非 揮發性（像是R〇Μ、快閃記憶體等），或是一些該等二者之 组合。此最基本組態係在第1圖中由虛線1 0 6所示。 此外，該裝置1 0 0亦可具有額外特性/功能性。例如， 裝置100亦可含有額外的儲存裝置（可移除及/或非可移 除），這些包含磁性或光學碟片或條帶，然不限於此。此等 額外儲存裝置在第1圖中係按如可移除儲存裝置1 〇 8及非 可移除儲存裝置Π 0所述。電腦儲存媒體包含按任何用以 儲存即如電腦可讀取指令、資料結構、程式模組或其他資 料之資訊的方法或技術所實作之揮發性及非揮發性、可移 除及非可移除媒體。記憶體1 04、可移除儲存裝置1 0 8及 非可移除儲存裝置1〗〇皆為電腦儲存媒體的範例。電腦儲 存媒體包含’但不限於此，RAM、ROM、EEPROM、快閃 記憶體或其他記憶體技術、CD-ROM、數位光碟片（DVD) 或其他光學儲存、磁匣、磁帶、磁碟儲存或其他磁性儲存 裝置，或者是任何其他可用以儲存所欲資訊並且可由該裝 置1 0 0所存取的媒體。任何此等電腦儲存媒體皆可為該裝 置1 0 0的一部分。 計算裝置100含有一或更多的通訊連接114，此等可 10

200907816 讓該計算裝置1 00能夠與其他電腦/應戶 訊。裝置100亦可具有（多個）輸入裝置： 鼠、點筆、語音輸入裝置、觸控輸入裝置 個）輸出裝置Π 1，像是顯示器、喇叭、 裝置屬業界眾知者，且無需在此詳細敘 該計算裝置1 0 0包含交易式記憶體應用 圖中將對該交易式記憶體應用程式2 0 0 : 現續於第1圖而參照第2圖，其中 算裝置1 0 0之上的交易式記憶體應用程 記憶體應用程式2 0 0係常駐於該計算裝 用程式的其一者。然而，將能瞭解該交 式200可另替地或額外地在一或更多電 第1圖所示之不同變化項目中，按如電 體實作。此外，或另者，該交易式記憶 一或更多部份亦可位在其他電腦及/或應 如熟諳電腦軟體技藝之人士所能慮及的 上，而為系統記憶體1 〇 4的一部份。 該交易式記憶體應用程式2 0 0含有 者負責執行部份或所有的本揭所述技術 含有一邏輯 206，此者可用以在當一巢 釋放一寫入卡鎖時用於建立一寫入取消 (如後文中參照於第4圖所述）；一邏輯 在該 WACM裡各個項目之中記錄一巢 易式記憶體字組裡釋放該寫入卡鎖的4 弓程式 11 5進行通 I 1 2，像是鍵盤、滑 等等。亦可納入（多 印表機等等。這些 述。在一實作裡， 程式200。底下第2 道一步詳細說明。 說明一運作在該計 式200。該交易式 置1 0 0上之多個應 易式記憶體應用程 腦上，及/或在異於 腦可執行指令而具 體應用程式200之 :用程式1 1 5上，或 其他該等變化項目 程式邏輯2 0 4，此 。該程式邏輯204 狀交易首次退返及 補償映圖（WACM) 2 0 8，此者可用以 狀交易於一給定交 L數（如後文中參照 11 200907816 於第4圖所述）；一邏輯210，此者可用以在親代的交易日 誌裡握存該WACM (如後文中參照於第4圖所述）；一邏輯 2 1 2，此者可用於若一特定巢狀交易重新執行並再度退返則 利用並更新相同的WACM (如後文中參照於第4圖所述）； 一邏輯2 1 4，此者可用以視適當情況而累集WA C Μ (如後文 中參照於第5圖所述）；一邏輯2 1 6，此者可用以在交易驗 核期間利用該WACM，藉此決定失敗樂觀讀取實際上究係 為有效或無效（如後文中參照於第6圖所述）；以及其他用 於操作該應用程式的邏輯2 2 0。 現續於參照第1 - 2圖而前往第3 - 6圖，進一步詳細說 明用以實作該交易式記憶體應用程式2 0 0之一或更多實作 的多個階段。在一些實作裡，第3 - 6圖之程序係至少部分 地在該計算裝置1 0 0的操作邏輯中所實作。第3圖係一對 於該交易式記憶體應用程式2 0 0的高階處理流程圖。該處 理程序開始於起點 2 4 0。任何在巢狀交易退返期間所釋放 的寫入卡鎖都具有判定該親代轉導的潛在性（階段242)。 當一交易退返時，就會記憶每次的版本編號遞增（階段 244)。該系統會針對各個退返巢狀交易來追蹤此項資訊（ 段24 6)。在交易驗核期間，該系統可利用此項資訊以決定 一未通過驗核之特定樂觀讀取是否實際上由於差值係因重 新執行巢狀子代所造成而為有效（階段2 4 8)。這些階段將 於第4 - 6圖中進一步詳細說明。該程序結束於終點2 5 0。 第4圖說明一牵涉到建立及維護寫入取消補償映圖之 階段的實作。該程序開始於起點 2 7 0，即為建立一寫入取 12 200907816 消補償映圖（WACM)，而此者係在當一巢狀交易首次退 且釋放一寫入卡鎖時由一唯一卡鎖識別碼所鍵排（階 272)。該WACM内的各個項目記錄有該巢狀交易在一給 交易式記憶體字組上釋放一寫入卡鎖的次數（階段274)。 該WA C Μ係被握存於一親代交易的日誌中，並且在 巢狀交易之開始處於所有由該親代所執行的樂觀讀取之 而經排序（階段 2 7 6)。若一特定巢狀交易重新執行並再 退返，則該系統利用同一 WACM，並以任何新的寫入鎖 釋放將其更新（階段2 7 8 )。若該巢狀交易再度地取得一 先前執行作業中所取得的卡鎖，則在該WACM裡會將對 該交易式記憶體字組的計數值予以遞增（階段 2 8 0)。該 序結束於結束點2 8 2。 第5圖說明一牵涉到在交易退返期間累集WACM之 段的實作。該程序開始於起點 2 9 0，而一亦為許多巢狀 代之親代的巢狀交易可能會在時間上具有多個散佈於其 誌上 WACM (階段 292)。若在交易退返期間遭遇到多 WACM，則會因該巢狀子代之故而將所有的WACM累集 一單一 WACM並且放置在該親代的日誌裡（階段294)。 程序結束於結束點296。 第6圖說明一牽涉到在交易驗核期間利用WACM以 免巢狀交易錯誤判定親代之階段的實作。該程序開始於 點3 1 0而累集任何所見WACM，因為將樂觀讀取項目處 為一用於該驗核程序的臨時WACM，而同時逆反地處理 親代的日誌（階段 3 1 2)。若該樂觀讀取因版本編號不符 返 段 定 該 後 度 定 在 於 程 階 子 曰 個 成 該 避 起 理 該 之 13 200907816 故而無法被驗核（決策點3 1 4 )，則會利用該T M W 一排鍵以諮詢該臨時W A C Μ (階段3 1 6 )。若在該 址上有一相符項目（決策點 3 1 8 )，則該系統計算 相關聯之計數值是否精確地符合在版本編號上白 策點320)。若該計數值精確地符合在版本編號上€ 策點320)，則該樂觀讀取為有效，並且該差值全 重新執行該巢狀子代之故（階段 3 2 2)。若否，則 取為無效，並且係因其他交易的涉行/退返所S 3 24) °對於整個親代曰誌重複進行該等階段（決策 該程序結束於結束點328。 雖既已按照特定於結構特性及/或方法動作 描述主題事項，然應瞭解在後載申請專利範圍中 題事項並非必然地受限於前述各項特定特性或動 地，上述各項特定特性及動作係按如實作該申請 之範例形式所揭示。所有歸屬於本揭所述實作之 内，及/或藉由後載申請專利範圍，的等同、變化 為所欲予保護者。例如，熟諳電腦軟體技藝之人 知到可按不同方式以將本揭中所討論的範例組織 多電腦上，藉此納入異於該等範例中所繪述之較 的選項或特性。 【圖式簡單說明】 第1圖係一實作之電腦系統的概略視圖。 第2圖係一在該第1圖電腦系統上運作之實 位址作為 TMW位 與該項目 差值（決 I勺差值（決 係肇因於 該樂觀讀 L生（階段 點 326)。 之語言來 所定義主 作。相反 專利範圍 精神範圍 和修改皆 士將能認 於一或更 少或額外 作的交易 14 200907816 式記憶體應用程式概略視圖。 第3圖係一對於一第1圖系統之實作的高階處理流程 圖。 第4圖係一對於一第1圖系統之實作的處理流程圖， 其中說明牽涉到建立及維護寫入取消補償映圖的數個階 段。 第5圖係一對於一第1圖系統之實作的處理流程圖， 其中說明牽涉到在交易退返期間累集寫入取消補償映圖的 數個階段。 第6圖係一對於一第1圖系統之實作的處理流程圖， 其中說明牽涉到在交易驗核期間利用寫入取消補償映圖藉 此避免巢狀交易之親代錯誤判定的數個階段。 【主要元件符號說明】 1〇〇 計算裝置 102 處理單元 104 系統記憶體 106 基本組態 108 可移除儲存裝置 110 非可移除儲存裝置 111 (多個）輸出裝置 112 (多個）輸入裝置 114 (多個）其他通訊連接 115 其他電腦/應用程式 15 200907816 200 交易式記憶體應用程式

Claims (1)

1. 200907816 十、申請專利範圍： 1. 一種用以在一交易式記憶體系統中避免巢狀子代之錯 誤判定親代交易的方法，其中包含下列步驟： 當退返各巢狀交易時，每次釋放一寫入卡鎖即追蹤一 釋放計數值；以及 在驗核一親代交易之期間，利用該釋放計數值以決定 失敗驗核的一樂觀讀取實際上是否為有效。 2. 如申請專利範圍第1項所述之方法，其中若在版本編 號上的一差值精確地符合於該釋放計數值，則該失敗驗核 實際上為有效。 3. 如申請專利範圍第1項所述之方法，其中是在一寫入 取消補償映圖裡追蹤該釋放計數值。

   4. 如申請專利範圍第3項所述之方法，其中該寫入取消 補償映圖係針對於該等巢狀交易之各者而建立。 5. 如申請專利範圍第4項所述之方法，其中該寫入取消 補償映圖係針對該等巢狀交易之個別者在當該個別者首次 退返並釋放一寫入卡鎖時而建立。 6. 如申請專利範圍第4項所述之方法，其中是將對於該 17 200907816 等巢狀交易之各者的寫入取消補償映圖累集成一累集寫入 取消補償映圖。 7. 如申請專利範圍第6項所述之方法，其中在當處理該 親代交易之一交易日誌以決定該失敗的樂觀讀取是否實際 上為有效時即使用該累集寫入取消補償映圖。 8. 如申請專利範圍第7項所述之方法，其中該親代的交 易日誌係按一逆返次序所處理。 9. 一種電腦可讀取媒體，此者含有電腦可執行指令以令 一電腦執行如申請專利範圍第1項中所述之步驟。 10. 一種電腦可讀取媒體，此者含有電腦可執行指令以令 一電腦執行包含如下之步驟： 建立一對於一巢狀交易的寫入取消補償映圖； 在該寫入取消補償映圖之中記錄該巢狀交易釋放一寫 入卡鎖的次數；以及 在一親代交易的驗核期間利用該寫入取消補償映圖以 決定一失敗樂觀讀取是否實際上為有效。 11. 如申請專利範圍第1 0項所述之電腦可讀取媒體，其中 當該巢狀交易首次退返並釋放一寫入卡鎖時即建立該寫入 18 200907816 取消補償映圖。 12.如申請專利範圍第1 0項所述之電腦可讀取媒體，其中 若一在版本編號上的差值精確地符合該巢狀交易釋放該寫 入卡鎖的次數，則該失敗樂觀讀取實際上為有效。 1 3 .如申請專利範圍第1 0項所述之電腦可讀取媒體，其中 該寫入取消補償映圖係經握存於該親代交易的交易日誌 中 。 1 4 ·如申請專利範圍第1 3項所述之電腦可讀取媒體，其中 會在該巢狀交易開始處由該親代交易進行的所有樂觀讀取 之後對該寫入取消補償映圖加以排序。 1 5.如申請專利範圍第1 0項所述之電腦可讀取媒體，其中 該寫入取消補償映圖係經累集於對其他巢狀子代所遭遇到 的其他寫入取消補償映圖，藉以在親代交易之退返期間構 成一累集寫入取消補償映圖。 1 6.如申請專利範圍第1 5項所述之電腦可讀取媒體，其中 該累集寫入取消補償映圖係經放置於該親代交易的一交易 曰誌中。 19 200907816 1 7.如申請專利範圍第1 6項所述之電腦可讀取媒體，其中 該累集寫入取消補償映圖係在當按一逆反次序處理該親代 之交易日誌時放置在親代交易的交易日誌中。 18. —種為以在交易驗核期間利用寫入取消補償映圖以避 免巢狀交易之錯誤判定親代的方法，其中包含下列步驟： 當處理一親代日誌時，將在巢狀子代交易中所觀見之 /任何寫入取消補償映圖累集成一累集寫入取消補償映圖； c 若一樂觀讀取因版本編號不符之故而無法驗核，則會 諮詢該累集寫入取消補償映圖以擷取出對於該巢狀子代交 易的一寫入卡鎖釋放計數值；以及 若在版本編號上的差異精確地符合對於該巢狀子代交 易的寫入卡鎖釋放計數值，則該樂觀讀取為有效。 1 9.如申請專利範圍第1 8項所述之電腦可讀取媒體，其中 若在版本編號上之差值並不精確地相符於對於該巢狀子代 C_ j ' 交易的寫入釋放計數值，則該樂觀讀取為無效。 20. —種電腦可讀取媒體，此者含有電腦可執行指令以令一 電腦執行如申請專利範圍第1 8項中所述之步驟。 20