[發(fā)明專利]使用事務(wù)來并行化順序框架

有效

• 申請?zhí)枺?/td>: 200880018922.8
• 申請日: 2008-05-30
• 公開（公告）號: CN101681272A
• 公開（公告）日: 2010-03-24
• 發(fā)明（設(shè)計）人: J·J·達菲;J·格雷;Y·萊瓦諾尼
• 申請（專利權(quán)）人: 微軟公司
• 主分類號: G06F9/46
• 分類號: G06F9/46
• 代理公司: 上海專利商標事務(wù)所有限公司
• 代理人: 張政權(quán);錢靜芳

背景

軟件事務(wù)存儲器(STM)是類似于數(shù)據(jù)庫事務(wù)的、用于在并發(fā)計算中 控制對共享存儲器的訪問的并發(fā)控制機制。事務(wù)存儲器的上下文中的事務(wù) 是執(zhí)行對共享存儲器的一系列讀取和寫入的一段代碼。STM用作傳統(tǒng)鎖定 機制的替換。程序員在代碼塊周圍放置聲明性注釋(例如，原子的)以指 示這些代碼塊所需要的安全特性，并且系統(tǒng)自動保證該塊相對于其它受保 護的代碼區(qū)域原子地執(zhí)行。軟件事務(wù)存儲器編程模型防止了基于鎖的優(yōu)先 級倒置和死鎖問題。

雖然典型的STM系統(tǒng)具有許多優(yōu)點，但它們?nèi)匀恍枰绦騿T仔細地避 免非預(yù)期的存儲器訪問排序。例如，在典型的STM環(huán)境中提交事務(wù)(即， 提交處理)的次序是不受約束的。各事務(wù)彼此競爭提交，這意味著事務(wù)1 是在事務(wù)2之前還是之后提交通常是程序的動態(tài)調(diào)度的產(chǎn)物(并且通常也 由程序?qū)Ｓ眠壿媮碚{(diào)度)。此外，如果兩個事務(wù)沖突，諸如通過試圖向同 一段存儲器寫入等，則它們的提交次序可基于多個可能的爭用管理策略中 的一個來任意決定。在這兩種情況下，不保證任何特定提交次序；因此確 保程序員的程序按任一次序都正確地運作的負擔(dān)就落在程序員身上。這使 得并行編程非常困難。

其中執(zhí)行次序可能很重要并且其中并行性很有吸引力的一個場景是在 并行地執(zhí)行一循環(huán)的多次迭代時。以典型的“for...each”循環(huán)為例，如下 所示：

ForEach(string?s?in?List<string>)

{

????S；

}

在該循環(huán)的每一迭代期間，都將執(zhí)行該循環(huán)主體中的語句S。這一循 環(huán)被編寫來順序地執(zhí)行，其中該循環(huán)的第一次迭代在第二次迭代開始之前 結(jié)束，以此類推。如果在沒有處理可能的副作用或次序依賴性的額外預(yù)防 措施的情況下并行地執(zhí)行這一順序循環(huán)，則可能發(fā)生意外結(jié)果。

概述

公開了用于對事務(wù)存儲器系統(tǒng)中的事務(wù)應(yīng)用排序的各種技術(shù)和方法。 事務(wù)存儲器系統(tǒng)具備允許為多個事務(wù)指定預(yù)定提交次序的特征。在運行時 使用該預(yù)定提交次序來幫助確定提交事務(wù)存儲器系統(tǒng)中的事務(wù)的次序。在 一個實現(xiàn)中，預(yù)定提交次序可以或者是總體排序或者是部分排序。在總體 排序的情況下，迫使事務(wù)以線性次序來提交。在部分排序的情況下，允許 在多個可接受場景中的一個中提交事務(wù)。在一個實現(xiàn)中，提交仲裁器跟蹤 表示應(yīng)被允許接下來提交的事務(wù)的下一個提交(next-to-commit)值，并且 當特定事務(wù)準備好提交時，該事務(wù)在其提交序號匹配提交仲裁器的下一個 提交值的情況下被允許提交。

當在第一事務(wù)和第二事務(wù)之間發(fā)生沖突時調(diào)用爭用管理過程。在爭用 管理過程中使用預(yù)定提交次序來幫助確定第一事務(wù)還是第二事務(wù)應(yīng)當贏得 沖突并被允許繼續(xù)。

公開了用于將順序循環(huán)轉(zhuǎn)換成并行循環(huán)以與事務(wù)存儲器系統(tǒng)一起使用 的技術(shù)。提供了一種基于事務(wù)存儲器的系統(tǒng)。將包含原始順序循環(huán)的第一 部分代碼轉(zhuǎn)換成包含使用事務(wù)來保留原始的輸入到輸出映射的并行循環(huán)的 第二部分代碼。例如，可以通過取原始順序循環(huán)的每一迭代并生成遵循預(yù) 定提交次序過程的單獨事務(wù)，并隨后將這些事務(wù)分配到不同的線程以使它 們并行執(zhí)行，來將原始順序循環(huán)轉(zhuǎn)換成并行循環(huán)。萬一在執(zhí)行并行循環(huán)時 從特定事務(wù)中檢測到未經(jīng)處理的異常，則提交該特定事務(wù)和任何前導(dǎo)事務(wù) 所作出的狀態(tài)修改并丟棄任何后續(xù)事務(wù)所作出的狀態(tài)修改。否則，所有事 務(wù)提交。

在一個實現(xiàn)中，可以將開放和/或封閉順序循環(huán)轉(zhuǎn)換成并行循環(huán)。例如， 分析包含原始順序循環(huán)的一部分代碼以確定該原始順序循環(huán)的固定迭代次 數(shù)。將原始順序循環(huán)轉(zhuǎn)換成可生成數(shù)量等于固定迭代次數(shù)的事務(wù)的并行循 環(huán)。作為另一示例，可以將開放順序循環(huán)轉(zhuǎn)換成生成包含推測流水線的每 一迭代的相應(yīng)工作項的單獨事務(wù)的并行循環(huán)。將這些事務(wù)分配到不同的線 程以允許并行循環(huán)的至少一部分并行執(zhí)行。并行循環(huán)隨后在使用預(yù)定提交 排序的好處的事務(wù)存儲器系統(tǒng)的保護之下執(zhí)行。