algorithm - 这种多处理器线程调度算法是否适用于所有情况？

Question

该算法在这篇论文中有描述:Thread Scheduling for Multiprogrammed Multiprocessors .简而言之，计算分布在进程中，每个进程都有一个双端线程来完成这项工作。一个进程可以将线程推送(弹出)到(从)其双端队列的底部，而其他进程可以通过从顶部弹出线程来窃取它。因此，可以通过推送操作动态地创建工作。算法如下。

我的问题是关于 popTop() 工作窃取功能。我认为它不会适用于所有情况。例如，假设一个进程 A 有它的队列 Q 和一个进程 B 试图从 Q 窃取工作，调用 popTop()。还假设此时 B 在 popTop() 的第 2 行之后被抢占并且 localBot = X。如果 A 运行 popBottom() 直到 Q <= X 的底部，当 B 恢复运行时它会得到一个已经被 A 处理过的线程。

我的想法正确吗？我需要验证它，因为我将实现它以在 CUDA 程序中进行工作平衡。

Answer 1

该代码使用 cas()(比较和交换)来尝试停止您所描述的那种事情。如果 popTop() 在第 2 行之后停止，它会在读入 age 和 bot 后停止。如果 popBottom() 然后运行并返回一个线程，它将在 age 内增加字段并使用 cas() 将增加的版本写回内存。现在，当 B 恢复并调用 cas() 时，cas() 指令发现 B 为年龄提供的值与内存中的值不匹配(这意味着对 cas() 的调用不会修改内存)。所以 B 发现 (oldAge == newAge) 并返回 ABORT。在这种情况下，您通常会再试一次并希望下次好运。这篇文章似乎是说调用 yield() 是获得好运所必需的，但在任何情况下，popTop() 都不应该返回其他人已获取的线程。

在 http://en.wikipedia.org/wiki/Compare-and-swap 上当然有一篇关于 cas() 的维基百科文章.

我会将使用锁的并行代码置于串行代码之上一个难度级别，将无锁并行代码置于锁定并行代码之上一个难度级别。我不会编写无锁并行代码，除非我确定我需要性能，并且没有我可以重用的现有已知可信赖代码。我不会相信这样的代码，除非我对其进行了详尽的测试，而且如果可能的话，我实际上更愿意进行模型检查。