Sequence Locks[1]
05/16/2015Ever 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
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | 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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | 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.