CODEWITHSUNDEEP
javamultithreadingobjectarraylist
Ship.Asriadie
Ship.Asriadie

Reputation: 1

ArrayList<object> manipulation using Thread in Java

i was trying to solve a problem regarding list.add and list.remove with combination in using Thread in java. Lets assume we play with Stack

this is my Stack definition class..

import java.util.ArrayList;

public class Stack {

    private int size;
    private int maxSize;

    private final ArrayList<Object> list;

    public Stack(int size) {
        this.size = 0;
        this.maxSize = size;
        this.list = new ArrayList<Object>(size);
    }

    public boolean push(Object o) {
        if (size >= maxSize) {
            return false;
        }

        this.list.add(0, o);
        this.size++;
        return true;
    }

    public Object pop() {
        Object o;
        if (this.size == 0) {
            return null;
        }

        o = this.list.remove(0);
        this.size--;
        return o;
    }

    public int size() {
        return this.size;
    }
}

And here is how we using the stack in thread in Java

final Stack stack = new Stack(4);
for(int i = 0; i < 10000; i++) {
    final String data = "hello " + i;
    final int x = i;
    new Thread(new Runnable() {
        public void run() {
            if(x % 2 == 0) {
                System.out.println(stack.push(data));
            } else {
                System.out.println(stack.pop());
            }
        }
    }).start();
}

So basically we just create 10000 thread to manipulate Stack object. stack.push resulted True (if stack not yet full) or false (if stack already full) stack.pop resulted null if stack is empty

And the question is : Whats wrong with Stack implementation above and how to fix it?

My analysis so far is how thread running in java. Thread run in parallel instead sequentially. I tried to execute the program and sometimes exception IndexOutOfBounds pops out. If my analysis is true (or close), is there a way to evade the exception? Maybe include some checking method in Stack class?

If my analysis is false, so what's wrong with the implementation above? and how to fix it?

Upvotes: 0

Views: 903

Answers (2)

ka4eli
ka4eli

Reputation: 5424

Whats wrong with Stack implementation above

Your implementation is good when only one thread can access stack object. But if at least 2 threads can perform pop and push operations on the same stack - data races can occur. The main description of java multithreading is described in JSR-133.

Imagine situation with this code from pop method:

if (this.size == 0) {
    return null;
}
o = this.list.remove(0);
  1. First thread executes if condition, size is 1.

  2. Second thread executes the same if condition - the size is still 1.

  3. First thread tries to remove element with index 0 from list - success, size becomes 0.

  4. Second thread tries to remove element with index 0 from list when the size is 0 - exception is thrown.

You need to be sure that some events happen before others. One of the way is to synchronize your pop and push methods. This can be done easily by adding synchronized keyword before method return type.

public synchronized boolean push(Object o) {...}

public synchronized Object pop() { ...}

Here both methods are synchronized on the same object - this. So when one thread acquires this lock by executing pop or push no other thread can enter the code block or method locked (synchronized) by the same this object. It's completely thread safe to use these methods.

If you use some synchronized collection instead of regular ArrayList you can still get into trouble because your logic depends on size variable and previous error scenario is still working. If you need concurrent Stack implementation you can use LinkedBlockingDeque class from java.util.concurrent package. It would also be much more efficient because the cost of adding an element to the beginning of ArrayList is very high. But if you want to imlement it by yourself you can just add synchronized modifiers to pop and push methods and change your list to LinkedList.

Upvotes: 4

Solomon Slow
Solomon Slow

Reputation: 27115

@ka4eli told you why your Stack class is not thread-safe, but this is wrong too:

if(x % 2 == 0) {
    System.out.println(stack.push(data));
} else {
    System.out.println(stack.pop());
}

Even if your stack is completely thread-safe, you're bound to get NullPointerExceptions in the else case.

Unsynchronized threads can run in any order. Just because your program starts thread 0 before it starts thread 1 does not mean that thread 1 won't try to pop a string off of the stack before thread 0 (or any other thread) has pushed something.

Upvotes: 1

Related Questions