2

Say I have a LinkedList filled objects and each objects stores relevant information that I need. I have threads accessing this list's first element to retrieve the information and do some operations on it, at the end of the operation I want that first element removed from the list. How do I make sure that remove() is only called once for each element? So that each threads can access the same next element on the list?

public class Test {
    private static LinkedList<foo> list;

    public static void main(String args[]) {
        list = new LinkedList<>();
        list.add(foo1);
        list.add(foo2);
        list.add(foo3);
        for(int i = 0; i < 5; i++) {
            new Thread(run()).start();
        }
    }

    private static Runnable run() {
        while(true) {
            while(SomeCondition) {
                //Do work.
            }
            list.remove();
        }
    }
}

I've tried creating a lock for the remove methods but this caused significant lag between each element for all the thread. Is it a good idea to just have a

LinkedList<LinkedList<food>> mainList;

so that each thread will have its own list to work off of? Then each thread can just do this to access the their element:

mainList.get(i).element();
mainList.get(i).remove();

EDIT: I failed to mentioned that main() has it's own thread where it continuously adds more elements into the list. The main purpose is that this is a server where it constantly receives requests, the requests are being placed in the list as a "queue". then the other threads spun off main() performs the operations. The request's message contains a field that will let me know which thread will perform what operation.

EDIT 2: I may have been too vague on the requirement to get a proper answer, sorry! This is a server that constantly receives requests from one client, The the list is being constantly populated with requests, the most important field for this purpose is the requested time:

for(int i = 0; i < 5; i++) {
    new Thread(run(i)).start();
}

private static Runnable run(int streamNumber) {
    while(true) {
        while(SomeCondition) {
            //Do work.
        }
        list.remove();
    }
}

So then the streamNumber dictates the following: 1. What IP address I am broadcasting to. 2. Using the requested time and streamNumber, which pointer to a payload I need to use(from a file).

Finally, each thread will send the payload out. So each thread needs the same information, but will respond differently. Once it sends the payload, it will grab the next requested time and do everything all over again.

Hydron
  • 75
  • 5
  • Have you considered giving each thread its own (shallow) copy of the list? – John Bollinger Jun 27 '18 at 18:39
  • Or if the threads did not exchange data via the objects drawn from the list, then you could even make that a *deep* copy. – John Bollinger Jun 27 '18 at 18:40
  • Can you elaborate? my next train of thought is creating the list filled with lists, then each thread can work on its own copy of the list – Hydron Jun 27 '18 at 18:41
  • Are you asking now how to *represent* the list copies? The first thing I'd do here is stop relying on class variables. It makes sense to me to make each thread's list an instance variable of a separate `Runnable` by which the thread's work is defined. Your code is broken in this general area, but you might, for instance, pass list copies to the method or constructor by which you obtain the `Runnable`s. – John Bollinger Jun 27 '18 at 18:46
  • Sorry about that! I guess I should've included the fact that the list is being constantly added, so making a deep copy is not efficient. – Hydron Jun 27 '18 at 18:50
  • Please clarify: are all the threads working on the same object at once, or does each get its own object from the list to work on? – John Bollinger Jun 27 '18 at 18:56
  • If each request is marked in a way that determines to which thread it should go, then I *absolutely* would assign a separate data structure to each thread for exchanging these objects. But whether you do that or use a shared data structure, this is a producer / consumer problem, and you'll find a lot of information under that name. – John Bollinger Jun 27 '18 at 19:01
  • Thank you! I just didn't know if giving each thread its own data structure is the best way of doing it. – Hydron Jun 27 '18 at 19:17
  • How about this, you allocate N threads. N-1 will be used to process messages, each with their own queue/linked list. And one thread will be used to read from the original linked list, distribute the head element to the other N-1 threads and remove the head from the original linked list? Like N-1 workers and 1 manager. – rtybase Jun 27 '18 at 19:27
  • How about this, Instead of making a list of `Foo` objects, where you want to do five things to each member, why not use a _thread pool_, and push five _tasks_ onto its queue for each `Foo` object? – Solomon Slow Jun 27 '18 at 20:12
  • I appreciate the quick accept ;-) – GhostCat Jun 28 '18 at 15:25

2 Answers2

1

First of all, when multiple threads are accessing the list for write operations, then a LinkedList is simply a bad choice. You could start here to find other implementations of the List interfaces that better suit such needs.

And as you commented yourself: another option is to slice your data into separate buckets and handing each thread a distinct bucket. Which solution is giving you better results depends on your exact requirements. Creating buckets has upfront cost, whereas thread safe queues cost you each time you add/remove elements.

Another approach:

  • go with one list, but don't have 5 threads walking the list
  • instead, your sequentially iterate the list, and then, for each loop iteration, you take a list entry and then you push 5 task objects into some ExecutorService instance.

The service is instantiated before, and you can base it on a ThreadPool, or whatever else you want (even a single thread executor, which is great for unit-testing). That adds some overhead, as you have to create these task objects, but it makes everything else much simpler.

GhostCat
  • 137,827
  • 25
  • 176
  • 248
0

The solution that I adopted was to create a:

ExecutorService threadPool = Executors.newFixedThreadPool(5);
while(true) {
    Request msg = new Request();
    //Set data into msg via DataInputStream
    for(int i = 0; i < 5; i++) {
        threadPool.execute(stream(i, msg));
    }
}

private Runnable stream(int streamNumber, Request msg) {
    //Do some work.
}

Instead of having 5 threads using 1 list and running into complications, I am just pushing 5 tasks into the pool. the streamNumber and message(flags and etc) will dictate what happens to the task for that given requested time. Thanks for everyone's input!

Hydron
  • 75
  • 5