Interval lock Implementation

Question

I am looking for an implementation of interval lock. Given an interval (x, y), a thread can acquire the lock if no-one else is acquiring any interval that contains point p where x <= p <= y.

My current idea is maintaining an array of existing granted intervals (x1, y1, x2, y2, ..., xn, yn) where x1 < y1 < x2 < y2 < ... < xn < yn and checks to see if (x, y) overlaps with any of those intervals.

The search takes O(logn) time which makes me happy. However, when the search returns that there is some overlaps, the lock function needs to somehow retry efficiently until it can acquire the lock when others release their interval locks. Busy-waiting or sleep seems not a good idea.

Is there a way to implement the retry efficiently?

Answer 1

As @c0der suggested I've made an implementation that simply tracks the locked intervals.

My code implies a Range class that ...

• is immutable
• has a lower and upper bound (extending to unbounded ranges shouldn't be too hard)
• properly implements equals() and hashCode()

The RangeLock class currently only implements a blocking lock method. Unlocking is done through a returned Unlocker instance. This is to avoid threads not having acquired the lock, being able to unlock a given 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();
    }
}

Answer 2

I think the question is essentially about an efficient way to have a thread wait and retry.
How about listening to changes in the

array of existing granted intervals

and retry only when it has changed ?
The following should not be considered a proper implementation (my experience with thread is very limited), but a demonstration of the proposed mechanism:

Ranges.java and Range.java

//represents all ranges
//see also: https://stackoverflow.com/a/7721388/3992939
public class Ranges {

    private List<Range> ranges = new ArrayList<>();
    private PropertyChangeSupport rangeChangedProperty = new PropertyChangeSupport(this);

    public Range getRange(int rangeStart, int rangeEnd) {

        if(contains(rangeStart) || contains(rangeEnd)) {
            return null;
        }
        Range range = new Range(rangeStart, rangeEnd);
        range.addListener( (observable, oldValue, newValue) -> {
                rangeChangedProperty.firePropertyChange("Range", "-" , "changed");
            }
        );
        ranges.add(range);
        return range;
    }

    private boolean contains(int number){
        for(Range range : ranges) {
            if(range.contains(number)) {return true;}
        }
        return false;
    }

    public boolean removeRange(Range range) {

        boolean isContains = ranges.remove(range);
        rangeChangedProperty.firePropertyChange("Range", "-" , "removed");
        return isContains;
    }

    /**
     * Listen to {@link #rangeChangedProperty}. Fires whenever a range changes
     * or removed.
     * <br/>A client and a listener and when it fires, notify all threads.
     */
    public void addChangeListener(PropertyChangeListener listener) {
        rangeChangedProperty.addPropertyChangeListener(listener);
    }

    //represents a single range
    //It is muttable 
    //can be implemented using ValueRange (https://stackoverflow.com/a/40716042/3992939)
    class Range{

        private SimpleIntegerProperty low = new SimpleIntegerProperty();
        private SimpleIntegerProperty high = new SimpleIntegerProperty();
        private SimpleObjectProperty<int[]> rangeProperty = new SimpleObjectProperty<>();

        private Range(int rangeStart, int rangeEnd){

            low.set(rangeStart) ; high.set(rangeEnd);
            updateRange();
            low.addListener((observable, oldValue, newValue) -> { updateRange(); });
            high.addListener((observable, oldValue, newValue) -> { updateRange(); });
        }

        /**
         * Listen to {@link #rangeProperty} that changes whenever the range changes
         */
        void addListener(ChangeListener<int[]> listener) {
            rangeProperty.addListener(listener);
        }

        private void updateRange() {rangeProperty.set(new int[] {low.get(), high.get()});}

        public int getRangeStart() { return low.get(); }

        public void setRangeStart(int rangeStart) { low.set(rangeStart);}

        public int getRangeEnd() {return high.get();}

        public void setRangeEnd(int rangeEnd) { high.set(rangeEnd);}

        public boolean contains(int number){
            int min = Math.min(low.get(), high.get());
            int max = Math.max(low.get(), high.get());
            return ((number >= min) && (number <= max));
        }
    }
}

GetRange.java

//used to simulate a thread trying to get a range 
public class GetRange implements Runnable{

    private Ranges ranges;
    private int low, high;
    private String id;

    GetRange(Ranges ranges, int low, int high, String id) {
        this.ranges = ranges;
        this.low = low; this.high = high; this.id = id;
    }

    @Override
    public void run() {
        synchronized (ranges) {
            while(ranges.getRange(low,high) == null) {
                System.out.println("Tread "+ id + " is waiting");
                try {
                    ranges.wait();
                } catch (InterruptedException ex) { ex.printStackTrace();}
            }
        }
        System.out.println("Tread "+ id + " got range. All done");
    }
}

Test is with :

//test
public static void main(String[] args) throws InterruptedException {
    Ranges ranges = new Ranges();
    ranges.addChangeListener( (evt) -> {
        synchronized (ranges) {
            ranges.notifyAll();
            System.out.println(evt.getPropertyName() + " "+ evt.getNewValue());
        }
    });

    Range range1 = ranges.getRange(10,15);
    Range range2 = ranges.getRange(20,25);

    new Thread(new GetRange(ranges, 10, 12, "A")).start();
    new Thread(new GetRange(ranges, 21, 28, "B")).start();
    new Thread(new GetRange(ranges, 10, 12, "C")).start();

    Thread.sleep(50);
    System.out.println("-- Changing end of range 1. Threads notifyied and keep waiting -----");
    range1.setRangeEnd(16);   //no thread effected
    Thread.sleep(50);
    System.out.println("-- Changing start of range 1. Threads notifyied and A or C get range -----");
    range1.setRangeStart(13); //effects thread A or C
    Thread.sleep(50);
    System.out.println("-- Removing range 2. Threads notifyied and B get range -----");
    ranges.removeRange(range2);//effects thread B
    Thread.sleep(50);
    System.exit(1);
}

Output:

Tread A is waiting
Tread C is waiting
Tread B is waiting
-- Changing end of range 1. Threads notifyied and keep waiting -----
Range changed
Tread B is waiting
Tread C is waiting
Tread A is waiting
-- Changing start of range 1. Threads notifyied and A or C get range -----
Range changed Tread A got range. All done
Thread C is waiting
Tread B is waiting
-- Removing range 2. Threads notifyied and B get range -----
Range removed
Tread B got range. All done
Tread C is waiting