о뷢չ
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
1999 36 8 Vol.36 No.8 1999



ADAͨĶ̬ⷽ
ʷǡۡ
ժҪADAص㣬һµADA̬ⷽ۵Ļʵһ̬ԹDDTT(dynamic deadlock testing tool).˹ܹȷADAͨŹϵɵ.ϸ˶̬ԹDDTTȫжԼĹԭ.
ؼʡADA򣬶̬
ͼšTP311
A DYNAMIC DEADLOCK TESTING METHOD OF A CONCURRENT ADA PROGRAM
SHI Xiao-Hua, GAO Zhong-Yi, and SHAO Hui
(Software Engineering Institute Beijing University of Aeronautics and Astronautics Beijing 100083)
AbstractAccording to the features of ADA concurrent programs, a new theory is introduced, which can be used to detect most deadlocks in an ADA program. A deadlock detecting tool named DDTT(dynamic deadlock testing tool) relying on this theory is designed. This detecting tool can be used to detect communicating deadlocks in a multi-task ADA program. The theory and detecting rules used by DDTT are described in detail. Finally, the working principle of DDTT is introduced.
Key wordsdeadlock, ADA program, dynamic detecting
1
ADA쵼Ƶͨ,ڷֲʽϵͳеõ˹㷺Ӧ,ҪԭADAṩǿĲƽ̨Ķ̻.ֲʽмҪƽ, ֮һηֹ.(task)ΪADAĵԪвǡͨʱԵ³͵ǿͨؼ.
̬ǷչýⷽдԵֱַΪ򼯣1ݺPetri.ӹɶԳ̬ԵõһȽȫ͸˽⣬һõķģͣǿܶһĸõȽȫж.Ǿ̬ķǺѴģһǳе顢ȱʵоǾ̬ķΪ׷ȫ棬յNP⡢ϱը.ͬʱû˵̬õġܡıǲܹ.ǸʵʱǷʵʱġǷΪȵȷǳ.ˣڴѾо.дԵJinde ChengADAȫ෽ҸӦĽһö̬طʽʵʱķ2ݣڹδоɹ.ҪǣADAͨĶ壻ԪͨŹϵUDGͼʽʾ֤жԼ۹Ļʵһ̬ADAͨĹԭ.
н۲öֶ̬μADAͨĲǡʱҪۣȻ򵥽ڴ˻ҵʵֵһ̬⹤DDTT(dynamic deadlock testing tool).
2̬׼
2.1ͨĶ
1. ͨ
ǳһڽĳһڵΪADAԵͨ.
2. ADAԵͨ
һADAָͨһͨ䴦һֲѭµ޵ȴ״̬ӶЩ޷ִȥ(粻رעἰġΪADAͨ).
2.2ж
2.2.1ԪͨŹϵUDGͼʾ.
һЩҪĸ׼3ݣ
3. ִеԪɷΪ4ࣺ
(1) Subprogram:   procedure  function
(2) Block:   declare-block  accept-block
(3) Task:   task body  the object of a task type
(4) Package:   package specification  package body.
4. Ԫ
ǳһִеԪΪģҽеһ֣
(1) һӵwith packagesԪԣʼֱִӻwith packageĴ룻
(2) ִеԪԣʼִڴ˵Ԫд룻
Ԫûֹ.
رأڲͬʱ̻ͬλõͬһSubprogramͬһtask typeĲִͬͬһtask body Ĵ룬ǶĳһضʱǲͬĻԪ.Եݹԣ˵ΪҪ.
5. Ԫȷ׶(elaboration)
ǳһԪȷ׶Σҽ˻Ԫδִ.
6. Ԫִн׶
ǳһԪִн׶Σҽ˻Ԫȷ׶.
7. Ԫ״̬
ǳһִн׶εĻԪΪ״̬ҽ˵ԪִеEND֮ǰδִĽ.
8. ֹԪ
ǳһԪENDִ֮󣬴˵ԪΪֹ.
9. ӵԪ
ǳһԪUnit1ΪһԪUnit2ӵԪҽ3ֹϵеһ֣
(1) Unit1Unit2ͨwithֱӻõİUnit2ΪADAԪ
(2) Unit1Unit2õӳ
(3) Unit1Unit2ֱڶ32еĵԪ.
10. ֱӼ
ǳһTaskTask TypeĶǱһڶ3123еĻԪֱӼģҽֹϵеһ֣
(1) tasktask typeĶִеԪֱ˵ģ
(2) tasktask typeĶڱִеԪֱӻõİУ弰ֱ˵ģִеԪADAԪ.
11. Ԫʶ
һADAУÿһԪӵһΨһıʶֱֹ״̬ΪֲͬԪΨһʶ.
12. ʶ
һADAУÿԪ34ִеԪӵһʶ.ÿֹtasktask typeĶԣ붼Ψһ.ͬtasktask typeĶͬһtask type ĲͬӵһΨһԼʶ.
رأǶһ˳елԪӵһͬʶ.
13. ǶԪUnit1Unit2ӵͬʶ룬ҽԪֹϵеһ֣
(1) Unit1ΪUnit2ӵԪ֮
(2) һ򼯺ϣ
P1Pmm0
 P1ΪUnit1ӵԪ
 Unit2ΪPmӵԪ
 κδڵ1imPiΪPi-1ӵԪ
Unit1Unit2任λ.
14. Ԫ
ǳֱӼһtasktask typeĶĻԪΪĸԪ.ɶ12֪һԪĸԪʶ벻ͬڴʶ룬ҲͬڷκֹԪʶ.
15. Ԫɵȴ״̬
ǳһԪɵȴ״̬ҽͬʱ
(1) ˻Ԫ״̬
(2) ˻ԪֱӼУδֹ״̬ĵԪ.
16. Ԫͼ(unit description graph)
ǶһͼĳһضʱtʵʱǶʽϵͳinterleaved implementationtΪĳһʱ̣ڷֲʽϵͳdistributed implementationtΪĳһʱ̣ĳһضıⲢADAP÷űʾΪUDG(P,t)Ӧһ9Ԫͼ
(OA(P,t)OF(P,t)E(P,t)AactAextAcallAaccDW)
(1) OA(P,t)OAT(P,t) OAB(P,t)  OAS(P,t)  OAP(P,t)
OAT(P,t)ʾʱtڶ33еĻԪ
OAB(P,t)ʾʱtڶ32еĻԪ
OAS(P,t)ʾʱtڶ31еĻԪ
OAP(P,t)ʾʱtڶ34еĻԪ
(2) OF(P,t)OFT(P,t) OFB(P,t)  OFS(P,t)  OFP(P,t)
OFT(P,t)ʾʱt֮ǰֹڶ33еĵԪ
OFB(P,t)ʾʱt֮ǰֹڶ32еĵԪ
OFS(P,t)ʾʱt֮ǰֹڶ31еĵԪ
OFP(P,t)ʾʱt֮ǰֹڶ34еĵԪ
(3) E(P,t)ΪPʱtĻԪʱt֮ǰֹԪļϣ
(4) AactOA(P,t)OAT(P,t)
AactʾOA(P,t)OAT(P,t)֮һֶԪϵ
V1OA(P,t)V2OAT(P,t)ҽV2ǱV1ֱӼģ(V1,V2) Aact
(5) AextOA(P,t)OAB(P,t)  OAS(P,t)  OAP(P,t)
AextʾOA(P,t)OAB(P,t)  OAS(P,t)  OAP(P,t)֮һֶԪϵ
V1OA(P,t)V2OAB(P,t)  OAS(P,t)  OAP(P,t)ҽV2V1ӵԪ(V1,V2) Aext
(6) AcallOAT(P,t) OAB(P,t)  OAS(P,t) OAT(P,t)  OFT(P,t)E(P,t) 
AcallʾOAT(P,t) OAB(P,t)  OAS(P,t)OAT(P,t)  OFT(P,t)E(P,t) ֮һԪϵ
V1OAT(P,t) OAB(P,t)  OAS(P,t)V2OAT(P,t)  OFT(P,t)eE(P,t)ҽV1V2e(V1, V2 ,e) Acall
(7) AaccOAT(P,t) OAB(P,t) OAT(P,t) OAB(P,t) E(P,t)
AaccʾOAT(P,t) OAB(P,t) 루OAT(P,t) OAB(P,t) E(P,t) ֮һԪϵ
V1ʣOAT(P,t) OAB(P,t) eE(P,t)ҽеһ֣
.V1յȴһe
.V1һѡeͬʱ4
 eѾV1ĽյȴУ
 eûнϽ׶εִУ
 eûбһʱƻһelseԼһorterminateԼ
 a=(V1Vk) Aext(V1V1e) Aacc.
(8) DOA(P,t)OAT(P,t)
DʾOA(P,t)OAT(P,t)֮һֶԪϵ
V1OA(P,t)V2OAT(P,t)ҽ3ͬʱ
 (V1,V2) Aact
 V1V2ڻԪȷ׶Σ
 һV3OAT(P,t)ʹ(V2,V3) D(V1,V2) D.
(9) WOAT(P,t) OAB(P,t)  OAS(P,t)OAT(P,t)
WʾOAT(P,t) OAB(P,t)  OAS(P,t)OAT(P,t)֮һֶԪϵ
V1OAT(P,t) OAB(P,t)  OAS(P,t)V2OAT(P,t)ҽͬʱ
 V1ɵȴ״̬
 (V1,V2) Aact(V1,V2) W.
2.2.2ж
1. ԪĳһUDG(P,t)У
(1) a =V1V2e1Acall
V2OFTǳV1ںһѾֹĵԪ.
(2) a =V1V2e1Acall
V2OATV2״̬ǳV1ںһѾɵĵԪ.
(3) a =V1V2e1) Acall
V2Ѿ״̬ǳV1ںһѾĵԪ.
(4) a =V1V2) Aext
V2Ѿ״̬ǳV1Ϊ.
(5) a =V1V2) D
V2Ѿ״̬ǳV1Ϊ.
(6) a =V1V2) W
V2Ѿ״̬ǳV1Ϊ.
(7) һ򻷣a1 an  n1
Сai Acall 
ai Aext 
ai D 
ai W1in) 
ҵǰai=ViVi+1ei) Acallд ʽʱ򻷿ԱʾΪ 
V1V2) VnV1)  
ΪϵĽڵViOA1in) .
֤. ADA壬(1)(6)ǳ.ǽ֤(7).
ȸݶ491016֪(1)жУڲٴһai Acall.
Ǹѧɷ֤һ.
Ķ(1)a1=ViVi+1ei) Acall
 ֻһߣn=1ʱ
a1=V1V1ei) .
֪һڵĵԶܲϣɶ2֪V1Ϊ.еVi1in) ViΪ.
 n=kʱӵkߵеVi1in) ViΪ.ǰд(1)ļдʽʱ
V1V2) VkV1) 
 n=k+1ʱ֪ak+1 AcallAextDW.۵ak+1=Vk+1V1ek+1) Acallʱ
a1ak+1д(1)ļдʽ
V1V2) VkVk+1) Vk+1V1) 
ɶ16֪VkִܷнȡVk+1״̬Vk+1ִܷСܷͬV1һ,ȡV1״̬ҲVkͨVk+1V1״̬.ǿV1-V2-Vk-V1֮һ໥Ļ(2)еļ裬Ļÿһڵ㶼.(3)֪Vk+1V1ek+1) Vk+1һѾĽڵV1Vk+1Ҳ.еVi1ik+1) .
ak+1 AextDWʱɶ16֤֪ͬϵн㶼Ϊ.
2. ж
һUDG(P,t)VjOA֮һǳелԪΪģ
(1) ݶ1жVjΪģ
(2) 
a1 an n0
n0ʱ
aiAcall 
aiAext 
aiD 
aiW1in) 
an=VnVnen) Aacc
a1ǴӽڵVjı.
ԣ
һanam=VmVm+1em) Acall Vm+1ʶVnʶͬôڣVnVnek) Aaccʹek=em.
֤. ֤һUDGͼлԪ֮һелԪΪ.
һԪVj1Լģ
Ԫ2˵VjִܷȡVnǷԲһ.(2)Կ֪һԪVlʹVlVnڵȴڲҲһ.Ҳ˵VjִܼȥΪ.
3̬⹤ߵʵ
̬⹤DDTTɣһԤһǼ.
3.1Ԥ
Ԥɾ̬ԴתһϢ.ͼ1ʾ.


ͼ1
̬ΪADAһԵĹߣķϷADA83ıADAԴз.ҪԴ򣬶ǽADAԴΪϵͳݣԶزľ̬ԱΪ̬ԼԵ춨ݻ.
ԴתֳԴ봦ԤмϵĹؼ.˼壬һֵĹǽһPתΪҪĳP䣬תĳϢھ̬.ܵԭڳвװʵ֪315еĸֵԪ״̬֮ĸֹϵ.
Ϣڹ.κβͬıļ˱޸ĺıļһ.
3.2
뱻򽫲ýͨŵֶﵽϢ.ϵͳбٳһרļб֮ͨ.
ϢһнУǿ԰һֻڲװλϵúڴеϢдйϢɣͬʱڴȡϢļ.մļȡӦϢǰ弰жԴ.
4
һADAʼкʱtݲͬԪ״̬жϴ˳ǷͨƲµ״̬Ľ.ݴ˷ڱо塱塱ҵɵADAԹߵĻϣʵһнϺʵԡԴбȽȫADA̬⹤.ȫǻк·ҪߵģǱ˽һ֡һֵķ룬ϣܹСһǰ.
߼飺ʷУ19733ʿоҪоΪ̺Լ.ǣУ19351ڣҪоΪʽԶۡɿԡ̻̹.ͣУ19695˶ʿоҪоΪǶʽϵͳĿԡ̼价.
ߵλʷǡۡ͡պѧо100083
ο
1ܲ. ADAԭ. : ܲ. ߺͻ. : ҵѧ磬1985, 117129
(Zhou Bosheng. A deadlock detecting theory of ADA program. In: Zhou Bosheng ed. Computer Software Developing Methods, Tools, and Environment(in Chinese). Xi'an: Northwest Industry University Press, 1985, 117129)
2Cheng Jingde. A survey of tasking deadlock detection methods. ACM Ada Letters, 1991, 11(1): 8291
3ANSI/MIL-STD-1815A-1983 Reference Manual for the Ada Programming Language. Washington: Ada Joint Program Office, 1983
յڣ1997-11-19
޸ڣ1999-03-08
