并发模型分析.pdfVIP

维普资讯 计算机科学 1995Vo[．22№．3 1～II) ‘ ·并岑模型分析 型登 TP3o1． (国睁科技大学计算机系 长沙410073)IJ 摘 要 并发一直是计算机抖学中矛盾的潭泉和争论的焦点之一 。本文分析和比较 了三种并发模 型；Petr阿、CSP和ccs的发展历史、描述方法、处理并发与不确定性岛方式等。 关键词并发， 。 ljc、 i h 许多方面。CSP和 CCS的研究都是在 Petri阿的基 一 、 引 言 础上展开 的。 计算机语言的形式语义是计算机科学的重要基 通信顺序进程 (CSP)是 Hoare．C．A．R于 1978 础t对它的研究始于六十年代 ．并 由此蓬勃发展起 年提出的一个并发程序设计语言+它把同步输入 ／车卣 来 先后出现 了四大漉派．即操作语 义、指称语义 ，公 出语句作为基本原语+通过组合和握手通信来扩展 理语义及代数语义 ．它们从不同的佣面、用不同的理 Dijkstra的卫士命令 。csP一经出现就被广瑟地传 论为程序设计语言含义的描述提供了很好的方法t 描和使用 。在CSP的早期敝本中投给出其精确的数 副 目前为止 对顺序程序设计语言的语义的研究 已 学语义，所以对于象 并发嵌套 递归调用 等重要 趋于成熟 。六十年代末七十年代初．计算机界开始遇 同题无法解决．于是 出现了更新更抽象 的版本TC． 到并发现象，但 由于并发机的咎系结掏 日趋多佯化 SP(TheoryofCommunLezdngSequentialProcess)． 以及井发程序设计思想和并发语言 的不断变 化．人 TCSP在很大程度上受Milner的CCS的影响．它的 们对并发缺乏理解+对并发所造 成的后果心存述惑 并发和通讯方法及语义的研究与CCS稂类似．TC． 和恐惧心理 。几十年来 ．并发一直是计算机科学的重 sP的 失破语 义 给出其精确的数学描述 ．使 CSP 要课题，暖号f着大批有创新能力和献身精神柏抖学 理论更加可靠完善． 家 ．从六十年代的Petri同论到七 ，八十年代的CSP 并发的数学模型的主要赛琏是Robi~trainer完 和CCS．再到它们的各种糖化、导出l跹本 以及其它并 成的，在他于 1980年发表的 通信系统演算 (CCS) 发模型 ．对并发 的研究可谓丰富多彩．本文主要介绍 中t给 出了一个建立于扳小原语集上的函数式程序 这三种博型 ．并对它 仃『进行比较和分析 。 设计语言CCS．为遥信的．非确定的并发系统提供了 一 十通用数学模型。在 Milner84年的关于 CCS的 二、发展历史和应用 讲话中．他叉给出了更基本的演算．并证明原来的演 1962年 ，C．A．Petri以其论文 K0rnmunikat “ 算是后者的一十导 出演算 ．此后CCS理论曲发展主 mitAutomaten 在达姆施塔特大学获博士学位 ，标 要是匿绕更基础的演算进行的 。1989年 Miln