Java: Thread synchronization in a Stack implementation

Question

I'm learning Threads in Java and I though of creating a simple stack to test Thread synchronization. Here is the stack class:

public class Stack {

    private int counter;
    private String[] storage;
    
    public Stack(final int number) {
        storage = new String[number];
        counter = 0;
    }
    
    public synchronized void push(final String msg) {
        if(counter == storage.length) {
            System.out.println("Counter full");
        } else {
            storage[counter++] = msg;
        }
    }
    
    public synchronized String pop() {
        if(isEmpty()) {
            System.out.println("There is nothing to pop");
            return null;
        } else {
            String lastElement = storage[--counter];
            storage[counter] = null;
            return lastElement;
        }
    }
    
    public boolean isEmpty() {
        return counter == 0 ? true : false;
    }
    
    public synchronized void printElements() {
        for(int i=0; i < storage.length; i++) {
            System.out.println(storage[i]);
        }
        System.out.println("Number of elements "+counter);
    }
}

And here is the main method:

public static void main(String[] args) {
        Stack s = new Stack(10);
        
        final Thread t1 =  new Thread(() -> {
            for(int i=0; i < 2; i++) {
                s.push("Hello "+i);
            }
            for(int i=0; i < 2; i++) {
                s.push("How are you? "+i);
            }
        });
        
        final Thread t2 = new Thread(() -> {
            for(int i=0; i < 2; i++) {
                s.push("Nice to meet you "+i);
            }
            s.pop();
        });
        
        t1.start();
        t2.start();

        try {
            t2.join();
            t1.join();
        } catch(InterruptedException e) {
            e.printStackTrace();
        }
        
        s.printElements();
    }

Using the synchronized word is basic way of making a method gets executed by one Thread at a time only. Most of the time, I receive the sequence

Hello 0
Hello 1
How are you? 0
How are you? 1
Nice to meet you 0
null
null
null
null
null
Number of elements 5

which is the desired result. However there are also some situations where different sequence is returned and this is where my question appeared. Using synchronized will guarantee that only one thread at a time came execute a method i.e. securing the critical section. But it doesn't mean that the sequence of operations, specified in the lambda expression for creating a Runnable, will be executed always in the same flow, or? (Sorry, if it's a dummy question)

rzwitserloot · Accepted Answer

Yes, why would it?

Threads run simultaneously, and they introduce a lot of what appears to be randomness (though it is certainly not the kind of randomness you should rely on! If you generate crypto with this as a source of randomness, it'll likely be trivial to compromise whatever you generated with it, for example!).

What your synchronized gates are giving you is two separate things:

JMM streamlining: It establishes Happens-Before/Happens-After (HBHA) relationships.
Gating: You guarantee that you don't run into any issues where e.g. 2 push ops happen simultaneously, and therefore, they both write to e.g. storage[5], and one arbitrary overwrites the other. Sometimes, counter goes up by 2, or only by one.

Each thread is free to make a local clone copy of any field in any object at any time and is free to write only to its local clone copy. But it doesn't have to - so you can't rely on it. If you write code that acts differently depending on whether the thread decided to make that copy, you've written a bug. The way to stop that from happening is to establish HBHA relationships. You can search the web for the full list, but synchronized is one easy way to establish them.

Hence, your code has a bug. Your isEmpty() method is not synchronized, and yet is accessing shared state (The counter field is accessed and changed by multiple threads - thus, there are really any number of counter copies floating around, and without HBHA you have no idea which stale copy you might be reading there).

Furthermore, once you talk about 'establishing an ordering' you're almost entirely lost as far as parallelising is concerned: The whole point is for things to occur simultaneously, and every time 2 threads have to coordinate, then most of the advantages of multithreading disappear.

Note that within a single thread, code runs sequentially (or at least, you cannot observe any effects that can only be explained by the code running in some other order or simultaneously, though the hotspot compiler and CPU will work together and re-order code and run them (near) parallel if sequential statements do not affect each other at all. You can't write code to show this off, though, that's the point - if you could observe it, the optimizers will realize this and won't apply it).

Starting a thread creates HBHA between the x.start() call and the first line of the thread, but that's where it ends. So, when you write:

x = "hello";
t1.start();
t2.start();

That guarantees that both threads will 'see' your write to the x field (HBHA established by starting a thread), but you have no guarantee that t2 will start running after t1 starts running. Maybe t2 starts earlier, the JVM is free to do so. Or not - up to the VM; if your code acts differently if t1 starts 'earlier' than t2*, then you wrote a bug.

*) This is really the wrong to think about it. They start simultaneously. But it's about what you observe: It is legal for the JVM according to the JVM Specification that you observe anything t2 is doing before you observe things t1 can be expected to do in the same amount of time. Whether t2 actually ran 'earlier' is more nebulous. Maybe not, but t2 didn't make local cached copies and t1 did, for example.

Java: Thread synchronization in a Stack implementation

Answers (2)

Related Questions