問題タブ [stm]

私はHaskellのSTMライブラリを使用してきましたが、トランザクションを作成する機能と、STMの一般的な「この間違いを取得できない」という性質が本当に気に入っています。

正当な理由で、STMはトランザクション内のIOアクションを許可しません。IOアクションを再試行する方法はありません。（ここに発射ミサイルのリファレンスを挿入してください）。一方、データベーストランザクションには、非常によく似た原子性の保証がいくつかあります。2つを一緒に使用するための受け入れられた方法はありますか？

次のバージョンのリーダー-ライター問題があります: 複数のリーダーとライター、2 人以上のリーダーが同時に読み取ることができます。ライターが書き込みを行っている場合、誰も読み書きできません。 100 ラウンドの例では、5 人のライターがそれぞれ約 20 回書き込む必要があります)。STMを使用してClojureでこれを実装する適切な方法は何ですか? 私は完全なコードを探しているのではなく、いくつかの一般的な指示を探しています。

ライブラリ内のcheck関数に型があり、型を持つのではなく成功時に返される正当な理由はありますか? 型チェッカーが実装されている方法では、実行時にのみ失敗する で終わる do ブロックをポリシー コンパイルします。Contol.Concurent.STMBool -> STM aundefinedBool -> STM ()check foo*** Exception: Prelude.undefined

私は、STM（ソフトウェアトランザクショナルメモリ）の実装、特にロックを利用し、C /C++などの非管理言語との互換性を維持するためにガベージコレクターの存在に依存しないアルゴリズムについていくつかの調査を行ってきました。HerlihyとShavitの「TheArtofMultiprocessor Programming」のSTMの章を読んだほか、彼の「TransactionalLocking」と「TransactionalLockingII 」について説明しているShavitの論文をいくつか読みました。STMの実装。彼らの基本的なアプローチは、グローバルバージョンクロックとロックの値を格納するハッシュテーブルを利用して、メモリ位置が別のスレッドの書き込みによって影響を受けたかどうかを判断することです。アルゴリズムを理解しているように、書き込みトランザクションが実行されると、バージョンクロックが読み取られてスレッドローカルメモリに格納され、読み取りセットと書き込みセットもスレッドローカルメモリに作成されます。次に、次の手順が実行されます。

1. 読み取られたアドレスの値は、読み取りセットに格納されます。これは、トランザクションが、読み取られている場所がロックされておらず、ローカルに保存されているバージョンクロック値以下であることを確認することを意味します。
2. 書き込まれたアドレスの値は、それらの場所に書き込まれる値とともに、書き込みセットに格納されます。
3. 書き込みトランザクション全体が完了すると（これには、複数の場所への読み取りと書き込みが含まれる場合があります）、トランザクションは、アドレスに対してハッシュされるハッシュテーブルのロックを使用して、書き込まれる各アドレスをロックしようとします。 ' 価値。
4. すべての書き込みセットアドレスがロックされると、グローバルバージョンクロックがアトミックにインクリメントされ、新しいインクリメントされた値がローカルに保存されます。
5. 書き込みトランザクションは、読み取りセットの値が新しいバージョン番号で更新されていないこと、または別のスレッドによってロックされていないことを確認するために再度チェックします。
6. 書き込みトランザクションは、そのメモリ位置のバージョンスタンプを手順4で保存した新しい値で更新し、書き込みセットの値をメモリにコミットします。
7. メモリ位置のロックが解除されます

上記のチェックステップのいずれかが失敗した場合（つまり、ステップ＃1、＃3、および＃5）、書き込みトランザクションは中止されます。

読み取りトランザクションのプロセスははるかに簡単です。Shavitの論文によると、私たちは単に

1. グローバルバージョンクロック値を読み取り、ローカルに保存します
2. メモリ位置に現在保存されているグローバルバージョンクロック値よりも大きいクロック値がないことを確認し、メモリ位置が現在ロックされていないことも確認します
3. 読み取り操作を実行します
4. 検証のためにステップ2を繰り返します

手順2または4のいずれかが失敗した場合、読み取りトランザクションは中止されます。

ヒープ内にあるオブジェクト内のメモリ位置を読み取ろうとしたときに、別のスレッドがdeleteそのオブジェクトへのポインタを呼び出すと、どうなるのでしょうか。Shavitの論文では、リサイクルまたは解放されたメモリ位置への書き込みができないことを詳しく説明していますが、読み取りトランザクションの内部では、可能性のあるタイミングシナリオを妨げるものは何もないようです。別のスレッドによって解放されたオブジェクト内のメモリ位置から読み取るため。例として、次のコードについて考えてみます。

Thread Aアトミック読み取りトランザクション内で次を実行します。linked_list_node* next_node = node->next;

Thread B以下を実行します。delete node;

next_nodeはスレッドローカル変数であるため、トランザクションオブジェクトではありません。の値を割り当てるために必要な間接参照操作はnode->next、実際には2つの別々の読み取りを必要とします。これらの読み取りの間に、deleteを呼び出すことができるnodeため、メンバーからの読み取りは、nextすでに解放されているメモリのセグメントから実際に読み取られます。node読み取りは楽観的であるため、 inが指すメモリの解放はThread Bで検出されませんThread A。クラッシュやセグメンテーション違反が発生する可能性はありませんか？もしそうなら、読むためのメモリ位置もロックせずにそれをどのように回避できますか（教科書と論文の両方が示すものは不要です）？

TransactionalMap通常の不変マップと混合するよりもAkkaを優先する必要があるのはSynchronizedMapいつですか？（または、ここでリンゴとオレンジを比較していますか？）

Data.Uniqueでこのイディオムに気付きました:

一度だけ実行されることが保証されていますか?

私は関数型プログラミングとClojureを初めて使用するので、大学でのプロジェクトで何をすべきかよくわかりません。プロジェクトは、銀行取引（口座Aから口座Bへの送金）におけるClojureSTMの利点を示す必要があります。だから私はこのように進めることを計画しています：

1. 参照のマトリックスなどの初期データを定義する
2. 実行するランダム操作を生成します。[ random-account-source-id(0, N_MAX) , random-account-destination-id(0, N_MAX), random-money (0, 1000) ]
3. トランザクションをデータ構造に挿入します
4. 次のようなマトリックスへのすべての挿入について、source-idからdestination-idへの送金を同期します。 /li>

これについてはよくわかりませんが、多分：

元の質問

STMは初めてです。Haskellでやりたいことの1つは、大きなデータと、その大きなデータの小さな部分の読み取りと書き込みを行う多数の軽量スレッドです。読み取りおよび書き込みの場所は、本質的にランダムで小さいと見なすことができます。STMはこれには最適のようですが、問題をどのように攻撃するかについていくつか質問があります。私はいくつかの可能なアプローチを見て、それぞれにいくつかの欠点があり、いくつかは明らかに愚かなようです。これらに関するいくつかのコメント、または代替案に関する他のアイデアをいただければ幸いです。

簡単にするために、大きなデータがData.Vector aであり、要素自体が小さいと仮定しましょう。

1. データ全体を1つにTVar (Vector a)。STMは、個々の書き込みが共有データ全体に影響を与えている可能性があると考えているため、これにより膨大なデータのコピーが大量に発生すると思います。確かに、読み取りと書き込みが非常にローカライズされていること、および大きなデータ全体での一貫性が必要ないことをSTMが識別する場合、魔法は起こりませんか？

2. 大量のTVar as、基本的に各要素に1つ、完全にローカライズされたSTMを提供しますが、基本的に全体を複製しますVector a。これはばかげているようです。

3. TVar (Vector a)データのサブベクトルに対応する妥当な数のsが得られるように、データをセグメント化することによる1と2の間の妥協点。このソリューションは、セグメントの大きさなど、ヒューリスティックに大きく依存していると思います。

4. メッセージング。各ワーカーは、STMを使用してデータの読み取りと書き込みを行う代わりに、データの読み取り要求またはデータのチャンクをSTMメカニズムなどのSTMメカニズムを介して書き込むメッセージを書き込みますTChan。特別なスレッドがこれらのメッセージを受信し、別のスレッドを介して要求されたデータを渡すTChanか、受信したデータを取得して共有データ構造に書き込みます。このソリューションは、ソリューション1〜3を悩ませている問題がないように見えますが、データの一貫性を維持するためにSTMの優れた機能を使用することを本質的に諦めているようにも見えます。むしろ、それは単なるメッセージパッシングです。確かに、メッセージパッシング部分はSTMで実装されていますが、私の本当の問題はメッセージパッシングで解決されます。STMはとても素晴らしいようです、メッセージパッシングはとても...まあ。

私はこれについて正しく考えていますか？誰かが何かヒントや他の提案がありますか？

私はSTMの経験がなく、上記の解決策をまだ試したことがないことを覚えておいてください。肘掛け椅子から降りますが、何かを試す前にこれらのことを考えておくとよい場合があります。

補遺： 5番目のアプローチはNathan Howellによるもので、を使用していますTArray。それは私が望むもののように聞こえますが、ドキュメントには次のように書かれています。

現在、Array ix（TVar e）として実装されていますが、将来、より効率的な実装に置き換えられる可能性があります（ただし、インターフェイスは同じままです）。

私はこれをTArray、より良い服を着た私のアプローチ2番だと解釈します。「より効率的な」実装について示唆しているドキュメントは、実際にはより優れたアプローチがあることを示唆しているため、興味深いものです。

VagifVerdiの回答のフォローアップ

Vagif Verdiの答えは非常に興味深いので、少し実験して試してみました。今はコードをスリム化する時間がないので、これに興味のある人は、必要不可欠なものだけでなく、コードについても我慢しなければなりません。Int「大きな共有データ」として10^8秒の可変ベクトルを使用し、複数のリーダー/ライターをネットワークソケットに取り込むスレッドに対応させることにしました。

コードは、共有されたデータの読み取りや書き込みさえも行わないことに注意してください。それは単にそこにあり、各スレッドはそれに保持しTVarます。

では、どうなりますか？プログラムを実行すると、すぐに約780 MBのRAMが必要になります。これは、予想されるとおりです（これは、おおよそ10 ^ 8Int秒に必要な量です）。ここで、netcatを使用していくつかのクライアントを接続し、少しのテキストを書き込むと、プログラムはそれを出力し、共有データには書き込まないことになっています。プロセスのCPU使用率は1秒以上100％に急上昇します。 ！！テキストが表示されるまでに顕著な遅延があります。明るい面では、メモリ使用量は一定のままです（Vagif Verdiの回答による）。ベクトルとを削除するとTVar、つまりすべてのSTMと共有データを削除すると、すべてが非常に高速で応答性が高く、クライアントが何かを書き込んだときにCPU使用率が目立つことはありません。

したがって、共有データが実際に複製されていないことを確認するのは非常に良いことですが（これを完全に検証するには、実際に共有データに書き込む必要があると思いますが）、コヒーレント状態の維持には非常に大きなパフォーマンスの低下が伴います。私にとって、私の質問は残ります。STMの優れた点を維持しながら、この問題を適切に攻撃するにはどうすればよいでしょうか。

いくつかの非常に興味深い点を提起してくれたVagifVerdiに感謝します。

Snap ソース内 Snap.Internal.Http.Server.TimeoutManager

_morePlease フィールドがあるのはなぜですか?
何をし_ <- tryPutMVar morePlease ()ますか？

Web アプリで、限られた ID プールから一意のスレッド セーフ ID を生成しようとしています。私が直面している問題は、別のスレッドの読み取りと書き込みの間に、データ構造が既に変更されている可能性があることです。これが私が頼らなければならない理由ですcompare-and-set!。

sid-pool「手動で」STM を実行する必要がなく、フィールドをからの戻り値として悪用することなく、読み取りと書き込みを同期する簡単な方法はありswap!ますか?