并行程序调试、测试与模型检测

并行程序调试、测试与模型检测

并行程序调试的挑战：

1、由于不能确定不同线程的执行顺序，导致可能的执行路径发生组合爆炸；

2、使用模型检验程序正确性能以应用到分布式系统上。

名词解释

确定性重放：通过记录系统中不确定性事件的发生顺序，在重放阶段按照记录的顺序执行相关事件，使得重放阶段与记录阶段的执行具有相同的程序状态，从而缓解并行程序执行的不确定性对调试带来的影响。

确定性并行：在并行程序执行时，必须遵守一定的规则来执行不确定事件，从而直接将并行程序的执行本身变成确定性的。

并发错误：通常来源于多线程中未能正确处理同步问题。其特点是存在于多线程环境中并且具有不确定性。本质上，并发错误可分为：原子性违例、顺序违例和死锁。原子性违例发生于一个线程的代码区域与另一个线程出现非可串行化交叉的情况。顺序违例是指当一个线程的操作A本应发生在另一个线程的操作B之后，却发生在了B之前的情况。死锁是指多个线程循环等待共享资源，彼此不释放以获得资源的一种情况。

相关技术

确定性并行

不确定的线程交叉运行和线程间的访存冲突为多核程序执行带来了不确定性。这种不确定性为多核程序调试带来了困难。特别是对bug的重现，往往因为多核程序执行的随机性，使得恢复同一bug的运行变得十分困难。通过将并行串行化，能够使得多核程序的运行路径变得可预测和确定。其中的方法包括轮流执行法、无冲突访存法、确定性编程模型。轮流执行通过将串行和并行代码进行分离，对访存冲突的代码段采用串行执行方式，方法是根据线程对内存块的请求情况，重新分配线程访问内存块的的权限。无冲突访问通过将线程的共享内存进行分离，为每个线程创建共享变量的本地副本使得线程的执行不会导致访存冲突，从而避免了多核程序运行的不确定性。确定性编程模型通过改变并行编程模型来对多核程序的执行实现控制，包括diverge&merge模型，消息通信模型，函数式编程模型等等。

软件测试

软件测试需要满足完备性和可靠性。测试方法包括对代码的静态测试和动态测试。前者包括基于程序验证的方法发现运行逻辑和语法定义等方面的错误，其中的研究课题包括模式匹配、定理证明、模型测试、经典的符号执行和基于学习的测试等；后者是通过实际运行程序检查运行结果与预期结果的差距来确定被测程序是否存在错误，相关的测试方法有可以从调度粒度和调度策略两个角度进行分类。调度策略包括压力测试，多次重复测试；启发式引导，实时监控和引导程序执行；随机调度，改变系统（包括操作系统）的调度方式，加大系统调度方式的随机性，包括随机休眠、默认抢占、限定抢占等调度策略；系统调度，结合模型检验技术穷举测试程序可能的状态看哦可能关键，从而断言被测程序是否存在漏洞。

问题：

多线程之间的同步可以通过锁和条件变量之间的协作获得较好的性能，在多进程之间的同步又是有怎样的工作机制？

参考：

CCF 2013年2月刊 http://www.ccf.org.cn/sites/ccf/jsjtbbd.jsp?contentId=2722092546435

内存一致性模型：http://blog.csdn.net/force_eagle/article/details/7743063