遅延ロック時に特定のモニタを保持しながら、オブジェクトの揮発性のブール値フィールドを変更することは何ですか？

Question

boolean add（T item）、boolean remove（T item）、boolean contains（T item）のようなメソッドをサポートする遅延ロックリストを実装しました。

例えばaddメソッドは：

Nodeオブジェクトは、揮発性のブールフィールドを持つ

@Override 
public boolean add(T item) { 
    int key = item.hashCode(); 

    while(true){ 
     Node pred = head; 
     Node curr = pred.next; 

     while(curr.key < key) { pred = curr; curr = curr.next; } 

     pred.Lock.lock(); 
     curr.Lock.lock(); 

     try{ 
      if(!pred.marked && !curr.marked && pred.next == curr){ 
       if(curr.key == key){ return false; } 
       else{ Node insertMe = new Node(item); insertMe.next = curr; pred.next = insertMe; return true; } 
      } 
     } finally{ pred.Lock.unlock(); curr.Lock.unlock(); } 
    } 
} 

デフォルトでfalseに設定し、「マーク」。ノードのロックはリエントラントなものです。 trueとマークされたノードは、すでにremoveメソッドによって削除されているとみなされます。しかし、特定のオブジェクトのモニタが特定のスレッドによって保持されている場合、これはなぜ関連していますか？言い換えれば、スレッドがオブジェクトのロックを取得していて、そのノードが削除済みとしてマークされていることをいつでも知ることができますか？

編集： containsメソッドは明らかにロックされませんが、containsチェックを行うために削除されたノードをマークする目的はありますか？したがって、マークされたフィールドをvolatile宣言する必要がありますか？

は含まれています

@Override 
public boolean contains(T item) { 
    int key = item.hashCode(); 

    while(true){ 
     Node curr = head; 

     while(curr.key < key) { curr = curr.next; } 

     if(curr.key == key && !curr.marked) return true; 
     else return false; 
    } 
} 

削除：addメソッドのためのメソッドが含まれていないために、あなたの場合は

@Override 
public boolean remove(T item) { 
    int key = item.hashCode(); 

    while(true){ 
     Node pred = head; 
     Node curr = pred.next; 

     while(curr.key < key) { pred = curr; curr = curr.next; } 

     pred.Lock.lock(); 
     curr.Lock.lock(); 

     try{ 
      if(!pred.marked && !curr.marked && pred.next == curr){ 
       if(curr.key != key) { return false; } 
       else{ 
        curr.marked = true; 
        pred.next = curr.next; 
        return true; 
       } 
      } 
     } finally{ pred.Lock.unlock(); curr.Lock.unlock(); } 
    } 
} 

Answer 1

markedが必要です。私の推測では、追加機能のmarked -checkは絶対に何もしません。

markedフィールドは絶対に揮発性でなければなりません。なぜなら、JITはコードを再注文して利益を得ることができるからです。唯一の保証は、揮発性フィールドが操作される前のコードが、volatileフィールドが変更される前に完全に実行されていることです（前後関係）。

フィールドが揮発性でない場合、JITは 'contains'を呼び出すスレッドにmarkedのスレッドローカルコピーを作成し、その後そのローカルバージョンmarkedをチェックすることができます。おそらくその時点で時代遅れになっています。この場合、同時にcontainsとremoveを実行すると、競合状態が発生する可能性があります。

並行パッケージのコレクションは、これらの問題をはるかにエレガントな（そしてバグのない）ものとして解決するため、すべてのケースで好ましいと言わざるを得ない。標準ライブラリにすでに存在するクラスを複製する場合は、通常、それを悪化させます。