java - 区间锁实现

Question

我正在寻找间隔锁的实现。给定一个区间 (x, y) , 如果没有其他人正在获取包含点 p 的任何间隔，则线程可以获取锁其中 x <= p <= y .

我目前的想法是维护现有授予间隔的数组 (x1, y1, x2, y2, ..., xn, yn)其中 x1 < y1 < x2 < y2 < ... < xn < yn并检查是否 (x, y)与这些间隔中的任何一个重叠。

搜索需要O(logn)让我快乐的时间。但是，当搜索返回存在一些重叠时，lock功能需要以某种方式有效地重试，直到它可以在其他人释放他们的间隔锁时获得锁。忙等待或 sleep 似乎不是一个好主意。

有没有办法有效地实现重试？

Answer 1

正如@c0der 所建议的那样，我已经实现了一个简单地跟踪锁定间隔的实现。

我的代码暗示了一个 Range 类......

• 是不可变的
• 有下限和上限(扩展到无界范围应该不会太难)
• 正确实现 equals() 和 hashCode()

RangeLock 类目前只实现了阻塞锁方法。解锁是通过返回的 Unlocker 实例完成的。这是为了避免线程没有获得锁，能够解锁给定的 Range。

public class RangeLock<T extends Comparable<? super T>> {

    private final SortedSet<Range<T>> locked = new TreeSet<>(Comparator.comparing(Range::lower));
    private final Object lock = new Object();

    public Unlocker lock(Range<T> range) throws InterruptedException {
        synchronized (lock) {
            while (!available(range)) {
                lock.wait();
            }
            locked.add(range);
            return () -> {
                synchronized (lock) {
                    locked.remove(range);
                    lock.notifyAll();
                }
            };
        }
    }

    private boolean available(Range<T> range) {
        SortedSet<Range<T>> tailSet = locked.tailSet(range);
        SortedSet<Range<T>> headSet = locked.headSet(range);
        return (tailSet.isEmpty() || !tailSet.first().overlaps(range)) && (headSet.isEmpty() || !headSet.last().overlaps(range));
    }

    public interface Unlocker {
        void unlock();
    }
}