ON PETRI NET APPROACH TO MODELING, ANALYSIS AND SOME DESIGN ASPECTS OF SOFTWARE SYSTEMS

Abstract

Over the last two decades, Petri nets have emerged as a widely acceptable modeling tool for representing and studying the asynchronous and concurrent activities in the systems. Petri nets can be viewed as a very useful model for describing and analyzing the various kinds of computer systems. An interpretation assigned to the entities of Petri nets, viz. places, transitions and tokens, plays an important role in making the Petri net, a powerful tool. It is inherent in the modeling of the Petri nets that the dynamic behaviour be taken into consideration, because of the movement of flow of information in the form of tokens flow from one location to another in the model. It is interesting to note how the Petri net as a modeling tool is versatile enough to represent wide ranging aspects of computer systems- This, in fact, is primarily due to the powerful modeling capability of the Petri nets which has been exploited in this thesis- An interesting problem concerning the use of Petri nets as a tool for the representation, analysis and design,would be the derivation of interpretations,which may be assigned to the Petri net entities in the model depending upon the requirements of the systems- In the present thesis, an interpretation has been sought for different kinds of programming languages

both high level and low level. This has been achieved by deriving the appropriate interpretations of various structures and modules of the programming languages in terms of the Petri net entities. This problem has further been tackled from another point of view, i.e. by consider ing both unstructured and structured programs. Once the interpretation of- various structures and modules of different languages, in terms of the Petri net entities has been soughts it becomes easy to model a language by Petri nets, and this also provides a common basis for modeling and representing the description of different languages at different levels of abstractions. During the modeling process, a concept of dummy or pseudo transition is intro duced which is used for modeling the transfer of the data, either between two programs or between a program and Input-' Output Buffer. Having transformed a language into appropriate Petri net model, the modeled system is then subjected to the evaluation of various software parameters through the performance analysis of the models. The software parameters considered are the execution time, reliability, etc. Two criteria for the evaluation of these software parameters in the model, have been considered in this thesis, namely, complexity measure and software measure. The different complexity measures, considered here are: execution time, cyclomatic number, simple reachable path and knot. A

different methodology based on the reachability concept of state equation of Petri nets has been presented for the determination of cyclomatic number of a program model. The problem of execution time as a measure of complexity has been considered by associating it with the transitions representing the statements or operations or subroutines^ Other measures of program complexity have also been considered. The evaluation of program complexity aids the programmers in the developments of the programs within these constraints (i.e. measures). Another criterion of program complexity has been proposed and is termed as software measure which includes not only the execution time,but also the more important attribute of performance i.e. the reliability of the program. A technique utilizing the Petri net transforma tions of serial, parallel and loop structures for the determination of software measure of a program model,is presented. A class of special configurations are further proposed for the evaluation of software measure of the program models,which cannot be covered fully by the above, mentioned structures. The approach is applicable to both single-input single-output and multi-input multi-output program models. Further, this concept is extended to postulate a simple procedure for the evaluation of soft ware parameters of general structured program models. The determination of software measure helps the program designers, especially in making the trade off decisions between the reliability, performance, cost etc. Another software aspect considered in the thesis jis the modeling of a low level language, typically the assembly language. The transformation to an assembly language,in fact, forms an intermediate stage during the compilation process. The assembly language after the process of Parsing and Code generation needs to be optimized,to generate minimal assembly code so as to reduce the execution time. Hitherto this was attempted mostly by using tabular comparisons. The present thesis discusses the optimization problem using Petri net model,developed for the assembly language. A mathematical technique based on the state space representa tion of Petri nets has been proposed for obtaining an optimal assembly language code during the compilation process for a class of instructions. The other important problem regarding the software aspect associated with the computer software and which is currently inviting attention from the software designers* is the detection of parallelism inherently present in the sequential software systems. The identification of para llelism in a sequential process,provides a useful information for the design of system software in a parallel processing environment. The basis for the detection of parallelism

in the modeled system,is the identification of the various locations of shared data, in the model. The Petri net based approach presented is general and is applicable to any sequential software system which has got inherent parallelism potential for adoption amongst the different processes,in a multiprocessing environment. Towards this direction, a specific cross assembler that was available, has been modeled and the philosophy of detection of parallelism is illustrated. Considerable interest is being shown recently in the area of data bases. The primary aim in the software develop ment for the data bases is to represent a data structure in such a way that information retrieval is achieved in minimum time. The various data structures are- Network, Hierarchical and Relational. Prominent amongst these is the network structure.The concept of Petri net modeling has been extended for the data base systems through meaningful interpretation of various structures. The conflict aspect in Petri nets has been given a mathematical interpretation to suit its application to the data base structures. A new class of application for the reachability equation has been proposed. Based upon this, an algorithm has been postulated to access the data paths between any two specified nodes in the data base model, with an aim that it may provide useful data for the design of data, bases. vii To conclude, the present thesis is a step towards the direction of modeling of computer software systems through Petri nets- This has been made possible by giving appropriate interpretation to various entities of Petri net. The systems so modeled have been then subjected to the analysis,and useful design criterion obtained.