死锁外链查询工具

ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.
ac.
cnJournalofSoftware,Vol.
19,No.
10,October2008,pp.
25272538http://www.
jos.
org.
cnDOI:10.
3724/SP.
J.
1001.
2008.
02527Tel/Fax:+86-10-625625632008byJournalofSoftware.
Allrightsreserved.
一种解决构件连接死锁问题的方法毛斐巧+,齐德昱,林伟伟(华南理工大学计算机科学与工程学院,广东广州510640)AnApproachtoSolveDeadlockProblemofComponentConnectionMAOFei-Qiao+,QIDe-Yu,LINWei-Wei(CollegeofComputerScienceandEngineering,SouthChinaUniversityofTechnology,Guangzhou510640,China)+Correspondingauthor:E-mail:maofeiqiao@163.
comMaoFQ,QiDY,LinWW.
Anapproachtosolvedeadlockproblemofcomponentconnection.
JournalofSoftware,2008,19(10):25272538.
http://www.
jos.
org.
cn/1000-9825/19/2527.
htmAbstract:Procedurecall-basedcomponentconnectionswhicharelatentinhardcodedonotonlyrestricttheflexibilityofsoftwarebutalsocausehiddenproblemstosoftwarereliabilitybecauseoftheexistingdeadlockconnectionloops.
Tosolvethisproblem,first,aformalsemanticmodelcalledcall-basedconnectorhasbeenbuiltwhichexplicitlyseparatesconnectionfromcomponents.
Second,mappingrulesusedtoconvertcall-basedconnectorsintocomponenttheconnectiondirectedgraphareproposed.
Then,twoalgorithms,TPDCC(twophasesdeadlockconnectioncheck)usedtofindallexistingdeadlockconnectionloops,andDCEMRF(deadlockconnectioneliminationbasedonmaximumreusefrequency)usedtofindlocationswiththeleastnumberofconnectionsthatmustbeeliminatedtoeliminatetheloops,areprovidedrespectively.
Last,itsapplicationandexperimentalresultsshowthatthepresentedapproachisfeasibleandeffective,soitcanbeusedtoenhancethereliabilityofsoftware,alsobefitasabasistofurtherdesignandimplementadaptiveconnectorduetoitsseparativewayofdescriptionandstorageofcomponentconnectioninsemantic.
Keywords:adaptability;reliability;connector;component;deadlock摘要:隐式硬编码的基于过程调用构件连接束缚构件集成的灵活性,且存在的死锁连接造成软件可靠性隐患问题.
针对该问题,首先建立基于过程调用连接器形式语义模型,显式地将连接关系从构件中分离;然后给出并通过映射规则进行连接器到构件连接有向图的转换,并设计给出两阶段死锁检查算法和基于极大复用频率死锁连接消除算法,用于找到存在的所有死锁连接回路和消除所有死锁连接需要消除的最小数目连接的位置.
最后应用及实验结果表明,该解决方法可行而且有效,可以用于增强软件可靠性,同时因其从语义上分离描述和存储构件连接方式,适合以此为基础进一步设计实现适应性连接器.
关键词:适应性;可靠性;连接器;构件;死锁中图法分类号:TP311文献标识码:ASupportedbytheNaturalScienceFoundationofGuangdongProvinceofChinaunderGrantNo.
05300200(广东省自然基金);theGuangdong-HongKongTechnologyCooperationFundingSchemeofChinaunderGrantNo.
2005A10307007(粤港关键领域重点突破项目)Received2007-06-04;Accepted2007-10-092528JournalofSoftware软件学报Vol.
19,No.
10,October2008在构件化软件中,通过构件连接将构件集成为应用软件.
根据交互方式的不同,构件间的连接有基于消息传递的连接、基于过程(也称为方法或函数)调用的连接和基于事件传递的连接等[1].
在形式化软件体系结构研究中将基于各种不同交互方式的连接均抽象为非功能实体连接器.
而构件是功能实体,目前软件开发中使用的主流构件模型主要有OMG的CORBA,Microsoft的COM/DCOM/COM+和Sun的JavaBean/EJB,这些功能实体间的交互以过程调用(本地或远程)为主[2].
并且这种基于过程调用交互方式的连接是直接的,隐式的硬编码在构件实现体中,没有显式地与构件分离,使构件之间的连接呈现一种紧密耦合方式.
这种连接方式不仅限制了构件间集成的灵活性和可扩展性,而且使构件间极易存在循环递归调用环.
这种环在软件编译链接时无法发现,而在软件运行时形成死锁,造成软件稳定性和可靠性的隐患问题.
所以,本文针对基于过程调用构件连接方式中存在的死锁连接问题进行研究,建立基于过程调用连接器形式语义模型,在此基础上,提出两阶段死锁连接检查算法,用于找出造成死锁的构件间连接存在的循环递归调用环;然后给出基于极大复用频率的死锁连接消除算法,用于找到存在的所有死锁连接回路和消除所有死锁连接需要消除的最小数目连接的位置.
在为该问题提供一种可行而有效的解决方法的同时,为增强软件的稳定性和可靠性提供一条途径,并且为设计实现具有适应性的构件连接器奠定基础.
1问题描述这里,从一个简单的例子引出问题.
4个由Java类实现的构件体(Scone,Sctwo,SCthree和SCfour)连接集成的小示例应用(这里只是为了说明和描述问题而设计的一个非常简单的例子,在实际应用中构件的实现体要复杂得多),如图1(a)~图1(d)所示.
在编译链接时没有任何问题,运行时却异常终止.
其错误提示如图2(a)所示,即发生了堆栈溢出.
这是因为,如图2(b)所示,其中3个构件(Scone,SCtwo和SCthree)的方法之间调用形成了连接环,运行时一直沿着环进行循环递归调用,而不会有递归结束条件产生,形成僵局,导致不停地有构件实例对象产生,直到存储空间不足,应用才异常终止.
因此,可将基于过程调用构件连接集成中的死锁连接问题定义为:定义1.
在基于过程调用构件连接集成的软件中,因多个构件间的调用交互,某一构件的功能方法(即过程)间接调用其自身,在构件的功能方法之间形成连接环,导致软件运行时构件间的循环递归调用无法返回,造成一种僵局,使软件无法向前运行,甚至异常终止.
Fig.
1Asimpleexample图1一个简单的例子(a)(b)(c)(d)毛斐巧等:解决构件连接死锁问题的一种方法2529Fig.
2Deadlockproblem图2死锁问题而要解决该问题就需要找出构件连接间存在的所有死锁连接,并消除这些死锁连接.
2解决方法2.
1连接器形式语义模型从构件间的交互方式出发,建立基于过程调用连接器形式语义模型,抽象出构件间的连接关系,为死锁连接检查奠定基础.
在设计模式中,硬编码基于过程调用构件的交互语法格式为:(1)有返回值的,resultVariable=objectname.
methodname(arguments)或(2)无返回值的,objectname.
methodname(arguments).
某些情况下,arguments也可以为空.
在这种格式的描述下,调用构件和被调用构件之间建立起连接.
目前进行编译链接的软件开发工具,只能检查出其中存在的语法错误,而对于语义层次上的可能造成像死锁连接这样的逻辑错误,却不能发现.
因此,建立连接器形式语义模型,以支持语义层次上像死锁连接这样的逻辑错误的自动化检查.
已存在一些具有代表性的与构件连接的形式语义建模相关的研究.
以Allen[3]为代表的一类研究者,以CSP(communicatingsequentialprocesses)为基础将构件间的交互方式抽象为连接器时(如文献[46]),连接器的形式语义模型为由role和glue描述的CSP进程.
他们主要从参与交互的角色和交互过程的行为协议角度来建立模型.
基于这种模型,可以通过描述转化预处理后,使用商业FDR(failuredivergencerefinement)模型检查工具检查单个连接器本身各role与glue中是否存在等待死锁,不支持应用系统内连接器间形成的构件死锁连接检查.
以Magee[7]为代表的另一类研究者,以π演算[8]为基础建立构件连接形式语义模型.
如Magee以一阶π演算为基础,将连接器描述为bind断言,以声明相交互的构件间provides服务的output和requires服务的input间的对应关系;再如文献[911]以高阶π演算为基础,将连接器描述为一组端口port和一个路由行为routing.
这类以π演算为基础建立的连接器语义模型,支持描述SA(softwarearchitecture)的动态行为以及SA的演化和精化,但不支持死锁检查和相容性检查.
与上述建模方式不同,针对基于过程调用构件交互方式,我们结合CSP和谓词逻辑建立基于过程调用连接器语义模型.
基于这种模型,不仅能够检查出连接器间形成的构件死锁连接,而且能够找到消除死锁连接的位置,同时提供了专门的检查工具DCCTool(deadlockconnectionCheckTool).
在Wright[12,13]中,将构件形式化为CSP[14]中的进程(process).
这里,构件也按这种语义形式化,另外,以C标识,并附以下标以区别不同的构件.
下面借用CSP中的符号,给出建立这种连接器形式语义模型的其他相关语义定义.
定义2.
构件对外提供的任一功能操作方法(即过程),称为构件的外交互点,其形式语义为外通道(external-channel),记为OP,并附以下标以区别同一构件内对外提供的不同方法.
其中:(a)(b)2530JournalofSoftware软件学报Vol.
19,No.
10,October2008(1)构件内部隐藏的、任一有与其他构件外交互点交互的功能操作方法(过程),称为构件的内交互点,其形式语义为内通道(internal-channel),记为\OP,并附以下标以区别同一构件内隐藏的不同方法;(2)返回值类型形式化为内/外通道输出类型,记为X,并附以下标以区别不同的通道输出类型;(3)输入参数类型列表形式化为内/外通道输入类型,记为Y,并附以下标以区别不同的通道输入类型;(4)符合X类型的变量或值x,记为X:=x;(5)符合Y类型的变量向量或值向量y,记为Y:=y;(6)Y和X均可以为空;(7)X:=x,z,则表示变量或值x和z均符合X类型;则将构件两种类型的交互点分别形式化为External-channel=OP!
YX,Internal-channel=\OP!
YX.
定义3.
构件对外提供的某一功能方法OP,其形式语义为进程C的某一通道OP,记为C.
OP;内部隐藏的某一功能方法OP,其形式语义为进程C的某一内通道,记为C.
\OP.
定义4.
构件的所有实例形式化为集合L,与构件之间的关系形式化为L:C;构件的某一实例形式化为集合元素l,与构件之间的关系形式化为l:C,且有l∈L;实例对外提供的某一功能方法记为l:C.
OP.
定义5.
构件任一功能方法内部,显式或隐式存在的所有变量元或常量元,其形式语义定义为通道状态元集,记为OP.
Sch;则其上任一状态元y,有y∈OP.
Sch;引起状态元y状态变化的算法步骤,形式化为映射函数f,变化前的状态为y,变化后的状态为f(y),对于常量元,则是一种等价映射,有y=f(y).
例如,构件一种功能方法内两条语句:inta=0;a++;状态元a在变化前为a=0;经自增算法运算后f(a)=1.
另外,两个状态元相等用"="连接来表示.
定义6.
硬编码的基于过程调用交互中遵循的交互协议,其形式语义为连接(join),记为Join=AB,其中,前件A描述交互协议中应满足的条件,后件B描述满足交互协议条件的结果.
为降低语义描述的复杂性,我们做出以下假设约束:约束规则1.
不允许构件中出现对外交互的内交互点,凡是内交互点,均修改为外露的.
事实上,在目前的程序设计中是没有这种设计约束的,允许构件的私有方法调用其他构件的公有方法.
但是,假设约束中规定做出的修改,也是目前的程序设计所允许的,所以这种假设约束是允许的.
通过约束规则1,将两种类型的交互点统一为一种形式:OP!
YX.
为了避免在死锁连接检查算法中构造构件连接有向图时生成具有重边的有向图,以降低生成的有向图的复杂性,我们做出以下假设约束:约束规则2.
不允许在构件的一种功能方法中,重复调用另一构件的同一种方法.
事实上,在目前的程序设计中也没有这种设计约束,在不少情况下是存在重复调用的,并且也是需要存在的.
所以这种约束对于实际程序设计来说不太恰当,但这里做出这种约束,目的是为了降低后面问题解决的难度.
另外,针对这种假设的不恰当性,规定这种约束是非强制性的,在必须的情况下,可以违反这种约束,出现重复调用.
如果出现这种重复,则做出简化处理,认为只调用了1次.
这种处理不会影响死锁连接回路的查找,也避免了重边的出现.
基于上述形式语义定义和约束规则,将两构件(C1和C2)之间基于过程调用的交互,形式化为基于过程调用连接器(call-basedconnector),其形式语义模型如下:Call-basedConnectorChannelcaller=C1.
OP1!
Y1X1Channelcallee=C2.
OP1!
Y2X2Join=y1,z1∈C1.
OP1!
Y1X1.
Sch∧Y2:=f(y1)∧X2:=x2,z1∧x2∈C2.
OP1!
Y2X2.
Schl1:C2.
OP1!
f(y1)x2∧z1=x2在该模型中,通道channel描述了连接器的两个交互点,并用caller和callee标识调用者和被调用者;连接Join描述了两个交互点间进行交互遵循的协议.
模型将一种特殊情况也包含在内:caller和callee分别标识的channel可以是同一个构件的两个不同通道,这种情况下,模型表示的语义为同一构件不同通道之间的交互.
因为在程序设计中,为提高代码的重用性,一个构件对外提供的任一功能方法也允许被该构件对外提供的其他功毛斐巧等:解决构件连接死锁问题的一种方法2531能方法所调用,这种重用方式被开发人员使用后容易间接地造成构件间的死锁连接,所以将这种特殊情况考虑在内以扩大连接器的语义范围,从而将构件内部基于过程调用造成的死锁连接也覆盖在内.
该模型除了可以用于语义层次上的死锁连接检查以外,还可用于语法层次上的类型匹配检查,这里的研究主要关注前者.
2.
2两阶段死锁连接检查算法基于第2.
1节的Call-BasedConnector模型,可以将各个构件中各处硬编码的过程调用交互连接抽象成为一个个的Call-BasedConnector,然后进一步在其中找出存在的死锁连接.
为了在这些Call-BasedConnectors中找出存在的所有死锁连接,给出两阶段死锁连接检查算法(twophasesdeadlockconnectioncheck,简称TPDCC).
TPDCC算法第1阶段是基于Call-BasedConnectors动态构造构件连接有向图,第2阶段是在有向图中查找出所有简单回路.
在描述算法之前,先给出从Call-BasedConnector到构件连接有向图的映射规则、判定规则以及相关定义.
映射规则1.
将caller和callee标识的Channel分别映射为构件连接有向图中的顶点.
定义7.
对于Channel1=C1.
OP1!
Y1X1和Channel2=C2.
OP1!
Y2X2,若Channel1与Channel2的形式一样,即C1.
OP1!
Y1X1=C2.
OP1!
Y2X2,则称Channel1和Channel2为等价通道,描述的是同一个交互点.
映射规则2.
等价通道映射为构件连接有向图中相同的顶点.
映射规则3.
将Join映射为构件连接有向图中连接代表其callerChannel和calleeChannel的顶点的有向边;将Join后件中的li:Cj映射为构件连接有向图中代表其所在的Join的有向边的边权.
映射规则4.
将caller标识的Channel映射为构件连接有向图中代表其所在的Join的有向边的始点;将callee标识的Channel映射为构件连接有向图中代表其所在的Join的有向边的终点.
映射规则5.
将Call-BasedConnectors间存在的死锁映射为构件连接有向图中的回路.
判定规则1.
若构件连接有向图中存在一个简单回路,则构件连接间存在一个死锁连接,并且死锁连接就是该简单回路.
在上述映射规则的基础上,可以应用如下所示的TPDCC算法(在算法中默认起始输入的连接器个数至少为1)动态地构造构件连接有向图,并将查找构件连接中的所有死锁连接问题,转化为查找构件连接有向图中存在的所有简单回路问题,找出构件连接中的所有死锁连接.
TPDCC算法伪码描述.
Step1.
1:{Connector}=inputAllConnectors(connectorfile.
xml);{Connector}.
length=computeConnectorLength();i=1;{Vertex}=;{Edge}=;gotoStep1.
2;Step1.
2:if({Connector}.
length>=1){i++;{Connector}.
length-=1;gotoStep1.
3;}else{gotoStep2.
1;}Step1.
3:{Connector}[i]=getConnector(i);if({Connector}[i].
caller{Vertex}){{Vertex}.
createV({Connector}[i].
caller);}if({Connector}[i].
callee{Vertex}{{Vertex}.
create({Connector}[i].
callee);}{Edge}[j]={Edge}.
createE({Connector}[i].
caller,{Connector}[i].
callee);{Edge}[j].
power={Connector}[i].
Join.
getPowerinB();gotoStep1.
2;Step2.
1:computeInandOutDegreeofVertex({Vertex});{ZeroinDegreeVertex}=findAllZeronInDegreeVertex({Vertex});{Circle}=;{UnvisistedVertex}={Vertex};gotoStep2.
2;Step2.
2:if({ZeroinDegreeVertex}!
=){{ZeroinDegreeVertex}[m]=findMaxOutDegreeVertex({ZeroinDegreeVertex});gotoStep2.
3;}else{if({UnvisistedVertex}!
=){{UnvisistedVertex}[m]=findMaxOutDegreeVertex({UnvisistedVertex});startVertex={Vertex}[{UnvisistedVertex}[m].
index];{Presequence=;k=1;gotoStep2.
4;}else{gotoStep2.
6;}}Step2.
3:startVertex={Vertex}[{ZeroinDegreeVertex}[m].
index];2532JournalofSoftware软件学报Vol.
19,No.
10,October2008{Presequence}=;k=1;{ZeroinDegreeVertex}.
delete(m);gotoStep2.
4;Step2.
4:if({Presequence}==){{Presequence}.
add(startVertex);gotoStep2.
5;}else{k={Presequence}.
find({startVertex};}if(k>=0){{Circle}.
add({Presequence}.
copySequence(k));k=1;startVertex={Presequence}.
getLastNode();gotoStep2.
5;}else{{Presequence}.
add(startVertex);gotoStep2.
5;}}Step2.
5:if({Vertex}[IndexofstartVertexin{Vertex}].
visited==true){If(startVertex∈vertexesIn{Circle}){{Presequence}.
deleteLastNode();startVertex={Presequence}.
getLastNode();if(startVertex==null){modify{UnvisitedVertex};gotoStep2.
2;}else{gotoStep2.
5;}else{if({Vertex}[IndexofstartVertexin{Vertex}].
outDegree!
=0){{Vertex}[IndexofstartVertexin{Vertex}].
visited=false;for(eachadjacentedgeiof{Vertex}[IndexofstartVertexin{Vertex}]){{Edge}[i].
visited=false;gotoStep2.
5;}}else{{Presequence}.
deleteLastNode();startVertex={Presequence}.
getLastNode();if({startVertex==null}{modify{UnvisitedVertex};gotoStep2.
2;}else{gotoStep2.
5;}))else{if({Vertex}[IndexofstartVertexin{Vertex}].
outDegree==0||alladjacentedgesarevisited){{Vertex}[IndexofstartVertexin{Vertex}].
visited=true;{Presequence}.
deleteLastNode();startVertex={Presequence}.
getLastNode();if(startVertex==null){modify{UnvisitedVertex};gotoStep2.
2;}else{gotoStep2.
5;}}else{chooseanedgeiinitsunvisitedadjacentedges;startVertex={Edge}[i].
endNode;{Edge}[i].
visited=true;gotoStep2.
4;}}Step2.
6:if({Circle}!
=){outputallcircles({Circle});}else{output:nodeadlockcircles.
}2.
3基于极大复用频率死锁连接消除算法找出所有死锁连接后,关键问题是如何消除这些死锁连接.
造成死锁连接是因为连接形成了回路,因此要找到合适的有向边作为破除边,有效地打破回路.
我们给出基于极大复用频率的死锁连接消除算法(deadlockconnectioneliminationbasedonmaximumreusefrequency,简称DCEMRF).
该算法主要解决了消除死锁连接的关键部分,即找出要破除的有向边.
而死锁连接的真正消除还要进行具体的实现工作:修改设计实现,即根据找出的要破除的有向边,对应到其所代表的构件交互连接的实现;在保证功能不变的前提下,修改这些实现,去掉这些交互连接,即进行代码重构.
针对实现,为防止进行代码重构后形成新的死锁连接,这里给出修改设计实现的约束规则.
约束规则3.
要破除构件交互连接,需修改连接实现的位置;需修改的位置,在进行代码重构后,不存在连接,或存在连接但与之连接的交互点有且仅有一个连接.
该算法的主要思想是,找出回路集内存在的不同边中复用频率最高的一个作为消除边,然后删除回路集内所有包含有此边的回路;如此反复进行,直到回路集变空,便找到了破除所有回路,要破除的最小数量的有向边.
其中复用频率的定义如下:定义8.
在检查出的所有死锁连接回路中存在的、代表不同构件连接的有向边,在所有回路中出现的次数之和,称为该有向边(或构件连接)的复用频率.
DCEMRF的算法描述如下所示(在算法中默认输入的死锁连接回路集非空).
DCEMRF算法伪码描述.
Step1:inputdeadlockcircles({circle});gotoStep2;Step2:computeEdgeReuseFrequency({circle},{Edge});{Edge}[m]=findMaxReuseFrequency();{EleminateEdge}.
add({Edge}[m]);gotoStep3;毛斐巧等:解决构件连接死锁问题的一种方法2533Step3:for(eachcircle∈{circle}){If({Edge}[m]∈circle.
{edges})deletecircle(circle);}if({circle}!
=){gotoStep2;}else{gotoStep4;}Step4:if({EleminateEdge}!
=){outputEleminatedEdges({EleminateEdge});}else{output:errormessage;}3应用及实验结果与分析3.
1方法的应用在我们正在研发的软件开发平台SmartFramework中,应用上述方法实现了DCCTool子工具.
使用DCCTool,可以检查出应用系统的构件中存在的所有基于过程调用死锁连接,并找到消除这些死锁连接需要打破的构件连接.
不过,目前从硬编码的构件连接到抽象语义模型连接器的建立这一步来看,DCCTool还没有实现自动化,还要靠人工将硬编码的基于过程调用的构件连接抽象成为连接器,并将之保存在特定结构的XML格式文件中.
在DCCTool中实现TPDCC算法时,连接器直接从XML格式文件中输入.
第3.
4节给出了我们在实际系统中使用DCCTool进行检测的结果.
3.
2实验与结果为了检验解决方法的有效性、TPDCC算法和DCEMRF算法的正确性,并测量这两种算法的性能,我们设计测试实例,使用DCCTool进行实验.
实验硬件环境是P4CPU2.
40GHz,1G内存;实验软件环境为DCCTool.
另外,DCCTool的运行环境JVM的内存空间范围为(64M~512M),版本为jdk1.
5.
0_02.
测试实例设计:设计10组测试实例,调整每组实例中包含的交互点的个数v,连接器个数m和死锁连接回路个数n,在DCCTool中分别输入每组测试实例并运行该工具,观察运行结果中找到的死锁连接回路、要消除的构件连接、TPDCC算法和DCEMRF算法执行的时间以及占有的内存空间.
其中1组测试实例含10个交互点、12个连接器和2个死锁连接回路(限于篇幅,这里省略详细实例),该实例其中1次测试运行结果如图3所示,其他测试实例都是在该实例的基础上进行增加和删除的,这里也省略描述,只给出运行结果中要消除的连接,两种算法各自的执行时间和占有的内存空间,见表1(注:每组测试实例都至少运行5次,两种算法执行时间和占有的存储空间值取其中较稳定的3次的平均值作为最终结果).
Fig.
3Atestingresult图3一个测试结果2534JournalofSoftware软件学报Vol.
19,No.
10,October2008通过利用这10组测试实例进行实验,所测结果表明,应用所提出的解决方法是能够找到构件连接中存在的所有死锁连接的,并能正确给出破除所有死锁连接需要消除的连接.
Table1Runningresultsof10groupsoftestcases表110组测试实例运行结果TPDCCalgorithmDCEMRFalgorithmGroupvmnTime(ms)Space(Kbyte)Time(ms)Space(Kbyte)Connectionstobeeliminated0101114.
4795248.
5700.
0077786.
461C2.
OP1!
Y2X2--l1:C3→C3.
OP1!
Y1X11101004.
248157.
2730.
0029736.
797Noconnectiontobeeliminated2101224.
5290246.
4240.
0082836.
477C4.
OP1!
Y5X3--l2:C5→C5.
OP1!
Y4X13141624.
6048253.
5630.
0090476.
555C4.
OP1!
Y5X3--l2:C5→C5.
OP1!
Y4X14161824.
6161257.
3440.
0089866.
836C4.
OP1!
Y5X3--l2:C5→C5.
OP1!
Y4X15182134.
6614265.
3670.
0482457.
531C4.
OP1!
Y5X3--l2:C5→C5.
OP1!
Y4X1C4.
OP2!
Y2X4--l2:C6→C6.
OP1!
Y2X26232634.
7345270.
8360.
0131316.
320C4.
OP1!
Y5X3--l2:C5→C5.
OP1!
Y4X1C4.
OP2!
Y2X4--l2:C6→C6.
OP1!
Y2X27262824.
7770271.
0310.
0128356.
320C2.
OP1!
Y2X2--l1:C3→C3.
OP1!
Y1X1C4.
OP2!
Y2X4--l2:C6→C6.
OP1!
Y2X28303444.
8737285.
6170.
02026712.
328C4.
OP1!
Y5X3--l2:C5→C5.
OP1!
Y4X1C8.
OP1!
Y2X1--l1:C10→C10.
OP1!
Y2X4C4.
OP2!
Y2X4--l2:C6→C6.
OP1!
Y2X29333854.
9612294.
3830.
03284218.
805C4.
OP1!
Y5X3--l2:C5→C5.
OP1!
Y4X1C8.
OP2!
Y3X3--l2:C9→C9.
OP2!
Y2X2C8.
OP1!
Y2X1--l1:C10→C10.
OP1!
Y2X4C4.
OP2!
Y2X4--l2:C6→C6.
OP1!
Y2X23.
3算法性能分析由10组测试实例测得的实际复杂度仅能反映出TPDCC算法和DCEMRF算法在连接器个数m、交互点个数v和死锁连接回路个数n在较小范围内变化时的实际性能,而针对这两种算法也很难设计出具有代表性和普遍性的测试实例.
另外,测试实例数据很难自动生成,目前主要靠手工设计,进行大规模的实例测试可行性不大.
因此,我们进一步从理论上对TPDCC算法和DCEMRF算法进行渐近性能分析(m,v,n为变量,其他均为常量).
在TPDCC算法中与时间复杂度相关的关键操作有输入m个连接器的时间t1m(t1为输入一个连接器的平均时间);创建所有顶点时间t2v(t2为创建一个顶点的平均时间);创建所有顶点所进行比较操作的时间(v(v+1)/2)t3(t3为一次顶点比较的平均时间);创建所有边的时间t4m(t4为创建一条边的平均时间);计算所有顶点出度和入度的时间2t3v2;查找新一轮访问起始顶点最坏情况下的时间共为nvt3;查找回路在访问集中的起点位置的时间共约为n(v/2)t3;取所有回路的时间共约为nt5(t5为平均一次取回路的时间);找到所有死锁回路访问顶点最好情况下共需时间约为vt6+nt6(t6为访问一个顶点的平均时间);输出所有回路的时间共约为t7n(t7为平均输出一个死锁回路的时间).
因此,TPDCC算法的渐近时间复杂度为O(m+v2+nv).
在TPDCC算法中与空间复杂度相关的关键数据存储空间主要有所有连接器占用的空间p2m(p2为一个连接器需占用的字节);所有顶点占用的空间p1v(p1为一个顶点需占用的字节);所有边所占用的空间p3m(p3为一条边需占用的字节);回路集{circle}共占用的空间约为(l1/k1)mn(假设每个回路中含(1/k1)m条边,1≤k1≤m,每个对象引用占l1字节);入度为0的顶点共占用的空间约为(l1/k2)v(设入度为0的顶点共有(1/k2)v个,1≤k2≤v);未访问过的顶点集共占用的空间约为(l1/k4)v(1≤k4≤v);一轮访问前序顶点集占用的空间约为(l1/k3)v(1≤k3≤v).
因此,TPDCC算法的渐近空间复杂度为Θ(v+mn).
在DCEMRP算法中,与时间复杂度相关的关键操作有计算复用频率的时间(n/l)k2m2(假设需计算l轮,1≤l≤n,则每个死锁回路中有km条边,0≤k≤l);找出复用频率最大值边的时间约为t3m2k2(n/l);输出要消除的边的时间约为qnt0(q为输出一条边的平均时间,0≤q≤1).
因此,DCEMRP算法的渐近时间复杂度为O(nm2).
在DCEMRP算法中,与空间复杂度相关的关键数据存储空间有回路集{circle}共占用的空间约为(l1/k1)mn;要消除的边占用的空间(l1/j1)n(1≤j1≤n);暂存待删除的回路对象的引用占用的空间约为(l1/j2)n(1≤j2≤n).
因此,DCEMRP算法的渐近空毛斐巧等:解决构件连接死锁问题的一种方法2535间复杂度为Θ(mn).
3.
4工具的应用我们尝试在实际系统中使用DCCTool进行检测,所获结果初步体现出其在增强软件可靠性上存在的价值.
所检测的福利注册系统是一个典型的由EJB构件基于过程调用连接而构成的应用系统,是在Sun公司提供的用于剖析EJB构架和说明如何使用EJB构件的开源福利注册应用程序[15]基础上扩展得到的.
该系统中的构件在功能和类型上均具有代表性:EJB构件的所有类型(有状态会话型、无状态会话型、消息驱动型和实体型)均有包含,企业信息系统常用的功能(如辅助展现,数据库初始化,增、查和改等业务处理功能)也有包含.
并且系统所含的交互点个数和连接器个数与实验中的测试实例相比也有数量级的提高.
检测结果如图4所示,存在一个死锁连接.
根据所建立的连接器模型在语义上与实际构件交互的映射关系(见表2,这里只给出了与死锁连接相关的部分映射关系,并且构件对外提供的方法只给出了名称,其他部分略),对应可知,Options构件的getOptionDescription方法、OptionContent构件的setContent方法、EnrollmentBean构件的setMedicalOption方法、SelectionCopy构件的setMedicalPlan方法与OptionContent构件的isAccess方法之间形成了循环递归调用.
其中,SelectionCopy构件和EnrollmentBean构件属于实体型,Options和OptionsContent构件分别属于有状态会话型和无状态会话型.
Fig.
4Checkingresultofwelfareregistrationsystem图4福利注册系统检测结果Table2Partialmappingrelationsofconnectormodel表2连接器模型的部分映射关系ComponentsMethodsInstanceEdgepowerConnectorchannelsEnrollmentBeansetMedicalOptionebl7:C3C3.
OP5!
Y4X1OptionsgetOptionDescriptionopsl7:C9C9.
OP4!
Y4X10SelectionCopysetMedicalPlanselcopyl1:C40C40.
OP4!
Y10X1OptionContentisAccessopcl1:C49C49.
OP1!
Y1X11OptionContentsetContentopl2:C49C49.
OP2!
Y1X9而且所指出的应当消除的死锁连接是C9.
OP4!
Y4X10—l2:C49C49.
OP2!
Y1X9,即Options构件的getOptionDescription方法中创建了OptionContent构件名为op的实例,以op实例为对象调用OptionContent构件的setContent方法,按照第2.
3节的约束规则3,这段代码必须进行重构.
我们采用的重构方式是直接删除这段代码,取而代之的是在OptionContent构件内部新建一种与外部无交互的私有方法,实现与OptionContent构件的setContent方法相同的功能,直接调用该私有方法.
在该系统检测过程中,TPDCC算法耗时约7.
0351ms,占存储空间约441.
383k;DCEMRF算法耗时约0.
008743ms,占存储空间约7.
188k.
而该系统中包含的交互点个数为194,连接器个数为295,与测试实验中第0组测试2536JournalofSoftware软件学报Vol.
19,No.
10,October2008实例测试结果相比,当连接器个数和交互点个数有数量级提高时,两种算法所耗时间和空间都没有发生数量级的猛增,体现了算法的稳定性.
4相关研究工作构件死锁连接是一种逻辑错误,是构件化软件语义层次上的一个问题,是在构件集成过程中产生的一种错误,也是造成构件化软件系统产生死锁的因素之一.
目前,在国内外同行的研究中,还未发现有专门解决该问题的文献,但在软件系统死锁问题研究领域存在一些较有代表性的研究工作.
Christoph[16]通过构造基于构件系统的3-SAT公式,每个构件的行为用一个有限标签变换系统表示,整个系统的行为由各连接器的行为和各构件的标签变换系统构成的一个全局标签变换系统表示,执行系统状态空间变换和分析,得出结论为:在基于构件的软件系统中,局部和全局死锁存在性检测都是NP难题.
之所以成为NP难题,是因为检测过程涉及到系统全局状态分析.
不过,Chritoph与其同事在文献[17]中给出一种可在多项式时间内检测完毕的参数化的系统局部无死锁确认算法,但实际可用性较低.
其研究针对的死锁检测不区分产生死锁的原因,构件化软件系统中导致死锁的原因有多种类型(如资源共享[18]、强同步约束[18]和多线程同步[19]等),为了追求全面,将各种原因都包括在内而使问题更加复杂,难以解决,又沿状态空间变换和分析途径解决,随着系统复杂度的增大,必然会面临状态空间爆炸问题.
构件死锁连接也是导致系统产生死锁各原因中的一种类型,本文只针对这一类型进行研究,缩小了问题范围,便于解决.
同时,避开了系统状态空间分析,将问题转化为简单有向图回路查找问题,从而使问题得到较好的解决.
与我们具有相似解决死锁问题方针的文献[20],针对另一种类型的死锁产生原因:即通信关系不当导致系统产生死锁,给出了检测方案,并提供了动态死锁测试工具(DDTTool),虽然其研究直接针对的是并发多任务的ADA程序,而非构件化软件,但运行于分布式环境中的构件化软件同样具有并发多任务特征,故其解决方案亦可以借鉴.
另外,文献[19]针对因多线程同步不当而导致系统死锁给出解决方法,并提供了该类死锁的检测工具(C-checker),而其研究直接针对的是共享主存并行程序OpenMP.
另外,文献[21]给出一种基于代数变换方法,从软件设计形式规约出发,可推导系统中是否存在因构件间通信数据依赖和缓冲区对称访问等而引起的死锁.
该方法虽然理论上不受软件系统复杂性的限制,但其复杂的推理公式和变换规则,没有自动推导工具支持,难以付诸实践.
而文献[22]则建立了一种并发计算数据流模型,构件间采用数据托肯(token)流进行通信,通过为构件设计一种因果依赖接口,静态分析构件间是否存在因数据依赖环而产生的死锁.
对于基于状态空间分析方法检测死锁会遇到的状态空间爆炸问题,文献[23]提出一种基于启发式的搜索技术,但并不能彻底解决该问题.
不过其方法可以与其他削减状态空间的方法(如基于状态等价[24,25]、局部模型检测[26])结合使用.
此外,文献[27]在所建立的状态缩减理论(IOT-failure和IOT-state等价理论)的基础上,也给出7条基本的启发式规则,用于削减状态空间.
在死锁避免方面,文献[2,18]从软件构造的角度提出一个基于构件的建模框架,指导构件正确组装,可用于从无死锁的构件构造无死锁的软件系统,并给出了无死锁系统中构件应满足的充要条件,以及由无死锁构件构造无死锁系统应满足的充要条件.
文献[28]用进程代数PA(processalgebra)形式化地描述构件间的交互行为协议,提供一组交互行为协议相容性检验规则和定理,可用于防止相组装的两个构件因接口行为不一致而产生死锁的情况出现.
5总结及今后的工作针对构件化软件中采用基于过程调用交互方式构件连接所存在的构件间死锁连接问题,我们研究提出了一种完整的解决方法.
建立了基于过程调用连接器形式语义模型call-basedconnector,给出了TPDCC算法和DCEMRP算法以及消除死锁连接的设计约束规则.
应用该解决方法设计实现了DCCTool子工具,证明该方法是可行的;10组测试实例和福利注册系统在DCCTool中检测执行的结果表明,所给出的解决方法能够正确找到构件连接中存在的所有死锁连接,并能准确给出消除所有死锁连接需要消除的最小数目连接的位置.
此外,构件间毛斐巧等:解决构件连接死锁问题的一种方法2537的死锁连接问题属于语义层次上的问题,目前的软件开发工具在编译链接应用系统时只能检查出语法问题,无法检查出存在的构件死锁连接.
因此,本文的研究工作为构件连接存在的死锁连接问题提供了一种可行而有效的解决方法,同时,为增强软件的稳定性和可靠性提供了一种途径.
在解决问题的过程中,抽象出的所有call-basedconnector保存在特定的XML格式文件中.
这种处理方式,一方面将构件与连接关系显式分离,另一方面,将连接关系描述为与构件具有同等地位的独立实体.
在设计实现软件时可以采用这种处理方式,这样可以使构件间的连接关系易于修改和扩展,从而支持构件间柔性集成,在构件连接层次上为适应性软件设计提供新思路.
Call-BasedConnector目前主要描述出了构件间的交互协议以及数据类型和传递约定,在此基础上可增加支持构件动态连接的操作,以方便构件交互关系的定制和调整以及构件的替换,为设计实现适应性连接器奠定基础.
这些是可继续深入研究的工作,也正是我们下一步的研究工作.
而可继续开展的扩展性研究包括,设计实现相容性检查工具,以辅助进行正确的构件集成和支持构件连接可配置软件的配置部分的正确性检查,因为call-basedconnector语义模型也支持语法层次上的类型匹配检查.
References:[1]LiG,JingMZ.
Concept,propertiesandfunctionsofcomponentconnectioninadaptivesoftwarearchitecture.
ComputerEngineering,2003,29(1):265267(inChinesewithEnglishabstract).
[2]GosslerG,SifakisJ.
Compositionforcomponent-basedmodeling.
ScienceofComputerProgramming,2005,55(1-3):161183.
[3]AllenRJ.
Aformalapproachtosoftwarearchitecture[Ph.
D.
Thesis].
Pittsburgh:CarnegieMellonUniversity,1997.
[4]RenHM,QianLQ.
Researchoncomponentcompositionanditsformalreasoning.
JournalofSoftware,2003,14(6):10661074(inChinesewithEnglishabstract).
http://www.
jos.
org.
cn/1000-9825/14/1066.
htm[5]XiongHM,YingS,YuLJ,ZhangT.
Acompositereuseofarchitecturalconnectorsusingreflection.
JournalofSoftware,2006,17(6):12981306(inChinesewithEnglishabstract).
http://www.
jos.
org.
cn/1000-9825/17/1298.
htm[6]WermelingerM,LopesA,FiadeiroJL.
Superposingconnectors.
In:Proc.
ofthe10thInt'lWorkshoponSoftwareSpecificationandDesign.
SanDiego:IEEEComputerSocietyPress,2000.
8794.
http://csdl2.
computer.
org/persagen/DLAbsToc.
jspresourcePath=/dl/proceedings/&toc=comp/proceedings/iwssd/2000/0884/00/0884toc.
xml&DOI=10.
1109/IWSSD.
2000.
891129[7]MageeJ,DulayN,EisenbachS,KramerJ.
Specifyingdistributedsoftwarearchitectures.
In:SchaferW,BotellaP,eds.
Proc.
ofthe5thEuropeanSoftwareEngineeringConf.
Berlin:Springer-Verlag,1995.
137153.
[8]MilnerR,ParrowJ,WalderD.
Acalculusofmobileprocesses.
InformationandComputation,1992,100(1):140.
[9]OquendoF.
π-ADL:Anarchitecturedescriptionlanguagebasedonthehigher-ordertypedπ-calculusforspecifyingdynamicandmobilesoftwarearchitectures.
ACMSoftwareEngineeringNotes,2004,29(3):114.
[10]LiCY,LiGS,HePJ.
Aformaldynamicarchitecturedescriptionlanguage.
JournalofSoftware,2006,17(6):13491359(inChinesewithEnglishabstract).
http://www.
jos.
org.
cn/1000-9825/17/1349.
htm[11]CmpanS,LeymonerieF,OquendoF.
Handlingdynamicbehaviourinsoftwarearchitectures.
In:MorrisonR,OquendoF,eds.
Proc.
ofthe2ndEuropeanWorkshoponSoftwareArchitectures.
LNCS3527,Berlin:Springer-Verlag,2005.
7793.
[12]AllenR,GarlanD.
Aformalbasisforarchitecturalconnection.
ACMTrans.
onSoftwareEngineeringandMethodology,1997,6(3):213249.
[13]AllenR,DouenceR,GarlanD.
Specifyingandanalyzingdynamicsoftwarearchitectures.
In:AstesianoE,ed.
Proc.
ofthe1stInt'lConf.
onFundamentalApproachestoSoftwareEngineering.
LNCS1382,Berlin:Springer-Verlag,1998.
2137.
[14]HoareCAR.
Communicatingsequentialprocess.
2004.
http://www.
usingcsp.
com[15]MatenaV,DrishnanS.
ApllyingEnterpriseJavaBeans,Component-BasedDevelopmentfortheJ2EEPlatform.
2nded.
,Beijing:PearsonEducation,Inc.
,TsinghuaUniversityPress,2004.
50207.
[16]MinnameierC.
Localandglobaldeadlock-detectionincomponent-basedsystemsareNP-hard.
InformationProc.
Letters,2007,103(3):105111.
[17]Majster-CederaumM,MartensM,MinnameierC.
Apolynominal-timecheckablesufficientconditionfordeadlock-freedomofcomponent-basedsystems.
In:vanLeeuwenJ,ed.
Proc.
ofthe33rdInt'lConf,onCurrentTrendsinTheoryandPracticeofComputerScience.
LNCS4362,Berlin:Springer-Verlag,2007.
888899.
[18]GosslerG,SifakisJ.
Compoent-Basedconstructionofdeadlock-freesystems.
In:PandyaPK,ed.
Proc.
oftheAnnualConf.
onFoundationsofSoftwareTechnologyandTheoreticalComputerScience.
LNCS2914,Berlin:Springer-Verlag,2003.
420433.
2538JournalofSoftware软件学报Vol.
19,No.
10,October2008[19]WangZF,HuangC.
StaticdetectionofdeadlocksinOpenMPFortranprograms.
JournalofComputerResearch&Development,2007,44(3):536543(inChinesewithEnglishabstract).
[20]ShiXH,GaoZY,ShaoH.
AdynamicdeadlocktestingmethodofaconcurrentADAprogram.
JournalofComputerResearch&Development,1999,36(8):954960(inChinesewithEnglishabstract).
[21]CompareD,InveradiP,WolfAL.
Uncoveringarchitecturalmismatchincomponentbehavior.
ScienceofComputerProgramming,1999,33(2):101131.
[22]YeZ,LeeEA.
Acausalityinterfacefordeadlockanalysisindataflow.
In:Proc.
oftheACM&IEEEConf.
onEmbeddedSoftware.
Seoul:ACMPress,2006.
4452.
http://portal.
acm.
org/citation.
cfmid=1176887.
1176895&coll=GUIDE&dl=ACM&CFID=2029577&CFTOKEN=10062163[23]GradaraS,SantoneA,VillaniML.
DELFIN+:AnefficientdeadlockdetectiontoolforCCSprocesses.
JournalofComputerandSystemScience,2006,72(8):13971412.
[24]BouajjaniA,FernandezJC,HalbwachsN.
Minimalmodelgeneration.
In:Proc.
ofthe2ndInt'lWorkshoponComputer-AidedVerification.
LNCS531,Berlin:Springer-Verlag,1990.
197203.
http://springerlink.
lib.
tsinghua.
edu.
cn/content/jntlcg33mv7rrwpd/p=61814a0ed1d74ecc930363eec0f0292e&pi=4[25]GrafS,SteffenB,LuttgenG.
Compositionalminimizationoffinitestatesystemsusinginterfacespecifications.
FormalAspectsofComputing,1996,8(5):128.
[26]StirlingC,WalkerD.
Localmodelcheckinginthemodalmu-calculus.
TheoreticalComputerScience,1991,89(1):161177.
[27]TsaiJJP,JuanEYT.
Modelandheuristictechniqueforefficientverificationofcomponent-basedsoftwaresystems.
In:Proc.
ofthe1stInt'lConf.
onCognitiveInformatics.
Calgary:IEEEComputerSocietyPress,2002.
5968.
http://csdl2.
computer.
org/persagen/DLAbsToc.
jspresourcePath=/dl/proceedings/&toc=comp/proceedings/icci/2002/1724/00/1724toc.
xml&DOI=10.
1109/COGINF.
2002.
1039283[28]HuHY,LuJ,MaXX,TaoXP.
Studyonbehavioralcompatibilityofcomponentinsoftwarearchitectureusingobject-orientedparadigm.
JournalofSoftware,2006,17(6):12761286(inChinesewithEnglishabstract).
http://www.
jos.
org.
cn/1000-9825/17/1276.
htm附中文参考文献:[1]李刚,金茂忠.
适应性软件体系结构中构件连接的概念、特点和作用.
计算机工程,2003,29(1):265267.
[4]任洪敏,钱乐秋.
构件组装及其形式化推导研究.
软件学报,2003,14(6):10661074.
http://www.
jos.
org.
cn/1000-9825/14/1066.
htm[5]熊惠民,应时,虞莉娟,张韬.
基于反射的连接器组合重用方法.
软件学报,2006,17(6):12981306.
http://www.
jos.
org.
cn/1000-9825/17/1298.
htm[10]李长云,李赣生,何频捷.
一种形式化的动态体系结构描述语言.
软件学报,2006,17(6):13491359.
http://www.
jos.
org.
cn/1000-9825/17/1349.
htm[19]王昭飞,黄春.
OpenMPFortran程序中死锁的静态检测.
计算机研究与发展,2007,44(3):536543.
[20]史晓华,高仲仪,邵晖.
ADA程序通信死锁的动态检测方法.
计算机研究与发展,1999,36(8):954960.
[28]胡海洋,吕建,马晓星,陶先平.
面向对象范型体系结构中构件行为相容性研究.
软件学报,2006,17(6):12761286.
http://www.
jos.
org.
cn/1000-9825/17/1276.
htm毛斐巧(1980-),女,湖北老河口人,博士生,主要研究领域为软件工程,分布式计算.
林伟伟(1980-),男,博士,讲师,主要研究领域为计算机体系结构,网格计算.
齐德昱(1959-),男,博士,教授,博士生导师,主要研究领域为软件开发模式,网络安全,分布式计算.