根据进程代数的多路拜访协议模型研讨与完成

  

第一章绪论

 

        1.1本文研究的背景计算机科学从诞生开始就是一门发展迅猛的学科，而且应用范围广泛，渗透到社会生活中的各个领域，如天气预报、图像处理和各种信息管理支持系统都会用到计算机来处理数据。而计算机科学在发展的过程中也遇到了很多问题，如当今大家所关注的进程的并发问题。简单介绍一下并发问题:在计算机发展的初期，还没有操作系统，计算机至始至终执行地一个程序，这个程序直接访问机器的所有资源。这样的一个程序运行在没有保护的硬件上，写起来相当困难。由于每次只能运行一个程序，不能很好的利用计算机的硬件资源，比如程序访问内存的时候，处理器空闲出来，浪费了宝贵的处理器时间。如何充分利用资源，即让多个程序同时在一计算机上执行不浪费资源，就产生了并发。

 

        程序的并发带来了很多问题，如公平性:程序A和程序B同时在计算机上执行，可能程序A执行了很长的一段时间，而程序B却一点也没有执行;还有临界资源的访问问题:程序C和程序D都需要访问打印机，如果程序C访问打印机打印了一行就退出，程序D接着执行程序打印了一行也退出了执行，程序C和程序D如是反复，结果打印出来的东西很乱导致无法阅读，也得不出想要的结果。如何描述和控制程序的并发是当今计算机科学界所关注度的热点问题之一。我们知道，计算机非常重要的一个用途是用来通信，而通信需要多个协议参与，在计算机的各种的协议中，描述的并发的不在少数。如何描述这些协议，如何确保这些协议的正确性。出现了很多方法来刻划网路协议，如Petri网，形式化方法等。其中在形式化方法中一个十分重要的分支一进程代数，进程代数中主要有三种，CCS(TheCalculusofCommunicatingSystems通信系统演算)、二演算(二Calculus)和CSP(CommunicatingSequentialProcesses通信顺序进程)。CSP是C.A.R.Hoare提出的，是面向分布式系统的程序设计语言;CCS是和二演算RobinMilner发明的，分别是用于描述通信并发系统和移动通信并发系统的代数理论。

 

       1.2相关领域的研究状况在进程代数的各个分支中，CSP和CCS是最为著名的两种。在CSP语言中，一个并发系统由若干并行运行的顺序进程组成，进程之间通过通道传递消息来进行通信，每个进程不能对其他进程的变量赋值。进程之间只能通过一对通信原语实现协作:(}->x表示从进程Q输入一个值到变量x中:P<一e表示把表达式e的值发送给进程P。当P进程执行Q一>x，同时Q进程执行P<一e，发生通信，e的值就是从Q进程传送给P进程的变量x。进程之间的通信都是同步，没有缓冲区。CSP中定义了一些动作的集合，这些动作用于进程之间进行通信，而且这些动作都是原子动作，不可再分的，一旦发生，立刻完成，如时钟走动的动作tick等，也可以是复合动作如Clock.tick或者其它的复合动作。CSP中也有一些原子进程如STOP(进程什么都做不了，处于死锁状态)和SKIP(进程成功结束，可以接着执行下面的程序)。CSP语言的核心是一组完备的代数运算表达式，如并行运算}}，与运用八，或运算V，前缀运算分，内部选择运算n，外部选择运算口等。算子通过合理的组合就可以对各种系统进行建模，一个经典的例子一自动售货机1，投入1便士可以得到一个小的巧克力或者继续插入1便士，投入2便士可以得到一个大的巧克力或者选择一个小的巧克力，找零1便士。模型如下:vMC=(in2p一(large-}VMC}small--3outlp--}VMC)}inlp一(small-}VMC}inlp一(large一VMC}号STOP)))CSP部分语法定义如下:1C.A.RHoareCommunicatingSequentialProcessesP$ACMUSA1978.8