7

階層的に編成されたリソースへのアクセスを管理するために、一連の読み取り/書き込みロックを階層的に編成する効率的なシステムを探しています。サブツリーが書き込み用にロックされている場合、サブツリーが解放されるまで、サブツリー全体で他のロックを取得できないようにする必要があります。同様に、サブツリーの書き込みロックは、親のロックを防ぐ必要があります。

これが私が考えていたアイデアです：

  • ApacheCommonsTransactionを使用します。残念ながら、プロジェクトは2008年3月以降更新されておらず、非公式に終了しています。一部のAPIドキュメントは、今後のバージョン（1.3または2.0）に何らかの階層ロックが含まれることを示しているようですが、ソースが見つからず、SVNリポジトリにアクセスできなくなっているようです。

  • 一連のReentrantReadWriteLocksを使用します。これは、階層的に編成します。私は並行性の専門家ではないので、自分でそれを行うのは少し怖いです。予備的な考えでは、サブツリーをロックする前に、ReentrantReadWriteLocks自体を管理する構造全体に外部ロックを使用する必要があることを示しているようです。そのため、ロックを解放する場合でも、外部ロックを使用する必要があります。 …</p>

  • からのクラスを使用java.util.concurrentしjava.util.concurrent.atomicReentrantReadWriteLockて、一連のsで実行できるよりも効率的な方法で階層ロックを実装します。

私はその最後の道を進む準備ができていますが、この問題をよりよく解決する既存のライブラリが見つからないことに驚きました。それで：

  • 私はいくつかの明白な解決策を逃しましたか？
  • それとも、この問題を適切に解決するのは特に難しいですか？
4

2 に答える 2

4

サブツリーを書き込み用にロックすると、構造全体がロックされるとおっしゃっていますが、あなたの質問をよく理解したかどうかはわかりません。したがって、単純な解決策は、構造全体に対して1つのRWロックを設定することです。

ちなみに、java.util.concurrent.atomicRWロックのツリー以上の助けにはなりません。

兄弟を独立してロックできるようにしたい場合は、2番目の解決策（各ノードがその親への参照を持つロックのツリー）を使用できます。

ノードをロックすると、書き込みロックを使用してノードがロックされ、読み取りロックを使用してすべての親がロックされます。子がすでに読み取りロックを取得しているため、子をロックすると書き込みロックを取得できないため、子がロックされている間は親をロックできません。子のロックは、他のスレッドが親を書き込みロックしていない場合にのみ許可されます。

上記のロックは専用ロックです。 （読み取り/書き込みロックの別名は共有専用ロックです）

共有ロックを追加するには、各ノードに次のことを示すアトミック整数も必要です。正の場合、間接的な書き込みロックされた子の数。負の場合、ノードがリードロックされた回数。また、ノードとその親は、親で新しい書き込みロックが取得されないように、読み取りロックされます。

擬似コード：

Node {
    // fields
    parent: Node
    lock: RWLock
    count: AtomicInteger
}

public boolean trylocktree(node: Node, exclusive: boolean) {
    if (exclusive) {
        return trylocktree_ex(node, true);
    } else {
        return trylocktree_sh(node);
    }
}
private boolean switch_count(i: AtomicInteger, diff: int) {
    // adds diff to i if the sign of i is the same as the sign of diff
    while (true) {
        int v = i.get();
        if (diff > 0 ? v < 0 : v > 0)
            return false;
        if (i.compareAndSet(v, v + diff))
            return true;
    }
}
private boolean trylocktree_ex(node: Node, writing: boolean) {
    // check if a node is read-locked
    if (!switch_count(node.count, 1))
        return false;
    // lock using the lock type passed as an arg
    if (!node.lock(writing).trylock()) {
        node.count--;
        return false;
    }
    // read-lock every parent
    if (!trylocktree_ex(node.parent, false)) {
        node.count--
        node.lock(writing).unlock();
        return false;
    }
    return true;
}
private boolean trylocktree_sh(node: Node) {
    // mark as shared-locked subtree
    if (!switch_count(node.count, -1))
        return false;
    // get shared-lock on parents
    if (!readlock_recursively(node)) {
        node.count++;
        return false;
    }
    return true;
}
private boolean readlock_recursively(node: Node) {
    if (!node.lock(false).trylock())
        return false;
    if (!readlock_recursively(node.parent)) {
        node.lock(false).unlock();
        return false;
    }
    return true;
}

ロックを取得できなかった場合は、ロックしたもののロックを解除し、後で再試行します（これを実現するには、グローバル条件変数、タイムアウトなどを使用できます）。

編集：ツリーを読み取りロック/書き込みロックするためのコードを追加しました

于 2011-05-27T16:03:58.273 に答える
0

私はあなた自身の解決策を選び、Apache Apache CommonsTransactionAlgorithmによって与えられたアルゴリズムを出発点とします。ReentrantReadWriteLockを使用できますが、通常、このロックは1つのプロデューサーのパターンによく適合します。多くのリーダーの場合は、探しているものとは異なる場合があります。あなたのロックは、通常のリエントラントミューテックスロックに似ているようです。

于 2011-05-27T16:42:15.913 に答える