ArrayList

Question

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?

Your stack implementation is not thread safe. Thread safety is all about protecting mutable state so that objects undergo consistent, reliable state transitions when accessed concurrently. Unfortunately, your class is subject to race conditions which will leave your objects with an undefined or inconsistent state. Using locking to force mutual exclusion of threads is an easy (if not performant) way to ensure atomic state transitions. — scottb, Aug 04 '15 at 17:43

score 4 · Answer 1 · edited May 23 '17 at 10:27

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);

First thread executes if condition, size is 1.
Second thread executes the same if condition - the size is still 1.
First thread tries to remove element with index 0 from list - success, size becomes 0.
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.

I will copied what other user named erhun said in other question thread. "well, but what if you got two methods: addFinisher and delFinisher? Both methods are thread-safe but since both access the same ArrayList you would still get trouble". As you can see my stack also have 2 methods in it. Any suggestion about this? Big thanks — Ship.Asriadie, Aug 05 '15 at 01:32
Edit: also how about using syncronizedlist or lock in this situation? Thank you very much — Ship.Asriadie, Aug 05 '15 at 01:41

score 1 · Answer 2 · answered Aug 04 '15 at 19:15

1

@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.

answered Aug 04 '15 at 19:15

Solomon Slow

25,130
5
37
57

But those block accessing the same Stack object, right? So if thread 1 run the else block(pop), the thread will access the stack object and trying to use its resources, but since thread 0 using it with synchronized mode, so thread 1 have to wait until thread 0 finished its work, right? – Ship.Asriadie Aug 05 '15 at 03:17
@Ship.Asriadie, No, Look at the OP's implementation: `stack.pop()` returns `null` if the stack is empty. – Solomon Slow Aug 05 '15 at 12:34

2 Answers2