活動圖并發語義代碼自動生成算法設計

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

（哈爾濱工業大學計算機科學與技術學院，150001 哈爾濱）

活動圖并發語義代碼自動生成算法設計

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

（哈爾濱工業大學計算機科學與技術學院，150001 哈爾濱）

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

代碼自動生成;活動圖;并發語義

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

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

1 設計目標

本文通過對UML活動圖進行分析，設計實現了一個以UML活動圖為基礎，進行代碼自動生成并驗證的系統.系統選取了活動途中的6個圖元作為基本圖元，分別為 initial、flow final、activity final、activity、fork、join.

系統的整體流程如圖1所示.

圖1 驗證系統處理流程

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

2 活動圖的XML描述

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

對于圖2中的示例活動圖，本文根據上述所制定的規則，繪制出圖3所示的對應的XML樹狀結構.

圖2 一個活動圖實例

圖3 示例活動圖所對應的樹狀結構

活動圖的節點和邊相應的數據結構定義如下:

節點的數據結構node中的屬性id記錄原活動圖中節點的圖元序號，屬性kind記錄節點類型;邊的數據結構edge中屬性source記錄邊的源節點序號，屬性target記錄邊的目標節點序號.

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

3 活動圖拆分成活動子圖

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

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

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

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

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

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

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

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

信號量Sem，設置在join節點上.初始值設為在進入join節點的進程數目，每當有進程進入join節點時進行減一操作，只有當Sem=0時才會創建后續的進程.信號量Sem保證了所有的并發進程都執行完后才會繼續執行.

信號量ActivitySem，設置存在嵌套子圖的activity圖元上.初始值設為1，在activity圖元的子圖進程結束時，將其置為0.同時在外層activity圖元之后監測ActivitySem的值，為0時繼續往下執行.信號量ActivitySem保證了嵌套在activity中的子圖能夠在activity后續任務之前執行，保證語義的正確性.

最后，翻譯每個拆分出來的進程，獲得其對應的目標代碼.

4.1 活動子圖拆分為進程

為了避免活動子圖拆分成若干進程后出現進程名稱沖突的情況，規定下面的進程命名規則為:

拆分后得到的進程Thread名字為Threadi1－i2－…－ik，其中 i1－i2－…－ik為該進程在原活動圖中先后經歷的節點.

按照上述的進程命名規則，可以避免進程名字重復，做到根據節點唯一缺點進程名.

進程類Thread中通過用鏈表idList存儲進程在活動圖中先后經歷的節點序列來實現存儲進程信息.

此外，為了判斷節點和邊是否已經被納入到進程中，建立Node類和Edge類，通過tag屬性來標識是否已經被納入某進程.

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

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

圖5 活動子圖拆分為進程

4.2 join節點對應生成信號量Sem

按照上面所設計的規則，對每一個join節點生成一個信號量Sem，命名為Sem+節點編號，同時計算進入join節點的進程數目，并賦作信號量的初始值.

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

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

4.3 存在子圖的activity節點對應生成信號量ActivitySem

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

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

4.4 進程翻譯為對應的目標代碼

將進程翻譯成對應的目標代碼的步驟為:

1)利用進程的節點序列idList來獲得進程的名字，根據進程的名字創建相應文件.

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

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

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

5 驗證

本文測試的環境為:PC實驗平臺，32 bitWindowsXP操作系統，2 GB內存，2.80 GHz雙核CPU，并采用Eclipse3.4.1的開發平臺.

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

運用本文的算法，圖5所示的拆分出的4個進程翻譯生成的目標代碼如下:

另外目標代碼也包括 Sem6.java和 ActivitySem4.java兩個文件就構成了完整可以運行的并發程序.

6 結論

1)本文通過采用UML活動圖的6個基礎語義來對程序的并發行為進行建模，并采用特定的算法將模型轉化為目標代碼.

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

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

［1］張天，張巖，于笑豐.基于MDA的設計模式建模與模型轉換［J］.軟件學報，2008，19(9):2203－2217.

［2］呂瑞峰，王剛，問曉先，等.基于模型驅動框架的計算無關層過程建模［J］.計算機集成制造系統，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］柳翔.嵌入式與實時系統開發［M］.北京:機械工業出版社，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.

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

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

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

曲明成，qumingcheng@126.com.

(編輯 張 紅)