ѧ
JOURNAL OF SOFTWARE
1999 19 3  Vol.19 No.3 1999



ֲֶ֧мģ͵о
½㡡ڴ󴨡David L.Shang
ժҪΪֲ֧гƣеĳԾͨṩͬͨŻ֧ĳһ߼мģͣAdaԵϻԼJavaԵ̺߳ͬ.ȻĳԽ֧һָ߼мģ.ܵģ͵;ĳЩӦ˵򵥶ЧʵеΪӶȫõһģ.²ԻƺͿܼ.ͨии߼мģ͵ĹԣµԻ.ԴΪ˲ܵĸʹø߼мģ͵ķ.ǣĳ½߼мģʹзһԿɶпܼ֧ţӶʹڵһֶָ֧߼мģͳΪ.
ؼʡģͣпܣǶ࣬࣬ʽ룬auto.
ͼšTP311
Researches on Object-oriented Frameworks Supporting
Multiple Parallel Computing Models
L Jian1,2 LU Pei1,2 YU Da-chuan1,2
1(State Key Laboratory for Novel Software Technology Nanjing University Nanjing 210093)
2(Institute of Computer Software Nanjing University Nanjing 210093)
David L. Shang
Software Systems Research Laboratory Motorola Inc. USA
Abstract In order to support parallel programming, almost all of the programming languages incorporate a high-level parallel computing model into the language by providing parallelism and synchronization mechanisms, such as Ada's task with rendezvous and Java's thread with synchronized method. Obviously, such a programming language can only support one high-level parallel computing model. Although the approach of one model is simple and fairly effective to some applications, unfortunately the problems in the real world are always too diverse to be solved by using a single parallel computing model. In this paper, a new object-oriented approach to this problem is proposed. After analyzing the high-level parallel models of the various languages, some novel object-oriented language mechanisms are presented. Based on them, the concept of object-oriented parallel framework is proposed and the method for expressing and using the high-level parallel computing models by parallel frameworks is discussed. As a result, the high-level computing models are separated from languages in some sense and more than one framework could be given within a single language. Therefore, using a single language to support the various parallel models turns to be feasible.
Key wordsParallel model, parallel framework, nested class, abstract function class, implicit code, auto mechanism.
ӽϵͳеĲ⿪ʼֱMPPϵͳĳ֣гһֱǼоȵ1,2.ڷֲʽϵͳϵͳʵʱϵͳгƵҪڳֲ֧гǳеҪ֮һ.ֲ֧гƵԣAda833ݣConcurrent PascalActor4ԼµJava5ݵȣ϶ڴͳԵĻϣһЩлԼͬͨŻƣ֧ضĲмģ.Ada83ľлϻƵTaskģ͡Concurrent PascalĻڹ̵ܳProcessģ͡CSPͬͨģͣ6ݺABCL/1ĻڶϢģʽActorģͣ7.
ЩԽоѷ֣ĳһֳԣֻ֧һضĲмģ֧ͣӦģ͵ĲͬͨŻƾͨؼֵʽܵǶ뵽ȥ.ǣ͹еĲ⸴ӶĳһضĲģȻܹЧؽĳһ⣬еĳ.磬ڹĹܳģܽϺõؽϵͳеԴ⣬ҪʵԶ̵̹þԵúѣϢģǡǡ෴.͹ľҪһֲֳֶ֧мģ.
£ʹһЩͲƼģʵҪĵԲֵ֧Ĳģ.ȻģʵǲȻģʹϵͳṹϲ⡢ά.
һֻܵķ.ڶԲģͽоĻϣһЩµԻƣʹЩƲ벢صĵͲϵͳԭɽùؼֱĲģʹӳзò.ˣṩԻƿʹòܵʹúͳйؼֵʹֱͬ.ͬһԿֲֶ֧ͬĲпܣӶʹõһֲֶ֧ģͳΪ.ȶ͵ĲмģͽзȻڱʹøֲģ͵Իƣ˲пܻڱﲢģͣһϸӣͨ˵JavaAda83Ӧģֱͣ˹ϢģͣĲпܣ˵ͬһֲֳ֧ͬĲģǿܵ.
1ģͷ
ͳֵ֧ĲģʹࣺϢ.
ִָеԪöдķʵͬͨ.ģҪУConcurrent Pascal Ļڹ̵ܳProcessģ͡SmalltalkĻPVProcessģͣ8ݺJavaĻڹ̵ܳĶ߳ģ.
ϢݾִָеԪøָϢֶʵͬͨ.ģҪУAda83ľлϻƵTaskģ͡CSPͬͨģͺABCL/1ʹöͨģʽĻActorģ.
ģͽзѷ֣Ҫͨṩؼ֧ĳһضĲмģͣһ벢ִеԪйصĹؼ֣Task, ProcessThreadͨźͬйصĹؼ֣Entry, Synchronized.ҵ2ؼͨڵ1ؼ̻ĵԪʹ.ˣҪڵһֲֶ֧мģͣͱ뽫ӳз.ܷȡڿɷĸؼּ໥Ĺϵ.˼·£
(1) ԽThreadProcessTaskΪ࣬ÿһִеԪһЩǿִеĴ.볣ͬǣڴЩʱϵͳҪһϵеײ㴦ƿԴעᵽԹȵ.ڶйУ乤ʽں.ʱҲҪһϵеײ㴦.Ϊ˿̻ThreadProcessTask࣬˺ĸ.
(2) Javasynchronizedؼ֣Ada83entryacceptcallؽֵȵҪǰһЩͬͨйصĴ룬ǳ֮Ϊʽ롱.磬JavaеĳһִһsynchronizedؼֵĺʱԶһδ룬δöǷsynchronizedڱ߳ãɴ߳ǽȴлǼִȥAda83ִһentryʱaccept͵call񶼱ȵһͬͨŵĴ.ؿ̻δ벢ʹֱ֮۵ʹĹؼ.Ϊˣauto.
(3) ͨؼ֮Ƕ׹ϵ磬Ada83ĳɶTaskɵģÿTaskоǶжentry.ABCL/1ĳɶActorɵģÿActorжscript.Ϊ˷ӳĹϵǶṹ.
(4) ΪܲڹؼֵķʹǶ̻ĲмģͣǶ׼̳л,ǰ׺ʽʹ÷.
2Ի
Գвмģ͵ķڳԻ˼ֶʹòģ֮ЧԻ.
(1) ֮࣬Ϊࣨfunction class.ÿΪʵ.ʵһָռ䣬ȻĹ캯гʼ.ʵĽһ¶һֱڴ洢Уֱʽɾ.ɾǰճ溯ù̻ĳһһýúڴ洢.
ΪǷ֣ʵɶȫԲڳԺõĹ涨.ԱȫԼҪ,дĶ󴴽createͶterminate,Դ岻ͬĶ󴴽.ǰtaskprocessthreadȣ.
(2) ԶǶ.һڲԶһ.AжBǳBΪAǶ࣬AΪB.һCκһǶ࣬Ϊ.
ں࣬еĳԱҲԿǶ׵ĳԱ.ˣогԱ඼ԿǶײε.ǶܹӰϵĽǶȷӳģ͵ϵṹ.ǶṹԱȽϷؿ̻мģйؼ֮໥ϵ.
Ƕײνṹļ̳ͬʱǣ浽Ƕ˫ؼ̳УʹһǶ׽ṹʿӦǶ׽ṹһµؼ̳.Ƕ̳й£ACǶ࣬C̳DA̳BBΪһ࣬DǶ.ͼ1ʾ.

ͼ1Ƕ׽ṹļ̳ʾͼ
(3) auto.һĹ캯˵ΪautoģֱĹ캯ִ֮ǰһҪִиĹ캯ֱִ֮һҪִи.жһ̳йϵʱɴƣݹִеauto.
autoƵĻ֮ϣۺļ̳.ȣǶ塰ࡱabstract function class),ָǲܽʵֱӵãĺֻ̳࣬.û壬ֻй캯enter( )exit( )Ǳ뱻Ϊauto.auto壬һF1Ļǳģ̳һF2ָںF1֮ǰȵF2Ĺ캯enter( )ںF1֮󣬱F2exit( ).
(4) ؼ໯.봫ͳе벢лصĹؼͨʽ.ɱΪؼ.
Task,process,threadִеԪĹؼ֣ͨǰĸıĶ󴴽̵ķǷװ.
ͬصĹؼ֣synchronizedȣԽǷװΪ.磬ǽJavasynchronizedؼ໯ΪSynchronized_functionʽװĹ캯˵Ϊautoģ.ǽҪִеĺ˵ΪSynchronized_function.ÿǵʱͻԶִSynchronized_functionжʽ룬ﵽִеĿģϸ4ڵӣ.
ؼ໯ƵʵʾǣԹؼʽǶ봫ͳеĲлƣġɷʽԷװ.
ʵϣǿԽͳؼֵʹú͹ؼļ̳ʹ﷨ʽϵͬʹȻƹؼֵķʽʹǽؼַװɵ.磬task tڴͳùؼtasktһɲе.ǵĹؼ໯˼£ǡttaskһࡱt̳taskһ﷨дͬڡt is task t inherit task.
3п
ԻƣǾͿԱȽϷʹøֲģ.ʹͨĲпʵֵ.ܼǵǰоȵ9,10ݣڡܡһ,Ŀǰûͳһȷʶ.ָĲпܣΪĳֲģͶϵһһ࣬Щкзӳģ͵ĲеλɺͬͨŵĻ.
пܵȻҪ漰һЩϵͳײصĲԣ۽ṹþǰǶȻƵкĵʽȲϵͳṩĵײԭӲʵ.ؼ໯пܵĺ֮ڣԭǶеĲлơȡʽԷװ.һֲģ͵ȫزлƶӦð䲢пУһģͲȫһ.
пܵʹҪͨǰǶ̳ʵ.̳ͨпе࣬ûԾвпе벢صʣ磬̳һ߳ͿԵõһɲִе̣߳ԼʹÿеͬͨŻƣʽ룩.һ򵥵Ķ߳Ŀܼ̳ʹͼ2ʾ.

ͼ2̳ͨʹòпܵʾͼ
ͨ벢пܣǳɹؽԺͲģͷ뿪.һԣֻҪǰ۵ԻƣκβлƣֻҪϵͳͲӳɲͬģ͵ĲпܣͨʹЩиֲͬĲгƣӶﵽͬһֲ֧ͬģ͵Ŀ.
ںܶಢģ൱ӣпܱĿͲһ򵥵ĹԣпܵĳȫԴӴͳĳзǳ֮Ϊơģơ.ӦõĲгƿԴӷصͬϸнѳֱÿܳԱṩĸ߲㲢пɿԺáṹάĲϵͳ,ͼ3ʾ.пܿԹһܿ⣬Ե֧ſά.

ͼ3пʹʾͼ
4һ򵥵
ͨһ򵥵˵˼.ӻǰԻƣͨһпּ֧˵JavaĶ߳ģ.ΪĶܵĺ۽ṹC++αдһЩĵײ.
˵JavaԶ߳ģֻṩ߳ࡢ෽Synchronizedؼ˵Ͳκβwait( )notify( )ֻάһȴУ京嶼Javaͬ.ʵҲһ򵥵Monitorģͣ11.ϵͳײṩPVPVʵֹSynchronizedؼֵȫʽ.
ǵĲпȫһMulti_threadУǶֲִ֧еԪThread֧ͬƵSynchronized_class.£
class Multi_thread{
class Thread{
terminate( ){  ı
...  terminating, releasing occupied resource
...  Notify Multi_threadself to kill the thread
}
meta create( encloser: Multi_thread){  ı󴴽
...  Create a thread according to code in self. Run()
...  Pushing the thread object into the stack
...  Pushing arguments into the stack
...  Get the entry point of selfclass
...  Set the teminating address
...  Notify encloser to register/schedule the thread
}
virtual void Run( ); 
}  End of class Thread
class Synchronized_class{
Semaphone mutex, condsem, urgent;  Semaphoneϵͳṩԭ
int wcount, urgentcount, condcount ;  3
wait( ){  ʹõĺ
condcount=condcount+1;
if (urgentcount>0) V(urgent); else V (mutex);
P(condsem);
condcount=condcount+1;
}
notify( ){  ʹõĺ
urgentcount=urgentcount+1;
if (condcount>0) {V(condsem); P(urgent)}
urgentcount=urgentcount-1;
}
abstract_function_class Synchronized{ Synchronizedؼ໯Ϊһ
auto enter( ){P(mutex)}  캯˵Ϊauto
auto exit( ){  ˵Ϊauto
if (urgentcount>0) V(urgent); else V(mutex)
}
}  End of class Synchronized
}  End of class Synchronized_class
}  End of class Multi_thread
ͨд󴴽terminate( )create( )ʵThreadࣻͨPVʵʽ룬ʵSynchronizedԼSynchronized_classࣻMulti_thread.ʹʱֱӼ̳Multi_ThreadûĶ߳ӦãУThreadеRun( )û߳ࣨΪJavaṩģ͵ļ򻯣ֻҪһ߳ĶһɣִУ̳Synchronized_classǶSynchronizedҪͬƵĶ.
һ̺̹߳߳һеĶ̵߳ĲӦ.
Multi_thread Producer_and_Consumer{ Producer_and_ConsumerMulti_thread
SharedQueue sq;  ʹúSharedQueue, SharedQueueĶ.
Thread producer(speed: integer){
Run( ){ ...; sq.Push(random_integer); ...  Ըٶspeed빲sq.}
}
Thread consumer(speed: integer){
Run( ){ ...; sq.Pop( ); ...  Ըٶspeedӹsqȡ.}
}
Synchronized_class SharedQueue{ SharedQueueSynchronized_class.
Element* Head=NULL, Tail=NULL; еͷָβָ.
Synchronized Push(int aValue) { PushǳSynchronizedһ.
Element* tmpNode;
tmpNode=new Elment; tmpNode.value=aValue;
if(Head==NULL) Head=tmpNode; else Tail.next=tmpNode;
tmpNode.next=NULL; Tail=tmpNode;
notify( );
}
Synchronized int Pop( ){ PushǳSynchronizedһ.
int TmpValue; 
if (Tail==NULL) wait( );
TmpValue=Head.value;
Head=Head.next;
 ˴ʡȥͷHeadָָռĲϵͳ֧Զռ.
return TmpValue;
}
} end of SharedQueue.
} end of Producer_and_Consumer.
Producer_and_Consumer pc_test;
pc_test.producer(5);  ɵ1Producer̲߳,ٶ5󵽹ȥ
pc_test.consumer(10);  ɵ2Consumer̲߳,ٶ10ӹȡ
pc_test.producer(8);  ɵ2Producer̲߳,ٶ8󵽹ȥ
һӴʽThreadSynchronized_classSynchronizedproducer/consumerShardQueuePush/PopĴͳĹؼ֣ʵϷֱproducer/consumerSharedQueueͺPush/Popĸ.̳ͨУproducer/consumerǿɲִе̣߳ǹShardQueueĶsqдͬصźͼͬʱڱproducer/consumer̵߳õĺPush/Pop̳˳Synchronizedڿʼ֮ǰԶSynchronizedеauto캯enter( );ڵǽ֮󣬾ԶSynchronizedеautoexit( );ңPush/PopпֱʹSynchronized_classжwait( )notify( )SharedQueueеıждﵽͬЧ.һϵڲʵֶû˵͸ģûȻһڴͳĹؼֵķʽʹòпṩĲлƺͬ.
5
ĵҪڣԻƣòпܼԭǶĳһеĲмģʹзӶʹͬһֲֶ֧ģͳΪ.ĵ˼·عһ£ѷ֣ģ͵ĻƴгȡԿܵʽһ뷨ڲмͬڷֲʽʵʱ.
ܼоĿǰоȵ.ӷӳ߲ģһǶȶԿܽеֻ̽Ϊ.ڼӦõԽԽ㣬ĸ߲ģҲԽԽḻֲָ̽ͬܵʹЩܵԻǺбҪ.ܴǿһĳһнֲͬ.
оɹڻTransframeԵMagicFrame֮.MagicFrameǺMotorola˾оĿ,ҪĿ֮һԿֶ֧ܵس.
ĵĹֻһ.ڶԲпַ֧ܵ棬ֻ˺ΪࡢǶ̳Сؼ໯autoƵԻ.ڲмģ͸ӶҪǿĻֲ֧пܵʹ.һĹǣ(1) ӸķΧֲͬĲģͣӶЧԻƣ(2) ʵֵĽǶʵһЩ͵Ĳģ͵Ŀܣ(3) й1214ݵĻϣۻڲпܵԼʽ.
оõʵǼƻĿ𡢹ҽܳѧMotorolaĿ.1960ʿڣʿʦҪоΪԶ뻷гʽ.½㣬1974˶ʿҪоΪ뻷гʽ.ڴ󴨣1977˶ʿҪоΪ뻷гʽ.David L. Shang1958ʿҪоΪ뻷.
ͨѶϵ:Ͼ210093,Ͼѧ¼صʵ
ߵλ ½ ڴ󴨣Ͼѧ¼صʵҡϾ210093
 ½ ڴ󴨣ϾѧоϾ210093
David L. Shang:Motorola˾ϵͳоʵҡ
ο
1Snow C R. Concurrent Programming. Cambridge: Cambridge University Press, 1992
2Andrews Gregory R, Schneider Fred B. Concepts and notations for concurrent programming. Computing Surveys, 1983,15(1):343
3Stratford-Collins M J. ADA: A Programmer's Conversion Course. New York: John Wiley and Sons, Inc., 1982
4Beaudouin-Lafon Michel. Object-oriented Languages: Basic Principles and Programming Techniques. London: Chapman & Hall, 1994
5Arnold Ken, Gosling James. The Java Programming Language. Reading, Massachusetts: Addison-Wesley Publishing Company, 1996
6Hoare C A R. Communicating Sequential Process. Englewood Cliffs, NJ: Prentice Hall, 1985
7Yonezawa A, Briot J-P, Shibayama E. Object-oriented concurrent programming in ABCL/1. In: Norman Meyrowitz ed. Proceedings of ACM SIGPLAN Conference'86 on Object-oriented Programming Systems, Languages and Applications (OOPSLA'86). New York: ACM Press, 1986. 252268
8Goldberg Adele, Robson David. Smalltalk-80: The Language and Its Implementation. Reading, Massachusetts: Addison-Wesley Publishing Company, 1983
9Johnson Ralph E. Documenting frameworks using patterns. In: Andreas Paepcke ed. Proceedings of ACM SIGPLAN Conference'92 on Object-oriented Programming Systems, Languages and Applications (OOPLSA'92). New York: ACM Press, 1992. 6376
10Nierstrasz Oscar, Tsichritzis Dennis. Object-oriented Software Composition. Englewood Cliffs, NJ: Prentice Hall, 1995
11Hoare C A R. Monitors: an operating system structuring conception. Communications of ACM, 1974,17(10):549557
12L Jian. Introducing data decomposition into VDM for tractable development of programs. ACM Sigplan Notices, 1995,30(2):4146
13L Jian. Developing parallel object-oriented programs in the framework of VDM. In: McGregor J D ed. Annals of Software EngineeringSpecial Volume Object-oriented Software Engineering: Foundations and Techniques. Amsterdam: Baltzer Science Publishers, 1996. 199211
14L Jian. Sound and complete rules for data reification. Science in China (Series E), 1997,40(4):379386
1998-03-30ո壩
