ツーロック同時キューアルゴリズムの問​​題

Question

だから私はMaged M.マイケルとマイケル・L.スコット記事Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms上で行っていた、と私は取得しない小さな問題があります：

キューが初期化された直後に起動される2つの同時スレッドがあるとします。スレッドの1つはenqueueを呼び出し、他のコールはdequeueを呼び出します。ダミーノードのnextフィールドに同時にアクセスすることを妨げる要因は何ですか？ dequeueスレッドがnextフィールドを読み取ることはできませんが、enqueueスレッドはスレッドに書き込みますか？彼らはどちらも異なるロックを使用するので、私はそれらの間で同期するものを理解していません..

ありがとう。

Answer 1

enqueue（）はテールのみを操作し、dequeue（）はヘッドを操作するため、同じロックを使用する必要はありません。 headとtailが同じノードを指しているときには特別なケースがあります。これは初期化時に作成された「ダミー」ノードです。 dequeue（）がそれを読み込もうとしている間、enqueue（）がそのノードの次のポインタに書き込んでいる可能性があります。

その並行読み書きに問題はありません。 enqueue（）は新しいノードを作成し、そのオブジェクトをtail-> nextに書き込む前に完全に初期化します。したがって、途中で初期化された状態で、この新しいノードを他のコードで見ることはできません。さらに、ポインタへの読み書きはアトミックなので、dequeue（）ではポインタの半分を取得することはできません。

だから、エンキュー（）およびデキュー（）は両方ともすぐに呼ばれているシナリオでは、二つの可能性があります。

• エンキューは、（）（デキュー前に次> tail-に書き込み）頭部から読み込みます>次へこの場合、dequeue（）はエンキューされたノードを表示し、それを返します。
• dequeue（）は、enqueue（）がtail-> nextに書き込む前にhead-> nextから読み取ります。この場合、dequeue（）はキューが空であるとみなし、falseを返します。