Pessimistic Concurrency Control (PCC)

2-phase locking (2PL) is a pessimistic concurrency control protocol that uses locks to prevent concurrent transactions from interfering. These locks indicate that a record is being used by a transaction, so that other transactions can determine whether it is safe to use it or not.

Types of locks

There are two basic types of locks used in this protocol:

• Write (exclusive) locks: These locks are acquired when a record is going to be written (inserted/updated/deleted).
• Read (shared) locks: These locks are acquired when a record is read.

Interaction between write (exclusive) locks and read (shared) locks

• A read lock does not block a read from another transaction. This is why it is also called shared because multiple read locks can be acquired at the same time.
• A read lock blocks a write from another transaction. The other transaction will have to wait until the read operation is completed and the read lock is released. Then, it will have to acquire a write lock and perform the write operation.
• A write lock blocks both reads and writes from other transactions, which is also the reason it’s also called exclusive. The other transactions will have to wait for the write operation to complete and the write lock to be released; then, they will attempt to acquire the proper lock and proceed.

If a lock blocks another lock, they are called incompatible. Otherwise, they are called compatible.

As a result, the relationships described above can be visualized in a compatibility matrix, as shown in the following illustration.

The astute reader might notice a similarity between this matrix and the definition of conflicts in conflict serializability. This is not a coincidence. The two-phase locking protocol makes use of these locks to prevent cycles of these conflicts from forming, as described before.

Each type of conflict is represented by an incompatible entry in the above matrix.

Phases where transactions acquire or release locks

In 2-phase locking protocol, transactions acquire and release locks in two distinct phases:

Expanding phase

In this phase, a transaction is allowed to only acquire locks, but not release any locks.

Shrinking phase

In this phase, a transaction is allowed to only release locks, but not acquire any locks.

The following illustration shows these phases.

It’s been implied so far that locks are held per record. However, it’s important to note that if the associated database supports operations based on predicates, there must also be a way to lock ranges of records (predicate locking), e.g., all the customers of ages between 23 and 29. This is to prevent anomalies like phantom reads.

As proven by FrankingM. J. Franking, “Concurrency Control and Recovery,” SIGMOD ’92, 1992., this protocol only allows serializable executions to happen.

A schedule generated by two-phase locking will be conflict equivalent to a serial schedule, where transactions are serialized in the order they completed their expanding phase.

There are some slight variations of the protocol that can provide some additional properties, such as:

• Strict two-phase locking (S2PL)
• Strong strict two-phase locking (SS2PL)

Deadlocks

The locking mechanism introduces the risk for deadlocks, where two transactions might wait on each other for the release of a lock, thus never making progress. This is shown in the following illustration.

Ways to deal with deadlocks

In general, there are two ways to deal with these deadlocks.

Prevention

This method prevents the deadlocks from being formed in the first place.

For example, this can be done if transactions know all the locks they need in advance and acquire them in an ordered way. This is typically done by the application since many databases support interactive transactions and are thus unaware of all the data a transaction will access.

Detection

This method detects deadlocks that occur, and breaks them. For example, this can be achieved by keeping track of which transaction a transaction waits on, using this information to detect cycles that represent deadlocks, and then forcing one of these transactions to abort. This is typically done by the database, without the application having to do anything extra.