Take the 2-minute tour ×

I've got a computation (CTR encryption) that requires results in a precise order.

For this I created a multithreaded design that calculates said results, in this case the result is a ByteBuffer. The calculation itself of course runs asynchronous, so the results may become available at any time and in any order. The "user" is a single-threaded application that uses the results by calling a method, after which the ByteBuffers are returned to the pool of resources by said method - the management of resources is already handled (using a thread safe stack).

Now the question: I need something that aggregates the results and makes them available in the right order. If the next result is not available, the method that the user called should block until it is. Does anyone know a good strategy or class in java.util.concurrent that can return asynchronously calculated results in order?

The solution it must be thread safe. I would like to avoid third party libraries, Thread.sleep() / Thread.wait() and theading related keywords other than "synchronized". Futhermore, The tasks may be given to e.g. an Executor in the correct order if that is required. This is for research, so feel free to use Java 1.6 or even 1.7 constructs.

Note: I've tagged these quesions [jre] as I want to keep within the classes defined in the JRE and [encryption] as somebody may already have had to deal with it, but the question itself is purely about java & multi-threading.

share|improve this question
Why not make a ByteBuffer array and pass the Bytebuffer to threads? When all threads are done, just write the ByteBuffers in array order –  fge Dec 18 '11 at 18:23
I removed the 'encryption' tag since this has nothing to do with encryption. –  Mike Nakis Dec 18 '11 at 18:49
add comment

3 Answers

Use the executors framework:

ExecutorService executorService = Executors.newFixedThreadPool(5);
List<Future> futures = executorService.invokeAll(listOfCallables);
for (Future future : futures) {
   //do something with future.get();

The listOfCallables will be a List<Callable<ByteBuffer>> that you have constructed to operate on the data. For example:

list.add(new SubTaskCalculator(1, 20));
list.add(new SubTaskCalculator(21, 40));
list.add(new SubTaskCalculator(41, 60));

(arbitrary ranges of numbers, adjust that to your task at hand)

.get() blocks until the result is complete, but at the same time other tasks are also running, so when you reach them, their .get() will be ready.

share|improve this answer
I was afraid that would be one of the first answers (as it has been covered on StackOverflow before). Unfortunately, the ByteBuffers become available after use, and the next task should then be fired off when the other resources become available. In other words, I cannot fire all the tasks at the same time. –  owlstead Dec 18 '11 at 18:47
+1 for using Executors. @owlstead, I don't understand your reply. What does "become available after use" mean? You can limit the number of tasks in action at one time (in the example code it's set to 5), and there are CompletionServices to do fancy stuff as tasks are completed. –  user949300 Dec 18 '11 at 18:56
I didn't get it either. If your next task depends on the previous, do it synchronously - you don't have another option –  Bozho Dec 18 '11 at 19:04
@user949300: Currently looking into completion services. I mean that the task use resources (such as ByteBuffers and a Cipher) which are reused. Once ByteBuffers become available (and the maximum set of tasks are not running) they should be refilled. Once they are refilled, then that's a result. All buffers are then read by the user in order. –  owlstead Dec 18 '11 at 19:14
@owlstead Why reuse/pool the ByteBuffers? If the computation isn't complete, you have to store the intermediate results somewhere, so you aren't saving any memory and you are complicating the solution. And I hardly think they are a precious system resource like a DB Connection. If they are, please elaborate. –  user949300 Dec 18 '11 at 19:37
show 3 more comments

Returning results in the right order is trivial. As each result arrives, store it in an arraylist, and once you have ALL the results, just sort the arraylist. You could use a PriorityQueue to keep the results sorted at all times as they arrive, but there is no point in doing this, since you will not be making any use of the results before all of them have arrived anyway.

So, what you could do is this:

Declare a "WorkItem" class which contains one of your bytearrays and its ordinal number, so that they can be sorted by ordinal number.

In your work threads, do something like this:

...do work and produce a work_item...

synchronized( LockObject )
    ResultList.Add( work_item );

In your main thread, do something like this:

synchronized( LockObject )
    while( number_of_results != number_of_items )
...go ahead and use the results...
share|improve this answer
Thanks MikeNakis. The idea is however that I make the results available as soon as possible, otherwise the user would block while calculation is performed on results other than the one needed at that time. –  owlstead Dec 18 '11 at 18:49
OK, this was not specified in the question. So, are you saying that the caller will be working on the results in parallel to the code which produces the results, and you want it to work while the next result is in order, but wait if not yet? –  Mike Nakis Dec 18 '11 at 19:05
Exactly! You got it. –  owlstead Dec 18 '11 at 19:54
add comment

My new answer after gaining a better understanding of what you want to do:


Make use of a java.util.PriorityQueue which is kept sorted by ordinal number. Essentially, all we care is that the first item in the priority queue at any given time will be the next item to process.

Each work thread stores its result in the PriorityQueue and issues a NotifyAll on some locking object.

The main thread waits on the locking object, and then if there are items in the queue, and if the ordinal of the (peeked, not dequeued) first item in the queue is equal to the number of items processed so far, then it dequeues the item and processes it. If not, it keeps waiting. If all of the items have been produced and processed, it is done.

share|improve this answer
This sounds like a very promising answer, will investigate the use of a locking object and priority queue. –  owlstead Dec 18 '11 at 20:17
I've tried some code, but I keep running into race conditions on putting the element on the queue and the peeking/removal of the element, together with the locking object. –  owlstead Dec 18 '11 at 21:17
Multithreading is not easy. Note that PriorityQueue is not synchronized, so you need to provide your own synchronization. You need to be very careful with when you lock things, and when you access them. You need to check the condition before entering wait(), otherwise you may never be notified. Waking up from a wait() doesn't mean the condition you were waiting for has happened, so you generally need to wait in a loop until the condition actually holds. If you can't solve it, you might want to post your code so people can help you spot the problem. –  Mike Nakis Dec 18 '11 at 22:59
Something tells me I will have to look into Lock object and Conditions, but it's 1.25 AM here now, so I'll stall this until tomorrow evening after work. –  owlstead Dec 19 '11 at 0:26
Thanks for thinking with me, MikeNakis. After a while I had to rewrite the code. Yes, MT is hard, but I've got it working now using just three classes (BlockingQueue, FutureTask and Callable) and possibly a AtomicReference to an enum for state handling - the manager thread has got to quit sometime... –  owlstead Dec 20 '11 at 18:32
show 2 more comments

Your Answer


