通信软件及通信协议5

1、四、协议的形式描述语言1Slide 1主要内容形式化方法协议的形式化模型协议的形式描述语言SDL2Slide 21、形式化方法3Slide 3形式化方法的引入系统行为的复杂性增大了行为描述的难度，必须借助一种语言或一种技术来准确的描述系统的行为。自然语言具有冗长、不完整、语句容易产生二义性、结构性差和没有描述标准等缺点。国际标准化组织建议用形式化方法来描述复杂的系统。形式化方法使得对通信系统的描述、实现和测试变得容易。4Slide 4与自然语言相比，形式化方法具有以下的特点：形式化的语法形式化的语义清楚的概念模型界面统一表示强大的表达和描述功能有助于系统的实现和完善形式化方法的特点5Slide

2、 5形式化方法的最终目的为开发者提供一种分析、设计的方法作为对开发结果进行验证、测试的基础为设计和应用人员提供交流的途径作为开发文档易于今后的维护和再开发6Slide 62、协议的形式化模型7Slide 7协议的形式化模型有限状态机（FSM）Petri网时态逻辑TL通信进程演算8Slide 8有限状态自动机可定义为一个四元系统 ，其中：S：系统状态集，状态数有限；i：系统初始状态，i S;E：输入字母集；T：转移函数集，是从 SE到S的映射；有限状态自动机（1）9有限状态自动机（2）单比特奇偶检验器的有限状态自动机偶奇11Slide 90010Slide 10扩展有限状态自动机（1）扩展有限状

3、态自动机定义为一个四元系统 ，其中：S：系统状态集，状态数有限；i： 系统初始状态， i S;E：输入事件集；T：转移函数，是从SE到S的映射11扩展有限状态自动机（2）转换函数的定义：SiSj T， Si，SjSt = e / p：a；或t = e / a；或t = e其中：eE，p为谓词，表示条件；a表示动作Slide 11t12等AK扩展有限状态自动机（3）等待DC等CCDC未连接AKTDTreq/DTCC/TCONconfTDISreq/DR已连接TCONreq/CR传输层协议机Slide 1213Slide 13可通信的扩展有限状态自动机系统的行为通过可通信的扩展有限自动机来描述系统

4、由扩展的有限状态自动机组成扩展的有限状态自动机具有与外界通信的能力：输入/输出动作14Slide 14Petri网Petri网的概念最早是由德国的Carl Adam Petri于1962年提出的。它是一种适合于并发、异步、分布式系统描述与分析的图形数学工具。Petri网已成为网络协议分析和设计的典型形式化模型之一。15Slide 15时态逻辑（TL）它涉及含有时间信息（现在、过去、将来、之前、之后等）的事件、状态及其关系的命题、谓词和演算。16P1=a.(c.NIL+b.NIL)P1=Q2 I Q3（选择）（并行）通信进程演算（CCS）是计算机通信系统的基本理论模型，也是许多形式化语言的基础。

5、CCS的基本成分是事件和进程，而进程是通过顺序、选择和并行三个基本算子来定义的。P1=a.b.NIL P2=a.b.P2 （顺序）17Slide 173、协议的形式描述语言18Slide 18ESTELLE为准确描述OSI协议，ISO的FDT（形式描述技术）小组于20世纪80年代初开始进行形式描述语言的开发研究。最初提出了20多种方法，大致可归结为2类：基于有限状态机语言类和基于代数方法语言类。ESTELLE（一种扩充的有限状态机语言）是前一类语言的典型代表。1989年，ISO公布了作为形式描述技术国际标准之一的ESTELLE。ESTELLE是基于扩展的有限状态机，是一种形式化、数学化，并且与

6、具体实现相独立的描述技术。它具有良好的结构和定义，并且具有很强的表达能力，可以完整、一致、简练、准确的描述分布、并行信息处理系统。ESTELLE的特点：基于扩展有限状态机，专为描述协议而设计；是Pascal语言的扩充，是面向协议实现的FDL；模块之间的通信方式为异步通信；对并发、不确定性、超时、异步通信状态转换有较强的表达能力，但对递归、共享通道、同步通信的表示不足；其所描述的协议很容易转换为FSM、Petri网模型，不容易转换成TL、 CCS模型。19Slide 19ISO的FDT（形式描述技术）小组经过8年多时间的努力，于1988年8月完成了作为国际标准的形式描述语言（LOTUS,Lang

7、uage of Temporal Ordering Specification）。LOTOS的基本思想是：外部可观察到的系统行为由一系列的交互作用组成，通过对这些交互作用的时间关系进行定义，从而描述整个系统。LOTOS的特点：基于进程代数CCS和多类代数的FDL；进程通信为同步通信；不是面向协议实现的语言；其所描述的协议很容易转换为CCS模型，也比较容易转换成TL、FSM、Petri网模型。LOTOS的不足之处：无异步通信机制、无清晰的记录型数据结构的描述手段、无常量描述手段、可读性差。LOTOS20Slide 20SDLSDL（Specification and Description La

8、nguage）是ITU-T提出的一种形式化描述语言，由Z.100建议定义。SDL的版本： SDL-88：是后续版本的基础 SDL-92：引入面向对象的概念 SDL-96：对SDL-92的完善 SDL-2000：对面向对象的特征作了进一步的扩展；引入了其它语言，如ASN.1、ITU-T ODL、UML等21Slide 21SDL的特点可用于需求分析到具体实现的整个开发过程。适应于实时系统基于扩展的有限状态机图形化表示方式，可视性强具有面向对象的特征22Slide 224、SDL23Slide 23内容SDL语言概述SDL基本概念SDL中的数据24Slide 244-1、SDL语言概述25Slid

9、e 25SDL的应用（1）SDL主要应用于电信领域，适用于描述活性离散系统。活性：是指系统对外来的信号（输入）是有反应（输出）的离散：是指系统与环境的信息交互不是连续的26Slide 26SDL的应用（2）既可以用来说明（specification ）一个系统应具有的行为（behaviour）；又可以用来描述（description ）一个系统实际具有的行为（behaviour）。SDL可用来制作以下文档：需求说明ITU-T建议系统设计说明系统设计描述系统测试说明27SDL的系统和环境系统环境交互信号SDL系统环境信号28SDL系统层次关系系统功能块功能块进程功能块进程进程功能块进程29Sli

10、de 29SDL系统包含关系SDL系统功能块图进程图30Slide 30SDL中的主要术语代理（agent）系统（system）功能块（block）进程（process）信号（signal）信道（channel）状态（state）实例（instance）过程（procedure）数据类型（sort）进程标识（pid）31Slide 31SDL文法概述graphical grammarabstract grammarcommon textual grammarSDL/GRSDL/PRtextualgrammar32Slide 324-2、SDL基本概念33Slide 33系统（1）SDL系统：完

11、整地描述一个真实系统或一个真实系统中相对独立的一部分。一个系统可以划分为若干个功能块；功能块之间以及功能块与环境之间用信道相连。系统各功能块之间以及功能块与环境之间可以使用信号通信；信号通过信道来传递。系统的文本域：用来定义信号、信号列表、数据类型、变量等，这些定义包含在文本符内。系统的交互域：描述系统图中功能块的划分情况以及信道的设置情况。34Slide 34系统（2）35Slide 35功能块（1）功能块包括一个或多个并发的功能块或进程；功能块文本域定义本功能块内部信号、信号列表、数据类型等内容；功能块的交互域描述本功能块中功能块或进程的组成及交互关系；在功能块图的边界上，要标出与本功能块

12、相连的信道标识。36Slide 36功能块（2）37Slide 37功能块（3）38Slide 38进程（1）进程是系统的基本组成单位，系统的行为主要由进程来描述；进程图中每个进程实例都有一块私有存储空间，记录进程图中定义的变量的数值及实例所处的状态。39Slide 39进程（2）进程实例一旦被创建，就拥有了一个自己的pid，通过以下四种pid表达式可以得到进程实例的pid：self返回本进程实例的pid；sender返回发送最近被消耗信号的进程实例的pid；parent返回创建本进程实例的进程实例（父进程）的id；offspring返回最近被本进程创建的进程实例（子进程）的 pid。40Sl

13、ide 40进程（3）进程中可以定义过程，过程图可被包含在进程图中，也可单独定义。在进程图中用过程符来说明定义关系。如果在进程图中包含了过程符，则在SDL描述中必然有具有相同过程名的过程图存在。过程只能由包含该过程的进程的实例来调用，如果该进程以外的代理实例要调用该过程，就必须把该过程声明为远端过程（remote procedure）。41proc1状态机图进程（4）use process 定义变量等42Slide 42过程（1）过程是进程的一部分过程不存在过程实例，它可由包含该过程的进程集的所有实例来调用过程用过程图来定义过程中还可以定义过程过程可以带参数，参数类型有三种：in/out，in

14、，out；过程还可以定义成返回型过程，返回值类型定义跟在形参定义后面过程可以有状态，但过程没有独立的输入队列43Slide 43过程（2）procedure Proc1in/out x integer, in y integer- rslt char定义变量、定时器等过程图形域use 44Slide 44过程（3）过程图形域是过程的主体内容，与状态机图形域基本相同，但有以下不同：起始符不同，过程起始符定义为：状态机图可以没有终止符，而过程图必须有至少一个返回符，返回符定义为：带表达式的返回符仅用于要求返回值的过程，表达式的值即为本次过程调用的返回值45Slide 45通信SDL系统的通信手段包

15、括系统与环境之间或系统中的各代理之间交互信号远程过程调用使用远端变量46Slide 46信道（1）信道是用在代理与代理之间或代理与系统环境或信关之间传递信号的通道。信道分为单向和双向两种，在每个方向上需列出在该方向上传递的所有信号，这些信号用方括号（ ）括起来，标在信道的箭头处。信道分为：延迟信道：表示信号从源端到目的端要经过一定延迟，延迟时间是不确定的，但信道上的信号仍是有序的非延迟信道：表示信号从源端发出后直接到达目的地，没有延迟47Slide 47信道（2）延迟信道（单向）延迟信道（双向）非延迟信道（单向）非延迟信道（双向）48Slide 48信号（1）信号是SDL系统中代理之间通信的基

16、本单位信号必须在信道中传输要利用信号来通信，必须：信号定义：在相关代理图的文本域中定义信号；信号与信道关联：在信道的信号列表域中列出信号，说明信号可以在哪些信道中传递信号可以定义参数，定义过的信号可以用来定义信号列表。信号列表的定义也在文本符中定义。在信道上列出信号和/或信号列表时，信号列表标识符要用圆括号括起来，以区别于信号49Slide 49信号（2）定义举例signal call_hkof,call_hkon,dial_number(integer);signal called_hkof,called_hkon;Signal timeout(char,integer);signallis

17、t call_input=call_hkof,call_hkon,dial_number,timeout;signallist called_input=called_hkof,called_hkon,timeout;50Slide 50信号（3）51Slide 51状态机开始域（1）每个状态机有且仅有一个开始域开始域由开始符下接迁移过程组成开始符迁移过程：迁移过程由一系列动作组成，如输出信号、变量赋值、调用过程、创建实例等。52Slide 52状态机开始域（2）开始域的一般情况最简单的开始域是从开始符直接进入状态in i_ s ta te53Slide 53状态机状态（1）一个状态机包含若干

18、种状态状态符状态符下面可以连接的图形节点输入符优先输入符连续信号符保存符54Slide 54状态机状态（2）状态符与其它图形符号的连接关系图s155Slide 55状态机状态（3）状态列表的四种情况单个状态名s1msg56Slide 56状态机状态（4）多个状态名：表示在这几个状态下，同一事件引起的过程迁移是相同的s1，s2msg57Slide 57状态机状态（5）*：表示某一事件在本状态机所有状态下引起的迁移过程是相同的*msg58Slide 58状态机状态（6）*（状态列表1）：表示某一事件在本状态机除状态列表1中列出的状态以外的所有状态下引起的迁移过程是相同的*(s1，s2)msg59状

19、态机状态（7）下一状态：状态机经过迁移过程后进入下一状态s1s2s1-s1s160Slide 60状态机触发事件（1）触发事件是激发状态机从当前状态迁移到下一状态的事件。触发事件包括：输入、优先输入、连续信号状态机消耗一条信号后，用sender函数可得到发送该信号的代理实例的pid；但如果该信号来自环境，则sender函数返回的值将不同于系统内的任何一个pid值。61Slide 61触发事件输入（1）输入表示状态机接收并消耗信号一个状态机对应一个输入队列状态机输入队列按先进先出的原则排序输入用输入符表示输入符内可以包含多条信号，表示在本状态下，输入这几条信号引起的迁移过程是一样的62触发事件输

20、入（2）msgmsg1，msg2T63触发事件输入（3）多信号输入引起同一迁移过程msg2msg1*64触发事件输入（4）信号可以带参数，对于带参数的信号输入，在输入符中，除给出信号标识外，还需给出具有相应数据类型的变量名来接收参数值msg(x,y,z)msg(,z)msg(x)65Slide 65触发事件输入（5）带使能条件的输入msg1xmax66触发事件输入（6）自发输入noneoddnoneeven67Slide 67触发事件优先输入（1）优先输入可以使信号在某状态下一旦输入就立即处理优先输入用优先输入符表示优先输入符优先输入符下不接使能条件符68触发事件优先输入（2）S1sig1si

21、g269Slide 69触发事件连续信号（1）通过计算布尔表达式的值来触发状态机ymax70触发事件连续信号（2）带优先级的连续信号：当多个连续信号的布尔表达式计算结果为“真”时，取优先级最高者作为触发信号x3;priority 1y8; priority 271Slide 71状态机保存（1）保存可以将提前到达输入队列的有效信号保存下来保存用保存符来表示被保存下来的信号在下一状态中将优先得到处理，但前提是下一状态的输入符中包含了该信号如果在新的状态下，被保存的信号没有出现在该状态的输入符中，则该信号将被丢弃。72状态机保存（2）S1sig2sigbS2sig1S2sig3sigcS3sig1

22、sigaS4信号到达顺序：1）sig1, sig2, sig3；2）sig2, sig3, sig1Slide 7273Slide 73迁移过程概述（1）状态机所要完成的动作集中在迁移过程中这些动作包括：任务输出信号设置定时器复位定时器输出变量值创建代理实例调用过程调用远端过程等74Slide 74迁移过程概述（2）迁移过程结束于以下几种情况： 到达状态 仅适用于从开始域进入的迁移过程； 到达下一状态 完成状态转移； 到达分支域 产生多个分支，每个分支将开始一个新的迁移过程； 到达终止符 进程实例到此终止（stop）； 合并到另一个迁移过程中 合并点以下的操作对两个迁移过程是相同的； 遇出连接

23、符 后续动作将在具有相同连接名的入连接符开始的迁移过程中继续； 到达返回符 适用于过程返回的情况75Slide 75迁移过程输出（1）输出的作用是通过信道把信号发送到另一代理实例输出操作是代理之间通信的基础输出符定义：输出信号可以是一个或多个带参数的信号在输出符中需要给出实际参数值76迁移过程输出（2）输出举例to status1s3p1_pid:=senders2 to p1_pidstatus2Slide 7677Slide 77迁移过程输出（3）to status1s3status2s1 to p378Slide 78迁移过程输出（4）via status1s3status2s1 via

24、 c2via c179Slide 79迁移过程输出（5）P1P2P3S1,S2S5,S6S1,S7C1C2S3,S4在进程P2中，以下输出是允许的：S1 to P3S1 via C1S7 via C2S2via C2在进程P2中，以下输出是不允许的：因为信号S1可通过两条信道C1和C2发送出去S180Slide 80迁移过程输出（6）信号中参数的使用 声明信号时,按顺序给出各参数的数据类型signal s1(integer,boolean,octet); 输出信号时,为每个参数赋值s1(var_send_int,var_send_bool,var_send_octet); 输入信号时, 使用同

25、类型变量来接收各参数值s1(var_rece_int,var_rece_bool,var_rece_octet); 定义信号列表时,信号名后不需要带参数signallist sig_list=s1,s2,s3; 保存信号时,信号名后不需要带参数s1,s2,s381Slide 81迁移过程创建代理实例代理实例的创建分为两种： 静态创建 动态创建实例创建符代理实例被创建后，该实例的self和parent就被赋好了值。创建是否成功的判断82caller(0,128)S1C1manager(1,1)callercaller_pid:=offspringcaller_pid=NULLfalseS1 to

26、 caller_pidSlide 82true83Slide 83迁移过程任务（1）任务执行与变量有关的动作，如给变量赋值、计算表达式等任务符一个任务符中可以包含多条语句，语句之间用分号（；）隔开；在任务符中的语句可以有下列几种： 赋值语句 IF语句 分支语句 组合语句 设置语句（设置定时器） 复位语句（复位定时器）84x:=9;Flag:=true;y:=119.5赋值语句decision (a) (100) m:=n;else m:=n+1IF语句a:=b+1;if (b7) b:=1;else b:=b+1组合语句85Slide 85迁移过程任务（2）任务符中还可以包含非形式化文本，非形

27、式化文本是用单引号括起来的字符串非形式化文本被视为注释内容，不会被执行在下列场合下可使用非形式化文本： 在开发过程中，当部分功能描述还未细化时，可用非形式化文本来说明这部分功能； 系统中需要说明一些对硬件的操作时，可用非形式化文本来说明； 当SDL文档不需要详细描述时，可用非形式化文本做简要说明； 当SDL文档主要用来供人阅读理解时，可用非形式化文本来说明 在SDL图中嵌入编程语言语句86Slide 86迁移过程过程调用（1）允许有任务的地方都可使用过程调用过程调用就是执行一遍过程描述的功能过程与任务的区别 过程可以有状态，过程使用调用该过程的代理实例的输入队列 过程中可以发送信号，过程发出的

28、信号相当于调用该过程的代理实例发出的信号过程的调用x:=call 87process caller1(18)setdataSlide 87迁移过程过程调用（2）过程调用方法步骤1在包含该过程的进程中声明该过程88procedure setdata1(1)fpar in/out number integer;number:=128Slide 88迁移过程过程调用（3）步骤2 描述该过程的功能89process caller8 (18)idles1(send_data)setdata(set_number)s2(set_number) to p1State_nSlide 89迁移过程过程调用（4）

29、步骤3 调用该过程90Slide 90迁移过程分支操作分支操作用来结束一个迁移过程，然后根据表达式的值产生多个新的不同迁移过程分支符：分支符有一个入口，两个或多个出口可以为表达式、非形式文本或any“any”表示将随机产生分支。这种分支操作可用来描述一些不确定或不可靠的情况91具有多个出口的分支操作x+ybafalsetrue1else具有两个出口的分支操作any92Slide 92迁移过程连接连接的功能是把属于同一迁移过程的两部分连接起来连接符93processp18(18)s1setupSetup_ack to p21Slide 9394processp112(18)1set(T)Setu

30、p to p3wait_ackSlide 9495迁移过程合并迁移过程s1Tsignal1reset(T)signal3s2signal2reset(T)signal4set(T)s396Slide 96定时器操作（1）定时器用来设置等待某事件发生的时间定时器的操作 设置定时器：在系统中启动一个定时器 复位定时器：停止计时定时器的应用方法 声明定时器：定时器可以带参数，参数主要用来区别不同的监视对象:timer wait_sig_time(user_id):=wait_duration;如果定时器每次设置的时间都一样，可以在定义时给其赋值:timer T,T1=60.0; 定时器设置:set(

31、now+var_duration,T) set(T1) 复位定时器:reset(T); reset(T1); reset(T2(1)97定时器操作（2）定时器超时用包含定时器名的输入符来表示，对于带参数的定时器，需用具有相同数据类型的变量来接收参数值TT2（X）T198Slide 984-3、SDL中的数据99Slide 99内容概述数据的定义数据的使用100Slide 100SDL中的数据概述数据类（Data Type）:数据类型（Sort）+ 操作（Operation）数据类型：数据项或元素的集合数据类型元素：数值（value）、对象（object）、进程标识（pid）布尔数据项： 布尔数

32、据类型包含两个元素：false，true 支持的操作：=，/=，not，and，or，xor，=101数据定义数据类（data type）定义预定义数据类结构（struct）选择（choice）通过特殊化（specialization）定义新数据类同义类（Syntype）定义同义词（Synonym）定义Slide 101定义新数据类通过使用预定义生成器定义新数据类串（String）数组（Array）通过使用数据类构造器定义新数据类字面量（literals）102Slide 102预定义数据类（1）SDL中预定义的数据类包括：Boolean：布尔型Character：字符型Charstring：

33、字符串型Integer：整型Natural：自然数型Real：实数型Pid：进程标识型Duration：时长类型103Slide 103预定义数据类（2）Boolean类= : Boolean, Boolean - Boolean 蕴涵操作：如果第一个操作数为true，第二个操作数为false，则操作结果为false；否则操作结果为true。既：true = true = truetrue = false = falsefalse = true = truefalse = false = true104Slide 104预定义数据类（3）Character类num : Character -

34、Integer;num（A）=65chr : Integer- Characterchr(65)=“A”105Slide 105预定义数据类（4）Charstring类first:Charstring-character;first(hello)=hmkstring:Character-charstring;length:Charstring-integer;length(Hello)=5;last:Charstring-character;last(hello)=o106Slide 106预定义数据类（4）Real类float : Integer-Real;float(100)=100.0f

35、ix:Real-floatfix(138.6)=138107newtype S1元素类为整型string(Integer, Empty)endnewtype;Empty代表空串Slide 107预定义生成器串（String）S1是一个由Integer 构成的串108newtype A1为CharacterArray(Character, Integer)endnewtype;元素类型为IntegerSlide 108预定义生成器数组（Array）A1是一个通过字符值来索引的数组数据类的索引类型109Slide 109数据类构造器字面量（Literals）newtype colorsLitera

36、ls red, yellow, blue, greenendnewtype;使用Literals定义的数据类支持以下操作：赋值操作、比较操作、first、last、succ、pred、numdcl color colors；数据类构造器通过列举或构造数据类型中元素的方法来描述数据类型的内容。110Slide 110数据类构造器结构（Struct）例：newtype Person StructName Charstring;Age Integer;Address Charstring;PhoneNumber Charstring;endnewtypedcl p1 Person;111Slide 111数据类构造器选择（Choice）例：newtype C1 choicea Integer;b Charstring;c Boolean;endnewtype;dcl var C1;var!a=5;112定义新的数据类特殊化（Specialization）newtype this_struct structa Integer;b Character;endnewtype;newt