线程工作分配的正确性

假设我有一堆工作线程，并且想避免线程确定谁获得什么工作的时间。线程工作分配的正确性

假设每个线程都有一个与它们相关的号码/ ID。有一份工作清单。队列中的每个作业都有一个与其关联的ThreadID。

ThreadID 
1   = Job Available 
0   = Job Finished 
> 1  = Active ==> ThreadID = ID of thread working on the job

对于在工作中工作的线程，它扫描列表并找到第一个ThreadID = 1并尝试执行该任务。

这种方式线程消耗工作。（显然他们会睡觉，需要正确地唤醒，但现在忽略所有这些）

问题是，两个线程可能会同时尝试在同一个工作上工作，这会很糟糕。

为了解决这个问题，每个线程只需将其线程ID分配给线程ID，这将阻止其他线程在作业上工作，除非在写入线程ID之前发生其中一个读取。

ThreadID  Thread 11   Thread 12   .... 
1    ThreadID == 1?       Job available 
           ThreadID == 1?  Job available 
11   ThreadID = 11       Try to take job 
12        ThreadID == 12  Try to take job 
       ThreadID == 11?      Job was taken by another thread 
           ThreadID == 12?  (If no other competing threads then thread 12 got the job)

不确定表格是否有意义，但它显示两个线程正在竞争作业。他们都认为他们有这份工作，但是ThreadId中的任何一个线程实际上都有他们的编号（这将是写入ThreadID的最后一个线程）。

我相信这样的方案不需要锁，是安全的吗？它是否正确？

来源

2013-07-02 user2541029

这一切都取决于您正在使用的编程语言的内存模型来实现这一点。但是，如果使用* [compare和swap]（http://en.wikipedia.org/wiki/Compare-and-swap）*，这应该是非常直接的。 – DaoWen

@DaoWen是的，如果CaS是可用的，但我相信我所说的比较写比较应该没有锁定的工作。 – user2541029

我认为你的“比较写比较”方法，就像你描述的那样，是不够的。看到这个情况：

Thread 0   Thread 1 

reads <empty> 
        reads <empty> 
writes 0 
reads 0 
runs task 
        writes 1 
        reads 1 
        runs task

那交织将有两个线程执行相同的任务。我可能在你的描述中遗漏了某些东西，但是如果我正确理解了你的算法，那么这应该是它的正确性的矛盾。

来源

2013-07-02 06:00:07 DaoWen

是的，你是对的。我最初认为这需要多次比较（循环），我认为最终还是会有这样的缺陷。我想最终需要一个CaS，然后才能让它工作。 – user2541029

@ user2541029 - 是的，你真的需要CaS。毕竟，这就是为什么他们将它添加到所有现代架构！你也可以做一些类似[Peterson的算法]（http://en.wikipedia.org/wiki/Peterson's_algorithm），其中你有不同的线程写入不同的内存段，但这比CaS效率低得多。 – DaoWen

通常，当您有一组作业和多个线程来处理作业时，您可以通过锁定或通过更复杂的非阻塞机制将作业置于线程安全队列中，如.NET 4中的ConcurrentQueue<T>

每个线程从队列中取出一个作业并对其进行处理。如果线程无法完全处理它，您需要一些适当的机制来重新回到队列中。

但是，如果您想继续将线程处理的作业标记为正在被线程处理的方法，那么这样做很简单，但您需要使用锁定来确保一次只有一个线程修改作业。

来源

2013-07-02 03:18:53

这是问题最后部分的重点。通过使用比较写比较应该不需要锁定，我说，我想避免。 – user2541029

@ user2541029，有方法可以设置一个值，只有当它是一个现有的值，它会在你不想锁定的情况下做你想要的。具体取决于您使用的语言。你使用哪种语言？ –

线程工作分配的正确性

回答

相关问题