[SOLVED] [Java] Threads and Locks (Synchronized) help understanding...

seishinryohosha · 2017-03-03 05:29:10

Good Day|Night

I'm a bit confused about a piece of code from a book.

Here's the code:

class Lock {
		private static boolean used = true;

		public synchronized void lock() {
				while (used)  {}
		}

		public synchronized void unlock() {
				used = false;
		}
}

class Worker extends Thread {
		public void run() {
				Lock l = new Lock();
				l.lock();
		}
}

public class LockTest {
		public static void main(String[] args) {
				new Worker().start();
				
				Lock l = new Lock();
				l.unlock();
		}
}

The book asks:

Does this program terminates?

To my knowledge, it should not terminate, but could be fixed with a volatile or AtomicBoolean.
The code uses an object lock on lock() and unlock() as

public synchronized void foo() {
    /* do stuff */
}

is the same as:

public void foo() {
    synchronized(this) {
        /* do stuff */
    }
}

so the change from ``used'' isn't guaranteed to be atomic.
Moreover ``main'' creates a new Lock, thus a new object, so ``synchronized'' does not lock.

But to my surprise it always terminated!
I tested it with:

for i in {1..500}; do
taskset 0x1 java LockTest
done

(Also tested without taskset)

I put a ``Thread.sleep(5)'' in the main, and it always got in an infinity loop.
(Lesser values didin't work)
A ``System.out.println("unlocking");'' got sometimes in an infinty loop.

Using a class-lock:

synchronized (Lock.class) {
    /* do stuff */
}

Nearly everytime got a dead-lock, except using ``taskset 0x1'', which always worked.

I used ``javap -c'' to see the Bytecode, but it didn't optimize anything.
(Maybe the JIT did?)

So my question is:
Am I missing something?
Why does it terminate?
Why does the Class-Lock version works with

taskset 0x1 java LockTest

but not without it?

Last edited by seishinryohosha (2017-03-07 05:20:50)

p0x8 · 2017-03-03 10:52:43

What I find surprising is the example that doesn't terminate (and indeed Thread.sleep() triggers that behavior).

It terminates because you're changing the value of Lock.used. You can even remove the synchronization directives and it will still work. As long as the interpreter behaves in a conservative manner both threads share the variable value.

Synchronize and volatile are about guarantees. Synchronize guarantees that a single thread at a time will execute a given code block. Volatile guarantees that a variable value will always be checked before being used. But the absence of volatile doesn't mean the value is never checked. And in this simple scenario it mostly works as expected.

Thread.sleep() seems to trigger some optimization that makes the looping thread never synchronize the value, so it apparently runs forever. This is actually a great example of why you should never make assumptions with multi-threaded code and always use guarantees when sharing state between threads.

ewaller · 2017-03-03 15:12:00

We used to have rules about homework in our code of conduct -- somewhere along the way that rule has gone missing. I any event, I ask, is this homework? If it is, fine; but please be honest about it. To those responding, if it is homework please do not provide the answer outright, but rather guide the OP in learning the answer. If it not homework, go for the direct approach.

seishinryohosha · 2017-03-03 21:34:28

No it's not homework.
I'm using the book to prepare for an exam, yes, but it's not part of the curriculum.

I understand why it (sometimes) terminates.
The locks, lock an the individual object.
Here the Lock-Object in the run-Method of the anonymous Object of Worker()
and the Lock-object in the main Method of LockTest.
As the locks never interact, as they lock different objects, it would be the same, as I never had
them in the first place.
The lock and unlock just use the static variable Lock.used (so not locked by the object-lock).
So the Lock.used is accessible in two Threads, here the Worker-Thread and the Main-Thread.
Everyone can change the variable through unlock() and unlock().
Lock.used could be kept in cache, as it's not marked volatile.
This explains, why it sometimes works and sometimes not.

My main question, which the book never asked, is:
Why it's so different, than using Thread.sleep(5) (Or bigger values) in main(String[] args).
Is it just, that in other cases main() managed to execute l.unlock() in it's Timeslice in time
and the Thread.sleep(5) hinders it, so Worker() gets a time-slice, as main got from state
``running'' into state ``sleep'' and after 5ms into state ``runnable''?
So Worker.lock() has time to actually execute and get into it's loop?
So maybe it holds the value of used as ``true'' in cache (Maybe the JIT optimzed it to ``true'').
So after the 5ms the actual value of Lock.used is changed to ``false'', but lock() never notices it,
as it's value is in cache?

I think I'm overlooking something here.

mpan · 2017-03-03 21:47:15

seishinryohosha:
Re-writing the answer (ignore previous one)

Last edited by mpan (2017-03-03 21:48:05)

mpan · 2017-03-03 21:56:48

seishinryohosha:
You should remember that between synchronization points threaded applications are non-deterministic. You seem to assume some particular order of execution of statements, despite they may be executed in arbitrary order in the threads. In particular the lock method in this code may never execute at all (and in a typical case it never will), because the program terminates before it even has a chance to run it. If you don’t know why, get a sheet of paper and write down, side-by-side, what happens in the program, line-by-line. Point out synchronization points between the threads. Scan/photo it and upload the result (for example to ptpb.pw if you don’t own a server) if you still don’t see what happens in your program.

Note: that has not much to do with Java, it’s a general behaviour of multithreaded applications. I can show you a bash script that exhibits exactly the same behaviour using sub-processes.

Last edited by mpan (2017-03-03 22:10:39)

seishinryohosha · 2017-03-04 17:25:53

So to summarise it:

As no synchronization takes effect the result is undefined?
Or better implementation specific.
Like how the scheduler works. Read from cache or not and so on.

It may terminate, it may not?

So the final answer for the book question is:
As no synchronisation takes effect and the Lock.used is accesible through lock() unlock() at any time,
the termination is undefined.

mpan · 2017-03-05 01:24:06

No, it has nothing to do with caches, not much to do with used variable or any other of your guesses. Can you show me your drawing and where exactly is the place in it, where anything about cache appears in it?

As for now I assume you’re just a help vampire seeking for someone to solve your homework.

seishinryohosha · 2017-03-05 18:36:10

Here is the image ~> http://pasteboard.co/4bsrSnbvi.png
If you think I'm a help vampire it's fine.
You could answer me in a week or two, so all "homework time" certainly is over.

But why used doesn't matter here?

Thread 1 aka the main Thread terminates certainly. (It has no loops or jumps)
Thread 2 aka Worker-Thread terminates only, if used is false (initially it's true), so the while-loop terminates, so the run-Method returns so the Thread can terminate, so the JVM can terminate so the whole program can terminate.

mpan · 2017-03-06 01:56:53

I haven’t said “used doesn’t matter“ — I’ve said “not much to do with used”. The phenomenon you’re observing is causing used field to be quite unimportant to the whole code.

On you picture there is no communication between the threads marked, except for the worker thread being started by the main thread. That should already give you a hint on why a call to unlock doesn’t hang because of lock (or the other way around). Let me be more specific: how would the behaviour of this code change if lock and unlock were not marked as synchronized? I can’t give you more detailed hint and not literally solve the problem for you.

There is a second, independent issue too. On your picture you have drawn the threads having their non-synchronized operations side-by-side. If they are not synchronized after a call to start, code in each of the threads may execute at any order in relation to the other thread. Consider shifting the threads a bit vertically and you should notice that second thing.

By the way: I hope you’re not assuming that threads can’t see updates to used just because it’s not synchronized or volatile. p ⇒ q is not equivalent to ¬p ⇒ ¬q.

Last edited by mpan (2017-03-06 01:59:37)

seishinryohosha · 2017-03-06 07:01:16

If I don't mark unlock() and lock() as synchronized, it would change nothing in their behaviour.

It would change, if I used the same Lock-object in both threads.
(E.g. create a Lock in main and pass it to a Worker-Constructor)

The second thing:
I tried to show this issue with the "traces" in my image.
They could be executed in arbitrary order.
So the Loop could get executed 100 times or 200 times, before unlock() is called.
(The loop could even never be executed, if unlock() is faster)

And no, I know they can see updates.
We just got told, that a short period may occur between write and update.
So it's not guaranteed they see the update instantly.
So maybe the ACID properties get hurt.
(It's not as severe as in e.g. a Linked-List, but hey)

mpan · 2017-03-07 02:47:54

seishinryohosha wrote:

If I don't mark unlock() and lock() as synchronized, it would change nothing in their behaviour.

So you have a half of the answer already.

seishinryohosha wrote:

So the Loop could get executed 100 times or 200 times, before unlock() is called.
(The loop could even never be executed, if unlock() is faster)

And you have the other half too.

And these two parts, only them, contribute to the fact that behaviour of the program is undefined. Not caches, synchronization, use of volatile or AtomicBoolean. That properly synchronized program is equally unpredictable:

public final class Main extends Thread {
    
    public static void main(final String[] args) {
        final Main o = new Main();
        o.start();
        o.unlock();
    }
    
    @Override
    public void run() {
        lock();
    }
    
    private boolean used = true;
    
    private void lock() {
        synchronized (Main.class) {
            while (used) {}
        }
    }
    
    private void unlock() {
        synchronized (Main.class) {
            used = false;
        }
    }
}

Note: despite the above code does proper synchronization, it has the same bug as your original: it does synchronization on a public object. I’ve repeated the bad implementation for clarity.

Usage of volatile or AtomicBoolean would make the program behaviour well-defined, but for reasons different than the ones that cause your code to have undefined behaviour. They would change the way the loop in lock is acting; the meaning of the loop would be completely different, so considering them to fix the original issue would make as much sense as telling that replacing a bicycle with shopping cart solves flat tire. Indeed there is no flat tire anymore, but merely because there is no bicycle in the first place, not because the tire has been repaired.

seishinryohosha · 2017-03-07 05:27:47

Thank you for your patience!

I surely mixed up alot (#^.^#)

Thank you very much!

Arch Linux

#1 2017-03-03 05:29:10

[SOLVED] [Java] Threads and Locks (Synchronized) help understanding...

#2 2017-03-03 10:52:43

Re: [SOLVED] [Java] Threads and Locks (Synchronized) help understanding...

#3 2017-03-03 15:12:00

Re: [SOLVED] [Java] Threads and Locks (Synchronized) help understanding...

#4 2017-03-03 21:34:28

Re: [SOLVED] [Java] Threads and Locks (Synchronized) help understanding...

#5 2017-03-03 21:47:15

Re: [SOLVED] [Java] Threads and Locks (Synchronized) help understanding...

#6 2017-03-03 21:56:48

Re: [SOLVED] [Java] Threads and Locks (Synchronized) help understanding...

#7 2017-03-04 17:25:53

Re: [SOLVED] [Java] Threads and Locks (Synchronized) help understanding...

#8 2017-03-05 01:24:06

Re: [SOLVED] [Java] Threads and Locks (Synchronized) help understanding...

#9 2017-03-05 18:36:10

Re: [SOLVED] [Java] Threads and Locks (Synchronized) help understanding...

#10 2017-03-06 01:56:53

Re: [SOLVED] [Java] Threads and Locks (Synchronized) help understanding...

#11 2017-03-06 07:01:16

Re: [SOLVED] [Java] Threads and Locks (Synchronized) help understanding...

#12 2017-03-07 02:47:54

Re: [SOLVED] [Java] Threads and Locks (Synchronized) help understanding...

#13 2017-03-07 05:27:47

Re: [SOLVED] [Java] Threads and Locks (Synchronized) help understanding...

Board footer