第2章 有限狀態(tài)機(jī)及其擴(kuò)展

1、1Chapter 2 有限狀態(tài)機(jī)及其擴(kuò)展有限狀態(tài)機(jī)及其擴(kuò)展 o有限狀態(tài)機(jī)有限狀態(tài)機(jī) n 有限狀態(tài)機(jī)是有限計(jì)算的基本模型，也是許多形式化規(guī)格、驗(yàn)證方法的基礎(chǔ)模型。o Statecharts n Statecharts是通過(guò)定義遞階狀態(tài)、狀態(tài)的AND或OR分解等高級(jí)特性的有限狀態(tài)機(jī)的一種擴(kuò)展形式。2（一）（一） 有限狀態(tài)機(jī)有限狀態(tài)機(jī)（1） 基本概念基本概念 有限狀態(tài)機(jī)（有限狀態(tài)機(jī)（finite state machine）或有限自動(dòng)機(jī)）或有限自動(dòng)機(jī)（finite automata）是有限計(jì)算的基本模型，是許多形式化）是有限計(jì)算的基本模型，是許多形式化規(guī)格、驗(yàn)證方法的基礎(chǔ)模型。規(guī)格、驗(yàn)證方法的基礎(chǔ)模

2、型。 超級(jí)商場(chǎng)的自動(dòng)門(mén)控制器超級(jí)商場(chǎng)的自動(dòng)門(mén)控制器 自動(dòng)門(mén)的前、后分別有兩個(gè)緩沖自動(dòng)門(mén)的前、后分別有兩個(gè)緩沖區(qū)。自動(dòng)門(mén)的前緩沖區(qū)用來(lái)檢測(cè)是否有人接近。自動(dòng)門(mén)的區(qū)。自動(dòng)門(mén)的前緩沖區(qū)用來(lái)檢測(cè)是否有人接近。自動(dòng)門(mén)的后緩沖區(qū)，使得控制器把門(mén)打開(kāi)足夠長(zhǎng)的時(shí)間讓人走進(jìn)去，后緩沖區(qū)，使得控制器把門(mén)打開(kāi)足夠長(zhǎng)的時(shí)間讓人走進(jìn)去，并且不讓門(mén)在打開(kāi)的時(shí)候碰到站在它附近的人。自動(dòng)門(mén)控并且不讓門(mén)在打開(kāi)的時(shí)候碰到站在它附近的人。自動(dòng)門(mén)控制器依據(jù)前緩沖區(qū)、后緩沖區(qū)的檢測(cè)信息給出打開(kāi)或閉合制器依據(jù)前緩沖區(qū)、后緩沖區(qū)的檢測(cè)信息給出打開(kāi)或閉合的動(dòng)作指令。的動(dòng)作指令。 自動(dòng)門(mén)的動(dòng)作控制應(yīng)滿足如下要求（規(guī)格）：自動(dòng)門(mén)的動(dòng)作控制應(yīng)滿足

3、如下要求（規(guī)格）： 當(dāng)前緩沖區(qū)和后緩沖區(qū)均無(wú)顧客出現(xiàn)，則自動(dòng)門(mén)處于閉當(dāng)前緩沖區(qū)和后緩沖區(qū)均無(wú)顧客出現(xiàn)，則自動(dòng)門(mén)處于閉合狀態(tài)；合狀態(tài)； 當(dāng)后緩沖區(qū)有顧客出現(xiàn)，則自動(dòng)門(mén)維持其原有狀態(tài)；當(dāng)后緩沖區(qū)有顧客出現(xiàn)，則自動(dòng)門(mén)維持其原有狀態(tài)； 當(dāng)前緩沖區(qū)有顧客且后緩沖區(qū)無(wú)顧客，則打開(kāi)自動(dòng)門(mén)。當(dāng)前緩沖區(qū)有顧客且后緩沖區(qū)無(wú)顧客，則打開(kāi)自動(dòng)門(mén)。前緩沖區(qū)后緩沖區(qū)（1） 基本概念基本概念狀態(tài)集合狀態(tài)集合Q = closed, open；初始狀態(tài)初始狀態(tài) q0 = closed；輸入集合輸入集合 = front, rear, both, neither狀態(tài)轉(zhuǎn)移關(guān)系集合狀態(tài)轉(zhuǎn)移關(guān)系集合 (closed, rear) =cl

4、osed；(closed,both)=closed；(closed, neither)=closed；(closed,front)=open(open, rear) = pen； (open,both) =open； (open, front) = open；(open, neither) = closedclosed：閉合狀態(tài)； open：打開(kāi)狀態(tài)；front：前緩沖區(qū)有顧客；rear：后緩沖區(qū)有顧客；both = front rear：前、后緩沖區(qū)都有顧客；neither = front rear：前、后緩沖區(qū)都無(wú)顧客closed openfrontneitherboth,rear,nei

5、therboth,rear,front前緩沖區(qū)后緩沖區(qū)4（1） 基本概念基本概念模模3計(jì)數(shù)器計(jì)數(shù)器 狀態(tài)集合狀態(tài)集合Q = 0, 1, 2 ；初始狀態(tài)初始狀態(tài) q0 = 0；輸入集合輸入集合 = inc, dec狀態(tài)轉(zhuǎn)移關(guān)系集合狀態(tài)轉(zhuǎn)移關(guān)系集合(0,inc)=1；(0,dec)=2；(1,inc)=2；(1,dec)=0；(2,inc)=0；(2,dec)=1 01dec2incincincdecdecinc：增加1dec：減少15（1） 基本概念基本概念身份認(rèn)證系統(tǒng)身份認(rèn)證系統(tǒng) （合法身份：（合法身份：ABAABA） 狀態(tài)集合狀態(tài)集合Q = 1, 2, 3, 4 ； 初始狀態(tài)初始狀態(tài) q0

6、= 1； 終結(jié)狀態(tài)集合終結(jié)狀態(tài)集合 F = 4； 輸入集合輸入集合 = A, B, C 狀態(tài)轉(zhuǎn)移關(guān)系集合狀態(tài)轉(zhuǎn)移關(guān)系集合 (1,A)=2；(1,B)=1；(1,C) =1；(2,A)=2；(2,B)=3；(2,C) =1；(3,A) =4；(3,B)=1；(3,C) =1 ABCACA AABCABA 12A3B,CB,CCBA4A6（1） 基本概念基本概念有限狀態(tài)機(jī)是一個(gè)五元組 M = (Q, , , q0, F)，其中 Q = q0, q1, qn是有限狀態(tài)集合。在任一確定的時(shí)刻，有限狀態(tài)機(jī)只能處于一個(gè)確定的狀態(tài)qi； = 1,2, m是有限輸入字符集合。在任一確定的時(shí)刻，有限狀態(tài)機(jī)只能接

7、收一個(gè)確定的輸入j； ：Q Q是狀態(tài)轉(zhuǎn)移函數(shù)。如果在某一確定的時(shí)刻，有限狀態(tài)機(jī)處于某一狀態(tài)qiQ，并接收一個(gè)輸入字符j，那么下一時(shí)刻將處于一個(gè)確定的狀態(tài)q = (qi，j)Q。在這里規(guī)定q = (q，) ； q0 Q是初始狀態(tài)，有限狀態(tài)機(jī)由此狀態(tài)開(kāi)始接收輸入； F Q是終結(jié)狀態(tài)集合，有限狀態(tài)機(jī)在達(dá)到終結(jié)態(tài)后不再接收輸入。 7（1） 基本概念基本概念一個(gè)有限狀態(tài)機(jī)包括：一個(gè)有限狀態(tài)集，用于描述系統(tǒng)中的不同狀態(tài)；一個(gè)輸入符號(hào)集，用于表征系統(tǒng)所接收的不同輸入信息；一個(gè)狀態(tài)轉(zhuǎn)移函數(shù)，用于表述系統(tǒng)在接收不同輸入下,從一個(gè)狀態(tài)轉(zhuǎn)移到另外一個(gè)狀態(tài)的規(guī)則。 狀態(tài)轉(zhuǎn)移函數(shù):刻畫(huà)其行為的最關(guān)鍵部分, 一個(gè)從Q到Q

8、的二元函數(shù)。狀態(tài)轉(zhuǎn)移函數(shù)通?？梢杂藐P(guān)系矩陣、狀態(tài)轉(zhuǎn)移表或狀態(tài)轉(zhuǎn)移圖的形式來(lái)表示。有限狀態(tài)機(jī)可用四元組 M = (Q, , , q0)或三元組 M = (Q, , )來(lái)表示。8（1） 基本概念基本概念o 狀態(tài)轉(zhuǎn)移矩陣 用行表示狀態(tài)機(jī)所處的當(dāng)前狀態(tài)，列表示將要到達(dá)的下一個(gè)狀態(tài)，行列交叉處表示輸入字符。稱該矩陣為轉(zhuǎn)移函數(shù)的關(guān)系矩陣，或者有限狀態(tài)機(jī)M 的狀態(tài)轉(zhuǎn)移矩陣。模3計(jì)數(shù)器 0 1 20 inc dec2 inc dec1 dec inc狀態(tài)轉(zhuǎn)移矩陣9o 狀態(tài)轉(zhuǎn)移表 用表格的行表示狀態(tài)機(jī)所處的當(dāng)前狀態(tài)，列表示當(dāng)前的輸入字符，行列交叉處表示要到達(dá)的下一個(gè)狀態(tài)。稱該表格為M的狀態(tài)轉(zhuǎn)換表。模3計(jì)數(shù)器 輸

9、入字符狀態(tài)inc dec1 20 12 0 012狀態(tài)轉(zhuǎn)移表10o 狀態(tài)轉(zhuǎn)移圖 用圓圈（結(jié)點(diǎn)）表示狀態(tài)；將存在轉(zhuǎn)移關(guān)系的狀態(tài)用有向弧連接，并標(biāo)注相應(yīng)的輸入字符在有向弧旁；用標(biāo)有箭頭的結(jié)點(diǎn)表示初始狀態(tài)；屬于終結(jié)狀態(tài)集中的狀態(tài)用雙圈表示。 01dec2incincincdecdec狀態(tài)轉(zhuǎn)移圖模3計(jì)數(shù)器 11（1） 基本概念基本概念p 前面討論的有限狀態(tài)機(jī)，可以看作僅接受輸入符號(hào)并發(fā)生狀態(tài)改變，但無(wú)任何輸出的自動(dòng)機(jī)器。p 現(xiàn)實(shí)生活中的許多有限狀態(tài)系統(tǒng),對(duì)于不同的輸入信號(hào)，除內(nèi)部狀態(tài)不斷改變外，還不斷向系統(tǒng)外部輸出各種信號(hào)。p 將有限狀態(tài)機(jī)進(jìn)行推廣，引出具有輸出機(jī)制的自動(dòng)機(jī)器模型。p 帶輸出的自動(dòng)機(jī)器

10、模型，按照輸出的不同分成兩類：輸出與狀態(tài)有關(guān)Moore機(jī)機(jī)；輸出與狀態(tài)和輸入有關(guān)Mealy機(jī)機(jī)。 12（1） 基本概念基本概念Moore機(jī)形式定義為六元組M = (Q, , , , , q0)，其中 Q = q0,q1,qn是有限狀態(tài)集合； = 1,2,m是有限輸入字符集合； = a1,a2,ar是有限輸出字符集合； ：Q Q是狀態(tài)轉(zhuǎn)移函數(shù)； ：Q 是輸出函數(shù)； q0 Q是初始狀態(tài)。 1/10/01/20/11/00/2q0q2q1例例：模：模3余數(shù)余數(shù)Q = q0，q1，q2= 0，1(qj) = j, j = 0,1,2在輸入010100 下，輸出為012212 13（1） 基本概念基本概

11、念Mealy機(jī)形式定義為六元組M = (Q, , , , , q0)，其中 Q = q0,q1,qn是有限狀態(tài)集合； = 1,2,m是有限輸入字符集合； = a1,a2,ar是有限輸出字符集合； ：Q Q是狀態(tài)轉(zhuǎn)移函數(shù)； ：Q 是輸出函數(shù)； q0 Q 是初始狀態(tài)。 狀態(tài)轉(zhuǎn)移函數(shù)為：(q0,0) = q1, (q0,1) = q2, (q1,1) = q2, (q1,0) = q1, (q2,1) = q2, (q2,0) = q1輸出函數(shù)為： (q0,0) = n, (q0,1) = n, (q1,1) = n, (q1,0) = y, (q2,1) = y, (q2,0) = n。在輸入01

12、100 下，輸出為nnyny 1/y0/n1/n0/y0/n1/nq0q2q114（1） 基本概念基本概念身份認(rèn)證系統(tǒng)（具有條件和變量機(jī)制的有限狀態(tài)機(jī)）(最大允許錯(cuò)誤次數(shù)為3)（err：報(bào)警狀態(tài)； ctr：計(jì)數(shù)變量）Xcon/Yexec含義在于：所標(biāo)注的狀態(tài)轉(zhuǎn)移關(guān)系在輸入x且條件con成立下，轉(zhuǎn)移至下一狀態(tài)，并輸出y且執(zhí)行exec。標(biāo)注中的各項(xiàng)x、con、y或exec可以缺省。12A3B,Cctr3/ctr:=ctr+1 BA4errCctr3/ctr:=ctr+1 B,Cctr=3/ctr:=ctr+1 B,Cctr=3/ctr:=ctr+1 A,Cctr=3/ctr:=ctr+1 B,Cc

13、tr3/ctr:=ctr+1 Actr3/ctr:=ctr+1 /ctr:= 0 15（1） 基本概念基本概念身份認(rèn)證系統(tǒng)身份認(rèn)證系統(tǒng)err12A3BA4ctr= 2 ctr= 2 ctr= 2 ctr= 2 12A3BA4ctr= 3 ctr= 3 ctr= 3 ctr= 3 12A3BA4ctr= 1 ctr= 1 ctr= 1 ctr= 1 12A3BA4ctr= 0 ctr= 0 ctr= 0 ctr= 0 ctr= 4 B,CB,CB,CB,CB,CB,CB,CB,CA,CCCCAAA16（2） 有限狀態(tài)機(jī)的復(fù)合有限狀態(tài)機(jī)的復(fù)合o 通常，軟件系統(tǒng)是以模塊或子系統(tǒng)的形式出現(xiàn)o 整個(gè)軟件

14、系統(tǒng)的有限狀態(tài)機(jī)規(guī)格,需要對(duì)各個(gè)模塊的有限狀態(tài)機(jī)進(jìn)行復(fù)合。o 有限狀態(tài)機(jī)復(fù)合的最簡(jiǎn)單方式是笛卡爾積o 有限狀態(tài)機(jī)的笛卡爾積復(fù)合,規(guī)格了多個(gè)有限狀態(tài)機(jī)相互獨(dú)立運(yùn)行的行為。o 軟件系統(tǒng)之間存在交互問(wèn)題，有限狀態(tài)機(jī)的復(fù)合也必然涉及交互問(wèn)題。17（2） 有限狀態(tài)機(jī)的復(fù)合有限狀態(tài)機(jī)的復(fù)合有限狀態(tài)機(jī)M1 = (Q1, 1, 1, q10)和M2 = (Q2, 2, 2, q20) 的笛卡爾積為M = M1 M2 = (Q, , , q0)，其中， Q = Q1Q2； = (1 )(2 )； q0 = (q10, q20) Q1Q2； (q1, q2), (a1, a2) = (q1, q2) 1(q1,

15、a1)=q1，a2 = ，a11 (q1, q2) 2(q2, a2)=q2，a1 = ，a22 (q1, q2) 1(q1, a1)=q1，2(q2, a2)=q2，a11，a22 無(wú)定義無(wú)定義 其余其余 18（2） 有限狀態(tài)機(jī)的復(fù)合有限狀態(tài)機(jī)的復(fù)合01dec2incincincdecdec模模3計(jì)數(shù)器計(jì)數(shù)器模模4計(jì)數(shù)器計(jì)數(shù)器01dec2incincdec3incincdecdecdeco 模3和模4計(jì)數(shù)器的笛卡爾積復(fù)合有34=12個(gè)狀態(tài)o 每個(gè)狀態(tài)下，兩個(gè)模計(jì)數(shù)器均可相互獨(dú)立地進(jìn)行加數(shù)、減數(shù)或保持不變19（2） 有限狀態(tài)機(jī)的復(fù)合有限狀態(tài)機(jī)的復(fù)合o 每個(gè)狀態(tài)有33=9種狀態(tài)轉(zhuǎn)移選擇，但其中一

16、種為無(wú)任何狀態(tài)轉(zhuǎn)移發(fā)生，故只有8種狀態(tài)轉(zhuǎn)移。o 其笛卡爾積復(fù)合具有128=96個(gè)狀態(tài)轉(zhuǎn)移2,02,12,32,21,01,11,31,20,00,10,30,2dec,decinc,inc,decinc,incdec,incdec,inc,dec模計(jì)數(shù)器的笛卡爾積模計(jì)數(shù)器的笛卡爾積復(fù)合復(fù)合 20有限狀態(tài)機(jī)的同步積復(fù)合有限狀態(tài)機(jī)的同步積復(fù)合有限狀態(tài)機(jī)M1 = (Q1, 1, 1, q10)和M2 = (Q2, 2, 2, q20) 的同步積復(fù)合為M = M1 M2 = (Q, , , q0)，其中， Q = Q1Q2； = 1 2 ； q0 = (q10, q20) Q1Q2； (q1, q2)

17、, a) = (q1, q2) 1(q1, a)=q1， 2(q2, a)=q2，a1 2 (q1, q2) 2(q2, a)=q2，a1，a2 (q1, q2) 1(q1, a)=q1，a1，a2 無(wú)定義 其余 21有限狀態(tài)機(jī)的同步積復(fù)合有限狀態(tài)機(jī)的同步積復(fù)合模計(jì)數(shù)器的同步積模計(jì)數(shù)器的同步積復(fù)合復(fù)合 2,02,12,32,21,01,11,31,20,00,10,30,2decincp模模3 3和模和模4 4計(jì)數(shù)器，可以進(jìn)行耦合運(yùn)行，阻止各自的獨(dú)計(jì)數(shù)器，可以進(jìn)行耦合運(yùn)行，阻止各自的獨(dú)立運(yùn)行行為。立運(yùn)行行為。只有只有incinc、incinc和和decdec、decdec兩種共兩種共2424個(gè)

18、狀態(tài)轉(zhuǎn)移個(gè)狀態(tài)轉(zhuǎn)移22有限狀態(tài)機(jī)的異步積復(fù)合有限狀態(tài)機(jī)的異步積復(fù)合有限狀態(tài)機(jī)M1 = (Q1, 1, 1, q10)和M2 = (Q2, 2, 2, q20) 的異步積復(fù)合為M = M1 M2 = (Q, , , q0)，其中， Q = Q1Q2； = 1 2 ； q0 = (q10, q20) Q1Q2； (q1, q2), a) = (q1, q2) 2(q2, a)=q2，a2 (q1, q2) 1(q1, a)=q1，a1 無(wú)定義 其余23有限狀態(tài)機(jī)的異步積復(fù)合有限狀態(tài)機(jī)的異步積復(fù)合模計(jì)數(shù)器的異步積模計(jì)數(shù)器的異步積復(fù)合復(fù)合 2,02,12,32,21,01,11,31,20,00,10

19、,30,2incdecincdecp模模3 3和模和模4 4計(jì)數(shù)器，可以進(jìn)行耦合運(yùn)行，但在任何狀態(tài)計(jì)數(shù)器，可以進(jìn)行耦合運(yùn)行，但在任何狀態(tài)下僅有其中一個(gè)模計(jì)數(shù)器運(yùn)行。下僅有其中一個(gè)模計(jì)數(shù)器運(yùn)行。 分別有分別有incinc和和decdec兩種共兩種共4848個(gè)狀態(tài)轉(zhuǎn)移個(gè)狀態(tài)轉(zhuǎn)移（3 3） 生產(chǎn)者生產(chǎn)者- -消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題 生產(chǎn)者消費(fèi)者系統(tǒng)生產(chǎn)者消費(fèi)者系統(tǒng)包含一個(gè)生產(chǎn)者和一個(gè)消費(fèi)者。生產(chǎn)者進(jìn)程產(chǎn)包含一個(gè)生產(chǎn)者和一個(gè)消費(fèi)者。生產(chǎn)者進(jìn)程產(chǎn)生消息，并把產(chǎn)生的消息寫(xiě)入一個(gè)能容納兩個(gè)消息的緩存區(qū)中。生消息，并把產(chǎn)生的消息寫(xiě)入一個(gè)能容納兩個(gè)消息的緩存區(qū)中。 生產(chǎn)者在進(jìn)行“生產(chǎn)”動(dòng)作后，狀態(tài)由P1轉(zhuǎn)變?yōu)镻2

20、；而在“寫(xiě)”動(dòng)作后，狀態(tài)由P2恢復(fù)為P1。消費(fèi)者進(jìn)程能讀取消息，并把消息從緩存器中取走。消費(fèi)者在“讀”動(dòng)作后，狀態(tài)由C1轉(zhuǎn)變?yōu)镃2；而在進(jìn)行“消費(fèi)”動(dòng)作后，狀態(tài)由C2恢復(fù)為C1。如果緩存器是滿的，那么生產(chǎn)者進(jìn)如果緩存器是滿的，那么生產(chǎn)者進(jìn)程必須等待，直到消費(fèi)者進(jìn)程從緩存器中取出一個(gè)消息，程必須等待，直到消費(fèi)者進(jìn)程從緩存器中取出一個(gè)消息，使緩存器產(chǎn)生一個(gè)消息空位。同樣，如果緩存器是空的，使緩存器產(chǎn)生一個(gè)消息空位。同樣，如果緩存器是空的，那么消費(fèi)者進(jìn)程就必須等待，直到生產(chǎn)者進(jìn)程產(chǎn)生一個(gè)那么消費(fèi)者進(jìn)程就必須等待，直到生產(chǎn)者進(jìn)程產(chǎn)生一個(gè)消息并把所產(chǎn)生的消息寫(xiě)入緩存器中。消息并把所產(chǎn)生的消息寫(xiě)入緩存器中

21、。緩存器在進(jìn)行“讀”動(dòng)作后，緩存器大小減“1”，而在“寫(xiě)”動(dòng)作后，緩存器大小加“1”。 生產(chǎn)者生產(chǎn)者P1生產(chǎn)P2寫(xiě)C1讀C2消費(fèi)讀20讀1寫(xiě)寫(xiě)緩存器緩存器消費(fèi)者消費(fèi)者25（3 3） 生產(chǎn)者生產(chǎn)者- -消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題 三個(gè)有限狀態(tài)機(jī) M1 = (P1, P2, 寫(xiě), 生產(chǎn), 1, P1) 、M2 = (C1, C2, 讀, 消費(fèi), 2, C1) 、M3 = (0, 1, 2, 讀, 寫(xiě), 3, 0)，顯然，1 3 讀，2 3 寫(xiě)。三個(gè)有限狀態(tài)機(jī)的同步積復(fù)合M = M1 M2 M3，其中， Q = Q1Q2Q3； = 1 23； q0 = (q10, q20, q30) Q1Q2Q3； (q

22、1, q2, q3), a) = (q1, q2, q3) 1(q1, a,)=q1，2(q2, a,)=q2，3(q3, a,)=q3，a 1 23 (q1, q2, q3) 1(q1, a,)=q1，2(q2, a,)=q2，a 1 2，a 3 (q1, q2, q3) 1(q1, a,)=q1，3(q3, a,)=q3，a 1 3，a 2 (q1, q2, q3) 2(q2, a,)=q2，3(q3, a,)=q3，a 2 3，a 1 (q1, q2, q3 ) 1(q1, a,)=q1，a 1，a 2，a 3 (q1, q2, q3 ) 2(q2, a,)=q2，a 2，a 1，a 3

23、 (q1, q2, q3 ) 3(q3, a,)=q3，a 3，a 1，a 2 無(wú)定義 其余（3 3） 生產(chǎn)者生產(chǎn)者- -消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題寫(xiě)生產(chǎn)讀0, P1,C1 消費(fèi)1, P1,C1 0, P1,C2 2, P1,C1 2, P1,C2 1, P1,C2 消費(fèi)消費(fèi)讀讀0, P2,C1 消費(fèi)1, P2,C1 0, P2,C2 2, P2,C1 2, P2,C2 1, P2,C2 消費(fèi)消費(fèi)讀生產(chǎn)生產(chǎn)生產(chǎn)生產(chǎn)生產(chǎn)寫(xiě)寫(xiě)寫(xiě)生產(chǎn)者生產(chǎn)者P1生產(chǎn)P2寫(xiě)C1讀C2消費(fèi)讀20讀1寫(xiě)寫(xiě)緩存器緩存器消費(fèi)者消費(fèi)者27（3 3） 生產(chǎn)者生產(chǎn)者- -消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題IIII ( (略）略）課堂練習(xí)：生產(chǎn)者消費(fèi)者

24、系統(tǒng)II包含兩個(gè)生產(chǎn)者和一個(gè)消費(fèi)者。生產(chǎn)者進(jìn)程產(chǎn)生消息，并等待消費(fèi)者消費(fèi)。 生產(chǎn)者在進(jìn)行“生產(chǎn)”動(dòng)作后，狀態(tài)由P1轉(zhuǎn)變?yōu)镻2；而在“寫(xiě)”動(dòng)作后，狀態(tài)由P2恢復(fù)為P1。消費(fèi)者進(jìn)程能讀取消息，消費(fèi)者在“讀”動(dòng)作后，狀態(tài)由C1轉(zhuǎn)變?yōu)镃2；而在進(jìn)行“消費(fèi)”動(dòng)作后，狀態(tài)由C2恢復(fù)為C1。生產(chǎn)者進(jìn)程在產(chǎn)生一個(gè)消息后必須等待，直到消費(fèi)者進(jìn)程取出所產(chǎn)生的消息。同樣，如果沒(méi)有生產(chǎn)者進(jìn)程產(chǎn)生的消息，那么消費(fèi)者進(jìn)程就必須等待，直到生產(chǎn)者進(jìn)程產(chǎn)生一個(gè)消息。類似問(wèn)題：生產(chǎn)者消費(fèi)者系統(tǒng)包含兩個(gè)生產(chǎn)者、一個(gè)消費(fèi)者和1個(gè)緩存容量的緩存單元？生產(chǎn)者消費(fèi)者系統(tǒng)包含m個(gè)生產(chǎn)者、n個(gè)消費(fèi)者和b個(gè)緩存容量的緩存單元？（3 3） 生產(chǎn)者

25、生產(chǎn)者- -消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題IIII生產(chǎn)者生產(chǎn)者1P11生產(chǎn)1P12寫(xiě)1C1讀C2消費(fèi)消費(fèi)者消費(fèi)者生產(chǎn)者生產(chǎn)者2P21生產(chǎn)2P22寫(xiě)2P11, P21,C1 P11, P22,C1P11, P21,C2P11, P22,C2消費(fèi)消費(fèi)P12, P21,C1消費(fèi)P12, P22,C1P12, P21,C2P12, P22,C2消費(fèi)生產(chǎn)1生產(chǎn)1生產(chǎn)2生產(chǎn)2生產(chǎn)1生產(chǎn)2生產(chǎn)1生產(chǎn)229有限狀態(tài)機(jī)的缺陷u 在多有限狀態(tài)機(jī)系統(tǒng)中，系統(tǒng)的狀態(tài)為所有狀態(tài)機(jī)的狀態(tài)的笛卡兒（同步、異步）積，因此系統(tǒng)的狀態(tài)數(shù)具有狀態(tài)組合復(fù)雜性問(wèn)題。即使對(duì)于非常簡(jiǎn)單的情況，復(fù)合后系統(tǒng)的狀態(tài)圖的規(guī)模也會(huì)變得非常龐大，甚至無(wú)法進(jìn)行；

26、u 有限狀態(tài)機(jī)模型實(shí)質(zhì)上存在一個(gè)限制性假定：在系統(tǒng)所處的每一個(gè)狀態(tài)上，在任何時(shí)刻，最多執(zhí)行一個(gè)操作。因此，有限狀態(tài)機(jī)僅能夠描述順序系統(tǒng)，無(wú)并發(fā)描述的能力；u 有限狀態(tài)機(jī)不能描述無(wú)限狀態(tài)系統(tǒng)，同時(shí)，缺乏描述時(shí)間特性的機(jī)制。有限狀態(tài)機(jī)也不適合于描述系統(tǒng)的功能和結(jié)構(gòu)特性。 30（二）（二） Statecharts （1） StatechartsStatecharts中的狀態(tài)中的狀態(tài) Statecharts是由以色列的Harel于1987年建立的傳統(tǒng)有限狀態(tài)機(jī)的一種擴(kuò)展形式。Statecharts中通過(guò)引入狀態(tài)的遞階（層次化）、狀態(tài)的“與（AND）”分解和“或（OR）”分解等高級(jí)特性，從而具有了更強(qiáng)的

27、描述能力。Statecharts中狀態(tài)用圓角方框圖示，狀態(tài)名標(biāo)注在圓角方框內(nèi)的上方 。SS2S22S21S1S1FFS3S2T1TSUT231 狀態(tài)的層次化狀態(tài)的層次化 有限狀態(tài)機(jī)在輸入F下均可從狀態(tài)S或T轉(zhuǎn)移到狀態(tài)U。這里可將狀態(tài)S和T合并成一個(gè)新的狀態(tài)，記為狀態(tài)V，并將兩個(gè)狀態(tài)轉(zhuǎn)移弧用一個(gè)弧來(lái)代替。狀態(tài)的層次化通過(guò)框圖的嵌套來(lái)圖示。具有子狀態(tài)的狀態(tài)稱為遞階狀態(tài)，沒(méi)有子狀態(tài)的狀態(tài)稱為簡(jiǎn)單狀態(tài)或者原子狀態(tài)。高級(jí)狀態(tài)或超狀態(tài)、父狀態(tài)、先輩狀態(tài)、子狀態(tài)、后代狀態(tài)（任意深度多層次描述）SFFUT SVFUTSS2S22S21S132 或（或（OR）狀態(tài)、與（）狀態(tài)、與（AND）狀態(tài)）狀態(tài)u狀態(tài)的層次

28、化可以通過(guò)自頂向下的狀態(tài)分解，或自底向上的狀態(tài)合并來(lái)實(shí)現(xiàn)。狀態(tài)的層次化可以通過(guò)自頂向下的狀態(tài)分解，或自底向上的狀態(tài)合并來(lái)實(shí)現(xiàn)。u或（或（OROR）狀態(tài)狀態(tài)：當(dāng)且僅當(dāng)位于該狀態(tài)就是位于其中的一個(gè)子狀態(tài)，即，位于一個(gè)或狀態(tài)不能同時(shí)位于該狀態(tài)的兩個(gè)以上的子狀態(tài)?；驙顟B(tài)表示了子狀態(tài)之間的一種異或關(guān)系。狀態(tài)的或狀態(tài)表示，稱為狀態(tài)的或分解。u與（與（ANDAND）狀態(tài)狀態(tài)：當(dāng)且僅當(dāng)位于該狀態(tài)就是同時(shí)位于其所有的子狀態(tài)。與狀態(tài)表示了子狀態(tài)之間的一種與關(guān)系。狀態(tài)的與狀態(tài)表示，稱為狀態(tài)的正交分解；與狀態(tài)的子狀態(tài)，又稱為狀態(tài)的正交分量。圖形表示中，用虛線將與狀態(tài)的正交分量或子狀態(tài)進(jìn)行隔離，與狀態(tài)的標(biāo)識(shí)符（即，狀態(tài)

29、名）標(biāo)注在和狀態(tài)邊框連與狀態(tài)的標(biāo)識(shí)符（即，狀態(tài)名）標(biāo)注在和狀態(tài)邊框連在一體的小方框內(nèi)在一體的小方框內(nèi)。S1FFS3S2T1TSUT2SS2S22S21S133 （2 2） StatechartsStatecharts中的遷移中的遷移 遷移上的條件、事件和動(dòng)作遷移的輸入遷移的輸入稱為觸發(fā)觸發(fā)（trigger），觸發(fā)可以是事件或者（和）條件。遷移的輸出遷移的輸出稱為動(dòng)作動(dòng)作（action），動(dòng)作可以是產(chǎn)生新的事件或執(zhí)行一個(gè)過(guò)程或函數(shù)等。輸入是狀態(tài)之間遷移發(fā)生的原因，只有當(dāng)一個(gè)遷移的輸入事件出現(xiàn)或者（和）遷移的輸入中條件滿足時(shí)，該遷移所聯(lián)系的狀態(tài)才可發(fā)生轉(zhuǎn)移。動(dòng)作的執(zhí)行被認(rèn)為是瞬時(shí)的。觸發(fā)和動(dòng)作以觸

30、發(fā)和動(dòng)作以“事件事件 條條件件/動(dòng)作動(dòng)作”的形式標(biāo)注在遷移弧旁。的形式標(biāo)注在遷移弧旁。 S1Ein(S1)/Rt=2/FS3S2T1TSRT2RF/EF/R34 遷移上的條件、事件和動(dòng)作遷移上的條件、事件和動(dòng)作預(yù)定義的與狀態(tài)、數(shù)據(jù)項(xiàng)、時(shí)間有關(guān)的條件、事件和動(dòng)作 （P36） 條件：in(S) 表示是否處于狀態(tài)S中，如是則為真，否則為假； ac(A) 表示活動(dòng)A是否處于活動(dòng)狀態(tài)，如是則為真，否則為假； hg(A) 表示活動(dòng)A是否處于掛起狀態(tài)，如是則為真，否則為假；事件：en(S) 表示進(jìn)入狀態(tài)S；ex(S) 表示退出狀態(tài)S；ns表示正在進(jìn)入當(dāng)前狀態(tài)； xs表示正在退出當(dāng)前狀態(tài)；st(A)表示活動(dòng)A

31、被啟動(dòng)；st表示當(dāng)前活動(dòng)被啟動(dòng)；sp(A)表示活動(dòng)A被停止；tr(C)表示條件C變?yōu)檎?；fs(C)表示條件C變?yōu)榧?；rd(X)表示X被動(dòng)作rd!讀；wr(X)表示X被動(dòng)作wr!寫(xiě)；ch(X)表示數(shù)據(jù)項(xiàng)X的值發(fā)生改變；tm(E，N)表示事件E發(fā)生后，已過(guò)了N個(gè)時(shí)間單位。動(dòng)作：tr!(C) 表示對(duì)條件C賦值真；fs!(C) 表示對(duì)條件C賦值假；st!(A)表示啟動(dòng)活動(dòng)A；sp!(A)表示停止活動(dòng)A；sd!(A)表示掛起活動(dòng)A；rs!(A)表示重新開(kāi)始活動(dòng)A；rd!(X) 表示讀數(shù)據(jù)或條件X；wr!(X) 表示寫(xiě)數(shù)據(jù)或條件X；hc!(S) 表示忘記狀態(tài)S的歷史信息；hd!(S) 表示忘記狀態(tài)S的后繼

32、狀態(tài)的歷史信息。事件、條件和動(dòng)作可進(jìn)行邏輯and ,or ,not等運(yùn)算。如：E1 and E2表示事件E1與E2同時(shí)發(fā)生；C1 or C2表示C1和C2的或邏輯運(yùn)算。 遷移與狀態(tài)的連接遷移與狀態(tài)的連接 遷移描述了簡(jiǎn)單狀態(tài)和簡(jiǎn)單狀態(tài)、簡(jiǎn)單狀態(tài)和遞階狀態(tài)、遞階狀態(tài)和遞階狀態(tài)之間的狀態(tài)轉(zhuǎn)移關(guān)系。遷移用有向弧圖示，有向弧可以從一個(gè)狀態(tài)的邊界引出，終止于另一狀態(tài)的邊界，也可以穿過(guò)先輩狀態(tài)的邊界。當(dāng)一個(gè)遷移沒(méi)有指明其源狀態(tài)時(shí)，則稱之為缺省遷移。其所指向的狀態(tài)，稱為缺省狀態(tài)。缺省遷移用圓點(diǎn)箭線弧表示。缺省遷移可以指向一個(gè)狀態(tài)，也可以穿過(guò)先輩狀態(tài)的邊框直接指向某一子狀態(tài)。當(dāng)遷移指向一個(gè)與狀態(tài)時(shí)當(dāng)遷移指向一個(gè)

33、與狀態(tài)時(shí)，則相當(dāng)于指向其所有的子狀態(tài)；，則相當(dāng)于指向其所有的子狀態(tài)；當(dāng)遷移指向當(dāng)遷移指向一個(gè)或狀態(tài)時(shí)一個(gè)或狀態(tài)時(shí)，則相當(dāng)于指向其缺省的子狀態(tài)。當(dāng)退出一個(gè)狀態(tài)時(shí)，則相當(dāng)于指向其缺省的子狀態(tài)。當(dāng)退出一個(gè)狀態(tài)時(shí)，則相當(dāng)退出其所有的子狀態(tài)則相當(dāng)退出其所有的子狀態(tài)。RFS2S22S21S1RFS2S22S21S1URFSS22S21S1TT2T1U36 復(fù)合遷移復(fù)合遷移 o為了簡(jiǎn)化圖形中遷移的有向弧線，Statecharts中引入了一些輔助符號(hào)，從而得到狀態(tài)之間轉(zhuǎn)移關(guān)系的復(fù)合遷移。o條件連接符 也稱為C-連接符，用于條件的連接。Statecharts規(guī)定始于C-連接符的條件分支可以多個(gè)，但是這些條件分支

34、必須是異或的。 S1S3S2C1ECC2S1S3S2EC1EC237 復(fù)合遷移復(fù)合遷移 -開(kāi)關(guān)連接符 開(kāi)關(guān)連接符，也稱為S-連接符，用于事件的連接。 S1S3S2E1ASE2E3S1S3S2AE1AE2AE338 復(fù)合遷移復(fù)合遷移-分叉（匯合）連接符 遷移的觸發(fā)和（或）動(dòng)作的相同部分，可以通過(guò)分叉（匯合）連接符形成一個(gè)單一的弧線進(jìn)入（離開(kāi)）連接符。分叉（匯合）連接符適用于條件連接符和開(kāi)關(guān)連接符所不能描述的情形。 S1S3S2R/ASS1S3S2C1EFS1S3S2SETS1S3S2/AC1E等價(jià) Statecharts圖？39 復(fù)合遷移復(fù)合遷移 -分叉（匯合）結(jié)構(gòu) o分叉（匯合）結(jié)構(gòu)是進(jìn)入（離

35、開(kāi)）與狀態(tài)的子狀態(tài)遷移的一種描述方式。o此類結(jié)構(gòu)下復(fù)合遷移所聯(lián)系的狀態(tài)轉(zhuǎn)移，要求遷移上所有的觸發(fā)同時(shí)滿足，且動(dòng)作也都同時(shí)執(zhí)行。 US1S3SS2S4AE1/A1c2/A2US1S3SS2S4Ac1/A1E2/A240 復(fù)合遷移復(fù)合遷移 -圖形連接符 o圖形連接符可以實(shí)現(xiàn)遷移的異地連接圖形連接符可以實(shí)現(xiàn)遷移的異地連接。用橢圓符號(hào)并標(biāo)注相同的名稱來(lái)圖示。oStatecharts規(guī)定每個(gè)圖形連接符出現(xiàn)與所連接的遷移必須具有相同方向的弧線（離開(kāi)或者進(jìn)入）。 S1INTSS2S3AE1/A1INTRINT41 復(fù)合遷移復(fù)合遷移 -歷史連接符 o歷史連接符規(guī)定系統(tǒng)進(jìn)入一個(gè)狀態(tài)組中的一個(gè)最近訪問(wèn)歷史連接符規(guī)

36、定系統(tǒng)進(jìn)入一個(gè)狀態(tài)組中的一個(gè)最近訪問(wèn)歷史狀態(tài)歷史狀態(tài),用標(biāo)注H的圓圈圖示。o歷史連接符可以理解為一個(gè)特殊的狀態(tài)。進(jìn)入歷史連接符就表示進(jìn)入該連接符所在狀態(tài)組中最近訪問(wèn)的那個(gè)狀態(tài)，若歷史狀態(tài)為空，則進(jìn)入歷史連接符所指向的狀態(tài)。 S1HS2TS從狀態(tài)從狀態(tài)T進(jìn)入狀態(tài)進(jìn)入狀態(tài)S時(shí)，首先進(jìn)入其歷史時(shí)，首先進(jìn)入其歷史狀態(tài)狀態(tài)H，即進(jìn)入最近訪問(wèn)的那個(gè)狀態(tài)。，即進(jìn)入最近訪問(wèn)的那個(gè)狀態(tài)。若上次訪問(wèn)的狀態(tài)為若上次訪問(wèn)的狀態(tài)為S2，則進(jìn)入狀態(tài)，則進(jìn)入狀態(tài)S2。如果如果H為空，則進(jìn)入為空，則進(jìn)入S1狀態(tài)。狀態(tài)。 42 （3 3） 電梯控制系統(tǒng)電梯控制系統(tǒng)o考慮一個(gè)m層的大樓、n個(gè)電梯的服務(wù)系統(tǒng)。需要建立一個(gè)用以描述電

37、梯在樓層之間的運(yùn)動(dòng),并完成電梯控制系統(tǒng)開(kāi)發(fā)的規(guī)格，系統(tǒng)存在如下一些約束和要求：o 每個(gè)電梯內(nèi)部都有一組按鈕，每個(gè)按鈕用于指示一個(gè)樓層。當(dāng)按下某個(gè)按鈕后，該按鈕指示燈就會(huì)發(fā)亮，直到到達(dá)相應(yīng)的樓層后按鈕的指示燈自動(dòng)熄滅；43 電梯控制系統(tǒng)電梯控制系統(tǒng)o 除了最高層和最低層以外，每個(gè)樓層都有兩個(gè)按鈕：一個(gè)用于請(qǐng)求電梯向下移動(dòng)，一個(gè)用于請(qǐng)求電梯向上移動(dòng)。這些按鈕在被按下后，相應(yīng)指示燈就會(huì)發(fā)亮。當(dāng)電梯按照所請(qǐng)求的方向移動(dòng)離開(kāi)該樓層時(shí)，按鈕的指示燈自動(dòng)熄滅；o 在沒(méi)有服務(wù)請(qǐng)求時(shí)，電梯停留在其當(dāng)前所處于的樓層，并且電梯門(mén)關(guān)閉。 o 整個(gè)電梯控制系統(tǒng)可分為：電梯控制按鈕、樓層控制按鈕和電梯運(yùn)動(dòng)系統(tǒng)三個(gè)部分。4

38、4 電梯控制按鈕o描述電梯按鈕、按鈕狀態(tài)以及狀態(tài)轉(zhuǎn)換的符號(hào)定義如描述電梯按鈕、按鈕狀態(tài)以及狀態(tài)轉(zhuǎn)換的符號(hào)定義如下下：oebij 電梯i中對(duì)應(yīng)于樓層j的按鈕；oebonij ebij的指示燈為亮的狀態(tài)狀態(tài)；oeboffij eb ij的指示燈為熄滅的狀態(tài)狀態(tài)；opress_ebij ebij被按下時(shí)所產(chǎn)生的事件事件；oarrives_atij 電梯i到達(dá)樓層j時(shí)所產(chǎn)生的事件事件。 ebonijeboffijarrives-atijpress-ebij45 樓層控制按鈕o除了最底層和最高層以外，其它各樓層都有兩個(gè)按鈕：一個(gè)用于一個(gè)用于請(qǐng)求電梯向上運(yùn)動(dòng)，另一個(gè)用于請(qǐng)求電梯向下運(yùn)動(dòng)請(qǐng)求電梯向上運(yùn)動(dòng)，另

39、一個(gè)用于請(qǐng)求電梯向下運(yùn)動(dòng)。用以描述的相應(yīng)符號(hào)為：ofbbj 樓層j對(duì)應(yīng)于運(yùn)動(dòng)方向b的按鈕（b up down）；ofbonbj fbbj的指示燈為亮的狀態(tài)；ofboffbj fbbj的指示燈為熄滅的狀態(tài)；ocall_fbbj 在fbbj被按下時(shí)所產(chǎn)生的事件；odepart_atbj 在方向b上運(yùn)動(dòng)的電梯離開(kāi)樓層j時(shí)所產(chǎn)生的事件。 fbonbjfboffbjcall-fbbjdepart-atbj46 電梯運(yùn)動(dòng)系統(tǒng)o 某個(gè)樓層j所能觀察到的電梯運(yùn)動(dòng)有如下可能的幾種情形：電梯一直向上移動(dòng)；電梯一直向下移動(dòng)；電梯從下面往上逐漸靠近，停止，然后繼續(xù)向上運(yùn)動(dòng)；電梯從上面往下逐漸靠近，停止，然后繼續(xù)向下運(yùn)

40、動(dòng)；電梯從下面往上逐漸靠近，停止，然后反向向下運(yùn)動(dòng)；電梯從上面往下逐漸靠近，停止，然后反向向上運(yùn)動(dòng)；電梯從下面往上逐漸靠近，停止，然后在空閑狀態(tài)等待；電梯從上面往下逐漸靠近，停止，然后在空閑狀態(tài)等待；從空閑狀態(tài)起動(dòng)，然后向下運(yùn)動(dòng)；從空閑狀態(tài)起動(dòng)，然后向上運(yùn)動(dòng)。 電梯運(yùn)動(dòng)系統(tǒng)對(duì)于某樓層的觀察者，電梯可能會(huì)處于如下?tīng)顟B(tài)之一：等待(w:wait)：在該層等待，并且門(mén)未打開(kāi)；停止-空閑(s-i:stop-idle)：停在該層，并且門(mén)打開(kāi)；停止-向上(s-u:stop-up)：電梯在向上運(yùn)動(dòng)過(guò)程中在該樓層暫停；停止-向下(s-d:stop-down)：電梯在向下運(yùn)動(dòng)過(guò)程中在該樓層暫停；靠近-向上(a-u

41、:approach-up)：電梯在向上運(yùn)動(dòng)過(guò)程中逐漸靠近該樓層；靠近-向下(a-d:approach-down)：電梯在向下運(yùn)動(dòng)過(guò)程中逐漸靠近該樓層；退出-向上(e-u:exit-up)：電梯離開(kāi)該樓層，繼續(xù)向上運(yùn)動(dòng)；退出-向下(e-d:exit-down)：電梯離開(kāi)該樓層，繼續(xù)向下運(yùn)動(dòng)。 e-ue-u e-de-d a-us-ue-ue-ds-da-d e-ua-d s-us-d a-us-ue-ds-d a-us-uws-i a-d s-dws-ie-u s-uwe-ds-dw 電梯運(yùn)動(dòng)系統(tǒng)電梯運(yùn)動(dòng)系統(tǒng)StatechartsStatecharts規(guī)格規(guī)格 sensorsensorexitexit-downexit-upstopstop-upstop-downstop-idlecall-fbbjclose-doorclose-doorreduce-speedwaitapproachapproach-upapproach-down狀態(tài)s-u、s-d和s-i可以合并