并发数据结构:迷人的原子

并发数据结构:迷人的原子2011-08-07 博客园 Angel Lucifer随着多核CPU成为主流，并行程序设计亦成为研究领域的热门。

要想利用多核/多路CPU带来的强大功能，通常使用多线程来开发应用程序。但是要想拥有良好的硬件利用率，仅仅简单的在多个线程间分割工作是不够的。还必须确保线程大部分时间在工作，而不是在等待工作或等待锁定共享数据结构。

在不止一个线程访问共享数据时，所有线程都必须使用同步。如果线程间不进行协调，则没有任务可以真正并行，更糟糕的是这会给程序带来毁灭性的错误。

现在让我们来看一下在.NET和D语言中的标准同步手段-锁定。.NET下我们使用lock关键字，而D语言则使用synchronized关键字。它们在Windows下均使用临界区（Critical Section）来实现，而在Linux下则使用互斥锁（Mutex）来实现。不论其如何实现，它们均强制实行互斥，来确保持有锁的线程对共享数据的独占访问权，以及当其他线程持有锁时，可以看到其对共享数据的修改。

简而言之，在基于锁的多线程编程中，任何针对共享数据，且有可能导致竞争条件的操作，我们都得将其改为原子操作（即连续的，不允许被打断的步骤；上面的lock/synchronized关键字就是我们实现原子操作的手段）。只要我们的线程持有锁，就不必担心其他线程会进来捣乱。

这听起来似乎很不错，我们只要加锁/解锁就可以为所欲为了。然而正是这种为所欲为的事实带来了问题。比如我们的线程持有锁之后，进行了耗时很久的I/O操作。这也就意味着任何其他想持有该锁的线程只能被晾在一边干等了，这时其他线程都处于饥饿状态。假如有更高优先级的线程，此时也只能干巴巴等待了。这就是所谓的优先级倒置。更糟糕的是，我们的线程现在试图霸占另一个锁，而该锁却被另外的线程持有。这个线程这时反过来想要霸占我们线程持有的锁。对于这种情况，我们人类只要互相打个哈哈，咱俩互换锁就OK了。但是CPU却是死脑筋一个，你不给我，我也不给你。结果两个线程都在干等对方，动弹不得。这就是死锁。

此外，如果成千上万个线程在同时竞争锁，我们的CPU就不堪忍受了。因为同步的竞争非常昂贵，所以这会大大降低CPU的吞吐量。

当然，我们也可以使用volatile变量来以比同步更低的成本存储共享数据，但是volatile变量相当有局限性。详情请参考谈谈volatile变量。

线程安全计数器经常被拿来做关于多线程并发的案例。我们接下来就来实现一个线程安全的计数器。在谈谈volatile变量中，我们实现了一个这样的计数器，但是其使用场景是在多线程读而少线程写的情况下，下面实现的则是一个一般的线程安全技术器。

.NET代码:

public class ThreadSafeCounter
    {
        private int value;
        private object obj = new Object（）;

        public int GetValue（）
        {
            lock （obj）
            {
                return value;
            }
        }

        public int Increment（）
        {
            lock （obj）
            {
                return ++value;
            }
        }

        public int Decrement（）
        {
            lock （obj）
            {
                return --value;
            }
        }
    }