2

for learning purpose i have tried to implements a queue data-structure + Consumer/producer chain that is thread-safe, for learning purpose too i have not used notify/wait mechanism :

SyncQueue :

package syncpc; /** * Created by Administrator on 01/07/2009. */ public class SyncQueue { private int val = 0; private boolean set = false; boolean isSet() { return set; } synchronized public void enqueue(int val) { this.val = val; set = true; } synchronized public int dequeue() { set = false; return val; } }

Consumer :

package syncpc; /** * Created by Administrator on 01/07/2009. */ public class Consumer implements Runnable { SyncQueue queue; public Consumer(SyncQueue queue, String name) { this.queue = queue; new Thread(this, name).start(); } public void run() { while(true) { if(queue.isSet()) { System.out.println(queue.dequeue()); } } } }

Producer :

package syncpc; import java.util.Random; /** * Created by Administrator on 01/07/2009. */ public class Producer implements Runnable { SyncQueue queue; public Producer(SyncQueue queue, String name) { this.queue = queue; new Thread(this, name).start(); } public void run() { Random r = new Random(); while(true) { if(!queue.isSet()) { queue.enqueue(r.nextInt() % 100); } } } }

Main :

import syncpcwn.*; /** * Created by Administrator on 27/07/2015. */ public class Program { public static void main(String[] args) { SyncQueue queue = new SyncQueue(); new Producer(queue, "PROCUDER"); new Consumer(queue, "CONSUMER"); } }

The problem here, is that if isSet method is not synchronized , i got an ouput like that :

97, 55

and the program just continue running without outputting any value. while if isSet method is synchronized the program work correctly.

i don't understand why, there is no deadlock, isSet method just query the set instance variable without setting it, so there is no race condition.

Improve this question
6
  • 3
    Use volatile for the set field to ensure visibility. Otherwise the CPU is allowed to store it in the cache / register and not update it as an optimization. Commented Jul 29, 2015 at 18:59
  • worked thx :), another question : why with the synchronized keyword, the program run correctly? do synchronized force the variable to be read from main memory, rather than cache/register? Commented Jul 29, 2015 at 19:03
  • 2
    Because synchronized has the same visibility results, which in hardware is a store memory barrier. I recommend reading Java Concurrency in Practice for a gentle introduction. You'll learn about happens-before and roach motel model, without getting lost in the hardware details (barriers, MESI protocol, etc). Commented Jul 29, 2015 at 19:08
  • @karim: What you need is a memory barrier to ensure that the read from the set field is fresh (not from cache). The volatile keyword causes a memory barrier to be inserted for every read and write operation. The synchronized keyword causes a monitor lock to be acquired and then released, and acquiring a monitor also inserts a memory barrier. More pedantically, you need a happens-before relationship between the write to set in enqueue and dequeue and the read in isSet; you can read the Java Language Spec to find all the ways a happens-before relationship can be established. Commented Jul 29, 2015 at 19:10
  • 2
    This example will work by adding volatile or synchronized as others have mentioned, but in general, you would want to surround the whole operation with a synchronized block. Otherwise, if you had 2 consumers, for example, both could check isSet() at the same time, see that there is a value there, then both try to dequeue the same value. This would happen in the case where a thread switch occurred between isSet() and dequeue(), and synchronizing both methods would not help you. Commented Jul 29, 2015 at 19:20

3 Answers 3

Reset to default
4

set needs to be volatile:

private boolean volatile set = false;

This ensures that all readers see the updated value when a write completes. Otherwise they will end up seeing the cached value. This is discussed in more detail in this article on concurrency, and also provides examples of different patterns that use volatile.

Now the reason that your code works with synchronized is probably best explained with an example. synchronized methods can be written as follows (i.e., they are equivalent to the following representation):

public class SyncQueue { private int val = 0; private boolean set = false; boolean isSet() { synchronized(this) { return set; } } public void enqueue(int val) { synchronized(this) { this.val = val; set = true; } } public int dequeue() { synchronized(this) { set = false; return val; } } }

Here, the instance is itself used as a lock. This means that only thread can hold that lock. What this means is that any thread will always get the updated value because only one thread could be writing the value, and a thread that wants to read set won't be able to execute isSet until the other thread releases the lock on this, at which point the value of set will have been updated.

If you want to understand concurrency in Java properly you should really read Java: Concurrency In Practice (I think there's a free PDF floating around somewhere as well). I'm still going through this book because there are still many things that I do not understand or am wrong about.

As matt forsythe commented, you will run into issues when you have multiple consumers. This is because they could both check isSet() and find that there is a value to dequeue, which means that they will both attempt to dequeue that same value. It comes down to the fact that what you really want is for the "check and dequeue if set" operation to be effectively atomic, but it is not so the way you have coded it. This is because the same thread that initially called isSet may not necessarily be the same thread that then calls dequeue. So the operation as a whole is not atomic which means that you would have to synchronize the entire operation.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

but, why when i use the synchronized keyword, the program work correctly, synchronized keyword force variable to be read/write from main-memory rather than from cache?
@karim I've added an explanation as to why synchronized works.
@karim In NUMA architecture, you have a store buffer cache for every core. So when you do write, they are done to store buffer cache first and then later they are flushed to main memory. This is perfectly fine in non thread world. But when you use locks around code, then you are telling the hardware not to do that for the code piece that is doing any write opertaion in critical section.
3

The problem you have is visibility (or rather, the lack of it).

Without any instructions to the contrary, the JVM will assume that the value assigned to a variable in one thread need not be visible to the other threads. It may be made visible sometimes later (when it's convenient to do so), or maybe not ever. The rules governing what should be made visible and when are defined by the Java Memory Model and they're summed up here. (They may be a bit dry and scary at first, but it's absolutely crucial to understand them.)

So even though the producer sets set to true, the consumer will continue to see it as false. How can you publish a new value?

  1. Mark the field as volatile. This works well for primitive values like boolean, with references you have to be a bit more careful.
  2. synchronized provides not just mutual exclusion but also guarantees that any values set in it will be visible to anyone entering a synchronized block that uses the same object. (This is why everything works if you declare the isSet() method synchronized.)
  3. Using a thread-safe library class, like the Atomic* classes of java.util.concurrent

In your case volatile is probably the best solution because you're only updating a boolean, so atomicity of the update is guaranteed by default.

As @matt forsythe pointed out, there is also a TOCTTOU issue with your code too because your threads can be interrupted by another between isSet() and enqueue()/dequeue().

Improve this answer

Comments

0

I assume that when we get stuck in threading issue, the first step was to make sure that both the threads are running well. ( i know they will as there are no locks to create deadlock)

For that you could have added a printf statement in enqueue function as well. That would make sure that enqueue and dequeue threads are running well.

Then second step should have been that "set" is the shared resource, so is the value toggling well enough so that code can run in desired fashion.

I think if you could reason and put the logging well enough, you can realize the issues in problem.

Improve this answer

1 Comment

I did that as Karim specified that it is for learning purpose :).

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.