java - 等待/锁定/无阻塞和OOC方法示例

Question

我正在阅读akka documentation现在我正在讨论非阻塞保证部分。以下是这些概念的定义:

A method is wait-free if evey call is guaranteed to finish in a finite number of steps

Lock-freedom is a weaker property than wait-freedom. In the case of lock- free calls, infinitely often some method finishes in a finite number of steps.

Obstruction-freedom is the weakest non-blocking guarantee [...]. a method is called obstruction-free if there is a point in time after which it ecxecutes in isolation

Optimistic concurrency control (OOC) methods are usually obstruction-free. the OOC approach is that every participant tries to execute its operation on the shared object, but if a participant detects confilict from others it rolls back the modifications, and tries again according to some schedule.

因此，考虑以下方法:

public class MyClass{

    private final AtomicInteger ai = new AtomicInteger(0);

    public void method(){
        while(true){
            int current = ai.get();
            if(ai.compareAndSet(current, current + 1))
                 break;
        }
    }
}

我们可以将其归入什么类别？我认为这是OOC方法(显然根据定义)和无阻塞方法(显然根据定义)，但它不是无锁 em> 一。

但我不太确定，无锁的定义有点模糊，尤其是无限经常地某些方法在有限数量的步骤中完成 。它应该意味着什么？您不能给我一个无等待和无锁方法的示例吗？

Answer 1

无等待

您的方法不能归入此类别。这是因为当多个线程运行 method() 函数时，一个或多个线程可能会使其他线程需要更多步骤。该问题的原因是:

int current = ai.get();
// another thread can adjust the number between our statements!
if(ai.compareAndSet(current, current + 1)) // Returns true if the value of ai is still 'current'
    break;

A method is wait-free if every call is guaranteed to finish in a finite number of steps.

If a method is bounded wait-free then the number of steps has a finite upper bound.

给定无限线程，上限将达到无穷大。

无锁

根据http://www.cs.swan.ac.uk/~csdavec/HPC/11LockFreedom.pdf

• At least one thread must be able to make progress at any given time

• Eventually, all threads must make progress

• Given infinite time, infinitely many threads will progress

所以你必须保证至少有一个线程取得进展。情况就是这样，因为 CompareAndSet 仅在值仍然相同时才更新该值。结合这样一个事实，如果它没有改变，代码就会继续(中断)。

因此，至少有一个线程可以保证取得进展。

无障碍

请参阅上一节中提到的链接。它指出:

A single thread, with all other threads paused, may complete its work.

您的代码将属于这一类别，因为如果在这 2 个语句期间只有一个线程处于 Activity 状态，那么它肯定会结束。

乐观并发控制 (OCC)

OCC似乎是无阻塞的一个特殊的子案例。它确实属于这种情况，因为如果compareAndSet检测到更改，它会取消数字的更新。

您的问题是“无限频繁地某个方法在有限数量的步骤中完成”。意思是:

它本质上是指我在无锁部分引用的部分，因为每当至少有 1 个进程运行代码时，就有一个进程必须取得进展。

这意味着只要有足够的时间，所有进程(如果进程数量无限，则无限!)都会取得进展。

*结论*

它不属于免等待类别。

它确实分为无锁、无障碍和 OCC。