5

Bartosz Milewski の STM に関するすばらしいブログ投稿を読んで、次の記事を読んで興奮しました。

ただし、重要な事実を考慮してください。STM は非常にきめ細かいものです。たとえば、アイテムをツリーに挿入する場合、STM トランザクションは、実際に変更しているノードのみをロックします。STM は、ツリー全体に 1 つのグローバル ロックを使用するソリューションよりも簡単に勝てます。

しかし、私が理解しているように、この動作は自動ではありませんよね? を使用するTVar (Map k a)と、マップ全体で単一のグローバル ロックとして機能しませんか? そして、このきめの細かい動作の利点を得るには、私 (または誰か) が、内部にTMap含まれるマップの置換 (たとえば、 )を実装する必要がありますね。TVars

これは明らかな質問のように思えるかもしれませんが、STM の実装について調べていると、TVars の読み取りとメモリ位置の読み取りを混同していました。私はそれが正しいことを確認したいだけです！

Bartosz 氏はさらに次のように述べています。

デッドロックのリスクがあるため、ノードごとの手動ロックを正しく実装するのは困難です。

私が理解しているように、STM との違いは、実際の STM 実装では手動でロックされたソリューションと同じようにロックを使用する一方で、実際のロックの取得と解放はプログラマーではなくランタイムによって処理されるということです。正しいですか?

4

1 に答える 1

8

ATVarは可変セルです。不変の構造では、2 つのスレッドが変更を前後に送信することはできないため、効果を引き起こすには可変セルの概念が必要です。特に、

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

SMT変更可能なセル内の値を置き換えるアクションを作成します。これらの操作のいくつかを一緒にシーケンスして、より大きく、より複雑なSTMアクションを構築し、次に呼び出すことができます

atomically :: STM a -> IO a

アクション全体STMを一度にアトミックにコミットします。これは、ソフトウェア トランザクション メモリの「トランザクション」部分です。これらの可変セルへの独自の参照を持つ他のスレッドは、実行されたアクション全体のみをatomically監視し、サブ部分は監視STMしません。これを実現するために、Haskell はロックを使用するか、より巧妙な方法を使用する可能性があります。これは単なる実装の詳細です。STM知っておくべき唯一のことは、STMブロック内のアクションが必要に応じて繰り返し実行される可能性があることです。したがって、一部の共有メモリ セルの変更以外の副作用は禁止されています。

では、細粒度の並行性を実現するにはどうすればよいでしょうか。簡単に言えば、さまざまなスレッドが同期するための可変セルを提供するだけです。たとえば、少なくとも 3 つの異なるMap型を読み取ることができます。

TVar (Map k v)
Map k (TVar v)
TVar (Map k (TVar v))

1 つ目は、部分的な変更が表示されないように、並行スレッドがMap一度に全体を変更できるようにします。2 つ目は、保存された値の変更を許可しますが、マップ自体の構造 (キーの選択と保存された値の選択) は不変であり、変更を他のスレッドに簡単に伝達できないことを維持します。

最終的な選択肢TVar (Map k (TVar v))は、最も柔軟です。Map外側を同期することで大規模な変更を行うことTVarができ、値まで読み込んTVarでその中のアクションを同期することで、マップに格納されている値を変更できます。このようなツリーで使用可能なセマンティクスの完全なセットは無数にあり、「全体のMapロック」と「個々の値のロック」の両方を一緒に行うことができます。

于 2014-04-02T07:05:34.070 に答える