--%>
Assignment Help - homework help

  Proof of equivalence of lock protocol and Hierarchical locks

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.