将绑定添加到无界队列

Question

我有一个用 Java 编写的近似并发有界队列 - 它旨在模仿 LinkedBlockingQueue 的行为，除了 a.它不使用锁和 b。它仅部分遵守队列的大小不变性。

public class LockFreeBoundedQueue<T> {
    private final ConcurrentLinkedQueue<T> queue = new ConcurrentLinkedQueue<>();
    private final AtomicInteger size = new AtomicInteger(0);
    private final int max;

    public LockFreeBoundedQueue(int max) {
        this.max = max;
    }

    public T poll() {
        T t = queue.poll();
        if(t != null) {
            size.decrementAndGet();
        }
        return t;
    }

    public boolean offer(T t) {
        if(t == null) throw new NullPointerException();
        if(size.get() < max) {
            size.incrementAndGet();
            return queue.offer(t);
        }
        return false;
    }

    public int size() {
        return queue.size();
    }
}

如果队列使用锁来强制大小不变，那么模型检查将相对简单，因为队列只有三种状态：空（poll returns null），满（ offer returns false)，既不空也不满。但是，有可能有多个线程在 size == (max - 1) 时通过 size.get() < max 守卫，这将使队列处于 size > max 状态。我不熟悉如何指定或验证这种 "approximate invariant"。

直觉上，给定一个具有 N 个线程并可以同时调用 offer 的系统，我可以对队列进行建模，就好像它具有 max + N 的精确界限；但是，如果我能证明这个不变量成立，那么我就不需要问如何证明这个不变量成立了。

Answer 1

您不能以原定的原子方式使用 if (size.incrementAndGet() < max) { 吗？

        if (size.incrementAndGet() < max) {
            return queue.offer(t);
        } else {
            // Undo my excessive increment.
            size.decrementAndGet();
        }

当然这会强制执行您的不变性。

将绑定添加到无界队列

Adding a bound to an unbounded queue

java

multithreading

data-structures

concurrency

lock-free