白话并发冲突与线程同步(1)

From: http://www.cnblogs.com/1-2-3/archive/2008/05/26/colloquialism-thread-synchronization-part1.html

 

摘要

男程序员勿进。（因为可能女程序员拍砖的力道会小些，俺比较能扛得住……）

并发冲突——当一条虫子遇上两只小鸡会发生什么事情？

当一条虫子遇上两只小鸡会发生什么事情？
可以肯定的是，那条虫子必定会去见上帝啦。
无法确定的是，到底是那虫子的上半截先去见上帝，还是下半截先去见上帝？
你一准儿在想：“我昨天晚上加班到12点，到现在还晕乎乎的。本想到博客园逛逛，可以暂时忘掉那些复杂多变的需求、防不胜防的Bug以及让人迷惑的办公室政治，没想到却遇到了个精神病，在这儿琢磨这种无聊问题。”
相信我，这绝对是性命攸关的重要问题！想想看，如果是虫子的下半截先去见上帝，上帝一准儿会问它：“你叫啥？是怎么死的啊？”，虫子的下半截答道：“我叫虫子甲，是被小鸡乙吃掉的。”于是上帝在他的本子上写到：“虫子甲是被小鸡乙吃掉的。”然后过了一会儿，虫子的上半截也见到了上帝。上帝也问它：“你叫啥？是怎么死的啊？”虫子的上半截答道：“我叫虫子甲，是被小鸡甲吃掉的。”上帝打开他的本子，发现里面已经写了“虫子甲是被小鸡乙吃掉的。”，然而此时虫子的下半截已经不知爬到哪里逍遥去了，无法详细盘问，于是上帝只好选择相信虫子的上半截，把本子上的记录改成“虫子甲是被小鸡甲吃掉的。”
但是如果碰巧是虫子的上半截先去见的上帝，最后在上帝的本子上就会写着“虫子甲是被小鸡乙吃掉的”。
也就是说，这条可怜的虫虫的死最后会算在哪只小鸡的头上，完全是不可预测的！这个问题不但让上帝颇为头痛，也有可能让程序员丢了性命，欲知后事如何，一段广告过后，马上回来！

广告音：“博客园，不是白菜园、不是幼儿园、不是游乐园，更加不是罗卜家园……博客园，程序员的网上家园。”

1-2-3的超级程序

我最近给客户开发了一个非常厉害的程序。

class Program {     static int n = 0;     static void foo1()     {         for (int i = 0; i < 1000000000; i++) // 10 亿         {                 int a = n;                 n = a + 1;         }         Console.WriteLine("foo1() complete n = {0}", n);     }     static void foo2()     {         for (int j = 0; j < 1000000000; j++) // 10 亿         {                 int a = n;                 n = a + 1;         }         Console.WriteLine("foo2() complete n = {0}", n);     }     static void Main(string[] args)     {         foo1();         foo2();     } }

怎么样？只用了40秒钟，这个程序就计算出了把一个初始为0的变量n累加20亿次1，变量n将等于20亿。什么？你说我是白费CPU不干正经事？这有什么，客户喜欢！顺便说一句，我的电脑是8年前买的，用的是赛扬800的CPU。

能更快些么？

可是，客户居然嫌它太慢了，并且威胁说如果不能把它压缩到10秒以内就让我去见上帝。
我的客户怎么这么狠？唉，打从一开始我就觉得这个总喜欢“击地”的山羊胡老头有些眼熟，这下后悔也晚了，用多线程试试吧。

使用多线程

现在知道我的程序为啥要使用两个函数“foo1()”和“foo2()”来实现了吧？因为我早就算到了这个情况，为使用多线程做了准备，现在我只要把“foo1()”和“foo2()”分别用两个线程来执行就可以了。（要不怎么说再好的架构师也比不上一个能掐会算的算命先生呢？）

class Program {     static int n = 0;     static void foo1()     {         for (int i = 0; i < 1000000000; i++) // 10 亿         {                 int a = n;                 n = a + 1;         }         Console.WriteLine("foo1() complete n = {0}", n);     }     static void foo2()     {         for (int j = 0; j < 1000000000; j++) // 10 亿         {                 int a = n;                 n = a + 1;         }         Console.WriteLine("foo2() complete n = {0}", n);     }     static void Main(string[] args)     {         new Thread(foo1).Start();         new Thread(foo2).Start();     } }

你说奇怪不奇怪？一下子结果全都不对了，而且每次执行的结果都不一样！在责怪CPU有Bug、内存有毛病、操作系统中了病毒之前，不妨先来分析一下这段代码是如何执行的。
附言：用了多线程之后，程序执行时间是34秒，所以就算结果正确我的小命也一样不保。

把n加1，统共分3步

在上面那个经过特别设计的例子中，把n加1，统共分3步：
第一步，把n的值保存到a中。
第二步，计算a+1的值。
第三步，把a+1的结果保存到n中。
如果你不能确定上面所说的这三步是不是事实，可以看程序的汇编代码（方法是先在VS2005里单步执行，然后使用菜单“调试 > 窗口 > 反汇编 Ctrl+Alt+D”打开反汇编窗口）。下图截取了汇编代码并使用了相应的伪码，涂了不同的底色以备后用。


正如我们所知道的，CPU只有一个，所以所谓的多个线程“并发执行”只不过是把这些线程排好队，然后让他们一个挨着一个地轮流使用CPU，每个线程只使用很短很短的时间。这样对于人类这样反应迟钝的动物来说，就感觉好像有多个线程在“同时”执行。让我们来看看，当第一个线程执行完“把n的值保存到a中”时，时间到！该轮到别的线程执行了，这时会发生什么事情？这时，你会听到Windows大喝一声：“帮我照顾好我七舅姥爷和他三外甥女——”，然后咔嚓一下就把第一个线程暂停了。所以，如果我们的第一、第二个线程的前三次循环以下图所示的顺序来执行是一点也不奇怪的。（黄色底色的代码属于第一个线程，绿色底色的代码属于第二个线程）


现在，第一、第二个线程里面的循环各自执行了3次，n的值是3，而不是我们期望的6。所以，即使我们的电脑里只有一个CPU（还不是双核的），一样会遇到并发冲突的问题。

真有人在Windows里群殴？

听说有线程发生了并发“冲突”，我们都睁大了眼睛，可实际上并没有什么热闹好看——那两个线程并未打得不可开交。它们虽然访问了同一个全局变量n，但是并未给对方或自己造成什么伤害。我们说这两个线程发生了并发冲突，其实想表达的意思不过是“它们做了我们我们不希望看到的重复工作”而已。

好吧，为了活命，我们必须找到防止这两个线程做重复工作——也就是线程同步——的方法。不过在此之前，先来看看在什么情况下不需要操心线程同步的问题。

不需要线程同步的情况

1. 对n的读取、赋值操作用一条汇编语句就能搞定的时候。

我们把程序稍稍改动一下：


如您所见，“n=n+1” 所对应的汇编代码只有一行 “inc dword ptr ds:[01608A60h]”，也就是通过inc指令直接把CPU的cache里的n的值增加1。CPU的catch真是一个方便的发明呀。不过现在高兴还有些早，因为我们还没有考虑多CPU的情况。要知道现在的服务器大多具有2个以上的CPU，就连PC机都是双核（一块芯片里含有2个逻辑CPU并且有两个cache，就跟安装了两块CPU没啥两样）的了。由于CPU在把cache里的n增加1之后，并不会立即把n的值写入到内存中，所以如果我们在安装了2块CPU的计算机上执行上面那段程序，并且假设第一个线程由CPU1来执行，第二个线程由CPU2来执行，那么这两个线程的前3次循环完全有可能像下面这样：


非常不幸地，n的值是3而不是我们期望的6。CPU cache这个方便的发明现在成了烫手的山芋。不过如果你在装有Intel的双核CPU的计算机上运行上面的代码，会发现结果仍然非常正确，似乎上图所示的麻烦事并没有发生，这是为什么呢？这是因为x86架构的CPU非常地道，它在确保cache一致性方面做了很多努力。
====== 2008-5-26更新 ======
今天又在Intel的双核CPU上测试了一下上面那个代码，发现居然不管加不加volatile关键字，结果都不对！！！不知道是不是我对volatile的理解有误，肯请高手指点。用下面的Interlocked.Increment()结果是正确的。没有认真测试我的代码，十分抱歉！
=======================
坏消息是：不是所有的CPU都像x86 CPU这么地道（例如IA64，由于性能等方面的考虑不会在cache一致性方面多做努力）；而好消息是：像IA64这样不地道的CPU都提供了volatile read（强制从内存读取）和volatile write（强制写入内存）操作。相应地，.net提供了volatile关键字。所以，我们只要在定义n的时候加上volatile关键字就可高枕无忧了。

附言 在我的赛扬800 CPU上，不管加不加volatile关键字，程序执行的时间都在14.5秒左右。
你可能不喜欢在声明变量的时候使用volatile关键字，因为这样一来不管是不是使用了多线程、不管是读取还是写入n都会被强制刷新内存；而且如果你把n按引用传递给方法，例如写 int.TryParse("123", out n)，volatile关键字将失效。所以.net提供了另一种方案：你可以在声明变量的时候不使用volatile关键字，而在读取和写入n的时候使用Thread.VolatileRead(...)和Thread.VolatileWrite(...)这两个静态方法。另外，还有一个Thread.MemoryBarrier() 函数的功能也是将cache中的数据保存到内存中。

你也可以使用更高级别的互锁方法，例如Interlocked.Increment()。当线程调用Interlocked类中的那些互锁方法时，CPU会强制cache的一致性。事实上，所有的线程同步锁（包括Monitor, ReaderWriterLock, Mutex, Semaphore, AutoResetEvent 以及 ManualResetEvent 等）都会在内部调用互锁方法。

这段程序在我的赛扬800 CPU上运行时间为60秒。

2. 你加m我加n，各加各的

消除线程间的共享资源，无疑是个釜底抽薪的办法。


这个方法虽然很酷，但是却不怎么实用。因为我很难防止别的程序员用两个线程执行foo1()。

3. 只有一个线程对n赋值，其它线程只是读取n值，并且不在乎n值是不是最新的

例如下面这段程序，foo1()负责累加n值，foo2()负责读取进度并且将进度显示给用户。用户呢，看进度只不过是想确定foo1()确实在努力工作中，而不是在炒股、聊QQ、上不良网站或写博客而已。


本篇到此结束，Sleep(1千万毫秒)先。下篇将介绍线程同步的方法。

附言 家里养了2只小鸡，白天的时候就把它们放到窗台上晒太阳。有时候，它们发现了好吃的东西，就会你追我赶的，从窗台的一头跑到另一头，然后扑腾两下小翅膀，作刹车状，再抡圆了小爪子飞快地跑回来，好像在开运动会，十分有趣。
看着两团淡黄色的绒球在窗台上啄食，忽感生命是如此美丽，同时又是如此的脆弱和渺小。
祝 身在震区的人都更坚强、好运！

参考文献

Jeffrey Richter, CLR via C#, Second Edition. Microsoft Press, 2006.
Thomas et al, 孙勇等 译, Programming Ruby 中文版。电子工业出版社，2007.

评论

1 楼 liudaoru 2009-02-24  

同步的关键是原子操作，i++/i--之类的操作并不是原子操作，所以这是不可行的。