使用信号量保护阵列

Question

假设有许多线程调用该方法m(int i)并将数组的值更改为位置i.以下代码是否正确,或者是否存在竞争条件？

public class A{
    private int []a =new int[N];
    private Semaphore[] s=new Semaphore[N];

    public A(){
        for(int i =0 ; i<N ; i++)
           s[i]=new Semaphore(1);
    }

    public void m(int i){
        s[i].acquire();
        a[i]++;
        s[i].release();
    }
}

Answer 1

该代码是正确的,我看不出有什么竞争条件虽然两者a并s应作出final.每次使用需要获取和释放的锁时,您还应该使用try/finally :

s[i].acquire();
try {
   a[i]++;
} finally {
   s[i].release();
}

但是,对于更新阵列,每个项目单独锁定的想法是非常不必要的.单个锁是恰当的,因为主要成本是内存更新和其他本机同步.这就是说,如果实际操作不是 a,int ++则保证使用Semaphore其他Lock对象.

但对于简单的操作,以下类似的东西很好:

// make sure it is final if you are synchronizing on it
private final int[] a = new int[N];
...

public void m(int i) {
   synchronized (a) {
      a[i]++:
   }
}

如果你真的担心阻塞,那么一个阵列AtomicInteger是另一种可能性,但即使这样也有点矫枉过正,除非探查者告诉你.

private final AtomicInteger[] a = new AtomicInteger[N];
...

public A(){
    for(int i = 0; i < N; i++)
       a[i] = new AtomicInteger(0);
}

public void m(int i) {
    a[i].incrementAndGet();
}

编辑:

我刚刚写了一个快速的愚蠢测试程序,它比较了一个synchronized锁,一个synchronized锁AtomicInteger数组,一个数组和Semaphore数组.结果如下:

• synchronized在int[]10617ms
• synchronized在一个Object[]1827毫秒的阵列上
• AtomicInteger 阵列1414ms
• Semaphore 阵列3211ms

但是,最重要的是这有10个线程,每个线程执行1000万次迭代.当然它更快但除非您真正进行了数百万次迭代,否则您的应用程序中不会看到任何明显的性能提升.这是"过早优化"的定义.您将为代码复杂性付出代价,增加错误的可能性,增加调试时间,增加维护成本等.引用Knuth:

我们应该忘记小的效率,大约97%的时间说:过早的优化是所有邪恶的根源.

现在,正如OP在评论中所暗示的那样,这i++不是他/她正在保护的真实操作.如果增量耗费更多(即阻塞增加),则需要锁定数组.