 |
|
|
|
[原创] 超级质数机：并发执行中的异步问题处理心得
[ 2007-09-01 03:04:14 ]
引言/提要：知识是死的，人是活的，有时候学到的东西并不直接在现实中发挥作用，而是一种厚积薄发的潜在能量。
关键词：并行计算，共享冲突，核心算法，核心技术
我在高级操作系统课程中所学到，或者曾学过的许多知识，例如资源管理、任务调度、冲突处理等等，其实并不仅仅限于专业技术上的用途。在日常工作、生活中，我也时常需要利用这些知识解决实际问题。
例如，工作中总有多项任务要我一个人完成，时间有限，忙不过来，因此我必须根据任务的重要性、紧急程度、工作量等因素来确定优先级，从而使任务的加权平均等待时间尽量短。这里，实际上已经用到了操作系统中的CPU调度方法。
就以最近我在程序开发中碰到的异步问题为例，这是应用层面上的程序，跟操作系统层次没有直接的联系，但是异步问题在原理上却是一样的。
我曾编写过大运算量的应用程序，例如直接从电话清单统计成市场部汇总报表的程序。不过以往的程序多数是单线程执行的，而现在多核CPU开始进入主流，并行计算渐成趋势，我的程序要想提高性能，也必须走多线程的方向了。
先简单介绍一下我开发的求64位质数的程序：它的任务是在某一段指定的64位整数区间内，快速地把所有质数一个个找出来，保存到硬盘上。之前我已经开发出单线程的程序，用一般PC机可以平均10秒钟求出一个64位质数。现在我要把它改为多线程并发执行，那么理论上，求一个质数的平均时间，在双核CPU上只要5秒，四核CPU只要2.5秒。
并发执行会遇到异步问题，例如多个线程同时写入文件缓冲区的问题，线程之间如何分工的问题，共享内存数据的问题，等等。处理这些问题需要一定的开销，导致运行速度达不到理论极限。
按照常规的想法，当然就是利用操作系统中的同步方法，在线程需要访问共享资源的地方加入锁。但我在设计算法的过程中就已意识到：同步并不是解决共享冲突的最佳方法，因为同步非常浪费时间，甚至可能抵消并发执行所带来的性能提升。
我把设计思路改为：选择一个好的算法，尽量避免共享冲突，从而规避烦人的异步问题。这样既能够减少出错的可能性，又可以减少同步方法带来的开销，从而提高性能。
首先是并发线程共享内存数据的问题。我的办法是每个线程有自己独立的数据空间，同时有一个共享的只读数据区。只读数据区在程序初始化时写入数据，之后每个线程都只准读取，不能写入。共享只读数据区避免了异步问题，同时又节约了大量内存。
然后是同时写入文件缓冲区的问题。我的办法是每个线程有自己的缓冲区，对应各自的输出文件。这样将会生成多个输出文件，到最后才把它们合并。这样，求质数的过程中就避免了文件缓冲区的写入冲突，而最后的合并过程很快，用单线程即可。
其实，多个输出文件同时写入硬盘，在操作系统的层次上还是有共享冲突问题的，不过操作系统已经解决得很好，应用程序就可以省心了。
最能体现算法设计优劣的，是线程之间如何分工的问题。我发现，线程之间的联系越密切，产生异步问题的机会越多。如果线程能够各干各的事，老死不相往来，完全由算法决定了线程在逻辑上的配合，反而消除了共享冲突，最大限度发挥出并行计算的性能优势。
基于上述理由，我不让多个线程共同检测一个64位奇数是否为质数，而是每个线程各自取一个奇数来检测。这样，单从每个奇数来看，只有一个线程在处理它，就没有异步的问题了。
现在的问题是：指定区间内这么多个奇数，怎么分给多个线程呢？
首先想到的算法，自然是多个线程按顺序来取，某个线程检测完一个奇数，就取尚未检测的下一个，直到取完为止。但这就意味着每次取一个新的奇数，都必须处理并发线程的异步问题。有多少个奇数，就要做多少次锁的申请、释放操作，对性能影响很大。
我选择了另一种算法：n个线程，每一个都跳开n－1个奇数来取，每个线程所取的奇数互不重复。这就相当于把指定的区间纵向分割成了n份，每个线程都在自己的一份区间里运行，不会干扰邻居，也不必理会其它线程的快慢。如此一来，奇数分配上也避免了异步问题，线程得以全速执行。
经过上述设计，这个多线程求64位质数的程序只剩下一小部分地方有可能出现共享冲突，那就是断点保存，以及每个线程执行到最后，需要判断是否其它线程已经结束，以便进行收尾工作。此处用到了锁，但是对性能影响很小，因为线程并不经常执行到这两个地方。
以上处理异步问题的时候，我发现消除异步问题比采取同步方法更好。这让我想起了一个道理：预防胜于治疗，解决问题的最好办法就是不要出现问题。
由此联想到网上介绍的函数式编程，那是一种尝试从根本上消除异步问题的方法。核心思想是：传统过程式编程之所以有异步问题，是因为基于图灵机，而图灵机保存的状态如果受到并发影响，造成状态不确定，就会有异步问题。
而函数式编程则是基于函数演算，程序中不存在变量，函数返回值只取决于参数，所有状态都体现在函数调用栈中。这样，函数计算的先后顺序无关紧要，于是程序流程也不必固定。函数式编程无须专门编写多线程，直接就可以在单个程序内部实现函数之间的并发。
我的想法是：函数式编程不失为一种解决异步问题的好思路，但在实际应用中很难完全抛弃过程式编程，例如输入输出函数内部，始终存在时序关系。我设想一种原子函数的概念，原子函数内部允许过程式编程，但所有数据被封装在函数内部，不准共享，只有返回值可以传递到函数外部。而且，在一次完整的程序运行过程中，同一个原子函数同样的参数，不管调用多少次，只能有同一返回值。
这样，既保留了过程式编程的功能，又得到了函数式编程能够安全地并发执行的好处，一举两得。
更进一步，参照我在求质数程序中只读共享数据区的做法，可以允许所有函数以只读方式访问共享数据结构。这些数据架构在初始化时一次性写入，之后不再改变。如此一来，函数式编程在维持了并发执行的安全特性同时，其程序设计方法和传统过程式编程又拉近了一步。
如果在操作系统中，也能够这样消除共享冲突、避免异步问题就好了。不过操作系统总是要负责资源的管理和分配，而资源通常是有限的，所以很难从根本上防止共享冲突。但无论如何，好的设计和算法所起的作用相当大，而且越是底层，效果越明显，操作系统层就比应用软件层更容易影响性能。
虽然日常工作中很少真正涉及到操作系统的核心部分，但这门课程的实用价值却时时得到体现。我感觉，知识是死的，人是活的，有时候学到的东西并不直接在现实中发挥作用，而是一种厚积薄发的潜在能量。这种能量有可能是在学习的过程中，培养了解决问题的能力，也有可能暂时用不上，却在日后某个时刻得到触类旁通的灵感和创造力。或许，这就是学习深造和普通工作培训的关键区别。
|
|
|
相关文章：
 [转载] 关于网页设计价值的讨论及中国网络网页设计价格标准 [2007-05-17]
[转载] 程序员的职业水准 [2007-05-08]
[转载] 美放宽高科技对华出口真相：中国恐难得实惠 [2007-05-07]
[合著] 专利：一种计算机组成原理的实验装置 [2007-04-25]
[转载] 美严管对华高技术产品出口危及全球产业链 [2007-04-25]
[转载] 函数式的编程序 [2007-02-15]
最新留言：
 [2014-10-16]
[2014-10-16]
[2014-06-04]
[2014-06-04]
[2013-12-08]
[2013-11-29]
|
|
|
相关链接 |
|
人次