Hari Seshadri

Sequence Locks^[1]

05/16/2015

Ever been in a situation where you'd give anything just to enforce that threads within the same process would execute through a block of code in a deterministic and configurable ordering? Neither have I, but this post discusses how I'd structure a concurrency mechanism to make that possible.

For a little inspiration, this problem presents itself when you're dealing with many snippets of information (each with a "sequence" number) which need to be interpreted in a specific ordering to tell a coherent story, but are provided to you asynchronously and possibly not in that sequenced ordering. Let's say you are writing a video game client and you receive UDP packets tagged with sequence number and an action, such as

#493: Mike moves from (10,10) -> (10,11)
#495: Cannonball goes through (10,11)
#494: Mike moves from (10,11) -> (10,12)
In this case a sequence lock could save Mike's virtual life! In a more generic case with say four threads, here's a diagram explaining how I'd want the sequence lock to work (pardon art skills as always):

A little explanation on the colored lines:

They key point here being that Thread #1 went through its entire critical section before Thread #2 even entered, and Thread #2 went through its entirely, etc. Also note that no context switch was required for Thread #4's call to sequence_lock(4) as Thread #3 had already unlocked. My task here is implement the functions sequence_lock and sequence_unlock.

In other words, the following should print count from 1 to 300 in order

public class ShouldPrint1To300InOrder {

    public static void main(String[] args) {

        final SequenceLock sequenceLock = new SequenceLock(1l);

        for(long i = 1; i <= 300; i++) {
            final long j = i;
            Thread toRun = new Thread(){
                @Override
                public void run() {
                    try {
                        Thread.sleep((long) (Math.random() * 1000));
                    } catch(InterruptedException ie) {}
                    sequenceLock.lock(j);
                    System.out.print(j + " ");
                    System.out.flush();
                    sequenceLock.unlock(j);
                }
            };
            toRun.start();
        }
    }
}

Here's what I came up with for an implementation of SequenceLock:

import com.google.common.collect.Maps;
import java.util.Map;
/***
 * Concurrency variable which can serialize the flow of threads based
 * on a self-provided sequence number
 */
public class SequenceLock {
    //This sequence variable keeps track of who is currently allowed to enter.
    private volatile Long sequence;
    private Map<Long, Thread> sequenceToThreadWaiting;

    public SequenceLock(Long startingSequence) {
        sequence = startingSequence;
        sequenceToThreadWaiting = Maps.newConcurrentMap();
    }

    public void lock(Long seq) {
        synchronized (this) {
            if(seq.equals(sequence)) {
                return;
            } else {
                sequenceToThreadWaiting.put(seq, Thread.currentThread());
            }
            do {
                try {
                    this.wait();
                } catch (InterruptedException e) {
                }
            } while(!seq.equals(sequence));
        }
    }

    public void unlock(Long seq) {
        synchronized (this) {
            if(!seq.equals(sequence)) {
                throw new IllegalStateException("Called unlock on sequence with " + seq + " but was last locked with " + sequence);
            }
            sequenceToThreadWaiting.remove(sequence);
            sequence++;
            if(sequenceToThreadWaiting.containsKey(sequence)) {
                sequenceToThreadWaiting.get(sequence).interrupt();
            }
        }
    }
}

A few notes on the above

I am not 100% sure this works - but it seems to pass my tests. If you see something wrong drop me a line!
One could accomplish this also invoking notifyAll on anybody on the queue for the lock (and not maintaining a map), but then you end up waking up many threads just to put them back to sleep.
If you use == on the Long objects instead of .equals, you end up with an interesting bug where the lock only works for the first 127 sequence numbers...
If this was all there was to the SequenceLock class, then you don't need a re-entrant Map, as it is only accessed within synchronized blocks.

[1] Two disclaimers about the name. First, the devised construct is simple enough that it likely has been discussed before (maybe under a different name), but I wasn't able to find anything like this with a quick google search. Second, I just came up with the term "sequence lock," and the proposed device has nothing to do with Wikipedia's SeqLock.

Beyond first glance

Sequence Locks[1]

Sequence Locks^[1]