1

私が書いているライブラリには、2 次元マップを実装するクラスがあり、効率的な読み取りのために、行/列ビューの小さなマップも提供します。これまでのところ、すべてのメソッドがオーバーライドされているため、メイン マップの変更はサブ マップにミラーリングされ、その逆も同様です。問題は同時操作で発生します。

理想的には、マスター マップからアイテムを削除すると、それぞれの行マップと列マップからアイテムが同時に削除されますが、これはもちろん不可能です。たとえば、私のput関数では：

public synchronized Cell put(Duple<Integer, Integer> key, Cell arg1){
    //preprocessing, detecting the row/col, creating row/col if not present yet, etc.
    Cell outcell = super.put(key, arg1);
    rowArr.putPriv(key.getElem2(), arg1);
    colArr.putPriv(key.getElem1(), arg1);
    arg1.assignCell(this, key);
    return outCell;
}

マップの同時読み取りは完全に許容され、同時変更でさえ問題ではありませんが (同期するために remove と put が必要な行/列の作成/削除を除く)、4 段階の変更 (super.put 、行と列の書き込み、およびセル位置の更新) は、一致しないデータを読み取れないようにするためにアトミックである必要があります。

私のオプションは何ですか？私の検索からわかった限りでは、Java でステートメントのアトミック シーケンスを作成することは不可能であり、すべての関数を同期しない限り同期は機能しません (これにより同時読み取りが防止され、複数のロックが必要になります)。アイテム）。私は基本的なセマフォの概念の原則を知っています (ただし、特に実践されていません) が、非常に複雑なロックオンライト セマフォを作成する簡単な方法は見当たりません。書き込みスロット。どのような追加オプションがありますか?

注: 私が取り組んでいるプロジェクトのため、groovy などの派生言語を使用することはできませんが、サード パーティのライブラリがなければ、標準の Java 1.6u24 しか使用できません。

4

2 に答える 2

1

メソッド全体で同期しないことをお勧めしますput。ただし、特定のセルでのみ同期します。以下のコードでは、その方法を説明します。

class ConcurrMattr {

    private ConcurrentHashMap<Integer, Lock> locks = 
                    new ConcurrentHashMap<Integer, Lock>();

    public Cell put( CellCoords key, Cell arg1 ) {
        // get or create lock for specific cell (guarantee its uniqueness)
        Lock lock = this.locks.putIfAbsent( coords.hash % 64, new ReentrantLock() );
        // 64 threads may concurrently modify different cells of matrix

        try {
            // lock only specific cell
            lock.lock();

            // do all you need with cell

            return ...;

        } finally {
            // unlock cell
            lock.unlock();
        }
    }    
}


// Immutable class to represent cell coordinates
class CellCoords {    
    public final int x;
    public final int y;
    public final int hash;

    public CellCoords( int x, int y ) {
        this.x = x;
        this.y = y;
        this.hash = this.calcHash();
    }

    private int calcHash() {
        int result = 31 + this.x;
        return 31 * result + this.y;
    }
}

したがって、マトリックスの他の部分が他のスレッドにアクセスできるようにしread/writeながら、特定のセルでメソッドを同期することができます。

javadocを見てConcurrentHashMapくださいLock

PS
お気づきかもしれませんが、そのCellCoordsフィールドのhashタイプはintです。ロックマップのサイズが2^31まで大きくならないようにするには、ハッシュの範囲を制限する必要があります。次に例を示します(coords.hash % 64)。-マトリックス全体で動作できるのは64個の同時スレッドのみです。

PPSはあなたにとって興味深い記事かもしれません：http ：//www.ibm.com/developerworks/java/library/j-jtp08223/

于 2012-10-11T10:20:31.930 に答える
1

関連するメソッドが呼び出されたときに、行/列ビューを動的に作成できます。そうすれば、問題の原因となっている 4 方向の更新から解放されます。

(シンプルさと引き換えに効率が低下しますが、パフォーマンスの高い環境でなければ問題にはならないかもしれません。その場合でも、ソリューションのベンチマークを行って、それが本当に悪い動きであるかどうかを確認する価値があります。 ）。

于 2012-10-11T10:07:07.690 に答える