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

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

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

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

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

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

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

代碼自動(dòng)生成;活動(dòng)圖;并發(fā)語(yǔ)義

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

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

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

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

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

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

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

2 活動(dòng)圖的XML描述

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

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

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

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

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

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

圖2所示活動(dòng)圖的XML文件為:

3 活動(dòng)圖拆分成活動(dòng)子圖

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

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

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

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

圖4 圖2活動(dòng)圖拆分為活動(dòng)子圖

4 活動(dòng)子圖的代碼自動(dòng)生成

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

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

信號(hào)量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í)才會(huì)創(chuàng)建后續(xù)的進(jìn)程.信號(hào)量Sem保證了所有的并發(fā)進(jìn)程都執(zhí)行完后才會(huì)繼續(xù)執(zhí)行.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1)利用進(jìn)程的節(jié)點(diǎn)序列idList來(lái)獲得進(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)對(duì)應(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語(yǔ)言的結(jié)構(gòu)特征，將對(duì)每個(gè)activity節(jié)點(diǎn)都進(jìn)行2次分析翻譯的過(guò)程.其中第1次分析翻譯過(guò)程只生成activity+id()，第2次才對(duì)函數(shù)體內(nèi)的具體內(nèi)容進(jìn)行分析翻譯.

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

5 驗(yàn)證

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

選擇Eclipse作為開(kāi)發(fā)平臺(tái)，因?yàn)镋clipse是一個(gè)開(kāi)發(fā)源代碼，基于JAVA的開(kāi)發(fā)平臺(tái).Eclipse平臺(tái)不僅包括了IDE，即JAVA的集成開(kāi)發(fā)環(huán)境，還提供了相關(guān)的調(diào)試工具，便于開(kāi)發(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)本文通過(guò)采用UML活動(dòng)圖的6個(gè)基礎(chǔ)語(yǔ)義來(lái)對(duì)程序的并發(fā)行為進(jìn)行建模，并采用特定的算法將模型轉(zhuǎn)化為目標(biāo)代碼.

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

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

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

［2］呂瑞峰，王剛，問(wèn)曉先，等.基于模型驅(qū)動(dòng)框架的計(jì)算無(wú)關(guān)層過(guò)程建模［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)開(kāi)發(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.

國(guó)家高技術(shù)研究發(fā)展計(jì)劃資助項(xiàng)目(2005AA742013).

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

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

曲明成，qumingcheng@126.com.

(編輯 張 紅)