无锁守卫用于同步的获取/释放

Question

我有一个共享的临时文件资源，被分成4K（或类似值）的块。文件中的每个4K都由从零开始的索引表示。对于这个共享资源，我跟踪正在使用的4K块索引，并始终返回未使用的最低索引的4K块，如果所有块都在使用，则返回-1。

这个索引的ResourceSet类有一个公共的acquire和release方法，两者都使用同步锁，其持续时间大约像生成4个随机数一样长（在CPU方面昂贵）。

因此，如下所示的代码所示，我使用了AtomicInteger“计数信号量”来防止大量线程同时进入关键部分，在acquire（）上返回-1（当前不可用）如果有太多的线程。

目前，我在acquire中使用100的常量来紧密CAS循环尝试增加原子整数，并使用10的常量来允许进入关键部分的最大线程数，这足够长以创建争用。我的问题是，在具有几个线程尝试访问这些4K块的中等到高度加载的servlet引擎中，这些常量应该是什么？

public class ResourceSet {

    // ??? what should this be
    // maximum number of attempts to try to increment with CAS on acquire
    private static final int    CAS_MAX_ATTEMPTS = 50;

    // ??? what should this be
    // maximum number of threads contending for lock before returning -1 on acquire
    private static final int    CONTENTION_MAX = 10;

    private AtomicInteger        latch = new AtomicInteger(0);

    ... member variables to track free resources

    private boolean aquireLatchForAquire ()
    {
        for (int i = 0; i < CAS_MAX_ATTEMPTS; i++) {
            int val = latch.get();
            if (val == -1)
                throw new AssertionError("bug in ResourceSet");        // this means more threads than can exist on any system, so its a bug!
            if (!latch.compareAndSet(val, val+1))
                continue;
            if (val < 0 || val >= CONTENTION_MAX) {
                latch.decrementAndGet();
                // added to fix BUG that comment pointed out, thanks!
                return false;
            }
        }
        return false;
    }

    private void aquireLatchForRelease ()
    {
        do {
            int val = latch.get();
            if (val == -1)
                throw new AssertionError("bug in ResourceSet");    // this means more threads than can exist on any system, so its a bug!
            if (latch.compareAndSet(val, val+1))
                return;
        } while (true);
    }

    public ResourceSet (int totalResources)
    {
        ... initialize
    }

    public int acquire (ResourceTracker owned)
    {        
        if (!aquireLatchForAquire())
            return -1;

        try {
            synchronized (this) {
                ... algorithm to compute minimum free resoource or return -1 if all in use
                return resourceindex;
            }
        } finally {
            latch.decrementAndGet();
        }
    }

    public boolean release (ResourceIter iter)
    {
        aquireLatchForRelease();
        try {
            synchronized (this) {
                ... iterate and release all resources
            }
        } finally {
            latch.decrementAndGet();
        }
    }
}

- Andy Nuss

---

你有一些代码可以分享吗？ - Eran Medan

我刚刚添加了代码以展示我正在做什么。 - Andy Nuss

请写出简明扼要的内容。 - Bhavik Ambani

一旦达到contention_max，这段代码不是有bug了吗？因为该方法将返回false，然后永远不会调用decrement。 - benmmurphy

@benmmurphy -- 太棒了，你的建议让我在测试中避免了很多痛苦！ - Andy Nuss

为什么不使用AtomicInteger来管理对块文件索引的访问？ - Dimitri

Answer 1

编写一个好的、高效的自旋锁实际上是相当复杂的，需要对内存屏障有很好的理解。仅仅选择一个常量是不够的，也肯定不具备可移植性。Google的gperftools有一个示例，你可以参考一下，但可能比你需要的要复杂得多。

如果你真的想减少锁的争用，你可能需要考虑使用更细粒度和乐观的方案。一个简单的方法是将你的块分成n组，并为每个组关联一个锁（也称为分离）。这将有助于减少争用并增加吞吐量，但不会帮助减少延迟。你还可以为每个块关联一个AtomicBoolean，并使用CAS来获取它（在失败的情况下重试）。在处理无锁算法时要小心，因为它们往往很难正确实现。如果你做对了，它可以显著降低获取块的延迟。

请注意，在不知道你的块选择算法是什么样子之前，很难提出更细粒度的方法。我还假设你确实有性能问题（已经进行了剖析等）。

顺便提一下，你的自旋锁实现有缺陷。你不应该直接在CAS上自旋，因为这会导致内存屏障过多。如果存在大量争用（与 thundering-herd problem相关），这将非常慢。最好的方法是，在进行CAS之前先检查变量是否可用（简单的无屏障读取即可）。更好的方法是，不要让所有线程都在同一个值上自旋。这样可以避免相关的高速缓存行在核心之间来回反弹。

请注意，我不知道Java中原子操作所关联的内存屏障类型，因此我的建议可能不是最优或正确的。

最后， The Art Of Multiprocessor Programming是一本有趣的书，可以帮助你更好地了解我在这个答案中所说的一切废话。

- Ze Blob

---

你的回答让我想知道，如果我的CAS循环导致内存屏障成为性能问题，那么java.util.concurrent.Semaphore如何执行它们的自旋锁来进行decrementAndGet等操作。 - Andy Nuss

我检查了JDK源代码并发现getAndIncrement使用了一个CAS循环，就像我的一样，只是它永远不会结束。 - Andy Nuss

我想表达的是，AtomicInteger getAndIncrement() 方法使用了与我的代码相同的 CAS 循环，只不过它是无限循环。因此，如果我的 CAS 循环会导致内存屏障频繁触发，那么 AtomicInteger 的 CAS 循环在增量和减量时也会如此。 - Andy Nuss

Answer 2

我不确定在这种情况下是否有必要自己编写锁类。因为JDK提供了ReentrantLock，它在获取锁时也利用了CAS指令。与您个人编写的锁类相比，性能应该非常好。

- James Gan

---

一个ReentrantLock不能满足这个问题。有10个许可的Semaphore可以模拟我的代码，但我无法控制CAS循环。Semaphore类的CAS循环会一直循环，直到获取锁为止。 - Andy Nuss

是的，ReentrantLock 不会起作用。对于我的误解感到抱歉。另一方面，如果许可证已经用完，Semaphore 调用 LockSupport.park(this) 来挂起当前线程。在我看来，这是正确的行为，因为它可以节省 CPU 从忙碌的重试中获取许可证。 - James Gan

Answer 3

如果您希望您的线程在没有可用资源时停止并等待，您可以使用Semaphore的tryAcquire方法。

我个人会将您的synchronized关键字替换为ReentrantLock并在其上使用tryLock()方法。如果您希望让您的线程等待一段时间，可以在相同的类上使用tryLock(timeout)。应该通过性能测试来确定选择哪一个以及timeout的值。

对我而言，似乎创建显式的门是不必要的。我并不是说它从不有帮助，但我认为它更可能会损害性能，并且它是增加的复杂性。因此，除非您在此处遇到性能问题（基于您进行的测试）并且发现这种门控有所帮助，否则建议使用最简单的实现。

- Enno Shioji

---

我检查了JDK Semaphore.tryAcquire(long timeout, TimeUnit)的代码，并在无法立即获取锁时，在其最紧密的循环中调用了 System.nanoTime()。我在我的系统上对System.nanoTime()进行了分析，它花费了半微秒的时间，而我试图用CAS保护的临界区比System.nanoTime!快大约10倍。因此，我认为Semaphore和ReentrantLock的开销太大了。 - Andy Nuss

@AndyNuss：实际上，当你无法成功进行CAS时，将CPU让给其他线程通常是有意义的。另一方面，如果你的临界区非常快，那么使用阻塞模式可能是错误的。为什么不直接使用synchronized，让线程等待获取他们想要的东西呢？ - Enno Shioji