java - Java 中用于匹配数据的原子 block

Question

我正在编写的库有一个实现二维 map 的类，并且还为行/列 View 提供了更小的 map ，以实现高效阅读。到目前为止，所有方法都已被重写，以便主 map 中的任何更改都会反射(reflect)在子 map 中，反之亦然。问题出在并发操作上。

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

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

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

注意:由于我正在进行的项目，我无法使用衍生语言，例如 groovy，而只能使用标准 Java 1.6u24，没有第三方库。

Answer 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;
    }
}

因此，您可以同步特定单元格上的读/写方法，而矩阵的其他部分将可供其他线程访问。

查看 javadoc 中的 ConcurrentHashMap和 Lock

附注
您可能会注意到，CellCoords 字段hash 的类型为int。为了避免锁映射大小增长到 2^31，您必须限制哈希范围。例如:(coords.hash % 64) - 仅允许 64 个并发线程处理整个矩阵。

P.P.S。您可能会感兴趣的文章:http://www.ibm.com/developerworks/java/library/j-jtp08223/