Keywords: Locking,Multiple Granularity, Serializability,Colourd Petri Net

Abstract: One of the methods of serializability in transaction commands is lock-based protocol[9]. Although locking ensures mutual exclusion, it brings about starvation or deprivation in executing transactions.Locking on a tree structure through using multiple aggregation method is one of the locking methods for nodes of a tree that allows each node to have various sizes[6,9]. At the same time, it creates a hierarchy of data in which smaller particles are located within the larger ones[6,8,9]. This article fully explains the colored Petri Net model of the protocol along with shapes of places, transitions, functions and commands.

Keywords: Locking,Multiple Granularity, Serializability,Colourd Petri Net

1.Introduction

1.1 Concurrency Control

One of the techniques used for concurrency control is a Lock-Based Protocol[9]. A database system must be able to control the connections between concurrent transactions[7,9]. If concurrent transactions are properly controlled, the efficiency of the system will be increased. If the Schemas of concurrent transactions are serializable, the result will be correct. Concurrency Control Scheme is used in order to ensure this serializability[6,7,9].

The techniques which are reviewed in this section do not consider the failure problem of transactions. Each of these techniques has advantages and disadvantages. In general, they make the transactions wait for other transactions or they give a particular way to implementing transactions[4,6]. They may also allow the transactions to be run without any limitation, but at the end of the transaction, they would check in order to find out whether any problem has occurred. If any problem has arisen, the effect of implementing those transactions will be removed from the database[6]. One technique used to guarantee the serializability feature is mutually exclusive access to the data item. It means that when a transaction would have access to the data item, no other transaction has the possibility to modify that data[6,7,9].

To implement this method, locking is used. Locking makes it possible for one transaction to get access to the data if it has the lock at the time of accessing[6,9]. Locking is a mechanism for controlling concurrent access to data. Two types of locks for a data item can be considered[9]:

• Exclusive mode or exclusive lock that is indicated by X. Data with exclusive mode is both readable and writable. A transaction which tends to put an X-lock on a data item should send the X-lock command to subsystem of locking which is a component of the database system.

• Shared mode or a shared lock is indicated by S. When a transaction locks a data in shared mode, it can only read that data. If a transaction tends to put an S-lock on a data item, it should command S-lock.

Locking requests are sent to the Concurrency Control Manager module. A transaction which has sent a locking request will continue working if the Concurrency Control Manager gives that lock to the transaction. In other words, the concurrency Control Manager assigns the permission of accessing specific data to the particular transaction in question according to the locking compatibility Table.

Table 1

In this technique, three other modes besides share lock or exclusive lock are introduced. These modes are:

• Intention-Shared (IS)

• Intention-Exclusive (IX)

• Shared and Intention-Exclusive (SIX)

In this technique, when the intention of putting a lock on a node is announced, nodes at lower levels of the hierarchy will be explicitly locked. In this technique, before locking the node explicitly, all nodes above the node must be locked in an intention lock mode. Using this intention lock allows the nodes located on the upper levels to be locked on a share or exclusive mode without any need for all its descendent nodes to be controlled[6,9].

IS: When a node is locked in this mode, it means that some nodes locate below this node are explicitly locked in share mode.

IX: When a node is locked in this mode, it means that some nodes located below this node are explicitly locked in exclusive mode or share mode.

SIX: If a node is locked in this mode, it means that the entire sub-tree of that node is explicitly locked in share mode and there are also some nodes at lower-level of this node which are explicitly locking in exclusive mode.

1.2 Compatibility Matrix with Intention Lock Modes

The following matrix is a compatibility matrix which shows the association of five locks[6,7,9].

Table2

As you can see, X-lock is not compatible with any other lock (i.e. if a transaction put X-lock on a data, no other transaction can put another lock on that data item). Locks in SIX mode are compatible with locks in IS mode. The lock in S mode is compatible with IS or S mode. Locks in IX mode are only compatible with locks in IS and IX modes. Locks in IS mode are only compatible with locks in IS, IX, S, SIX modes.

1.3 Multiple Granularity Locking Rules with Intention Locks

Here, we will observe the rules concerning locking transactions using intention lock. Transaction can lock a node Q, using the following rules[4,5,9]:

1. Thelockcompatibility matrixmustbe observed.
2. The root of the tree must be locked first, and may be locked in any mode.
3. A Node Q can be locked by transaction Ti in S or IS mode only if parent of Q can be locked by transaction Ti in IX or IS mode.
4. A Node Q can be locked by transaction Ti in X, SIX, or IX mode only if parent of Q can be locked by transaction Ti in IX or SIX mode.
5. Transaction can lock a node only if no node has been unlocked by the transaction. In fact, it is the two-phase locking concept with which you are already familiar. Therefore, the transaction is practical in two-phase locking mode.
6. can unlock a node Q only if none of Q’s children are locked by transaction at that time.

So, observe that locks are acquired in root-to-leaf order, whereas they are released in leaf-to-root order. Now, based on the above descriptions, we will start exploring and implementing this protocol[7,8].

The model is composed of two parts. The first part is allocating lock to a node of a tree and second part is unlocking the node. INPUT and Achieved LOCKlocations are the same in both parts, and because of excessive size of the model using CPN TOOLS fusion technique, have the same values and any changes in one will result in changes in the values of the second. INPUT location includes initial values ​​of the list of locks of various transactions on a node of a tree. Achieved LOCK location in lock allocation section includes amounts of allocation locks and release locks of nodes of a tree, and both are considered as locks bank. Tree structure location keeps the following structure as initial values in form of a list[8,9].

Figure 1

Node's Childs location in release lock part of parent’s node with children index number, stores the parent’s node in their values. The location ​​of other transaction locks from this node varies in value depending on the amount of space of database of dedicated locks (Achieved LOCKS). In other words, it finds other transactions’ lock on a node of the tree, stopping any collision from happening among the locks, and preventing any transference of lock to other transactions on a node[6,7,8,9].

Two other locations give initial values of allowed locks matrices to ​​LOCKING transition which has the Parent-Child Compatibility Matrix location possessing the initial values ​​of lock compatibility matrix between parent and child on the tree structure (Table 1) and also has the Multi Transaction Compatibility Matrix location possessing the initial values ​​of lock compatibility matrix between different transactions (table 2). LOCKING transition perform locking process after controlling all properties of multiple aggregation protocol.

The second part of the model which is located on the right side of locks is almost similar to the first part, with the only difference that by placing a transition called Checking Descendants Locks, the availability of children locks of parent’s node could be considered, so If at least one of the children of parent’s node is locked, token will be redirected to the return transition, and ultimately, will be added to the last line of location of node's child until the condition is set to unlock the node. But, if any of the children of the parent node is not locked, token will be directed to the omitting transition, and release lock from the node will be added to the Achieved LOCKS location[4,5,9].

Now, based on initial and hypothetical values ​​of structure of Figure 1, the above model includes the following definitions[1,2,3,5,8]:

(* Standard priorities *)

val P_HIGH = 100;

val P_NORMAL = 1000;

val P_LOW = 10000;

(* Standard declarations *)

colset UNIT = unit;

colset INT = int;

colset BOOL = bool;

colset STRING = string;

(* VARIABLES *)

var p:P_C_C_LIST;

var lc:L_C_LIST;

var TL:TRANS_L;

var TSL:T_S_L;

var O: OPERATION;

var S : SEQUENCE;

var NN,NN1,NN2:NODE_ID;

var N,N1,N2:NODE_NAME;

var D:DEPENDENCY;

var DL,dl:ANCESTORS;

var DE:DESCENDANTS;

var L,PL,PL1:LL;

var LO,LO1,LO2:LOCK;

var LC:LOCKS_COMPATIBILITY;

var PC:PARRENT_CHILD_COMPATIBILITY;

var TI:TRANS_ID;

var i,x:INT;

var s,pl,cl:STRING;

var b:BOOL;

var IL:I_L;

(* COLSETS *)

colset SEQUENCE = int;

colset NODE_ID=int;

colset NODE_NAME = string;

colset DEPENDENCY = int;

colset TRANS_ID= string;

colset ancestors=int;

colset descendants=int;

colset LOCK=string;

colset OPERATION = string;

colset SEQ_LOCK_NODE =

product SEQUENCE * OPERATION* NODE_NAME;

colset TRANS_LOCK_NODE =

product TRANS_ID* OPERATION* NODE_NAME;

colset TRANS_L=list TRANS_LOCK_NODE;

colset TREE_STRUCTURE=

product NODE_ID * NODE_NAME * DEPENDENCY ;

colset T_S_L=list TREE_STRUCTURE;

colset ANCESTORS=list ancestors;

colset DESCENDANTS=list descendants;

colset TREE_STRUCTURE1=

product NODE_ID * NODE_NAME *ANCESTORS ;

colset LOCKS_COMPATIBILITY=product LOCK*LOCK;

colset PARRENT_CHILD_COMPATIBILITY=product LOCK*LOCK;

colset P_C_C_LIST=list PARRENT_CHILD_COMPATIBILITY;

colset L_C_LIST=list LOCKS_COMPATIBILITY;

colset NODEID_LOCKS=product TRANS_ID*NODE_ID*LOCK;

colset NODEID_LOCKS_LENGTH=product TRANS_ID*NODE_ID*INT;

colset LL = list NODEID_LOCKS;

colset I_L=list INT;

(* FUNCTIONS *)

fun ins l x = l^^[x]

fun mem [] a = false

| mem (x::xs) a = a=x orelse mem xs a

fun rm a [] = []

| rm a (x::xs) = if a=x

then xs

else x::(rm a xs)

fun rmall a [] = []

| rmall a (x::xs) = if a=x

then rmall a xs

else x::(rmall a xs)

fun ins_new l x =

if mem l x

then l

else ins l x

fun FindLock(N,i,PL)=

if mem PL (N,i,"IS") then

1`(N,i,"IS")

else

if mem PL (N,i,"SIX") then

1`(N,i,"SIX")

else

if mem PL (N,i,"IX") then

1`(N,i,"IX")

else

if mem PL (N,i,"S") then

1`(N,i,"S")

else

if mem PL (N,i,"X") then

1`(N,i,"X")

else

1`("",0,"")

fun RemoveLock(N,i,PL)=

if mem PL (N,i,"IS") then

rmall (N,i,"IS") PL

else

if mem PL (N,i,"SIX") then

rmall (N,i,"SIX") PL

else

if mem PL (N,i,"IX") then

rmall (N,i,"IX") PL

else

if mem PL (N,i,"S") then

rmall (N,i,"S") PL

else

if mem PL (N,i,"X") then

rmall (N,i,"X") PL

else

PL^^empty

fun LOG(N,NN,LO,LO1,LO2,p,lc,PL)=

if FindLock(N,NN,PL) > 1`("",0,"") then

"One Transaction Cannot Have Two Locks At The Same Time In One Node."

else

if NN=1 andalso LO2="" then

P^N^P2^P5

else

if NN=1 andalso not(mem lc (LO,LO2)) then

P^N^P1^P6

else

if NN=1 andalso not(mem lc (LO,LO2)) then

P^N^P1^P7

else

if not(mem p (LO1,LO)) andalso not(mem lc (LO,LO2)) then

P^N^P1^P8

else

if (NN=1 andalso mem lc (LO,LO2)) orelse

(NN=1 andalso LO2="" ) then

P^N^P2^P9

else

if (mem p (LO1,LO) andalso

mem lc (LO,LO2)) orelse (mem p (LO1,LO) andalso

LO2="") then

P^N^P2^P10

(Ins): gets an element and adds it to the array.

(Mem): searchesthearrayfor the element,and returnstrue if the elementexistsin the array,otherwisereturnsfalse.

(Rm): removes an element from the array.

(Rmall): searchesthearrayfor an element, and eliminates all identical elements to the first one.

(Ins_new): does not add up an element if it already exists in the array.

(FindLock): based on transaction name and name of a tree node, finds ifthisnodeholds a lock; otherwise returns null.

(RemoveLock): finds and eliminates compatible locks to transactions in the list; otherwise returns null.

Conclusion

The described model performs all functions concerning locking and unlocking on tree structure, using multiple aggregation protocol and works for more than two transactions without errors. However, the reader should utilize the model based on the features of multiple aggregation protocol and know that it fails to function on other methods of tree locking. For example, locking or unlocking a node cannot take place in the middle of a tree structure, using this model.

Acknowledgment

We would like to express our heartfeltthanks to Dr. LiLi Mohammadkhanli and Dr. Saeed Pashazadeh for his unfailing support and sound advice during the semester.

References

[1] Jensen, K.(1992). Coloured Petri Nets: Basic Concepts, Analysis methods and Practical Use,Springer, ISBN : 3-540-60943-1, Berlin, German.

[2] Peterson, J.L.(1991). Petri Net Theory and the Modeling of Systems, Prentice-Hall, ISBN:0-13-661983-5, N.J., USA.

[3] Juan, T., A. R. Pearce and L. Sterling (2002). ROADMAP: extending the Gaia methodology for complex open systems. See AAMAS (2002), pp. 3{10.

[4] Kohler, M., D. Moldt and H. R olke (2001). Modelling the structure and behavior of Petri net agents. In J. Colom and M. Koutny (Eds.), Proceedings of the 22nd Conference on Application and Theory of Petri Nets 2001, Volume 2075 of Lecture Notes in Computer Science, pp. 224{241. Springer-Verlag.

[5] R. Blossey, L. Cardelli, A. Phillips: Compositionality, Stochasticity and Cooperativity in Dynamic Models of Gene Regulation. HFSP Journal. 2(1), 17-28 (2008)

[6] N. Bahi-Jaber, D. Pontier: Modeling Transmission of Directly Transmitted Infectious Diseases Using Colored Stochastic Petri Nets. Mathematical Biosciences.

[7] M. Heiner, S. Lehrack, D. Gilbert, W. Marwan: Extended Stochastic Petri Nets for Model-based Design of Wetlab Experiments. Transaction on Computational Systems Biology XI. LNCS/LNBI, 5750, 138-163 (2009) [9] H.J. Genrich, K. Lautenbach :The analysis of distributed systems by means of predicate/transition-nets. G. Kahn (Ed.), Semantics of Concurrent Computation, Lecture Notes in Computer Science, 70, Springer, Berlin (1979), pp. 123–146.

[8] Jensen, Kurt (1996). Coloured Petri Nets (2 ed.). Berlin: Heidelberg. p.234. ISBN3-540-60943-1.

[9] B. Schatz, A. Pretschner, F. Huber, and J. Philipps, “Model-based development of embedded systems,” in Advances in Object-Oriented Information Systems, pp. 298–311, Springer, 2002.

KAVEH ABUBAKRI received the M.S. degree Software Engineering from Tabriz University in 2014, he work in Telecommunication Company of IRAN, and study Caching Servers, and Vehicular ad hoc networks (VANETs).

SABER MARDKARDIDEHreceived the M.S. degree in Software Engineering from Tabriz University in 2014, he work in Tabriz University, and study Trust Services-Oriented Multi-Objects Workflow Scheduling Model for Cloud Computing Using Evaluationaryand Petri Net.

BEHNAM KIANI KALAJAHIreceived the M.S. degree in Software Engineering from Tabriz University in 2014, Now he is Network Administrator In AzarAbadegan Medical Imaging Center, and study Securityand Privacy of Electronic Medical Records in CloudComputing.