Testing Multi Threaded Scala Code

 
Recently I did a (somewhat brute force) port of MultithreadedTC. All of this work stems directly from it, and I deserve basically no credit. However, I've done a bunch of interesting work around it, and I wanted to talk about it a bit. First I want to mention a few important points.

1. We all know that the concurrency model used in Java has proven to be far too complex. About 5 people in the world can actually do it right. While this test api can be used to test code written in that style pretty easily, I'm not advocating writing anything in that style.
   
2. java.util.concurrent is still very useful. This api can be used to test j.u.c, Scala libraries that wrap it, and Scala libraries that use it.
   
3. This code will be in an upcoming release of ScalaTest, and (pending discussions) could make its way into Specs as well.
   
4. In the very near future this library should be very useful for testing actor code as well. Discussions and experimental implementations are ongoing. Expect a post about that very soon. Additionally, any Actor testing api will most definitely make its way into ScalaTest.
   

Onward to an example! I'm going to dump it out, and explain after.

package scala.util.concurrent.locks


class PimpedReadWriteLockTest extends MultiThreadedSuite with 
  MustMatchers with MustBeSugar {
  
  val lock = new java.util.concurrent.locks.ReentrantReadWriteLock
  import Implicits.RichReentrantReadWriteLock

  thread("writer thread") {
    waitForTick(1)
    lock.write {tick mustBe 2}
  }

  thread("reader thread") { 
    lock.read { waitForTick(2) } }
  }

  5.threads("reader thread("+_+")") {
    lock.read { waitForTick(2) }
  }

  10 anonymousThreads {
    lock.read { waitForTick(2) }
  }
}

There's a huge amount of stuff going on here, and I'll do my best to explain it one line at a time. Also, for the purposes of understanding and clarity, I might intentionally leave out some details that would only confuse. Okay, go.

class PimpedReadWriteLockTest extends MultiThreadedSuite with 
  MustMatchers with MustBeSugar {

MultiThreadedSuite is a ScalaTest suite that contains all the goodies for multithreaded testing. Those goodies will be covered as we go. The matchers give me my must methods as seen in: tick mustBe 2.

  val lock = new java.util.concurrent.locks.ReentrantReadWriteLock
  import Implicits.RichReentrantReadWriteLock

Create a read/write lock, and then import the code to Pimp it. The rich version allows you to say lock.read{...}, and lock.write{...}. These do basically what you would imagine, but here's a shallow example for lock.read (its not exact, but you get the idea):

  readLock.lock()
  f()
  readLock.unlock()

Creating a test Thread

  thread("writer thread") {
    ...
  }

On this line, a Thread is created with the name "writer thread". The thread method also returns the Thread, so you could assign it to a val and use it later on like so: val writer = thread("writer thread"){ ... } When the thread is started, it will run the code in between the curly brackets. I'll explain that code now.

Wait For Tick

Internally, MultiThreadedSuite maintains a clock. The clocks time starts at 0 and only advances when the following conditions hold:

1. ALL test threads are blocked.
   
2. At least one of those threads is waiting for the clock to tick.
   

Why the last condition? If all threads are blocked, and no one is waiting for a clock tick, you have a deadlock!

waitForTick(n) blocks the current thread until time n is reached on the clock. If the current time on the clock is greater than n, then the thread does not block.

Revisiting the code:

  thread("writer thread") {
    waitForTick(1)
    lock.write {tick mustBe 2}
  }

The writer thread immediately blocks, waiting for tick 1. When time 1 is reached, the thread unblocks, and attempts to acquire the write lock. As we'll find out later shortly, it will be unable to do so just yet. That's the important part of this test.

Next:

  thread("reader thread") { 
    lock.read { waitForTick(2) } }
  }

Just as with the writer thread, this code creates a thread that will run during the test. When the thread runs it will acquire the read lock, and then wait for tick 2. This thread is guaranteed to get the read lock before the writer thread gets the write lock. How? Because the write thread immediately blocks waiting for tick 1. Recall that the clock doesn't tick until ALL threads are blocked. The reader thread doesn't block until it says waitForTick(2), at which point it already has the read lock. :)

Now, the curious reader might wonder, why waitForTick(2). Let me explain. The test notices that someone is waiting for a tick, and if all threads are blocked, it advances the clock. The thread waiting for a tick only unblocks if the current time is equal to the time its waiting for, otherwise it stays blocked. The test system sleeps for a little bit, wakes up, realizes that all threads are still blocked and someone is still waiting for a tick, and advances the clock again.

With that explained, you can see that waitForTick(2) is just shorthand for:

waitForTick(1)
waitForTick(2)

Breaking it up this way will help us analyze what is happening in the test, and I'll do that shortly. First though, lets take a look at the rest of the code.

Creating LOTS of threads

  5.threads("reader thread("+_+")") {
    lock.read { waitForTick(2) }
  }

This code simply creates 5 threads. They all happen to be reader threads, and they are given the names "reader thread(1)" ... "reader thread(5)". It's a convenience method for creating many threads that you want to do exactly the same thing.

  10 anonymousThreads {
    lock.read { waitForTick(2) }
  }

Creates 10 anonymous threads that also happen to be reader threads. They are actually given names, because all threads have names. The name is "Thread N", where N corresponds to the number of threads created so far. So these guys will actually get named something like Thread 7 ... Thread 16. I don't really recommend using anonymous threads, but the style is a little bit less verbose, so maybe someone will like it.

Now, these methods return List[Thread]. I've chosen to ignore the return value here, but I can imagine cases where its very useful to have. The code could easily be rewritten:

  val readers: List[Thread] = 5.threads("reader thread("+_+")") {
    lock.read { waitForTick(2) }
  }
  val namelessReaders: List[Thread] = 10 anonymousThreads {
    lock.read { waitForTick(2) }
  }

Step by Step

1. waitForTick(1) blocks the writer thread until tick 1 happens.
   
2. The reader threads all get the read lock.
   
3. waitForTick(1) blocks the reader thread until tick 1 happens. The writer thread is also waiting for tick 1. They will all get the read lock, and then all block waiting for tick 1. When they all get to that point, the clock is advanced, and the threads continue.
   
4. The write thread will wake up and try to grab the write lock, but it wont be able to, because the read lock is held 16 times over! It will block.
   
5. waitForTick(2) causes the reader threads to block waiting for tick 2. The clock can advance because all the reader threads are blocked waiting for tick 2, and the writer thread is blocked waiting for the write lock.
   
6. After tick 2, all the reader threads wake up. The writer thread is still blocked, waiting for the read lock.
   
7. The reader threads all give up the read lock in concert.
   
8. The writer thread finally gets the write lock. When it does, it makes sure that the current tick is 2. Indeed, it is.
   

Summary

This should be the foundation of some really interesting work to come. I'll keep everyone informed.