Mutual Exclusion and Transactional Access
- mutually-exclusive access
- to a resource ensures that only one process at a time may be granted write-mode access to that resource while any other process requiring it be denied reading or writing access [Tan01]. (Conversely, read-only access permissions can be granted to multiple processes simultaneously.)
Example 1 (Mutually-exclusive access)
Consider a railway system that interconnects three stations: Venice, Vienna, Berlin. (Cf. figure) A passenger wants to buy a ticket from Venice to Vienna. When the counter staff contacted by the passenger commences the ticket issue procedure procedure, no other counter staff anywhere in the railway system may begin to issue tickets on the Venice-Vienna line until the ticket issue procedure in progress on that line completes. In this example the shared resource is the passenger seat on a single railway line, the exclusive right to which is represented by a ticket.
Figure A1.1: Mutual Exclusion and Transactional Access
Notice that if a passenger wants to buy a ticket from Venice to Berlin, the mutual exclusion access guaranteed alone could cause the following situation: the passenger may actually acquire a ticket from Venice to Vienna only to discover that all tickets from Vienna to Berlin (in the time window of interest) have already been sold out.
- transactional access
- to a resource ensures that only one process at a time may be granted access to that resource until completion of a designated set of operations; not all the operations in the set need to operate on one and the same the shared resource, as for example in set: read from resource; process value outside the resource; write to resource. Any other process that requires access to a resource locked with transactional access will be denied access until the resource has been released (and thus the entire set of operations has completed) [SG03]. It follows from this definition that a single transactional-access operation set may involve multiple mutually-exclusive-access resources and lock them all for the entire duration of the operation set.
Example 2 (Transactional Access)
Consider the system depicted in the previous figure. A passenger wants to buy a ticket from Venice to Berlin. When the counter staff contacted by the passenger commences the ticket issue procedure, no other counter staff in the system may issue tickets until the current procedure completes. In this example the transactional-access operation involves two mutually-exclusive-access resources and locking both of them in effect locks the entire system.
Transactional access in HRT-UML/RCM
At present the HRT-UML/RCM methodology provides partial support for node-local transactions.
In the Toy Example, the original problem specification requires the read-compute-update sequence to be performed while holding exclusive access rights on the POS resource. In HRT-UML/RCM, one way to obtain this behaviour is to define an additional operation, which we named Read_X_Write, whose only purpose is to execute the sequence of operations requiring transactional access on POS. Marking Read_X_Write as protected caters for access to POS to be locked during the execution of the three required operations. In fact, the ceiling assigned to the protected resource associated with Read_X_Write will reflect the ceiling of POS to ensure that, when the execution of Read_X_Write commences, no local competition could ever arise on access to POS. For the same reason, should POS require additional protected data resources for the execution of Read or Write, mutual exclusion access to those resources would automatically be acquired at the beginning of the execution of the transactional operation.
Figure A1.2: Providing transactional access using an additional protected PI
Figure A1.2 shows how the mechanism could be automated: in an ideal scenario, whenever a designer wished to perform a transaction on a single resource, s/he would simply mark the operations required within that transaction as transactional RI, Read, Compute and Write in the example. The tool would then automatically and transparently copy the transactional operation GNC_op to a separate resource, marking it "protected". In figure A1.2, this copy is named Read_X_Write, and the resource is named GNC_POS_T. The original APLC (GNC) is transformed to substitute the original RI of GNC_op with a single RI connected to the new PI (Read_X_Write). RI of GNC_POS_T are eventually connected to the PI the designer originally intended to use.
To optimize the solution, the new PI (Read_X_Write) could be placed into the called APLC (POS), in order to bypass access control structures (OBCS) of the called APLC. Otherwise, the copy could be placed into the caller APLC (GNC) in order to avoid additional dependencies between the callee (POS) and the caller (GNC).