1
$\begingroup$

Consider the following variant of the two phase locking protocol. Suppose a transaction $T$ accesses (for read or write operations), a certain set of objects ${O_1,...,O_k}$.

The modified algorithm works as :

Step 1. $T$ acquires exclusive locks to $O_1, . . . , O_k$ in increasing order of their ids.

Step 2. The required operations are performed.

Step 3. All locks are released.

Does this protocol ensure serializability and freedom from deadlock?

Since the locks are being obtained in an increasing order of their ids, the circular wait condition cannot prevail and a deadlock can thus be avoided. But does it ensure serializability? How to argue with respect to the serialization aspect?

$\endgroup$
2
$\begingroup$

The question is not clear about the details, but assuming said resources are always locked-then-accessed sequentially, then a deadlock is not possible to occur. Since the locks are always obtained in the same order, precedence would prevent any cross-lock scenarios. Once a transaction acquires the lock for the first item in the list, other transactions will have to wait for that lock to be released.

Even if the locks are acquired-released on one-by-one basis, deadlocks would not occur. Supposing 2 transactions T1 and T2 are concurring the locks for the resources A, B, C, the sequence of events would be:

  1. T1 acquires A
  2. T2 waits A
  3. T1 releases A
  4. T2 acquires A
  5. T1 acquires B
  6. T2 releases A
  7. T2 waits B

Then there's the scenario where T2 overtakes T1. In that case nothing would change, T2 would then be the contentious transaction (holding everyone else behind). But no deadlocks.

  1. T1 acquires A
  2. T2 waits A
  3. T1 releases A
  4. T2 acquires A
  5. T2 releases A
  6. T2 acquires B
  7. T1 waits B
  8. T2 releases B
  9. T2 acquires C
  10. T1 acquires B

The number of concurrent transactions is not important. Possibly, the great the numbers of transactions concurring, the greater the number of overtakes. It would be contentious and some transactions, even though they entered first, could possibly lag way behind other transactions that arrived later. In edge cases, some transactions could give the impression they are deadlocked when in fact they are not (they are just being thrown around by the OS scheduler).

Also, in most (all?) Systems locks are not served on the the same order they are requested. T1, T2, T3 could request a lock for the resource A, but T3 could be the first to get it. It's very likely the locks will be given in the order they were requested, but it's not guaranteed, especially if the system running the process is already dealing with too many threads. In such cases the OS can reorder the threads, thus changing the order the locks are acquired. No deadlocks still, but some transactions could take abnormally longer than others.

The case you describe (all locks being acquired and released at once) could be even more contentious, and could become a pain in the arse as the load in the system increases - because strange (and often *un-*debuggable) things starts to happen.

Still no deadlocks though.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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