stm - STM ソフトウェアを作成する場合、論理ロックはまだ必要ですか?

Question

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

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

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

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

Answer 1

論理ロックは必要ありません - 確かにこのシナリオでは必要ありません。

1 つのスロットがまだ空いていることに 2 つのスレッドが「気づき続ける」ことはできません。1 つのスレッドがロールバックされる唯一の方法は、別のスレッドが正常にコミットされた場合、つまり最後のスロットがいっぱいになった場合です。

ロックはコミット フェーズ中にのみ発生するため、デッドロックは決して発生しないことが保証されます。それまでに、何をロックするかが正確にわかり、一貫した順序でロックを取得できます。別のトランザクションが正常にコミットされた場合にのみ、1 つのトランザクションがロールバックできるため、ライブロックが発生しないことが保証されます。したがって、2 つのトランザクションが互いに永久にブロックされることはありません。

理論的に可能なのは飢餓です。特に不運なトランザクションの 1 つは、無限にロールバックされる可能性があります。これは、無数の競合するトランザクションが正常にコミットされている場合にのみ発生します。そのため、システムは全体的に進歩する必要がありますが、ローカルでは特定のトランザクションが停止する可能性があります。

実際には、これが発生する可能性が高い唯一の方法は、短いトランザクションの無限のストリームを実行していて、その後、完了できない非常に長いトランザクションを 1 つ開始した場合です。