用Java编写线程安全模块计数器

Question

完全免责声明:这不是一个真正的功课,但我标记它是因为它主要是一个自学习练习而不是实际的"工作".

假设我想用Java编写一个简单的线程安全模块计数器.也就是说,如果模数M为3,那么计数器应该0, 1, 2, 0, 1, 2, … 无限循环.

这是一次尝试:

import java.util.concurrent.atomic.AtomicInteger;

public class AtomicModularCounter {
    private final AtomicInteger tick = new AtomicInteger();
    private final int M;

    public AtomicModularCounter(int M) {
        this.M = M;
    }
    public int next() {
        return modulo(tick.getAndIncrement(), M);
    }
    private final static int modulo(int v, int M) {
        return ((v % M) + M) % M;
    }
}

我对此代码的分析(可能有问题)是因为它使用AtomicInteger,即使没有任何显式synchronized方法/块,它也非常安全.

不幸的是,"算法"本身并不完全"工作",因为当tick环绕时Integer.MAX_VALUE,next()可能会返回错误的值,具体取决于模数M.那是:

System.out.println(Integer.MAX_VALUE + 1 == Integer.MIN_VALUE); // true
System.out.println(modulo(Integer.MAX_VALUE, 3)); // 1
System.out.println(modulo(Integer.MIN_VALUE, 3)); // 1

也就是说,当模数为3并且环绕时,两次调用next()将返回.1, 1tick

next()获取无序值也可能存在问题,例如:

1. Thread1调用next()
2. Thread2调用next()
3. Thread2完成tick.getAndIncrement(),返回x
4. Thread1完成tick.getAndIncrement(),返回y = x + 1(mod M)

在这里,除了前面提到的包装问题,x和y确实是这两个next()调用返回的两个正确值,但是根据指定计数器行为的方式,可以认为它们是乱序的.也就是说,我们现在有(Thread1,y)和(Thread2,x),但是可能真的应该指定(Thread1,x)和(Thread2,y)是"正确的"行为.

所以通过一些词的定义,AtomicModularCounter是线程安全的,但实际上不是原子的.

所以问题是:

• 我的分析是否正确？如果没有,请指出任何错误.
• 我上面的陈述是使用正确的术语吗？如果没有,那么正确的陈述是什么？
• 如果上面提到的问题是真的,那你将如何解决？
• 你可以synchronized通过利用原子性来解决它AtomicInteger吗？
• 你怎么写它tick本身是由模数控制的范围,甚至从来没有机会包裹Integer.MAX_VALUE？
  • 我们可以假设M至少比Integer.MAX_VALUE必要时小一个订单

---

附录

这是List无序"问题" 的类比.

• Thread1调用add(first)
• Thread2调用add(second)

现在,如果我们已经成功更新了列表并添加了两个元素,但是second之前first,最后是"线程安全"？

如果那是"线程安全的",那么它不是什么？也就是说,如果我们指定在上面的场景中,first应该总是在之前second,那个并发属性被称为什么？(我把它称为"原子性",但我不确定这是否是正确的术语).

对于它的价值,Collections.synchronizedList这个无序方面的行为是什么？

Answer 1

据我所知,你只需要一个getAndIncrement()方法的变体

public final int getAndIncrement(int modulo) {
    for (;;) {
        int current = atomicInteger.get();
        int next = (current + 1) % modulo;
        if (atomicInteger.compareAndSet(current, next))
            return current;
    }
}

Answer 2

我会说,除了包装,它没关系.当两个方法调用有效地同时进行时,您无法保证首先会发生哪种方法.

代码仍然是原子的,因为无论哪个实际发生,它们都不会相互干扰.

基本上,如果您的代码试图依赖于同时调用的顺序,那么您已经有了竞争条件.即使在调用代码中一个线程获取到开始next()前的其他呼叫,你能想象它的到来给其时间片结束它得到前进入的next()呼叫-允许第二个线程在那里得到的.

如果next()调用有任何其他副作用 - 例如它打印出"以线程(线程ID)开始" 然后返回下一个值,那么它将不是原子的; 你的行为会有明显的差异.事实上,我觉得你很好.

一件事想就包装:可以使计数器如果您使用的包装之前最后一个可怕的很多更长的AtomicLong:)

编辑:我刚刚想到了在所有现实场景中避免包装问题的简洁方法:

• 定义一些大数M*100000(或其他).这应该被选择为足够大以至于不会经常被击中(因为它会降低性能)但是足够小以至于你可以期望下面的"修复"循环在太多线程添加到勾号之前有效包裹.

• 当您获取值时getAndIncrement(),请检查它是否大于此数字.如果是,进入"减少循环",看起来像这样:

  long tmp;
  while ((tmp = tick.get()) > SAFETY_VALUE))
  {
      long newValue = tmp - SAFETY_VALUE;
      tick.compareAndSet(tmp, newValue);
  }
  

基本上这说,"我们需要通过递减模数的一些倍数将值恢复到安全范围内"(这样它不会改变模值M的值).它在紧密循环中执行此操作,基本上计算出新值应该是什么,但只有在没有其他任何改变它们之间的值时才进行更改.

它可能会导致病理状况出现问题,你有无数个线程试图增加值,但我认为这实际上是可以的.