1

我正在编写的一个库有一个实现二维映射的类，并且还为高效阅读提供了行/列视图的较小映射。到目前为止，所有方法都已被覆盖，因此主地图中的任何更改都会反映在子地图中，反之亦然。问题在于并发操作。

理想情况下，从主映射中删除一个项目将同时从相应的行和列映射中删除该项目，但这当然是不可能的。例如在我的 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;
}

虽然同时读取地图是完全可以接受的，甚至并发修改也不是问题（除了需要删除和放置同步的行/列的创建/删除），但是修改的 4 个阶段（super.put ，行和列放置，以及单元格位置更新）需要是原子的，以确保无法读取不匹配的数据。

我有哪些选择？据我从搜索中发现，不可能在 Java 中创建原子的语句序列，除非我同步所有函数（这会阻止并发读取，并且我需要锁定多个项目）。我知道（但不是特别实践）基本信号量概念的原则，但没有看到任何简单的方法来制作没有大量复杂性的写锁定信号量，特别是如果我不想大量等待一个写作槽。我还有哪些其他选择？

注意：由于我参与的项目，我不能使用衍生语言，如 groovy，但只能使用标准 Java 1.6u24，没有 3rd 方库。

4

2 回答 2

1

您可以在调用相关方法时动态创建行/列视图。这样，您就可以摆脱导致问题的四向更新。

（您将以简单性换取效率降低，但如果您不在高性能环境中，这可能不是问题。即便如此，值得对解决方案进行基准测试，看看它是否真的是一个糟糕的举动）。

于 2012-10-11T10:07:07.690 回答
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 forConcurrentHashMap和 forLock

P.S.
You may notice, that CellCoords field hash has type int. To avoid growth of locks map size till 2^31, you have to limit range of hashes. For example: (coords.hash % 64) - allows only 64 concurrent threads to work with entire matrix.

P.P.S. Might be interesting article for you: http://www.ibm.com/developerworks/java/library/j-jtp08223/

于 2012-10-11T10:20:31.930 回答