0

synchronized私はスレッド、ロックなどについて学んでいます。したがって、キーワードやそれ以外のクラス (アトミック変数なし) は使用thread-safeしたくありません。semaphoreReentrantLock

のサイズで順序LinkedList<T>を同期させたいと思います（これは、関数と関数を持っていると仮定します）。すべてのリストをロックせずに、関数によって2つを置き換えることができるようにしたい.Node<T>TTimplementsinterfacesizeincrementlockunlockNodesT.getSize()

たとえば、スレッドが 1 つしかない場合、関数は次のような「古典的な」置換関数になります。

public void IncrementAndcheckReplace(Node<T> node)
{
    node.getData().incrementSize();
    Node nextNode = node.getNext();
    if(nextNode == null)
        return;
    while(node.getData().getSize() > nextNode.getData().getSize())
     {
        node.getPrev().setNext(nextNode);
        nextNode.setPrev(node.getPrev());
        Node nextnext = nextNode.getNext();
        nextNode.setNext(node);
        node.setPrev(nextNode);
        node.setNext(nextnext);
        nextnext.setPrev(node);

        nextNode = node.getNext();
        if(nextNode == null)
            break; 
    }

}

同期の問題に取り掛かりましょう。

lock私は自分のためにを作成するためにそのようなことをしようと考えましたNodes:

public void IncrementAndcheckReplace(Node<T> node)
{
    node.lock(); //using fair ReentrantLock for specific node       
    node.getData().incrementSize();
    Node nextNode = node.getNext();
    if(nextNode == null)
    {
        node.unlock();
        return;
    }
    nextNode.lock();
    while(node.getData().getSize() > nextNode.getData().getSize())
     {
        Node prev = node.getPrev();
        if(prev != null)
        {
            prev.lock();
            prev.setNext(nextNode);
        }
        nextNode.setPrev(prev);
        Node nextnext = nextNode.getNext();
        if(nextnext != null)
        {
            nextnext.lock();
            nextnext.setPrev(node);
        }
        nextNode.setNext(node);
        node.setPrev(nextNode);
        node.setNext(nextnext);
        if(prev!=null)
            prev.unlock();
        if(nextnext!=null)
            nextnext.unlock();
        nextNode.unlock();

        nextNode = node.getNext();
        if(nextNode == null)
            break;
        nextNode.lock();
    }
    node.unlock();
}

問題は、これがスレッド セーフではないことであり、デッドロックが発生する可能性があります。たとえば、スレッド A が a で置換関数を使用しようとしてNode a, Node bいa.next == b and b.prev==aて、スレッド B が b で置換関数を使用しようとしている場合、両方がロックされ、どこにも到達しないと仮定します。

リスト全体thread safeなしで置換機能を作成するにはどうすればよいですか? とlockを避けたい。dead-lockstarvation

ありがとう！

4

1 に答える 1

1

最も一般的な答えは、同時実行性を最大限に高めることであり、並べ替えに関係する 4 つのノードすべてをロックすることです。それらがすべてロックされたら、順序が変更されていないことを確認します。変更されている場合は、おそらく中止して再試行します。次に、並べ替えを行い、逆の順序でロックを解放します。

注意が必要なのは、デッドロックを回避するために、固定された順序に従ってノードを順番にロックする必要があることです。残念ながら、リスト内の位置で並べ替えることはできません。その順序は変更される可能性があるためです。衝突が発生する可能性があるため、ノードの hashCode と identityHashCode の動作は保証されません。独自の順序付けを提供する必要があります。たとえば、構築時に各ノードに一意の永続 ID を付与し、それをロック順序に使用できます。

于 2016-05-27T03:08:39.147 に答える