Proof of equivalence of lock protocol:
We will now prove that the illustrated lock protocol is equivalent to a conventional one which uses only two modes (S and X) and which explicitly locks atomic resources (the leaves of a tree or sinks of a DAG).
Let G = (N, A) be a finite (directed acyclic) graph where N is the set of nodes as well as A is the set of arcs. G is presumed to be without circuits that are there is no non-null path leading from a node n to itself. A node p is a parent of a node n as well as n is a child of p if there is an arc from p to n. A node n is a source (sink) if n has no parents (no children). The ancestor of node n is any node (including n) in a path from a source to n. A node-slice of a sink n is a collection of nodes such that every path from a source to n contains at least one node of the slice. allow Q be the set of all sinks of G.
We as well introduce the set pf lock modes M = {NL, IS, IX, S, SIX, X} and the compatibility matrix C: AxM-> (YES, NO) described in
Table 1. Let c: AxM -> {YES, NO} be the restriction of C to m = {NL, S, X}.
A lock graph is a mapping L: N->M such that:
(a) If L(n) is in {IS, S} subsequently either n is a source or there exists a parent p of n such that L(p) is in { IS, IX, S, SIX, X). By induction there exists a path as of a source to n such that L(ni) takes only values in {IS, IX, S, SIX, X} on all nodes ni of that path. Consistently L(ni) is not equal to NL on the path.
(b) If L(n) is in {IX, SIX, X} afterwards either n is a root or for all parents p1,..., pk of n we have L(pi) is in { IX. SIX, X} for i = 1,..., k . By induction L takes merely values in {IX, SIX, X} on all the ancestors of n.
The interpretation of a lock-graph is that it provides a map of the explicit locks held by a particular transaction observing the six state lock protocol described above. The notion of projection of a lock-graph is now initiates to model the set of implicit locks on atomic resources acquired by a transaction.
A projection of a lock-graph L is the mapping p Q->m (from sinks to modes) constructed as follows
(a) p(n)=X if there exists a node-slice {n1,.. , ns} of N such that p(ni)=X for every node in the slice.(b) p(n)=S if (a) is not satisfied as well as there exists an ancestor na of N such that p(na) is in {S, SIX, X}.(c) p(n)=NL if (a) and (b) aren’t satisfied.
Two lock-graphs L1 as well as L2 are said to be compatible if C(L1(n), L2(n)) = YES for all n in N. Likewise two projections p1 and p2 are compatible if c(p1(n), p2(n)) = YES for all sink nodes n in Q.
Theorem- If two lock-graphs L1 as well as L2 are compatible then their projections P1 as well as P2 are compatible.
Otherwise if the explicit locks set by two transactions don’t conflict then also the three-state locks implicitly acquired do not conflict.
Proof: Presume that L1 as well as L2 are incompatible. We would like to prove that P1 and P2 are incompatible. By definition of compatibility there should exist a sink n such that L1(n)=X and L2(n) is in {S, X} (or vice versa).
By definition of projection there should exist a node-slice {n1,..., ns} of N such that L1(n1)=...=L1(ns)=X.
As well there must exist an ancestor na of n such that L2(na) is in {S, SIX, X}. From the definition of lock-graph there is a path Path1 from a source to na on which L2 doesn’t take the value NL. If Path1 intersects the node-slice at ni subsequently L1 and L2 are incompatible since L1(ni)=X which is incompatible with the non-null value of L2(ni). Therefore the theorem is proved.
On the other hand there is a path Path2 from na to the sink n that intersects the node-slice at ni. From the definition of lock-graph L1 obtains a value in {IX, SIX, X} on all ancestors of ni. In particular L1 (na) is in {IX, SIX, X}. Ever since L2 (na) is in {S, SIX, X} we have C(L1(na), L2 (na))= NO.
Q. E. D.
Latest technology based Operating System Online Tutoring Assistance
Tutors, at the www.tutorsglobe.com, take pledge to provide full satisfaction and assurance in Operating System help via online tutoring. Students are getting 100% satisfaction by online tutors across the globe. Here you can get homework help for Operating System, project ideas and tutorials. We provide email based Operating System help. You can join us to ask queries 24x7 with live, experienced and qualified online tutors specialized in Operating System. Through Online Tutoring, you would be able to complete your homework or assignments at your home. Tutors at the TutorsGlobe are committed to provide the best quality online tutoring assistance for Operating System Homework help and assignment help services. They use their experience, as they have solved thousands of the Operating System assignments, which may help you to solve your complex issues of Operating System. TutorsGlobe assure for the best quality compliance to your homework. Compromise with quality is not in our dictionary. If we feel that we are not able to provide the homework help as per the deadline or given instruction by the student, we refund the money of the student without any delay.
While a vacuum cleaner fails to clear the dirt efficiently, we consider of replacing it with another one. Although troubleshooting a vacuum cleaner is not a so hard task.
the chemical industry-an overview tutorial all along with the key concepts of complex characteristics of the chemical industry, what does the chemical industry produce and economic aspects
Coupled Oscillations tutorial all along with the key concepts of Oscillations of two coupled masses, Differential Equation, Normal Coordinates and Normal Modes, Modulation of Coupled Oscillations, Energy of Two Coupled Masses, Two Coupled Pendulums, Inductively Coupled LC circuits
identification of the fault in specified tv receiver - switch 'on' the tv receiver. if the picture on the screen is with snow and noisy sound, then go to the subsequent step. it verifies the receiver has snow picture fault.
tutorsglobe.com darwinism assignment help-homework help by online theories of evolution tutors
tutorsglobe.com paulings scale assignment help-homework help by online electronegativity scales tutors
Synthetic Fibres tutorial all along with the key concepts of Definition of Synthetic Fibres, Kinds of Fibres, Properties and Applications of Synthetic Fibres, Kinds of Synthetic Dyes, Dyes for Man- Made Fibres
Wittig Synthesis of C=C bond tutorial all along with the key concepts of Preparation of reagents, Mechanism and Stereochemistry of the Wittig reaction, Horner-Wadsworth-Emmons reactions and Advantages of Wittig reaction
tutorsglobe.com environmental microbiology assignment help-homework help by online environmental, food and industrial microbiology tutors
tutorsglobe.com dialysis assignment help-homework help by online renal failure tutors
tutorsglobe.com computing internal rate of return assignment help-homework help by online internal rate of return tutors
Field Effect Transistors tutorial all along with the key concepts of Field effect transistor operation, Terminals of the field effect transistor, Kinds of field effect transistors
tutorsglobe.com improved varieties assignment help-homework help by online biology in human welfare tutors
tutorsglobe.com leverage consequence on roe assignment help-homework help by online leverage tutors
Applications of UV-Visible Spectroscopy tutorial all along with the key concepts of applications of uv-visible spectroscopy in Quantitative Analysis, applications in Pharmaceutical Quantitative analysis, Application of UV/Visible Spectroscopy in the determination of pKa Values
1950128
Questions Asked
3689
Tutors
1466848
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!