Databases
StackOverflow2013
Postsdbo
POQ&A: Complex deadlock assessment test and how answers are rated
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POQ&A: Complex deadlock assessment test and how answers are rated
    primarykey
    data
    text
    <p>The following code has been constructed for a test. In this test the reader is asked to explain why the code will enter a deadlock less then a second after starting the code. </p> <p>Can anyone please <strong>exactly</strong> describe what causes the deadlock in this code?</p> <pre><code>public class Test { static class FailerThread implements Runnable { final Object[] objects; final Random random; final int number; public FailerThread(final Object[] objects, final int number) { this.objects = objects; this.random = new Random(); this.number = number; } @Override public void run() { final boolean isWriter = number % 2 == 0; int index = random.nextInt(objects.length); try { while (Thread.interrupted() == false) { synchronized (objects) { if (isWriter) { while (objects[index] == null) { System.out.println(number + ": Index " + index + " is null, waiting..."); objects.wait(); } for (int copyIndex = 0; copyIndex &lt; objects.length; ++copyIndex) { if (objects[copyIndex] == null) { objects[copyIndex] = this.objects[index]; } } objects.notifyAll(); } else { objects[index] = null; } } ++index; if (index &gt;= objects.length) { index = 0; } } } catch (InterruptedException e) { } } } public static void main(String[] args) throws InterruptedException { final Object[] objects = new Object[10]; for (int i = 0; i &lt; objects.length; ++i) { objects[i] = new Object(); } final int NUM_THREADS = 32; final ExecutorService executor = Executors.newFixedThreadPool(NUM_THREADS); for (int i = 0; i &lt; NUM_THREADS; ++i) { executor.execute(new FailerThread(objects, i)); } } } </code></pre> <p><strong>Edit:</strong> The official answer to this test (similar to what Tudor wrote, just more detailed)</p> <p>The above construct deadlocks, because at some point all "writers" wait on a null, but since those writers are the only one who could release them, they will hang indefinitely. The more important question however is: why?</p> <p>At a first glance the code looks like those writers are dominant. Each loop a single thread (either writer or nuller) is selected to process on the array, but while a nuller only writes a single null, a writer eliminates all nulls in the array. So one would expect that deadlocking - while possible - is very unlikely (yet surprisingly the code deadlocks within a second). On a closer look however this assumption turns out to be false, because we are dealing with threads.</p> <p>Given enough execution time, in a multi-threaded application what matters is: which part of the code is actually able to block? Let's take a look at the possible worst-case scenarios for writers/nullers:</p> <ul> <li><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></li> <li><p>A writer can - in worst-case - block indefinitely.</p></li> </ul> <p>Furthermore at the beginning of the synchronized block a (more or less) random candidate is chosen to enter. At the beginning this is 50% for both writers and nullers, however for each blocked writer, the chances favor into the direction of the nullers. Even though a successful write eliminates all nulls, the chance for nullers is always 50% or more, because the chance for writers (thanks to blocking) constantly diminishes. So from a threaded perspective the nullers are actually the dominant part, as the entire system is designed to favor them as candidates for the synchronized block.</p> <p>In addition - and this is the important part - <strong>the order of execution with threads is undefined</strong>. A naive impression is that which thread is allowed to execute alternates, but this is not the case. A synchronized block has no preferences, and which thread gains access is undefined (one could say: completely random, although no random is involved). So with all 16 threads waiting on the synchronized, the chance that within 20 executions threads alternate perfectly, is exactly equal to the chance that 20 writers or 20 nullers are called in a row. But since nullers are dominant (20 writers just do nothing), calling 20 nullers in a row is almost guaranteed to set the entire array to null, which then causes any subsequent writers to block indefinitely.</p> <p>If you add more logging output to the code to see which thread is actually selected, you will very soon see something like 10 or more nullers being called in a row, usually within the first 200 loops. Right after that the system hangs.</p> <p><strong>Why this question was asked</strong></p> <p>I am currently developing a test set for assessments for expert Java programmers and with all code written it eventually needs to be tested. The good news: it succeeded. ;)</p> <p>Now before you complain about improper use of StackOverflow: please see this one as Q&amp;A. And there is much to learn from this example for real implementation of multi-threaded architecture. As this is an expert level question - as expected - not many people were able to answer it nor even understand it. The good thing however about expert level questions is, that you can as well learn much from expert level answers. That is why I included the fully detailed answer.</p> <p><strong>How the candidate is rated</strong></p> <p>Foreseeing that some people will consider this question to be way too difficult for an assessment test, and to give your the viewpoint of the tester, this is how candidates will be rated:</p> <p>Yes the question is too difficult, and no one is expected to find the correct answer during the test, what matters is how they approach the problem. Every day a programmer encounters tasks that he/she has never solved before and does not know how to solve right away, therefore having a good skill in problem-solving is what matters in this business. No one can know everything, but everyone can learn.</p> <p>In general there are 4 possible results:</p> <ol> <li><p>The candidate does not know the answer and says so. This is a good beginner level, because the candidate has the strength to admit that during a stressful test situation. A good student is the one that listens, and therefore can be taught.</p></li> <li><p>The candidate does now know the answer, but either blames the "bad" question (aka down-vote) or comes up with a wrong answer, that he/she then defends furiously. This is basically the worst-case candidate: he is at beginner/intermediate level, but considers himself an expert and therefore refuses to learn and will be stuck at this level. In a team this candidate will either block advancement of the team (if they believe him to be the "expert") or become a nuisance soon.</p></li> <li><p>The candidate comes up with a (more or less correct) answer, and uses a methodical approach to find it. This is a good intermediate/expert level candidate. He/She has developed a methodical approach to challenging tasks and depending on the answer can be expected to advance even further.</p></li> <li><p>The candidate uses a methodical approach and comes up with a correct answer. This is the best possible result, but encountered probably only as one in a million.</p></li> </ol>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USTwoThe
    1. USTwoThe
    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. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POQ&A: Complex deadlock assessment test and how answers are rated
      1. This table or related slice is empty.
      1. VTDownMod
    2. VO
      singulars
      1. POQ&A: Complex deadlock assessment test and how answers are rated
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POQ&A: Complex deadlock assessment test and how answers are rated
      1. This table or related slice is empty.
      1. VTDownMod
    1. COQuestions must demonstrate a minimal understanding of the problem being solved. Include your thoughts so far and specific questions on what you don't understand.
      singulars
      1. POQ&A: Complex deadlock assessment test and how answers are rated
      1. USJohn Kugelman
    2. COThe question is obvious, the code is perfectly describing the problem and my thoughts so far could be wrong as much as they could be correct. This is not a coding issue, but a logic issue.
      singulars
      1. POQ&A: Complex deadlock assessment test and how answers are rated
      1. USTwoThe
    3. COCould it be that the notifyAll call is inside the if(isWriter) condition? If only indices corresponding to null writers are used (which I think could happen) notifyAll will never be called.
      singulars
      1. POQ&A: Complex deadlock assessment test and how answers are rated
      1. USbroncoAbierto
 

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