《可重复使用的并行数据结构和算法》由会员分享，可在线阅读，更多相关《可重复使用的并行数据结构和算法（22页珍藏版）》请在金锄头文库上搜索。
1、9种可重复使用的并行数据结构和算法目录倒计数锁存(Countdown Latch)可重用旋转等待 (Spin Wait)屏障(Barrier)阻塞队列受限缓冲区(Bounded Buffer)Thin事件无锁定LIFO堆栈循环分块并行分拆总结本专栏并未涉及很多公共语言运行库(CLR)功能的机制问题，而是更多介绍了如何有效使用您手头所具有的工具。身为一名程序员，必须做出很多决策，而选择正确的数据结构 和算法无疑是最常见的，也是最重要的决策之一。错误的选择可能导致程序无法运行，而大多数情况下，则决定了性能的好坏。鉴于并行编程通常旨在改进性能，并且要难于串行编程，因此所作的选择对您程序的成功就更为重
2、要。在本专栏中，我们将介绍九种可重复使用的数据结构和算法，这些结构和算法是许多并行程序所常用的，您应该能够轻松将它们应用到自己的.NET软件中。专栏中每个示例随附的代码都是可用的，但尚未经过完全定型、测试和优化。这里列举的模式虽然并不详尽，但却代表了一些较为常见的模式。如您所见，很多示例都是互为补充的。在开始前，我想还是先介绍一些相关内容。Microsoft ? .NET Framework 提供了几个现有的并发基元。虽然我要为您讲解如何构建自己的基元，但实际上现有基元是足以应付大多数情况的。我只是想说某些可选的方案有时也是有参考价值的。此外，了解这些技巧如何应用于实际操作也有助于加深您对并行
3、编程的整体理解。在开始讲解前，我假定您对现有基元已经有了一个基本的了解。您也可以参阅MSDN杂志2005年8月版的文章 关于多线程应用程序：每个开发人员都应了解的内容”，以全面了解其概念。、倒计数锁存(Co un tdow n Latch)Semaphore之所以成为并发编程中一种较为知名的数据结构，原因是多方面的，而并不只是因为它在计算机科学领域有着悠久的历史(可以追溯到19世纪60年代的操作系统设计)。Semaphore只是一种带有一个计数字段的数据结构，它只支持两种操作：放置和取走(通常分别称为 P和V)。一次放置操作会增加一个 semaphore计数，而一次取走操作会减少一个semap
4、hore计数。当semaphore计数为零时，除非执行一项并发的放置操作使计 数变为非零值，否则任何后续的取走尝试都将阻塞(等待)。这两种操作均为不可再分 (atomic) 操作，并发时不会产生错误，能够确保并发的放置和取走操作有序地进行。Windows具有基础内核和对 semaphore 对象的 Win32支持(请参阅 CreateSemaphore 和相关API)，并且在.NET Framework 中这些对象可以通过 System.Threadi ng.Se map hore 类公 开到上层。Mutex和Monitor 所支持的临界区，通常被认为是一种特殊的semaphore，其计数会在
5、0和1之间来回切换，换句话说，是一个二进制的semaphore o另外还有一种反向semaphore 也是非常有用。也就是说，有时您需要数据结构能够等 待数据结构计数归零。Fork/join式并行模式在数据并行编程中是极为常见的，其中由单个主”线程控制执行若干 辅助”线程并等待线程执行完毕。在这类情况下，使用反向 semaphore会很有帮助。大多数时候，您其实并不想唤醒线程来修改计数。因此在这种情况下，我们将结构称为倒计数锁存”,用来表示计数的减少，同时还表明一旦设置为Sig naled ”状态，锁存将保持sig naled ”(这是一个与锁存相关的属性)。遗憾的是，Win dows和.NE
6、TFramework均不支持这种数据结构。但令人欣慰的是，构建这种数据闭锁并不难。要构建倒计数锁存，只需将其计数器初始值设为n,并让每项辅助任务在完成时不可再分地将n减掉一个计数，这可以通过为减量操作加上锁或调用Interlocked.Decrement来实现。接下来，线程可以不执行取走操作，而是减少计数并等待计数器归零；而当线程被唤醒时，它就可以得知已经有n个信号向锁存注册。在 while (count != 0) 循环中，让等待的线程阻塞通常是不错的选择(这种情况下，您稍后将不得不使用事件)，而不是使用旋转。public class Coun tdow nLatch private int
7、 m_rema in;private Eve ntWaitHa ndle m_eve nt;public Coun tdow nLatch(i nt count) m_rema in = count;m_eve nt = new Manu alResetEve nt(false);public void Sig nal()/ The last thread to sig nal also sets the eve nt.if (In terlocked.Decreme nt(ref m_remai n) = 0)m_eve nt.Set();public void Wait（） m_eve n
8、t.Wait On e（）;这看上去极为简单，但要正确运用还需要技巧。稍后我们将通过一些示例来讲解如何使用这种数据结构。请注意，此处所示基本实现还有很多可以改进地方，例如：在事件上调用WaitOne之前添加某种程度的旋转等待、缓慢分配事件而不是在构造器中进行分配（以防足够的旋转会避免出现阻塞，如本专栏稍后介绍的Th in Eve nt 演示的那样）、添加重置功能以及提供Dispose方法（以便在不再需要内部事件对象时将对象关闭）。】、可重用旋转等待 （Spin Wait）虽然忙碌等待（busy wait in g）更容易实现阻塞，但在某些情况下，您也许的确想在退回到真正的等待状态前先旋转（sp
9、in）段时间。我们很难理解为何这样做会有帮助，而大多数人之所以一开始就避免旋转等待，是因为旋转看上去像是在做无用功；如果上下文切换（每当线程等待内核事件时都会发生）需要几千个周期（在Windows上确实是这样），我们称之为c,并且线程所等待的条件出现的时间少于2c周期时间（1c用于等待自身，1c用于唤醒），则旋转可以降低等待所造成的系统开销和滞后时间，从而提升算法的整体吞吐量和可伸缩性。如果您决定使用旋转等待，就必须谨慎行事。因为如果这样做，您可能需要注意很多问题，比如：要确保在旋转循环内调用Thread.SpinWait |，以提高Intel超线程技术的计算机上硬件对其他硬件线程的可用性；偶
10、尔使用参数1而非0来调用Thread.Sleep ，以避免优先级反向问题；通过轻微的回退（back-off）来引入随机选择，从而改善访问的局部性（假定调用方持续重读共享状态）并可能避免活锁；当然，在单CPU的计算机最好不要采用这种方法（因为在这种环境下旋转是非常浪费资源的）。Spin Wait类需要被定义为值类型，以便分配起来更加节省资源。现在，我们可以使用此算 法来避免前述Cou ntdow nLatch 算法中出现的阻塞。public struct Sp in Wait private int m_co unt;private static readonly bool s_isSingle
11、Proc =（Environmen t.ProcessorC ount = 1）;private const int s_yieldFreque ncy = 4000;private const int s_yieldO neFreque ncy = 3*s_yieldFreque ncy;public int Spin() int oldCo unt = m_co unt;/ On a si ngle-CPU mach ine, we en sure our coun ter is always/ a multiple ofs_yieldFreque ncy ,so we yield eve
12、ry time./ Else, we just increment by one.m_co unt += (s_isS in gleProc ? s_yieldFreque ncy : 1);/If not a multiple ofs_yieldFrequency spin (w/ backoff).int coun tModFreque ncy = m_co unt % s_yieldFreque ncy;if (co un tModFreque ncy 0)Thread.SpinWait(int)(1 + (countModFrequency * 0.05f);elseThread.Sl
13、eep(m_co unt = s_yield On eFreque ncy ? 0 : 1);retur n oldCo unt;private void Yield()Thread.Sleep(m_co unt 0)if (s.Sp in() = s_sp inCount) m_eve nt.Wait On e();不可否认，选择频率和旋转计数是不确定的。与Win32临界区旋转计数类似，我们应该根据测试和实验的结果来选择合理的数值，而且即使合理的数值在不同系统中也会发生变化。例如，根据 Microsoft Media Ce nter 和 Win dows kernel团队的经验， MSDN文
14、档建议临界区旋转计数为 4,000 ，但您的选择可以有所不同。理想的计数取决于多种因素，包 括在给定时间等待事件的线程数和事件出现的频率等。大多数情况下，您会希望通过等待事件来消除显式让出时间，如锁存的示例中所示。您甚至可以选择动态调整计数：例如，从中等数量的旋转开始，每次旋转失败就增加计数。一旦计数达到预定的最大值，就完全停止旋转并立即发出Wait One。逻辑如下所示：您希望立即增加达到预定的最大周期数，但却无法超过最大周期数。如果您发现此最大值不足以阻止上下文切换，那么立即执行上下文切换总的算来占用的资源更少。慢慢您就会希望旋转计数能够达到一个稳定的值。三、屏障(Barrier)屏障，又称集合点，是一种并发性基元，它无需另一主”线程控制即可实现各线程之间 简单的互相协调。每个线程在到达屏障时都会不可再分地发出信号并等待。仅当所有n都到达屏障时，才允许所有线程继续。这种方法可用于协调算法(cooperative algorithms)，该算法广泛应用于科学、数学和图形领域。很多计算中都适合使用屏障，实际上，甚至CLR的垃圾收集器都在使用它们。屏障只是将较大的计算分割为若干较小的协作阶段(cooperative phase)，例如：const int P =；Barrier barrier = new Barrier(P); Data partiti
