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

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

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

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

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

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

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

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

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

現(xiàn)有研究中，在基于活動圖或者狀態(tài)圖來生成代碼的過程中，狀態(tài)圖被用來作為生成頂層的代碼框架，而在刻畫程序的執(zhí)行邏輯時(shí)只是單純的使用流程圖.因?yàn)闋顟B(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 個(gè)圖元來描述系統(tǒng)的并發(fā)行為.通過將活動圖解析成若干活動子圖和同步信號量來實(shí)現(xiàn)生成程序代碼的目標(biāo).基于本文算法開發(fā)的原型系統(tǒng)取得了較滿意的效果，同時(shí)也證明了所提出的方法和算法的正確性、有效性.

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

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

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

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

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

2 活動圖的XML描述

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

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

圖2 一個(gè)活動圖實(shí)例

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

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

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

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

3 活動圖拆分成活動子圖

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

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

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

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

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

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

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

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

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

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

最后，翻譯每個(gè)拆分出來的進(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é)點(diǎn).

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

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

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

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

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

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

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

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

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

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

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

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

圖2中的示例活動圖，activity節(jié)點(diǎn)4帶有嵌套的子圖，實(shí)現(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é)點(diǎn)序列idList來獲得進(jìn)程的名字，根據(jù)進(jìn)程的名字創(chuàng)建相應(yīng)文件.

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

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

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

5 驗(yàn)證

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

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

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

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

6 結(jié)論

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

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

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

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

［2］呂瑞峰，王剛，問曉先，等.基于模型驅(qū)動框架的計(jì)算無關(guān)層過程建模［J］.計(jì)算機(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］柳翔.嵌入式與實(shí)時(shí)系統(tǒng)開發(fā)［M］.北京:機(jī)械工業(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ā)展計(jì)劃資助項(xiàng)目(2005AA742013).

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

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

曲明成，qumingcheng@126.com.

(編輯 張 紅)