Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>The "official answer" that questioneer posted is wrong in so many ways, I'm going to post another answer for those who will stumble on this question in future.</p> <p>And before someone starts to argue that I'm the "worst case" candidate, who "defends the wrong answer furiously" (as poster implied):</p> <ul> <li>I did logging and breakpoint debugging (apparantly unlike original poster, or maybe he just didn't devote enough time for this).</li> <li>I'm not a candidate at all, I'm just trying to use Stackoverflow as intended, providing the best answer I can,if not for benefit of questioneer then others who will be visiting</li> <li>And I do this because from original poster's answer others will get incorrect notion of what synchronization is.</li> <li>And it wasn't me who downvoted question, though ironically original poster downvoted my answer</li> </ul> <p>Not to mention that answering "expert"-level question with incorrect assumptions about basics will not give you right answer.</p> <h2>Synchronization</h2> <p>In the answer poster mentions several times that nuller writes only a single value:</p> <blockquote> <p>but while a nuller only writes a single null, a writer eliminates all nulls in the array.</p> <p>A nuller can - in worst-case - execute without any effect. That is: it writes null to a position in the array that is already null.</p> </blockquote> <p>There's nothing in the code that makes it true. </p> <p>Just leaving synchronization clause don't make thread give up execution for another thread.</p> <p>The sole purpose of synchronization is to guarantee that no two threads will enter same critical section simultaneously, basically it is just a mutex.</p> <p><a href="http://docs.oracle.com/javase/tutorial/essential/concurrency/locksync.html" rel="nofollow noreferrer">Intrinsic Locks and Synchronization</a></p> <p><a href="https://en.wikipedia.org/wiki/Mutual_exclusion" rel="nofollow noreferrer">Mutual exclusion</a></p> <p>There are several ways in java to make thread cease control:</p> <ul> <li><a href="http://docs.oracle.com/javase/7/docs/api/java/lang/Thread.html#yield%28%29" rel="nofollow noreferrer">Thread.yield()</a> - <strong>hints</strong> jvm that it could give execution to another thread. Basically it says to jvm <em>"I did plenty of work here, you may give other guys some processor time if you want to, but I could also go on."</em></li> <li><a href="http://docs.oracle.com/javase/7/docs/api/java/lang/Thread.html#sleep%28long%29" rel="nofollow noreferrer">Thread.sleep()</a> - suspends thread for fixed amount of time.</li> <li><a href="http://docs.oracle.com/javase/7/docs/api/java/lang/Object.html#wait%28%29" rel="nofollow noreferrer">Object.wait()</a> - suspends thread until someone calls notify(which wakes only one waiter)/notifyAll(wakes all waiters) on the same object.</li> <li>there are others but they are similiar and usually based on these</li> </ul> <p><strong>But none of them are used for nullers! So there's absolutely no guarantee that nuller will write only one value.</strong> </p> <p>In fact due to the low computational intensity of one iteration it is more likely that during the execution window that thread recieves it will be able to do several iterations.</p> <p>But again you don't have to believe me, just do logging and debugging. Without actual testing it is all just a demagogy. (UPDATE: note, that logging should be inside synchronization block)</p> <p><img src="https://i.stack.imgur.com/TVPkT.png" alt="Screenshot with output of the program, showing how nuller resets several values in a row then one writer overwrites all values and then nuller resets all elements, leading to the problem described in question"> Notice that first nuller resets several values in a row without being interrupted by writer (contrary to what poster says), then writer overwrites array, and then nuller resets all array (several elements at time), while writers fall to sleep, leading to described problem.</p> <p><strong>UPDATE:</strong> Furthermore author says</p> <blockquote> <p>In addition - and this is the important part - the order of execution with threads is undefined. A naive impression is that which thread is allowed to execute alternates, but this is not the case.</p> </blockquote> <p>However falls himself a victim of that "naive impression" by expecting that after executing nuller that very thread could not be the one entering synchronization.</p> <h2>Probabilty-driven development</h2> <blockquote> <p>Even though a successful write eliminates all nulls, the chance for nullers is always 50% or more</p> </blockquote> <p>That just throws whole probability theory out of the window, not to mention that writing code based on probabilties is really bad idea, especially when it involves multithreading and long execution time (<a href="https://en.wikipedia.org/wiki/Infinite_monkey_theorem" rel="nofollow noreferrer">infinite monkey theorem</a>). </p> <p>Though in one thing author is right: with time there will be more nullers and less writers.</p> <p><strong>UPDATE:</strong> reason why it is important is because you shouldn't talk about multithreading in terms of probabilities at all, because if some scenario is POSSIBLE no matter how improbable it WILL occur at some point. </p> <p>Multithreading should be discussed in terms of worst case scenarios, like author was at the beginning, though he failed to identify actual worst case scenario for nullers, namely when single nuller thread iterates over all array without being interrupted and sets all values to null.</p> <p><strong>UPDATE:</strong> To demonstrate how incorrect 50/50 chances split, consider following simplified example:</p> <p>Lets say we have two threads and we don't set a priority for them, so they both have java.lang.Thread.NORM_PRIORITY by default. Scheduler will attempt divide processor time more or less equally between them to the best of its abilities.</p> <p>However one thread iterates over a big array, and it takes lets say a minute to do so.<br> And another one only sets a single element of the array, and it takes a second.<br> Also both of them synchronize on one object, so they can not execute simultaneously.</p> <p>In the begging scheduler gives control to the first thread and it starts iterating over array, and even if scheduler will attempt to interrupt it and give some time to the second thread, second thread could not proceed, since the first thread already acquired lock.</p> <p>So when minute passes and first thread releases lock, scheduler decides that's enough for him and it have to give a minute or so time for the second thread since they both have equal priority, but because second thread in its critical section takes only one second then it could enter it ~60 times.</p> <p>Of course example is simplified and there will be jitter and sometimes scheduler will be giving unequal chunks of time, but overall it will be trying to give threads amount of processor time according to their priority.</p> <p>So reasoning that "in 50% cases it will be writers entering critical section because there's equal amount of writers and nullers" similiar to an old anecdote:</p> <blockquote> <p><code>- What's the probability that leaving your home you will see an alive dinosaur?</code><br> <code>- 50% either I will see it or not.</code></p> </blockquote>
    singulars
    1. This table or related slice is empty.
    1. POQ&A: Complex deadlock assessment test and how answers are rated
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USelusive-code
    1. USelusive-code
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTDownMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTModeratorReview
    1. COSo I double-checked your answer - again - and again came to the same conclusion: you are wrong. Error 1: Debugging totally screw up thread timing, so any thread-timing-conclusion under debugging is most likely wrong (so does logging). Error 2: synchronized is undefined (my bold text), there is neither a guarantee for what you observed nor can you make a general conclusion out of it. Even my test sometimes start with 20 writes from the same thread in a row. Error 3: you make assumptions on a single test on a single hardware, even your links say that synchronized is implementation dependent.
      singulars
      1. PO
      1. USTwoThe
    2. COI use probability to make it understandable what happens, I say "although no random is involved" right afterwards. The actual chance cannot be calculated, because it is dependent on the implementation of the JVM, OS and hardware, what matters is that with every locked writer, the chance for a nuller increases. By what chance and what are the chances total is irrelevant. Since you concluded out of that, that I encourage writing code based on probabilities I am not sure if you actually understood my explanation correctly.
      singulars
      1. PO
      1. USTwoThe
    3. COIt wasn't a single test (i even posted screenshots several times choosing the one that illustrates better). And, since on my hardware there is a problem with resets of several elements in a row, it IS A PROBLEM that will be present on some other hardware. My main point is that you state that nuller updates only one element at a time, while it is not so. Maybe let's go to the chat (Java)? (Stackoverflow is q/a not a discussion site)
      singulars
      1. PO
      1. USelusive-code
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload