how to do Multi-threaded processing in sequence?

Question

Here it is the problem I am trying to solve but not sure how to do it: I have an array of objects (say size is 100) and each object has some id.

Class Employee{
   int EmployeeId;
}

There are 10 threads which will read data from this array and insert it into database.

How to make sure data is inserted into DB based on the sequence of EmployeeId in increasing sequence. For example:

If array has objects with EmployeeID 6, 8 and 4, then these objects should be inserted in DB in sequence of EmployeeID 4,6,and 8 in DB. How to write multi-threaded code for this?

UPDATE: Please ignore DB part, if it is confusing, My main intention is to process concurrently but in sequence.

What difference does it make to enter them in a specific order if the database isn't controlling the id generation? — Sotirios Delimanolis, Sep 06 '13 at 14:57
It's usually really hard (impossible ?) to know in advance the sequence in which the threads are going to be excecuted. So I gues you can not make sure your objects are added in sequence if they are added by different threads racing. But you can implement semaphores to lock a thread and wait for the others threads to add their Object in the DB. — Marc, Sep 06 '13 at 14:59
http://stackoverflow.com/questions/7811681/java-threads-waiting-value — Fernando, Sep 06 '13 at 15:17
If you want a defined sequence, just use one thread. Multi-threads are for concurrent, independent tasks. — Peter Lawrey, Sep 06 '13 at 16:13

score 5 · Answer 1 · edited May 23 '17 at 12:23

5

I think you're not understanding the use of threading here. Threading¹ is meant for parallel tasks where(except for a few barriers perhaps) ordering doesn't matter and your threads run in parallel. You want a simple loop or other sort of serial behavior here.

You could easily do this with one thread. You could take the safe path here. Threads do not guarantee anything regarding optimizations and ordering. If preprocessing is expensive, do it in a threaded manner, then ensure threads all finish with a CountdownLatch and then insert into the database.

¹Threading can lead to death, asphyxiation, chills, fever, drowning, infection, nausea, and the inability to control heavy machinery.

edited May 23 '17 at 12:23

Community

1
1

answered Sep 06 '13 at 14:55

nanofarad

40,330
4
86
117

If there's heavy processing per item and order is only important when the results are returned, parallelism still makes sense. In a case like this, something like a countdown latch could probably be (ab)used. – jpm Sep 06 '13 at 14:57
@jpm *ab*used. And it's still better to thread processing and then finish the serial parts serially. – nanofarad Sep 06 '13 at 14:59
@jpm You'll still be constrained by the speed of the database. – Sotirios Delimanolis Sep 06 '13 at 15:00
Right, it all depends on whether processing or IO is more expensive for this problem. (Hint: it's usually IO) – jpm Sep 06 '13 at 15:00
@hexafraction What if we ignore all implications and just want to process all these objects in multi-threading in sequence? – AKS Sep 06 '13 at 15:13
@AKS: Argh, these two terms, "multithreading" and "in sequence", just don't fit together very well. You can't control the order in which threads execute. Do you wan't to process them using "multithreading" and then add them to the DB "in sequence"? – tilpner Sep 06 '13 at 15:58
@AKS That's like saying "OK, so if we ignore the fact that cars don't float, would we be able to drive on water?" – nanofarad Sep 06 '13 at 16:34
@hexafraction I was asked this question in interview by an investment banking company , and that's why i am insisting on this part. – AKS Sep 06 '13 at 17:52
@AKS The real correct answer is to state that multithreading is not a viable idea for the aforementioned reasons. – nanofarad Sep 06 '13 at 17:53
@hexafraction I agree, but you are allowed to ask anything when you are interviewer, and that guy was putting this question like his company will not run if this problem is not solved ;) – AKS Sep 06 '13 at 18:35

Barranka · Answer 2 · 2014-03-14T17:29:50.053

If I understand correctly, you have some tasks that must be performed sequentially (I assume 10) for each entry of the array.

First, you need to organize this 10 tasks sequentially, in a class that implements Runnable:

public class ThreadedTask implements Runnable {
    private Employee employee;
    public ThreadedWork(Employee employee) {
        this.employee = employee;
    }
    public void executeTaskList(Employee employee) {
        task1(employee);
        task2(employee);
        // ...
        task10(employee);
    }
    public void run() {
        executeTaskList();
        notify();
    }
}

Then, you can implement one of this solutions:

Insert the Employee object in the array, create a ThreadedTask object and call its execution on a thread.
Insert all the Employee objects in the array, and then use a for loop to create a ThreadedTask object and call its execution on a thread.

I'll write here a simple proposal for option 2:

/*
 * I am assuming that there`s an array called empArray, which holds 100 employees.
 * It's up to you to decide how it is populated.
 */
public void processEmployees() {
    // ...
    for(Employee e : empArray) {
        (new Thread(new ThreadedTask(e))).start()
    }
    // ...
}

As you see, the logic is split in two: It's up to you to define the way empArray is populated, and how the ThreadedTask object is created and executed. But the ThreadedTask executes the task list sequentially for every Employee object.

Notice that there's no way to tell which Employee object is processed on any given moment. All the employees are processed concurrently, but the tasks for each employee are executed sequentially.

Hope this helps

You are right, I was also thinking of putting all objects in a PriorityBlockingQueue where priority will be EmployeeID, and then pass that queue to a task and start 10 threads and let the task get executed. But I was asked again that all threads will pick the task sequentially, but not sure it will finish sequentially or not. (I was asked this question in an interview) . As was not able to solve it , I was told to solve how to make sure different threads are not picking same record from the input. :( — AKS, Sep 06 '13 at 17:50
You have to isolate the tasks. In the solution I am proposing, each `Runnable` object is related to one (and only one) `Employee` object, so there's no chance for one thread to work with another `Employee`. — Barranka, Sep 06 '13 at 18:31
@Barranka - I think you've answered a question of mine here. Just to be sure, I need to perform heavy math on each element in a List of 45 elements using six threads but when completed, the List must be in the same order. Does your answer apply to my situation? Or is there a better way now with newer versions of Java? — Patricia, Dec 01 '15 at 00:22
@MissLucy Thank you for reading my post. I think it's better if you post your comment as a new question (if you think this post was useful, consider putting a link to it). Be sure to include some sample code to see what you're doing (remember to read ["Help Center: How to create a Minimal, Complete and Verifiable Example"](http://stackoverflow.com/help/mcve)) — Barranka, Dec 01 '15 at 00:26

how to do Multi-threaded processing in sequence?

2 Answers2