【正文】 ng how FSMs are colocated different methods of munications are possible (message passing, shared memory, … ) 第 3章 協(xié)議形式化描述技術(shù) (1－概述及 FSM) 75 Comm. Mechanisms for Concurrent Syst. ?Message passing involves sending and receiving messages through a channel Process Process Shared Memory Write Read Process Process Receive Send Channel ?In the Shared Memory Approach memory is mon to both processes, and they can read and write to the memory ?The two are equivalent. We will only consider message passing as more general. 第 3章 協(xié)議形式化描述技術(shù) (1－概述及 FSM) 76 Asynchronous amp。 Synchronous Communication ? There are two approaches to implementing message passing: Synchronous amp。 Asynchronous ?In Synchronous Communication ?the processes involved in munication are required to participate at the point of munication simultaneously. If Process A attempts to send a message and Process B is not ready to receive it process A must wait until Process B is ready. 第 3章 協(xié)議形式化描述技術(shù) (1－概述及 FSM) 77 Asynchronous Communication ? In Asynchronous Communication ? the processes involved in munication are not required to participate at the point of munication simultaneously. ? If Process A attempts to send a message and Process B is not ready to receive it sends it anyway. ? If process B is ready to receive a message and A has not sent it process B must wait. ? Asynchronous munication requires the use of buffers to store messages ? All of the protocol specification methods studied in this course will be based upon Asynchronous Communication 第 3章 協(xié)議形式化描述技術(shù) (1－概述及 FSM) 78 Asynchronous Communication using FIFOs ? In most municating systems, a FIFO (First In First Out) discipline is enforced on sending and receiving messages. ?During a send event the a message is appended to the end of the queue while a receive event removes a message from the front of a queue. ?It is possible to modify the munications channel to provide additional munication constructs such as priority signals. ?To absorb any delay variation in the munications channel, FIFOs are usually used at the interfaces 第 3章 協(xié)議形式化描述技術(shù) (1－概述及 FSM) 79 Asynchronous Communication using FIFOs Process Process FIFO CHANNEL FIFO CHANNEL Send Receive Receive Send 第 3章 協(xié)議形式化描述技術(shù) (1－概述及 FSM) 80 Communicating FSMs ? Now consider a model for municating finite state machines. ?Each process can be defined by a set of states. ?The process waits in a state for an event to occur. ?Messages are received as events by the receiving FSM. ?When this input event occurs, it transitions to another state, and in doing so can send out messages and performs other tasks. ?This model is the model used by the ITU Specification and Description Language (SDL) 第 3章 協(xié)議形式化描述技術(shù) (1－概述及 FSM) 81 Communicating FSMs Example S11 S12 Receive(Y)/ Send(R) Receive(X)/ Send(P) S21 S22 Receive(R)/ Send(X) Receive(P)/ Send(Y) FSM1 FSM2 Y 第 3章 協(xié)議形式化描述技術(shù) (1－概述及 FSM) 82 Communicating FSMs Example R Y P X FSM1 FSM2 Y After receiving event Y FSMs will continue to oscillate indefinitely between their two states 第 3章 協(xié)議形式化描述技術(shù) (1－概述及 FSM) 83 Benefits of the Communicating FSM model ? The overall state of the system can be described by a vector of all the states of the individual processes. ?The overall system state itself bees a finite state machine, and thus its behaviour bees more deterministic. 第 3章 協(xié)議形式化描述技術(shù) (1－概述及 FSM) 84 FSMs Summary ? Meaning of FSM ? Discrete event processes and finite state machines are key concepts in modelling the dynamic realtime behaviour of telemunications software. ? FSM consist of ? States (Initial, Current and New) ? Input Events ? Output Events ? In case when “state explosion” is an issue extended FSM (EFSM) may be used so some states are replaced by local variables ? Complex Telemunication Systems can be modelled as number of municating FSMs 第 3章 協(xié)議形式化描述技術(shù) (1－概述及 FSM) 85 Protocol Specification amp。 FSMs ?Many Formal protocol methods are based upon Finite State Machines. ?The ITU Specification and Description Language (SDL) is one such formal specification method ?Most protocols defined by ITU after the advent of SDL are described using SDL. ?Prior to the introduction of SDL protocols were described using a variety of different methods including natural language. 第 3章 協(xié)議形式化描述技術(shù) (1－概述及 FSM) 86 Protocol Specification amp。 FSMs ?Even with the advent of formal specification languages there still exist ambiguities and inpleteness in the protocol specifications that must be resolved in the software design ?Even formally specified protocols may not have been validated sufficiently. ?The standards don’t include machine dependent details (like create application process) leaving the software designer to fill the gaps in. 第 3章 協(xié)議形式化描述技術(shù) (1－概述及 FSM) 87 FSM: 思考題 ?畫出自動(dòng)回叫系統(tǒng)的有限狀態(tài)機(jī)狀態(tài)變遷圖。 自動(dòng)加叫： 在被呼叫方正忙的情況下，系統(tǒng)繼續(xù)保持對(duì)被呼叫方狀態(tài)的檢測(cè)，一旦被呼叫方出現(xiàn)空閑狀態(tài)，則系統(tǒng)將再次對(duì)其進(jìn)行呼叫 。過程如下： ? A呼叫 B，但 B的電話正忙； ? A按下“自動(dòng)回叫”鍵； ? A聽到確認(rèn)提示，然后放下電話； ? B回到了空閑狀態(tài)； ? A端的電話進(jìn)行特殊的響鈴提示，說明 B已經(jīng)處于空閑狀態(tài)； ? A拿起聽筒； ?系統(tǒng)自動(dòng)地再次向 B發(fā)出呼叫； ? B拿起聽筒； ? A與 B通話 第 3章 協(xié)議形式化描述技術(shù) (1－概述及 FSM) 88 FSM：思考題（續(xù)） 需考慮的特殊情況： ?如果有多個(gè)用戶同時(shí)針對(duì)同一個(gè)目的端使用自動(dòng)回叫服務(wù)，將如何處理？ ?當(dāng)系統(tǒng)檢測(cè)到目的端空閑，并向發(fā)起呼叫的用戶響鈴提示時(shí)，如果該用戶不命起聽筒（例如改變了主意，不再希望與 B通話），那么將如何處理？ ?在系統(tǒng)向呼叫發(fā)起端進(jìn)行響鈴?fù)ㄖ倪^程中，如果目的端又重新進(jìn)行了忙的狀態(tài)，此時(shí)將如果處理？ ?在自動(dòng)呼叫結(jié)束前，如果呼叫發(fā)起端希望取消自動(dòng)呼叫服務(wù)（例如掛斷了電話），此時(shí)系統(tǒng)將如何處理？