Abstract:
In a method and a system for simulating a distributed system, a target system is divided into asynchronously operative processes so that the simulation of said asynchronously operative, distributed system may be comprehended with the changes in the data structures by using (1) a whole structure table indicating what certain of the said divided processes can provide for other processes, (2) a system structure table representing certain of said processes with a Petri net model, and (3) a data structure table storing the data structures of input and output processing data.

Description:
This application is a continuation of application Ser. No. 730,862, filed May 6, 1985, now abandoned. 
    
    
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to a function simulation method and an apparatus therefor and, more particularly, to simulation method and apparatus which are suitable for function simulation of an asynchronously and parallel operative distributed system. In this simulation method, moreover, a Petri net model conducts the simulation of a function to transform the input data into the output data of the system. 
     2. Description of the Prior Art 
     There has not yet been established a method which is suitable for simulating the functions of an asynchronous self-controlled distributed system rather than a synchronous system. 
     The Petri net, a numerical model for describing and analyzing the flow and control of data in an asynchronous, parallel system, was proposed by Petri in 1962. 43 The Petri net model has been widely used and studied. See &#34;Spectral Feature `Putting Petri nets to Work`&#34; (by Tilak Agerwala, IEEE, Computer, December 1979, pp. 85 to 94). 
     Petri nets are expressed by an oriented graph which has two kinds of nodes, i.e., places and transitions. Arcs are oriented from the places to the transitions or vice versa. The places have tokens, and the arrangement of these tokens are called the &#34;markings&#34; of the Petri net model, the first of which is called the &#34;initial marking&#34; of the Petri net. 
     When a system is to be simulated by a Petri net model, the passage of the token through the transition means that data is processed and output. The token indicates data movement, but it does not indicate which data structure has been transformed nor does it indicate what structure it has been transformed into. This has the obvious disadvantage that data transforming procedures which are crucial in the simulation of functions are left undisclosed. 
     SUMMARY OF THE INVENTION 
     An object of the present invention is to simulate function of an asynchronous and parallel system with a Petri net model. 
     Another object of the present invention is to provide a simulation system which can track changes in data structure as the simulation proceeds. 
     The present invention is characterized by dividing a system to be simulated into a plurality of asynchronous process units; by preparing a table for the entire structure with both functions, which are defined as divided processes and other processes, and input/output data; by preparing a system structure table with said processes with a Petri net model; storing the structures of said input/output data in the data structure table; and by conducting simulation with said three tables while displaying, through some means, the procedures or results of said simulation. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram showing the case in which a plurality of cash dispensers are coupled to one host computer; 
     FIG. 2 is a diagram showing the processing of the cash dispenser and the host computer with a Petri net model; 
     FIG. 3 is a detailed diagram showing a portion of FIG. 2; 
     FIG. 4 is a block diagram showing the whole structure of the present invention; 
     FIG. 5 shows the construction of the whole structure table of FIG. 4; 
     FIG. 6 shows the construction of a system structure table of FIG. 4; 
     FIG. 7 shows the construction of a data structure table of FIG. 4; 
     FIG. 8 is a simulation processing flow chart in the system simulation system; 
     FIGS. 9(a) to (g) exemplify transfer of information between the terminals and the host computer and the data structures; 
     FIG. 10 shows the coupling between the host computer and the terminal unit, i.e., the cash dispenser through points in the Petri net model; 
     FIG. 11 shows an example of the whole structure table; 
     FIG. 12 shows a system structure table according to the examples of FIG. 9; 
     FIG. 13 likewise shows an example of the data structure table; 
     FIG. 14 exemplifies a detailed diagram of the host computer which is expressed by a Petri net model; 
     FIGS. 15(a) to (d) and FIGS. 16(a) to (c) exemplify the displays of the simulation procedures and the procedures for movement of tokens, respectively; and 
     FIGS. 17(a) and (b) exemplify the token flags in the functional simulation places. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     The present invention aims to comprehend not only the movements of tokens but also their data transformation procedures and to simulate asynchronous, parallel operation. An example of such a system is considered here where a plurality of cash dispensers for depositing and dispensing money by means of credit cards are coupled to a host computer. 
     FIG. 1 is a block diagram showing the structure in which cash dispensers are coupled to a host computer. This is an example in which a number n of terminal units are connected to the host computer through communication lines. The relationship between one terminal unit and the host computer is expressed by the Petri net models, as shown in FIG. 2. FIG. 2 shows the case in which money is dispensed by using cash cards. 
     In FIG. 2, reference letters T CD1 , T CD3 , T CD5  and T CD7  indicate transition, and letters P CD2 , P CD4  and P CD6  indicate places, both being located at the side of the cash dispenser. Letters P C1 , P C2  and P C3  indicate the communication line places; letters T h3  and T h4  the host computer transition; and letters P h1  and P h2  the host computer places. 
     Let us consider the on-line system of a bank which comprises a host computer and cash dispensers so that information such as account numbers or amount of cash payment is exchanged between host computer and dispenser. The host computer computes and executes balance renewal, and the cash dispensers verify cash cards and accept and dispense cash independently of one another. 
     If the functions of such a system are simulated, the respective components are mixed rather than separated. This makes it impossible to determine the relationship of a particular function to the system or to other functions so that the functions and operations intrinsic to the system cannot be identified and defined for simulation. 
     The processing flow will now be schematically explained. The cash card is received at transition T CD7  ; the card number is read at the place P CD6  ; and the cash card is verified at the transition T CD5 . A cash payment demand signal is generated at the place P CD4  ; payment is received at transition T CD3  ; and the cash payment amount is transmitted to the host computer through the place P C3 . From the transition T CD5 , the account number is transmitted through the place P C2  to the host computer. At transition T h3 , the host computer determines the cash payment amount, the account number and the balance (at T h4 ) after the cash is dispensed, so as to certify the balance (at P h1 ) When predetermined conditions are satisfied, the host computer transmits the cash payment amount through the place P C1  to the cash dispenser so that the cash is dispensed (at T CD1 ) After a series of these processings, the host computer then allows a subsequent card reception demand signal (at P CD2 ). The place P h2  at the host computer indicates maintaining data, i.e., the cash payment amount. Letters P C1  to P C3  indicate memory buffers which can belong to terminals or to the host computer. 
     FIG. 3 shows the transition T CD5  of FIG. 2 in detail. T cd1  indicates reading the user I.D.; T cd2  indicates input of user I.D.; T cd3  indicates verification of user I.D.; T cd4  denotes an error message indicating wrong user I.D. (NG); P cd1  and P cd2  denote user I.D.; P cd3  denotes a place having an input demand. P CD4  indicates the place which is equivalent to P CD4  of FIG. 2 but contains oriented graphic expressions for the transition T cd4 . 
     FIG. 4 is a block diagram of the structure of an embodiment of the present invention. 
     A whole structure table 31, a system structure table 32 and a data structure table 33 are mounted on a memory unit (Me), which stores the data concerning the system to be simulated. A system determining program 34 reads in the simulation initializing point in the target system, which is determined by an input-output device so as to prompt the simulation system 30. 
     An information input program 35 displays the information required of the simulation system 30 as the input demand in the input-output device 36 and inputs the necessary information from that device to the simulation system 30. This simulation system 30 simulates, when it is informed of the target system and the simulation initialization point from the system determining program 34, the system which is stored in the whole structure table 31, the system structure table 32 and the data structure table 33, to display the procedures in the input-output device 36. 
     Next, the structural components of FIG. 4 will be described. The whole structure table 31 is shown in FIG. 5. A process distinguishing name, hereafter called the &#34;process name&#34; is used in constructing the system. This is stored in a memory area 4a (PR 1  to PR i ) Here, i indicates the number of processes which are required for expressing the target system. In the example of FIG. 2, the memory area corresponds to the number of terminal units n, the cash dispensers, and the host computer. 
     Now, if it is assumed that information from the host computer of FIG. 2 is stored in the place PR 2 , and that information from the cash dispenser of FIG. 2 is stored in the place PR 1 , then, process name information related to memory areas 4b, 4c and 4d is stored in places PR 2  to PR i  of FIG. 5. 
     The memory area 4b, (FNK 1 ,1,1 to FNK i ,i,j) for the process name contains the function names, which are to be input from the line processes and transformed and output to the column processes, of the functions belonging to the line processes between the processes which are stored in the process name memory areas constructing the system. Here, i has a meaning similar to the aforementioned one. indicates the total number of functions belonging to the column processes, which are to be used by the line processes. 
     The memory area 4c (i.e., IDS 1 ,1,1 to IDS i ,i,j) for the input data structure names corresponds to the function name memory area and contains the data structure names to which the functions stored in the function name memory area are to be input. Here, i and j have meanings similar to the aforementioned ones. 
     The memory area 4d (i.e., ODS 1 ,1,1 to ODS i ,i,j) for the output data structure names contains the data structure names from which the functions stored in the function name memory area are output. Here, i and j have meanings similar to the aforementioned ones. 
     The system structure table 32 is shown in FIG. 6. The memory area 5a (i.e., PF 1  to PF i ) for the function or process name contains the structures of the respective functions (containing the processes) in the system structure table at a unit of the function (containing the process). Here, i indicates the total number of functions and processes which are required of the target system as a whole. 
     A memory area 5b (i.e., TM 1  to TM m ) for transition names stores recognition names for distinguishing transitions. Here, letter m indicates the number of transitions required to express the system to be simulated. 
     A memory area 5c (i.e., NF 1  to NF m ) for function names corresponds to the transition name memory area and contains the names of the functions to be conducted by the transitions. Here, m has a meaning similar to the aforementioned one. 
     A memory area 5d (i.e., NFF 1  to NFF m ) for flags, which determine the details of function in the step corresponds to the function name memory and contains information as to whether the functions of the names of the respective function name memory areas are detailed by the system structure table. Here, m has a meaning similar to the aforementioned one. 
     A memory area 5e (i.e., WSF 1  to WSF m ) for flags, which determine whether action is requested in the next step, contains information as to whether the token has moved to another system structure table and whether the system is awaiting its return. Here, m has a meaning similar to the aforementioned one. 
     A memory area 5f (i.e., PM 1  to PM n ) for place names contains identifiers (hereafter called place names) which denote the standby location of the token. Here, n indicates the number of place names required to represent the target system. 
     A memory area 5g (i.e., DSM 1  to DSM n ) for data structure names contains the names of the data structures which are to be held by the token standing by in said place. Here, n has a meaning similar to the aforementioned one. 
     A memory area 5h (i.e., TFM 1  to TFM n ) for flags which determine whether the present step is a token step corresponds to the place name memory area and contains data indicating whether the token is present in said place. Here, n has a meaning similar to the aforementioned one. 
     A memory area 5l (i.e., TFM 1  to TFM n ) for the relationship between places and transitions corresponds to the place name memory area and the transition name memory area and contains data indicating the relationship between places and transitions. The relationships are those in which the token moves from place to transition, those in which the token moves from transition to place, and those in which there is no relationship between transition and token. Here, n and m have meanings similar to the aforementioned ones. 
     A memory area 5k (i.e., TTM 1 ,1 to TTM n ,m) for token movement data corresponds to the memory area for the relationship between places and transitions and contains data indicating which transition the token moves to in case the token can move from a place to a plurality of transitions. Here, n and m have meanings similar to the aforementioned ones. 
     Next, the data structure table 33 is shown in FIG. 7. A memory area 6a (i.e., DSE 1  to DSE i ) contains data structure names. Here, i indicates the number of the data structure names required to represent the system to be simulated. 
     A memory area 6c (DUE 1  to Due k ) for subordinate data structure names corresponds to the data structure name memory area and contains the subordinate data structure names for data structure names stored in the data structure name memory area. Here, k indicates the total number of subordinate data structure names for the data structure names. 
     A related memory area 6b (i.e., DRM 1  to DRM j ) corresponds to the data structure name memory area and it contains data indicating how the data structure names are related to the subordinate data structure names. Here, J indicates the number of relationships which are required for preparing the data structure to represent the system to be simulated. 
     The simulation system 30, containing a processor, executes the process indicated in the flow chart shown in FIG. 8. 
     The operation of the present simulation system 30 will be described by considering a specific example, the system which is shown in FIG. 9. FIG. 9(a) shows a simple system structure, the host computer and a cash dispenser coupled to the host computer. The process names indicate the relationship between the cash dispenser and the host computer. The data structure names to be transmitted from the cash dispenser to the host computer correspond to the cash payment data pulse train, and the data structure names to be transmitted from the host computer to the cash dispenser correspond to the cash payment amount. The host computer executes the functions to input, transform and output the data structures from the cash dispenser, namely, the functions for balance verification. 
     FIGS. 9(b) and (c) show the data structures to flow between the processes. For example, the relationships between the data structure name &#34;cash payment data pulse train&#34; and the cash payment data are expressed by a pulse train. 
     FIGS. 9(d) to (g) show the internal structures of the functions. FIG. 9(g) shows the data structure of a portion of the data structure names shown in FIGS. 9(d) to (g). Letters P and T indicate places and transitions, respectively. 
     In FIG. 9(a), the system is constructed of processes called the &#34;cash dispenser&#34; and the &#34;host computer&#34;. The data called the ⃡cash payment data pulse train&#34; and the &#34;cash payment amount&#34; are transferred between the cash dispenser and the host computer. FIG. 9(b) shows the structure of the data structure name &#34;cash payment data pulse train&#34; to be transmitted from the cash dispenser to the host computer, and shows that the &#34;cash payment data pulse train&#34; is given as the pulse train in sequence with the cash payment data composed of the account number and the cash payment amount. 
     FIG. 9(d) shows the Petri net model for the cash dispenser. The P CD2 , P CD4 , P CD6 , P C1 , P C2  and P C3  indicate places, and the T CD1 , T CD3 , T CD5 , T CD7  and T h4  indicate the transitions. 
     The function assigned to the transition T h4 , i.e., the &#34;the host computer: balance certification&#34; does not indicate execution of the present function in the cash dispenser; it indicates the attainment of the resultant data by sending the data to the function of the &#34;host computer&#34;, i.e., the &#34;balance verification&#34;. In other words, it is shown that the data is transferred between these processes during the execution of the present function. 
     The simulation system 30 conducts, at step 71 of FIG. 8, the initial determination of the whole structure table, the system structure table, the data structure table and the tokens, which are required for the simulations, in accordance with the system determining program 34 of FIG. 4. The whole structure table is prepared on the basis of the information shown in FIG. 9(a). Here, the whole structure of the present embodiment is shown in FIG. 10. The host computer is coupled to the cash dispensers. The function of the host computer, i.e., the &#34;balance verification&#34; is also used in the cash dispensers. Moreover, this function is executed when the tokens are at the place (P h1 ) called &#34;balance&#34;, the place (P C1 ) called &#34;cash payment amount&#34;, and at the place P C2  called &#34;account number&#34;. If one cash dispenser makes use of the &#34;balance verification&#34; of the host computer, the other cash dispensers are made to wait because the tokens cannot set at &#34;balance certification&#34;, &#34;cash payment amount&#34; and &#34;account number&#34;. 
     The whole structure table reflecting the information of FIG. 9(a) is shown in FIG. 11. The system structure table is prepared on the basis of the information shown in FIGS. 9(d) to (f). The system structure table reflecting the information of FIG. 9(d) is prepared in accordance with FIG. 6 and is shown in FIG. 12. FIGS. 9(e) and (f) are also prepared in a similar manner (although not described in the present example). In FIG. 12, the &#34;token present&#34; flag memory area 5h is set at &#34;absence&#34; (0), and the action requesting state flag memory area 5e is set at &#34;non-standby&#34; (0). The data structure table is prepared on the basis of the information shown in FIGS. 9(b), (c) and (g). The data structure table reflecting the information of FIGS. 9(b), (c) and (g) is shown in FIG. 13. Moreover, one or more tokens are set at the start position of the simulation at a process unit. The initial data thus far described is determined. 
     An example of simulation will be described in the following where tokens are set at P CD6  of FIG. 9(d) and at P h1  of FIG. 9(e). 
     At a step 72 of FIG. 8, all the &#34;token present&#34; flag memory areas of all the system structure tables are examined to determine all the places where the tokens are present. The present example corresponds to the cases in which the tokens are input from the input-output device 36 and the P CD6  of the cash dispenser and the P h1  of the host computer. 
     At a step 73 of FIG. 8, the respective tokens identified at step 72 are judged as to the relationships between places and transitions of the system structure table. It is determined whether the number of &#34;removal from place to the transition&#34; relationships is two or more, one or none. In the case of the present example, there exists the transition of removal from the &#34;T CD5  of the P CD6  of the cash dispenser&#34; and the &#34;T h4  of the P h1  of the host computer&#34;. 
     At step 74, it is determined in accordance with the result revealed at the step 73 whether the function to be executed next can be simulated. In case the number of the relationships examined at the step 73 and present between the places and the transitions is two or more, the destination of the token cannot be determined, but step 75 is executed. In the present example, the token at the P CD6  of the cash dispenser can be moved to the transition T CD5  whereas the token at the P h1  of the host computer can be removed to the transition T h4  so that the step 77 is conducted. 
     At a step 75, the content of the token removing memory area, which contains the relationship of the &#34;removal from place to transition&#34; is displayed on the input-output device. Moreover, the transition to which the token is removed is selected. 
     At step 76, the transition in the place where the token is removed is input from the input device of the input-output device 36 by the use of the information input program 35. 
     At a step 77, synchronization of the destination transition found at steps 74 and 76 is confirmed. For the destination transition which has been identified at steps 74 and 76, as shown in FIG. 6, a search determines that all &#34;token present&#34; flags corresponding to place names relating to the &#34;removal from place to transition&#34; indicate &#34;presence&#34;, and that all token presence flags corresponding to the place names relating to the &#34;removal from the transition to the place&#34; indicate &#34;absence&#34;. If the token removal condition memory area is present at that time, it is searched to find whether the destination transition has been selected at step 76. 
     For tokens having no destination transition, all place name token presence flags stored in the system structure table, in which the destination tokens are present, but have no relationship to the &#34;removal from place to transition&#34; are checked. Then, it is assumed that synchronization has been done for &#34;presence&#34;, but not for &#34;absence&#34;. 
     At a step 78, if the results from step 77 reveal that all the token presence flags indicate &#34;presence&#34;, that the token is absent from the destination and that the removal condition of the token is satisfied, it is determined that synchronization has been taken in case the destination transition is selected, and the operation advances to step 79. Otherwise, the operation is returned to step 72. In the present example, both tokens are synchronized so as to be subjected to step 79. 
     At this step 79, if the destination transition of the token of FIG. 6 to be removed is present, the detailed presence flag memory area 5d of the function of the transition is examined. In the case of the state of the &#34;absence of the detail of the function&#34;, the data of the place name token presence flag memory area relating to the &#34;removal from place to transition&#34; of the related memory area for place and transition of the destination transition are determined at &#34;absence&#34;, whereas the data for the place name token presence flag memory area 5l relating to &#34;removal from the transition to the place&#34; are determined at &#34;presence&#34;. In the memory area 5l the value &#34;0&#34; means no relationship, the value &#34;1&#34; means the removal from the place to the transition, and the value &#34;-1&#34; means the removal from the transition to the place. 
     Here, the column of intersections of P CD6  - T CD5  in FIG. 12, for example, will be described in the following. An arc is present from the place P CD6  to the transition T CD5 . This is expressed at [1] in the upper lines. There is no special condition at this time. This is expressed at [-] in the lower lines. In the column of the intersections of P CD6  - T CD7 , the value [-1] in the upper lines indicates that an opposite arc is present, and the value [1] in the lower lines indicates that no special condition is present. 
     For the condition &#34;details of the function are determined&#34;, the action requesting condition flag memory area 5e corresponding to said transition is set at &#34;1&#34;, in which &#34;the token is being removed to another system structure table&#34;, to examine the system structure table which is coincident with the discriminator stored in the &#34;function name or process name memory area&#34; of that system structure table coinciding with the function name of the function name memory area. The coinciding system structure table will be called the &#34;destination system structure table&#34;, whereas the system structure table in which said token is present will be called the &#34;destination system structure table&#34;. The memory area 5e is set at &#34;0&#34; in the absence of the request. 
     In the place-transition relating memory area al of the destination system structure table, it is possible to determine the data structure name belonging to the place name to which the token can be removed from the destination transition. 
     In the data structure name memory area of the destination system structure table, one coincident with said data structure name is examined, and the flag or the &#34;token present&#34; flag memory area corresponding to the coincident data structure name is set at &#34;present&#34;. 
     In the destination system structure table, the &#34;token present&#34; flag indicating the token to be removed is set at the &#34;absent&#34;. 
     In case the destination transition of the token to be removed is absent, both the function name of the &#34;function name or process name memory area&#34; of the system structure table, in which said token to be removed is present, (which will be called the &#34;destination system structure table&#34;), and the data structure name corresponding to the name of the place, in which said token is present, are examined (which will be called the &#34;destination function name and destination data structure name&#34;). 
     Next, the function name memory area of another system structure table is examined to find the one with the destination function name. If a matching name is found, it is determined whether or not the data of the action requesting state flag memory area corresponding to the coincident function name are in the state where &#34;the token is being removed to another system structure table&#34;. If no matching name is found, the search continues. If a matching name is found, the data for the action requesting state flag memory area are set at &#34;non-stand-by&#34;, and the &#34;token present&#34; flag memory area for the place name having the data structure name coincident with the destination data structure name is set at &#34;present&#34; whereas the token presence flag indicating the destination token of the destination system structure table is set at &#34;absent&#34;. 
     At step 80, the input data structure and the output data structure of the transition, through which the token has passed, are prepared. More specifically, the data structures, which have been held by the tokens present in all the places of the place names relating to the transition names at the previous step, are prepared with reference to FIG. 7. In other words, the relationships between the data structure names and the subordinate data structure names, and the subordinate data structure names are examined in view of the data structure table by using as keys, those data structure names which correspond to the place names for preparing the data structure. The subordinate data structure names attained as a result of the examinations are further examined in a similar manner. These examinations are repeated when examination has revealed that no subordinate data structure names are present. 
     At step 81, the execution procedures for the aforementioned functions are displayed on the input-output device 36. At the end of the present step, the operation is returned to step 72. 
     FIG. 14 shows an example of a built-in Petri net model in the transition T h4  of the host computer. T h41 , T h42 , T h43  and T h44  indicate transitions, and P h3  indicates the place where the result of the account number certification (T 41 ) is present. As a result, the token is removed to transition T 43  if the account is absent and to transition T 42  if it is present. 
     Transition T h4  indicated by a single-dotted line in FIG. 14 is the host computer seen from the terminal unit side and can be considered a black box using the places P h1  and P h2  as the terminal units as seen from the host. 
     The display procedures when the system simulation in this example is executed are shown in FIGS. 15(a) to (d) and FIG. 16 (a) to (c). Here, the display procedures shown are those which are executed by the uppermost-rank function. 
     FIG. 15 shows the operation of the whole system microscopically. The cash dispenser executes &#34;cash card reception&#34; as a result of the first transition, and the host computer waits for the execution of &#34;balance certification&#34; as shown in FIG. 15(a). As a result of the second transition, as shown in FIG. 15(b), the cash dispenser executes &#34;reception of cash payment&#34;, and the host computer awaits for &#34;balance certification&#34;. As a result of the third transition (as shown in FIG. 15(c)), the cash dispenser requests &#34;balance certification&#34; of the host computer and waits for it while the host computer executes &#34;balance certification&#34;. As a result of the fourth transition, as shown in FIG. 15(d), the cash dispenser executes &#34;cash payment&#34;, and the host computer executes &#34;balance renewal&#34;. Upon the third transition, &#34;payment data&#34; is removed from the cash dispenser to the host computer. Upon the fourth transition, &#34;cash payment amount&#34; is delivered from the host computer to the cash dispenser. 
     FIGS. 16(a) to (c) show the data structure transformation procedures by the specific token removal. Of the displayed examples, FIG. 16(c) shows the first transition display. 
     In FIG. 16, the solid circle indicates the initial position of the token, the blank circle indicates the first position, the solid triangle indicates the second position, the blank triangle indicates the third position, and the solid square indicates the fourth position. 
     FIGS. 17(a) and (b) show the changes of the token presence flags of the function simulation shown in FIG. 12. FIG. 17(a) shows the cash dispenser token presence flag and corresponds to FIG. 16(a). FIG. 17(b) shows the token presence flag in the host computer and corresponds to FIG. 16(b). 
     With the present system, function simulation of a distributed processing system can be executed properly even in a large, complex system. 
     Although a cash dispenser has been described hereinbefore, the present invention can be similarly applied to other systems.