平行，因为有异常的行为

本文关键字：异常 因为 平行 | 更新日期: 2023-09-27 17:56:58

我正在尝试将这个主要筛分功能转移到使用Parallel.For，以便它可以利用多个内核。

但是，当我运行它时，b 变量的值似乎随机跳跃甚至根本没有变化，尤其是对于较高的 To 值。

static List<long> Sieve(long To)
{
    long f = 0;
    To /= 2;
    List<long> Primes = new List<long>();
    bool[] Trues = new bool[To];
    if (To > 0)
        Primes.Add(2);
    long b = 0;
    Parallel.For(1L, To, a =>
    {
        b++;
        if (Trues[b])
            return;
        f = 2 * b + 1;
        Primes.Add(f);
        for (long j = f + b; j < To; j += f)
            Trues[j] = true;
    });
    return Primes;
}

这是怎么回事，我怎样才能阻止这种情况发生？

平行，因为有异常的行为

b在

线程之间共享。如果多个线程同时撞击该糟糕的变量，您期望会发生什么？

似乎b和a在您的代码中总是相等的（或相差一个）。使用 a .并同步对所有其他共享状态（如列表）的访问。

欢迎来到多线程的奇妙世界。

马上，我可以看到循环的每次迭代都会执行b++，然后在整个过程中使用b。这意味着循环的每次迭代都将在所有其他迭代中修改b的值。

您可能想做的是使用内联函数中提供的a变量，它完全符合您似乎试图用b执行的操作。如果情况并非如此，那么您应该考虑锁定b并将其值复制到局部（每次迭代）变量，然后再对其进行操作。

试试这个，让我知道这是否是你想做的：

static List<long> Sieve(long To)
{
    To /= 2;
    List<long> Primes = new List<long>();
    if (To > 0)
        Primes.Add(2);
    Parallel.For(1L, To, a =>
    {
        long f = 2 * a + 1;
        Primes.Add(f);
    });
    Primes.Sort();
    return Primes;
}
您

在这里面临的问题称为race conditions，这是当多个CPU内核将同一变量加载到各自的缓存中，对其进行处理，然后将值写回RAM时发生的情况。显然，写回 RAM 的值可能在此期间已经很旧了（例如，当内核在被另一个值覆盖之前加载变量时）

首先：我不会使用b++而是int i = Interlocked.Increment(ref b);。互锁。增量可确保没有 2 个线程尝试同时递增相同的值。结果是递增的值，该值将保存到变量i中。这非常重要，因为您需要该值在 for 循环的每次迭代中保持不变，否则这是不可能的，因为其他线程将递增此变量。

接下来是变量f和a（定义为 For-iterator）。忘记f，改用a。

f = 2 * b + 1; // wrong
a = 2 * b + 1; // correct

最后：System.Collections.Generic.List 是 NOT，我再说一遍（因为它很重要）不是线程安全的。有关更多详细信息，请参阅 http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx。

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
}

lock 关键字只接受引用类型的变量作为参数，这是因为锁定变量不会阻止另一个线程访问它。相反，您可以将其想象为在引用顶部设置一个标志，以便向其他线程发出信号I'm working here, please do not disturb!

当然，如果另一个线程尝试访问Primes而事先要求锁定它，则该线程仍然可以访问该变量。

不过，您应该已经学习了所有这些，因为并行 Prime Sieve 是第一次学习多线程时最常见的初学者练习之一。

编辑：

完成上述所有步骤后，程序不应运行;但是，这并不意味着解决方案是正确的，或者您将获得加速，因为您的许多线程将执行重复工作。

假设Thread a有责任标记 3 的每个倍数，而Thread n有责任标记 9 的倍数。当按顺序运行时，当Thread n开始处理 9 的倍数时，它将看到 9 已经是另一个（素数）的倍数。但是，由于您的代码现在是并行的，因此不能保证在Thread n开始工作时将标记 9。更不用说 - 因为 9 可能没有标记 - 可能会被添加到质数列表中。

因此，您必须按顺序找到 1 和 To 平方根之间的所有素数。为什么是To的平方根？这是你必须自己找出来的。

一旦你找到了从1到To的平方根的所有素数，你就可以启动你的平行素数筛，以便使用之前找到的所有素数找到其余的素数。

最后值得注意的一点是，只有在填满Trues之后才能建造Primes。这是因为：

1. 您的线程只需要将 2 的倍数处理到To的平方根，因此在当前实现中不会再向根以外的Primes添加任何元素。

2.如果您选择让您的线程超出根，您将面临一个问题，即您的一个线程将在另一个线程将该数字标记为非素数之前不久将一个非素数添加到Primes，这不是您想要的。

3.即使你很幸运，Primes的所有元素确实都是1到To之间的质数，它们也不一定是有序的，需要Primes先排序。

相关文章：