私は、STM（ソフトウェアトランザクショナルメモリ）の実装、特にロックを利用し、C /C++などの非管理言語との互換性を維持するためにガベージコレクターの存在に依存しないアルゴリズムについていくつかの調査を行ってきました。HerlihyとShavitの「TheArtofMultiprocessor Programming」のSTMの章を読んだほか、彼の「TransactionalLocking」と「TransactionalLockingII 」について説明しているShavitの論文をいくつか読みました。STMの実装。彼らの基本的なアプローチは、グローバルバージョンクロックとロックの値を格納するハッシュテーブルを利用して、メモリ位置が別のスレッドの書き込みによって影響を受けたかどうかを判断することです。アルゴリズムを理解しているように、書き込みトランザクションが実行されると、バージョンクロックが読み取られてスレッドローカルメモリに格納され、読み取りセットと書き込みセットもスレッドローカルメモリに作成されます。次に、次の手順が実行されます。
- 読み取られたアドレスの値は、読み取りセットに格納されます。これは、トランザクションが、読み取られている場所がロックされておらず、ローカルに保存されているバージョンクロック値以下であることを確認することを意味します。
- 書き込まれたアドレスの値は、それらの場所に書き込まれる値とともに、書き込みセットに格納されます。
- 書き込みトランザクション全体が完了すると（これには、複数の場所への読み取りと書き込みが含まれる場合があります）、トランザクションは、アドレスに対してハッシュされるハッシュテーブルのロックを使用して、書き込まれる各アドレスをロックしようとします。 ' 価値。
- すべての書き込みセットアドレスがロックされると、グローバルバージョンクロックがアトミックにインクリメントされ、新しいインクリメントされた値がローカルに保存されます。
- 書き込みトランザクションは、読み取りセットの値が新しいバージョン番号で更新されていないこと、または別のスレッドによってロックされていないことを確認するために再度チェックします。
- 書き込みトランザクションは、そのメモリ位置のバージョンスタンプを手順4で保存した新しい値で更新し、書き込みセットの値をメモリにコミットします。
- メモリ位置のロックが解除されます
上記のチェックステップのいずれかが失敗した場合（つまり、ステップ＃1、＃3、および＃5）、書き込みトランザクションは中止されます。
読み取りトランザクションのプロセスははるかに簡単です。Shavitの論文によると、私たちは単に
- グローバルバージョンクロック値を読み取り、ローカルに保存します
- メモリ位置に現在保存されているグローバルバージョンクロック値よりも大きいクロック値がないことを確認し、メモリ位置が現在ロックされていないことも確認します
- 読み取り操作を実行します
- 検証のためにステップ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。クラッシュやセグメンテーション違反が発生する可能性はありませんか？もしそうなら、読むためのメモリ位置もロックせずにそれをどのように回避できますか（教科書と論文の両方が示すものは不要です）？