🦇 🔂 🖐🏿 トランザクションメモリ：履歴と開発 ⏹️ 🧔🏿 😘

定義

並列プログラミングは困難です。共有メモリを備えたシステムを使用する場合、共有リソース（メモリ）への並列プロセス/スレッドのアクセスの同期は不要です。これを行うには、次を使用します。

ロック（ミューテックス）;
ロックのないアルゴリズム（ロックレス、ロックフリー）;
トランザクションメモリ。

トランザクションメモリは、競合するスレッドを同期するための技術です。命令グループをアトミックトランザクションに分離することにより、同時プログラミングを簡素化します。競合するスレッドは、同じメモリの変更を開始するまで並列に実行されます¹ 。たとえば、ノードを赤黒ツリーに追加する操作（ヘッダー内のアニメーション）は、複数のスレッドで並行して動作できます。

非表示のテキスト

/* 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 act

する効果は、他のフローからすぐに、そして全体として見えるようになります。他のストリームはアトミックアクション内の状態を見ることができず、最終状態のみを見ることができます。
分離- atomically act

呼び出し中atomically act

アクションは他のスレッドから完全に独立して実行されます。起動時に世界の状態を削除し、その状態で実行します。

atomically

のタイプはatomically :: STM a -> IO a

です。タイプSTM a

のアクションは引数です。 IO

アクションと同様に、 STM

アクションには副作用がありますが、その範囲ははるかに狭くなります。基本的に、 STM

アクションはトランザクション変数TVar a

書き込みまたは読み取りを行います。

readTVar :: TVar a -> STM a
writeTVar :: TVar a -> a -> STM ()

銀行口座間で資金を移動する例を考えてみましょう。

非表示のテキスト

 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の実装が含まれます。

キーワードは言語に入力されます：

__transaction_atomic { … }

-コードブロックがトランザクションであることを示します。
__transaction_relaxed { … }

-ブロック内の安全でないコードが副作用につながらないことを示します。
__transaction_cancel

明示的なトランザクションのキャンセル。
attribute((transaction_safe))

-トランザクションセーフ機能の表示。
attribute((transaction_pure))

-副作用のない関数を示します。

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インチの冷却ファンを装着する必要があるほど暑かった。このプロジェクトを続けるのは夢中になります。」 ²

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はトランザクション機能の実装を簡素化します。

結論

トランザクションメモリの使用は、並列プログラミングを簡素化する既存の同期技術の実行可能な代替手段です。

翻訳、文体、およびタイプミスの間違いについては、個人的なメッセージを書いてください。

注釈

「競合性」と「並列性」の概念の違いは、ロブ・パイクの演説「並行性は並列性ではありません」で正しく表現されました。
はい、優れたソフトウェア製品（OpenSolaris、MySQL、OpenOffice）のバンドルに加えて、オラクルは有望なハードウェア技術を放棄しました

トランザクションメモリ：履歴と開発

定義

技術の誕生

ソフトウェアの実装（ソフトウェアトランザクションメモリ、STM）

クロージュア

ハスケル

スカラ

C / C ++（GCC 4.7+）

ハードウェア実装（ハードウェアトランザクションメモリ、HTM）

サンロック（SPARC v9）2007-2008

IBM BlueGene / Q（PowerPC A2）2011

IBM zEnterprise EC12（Z /アーキテクチャー）2012

IBM Power8（Power）2013

Intel Haswell（x86）2013

ハードウェアロックエリシオン

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

結論

注釈

ソース

More articles: