11. Transactions and Concurrency II

Question 1

2 main kinds of locks in DBMS

Answer 1

a transaction that wants to read data will ask for a Shared (S) lock on the appropriate resource, and a transaction that wants to write data will ask for an Exclusive (X) lock on the appropriate resource. Only one transaction may hold an exclusive lock on a resource, but many transactions can hold a shared lock on data.

Question 2

Two phase locking (2PL) - describe the scheme, 2 main rules

Answer 2

Two phase locking (2PL) is a scheme that ensures the database uses conflict serializable schedules.

The two rules for 2PL are:

• Transactions must acquire a S (shared) lock before reading, and an X (exclusive) lock before writing.
• Transactions cannot acquire new locks after releasing any locks – this is the key to enforcing serializability through locking!

Question 3

The main problem of two-phase locking

Answer 3

it does not prevent cascading aborts. For example,

• T1 updates resource A and then releases the lock on A.
• T2 reads from A.
• T1 aborts.
• In this case, T2 must also abort because it read an uncommitted value of A.

Question 4

Strict two-phase locking - describe, why needed?

Answer 4

Strict 2PL is the same as 2PL, except all locks get released together when the transaction completes.

It prevents cascading aborts (ordinary 2PL does not!)

Question 5

Lock manager architecture - describe

Answer 5

The LM maintains a hash table, keyed on names of the resources being locked.

When a lock request arrives, the Lock Manager checks if any Xact in the Granted Set or in the Wait Queue wants a conflicting lock. If so, the requester gets put into the Wait Queue. If not, then the requester is granted the lock and put into the Granted Set.

Question 6

What is a lock upgrade? How lock manager handles it?

Answer 6

lock upgrade: this is when a Xact with shared lock requests to upgrade to exclusive. The Lock Manager will add this upgrade request at the front of the queue

Question 7

Deadlock - def

Answer 7

a cycle of Xacts waiting for locks to be released by each other

Question 8

Deadlock avoidance - describe

Answer 8

One way we can get around deadlocks is by trying to avoid getting into a deadlock.

We will assign the Xact’s priority by its age: now - start time.

If T_i wants a lock that T_j holds, we have two options:

• Wait-Die: If T_i has higher priority, T_i waits for T_j; else T_i aborts
• Wound-Wait: If T_i has higher priority, T_j aborts; else T_i waits

Question 9

Deadlock detection - main mechanism

Answer 9

creating and maintaining a “waits-for” graph

Question 10

“waits-for” graph - 2 rules

which condition indicates a deadlock?

What a lock manager does to recover from a deadlock?

Answer 10

This graph will have one node per Xact and an edge from Ti to Tj if:

• Tj holds a lock on resource X
• Ti tries to acquire a lock on resource X, but Tj must release its lock on resource X before Ti can acquire its desired lock.

cycles in a graph indicate a deadlock. If a cycle is found, we will ”shoot” a Xact in the cycle and abort it to break the cycle.

Question 11

Lock granularity - tree view of the database. Why needed?

Answer 11

The top-level is the database. The next level is the table, which is followed by the pages of the table. Finally, the records of the table themselves are the lowest level in the tree.

It helps to imagine how locking on different levels works. When we place a lock on a node, we implicitly lock all of its children as well. E.g. if you place a lock on a page, then you’re implicitly placing a lock on all the records.

Question 12

What is IX, IS, and SIX locks?

Answer 12

• IS: Intent to get S lock(s) at a finer granularity.
• IX: Intent to get X lock(s) at a finer granularity.

Note: that two transactions can place an IX lock on the same resource – they do not directly conflict at that point because they could place the X lock on two different children! So we leave it up to the database manager to ensure that they don’t place X locks on the same node later on while allowing two IX locks on the same resource.

• SIX: Like S and IX at the same time. This is useful if we want to prevent any other transaction from modifying a lower resource but want to allow them to read the whole subtree.

Question 13

Multiple Granularity Locking Protocol

Answer 13

1. Each Xact starts from the root of the hierarchy.
2. To get S or IS lock on a node, must hold IS or IX on the parent node.
3. To get X or IX on a node, must hold IX or SIX on the parent node.
4. Must release locks in bottom-up order.
5. 2-phase rules enforced as well