白话并发冲突与线程同步.doc

猴子抬头道：“我有一个梦，我想我飞起时，那天也让开路，我入海时，水也分成两边，众仙诸神，见我也称兄弟，无忧无虑，天下再无可拘我之物，再无可管我之人，再无我到不了之处，再无我做不成之事，再无我战不胜之物。”今何在摘自悟空传摘要男程序员勿进。（因为可能女程序员拍砖的力道会小些，俺比较能扛得住）并发冲突当一条虫子遇上两只小鸡会发生什么事情？当一条虫子遇上两只小鸡会发生什么事情？可以肯定的是，那条虫子必定会去见上帝啦。无法确定的是，到底是那虫子的上半截先去见上帝，还是下半截先去见上帝？你一准儿在想：“我昨天晚上加班到12点，到现在还晕乎乎的。本想到博客园逛逛，可以暂时忘掉那些复杂多变的需求、防不胜防的Bug以及让人迷惑的办公室政治，没想到却遇到了个精神病，在这儿琢磨这种无聊问题。”相信我，这绝对是性命攸关的重要问题！想想看，如果是虫子的下半截先去见上帝，上帝一准儿会问它：“你叫啥？是怎么死的啊？”，虫子的下半截答道：“我叫虫子甲，是被小鸡乙吃掉的。”于是上帝在他的本子上写到：“虫子甲是被小鸡乙吃掉的。”然后过了一会儿，虫子的上半截也见到了上帝。上帝也问它：“你叫啥？是怎么死的啊？”虫子的上半截答道：“我叫虫子甲，是被小鸡甲吃掉的。”上帝打开他的本子，发现里面已经写了“虫子甲是被小鸡乙吃掉的。”，然而此时虫子的下半截已经不知爬到哪里逍遥去了，无法详细盘问，于是上帝只好选择相信虫子的上半截，把本子上的记录改成“虫子甲是被小鸡甲吃掉的。”但是如果碰巧是虫子的上半截先去见的上帝，最后在上帝的本子上就会写着“虫子甲是被小鸡乙吃掉的”。也就是说，这条可怜的虫虫的死最后会算在哪只小鸡的头上，完全是不可预测的！这个问题不但让上帝颇为头痛，也有可能让程序员丢了性命，欲知后事如何，一段广告过后，马上回来！广告音：“博客园，不是白菜园、不是幼儿园、不是游乐园，更加不是罗卜家园博客园，程序员的网上家园。”1-2-3的超级程序我最近给客户开发了一个非常厉害的程序。classProgramstaticintn=0;staticvoidfoo1()for(inti=0;i1000000000;i+)/10亿inta=n;n=a+1;Console.WriteLine(foo1()completen=0,n);staticvoidfoo2()for(intj=0;j1000000000;j+)/10亿inta=n;n=a+1;Console.WriteLine(foo2()completen=0,n);staticvoidMain(stringargs)foo1();foo2();怎么样？只用了40秒钟，这个程序就计算出了把一个初始为0的变量n累加20亿次1，变量n将等于20亿。什么？你说我是白费CPU不干正经事？这有什么，客户喜欢！顺便说一句，我的电脑是8年前买的，用的是赛扬800的CPU。能更快些么？可是，客户居然嫌它太慢了，并且威胁说如果不能把它压缩到10秒以内就让我去见上帝。我的客户怎么这么狠？唉，打从一开始我就觉得这个总喜欢“击地”的山羊胡老头有些眼熟，这下后悔也晚了，用多线程试试吧。使用多线程现在知道我的程序为啥要使用两个函数“foo1()”和“foo2()”来实现了吧？因为我早就算到了这个情况，为使用多线程做了准备，现在我只要把“foo1()”和“foo2()”分别用两个线程来执行就可以了。（要不怎么说再好的架构师也比不上一个能掐会算的算命先生呢？）classProgramstaticintn=0;staticvoidfoo1()for(inti=0;i1000000000;i+)/10亿inta=n;n=a+1;Console.WriteLine(foo1()completen=0,n);staticvoidfoo2()for(intj=0;j 窗口 反汇编 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-2-3 和比尔盖茨的一些往事在上一篇里我们说道，1-2-3写了一段程序，并且在使用了2个线程分别执行foo1()和foo2()之后，程序的结果就不对了。classProgramstaticintn=0;staticvoidfoo1()for(inti=0;iinta=n;n=a+1;Console.WriteLine(foo1()completen=0,n);staticvoidfoo2()for(intj=0;jinta=n;n=a+1;Console.WriteLine(foo2()completen=0,n);staticvoidMain(stringargs)newThread(foo1).Start();newThread(foo2).Start();究其原因，就是因为Windows总是不问青红皂白随随便便就把我的线程给停掉了。例如，上面的那个程序很可能会以下面的顺序来执行（黄色底色的代码属于第一个线程，绿色底色的代码属于第二个线程）：这样，第一、第二个线程里面的循环各自执行了3次，n的值是3，而不是我们期望的6。所以呢，我就打算建议比尔盖茨在C#里加一个关键字：对foo2()也做同样的修改，这样，就可以确保程序以下图所示的顺序执行了：如果这个建议被微软接受，它将创造两个记录： 1. 它将是C#里面第一个中文关键字。 2. 它将是C#里面最长的关键字。 可是，比尔盖茨听了我的建议之后，却把眉毛皱成了个大疙瘩，叹道：“大哥，不行呀。你知道，Windows里会同时运行着上千个线程，且不说那些居心不良的病毒和木马，就是那些干正经事的线程，谁又能保证在你那个超长关键字里包裹的代码不会运行个二、三十秒？CPU可只有一个，在那个线程运行的二、三十秒里，整个Windows都会一动不动的，不知情的用户还以为是Windows又挂掉了，最后挨骂的可是兄弟我呦！”“不过，”比尔又接着说，“我可以提供另一种方案来达到同样的效果。我可以让线程1里面的指定代码块不执行完，线程2就一直处于阻塞(ThreadState.WaitSleepJoin)状态。”要达到这个效果，需要使用.net里的两个函数。Monitor.Enter(n); / 尝试获取对n的控制权。如果n没主儿，则成功获取了n的控制权；如果n已经有主儿了，则此线程阻塞，死等。Monitor.Exit(n); / 释放对n的控制权。等待着n的那个阻塞中的线程将获取n的控制权，并从阻塞状态变成运行状态。可以把n想像成WC里的一个蹲位，线程1 Enter了之后，其它线程就不能Enter了，只能干等着，直到线程1 Exit，下一个等着的线程才能Enter，之后才能继续办事。如果一个线程Enter了之后迟迟不Exit（例如Enter了之后，发生了异常，比如忘了带SZ），就是所谓的“占着MK不LS”了。（一边吃午饭一边看贴的兄弟对不住啦）使用 Monitor现在就可以在我的代码里使用Monitor了。classProgramstaticintn=0;staticvoidfoo1()for(inti=0;i1000000000;i+)/10亿Monitor.Enter(n);inta=n;n=a+1;Monitor.Exit(n);Console.WriteLine(foo1()completen=0,n);staticvoidfoo2()for(intj=0;j1000000000;j+)/10亿Monitor.Enter(n);inta=n;n=a+1;Monitor.Exit(n);Console.WriteLine(foo2()completen=0,n);staticvoidMain(stringargs)newThread(foo1).Start();newThread(foo2).Start();这段代码很可能会以下图所示的顺序执行（黄色底色的代码属于线程1，绿色底色的代码属于线程2。下图演示了线程1循环2次，线程2循环1次，n的值为3）：如果我们把上图之中与Monitor相关的行和演示线程状态的行去掉，就可以得到下图：怎么样？和我的那个超长关键字的效果一样吧？不过，如果你尝试运行上面那个代码，就会发现它根本无法通过编译！这是因为Monitor.Enter()只接受类型为Object的参数。那么，可不可以写 Monitor.Enter(Object)n); 呢？它确实能够通过编译，但是这样岂不是要装箱20亿次？所以千万别这么写。没法子了，我们只能再声明一个Object类型的变量，专门用于这两个线程的同步。classProgramstaticintn=0;staticobjectmk=newobject();staticvoidfoo1()for(inti=0;i1000000000;i+)/10亿Monitor.Enter(mk);inta=n;n=a+1;Monitor.Exit(mk);Console.WriteLine(foo1()completen=0,n);staticvoidfoo2()for(intj=0;j1000000000;j+)/10亿Monitor.Enter(mk);inta=n;n=a+1;Monitor.Exit(mk);Console.WriteLine(foo2()completen=0,n);staticvoidMain(stringargs)newThread(foo1).Start();newThread(foo2).Start();这段代码在我的赛扬800的机器上运行时间为3分零6秒。lock 关键字在C#里面有一个lock关键字，它其实是一个语法糖。小贴士：在VB里与lock等价的关键字是SyncLock。用法是SyncLock(mk)DimaAsInteger=nn=a+1EndSyncLock死锁还有比占着MK不LS更恶劣的行径么？有，那就是吃着碗里的望着锅里的。在下面的这段代码中，线程1喜欢先占着mk1然后在mk2里办事；线程2呢，喜欢先占着mk2，然后在mk1里办事，要是这两个活宝碰到一起classProgramstaticobjectmk1=newobject();staticobjectmk2=newobject();staticvoidfoo1()for(inti=0;i100;i+)Monitor.Enter(mk1);Console.WriteLine(i=0线程1：先占着mk1，再去mk2里办事。,i);Monitor.Enter(mk2);Console.WriteLine(i=0线程1：进入了mk2，办事,i);Monitor.Exit(mk2);Console.WriteLine(i=0线程1：办完事了，离开mk2,i);Monitor.Exit(mk1);Console.WriteLine(i=0线程1：办完事了，离开mk1,i);staticvoidfoo2()for(intj=0;j 线程2 Enter mk2 - 线程1 想要Enter mk2 发现 mk2 已经被占用，线程1阻塞 - 线程2 想要Enter mk1 发现 mk1 己经被占用，线程2阻塞”这个顺序执行时，线程1等待线程2释放mk2，线程2等待线程1释放mk1，两个线程双双陷入阻塞状态，直到山无棱、天地合这就是死锁。参考文献Jeffrey Richter, CLR via C#, Second Edition. Microsoft Press, 2006.不过这热气是从实在的火里发出来的呢，还是从他的爱情里发出来的呢，他完全不知道。他的一切光彩现在都没有了。这是因为他在旅途中失去了呢，还是悲愁的结果，谁也说不出来。安徒生摘自坚定的锡兵摘要1-2-3翻开那葵花宝典，只见页首赫然写着几个大字：“欲练神功，必先自宫”，旁边几行歪歪扭扭的小字，又不知是哪位前辈高人所写：“在WC里占蹲位的3种方法：1. 如果你只对某个蹲位情有独钟，就要WaitOne()，但是不要忘了ReleaseMutex()，千万别WaitOne()两次只ReleaseMutex()一次（你干这种占着MK不LS的事，憋坏了后来的小朋友怎么办？就算没有小朋友，憋坏了小猫小狗也不好啊）；2. 如果你喜欢讲排场，需要占2个蹲位才肯办事，则要WaitAll(蹲位1, 蹲位2)；3. 如果你觉得随便去哪个蹲位办事都无所谓，那就可以WaitAny(蹲位1, 蹲位2)”。Mutex的WaitOne()函数前几天1-2-3去黑木崖找东方不败玩，听到东方不败抱怨说整天绣花眼睛好累呀，于是1-2-3就给东方不败编了一个活动眼睛的程序。classProgramstaticvoidMain(stringargs)/为截图方便把窗体设小一点Console.WindowWidth=30;Console.BufferWidth=30;Console.WindowHeight=16;Console.BufferHeight=16;Mutexmk=newMutex(false,mymutex);for(inti=0;i1000;i+)mk.WaitOne();for(intj=0;j);Thread.Sleep(100);mk.ReleaseMutex();Thread.Sleep(500);接连运行此程序的两个实例，把它们并排排放在一起（如下图所示），即可看到箭头从左边的窗体“穿越”到右边窗体的效果了。是的，我们需要同步两个进程（中的主线程），这个工作需要交给Mutex。Mutex和Monitor的概念十分相似，只不过Monitor是.net内建的线程同步机制，Mutex是封装了Windows操作系统的线程同步机制；Monitor速度快，Mutex的速度要比Monitor慢很多；Monitor只能用于同步同一进程内的线程；Mutex则可以用于同步隶属于不同进程的线程。Mutex的WaitAll()函数现在我们对WC进行了扩建，把mk增加到两个，可是却遇到了两个讲排场的进程，它们都要同时占两个mk才肯办事，所以运行起来的效果和前一个程序一样。classProgramstaticvoidMain(stringargs)/为截图方便把窗体设小一点Console.WindowWidth=30;Console.BufferWidth=30;Console.WindowHeight=16;Console.BufferHeight=16;Mutexmk1=newMutex(false,mymutex1);Mutexmk2=newMutex(false,mymutex2);Mutexmks=newMutexmk1,mk2;for(inti=0;i1000;i+)Mutex.WaitAll(mks);for(intj=0;j);Thread.Sleep(100);mk1.ReleaseMutex();mk2.ReleaseMutex();Thread.Sleep(500);Mutex的WaitAny()函数看下这个小程序1classProgram23staticvoidMain(stringargs)45/为截图方便把窗体设小一点6Console.WindowWidth=30;Console.BufferWidth=30;7Console.WindowHeight=16;Console.BufferHeight=16;89Mutexmk1=newMutex(false,mymutex1);10Mutexmk2=newMutex(false,mymutex2);11Mutexmks=newMutexmk1,mk2;1213for(inti=0;i1000;i+)1415intindex=Mutex.WaitAny(mks);/返回值为此进程占用的mk在mks里的index16Console.Write(Index:+index.ToString();17for(intj=0;j);20Thread.Sleep(100);212223mksindex.ReleaseMutex();24Thread.Sleep(newRandom().Next(100,3000);252627如果同时运行此程序的两个实例，正如本文摘要里所写的，只要mk1和mk2有一个是空闲的