Starvation is a situation when one transaction keeps on waiting for another transaction to release the lock. This is also called LiveLock. As we already learned in transaction management that a transaction acquires lock before performing a write operation on data item, if the data item is already locked by another transaction then the transaction waits for the lock to be released. In starvation situation a transaction waits for another transaction for an infinite period of time.
Why Starvation occurs?
1. If the transactions are not having a priority set. Generally the older transaction is given higher priority so that the transaction waiting for a longer period of time gets the lock sooner than the transaction waiting for a short period of time. If the priorities are not set then a transaction can keep on waiting while other transactions are continuously acquiring the lock on data item.
2. Resource leak: When a transaction does not release the lock after it has acquired the lock on a particular data item.
3. Denial of service attack: A Denial-of-Service (DoS) attack is an attack that is meant to shut down a machine or network, making it inaccessible to the users. DoS attack make the data item engaged so that the transaction are not able to acquire the locks.
Starvation Example
Let’s say there are three transaction T1, T2 and T3 waiting to acquire lock on a data item ‘X’. System grants a lock to the transaction T1, the other two transaction T2 and T3 are waiting for the lock to be released.
Once the transaction T1 release the lock, the lock is granted to transaction T3, now transaction T2 is waiting for the lock to be released.
While transaction T3 is performing an operation on ‘X’, a new transaction T4 enters into the system and wait for the lock. The system grants the lock to T4. This way new transactions keep on entering into the system and acquiring the lock on ‘X’ while the older transaction T2 keeps on waiting.
How to solve the starvation problem in DBMS?
1. Increase priority: One way of fixing the starvation issue is to grant higher priority to the older transaction. This way the transaction that requested for the lock first will have higher priority than the transaction that requested for the lock later.
The drawback to this solution is that a faulty transaction keeps on acquiring the lock and failing so it never gets completed and remains there with the higher priority than other transactions, thus keeps on getting the lock on a particular data item.
2. By changing the victim selection algorithm: In the above solution, we saw a drawback where a victim transaction keeps on getting the lock. By lowering the priority of a victim transaction, we can fix the drawback of above solution.
3. FCFS (First come first serve): In this approach, the transaction that entered into the system first, gets the lock first. This way no transaction keeps on waiting.
4. Wait-die Scheme: If a transaction requests a lock on data item that is acquired by another transaction then system checks for the timestamp and allow the older transaction to wait for the data item.
5. Wound-wait Scheme: In this scheme, if older transaction requests for the lock which is held by younger transaction then the system kills the younger transaction and grants the lock to older transaction.
The killed younger transaction is restarted with a specific delay but with same timestamp, this make sure that after some time when this transaction is old enough it can acquire the lock on particular data item.
These both schemes can be represented in a tabular format like this:
| Situation | Wait – Die | Wound- Wait |
|---|---|---|
| Older process needs a resource held by younger process | Older process waits | Younger process dies |
| Younger process needs a resource held by older process | Younger process dies | Younger process waits |