并发程序内部表示及静态切片算法的改进

通过分析Krinke切片算法对程序循环体内嵌套一个或多个线程结构会产生切片不精确现象,得出Krinke算法所基于的程序依赖图对线程间数据的依赖关系定义得过于粗糙,且对并发程序执行行为的合法性约束不够严格的结果.据此,提出一种新的并发程序依赖图,引入跨线程边界循环-承载数据依赖关系,并在此数据结构上改进了切片算法;引入区域化执行证据概念,进一步约束程序执行行为的合法性,并给出了添加跨线程边界循环-承载数据依赖关系的算法及新的并发程序切片算法的伪代码.实例分析与算法性能测试表明,改进的切片算法克服了Krinke算法的不精确现象,降低了时间开销,改善了算法的可伸缩性.     

Turbo Pascal的并发程序单元

对用Turbo Pascal3.0实现的并发设施作了修改,修改后的子程序收入两个外部程序单元。它们可供Turbo Pascal 4.0及以上版本成功地调用。     

UNIX进程控制的内部实现

介绍ＵＮＩＸ进程状态及其相互转换,分析与进程控制有关的主要系统调用,并给出了多进程并发执行的程序实例。     

并发进程的一种跟踪与重演算法

并发程序的执行具有“不确定性”,即在同样的输入条件下并发程序的执行结果不一定相同。这使得传统的对于顺序程序的循环调试方法对于并发程序的调试不再有效。通过对并行程序的执行情况进行跟踪和重演,可以保证并发程序在相同的输入时候两次执行完全一样。本文分析了基于消息传递的并发程序执行模型,并给出了相应的跟踪和重演算法及其实现。     

并发程序模型的可信性研究

讨论基于交替计算模式的并发程序执行行为的可信性问题。通过比较共享变量程序的交替计算与实际重叠执行，对并发程序的执行过程进行粒度分析－首先提出了种粒度细化、求精方法，限制单个原子转换包含的临界事件数目；继而引入一种限制临界引用（ＬＣＲ）条件，进上步限制每一与语名相关的转换至多执行一次临界引用；对任一程序，通过转换算法将其转化为与之等价的ＬＣＲ程序，且ＬＣＲ程序的交替计算结果与实际的重叠执行结果一致的     

时态逻辑与并发程序

分别阐述了基于Ｍａｎｎａ－Ｐｎｕｅｌｉ框架的命题线性时态逻辑ＰＬＴＬ和基于共享变量方式的并发程序（转换图）模型,并给出该模型与转换系统之间的对应关系;将时态逻辑与公平转移系统ＦＴＳ相结合来描述并发程序及其性质（公平性、安全性及活性）;指出了时态逻辑具备其它形式化方法（ＦＳＭ、Ｐｅｔｒｉ网）所没有的一些优势。     

UNIX进程控制和管理的特性分析

详细介绍和分析了ＵＮＩＸ系统中进程控制和管理的方法及特点，提出了用户程序如何通过系统的调用实施对自己进程的控制，从而提高计算机系统资源的利用率。     

并发程序切片方法综述

随着实际应用对并发软件需求的不断增加,并发程序的应用越来越广,程序切片的研究不再仅仅局限于顺序程序,并发程序切片的研究也越来越多.但是由于并发程序执行的不确定性,并发程序切片的研究还有许多问题有待解决.文中介绍了当前主要的几种并发程序切片方法及其主要特性,并对这些切片方法进行了比较分析,结果表明并发程序切片的效率和精度都达到理想的目标是不可能的,只能是在两者之间的均衡,最后简要介绍了并发程序切片的应用.     

基于上下文敏感分析的数据竞争检测方法

为了提高数据竞争检测过程的准确性,提出了一种基于上下文敏感分析的数据竞争检测方法。使用控制流分析构建上下文敏感的调用图,采用逃逸分析查找出可能发生数据竞争的线程逃逸对象,进行上下文敏感的别名分析以减少误报和漏报,通过发生序关系判断消除由于忽略线程交互而导致的误报。依据该方法,在WALA软件分析框架实现了一个数据竞争检测工具ConRacer,并将该工具与现有的检测工具SRD和RVPredict进行了比较。结果表明,与SRD和RVPredict相比,ConRacer的检测准确度最高,不仅可以有效地检测数据竞争,而且可以降低检测过程中的误报和漏报。通过结合上下文敏感分析技术与传统的静态检测技术,ConRacer提高了检测过程的准确性,对发现并发错误和优化软件性能有一定的参考价值。     

一种基于P/T网的低级并发程序验证模型

随着片上多处理器/多核技术的不断发展,采用机器级语言的并发程序(低级并发程序)有了更加广阔的应用前景.然而,低级并发程序的验证问题也成为程序语言领域一种新的挑战.并发程序安全性验证领域现有的工作多数是针对高级语言、规范或者演算,而针对机器级语言的甚少。这种情况的主要原因之一是缺少低级抽象模型.文中描述一种可验证的低级并发编程模型P-PMCC.P-PMCC程序是一个扩展的P/T网系统,其网结构用来刻画低级并发线程(原子的顺序汇编级代码)之间的并发关系.P-PMCC程序的验证采取模型检查和定理证明相结合的方法,分开考虑并发行为与顺序线程的规范和验证:前者借助于Petri网领域已有的方法,后者则借助现有的顺序程序的正确性证明方法。P-PMCC程序也可以看作并发程序的一种可验证的低级中间表示.