問題タブ [stm]

STM にいくつかの値のバッファを保存する必要があります。書き込みスレッドは、バッファーのサイズを監視する必要があります。私はTChannelを使用してこのことを実装し始めましたが、API がチャネルの長さを測定する方法を提供していないことがわかりました。1 つの頑固な男であるため、私はそれを自分で実装しました。

今ではすべて正常に動作していますが、標準ライブラリに実装されていないような些細なことの理由と、そのような問題への好ましいアプローチは何なのか疑問に思っています。このアルゴリズムには少なくとも O(n) の複雑さがあることはわかっていますが、それが理由になることはありませんよね?

まず、いくつかの背景。2 つの異なるモードのいずれかで操作したいキューが必要です。最初のモードでは、要素がキューに存在する場合は要素を取得できるようにしたいが、要素がない場合はブロックしたくない。2 番目のモードでは、キューに要素が含まれるまでブロックできるようにしたいと考えています。（各モードに特化したメカニズムを使用できることは承知していますが、いくつかの共通コードを除外したいので、両方の動作モードで同じメカニズムを使用できれば最も簡単です。）

を使用できますChanが、ドキュメントによると、isEmptyChanデッドロックの可能性があるため非推奨であるため、使用しないでください。これは私を残しますTChan。このtryReadTChan関数は、最初のモードに必要なものを正確に提供します (つまり、ブロックせずに要素が存在するかどうかを確認できます) が、何が機能するのか正確にはわかりreadTChanません。私のメンタル モデルはatomically、要素がチャネルに存在するまでブロックが再試行し続けるというものです。これは、CPU サイクルを浪費するビジー ループになることを意味します。これはreadChan、MVar がランタイム スレッド スケジューラによって理解されるため、要素が利用可能になるまでスレッドの実行を実際にブロックする (正しく理解できれば) (つまり、非 STM バージョン) とは異なります。

つまりTChan、ランタイムChanを使用readTChanすると、値が利用可能になるまで呼び出し元のスレッドをスケジュールしないほどスマートであるということですか? それとも、値が到着するまで継続的にポーリングするために多くの CPU サイクルを無駄にしますか?

MVar は少しシンプルに見えますが、TVar はもう少し機能が豊富ですが、TVar は非常に使いやすいと思います。

だから私の質問は非常に単純です.TVarではなくMVarに行きたいのはどのような条件ですか? トランザクションの更新が必要ないときはいつでもMVar を使用できると思いますが、それはどのようなメリットがありますか?

並列プロセスを管理するためにDeuce STMを利用する円周率計算用のJavaライブラリを作成しました。 さらに、ライブラリの型安全性を証明したいと考えています。 Deuce STM ライブラリは型安全ですか? はいの場合、同じリンクをいくつかいただければ幸いです。

Clojure のマップ ref のカウンターの更新に取り組んでいます。

ただし、alter value inc ステートメントが参照を失っているようです。

どちらが印刷されますか:

このシナリオで更新中に同じ参照を保持するにはどうすればよいですか?

GHC Haskellstm、ネットワーク コンジット、およびコンジットを利用する私のアプリケーションでは、各ソケットにストランドがあり、これは を使用して自動的にフォークされますrunTCPServer。ストランドは、ブロードキャスト TChannel を使用して他のストランドと通信できます。

これは、コンジット「チェーン」をセットアップする方法を示しています。

したがって、ここにあるのは 2 つのソース (それぞれがヘルパー コンジットにバインドされている) で、Packetオブジェクトを生成します。このオブジェクトencoderは、受け入れて に変換ByteStringし、ソケットを送信します。私は、2 つの入力を効率的に (パフォーマンスが懸念事項です) 融合するのに非常に苦労しました。

誰かが私を正しい方向に向けることができれば幸いです。

試みずにこの質問を投稿するのは失礼なので、以前に試したことをここに記載します。

TMChan (クローズ可能なチャネル) からソースを (ブロッキング) 生成する関数を作成/チェリーピックしました。

同様に、Chan をシンクに変換する関数。

次に、mergeSources は簡単です。2 つのスレッドをフォークして (これは本当にやりたくないのですが、一体何なのか)、それらの新しいアイテムを 1 つのリストに入れることができ、そのリストからソースを生成します。

これらの関数をタイプチェックすることには成功しましたが、これらの関数をタイプチェックに使用することには成功しませんでした。

とにかく、この方法には欠陥があると思います。多くの中間リストと変換があります。これでは、パフォーマンスが向上しません。ガイダンスを求めています。

PS。私が理解できることから、これはの複製ではありません。コンジットを複数の入力と融合します。私の状況では、両方のソースが同じ型を生成し、どちらのソースからPacketオブジェクトが生成されたかは気にしません。

PPS。サンプル コードでのレンズの使用 (したがって、知識が必要) についてお詫び申し上げます。

これは、睡眠中の床屋の問題に対する解決策として提示されています。（CGrandに起因しますが、参照はこちらで見つかりました）

dosyncのブロックが気になりますenter-the-shop。私の理解では、これはトランザクションであり、empty-seatsSTM により一貫性が保たれます。send-offしかし、トランザクションがリトライされると、複数回呼び出される可能性はありませんか? そうでない場合、その理由は何ですか? もしそうなら、どのように解決しますか?

アップデート

受け入れられた答えはまだ正しいですが、私が気づいたことの 1 つは、実行できる最適化があることsend-offです。トランザクション内で呼び出す理由はありません。次のように、トランザクションの戻り値を取得したら、後で送信できます。

興味深いことに、 Haskell の同等の作業中にこれを理解しました。これにより、STM 内と STM 外の「エージェント」に異なるタイプを使用することが強制されます。上記の元のソリューションは、両方がトランザクション内にあるか、トランザクション外にある必要があるため、コンパイルされません。(私の最初の反応は、トランザクション内に両方を入れることでしたが、これが必要ではなく、両方を抽出できることに気付くまで)。

変更されたトランザクションは、トランザクションをより速く閉じ、トランザクションから変数を削除し、読みやすいという点で優れていると思います (トランザクションが 2 回送信される可能性について考える必要さえありません。この質問全体は意味がありません) それでも、STM とエージェントがどのように相互作用するかについて知る必要がある他の人のために、とにかく質問を残しておきます.

STM トランザクションが失敗して再試行した場合、呼び出しwriteTChanが再実行されて 2 つの書き込みが発生するのでしょうか? それともトランザクションがコミットされた場合に STM が実際に書き込みを実行するだけでしょうか? つまり、寝ている床屋の問題に対するこの解決策は有効でしょうか? それとも、トランザクションenterShopが最初に失敗した場合、顧客は 2 つのヘアカットを受けるのでしょうか?

更新hairRequestChanとにかく、上記がトランザクションの一部である必要がない という事実の後まで、私は気づきませんでした。レギュラーを使用して、 のブロックの後のステートメントChanで実行できます。しかし、その改善を行うと、質問をする理由全体が破壊されるため、ここではそのままにしておきます。writeChanifatomicallyenterShop

STM (Software Transactional Memory) 関連のことは何も書いておらず、Web 上の情報を読んだだけです。したがって、これは単なる架空の例です

最大許容アイテムを含む FIFO バッファがあるとします。そのため、最大項目数に達するまで配列を埋め、それ以上項目がなくなったらシフトします。従来のアプローチでは、実際のシフトと追加だけでなく、最大値に達したかどうかをチェックする条件付き読み取りもロックします。そうしないと、2 つのスレッドがシミュレートして、残された唯一のアイテムがそれらに向けられたものであると判断できます。したがって、書き込みの競合とは直接関係のない一種の論理ロックがここにあります。

STM を使用すると、2 つのスレッドがアイテムが残っていると判断し、最後のアイテムを埋めようとすることができると思います。ただし、別のスレッドが同じメモリを変更したことを検出した後、1 つのスレッド (または両方) でロールバックが発生するため、正確性は維持されます。楽観的なシナリオでは、スレッドの 1 つが最終的に要素数を増やし、別のスレッドが最終的に別の分岐に移動する (FIFO シフト) と述べています。しかし、両方が最後のアイテムが残っていることに気づき、それを埋めようとすると、ここで無限ループの可能性も見えます。

では、STM 関連のソフトウェアを作成するときに「論理」ロックを追加する必要はありますか?

次の構造を持つ非常に単純なハッシュテーブルを考えてみましょう。

put、、 などの基本的な操作がgetありremoveます。を使用して並行してテストするためのいくつかのテストを作成しましたpcalls。最初に 1 つの " " で実行するテストを開発しthread(つまり、1 つの関数を使用して を呼び出すだけpcalls)、成功したため、問題はそこにはなく、removeスレッドセーフでない関数にあると想定する必要があります。

削除は次のように実装されます。

奇妙なことに、たった 1 つの要素のバケットが削除されないことさえあります。ベクトルの要素のみが参照であり、ベクトル全体ではないため、これは奇妙です。 質問: このコードがスレッドセーフでないのはなぜですか?

注:多くの人がこのアプリケーションの設計についてコメントしようとすることは承知していますが、これは私が興味を持っている種類の回答ではありません。純粋な機能コードを記述するよりも、clojure の STM を理解したいのです。