并发执行中的异步问题处理心得.docVIP

并发执行中的异步问题处理心得 ——高级操作系统学习体会 我在高级操作系统课程中所学到，或者曾学过的许多知识，例如资源管理、任务调度、冲突处理等等，其实并不仅仅限于专业技术上的用途。在日常工作、生活中，我也时常需要利用这些知识解决实际问题。 例如，工作中总有多项任务要我一个人完成，时间有限，忙不过来，因此我必须根据任务的重要性、紧急程度、工作量等因素来确定优先级，从而使任务的加权平均等待时间尽量短。这里，实际上已经用到了操作系统中的CPU调度方法。 就以最近我在程序开发中碰到的异步问题为例，这是应用层面上的程序，跟操作系统层次没有直接的联系，但是异步问题在原理上却是一样的。 我曾编写过大运算量的应用程序，例如直接从电话清单统计成市场部汇总报表的程序。不过以往的程序多数是单线程执行的，而现在多核CPU开始进入主流，并行计算渐成趋势，我的程序要想提高性能，也必须走多线程的方向了。 先简单介绍一下我开发的求64位质数的程序：它的任务是在某一段指定的64位整数区间内，快速地把所有质数一个个找出来，保存到硬盘上。之前我已经开发出单线程的程序，用一般PC机可以平均10秒钟求出一个64位质数。现在我要把它改为多线程并发执行，那么理论上，求一个质数的平均时间，在双核CPU上只要5秒，四核CPU只要2.5秒。 并发执行会遇到异步问题，例如多个线程同时写入文件缓冲区的问题，线程之间如何分工的问题，共享内存数据的问题，等等。处理这些问题需要一定的开销，导致运行速度达不到理论极限。 按照常规的想法，当然就是利用操作系统中的同步方法，在线程需要访问共享资源的地方加入锁。但我在设计算法的过程中就已意识到：同步并不是解决共享冲突的最佳方法，因为同步非常浪费时间，甚至可能抵消并发执行所带来的性能提升。 我把设计思路改为：选择一个好的算法，尽量避免共享冲突，从而规避烦人的异步问题。这样既能够减少出错的可能性，又可以减少同步方法带来的开销，从而提高性能。 首先是并发线程共享内存数据的问题。我的办法是每个线程有自己独立的数据空间，同时有一个共享的只读数据区。只读数据区在程序初始化时写入数据，之后每个线程都只准读取，不能写入。共享只读数据区避免了异步问题，同时又节约了大量内存。 然后是同时写入文件缓冲区的问题。我的办法是每个线程有自己的缓冲区，对应各自的输出文件。这样将会生成多个输出文件，到最后才把它们合并。这样，求质数的过程中就避免了文件缓冲区的写入冲突，而最后的合并过程很快，用单线程即可。 其实，多个输出文件同时写入硬盘，在操作系统的层次上还是有共享冲突问题的，不过操作系统已经解决得很好，应用程序就可以省心了。 最能体现算法设计优劣的，是线程之间如何分工的问题。我发现，线程之间的联系越密切，产生异步问题的机会越多。如果线程能够各干各的事，老死不相往来，完全由算法决定了线程在逻辑上的配合，反而消除了共享冲突，最大限度发挥出并行计算的性能优势。 基于上述理由，我不让多个线程共同检测一个64位奇数是否为质数，而是每个线程各自取一个奇数来检测。这样，单从每个奇数来看，只有一个线程在处理它，就没有异步的问题了。 现在的问题是：指定区间内这么多个奇数，怎么分给多个线程呢？ 首先想到的算法，自然是多个线程按顺序来取，某个线程检测完一个奇数，就取尚未检测的下一个，直到取完为止。但这就意味着每次取一个新的奇数，都必须处理并发线程的异步问题。有多少个奇数，就要做多少次锁的申请、释放操作，对性能影响很大。 我选择了另一种算法：n个线程，每一个都跳开n－1个奇数来取，每个线程所取的奇数互不重复。这就相当于把指定的区间纵向分割成了n份，每个线程都在自己的一份区间里运行，不会干扰邻居，也不必理会其它线程的快慢。如此一来，奇数分配上也避免了异步问题，线程得以全速执行。 经过上述设计，这个多线程求64位质数的程序只剩下一小部分地方有可能出现共享冲突，那就是断点保存，以及每个线程执行到最后，需要判断是否其它线程已经结束，以便进行收尾工作。此处用到了锁，但是对性能影响很小，因为线程并不经常执行到这两个地方。 以上处理异步问题的时候，我发现消除异步问题比采取同步方法更好。这让我想起了一个道理：预防胜于治疗，解决问题的最好办法就是不要出现问题。 由此联想到网上介绍的函数式编程，那是一种尝试从根本上消除异步问题的方法。核心思想是：传统过程式编程之所以有异步问题，是因为基于图灵机，而图灵机保存的状态如果受到并发影响，造成状态不确定，就会有异步问题。 而函数式编程则是基于函数演算，程序中不存在变量，函数返回值只取决于参数，所有状态都体现在函数调用栈中。这样，函数计算的先后顺序无关紧要，于是程序流程也不必固定。函数式编程无须专门编写多线程，直接就可以在单个程序内部实现函数之间的并发。 我的想法是：函数式编程不失