随着多核CPU成为主流，并行程序设计亦成为研究领域的热门。
要想利用多核/多路CPU带来的强大功能，通常使用多线程来开发应用程序。但是要想拥有良好的硬件利用率，仅仅简单的在多个线程间分割工作是不够的。还必须确保线程大部分时间在工作，而不是在等待工作或等待锁定共享数据结构。
在不止一个线程访问共享数据时，所有线程都必须使用同步。如果线程间不进行协调，则没有任务可以真正并行，更糟糕的是这会给程序带来毁灭性的错误。
现在让我们来看一下在.NET和D语言中的标准同步手段-锁定。.NET下我们使用lock关键字，而D语言则使用synchronized关键字。它们在Windows下均使用临界区(Critical Section)来实现，而在Linux下则使用互斥锁(Mutex)来实现。不论其如何实现，它们均强制实行互斥，来确保持有锁的线程对共享数据的独占访问权，以及当其他线程持有锁时，可以看到其对共享数据的修改。
简而言之，在基于锁的多线程编程中，任何针对共享数据，且有可能导致竞争条件的操作，我们都得将其改为原子操作(即连续的，不允许被打断的步骤；上面的lock/synchronized关键字就是我们实现原子操作的手段)。只要我们的线程持有锁，就不必担心其他线程会进来捣乱。
这听起来似乎很不错，我们只要加锁/解锁就可以为所欲为了。然而正是这种为所欲为的事实带来了问题。比如我们的线程持有锁之后，进行了耗时很久的I/O操作。这也就意味着任何其他想持有该锁的线程只能被晾在一边干等了，这时其他线程都处于饥饿状态。假如有更高优先级的线程，此时也只能干巴巴等待了。这就是所谓的优先级倒置。更糟糕的是，我们的线程现在试图霸占另一个锁，而该锁却被另外的线程持有。这个线程这时反过来想要霸占我们线程持有的锁。对于这种情况，我们人类只要互相打个哈哈，咱俩互换锁就OK了。但是CPU却是死脑筋一个，你不给我，我也不给你。结果两个线程都在干等对方，动弹不得。这就是死锁。
此外，如果成千上万个线程在同时竞争锁，我们的CPU就不堪忍受了。因为同步的竞争非常昂贵，所以这会大大降低CPU的吞吐量。
当然，我们也可以使用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; } }
} D Code public class ThreadSafeCounter { private int value; public synchronized int GetValue() { return value; } public synchronized int Increment() { return ++value; } public synchronized int Decrement() { return --value; } } 为了安全实现计数器，我们在每个方法上都加上了lock/synchronized关键字来确保其他线程不能打断。否则，如果两个线程试图同时增加计数，交叉的操作将导致计数只增加了1，而不是2。
现在我们开始真正进入令人激动的Lock-Free世界。
在Lock-Free世界里，最简单也最普遍的一个通用原语是CAS(Compare and Swap)操作。支持并发的现代的处理器都提供了这个原语的硬件实现。比如x86架构下其对应的汇编指令是lock cmpxchg，如果想要64Bit的交换，则应使用lock cmpxchg8b。在.NET中我们可以使用Interlocked.CompareExchange函数，而在D中则可以使用tango.core.Atomic(T).storeIf函数，或者system.threading.Atomic.compareAndSwap(T)模板函数。你可以在浏览代码。该代码基于Tango代码，我将其修改成.NET风格，并添加了atomicAdd模板函数。
CAS原语负责比较某个内存地址处的内容与一个期望值，如果比较成功则将该内存地址处的内容替换为一个新值。这整个操作是原子的。下面的代码模拟了CAS操作的行为(而不是性能特征)。CAS的价值在于它可以在硬件中实现，且是极轻量级的。
.NET代码:
public T CAS < T > ( ref T value, T newValue, T equalTo) where T : class { lock (obj) { if (value == equalTo) value = newValue; return value; } } public int CAS( ref int value, int newValue, int equalTo) { lock (obj) { if (value == equalTo) value = newValue; return value; } } public long CAS( ref long value, long newValue, long equalTo) { lock (obj) { if (value == equalTo) value = newValue; return value; } } D Code public synchronized bool CAS(T)(ref T value, T newValue, T equalTo){ static assert( IsIntegerType!(T) || IsPointerType!(T) ); if (value == equalTo) value = newValue; return value;} AtomicStampedReference类就支持这种方法。我们应当知道能够交换的位越长，ABA发生的几率越低。 基于CAS的并发算法，我们称为Lock-Free算法，因为线程不必再等待锁定。当然，也有很多其他扩展的硬件原语可用于并发算法，比如DCAS，但是目前只有CAS是被广泛实现的。其他如FetchAndAdd，原子队列等则被证明不足以良好的同步两个以上的线程。无论 CAS 操作成功还是失败，在任何一种情况中，它都在可预知的时间内完成。如果 CAS 失败，调用者可以重试 CAS 操作或采取其他适合的操作。下面我们使用CAS原语来实现线程安全的计数器。 public class CASCounter { private int value; public int GetValue() { return value; } public int Increment() { int oldValue; do { oldValue = value; } while (Interlocked.CompareExchange(ref value, oldValue+1, oldValue) != oldValue); return oldValue + 1; } // } D Code public class CASCounter { private int value; public int getValue() { volatile return value; } public int increment() { int oldValue; do { oldValue = value; } while (!Atomic.CompareAndSwap(value, oldValue+1, oldValue)); return oldValue + 1; } // } 如果仔细比对两段代码，可以发现D的实现代码使用volatile关键字，而.NET则没有用。这是因为.NET的已经明确提出原子操作会维持高速缓存一致性，而D的文档规范里则只字未提内存模型，所以加上volatile来确保高速缓存一致性。当然我们也可以使用Interlocked.Increment函数来计数，此处只为了说明CAS的思想。
在Lock-Free的世界里，几乎任何操作都无法原子的完成。只有极少的操作可以原子完成，这一限制使得编程难度大大增加。但是Lock-Free的程序能够确保执行它的所有线程中至少有一个能够继续往下执行。这便意味着有些线程可能会被任意地延迟，然而在每一步都至少有一个线程能够往下执行。因此这个系统作为一个整体总是在“前进”的，尽管有些线程的进度可能不如其它线程来得快。而基于锁的程序则无法提供上述任何保证。
关于Lock-Free的优缺点可以参考。除了文章中所提到的内容外，Lock-Free编程还有三大优点:
- 线程中止免疫:杀掉系统中的任何线程都不会导致其它线程被延迟。
- 优先级倒置免疫：所谓“优先级倒置”就是指一个低优先级线程持有了一个高优先级线程所需要的互斥体。这种微妙的冲突必须由OS内核来解决。而等待无关和锁无关算法则对此免疫。
- 死锁免疫:因为没有使用锁，所以也就不存在死锁的可能。但是乐观的并发，可能会导致活锁。
虽然Lock-Free编程非常困难，但是它通常可以带来比基于锁编程更高的吞吐量。所以Lock-Free编程是大有前途的技术。它在线程中止、优先级倒置以及信号安全等方面都有着良好的表现。
下集预告:并发数据结构.