在 Java 中编写线程安全的模块化计数器

concurrency multithreading java thread-safety

2022-09-03 02:28:46

完整的免责声明：这不是真正的家庭作业，但我将其标记为这样，因为它主要是一种自学练习，而不是实际的“工作”。

假设我想用Java编写一个简单的线程安全模块化计数器。也就是说，如果模数为3，则计数器应无限期循环。M0, 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

不幸的是，“算法”本身并不完全“有效”，因为当环绕时，可能会根据模返回错误的值。那是：tickInteger.MAX_VALUEnext()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 并环绕时，将返回两个调用 to。next()1, 1tick

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

线程 1 调用next()
线程 2 调用next()
线程 2 完成，返回 xtick.getAndIncrement()
线程 1 完成，返回 y = x+1 （mod M）tick.getAndIncrement()

在这里，除了前面提到的包装问题之外，x 和 y 确实是为这两个调用返回的两个正确值，但根据计数器行为的指定方式，可以认为它们是无序的。也就是说，我们现在有（Thread1，y）和（Thread2，x），但也许应该指定（Thread1，x）和（Thread2，y）是“正确”的行为。next()

因此，根据单词的某些定义，是线程安全的，但实际上不是原子的。AtomicModularCounter

所以问题是：

我的分析是否正确？如果没有，请指出任何错误。
我上面的最后一句话是否使用了正确的术语？如果不是，正确的说法是什么？
如果上面提到的问题是真实的，那么您将如何解决它？
你能在不使用的情况下修复它吗？的原子性？synchronizedAtomicInteger
你会怎么写它，以至于它本身是由模控制的，甚至从来没有机会包络？tickInteger.MAX_VALUE
- 我们可以假设至少比必要时小一个订单MInteger.MAX_VALUE

附录

这是无序“问题”的类比。List

线程 1 调用add(first)
线程 2 调用add(second)

现在，如果我们成功地更新了列表，添加了两个元素，但排在前面，即最后，那么“线程安全”吗？secondfirst

如果这是“线程安全”，那么它不是什么？也就是说，如果我们指定在上面的场景中，应该总是在前面，那么并发属性叫什么？（我称之为“原子性”，但我不确定这是否是正确的术语）。firstsecond

就其价值而言，这种无序方面的行为是什么？Collections.synchronizedList

答案 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;
    }
}

答案 2

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

代码仍然是原子的，因为无论哪个实际首先发生，它们都不能相互干扰。

基本上，如果你有代码试图依赖于同时调用的顺序，你已经有一个竞争条件。即使在调用代码中，一个线程先于另一个线程到达调用的开头，您也可以想象它在进入调用之前到达其时间片的末尾 - 允许第二个线程进入那里。next()next()

如果调用有任何其他副作用 - 例如，它打印出“从线程（线程id）开始”，然后返回下一个值，那么它就不是原子的;你会在行为上有明显的差异。事实上，我认为你很好。next()

关于包装需要考虑的一件事是：如果您使用:)AtomicLong

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

定义一些大数 M * 100000（或其他）。这应该选择足够大，不会被太频繁地击中（因为它会降低性能），但足够小，你可以期望下面的“修复”循环在太多的线程添加到刻度线导致它换行之前是有效的。
当您使用获取值时，请检查它是否大于此数字。如果是，请进入一个“还原循环”，如下所示：getAndIncrement()
```
long tmp;
while ((tmp = tick.get()) > SAFETY_VALUE))
{
    long newValue = tmp - SAFETY_VALUE;
    tick.compareAndSet(tmp, newValue);
}
```

基本上，这表示，“我们需要通过递减模量的一些倍数来使值回到安全范围内”（这样它就不会改变值mod M）。它在一个紧密的循环中执行此操作，基本上计算出新值应该是什么，但只有在两者之间没有其他更改值时才进行更改。

在病理条件下，它可能会导致问题，因为您有无限数量的线程试图增加值，但我认为这实际上是可以的。