活動圖并發(fā)語義代碼自動生成算法設(shè)計

吳翔虎，曲明成，李建中，王志超

（哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院，150001 哈爾濱）

活動圖并發(fā)語義代碼自動生成算法設(shè)計

吳翔虎，曲明成，李建中，王志超

（哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院，150001 哈爾濱）

針對活動圖能夠比狀態(tài)圖更自然和直觀地顯示程序的并發(fā)行為，為達(dá)到圖形化描述程序的并發(fā)行為并自動生成代碼的目標(biāo)，通過分析活動圖的圖元語義，以 fork、join、activity、initial、activity final、flow final等6個圖元作為圖形建模和代碼生成的基礎(chǔ)，提出了一套代碼自動生成算法.該算法把活動圖拆分成若干獨立的活動子圖;再把每個活動子圖解析成若干進(jìn)程和信號量;最后對每一個進(jìn)程和信號量進(jìn)行代碼生成.實驗證明，基于本算法開發(fā)的原型系統(tǒng)取得了較滿意的效果，同時也證明了所提出的方法和算法的正確性、有效性.

代碼自動生成;活動圖;并發(fā)語義

基于 UML模型的代碼自動生成［1－3］是一種以UML模型為起點，可以直接生成多層系統(tǒng)結(jié)構(gòu)，并同時保留原有模型中層次關(guān)系的代碼自動生成技術(shù)［4］.例如基于狀態(tài)的代碼自動生成工具I-Logix，Rhapsody以及基于流程圖的代碼生成工具都屬于該技術(shù)范疇［5－7］.

現(xiàn)有研究中，在基于活動圖或者狀態(tài)圖來生成代碼的過程中，狀態(tài)圖被用來作為生成頂層的代碼框架，而在刻畫程序的執(zhí)行邏輯時只是單純的使用流程圖.因為狀態(tài)圖對并發(fā)的語言較難轉(zhuǎn)化為代碼，所以以狀態(tài)圖生成代碼框架的研究成果對于并發(fā)的任務(wù)或者系統(tǒng)線程的支持并不理想［8］.UML活動圖可以有效的描述系統(tǒng)的執(zhí)行流程、狀態(tài)和并發(fā)活動，可以作為研究多線程并發(fā)的有力手段［9］.為了能夠在建模過程中對并發(fā)活動進(jìn)行較好的支持，本文采用活動圖的fork、join、activity、initial、activity final、flow final等 6 個圖元來描述系統(tǒng)的并發(fā)行為.通過將活動圖解析成若干活動子圖和同步信號量來實現(xiàn)生成程序代碼的目標(biāo).基于本文算法開發(fā)的原型系統(tǒng)取得了較滿意的效果，同時也證明了所提出的方法和算法的正確性、有效性.

1 設(shè)計目標(biāo)

本文通過對UML活動圖進(jìn)行分析，設(shè)計實現(xiàn)了一個以UML活動圖為基礎(chǔ)，進(jìn)行代碼自動生成并驗證的系統(tǒng).系統(tǒng)選取了活動途中的6個圖元作為基本圖元，分別為 initial、flow final、activity final、activity、fork、join.

系統(tǒng)的整體流程如圖1所示.

圖1 驗證系統(tǒng)處理流程

本系統(tǒng)中活動圖用XML可擴展標(biāo)記語言來描述，活動圖可以通過DOM技術(shù)解析XML文件從而以樹狀結(jié)構(gòu)載入系統(tǒng).再進(jìn)行根遍歷XML樹，將活動圖可以劃分為若干個獨立的子活動圖.之后利用相應(yīng)的算法將每一個子活動圖轉(zhuǎn)化為若干進(jìn)程，同時添加對這些進(jìn)程進(jìn)行并發(fā)控制的信號量，并將生成的進(jìn)程和信號量翻譯成相應(yīng)代碼.本文選擇java語言作為目標(biāo)代碼，由于算法的通用性，不難獲得在其他平臺上運行的其他語言形式的目標(biāo)代碼.

2 活動圖的XML描述

UML活動圖可以通過XML可擴展標(biāo)記語言來進(jìn)行準(zhǔn)確的描述，并且可以利用DOM技術(shù)把XML文件解析成一個樹狀的數(shù)據(jù)結(jié)構(gòu)，解析得到樹狀結(jié)構(gòu)通常形式為:以root節(jié)點作為根節(jié)點，根節(jié)點的下一層為所以活動圖的節(jié)點和邊，其中所有邊都在節(jié)點之后.另外用遞歸的形勢表示activity節(jié)點的子圖(若包含).

對于圖2中的示例活動圖，本文根據(jù)上述所制定的規(guī)則，繪制出圖3所示的對應(yīng)的XML樹狀結(jié)構(gòu).

圖2 一個活動圖實例

圖3 示例活動圖所對應(yīng)的樹狀結(jié)構(gòu)

活動圖的節(jié)點和邊相應(yīng)的數(shù)據(jù)結(jié)構(gòu)定義如下:

節(jié)點的數(shù)據(jù)結(jié)構(gòu)node中的屬性id記錄原活動圖中節(jié)點的圖元序號，屬性kind記錄節(jié)點類型;邊的數(shù)據(jù)結(jié)構(gòu)edge中屬性source記錄邊的源節(jié)點序號，屬性target記錄邊的目標(biāo)節(jié)點序號.

圖2所示活動圖的XML文件為:

3 活動圖拆分成活動子圖

利用樹的中序遍歷算法遍歷一遍整個活動圖，獲得遍歷的結(jié)果為一系列獨立的活動子圖和帶有嵌套子樹的activity節(jié)點.在這里，本文只需要解決活動子圖的本層樹狀結(jié)構(gòu)而不需要考慮它的activity節(jié)點是否還嵌套了子樹.

上述的算法，將帶有嵌套問題的活動圖問題轉(zhuǎn)化為處理若干獨立活動子圖的過程.

中序遍歷一遍活動圖，解決活動圖中的嵌套問題，生成若干不帶嵌套的獨立活動子圖的算法的偽代碼如下:

通過上述算法，將圖2所示的活動圖拆分成圖4所示的分別以原圖根節(jié)點root和節(jié)點node作為根節(jié)點的兩個活動子圖.

圖4 圖2活動圖拆分為活動子圖

4 活動子圖的代碼自動生成

為了要實現(xiàn)通過活動子圖的代碼自動生成，首先按照相應(yīng)規(guī)則將獨立的活動子圖拆分為若干的進(jìn)程.本文中進(jìn)程的拆分規(guī)則定義為:開始節(jié)點一定是 fork、join、initial節(jié)點，結(jié)束節(jié)點一定是fork、join、final節(jié)點.

在進(jìn)行拆分后，本文通過運用建立兩種信號量Sem和Activity來解決并發(fā)進(jìn)程的時序控制問題.

信號量Sem，設(shè)置在join節(jié)點上.初始值設(shè)為在進(jìn)入join節(jié)點的進(jìn)程數(shù)目，每當(dāng)有進(jìn)程進(jìn)入join節(jié)點時進(jìn)行減一操作，只有當(dāng)Sem=0時才會創(chuàng)建后續(xù)的進(jìn)程.信號量Sem保證了所有的并發(fā)進(jìn)程都執(zhí)行完后才會繼續(xù)執(zhí)行.

信號量ActivitySem，設(shè)置存在嵌套子圖的activity圖元上.初始值設(shè)為1，在activity圖元的子圖進(jìn)程結(jié)束時，將其置為0.同時在外層activity圖元之后監(jiān)測ActivitySem的值，為0時繼續(xù)往下執(zhí)行.信號量ActivitySem保證了嵌套在activity中的子圖能夠在activity后續(xù)任務(wù)之前執(zhí)行，保證語義的正確性.

最后，翻譯每個拆分出來的進(jìn)程，獲得其對應(yīng)的目標(biāo)代碼.

4.1 活動子圖拆分為進(jìn)程

為了避免活動子圖拆分成若干進(jìn)程后出現(xiàn)進(jìn)程名稱沖突的情況，規(guī)定下面的進(jìn)程命名規(guī)則為:

拆分后得到的進(jìn)程Thread名字為Threadi1－i2－…－ik，其中 i1－i2－…－ik為該進(jìn)程在原活動圖中先后經(jīng)歷的節(jié)點.

按照上述的進(jìn)程命名規(guī)則，可以避免進(jìn)程名字重復(fù)，做到根據(jù)節(jié)點唯一缺點進(jìn)程名.

進(jìn)程類Thread中通過用鏈表idList存儲進(jìn)程在活動圖中先后經(jīng)歷的節(jié)點序列來實現(xiàn)存儲進(jìn)程信息.

此外，為了判斷節(jié)點和邊是否已經(jīng)被納入到進(jìn)程中，建立Node類和Edge類，通過tag屬性來標(biāo)識是否已經(jīng)被納入某進(jìn)程.

實現(xiàn)將活動子圖拆分成為若干進(jìn)程的算法GetThread()的偽代碼如下所示:

經(jīng)過上面的GetThread()算法，將圖2示例的活動圖中以root為根節(jié)點的活動子圖拆分成圖5中所示的 Thread1－2－3 和 Thread3－5－6、Thread3－4－6以及Thread6－7－8這4個進(jìn)程.

圖5 活動子圖拆分為進(jìn)程

4.2 join節(jié)點對應(yīng)生成信號量Sem

按照上面所設(shè)計的規(guī)則，對每一個join節(jié)點生成一個信號量Sem，命名為Sem+節(jié)點編號，同時計算進(jìn)入join節(jié)點的進(jìn)程數(shù)目，并賦作信號量的初始值.

為每個join節(jié)點生成Sem信號量的算法SemCompiler()的偽代碼如下:

對圖2示例的活動圖中運行SemCompiler()算法后，對join節(jié)點6生成命名為Sem6的信號量，該信號量對應(yīng)的Sem6.java文件如下:

4.3 存在子圖的activity節(jié)點對應(yīng)生成信號量ActivitySem

相應(yīng)的，本文同樣按照上述設(shè)計的規(guī)則，對每一個嵌套子圖的activity節(jié)點也生成一個信號量，同樣的命名為Activity+節(jié)點編號，初始值設(shè)定為1.

圖2中的示例活動圖，activity節(jié)點4帶有嵌套的子圖，實現(xiàn)對它進(jìn)行并發(fā)控制的信號量命名為 ActivitySem4，生成的 ActivitySem4.java文件如下:

4.4 進(jìn)程翻譯為對應(yīng)的目標(biāo)代碼

將進(jìn)程翻譯成對應(yīng)的目標(biāo)代碼的步驟為:

1)利用進(jìn)程的節(jié)點序列idList來獲得進(jìn)程的名字，根據(jù)進(jìn)程的名字創(chuàng)建相應(yīng)文件.

2)依次分析節(jié)點序列中的每個節(jié)點的內(nèi)容.按照節(jié)點的不同類型，翻譯成該節(jié)點對應(yīng)到目標(biāo)文件中的代碼.注意進(jìn)程的第1個節(jié)點(initial、fork、join中的某個)不進(jìn)行翻譯，所以從節(jié)點序列中的第2個節(jié)點進(jìn)行分析翻譯.

3)為了使生成結(jié)果能夠符合Java語言的結(jié)構(gòu)特征，將對每個activity節(jié)點都進(jìn)行2次分析翻譯的過程.其中第1次分析翻譯過程只生成activity+id()，第2次才對函數(shù)體內(nèi)的具體內(nèi)容進(jìn)行分析翻譯.

對進(jìn)程轉(zhuǎn)化生成為java代碼的算法Thread-Compiler()的偽代碼如下:

5 驗證

本文測試的環(huán)境為:PC實驗平臺，32 bitWindowsXP操作系統(tǒng)，2 GB內(nèi)存，2.80 GHz雙核CPU，并采用Eclipse3.4.1的開發(fā)平臺.

選擇Eclipse作為開發(fā)平臺，因為Eclipse是一個開發(fā)源代碼，基于JAVA的開發(fā)平臺.Eclipse平臺不僅包括了IDE，即JAVA的集成開發(fā)環(huán)境，還提供了相關(guān)的調(diào)試工具，便于開發(fā)和調(diào)試Java程序.

運用本文的算法，圖5所示的拆分出的4個進(jìn)程翻譯生成的目標(biāo)代碼如下:

另外目標(biāo)代碼也包括 Sem6.java和 ActivitySem4.java兩個文件就構(gòu)成了完整可以運行的并發(fā)程序.

6 結(jié)論

1)本文通過采用UML活動圖的6個基礎(chǔ)語義來對程序的并發(fā)行為進(jìn)行建模，并采用特定的算法將模型轉(zhuǎn)化為目標(biāo)代碼.

2)通過原型系統(tǒng)的開發(fā)，充分證明了采用6個基礎(chǔ)圖元來描述程序并發(fā)行為的基本能力，以及由此生成程序代碼的可行性.

3)彌補了狀態(tài)圖對程序并發(fā)行為描述能力的不足，為基于活動圖、狀態(tài)圖、流程來構(gòu)建并發(fā)系統(tǒng)框架和行為邏輯提供了有益的參考.

［1］張?zhí)?，張巖，于笑豐.基于MDA的設(shè)計模式建模與模型轉(zhuǎn)換［J］.軟件學(xué)報，2008，19(9):2203－2217.

［2］呂瑞峰，王剛，問曉先，等.基于模型驅(qū)動框架的計算無關(guān)層過程建模［J］.計算機集成制造系統(tǒng)，2008，14(5):1 －8.

［3］LIANG Yizhi，WANG Yanzhang，LIU Yunfei.The formal semantics of an UML activity diagram［J］.Journal of Shanghai University(English Edition)，2004，8(3):322－327.

［4］MEDVIDOVIC N，ROSENBLUM D S，ROBBINS J E，et al.Modeling software architectures in the unified language［J］.ACM Transactions on Software Engineering and Methodology，2002，11(1):2－57.

［5］DAKHORE H，MAHAJAN A.Generation of C-code using XML parser［OL］.http://www.rimtengg.com/iscet/proceedings/pdfs/advcomp/149.pdf.

［6］CARLISLE M C，WILSON T A，HUMPHRIES J W，et al.Raptor:introducing progra mming to non-majors with flowcharts［J］.Journal of Computing Sciences in Colleges，2004，19(4):52 －60.

［7］KANIS C，SOMKIAT W.Visual programming using flowchart［C］//ISCIT ＇06.International Symposium on Communications and Information Technologies.Washington，DC:IEEE Xplore，2006:1062－1065.

［8］SAMEK M.Quantum programming for embedded systems:toward a hassle-free multithreading［J］.C/C++Users Journal，2003，3(1):1 －10.

［9］柳翔.嵌入式與實時系統(tǒng)開發(fā)［M］.北京:機械工業(yè)出版社，2006:207－208.

Design of automatic code generation algorithm based on concurrency semantics of activity diagrams

WU Xiang-hu，QU Ming-cheng，LI Jian-Zhong，WANG Zhi-chao

(School of Computer Science and Technology，Harbin Institute of Technology，150001 Harbin，China)

Compared with state diagram，activity diagram can be used to display the concurrent behavior of program in a more natural and intuitive way.Six primitives of initial，fork，join，flow final，activity final and activity were selected as the basis for graphical modeling and automatic code generation.A XML document format was defined to describe the activity diagram，then the XML document was parsed based on DOM，after that original activity diagram was split into separate activity sub-diagrams;and then each activity diagram was parsed into a number of processes and semaphores and codes.The methods and algorithms proposed were tested by designing and implementing a software system and good results were achieved，it showed that the methods and algorithms were right and effective.

automatic code generation;activity diagram;concurrency semantic

TP311

A

0367－6234(2012)09－0085－06

2011－03－14.

國家高技術(shù)研究發(fā)展計劃資助項目(2005AA742013).

吳翔虎(1968—)，男，教授;

李建中(1950—)，男，教授，博士生導(dǎo)師.

曲明成，qumingcheng@126.com.

(編輯 張 紅)