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

5 月，2 周 Questions & Answers 6998

完整免责声明：这并不是真正的家庭作业，但我给它贴上了这样的标签，因为它主要是一种自学练习，而不是真正的“为了工作”

假设我想用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;
    }
}

我对这段代码的分析（可能是错误的）是，因为它使用了^{}，所以即使没有任何显式的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且tick换行时，对next()的两个调用将返回1, 1

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

Thread1调用next()
Thread2调用next()
Thread2完成tick.getAndIncrement()，返回x
Thread1完成tick.getAndIncrement()，返回y=x+1（mod M）

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

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

因此，问题是：

我的分析正确吗？如果没有，请指出任何错误
我上面的最后一句话是否使用了正确的术语？如果不是，正确的说法是什么
如果上述问题是真实的，那么您将如何解决
通过利用AtomicInteger的原子性，您能在不使用synchronized的情况下修复它吗
你会如何写它，使得tick本身是由模控制的范围，甚至从来没有机会包装Integer.MAX_VALUE？
- 如有必要，我们可以假设M至少是小于Integer.MAX_VALUE的顺序

附录

这里有一个无序“问题”的类比

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

现在，如果我们成功地更新了列表，添加了两个元素，但是second在first之前，也就是在末尾，那么这是“线程安全”吗

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

值得一提的是，这个无序方面的Collections.synchronizedList行为是什么

Tags:

共 (4) 个答案

# 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 楼答案
原子（据我所知）指的是从外部看不到中间状态的事实atomicInteger.incrementAndGet()是原子的，而return this.intField++;不是原子的，因为在前者中，您无法观察到整数已递增但尚未返回的状态

至于线程安全，Java并发实践的作者在他们的书中提供了一个定义：

A class is thread-safe if it behaves correctly when accessed from multiple threads, regardless of the scheduling or interleaving of the execution of those threads by the runtime environment, and with no additional synchronization or other coordination on the part of the calling code.

（我个人的意见如下）

Now, if we have the list updated succesfully with two elements added, but second comes before first, which is at the end, is that "thread safe"?

如果thread1在thread2之前输入互斥对象的条目集（对于Collections.synchronizedList（）列表本身），则可以保证更新后first位于列表中second的前面。这是因为synchronized关键字使用公平锁。谁坐在队伍前面谁就得先做事情。公平锁可能非常昂贵，而且java中也可能存在不公平锁（通过使用java.util.concurrent实用程序）。如果你这么做，那么就没有这样的保证

然而，java平台不是一个实时计算平台，因此您无法预测一段代码需要运行多长时间。这意味着，如果您希望first在second之前，您需要在java中明确地确保这一点。通过“控制通话时间”来确保这一点是不可能的

现在，什么是线程安全还是不安全？我认为这完全取决于需要做什么。如果您只需要避免列表被损坏，并且不管first是列表中的第一个还是second是列表中的第一个，应用程序才能正确运行，那么只要避免损坏就足以建立线程安全。如果没有，就不是

因此，我认为，如果没有我们试图实现的特定功能，就无法定义线程安全性

著名的String.hashCode()没有使用java中提供的任何特定“同步机制”，但它仍然是线程安全的，因为人们可以在自己的应用程序中安全地使用它。不用担心同步等问题

著名的弦乐。hashCode（）技巧：
```
int hash = 0;

int hashCode(){
    int hash = this.hash;
    if(hash==0){
        hash = this.hash = calcHash();
    }
    return hash;
 }
```
# 3 楼答案
我想说的是，除了包装外，这很好。当两个方法调用有效地同时进行时，您无法保证哪一个将首先发生

代码仍然是原子的，因为无论哪一个先发生，它们都不会相互干扰

基本上，如果您的代码试图依赖于同时调用的顺序，那么您已经有了竞争条件。即使在调用代码中，一个线程比另一个线程先到达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); }

基本上这是说，“我们需要通过减少一些模的倍数将值恢复到一个安全范围”（这样它就不会改变mod M的值）。它在一个紧密的循环中完成这项工作，基本上计算出新值应该是什么，但只有在没有其他东西改变值的情况下才进行更改

在病态条件下，如果有无限多线程试图增加值，则可能会导致问题，但我认为这实际上是可以的

# 4 楼答案

关于原子性问题：我认为计数器本身不可能提供行为来保证您所暗示的语义

我想我们有一根线在做一些工作

A - get some stuff (for example receive a message) B - prepare to call Counter C - Enter Counter <=== counter code is now in control D - Increment E - return from Counter <==== just about to leave counter's control F - application continues

您正在寻找的中介涉及在A建立的“有效负载”标识顺序

例如，两个线程各自读取一条消息—一个线程读取X，一个线程读取Y。您希望确保X获得第一个计数器增量，Y获得第二个计数器增量，即使两个线程同时运行，并且可以跨一个或多个CPU任意调度

因此，必须在所有步骤A-F中强制执行任何排序，并由计数器外部的某个并发countrol强制执行。例如：

pre-A - Get a lock on Counter (or other lock) A - get some stuff (for example receive a message) B - prepare to call Counter C - Enter Counter <=== counter code is now in control D - Increment E - return from Counter <==== just about to leave counter's control F - application continues post- F - release lock

现在我们有了一个以牺牲并行性为代价的保证；线程正在互相等待。当要求严格排序时，这确实会限制并发性；这是消息传递系统中的常见问题

关于清单问题。线程安全应该从接口保证的角度来看待。有一个绝对最低要求：列表必须具有弹性，以应对来自多个线程的同时访问。例如，我们可以想象一个不安全的列表可能会死锁或使列表链接错误，这样任何迭代都会永远循环。下一个要求是，我们应该指定两个线程同时访问时的行为。有很多案例，这里有一些

a). Two threads attempt to add b). One thread adds item with key "X", another attempts to delete the item with key "X" C). One thread is iterating while a second thread is adding

如果实现在每种情况下都有明确定义的行为，那么它是线程安全的。有趣的问题是什么行为是方便的

我们可以简单地在列表上同步，因此很容易给出a和b的良好行为。然而，这在并行性方面是有代价的。我认为这样做没有任何价值，因为您仍然需要在更高的级别上进行同步以获得有用的语义。所以我会有一个接口规范，上面写着“添加以任何顺序发生”

至于迭代——这是一个困难的问题，看看Java集合承诺了什么：不是很多

This article，其中讨论Java集合可能很有趣

Python中文网

有 Java 编程相关的问题?

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

附录

共 (4) 个答案

# 1 楼答案

# 2 楼答案

# 3 楼答案

# 4 楼答案