标签: compare-and-swap

我正在阅读Book Java Concurrency in Practice.在第15章中,他们讨论的是非阻塞算法和比较交换(CAS)方法.

据说CAS比锁定方法表现更好.我想问那些已经使用过这两个概念的人,并希望听到你何时更喜欢这些概念中的哪一个？它真的快得多吗？

对我来说,锁的使用更清晰,更容易理解,甚至可能更好维护(如果我错了,请纠正我).我们是否应该专注于创建与CAS相关的并发代码而不是锁定以获得更好的性能提升或者可持续性更重要？

我知道在使用什么时可能没有严格的规定.但我只是想听听CAS新概念的一些看法和经验.

我最近使用std :: atomic三重缓冲区为C++ 11创建了一个端口,用作并发同步机制.这种线程同步方法背后的想法是,对于生产者 - 消费者情况,你有一个运行速度更快的生产者,消费者,三重缓冲可以带来一些好处,因为生产者线程不会因为必须等待而"减慢"速度对于消费者.在我的例子中,我有一个物理线程,在~120fps时更新,以及一个以~60fps运行的渲染线程.显然,我希望渲染线程始终能够获得最新状态,但我也知道我将从物理线程中跳过很多帧,因为速率不同.另一方面,我希望我的物理线程保持其不变的更新速率,而不受锁定我的数据的较慢渲染线程的限制.

最初的C代码是由remis-ideas制作的,完整的解释在他的博客中.我鼓励任何有兴趣阅读它的人进一步了解原始实现.

我的实现可以在这里找到.

基本思想是使一个具有3个位置(缓冲区)的数组和一个原子标志进行比较和交换,以定义在任何给定时间哪些数组元素对应于什么状态.这样,只有一个原子变量用于模拟数组的所有3个索引和三重缓冲背后的逻辑.缓冲区的3个位置被命名为Dirty,Clean和Snap.该生产商始终写入脏指数,以及可翻转作家交换肮脏与当前清洁指数.该消费者可以要求一个新的管理单元,其交换与清洁指数当前捕捉指数以获得最新的缓冲区.该消费者总是读取对齐位置的缓冲区.

该标志由8位无符号整数组成,这些位对应于:

(未使用)(新写入)(2x脏)(2x清洁)(2x快照)

newWrite extra bit标志由写入器设置并由读取器清除.读者可以使用它来检查自上次捕捉以来是否有任何写入,如果不是,则不会再次捕捉.可以使用简单的按位运算获得标志和索引.

现在好了代码:

template <typename T>
class TripleBuffer
{

public:

  TripleBuffer<T>();
  TripleBuffer<T>(const T& init);

  // non-copyable behavior
  TripleBuffer<T>(const TripleBuffer<T>&) = delete;
  TripleBuffer<T>& operator=(const TripleBuffer<T>&) = delete;

  T snap() const; // get the current snap to read
  void write(const T newT); // write a new value
  bool newSnap(); // swap to the latest value, if any
  void …

Java中比较和交换的语义是什么？也就是说,AtomicIntegerjust 的compare和swap方法是否保证在不同线程之间对原子整数实例的特定内存位置进行有序访问,或者它是否保证对内存中所有位置的有序访问,即它就像是一个volatile一样(记忆围栏).

来自文档:

• weakCompareAndSet原子地读取并有条件地写入变量但不创建任何发生前的排序,因此不提供关于除了目标之外的任何变量的先前或后续读取和写入的保证weakCompareAndSet.
• compareAndSet以及所有其他读取和更新操作,例如getAndIncrement读取和写入volatile变量的内存效应.

从API文档中compareAndSet可以看出,它就好像是一个易变的变量.但是,weakCompareAndSet应该只是改变其特定的内存位置.因此,如果该存储器位置是单个处理器的高速缓存所独有的,weakCompareAndSet则应该比常规处理器快得多compareAndSet.

我问这个是因为我通过运行threadnum不同的线程来对以下方法进行基准测试,threadnum从1到8 不等,并且totalwork=1e9(代码是用Scala编写的,这是一种静态编译的JVM语言,但它的含义和字节码转换都是同构的在这种情况下Java的代码 - 这个简短的代码片段应该是清楚的):

val atomic_cnt = new AtomicInteger(0)
val atomic_tlocal_cnt = new java.lang.ThreadLocal[AtomicInteger] {
  override def initialValue = new AtomicInteger(0)
}

def loop_atomic_tlocal_cas = {
  var i = 0
  val until = totalwork / threadnum
  val acnt = atomic_tlocal_cnt.get
  while (i < until) {
    i += 1
    acnt.compareAndSet(i - …

主要的原因使用原子能超过互斥,是互斥是昂贵的,但与默认的内存模型atomics是memory_order_seq_cst,这不仅是因为贵吗？

问题:并发使用锁的程序可以和并发无锁程序一样快吗？

如果是这样,除非我想memory_order_acq_rel用于原子,否则它可能不值得.

编辑:我可能会遗漏一些东西,但基于锁定不能比无锁更快,因为每个锁也必须是一个完整的内存屏障.但是,通过无锁,可以使用比内存障碍更少限制的技术.

那么回到我的问题,没有锁定比基于新的C++ 11标准的默认锁定更快memory_model？

"无锁定> =在性能测量时基于锁定"是真的吗？我们假设有2个硬件线程.

编辑2:我的问题不是关于进度保证,也许我正在使用"无锁"脱离上下文.

基本上当你有2个共享内存线程时,你需要的唯一保证就是如果一个线程正在编写然后另一个线程无法读写,我的假设是简单的原子compare_and_swap操作比锁定互斥锁要快得多.

因为如果一个线程甚至从未触及共享内存,您将无缘无故地反复锁定和解锁,但使用原子操作时,每次只使用1个CPU周期.

关于注释,当争用很少时,自旋锁与互斥锁是非常不同的.

我正在实现请求实例的FIFO队列(预先分配的请求对象以获得速度),并在add方法上使用"synchronized"关键字开始.该方法非常短(检查固定大小缓冲区中的空间,然后向数组添加值).使用visualVM看起来线程比我更喜欢阻塞("监视器"准确).因此,我将代码转换为使用AtomicInteger值,例如跟踪当前大小,然后在while循环中使用compareAndSet()(因为AtomicInteger在内部为incrementAndGet()等方法执行).代码现在看起来要长一点.

我想知道的是使用synchronized和更短代码的性能开销与没有synchronized关键字的更长代码相比(因此永远不应该阻塞锁).

这是使用synchronized关键字的旧get方法:

public synchronized Request get()
{
    if (head == tail)
    {
        return null;
    }
    Request r = requests[head];
    head = (head + 1) % requests.length;
    return r;
}

这是没有synchronized关键字的新get方法:

public Request get()
{
    while (true)
    {
        int current = size.get();
        if (current <= 0)
        {
            return null;
        }
        if (size.compareAndSet(current, current - 1))
        {
            break;
        }
    }

    while (true)
    {
        int current = head.get();
        int nextHead = (current + 1) % requests.length;
        if (head.compareAndSet(current, nextHead))
        {
            return requests[current]; …

有人可以解释一下atomicModifyIORef有效吗？特别是:

(1)是否等待锁定,或者乐观地尝试重试(如果存在争用TVar).
(2)为什么签名atomicModifyIORef不同于签名modifyIORef？特别是,这个额外的变量是什么b？

编辑:我想我已经找到了(2)的答案,因为这b是一个要提取的值(如果不需要,这可以是空的).在单线程程序中,知道该值是微不足道的,但在多线程程序中,人们可能想知道在应用函数时先前的值是什么.我假设这就是为什么modifyIORef没有这个额外的返回值(因为这样的modifyIORef返回值的使用可能应该使用atomicModifyIORef.我仍然对(1)的答案感兴趣.

我的问题很简单.为什么没有std::atomic<double> 完全实施？我知道它与互锁变量访问有关.但是我真的没有看到,为什么这不应该是双倍的.

它被指定可以使用任何普通的可复制类型.当然,双重是其中之一.所以基本操作应该没问题(设置,阅读等).但是,在整数上可能有一组额外的操作(fetch_add,++,+ =等).

双重与这些类型的差别很小.它是原生的,三维可复制的等等.为什么标准不包括这些类型的双重？

我已经阅读了一些帖子,说比较和交换保证原子性,但是我仍然无法得到它是怎么回事.这是比较和交换的通用伪代码:

int CAS(int *ptr,int oldvalue,int newvalue)
{
   int temp = *ptr;
   if(*ptr == oldvalue)
       *ptr = newvalue
   return temp;
}

这如何保证原子性？例如,如果我使用它来实现互斥锁,

void lock(int *mutex)
{  
    while(!CAS(mutex, 0 , 1));
}

这如何防止2个线程同时获取互斥锁？任何指针都会非常感激.

显然,可以使用比较和交换指令以原子方式递增两个整数.这个谈话声称存在这样的算法,但它没有详细说明它的样子.

如何才能做到这一点？

(注意,一个接一个地递增整数的明显解决方案不是原子的.另外,将多个整数填充到一个机器字中并不算数,因为它会限制可能的范围.)

从关于C++原子类型和操作的C++ 0x提议:

29.1顺序和一致性[atomics.order]

添加一个包含以下段落的新子句.

枚举memory_order指定详细的常规(非原子)内存同步顺序,如[由N2334或其采用的后继者添加的新部分]中定义的,并且可以提供操作排序.其列举的值及其含义如下.

• memory_order_relaxed

该操作不会命令内存.

• memory_order_release

对受影响的内存位置执行释放操作,从而使常规内存写入通过应用它的原子变量对其他线程可见.

• memory_order_acquire

对受影响的内存位置执行获取操作,从而在通过应用它的原子变量释放的其他线程中进行常规内存写入,对当前线程可见.

• memory_order_acq_rel

该操作具有获取和释放语义.

• memory_order_seq_cst

该操作既具有获取和释放语义,另外,具有顺序一致的操作顺序.

提案中较低:

bool A::compare_swap( C& expected, C desired,
        memory_order success, memory_order failure ) volatile

Run Code Online (Sandbox Code Playgroud)

可以指定CAS的内存顺序.

我的理解是" memory_order_acq_rel"只需要同步操作所需的那些内存位置,而其他内存位置可能保持不同步(它不会表现为内存栅栏).

现在,我的问题是 - 如果我选择" memory_order_acq_rel"并应用于compare_swap整数类型,例如整数,这通常如何转换为现代消费者处理器(如多核英特尔i7)上的机器代码？那么其他常用的架构(x64,SPARC,ppc,arm)呢？

特别是(假设一个具体的编译器,比如说gcc):

1. 如何将整数位置与上述操作进行比较和交换？
2. 这样的代码会产生什么指令序列？
3. i7上的操作是否无锁定？
4. 这样的操作是否会运行完整的缓存一致性协议,同步不同处理器内核的缓存,就好像它是i7上的内存栅栏一样？或者它只是同步此操作所需的内存位置？
5. 与之前的问题相关 - acq_rel在i7 上使用语义是否有任何性能优势？其他架构呢？

感谢所有的答案.