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

Description

Γ363299 九、發明說明： 【發明所屬之技術領域】 本發明是有關於巢狀交.易中錯誤判定親代之處 【先前技術】 軟體交易式記憶體（STM)是一種並行控制機制 類比於資料庫交易’而為以在並行計算處理中控制 記憶體的存取。在交易式記憶體的情境裡’交易疋 一系列對共享記憶體進行讀寫作業的程式瑀片段。 用來作為一種對於傳統鎖定機制的替代方式。STM 簡易地撰寫出並行程式。一交易標定一經設以按照 離之方式而執行的程式碼序列〇該隔離的錯覺是藉 的細敏性鎖定，並且執行於某一模式下而達成’其 式在發現該交易與某一其他交易相衝突時允許該交 退返之副作用。若對於一資料存取所產生之程式碼 改以納入對於該等鎖定及退返機制的支援，則我們 料存取係經「交易J。 許多STM系統都支援巢狀交易，以供有效率地 用多項交易所撰作出的不同元件》若一巢狀交易的 與該巢狀交易所包含（或是親代）之交易相同之隔離 一部份，則該巢狀交易被視為封閉。當—封閉巢狀 交（commit)時’其效力對於該系統的其餘部分並 為可見。相反地’其效力變成親代交易的_部份而 中，並且僅在當該親代交易最终提交時方才對於該 理。 ，此者 對共享 指執行 STM是 可供更 宛若隔 由物件 中該模 易進行 既經修 稱此資 組成利 效力為 邊界的 交易提 不會成 仍進行 系統的 5 Γ363299 其餘部份成為可見。當一巢狀交易退返時，其臨時效力會 被退解，並且將該親代交易的狀態復原至該巢狀交易開始 時的點處。 運用當場寫入及樂觀讀取的 STM系統是利用一與各 個可鎖定記憶體範圍相關聯之版本编號，藉以表述何時對 共享資料進行變更。一讀取交易將樂觀地記錄該記憶體（物 件、快取線等等）的版本編號，然並未另對該資料加以鎖 定。若該版本編號在該交易之壽命上並未改變，則該交易 可提交。而寫入交易在當為提交或退返之目的而釋放其寫 入卡鎖時，會將該版本編號遞增。由於寫入交易已當場臨 時地更新資料，因此在退返期間必須遞增該版本編號。該 讀取交易可觀見這些更新，並因可能讀取到不一致資料故 必須獲得通知而無法提交。 寫入尚未被親代寫入之資料的巢狀交易在退返時必須 將版本編號遞增，即如非巢狀交易者（頂層）。然而，考量 到其中一親代交易樂觀地讀取一變數X，並且一巢狀子代 交易首次寫入至變數X的情況。該親代將在其日誌裡記錄 X的版本編號，例如版本V 1。該巢狀交易將開始進行’並 且取得一對於X的寫入卡鎖。若該巢狀交易提交，則並不 會發生問題：該寫入卡鎖不會被釋放並且會被傳送至該親 代，同時該親代保持為一致而能夠提交。但是，若該巢狀 交易無論基於任何原因而退返，則必須釋放該寫入卡鎖並 且將對於X的版本編號遞增為V2。該親代在提交時間處 將顯似為不一致。X的版本為 V2，然該親代是在早前於 6 1363299 VI處讀取之’且並無由何者將該版本编號改變成V2的記 錄。所顯似者係該親代與另—交易相衝突，然事實是此係 一造成該版本編號增加的巢狀交易，而實際上並非衝突。 該親代既已由其子代之退返操作所判定。此問題會造成 STM系統體驗到親代交易的虛假再執行。 【發明内容】 在此揭示為以於交易式記憶體系統中偵測出巢狀子代 之錯誤判定親代交易的各式技術及技巧β當進行巢狀交易 退返時’在每次對於一給定巢狀交易而釋放一寫入卡鎖時 即追縱一釋放計數值。例如，可利用一寫入取消補償映圖， 藉以針對各個退返之巢狀交易而釋放的各個卡鎖來追蹤該 釋放計數值。該巢狀交易釋放一寫入卡鎖的次數會被記錄 甘- . ''個別的寫入取消補償映圖之中。可在一親代交易之驗 &期間’利用該等釋放計數值來決定一顯見無效的樂觀讀 取實際上是否為有效 在—實作裡，當處理一親代交易曰誌時，可在該親代

狀子代交易所觀見的寫入取消補償映圖累集成 集寫入取消補償映圖。若該樂觀讀取因版本編號不 而無法驗核，則會諮詢該累集寫入取消補償映圖， 辦於該巢狀子代交易擷取出一特定變數的寫入卡鎖 數值。若在版本編號上的差異精確地符合對於該巢 交易的寫入卡鎖釋放計數值，則該樂觀讀取為有效。 「概述」係經提供以介紹一種按一較簡化形式，而 7 1363299 在後文「詳細說明」所進一步描述的選擇概念。本 並非為以識別所主張之標的各項關鍵特點或基本特 非為以用於決定所主張標的之範圍的辅助。 【實施方式】 本揭技術及技巧雖按如交易式記憶體系統之一 所描述，然該系統亦可用於除此之外的其他目的。 作裡，本揭所示之技術的一或更多者可為按如在 MICROSOFT® .NET Framework 之框架程式内的 性’或者自任何提供平台以供開發者開發出軟體應 之其他類型的程式或服務，所實作。在另_實作裡 所示技術之一或更多者則可為按如藉處理開發在— 境中執行之應用程式的其他應用程式之特性所實作 在一實作裡，一交易式記憶體系統係經供置而 偵測並避免巢狀子代交易的親代交易錯誤判定。如 使用之詞彙Γ判定（doomed)」是指包含因該等既 或更多由其他交易而經後續寫入之變數執行―或t 讀取而稍後被退返的交易。當嘗試提交此一交 的樂觀讀取將造成該交易被退返且重新執行。如I 用之詞彙「經錯誤判定（falsely doomed)」是指包 因失敗樂觀讀取而顯似為判定然實際上並非判定的 其原因在於該樂觀讀取係因巢狀交易操作之故 為有效。如本揭所使用之詞彙「巢狀交易 ( transaction)」是指包含任何其效力被涵蓋在另―交 「概述」 性’亦 般情境 在一實 一像是 多項特 用程式 ’本揭 並行環 〇 可供以 本揭所 已對一 多樂觀 ’失敗 揭所使 含任何 交易， 際上確 nested 易之隔 8 Γ363299 離邊界内 的「親代 交易。包封該巢妝夺 乂易之交易稱為該巢狀交易 ,益且該巢狀交易通常 *疋稱為「子代」。各個巢 狀十μ ^寫人卡鎖的次數會在—逐卡㈣放計數值+ 被追蹤。在/實作裡疋於一寫入取消補償映園裡追蹤這 些計數值。如本揭所使用之詞彙「寫入取消補償映圖」是 指包含一資枓結構，此者儲存對於各巢狀子代所釋放之各 個卡鎖的逐卡鎖釋放什數值。多個寫入取消補償映圖可在 交易驗核或退返期間累集為一累集映圖。 當驗核一親代交易時，若一樂觀讀取無法通過驗核， 則會諮詢該目前累集寫入取消補償映圖，藉以瞭解一交易 式記憶體字组内之版本編號的差值是否精確地符合對於該 物件或記憶體範圍之巢狀子代交易的累集釋放計數值。若 是，則該樂觀讀取實際上為有效，並且不應錯誤地利定該 親代。如本揭所述之交易式記憶體字組在此是指包含一針 對各交易而供置的資料結構，此者追蹤有關於該給定交易 的各種資訊’像是卡鎖狀態（丨oclc status )及版本編號 例如，該TMW可含有一版本編號以及一讀取器之列表/計 數值及/或指示器。在一實作裡’該讀取器之列表/計數值 及/或指示器可含有一在一給定時間點處讀取器存取該特 定值之次數的計數值。在另一實作裡，該讀取器之列表/ 計數值及/或指示器可含有—在一給定時間點處存取該特 定值之特定讀取器（即如悲觀者）的列表。又在另一貫作 裡，該讀取器列表/計數值及/或指示器係僅一旗標或其他 指示器，藉以表述在一給定時間點處有—或更多的讀取器 9 ^06299 存取該特定值。此等僅為範例，並且如本揭使用該詞彙 Tlvi你係為以涵蓋各種用於追蹤交易狀態的機制。 即如第1圖所示為以貫作該系統之一或更多部份 的不範性電腦系統含一計算裝置，像是該計算裝置1 00。 在其最基本組態裡，該計算裝置100通常包含至少一處理 να 早元1 02及系統記憶體1 04。根據計算裝置的精確組態及 型式而定，該系統記憶體104可為揮發性（像是RAM)、非 揮發性（像是r〇M、快閃記憶體等），或是一些該等二者之 、· & °此最基本組態係在第1圖中由虚線1 〇6所示。 此外’該裝置1 00亦可具有額外特性/功能性。例如， UJu 置100亦可含有額外的儲存裝置（可移除及/或非可移 除），這些包含磁性或光學碟片或磁帶，然不限於此。此等 額外储存裝置在第1圖中係按如可移除儲存裝置1〇8及非 可移除儲存裝置丨1 〇所述。電腦儲存媒體包含按任何用以 健存即如電腦可讀取指♦、資料結構、程式模組或其他資 钭之資訊的方法或技術所實作之揮發性及非揮發性可移 除及非可移除媒體。記憶體104、可移除儲存裝置108及 非可移除儲存裝置1 1 0皆為電腦儲存媒體的範例。電腦儲 存媒體包含，但不限於此 RAM、ROM、EEPROM、快閃 記憶體或其他記憶體技術、CD_R〇M、數位光碟月（dvd) 或其他光學赌存m、磁帶、磁碟储存或其他磁性健存 裝置，或者是任何其他可用以儲存所欲資訊並且可由該裝 置100所存取的媒體。任何此等電腦儲存媒體皆可為該裝 置100的一部分。 、 10 1363299 計算裝置100含有一或更多的通訊 讓該計算裝置100能夠與其他電腦/應； 訊。裝置100亦可具有（多個）輸入裝置 鼠、點筆'語音輸入裝置、觸控輸入裝置 個）輸出裝置1 1 1，像是顯示器、喇叭、 裝置屬業界眾知者，且無需在此詳細敘 該計算裝置100包含交易式記憶體應用 圖中將對該交易式記憶體應用程式200 : 現續於第1圖而參照第2圖，其中 算裝置1 0 0之上的交易式記憶體應用程 記憶體應用程式200係常駐於該計算裝 用程式的其一者。然而，將能瞭解該交 式2 00可另替地或額外地在一或更多電 第1圖所示之不同變化項目中，按如電 體實作。此外，或另者，該交易式記憶 一或更多部份亦可位在其他電腦及/或應 如熟諳電腦軟體技藝之人士所能慮及的 上，而為系統記憶體1 04的一部份。 該交易式記憶體應用程式2 00含有 者負責執行部份或所有的本揭所述技術 含有一邏輯206，此者可用以在當一巢 釋放一寫入卡鎖時用於建立一寫入取消 (如後文中參照於第4圖所述）；一邏輯 在該 WACM裡各個項目之中記錄一巢； 連接1 14，此等可 3程式1 1 5進行通 1 1 2，像是鍵盤、滑 等等。亦可納入（多 印表機等等。這些 述。在一實作裡， 程式200。底下第2 進一步詳細說明。 說明一運作在該計 式200。該交易式 置100上之多個應 易式記憶體應用程 腦上，及/或在異於 腦可執行指令而具 體應用程式200之 用程式1 1 5上，或 其他該等變化項目 程式邏輯204，此 。該程式邏輯 204 狀交易首次退返及 補償映圖（WACM) 208，此者可用以 狀交易於一給定交 11 Γ363299 易式記憶體字组裡釋放該寫入卡鎖的次數（如後文中參照 於第4圖所述）；一邏輯210，此者可用以在親代的交易曰 誌裡握存該WACM (如後文中參照於第4圖所述）；一邏輯 212,此者可用於若一特定巢狀交易重新執行並再度退返則 利用並更新相同的WA C Μ (如後文中參照於第4圖所述）； 一邏輯214,此者可用以視適當情況而累集WACM(如後文 中參照於第5圖所述）；一邏輯216，此者可用以在交易驗 核期間利用該WACM，藉此決定失敗樂觀讀取實際上究係 為有效或無效（如後文中參照於第6圖所述）；以及其他用 於操作該應用程式的邏輯220。 現續於參照第卜2圖而前往第3 -6圖，進一步詳細說 明用以實作該交易式記憶體應用程式2 0 0之一或更多實作 的多個階段》在一些實作裡，第3-6圖之程序係至少部分 地在該計算裝置1 00的操作邏輯中所實作。第3圖係一對 於該交易式記憶體應用程式2 0 0的高階處理流程圖。該處 理程序開始於起點240。任何在巢狀交易退返期間所釋放 的寫入卡鎖都具有判定該親代轉導的潛在性（階段242)。 當一交易退返時，就會記憶每次的版本編號遞增（階段 2 4 4)。該系統會針對各個退返巢狀交易來追蹤此項資訊（P皆 段2 4 6)。在交易驗核期間，該系統可利用此項資訊以決定 一未通過驗核之特定樂觀讀取是否實際上由於差值係因重 新執行巢狀手代所造成而為有效（階段248)。這些階段將 於第4 - 6圖中進一步詳細說明。該程序結束於终點2 5 0。 第4圖說明一牽涉到建立及維護寫入取消補償映圖之 12 Γ363299 階段的實作。該程序開始於起點270 ’即為建立一寫入 消補償映圖（WACM)，而此者係在當一巢狀交易首次退 且釋放一寫入卡鎖時由一唯--^鎖識別碼所鍵排（階 272)。該WACM内的各個項目記錄有該巢狀交易在一給 交易式記憶體字组上釋放一寫入卡鎖的次數（階段274)。 該WA CM係被握存於一親代交易的日达中，並且在 巢狀交易之開始處於所有由該親代所執行的樂觀讀取之 而經排序（階段276)。若一特定巢狀交易重新執行並再 退返，則該系統利用同一 WACM ’並以任何新的寫入鎖 釋放將其更新（階段278)。若該巢狀交易再度地取得一 先則執行作業中所取得的卡鎖，則在該WACM裡會將對 該父易式s己憶餿字組的計數值予以遞增（階段280)。該 序結束於結東點2 8 2。 第5圖說明一牽涉到在交易退返期間累集waCM之 段的實作。該程序開始於起點29〇，而一亦為許多巢狀 代之親代的巢狀交易可能會在時間上具有多個散佈於其 誌上WACM (階段292)。若在交易退返期間遭遇到多 WACM ’則會因該巢狀子代之故而將所有的wacm累集 一單一 WACM並且放置在該親代的日誌裡（階段294)。 程序結束於结束點2 9 6。 第6圖說明—牽涉到在交易驗核期間利用WACM以 免巢狀交易錯誤判定親代之階段的實作。該程序開始於 點3〗0而累集任何所見WACM，因為將樂觀讀取項目處 為一用於該驗核程序的臨時WACM，而同時逆反地處理 取 返 段 定 該 後 度 定 在 於 程 階 子 曰 個 成 該 避 起 理 該 13 Γ363299 親代的日誌（階段 312)。若該樂觀讀取因版本編號不符之 故而無法被驗核（決策點3 M)，則會利用該TMW位址作為 一排鍵以諮詢該臨時WACM (階段316)。若在該TMW位 址上有一相符項目（決策點 3 1 8 )，則該系統計算與該項目 相關聯之計數值是否精確地符合在版本编號上的差值（決 策點32 0)。若該計數值精確地符合在版本編號上的差值（決 策點320)，則該樂觀讀取為有效，並且該差值全係肇因於 重新執行該巢狀子代之故（階段3 2 2)。若否，則該樂觀讀 取為無效，並且係因其他交易的提交/退返所致生（階段 3 24)。對於整個親代日誌重複進行該等階段（決策點326)。 該程序結束於結束點3 2 8。 雖既已按照特定於結構特性及/或方法動作之語言來 描述主題事項，然應瞭解在後載申請專利範圍中所定義主 題事項並非必然地受限於前述各項特定特性或動作。相反 地，上述各項特定特性及動作係按如實作該申請專利範圍 之範例形式所揭示。所有歸屬於本揭所述實作之精神範圍 内，及/或藉由後載申請專利範圍，的等同、變化和修改皆 為所欲予保護者。例如，熟諳電腦軟體技藝之人士將能認 知到可按不同方式以將本揭中所討論的範例組織於一或更 多電腦上，藉此納入異於該等範例令所繪述之較少或額外 的選項或特性。 【圖式簡單說明】 第1圖係一實作之電腦系統的概略視圖。 14 Γ363299 第2圖係一在該第1圖電腦系統上運作之實作的交易 式記憶體應用程式概略視圖。 第3圖係一對於一第1圖系统之實作的高階處理流程 圖。 第4圖係一對於一第1圖系統之實作的處理流程圖， 其中說明牵涉到建立及維護寫入取消補償映圖的數個階 段。 第5圖係一對於一第1圖系統之實作的處理流程圖， 其中說明牽涉到在交易退返期間累集寫入取消補償映圖的 數個階段。 第6圖係一對於一第1圖系統之實作的處理流程圖， 其中說明牽涉到在交易驗核期間利用寫入取消補償映圖藉 此避免巢狀交易之親代錯誤判定的數個階段。 【主要元件符號說明】 100 計算裝置 1 02 處理單元 1 04 系統記憶體 1 06 基本組態 108 可移除儲存裝置 110 非可移除儲存裝置 111 (多個）輸出裝置 112 (多個）輸入裝置 1 14 (多個）其他通訊連接 15 115Γ363299 200 其他電腦 交易式記 /應用程式 憶體應用程式 16

Claims (1)

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

   Γ363299 第％ μ叫叫號專利寒昨年(咕修正 七、指定代表圖： (一） 、本案指定代表圖為.第（4)圖。 (二） 、本代表圖之元件代表符號簡單說明 八、本案若有化學式時，請揭示最能顯示 發明特徵的化學式： 無 4