我正在寻找间隔锁定的实现。给定一个间隔(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();
}
}