Home

Rapid Prototyping of High-Performance Concurrent Java Applications

Contents

1. Figure 5 5 The SimResults Window Client Proxy Server model results 51 correctly or not and to see whether the PEPA2Java results are similar to the PEPA Workbench results Chapter 6 Implementation of the Translator This chapter starts by describing how the Translator works and concludes with how to go about using it 6 1 Overview of the Translation Process Figure 6 1 shows the four steps involved in translating aPEPA model into its PEPA2Java equivalent For the lexing and parsing stages it was possible to build upon previous PEPA related work and also make use of standard lexer and parser generators The latter stages analysing the parser output and extracting the necessary information to build the data structures for the final Java code output were the most challenging part of creating the Translator Creation of Data Structures Figure 6 1 The Translation Process 52 Chapter 6 Implementation of the Translator 53 6 2 The Translator Grammar The PEPA grammar that the Workbench accepts in EBNF notation Gilmore 2001 is given in figure 6 2 This same grammar is used in the Translator s parser However the Workbench does not accept the full grammar and neither does the Translator Rather it accepts a subset of the grammar known as guarded PEPA Specifically e As justified in section 3 1 3 there is no provision for Hiding in PEPA2Java e The composition line may contain only Cooperation con
2. The second is the more elegant of the two solutions Alternative Distributions The Java CUP grammar already specifies a syntax for creating Rates with either Uni form or Normal distribution This part of the grammar is commented out for the PEPA Chapter 7 Evaluation 83 workbench however presumably because these distributions lack the properties al lowing memoryless analysis where resumed and restarted activities may be treated in the same fashion However should these distributions be required modification of the PEPA2Java system would be simple The package containing the ExponentialDistribution class Siegrist and Duehring 2001 also contains Uniform and NormalDistribution classes that may be created and used in exactly the same way because they share a common parent which defines the sample methods etc Therefore it would only be a matter of plugging them in to the Rate class and would require a minimum of further alteration Supplying Action Scripts It should be possible to pass an object that implements Runnable to an Action object in the same way that can be done with Thread objects This would define the Action s behaviour in the actual implementation over riding the default sleep behaviour when run Avoiding the Creation of extra Rate Objects Currently the Translator equates the PEPA phrase a 1 0 with the PEPA2Java equivalent a Activ joinAt new Rate 1 0 This means a new object is created ea
3. Choosing To draw at tention to the active elements Components that have joined an action are highlighted The second table displays information on the Activities in the system giving their state their currently assigned Rate their type shared or individual and the number of times they have run Activities which are in the state Joined those that have been selected as Runners are highlighted The bottom table displays information on the Actions in the system again giving their state but also their determining Rate the state of their synchronization tree and the number of times they have been run The full synchronization tree is given and those nodes which are ready or locked are marked with an asterisk The two most common states for an Action are Waiting on Synch and Started Those Actions which have been started are highlighted 5 11 2 2 The Message Window In the middle portion of the SimWindow lies the message window Here all system and object debug messages are displayed along with the name and type of the ob ject from which the message originates By default only system status messages are displayed but the level of detail can be modified below in the control panel to the point where a great deal of information can be discovered on exactly what is happen ing not only in the PEPA model but also what the API s methods are doing below the surface Set to the least discriminating level for example lock
4. 6 5 2 Creating Components and Scripts Apart from generating the synchronization set trees the composition line is also used to create the Components of the system Each Component identifier found in the com Chapter 6 Implementation of the Translator 60 position line will be made into a running instance of a Component extending class There may be multiple instances of a single class as is the case in this composition line from the model example given before Client Client lt serve gt Server In this example the multiple instances of Client will be given names such as client i0 Comp and client i1 Comp and will be of the Client Comp class For the initial behaviour of the Components equality of identifier is searched for between the Component definition in the composition line and the sequential process definitions When the sequential process definitions are turned into CompScript ob jects the setStartScript method is used to set the reference to the initial script that Component should execute The parser returns a tree made of ProcObj objects for each sequential definition Turning the tree into an actions method of a CompScript object is difficult especially as correct nesting is important not only for proper execution but also for comprehen sibility Good tabbing e g indentation of nested blocks is also equally important for comprehension by the user First the Component s behaviour trees are traversed to gather a lis
5. Activities a i0 Comp a 1 143 sleepTime 2037 121 secs 100 0 Runs 2181 AVG 0 9340307 secs run test6 pepa KKRKK KK KK KK KK KK KK KK KK KK KK KK KK KK Axex SIM RESULTS eeeeee rk GenSkel test6 Total sleeptime 719 956 seconds Actions a sleepTime 503 17 secs 69 8889932 Runs 202 AVG 2 4909406 secs run Indiv Activities a i0 Comp b 3 0 sleepTime 131 189 secs 18 221808 Runs 201 AVG 0 6526816 secs run b i0 Comp c 4 0 sleepTime 85 597 secs 11 8891988 Runs 201 AVG 0 4258557 secs run test8 pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkik Kxkkxkkkk SIM RESULTS eeeeee RR GenSkel test8 Total sleeptime 661 429 seconds Actions reglockll sleepTime 10 939 secs 1 6538434 Runs 44 AVG 0 2486136 secs run writelockll sleepTime 10 585 secs 1 6003229 Runs 44 AVG 0 2405682 secs run Indiv Activities txncl i0 Comp thinkl tl sleepTime 540 541 secs 81 7232084 Runs 54 AVG 10 0100185 secs run txncl i0 Comp fork wlxrll sleepTime 43 172 secs 6 52708 Runs 113 AVG 0 3820531 secs run txncl i0 Comp finish allxonemg sleepTime 21 696 secs 3 2801707 Runs 113 AVG 0 192 secs run txncl i0 Comp reglocklr rllr sleepTime 17 11 secs 2 5868234 Runs 69 AVG 0 247971 secs run Appendix F Model Evaluation Results txncl i0 Comp readlock rl testll pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkk KKKKKKKKK SIM RESULTS KKKKKKKK KKKK KK KK KK KK KK KK KKK KKK KK KK KK KK GenSkel testll
6. Translation Process sz fou drug ae a The Java PEPA Workbench s PEPA Grammar The data structure created from A lt m gt B lt n gt C Action M s Unpruned Synchronization Tree for A m B n C Action M s Pruned Synchronization Tree for A m B n C 59 CompScript generated from A m 1 0 A n 2 0 A 0 3 0 x 0 5 A 4 OSANE a ee p 08 co ty up e The PEPA2Java Translator Dialog Window viii 62 List of Tables 2 1 ASCII equivalents of PEPA constructs 7 Comparing the Workbench s steady state and simulation results 7 2 Runs per Action as percentage of all Runs Chapter 1 Introduction 1 1 Principal Goal The design and implementation of distributed and concurrent systems has proved prob lematical as the interaction of multiple executing processes can lead to unexpected and unwanted behaviour such as deadlock live lock and starvation Creation of these sys tems is a far more error prone process than the creation of sequential systems The objective of this project is to develop a methodology and supporting tools that auto mate much of the process in order to remove some of the pitfalls associated with the design of higher performance concurrent and distributed systems One common technique is to use modelling languages to aid the design process as they allow a particular design to be tested and refined so as to deliver maximum performance whilst eliminating dange
7. import prototypeA Appendix B Prototype A Example the Client Proxy Server System 93 cp Title Client Proxy Server Prototype 2 lt p gt lt p gt Description lt p gt lt p gt Copyright Copyright c 2002 lt p gt lt p gt Company Edinburgh University lt p gt author K J R Powell version 1 0 public class Sim extends Simulator public static final double rP 1 rS 1 Server server Proxy proxy Client client public Sim int debugLevel super Client Proxy Server System debugLevel public void createComponents new Client new Proxy new Server public void createActivities new Activity proxyRequest Sim rP new Activity proxyReply Sim rP Appendix B Prototype A Example the Client Proxy Server System 94 new Activity serverReguest Sim rS new Activity serverReply Sim rS public static void main String args Sim sim new Sim Simulator DEBUG ALL Sim siml new Sim 30 5 Appendix C Prototype B Example the Client Proxy Server System DRE RR a s s s ohe s s ok oko k k k k k he dk k k k k k k ske ske sk sk ske ohe sk skoke ok ok REESE SERERE Client Comp java 2k ie ok skoke ske skok DRE AR o s s s s s 2 2 ok oko se ne k k k he k k k k k k k k k lc package CPS import pepa Pepa2Java Simulator Skeleton generated by Pepa2Java Translator v 0 1 Built 29 August 2002 12 00 18 CEST Source home
8. model the result will maintain the performance and behavioural characteristics of the model providing a sound framework for completing the concurrent application Not only do these tools ensure the system characterisics remain true to the high level model they remove uncertainty and the potential of introducing human error whilst also greatly speeding the process of prototyping and implementation Appendix A The Client Proxy Server PEPA Model Note that all the working models used in this paper have been added to the models directory and may be recognized by their p2 j_ prefix a 1 0 b 2 0 c 3 0 Client cReg a cRep T Client Proxy cReq T Proxy Proxy cRep b Proxy pReq a pRep T cRep b Proxy Server pReq T pRep c Server Client cReq cRep gt Proxy pReq pRep gt Server 87 Appendix B Prototype A Example the Client Proxy Server System FRR ok s s s ohe ohe ohe s ok ok k k k k k he he k k k ohe fette fB Chent java nee FRR o s s s ok 2 2 s ok ok k k k k k he he k k k k k k ske ohe ske ohe ohe ohe ohe ohe package csp import prototypeA cp Title Client Proxy Server Prototype 2 lt p gt lt p gt Description lt p gt lt p gt Copyright Copyright c 2002 lt p gt lt p gt Company Edinburgh University lt p gt author K J R Powell version 1 0 88 Appendix B Prototype A Example the Client Proxy Server
9. p_i0_Comp write n sleepTime 38 78 secs 22 6954837 0 AVG 0 4308889 secs run p_il_Comp read m sleepTime 44 374 secs 25 9692985 01 AVG 0 4393465 secs run II G t3 un F o X Runs p il Comp write n sleepTime 40 285 secs 23 5762651 01 AVG 0 3988614 secs run N F Runs We can see from the results how much of the total Action running time this partic ular Action accounted for how many times it ran and the average duration of the runs For example we can see that the second instance of P p il Comp running Action write accounted for approximately 23 58 of the total running time It does not give information regarding which Activity the other Component p i1 Comp was running at the same time Providing the same complete state analysis that the Workbench provides would be useful and is therefore a suggested extension to the Simulator package section 7 5 There is an alternative to using the steady state results of the PEPA Workbench The Workbench s simulation menu allows a model to be run as a simulation using Edinburgh s SimJava package The results from the simulation include a summary of how many times each Action ran So although it is not possible to quantitatively test whether the PEPA2Java model is behaving as the steady state solution predicts the model should it is possible to test whether the PEPA2Java system runs as the Workbench simulation does However this may not be
10. 2 3204837 secs run dBelt 1 i0 Comp D sensor Off D B sleepTime 347 618 secs 5 1568546 Runs 152 AVG 2 2869605 secs run crane i0 Comp mag u C V sleepTime 603 12 secs 8 9471838 Runs 305 AVG 1 9774426 secs run crane i0 Comp over belt2 C H sleepTime 305 073 secs 4 5257067 Runs 153 AVG 1 9939412 secs run crane i0 Comp mag d C V sleepTime 537 962 secs 7 9805759 Runs 304 AVG 1 7696118 secs run crane i0 Comp over beltl C H sleepTime 246 025 secs 3 6497395 Runs 152 AVG 1 6185855 secs run Appendix F Model Evaluation Results 117 crane i0 Comp can accept xi sleepTime 44 071 secs 0 6537859 Runs 152 AVG 0 2899408 secs run test pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkik A SIM RESULTS kk VKR A kok kok kok III IO IO IO K K GenSkel test Total sleeptime 652 918 seconds Actions a sleepTime 261 614 secs 40 0684313 Runs 114 AVG 2 2948596 secs run Indiv Activities a_i0_Comp b a2 sleepTime 120 681 secs 18 4833318 Runs 114 AVG 1 0586053 secs run a_i0_Comp c a4 sleepTime 61 918 secs 9 4832736 Runs 114 AVG 0 5431404 secs run b i0 Comp f al sleepTime 108 981 secs 16 6913763 Runs 60 AVG 1 81635 secs run b i0 Comp g al sleepTime 99 724 secs 15 2735872 Runs 54 AVG 1 8467407 secs run testl pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkik kkkkkkk SIM RESULTS eeeeeec KRK kk kk kk dele kok K K K K GenSkel testl Total sl
11. 2 Determining Rates in choice In choice constructs the participating components have not been set yet therefore the determining Rate is not yet known In this case the determining Rate is retrieved by the getRate myPath method This method returns the determining Rate of the Com ponents included in the synchronization tree containing all the required participants of the subset which includes the Activity the choice method is currently considering For example in the three client one server model a call to getRate pathToClientl would return the slower of the two Rates of Client1 s serve Activity and Server s serve Activity but would not consider the serve Activities Rates for Client2 or Client3 Chapter 5 Prototype B Specification amp Implementation ofthe PEPA2Java API 47 5 11 The Simulator Package Extensions All the details given so far describe the working of both the Barebones and the Simula tor implementations However the Simulator implementation has added functionality in the form of debugging output and the SimWindow These extra functions are embedded into the source code of the Barebones im plementation but are marked by special comment tags These tags allows the extra commands to be commented out automatically with a simple script These tagged commands call the methods of the SimWindow and Debug class to do things like no tify the SimWindow of state changes to each individual PEPA object or send debug m
12. 2 Specified Objects and Methods The final API defines Component and Action objects Inheritance is used to extend these objects and make use of their methods to will provide PEPA like functionality Components also contain nested classes called Scripts which define their behaviour Each Component is run as a separate Java Thread in the system executing its scripts Each script returns a reference to the next script which should be run In addition a Rate class and Activity class are defined The Rate class provides methods for accessing an exponentially distributed random number generator The Activity class provides methods for a Component to interface with global and individual Actions also defined as separated executing Threads Finally a PepaSystem class is defined that creates the Components and their Scripts the Actions and their synchronisation sets initialises all these objects and starts the Chapter 3 Design 13 whole system running 3 3 The Barebones and the Simulator Packages These two packages are the concurrent system implementations of the PEPA2Java API Their functionality and their code is for the most part identical except that the Sim ulator package includes as the name suggests the ability to display the state of the system This is useful for debugging purposes and discovering what is happening in the system In order to keep the two packages working identically they are generated from the same source code e
13. API 43 5 9 1 Registering Interest The first phase is a registering of interest in all the Activities which could possibly be chosen i e all those in the array This involves setting the ready flag on the Activity to true indicating to other Components that this Activity may by chosen These other Components evaluating choices of their own make use of this when deciding which of their branches may run This way two or more simultaneously executing choice methods may choose branches where there is not yet a fully ready cooperation set i e not all Activities in the set are committed to the Action Without some ready but not locked provision there would be starvation for some branches For example consider the example A m T A n T A m 1 0 B i 1 B C n 1 0 C C lt n gt A lt m gt B After registering interest in the set of Activities this Component pauses for choice pause a constant set in the Component class Any other choice methods that had previously yielded may discover that there are now additional Activities that may po tentially run that will complete the set of an Action they themselves are considering choosing They may then choose a branch that was previously believed to be unready for running Without the choice pause and some provision for discovering potential choices B would always choose individual Activity i and A would always cooperate with C on n This is incorrect behavio
14. AVG 0 2442982 secs run Runs 285 AVG 0 257386 secs run Runs 21 AVG 42 264619 secs run Runs 104 AVG 0 9052404 secs run Runs 104 AVG 0 2015481 secs run Runs 78 AVG 0 2288205 secs run Runs 78 AVG 0 2386538 secs run Runs 112 AVG 0 2605357 secs run Runs 112 AVG 0 2607946 secs run Runs 217 AVG 0 2443134 secs run Runs 217 AVG 0 2382488 secs run 63 AVG 0 236254 secs run 63 AVG 0 2636984 secs run Runs 65 AVG 10 4091385 secs run Runs 112 AVG 0 4370446 secs run Runs 112 AVG 0 2017946 secs run 80 AVG 3 4036625 secs run Runs 217 AVG 1 6022765 secs run Runs 217 AVG 0 2031475 secs run 9 AVG 64 5136667 secs run 63 AVG 3 1690476 secs run 63 AVG 0 2049841 secs run Runs Runs Runs Runs Runs 53 AVG 0 2241887 secs run Runs 53 AVG 0 2513019 secs run Runs 23 AVG 0 2024783 secs run Runs 23 AVG 0 3706087 secs run Runs 30 AVG 0 2737 secs run Appendix F Model Evaluation Results 113 writelock21 sleepTime 6 898 secs 0 4115892 Runs 30 AVG 0 2299333 secs run reglock22 sleepTime 6 437 secs 0 3840823 Runs 29 AVG 0 2219655 secs run writelock22 sleepTime 8 242 secs 0 4917828 Runs 29 AVG 0 2842069 secs run Indiv Activities txncl i0 Comp thinkl tl sleepTime 671 494 secs 40 0666371 Runs 69 AVG 9 7317971 secs run txncl i0 Comp fork wlxrrl sleepTime 74 486 secs 4 4444232 Runs 168 AVG 0 443369 secs run txncl i0 Comp finish alrxonemg sleepTime 31
15. Comp fork wlxrll sleepTime txncl i0 Comp finish allxonemq txncl i0 Comp reglocklr rllr SleepTime SleepTime 45 6028321 54 3971679 0 3104921 0 1471831 0 1192314 0 1092535 0 1838025 0 2175662 0 2767956 5 0 1828954 5 0 1589416 5 0 0690729 5 0836535 5 0 0965207 5 0 0806634 5 0 0545931 0 0720629 5 sleepTime 822 015 secs 72 565 secs sleepTime 27 5 secs sleepTime 18 025 secs 111 187 686 secs 177 873 secs 19 875612 5 18 8364328 5 Runs 11 AVG 17 0623636 secs run Runs 13 AVG 13 6825385 secs run 881 secs 0 7286856 Runs 8 AVG 0 860125 secs run 653 secs 0 1750497 Runs 3 AVG 0 551 secs run 798 secs 0 5080996 Runs 10 AVG 0 4798 secs run 15 secs 0 4394776 Runs 12 AVG 0 3458333 secs run 829 AVG 0 8347431 secs run 828 AVG 0 9969227 secs run Runs Runs 384974 Runs 45 AVG 0 2546444 secs run Runs 44 AVG 0 2100455 secs run Runs 19 AVG 0 2305789 secs run Runs 19 AVG 0 1867895 secs run Runs 16 AVG 0 20325 secs run Runs 16 AVG 0 3419375 secs run Runs 39 AVG 0 2823333 secs run Runs 39 AVG 0 1660513 secs run Runs 37 AVG 0 2226757 secs run 0 4043923 Runs 37 AVG 0 3253243 secs run Runs 19 AVG 0 2865263 secs run Runs 19 AVG 0 249 secs run Runs 8 AVG 0 257 secs run Runs 8 AVG 0 31125 secs run Runs 9 AVG 0 3192222 secs run 9 AVG 0 2667778 secs run Runs 9 AVG 0 1805
16. Components come together at one choice at the same time deadlock may result The conditions leading to this are quite complicated but once understood the problem is clear The choice method utilises locking of Actions when evaluating branches to avoid the deadlock Consider the example HA m 1 0 A n 1 0 A B m infty B n infty B A m n B Without locking both A and B could register interest in both Actions m and 66 99 n at the same time Without locking both would believe m and n ready A might choose m and B might choose n resulting in deadlock Instead A will lock the two Actions and commit to one then withdrawing its ready flag from the other before unlocking B would then receive the locks but see only one of the Actions as ready and therefore choose the same one as A avoiding deadlock The problem with the Big model is that there are parts of the model where three Components come together in a choice block The participation of one the Node Chapter 7 Evaluation 80 Component is required by both of the other Components the Bidder Components However the Action is exclusive only one of the two Bidder Components may join Occasionally all three Components arive at the choice almost simultaneously They register their readiness to choose between the multiple branches
17. Java skeleton of a model runs as the PEPA model dictates it should However there is no native support for the concept of synchronising multiple threads of execu tion for cooperation on an action Therefore much of the challenge lies in getting Java to behave in this way The Action class specified in section 5 6 ensures the proper synchronisation of multiple threads on cooperating sections To accomplish this the Action class and also the Component class make use of two simple concurrency con trol helper classes see section 3 3 2 the Lock class and the Waiter class The Waiter class is a very simple extension to java lang Object It uses the ob ject monitor each Java object has and provides wrapper methods w and n around its wait and notifyAll methods These wrapper methods are synchronised because the caller must own the object monitor before it can call wait or notifyAll In addition it catches any thrown InterruptedException and exits the method performing no further action The Waiter class exists to avoid any user defined extending subclass inadvertently locking or releasing the object monitor and interfering with the function ing of the PEPA2Java implementation It also allows as many Waiter objects to be created as needed and allows these objects to be private to an object or shared within Chapter 5 Prototype B Specification amp Implementation ofthe PEPA2Java API 31 the package as a protected object These objects are u
18. Runs Runs 306 AVG 0 3479118 34 AVG 1 3756765 17 AVG 2 2082941 secs run secs run 18 AVG 1 5014444 secs run 7 AVG 2 197 secs run 62 AVG 2 4470484 secs run secs run secs run secs run secs run Runs 219 AVG 0 4768721 secs run secs run Runs 306 AVG 0 2818137 secs run 108 Appendix F Model Evaluation Results 109 c sleepTime 33 935 secs 28 6979171 Runs 17 AVG 1 9961765 secs run Indiv Activities deadlock pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkik KKKKKKKKK SIM RESULTS KKKKKKKK KK KK KK KK KK KK KK KK KK KK KK KK KK KK KK GenSkel deadlock Total sleeptime 1 771 seconds Actions a sleepTime 0 4 secs 22 5861095 Runs 1 AVG 0 4 secs run b sleepTime 1 371 secs 77 4138905 Runs 2 AVG 0 6855 secs run Indiv Activities kkkkkkkkkkkkkkkkkkkkkkkkak java pepa skipped kkkkkkkkkkkkkkkkkkkkkkkkak maple mod pepa K P added rates all 1 0 as they were referred to but undefined kkkkkkkkkkkkkkkkkkkkkkkkkkkkkk Ae SIM RESULTS FOGG kok kok kok ko kok kok oko k kok GenSkel maple mod Total sleeptime 148 965 seconds Actions a sleepTime 78 08 secs 52 4149968 Runs 44 AVG 1 7745455 secs run b sleepTime 26 949 secs 18 0908267 Runs 22 AVG 1 2249545 secs run c sleepTime 43 936 secs 29 4941765 Runs 21 AVG 2 0921905 secs run Indiv Activities p2j bigchoice pepa rk xe SIM RESULTS eeeeee RR GenSkel p2j_bigchoice Total
19. Runs 498 AVG 0 2304217 secs run Indiv Activities b i0 Comp i 1 0 sleepTime 145 443 secs 42 8611844 Runs 465 AVG 0 3127806 secs run p2j PC LAN4 mod pepa kokokok kok kok I K KK K IO K K kok eek STM RESULTS eeeeeec kokokok kok kok kok IO IO K KK K K K K K GenSkel p2j_PC_LAN4_mod Total sleeptime 944 303 seconds Actions requestl sleepTime 0 717 secs 0 075929 Runs 8 AVG 0 089625 secs run servel sleepTime 15 272 secs 1 6172775 Runs 8 AVG 1 909 secs run walkon2 sleepTime 20 564 secs 2 1776908 Runs 33 AVG 0 6231515 secs run request2 sleepTime 0 355 secs 0 0375939 Runs 3 AVG 0 1183333 secs run serve2 sleepTime 2 374 secs 0 2514024 Runs 3 AVG 0 7913333 secs run walkon3 sleepTime 24 473 secs 2 591647 Runs 38 AVG 0 6440263 secs run request3 sleepTime 3 022 secs 0 3200244 Runs 10 AVG 0 3022 secs run serve3 sleepTime 13 605 secs 1 4407452 Runs 10 AVG 1 3605 secs run walkon4 sleepTime 20 915 secs 2 2148611 Runs 30 AVG 0 6971667 secs run request4 sleepTime 1 943 secs 0 2057602 Runs 12 AVG 0 1619167 secs run served sleepTime 38 393 secs 4 0657501 Runs 12 AVG 3 1994167 secs run walkonl sleepTime 20 094 secs 2 1279187 Runs 28 AVG 0 7176429 secs run Indiv Activities pRl i0 Comp arrive lambda sleepTime 199 215 secs 21 0965125 Runs 9 AVG 22 135 secs run pR2 i0 Comp arrive lambda sleepTime 200 32 secs 21 21353 Runs 4 AVG 50 0
20. Seeing that the Node Component is ready to join either branch Bidderl might commit to the first branch Bidder2 also seeing that Node is prepared to join either branch might then register to join the second branch s Action Say then that the Node Com ponent chooses to participate with Bidder2 on the second branch The Action will run and in this particular model Bidder2 now goes into another part of the model interacting with other Components The Node then continues running before entering a derivative state where it must run again the Action it just ran with Bidder2 this time without a choice The model designer anticipated that Bidderl would still be choosing between the two branches and could then cooperate with Node However in this implementation the Bid derl has already committed to executing the other branch and is stuck there it can t change branches At this point the model s execution ends in deadlock 7 4 3 Fixing the choice method The two problems above can be solved Introducing true race conditions is one way but is undesirable for the reasons given previously To address the first problem there should be a finer prioritizing of branches At the moment after pausing for some time the fastest ready branch wins Instead the model should pause only if there are no shared Action branches ready to go In this case it could pause for a time to allow o
21. Total sleeptime 304 026 seconds Actions reglockll sleepTime 7 82 secs writelockll sleepTime 7 415 secs reglockl2 sleepTime 5 156 secs writelockl2 sleepTime 4 284 secs Indiv Activities txncl i0 Comp thinkl tl txncl i0 Comp fork wlxr12 txncl i0 Comp finish allxq testl2 pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkik KKKKKKKKK SIM RESULTS KKKKKKKK KKKK KK KK KK KKK KKK KK KK KK KK KK KK KK GenSkel test12 Total sleeptime 205 491 seconds Actions reglockll sleepTime 18 661 secs writelockll sleepTime 23 261 secs reglock12 sleepTime 20 171 secs writelockl2 sleepTime 15 362 secs Indiv Activities txnl_i0_Comp fork wlxr12 txnl_i0_Comp finish allxq testl3 pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkik KKKKKKKKK SIM RESULTS KKKKKKKK KKKK KK KK KK KK KK KK KK KK KK KK KK KK KK GenSkel test13 Total sleeptime 87 586 seconds Actions reglockll sleepTime 14 896 secs writelockll sleepTime 19 7 secs reglock12 sleepTime 16 36 secs writelock12 sleepTime 17 533 secs Indiv Activities txnl_i0_Comp finish allxq 2 5721484 1 6959076 sleepTime 17 386 secs 2 4389361 1 40909 5 sleepTime 234 115 secs sleepTime 35 648 secs sleepTime 9 588 secs 9 0811763 11 3197172 Runs 59 AVG 0 3418814 secs run 9 8160017 7 4757532 sleepTime 102 332 secs sleepTime 25 704 secs 17 0072843 22 4921791 18 6787843 20 0180394 sleepTime 19 097
22. actions pre completion which would make the skeleton impossible to flesh out Instead simulating the race condition as is Chapter 3 Design 14 done in these implementations allows some certainty e once committed to an Action a Component will not do anything else until the Action has completed e once started an Action must complete e ifa branch has been chosen the other branches will definitely not be chosen and will therefore not be able to affect the system These certainties are not of value in evaluating a model but they are necessary for creating a full implementation Speculative execution would mean Actions might not complete and this would lead to the system being left in an inconsistent state were it actually performing commands Apart from this point it would mean spawning a new thread for each branch and then culling the losing branching leading to very inefficient runtime characteristics 3 3 2 Concurrency Control In accordance with tried and tested design patterns Lea 1997 concurrency control is separated from the functionality through the creation of separate utility classes This is especially important where inheritance is used the Component objects of the system are extended and these extensions may use the object s synchronising object monitor lock When using inherited methods unexpected behaviour may arise when the dif ferent layers of code lock or wait on the object monitor whilst it
23. as time permits take the project beyond its original scope by considering possible additions and enhancements 6 Documentation write the project report and review complete the commenting of the code In the event difficulties and unforeseen obstacles relating to the implementation resulted in this phase absorbing a disproportionately large amount of the time and 9 Chapter 3 Design 10 effort invested The difficulties encountered are described in the next chapter They arose mainly from the challenge of creating efficient and correct equivalents of PEPA constructs in Java Because this report has been produced at the end of the project this design chapter describes the whole process of ongoing design The design ideas were as much affected by the process of implementation and its changing needs as the implementation was determined by the initial ideas and designs There is no clear split between design and implementation stages so this chapter records some of the ideas i e the concept of Scripts that developed only as implementation progressed The implementation has been carried out in Java and in line with object oriented design the different parts of the implementation were modularised as far as possible Three things have been produced the API section 3 2 the Barebones and Simulator packages implementing the API section 3 3 and the Translator section 3 4 3 1 1 Concurrent and Distributed Systems Practicalities o
24. class is the choice method which 1s detailed in section 5 9 5 6 Actions Each shared Action of the model is represented by an Action object which implements the Runnable interface It also holds the root to a synchronisation tree section 5 8 which is used to determine whether the Action is ready to run or not An Action steps Chapter 5 Prototype B Specification amp Implementation ofthe PEPA2Java API 34 through five stages 1 Wait for noRunners The first command of a running Action object is to hold until all Component members of its synchronisation set have their runner flag set to false This indicates that the Component believes the previous run of the Action to be completed which is a prerequisite of the next run When all Components know that the last run has completed the next step can take place This is necessary because if an Action is very short there is the possibility that in the multi threaded concurrent execution environment one or more of the the last chosen Component threads may not have executed since the last run If the next run were to be allowed to start before all Components were aware that the last had ended deadlock might occur while one of the Components might still be waiting for the already executed Action to run those Components aware that the last Action already ran might be waiting for the next Action to occur Neither Action could then ever execute because neither would have a complete synchr
25. create a full synchronisation set tree and then prune the tree The four steps for generating the full synchronisation tree from the composition line tree are for each Action 1 Set a SharedAction flag to false 2 Start at the top of the composition line tree fig 6 3 3 If the current node is a Cooperation node e If the current Action is in this node s ActionSet return a new AndNode in our synchronisation tree Also set the SharedAction flag to true Chapter 6 Implementation of the Translator 58 Component AndNode OrNode Figure 6 4 Action M s Unpruned Synchronization Tree for A lt m gt B lt n gt C e If the current Action is not in this node s ActionSet return a new OrNode in our synchronization tree e Set the left and right child to be the return result of a recursive descent into those nodes 4 If the current node is a Component identifier return the reference to it For Action m this would return the unpruned tree shown in figure 6 4 The next step is to prune the tree to contain only Components that cooperate on this Action If the SharedAction flag is still set to false this is an individual Action which requires no cooperation the synchronization tree is scrapped Otherwise we set the Action s synchronization tree to be the result of the method unpruned root prune which will return a pruned version of the tree The three steps in the pruning algorithm are 1 Call the contains thisAct
26. first step is to pass the PEPA identifier to the legalize method This method takes as input any string and returns a legal Java identifier by removing illegal characters or replacing them with legal ones If the name cannot be legalized an error is thrown informing the user to modify the identifier in the PEPA input A character that is often seen in PEPA models is denoting derivative behaviours Also some ee 99 of the models include the dash symbol These characters may not be used in Java identifiers or as file directory names for that matter and are therefore replaced by the underscore character The result may be used as both legal Java and file system identifiers In line with common coding practice class identifiers begin with an upper case letter whilst object identifiers begin with a lower case letter Additionally objects and classes are suffixed with an abbreviation indicating their type These suffixes are set as final static strings in the Main class of the Translator Other defaults Appendix D control the name of the PepaSystem extending class the default output directory and the names of the implementing packages The full list of the Translator s default constants is given in Finally because multiple instances of the same Component may exist in a system each Component instance has the infix iX inserted between the identifier and the type suffix where X is incremented for each new instance This
27. following results are taken from translating compiling and running the models in the jpwb2 models directory Badge pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkk KKKKKKKKK SIM RESULTS KKKKKKKK kkkkkkkkkkkkkkkkkkkkkkkkkkkkkk GenSkel badge Total sleeptime 141 798 seconds Actions regl4 sleepTime 10 669 secs 7 5240836 Runs 77 AVG 0 1385584 secs run regl5 sleepTime 17 235 secs 12 1546143 Runs 96 AVG 0 1795312 secs run regl6 sleepTime 8 579 secs 6 0501559 Runs 37 AVG 0 2318649 secs run repl4 sleepTime 6 709 secs 4 7313784 Runs 77 AVG 0 0871299 secs run repl5 sleepTime 7 569 secs 5 337875 Runs 96 AVG 0 0788438 secs run repl6 sleepTime 3 284 secs 2 3159706 Runs 37 AVG 0 0887568 secs run Indiv Activities pl4_i0_Comp movel5 m sleepTime 42 094 secs 29 6858912 Runs 104 AVG 0 40475 secs run pl4_i0_Comp movel4 m sleepTime 24 135 secs 17 0206914 Runs 61 AVG 0 3956557 secs run pl4_i0_Comp movel6 m sleepTime 21 524 secs 15 1793396 Runs 43 AVG 0 5005581 secs run Big pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkk KKKKKKKKK SIM RESULTS KKKKKKKK kkkkkkkkkkkkkkkkkkkkkkkkkkkkkk GenSkel big Total sleeptime 199 154 seconds Actions bid in sleepTime 5 11 secs 2 5658536 Runs 19 AVG 0 2689474 secs run preq in sleepTime 6 965 secs 3 4972936 Runs 22 AVG 0 3165909 secs run forward accept sleepTime 19 142 secs 9 6116573 Runs 13 AVG 1 4724615 secs run 106 Appendix F M
28. given in Appendix A is implemented using the Pro totype A package and executes as desired The Java code given in Appendix B is relatively straightforward the parallels between the PEPA constructs and the Java constructs are clear The PC LAN 4 model has also been manually translated to run the Prototype A package With Prototype A seemingly capable of running models correctly and a few manual translations implemented the API and its implementations were frozen to be gin work on creating an automatic translator Chapter 4 Prototype A Specification amp Implementation of a Flawed API 25 4 3 7 Translator As chapter 6 is dedicated to describing the implementation of the Translator and much of the final Translator is very similar to the first Translator this section will only give a brief overview of the first incarnation The first translator is quite simple in its functioning as the initial API takes a rather rudimentary view of the way PEPA works It parses the various data structures created by the parser but does not need to do a lot of maniplation to create its output For example each definition line in the PEPA model becomes a Component each Compo nent in the composition line has a flag set so that it is started by the Simulator when the system is started and for each Action in the composition line all Components found in the set to the left and right of it call the addMeTo thisActivity method Although the code of the
29. kip PEPA jpwb2 models CPS pepa public class Client Comp extends Component Rate a Rate new Rate a 1 0 Rate TOP_Rate new Rate Activity cReq Activ new SharedActiv Sim cReq Act this Activity cRep Activ new SharedActiv Sim cRep Act this 95 Appendix C Prototype B Example the Client Proxy Server System 96 Client Script client Script new Client Script public Client Comp String name super name public class Client Script implements CompScript public CompScript actions cReq Activ joinAt a_Rate cRep Activ joinAt TOP Rate return client Script JR Ra ok s s s s s s s oko k ok ok k k he k k k k ok k kk k lc REESE ERE EG Proxy_Comp java K k k ske skok RR s s s s ohe ok 2 2 oko he k k k k he k k k k k k lc package CPS import pepa Pepa2Java Simulator Skeleton generated by Pepa2Java Translator v 0 1 Built 29 August 2002 12 00 18 CEST Source home kip PEPA jpwb2 models CPS pepa public class Proxy_Comp extends Component Rate TOP Rate new Rate Rate b Rate new Rate b 2 0 Rate a Rate new Rate a 1 0 Appendix C Prototype B Example the Client Proxy Server System 97 Activity cReq Activ new Shared Activ Sim cReq_ Act this Activity cRep Activ new SharedActiv Sim cRep Act this Activity pReq Activ new SharedActiv Sim pReq Act this Activity pRep Activ new SharedActiv Sim pRep Act this Proxy Script proxy Scr
30. of the Seventh International Conference on Modelling Tech nigues and Tools for Computer Performance Evaluation number 794 in Lecture Notes in Computer Science pages 353 368 Vienna Springer Verlag Gilmore and Hillston 1996 Gilmore S and Hillston J 1996 Refining internal choice in PEPA models pages 49 64 Department of Computer Science The Uni versity of Edinburgh 122 Bibliography 123 Gilmore et al 1996 Gilmore S Hillston J and Holton D 1996 From SPA models to programs pages 179 198 Dipartimento di Informatica Universit di Torino CLUT Hidders 2001 Hidders J 2001 Wikipedia definition Parser http www wikipedia org wiki Parser Hillston 1996 Hillston J 1996 A Compositional Approach to Performance Mod elling Cambridge University Press Hudson 1999 Hudson S E 1999 LALR Parser Generator for Java CUP User s Manual Graphics Visualization and Usability Center Georgia Institue of Technol ogy http www cs princeton edu appel modern java CUP manual html Hunter 1999 Hunter J 1999 Re evaluation of the PEPA Workbench Master s thesis School of Computer Science The University of Edinburgh Lea 1997 Lea D 1997 Concurrent Programming in Java Design Principles and Patterns Addison Wesley Siegrist and Duehring 2001 Siegrist K and Duehring D 2001 The prob ability statistics object library Mathematical distributions java package edu
31. or 6 PCs If the current PC has a network request it participates in the serve Action otherwise it participates in the walkon Action In either case once the Action is complete access to the LAN is passed on to the next PC The model is given as lambda 2 omega 3 mu 1 PC10 PC11 PC20 PC21 PC30 PC31 PC40 PC41 S1 52 53 54 PC10 The first PC starts in state PC10 A race condition between the internal arrive arrive lambda PCll walkon2 infty PC10 servel infty PC10 arrive lambda PC21 walkon3 infty PC20 serve2 infty PC20 arrive lambda PC31 walkon4 infty PC30 serve3 infty PC30 arrive lambda PC41 walkonl infty PC40 serve4 infty PC40 walkon2 omega S2 walkon3 omega S3 walkon4 omega S4 walkonl omega S1 lt gt PC20 lt gt PC30 lt gt PC40 servel mu serve2 mu serve3 mu serve4 mu walkonl walkon2 walkon3 walkon4 lk2 0mega 1k3 omega 1k4 omega Ik1 omega S2 835 S4 SL servel serve2 serve3 serve4 gt Sl Chapter 7 Evaluation 78 Action and the shared walkon2 Action governs which behaviour the PC exhibits The arrive Action is used to model other processes on the PC issuing LAN requests On completion of the arrive Action the Component will take the PC11 derivative behaviour indicating it requires network a
32. pReq Act setSynch SSNode AND Sim proxy 10 Comp pReq Activ Sim server 10 Comp pReq Activ pRep Act setSynch SSNode AND Sim proxy_i0_Comp pRep_ Activ Sim server 10 Comp pRep Activ public void createComps 1 client 10 Comp new Client Comp client 10 Comp client i0 Comp setStartScript client 10 Comp client Script proxy i0 Comp new Proxy Comp proxy i10 Comp proxy i0 Comp setStartScript proxy 10 Comp proxy Script server 10 Comp new Server Comp server 10 Comp server 10 Comp setStartScript server 10 Comp server Script Appendix C Prototype B Example the Client Proxy Server System 101 public static void main String args Sim sim new Sim Appendix D Default Constants Defined in the API impleme Simulat Barebon For model o PepaSys Default Write o Overwri Translator nting packages or package es package utput output path utput to disk te existing files Class and Object identifiers Action suffix Activity suffix Component suffix CompScr Rate su ipt suffix ffix tem extending Class 102 pepa Pepa2Java Simulator pepa Pepa2Java Bare W Sim models p2 jgens true false W Act Activ Co mp W Script Rate Appendix D Default Constants Defined in the Translator 103 Choice Switch block variables For Choice Activity array prefix Choice Rate a
33. requests and releases the status of all Activities in a choice call and the eventual outcome and even Rate comparison messages are available This is useful if the model is behaving incorrectly Chapter 5 Prototype B Specification amp Implementation ofthe PEPA2Java API 50 or unexpectedly 5 11 2 3 The Control Panel The controls available are play and pause for resuming and pausing the running of the simulation and interrupt for prematurely ending long running Actions The in terrupt command will wake any sleeping Thread Because the Thread suspend and Thread resume methods are depracated since the release of JDK 1 3 it is possible that the Simulator package may display warnings on compilation This is because careless use of these methods can lead to deadlock However in this package the use of these methods is the best way to control the simulator s behaviour and is perfectly safe Additionally there are two pull down lists where simulation speed and the level of debug messaging can be specified There are five speeds to choose from which affect the multiplier used to determine the sleep time of Actions as calculated by Rate objects The level of debugging too can be set to five levels of detail ranging from no feedback to very detailed feedback 5 11 3 Simple Analysis Finally when the simulation is halted by closing the window another window fig 5 5 will pop up displaying some basic statistics to allow analysis of the mo
34. scheme ensures that all objects are easily identifiable The suffix clearly identifies the object class regardless of the context in which it is used Most importantly however this scheme also ensures that the unintentional clashing or multiple declaration of identifiers is minimised The package name for the output is derived from the legalized version of the PEPA model s filename Chapter 6 Implementation of the Translator 64 6 7 Using the Translator The Translator can be interfaced via either the command line or via the P2J Dialog window see section 6 7 3 Either of these methods gathers the necessary information to begin translation and spawns a new Translator Due to the use of some static data structures only one Translator can be started at any one time The following informa tion is gathered from user interaction with either the dialog window or the command line invocation and passed to the Translator Filename The path to and the name of the PEPA model file that should be translated The filename is also used to generate the Package name see section 6 6 1 Output Path The path to the directory in which the new model should be created In accordance with Java package naming rules a subdirectory will be created with the name of the package Note that whilst the subdirectory will be created the output path must be an already existing directory Otherwise the translation will fail Output type A flag is passed that i
35. server s request method i e if the proxy can not fulfil the request This choice is determined by a randomly generated number When the proxy does need to call the server s request method the server will reply Finally the proxy passes back the reply to the client completing one loop of the system The method call concept fits very nicely with traditional programming ideas but is quite different from the way a PEPA model functions In a PEPA model each Compo nent is executing separately and shared activities are places in the system where mul tiple threads synchronise on a single action This is also more akin to an actual client server relationship where both computers are executing independently The server is idle until a request comes in It processes the incoming request and then becomes idle again The original concept will work only for those PEPA models which follow the passive active activity cooperation scheme and where one thread of execution is sufficient to capture all system behaviour This is clearly unacceptable 4 3 Prototype A Given these rather severe limitations a new concept sprung to mind The new concept allowed the system to behave much more like a genuine PEPA model and became Prototype A Chapter 4 Prototype A Specification amp Implementation of a Flawed API 20 4 3 1 The Component and Activity Classes Instead of having one thread of execution which moves between Components each Component object shou
36. set overwrite files in the output Chapter 6 Implementation of the Translator 66 directory debug 0 6 set Debug Message level O none 6 all dry Dry run write only to screen simDebug 0 5 Simulation debug level simSpeed 0 4 Sim speed 0 slowest 4 fastest These are used to set the Translator s parameters as described in Section 6 7 Any messages will be printed to the screen 6 7 3 Integration with the PEPA Workbench The P2J Dialog Win dow An easier way to control the Translator is by accessing it through the PEPA Workbench Selecting Translate model from the Pepa2Java will open the PEPA2Java Translator Dialog window as shown in figure 6 7 The Translator Dialog window is passed whichever PEPA model file is currently open in the PEPA Workbench the current file is displayed at the top of the Dialog window The window allows the user to specify the output directory whether to use the Simulator or the Barebones package the initial Simulation speed and Debug level The text area displays any messages from the translation process At the bottom of the screen the user may select to overwrite existing files and to get extra information about the Translation process as it is carried out Finally action is invoked by the two buttons at the bottom of the window Selecting the first will cause the Translator to process the model and output the PEPA2Java equivalent Selecting the second will
37. that the synchronization set has two subsets of cooper ating Runners Both sets include the Server Component and either one or the other of the two Client Components This would yield the synchronization tree specified in figure 5 2 The most im portant function of the synchronization tree is to determine whether the Action may run or not This is checked each time the Action object calls isLocked on the root node of the tree The method is recursively called on the nodes AND nodes return Chapter 5 Prototype B Specification amp Implementation ofthe PEPA2Java API 39 Activit Activit Activit Figure 5 2 A Simple Synchronization Tree Chapter 5 Prototype B Specification amp Implementation ofthe PEPA2Java API 40 true iff both the left and the right child return true whereas OR nodes return true iff either or both of the children return true The tree construct is equivalent to the com position line because the serve action requires the Server Component and either of the two Client Components to cooperate before it can execute Using these trees an arbitrarily complex synchronization set can be represented When the Action runs it calls the setRunners actionThread method on the root of the tree This passes the reference to the running Thread that will execute the Action on which the Runners should call actionThread join N B the naming of the Activity join method is not ideal as it could easily be confused with the T
38. the choice pause and the slower the simulation the less chance there is of all the members of a synchronisation set arriving in time before the choice pause expires to be considered as a ready branch As it is always ready individual Actions have an unfair advantage regardless of the branch rates For example with the model A m infty A n infty A B m 1 0 B i 1 0 B 10 2 no Lye A m n B lt gt C we can see the effects the value of choice pause and the speed of simulation have on defining behaviour by examining table 7 2 The behaviour of the system is variable depending on the values chosen This underlines the difficulties surrounding choice when true race conditions are not used In the example above this implementation s particular method for simulating race conditions means behaviour is not wholly dependent on the model but also on other parameters specifically the value of choice pause This is undesirable but is not fatal except in the case of the two PC LAN models Sim Speed Choice pause Normal 100ms Fastest 500ms Action m 4 268 96 25 369 96 Action n 45 122 96 38 635 96 Action i 50 61 36 074 Table 7 2 Runs per Action as percentage of all Runs Chapter 7 Evaluation The PC LAN models execute incorrectly using PEPA2Java In these models there are 4 or 6 PCs respectively being served by a token ring LAN Access to the LAN is passed around the ring of 4
39. to query the server when it can t fulfil a request itself The ASCII formatted PEPA model is a 1 0 sb 2 0 c 3 0 Client cReq a cRep T Client Proxy cReq T Proxy Proxy cRep b Proxy pReq a pRep T cRep b Proxy Server pReq T pRep c Server Client cReq cRep gt Proxy pReq pRep gt Server This model provides a simple example which nevertheless contains all the PEPA con structs most important to the project Chapter 4 Prototype A Specification amp Implementation of a Flawed API 19 4 2 2 Activities as Method Calls In the Proof of Concept version method calls are used by the passive participant of an activity to call a method of the actively participating Component This works because all shared Actions in the model contain one active and one passive participant This is also the case with most of the example PEPA models distributed with the PEPA Workbench Using method calls each request has an implicit reply so the request and reply Activities can be merged Each passive participant needs a reference to the active participant so it can call for example Proxy request info There is only one thread of execution in such a system which follows the method calls through the system For example the client calls the proxy s request method This request method either returns a reply straight to the client i e if it can fulfil the request or calls the
40. uah math distributions The Department of Mathematical Sciences The Uni versity of Alabama in Huntsville http www math uah edu psol GNU General Public License
41. 0 2405656 secs run 366 AVG 0 2412951 secs run Runs 10 AVG 1 7787 secs run Runs 39 AVG 2 1498462 secs run Runs 100 AVG 1 87636 secs run Runs 157 AVG 2 1588344 secs run Runs 5 AVG 1 7976 secs run Runs 55 AVG 0 9911091 secs run Runs 163 AVG 0 9468098 secs run Runs 5 AVG 1 8464 secs run Runs 63 AVG 0 5701746 secs run Runs 301 AVG 0 6528239 secs run Total sleeptime 347 86 seconds Actions getl sleepTime 2 964 secs 0 8520669 Runs 343 AVG 0 0086414 secs run use sleepTime 66 025 secs 18 9803369 Runs 1006 AVG 0 0656312 secs run rel sleepTime 52 026 secs 14 9560168 Runs 1006 AVG 0 0517157 secs run get2 sleepTime 2 982 secs 0 8572414 Runs 335 AVG 0 0089015 secs run get3 sleepTime 2 739 secs 0 7873857 Runs 328 AVG 0 0083506 secs run Indiv Activities pl_i0_Comp think lambdal sleepTime 26 965 secs 7 7516817 Runs 74 AVG 0 3643919 secs run Appendix F Model Evaluation Results 116 pl il Comp think lambdal sleepTime 37 571 secs 10 8006094 Runs 101 AVG 0 3719901 secs run pl i2 Comp think lambdal sleepTime 31 7 secs 9 1128615 Runs 90 AVG 0 3522222 secs run pl i3 Comp think lambdal sleepTime 29 097 secs 8 364572 Runs 82 AVG 0 3548415 secs run p2 i0 Comp think lambda2 sleepTime 16 341 secs 4 6975795 Runs 85 AVG 0 1922471 secs run p2 il Comp think lambda2 sleepTime 13 688 secs 3 9349163 Runs 86 AVG 0 1591628 secs ru
42. 2 secs 1 8616385 Runs 168 AVG 0 1857143 secs run txncl i0 Comp reglocklr rllr sleepTime 22 553 secs 1 3456902 Runs 92 AVG 0 2451413 secs run txncl i0 Comp readlock rl sleepTime 20 308 secs 1 2117357 Runs 92 AVG 0 2207391 secs run txnc2 i0 Comp think2 t2 sleepTime 445 238 secs 26 5664166 Runs 101 AVG 4 408297 secs run txnc2 i0 Comp fork w2xrr2 sleepTime 167 083 secs 9 9694918 Runs 312 AVG 0 5355224 secs run txnc2 i0 Comp finish a2rxonemg sleepTime 59 238 secs 3 5346071 Runs 312 AVG 0 1898654 secs run txnc2 i0 Comp reglock2r rl2r txnc2 i0 Comp readlock r2 sleepTime 61 468 secs tompll pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkik KKKKKKKKK SIM RESULTS KKKKKKKK KKKK KK KK KK KK KK KK KK KK KK KKKK KK KK GenSkel tompll Total sleeptime 1110 276 seconds Actions getl sleepTime 56 881 secs 5 1231406 use sleepTime 557 138 secs 50 1801354 rel sleepTime 126 014 secs 11 3497905 get2 sleepTime 59 103 secs 5 323271 Indiv Activities pl i0 Comp think lambdal p2 i0 Comp think lambda2 93 792 secs 217 348 secs sleepTime sleepTime tomplll pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkik KKKKKKKKK SIM RESULTS KKKKKKKK KKRKKK KKK KK KK KK KK KK KK KK KK KK KK KK GenSkel tomp111 Total sleeptime 1597 932 seconds Actions getl sleepTime 54 598 secs 3 4167912 use sleepTime 316 467 secs 19 8047852 rel sleepTime 227 13 secs 14 2139966 get2 slee
43. 556 secs run 9 AVG 0 2383333 secs run 369923 Runs Runs 27 6162288 Runs 72 AVG 11 416875 secs run 2 4378772 Runs 151 AVG 0 4805629 secs run 0 9238837 Runs 150 AVG 0 1833333 secs run 0 6055638 Runs 71 AVG 0 2538732 secs run Appendix F Model Evaluation Results txncl i0 Comp readlock rl s think2 t2 leepTime 18 709 secs txnc2 i0 Comp SleepTime 469 267 secs txnc2 i0 Comp fork w2xrr2 sleepTime 196 637 secs txnc2 i0 Comp finish a2rxg sleepTime 70 859 secs txnc2 i0 Comp reglock2r rl2r readlock r2 s think3 t3 fork w3xr31 s txnc2 i0 Comp leepTime 73 355 secs txnc3 i0 Comp SleepTime 887 557 secs txnc3 i0 Comp leepTime 94 145 secs txnc3 10 Comp finish a31xonema txnc3 i0 Comp reglock3r rl3r txnc3 i0 Comp readlock r3 sleepTime 18 615 secs papmmodelsmall pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkik kkkkkkk STM RESULTS jeeeeeeek KRK kk kk skok a IO K K IO K K GenSkel papmmodelsmall Total sleeptime 2400 003 seconds Actions 1 2158318 1 2170401 2 2089972 2 154164 0 6201659 0 6922075 reglockll lockll sleepTime 29 18 secs write sleepTime 29 209 secs reqlock21 lock21 sleepTime 53 016 secs write sleepTime 51 7 secs reglock31 lock31 sleepTime 14 884 secs write sleepTime 16 613 secs Indiv Activities txncl i0 Comp thinkl tl un leepTime 676 594 secs txncl i0 Comp fork wlxrl
44. 8 secs run Appendix F Model Evaluation Results pR3_i0_Comp arrive lambda pR4 i0 Comp arrive lambda sl i0 Comp walk2 omega sleepTime 6 sl i0 Comp walk3 omega sleepTime 1 sl i0 Comp walk4 omega sleepTime 4 sl i0 Comp walkl omega sleepTime 4 p2j Server 3Client pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkak KKKKKKKKK SIM RESULTS KKKKKKKK kkkkkkkkkkkkkkkkkkkkkkkkkkkkkk GenSkel p2j Server 3Client Total sleeptime 1517 454 seconds Actions reg sleepTime 692 002 secs rep sleepTime 825 452 secs Indiv Activities papmmodel pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkk KKKKKKKKK SIM RESULTS kk kk KKK kkkkkkkkkkkkkkkkkkkkkkkkkkkkkk GenSkel papmmodel Total sleeptime 2976 565 seconds Actions reqloc leepTime 11 459 secs 0 writel sleepTime 9 242 secs regloc leepTime 4 381 secs writel sleepTime 3 549 secs regloc leepTime 3 252 secs writeloc 71 secs k2 sleepTime 5 4 regloc leepTime 11 011 secs 0 writeloc 76 secs k22 Lock22 23 Lock23 k31 Lock31 32 loc k33 k33 sleepTime 6 4 regloc leepTime 8 239 secs write sleepTime 12 037 secs reqloc sleepTime 5 444 secs write sleepTime 4 731 secs reqloc sleepTime 2 056 secs write sleepTime 2 49 secs 0 reqloc S 32 S leepTime 2 873 secs write sleepTime 2 401 secs regloc leepTime 1 625 secs writeloc sleepTime 2 145 secs Activities _i0_Comp think1 t1 Indiv txnc txnc i0
45. 84 secs 2 4302801 Runs 4 AVG 1 21 secs run forward bid cs sleepTime 16 241 secs 8 1549956 Runs 7 AVG 2 3201429 secs run forward preq cs sleepTime 2 021 secs 1 0147926 Runs 4 AVG 0 50525 secs run Indiv Activities bugl pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkik eee SIM RESULTS jee eeeee KR kk kok kok skok skok IOI IO IO K K K K GenSkel canonl Total sleeptime 235 49 seconds Actions a sleepTime 92 18 secs 39 1439127 Runs 45 AVG 2 0484444 secs run Indiv Activities a_i0_Comp b r sleepTime 46 83 secs 19 8861947 Runs 45 AVG 1 0406667 secs run a_i0_Comp c s sleepTime 25 261 secs 10 7269948 Runs 44 AVG 0 5741136 secs run b i0 Comp f m sleepTime 35 625 secs 15 1280309 Runs 22 AVG 1 6193182 secs run b_i0_Comp g m sleepTime 35 594 secs 15 1148669 Runs 23 AVG 1 5475652 secs run bug2 pepa KKKK KK KKK KKK KK KK KK KK KK KK KK KK KK Axe SIM RESULTS eeeeee Re GenSkel bug2 Total sleeptime 127 904 seconds Actions a sleepTime 46 985 secs 36 7345822 Runs 25 AVG 1 8794 secs run Indiv Activities a i0 Comp b r sleepTime 25 381 secs 19 8437891 Runs 25 AVG 1 01524 secs run a i0 Comp c s sleepTime 13 133 secs 10 2678571 Runs 24 AVG 0 5472083 secs run Appendix F Model Evaluation Results b i0 Comp f m sleepTime 27 026 secs b i0 Comp g m sleepTime 15 379 secs canonl pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkak KKKKKKKKK SIM RESULTS KKKKKKKK kkk
46. Activ class exists to increase efficiency of execution as individual Activities may always run immediately on joining whereas shared ones may need to pause until other Components are ready Therefore a lot of the check and wait methods needed to synchronize multiple objects such as i sReady and choice locking are not needed in the case of individual activities and return immediately without performing any commands This allows the rest of the framework to treat individual and shared activities identically 5 8 Synchronization Trees and the SSNode class Synchronization set trees connect Actions to their participating Activities An Action is constantly waiting to run Each time an Activity joins it the Action will re check the status of its synchronization tree to see whether it may run This waiting is ac complished with the usual wait notify Waiter methods see section 5 3 The tree is made up of SSNode objects There are three types of SSNode objects two used as the branches and one as the leaves AND nodes and OR nodes are the branches and Activity objects are the leaves Each branch node has a left child and a right child Though the leaves of the tree are specified as Activity objects only SharedActiv ob jects are used as part of a sychronization tree because individual Activities require no synchronization Consider the Composition line from section 5 7 1 again Client Client serve Server From this line we can see
47. CPS model Appendix B was manually translated the first Translator produces exactly the same code With both Prototypes A and B the Java code needed to define a PEPA system is purposely kept as straightforward as possible and is also as similar as possible to the PEPA model code This is to make manual translation extension and comprehension of the code as simple as possible but has the added side effect of making an automatic Translator s work easier Unfortunately however the first API was too simple to run many PEPA models 4 4 Problems with Prototype A Two months into the project there was a fully working PEPA2Java package and Trans lator At this stage testing began by using the Translator to generate Java equivalents of many of the PEPA models found in the Java Workbench package However whilst some models were successfully translated and ran as desired there were many cases where this was not the case It was now clear that this version of the PEPA2Java API was fundamentally flawed in the sense that it did not provide PEPA equivalent constructs a key condition for meeting the objective of the project Considerable effort was spent to try and correct the problems but eventually these endeavors were abandoned in favour of taking a new Chapter 4 Prototype A Specification amp Implementation of a Flawed API 26 approach as outlined in the next chapter The new approach would maintain the parts of Prototype A that work well wh
48. Comp think lambdal sleepTime 2 902 secs pl il Comp think lambdal sleepTime 74 876 secs p2 i0 Comp think lambda2 sleepTime 221 063 secs tomp221 pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkik KKKKKKKKK SIM RESULTS KKKKKKKK KKKKKK KK KK KK KK KK KK KK KK KKKKKK KK GenSkel tomp221 Total sleeptime 2954 024 seconds Actions getl sleepTime 92 134 secs 3 118932 use sleepTime 566 574 secs 19 1797358 5 rel sleepTime 396 82 secs 13 4332016 5 get2 sleepTime 119 724 secs 4 0529122 5 get3 sleepTime 129 078 secs 4 369565 Indiv Activities pl_i0_Comp think lambdal sleepTime 271 142 pl il Comp think lambdal sleepTime 511 888 p2 i0 Comp think lambda2 sleepTime 114 281 p2 il Comp think lambda2 sleepTime 411 184 p3 i0 Comp think lambda3 sleepTime 341 199 tomp333 pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkik KKKKKKKKK SIM RESULTS KKKKKKKK KK KK KK KK KK KK KK KK KK KK KK KK KK KK KK GenSkel tomp333 Total sleeptime 1846 95 seconds Actions getl sleepTime 68 134 secs 3 6890008 use sleepTime 355 151 secs 19 2290533 rel sleepTime 248 436 secs 13 4511492 get2 sleepTime 27 177 secs 1 4714529 get3 sleepTime 116 976 secs 6 3334687 Indiv Activities Runs Runs secs secs secs secs secs 114 Runs 218 AVG 0 2534817 secs run 437 AVG 1 2630778 secs run 0 2685021 5 6 9277607 5 20 4534373 5 9 AVG 0 3224444 secs run Runs 211 AVG 0 3548626 secs run
49. EPA model and returns a reference to the object representing that construct in the system or if no match can be found throws an Exception References are added automatically to the appropriate vectors of the Ref object by the Component and Activity constructors calling new Component CompA will automatically add a reference to the newly created object to Ref s Components Vector Other Components may then obtain the reference to Component A by calling Ref getComponent CompA 4 3 5 The Simulator Class This class creates all the Activity and Component objects starts those Components mentioned in the composition line and handles all Simulator calls to do with updating the Simulator Window It defines abstract methods createActivities and createCompo nents which is the place where a model implementation should issue the appropriate Component and Activity creation statements This is necessary because the Simula tor needs to perform background commands on the Activities and Components be fore it can start the system such as calling Component init on all Components and Component start on all Components which are set to begin on start up In addition the Simulator adds the various Threads of the system to appropriate ThreadGroup objects so that it can perform actions such as pausing the execution of the system or force Activities to awake from long s eep delays 4 3 6 Model Implementations The Client Proxy Server model
50. EPA offers both qualitative i e testing for deadlock and quantitative performance measurement output from the same system description Additionally the hierarchical composition of PEPA models is familiar to system designers whilst the Component and Activity constructs are similar to the object and method constructs of object oriented languages A stochastic representation of the system may be generated from the derivation graph of the PEPA model When activity rates are based on randomly sampled expo nential distributions this stochastic model is equivalent to a continuous time Markov process meaning the steady state equilibrium if one exists can be found In terms of Chapter 2 Performance Evaluation Process Algebra 5 performance analysis this corresponds to the system s long term settled behaviour showing all the states that it will visit deadlock is detected if the system gets stuck in one state Moreover because we add timing in terms of rates the mean residence time in each of these states is also calculated enabling the discovery of any potential bottlenecks in the system A system is modelled in PEPA by splitting it into its component parts The inter action of these components determines the behaviour of the system as a whole The components may be atomic or define the behaviour of larger collections of compo nents Each component s behaviour is defined by the activities in which it may par ticipate and how it dete
51. EPA system which client is served at any one time is determined randomly However in a real system client s requests will be triggered by some other action such as a user s interactions The generated skeleton s behaviour will be probabilistic rather than deterministic This is not a problem as over the long term a client s requests may be adequately modelled by a random distribution Therefore performance measures will still be useful as long as rates are carefully chosen However the skeleton will be useful only as a starting point in implementation one of the first things which will be done in implementation is to replace the probabilistic choice branching with deterministic branching In section 3 3 1 below the determination of branching is discussed further 3 1 3 Design Decision PEPA Hiding In consultation with the project supervisor it was realised that whilst the Hiding con struct may be valuable for the process of abstract model design and evaluation its importance in an actual system implementation is not obvious Hiding is used to simplify complex models so that some of the details of the un derlying complexity may be hidden The process of top down implementation works in the opposite direction adding the underlying complexity abstracted away in mod elling languages for example PEPA s replacement of actions with delays and its use of probabilistic branching As PEPA2Java is a tool for speeding implementation ther
52. PA Workbench 69 7 2 Qualitative Evaluation oe Fre we ae a a en den en a 73 7 3 Results of Model Tests 4 lt 4 2 24 ok RR RR 224 2 74 7 4 Evaluation of Results and Suggestions for Improvement 75 7 4 1 Drawbacks to the choice pause Mechanism 75 7 4 2 Drawbacks to Choice Committing 79 7 4 3 FFixingthechoicemethod 80 7 5 Suggestion for Extension 81 7 5 1 FullStated based Analysis 81 7 5 2 Minor Improvements Extensions 82 1 6 Future Work z nan 308 ked BS a BR eG a ae ES 84 8 Conclusion 85 A The Client Proxy Server PEPA Model 87 B Prototype A Example the Client Proxy Server System 88 C Prototype B Example the Client Proxy Server System 95 D Default Constants Defined in the Translator 102 E The Modified PC LAN 4 Model 104 F Model Evaluation Results 106 Bibliography 122 vii 1 1 5 1 5 2 5 3 5 4 5 5 6 1 6 2 6 3 6 4 6 5 6 6 6 7 List of Figures A Process for the Rapid Prototyping of High Performance Java Con current Distributed Applications The SSNode Activity class hierarchy A Simple Synchronization Tree Synchronization Tree of Client 1 Client2 Client3 lt serve gt Server The SimWindow Running the Client Proxy Server model The SimResults Window Client Proxy Server model results Th
53. PI 48 Wirte tt Dune O IE OFS Ciemi EM chm JU Comp CE S99 Figure 5 4 The SimWindow Running the Client Proxy Server model 5 11 2 The SimWindow The SimWindow is a GUI intended to allow the user to understand the state of the running model pause and resume simulation interrupt sleeping Actions and adjust the execution speed and the level of debug messaging All the elements in the window including the window itself can be resized to allow the user to monitor the parts she is interested in even in particularly large models As can be seen in figure 5 4 the initial space allocated to the various tables is propor tional to the number of rows in each of them so that if possible all elements may be monitored at the same time Chapter 5 Prototype B Specification amp Implementation ofthe PEPA2Java API 49 Consulting figure 5 4 there are three main parts to the SimWindow the state tables the debug message panel and the control panel There are three state tables each displaying information on the three main different types of PEPA objects of the model 5 11 2 1 The System State Tables The top table displays information on the Components running in the system giving the state they are currently in the name of the script they are running the current Activ ity if any they are participating in and the number of scripts they have run Possible states are things such as Waiting for others Joined and
54. Rapid Prototyping of High Performance Concurrent Java Applications K J R Powell Master of Science School of Computer Science School of Informatics University of Edinburgh 2002 Graduation date December 2002 Abstract The design and implementation of concurrent applications is more challenging than that of sequential applications The aim of this project is to address this challenge by producing an application which can generate skeleton Java systems from a high level PEPA modelling language description By automating the process of translating the design into a Java skeleton system the result will maintain the performance and be havioural characteristics of the model providing a sound framework for completing the concurrent application This method accelerates the process of initial implementation whilst ensuring the system characterisics remain true to the high level model Acknowledgements Many thanks to my supervisor Stephen Gilmore for his excellent guidance and ideas I d also like to express my gratitude to L L for his assistance above and beyond the call of duty in the field of editing Declaration I declare that this thesis was composed by myself that the work contained herein is my own except where explicitly stated otherwise in the text and that this work has not been submitted for any other degree or professional qualification except as specified K J R Powell 2 3 Table of Contents 1 Intro
55. Runs 219 AVG 1 0094201 secs run Runs Runs 386 AVG 0 2386891 secs run Runs 1409 AVG 0 4021107 secs run Runs 1408 AVG 0 2818324 secs run 511 AVG 0 2342935 secs run 512 AVG 0 2521055 secs run 9 1787338 17 3284983 3 8686551 13 9194536 11 5503124 Runs 123 AVG 2 2044065 secs run Runs 265 AVG 1 9316528 secs run Runs 129 AVG 0 8858992 secs run Runs 384 AVG 1 0707917 secs run Runs 512 AVG 0 6664043 secs run Runs 324 AVG 0 2102901 secs run Runs 886 AVG 0 4008476 secs run Runs 885 AVG 0 2807186 secs run Runs 121 AVG 0 2246033 secs run Runs 441 AVG 0 2652517 secs run Appendix F Model Evaluation Results pl i0 Comp think lambdal sleepTime 54 973 secs 2 9764206 pl il Comp think lambdal sleepTime 216 597 secs 11 7272801 pl i2 Comp think lambdal sleepTime 362 521 secs 19 6280896 p2 i0 Comp think lambda2 sleepTime 1 196 secs 0 0647554 5 p2_il_Comp think lambda2 sleepTime 28 217 secs 1 527762 p2_i2_Comp think lambda2 sleepTime 81 416 secs 4 4081323 5 p3_i0_Comp think lambda3 sleepTime 2 21 secs 0 1196567 p3_il_Comp think lambda3 sleepTime 44 028 secs 2 383822 p3 i2 Comp think lambda3 sleepTime 239 918 secs 12 9899564 tomp433 pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkik KKKKKKKKK SIM RESULTS KKKKKKKK KK KK KK KKK KKK KK KK KK KK KK KKKKKK KK GenSkel tomp433 Total sleeptime 1892 025 seconds Actions getl slee
56. System 89 public class Client extends Component Activity proxyRequest proxyReply public Client super Client true protected void init proxyRequest Ref getActivity proxyReguest proxyReply Ref getActivity proxyReply try addMeTo proxyReply false addMeTo proxyRequest false catch AlreadylnitializedException aie aie printErrMsg public void loop call proxyRequest call proxyReply Jr ak eseje k ok kok k ke kok kkk kk kkk kk peer CEE Proxy java Fkk Jr ak ses oe k kok k ko kkk kk kkk kk package csp import prototypeA Appendix B Prototype A Example the Client Proxy Server System 90 cp Title Client Proxy Server Prototype 2 lt p gt lt p gt Description lt p gt lt p gt Copyright Copyright c 2002 lt p gt lt p gt Company Edinburgh University lt p gt author K J R Powell 9 version 1 0 4 public class Proxy extends Component Activity proxyRequest proxyReply serverRequest serverReply public Proxy super Proxy true protected void init proxyRequest Ref getActivity proxyReguest proxyReply Ref getActivity proxyReply serverRequest Ref getActivity serverRequest serverReply Ref getActivity serverReply try addMeTo proxyReguest true addMeTo proxyReply true addMeTo serverReguest false addMeTo serverReply false catch AlreadylnitializedException aie aie printE
57. They can also be used in Hiding constructs but PEPA2Java accept these constructs see section 3 1 3 These objects are either created as components of the ProcObj trees or are put into static vectors so that they can be easily referenced in the analysis stage Note that no Component objects exist yet the parser returns as it s final result a ProcObj which corresponds to the model s composition line This composition line will be analysed to create the Components and the synchronisation set trees 6 5 Analysis Algorithms Once the parsing has been completed the input has been transformed into a collection of Java objects holding the model s details Several steps need to be performed to manipulate this data into the correct form for outputting a PEPA2Java skeleton 6 5 1 SSNode One of the most challenging problems is that of generating the PEPA2Java commands for building correct synchronisation trees from the composition line The composition line returned by the parser is of a tree form For example take the the composition Chapter 6 Implementation of the Translator 57 ActionSet Component Cooperation Figure 6 3 The data structure created from A m gt B lt n gt C line A m B n C The parser will return the tree as shown in figure 6 3 For PEPA2Java a setSynch method call must be made by each Action to create the synchronisation tree To generate this call the algorithm goes through two stages
58. U TC 17 4 2 First Steps Proof OF Concept 3383283 hada ee re S To tt 18 4 2 1 A Simple Client Proxy Server System 18 4 2 2 Activities as Method Calls 19 23 POODE A nn a A NA A A a A leu 19 4 3 1 The Component and Activity Classes 20 4 3 2 The SynchSet Class esse Dr a 23 43 37 The Rate Class 3297935 nr Mr eS nr 23 4 3 4 The Ref Class 2 ee RD 23 4 3 5 The Simulator Class 2 2 umi sha ota rer S 24 4 3 6 Model Implementations 24 d SEESUSIGEUE S EI oeuf coh Pec a aka ARD doe a e at 25 4 4 Problems with Prototype A 2 4 4 1 SynchronisationSett 26 4 4 2 Activities and Actions 27 4 4 3 The Form of Components 27 4 4 4 FTheMethod CallStask 28 44 5 Conclusion s 08088 ee 28 Prototype B Specification amp Implementation of the PEPA2Java API 29 5 1 5 2 5 3 5 4 5 5 OVErVIEW a me pe pne eka PR ee ee 29 The PEPA System cea ua AT Ber was 29 Forcing Lock step The Waiter and Lock classes 30 Simulating Race Conditions 31 Components and Scripts 32 6 930 SNGUGIIS cur ato So eos xc whe ee eet ues en a re 33 DY ACHUVIUES aja uos ados doter Elo UR XO 302 apo k Ro Sf 33 5 7 1 The SharedActiv class auto 42205 9 en ae te er le 36 5 7 2 The IndivActiv class s 4 4 sb 4 24 22 RR 2 38 5 8 Synchro
59. VG 0 945518 secs run robot i0 Comp at press arm 2 R 2 sleepTime 71 418 secs 1 059474 Runs 153 AVG 0 4667843 secs run robot i0 Comp pick posn arm 2 A2 T1 sleepTime 331 113 secs 4 9120057 Runs 153 AVG 2 1641373 secs run robot i0 Comp at belt arm 2 R 3 sleepTime 50 024 secs 0 7420976 Runs 153 AVG 0 3269542 secs run robot i0 Comp put posn arm 2 A2 T2 sleepTime 157 448 secs 2 3357146 Runs 153 AVG 1 0290719 secs run robot i0 Comp safe posn arm 2 A2 T3 sleepTime 89 599 secs 1 3291861 Runs 153 AVG 0 5856144 secs run robot i0 Comp at press arm 1 R 4 sleepTime 50 143 secs 0 743863 Runs 152 AVG 0 3298882 secs run robot i0 Comp put posn arm 1 A1 T2 sleepTime 149 609 secs 2 2194244 Runs 152 AVG 0 9842697 secs run robot i0 Comp at table arm 1 R 1 sleepTime 100 453 secs 1 4902034 Runs 152 AVG 0 660875 secs run belt i0 Comp B sensor On F T sleepTime 327 529 secs 4 8588377 Runs 155 AVG 2 1130903 secs run belt i0 Comp B sensor Off F B sleepTime 328 627 secs 4 8751263 Runs 154 AVG 2 1339416 secs run table i0 Comp move table T T sleepTime 620 198 secs 9 2005331 Runs 308 AVG 2 0136299 secs run press i0 Comp move press P b2m sleepTime 587 978 secs 8 7225548 Runs 305 AVG 1 9277967 secs run dBelt 1 i0 Comp delay D B sleepTime 261 216 secs 3 8750955 Runs 153 AVG 1 7072941 secs run dBelt 1 i0 Comp D sensor On D T sleepTime 355 034 secs 5 2668697 Runs 153 AVG
60. ad Those Components that are referred to in the composition line are started on system start up but are otherwise no different to other Components So in a Prototype A translation of the above system Component A executes an Activity a then calls A1 to execute Similarly A1 executes b and then calls A For Prototype A the composition line is used only to determine that the Thread object holding A should be started on system start up Chapter 4 Prototype A Specification amp Implementation of a Flawed API 28 Again the system functions as one would expect a PEPA system to function How ever there is a lack of equivalence between a PEPA Component and a PEPA2Java Component potentially causing confusion Also this means that more Component classes are created by the Translator than necessary and Thread objects are created which are never started These problems lead to less efficient run time performance once all the objects are created 4 4 4 The Method Call Stack This final problem with Prototype A is not a problem with the translation of PEPA se mantics but an implementation problem The way Components call other Components without ever exiting their 1oop method leads to a forever growing method call stack Consider the model introduced above in Section 4 4 3 The final action of both Component A and Al is to call the other Due to the cycle neither of the loop method calls will ever return so the stack will continuing growing unti
61. as useful as it first seems Firstly the results of the simulation give the number of times each Action has been run but does not in the case of individual Actions distinguish between the different Components The results for one run are event read 4 0 fired times 1505 event write 5 0 fired times 1506 Chapter 7 Evaluation 72 The results for this model are hardly surprising as each read must be followed by a write More useful would be the residence times for each Action but unfortunately these are not given Instead the mean residence times are given for the states as defined for the steady state solution The Workbench allows the two to be easily compared It might still be possible to use the simulator s results as a bridge between the PEPA2Java results and the steady state solution If e the Workbench s simulation results for the number of times each Action is run are equivalent to the PEPA2Java Simple Analysis results and e the Workbench s simulation results for state residence means are equivalent to the Workbench s steady state solution s calculated state residence means then it might be possible to argue that the PEPA2Java system is behaving as the steady state solution predicts the PEPA model should by using the Workbench s simulation results as a common comparison measure However this tenuous transitive comparison of results falls at the first hurdle No statistical test is needed to rea
62. blem is the main reason why Prototype A was scrapped Chapter 4 Prototype A Specification amp Implementation of a Flawed API 27 4 4 2 Activities and Actions In Prototype A Activities performed a combination of the function that Actions and Activities perform in PEPA There was no Action class at all because the Activity class was a hybrid of the two constructs There was no clear separation of an Activity which is local to a Component and an Action which is a global construct that may or may not be joined by multiple Activities This difference did not cause any real problems when it came to running a model as a Java system but was counterintuitive to the user Therefore Prototype B should specify separate Activity and Action classes 4 4 3 The Form of Components Consider the simple PEPA model A a 2 0 Al Al b 1 0 A In a true PEPA interpretation of the model the separate Components of the system are defined in the final composition line Each variable in the composition line equates to a separately executing process and the Actions they cooperate on are held in the synchronization sets between them Therefore A is the only Component in the system above Component behaviour is defined above in the process definitions so A can exhibit both the behaviour defined by A and the behaviour defined by A1 However in Prototype A each definition is taken as a separate Component capable of being executed as a separate Thre
63. ccess Alternatively if the walkon Action completes this indicates access to the LAN became available to this PC when there were no outstanding requests Therefore it moved on the next PC in the ring Using a race conditions as PEPA does means that the arrive Action can be started whilst the the walkon2 Action must await synchronisation with the Server Component i e must wait for it to enter its S1 state However once the Server becomes available it participates in walkon2 If that Action completes before the arrive Action does the Component will abort the arrive action The problem with translating this model into the PEPA2Java equivalent is that only ready branches may be chosen as outlined in points four and five in section 5 4 The arrive Action is always ready whilst the walkon2 Action requires synchronisation In most models the choice pause mechanism provides a chance for synchronisers to arrive but in this model the Server needs to make three other choices with the three other PCs before it returns to the first state This means it needs to await three choice pause expiries before returning By that time the choice pause of this branch will of course have expired Therefore the walkon branch will never be executed always losing to the individual Action This is a major drawback of using the choice pause mechanism in place of an interruptable race condition It is possible to modify the program so that it b
64. ch time the Activity is called To avoid this inefficiency the Translator could define a Rate object say called Rate 1 0 for the Component calling this Activity so the Rate could be re used and resampled rather than recreated each time Echo stdin and sterr to the P2J Dialog Window Code to catch the messages and errors from running an external process is already included in the P2J Dialog Window class but at present does not work correctly Being able to see the messages especially error messages during compilation and running of models from within the Workbench would be very useful Chapter 7 Evaluation 84 7 6 Future Work It would be an interesting follow up exercise as outlined in section 3 5 to use the tools produced to work through the design and implementation of an actual system however simple following the plan stipulated in figure 1 1 Chapter 8 Conclusion The principal goal of the project was to devise a method for the Rapid Prototyping of High Performance Concurrent Java Applications This was accomplished by au tomating the creation of skeleton Java implementations from designs specified in the high level modelling language PEPA Automating the process means undesirable behaviour such as deadlock will not be introduced Also the performance characteristics of the model tweaked to deliver the best results in the Workbench will be maintained into implementation In order to fulfill the goal o
65. compile and run the resulting model Naturally the model cannot be compiled or run before it has been translated On translation a dialog window will pop up to inform the user if translation was successful or if not the cause of the failure Though the Dialog window allows a more user friendly interface with the Trans lator it comes at a cost Because calling the Java Compiler from within the runtime environment is not supported in most versions of the Java Developer Kit the compile and run button instead causes the runtime to execute the make run ModelName com mand as a new system process There are two problems with this approach firstly the Chapter 6 Implementation of the Translator 67 Gathering data for se weet 2 CLE Meg SHARED Action pec SHARED pec SHARED Files will b Di rec tary alre Creating Sim Clas overwriting f Creating Client rwriting f Creating Proxy cl Overwr ting Creating Server c Dverwrh ting N20 Cs bly 3 47 taie Creating Makef la A overwriting file pe Kon ry Translation Finished Figure 6 7 The PEPA2Java Translator Dialog Window Chapter 6 Implementation of the Translator 68 compile and run command can therefore only be used in systems with make installed Therefore the Translator cannot automatically compile and run the model in some less developer friendly operating systems such as Microsoft Windows Secondly and more importantly any error messages from the c
66. ctivity is currently set to run at When the Action is about to run it calculates its determining Rate from all the participating Activities The mechanism for deciding the determining rate of the Action is described in section 5 10 1 The joinAt method is identical to the join method except that it also allows the caller to specify the Rate Chapter 5 Prototype B Specification amp Implementation ofthe PEPA2Java API 36 at which this Activity should be performed This second method is the recommended implementation of the PEPA prefix construct and is the method always used in Trans lator generated code It is equivalent to a setRate call immediately followed by a call to join Otherwise the Activity will use whichever Rate it is currently assigned There are two sub classes of the Activity class IndivActiv and Shared Activ In divActiv is used for executing individual Activities those without synchronization SharedActiv is used to execute Activities which require synchronization between mul tiple Components 5 7 1 The SharedActiv class The SharedActiv class is quite complex Synchronization is handled by creating Syn chronization Set trees from SSNode objects As is clear from figure 5 1 the Activity class and its subclasses inherit SSNode class functionality These objects are detailed below in section 5 8 The most complex methods of the SharedActiv and the SSNode classes deal with choice branching and the manner this is accomp
67. cture the Workbench writes to disk and parse it to build an table of all the system states in the Simulator Then each time a Component performs an action that means a global state transition such as executing an Activity it could submit the details of the change along with a global timestamp taken from the system clock to a static queue like mechanism Once the execution of the system has completed the queue could be processed beginning from the initial system state which is known and look up each transition in the state table A similar lookup mechanism the PEPA State Finder already exists in the Workbench The lookup would give the state index numbers and using this together with the timestamp would be enough to calculate the mean residence time of each state because the queue contains all the Component transitions 7 5 2 Minor Improvements Extensions Simple Analysis If the user changes the speed whilst a model is running with the Simulator the Simple Analysis at the end of the model run is invalid Because the Simple Analysis tallies sleep times changing the multiplier used for calculating those sleep times from the exponential distribibuted random samples will skew the results There are two possible solutions 1 reset the sleep counters and the Action Activity run counters each time the speed is changed or 2 tally the sample rather than the sleep times and calculate the totals at the end using a single multiplier
68. d evaluated Some ideas survived right through to the final version but most came and went The most dramatic stage was when after Prototype A and its Translator were fully completed it was discovered to have major shortcomings Almost all the code was scrapped and Prototype B was started As disheartening as starting from scratch was the time and effort that went into Prototype A described in this chapter was certainly not wasted Prototype B is much stronger for the process and eventually became the finalised PEPA2Java pack age Chapter 5 describes the functionality of the completed version However it is also worthwhile recounting the evolution of the implementations and the ideas that didn t work as well as the ones that did 17 Chapter 4 Prototype A Specification amp Implementation of a Flawed API 18 4 2 First Steps Proof of Concept The first step to building the API and its implementation is to take a simple PEPA example and build a working Java model of it Through this process ideas are tested A practical working system helps to give substance to the concepts and highlight those areas where the ideas do not work 4 2 1 A Simple Client Proxy Server System The model chosen for the Proof of Concept is a simple system made up of three com ponents a client that makes requests for information a server that is the authoritative provider of the requested information and a proxy that serves the client but may also need
69. d yield two Component objects A and A Atthe beginning of the simulation A would be set running The last instruction of its loop method after it had completed Activity a r would execute the this call A method call Respectively Component A would issue this call A as its last instruction Chapter 4 Prototype A Specification amp Implementation of a Flawed API 21 This is the first problem with Prototype A the method call stack will continue to grow as these loop methods never complete but instead keep calling each other in a cycle Component init and Component addMeTo The init method is an abstract method which needs to be defined for each particular Component It gets and sets the references to other Components and Activities it needs and also calls the addMeTo method to add itself to particular Activities it participates in as either a passive or an active participant Component call A call method is defined for Component objects which takes as an argument an Ac tivity to join This ocks the Component into running that Activity and also sets the ready flag Individual activities are always able to execute immediately but shared ones require synchronisation between multiple Components Shared Activities con tain a SynchSet object which holds a Ready and a Locked flag for each Component that participates in the Activity Only once all the Locked flags are set have the re quired participants joined and the Activ
70. del Unlike solving for steady state in Markov chains this analysis is much more simple Because the model runs concurrently and is therefore made up of multiple Threads of execu tion rather than the percentage spent in each state the percentages spent running each Action are given Each time an Action runs it adds the length of time it will sleep to the global sleep time total as well as its own internal sleep time total Then at the end of the simulation it calculates how much time as a percent of the system total it accounted for in the global running time Note this does not include the time taken waiting for synchronization or internal system actions such as acquiring locks status checking etc Also displayed are the mean sleep time of each run and the number of times each Action shared and internal was executed This facility is meant only to provide basic feedback to help the user determine whether the model is working Chapter 5 Prototype B Specification amp Implementation ofthe PEPA2Java API Peed ae eR ee dd ARA j Penn Silki RESULTS PTT retire don a riti nie kia ruta rati Total sleeptime 1740419 seconds klaren Time sleep Time sleep Time sleep Time ndiv Activities 745 905 gees GO 1335516 X 318 007 gees 25 A7LB27193X 80 299 secs RE 205 secs F 2797176 8 F 1109037 5 ao0B AWn 12372118 gece fran ADELA 0 78 02542 sers run 14 11AwG 0 amp 404124 secsirani 14140 0 625567 secz Irun
71. duction 1 li Prin ipal Goal sz sa are BS eS rer re km Xe 1 1 2 PEPA and Jaya aci ve ate os ate ae whee ena ate hee ae cad 2 1 3 Project Objective S kg sp we ke eee a ee tete 2 Performance Evaluation Process Algebra 4 2 1 Overview of PEPA and its roleindesign 4 22 CIhesyntax OE PEPA me ae en ZA BO ae Ney 6 23 Existing Tools and Related Work 8 2 3 1 Java PEPA Workbench ns 23 8 4425093 tease ae k 8 DD PEPA NA san a Pa oa SONS HR 8 Design 3 1 Overview and Design Decisions 3 1 1 Concurrent and Distributed Systems Practicalities of Initial Implementation 2 24 24 220 2 Sheed Kae 10 3 1 2 Inherent Limitations Deterministic and Probabilistic Behaviour 10 3 1 3 Design Decision PEPA Hiding 11 32 The PEPA2Java API 454593 22er 12 3 2 1 Package independence 0 24 2 4 24 829544 24 12 32 2 Specified Objects and Methods 12 3 3 The Barebones and the Simulator Packages 13 3 3 1 Simulating the Race Conditton 13 3 3 20 Concurrency Contol 14 5 3 4 The PBPA2Iava Translator sa s Xue we en ee Neal ana 14 34 1 Lexer and Parser sane roti p NA VAR LE NEN 15 3 4 2 The Translator s Data Structures 15 3 4 3 Integration into the PEPA Workbench 16 Do Evaluations sea shod skok er RER El slu 16 Prototype A Specification amp Implementation of a Flawed API 17 LA EEG Usu AN Bc P
72. e is no need to include support for Hiding the tool exists to aid in the process of adding the underlying detail not to remove it Accordingly there is no equivalent for Hiding constructs in the API and the Translator will fail to translate any model including them Chapter 3 Design 12 3 2 The PEPA2Java API 3 2 1 Package independence The heart of the project is the API for executing PEPA equivalent commands in a Java program which provides a clear straight forward manner to do this One of the benefits of the API is that it is general and flexible enough to work with different packages each providing different functionality For example in the next section the two packages implemented for this project are introduced The API implementing packages can be used interchangeably to provide different functionality for executing a PEPA model In the same vein if would be possible to create a PEPA2Java package which imple ments Remote Method Invocation Then any translated model could be run as either a simulation a concurrent system or a distributed system It should be possible to re use a great deal of the current code if this were attempted The algorithms for syn chronisation and the form of the objects would remain the same though some of the synchronisation code would need to be modified to reduce the number of method calls and sharing of data structures There are more details on the actual API in the next two chapters 3 2
73. eeptime 175 816 seconds Actions Indiv Activities a_i0_Comp a r sleepTime 67 926 secs 38 634709 Runs 37 AVG 1 8358378 secs run a i0 Comp b u sleepTime 76 544 secs 43 5364244 Runs 98 AVG 0 7810612 secs run a i0 Comp c t sleepTime 31 346 secs 17 8288665 Runs 12 AVG 2 6121667 secs run test2 pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkik xe SIM RESULTS xxxxKKxx RR GenSkel test2 Total sleeptime 1990 241 seconds Actions Indiv Activities a_i0_Comp a r sleepTime 1319 121 secs 66 2794606 Runs 678 AVG 1 9456062 secs run a i0 Comp b s sleepTime 671 12 secs 33 7205394 Runs 678 AVG 0 9898525 secs run test4 pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkik kkkkkk SIM RESULTS KKKKKKKK KKKKKK KK KK KK KK KK KK KK KKKKKKKKKK GenSkel test4 Total sleeptime 1990 039 seconds Actions Indiv Activities Appendix F Model Evaluation Results 118 a_i0_Comp a u sleepTime 1990 039 secs 100 0 Runs 4206 AVG 0 4731429 secs run test5 pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkk KKKKKKKKK SIM RESULTS KKKKKKKK KKKK KK KK KK KK KK KK KK KK KK KK KK KK KK GenSkel test5 Total sleeptime 1894 211 seconds Actions Indiv Activities a i0 Comp a al sleepTime 1894 211 secs 100 0 Runs 2615 AVG 0 7243637 secs run test5c pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkk KKKKKKKKK SIM RESULTS KKKKKKKK KKKK KK KK KKK KKK KK KK KK KK KK KKKK KK GenSkel test5c Total sleeptime 2037 121 seconds Actions Indiv
74. ehaves in the same manner but does not require the use of a race condition Namely adding a separate process PR to model the arrival of network requests means the Component is only committed to the serve Action when the arrive Action has completed It does not lock out the possibility of executing the walk on Action The modified model is given in Appendix E Admittedly this has made the model more complex but it will now work with a system such as PEPA2Java where Actions may not be aborted Note that this also means that it is not necessary to isolate the serve Action in a separate derivative as was the case before using PC10 and PC11 once the serve Action has been Chapter 7 Evaluation 79 chosen it will not be usurped by the walkon Action 7 4 2 Drawbacks to Choice Committing This second problem is the more serious of the two and also arises from the simulation of the race conditions that govern branching in PEPA As detailed in previous sections 3 3 1 and 5 4 tentative execution of all branches is not an option in a skeleton im plementation of a model Instead the program must somehow choose one branch to execute but behave in the same way as the PEPA model does In the choice mechanism there is currently a two stage algorithm of expressing readiness pausing for choice pause and then choosing the fastest ready branch However in the Big model when three
75. erver Script public Server Comp String name super name public class Server Script implements CompScript public CompScript actions pReq Activ joinAt TOP Rate Appendix C Prototype B Example the Client Proxy Server System 99 pRep Activ joinAt c Rate return server Script RR o A s oh s oh k k k k k k k k k k k k k kk lc ee REEERE Sava SP EREE ERKEK PEE a s s s ok s s s s he k k k k k k k k k kk k kk k ohe sk ohe k KK K k package CPS import pepa Pepa2Java Simulator Skeleton generated by Pepa2Java Translator v 0 1 Built 29 August 2002 12 00 18 CEST Source home kip PEPA jpwb2 models CPS pepa 7 public class Sim extends PepaSystem Shared Actions static Action cReq Act static Action cRep Act static Action pReq Act static Action pRep Act Components static Client Comp client i0 Comp static Proxy Comp proxy i0 Comp Appendix C Prototype B Example the Client Proxy Server System 100 static Server Comp server_i0_Comp public Sim super GenSkel CPS 2 1 public void createActions cReq Act new Action cReq cRep Act new Action cRep pReq Act new Action pReg pRep Act new Action pRep public void initSynchs cReq Act setSynch SSNode AND Sim client 10 Comp cReq Activ Sim proxy 10 Comp cReq Activ cRep Act setSynch SSNode AND Sim client 10 Comp cRep Activ Sim proxy 10 Comp cRep Activ
76. es in the same choice Also the almostClone method means two Activities can share the same Rate object outside the choice method with out having identical sleep times within it 2 Use the getPriority method to get the determining Rate of this Activity s Ac tion e For individual Activities this returns its Rate e For shared Activities if the Action the Activity participates in is ready to run the method calls getRate myPath on the synchronization tree see section 5 10 2 to return the determining Rate If the Activity is not ready the method returns null signifying this Activity is unavailable for choosing An Activity is ready to run if the subset of cooperating Runners that contains this Activity are either Locked joined or Ready as set by another choice method 3 If the determining Rate returned from getPriority is faster than that referred to by best this Activity is the current winner Note that in the case of equal sleeptimes one is chosen at random After checking all Activities if a winner is found those Activities that are not chosen have their ready flags set back to false all locks are released and the position Chapter 5 Prototype B Specification amp Implementation ofthe PEPA2Java API 45 ofthe winner in the Activities array will be returned as the result ofthe choice method Alternatively if after checking all the Activities there are no ready Actions all locks are released the Thread will pa
77. essages that give specific information on what the objects are doing It was important to be able to use one source for both implementations as during development so much of the code was being constantly fixed or scrapped and replaced Maintaining two sets of code that were meant to operate identically in all ways except the debugging information and the GUI updates would have proven impossible 5 11 1 Debugging If run with the Simulator package included every object in the PEPA2Java model will contain an instance of a Debug object This provides two core methods The first method is debug println which takes a String and an integer as argu ments This method will echo the message to screen and to the SimWindow providing it is not filtered The filter works by only printing those messages with a integer less than or equal to the current Debug level set There are final static integers set in the Debug class naming the various granularities of debug messaging for convenience i e NONE CALLS ALL etc The second method is debug set State which takes as argument an integer repre senting the state of the object These integers like the debugging level reference a set of predefined final static integers defined in the Debug class and allow the state to be set to things like Debug JOINED This information is used to keep the SimWindow updated Chapter 5 Prototype B Specification amp Implementation of the PEPA2Java A
78. ever activity completes first determines whether the system will next behave as P or Q Cooperation P P Q The cooperation set L determines the interaction between components P and Q Specif ically the set is made up of all those actions on which P and must synchronise the Chapter 2 Performance Evaluation Process Algebra 7 Prefix Choice Hiding Constant Synchronisation P lt L gt Q P lt gt 0 or P for parallel composition Table 2 1 ASCII equivalents of PEPA constructs actions reguire the simultaneous participation of both components Shared actions are made up of the activities of components P and which participate in the action Shared actions will complete at a rate determined by the slowest participant Pas sive activities 1 e those with rate T may be required participants but do not affect the action s rate Activities present in components P and Q whose actions do not appear is set L are termed individual activities and do not reguire synchronisation Parallel composition where there is no cooperation between components is de noted P P O or P Q In this case both components run concurrently and indepen dently Hiding P L The component P L behaves as P except that any activities in set L are hidden they participate in special action type t behaving as an individual activity They are not externally observable and may not synchronise with other components def C
79. f Initial Implementation The original title of the project was Rapid Prototyping of High Performance Dis tributed Java Applications However in order to focus on the core problem of en suring a close fit of PEPA2Java to PEPA an early decision was made to build a con current implementation of the API The difference between a concurrent system and a distributed system is not large especially if there is an API such as Java s Remote Method Invocation available In essence the main differences of a concurrent system are the more efficient communication between components and the sharing of a com mon memory To reflect the shift of emphasis the project has been re titled Rapid Prototyping of High Performance Concurrent Java Applications 3 1 2 Inherent Limitations Deterministic and Probabilistic Behaviour One clear limitation of translating from a PEPA model to an actual implementation is that of branching In a model the choice of which branch to execute is simplified In the case of PEPA it is determined by a race condition of randomly sampled exponen Chapter 3 Design 11 tially distributed rates However in an implemented system branching is decided by the system s past choices namely it is deterministic For example consider a system which is made up of a server and three clients The server serves one client at a time participating in a shared action such as sending the client some requested data In a P
80. f the project two objectives were set The first objective was to produce and implement an API for creating and using PEPA equivalent constructs in Java The PEPA2Java API has been specified and is implemented by the Barebones and Simulator packages These can run any PEPA model as a concurrent system The second objective was to build an application that could translate PEPA models into Java The PEPA2Java Translator produces running skeleton implementations which use the commands specified in the PEPA2Java API to run as PEPA equivalent systems The evaluation of the finished tools found that all models were able to be trans lated successfully into PEPA2Java compatible Java packages Compiling and running these systems with the Simulator package found that in all but two cases the resulting systems performed as expected The two special cases arose as a consequence of the necessity of replacing genuine race conditions with simulated race conditions Sug 85 Chapter 8 Conclusion 86 gestions made to extend and improve the Barebones and Simulator packages would if put into effect enable the implementations to run these final two models correctly They will also provide the facility for statistical comparison of the PEPA2Java execu tion of a model to the steady state solution found in the PEPA Workbench in order to see whether they are truly equivalent By automating the process of creating the initial Java implementation from a PEPA
81. for each process definition line It consists of an identifier and the process tree consisting of ProcObj objects These definitions are used to specify a Component s behaviour and are named to reflect the fact that they will be translated into the CompScript classes in the final Java output RateObj Rates are created from rate declarations e g amp 1 0 and within prefix con structs where they may be given as unspecified T infty as a numerical value e g 1 0 or refer to a previously declared Rate e g Chapter 6 Implementation of the Translator 56 ActivObj When a Prefix is found an ActivObj is created which holds two references one to a RateObj representing the rate at which the Activity runs and the other to an ActionObj which represents the global Action this Activity participates in If the name of the Action does not correspond to an already defined ActionObj a new one with that identifier 1s created ActionObj Unlike Rates or Activities the set of Actions may not contain duplicate identities Each Action is a global entity even when they are executed without synchronisation Therefore when the parser comes across an Action if the Ac tion has already been defined a reference to the existing Action is returned If the Action is not already defined a new ActionObj is created ActionSet ActionSet objects are created within Cooperation constructs and define which Actions Components must synchronise on
82. fully transformed compiled and run some of them do not execute as the Workbench predicts they should The full list of results can be found in Appendix F The following models are the ones which caused problems In increasing order of severity they are Deadlock Running this model results in deadlock but the clue is in the name this is the correct behaviour Maple This model refers to the rates a B y and but does not define them anywhere The model was completed by specifying all these rates to be equal to 1 0 This version was saved as maple mod pepa and now works as it should in both the Workbench and as a PEPA2Java system test9 test10 test17 These models deadlock when running because they are invalid Specifically they define and try to start Actions which do not contain any active Chapter 7 Evaluation 75 participants test7 The composition line of this model refers to Actions that are not used anywhere in the model The Translator creates code to initialise these Actions but compi lation fails because the Actions are not defined anywhere PC LAN4 The PC LAN 4 system demonstrates the second short coming of the choice algorithm more serious than the first This problem is related to the race condi tion problems of Big In this case under certain circumstances a branch may never be chosen As the models are so similar this same starvation occurs in PC LAN 6 One potential solution is to modify the model i
83. h first determines what happens next All other activities are aborted Similarly if a component has a choice of activities all are started The first activity to complete determines the component s behaviour The random sampling means any activity may be the first to finish but the proba Chapter 2 Performance Evaluation Process Algebra 6 bility of an activity completing is given by the ratio of its rate over the sum of the rates of all the activities participating in the action In the long term this probability will determine the number of completed runs for each activity Unlike sequential systems distributed and concurrent systems have multiple si multaneously active interacting processes PEPA represents this cooperation of com ponents in its composition line defining synchronisation sets which specify which components must cooperate on which actions 2 2 The Syntax of PEPA The syntax of PEPA is given as P A r P P Q PIQ P L A The ASCII equivalents used in this paper are given in table 2 1 The functionality of the above constructs is given below Prefix o r Prefix is used to specify the behaviour of components In the above example the com ponent carries out activity a r which participates in action at rate r The component then behaves as component P Choice P O A choice in PEPA means that the system may behave as either or Q The current ac tivities of P and Q are both enabled and which
84. he SynchSet class is the fatal flaw in Prototype A because it failed to take into account the facility of PEPA to contain more complex synchronisation sets See 4 4 1 4 3 3 The Rate Class Exponential rate distributions were first built directly into Activity objects and were used to determine how long the delay was when the Activity ran In order to separate functionality Rate objects were created These Rate objects were initialised with the distribution s rate and used to calculate a sleep time sleep time ExpDist rate sample baseSleep To generate useful delays the base sleep time was set to 1000 When an Activity was run sleep sleep time was called on the executing Thread which paused it for so many milliseconds The ExponentialDistribution class used generates properly balanced distributions and is included in a GNU General Public License package The package originates from the Probability Statistics Object Library of the Department of Mathematical Sci ences University of Alabama in Huntsville Siegrist and Duehring 2001 4 3 4 The Ref Class The Ref class contains Vector objects that hold references for all the system s Com ponent and Activity objects It defines two methods getActivity and getComponent which take as argument the id string of the Activity or Component usually just the Chapter 4 Prototype A Specification amp Implementation of a Flawed API 24 name as given in the P
85. hread join method which is another reason to instead use Activity joinAt Also the setRunners method returns the determining Rate of the subset it has chosen which will specify the pause length simulating the Action running Calling setRunners on an AND node will recursively call the method on both the node s children whereas calling it on an OR node will cause it to be recursively called on only one of the node s children Which child is chosen in an OR node is determined firstly by whether either or both the children return true for isLocked If both are locked then the faster branch will be returned If they are the same speed i e because they both run at rate T then the choice is decided by a weighted random function the chance of setRunners being called on the left branch is equal to the proportion of leaves in the left subtree over the total number of leaves in the two subtrees If only one of the two subtrees returns true for isLocked then setRunners is called on the locked subtree If there were three C1ient Components see figure 5 3 they all operated at rate T and only one was needed to join the Action then the first OR node would return the right child Client1 s node one third of the time and the left child another OR node two thirds of the time The lower OR node would contain the final two Client nodes and would return them with equal probability This method is quite fair except that Client2 and C1ient3 have a slig
86. ht advantage over Clientl Imagine Client1 and Client2 are committed to join but Client3 is not In this case Client2 will be chosen with a two thirds probability and Client1 with a one third probability whereas it should be even To fix this the weight used Chapter 5 Prototype B Specification amp Implementation ofthe PEPA2Java API 41 should be the number of children in the locked state rather than just the total number of children However to fix this for larger mixed AND and OR subtrees would confuse the matter further and require more complex algorithms In any case in most models the synchronization set is quite simple and the Action runs as soon as the first subset returns true for isLocked If not the fastest branch usually decides matters Never theless this is an area which could be looked into to see if a solution exists which still runs efficiently but chooses completely fairly One final note is that the members which are ready but are not set as Runners have their Rates resampled to avoid them being passed unfairly over and over again The other defined methods are used in the evaluation of choices and are therefore described in section 5 9 5 9 The choice Method The mechanism for evaluating choice constructs fairly together with the mechanisms for ensuring lock step section 5 3 is the most complex part of the implementation The Component class defines a method choice that takes as argument an array of Acti
87. ies each Action contains aLock object The static methods request Lock and release Lock are similar to their non static cousins except that they lock an array of Lock objects rather than a single one Because the Locks arrays are returned in a globally sorted order by Hashcode two threads simultaneously requesting Lock sets with shared members will never cause deadlock 5 4 Simulating Race Conditions To address the schism between PEPA models and working systems the race condition see section 3 3 1 is simulated in the following manner in the Simulator and Barebones packages that make up Prototype B Chapter 5 Prototype B Specification amp Implementation ofthe PEPA2Java API 32 Rate samples are decided a priori the branch with the smallest sleep time will be chosen This is the case for both types of branching choosing and multiple Components vying to join an Action see section 3 3 1 2 Losing branches are resampled to simulate speculative execution this prevents branches that get a high sleep time from losing again and again because of one unlucky sample 3 The winning branch will pause for its sleep time resample and then execute its next behaviour 4 Before a branch can be chosen it must be ready to execute all the members of the synchronisation set must be prepared to participate Otherwise another branch will be chosen If no branches are ready the system will execute the first b
88. ilst replacing those that do not Prototype A s API differed to the semantics of PEPA in three ways 4 4 4 Synchronisation Sets The biggest problem with Prototype A was its implementation of synchronization sets Each Activity had one synchronization set and this set contained all the Components that cooperate on the Activity However the implementation was overly simple it allowed only for one set per Activity and thus limited the number and type of PEPA models that could be translated In Prototype A an Activity may not run until all the members of its synchronization set have committed to it Consider for example the model oo amp Il 1 0 2 0 olo o Il Server reg T rep b Server Client reg a rep T Client Server lt reg rep gt Client Client This system cannot be modelled correctly in Prototype A In order to implement a system such as this one Activity reg would need to be split into Activity reg and req The two Activity objects would have slightly different synchronization sets each containing the Server and one of the two Client Components This type of hack may work but adding extra Activities is undesirable as it breaks the parallel between the Java Skeleton and the PEPA model Also there are some models where this fix would cause the model to act differently Finally it results in the creation of extra objects which negatively affects running efficiency The SynchSet pro
89. ing race conditions in branching TOP rates have the specified flag set to false and return Long MIN VALUE as their sleep time Specified Rates return a sleep time which is a random sample from an Exponential Distribution Each time an Activity runs it generates a new sample by calling Rate next Losing branches are also resampled to simulate a race condition Chapter 5 Prototype B Specification amp Implementation ofthe PEPA2Java API 46 In addition there is a final static unspecified Rate named UNSPEC which is defined for convenience and to avoid the unnecessary creation of multiple TOP Rate objects The static slowerRate method takes two Rates as parameters and returns the one with the longer sleep time Similarly the compare method is used to compare this Rate to another If this Rate is faster it returns 1 if it is slower it returns 1 and if the sleep times are identical or they are both T it returns O 5 10 1 Determining Rates of an Action An Action s Rate is the determining rate meaning that when the Action eventually runs it will use this Rate to determine the sleep time The determining rate is also used to decide the branching in choice constructs where the fastest branch is chosen The determining rate is defined as the slowest rate of all actively participating Activities Participating Activities are those members of whichever subset of the synchronization set is currently set as the Action s Runners 5 10
90. ion method on the left child node This method returns true if this sub tree contains a Component that contains an Activity that participates in this Action e If the method returns false return the result of right node prune this node and it s left sub tree have been pruned The ends the algorithm for this node Chapter 6 Implementation of the Translator 59 Figure 6 5 Action M s Pruned Synchronization Tree for A lt m gt B lt n gt C 2 Call the contains thisAction method on the right child node e If the method returns false return the result of left node prune e If no result has been returned then both children must have returned true for contains The left node is set to the result of left prune and set the right node to right prune 3 Finally return this as the result of this prune this node has not been pruned Action M s resulting pruned tree is shown in figure 6 5 Because the right child of the OrNode did not contain any Activities participating in Action M but its left subtree did the left subtree was returned as the result of calling prune on the root The OrNode and its right subtree were dropped The left subtree survived intact because both its children contained Components that participate in Action M Performing these two algorithms on all the Actions in the model will create the synchronization set trees needed to define the PEPA2Java API s abstract initSynchs method in the PepaSystem object
91. ipt new Proxy Script Proxy Script proxy Script new Proxy Script public Proxy_Comp String name super name public class Proxy_Script implements CompScript public CompScript actions cReq Activ joinAt TOP Rate return proxy Script public class Proxy__Script implements CompScript Activity ch Act 0 fcRep Activ pReq Activ Rate ch Rate 0 b Rate a Rate public CompScript actions switch choice ch Act 0 ch Rate 0 4 case 0 cRep Activ joinAt b Rate return proxy Script case 1 pReq Activ joinAt a Rate pRep Activ joinAt TOP Rate cRep Activ joinAt b Rate return proxy Script Appendix C Prototype B Example the Client Proxy Server System 98 throw new Error Problem with choice no valid case returned DRE AR a a s s s k kk k k k k k k k k k k k k kk k lc EEK AR s s k GE Server_Comp java 2k ie ok sk sk sk K K RR a a s ok s ohe kk k k k k k k k k k k k k kk k k k k k Kk K K package CPS import pepa Pepa2Java Simulator Skeleton generated by Pepa2Java Translator v 0 1 Built 29 August 2002 12 00 18 CEST Source home kip PEPA jpwb2 models CPS pepa ki public class Server Comp extends Component 4 Rate TOP Rate lt new Rate Rate c Rate new Rate c 3 0 Activity pReq Activ 2 new SharedActiv Sim pReq Act this Activity pRep Activ new SharedActiv Sim pRep Act this Server Script server Script new S
92. is also passed Additionally a ChoiceData object is created for each new choice block to hold information on the Activity of each branch and its corresponding Rate This is used to create the ch Act and ch Rate arrays defined in each CompScript The arrays are passed to the choice method at the top of each choice block The ChoiceData object is also used to guarantee a unique name is given to each choice block It also holds the case number of the current branch and registers tabbing information for formatting the output A ChoiceData object is passed along with the current ProcObj and the previous ProcObj as arguments to the createScript method which recursively descends the tree and eventually returns a String which will be written to disk as the final Comp Script object 6 6 Form of the Output To see an example of the type of output the Translator creates consult Appendix C A file holding the Component class and its nested CompScript classes will be created for each of the Components Also a PepaSystem extending class will be created in a file by default named Sim see Appendix D for a full list of Translator defaults These files define the behaviour of the system Important to note is that all these files will import one of the two PEPA2Java API implementing packages Therefore it is important to make sure the API package is in the classpath for compiling and running Chapter 6 Implementation of the Translator 62 public clas
93. is also being used separately in another layer 3 4 The PEPA2Java Translator The API and its implementations handle running a PEPA like model as a Java system but it is the job of the Translator to create the classes that make up the implementation of a particular model It is designed to be very easy to use and creates clear code which may be compiled and run automatically by creating Makefiles Chapter 3 Design 15 3 4 1 Lexer and Parser The process of lexical analysis is one of pattern matching input text to recognise spec ified tokens such as keywords and operators and returning them to a tool such as a parser for further processing A parser is a program or a component of a program that analyses the grammatical structure of an input with respect to a given formal grammar Hidders 2001 It takes its input from the lexical analyser and uses a specified grammar to break the PEPA model into its constituent definitions and commands The lexer of the PEPA Workbench can be re used as is However as the Transla tor will need to create different types of objects than the Workbench because of the its different functionality the parser needed to be modified The PEPA Workbench uses a Look Ahead Left Right LALR parser generated by the YACC like Java CUP tool Appel 1998 Hudson 1999 This helpful utility enables quick generation of Java LALR parsers It was possible to reuse the PEPA Workbench s CUP grammar speci fica
94. ity may start Alternatively the call method can take a Component as its argument In this case it starts that Component by calling Component loop Component choice Component objects have a choice method defined that takes as argument two Activities and returns either 1 or 2 as the decision on which Activity to run It is used in a switch block in the Component s oop method to choose which branch a model should take as illustrated below switch this choice activity1 activity2 case 1 this call activity 1 break Chapter 4 Prototype A Specification amp Implementation of a Flawed API 22 case 2 this call activity2 break On calling choice the ready flag is set in the Activity s synchronisation set object indicating that this Component may choose to join this Activity The execution of this Component is then paused briefly to allow other Components to join this Activ ity or evaluate their own Choices with this Component marked as Ready for the two Activities When it awakes the Choice method then checks whether either Activity is able to execute i e all Ready flags are set If so that Activity may be chosen depending on whether the other Activity is ready or not Activities are prioritised for choosing with Shared Active as highest priority then Shared Passive and Individual as lowest If both Activities are ready to go and also of the same priority the faster one the one with the smaller sleep ti
95. kkkkkkkkkak KKKKKKKKK SIM RESULTS KKKKK KKK kkkkkkkkkkkkkkkkkkkkkkkkkkkkkk GenSkel test15 Total sleeptime 791 742 seconds Actions rll sleepTime 68 367 secs 8 6350099 Runs 104 AVG 0 657375 secs run wll sleepTime 43 683 secs 5 5173276 Runs 104 AVG 0 4200288 secs run rl2 sleepTime 131 339 secs 16 5886109 Runs 252 AVG 0 5211865 secs run w12 sleepTime 80 032 secs 10 1083434 Runs 252 AVG 0 3175873 secs run Indiv Activities txnl i0 Comp f a2 sleepTime 468 321 secs 59 1507082 Runs 357 AVG 1 3118235 secs run testl6 pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkik KKKKKKKKK SIM RESULTS KKKKKKKK KK KK KK KK KK KK KK KK KK KK KKKKKKKKKK GenSkel test16 Total sleeptime 1167 068 seconds Actions rll sleepTime 363 436 secs 31 1409447 Runs 529 AVG 0 6870246 secs run wll sleepTime 209 64 secs 17 9629636 Runs 528 AVG 0 3970455 secs run rl2 sleepTime 156 115 secs 13 3766841 Runs 343 AVG 0 4551458 secs run w12 sleepTime 105 045 secs 9 0007609 Runs 343 AVG 0 3062536 secs run Indiv Activities txnl i0 Comp f a2 sleepTime 332 832 secs 28 5186467 Runs 343 AVG 0 9703557 secs run testl8 pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkk KKKKKKKKK SIM RESULTS KKKKKKKK KKKK KKK KKK KK KK KK KK KK KK KK KK KK KK GenSkel test18 Total sleeptime 1298 439 seconds Appendix F Model Evaluation Results 121 Actions rll sleepTime 280 892 secs 21 6330532 Runs 427 AVG 0 6578267
96. kkkkkkkkkkkkkkkkkkkkkkkkkkak GenSkel canonl Total sleeptime 151 717 seconds Actions Indiv Activities a i0 Comp a r sleepTime 151 717 secs canon2 pep kkkkkkkkkkkkkkkkkkkkkkkkkkkkkk KKKKKKKKK SIM RESULTS KKKKKKKK KKKK KK KK KK KK KK KK KK KK KK KK KKKK KK GenSkel canon2 Total sleeptime 504 129 seconds Actions Indiv Activities a_i0_Comp a m sleepTime 137 316 secs a_i0_Comp b n sleepTime 116 791 secs b_i0_Comp c s sleepTime 131 918 secs b_i0_Comp d t sleepTime 118 104 secs canon3 pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkk KKKKKKKKK SIM RESULTS KKKKKKKK kkkkkkkkkkkkkkkkkkkkkkkkkkkkkk GenSkel canon3 Total sleeptime 389 188 seconds Actions b sleepTime 92 057 secs 23 653607 Indiv Activities a i0 Comp a m sleepTime 104 435 secs b i0 Comp c s sleepTime 106 461 secs b i0 Comp d t sleepTime 86 235 secs canon4 pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkk KKKKKKKKK SIM RESULTS KKKKKKKK kkkkkkkkkkkkkkkkkkkkkkkkkkkkkak GenSkel canon4 Total sleeptime 118 249 seconds Actions a sleepTime 46 773 secs 39 5546685 b sleepTime 37 541 secs 31 7474144 21 1299099 12 0238616 100 0 27 2382664 23 1668878 26 1675087 23 4273371 Runs Runs Runs 290 AVG 0 4735034 290 AVG 0 4027276 422 AVG 0 3126019 422 AVG 0 2798673 Runs Runs Runs Runs Runs 218 AVG 0 4222798 secs run 26 834075 5 27 3546461 5 22 1576719 5 Runs
97. l sleepTime 48 949 secs txncl i0 Comp al 2 t2 s xonemq s txnc2 i0 Comp leepTime 272 293 secs txnc2 i0 Comp W2xr21 sleepTime 347 694 secs pa 3 t3 S fork w3xr31 s txnc2 i0 Comp xonemg s txnc3 i0 Comp leepTime 580 623 secs txnc3 i0 Comp leepTime 199 65 secs txnc3 i0 Comp finish a3lxonemg s papmmodel smaller exp pepa kkkxkxkkkkkkkkkkkkkkkkkkkkkkkkxkxk kkkkkkkkxk SIM RESULTS kkkkkkkk kkkxkxkkkkkkkkkkkkkkkkkkkkkkkkxkxk GenSkel papmmodel_smaller_exp Total sleeptime 1675 943 seconds Actions reqlock11 sleepTime 11 882 secs 0 708974 5 writelock11 sleepTime 13 319 secs 0 7947168 reqlock12 sleepTime 4 657 secs 0 2778734 writelock12 sleepTime 8 524 secs 0 5086092 5 reqlock21 sleepTime 8 211 secs 0 4899331 5 sleepTime 69 625 secs sleepTime 20 961 secs sleepTime 17 848 secs Runs Runs leepTime 22 601 secs leepTime 44 083 secs leepTime 12 914 secs 0 6285433 5 15 7653873 6 6061719 2 3805628 5 2 4644179 29 8181629 3 162874 0 704201 0 6253853 5 28 1913814 2 0395391 11 3455275 14 4872319 24 1925948 8 3187396 2 3391056 0 5996173 0 9417072 1 8367894 5 0 5380827 112 Runs 71 AVG 0 263507 secs run Runs 118 AVG 3 976839 secs run Runs 380 AVG 0 5174658 secs run Runs 379 AVG 0 1869631 secs run Runs 285
98. l it eventually over flows This is a problem with the definition of Components and the implementation mechanism used to mimic PEPA Component behaviour 4 4 5 Conclusion Any one of these problems might have been solved but taken together they indicated a serious rift between PEPA constructs and their PEPA2Java equivalents Specifically the composition line being the core definition of a PEPA system was not the core definition of a PEPA2Java system Also as Prototype A had started life as a proof of concept the code was becoming more and more convoluted To solve these discrep ancies and end up with a more elegant implementation the slate was wiped clean and Prototype B was created Chapter 5 Prototype B Specification amp Implementation of the PEPA2Java API 5 1 Overview In developing Prototype B the flawed ideas and the shortcomings of its predecessor were left on the drawing board but the lessons learnt and the sound principles estab lished provided a solid base from which to move forward Prototype B is both a versa tile and powerful tool It is the blueprint for the final PEPA2Java API specification and has evolved into the Barebones and Simulator packages which implement that API 5 2 The PEPA System Central to the implementation is the PepaSystem class This class performs essentially the same function as the Simulator class did in Prototype A It defines three abstract methods which must be defined by implementi
99. ld be a separately executing Thread object Each Thread should loop through its Activities Shared Activities needing synchronisation should pause until all Component members of the synchronisation set are in the right state and ready to cooperate on the Activity A semaphore mechanism which is decremented each time a Component commits to the Activity holds them and only lets the Activity run when the counter hits zero It continues holding the Components until the Activity completes then releases them to continue their separate executions Activities are a separate class from Components and Components receive refer ences to the Activities they participate in from a central Reference object One of the active participants in an Activity starts it when all participants are in the correct state Component run and Component loop The run method of the Thread superclass will repeatedly call this loop as long as the system is running The oop method cycles through this Component s instructions Components in this prototype equate not to the Components as defined in the com position line of the PEPA model but rather to the definition lines of Components in the model Furthermore a separate Component class is created for each derivative The PEPA composition line is used to determine which Threads begin started and which ones do not Take for example the simple model FA a r A A b s A A The translation of this model woul
100. lise that the results given in Table 7 1 comparing the mean state residences of the simulation and the steady state solution for the simple two component model given at the beginning of this section are different There is no chance that these two are equivalent The results in Table 7 1 are for a relatively short run of the simulation lt 5 minutes but the model is also very basic It is stated Fotis 2001 that for very long simulation runs gt 20 hours even large state space models are completely sampled and that the closeness of fit of the simulation and steady state results is directly proportional to the simulation length Unfortunately it is at this time wholly inpractical to run the simulation for such long periods of time to establish what would be at best a tenuous link between the PEPA2Java results and steady state results Therefore comparing the PEPA2Java system to the Workbench s simulation results still does not get us closer to the real goal discovering whether or not a PEPA2Java translation maintains the same running properties as the PEPA model s steady state solution This goal is not achievable with the current PEPA2Java Simulator implementation Chapter 7 Evaluation 73 In order to do this the Simulator package would need to be extended to provide mean residences in each of the states as defined by the Workbench section 7 5 1 That said it has been possible to appraise the important aspects of the performance
101. lished is detailed in section 5 9 An individual Activity may execute an Action immediately on calling joinAt whereas a shared Activity will most likely need to wait for additional Components to join Also even if a Component does join an Action it may or may not be chosen as a participant if there are multiple possible combinations of cooperators for an Action Using an example from a previous chapter consider the composition line Client Client serve Server In this case the Server Component will always participate whenever the serve Action is run However only one of the two C1ient Components may join each run Therefore if both C1ient Components are waiting for serve one must be chosen at random to be a Runner whilst the other will need to wait for a future run of the Action As outlined above the Action will designate the Runners when it is ready to execute The setRunners method traverses the synchronisation set tree and picks the fastest subset which is ready to go The rates of the losing subsets are resampled to ensure they aren t continually passed over Chapter 5 Prototype B Specification amp Implementation ofthe PEPA2Java API 37 java lang Object Pepa2Java SSNode Pepa2Java Activity Abstract Pepa2Java IndivActiv Figure 5 1 The SSNode Activity class hierarchy Chapter 5 Prototype B Specification amp Implementation ofthe PEPA2Java API 38 5 7 2 The IndivActiv class In essence the Indiv
102. me is chosen If neither Activity is ready to run the Component cycles through the pause re check routine until one of the Activities becomes available to run Activity run When all synchronising Components have joined an Activity it is run It pauses for a period determined by its rate and then exits Activity problems A problem with the Activity class is that there is no separation of Activities and Ac tions as there is in PEPA In this implementation an Activity is behaving more like an Action In PEPA Actions are global whereas Activities specify for a single Com ponent which Action it is partaking in and at what rate In this implementation all Components are referencing the same global Activity and submit the rate at which they wish to participate Chapter 4 Prototype A Specification amp Implementation of a Flawed API 23 4 3 2 The SynchSet Class This class represents the synchronisation set for a particular Action or Activity in this implementation specifying which Components must join before it can run Each Component can declare that it is Ready to join or that it has Locked A Ready Compo nent may or may not join it is notifying the Activity that it is choosing between this Activity and another Locking is a notification that the Component has committed to this Activity and is waiting for the Activity to execute Once committed the Component must halt its execution until the the Activity has run T
103. mpScript s actions method This executes the behaviour of the Component as it is defined for one particular definition for example by executing Activities or making branching choices The final action of the CompScript actions method is to return a reference to a CompScript object possibly itself The Component run method will then run the actions method of the newly assigned CompScript This implementation solves two problems of Prototype A First it resolves the po tential for Method Call Stack overflow because each method returns a CompScript reference and exits Second Components in this implementation may take on many varying behaviours as defined by scripts but their synchronisation sets and their rep resentation remain constant Thus Prototype B Components are equivalent to Compo nents as defined in the PEPA composition line and the Component s CompScripts are equivalent to a Component s sequential process definitions in a PEPA model CompScript implementing classes are defined as inner classes of their Component which means they have access to all the references of their holding Component in cluding the references to any other CompScript classes it may define The new translation mentioned in Section 5 2 of the Client Proxy Server example from the previous chapter demonstrates the new form of Components and their Scripts in Prototype B This translation is given in full in Appendix C Finally the other public method in Component
104. n write 5 0 P write 5 0 P 19 753086419753075 96 28 693142 P write 5 0 P 24 691358024691354 96 12 711846 write 5 0 P P 24 691358024691354 96 12 228244 P P 30 864197530864207 46 366653 Table 7 1 Comparing the Workbench s steady state and simulation results Chapter 7 Evaluation 74 reason for the problems 7 3 Results of Model Tests The Translator managed to produce compilable and runnable equivalents for every valid input model tested which is an excellent result Three of the models test19 test21 and tools were not evaluated because they make use of non exponential distributions They specify Normal or Uniform distributions Although the PEPA2Java API does not currently support these alternative distribitions it is a trivial matter to add them see section 7 5 2 Secondly one of the other models test4c performs rate maths in a rate defini tion The parser does not allow this Because there is already support for rate math when it occurs directly in a prefix construction modifying the CUP parser generator s grammar defining file to allow this should be straightforward However as this con struct occurs in only one of the models it is not a high priority In short the PEPA2Java Translator can produce compilable and runnable code from any model that the Workbench can read with one exception test7 mentioned be low Whilst the models can be success
105. n p2 i2 Comp think lambda2 sleepTime 13 659 secs 3 9265797 Runs 80 AVG 0 1707375 secs run p2 i3 Comp think lambda2 sleepTime 15 573 secs 4 476801 Runs 88 AVG 0 1769659 secs run p3 i0 Comp think lambda3 sleepTime 8 847 secs 2 5432645 Runs 86 AVG 0 1028721 secs run p3 il Comp think lambda3 sleepTime 8 832 secs 2 5389525 Runs 84 AVG 0 1051429 secs run p3 i2 Comp think lambda3 sleepTime 10 113 secs 2 907204 Runs 83 AVG 0 1218434 secs run p3 i3 Comp think lambda3 sleepTime 8 738 secs 2 5119301 Runs 79 AVG 0 1106076 secs run workcell2 pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkik kkkkkkk SIM RESULTS kk k kokokok kok kok IOI IO IO kok GenSkel workcell2 Total sleeptime 6740 892 seconds Actions ready to pick sleepTime 90 013 secs 1 3353277 Runs 306 AVG 0 2941601 secs run unload blank sleepTime 93 325 secs 1 3844607 Runs 306 AVG 0 3049837 secs run DBelt ready sleepTime 91 985 secs 1 364582 Runs 306 AVG 0 3006046 secs run load blank sleepTime 93 565 secs 1 3880211 Runs 304 AVG 0 3077796 secs run ready to put sleepTime 94 057 secs 1 3953198 Runs 308 AVG 0 3053799 secs run blank ready sleepTime 91 491 secs 1 3572536 Runs 304 AVG 0 3009572 secs run Indiv Activities robot i0 Comp pick posn arm 1 A1 T1 sleepTime 333 815 secs 4 9520894 Runs 153 AVG 2 1817974 secs run robot i0 Comp safe posn arm 1 A1 T2 sleepTime 288 383 secs 4 2781133 Runs 305 A
106. ng models namely createComponents createActions and initSynchs Examining Appendix C shows an example of the Client Proxy Server PEPA model given in Appendix A implemented using Prototype B It demonstrates the form and use of the PepaSystem extending Sim class that imple ments the required abstract methods The PepaSystem object will create and initialise all the model objects and start the model running If the Simulator package is used it 29 Chapter 5 Prototype B Specification amp Implementation ofthe PEPA2Java API 30 will also control the GUI and the debugging messages The PepaSystem object also maintains three vectors holding references to all the Components Activities and Actions that make up the system Two methods comp id and action id provide similar functionality to the Ref object s functionality see section 4 3 4 in Prototype A These vectors and methods are used by the SimWindow class The preferred manner for Components to get references to the other global objects is to access them through static references which should be defined in the PepaSystem implementing class for each model This is the form of the output as created by the Translator However the API is flexible enough to allow the user to assign references in whichever manner she finds convenient 5 3 Forcing Lock step The Waiter and Lock classes As in Prototype A the most important part of the implementation deals with ensuring that the
107. nization Trees and the SSNodeclass 38 5 9 The choice Method ii 2 246 28 2 24 dok ee ah 2 24 v 41 5 9 1 Registering Interest ue uoo B 2a 0 2 RT 43 5 9 2 Locking and Deciding 43 5 10 Rates and Sleep time 45 5 10 1 Determining Rates of an Action 46 5 10 2 Determining Ratesinchoice 46 5 11 The Simulator Package Extensions 47 DU Debugging lt lt c s cnoe stoc socs toa tastets es 47 5 11 2 The SimWindow uud 2 2 8 22 Rx RR 0 48 5 11 3 Simple Analysis sss 4 004 Rae Ba Bo aaa Oe 50 Implementation of the Translator 52 6 1 Overview of the Translation Process 52 6 2 The Translator Grammar 4 ome iir 2 2 B ao et 53 6 3 JLEXHIS Bee AR 5x o LM o Aag acr o A oe s ON 53 6 4 CPIESIIB socero ARE SB A Zo he OE uie aote 55 6 5 Analysis Algorithms 3 2 2 2a Se 1 22 20 Babe ea 56 BD ANA AK atre a dik au ftd dfe foster aue 56 6 5 2 Creating Components and Scripts 59 6 0 Formiof the Output u vostro ta re ee aat eet e At 61 6 6 1 Generating Valid Class Object and Package Names 63 6 5 Usmg th Translators 2m 2 ara Boe Ox ERE RR AT 64 6 7 1 Automatically Generated Makefiles 65 6 7 2 Running the Translator from the command line 65 6 7 3 Integration with the PEPA Workbench The P2J Dialog Window 66 vi 7 Evaluation 69 7 1 Quantitative Comparison to the PE
108. ns the Action s holder reference to it The Action object is passed to the Thread as a Runnable argument The Action s Rate is reset to TOP so that any Rates submitted by Activities will dominate The final action of the method is to start the newly created Thread This old holder Thread will then die releasing the joined Runners which will immediately set their runner flags back to false signalling they are aware that the current run of this Action has completed Note that on system start up the PepaSystem object section 5 2 will call the reset method of all Actions which will start them 5 7 Activities An Activity is joined when a Component calls its join or joinAt method These are the only public methods of the Activity class Conceptually there is a subtle difference between Activities as specified in PEPA and PEPA2Java Namely Activities in Prototype B are objects held by their execut ing Component Every Component participating in an Action holds one Activity per Action This means that if a Component runs multiple Activities at different rates but the Activities are participating in the same Action they will be represented by a single Activity object in the Component The only difference is that the Component will join that Activity at different Rates at different times This is done by changing the Rate reference the Activity holds The join method commits the Component to running the Activity at whichever Rate the A
109. odel Evaluation Results 107 forward_reject sleepTime 8 542 secs 4 2891431 Runs 4 AVG 2 1355 secs run forward_presp sleepTime 17 274 secs 8 6736897 Runs 20 AVG 0 8637 secs run bid _in sleepTime 0 0 secs 0 0 Runs O AVG NaN secs run preg in sleepTime 0 214 secs 0 1074545 Runs 1 AVG 0 214 secs run forward accept sleepTime 0 0 secs 0 0 Runs O AVG NaN secs run forward reject sleepTime 0 0 secs 0 0 Runs O AVG NaN secs run forward presp sleepTime 0 0 secs 0 0 Runs O AVG NaN secs run accept s sleepTime 14 305 secs 7 1828836 Runs 8 AVG 1 788125 secs run reject s sleepTime 5 563 secs 2 7933157 Runs 4 AVG 1 39075 secs run presp s sleepTime 22 077 secs 11 0853912 Runs 16 AVG 1 3798125 secs run forward bid sleepTime 27 16 secs 13 6376874 Runs 12 AVG 2 2633333 secs run forward preq sleepTime 31 837 secs 15 9861213 Runs 16 AVG 1 9898125 secs run forward accept sc sleepTime 0 0 secs 0 0 Runs O AVG NaN secs run forward reject sc sleepTime 0 0 secs 0 0 Runs O AVG NaN secs run forward presp sc sleepTime 0 0 secs 0 0 Runs O AVG NaN secs run forward bid nc sleepTime 0 0 secs 0 0 Runs O AVG NaN secs run forward preq nc sleepTime 0 0 secs 0 0 Runs O AVG NaN secs run accept sc sleepTime 9 665 secs 4 8530283 Runs 6 AVG 1 6108333 secs run reject sc sleepTime 8 198 secs 4 1164124 Runs 1 AVG 8 198 secs run presp sc sleepTime 4
110. of the API and to identify areas for extension and improvement These are described below 7 2 Qualitative Evaluation Even if it is not possible to test for statistical equivalence between the PEPA2Java output and the steady state solution to a model qualitative evaluation is still feasible To achieve this the Translator will be used to translate the majority just under 50 of the models included with the PEPA Workbench distribution to see if it can successfully create a PEPA2Java equivalent If a model can be successfully translated the resulting Java code will be compiled and run using the Simulator package The SimWindow debugging messages and Simple Analysis window results can then be examined to judge approximately how the Simulator s execution compared to the expected behaviour The expected behaviour is found through the manual examination of the PEPA model and the steady state solution found by the PEPA Workbench The clearest sign of a problem are Actions that are being chosen much more frequently than others or which are rarely never chosen In either case the model would need to be examined to see whether this is the correct behaviour Special attention will be given to the larger models such as the Big and Workcell2 models as well as the PAPM and TOMP series of models Also any models that fail to translate compile or run correctly will be more closely examined to discover the Workbench Steady state Workbench Simulatio
111. ompilation or running process are lost If the model does not run after pressing the compile and run button or it is acting strangely or freezing run the make command from the command line in the output directly to see any error messages Chapter 7 Evaluation 7 1 Quantitative Comparison to the PEPA Workbench One goal of testing is to discover whether or not a PEPA2Java translation maintains the same running properties as the PEPA model s steady state solution as calculated by the PEPA Workbench It is not evident how to compare the Action sleep times provided by the Simulator s Simple Analysis to the steady state solution analysis of the Workbench This is because the steady state solution gives the proportion of time the system is in each state For example for a basic two component model P read m write n P PP the PEPA Workbench calculates the various states of the system to be 1P P 2 write 5 0 P P 3 P write 5 0 P 69 Chapter 7 Evaluation 70 4 write 5 0 P write 5 0 P and gives the steady state solution as 0 30864197530864207 0 24691358024691354 0 24691358024691354 0 19753086419753074 gt W N rnm where the first number refers to the state as calculated above and the second gives the mean of the residence in that state the proportion of time the system is in that state For example the above system is in state 4 where both P Components are independently executing Activi
112. onisation set Therefore the Action will pause between runs until all Components have acknowledged its execution 2 Wait for allLocked The next step in the execution of this Action is to pause until the allLocked method returns true This happens only when all the Com ponent members of any particular subset of the synchronisation set have joined the Action and committed to its running The determination of the subsets is detailed in section 5 8 3 Set the Runners Now the Action is ready to be run it notifies the members of a particular cooperation set that they have been chosen to participate in this run of the Action The Action passes these members a reference to its holder Thread They set their runner flags to true and join this Thread meaning they will cooperate in the Action The join method is a Thread object method which causes the calling Thread to wait for the target Thread to die before it can resume execution 4 Start the Action The Action calls its action method which will cause the Thread to sleep for a number of milliseconds set by its determining rate Deter Chapter 5 Prototype B Specification amp Implementation ofthe PEPA2Java API 35 mining rates are described in section 5 10 1 Alternatively in user implementa tions the sleep action will be replaced by the actual functionality required 5 Reset The reset method is the final command of this run of Action It creates anew Thread object and assig
113. onstant 4 Constants are used to define the behaviour of components In the example above we say that constant A is defined by the behaviour of component P In this way names are assigned to components so they can be referred to more easily elsewhere for example in the system composition line or defining the behaviour that some other component will take on at the end of a prefix construct Chapter 2 Performance Evaluation Process Algebra 8 2 3 Existing Tools and Related Work 2 3 1 Java PEPA Workbench The PEPA Workbench Gilmore and Hillston 1994 Hunter 1999 is a tool used for the analysis of PEPA models It can compute the underlying Markov process and the transition matrix of a model As detailed in the previous section the steady state can be calculated giving rel ative frequencies of the system states This information is written to a text file which can be analysed to discover the model s behavioural and performance characteristics Additionally the walkabout tool can be used to step through a model manually to detect live lock i e when a model is stuck in a small loop limited to a small subset of all the states or to discover where a model is deadlocking The Workbench also includes a simulation tool Fotis 2001 which allows a model to be run as a SimJava simulation Also provided is a facility allowing the simulation results to be compared to the steady state solution As it stands the Workbench is a
114. ould if it is not return to stage 5 to fix the problem 7 To complete implementation switch from using the Simulator package to using the Barebones package Figure 1 1 A Process for the Rapid Prototyping of High Performance Java Concurrent Distributed Applications The API should be flexible and easy to use whilst providing a clear parallel to the PEPA syntax so that manual modification translation and extension remain feasible Additionally it should not impose an excessive burden in terms of running cost The Translator should be able to successfully translate any PEPA model into clear efficient Java code As an added convenience it should be integrated into the Java PEPA Workbench These tools could then be used in the process described in figure 1 1 to facilitate an improved methodology for the design and implementation of concurrent and dis tributed systems Chapter 2 Performance Evaluation Process Algebra The following two sections are based heavily on material from Jane Hillston s A Com positional Approach to Performance Modelling Hillston 1996 It should give the reader a brief overview of PEPA and why it is useful as a modelling language and design tool The second part of the chapter is a brief overview of some of the existing PEPA tools that are relevant to this project 2 1 Overview of PEPA and its role in design Process Algebras are valuable in system design because a language like P
115. pTime 68 465 secs 4 2846003 get3 sleepTime 74 908 secs 4 687809 Indiv Activities pl i0 Comp think lambdal p2 i0 Comp think lambda2 393 418 secs 255 933 secs 207 013 secs sleepTime sleepTime p3 i0 Comp think lambda3 sleepTime tompl2 pepa sleepTime 54 705 secs 3 2641325 3 6676665 8 4476292 19 5760333 24 6204469 16 0165138 12 9550569 5 Runs 253 AVG 0 2162253 secs run Runs 253 AVG 0 2429565 secs run Runs 217 AVG 0 2621244 secs run Runs 435 AVG 1 280777 secs run Runs 434 AVG 0 2903548 secs run Runs 218 AVG 0 2711147 secs run Runs 218 AVG 0 4302385 secs run Runs 218 AVG 0 9970092 secs run Runs 202 AVG 0 2702871 secs run Runs 786 AVG 0 4026298 secs run Runs 786 AVG 0 2889695 secs run Runs 284 AVG 0 2410739 secs run Runs 300 AVG 0 2496933 secs run Runs 203 AVG 1 9380197 secs run Runs 285 AVG 0 8980105 secs run Runs 301 AVG 0 6877508 secs run Appendix F Model Evaluation Results kkkkkkkkkkkkkkkkkkkkkkkkkkkkkak KKKKKKKKK SIM RESULTS KKKKKKKK KK KK KK KKK KKK KKK KKK KK KK KK KK KK KK GenSkel tomp12 Total sleeptime 1080 811 seconds Actions getl sleepTime 55 259 secs 5 1127348 use sleepTime 551 965 secs 51 0695209 5 rel sleepTime 122 218 secs 11 30799 get2 sleepTime 52 528 secs 4 8600542 Indiv Activities Runs Runs 436 AVG 0 2803165 secs run Runs 219 AVG 0 2398539 secs run pl i0
116. pTime 69 039 secs 3 6489476 Runs use sleepTime 346 353 secs 18 305942 Runs rel sleepTime 247 468 secs 13 0795312 Runs get2 sleepTime 53 165 secs 2 8099523 Runs get3 sleepTime 88 314 secs 4 6676973 Runs Indiv Activities pl i0 Comp think lambdal sleepTime 17 787 secs 0 9401039 pl_il_Comp think lambdal sleepTime 83 844 secs 4 4314425 5 pl i2 Comp think lambdal sleepTime 187 636 secs 9 9172051 5 pl i3 Comp think lambdal sleepTime 338 937 secs 17 9139811 p2 i0 Comp think lambda2 sleepTime 8 988 secs 0 4750466 5 p2 il Comp think lambda2 sleepTime 54 511 secs 2 881093 p2 i2 Comp think lambda2 sleepTime 154 33 secs 8 156869 p3 i0 Comp think lambda3 sleepTime 9 232 secs 0 4879428 5 p3 il Comp think lambda3 sleepTime 35 921 secs 1 8985479 5 p3 i2 Comp think lambda3 sleepTime 196 5 secs 10 3856979 5 tomp444 pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkik KKKKKKKKK SIM RESULTS KKKKKKKK KKKK KK KK KK KK KK KK KK KK KK KK KK KK KK GenSkel tomp444 115 Runs 34 AVG 1 6168529 secs run Runs 120 AVG 1 804975 secs run Runs 172 AVG 2 1076802 secs run Runs 2 AVG 0 598 secs run Runs 29 AVG 0 973 secs run Runs 93 AVG 0 8754409 secs run Runs 5 AVG 0 442 secs run Runs 71 AVG 0 6201127 secs run Runs 368 AVG 0 6519511 secs run 5 5 5 302 AVG 0 228606 secs run 888 AVG 0 3900372 secs run 888 AVG 0 2786802 secs run 221 AVG
117. r Chapter 6 Implementation of the Translator 55 Graham Clark created a lexer for the PEPAroni tool Clark et al 1999 using a JLex like tool which allows the quick generation of Java lexical analysers The lexer was also incorporated into the PEPA Workbench and is now again used in the Transla tor as the scanner for the parser 6 4 Parsing Unlike the lexer the parser could not be used as it was The previous PEPAroni work was of use however The parsers used in PEPAroni the PEPA Workbench and this Translator are all generated by the Java CUP program from the same grammar Whilst the three parsers use the same grammar what they do with the input and the objects they create are different For example the Translator needs to create a completely different type of object and perform different analysis than the Workbench does when it comes across a Rate definition an Action or the constructs in the composition line The CUP program takes as input a grammar specification with embedded com mands for each rule and generates the Java parser accordingly The definition of the grammar can be quite tricky so being able to re use the grammar whilst defining dif ferent actions sped its implementation The parser creates five types of object ProcObj Process objects are linked to each other in a tree like structure and represent the PEPA constructs Prefix Choice Hiding and Cooperation CompScript A Component Script object is created
118. ranch that becomes ready However choosing commits the system to execute that branch it cannot be interrupted by a faster branch that becomes ready later 5 Because the first ready branch wins the choice method necessarily needs a pause to allow participants of shared Actions to join Otherwise individual Actions would unfairly dominate choice branching as they are always ready The length of this pause is defined as a constant value in the Component class at present set to 100 milliseconds The first three mechanisms allow the PEPA2Java system to mimic a PEPA system perfectly but the last two are not ideal they cause some models to execute incorrectly Chapter 7 gives more detail 5 5 Components and Scripts The Component class extends the Java Thread class each is started on system startup Each Component represents one of the Components as defined in the composition line of the PEPA model A Component class on its own defines no behaviour For this the CompScript interface is used Chapter 5 Prototype B Specification amp Implementation ofthe PEPA2Java API 33 The CompScript interface is similar in idea to the Runnable interface It defines a single method actions The method takes no argument but crucially it must return a CompScript object reference Each Component has a reference to a CompScript object which is initially set by the Component setStartScript method The Component run method calls the current Co
119. rd libraries Additionally it has native support for multiple threading and remote method invocation As an object oriented language it allows us to take advantage of inheritance making it simpler to run a PEPA model as a Java process whilst hiding all the underlying mechanics from the user Should the techniques developed prove valuable it would be possible to re use the methodology with similar PEPA equivalent APIs for other programming languages The Translator s output could then be modified to cater for these new APIs 1 3 Project Objective The aim of this project is to produce two things 1 an Application Programming Interface API for running PEPA systems in Java and 2 a Translator which takes as input any PEPA model and produces a set of Java classes that use the API to run with the same functional and performance char acteristics as the PEPA models they are based on Chapter 1 Introduction 3 1 Design the system in PEPA 2 Evaluate and refine the resulting model with the PEPA Workbench 3 Translate the model to its PEPA2Java equivalent using the PEPA2Java Transla tor 4 Confirm the Java skeleton is behaving correctly by running it with the PEPA2Java Simulator package enabled 5 Flesh out the skeleton by implementing actual functionality in the Actions and replacing the probabilistic branching with deterministic behaviour 6 Use the Simulator package to ensure the system is still running as it sh
120. rmines which of those activities to execute A compositional approach allows the system to be analysed at varying granularities depending on the degree to which components are broken into sub components The macro behaviour of the system will remain the same The components represent the state of the system and the activities represent the transitions Activities perform actions either individually or as part of a cooperating set Each activity has an associated rate The rate at which an action is carried out is determined by the rates of the participating activities A rate may be specified as a sample from an exponential distribution or left unspecified and denoted T TOP T means the component is a passive participant in the Action Passive participants rely on actively partipating components to execute the action Exponentially distributed rates give the process algebra its probabilistic behaviour making it suitable for performance modelling and also allows activities to be memo ryless This memoryless property means that the time to the next event is independent from the time of the last event occurring Therefore it can be used to model activities which continue their execution each time they are resumed after interruption as well as activities which restart their execution from scratch after each interruption Race conditions are used to determine the branching in the system if multiple activities participate in an action the one to finis
121. rrMsg public void loop Appendix B Prototype A Example the Client Proxy Server System switch choice proxyRequest proxyRequest case 1 call proxyRequest call proxyReply break case 2 call proxyRequest call serverRequest call serverReply call proxyReply break FR RH E s oh 2 ohe ok ok he k k k k ik k k k k k k k ohe ohe ohe ohe ohe ohe ohe ohe EE EEG Server java ole he he ske ske sk sk k k K PE RF ok oh ok ohe oh 2 2 ok ok he k k k k k k k k k k k k ohe ohe ohe ohe ohe ohe ohe ohe package csp import prototypeA cp Title Client Proxy Server Prototype 2 lt p gt lt p gt Description lt p gt lt p gt Copyright Copyright c 2002 lt p gt lt p gt Company Edinburgh University lt p gt author K J R Powell version 1 0 91 Appendix B Prototype A Example the Client Proxy Server System 92 public class Server extends Component 4 Activity serverRequest serverReply public Server super Server true public void init serverRequest Ref getActivity serverRequest serverReply Ref getActivity serverReply try addMeTo serverReguest true addMeTo serverReply true catch AlreadylnitializedException aie aie printErrMsg public void loop call serverRequest call serverReply pekee kok kk ks oko k se ke kk EEE Sim java PPH PE ee o kok ok kok kok kok kk ks kok kkk kk package csp
122. rray prefix creating and updating Makefiles Default makefile name Java compil Java runtin ler command ne command Workbench HOME from model Classpath subdirectory ch Act ch Rate Makefile javac java MT EN LI SHOME HOME pepa Pepa2Java lib distributions jar Appendix E The Modified PC LAN 4 Model lambda 0 1 omega 3 mu 1 sigma 10 PR1 arrive lambda requestl sigma PR1 PC10 reguestl infty servel infty PC10 walkon2 infty PC10 PR2 arrive lambda request2 sigma PR2 PC20 request2 infty serve2 infty PC20 walkon3 infty PC20 PR3 arrive lambda request3 sigma PR3 PC30 request3 infty serve3 infty PC30 walkon4 infty PC30 PR4 arrive lambda reguest4 sigma PR4 PC40 reguest4 infty serve4 infty PC40 walkonl infty PC40 104 Appendix E The Modified PC LAN 4 Model 105 S1 walkon2 omega S2 servel mu walk2 omega S2 52 walkon3 omega S3 serve2 mu walk3 omega S3 53 walkon4 omega S4 serve3 mu walk4 omega S4 54 walkonl omega Sl serve4 mu walkl omega S1 PC10 lt reguestl gt PRI lt gt PC20 lt reguest2 gt PR2 lt gt PC30 lt reguest3 gt PR3 lt gt PC40 lt reguest4 gt PR4 walkonl walkon2 walkon3 walkon4 servel serve2 serve3 serve4 gt Sl Appendix F Model Evaluation Results The
123. rs such as deadlock However because there is usually no clear parallel between modelling language constructs and the facilities provided by programming languages there is the danger that the design of the system may veer away from the design suggested by the model once actual implementation of the system begins As a result the possibility of reintroducing unwanted behaviour into the system arises Automating the process of the model s translation to a skeleton implementation means the desirable performance and behavioural properties of the model are main tained This working skeleton would provide a sound framework for completing the Chapter 1 Introduction 2 implementation of the system whilst ensuring the system characterisics remain true to the high level model 1 2 PEPA and Java Performance Evaluation Process Algebra PEPA is a stochastic process algebra that uses probabilistic branching to model a system It includes timing attributes for all system activities and uses race conditions to determine state transitions This allows PEPA to evaluate performance as well as testing for correct functional behaviour in a model It can model parallel composition and synchronisation behaviour These features mean it is well suited as a high level design aid for concurrent and distributed systems Java is the target language because of its flexibility its widespread adoption its mobility between platforms and its rich set of standa
124. s A Script implements CompScript 4 Activity ch Act 0 m Activ n Activ o Activ Rate ch Rate 0 new Rate 1 0 new Rate 2 0 new Rate 3 0 Activity ch Act 1 x Activ y Activ Rate ch Rate new Rate 0 5 new Rate 0 5 public CompScript actions switch choice ch Act 0 ch Rate 0 4 case 0 m Activ joinAt new Rate 1 0 return a Script case 1 n Activ joinAt new Rate 2 0 return a Script case 2 o Activ joinAt new Rate 3 0 switch choice ch Act 1 ch Rate l 4 case 0 X Activ joinAt new Rate 0 5 return a Script case 1 y Activ joinAt new Rate 0 5 return a Script throw new Error Problem with choice no valid case returned throw new Error Problem with choice no valid case returned Figure 6 6 CompScript generated from A m 1 0 A n 2 0 A 0 3 0 x 0 5 A y 0 5 A Chapter 6 Implementation of the Translator 63 6 6 1 Generating Valid Class Object and Package Names To generate names for the different classes objects files and directories the Translator takes the identifiers from the PEPA model and performs some manipulation Naturally all the names to be used in the Java output must be legal a Java identifier may begin with any alphabetic character a currency symbol such as or an underscore The rest of the identifier must also be made up of these characters but may also include numeric characters Therefore the
125. s used to determine which API implementing pack age the model should run with If the flag is set to true the Simulator package is imported otherwise it is the Barebones package which will be imported The import statements may of course always be changed manually later Overwrite flag If this flag is set to true any files in the output directory with the same name as newly created files will be overwritten If set to false the Translator will exit without overwriting the existing files The default value is false Note that the Makefile entry will be created appended regardless of this flag Write files flag If this flag is set to false the Translator will perform as usual except that no files will be written to disk This is used mainly for debugging and accordingly is not very useful unless the debug level is set high Simulator Speed and Debugging Level The initial speed and debugging level at which to run the Simulator These have no effect on the Barebones package Verbosity Additionally the debug level of the Translator may be set on initialisation Chapter 6 Implementation of the Translator 65 6 7 1 Automatically Generated Makefiles In order to make the generated PEPA2Java model package easier to compile and run a Makefile is placed in the output path directory usually models p2 jgens if there is not already one there If a duplicate entry is found in the already existing Makefile it will be replaced The c asspa
126. secs Runs 2 6285512 5 119 Runs 69 AVG 0 251971 secs run Runs 37 AVG 0 2113514 secs run Runs 37 AVG 0 2004054 secs run 2241739 secs run 1947273 secs run Runs 23 AVG 0 Runs 22 AVG 0 77 0049272 11 725313 3 1536776 Runs 25 AVG 9 3646 secs run 60 AVG 0 5941333 secs run Runs 59 AVG 0 1625085 secs run Runs 84 AVG 0 2221548 secs run Runs 84 AVG 0 2769167 secs run Runs 58 AVG 0 2648621 secs run 49 7987746 12 508577 Runs 143 AVG 0 7156084 secs run Runs 142 AVG 0 1810141 secs run Runs 70 AVG 0 2128 secs run Runs 70 AVG 0 2814286 secs run Runs 72 AVG 0 2272222 secs run Runs 72 AVG 0 2435139 secs run 21 8037129 Runs 142 AVG 0 1344859 secs run Appendix F Model Evaluation Results 120 testl4 pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkk kkk k k SIM RESULTS eeeeee kokokok kok kok kok IO IO IO kok GenSkel test14 Total sleeptime 642 681 seconds Actions reglockll sleepTime 88 077 secs 13 7046217 Runs 348 AVG 0 2530948 secs run writelockll sleepTime 87 669 secs 13 6411377 Runs 348 AVG 0 2519224 secs run reglock12 sleepTime 57 617 secs 8 9651009 Runs 218 AVG 0 2642982 secs run writelock12 sleepTime 53 147 secs 8 269577 Runs 217 AVG 0 2449171 secs run Indiv Activities txnl i0 Comp fork wlxrl2 sleepTime 356 171 secs 55 4195627 Runs 566 AVG 0 6292774 secs run testl5 pepa kkkkkkkkkkkkkkkkkkkk
127. secs run wll sleepTime 149 964 secs 11 5495607 Runs 426 AVG 0 3520282 secs run Indiv Activities txnl i0 Comp f al sleepTime 867 583 secs 66 8173861 Runs 427 AVG 2 0318103 secs run test22 pepa kkkkkkkkkkkkkkkkkkkkkkkkkkkkkk KKKKKKKKK SIM RESULTS KKKKKKKK KKKKKK KK KK KK KK KK KK KK KK KK KKKK KK GenSkel test22 Total sleeptime 1193 328 seconds Actions Indiv Activities a_i0_Comp a m sleepTime 375 132 secs 31 435783 Runs 48 AVG 7 81525 secs run a_i0_Comp b n sleepTime 818 196 secs 68 564217 Runs 47 AVG 17 4084255 secs run Bibliography Appel 1998 Appel A W 1998 Modern Compiler Implementation in Java Cam bridge University Press Clark et al 1999 Clark G Gilmore S Hillston J and Thomas N 1999 Expe riences with the PEPA performance modelling tools IEE Proceedings Software 146 1 11 19 Special issue of papers from the Fourteenth UK Performance Engi neering Workshop Fotis 2001 Fotis S 2001 Enhancing the PEPA Workbench with simulation and and experimentation features Master s thesis School of Computer Science Divi sion of Informatics The University of Edinburgh Gilmore 2001 Gilmore S 2001 The PEPA Workbench User s Manual LFCS University of Edinburgh Gilmore and Hillston 1994 Gilmore S and Hillston J 1994 The PEPA Work bench A Tool to Support a Process Algebra based Approach to Performance Mod elling In Proceedings
128. sed throughout the implementation wherever an object must wait on a condition being true It is used for example in choice checking when a Com ponent is waiting on any branch to become available for running or when an Action is waiting for all cooperating Components to join This replaces the unnecessary and inefficient constant re checking of conditions checking only occurs after an influ encing condition has changed The Lock class is more complex and is intended to replace the object monitor when multiple locks are required to be held simultaneously It is specifically built for use in the choice method It defines two public functions request and release which respectively request the lock and release it Requesting a lock holds the caller until the lock is available The method locks the object again and returns Releasing the lock allows the next waiting requester to acquire the lock Note however that there is no guarantee of fairness the lock will go to one of those waiting but not necessarily the one that has been waiting longest Because locks are held only very briefly inside the Component choice method this is not a problem This functionality on its own adds no new behaviour but the class specifies several protected methods that do The Lock getLockers Activity method takes a multi set of Activity objects and returns a globally sorted set i e no duplicates of the Lock objects ofthe Actions referred to by those Activit
129. sleeptime 166 673 seconds Actions Indiv Activities a_i0_Comp m 1 0 sleepTime 28 88 secs 17 3273416 Runs 13 AVG 2 2215385 secs run a_i0_Comp n 2 0 sleepTime 19 539 secs 11 7229545 Runs 18 AVG 1 0855 secs run a i0 Comp o 3 0 sleepTime 14 671 secs 8 8022655 Runs 23 AVG 0 6378696 secs run a i0 Comp x 0 5 sleepTime 74 183 secs 44 5081087 Runs 13 AVG 5 7063846 secs run a i0 Comp y 0 5 sleepTime 29 4 secs 17 6393297 Runs 10 AVG 2 94 secs run p2j choiceyielding pepa two sets of results Appendix F Model Evaluation Results 110 first with choicetime 100 and speed normal kkkkkkkkkkkkkkkkkkkkkkkkkkkkkk KKKKKKKKK SIM RESULTS KKKKKKKK KKKK KK KK KK KK KK KK KK KK KK KKKKKK KK GenSkel p2j_choiceyielding Total sleeptime 641 919 seconds1414 Actions m sleepTime 20 155 secs 3 1398042 Runs 14 AVG 1 4396429 secs run n sleepTime 302 401 secs 47 1089031 Runs 148 AVG 2 04325 secs run Indiv Activities b i0 Comp i 1 0 sleepTime 319 363 secs 49 7512926 Runs 166 AVG 1 9238735 secs run p2j choiceyielding pepa two sets of results second with choicetime 500 and speed fastest kkkkkkkkkkkkkkkkkkkkkkkkkkkkkik KKKKKKKKK SIM RESULTS KKKKKKKK KKKKKK KK KK KK KK KK KK KK KK KKKKKK KK GenSkel p2j_choiceyielding Total sleeptime 339 335 seconds Actions m sleepTime 79 142 secs 23 3226752 Runs 327 AVG 0 2420245 secs run n sleepTime 114 75 secs 33 8161404
130. structs and Component identifiers e The composition line is also the only place that Cooperation constructs may be placed e Prefixes additional Choices or grouping structures holding either type of con struct are the only valid branches of choice constructs This is because the choice method chooses by comparing the determining Rate of the Action of the Activities of each branch Choices may have any number of branches and may also be nested as long as there is always be an Activity to evaluate for each branch For example HA a 1 A b 2 B c 3 d 4 D e 5 E is a valid construct but fA Boot L20 is not regardless of what B defines 6 3 Lexing Developing a lexer and parser for the PEPA input was straightforward because the PEPA2Java Translator accepts the same input syntax as the PEPA Workbench see figure 6 2 Chapter 6 Implementation of the Translator 54 program declaration seg component composition idseg rate id int declaration composition id seg component seq component idseg hiding seg component seg component choice id rate seg component prefix id variable seg component grouping seg component lt idseg gt seg component seg component lt idseg gt composition composition id id idseg id int infty alphanumeric seguence unsigned numeric seguence Figure 6 2 The Java PEPA Workbench s PEPA Gramma
131. t of all the Rates Activities and CompScripts this Component uses These will be defined as fields in the Component class Next to generate the CompScript output classes the CompScript createScript method is called on each CompScript object This method will recursively traverse the ProcObj tree generated by the parser and translate it into PEPA2Java commands A small example should help to illustrate Consider the input model A m 1 0 A n 2 0 A o 3 0 x 0 5 A y 0 5 A This results in the CompScript A Script given in figure 6 6 Handling references to sequential process definitions is simple they are translated into return statements that return the name of the CompScript object which defines the process behaviour Chapter 6 Implementation of the Translator 61 This exits the current actions method and causes the parent Component to call the actions method of the newly returned CompScript For Prefix constructs the result is also quite simple the appropriate joinAt Rate method call is inserted Processing a Choice construct is more difficult because any number of branches is allowed However since each Choice ProcObj has only two branches some account must be kept of whether each encounter with another Choice ProcObj is part of a new choice block or adding another branch to an existing choice block Therefore as well as receiving a reference to the current ProcObj a reference to the previous ProcObj
132. th the directory path to the Workbench and the com mands for running the Java compiler and runtime are held as default constants in the Main class of the translator see Appendix D This Makefile contains a target entry for each model generated In order to compile and run any model found in a package subdirectory of the one holding the Makefile the command make run ModelName can be issued from the command line This is useful for running Barebones models because these models cannot be run from the PEPA Workbench as they contain no GUI there would be no way to halt a running model Additionally the last model translated is also the default for the Makefile so typing make is sufficient 6 7 2 Running the Translator from the command line The Translator may be initialised from the command line in case the only required argument is the name of the input file The Translator should be run by issuing the command java Pepa2Java translator Main in PEPA input file Ensure the CLASSPATH environmental variable is defined to include the two jar files in pepa Pepa2Java lib Alternatively the classpath may be passed directly to the java interpreter with the classpath argument The optional command line arguments are in Pepa Input File File to translate Required out output path A lt packagename gt subdirectory will be created here skel Output Skeleton System not Simulation OW If
133. ther Components the opportunity to join the Action before deciding The value of choice pause is also fixed to a value which gave good results for the models However perhaps the pause could be related to the length of the slowest branch or be drawn as a random sample from an exponential distribution None of these suggestions are ideal but they would improve the situation The second problem being the more serious can thankfully also be solved Unfor tunately it requires extra steps and therefore introduces a higher overhead to running The solution lies in a more sophisticated commital algorithm similar to the two phase Chapter 7 Evaluation 81 commit protocol seen in distributed systems Using this would avoid Bidder1 com mitting without guarantee that Node is also going to commit This would necessitate an extra stage in the choice algorithm between the ready to run and the committed to run stages Each Component would advertise the branch it had chosen by removing the ready to run flags from the other branches and setting a chosen flag on its choice It would then keep monitoring the other choices until the full set of runners had committed or chosen the Action it had chosen Only at this point would it change from chosen to commit If before committing whilst monitoring the other branches it noticed another branch was ready to run it could change its choice Criticall
134. tion specifying new actions for each rule the parser comes across CUP was then used to generate a new parser suited to the project s needs 3 4 2 The Translator s Data Structures After parsing the Translator has all the information from the model available to it However this is not yet in the correct form for easy generation of a skeleton There fore the Translator first scans the various data structures it has built during parsing to determine how many components there are whether any of them are multiple instances of the same type how many actions there are which ones are shared which ones are private and the synchronisation sets It collects this information and stores it in new data structures of a friendlier form making it more easily available to the processes generating Java code On the whole this approach needs more memory but not excessive amounts Pro ducing a correct translation is of higher priority than minimising memory usage In any case once the Translator exits on completion the memory will be made available by the garbage collector should it be needed for running a model Chapter 3 Design 16 3 4 3 Integration into the PEPA Workbench Integration into the PEPA Workbench is straightforward a matter of adding a menu item which opens a Translator dialogue window From this window options such as translation type debug level and simulation speed can be set Buttons in the window allow the model
135. to be translated compiled and run The model translated is the one that is currently being worked on in the Workbench Keeping the Translator in a separate package and using a separate pop up window means that it will be easy to integrate in different versions of the Workbench or removed if necessary 3 5 Evaluation The evaluation has been carried out on the models produced by the Translator to see whether they compile and run correctly and also to see whether their performance is the same as predicted by the Workbench Evaluation has been carried out on the numerous existing PEPA models already distributed as part of the Workbench Some additional models which test areas not covered by the existing models were also created Though time has not allowed it would be worthwhile attempting to take a simple model of a practical application through the full process shown in figure 1 1 One such example might be to take a very simple Client Server model where the Server controls a resource such as a printer and turn it into a working Java system This exercise could highlight any problems with this idealised process of design and implementation Chapter 4 Prototype A Specification amp Implementation of a Flawed API 4 1 Overview The process of implementation is one of discovery of hacked solutions and of re design Designing the perfect system is impossible and this implementation is no ex ception Various ideas were tried an
136. tool for evaluating and exploring a model By adding a translation function it will enhance the tool s capabilities as a design aid extending its use into the early implementation stages of a system 2 3 2 Pepa2Ada The Pepa2Ada translator Gilmore et al 1996 is a tool for producing PEPA equivalent Ada programs Although the paper describing the process was very useful in provid ing pointers and the possible pitfalls Java is a very different language from Ada and so the approach taken was also different For example the problems that needed to be addressed regarding internal choice Gilmore and Hillston 1996 were not of rele vance to this project Also using Java s inheritance means most of the mechanics of synchronisation and choosing can be hidden and should make it easier to extend an automatically generated program Chapter 3 Design 3 1 Overview and Design Decisions The project plan is made up of six stages of which implementation was always going to be the most time consuming and challenging 1 Orientation and Exploration study related work investigate the issues surround ing the project and identify possible designs 2 Design select and finalise a design then review it with the supervisor of the project 3 Implementation bring the design to realisation 4 Review and Refinement scrutinise the implementation and make any necessary adjustments and corrections 5 Extension and Improvement as far
137. tself to fix the problem a modified version of the PC LAN 4 model named p2j_PC LAN4 mod pepa was created and runs without problems The problem is explained in full in the next section Big The Big model results in deadlock The problem concerns the mechanisms used to replace race conditions and determine choices It is also described in the next section The PEPA2Java translations of all the other models performed as expected 7 4 Evaluation of Results and Suggestions for Improve ment Whilst the PEPA2Java API implementing packages do a fine job at running almost all the PEPA models some problems have been found These are caused by one aspect of the implementation simulation of the race condition as described in section 5 4 The choice algorithm was a very difficult one to develop and it is still not perfect It involves complex checks for readiness of branches locking and unlocking of large numbers of objects wait notify mechanisms and prioritizing of branches Despite the careful design of the algorithm there remain two flaws described below Chapter 7 Evaluation 76 7 4 4 Drawbacks to the choice pause Mechanism The choice pause mechanism described in section 5 4 leads to undesirable variation in execution patterns For example the ability of shared Actions to run when competing against individual actions depends on two factors the speed of the simulation and the length of the choice pause The shorter
138. ty write 19 75 of the time State 1 is the system state when both Components are executing the read Activity Note that each state is a global snapshot describing the behaviour of every Component in the system at that point It can be very difficult to interpret the result of the steady state analysis of even moderately sized models as PEPA is prone to state space explosion For example by adding an extra P Component to the system which is wholly independent to the other two doubles the number of states from four to eight If an intermediary Activity is added i e read analyse write the number of states jumps from eight to 27 The ability to get such exact results is very useful but if one considers that the PAPM model has six components but 1557 states and 6155 possible transitions between states it becomes clear that analysing such in depth results for more complex systems can be very tricky The results returned from the PEPA2Java Simulator are quite different It does not return the type of global snapshot that the Workbench does hence the name Simple Analysis It returns the behaviour of the Actions the parts which will perform the actual work of the finished system Some sample results of it running the same model are Total sleeptime 170 871 seconds Actions Chapter 7 Evaluation 71 Indiv Activities p_i0_Comp read m sleepTime 47 432 secs 27 7589527 Runs 91 AVG 0 5212308 secs run N
139. ur as we can see from the Rates that Action m is the fastest of the three Actions The yielding increases the probability of two choice blocks to coming together at the same time and choosing Action m 5 9 2 Locking and Deciding After pausing once the Thread resumes execution it will attempt to gain the Locks of all the Actions it is considering joining As described in section 5 3 the Locks are Chapter 5 Prototype B Specification amp Implementation ofthe PEPA2Java API 44 requested in a globally sorted order meaning deadlock cannot occur Without a global ordering for example Component A holding Lock 1 and requesting Lock 2 will wait forever for Component B to release its holding of Lock 2 because B may be waiting forever to acquire Lock 1 from A This circular deadlock will not occur if Lock 1 is always requested before Lock 2 by all Components Once the Thread acquires the Locks of all the Actions it is considering it will create a null reference which will eventually point to the fastest Activity it finds and a reference named best to the fastest Rate it has found These are initially null and TOP respectively It then performs the following steps on each Activity 1 Set the Rate of the Activity to be an almostClone same Rate different sample of the one found in the corresponding position in the Rate array This is neces sary for cases suchas A x 1 x 2 where there are different Rates for identical Activiti
140. use again and the process beginning with the locking will repeat until a choice is returned If a winner is chosen all the losers Rates are resampled to avoid a branch being passed over unfairly again and again Notice that this includes the resampling of allthe branch s cooperators resampling a T rate has no effect and if that passive Activity s partner has sampled a very big sleep time that branch may be skipped many times The requesting and releasing of locks is necessary to avoid deadlock when there is more than one Component considering joining the same Action at the same time For example consider the following A m 1 n 1 m T m n T At the beginning both A and B register their interest in perhaps joining their Ac tivities m and n If they are allowed to continue without first acquiring the locks to the Actions m and n their concurrent execution might mean A chooses m whilst B chooses n This is possible because all the ready flags are still set to true after one Component has chosen whilst the other is still choosing Locking ensures a ready flag is only ever set to true when it should be by controlling access to the critical section 5 10 Rates and Sleep time The Rate object is least changed between Prototype A and Prototype B Each Rate object contains an ExponentialDistribution object Siegrist and Duehring 2001 and is used to calculate the period that an Action runs for as well as determin
141. vity objects and an array of their respective Rate objects It returns an integer which is the position in the array of the chosen Activity The choice method should be used in a switch statement just as it was in Prototype A see section 4 3 1 for the switch syntax However this implementation of choice is quite different from that in Prototype A There is no prioritization of choices as there was in the first implementation Rather this implementation sticks more closely to the original PEPA mechanism the fastest branch which is ready to run is the one that is chosen Determining the rate of individ ual Activities is simple there is only one Rate object However in shared Activities the Rate of the Action is determined by the slowest actively participating Activity In section 5 10 2 the mechanism for finding the correct determining Rate for an Action in a choice block is described Only those Actions which are ready to run are consid ered In order to discover which Actions are ready to run without the Component first committing to join any of them a two phase process is carried out Chapter 5 Prototype B Specification amp Implementation ofthe PEPA2Java API 42 serve Action Activit Clientl s serve Activit Client2 s serve Client3 s serve Activit Activit Figure 5 3 Synchronization Tree of Client1 Client2 Client3 lt serve gt Server Chapter 5 Prototype B Specification amp Implementation ofthe PEPA2Java
142. xcept that in the case of the Barebones package the de bugging statements are disabled and the Simulator window class is removed They therefore run identically but the Barebones package requires less overhead as there is no Simulator window to update All fields and methods are protected where appropriate to prevent the models from being able to disrupt the correct functioning of the underlying system 3 3 1 Simulating the Race Condition The race condition see section 2 1 can be viewed as a form of speculative execution of multiple branches There are two forms of branching in PEPA Choice constructs are the obvious form The more subtle form is the case where multiple Components are all vying for the chance to cooperate on some shared Action where not all may cooperate at the same time An example of this is two clients trying to synchronise with one server A model of this seen will be seen in section 4 4 1 Using race conditions means that in cases of branching all branches are specula tively executed and the first one to finish is the winner The winning branch then dic tates the ensuing behaviour of the Component whilst all other executions are aborted Using speculative execution in the form of race condition is nor an option when pro ducing skeletons that are to become full implementations in which each Component represents a single Thread of computation Speculative branching would mean the forking of execution and aborting of the
143. y though to avoid any other Components getting stuck in a deadlocked choice this Component would only be allowed to change its choice if no other members in its chosen branch had changed from chosen to committed Being able to change would avoid the deadlock in Big It would not affect the running characteristics except for the extra processing stages the Component did not commit to running the Action but only chose it The difference is that the chosen Action would not be able to run until all members committed Finally the requesting and releasing of locks using the current globally ordered mechanism would ensure that switching choices at any point would not cause deadlock This solution seems quite complex and would certainly be overkill for most mod els which use only basic choosing However if the PEPA modelling system were to be used to design genuine concurrent or distributed systems such a mechanism in PEPA2Java would be needed to avoid possible deadlock 7 5 Suggestion for Extension 7 5 1 Full Stated based Analysis In addition to the Simple Analysis already included in the Simulator package the ad dition of a method for calculating the mean residence times of the states as done in the Workbench would be very helpful as it would allow statistical equivalence testing between the two One way of doing this for example would be to parse the state table Chapter 7 Evaluation 82 stru

Download Pdf Manuals

Related Search

Related Contents

Philips 69191/14/PH  Samsung PL200 Bruksanvisning  F-Pro trabajando - Endata Argentina  StarTech.com 6 ft 14 AWG Computer Power Cord Extension - C14 to C13  ポラリエ-ミニポルタアダプター 取扱説明書（247KB）  RESISTRON - ropex.de  FinishLynx Bronze System  Temperature controller Sequence Timer  service manual  Zebra 105934-059  

Copyright © All rights reserved. Failed to retrieve file