最近、TVar
に関するいくつかの質問をしましたが、私はまだライブロックについて懸念しています。デッドロックやリソース枯渇のない並行した汎用データ構造
だから私はこのような構造を考えた:
- 各トランザクションは、(おそらく作成順に割り当てられた)一意のプライオリティを取得します。
- トランザクションは、アクセスするデータに対して読み取り/書き込みロックを取得しようとします。当然のことながら、同時読み取りは問題ありませんが、1つの書き込みロックは他のすべてのものを除外します(読み取りと書き込みの両方)。
- トランザクションAはトランザクションBよりも高い優先度を持ちます。Aがロックを保持している場合はBが待機しますが、Bがロックを保持し、Aがそれを望む場合、Bはロックから起動され、Aは取得し、
TVar
)。 Bは再試行のために現在の優先順位を保持します。 - ロックが解放され、待機中のトランザクションがある場合、最も優先度の高いトランザクションに進み、残りのトランザクションは待機し続けます。
このシステムでは、デッドロックを防ぎますが、飢餓を防ぐと考えています(TVar
とは異なります)。誰かがそのようなシステムを実装しているのかどうかは不思議に思っていました。
もちろん、このようなアプローチを簡単に拡張して、ユーザーが優先順位を指定できるようにすることができます。
優先度は(user_supplied_prio, auto_increment)
となり、user_supplied_prio
が優先されますが、優先度の高いタスクはFIFO順で解決されます。
コメント/ソリューション:
私はそれについて考えるときに実際に、私はすでに記述すると、単純にすべてのデータの周りに包まれた1 IORef
を使用して、とだけatomicModifyIORef
を使用することにより、Haskellで存在します。 atomicModifyIORef
は、トランザクションが確実に順番に適用されるようにします。しかしながら、これは、データ構造が連続的である(すなわち、効果的に1つのスレッドに限定される)が、怠惰のために実際には平行であることを意味すると考えることができる。
これを説明するには、高価な関数f
を考えてみましょう。これをData.Map
にキー "foo"のデータに適用します。
これは(foo -> x)
の代わりに(foo -> future(f x))
を置き換えたものです。このスレッドは実際には(f x)
の内容を解決し続けますが、その間に "bar"にgを適用できます。 gを "bar"に適用することは "foo"の結果を必要としないので、これを同時に処理することができます。
デッドロックがなく、飢えもなく、最終的にすべてのトランザクションが処理されます(受け取った順番で処理されます)。
私はHaskellに存在するそのようなシステムを知らない。ほとんどのユーザーにとってはあまりにも複雑すぎるように見えますが、実装するのはむしろ面倒です。特に、割り当てられたロックを無効にするには、ポーリング(やや面倒なコード)または非同期例外(他のワームの可能性があります)が必要です。私はあなたの実装にSTMを試して、それがどのように動作するかを見てみることをお勧めします。 STMアルゴリズムは、通常、それを交換する必要がある場合は時間がかかりません。 –
STMの観点から言えば、ランタイムに優先度機構を追加すると(日付に基づいて述べたものに似ています)、私が信じるライブロックの問題は解決します。ただし、スケジューラの選択肢が大幅に制限される可能性があります。これは、現在のSTMランタイムにこのようなメカニズムがない理由でもあります。 PS:質問が解決したかどうかをコミュニティに知らせるために、以前の質問に対する回答の一部を「受け入れられた回答」としたい場合があります。 – Peter
パフォーマンス要件は何ですか?グローバルチケットロック(http://en.wikipedia.org/wiki/Ticket_lock)などの十分に粗い手段で、または単一のスレッドによって連続して実行されるすべてのアクションをエンキューすることで、必要なものを得ることができます。洗練された同期方法は、より高いオーバーヘッドを持つ傾向があります。グローバル同期が特定のワークロードのボトルネックでない場合は、おそらく高速です。 – Heatsink