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.
It is fairly common for one company to be capable to exercise control over the activities of another.
tutorsglobe.com transmission electron microscopy assignment help-homework help by online light and electron microscope tutors
a subtractor can be designed by using similar approach like that of an adder in electronics.
tutorsglobe.com fiscal policy and capital formation assignment help-homework help by online objectives of fiscal policy tutors
Theory and lecture notes of First Welfare Theorem all along with the key concepts of first welfare theorem, Economics of Welfare, Economics, Walrasian equilibrium. Tutorsglobe offers homework help, assignment help and tutor’s assistance on First Welfare Theorem.
Classification of Algae-I tutorial all along with the key concepts of Criteria for categorization of Algae, Prokaryotic Algae, Eukaryotic Algae, Division CHLOROPHYTA, Division PHAEOPHYTA, Division RHODOPHYTA and Division XANTHOPHYTA
tutorsglobe.com insulin assignment help-homework help by online co-ordination systems tutors
Human helminths infections tutorial all along with the key concepts of Nematode Infections, Enterobius vermicularis, Ascaris lumbricoides, Trichuris trichiuria, Lymphatic filariasis, Onchocerca volvulus, Digenean Trematode Infections and Cestode Infections
The Cell tutorial all along with the key concepts of Cell Concept, Cell Size-Shape and Organization, Nucleus, Cell Membrane, Endoplasmic Reticulum, Cytoplasmic Matrix, Kinds of Cells
tutorsglobe.com factors affecting viscosity assignment help-homework help by online viscosity tutors
Thermoelectric-Photoelectric Thermionic Effects tutorial all along with the key concepts of Thermoelectric Effect, Seebeck and Peltier Effects, Photoelectric Effect and Thermionic Emission
tutorsglobe.com laboratory diagnosis of mycetoma assignment help-homework help by online mycetoma tutors
Amplifiers and its classification tutorial all along with the key concepts of Amplifier Gain, Efficiency, Class AB, Series-Fed Class A Amplifier, DC Bias Operation, AC Operation, Power Considerations, Using peak signals
Bryophyta and Pteridophyta tutorial all along with the key concepts of Life Cycles of bryophyta and pteridophyta, characteristics of Liverworts, Moses and Pteridophytes-Ferns
tutorsglobe.com crusaders and muslims-12 century assignment help-homework help by online history tutors
1955639
Questions Asked
3689
Tutors
1453509
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!