C/C ++を使用して、STM(ソフトウェアトランザクションメモリ)を読み取り、ロックします
質問
私は、C/C ++などの非管理言語との互換性を維持するために、ロックを利用し、ゴミコレクターの存在に依存しないアルゴリズムで、STM(ソフトウェアトランザクションメモリ)の実装についていくつかの調査を行ってきました。 HerlihyとShavitのSTMチャプターを読みました 「マルチプロセッサプログラミングの芸術」, 、彼を説明するいくつかのシャビットの論文を読んでください 「トランザクションロック」 と 「トランザクションロックII」 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
の Thread B
で検出されません Thread A
. 。それはクラッシュやセグメンテーションの欠陥の可能性を引き起こしませんか?もしそうなら、読み物のためにメモリの場所をロックせずにそれを避けることができます(教科書と論文の両方が意味するものの両方が不要です)?
正しい解決策はありません