Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (539)
Games in Android Showcase (132)
games submitted by our members
Games in WIP (603)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1] 2 3
  ignore  |  Print  
  Impossible race condition between threads?  (Read 10181 times)
0 Members and 1 Guest are viewing this topic.
Offline theagentd

« JGO Bitwise Duke »


Medals: 366
Projects: 2
Exp: 8 years



« Posted 2013-10-25 14:07:43 »

Hello everyone!

I recently encountered an extremely rare race condition in my threading code. After 4 hours of debugging I finally managed to reproduce the error somewhat reliably and managed to track it down and fix it, but I still can't wrap my head around WHY it happened in the first place.

The class in question is in charge of distributing tasks to worker threads. Since the total number of tasks was known, I simply kept an AtomicInteger counter to keep track of the number of completed tasks to be able to signal the main thread that all tasks had been completed. The problem was that the totalTasks field did not get synchronized, meaning that the value the atomic task counter was compared to was sometimes not updated. How can that possibly happen in the following code?

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
    private PriorityBlockingQueue<Task> taskQueue;

    protected AtomicInteger taskCounter;
    protected int totalTasks;

    public void run(TaskTree tree){ //A TaskTree contains tasks...
        taskCounter.set(0);
        totalTasks = tree.getNumTasks(); //This call here was sometimes not visible to the worker threads.
        for(Task t : tree.getTasks()){
            taskQueue.add(t); //This will cause the thread below to start processing.
        }
        //wait for completion signal that from worker thread(s)
    }

    //The worker thread run() method:
    public void run(){
        Task task;
            while (running) {
                try {
                    task = taskQueue.take();
                } catch (InterruptedException ex) {
                    break; //Closed, kill thread
                }
               
                task.process();
                if (taskCounter.incrementAndGet() == totalTasks) { //totalTasks sometimes had not been updated with the new value yet!
                    //Signal main thread that all tasks have been completed.
                }
            }
        }
    }


The code above is extremely simplified, so the taskCounter variable may seem redundant, etc. Anyway, the race condition only started occurring when I first ran a TaskTree with a single task (totalTasks = 1), and then ran a different TaskTree with 10 tasks. When the second TaskTree was run, a worker thread would sometimes process a single task, see that (taskCounter = totalTasks = 1) and signal that all tasks had been completed.

I "solved" this by counting backwards. By setting the taskCounter to totalTasks, decrementing instead of incrementing and comparing to 0 the race condition was avoided, but I still can't fathom why the locking done by the task queue does not cause proper synchronization between the threads. How can the thread be woken up from awaiting a lock and then read the wrong value? I was under the impression that locking a lock would cause all memory to be synchronized properly each time a thread acquires that lock.

Thanks for reading!

Myomyomyo.
Offline 65K
« Reply #1 - Posted 2013-10-25 14:19:14 »

Just from a quick glance:
Make totalTasks volatile or synchronize it.

Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 842
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #2 - Posted 2013-10-25 14:27:46 »

If you want help with code that is problematic don't give us pseudo code Roll Eyes

The locking code, which is critical, is just... gone.



Just like with synchronized, only the variables in the critical section are guaranteed to be synced among threads. After a thread unlocks a lock, no more guarantees can be made. Even for variables you just accessed in the critical section. Their value is undefined.
1  
2  
3  
4  
synchronized(mutex) {
    // all access to shared variables is safe
}
// all bets are off again (!)
1  
2  
3  
4  
5  
6  
7  
8  
lock.lock();
try {
    // all access to shared variables is safe
}
finally {
   lock.unlock();
}
// all bets are off again (!)



Last but not least, AtomicInteger.set(n) is rather awkward in multi threaded code. What if multiple threads call .run(TaskTree) ? Just call AtomicInteger.incrementAndGet() prior to adding each task to the queue.

Anyway, I'd advise to use CountdownLatch. Your solution to count backwards is what I always did, and is guaranteed to work, but it's what CountdownLatch does behind the scenes, including signalling the other thread(s) when the latch reaches zero. I however always make a new CountdownLatch for each run(TaskTree) operation, instead of stuffing it in a field, and simply attach the CountdownLatch to each task (can be a done with a holder object), and use latch.await() in the .run(TaskTree) method.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline theagentd

« JGO Bitwise Duke »


Medals: 366
Projects: 2
Exp: 8 years



« Reply #3 - Posted 2013-10-25 16:31:22 »

If you want help with code that is problematic don't give us pseudo code Roll Eyes

The locking code, which is critical, is just... gone.
I didn't remove anything important. The locking happens in PriorityBlockingQueue.

Last but not least, AtomicInteger.set(n) is rather awkward in multi threaded code. What if multiple threads call .run(TaskTree) ? Just call AtomicInteger.incrementAndGet() prior to adding each task to the queue.
run(TaskTree) is not meant to be thread safe, but I'll keep that in mind.

Anyway, I'd advise to use CountdownLatch. Your solution to count backwards is what I always did, and is guaranteed to work, but it's what CountdownLatch does behind the scenes, including signalling the other thread(s) when the latch reaches zero. I however always make a new CountdownLatch for each run(TaskTree) operation, instead of stuffing it in a field, and simply attach the CountdownLatch to each task (can be a done with a holder object), and use latch.await() in the .run(TaskTree) method.
That seems like a good idea, but a problem is that the main thread actually also processes tasks. Since the OpenGL context belongs to the main thread all tasks that use OpenGL have to be run on that thread.


Just like with synchronized, only the variables in the critical section are guaranteed to be synced among threads. After a thread unlocks a lock, no more guarantees can be made. Even for variables you just accessed in the critical section. Their value is undefined.
1  
2  
3  
4  
synchronized(mutex) {
    // all access to shared variables is safe
}
// all bets are off again (!)
1  
2  
3  
4  
5  
6  
7  
8  
lock.lock();
try {
    // all access to shared variables is safe
}
finally {
   lock.unlock();
}
// all bets are off again (!)

Now that is terrible. Once a task is completed it can unlock one or more new task which are then added to the queue. I was under the assumption that the synchronization in PriorityBlockingQueue would cover all memory, but you're telling me that there's a risk that if a task unlocks a new task which is picked up by a different thread than the first, there's a risk that it may not see the changes made by the first task? I think I need to sit down for a while...

Myomyomyo.
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 842
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #4 - Posted 2013-10-25 16:38:18 »

Keep in mind that the CPU (!) and the JVM are allowed to reorder instructions, so whatever happens in-order in your source code, and bytecode, that doesn't mean shit for actual behaviour. Only critical sections provide happens-before guarantees on the boundaries.

Right after you left the critical section, another thread/core/whatever may overwrite that field again with out of date data.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social
Offline theagentd

« JGO Bitwise Duke »


Medals: 366
Projects: 2
Exp: 8 years



« Reply #5 - Posted 2013-10-25 16:41:25 »

How would I guarantee that a task is run after its prerequisites then? I suppose what I'm looking for is a kind of memory barrier/fence... Or am I...?  Huh

Right after you left the critical section, another thread/core/whatever may overwrite that field again with out of date data.
That cannot happen in my case since once the critical section is left the thread won't modify that data anymore. Or did I misunderstand something again...? T___T

Myomyomyo.
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 842
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #6 - Posted 2013-10-25 16:50:02 »

IIRC, back when you introduced your thread library on JGO, I browsed the code and thought it could never be guaranteed to work. I decided to keep quiet, as you seemed so sure of yourself.

With your current code I also don't know how you could possibly handle tasks that are added to the queue while processing the queue, as they also increment/decrement your AtomicInteger, which will cause your blocking .run(TaskTree) to return way before all appended tasks have finished. It's all very tricky, and the code you posted doesn't take it into account at all...?

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 842
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #7 - Posted 2013-10-25 16:56:14 »

Right after you left the critical section, another thread/core/whatever may overwrite that field again with out of date data.
That cannot happen in my case since once the critical section is left the thread won't modify that data anymore. Or did I misunderstand something again...? T___T
Communication between threads/cores can happen at literally any time, which means stale data is 'synchronized', which means thread A and thread B can both know the field holds value 0 (at a specific point in time), but at one point (a bit earlier) thread A assigned it another value, and that value is only now being propagated to thread B. Causing thread B to see a stale value, outside of the critical section.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social
Offline theagentd

« JGO Bitwise Duke »


Medals: 366
Projects: 2
Exp: 8 years



« Reply #8 - Posted 2013-10-25 16:58:14 »

IIRC, back when you introduced your thread library on JGO, I browsed the code and thought it could never be guaranteed to work. I decided to keep quiet, as you seemed so sure of yourself.
I'll be damned... ._.

With your current code I also don't know how you could possibly handle tasks that are added to the queue while processing the queue, as they also increment/decrement your AtomicInteger, which will cause your blocking .run(TaskTree) to return way before all appended tasks have finished. It's all very tricky, and the code you posted doesn't take it into account at all...?
The total number of tasks in a task tree is known from the start. Before the worker threads are given any work through the task queue I call
remainingTasks.set(tree.getNumTasks());
. The atomic counter is not incremented as tasks are added to the queue. The atomic counter can never reach zero unless all tasks are finished.

Right after you left the critical section, another thread/core/whatever may overwrite that field again with out of date data.
That cannot happen in my case since once the critical section is left the thread won't modify that data anymore. Or did I misunderstand something again...? T___T
Communication between threads/cores can happen at literally any time, which means stale data is 'synchronized', which means thread A and thread B can both know the field holds value 0 (at a specific point in time), but at one point (a bit earlier) thread A assigned it another value, and that value is only now being propagated to thread B.
And there is no easy way to force a task to have a happens-before relationship with other tasks?

Myomyomyo.
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 842
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #9 - Posted 2013-10-25 17:00:47 »

Nothing is easy when dealing with concurrency. Immutable objects and message queues help.

As a dirty hack, you can give the 'dependent task' a lock that is used by the 'parent task', when modifying data. This shouldn't cause any blocking, unless a task has multiple 'children'.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline theagentd

« JGO Bitwise Duke »


Medals: 366
Projects: 2
Exp: 8 years



« Reply #10 - Posted 2013-10-25 17:09:49 »

Hmm...

So if all tasks synchronize all their prerequisites and on themselves they would be guaranteed to see the data of its required tasks. I still have a hard time accepting that that is necessary...

Myomyomyo.
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 842
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #11 - Posted 2013-10-25 17:13:53 »

You'd only have to lock on the parent (if any) and itself.

It's a bit like:
1  
2  
3  
4  
5  
synchronized(parent) {
   synchronized(this) {
       //
   }
}
but then preventing deadlocks by using Lock.tryLock to either acquire both locks or none.


Having said that, immutable objects and message queues are preferable.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social
Offline theagentd

« JGO Bitwise Duke »


Medals: 366
Projects: 2
Exp: 8 years



« Reply #12 - Posted 2013-10-25 17:51:53 »

Sorry, had dinner...

You'd only have to lock on the parent (if any) and itself.

It's a bit like:
1  
2  
3  
4  
5  
synchronized(parent) {
   synchronized(this) {
       //
   }
}
but then preventing deadlocks by using Lock.tryLock to either acquire both locks or none.
Yes, exactly. But don't I also have to make sure that all memory transactions that were done before calling run(TaskTree) have completed? And don't I have to ensure that all code that comes after can see the changes made by the tasks? This is ridiculous. I'd have to put the whole goddamn game under one big lock. -_-

Myomyomyo.
Offline Riven
« League of Dukes »

« JGO Overlord »


Medals: 842
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #13 - Posted 2013-10-25 17:56:25 »

Keep in mind CountDownLatch has happens-before guarantees, as long as all threads modifying data call coutdown(). But only the thread calling await() has this consistent view on the data modified by the worker threads.

http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/package-summary.html#MemoryVisibility

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social
Offline theagentd

« JGO Bitwise Duke »


Medals: 366
Projects: 2
Exp: 8 years



« Reply #14 - Posted 2013-10-25 18:02:53 »

http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/package-summary.html#MemoryVisibility
Quote
Actions in a thread prior to placing an object into any concurrent collection happen-before actions subsequent to the access or removal of that element from the collection in another thread.
When a task is completed, the tasks it unlocks are inserted into the concurrent collection. When they are removed from the collection, they are guaranteed to happen "after" the unlocking task(s) have completed regardless of locking. W-what's going on...? Once a task is taken out, it has to have a happens-after relationship with the tasks that happened before it thanks to this.

EDIT: To clarify, the problem still isn't solved. The same logic as the one above implies that the race condition I got should not be possible either.

Myomyomyo.
Online Roquen
« Reply #15 - Posted 2013-10-26 13:10:35 »

Locks suck. Smiley  Deadlocks, races, priority inversion...meh.

I don't understand why a worker thread is informing the main thread of anything.  Why do it that way?

(EDIT: BTW - I did see the "might seem redundant" part...what are you really attempting to do with this is my question).
Offline theagentd

« JGO Bitwise Duke »


Medals: 366
Projects: 2
Exp: 8 years



« Reply #16 - Posted 2013-10-26 19:40:27 »

I don't understand why a worker thread is informing the main thread of anything.  Why do it that way?
run(TaskTree) blocks until all tasks in the tree have been completed. That's why the worker threads have to be able to signal this.

Myomyomyo.
Offline theagentd

« JGO Bitwise Duke »


Medals: 366
Projects: 2
Exp: 8 years



« Reply #17 - Posted 2013-10-26 20:38:44 »

My attempts at reproducing the original error failed today. However, I believe I have found another problem with the assumptions I made when I wrote this concerning how certain tasks are executed. From what I know this problem should not be able to cause the original race condition, but it should be able to cause race conditions when a task requires several other tasks to complete before they're allowed to be executed.

Basically each task has a counter of how many of its prerequisites have been completed. It's an atomic int. When a required task is completed it increments this counter by 1 for all tasks that require the just completed task. Since only the last task interacts with the task queue (according to Oracle docs that guarantees correct order, see my above post), only the changes done by the task that finally unlocks the new task and adds it to the queue will be guaranteed to be visible to the new task. The other required tasks simply incremented an atomic counter, so some the unlocked task may not be able to see those changes. (I have never had any problems, but that's a bad argument here...)


Applying this to the original problem

Due to new tasks being added to the queue being added BEFORE incrementing the taskCounter, it's entirely possible for any task to be the last that "finishes" if the thread is not allowed to run anymore for some reason immediately after having queued up new tasks, so all tasks potentially need to be able to see what the main thread does.

The "root" tasks (the tasks available from the beginning) are added by the main thread, so the main thread should have a happens-before relationship with all the root tasks according to the Oracle docs. Assuming there is one more task that requires say 3 of the root tasks to complete before it can run, it'll then be unlocked by the same thread that completes the last required task. That means that the thread that runs the new task is guaranteed to be able to see the work done by the unlocking thread (1 of the 3 required tasks), but not the other two required tasks (the first two simply incremented the unlocking counter). Although this is bad, it still means that it'll always happen-after one of the tasks that happened-after the main thread.

It all becomes a mathematical proof that it should work correctly:
1. The root tasks happen-after the main thread.
2. If a task happens-after a task that happens after the main thread, it too happens after the main thread.
3. An unlocked task will happen-after ONE of its required task.
Conclusion: All tasks happen-after the main thread.

So, either my reasoning above is wrong, or my code does not work as I am thinking... Any ideas?


EDIT: I also don't know why this new problem isn't happening in practice. For example, I have tasks that are run X times (doing different things each run of course) and feature a finish() function that I use for merging the results.

Example:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
AtomicInteger subtaskID = new AtomicInteger(0); //ID of each subtask to make them process different parts of a task.
AtomicInteger completedSubtasks = new AtomicInteger(0); //How many subtasks that have completed
int numSubtasks = 4; //How many subtasks the task is divided into
...

task.run(subtaskID.getAndIncrement());

if(completedSubtasks.incrementAndGet() == numSubtasks){
    //All subtasks have been completed, but there's no synchronization between the threads
    //that processed the different subtasks.

    task.mergeResultsFromSubtasks(); //This call accesses data modified by other threads and should result in race conditions a lot, but it never does.
}


I assume that updating the atomic counter in some way causes the subtask data to be synchronized as well, but that it's just a fluke due to my use cases and/or how my processor works.

Myomyomyo.
Offline theagentd

« JGO Bitwise Duke »


Medals: 366
Projects: 2
Exp: 8 years



« Reply #18 - Posted 2013-10-27 18:25:46 »

Triple posting, but I wanted to "close" this thread. Clueless

Since I couldn't guarantee that my multithreading was thread-safe, I've decided to abandon my old multithreader. I've made a new one that has a bit more synchronization overhead but it should be 100% thread safe. Running 48 tasks with complex dependencies is now around 0.05 to 0.1ms slower, which is acceptable. The new multithreading system relies on a master thread that coordinates the worker threads and the draw thread. I no longer do any synchronization with atomic ints; I'm completely relying on concurrent collections as specified in the Oracle docs, and that the master thread is the only thread that can coordinate task (the old one allowed worker threads to add tasks). The old multithreader is still there, but is marked as experimental until I can prove or disprove that it's thread safe.

Myomyomyo.
Online Roquen
« Reply #19 - Posted 2013-10-30 21:46:32 »

I happened to still have this open and reskimmed.  If the first "snippet" is representative then the problem is that the variable reference can legally be promoted to local copy and thus the thread won't see changes (unless at some point the local version is updated).  This is one of those trick things to notice because slight and potentially unrelated code change can make the compiler perform the promotion or not.

Change to volatile (as 65K mentioned...syncronization won't help and there is no "race") or an atomic.  The latter more for code clarity than any practical purpose.

Also talking about "happens before" when discussing atomic operations is making the discussion too complicated.
Offline theagentd

« JGO Bitwise Duke »


Medals: 366
Projects: 2
Exp: 8 years



« Reply #20 - Posted 2013-10-30 21:54:35 »

So the fact that it was happening randomly was due to the JIT compiler? What exactly does "promoted to local copy" mean? The variable being assigned is a class variable... Thanks for your response!

Myomyomyo.
Online Roquen
« Reply #21 - Posted 2013-10-30 22:08:18 »

JIT = yes.  The JIT will treat a thread as being the only one running.  So if it sees that a variable cannot be modified in a method or loop (including deductions it may be able to make about all possible sub-methods that are called) it can pull that variable into a local (stack) variable or a register.  Specifying volatile tells it that the variable must be read/written to main at each access.
Offline theagentd

« JGO Bitwise Duke »


Medals: 366
Projects: 2
Exp: 8 years



« Reply #22 - Posted 2013-10-31 11:26:24 »

Makes sense, but I don't really understand what criteria the compiler is using to determine if it should promote a variable. My Google-fu gave me no relevant results...

It does not seem to take into account that the worker thread run() method was actually in an inner class that extended Thread. It should be obvious that the variable is used from multiple threads, but I guess it's not surprising that it didn't look that far. Besides, it's entirely possible to manually call the Thread's run() method without starting a new thread... *murr*

Myomyomyo.
Online Roquen
« Reply #23 - Posted 2013-10-31 21:36:53 »

It's too much work for the compiler to deduce (pretty often impossible)...every variable would have to be provably never modified by some other thread (or interrupt, etc.).  Every variable that couldn't be proven so would be equivalent to volatile (that would be bad).  Much better to have the programmer say: "Yo someone is reading or writing to this behind your back." and just declare volatiles.

Quote
I don't really understand what criteria the compiler is using to determine if it should promote a variable
This will be compiler specific.  An example is the value is loaded into a register to be used, and when that register is needed for something else it'll spill (be copied onto the stack) and when needed again the stack copy will be reread (again the compiler has deduced that the main memory version hasn't changed...so no reread is needed).  That's an example of when changing something that looks like it'll have no effect will make the bug appear and disappear.

Typed out quickly...hope ya'll can follow me.
Offline theagentd

« JGO Bitwise Duke »


Medals: 366
Projects: 2
Exp: 8 years



« Reply #24 - Posted 2013-11-01 11:09:43 »

Roquen:
You mentioned that modifying a variable in a loop or through a method would inherently make the variable volatile. Is that always the case?

If I can't have any assumptions on what the compiler can do to break the synchronization from my concurrent collections, don't I have to make everything volatile anyway? For example, let's say I want to pass a message object to a different thread. This message object is reused by a single thread (in a safe way of course). When the thread wants to send a message, it sets the variables of the message object and sends it to another thread. Doesn't all variables in that class need to be volatile in this case? This example can be extended to almost all parts of my threading library...

Myomyomyo.
Offline nsigma
« Reply #25 - Posted 2013-11-01 12:10:59 »

You mentioned that modifying a variable in a loop or through a method would inherently make the variable volatile. Is that always the case?

Feeling you're reading that backwards!  Wink

If I can't have any assumptions on what the compiler can do to break the synchronization from my concurrent collections, don't I have to make everything volatile anyway?

Assuming you're using the built-in concurrent collections (or a properly designed one), then no.  See the section on memory consistency (as Riven linked to earlier), in particular around concurrent collections.  The JIT compiler can't break things that are guaranteed by the JLS to be happens-before.

http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/package-summary.html#MemoryVisibility

Praxis LIVE - open-source intermedia toolkit and live interactive visual editor
Digital Prisoners - interactive spaces and projections
Offline theagentd

« JGO Bitwise Duke »


Medals: 366
Projects: 2
Exp: 8 years



« Reply #26 - Posted 2013-11-01 15:53:16 »

If I can't have any assumptions on what the compiler can do to break the synchronization from my concurrent collections, don't I have to make everything volatile anyway?

Assuming you're using the built-in concurrent collections (or a properly designed one), then no.  See the section on memory consistency (as Riven linked to earlier), in particular around concurrent collections.  The JIT compiler can't break things that are guaranteed by the JLS to be happens-before.

http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/package-summary.html#MemoryVisibility
But that's why I wrote "impossible" in the thread title. I wrote to the variable and added an object to a PriorityBlockingQueue, but after taking out the object from the queue the variable had not been updated... Does the variable have to be inside the object passed into the queue? Such a requirement isn't mentioned in that link.

Myomyomyo.
Offline Spasi
« Reply #27 - Posted 2013-11-01 17:22:50 »

The problem here is rather obvious and is what Roquen said in a previous post; the totalTasks value is read only once, instead of on every iteration of the while loop, and cached in a register. This is a perfectly valid transformation for the processing thread to do and it has nothing to do with synchronization or happens-before relationships. As far as it is concerned, it is the only thread doing anything with it. The fix is also easy, you just mark it volatile and it will force the processing thread to always read the value from memory. The memory reads enable all the happens-before constraints to become applicable (the PBQ alone is enough to provide the semantics you need) and you should always read the correct value.

In general, if you ever access the same memory location from multiple threads (and at least one access is a write), you must use volatile. In most cases though, shared memory access exposes you to all kinds of trouble and immutable message passing is almost always a better solution.

It does not seem to take into account that the worker thread run() method was actually in an inner class that extended Thread. It should be obvious that the variable is used from multiple threads, but I guess it's not surprising that it didn't look that far.

This should be obvious from what I wrote above, but there's no "analysis" going on. There's no difference between "normal" code and code running in a Thread/run(), it's all the same thing and the same optimizations apply. The only relevant information for the JIT compiler is whether the field is volatile or not.

You mentioned that modifying a variable in a loop or through a method would inherently make the variable volatile. Is that always the case?

No. The loop may be optimized by reading the field once, doing all mutations in a register, then writing out the result once at the end of the loop. Even if the JITed code always reads/writes from/to memory, it would still be different from volatile. Volatile provides very specific semantics and is implemented with special CPU instructions. A write to a volatile field is actually a write followed by a write-release barrier. A read to a volatile field is a read-acquire barrier followed by a read. The write-release barrier synchronizes with (i.e. happens-before) the read-acquire barrier. There's nothing like that going on for non-volatile field accesses, optimized or not.
Offline nsigma
« Reply #28 - Posted 2013-11-01 17:56:40 »

The problem here is rather obvious and is what Roquen said in a previous post; the totalTasks value is read only once, instead of on every iteration of the while loop, and cached in a register.

 Huh Actually shouldn't the take() in every iteration mean that totalTasks is not cached?

From link above

Quote
Actions in a thread prior to placing an object into any concurrent collection happen-before actions subsequent to the access or removal of that element from the collection in another thread.

@theagentd - btw, I'm wondering why you're trying to build this without making use of other concurrent utilities within the JDK?  Couldn't you look at the standard executor service, and use futures to model task dependencies?  Or fork / join?

Praxis LIVE - open-source intermedia toolkit and live interactive visual editor
Digital Prisoners - interactive spaces and projections
Offline Spasi
« Reply #29 - Posted 2013-11-01 18:58:12 »

Huh Actually shouldn't the take() in every iteration mean that totalTasks is not cached?

The way I understand it is the read indeed happens after the first take() and then cached. It explains this:

Anyway, the race condition only started occurring when I first ran a TaskTree with a single task (totalTasks = 1), and then ran a different TaskTree with 10 tasks. When the second TaskTree was run, a worker thread would sometimes process a single task, see that (taskCounter = totalTasks = 1) and signal that all tasks had been completed.

i.e. it works correctly only the first time through the loop, then the optimization kicks in.
Pages: [1] 2 3
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

rwatson462 (37 views)
2014-12-15 09:26:44

Mr.CodeIt (30 views)
2014-12-14 19:50:38

BurntPizza (62 views)
2014-12-09 22:41:13

BurntPizza (99 views)
2014-12-08 04:46:31

JscottyBieshaar (59 views)
2014-12-05 12:39:02

SHC (74 views)
2014-12-03 16:27:13

CopyableCougar4 (77 views)
2014-11-29 21:32:03

toopeicgaming1999 (138 views)
2014-11-26 15:22:04

toopeicgaming1999 (127 views)
2014-11-26 15:20:36

toopeicgaming1999 (38 views)
2014-11-26 15:20:08
Resources for WIP games
by kpars
2014-12-18 10:26:14

Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!