代码之家 › 专栏 › 技术社区 › polygenelubricants

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

thread-safety concurrency multithreading java

polygenelubricants · 技术社区 · 14 年前

这并不是一个真正的家庭作业,但我给它贴上了这样的标签,因为它主要是一个自学练习,而不是真正的“为了工作”。

假设我想用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() 可能返回错误的值取决于模 . 即:

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

也就是说,两个电话会回来的 1, 1 当模为3且绕过去。

这也可能是一个问题

螺纹1 电话
螺纹2 电话
螺纹2 tick.getAndIncrement() ,返回十
螺纹1 tick.getAndIncrement() y=x+1(M型)

这里,除了前面提到的包装问题, 十 y 这两个值返回的值是否正确调用,但根据如何指定计数器行为,可以认为它们是无序的。也就是说,我们现在有 (螺纹1,y) 和 (螺纹2,x) ,但也许真的应该指定 (螺纹1,x) 和 (螺纹2,y)

所以根据单词的定义, AtomicModularCounter 是 ,但实际上不是 原子的 .

我的分析正确吗?如果没有,请指出任何错误。
我上面的最后一句话用的是正确的术语吗?如果不是,正确的说法是什么?
如果上面提到的问题是真的,那么你会怎么解决呢?
你能不用电脑就修好吗 已同步 ?
打上钩 Integer.MAX\u值 ?
- Integer.MAX\u值

附录

这里有一个 List

螺纹1 add(first)
螺纹2 电话 add(second)

现在,如果我们成功地更新了列表,添加了两个元素,但是 second 在前面 first ,在结尾,是“线程安全”吗?

如果这是“线程安全”,那么它不是什么?也就是说,如果我们在上述场景中指定, 第一 第二 ,那个并发属性叫什么(我称之为“原子性”,但我不确定这是否是正确的术语)。

不管它值多少钱 Collections.synchronizedList 这方面的行为有问题吗?

4 回复 | 直到 14 年前

Joshua 14 年前

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

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

Jon Skeet 14 年前

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

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

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的值)。它是在一个紧密的循环中完成的,基本上是计算出新值应该是什么,但是只有在没有其他东西改变中间的值时才进行更改。

这可能会导致一个问题 病理的 在这种情况下,有无限多个线程试图增加值,但我认为这实际上是可以的。

djna 14 年前

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

  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

Enno Shioji 14 年前

原子的 atomicInteger.incrementAndGet() 是原子的,而 return this.intField++; 不是,从某种意义上说,在前者中,您无法观察到整数已递增但尚未返回的状态。

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

类的行为是线程安全的线程,而不考虑调度或交错执行运行时的那些线程同步或其他协调在调用代码部分。

现在,如果我们有名单已成功更新两个元素补充说,但是第二个在第一个之前, 最后是“线”吗 “安全”?

first 位于前面 second synchronized 关键字使用公平锁。谁坐在队伍前面,谁就得先做事。公平锁可能非常昂贵,而且java中也可能有不公平锁(通过使用java.util.concurrent实用程序)。如果你这么做,那就没有这样的保证了。

但是,java平台不是一个实时计算平台,因此您无法预测一段代码需要运行多长时间。也就是说,如果你想提前 第二

现在,什么是线程安全还是不安全?我认为这完全取决于需要做什么。如果你只需要避免列表被破坏 第一 是第一个还是第二个 第二 是列表中的第一个,这样应用程序才能正确运行,那么仅仅避免损坏就足以建立线程安全。如果没有,就不是。

因此,我认为如果没有我们正在努力实现的特定功能,就无法定义线程安全性。

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

著名的String.hashCode()技巧:

int hash = 0;

int hashCode(){
    int hash = this.hash;
    if(hash==0){
        hash = this.hash = calcHash();
    }
    return hash;
 }