非阻塞算法和互斥

Question

维基百科说：

非阻塞算法确保 线程共享 资源竞争没有自己的执行 无限期相互排斥 推迟。

如何确保在多个线程需要访问某个临界区时实现这个目标？

Answer 1

请原谅的文章，但是，往往是我的写作风格。

非阻塞算法有各种形状，但基本思想是构造算法，使得您可以在一个或多或少的确定性步骤中完成，而不是无限期地被锁定停止。如果您的操作可能很耗时，有时您可以做的最好的做法是确保您的线程有其他工作来推进程序的整体操作。

并非所有的算法都是适用于非阻塞方法，许多无阻塞方法有小的临界区在其中，因此不会严格地说无阻塞，但在实践中表现得如此。在实现任何类型的并发时都要用脑，因为它是调试的熊，无论你是否是有经验的程序员。

- =无阻塞算法= -

原子算法执行中发生的不能被中断的单个步骤的更新。一个简单的例子是使用++或+ =递增一个值，当更新发生时，它逐字地归结为单个CPU指令，因此将完成而没有被中断的可能性，并且如果多处理中断了CPU，则CPU将修复它更新。我不太清楚在一条CPU指令触及多个数据段时，这会延伸到SIMD指令的范围。

如果您有一种算法不需要返回值，那么您可以使用生产者/消费者队列系统，其中只有队列是基于锁的，或者可能使用原子更新将项插入队列。无论哪种情况，队列都会很快更新，并且在消费者线程处理积压时，控制权会返回给调用者。网络和磁盘写入通常具有这种变化。

如果需要返回值，在操作完成时的回调可以通知你的线程，或者一些新的数据可为您处理。最理想的是，您还有其他事情要做，而不是简单地等待回调。

CAS算法，其中读取和更新确保在首次完成时获胜系统是确保进度的另一种方式，但中止需要时间，因此如果算法需要重试，可能会创建非确定性完成时间当发生中止时。数据库使用一种称为乐观锁定的事务完成类型的CAS。当争用率较低时，或者在争用需要通知用户并收集其他输入的情况下，这种方式效果最佳。

- =阻止算法= -

阻塞算法块中的所有的向前进展，但螺纹（或多个）单个或多个小试图在共享资源上进行操作。如果操作冗长，这可能会导致严重的延迟，所以任何阻塞算法的目标都应该是将发生争用的关键部分减少到尽可能小的整体算法的一小部分。执行此操作的数据库事务使用悲观锁定。

- =死锁和活锁= -

死锁是两个线程分别阻断彼此，通常是因为每个持有锁的其它想要的。

活锁可能发生在两个线程再次希望访问其他控件的资源的情况下，或者两个线程完全由它们相互发送的数据使用的情况。在任何一种情况下，该算法都会不断等待，直到取得进展，但是这两个（或者更多）线程在不进行真正的前进过程的情况下继续旋转。

- =重要性= -

为什么这些重要？任何并发的主要问题是可能出现不可预知的状态，因为两个线程在相同的数据上运行而不考虑彼此的变化。为了防止这种情况发生，可以使用阻塞和非阻塞算法，但如果出错，最终可能导致死锁，活锁或数据损坏。

我希望这强调并发问题同时存在于阻塞和非阻塞算法中，无论您选择的杀死并发野兽的方法如何，您都必须密切关注您的程序的结构使用方式，或者提供共享资源。

Answer 2

非阻塞算法，充分利用中科院：Java Concurrency: CAS vs Locking