Abstract:
A method of scheduling distributed transactions, on each initiation of a current transaction, identifies, among older transactions in process of execution, operations activated or waiting to be activated of the transactions that conflict with a particular operation of the current transaction. For each particular operation of the current transaction for which a particular number of conflicting operations have been identified, the method associates with the particular operation a counter the value of which is indicative of the number of operations conflicting with the particular operation. It decrements the value of the counter as and when operations conflicting with the particular operation terminate so as to activate the particular operation only when its counter indicates that there are no longer any operations conflicting with it.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the invention 
     The invention concerns a method of scheduling distributed transactions for a transactional monitor. 
     2. Description of the prior art 
     A distributed transaction is a partially ordered set of operations to be executed remotely and distributed between a number of processes. These operations can be instantiated methods in objects potentially replicated in more than one process. 
     A transactional monitor serializes the activation (or invocation) of the operations of the transactions in conformance with the chronological order in which the transactions are initiated. 
     At the level of the monitor, each transaction is initiated on the reception of an event. During the execution of a transaction the termination of a given operation leads to the reception of an event enabling activation of a subsequent operation of the transaction. 
     In industrial control/command applications there is a need to maintain a coherent image of the monitored process so that its behavior can be controlled. Data reflecting the image of the process is managed by means of an application and interaction between the application and the process is assured by events sent and received by sensors distributed across the process. The process being of a distributed nature, the application uses distributed transactions to maintain a coherent image of the process in a database. These industrial control/command applications run in flexible real time and it is therefore important to initiate several transactions in parallel, but this possibility of parallel initiation of transactions causes a problem at the level of operation activation scheduling. The transactions include identical or analogous operations, known as conflicting operations, since they cannot be executed at the same time because they interact with the same data. 
     The aim of the invention is to propose a method of scheduling distributed transactions for a transactional monitor with the possibility of parallel initiation of transactions in order to serialize activation of the operations of the transactions in accordance with the chronological order in which the transactions are initiated and allowing for conflicts of execution between operations of different transactions or of the same transaction. 
     Another aim of the invention is to propose a scheduling method of this kind that is suitable for complex transactions including recovery sequences if necessary. 
     SUMMARY OF THE INVENTION 
     To this end, the scheduling method of the invention comprises the steps of: 
     on each initiation of a current transaction, identifying, among older transactions in process of execution, operations activated or waiting to be activated of the transactions that conflict with a particular operation of the current transaction, and 
     for each particular operation of the current transaction for which a particular number of conflicting operations have been identified, associating with the particular operation a counter the value of which is indicative of the number of operations conflicting with the particular operation and decrementing the value of the counter as and when operations conflicting with the particular operation terminate so as to activate the particular operation only when the counter of the particular operation indicates that there are no longer any operations conflicting with the latter. 
     One embodiment of the invention is described in more detail hereinafter with reference to the drawings. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 shows examples of expressions of distributed transactions. 
     FIG. 2 is a graphical representation of the expressions of the transactions from FIG.  1 . 
     FIG. 3 is a flowchart showing the main steps of the scheduling method of the invention. 
     FIG. 4 shows one example of the chaining of activation of operations of the transactions from FIG. 1 using the scheduling method of the invention. 
     FIG. 5 shows the serialization of activation of operations at the output of the transactional monitor for the operation chaining example from FIG.  4 . 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     The scheduling method of the invention is suitable for transactions with operations that can be activated in sequence, in parallel, chosen via a conditional expression or iterated in a loop. 
     In FIG. 1, the three transaction expressions  1 ,  2  and  3  are relatively simple. They use a sequential operation chaining operator  11  and a parallel operation chaining operator  12 . Each transaction expression defines a particular chronological order in which the operations of the transaction concerned must be chained. 
     Thus, for transaction  1 , activation of operation P 2  is chained after termination of operation P 1  (sequential activation) whereas activation of operation P 3  can be chained after activation of operation P 2  without waiting for P 2  to terminate, i.e. in parallel with operation P 2 . 
     For transaction  2 , activation of operation P 2  is chained after activation of operation P 4  without waiting for P 4  to terminate. 
     For transaction  3 , activation of operation P 6  is chained after termination of operation P 5 , activation of operation P 7  is chained after termination of operation P 6  and activation of operation P 2  is chained after activation of operation P 7  without waiting for P 7  to terminate. 
     Note that the transaction expressions from FIG. 1 are structured as regular expressions with operators having a greater or lesser priority relative to others. 
     In FIG. 2 the expressions  1 ,  2  and  3  of the transactions T 1 , T 2 , T 3  from FIG. 1 are shown in the form of directed graphs with leaves corresponding to operations and nodes corresponding to the operation chaining operators. These graphs are conventionally implemented in memory in the form of chained lists which define the chronological order in which the operations of each transaction must be activated. 
     The three transactions T 1 , T 2  and T 3  shown in FIG. 2 have a common operation, operation P 2 . If these three transactions can be initiated in parallel, it can be seen that there is a possibility of conflict in respect of operation P 2 . To comply with the causal order of initiation of the transactions, assuming T 3  is initiated after T 2  and T 2  is initiated after T 1 , operation P 2  of T 3  must be activated only after operation P 2  of T 2  terminates. Likewise, operation P 2  of T 2  must be activated only after operation P 2  of T 1  terminates. 
     Operations P 2  of T 1 , P 2  of T 2  and P 2  of T 3  are conflicting operations. The scheduling method of the invention provides a simple way of preventing parallel activation of these conflicting operations. 
     In FIG. 3, in the scheduling method of the invention, the transaction expressions, advantageously structured in the form of regular expressions, are entered into memory in the transactional monitor and are treated, by syntactical and semantic analysis, to be implemented in the form of chained lists (block  30 ) each of which indicates the order in which the operations of each transaction must be activated. 
     Each transaction entered in the transactional monitor is scheduled after an event is received indicating the initiation of the transaction (event EvTx in block  31 ). This transaction is referred to as the current transaction Tx, as opposed to transactions already initiated and in process of execution. 
     Scheduling the current transaction Tx consists firstly in identifying (block  32 ), in operations activated or waiting to be activated of older transactions already initiated and in process of execution, any operations that conflict with one or more particular operations of the current transaction. This identification can be based on a look-up table listing conflicting transactions and previously entered into the transactional monitor and updated as and when these conflicting operations terminate to indicate which are the conflicting operations in process of execution or waiting to be activated. 
     Then, a counter Cp(PyTx) is associated (block  33 ) with each particular operation (Py) of the current transaction Tx for which a particular number of conflicting operations has been identified and the value of the counter associated with a particular operation (block  33 ) is set to indicate the number of operations conflicting with the latter. 
     When the scheduling of the transaction Tx is terminated, this current transaction is executed (block  36 ), i.e. the activations of operations of the current transaction are chained in the order given by the expression of the transaction. Nevertheless, activation of a particular operation of the current transaction will be delayed as long as the counter associated with that particular operation indicates that there are still operations conflicting with the latter. 
     The value of the counter associated with this particular operation is decremented (block  35 ) as and when operations conflicting with the latter terminate (i.e. during the execution of older transactions), reported to the transactional monitor by the reception of an event EvPy(Tz) (block  34 ), until there are no more conflicting operations. When there are no more operations conflicting with the particular operation, the particular operation can be activated. 
     FIG. 4 shows in a highly schematic manner one example of chaining of operation activation for transactions T 1 , T 2 , T 3 . 
     In this figure, transaction T 1  is initiated first after reception of a initiation event EvT 1 . When this current transaction is initiated, there is no older transaction in process of execution and consequently the counters associated with the respective operations T 1  indicate that there are no conflicting operations. Transaction T 1  is executed and operation P 1  is activated first. 
     Transaction T 2  is initiated subsequently following reception of event EvT 2 . Transaction T 2  is then scheduled allowing for the conflicting operations of T 1 . Operation P 2  of T 2  conflicts with operation P 2  of T 1  waiting to be activated. Consequently, the value of the counter associated with operation P 2  of T 2  is set to  1  to indicate that there is a conflicting operation (Cp(P 2 /T 2 )=1). Transaction T 2  is executed and operation P 4  is activated. 
     Following termination of operation P 1  (indicated by reception of event EvP 1 ), operation P 2  of T 1  is activated. Operation P 4  has now terminated (reception of EvP 4 ) but activation of operation P 2  of T 2  is delayed because the value of the counter associated with operation P 2  of T 2  indicates that there is a conflicting operation (Cp(T 2 /T 2 )=1). 
     Operation P 3  of T 1  is now activated in parallel with operation P 2  of T 1 . 
     Transaction T 3  is initiated next, following reception of event EvT 3 . Transaction T 3  is then scheduled and for operation P 2  of T 3  there are two conflicting operations activated or waiting to be activated, respectively operation P 2  of T 1  and operation P 2  of T 2 . The value of the counter associated with operation P 2  of T 3  is set to 2 (Cp(P 2 /T 3 )=2). 
     Transaction T 3  is now executed and operation P 5  is activated. Following termination of operation P 5  (reception of EvP 5 ), operation P 6  is activated. Operation P 3  is now terminated (reception of EvP 3 ) and operation P 7  is activated after termination of operation P 6  (reception of EvP 6 ). 
     Now, following termination of operation P 2  of T 1 , indicated by reception of event EvP 2  (T 1 ), the value of the respective counters associated with operation P 2  of T 2  and operation P 2  of T 3  is decremented (Cp(P 2 /T 2 )=0 and Cp(P 2 /T 3 )=1). Operation P 2  of T 2  can now be activated. 
     Now, operation P 7  is terminated (reception of EvP 7 ) and after termination of operation P 2  of T 2 , indicated by reception of event EvP 2 (T 2 ), the value of the counter associated with operation P 2  of T 3  is decremented (Cp(P 2 /T 3 )=0). Operation P 2  of T 3  can now be activated. Event EvP 2 (T 3 ) is finally received and execution of the transactions is terminated. 
     In FIG. 5, the transactional monitor  50  serializes transactions T 1 , T 2 , T 3  to produce the following sequence of operation activations: P 1 -P 4 -P 2 -P 3 -P 5 -P 6 -P 7 -P 2 -P 2 , complying with the order of arrival of the transaction initiation events, the order of chaining of the operations within each transaction and the order of arrival of the operation termination events which are, in this example: 
     EvT 1 , EvT 2 , EvP 1 , EvP 4 , EvT 3 , EvP 5 , EvP 3 , EvP 6 , EvP 2  (T 1 ), EvP 7 , EvP 2 (T 2 ), EvP 2 (T 3 ). 
     The method in accordance with the invention of scheduling distributed transactions is also suitable for management of transactions including recovery sequences. A recovery sequence in a transaction corresponds to a branch of the transaction graph that is executed on reception of a particular event, known as an exception event, following a problem with executing an operation of that transaction. A transaction recovery sequence can of course include a plurality of operations which are chained and which are substituted for certain other operations of the transaction. When an exception event of this kind is received by the transactional monitor for a transaction in process of execution, the recovery sequence of that transaction must be scheduled using the counter management principle to allow for possible conflicts between operations of the recovery sequence and operations of other transactions in process of execution.