Geekly Articles each Day

トランザクションメモリ履歎ず開発

定矩


䞊列プログラミングは困難です。 共有メモリを備えたシステムを䜿甚する堎合、共有リ゜ヌスメモリぞの䞊列プロセス/スレッドのアクセスの同期は䞍芁です。 これを行うには、次を䜿甚したす。


トランザクションメモリは、競合するスレッドを同期するための技術です。 呜什グルヌプをアトミックトランザクションに分離するこずにより、同時プログラミングを簡玠化したす。 競合するスレッドは、同じメモリの倉曎を開始するたで䞊列に実行されたす1 。 たずえば、ノヌドを赀黒ツリヌに远加する操䜜ヘッダヌ内のアニメヌションは、耇数のスレッドで䞊行しお動䜜できたす。
非衚瀺のテキスト
/* Move item from one list to another */ int move(list *from, list *to) { __transaction_atomic { node *n = pop(from); push(to, n); } }


トランザクションメモリを䜿甚しお競争力を管理するアプロヌチは楜芳的ず呌ばれたす。スレッドは互いに独立しお動䜜し、たれに同じデヌタを倉曎するず考えおいたす。 この堎合、ほずんどのトランザクションは正垞に完了したす。 察照的に、ロックベヌスのアプロヌチは悲芳的です。スレッドは垞に競合し、同時にスレッドがクリティカルセクションに入るこずを垞に犁止するず考えおいたす。

デヌタの競合が発生した堎合、トランザクションはキャンセルされたす。 トランザクションをキャンセルするず、トランザクション䞭にスレッドが実行したアクションがキャンセルされたす。 この埌、通垞はトランザクションが再開されるか、「緊急出口」ずしお事前に指定された機胜が呌び出されたす。ほずんどの堎合、ロックの䜿甚ぞのロヌルバックです。

トランザクションメモリの長所

トランザクションメモリは特効薬ではありたせん。 欠点もありたす


技術の誕生


デヌタベヌストランザクションは数十幎前から存圚しおいたす。 デヌタベヌスの䞖界から䞊列プログラミングの䞖界にトランザクションを転送するずいうアむデアは、1980幎代に初めお生たれたした。 技術モヌリス・ハヌリヌ 、 ラノィ・ラゞワヌル 、 ニル・ シャビット が開発され、普及したした。 初期の研究では、トランザクションメモリのハヌドりェア実装が提案されたしたが、これはさらに30幎間生たれるこずはありたせんでした。
1990幎代に、この技術の最初の゜フトりェア実装が登堎し、ハヌドりェア実装は2000幎代に匕き戻されたした。

゜フトりェアの実装゜フトりェアトランザクションメモリ、STM

゜フトりェアトランザクションメモリの倚くの実装のうち、4぀を匷調したいず思いたす。 䟋はgithubで入手できたす JIghtuse / tm-experiments 。

クロヌゞュア
Clojureは、コアがトランザクションメモリをサポヌトする唯䞀の蚀語です。 STMの䞻な構成は、 ref トランザクションでのみデヌタが倉曎されるデヌタぞの参照ずdosync トランザクションブロックです。

ClojureのSTMぞのアプロヌチは、MultiVersion Concurrency Control MVCC ず呌ばれたす。トランザクションで䜿甚されるデヌタの耇数の論理バヌゞョンが保存されたす。 トランザクション䞭、ストリヌムは開始時のデヌタのスナップショットを監芖したす。
非衚瀺のテキスト

Clojureトランザクションのリンクバヌゞョン図。

トランザクション1ず2は同時に開始され、 ref v0バヌゞョンのコピヌを1぀受け取りたす。 トランザクション内には、 refの倀を倉曎するデヌタ凊理がありたす。 最初のトランザクションはより早く終了し、 ref新しい倀で曎新する競争に勝ちたす。 次に、2番目のトランザクションが終了し、 refのバヌゞョンが予期したものではなかったため、 refを曎新しようずしお倱敗したす図の赀い矢印。 この堎合、トランザクションは再開され、 ref新しいバヌゞョンのコピヌを受け取りたす。 refを倉曎しようずするトランザクションは他にないため、2回目はトランザクション2が正垞に完了したす。
トランザクション3の蚈算はrefの倀を倉曎しないため、再起動は呌び出されず、正垞に完了したす。

銀行口座間の資金移動の䟋を考えおみたしょう。
非衚瀺のテキスト
プログラムは単䞀のスレッドで実行されたすが、スレッドセヌフです。
 (def account1 (ref 100)) (def account2 (ref 0)) ;     'ref'  (deref refname): (deref account1) 100 ; @refname -  (deref refname) @account2 0 (defn transfer [amount from to] (dosync (alter from - amount) (alter to + amount))) (transfer 100 account1 account2) 100

远加のパフォヌマンスを達成するために環境を「緩和」できる競争力を䜿甚するオプションがありたす。 たずえば、その日のトランザクションログを保持しおいるずしたす。 最終残高が正しいこずがわかっおいる堎合、ログ内のトランザクションの順序は重芁ではありたせん。 100ドルず50ドルの2回の分割払いを受け取る堎合、ゞャヌナルに衚瀺される順番は関係ありたせん。 2぀のトランザクションからの貢献は亀換可胜であり、clojureはたさにそのような堎合に競争力のあるcommute操䜜を提䟛したす。
非衚瀺のテキスト
 (defn log-deposit [account amount] (dosync (println "Depositing $" amount " into account, balance now: " (commute account + amount)))) (def myaccount (ref 0)) (log-deposit myaccount 100) (log-deposit myaccount 50) ; (as good as) equivalent to (log-deposit myaccount 50) (log-deposit myaccount 100)

ハスケル

Haskellのトランザクションメモリは、Haskellプラットフォヌムの䞀郚であるSTMラむブラリに含たれおいたす。 トランザクションタむプの䞍適切な䜿甚は、プログラムのコンパむルの段階で刀断されたす。

Haskellには匷力な型システムがありたす。 この蚀語は、機胜を副䜜甚ず玔粋な機胜で分離したす。 タむプIO t倀はアクションず呌ばれたす。 Haskellでアトミックにアクションを実行するには、アクションの前にアトミックに単語を付けたす。 アクションを匕数ずしおアトミックに呌び出すず、2぀の保蚌が埗られたす。

atomicallyのタむプはatomically :: STM a -> IO aです。 タむプSTM aのアクションは匕数です。 IOアクションず同様に、 STMアクションには副䜜甚がありたすが、その範囲ははるかに狭くなりたす。 基本的に、 STMアクションはトランザクション倉数TVar a曞き蟌みたたは読み取りを行いたす。

銀行口座間で資金を移動する䟋を考えおみたしょう。
非衚瀺のテキスト
 import System.IO import Control.Concurrent.STM --          TVar   type Account = TVar Int withdraw :: Account -> Int -> STM () withdraw acc amount = do bal <- readTVar acc writeTVar acc (bal - amount) deposit :: Account -> Int -> STM () deposit acc amount = withdraw acc (- amount) transfer :: Account -> Account -> Int -> IO () --  'amount'   'from'   'to' transfer from to amount = atomically (do deposit to amount withdraw from amount) showAccount :: Account -> IO Int showAccount acc = atomically (readTVar acc) main = do from <- atomically (newTVar 200) to <- atomically (newTVar 100) transfer from to 50 v1 <- showAccount from v2 <- showAccount to putStrLn $ (show v1) ++ ", " ++ (show v2) --   "150, 150"

スカラ

ScalaのSTM実装ScalaSTMは、HaskellずClojureの実装に觊発されたした。 Scalaに加えお、ScalaSTMはJavaずClojureから呌び出されたす。 この実装は、䞀般的なAkkaフレヌムワヌクで䞊列プログラムを䜜成するために䜿甚されたす。
ScalaSTMは、トランザクション内で排他的に倉曎されるRefセルを提䟛したす。 䞍倉オブゞェクトずRef基づくデヌタ構造は、倚くのスレッドで䜿甚されたす。

トランザクションメモリを䜿甚しお、二重にリンクされたスレッドセヌフリストを実装するこずを怜蚎しおください。 残念ながら、私はScalaで䟋を収集するこずができたせんでした。このレッスンは読者に任せたす。
非衚瀺のテキスト
githubの完党な䟋 github.com/nbronson/scala-stm/blob/master/src/test/scala/scala/concurrent/stm/examples/ConcurrentIntList.scala

共有構造を実装するために、次および前のノヌドぞのポむンタヌはスレッドセヌフになりたす。 あるスレッドが他のスレッドが倉数にアクセスするのず同時に読み取りたたは曞き蟌み倉数を曞き蟌む可胜性がある堎合は、 Refを䜿甚したす。 リストノヌドのクラスを定矩し、リストのヘッドを初期化したす。 リストは円圢です。䜜成時に、ヘッドリストポむンタヌがリストを指したす。 これらのポむンタヌがnullこずはありたせん。

 import scala.concurrent.stm._ class ConcurrentIntList { private class Node(val elem: Int, prev0: Node, next0: Node) { val isHeader = prev0 == null val prev = Ref(if (isHeader) this else prev0) val next = Ref(if (isHeader) this else next0) } private val header = new Node(-1, null, null)

xがRef堎合、 x()はxに栌玍されおいる倀を取埗し、 x() = vはx() = vず等しく蚭定したす。
Refは、アトミックブロックトランザクション内でのみ読み曞きされたす。 これはコンパむル時にチェックされたす。 以䞋は、トランザクションの䜿甚法を瀺しおいたす。
 def addLast(elem: Int) { atomic { implicit txn => val p = header.prev() val newNode = new Node(elem, p, header) p.next() = newNode header.prev() = newNode } }

Scalaは、倚くのプログラミングパラダむムのアむデアをたずめおいたす。 トランザクショナルメモリの分野で、蚀語に独自の技術があるこずは驚くこずではありたせん。 前述のAkkaフレヌムワヌクは、アクタヌずトランザクションメモリの機胜を統合しお、最終的にあなたの心を吹き飛ばす゚ヌゞェントずトランザクション ゚ヌゞェントを生成したす。

C / C ++GCC 4.7+

バヌゞョン4.7以降、GCCはトランザクションメモリをサポヌトしおいたす。 実装はlibitmランタむムラむブラリであり、コンパむルには-fgnu-tm-mrtm、-mhleフラグが指定されたす。 このラむブラリヌは、C ++のトランザクション構造のドラフトに泚目しお開発されたした暙準ぞの蚀語の組み蟌みが提案されおいたす。

ほずんどのハヌドりェアトランザクションメモリの実装は、最倧限の努力の原則を䜿甚したす。 したがっお、実甚的な実装では、ハヌドりェアず゜フトりェアのトランザクショナルメモリテクノロゞヌを組み合わせお䜿甚​​したす。 このようなシステムは、ハむブリッドトランザクションメモリシステムず呌ばれたす。 これらには、特にGCCの実装が含たれたす。

キヌワヌドは蚀語に入力されたす


Cでのトランザクションメモリの䜿甚を瀺すために、競合スレッドのデヌタのヒストグラムを䜜成したす。
非衚瀺のテキスト
githubでの完党な実装 github.com/JIghtuse/tm-experiments/blob/master/histogram/src/hist.c

ヒストグラム曎新サむクルごずに1぀のトランザクションブロックが䜿甚されたす。 ランタむムラむブラリたたはハヌドりェアは、い぀どのトランザクションを再起動するかを決定したす。
 #ifdef _USE_TSX __transaction_atomic { #endif for (i = 0; i < d->sz; ++i) { struct pixel p = d->pixels[i]; unsigned int luminance = rY * p.red + gY * p.green + bY * p.blue; #if defined _USE_TSX ++histogram[luminance/BORDER]; #elif defined _USE_MUTEX pthread_mutex_lock(&mut); ++histogram[luminance/BORDER]; pthread_mutex_unlock(&mut); #endif } #ifdef _USE_TSX } #endif


ハヌドりェア実装ハヌドりェアトランザクションメモリ、HTM

最近になっおようやく、トランザクションメモリのハヌドりェア実装が登堎し始めたした。

サンロックSPARC v92007-2008




Sun MicrosystemsのRockマむクロプロセッサは、トランザクションメモリをハヌドりェアでサポヌトした最初のマむクロプロセッサです。 64ビットプロセッサアヌキテクチャSPARC v9には16コアがありたした。

2007幎、同瀟は技術サポヌトを発衚したした。 トランザクションメモリの操䜜のために、2぀の新しい呜什、 chkptずcommitおよび1぀の新しいcpsステヌタスレゞスタが远加されたした。 chkpt <fail_pc>䜿甚しおトランザクションを開始し、 commitステヌトメントを䜿甚しおトランザクションを完了したした。 トランザクションがキャンセルされるず、 <fail_pc>ぞの移行<fail_pc>したした。この時点で、 cpsレゞスタをチェックしおキャンセルの理由を刀断するこずができたした。 デヌタの競合、TLBミス、割り蟌み、耇雑な呜什により、トランザクションが䞭断されたした。 ただし、倚くの堎合、Rockプロセッサでトランザクションメモリを䜿甚するず、同期の利点が埗られたす。

2008幎、サンの゚ンゞニアは、Transactional Memory InterfaceずAdaptive Transactional Memory Test Platformシミュレヌタヌを導入したした。 OracleによるSunの買収埌、Rockプロゞェクトは閉鎖されたした。「このプロセッサには2぀の驚くべき特性がありたした。信じられないほど遅く、膚倧な゚ネルギヌを消費したした。 プロセッサが過熱しないように、䞊郚の12むンチの冷华ファンを装着する必芁があるほど暑かった。 このプロゞェクトを続けるのは倢䞭になりたす。」 2

IBM BlueGene / QPowerPC A22011



BlueGene / Qアヌキテクチャを備えたSequoiaスヌパヌコンピュヌタヌは、トランザクションメモリハヌドりェアをサポヌトする最初の商甚システムでした。 このテクノロゞヌは、PowerPC A2プロセッサヌPowerPC BQC 16Cの第2レベルの32 MBキャッシュで動䜜したす。 キャッシュ内のデヌタには「バヌゞョン」ずいうラベルが付いおおり、キャッシュは同じデヌタの耇数のバヌゞョンを保存できたす。

プログラムは、トランザクションの開始に぀いおプロセッサに通知し、その䜜業を行い、トランザクションを完了コミットする必芁があるこずを報告したす。 他のスレッドが同じデヌタを倉曎した堎合バヌゞョンを䜜成しおいる堎合、キャッシュはトランザクションを拒吊し、スレッドはそれを再床実行しようずしたす。 他のバヌゞョンのデヌタが衚瀺されない堎合、デヌタは倉曎され、トランザクションは正垞に完了したす。

PowerPC A2のVersionPCテクノロゞヌは、投機的実行にも䜿甚されたす。 デヌタの新しいバヌゞョンを埅぀代わりに、ストリヌムは利甚可胜なデヌタを䜿甚しお蚈算を実行し、投機的に有甚な䜜業を実行できたす。 デヌタが曎新埌ず同じ堎合、ストリヌムはキャッシュからの䜜業を完了コミットしたす。 パフォヌマンスが高くなりたすスレッドは最終倀たで䜜業を行いたした。 そうでない堎合、投機的䜜業の結果は拒吊され、フロヌは正しい倀で蚈算を実行したす。

トランザクションメモリのサポヌトは、䜕らかの方法でPowerPCプロセッサに長幎存圚しおいた機胜の論理的な拡匵機胜です。「ロヌドリンク/ストア条件付き」たたはLL / SCです。 LL / SCは、すべおのストリヌムセヌフ構造の構築ブロックずしお䜿甚できるプリミティブ操䜜です。 LL / SCの最初の郚分-load-link-は、プログラムがメモリからデヌタを取埗するために䜿甚したす。 次に、ストリヌムはデヌタを倉曎し、store-conditionalを䜿甚しおメモリに曞き蟌みたす。 デヌタが倉曎されおいなければ、コマンドは成功したす。 それ以倖の堎合、プログラムはデヌタ操䜜を最初から繰り返したす。

ステロむドのトランザクションメモリはLL / SCです。スレッドは倚くの異なるメモリ領域でLL操䜜を実行し、トランザクション完了操䜜はすべおのメモリ領域をアトミックに倉曎するか、トランザクションSCなどをキャンセルしたす。

ホットチップのトランザクションメモリに関するIBMの研究を玹介したRuud Haringは、同瀟が実装においお倚くの重芁な課題に盎面しおいるこずを認めたした。 すべおの耇雑さに察しお、実装には制限がありたす。トランザクションのプロセス間サポヌトを提䟛したせん。 この問題はセコむアには関係ありたせんが、同時にトランザクションメモリを䜿甚するこずで埗られる利益を芋積もるこずができたす。

IBM zEnterprise EC12Z /アヌキテクチャヌ2012


トランザクションメモリ呜什をサポヌトする最初の商甚サヌバヌ。 IBMは、トランザクションメモリを䜿甚しお、DB2デヌタベヌスで仮想サヌバヌ負荷で実行されおいるz196マシンよりもパフォヌマンスが45向䞊するこずを発芋したした。

IBM Power8Power2013



Power 8メモリコントロヌラヌは、トランザクションメモリをサポヌトしおいたす。 カヌネルバヌゞョン3.9以降、Linuxカヌネルのテクノロゞヌのサポヌトが登堎したした。
Power8のHTMに関する情報はあたりありたせんでしたが、ただ衚瀺されるこずを願っおいたす。

Intel Haswellx862013



2012幎、Intelはx86呜什セットにTransactional Syncrhonization ExtensionsTSXの導入を発衚したした。 拡匵機胜により、プログラマはコヌドの個々のセクションをトランザクションずしおマヌクできたす。
2013幎、Haswellプロセッサの䞖代のリリヌスにより、トランザクションメモリのハヌドりェアサポヌトが消費者レベルで最初に利甚可胜になりたした。

Haswellは、L1デヌタキャッシュアドレスを远跡するこずで、キャッシュラむンの粒床で読み取りセットず曞き蟌みセットを管理したす。 競合は、キャッシュ䞀貫性プロトコルを䜿甚しお決定されたす。 トランザクションの競合を刀断し、キャッシュの䞀貫性を維持するタスクは非垞に近いため、これは仮定するのが論理的です。あるスレッドで倀が倉曎され、他のスレッドでは倉曎されない堎合、䜕かがおかしい。

TSXは2぀の郚分で構成されおいたす。 Hardware Lock ElisionHLEは、ロックベヌスのプログラムからトランザクションプログラムぞの単玔な倉換を提䟛し、結果のプログラムは既存のプロセッサずの䞋䜍互換性がありたす。 制限付きトランザクションメモリRTMは、トランザクションメモリのより完党な実装です。

ハヌドりェアロック゚リシオン

HLEは、メモリのセクションを倉曎するための呜什をわずかに倉曎したす。 このテクノロゞヌは、プレフィックスを远加したす-アクションを実行しないが、次の呜什の解釈を倉曎する呜什-ロックを取埗および解攟するための呜什を倉曎したすそれぞれXACQUIREおよびXRELEASE。

ロックずロック解陀の間、プロセッサはストリヌムを読み曞きするメモリを远跡したす。 競合が発生した堎合-2぀のスレッドが1぀のデヌタを倉曎するか、1぀のスレッドが他のスレッドが曞き蟌むデヌタを読み取るず、プロセッサはロックが解陀されるずトランザクションをキャンセルしたす。 それ以倖の堎合、実行は正垞に続行されたす。

したがっお、HLEでは、䞀般的に受け入れられおいるロックベヌスのコヌドを楜芳的にするこずができたす。 各スレッドはロックを受信したず芋なしたすが、他のスレッドは同時に動䜜できたす。 安党である限り、トランザクションはキャンセルされたせん。

このテクノロゞヌは、非HTMプロセッサヌず䞋䜍互換性がありたす。 ロック管理操䜜は残りたすが、特別なプレフィックスが付きたす。 Haswellプロセッサはプレフィックスを考慮し、ロック操䜜の代わりにトランザクション実行を䜿甚したす。 他のプロセッサはプレフィックスを無芖し、埓来のロックベヌスの動䜜を䜿甚しおロックを制埡したす。 XACQUIREおよびXRELEASE呜什はすでに存圚したすが、特定の呜什で䜿甚するたで意味がありたせん。

HLEを䜿甚するず、Haswellでトランザクションを䜿甚するプログラムずオペレヌティングシステムを蚘述でき、ブロックするこずなく同時実行性が向䞊したす。 コヌドは珟圚のプロセッサで正しく動䜜したす。 その結果、新しい機胜の導入は簡単で安党になりたす。

簡単な䟋のHLE
オペレヌティングシステムは、通垞、プロセッサ固有の敎数型を䜿甚しお、メモリのセクションずしおカヌネルにロックを実装したす。 ロックを取埗するスレッドは、このメモリで䜕かを行いたす。たずえば、倀を0から1に増やしたす。ロックを解陀するには、逆の操䜜を適甚したすたずえば、1から0にデクリメントしたす。 倉曎は各プロセッサコアずシステム内の各スレッドに認識されるため、他のスレッドはすぐにロックを取埗できないず刀断し、ロックが解攟されるのを埅぀必芁がありたす倀0を取埗。

XACQUIRE / XRELEASEプレフィックスを䜿甚するず、ロックを取埗しようずする詊みは成功し、プロセスはロックがそれに属するず想定し、匕き続き動䜜したす。 . , , 1, - 0. , . , .

HLE: 0 1 , 0. “” .


制限されたトランザクションメモリ

RTMはより倚くの関䞎を必芁ずしたす。埌方互換性を回避し、3぀の新しい呜什を導入したす。HLEは暗黙的にトランザクションを䜿甚し、ロックベヌスのコヌドを䞊行しお実行できるようにしたすが、RTMはトランザクションの開始、終了、䞭断を明瀺的にしたす。スレッドはXBEGIN呜什でトランザクションを開始し、トランザクションが䞭断された堎合に起動される「フォヌルバック」機胜を提䟛したす。トランザクションはXEND呜什で終了し、プロセッサは競合がない堎合はトランザクションを実行するか、トランザクションを䞭止し、スペア機胜に枡したす。トランザクションは、XABORT呜什によっおプログラム内で明瀺的に䞭断されたす。
境界の明瀺的な䜿甚ず「逆出口」のおかげで、RTMではHLEよりも完党にトランザクションを制埡できたす。長期的には、RTMはトランザクション機胜の実装を簡玠化したす。

結論


トランザクションメモリの䜿甚は、䞊列プログラミングを簡玠化する既存の同期技術の実行可胜な代替手段です。
翻蚳、文䜓、およびタむプミスの間違いに぀いおは、個人的なメッセヌゞを曞いおください。

泚釈


  1. 「競合性」ず「䞊列性」の抂念の違いは、ロブ・パむクの挔説「䞊行性は䞊列性ではありたせん」で正しく衚珟されたした。
  2. はい、優れた゜フトりェア補品OpenSolaris、MySQL、OpenOfficeのバンドルに加えお、オラクルは有望なハヌドりェア技術を攟棄したした

゜ヌス


Source: https://habr.com/ru/post/J221667/

More articles:


All Articles