进程演算
计算机科学术语
在计算机科学中,进程演算(或进程代数)是用于正规建模并发系统的多种相关方法。进程演算提供了具体描述多个独立代理人程序或者是多个进程之间交互、通信、 同步的方法。
基本特征
虽然目前为止的进程演算种类繁多(包括含有随机行为,定时信息,专门研究基础的的交互的特例),但是所有的进程演算都有以下几个共同特征:
1.在独立进程之间进行通信(消息传递)时比修改共享变量更能体现交互性;
2.使用基本元和能合并这些基本元的操作符的集合来描述进程和系统;
3.定义了能通过方程式推理方法推导出进程表达式的操作符的代数法则。
数学表示
定义进程演算,一开始目的是为了提供通信手段的命名(如信道),在许多实现中,信道有优秀的内部结构以提高效率,不过这是从理论模型中抽象出来的。除命名之外,需要从之前的进程中运用一个方法来构建新的进程,其中的基础运算符,总是以某些形式或其他方式呈现,包括:
1.进程的并行组合;
2.详述用于传送和接受数据的信道;
3.交互操作的顺序化;
4.隐藏交互点;
5.递归或进程复制;
并行组合
两个进程P和Q的并行组合,通常写做P|Q,它是将进程演算从运算序列模型中识别出来的关键基本式。并行组合允许P和Q相互独立并且同时进行运算。但它也允许进行交互,那就是同步及P通过两者共享的信道将信息流传递至Q(或反之亦然)。至关重要的是,代理或进程可以一次连接到多个信道。
信道可以是同步或异步的。在同步信道的情况下,发送信息的代理需要等待至另一个代理接收到信息。异步信道不要求任何的同步。在一些进程演算(特别是π演算)中,它们的信道本身可以作为信息通过(其他的)信道发送,允许进程相互连接的拓扑结构发生改变。一些进程演算也允许信道在执行运算的过程中被创建。
通信
交互可以作为(但不总是)有向的信息流。也就是说,输入和输出能作为双重交互基本元被区分。进行这种区分的进程演算通常定义一个输入操作符(e.g X(v))和一个输出操作符(e.g X),这两者作为一个以双重交互基本元进行同步的交互点(这里是X)。
信息应该被交换,它将从输出流向输入进程。输出基本元将指定要发送的数据。在X中,这个数据是y。类似的,如果一个输入想要接受数据,当数据到达时,一个或多个绑定变量将作为占位符来替换数据。在X(v)中,v扮演那个角色。在交互中可以交换的数据类型的选择是区分不同进程演算的关键特征之一。
顺序组合
有时交互必须在时间上有序。例如,它可能要求指定算法:首先在X上接收数据,然后在y上传送数据。顺序组合可用于这些目的。在其他运算模型中它非常有名。在进程演算中,序列化运算符通常与输入或输出或两者结合。例如,进程X(v).P将等待(数据)输入到X上,只有当这个输入完成时进程P才会被激活,通过X接受的数据代替标识符v。
归约语义
归约法则运用的关键,包含了进程演算的计算实质,单独的依据并行组合、顺序化、输入和输出。演算间的归约细节不同,但是实质保持大致相同。通用的归约法则是:
X.P|X(v).Q → P|Q[y/v]
该归约规则的解释是:
P这类进程涉及的输出运算符的连续性本质上影响了演算的性质。
隐藏
递归与复制
迄今提出的操作仅描述有限的交互,也因此不满足包含非终止行为的完全可计算性。递归和复制允许以有限步描述无限的行为。递归具有的连续性领域是众所周知的,复制!P可以被理解为缩写可数集无限数的P进程的并行组合:
!P=P|!P
空进程
进程演算通常还包含没有交互点的空进程(多样的表示为nil,0,STOP,δ或一些其他的适当符号),它是完全无活动的,并且它唯一的用途表现在作为归纳锚点置于可以被生成的活跃进程之上。
离散和连续进程代数
已经针对离散时间和连续时间研究过进程代数(真实时间和稠密时间)。[4]
历史发展
在20世纪上半叶,提出了各种形式论来获得可计算函数的非正式概念,μ递归函数,图灵机和lambda演算可能是如今最著名的例子,令人惊讶的事实是,在它们可以相互编码的意义上,它们彼此之间基本上是等同的,支撑着Church-Turing论题。另一个难得的对它们共同特征的评论是:它们几乎都是作为最容易理解的连续计算模型,随后的计算机科学的整合需要更细微的计算概念的表达,特别是并行和通信的明确表达。作为进程演算的并行模型,1962年的Petri网,以及1973年出现于线路查询的Actor模型。进程演算的研究开始于1973年至1980年期间,与Robin Milner对连接系统演算(CCS)的开创性工作有关。C.A.R. Hoare的顺序进程(CSP)首次出现于1978年,随后直到20世纪80年代初期才被开发为一个完整的进程演算。CCS和CSP在发展的过程中,发生了许多思想上的交叉。在1982年Jan Bergstra和Jan Willem Klop开始致力于研究后来被熟知的通信处理代数(ACP),并且提出了术语“进程代数”来描述他们的工作。CCS、CSP和ACP构成了进程演算的三个重要的分支:其余大多数的进程演算的根源都可以追溯到这三个演算的其中之一。
现今研究
研究的进程演算多种多样但不是全部都符合这里描述的范例。最突出的例子可能是灰箱演算。作为进程演算研究预期的热门领域,目前对进程演算的研究集中在以下问题上:
软件实现
进程代数的想法提出后已经产生了许多工具包括:
.CADP[1]
.并行工具台
.mCRL2工具集
与其他并行模型的关系
历史独异点是能够一般的表示独立通信进程历史的自由对象。进程演算是形式语言以一致的方式应用于历史独异点之后得到的。[5]即是说,一个历史独异点只能够记录事件的顺序,带有同步性,但是这不表明允许状态的转变。因此,进程演算之于历史独异点相当于形式语言之于自由独异点(形式语言是Kleene star产生的字符所组成的所有可能的有限长度字符串的子集)。
使用信道进行通信是将进程演算与其它并行模型区分开的特征之一,例如Petri网和Actor模型(见Actor模型和进程演算)在进程演算中包含信道的基本动机之一是实现某些代数方法,从而让用代数方法来推导进程变得简单。
参考资料
最新修订时间:2024-05-21 13:06
目录
概述
基本特征
数学表示
参考资料