1
$\begingroup$

I am learning 2-phase locking and its unclear to me how it achieves/guarantees before-or-after atomicity (i.e. serilizability).

I went to the following notes

http://ocw.mit.edu/resources/res-6-004-principles-of-computer-system-design-an-introduction-spring-2009/online-textbook/atomicity_open_5_0.pdf

on page 9-73 it argues informally:

"Informally, once a transaction has acquired a lock on a data object, the value of that object is the same as it will be when the transaction reaches its lock point, so reading that value now must yield the same result as waiting till then to read it. Furthermore, releasing a lock on an object that it hasn’t modified must be harm­ less if this transaction will never look at the object again, even to abort. A formal argument that two-phase locking leads to correct before-or-after atomicity can be found in most advanced texts on concurrency control and transactions"

But I didn't really understand the argument and it seems that a formal proof is not trivial or maybe too complicated. So I was seeking an alternate intuitive argument to its correctness. I don't really understand why that is the reason but if someone else has a better way of explaining it or a different perspective, it would be greatly appreciated!

$\endgroup$

1 Answer 1

1
$\begingroup$

I'll try to phrase it from an intuitive perspective.

Anomalies occur when there are conflicts, i.e. when two different transactions write on the same object (clearly if they only read stuff nothing can go wrong). For example, here:

r1(x), r2(x), w1(x) // at this point, r2 read garbage

2PL is a way to prevent this kind of stuff from happening by putting a lock on every object a transaction deals with, and removing the locks when it's done. The lock can be a read lock (when T reads an object) or a write lock (when T writes an object) and the rules are simple:

  1. refuse a read-lock if a write-lock (from a different T) already held
  2. refuse a write-lock if any lock (from a different T) already held.

The idea behind these is that you don't want T2 to read something that T1 is going to overwrite (see the first example), and you don't want T2 to write onto something that was previously read or written by T1.

With 2PL, when T wants to read/write on an object it will ask permissions to put a lock on it, and this permission will be granted (or denied) based on the two rules above.

In the example I gave you, with 2PL T1 would have a write-lock on x so r2(x) would not happen before w1(x) because the read-lock would not be granted (rule 1).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.