（我认为）互斥体的共识数是 2。
信号量的共识数是多少（如在 pthread_sem_* 中）？
条件变量的共识数是多少（例如在 pthread_cond_* 中）？
问问题
3164 次
4 回答
10
互斥体的共识数是 1。很明显，互斥体对于单个线程是无等待的。从它的定义来看，互斥锁不再对两个线程无等待。因此，共识数 >=1 且 <2，因此它必须为 1。
同样，通过停止一个线程以支持另一个线程来工作的其他同步机制也具有共识编号 1，因此不能用于构造由 2 个线程共享的无等待对象。
于 2009-04-22T13:22:06.980 回答
4
答案取决于互斥体或信号量上支持的操作。如果只支持阻塞锁，则共识数为1。如果一个线程可以尝试锁定互斥锁而不等待，则共识数为2。那是因为如果有两个线程，都可以尝试锁定互斥锁，两者都可以同意哪一个得到它，所以有共识。如果互斥锁可以额外确定，对于任意数量的线程，哪个线程锁定了它，那么共识数是无限的。我认为信号量的情况类似。互斥量相当于带有计数器 1 的信号量。我不认为仅使用更大的计数器就可以达成共识，它仍然归结为相同的操作。Pthreads 支持非阻塞锁但不支持查询，所以答案是 2。
如果任何线程没有等待它，则向条件变量发出信号什么都不做，因此它们的共识编号为 1。
于 2012-01-05T12:41:52.227 回答
3
无限，确定吗？但他们不是免费等待的。
也许我是误会了。您说互斥体的共识数为 2 - 您的来源是什么？它旨在允许任意数量的线程共享资源，并权衡阻塞。
Atomic test-and-set的共识数为 2，但不会阻塞。
澄清一下：信号量、互斥体等是原语，您可以简单地包装共享资源以使其安全（只要您正确执行）。他们可能会阻止，但他们会保证您的数据是安全的。
您引用的论文是关于在不阻塞的情况下保护数据所需的原语，这很难。相同的原语也可能对锁有用，但这只是一个很好的附加功能。
于 2009-04-21T16:07:44.360 回答
0
仅从这篇文章中，您就可以得出结论，信号量的共识数必须小于或等于 2。原因如下：
在文章的第三页，他们说：“fetch&add 操作非常灵活：它可以用于信号量......”。由于我们知道 fetch&add 的共识数等于 2，因此可以使用该论文的定理 1 来证明信号量的共识数必须小于或等于 2。证明如下：
证明
假设存在通过 fetch&add 实现的信号量的无等待实现。进一步假设信号量的共识数大于 2。我们知道 fetch&add 的共识数为 2。从定理 1 我们可以得出结论，在超过 2 个进程的系统中不存在通过 fetch&add 实现的信号量的无等待实现. 这与存在 fetch&add 实现的假设相矛盾。因此，一个信号量的共识数必须小于或等于 2。
量子点
于 2009-04-21T20:29:04.153 回答