1) concurrent program dependence graph
并发程序依赖图
2) program dependency graph
程序依赖图
1.
The main idea of the algorithm is to retain the control-flow information while the threaded program dependency graph is constructed, with which the threaded realized paths can be identified, by doing this we can improve the slice s precision and slicing s efficiency.
介绍一种基于控制流的多线程程序的静态切片算法 ,该算法的主要思想是在构造多线程程序依赖图的同时保留程序的控制流信息 ,利用这些信息能够判断出程序中的多线程可实现路径 ,从而提高多线程程序静态切片的精度和效率 。
3) program dependence graph
程序依赖图
1.
The paper presents a program structure partition method based on the program dependence graph, i.
本文提出了一种基于程序依赖图的程序结构划分的测试方法 ,即程序块划分法 。
2.
This paper handled the transitivity of the information flow with the program dependence graph before constructing the IFG.
利用程序依赖图先处理系统信息流中的传递关系,然后再进行信息流图的生成,从而减少引入系统中不存在的信息流路径,减少信息流分析时的工作量。
3.
To resolve the inter-procedural call,the article converted it to intra-procedural call by establishing a suggestive table,which predigested the complexity of establishing the program dependence graph greatly.
在处理目标程序的过程间调用时,通过建立参数影射关系表,将过程间调用转换为过程内调用,简化了建立程序依赖图的复杂度;在归纳分析目标程序变量类型的基础上,给出了代数运算法则,对程序中的线性运算代码进行等价变换,缩减了切片程序的规模。
4) call graph
程序依赖图
1.
A program understanding technique that combines open compile analysis and reflective instrumentation dynamic analyses is introduced to construct static and dynamic combined call graph for assisting program comprehension.
针对静态程序分析得到的信息冗余且无法反映面向对象目标系统多态和动态绑定的本质特征,而动态分析则与动态程序执行有关的,无法得到完整的依赖关系,提出反射植入动态分析和开放编译静态分析相结合的方式,并将得到的静态和动态信息有机结合起来产生动静态结合程序依赖图。
5) PDG arithmetic
程序依赖图算法
补充资料：并发程序设计
由若干个可同时执行的程序模块组成程序的程序设计方法。这种可同时执行的程序模块称为进程。进程由数据和有关的语句序列组成。组成一个程序的多个进程可以同时在多台处理器上并行执行，也可以在一台处理器上夹插执行。采用并发程序设计可以使外围设备和处理器并行工作，缩短程序执行时间，提高计算机系统的效率。例如，在一个单处理器系统中，从磁盘读入数据经加工后打印输出，不采用并发程序设计时，解决这个问题的程序是循环地执行读入一批数据，然后，加工打印输出。执行这个程序时，磁盘机、处理器和打印机顺序执行输入、加工和输出操作。虽然计算机的外围设备和处理器可以并行操作，但执行上述程序时它们只能串行工作。如果采用并发程序设计，解决上述问题的程序由以下两个进程组成。①读盘进程：循环地执行读入一批数据，加工后送入输出缓冲区；②打印进程：循环地执行从缓冲区取出数据打印输出。在打印进程执行打印输出时只需要打印机，而不需要磁盘机和处理器。因此，在打印进程启动打印机后，在打印机输出的过程中可以启动读盘进程输入和加工数据。执行这个程序时，处理器、磁盘机和打印机并行工作，能缩短程序执行的时间，提高计算机系统的效率。
发展过程 60年代初期出现的多道程序设计是并发程序设计的萌芽。在一个多道程序设计系统中，一个计算机系统可以同时接受多个用户程序，并让它们交替占用处理器运行。当一道程序因为等待外围设备而暂时不能运行时，就启动另一道程序运行，而各道程序之间没有关系。因此，多道程序设计能提高计算机系统的效率，但并不能缩短一道程序的执行时间。在出现多道程序设计时，人们尚不清楚并发这个概念和由此产生的如死锁等问题。60年代初期出现的许多多道程序设计系统，根本没有考虑死锁问题。因此，这些系统都有不同程度的错误和隐患。1968年，E.W.代克斯特拉设计的操作系统T.H.E.，首次系统地表明了并发程序设计的概念和有关问题。他注意到并发进程访问公共变量的问题，提出用PV操作解决公共变量问题。此外，他还采用层次结构方法防止死锁。然而，T.H.E.系统是用汇编语言编写的。到70年代，人们才开始将并发程序设计的概念引入程序设计语言中，先后出现并发PASCAL、MODULA-II和ADA等程序设计语言。与此同时，还开展了防止死锁、死锁检测和同步机制的研究，提出银行算法、按序分配等防止死锁的算法和管程等同步机制。到80年代，并发程序设计的研究已逐渐完善，应用也日益广泛。
基本内容 并发程序设计的主要研究内容有：同步机制、死锁的预防和检测，以及并发程序设计语言。
同步 在并发程序设计中，将加工后的数据送入缓冲区和从缓冲区取出数据打印输出必须依次进行。在数据送入缓冲区前不能打印输出，在缓冲区内的数据没有打印输出完毕时不能输入；否则，一批数据可能被重复打印或者一批数据还没有打印输出就被新送入的数据冲掉。因此，对"送入缓冲区"和"从缓冲区取出数据"两个操作必须加以约制，以保证它们依次执行，否则就会发生错误。
产生这个问题的原因是两个进程都要访问缓冲区，也就是说它们有一个公共变量。在并发程序设计中，各进程对公共变量的访问必须加以约制，这种约制称为同步。进程的同步是通过同步机制实现的。现已有多种同步机制，具有代表性的是PV操作和管程。
PV操作是最早提出的同步操作。PV操作的名称来源于荷兰字prolagen(企图降低)和verhogen（升起）。PV操作是作用于信号量上的原语。所谓原语是指其执行是不会被打断的，即一个进程在执行PV操作时，不会强行地被打断而让处理器去执行另一个进程。PV操作的定义是：执行P操作P(S)时，信号量S之值减1,若结果不为负数，见P(S)执行完毕；否则,执行P操作的进程暂时停止。等待释放。执行V操作V(S)时,信号量S之值加1，若结果不大于 0，则释放一个等待释放的进程。有了PV操作后，上例中的问题就即可解决。
1973年，C.A.R.霍尔提出的管程是另一种重要的同步机制。管程是指一组公共数据同与其有关的操作的集合。只有引用管程中的操作才能访问管程中的数据。一个进程引用管程中的操作时，只有在管程中的各操作均不处于活动状态时才被响应。当管程中的一个操作被引用后，它就成为活动状态。当管程中一个操作已执行完毕或在执行中处于等待状态时，它就不是活动状态。管程将公共数据同与其有关的操作集中在一起，使得并发程序设计易于理解，程序正确性也容易保证。因此，管程有助于同步机制从PV操作向前发展。它是并发程序设计趋于成熟的标志之一。
死锁 进程因争夺资源而无休止地相互等待称为死锁。例如，进程P1占有了绘图机而申请行式打印机，进程P2占有了行式打印机而申请绘图机。它们都因为申请不到资源而永远等待，这就是死锁。解决死锁问题有两种途径：一是预防死锁，设计各种资源调度算法，防止死锁发生；另一种途径是检测死锁，当死锁发生时能及时发现并进行排除。
语言 要有效地采用并发程序设计，必须提供并发程序设计语言。并发程序设计语言的主要特征，是引入了进程概念。因此，用它编写的程序包含若干可同时执行的进程。此外，并发程序设计语言还提供实现进程同步和通信的手段。
参考书目
P.B.汉森著,杨芙清等编译:《并发程序的系统结构》，国防工业出版社,北京,1982。(Per Brinch Hansen,The Architecture of Concurrent Programs, Prentice Hall,Englewood Cliffs,New Jersey,1977.
发展过程 60年代初期出现的多道程序设计是并发程序设计的萌芽。在一个多道程序设计系统中，一个计算机系统可以同时接受多个用户程序，并让它们交替占用处理器运行。当一道程序因为等待外围设备而暂时不能运行时，就启动另一道程序运行，而各道程序之间没有关系。因此，多道程序设计能提高计算机系统的效率，但并不能缩短一道程序的执行时间。在出现多道程序设计时，人们尚不清楚并发这个概念和由此产生的如死锁等问题。60年代初期出现的许多多道程序设计系统，根本没有考虑死锁问题。因此，这些系统都有不同程度的错误和隐患。1968年，E.W.代克斯特拉设计的操作系统T.H.E.，首次系统地表明了并发程序设计的概念和有关问题。他注意到并发进程访问公共变量的问题，提出用PV操作解决公共变量问题。此外，他还采用层次结构方法防止死锁。然而，T.H.E.系统是用汇编语言编写的。到70年代，人们才开始将并发程序设计的概念引入程序设计语言中，先后出现并发PASCAL、MODULA-II和ADA等程序设计语言。与此同时，还开展了防止死锁、死锁检测和同步机制的研究，提出银行算法、按序分配等防止死锁的算法和管程等同步机制。到80年代，并发程序设计的研究已逐渐完善，应用也日益广泛。
基本内容 并发程序设计的主要研究内容有：同步机制、死锁的预防和检测，以及并发程序设计语言。
同步 在并发程序设计中，将加工后的数据送入缓冲区和从缓冲区取出数据打印输出必须依次进行。在数据送入缓冲区前不能打印输出，在缓冲区内的数据没有打印输出完毕时不能输入；否则，一批数据可能被重复打印或者一批数据还没有打印输出就被新送入的数据冲掉。因此，对"送入缓冲区"和"从缓冲区取出数据"两个操作必须加以约制，以保证它们依次执行，否则就会发生错误。
产生这个问题的原因是两个进程都要访问缓冲区，也就是说它们有一个公共变量。在并发程序设计中，各进程对公共变量的访问必须加以约制，这种约制称为同步。进程的同步是通过同步机制实现的。现已有多种同步机制，具有代表性的是PV操作和管程。
PV操作是最早提出的同步操作。PV操作的名称来源于荷兰字prolagen(企图降低)和verhogen（升起）。PV操作是作用于信号量上的原语。所谓原语是指其执行是不会被打断的，即一个进程在执行PV操作时，不会强行地被打断而让处理器去执行另一个进程。PV操作的定义是：执行P操作P(S)时，信号量S之值减1,若结果不为负数，见P(S)执行完毕；否则,执行P操作的进程暂时停止。等待释放。执行V操作V(S)时,信号量S之值加1，若结果不大于 0，则释放一个等待释放的进程。有了PV操作后，上例中的问题就即可解决。
1973年，C.A.R.霍尔提出的管程是另一种重要的同步机制。管程是指一组公共数据同与其有关的操作的集合。只有引用管程中的操作才能访问管程中的数据。一个进程引用管程中的操作时，只有在管程中的各操作均不处于活动状态时才被响应。当管程中的一个操作被引用后，它就成为活动状态。当管程中一个操作已执行完毕或在执行中处于等待状态时，它就不是活动状态。管程将公共数据同与其有关的操作集中在一起，使得并发程序设计易于理解，程序正确性也容易保证。因此，管程有助于同步机制从PV操作向前发展。它是并发程序设计趋于成熟的标志之一。
死锁 进程因争夺资源而无休止地相互等待称为死锁。例如，进程P1占有了绘图机而申请行式打印机，进程P2占有了行式打印机而申请绘图机。它们都因为申请不到资源而永远等待，这就是死锁。解决死锁问题有两种途径：一是预防死锁，设计各种资源调度算法，防止死锁发生；另一种途径是检测死锁，当死锁发生时能及时发现并进行排除。
语言 要有效地采用并发程序设计，必须提供并发程序设计语言。并发程序设计语言的主要特征，是引入了进程概念。因此，用它编写的程序包含若干可同时执行的进程。此外，并发程序设计语言还提供实现进程同步和通信的手段。
参考书目
P.B.汉森著,杨芙清等编译:《并发程序的系统结构》，国防工业出版社,北京,1982。(Per Brinch Hansen,The Architecture of Concurrent Programs, Prentice Hall,Englewood Cliffs,New Jersey,1977.
说明：补充资料仅用于学习参考，请勿用于其它任何用途。
参考词条