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

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

搜索需要O(logn)时间,这让我很高兴。但是,当搜索返回存在某些重叠时,lock函数需要以某种方式有效地重试,直到当其他人释放其间隔锁时它可以获取该锁。忙于等待或 sleep 似乎不是一个好主意。

有没有办法有效地执行重试?

最佳答案

正如@ 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();
        }
    }
    

    10-07 19:31
    查看更多