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.
tutorsglobe.com type of leverage assignment help-homework help by online leverage tutors
tutorsglobe.com electron transport chain assignment help-homework help by online krebs cycle tutors
tutorsglobe.com photoautotrophic bacteria assignment help-homework help by online nutrition in bacteria tutors
Protozoa tutorial all along with the key concepts of Locomotor structures, Food gathering structures, Osmoregulatory structures, Protective Structures, Life cycle phases-Protozoa and Protozoan Reproduction
tutorsglobe.com important products derived from cholesterol assignment help-homework help by online cholesterol biosynthesis tutors
tutorsglobe.com dynamics of filtration assignment help-homework help by online mechanism of urine formation tutors
www.tutorsglobe.com offers energetics homework help, energetics assignment help, online tutoring assistance, physical chemistry solutions by online qualified tutor's help.
The limitations of diagrammatic presentation of cost information - Diagrams and graphs do not depict perfectly accurate data. They are usually based on approximations. So these are suitable for general guidance and not for taking particular decisions.
Imperfection in Solids tutorial all along with the key concepts of Crystalline Defects, Point Defects, Vacancy, Self-interstitial or interstitialcy, Impurities, Schottky defect, Frenkel defect, Linear Defects, Edge dislocation, Screw dislocation, Volume (Bulk) Defects
Proboscidea-Sirenia-Carnivora tutorial all along with the key concepts of Features of Order Proboscidea, Features of Order Sirenia and Features of Order Carnivora
www.tutorsglobe.com offers solid-state chemistry homework help, solid-state chemistry assignment help, online tutoring assistance, physical chemistry solutions by online qualified tutor's help.
tutorsglobe.com cost of debt assignment help-homework help by online capital structure tutors
tutorsglobe.com cloning assignment help-homework help by online modern genetics tutors
i) water level all the time should be above the heater element if not the element gets overheated and might burst.
Temperature Measurement-Heat of Dissolution-Neutralization tutorial all along with the key concepts of Heat of dissolution, Description on Heat of Neutralization, Calculations
1959352
Questions Asked
3689
Tutors
1477783
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!