Clever Geek Handbook

Parallel test queue using ConcurrentSkipListMap

I recently had to do one of these interview training exercises. Basically, I needed to implement a message queue class that:

  • supports items based on the priority field in the incoming message.
  • a message can be in one of three priority categories: high, medium, low, controlled through the message.priorityField message range.
  • has getSize and isEmpty methods.
  • has a place (message) method.
  • has a delete method.
  • has a getFront () method (which returns the highest priority message)

What I did at the end, without going into details, was to implement a MessageQueue class that internally uses ConcurrentSkipListMap (a parallel and ordered map) to store messages.

I also implemented a basic JUnit test case that tests basic business requirements.

Now, since its messaging queue and hence messages can arrive at the same time, of course I need to test the occult aspect of the implementation.

Now I'm getting to the heart of the matter.

I think the main JUnit test case is to test if the code works when one thread interacts with the implementation.

Then I implemented a parallel test case that should test the occult aspect of the implementation.

Now here's the question: What concurrent aspects should I test?

The only thing I can think of is having multiple producer threads that inject methods into the queue and multiple consumer threads that delete messages (via getFront ()). What is being tested here is that all messages sent to the queue will eventually exit.

But is that enough? what other concurrent aspects can be tested here?

It is also worth noting that I have already submitted a solution, so anything you suggested will not affect my chances of getting this job I applied for.

+3


source to share


1 answer


Thread safety testing is a pain as you are basically trying to prove your program is correct for every possible parallel execution. There are several ways to do this:



  • Formally prove the correctness of your program in JMM terms. This will require you to discuss each apparent "incident in front of you" error in your program and how consistency is maintained based on these edges. It is possible for something as basic as a queue, but it becomes very complex, the more features and edges. I would recommend that you go through this process anyway and document your intentions / assumptions when writing parallel code.

  • Build test cases that demonstrate the intended behavior of the above, using fading gates or other ways to suspend threads of execution at specific points in your program to cause conflict. This can turn your code into a terrible mess if it takes too long, but it can be a very useful technique.

  • Demonstrate statistical accuracy by executing code for a sufficient period of time. This is the principle behind the concurrency torture suite used to validate the correct JVM implementation against the JMM. This will require you to create legal / illegal expectations for the threads involved and run your program for a long enough time on a machine with a sufficient parallel thread. If you've never got yourself into an illegal state, your program is correct :). If you run it long enough without getting into an illegal state, then in all likelihood you are right.

+2


source






More articles:


All Articles