產(chǎn)品線體系結(jié)構(gòu)并發(fā)演化沖突檢測(cè)技術(shù)研究

(西北工業(yè)大學(xué) a.軟件與微電子學(xué)院；b.計(jì)算機(jī)學(xué)院， 西安 710072)



摘 要：產(chǎn)品線體系結(jié)構(gòu)定義了產(chǎn)品線中所有產(chǎn)品的公共結(jié)構(gòu)及其特性，是軟件產(chǎn)品線最重要的核心資源之一。為了滿足其多個(gè)成員的特殊需求變更，產(chǎn)品線體系結(jié)構(gòu)需要并發(fā)演化，而并發(fā)演化沖突則成為產(chǎn)品線體系結(jié)構(gòu)演化的核心問題。應(yīng)用復(fù)用契約技術(shù)檢測(cè)產(chǎn)品線體系結(jié)構(gòu)的并發(fā)演化沖突，給出產(chǎn)品線體系的vADL模型的類型標(biāo)簽圖映射及約束，定義產(chǎn)品線體系結(jié)構(gòu)的編輯命令、應(yīng)用性沖突和演化性沖突，并且對(duì)該方法進(jìn)行實(shí)例說明。

關(guān)鍵詞：產(chǎn)品線體系結(jié)構(gòu)；演化；沖突檢測(cè)

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：10013695(2009)02057703



Research on detecting conflicts of concurrent evolution for product line architecture



ZHANG Taoa，WANG Haipengb，MA Chunyana，CHEN Yuzhena，HU Zhengguob

(a.College of Software Microelectronics，b.College of Computer， Northwestern Polytechnical University， Xi’an 710072， China)

Abstract:Product line architecture (PLA)is one of the most important core assets of software product line (SPL)，and specifies common and special structure of all members of SPL. Evolved PLA concurrently to adapt particular requirement change of members，and solved conflicts of concurrent evolvement.Provided a method to detect conflicts of PLA evolvement with reuse contract. The vADL model of PLA could be map to labeled typed graph， and defined constrains， evolve commands， applicability conflicts and evolution conflicts.It provided a simple example to explain detecting conflicts technique.

Key words:product line architecture; evolution; conflict detection



軟件產(chǎn)品線是一種面向特定領(lǐng)域、大規(guī)模系統(tǒng)的軟件復(fù)用技術(shù)，它的特點(diǎn)在于一次開發(fā)一組具有大量公共特征的相似產(chǎn)品[1]。產(chǎn)品線體系結(jié)構(gòu)定義了產(chǎn)品線中所有產(chǎn)品的公共結(jié)構(gòu)及其獨(dú)特性，是產(chǎn)品線成功開發(fā)的核心和基礎(chǔ)[2]。為了滿足各個(gè)成員的需求變更，產(chǎn)品線體系結(jié)構(gòu)需要并發(fā)演化為多個(gè)分支，發(fā)現(xiàn)和檢測(cè)并發(fā)演化沖突就成為產(chǎn)品線體系結(jié)構(gòu)演化的核心問題。體系結(jié)構(gòu)描述語言（ADL）能夠形式化規(guī)約軟件體系結(jié)構(gòu)，是體系結(jié)構(gòu)精化、分析、演化的基礎(chǔ)。產(chǎn)品線體系結(jié)構(gòu)描述語言Koala 基于配置管理系統(tǒng)管理產(chǎn)品線體系結(jié)構(gòu)演化，不支持并發(fā)演化[3]。xADL2.0 具有版本元素管理產(chǎn)品線體系結(jié)構(gòu)的并發(fā)演化，并且提供比較和合并算法檢測(cè)簡單的并發(fā)演化沖突[4]。

復(fù)用契約能夠結(jié)構(gòu)化描述可復(fù)用資源并基于契約增量修改可復(fù)用資源和評(píng)估可復(fù)用資源變更的影響。復(fù)用契約定義有擴(kuò)展、取消、細(xì)化、粗化等基本的契約類型，并且提供擴(kuò)展機(jī)制，可以定義新的契約類型和沖突，滿足不同領(lǐng)域的特殊需求。目前，復(fù)用契約已應(yīng)用于面向?qū)ο箢I(lǐng)域內(nèi)的并發(fā)演化沖突檢測(cè)[5]。

vADL（variabilityenabled architecture describe language）是筆者提出的一種產(chǎn)品線體系結(jié)構(gòu)描述語言[6]。在vADL基礎(chǔ)上，本文研究基于復(fù)用契約技術(shù)檢測(cè)產(chǎn)品線體系結(jié)構(gòu)并發(fā)演化沖突，并給出簡單的實(shí)例說明。

1 vADL簡介

vADL是一種顯式描述變化性產(chǎn)品線體系結(jié)構(gòu)的描述語言。它具有基于π演算的形式語義，能夠描述靜態(tài)和動(dòng)態(tài)體系結(jié)構(gòu)；支持產(chǎn)品線體系結(jié)構(gòu)的精化、演化、分析和定制。vADL的核心元素包括組件、連接件、配置和配置實(shí)例。

組件是計(jì)算單元，也可以是數(shù)據(jù)存儲(chǔ)的單位或狀態(tài)。組件通過功能接口與外部環(huán)境交互，功能接口由一組端口組成。通過端口，組件接收或者向外部環(huán)境發(fā)送值。組件定制接口描述組件內(nèi)部結(jié)構(gòu)和行為的變化性，定制接口包含一組變量。組件的非功能屬性則描述組件性能、運(yùn)行平臺(tái)、資源消耗等非功能性質(zhì)。組件的內(nèi)部行為定義為π演算形式。

連接件代表了組件之間的交互，表示了組件之間的通信和協(xié)調(diào)活動(dòng)。在vADL中，連接件可作為一種特殊的組件，同樣具有功能接口、定制接口和非功能屬性等。

配置定義組件和連接件實(shí)例之間的拓?fù)浣Y(jié)構(gòu)，即其相互連接關(guān)系。配置中不僅包含產(chǎn)品線的公共組件，也包含其變化組件。變化組件附有守護(hù)條件，定義為包含定制接口變量的布爾表達(dá)式。

配置實(shí)例是對(duì)產(chǎn)品線體系結(jié)構(gòu)配置的定制。根據(jù)產(chǎn)品線成員的特殊需求，確定產(chǎn)品線體系結(jié)構(gòu)的定制接口變量值，計(jì)算其各個(gè)變化組件的守護(hù)條件，去除守護(hù)條件為1的變化組件，則得到產(chǎn)品線成員的體系結(jié)構(gòu)。

2 并發(fā)演化沖突檢測(cè)技術(shù)

2.1 產(chǎn)品線體系結(jié)構(gòu)類型標(biāo)簽圖

在復(fù)用契約中，類型標(biāo)簽圖是一個(gè)附有標(biāo)簽和類型的圖，圖中的節(jié)點(diǎn)和邊均附有約束。標(biāo)簽惟一標(biāo)志一個(gè)節(jié)點(diǎn)，約束則可附加用于沖突檢測(cè)的任何信息。類型定義節(jié)點(diǎn)或者邊的分類，并且具有子類型關(guān)系。首先需要將產(chǎn)品線體系結(jié)構(gòu)的vADL模型映射為標(biāo)簽類型圖。圖1給出產(chǎn)品線體系結(jié)構(gòu)標(biāo)簽類型層次結(jié)構(gòu)。圖2則給出產(chǎn)品線體系結(jié)構(gòu)的標(biāo)簽類型約束，以限制不同類型節(jié)點(diǎn)之間所允許的連接關(guān)系。

2.2 vADL模型編輯命令

圖重寫邏輯包含一個(gè)初始圖和一組演化操作。從初始圖開始，演化操作可以在符合條件的基礎(chǔ)上將圖演化為一個(gè)新的版本。演化操作通常寫做P：L→R。其中L 和R分別是演化前后的子圖；P是演化操作，包含一組前置條件和一組后置條件。復(fù)用契約定義有標(biāo)準(zhǔn)的演化操作，如extension、cancellation、refinement、coarsening等。在表1則定義一組vADL模型的編輯命令，這些編輯命令可以映射為基本或者組合的復(fù)用契約演化操作。

2.3 vADL模型應(yīng)用性沖突

并發(fā)沖突類型包括應(yīng)用性沖突和演化性沖突。應(yīng)用性沖突主要由于某個(gè)操作命令執(zhí)行后，vADL模型不能滿足下一個(gè)操作命令的前置條件，即表現(xiàn)為兩個(gè)演化操作的順序不能調(diào)換，可通過復(fù)用契約的屬性形式化定義檢測(cè)。表2定義產(chǎn)品線體系結(jié)構(gòu)的應(yīng)用性沖突。

2.4 vADL模型演化性沖突

演化性沖突并不違反任何操作命令的前置條件，而且是對(duì)演化后的類型標(biāo)簽圖進(jìn)行檢測(cè)，以確認(rèn)是否是結(jié)果圖中包含的某種模式，每一種模式對(duì)應(yīng)于一種演化性沖突。演化性沖突是與領(lǐng)域相關(guān)的，即在某個(gè)領(lǐng)域內(nèi)是錯(cuò)誤的，而在另一個(gè)領(lǐng)域則可能不是錯(cuò)誤的。檢測(cè)演化性沖突有助于分析變更影響和控制變更傳播。vADL模型演化性沖突定義如表3所示。

表1 vADL模型編輯命令

命令契約類型前置條件說明

addPort (port )nestedExtension(Arch， ArchType，port， port.Mode)vADL模型中不存在該端口為vADL模型增加新的端口port

deletePort（port）nestedCancellation(Arch， ArchType，port.Mode)vADL模型中存在該端口刪除vADL模型的port端口

addVariability(variant)nestedExtension(Arch， ArchType， variant， Variant)vADL模型不存在該變化性變量為vADL模型增加新的變化性變量

deleteVariability(variant)nestedCancellation(Arch， ArchType， variant， Variant)vADL模型中存在該變化性變量，并且該變量沒有任何變量關(guān)聯(lián)關(guān)系刪除vADL模型的變化性變量

addInstance(inst)nestedExtension(Arch，ArchType，inst.Type)nestedExtension(inst，instType，cname(inst，inst.port)， inst.port.Mode)nestedExtension(inst，instType，cname(inst，inst.variant)， Variant)vADL模型中不存在該內(nèi)部元素實(shí)例為模型增加內(nèi)部實(shí)例，并同時(shí)增加所有的實(shí)例端口和變量。inst.port表示實(shí)例的端口，inst.variant表示實(shí)例的變量

deleteInstance(inst )nestedCancellation (inst， instType，inst.Port， portMode)nestedCancellation (inst， instType，inst.Variant， Variant)coarsening (ename(cname(connectInst， port1)， cname(componentInst，port2))， cname(connectInst，port1)， cname(componentInst， port2)，PortLink)coarsening (ename(port cname(inst， instport))， port， cname(inst， instport)，PortAttach)nestedCancellation (Arch， ArchType，inst， inst.Type)vADL模型中存在該內(nèi)部元素實(shí)例。這是一個(gè)復(fù)合操作，將從模型中刪除該內(nèi)部實(shí)例，以及實(shí)例所有的端口、變量、守護(hù)條件、變量綁定、端口連接和端口綁定關(guān)系等

addGuardCond (inst， guard)nestedExtension(inst， instType，cname(inst，guard)， GuardCondition)refinement(ename(guard.var cname(inst， guard))， guard.var， cname(inst， guard)， VariantRelated)該變化實(shí)例沒有定義守護(hù)條件為變化實(shí)例增加守護(hù)條件guard，并建立守護(hù)條件和組件變量直接的變量關(guān)聯(lián)關(guān)系

deleteGuardCond (inst，guard)nestedCancellation (inst， instType， cname(inst，guard)，GuardCondition) coarsening(ename(inst.var cname(inst， guard))， inst.var， cname(inst， guard)， VariantRelated)該變化實(shí)例具有守護(hù)條件刪除該變化實(shí)例的守護(hù)條件guard，并刪除所有的守護(hù)條件的變量關(guān)聯(lián)邊

addVariantBind(inst.var，value)nestedExtension(cname(inst， var)， Variant， cname(inst，var，value)， VariantBind)refinement(ename(var1 cname(inst， var))， var1， cname(inst， var， value)， VariantRelated)該內(nèi)部實(shí)例的變量沒有定義變量綁定為內(nèi)部實(shí)例的變量定義其變量綁定，并建立變量綁定與組件變量之間的變量關(guān)聯(lián)關(guān)系

replaceVariantBind(inst.var，oldValue，newValue)nestedCancellation (inst.var， Variant， cname(inst.var， oldValue)， VariantBind)coarsening (ename(var1 inst.var)， var1， cname(inst.var， oldValue)， VariantRelated)nestedExtension(inst.var， Variant， cname(inst.var， newValue)， VariantBind)refinement(ename(var1 inst.var)， var1， cname (inst.var， newValue)， VariantRelated)刪除內(nèi)部實(shí)例變量的變量綁定首先刪除內(nèi)部變量的原有變量綁定和相關(guān)的變量關(guān)聯(lián)邊，再增加新的變量綁定和新的變量關(guān)聯(lián)邊

addPortAttach(port， inst.port1)refinement(ename(port inst.port1)， port， inst.port1，PortAttach)存在該端口和內(nèi)部實(shí)例端口，并且內(nèi)部實(shí)例端口instport沒有綁定其他外部端口將外部端口port綁定到內(nèi)部實(shí)例端口instport

deletePortAttach(port， inst.port1)coarsening (ename(port inst.port1)， port， inst.port1，PortAttach)存在該端口綁定關(guān)系刪除端口綁定關(guān)系

addPortLink(connectInst.port1， componentInst.port2)refinement(ename(cname(connectInst， port1)， cname(componentInst， port2))， cname(connectInst， port1)， cname(componentInst， port2)，PortAttach)存在該連接件實(shí)例和組件實(shí)例，以及對(duì)應(yīng)的端口。并且組件端口沒有綁定到其他連接件將連接件實(shí)例connectInst的端口port1連接到組件實(shí)例componentInst的端口port2

deletePortLink(connectInst.port1， componentInst.port2)coarsening (ename(cname(connectInst， port1)， cname(componentInst， port2))， cname(connectInst， port1)， cname(componentInst， port2)，PortAttach)存在該端口連接關(guān)系刪除端口連接關(guān)系

注：cname(a，b)= a.b，cname(a，b，c)= a.b.c，生成節(jié)點(diǎn)的復(fù)合名字，解決標(biāo)簽類型圖中實(shí)例端口重名等問題；ename(a，b)= a_b生成邊的名字。

表2 產(chǎn)品線體系結(jié)構(gòu)應(yīng)用性沖突定義

編號(hào)沖突名稱沖突描述

AC1重復(fù)的端口當(dāng)兩個(gè)客戶端同時(shí)增加同名的端口時(shí)，出現(xiàn)該沖突

AC2重復(fù)的端口刪除兩個(gè)客戶端同時(shí)刪除同一個(gè)端口時(shí)

AC3重復(fù)的變量兩個(gè)客戶端同時(shí)增加同名的變量時(shí)

AC4重復(fù)的變量刪除兩個(gè)客戶端同時(shí)刪除同一個(gè)變量時(shí)

AC5重復(fù)的內(nèi)部實(shí)例兩個(gè)客戶端同時(shí)增加同名內(nèi)部實(shí)例時(shí)

AC6重復(fù)的內(nèi)部實(shí)例刪除兩個(gè)客戶端同時(shí)刪除同一個(gè)內(nèi)部實(shí)例時(shí)

AC7重復(fù)的守護(hù)條件兩個(gè)客戶端同時(shí)為某個(gè)內(nèi)部實(shí)例定義守護(hù)條件

AC8重復(fù)的守護(hù)條件刪除兩個(gè)客戶端同時(shí)刪除同一內(nèi)部實(shí)例的守護(hù)條件

AC9重復(fù)的變量綁定兩個(gè)客戶端同時(shí)為某個(gè)實(shí)例的變量定義變量綁定

AC10在變量綁定時(shí)未定義的實(shí)例當(dāng)一個(gè)客戶端刪除某個(gè)內(nèi)部實(shí)例，而另一個(gè)客戶端為該實(shí)例的某個(gè)變量增加或替換變量綁定時(shí)

AC11在守護(hù)條件定義時(shí)未定義的實(shí)例當(dāng)一個(gè)客戶端刪除某個(gè)內(nèi)部實(shí)例，而另一個(gè)客戶端為該實(shí)例增加或刪除守護(hù)條件

AC12在變量綁定時(shí)未定義的變量當(dāng)一個(gè)客戶端定義某個(gè)內(nèi)部實(shí)例變量綁定，而另一個(gè)客戶正在刪除變量綁定所相關(guān)聯(lián)的組件變量

AC13在守護(hù)條件定義時(shí)未定義的變量當(dāng)一個(gè)客戶端定義某個(gè)內(nèi)部實(shí)例的守護(hù)條件，而另一個(gè)客戶正在刪除守護(hù)條件所相關(guān)聯(lián)的組件變量

AC14未定義的端口綁定源當(dāng)一個(gè)客戶端建立端口綁定關(guān)系，而另一個(gè)客戶端刪除外部端口

AC15未定義的端口綁定目標(biāo)當(dāng)一個(gè)客戶端建立端口綁定關(guān)系，而另一個(gè)客戶端刪除端口所綁定的內(nèi)部實(shí)例

AC16未定義的端口連接源當(dāng)一個(gè)客戶端建立端口連接關(guān)系，而另一個(gè)客戶端同時(shí)刪除端口連接的內(nèi)部連接件實(shí)例

AC17未定義的端口連接目標(biāo)當(dāng)一個(gè)客戶端建立端口連接關(guān)系，而另一個(gè)客戶端刪除端口連接的內(nèi)部組件實(shí)例

AC18重復(fù)的端口連接當(dāng)兩個(gè)客戶端同時(shí)給同一連接件實(shí)例端口和組件實(shí)例端口建立端口連接關(guān)系時(shí)

AC19重復(fù)的端口綁定當(dāng)兩個(gè)客戶端同時(shí)在同一外部端口和內(nèi)部實(shí)例端口建立端口綁定關(guān)系時(shí)

AC20無效的端口多重綁定當(dāng)一個(gè)客戶端為某個(gè)外部端口建立與某個(gè)內(nèi)部實(shí)例的多重端口連接關(guān)系，而另一個(gè)客戶端同時(shí)刪除該內(nèi)部實(shí)例的守護(hù)條件

AC21無效的端口多重連接當(dāng)一個(gè)客戶端為某個(gè)連接件實(shí)例端口建立與某個(gè)內(nèi)部組件實(shí)例的多重端口連接關(guān)系，而另一個(gè)客戶端同時(shí)刪除該內(nèi)部組件實(shí)例的守護(hù)條件

表3 vADL模型演化性沖突定義

編號(hào)沖突名稱模式說明

EC1重復(fù)的端口到實(shí)例綁定圖3(a)當(dāng)兩個(gè)并發(fā)演化將同一外部端口分別綁定到某個(gè)內(nèi)部實(shí)例的不同端口，即分別執(zhí)行操作 addPortAttach(port，inst，instport1)和addPortAttach(port，inst，instport2)

EC2重復(fù)的端口實(shí)例連接圖3(b)當(dāng)兩個(gè)并發(fā)演化將某個(gè)內(nèi)部連接件實(shí)例端口分別綁定到某個(gè)內(nèi)部組件實(shí)例的不同端口，即分別執(zhí)行操作addPortLink(connectInst，port1，componentInst，port2)和addPortLink(connectInst，port1，componentInst，port3)

EC3失效的組件端口圖3(c)當(dāng)兩個(gè)并發(fā)演化都刪除同一外部端口的端口綁定關(guān)系，使某個(gè)組件外部端口不綁定任何內(nèi)部實(shí)例端口，即分別執(zhí)行操作deletePortAttach(port，inst1，instport1)和deletePortAttach(port，inst2，instport2)

EC4失效的組件變量圖3(d)當(dāng)兩個(gè)并發(fā)演化都在刪除內(nèi)部實(shí)例的變量綁定或者守護(hù)條件時(shí)，將同時(shí)刪除變量綁定或者守護(hù)條件與組件變量之間的變量關(guān)聯(lián)，使某個(gè)組件變量不與任何守護(hù)條件或者變量綁定關(guān)聯(lián)，即分別執(zhí)行操作deleteGuardCond (inst，guard)和replaceVariantBind (inst， var， oldVa-lue， newValue)

3 實(shí)例說明

下面以數(shù)據(jù)安全處理組件為例，說明如何使用復(fù)用契約的方法檢測(cè)和發(fā)現(xiàn)并發(fā)演化沖突。圖4給出了其初始vADL模型。圖5是演化后的最終vADL模型。表4給出了一組并發(fā)演化編輯命令以及所發(fā)現(xiàn)的應(yīng)用性沖突和演化性沖突。

表4 并發(fā)編輯和沖突檢測(cè)實(shí)例

命令序號(hào)編輯命令應(yīng)用性沖突演化性沖突

4 結(jié)束語

并發(fā)演化是產(chǎn)品線體系結(jié)構(gòu)演化的主要方式。基于復(fù)用契約技術(shù)能夠檢測(cè)產(chǎn)品線體系結(jié)構(gòu)模型的并發(fā)演化沖突、分析和評(píng)估產(chǎn)品線體系結(jié)構(gòu)演化影響。目前，只是針對(duì)產(chǎn)品線體系結(jié)構(gòu)并發(fā)演化沖突問題。下一步將應(yīng)用復(fù)用契約技術(shù)檢測(cè)產(chǎn)品線體系結(jié)構(gòu)和組件并發(fā)演化沖突問題，并且設(shè)計(jì)和開發(fā)基于復(fù)用契約技術(shù)的產(chǎn)品線體系結(jié)構(gòu)并發(fā)演化沖突檢測(cè)工具，實(shí)現(xiàn)自動(dòng)化檢測(cè)。

參考文獻(xiàn)：［1］

CLEMENTS P，NORTHROP L.Software product lines:practices and patterns［M］.Boston:AddisonWesley， 2001:520.

［2］MAGEE J，KRAMER J.Dynamic structure in software architectures[C]//Proc of the 4th ACM SIGSOFT’96:Symposium on Foundations of Software Engineering(FSE4).New York:ACM Press，1996:314.

［3］OMMERING R V，LINDEN F V，KRAMER J，et al.The Koala component model for customer electronics software［J］.IEEE Computer，2000，33(3):7885.

［4］DASHOFY E M，HOEK A，TAYLOR R N.An infrastructure for the rapid development of XML based architecture description languages[C]//Proc of the 24th International Conference on Software Engineering (ICSE 2002).New York:ACM Press，2002:266276.

［5］STEYAERT P，LUCAS C，MENS K，et al.Reuse contracts:managing the evolution of reusable assets[C]//Proc of OOPSLA ’96， ACM SIGPLAN Notices.New York:ACM Press，1996:268286.

［6］ZHANG Tao，WANG Haipeng.vADL：a variabilitysupported architecture description language for specifying product line architectures[C]//Proc of the 2nd International Software Product Lines Young Researchers Workshop (SPLYR 2005).2005.