Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>The problem you are facing here is called <code>race conditions</code>, it's what happens when multiple CPU cores load the same variable into their respective cache, work on it, then write the value back to RAM. Obviously, the value that's written back to RAM may already be old in the meantime (like when a core loads the variable right before it's overwritten with another value)</p> <p>First of all: I wouldn't use <code>b++</code> but <code>int i = Interlocked.Increment(ref b);</code> instead. Interlocked.Increment ensures that no 2 threads attempt to increment the same value at the same time. The result is the incremented value which will be saved into the variable <code>i</code>. This is <strong>very</strong> important, because you will need that value to remain constant for every iteration of your for-loop, which would be impossible otherwise, since other threads will be incrementing this variable.</p> <p>Next is your variable <code>f</code> and <code>a</code> (defined as the For-iterator). Forget <code>f</code>, use <code>a</code> instead.</p> <pre><code>f = 2 * b + 1; // wrong a = 2 * b + 1; // correct </code></pre> <p>Lastly: System.Collections.Generic.List is <strong>NOT</strong>, I repeat (because it's important) <strong>NOT</strong> thread safe. See <a href="http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx" rel="nofollow">http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx</a> for more details.</p> <pre><code>Primes.Add(f); // will likely break something lock (Primes) // LOCK the list { Primes.Add(a); // don't forget, we're using 'a' instead of 'f' now } </code></pre> <p>The <code>lock</code> keyword accepts only reference-type variables as argument, that is because locking a variable does <strong>NOT</strong> prevent another thread from accessing it. Instead, you can imagine it as setting a flag on top of the reference, in order to signal other threads <code>I'm working here, please do not disturb!</code></p> <p>Of course, if another thread attempts to access <code>Primes</code> without asking to lock it beforehand, the thread will still be able to access the variable.</p> <p>You should've learned all of this though, since the Parallel Prime Sieve is one of the most common beginner exercises when first learning about multithreading.</p> <p><strong>EDIT:</strong></p> <p>After all the above steps are done, the program shouldn't run amok; <strong>however</strong> this does not mean that the solution will be correct, or that you'll have gained a speedup, since many of your threads will be doing duplicate work.</p> <p>Assume <code>Thread a</code> is given the responsibility to mark every multiple of 3, while <code>Thread n</code> is given the responsibility to mark the multiples of 9. When run sequentially, by the time <code>Thread n</code> begins processing the multiples of 9, it will see that 9 is already a multiple of another (prime) number. However, since your code is now parallel, there is <strong>no guarantee</strong> that 9 will be marked by the time <code>Thread n</code> begins its work. Not to mention that - since 9 may not be marked - might be added to the list of prime numbers.</p> <p>Because of this, you have to <strong>sequentially</strong> find all prime numbers between 1 and the square root of <code>To</code>. Why the square root of <code>To</code>? That's something you'll have to find out yourself.</p> <p>Once you have found all prime numbers from 1 to the square root of <code>To</code>, you can start your parallel prime sieve in order to find the rest of the primes, using all primes found previously.</p> <p>One last noteworthy point would be, that <code>Primes</code> should be built only <strong>after</strong> <code>Trues</code> has been filled. That's because:</p> <p><strong>1.</strong> Your threads will only have to process the multiples of 2 to the square root of <code>To</code>, thus will in the current implementation not add any more elements to <code>Primes</code> beyond the root.</p> <p><strong>2.</strong> If you choose to have your threads go beyond the root, you'll face the problem, that one of your threads will add a non-prime number to <code>Primes</code> shortly before another thread marks that number as non-prime, which is not what you want.</p> <p><strong>3.</strong> Even in the event that you were lucky and all elements of <code>Primes</code> are indeed all prime numbers between 1 and <code>To</code>, they may not necessarily be in order, requiring <code>Primes</code> to be sorted first.</p>
    singulars
    1. This table or related slice is empty.
    1. POParallel.For having unusual behaviour
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USNolonar
    1. USNolonar
    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. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. CONone of the points here address the fundamental algorithmic problem that each iteration is dependent on the previous iteration having executed. The basic algorithm needs to change to remove that dependency. Using a thread save structure and synchronizing access to `b` won't fix all of that.
      singulars
      1. PO
      1. USServy
    2. CO@Servy You are right; but the question was "why do my variables misbehave and how do I stop this", not "why does my algorithm not work". The other problem involves sequentially solving the sieve for sqrt(To) and use the result of that as a base for all other threads to work on. Should I edit my answer to accommodate this part as well?
      singulars
      1. PO
      1. USNolonar
 

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