二维整数阵列的锁定

Question

我有以下类，我想制作set2Int-method螺纹安全。但是该方法上不应有锁定（增加同步）。如果如果条件为真，则阵列中的两个整数都应锁定（以避免僵局）。还应该可以同时调用该方法，这意味着整个数组上的锁定也不是所需的解决方案。

public class Container {
    private Integer[][] array;
    public Container(int xs, int ys){
       array = new Integer[ys][];
       for (int i = 0; i < xs; i++){
           array[i] = new Integer[xs];
       }   
    }
    public void set2Int(int a, int b){
        for(int i = 0; i < array.length - 1; i++){
            for(int j = 0; j < array[i].length - 1; j++){
                if(array[i][j] == 0 && array[i][j+1] == 0){
                    array[i][j] = a;
                    array[i][j+1] = b;
                    return;
                }   
                if(array[i][j] == 0 && array[i+1][j] == 0){
                    array[i][j] = a;
                    array[i+1][j] = b;
                    return;
                } 
            } 
        }   
    }
}

Answer 1

为每个整数使用锁可能会消耗一些内存。我将使用int[]阵列而不是整数，然后使用锁条。这意味着您可以保留较少数量的锁，并将每个数组单元分配给其中一个锁。

除此之外，我不会锁定用于读取的数组单元，而是使用volatile read。这是使用getOpaque，它不提供同步保证，但可以从内存中读取价值，而JIT不会将其优化。

可能有其他优化的位置。如果使用64位CPU，则可能需要使用64位CAS来设置array[i][j]和array[i][j + 1]，因为这些元素放置在同一64位单词中。

这是Java 9的可能实现。如果您使用Java 8或更低，则可以使用AtomicIntegerArray。

import java.lang.invoke.MethodHandles;
import java.lang.invoke.VarHandle;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class Container {
    private static final int LOCK_GRANULARITY = 128;
    private static final VarHandle AA = MethodHandles.arrayElementVarHandle(int[].class);
    private final int[][] array;
    private Lock[] locks = new Lock[LOCK_GRANULARITY];
    public Container(int xs, int ys){
        array = new int[ys][];
        for (int i = 0; i < ys; i++){
            array[i] = new int[xs];
        }
        locks = new Lock[LOCK_GRANULARITY];
        for(int i = 0; i < locks.length; i++) {
            locks[i] = new ReentrantLock(false);
        }
    }
    public void set2Int(int a, int b){
        for(int i = 0; i < array.length - 1; i++){
            int[] iArray = array[i];
            int[] iNextArray = array[i + 1];
            for(int j = 0; j < array[i].length - 1; j++){
                if((int)AA.getOpaque(iArray, j) == 0 && (int)AA.getOpaque(iArray, j + 1) == 0){
                    if(update(i, j, a, i, j + 1, b)) {
                        return;
                    }
                }
                if((int)AA.getOpaque(iArray, j) == 0 && (int)AA.getOpaque(iNextArray, j) == 0){
                    if(update(i, j, a, i, j + 1, b)) {
                        return;
                    }
                }
            }
        }
    }
    private boolean update(int i1, int j1, int v1, int i2, int j2, int v2) {
        lock(i1, j1);
        lock(i2, j2);
        try {
            if(array[i1][j1] == 0 && array[i2][j2] == 0) {
                array[i1][j1] = v1;
                array[i2][j2] = v2;
                return true;
            } else {
                return false;
            }
        } finally {
            unlock(i2, j2);
            unlock(i1, j1);
        }
    }
    private void lock(int i, int j) {
        locks[Math.abs(hash(i, j) % locks.length)].lock();
    }
    private void unlock(int i, int j) {
        locks[Math.abs(hash(i, j) % locks.length)].unlock();
    }
    private int hash(int i, int j) {
        //TODO: choose good hash!
        return 31 * (i + 31 * j);
    }
    public int[][] getArray() {
        return array;
    }
}

更新：

会同步（array [i] [j]）{同步（array [i] [j 1]）{ 同步（array [i 1] [j]}}是线程安全解决方案（插入 在第一次之前）？ 我相信那将是线程安全的。但是，阅读每个元素的锁定可能会很慢。

除此之外，Java对某些INT值使用相同的java.lang.Integer对象。这意味着，如果您有一个数组，并且每个元素都设置为1，那么每个元素都将是相同的对象！当您同步在同一对象上时，同步会很慢。

此代码打印相同的值，因为每个对象都是相同的。无论如何，您可能需要测试这两个实现并更快地查看什么。

    Integer[] array = new Integer[128];
    for(int i = 0; i < array.length; i++) {
        array[i] = 5;
    }
    for(int i = 0; i < array.length; i++) {
        System.out.println(System.identityHashCode(array[i]));
    }