Understanding the Starvation Problem - Starvation in Concurrency Control | OneNoughtOne

0/278

Database Management SystemsStarvation

Starvation in Concurrency Control

LevelAdvanced

Duration60 mins

TopicStarvation

1 / 5

Understanding the Starvation Problem

The Silent Killer of Database Performance

Imagine a busy restaurant where new customers continuously arrive, and the host always seats the most recent arrivals first. Early customers, despite arriving on time and waiting patiently, watch helplessly as newcomers are seated before them. Hours pass. The early customers remain standing. They've been starved of service—not because resources are unavailable, but because the allocation policy systematically disadvantages them.

This scenario captures the essence of starvation in database systems: a condition where a transaction waits indefinitely for a resource that is repeatedly granted to other transactions. Unlike deadlock, where transactions are blocked in a cycle and cannot proceed, starvation occurs when transactions could proceed but are perpetually passed over by the scheduling algorithm.

What You Will Learn

By the end of this page, you will have a deep understanding of what starvation is, how it differs from deadlock, the conditions that cause it, and why it represents a critical challenge in the design of fair and efficient concurrency control systems. You'll be able to identify starvation-prone scenarios and understand the theoretical foundations for preventing them.

Formal Definition of Starvation

Starvation (also called indefinite postponement or livelock in some contexts) occurs when a transaction is perpetually denied access to a shared resource, despite the resource being repeatedly available and granted to other transactions.

Formal Definition:

A transaction T is said to suffer starvation if:

T requests access to a resource R at time t₀
The resource R becomes available and is granted to other transactions at times t₁, t₂, t₃, ... where tᵢ > t₀ for all i
There exists no finite time t_final at which T is guaranteed to receive access to R

In essence, starvation violates the liveness property of a system—the guarantee that every request will eventually be satisfied. A system that permits starvation is unfair, even if it is deadlock-free and achieves high throughput.

Starvation vs. Deadlock: A Critical Distinction

Deadlock occurs when transactions are blocked in a circular wait—none can proceed. Starvation occurs when a transaction can proceed but isn't allowed to. A deadlock-free system can still suffer from starvation. This distinction is crucial: solving deadlock doesn't automatically solve starvation, and many deadlock prevention schemes can actually increase starvation risk.

Starvation vs. Deadlock Comparison
Property	Deadlock	Starvation
Nature	Circular blocking—no transaction can proceed	Indefinite waiting—transaction could proceed but doesn't
Detection	Wait-for graph contains a cycle	No structural pattern; requires analysis over time
Effect	Transactions halt permanently until intervention	Transaction waits indefinitely while others proceed
Resolution	Abort one or more transactions to break cycle	Modify scheduling policy to ensure fairness
System Progress	System makes no progress (stuck)	System makes progress, but unfairly
Cause	Resource allocation creates circular dependency	Scheduling policy systematically disadvantages some transactions
Recovery	Deterministic (abort and restart)	May require priority adjustment or policy change

Causes of Starvation

Starvation arises from the interaction between resource contention patterns and scheduling policies. Understanding the root causes is essential for designing systems that guarantee fairness. The primary causes can be categorized as follows:

Primary Causes of Starvation

•Priority-Based Scheduling — When transactions with higher priority are always serviced first, low-priority transactions can wait indefinitely as high-priority transactions continuously arrive. This is the classic cause of starvation.
•Shared Lock Preference — If a resource has multiple readers (holding shared locks) and a writer waiting, new readers may be granted access continuously, preventing the writer from ever acquiring an exclusive lock.
•Lock Upgrade Conflicts — When multiple transactions hold shared locks and each attempts to upgrade to an exclusive lock, they block each other while new shared lock requests may continue to be granted.
•Biased Lock Queuing — First-Come-First-Served (FCFS) should prevent starvation, but some implementations prioritize certain lock types, inadvertently creating unfairness.
•Hot Spot Resources — Resources accessed by many transactions become contention points. Without careful queue management, some transactions consistently lose the race for access.
•Timestamp Ordering Conflicts — In timestamp-based protocols, younger transactions may repeatedly cause older transactions to abort and restart, preventing the older transactions from ever completing.

The Reader-Writer Problem: A Classic Starvation Scenario

Consider a database system where:

Multiple transactions can hold shared locks (S-locks) simultaneously for reading
Only one transaction can hold an exclusive lock (X-lock) for writing
X-lock requests must wait until all S-locks are released

Now imagine this sequence:

Transaction T₁ acquires an S-lock on resource R
Transaction T₂ (writer) requests an X-lock on R → waits
Transaction T₃ requests an S-lock on R → granted (compatible with T₁)
Transaction T₁ releases its S-lock
Transaction T₄ requests an S-lock on R → granted (compatible with T₃)
Transaction T₃ releases its S-lock
... pattern continues indefinitely

Transaction T₂ never gets access to R because new readers keep arriving before all existing readers release their locks. The writer is starved.

Converting Mermaid diagram...

Mathematical Model of Starvation

To rigorously analyze starvation, we can model it using queuing theory and probabilistic analysis. This mathematical framework helps us understand when starvation is likely and how severe it might be.

Model Assumptions:

Transactions arrive at rate λ (Poisson process)
Service time (lock hold time) follows an exponential distribution with mean 1/μ
The system uses FCFS scheduling within each priority class

Key Metrics:

Queuing Theory Metrics for Lock Management
Metric	Symbol	Definition
Arrival Rate	λ	Number of lock requests per unit time
Service Rate	μ	Number of locks granted/released per unit time
Utilization	ρ = λ/μ	Fraction of time resource is locked
Expected Wait Time	W	Average time a transaction waits for lock
Queue Length	L	Average number of transactions waiting

Starvation in Priority Queuing Systems:

Consider a system with k priority classes, where class 1 has the highest priority. The expected waiting time for a transaction in class i is:

W_i = W_0 / [(1 - σ_{i-1})(1 - σ_i)]

Where:

W₀ = base waiting time without priority
σᵢ = Σⱼ₌₁ⁱ ρⱼ = cumulative utilization of classes 1 through i

Critical Insight:

If σᵢ approaches 1 for any i, the waiting time for lower priority classes (i+1, i+2, ...) approaches infinity. This is the mathematical definition of starvation:

Starvation occurs when lim_{t→∞} P(Tᵢ completes) = 0 for transactions in priority class i.

In practical terms: if high-priority transactions consume all available system capacity (ρ ≥ 1), low-priority transactions will wait forever.

Starvation-Free Condition

A scheduling system is starvation-free if and only if every transaction that enters the waiting queue is guaranteed to be serviced in finite time. Mathematically, this requires that the scheduling algorithm satisfies the bounded waiting condition: there exists a finite upper bound B such that no transaction waits longer than B time units before being granted access.

Real-World Manifestations

Starvation is not merely a theoretical concern—it manifests in production database systems with serious consequences. Understanding these real-world scenarios helps database administrators and developers identify and mitigate starvation risks.

Production Starvation Scenarios

•OLAP vs. OLTP Conflicts — Long-running analytical queries (OLTP) may starve short transactional updates (OLAP), or vice versa, depending on the lock scheduling policy. A reporting query scanning millions of rows can block time-sensitive order processing.
•Schema Migration Starvation — ALTER TABLE operations requiring exclusive table locks may wait indefinitely as continuous streams of SELECT queries hold shared locks. Developers wait hours for what should be a millisecond operation.
•Batch Processing Blockages — Nightly batch jobs that update large datasets may starve interactive user transactions, or continuous interactive traffic may prevent batch jobs from ever acquiring necessary locks.
•Index Maintenance Delays — Background index rebuilds requiring exclusive access to index structures may be perpetually delayed by query workloads that continuously read from the index.
•Deadlock Recovery Side-Effects — Systems that always abort the same transaction type during deadlock resolution (e.g., always the younger transaction) may cause repeated starvation of short-lived, frequently-restarted transactions.

Real-World Case Study: E-Commerce Black Friday

During a major e-commerce sale event

Input

Scenario: Inventory updates for popular items compete with order placement transactions

Output

Problem: Continuous order placement holds shared locks on inventory table, preventing inventory updates from acquiring exclusive locks. Result: Inventory counts become stale, overselling occurs, and manual intervention is required to force inventory updates through.

Symptoms of Starvation in Production:

Asymmetric Wait Times — Some transaction types consistently show 100x+ longer wait times than others
Stuck ThreadPool Workers — Worker threads appear to hang indefinitely waiting for locks
Queue Growth Without Progress — Lock wait queues grow but specific requests never reach the front
Timeout Cascades — Starved transactions hit timeouts, causing downstream failures
Resource Utilization Paradox — System appears underutilized (low CPU, I/O) but transactions are blocked

Database administrators often misdiagnose starvation as deadlock or performance issues. The key diagnostic signal is differential wait times—when transactions of similar complexity have wildly different completion times due to lock acquisition patterns.

The Liveness Property

In distributed systems and concurrency theory, liveness is a fundamental correctness property that guarantees something good eventually happens. It contrasts with safety properties, which guarantee that something bad never happens.

Applied to Database Locking:

Safety: "No two transactions hold conflicting locks simultaneously" (mutex is never violated)
Liveness: "Every transaction that requests a lock will eventually acquire it"

A lock manager that prevents deadlock may still violate liveness if it permits starvation. This is why fairness becomes a critical design requirement.

Safety vs. Liveness in Lock Management
Property Type	Example Property	Violation Consequence
Safety	Mutual exclusion	Data corruption
Safety	Deadlock-freedom	System hangs completely
Liveness	Starvation-freedom	Some transactions never complete
Liveness	Bounded waiting	Unpredictable transaction latencies
Liveness	Lock-freedom	Progress depends on scheduler fairness

The Fairness Hierarchy:

Computer scientists have identified several levels of fairness guarantees:

No Starvation (Weak Fairness): Every continuously enabled transaction will eventually execute.
- A transaction waiting for a lock will get it eventually, though no bound is guaranteed.
Bounded Waiting (Strong Fairness): Every transaction waiting for a lock will get it within a bounded number of steps.
- Example: FCFS queuing with a maximum queue depth.
Lock-Free: At least one transaction makes progress, but individual transactions may starve.
- Common in non-blocking algorithms; requires starvation-prevention layer.
Wait-Free: Every transaction makes progress; no transaction can starve.
- Most restrictive and expensive to implement; rarely used in databases.

Database systems typically aim for bounded waiting fairness as a practical balance between performance and fairness guarantees.

Theoretical Foundation: The Bakery Algorithm

Leslie Lamport's Bakery Algorithm (1974) was one of the first algorithms proven to be starvation-free. Like taking a number at a bakery counter, each transaction receives a ticket and is served in ticket order. This simple invariant—serve in ticket order—guarantees bounded waiting. Modern database lock managers often use similar ticket-based or timestamp-based approaches.

Starvation Across Different Lock Types

Different lock types create different starvation patterns. Understanding how starvation manifests across lock modes helps in designing more robust concurrency control mechanisms.

Shared Lock Starvation Pattern:

Shared locks rarely create starvation among readers because they are compatible with each other. However, they frequently cause writer starvation when:

A continuous stream of readers requests S-locks
Readers release and new readers acquire before all readers are cleared
Writers waiting for X-locks are perpetually blocked

Scenario:

Time 0: T1 acquires S-lock
Time 1: T2 (writer) requests X-lock → waits
Time 2: T3 acquires S-lock (compatible)
Time 3: T1 releases S-lock
Time 4: T4 acquires S-lock (compatible with T3)
... writer never gets lock ...

Solution Approaches:

Read-preference with write timeout: Allow limited reader grants before blocking for pending writers
Write-preference: Once a writer is waiting, block new readers
Fair ordering: Process requests in strict arrival order

Detecting Starvation

Unlike deadlock, which has a clear structural signature (cycles in the wait-for graph), starvation is difficult to detect because it is defined by temporal rather than structural properties. A transaction is starved not because of its position in a graph, but because of how long it has waited relative to when it should have been served.

Detection Approaches:

Starvation Detection Techniques

•Wait Time Monitoring: Track how long each transaction has waited for each lock. Flag transactions exceeding a configurable threshold. This is the most common approach in production systems.
•Throughput Differential Analysis: Compare transaction completion rates across transaction types. Significant disparities may indicate starvation affecting certain transaction classes.
•Queue Position Tracking: Monitor when transactions enter lock queues and how often they are bypassed by later arrivals. A transaction that is repeatedly jumped indicates starvation risk.
•Historical Pattern Analysis: Aggregate wait time statistics over time. Increasing median wait times for certain transaction types signals emerging starvation conditions.
•Fairness Index Calculation: Compute the Jain's Fairness Index or similar metrics across transaction classes. Values significantly below 1.0 indicate unfair resource distribution.

starvation_monitor.sql
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
-- SQL Server: Detect potential starvation
-- Transactions waiting more than 10 seconds
 
SELECT 
    r.session_id,
    r.blocking_session_id,
    r.wait_type,
    r.wait_time / 1000.0 AS wait_time_seconds,
    t.text AS query_text,
    r.start_time,
    DATEDIFF(SECOND, r.start_time, GETDATE()) AS total_elapsed_seconds
FROM sys.dm_exec_requests r
CROSS APPLY sys.dm_exec_sql_text(r.sql_handle) t
WHERE r.wait_type LIKE 'LCK%'  -- Lock-related waits
  AND r.wait_time > 10000      -- More than 10 seconds
ORDER BY r.wait_time DESC;
 
-- PostgreSQL: Long-running lock waits
SELECT 
    pid,
    usename,
    query,
    state,
    wait_event_type,
    wait_event,
    NOW() - query_start AS duration
FROM pg_stat_activity
WHERE wait_event_type = 'Lock'
  AND NOW() - query_start > INTERVAL '10 seconds'
ORDER BY duration DESC;

Detection Is Not Prevention

Detecting starvation after it occurs allows for reactive intervention but doesn't prevent the business impact. Production systems should focus on starvation prevention through proper scheduling policies rather than relying solely on detection. Detection is valuable for monitoring and alerting, but prevention must be built into the concurrency control design.

Summary: Understanding Starvation

We've established a comprehensive understanding of the starvation problem in database concurrency control. Let's consolidate the key concepts:

Key Takeaways

•Starvation is indefinite postponement — A transaction waits forever for a resource that is repeatedly granted to others, violating the liveness property.
•Starvation differs from deadlock — Deadlock is structural (circular wait), starvation is temporal (unfair scheduling). A deadlock-free system can still starve transactions.
•Root causes include scheduling policies — Priority-based scheduling, reader preference, and biased queuing all create starvation conditions.
•The reader-writer problem is iconic — Continuous readers can starve writers indefinitely, a classic scenario in database systems.
•Starvation violates liveness — The guarantee that 'something good eventually happens' is broken when transactions wait forever.
•Detection requires temporal analysis — Unlike deadlock's structural detection, starvation detection relies on wait time monitoring and fairness metrics.
•Prevention is preferable to detection — Building fairness into scheduling policies prevents business impact, while detection only enables reactive mitigation.

What's Next:

Now that we understand what starvation is and why it occurs, the next page examines fairness in depth—the formal property that prevents starvation. We'll explore different fairness guarantees, their mathematical definitions, and how database systems implement fairness policies.

Page Complete

You now have a deep understanding of the starvation problem—its definition, causes, manifestations, and detection methods. This foundation prepares you to understand fairness policies and prevention strategies in the subsequent pages.