Database Management SystemsStarvation

Starvation in Concurrency Control

LevelAdvanced

Duration60 mins

TopicStarvation

3 / 5

Priority Schemes in Lock Management

Not All Transactions Are Created Equal

An emergency room doesn't treat patients in arrival order. A patient with a minor bruise waits while someone experiencing cardiac arrest receives immediate attention. The system is unfair in the strict sense—later arrivals are served before earlier ones—but it is just, because it allocates resources based on urgency and need.

Database systems face similar decisions. A transaction updating stock prices that traders see live has different urgency than a nightly batch report. A transaction with a 10ms timeout from a mobile app has different constraints than a background analytics job that can run for hours. Priority schemes allow database systems to serve these different needs intelligently.

But priority creates risk. Unbounded priority leads to starvation. The challenge is designing priority systems that honor urgency while still guaranteeing eventual progress for everyone.

What You Will Learn

This page explores priority schemes in depth: static and dynamic priority assignment, priority inheritance to prevent inversion, the famous wound-wait and wait-die protocols for deadlock prevention with priority, and techniques for integrating priority with fairness guarantees. You will understand how to design priority policies that are both responsive and safe.

Priority Fundamentals

Priority in lock management is a mechanism for preferring certain transactions over others when allocating scarce resources. When multiple transactions wait for the same lock, priority determines which one receives access first.

Formal Definition:

Each transaction T is assigned a priority value P(T) from an ordered domain. When a lock becomes available:

Among all waiting transactions with compatible lock requests, the one with the highest priority is granted the lock
If multiple transactions share the highest priority, a tiebreaker (often FCFS) determines the winner

Priority can be based on:

Priority Assignment Approaches
Approach	Priority Based On	Advantages	Disadvantages
Timestamp-based	Transaction start time	Simple, inherently fair to older transactions	Newer urgent transactions may wait
Application-defined	Explicit priority from application	Business logic controls urgency	Requires application awareness
User-class	Database user or role	Administrative control	Coarse-grained, may not reflect actual need
Transaction type	Read vs. write, query class	Optimizes for workload patterns	May not match application requirements
Resource investment	Work already done by transaction	Protects sunk costs	May prioritize problematic long transactions
Deadline-based	Time remaining until deadline	Honors real-time constraints	Requires deadline specification

Static vs. Dynamic Priority:

Static Priority:

Assigned once at transaction start
Never changes during transaction lifetime
Simple to implement
Risk: low-priority transactions can starve indefinitely

Dynamic Priority:

Changes during transaction execution
Common adjustments: aging (priority increases with wait time), resource investment (priority increases with work done)
More complex but safer
Guaranteed to prevent starvation if aging is applied

Priority Is a Double-Edged Sword

Every priority-based grant is an implicit deferral of lower-priority transactions. Without safeguards, priority systems suffer from severe starvation. The remainder of this page focuses on mechanisms that harness priority's benefits while mitigating its dangers.

The Priority Inversion Problem

Priority inversion occurs when a high-priority transaction waits for a low-priority transaction, effectively demoting the high-priority transaction to the low priority level. This undermines the entire purpose of priority scheduling.

Classic Scenario:

Low-priority transaction L acquires lock on resource R
High-priority transaction H requests lock on R, must wait for L
Medium-priority transaction M starts executing (doesn't need R)
M runs uninterrupted while H waits for L

Result: H is delayed by M, even though H has higher priority than M.

Converting Mermaid diagram...

The Mars Pathfinder Incident:

Priority inversion isn't just a database problem—it famously caused issues in the Mars Pathfinder mission (1997). A low-priority task held a shared resource needed by a high-priority watchdog task, causing system resets. NASA engineers had to upload a patch to enable priority inheritance.

Impact in Databases:

In database systems, priority inversion can cause:

Critical transactions missing deadlines
SLA violations despite adequate resources
Throughput paradoxes (system is fast on average, but slow for important work)
Unpredictable latency for high-priority applications

The following sections describe solutions to prevent priority inversion.

Priority Inversion Can Be Unbounded

In the worst case, priority inversion duration is unbounded. If many medium-priority transactions continuously interrupt the low-priority lock holder, the high-priority waiter may wait indefinitely—not because of starvation, but because of inversion. This is distinct from starvation but equally dangerous.

Priority Inheritance Protocol

Priority Inheritance is the primary solution to priority inversion. When a high-priority transaction waits for a lock held by a lower-priority transaction, the lock holder temporarily inherits the higher priority.

Algorithm:

Transaction H (high priority) requests lock held by L (low priority)
L's effective priority is elevated to P(H)
L runs at elevated priority, completing its critical section faster
L releases the lock; L's priority reverts to original
H acquires the lock immediately

Formal Properties:

Bound on blocking: High-priority transaction is blocked for at most one critical section per lower-priority lock holder
Transitive inheritance: If M inherits from H, and L blocks M, then L inherits from H

priority_inheritance.pseudo
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
31
32
33
34
35
36
37
38
39
40
41
42
class PriorityInheritanceLockManager:
    
    def request_lock(transaction, resource):
        current_holder = get_lock_holder(resource)
        
        if current_holder is None:
            grant_lock(transaction, resource)
            return
        
        # Priority inheritance: boost holder if needed
        if transaction.priority > current_holder.effective_priority:
            boost_priority(current_holder, transaction.priority)
        
        # Add to wait queue
        wait_queue[resource].add(transaction)
        
        # Block until lock available
        wait_for_lock_release(resource)
        
        # Grant to highest priority waiter
        grant_to_highest_priority_waiter(resource)
    
    def boost_priority(transaction, new_priority):
        transaction.effective_priority = new_priority
        transaction.inherited_from.append(new_priority)
        
        # Transitive: if this transaction is waiting, propagate
        if transaction.waiting_for:
            holder = get_lock_holder(transaction.waiting_for)
            if holder and new_priority > holder.effective_priority:
                boost_priority(holder, new_priority)
    
    def release_lock(transaction, resource):
        # Revert priority
        transaction.inherited_from.remove_last()
        if transaction.inherited_from:
            transaction.effective_priority = max(transaction.inherited_from)
        else:
            transaction.effective_priority = transaction.base_priority
        
        release_resource(resource)
        wake_waiters(resource)

Priority Inheritance Effects
Without Inheritance	With Inheritance
High waits for low and medium	High waits only for low's critical section
Inversion duration unbounded	Inversion duration bounded
Cannot guarantee deadlines	Can bound maximum wait time
Simple lock manager	Requires priority tracking and propagation

Priority Ceiling Protocol: An Alternative

An alternative to priority inheritance is the Priority Ceiling Protocol, where each resource is assigned a priority ceiling equal to the highest priority of any transaction that may access it. A transaction can only acquire a lock if its priority exceeds the ceilings of all currently locked resources (except its own). This prevents deadlock entirely but requires advance knowledge of resource access patterns.

Wound-Wait Protocol

Wound-Wait is a deadlock prevention protocol that uses timestamp-based priority to determine whether a requesting transaction should wait or force concession from the lock holder.

Timestamp as Priority:

Each transaction receives a timestamp at start. Older transactions (lower timestamp) have higher priority. This creates a total ordering of transactions.

Wound-Wait Rules:

When transaction Tᵢ requests a lock held by Tⱼ:

If Tᵢ is older (higher priority): Tᵢ wounds Tⱼ—Tⱼ is aborted and rolled back. Tᵢ gets the lock.
If Tᵢ is younger (lower priority): Tᵢ waits for Tⱼ to release the lock.

Converting Mermaid diagram...

Why Wound-Wait Prevents Deadlock:

Deadlock requires a cycle in the wait-for graph. In Wound-Wait:

Older transactions never wait for younger transactions (they wound instead)
Wait edges always point from younger to older
Since timestamps form a total order, a cycle is impossible

Wound-Wait Properties:

Property	Description
Deadlock-free	Yes, wait edges are unidirectional (young → old)
Starvation-free	Yes, older transactions always win; restarted transactions keep original timestamp
Abort rate	Younger transactions may be aborted; can be high under contention
Work lost	Younger transactions lose all work when wounded

Critical Detail: Timestamp Preservation

When a transaction is aborted and restarted, it keeps its original timestamp. Without this, a transaction could be repeatedly aborted as new transactions arrive with earlier timestamps—causing starvation. By preserving the timestamp, the transaction eventually becomes the oldest and cannot be wounded.

Wound-Wait Favors Older Transactions

Wound-Wait is aggressive toward younger transactions—they are killed when blocking older ones. This makes it suitable for OLTP workloads with short transactions where aborts are cheap. For long-running transactions with significant work invested, the abort cost may be prohibitive.

Wait-Die Protocol

Wait-Die is the symmetric counterpart to Wound-Wait. Instead of older transactions forcing aborts, younger transactions abort themselves when they discover they can't proceed.

Wait-Die Rules:

When transaction Tᵢ requests a lock held by Tⱼ:

If Tᵢ is older (higher priority): Tᵢ waits for Tⱼ to complete.
If Tᵢ is younger (lower priority): Tᵢ dies—aborts itself and rolls back.

Converting Mermaid diagram...

Wound-Wait vs. Wait-Die Comparison
Property	Wound-Wait	Wait-Die
Older requests lock from younger	Wounds younger (abort)	Waits for younger
Younger requests lock from older	Waits for older	Dies (self-abort)
Who gets aborted	Younger (by older)	Younger (by itself)
Wait direction	Young waits for old	Old waits for young
Abort decision	Lock holder aborts requester	Requester aborts itself
Deadlock prevention	No young→old edges possible	No young→old wait edges
Typical abort count	Lower (only on direct conflict)	Higher (dies on any conflict)

Why Wait-Die Prevents Deadlock:

In Wait-Die:

Younger transactions never wait for older transactions (they die instead)
Wait edges always point from older to younger
Since older transactions are never blocked by younger ones in a wait position, cycles cannot form

Wait-Die Properties:

Property	Description
Deadlock-free	Yes, wait edges are unidirectional (old → young)
Starvation-free	Yes (with timestamp preservation)
Abort rate	Higher than Wound-Wait (younger aborts on any conflict)
Implementation	Simpler (no need to interrupt running transactions)

Choosing Between Wound-Wait and Wait-Die:

Wound-Wait: Better when older transactions should proceed quickly; aborts are "pushed" to younger transactions
Wait-Die: Better when abort decisions should be made by the requesting transaction; simpler implementation

In practice, wound-wait often results in fewer total aborts because the abort happens when there's an actual conflict requiring the lock. Wait-Die aborts preemptively, sometimes when waiting would have been fine.

Both Protocols Can Cause Unnecessary Aborts

Both wound-wait and wait-die abort transactions that might have completed successfully without deadlock. They are conservative—they prevent the possibility of deadlock by restricting wait patterns, not by detecting actual cycles. More sophisticated systems use deadlock detection (wait-for graphs) to abort only when actual deadlocks form.

Priority with Aging

Priority aging is the key technique for combining priority scheduling with fairness guarantees. The core idea: a transaction's priority increases the longer it waits, eventually reaching a level where it cannot be bypassed.

How Aging Works:

Each transaction has a base priority (assigned at start)
Each transaction has a wait time counter (since lock request)
Effective priority = base priority + f(wait time)
The function f increases with wait time
Eventually, effective priority exceeds all possible base priorities

aging_priority.pseudo
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
31
32
33
34
35
36
37
38
class AgingPriorityScheduler:
    # Priority ranges
    BASE_PRIORITY_MIN = 0
    BASE_PRIORITY_MAX = 100
    AGING_THRESHOLD = 200  # Aged transactions reach this
    
    # Aging parameters
    AGING_RATE = 2  # Priority units per second
    
    def calculate_effective_priority(transaction):
        base = transaction.base_priority
        wait_seconds = seconds_since(transaction.lock_request_time)
        
        # Linear aging
        age_bonus = wait_seconds * AGING_RATE
        
        # Cap at threshold to prevent overflow
        effective = min(base + age_bonus, AGING_THRESHOLD)
        
        return effective
    
    def select_next_transaction(wait_queue):
        """Select highest effective priority transaction"""
        best = None
        best_priority = -1
        
        for txn in wait_queue:
            eff_priority = calculate_effective_priority(txn)
            
            if eff_priority > best_priority:
                best = txn
                best_priority = eff_priority
            elif eff_priority == best_priority:
                # Tiebreaker: FCFS
                if txn.lock_request_time < best.lock_request_time:
                    best = txn
        
        return best

Aging Guarantees:

With properly configured aging, we can prove starvation-freedom:

Theorem: If the aging rate is positive and unbounded, every waiting transaction will eventually be granted its lock.

Proof Sketch:

Let T be a transaction waiting for lock L
T's priority increases at rate r per time unit
Let P_max be the maximum base priority of any transaction
After waiting time t = (P_max - P_base(T)) / r, T's effective priority exceeds all base priorities
Since new transactions arrive with base priority ≤ P_max, T cannot be bypassed
T will be granted when the current holder releases ∎

Aging Functions:

Different aging functions provide different characteristics:

Aging Function Comparison
Function	Formula	Behavior	Use Case
Linear	base + rate × wait	Steady increase	General purpose
Quadratic	base + rate × wait²	Accelerating increase	Urgency increases with wait
Logarithmic	base + rate × log(wait)	Diminishing increase	Limit aged priority range
Step	base + step if wait > threshold	Discrete jump	Hard deadline enforcement
Exponential	base × exp(rate × wait)	Rapid escalation	Strict latency requirements

Aging Parameters Must Be Tuned

The aging rate must be calibrated to your workload. Too slow: starvation still possible for low-priority transactions. Too fast: priority becomes meaningless (everyone ages to max quickly). A good starting point: set aging such that a minimum-priority transaction reaches maximum effective priority within your SLA deadline.

Priority Implementation in Real Databases

Modern database systems implement priority through various mechanisms. Understanding these implementations helps in configuring databases for optimal performance.

SQL Server Priority Mechanisms:

1. Resource Governor: Classifies workloads and assigns to resource pools with CPU, memory, and I/O limits.

-- Create classification function
CREATE FUNCTION dbo.WorkloadClassifier()
RETURNS SYSNAME WITH SCHEMABINDING
AS
BEGIN
    IF APP_NAME() LIKE '%Priority%'
        RETURN 'high_priority_group'
    RETURN 'default_group'
END

-- Create workload group with priority
CREATE WORKLOAD GROUP high_priority_group
WITH (
    IMPORTANCE = HIGH,
    REQUEST_MAX_CPU_TIME_SEC = 0,
    REQUEST_MEMORY_GRANT_TIMEOUT_SEC = 60
)

2. Lock Priority Hints: READPAST, NOWAIT, and deadlock priority.

-- Set deadlock priority (victim selection)
SET DEADLOCK_PRIORITY HIGH;  -- NORMAL, LOW

-- Skip locked rows instead of waiting
SELECT * FROM Orders WITH (READPAST) WHERE Status = 'Pending';

3. Query Priority: Part of SQL Server 2022+ workload management.

Designing Priority Policies

Effective priority policies require careful design. Here's a systematic approach to creating priority schemes that balance responsiveness with fairness.

Priority Policy Design Steps

•Identify Priority Classes — Group transactions by urgency: user-facing real-time, user-facing batch, system maintenance, background analytics. Typically 3-5 classes are sufficient.
•Assign Base Priorities — Higher priority for time-sensitive work. Leave gaps between levels for future refinement.
•Choose Aging Function — Select aging rate based on SLA requirements. Ensure lowest-priority transactions age to highest effective priority within deadline.
•Implement Inversion Prevention — Add priority inheritance to prevent high-priority transactions from being blocked by low-priority lock holders.
•Add Safeguards — Set maximum wait times, abort thresholds, and fallback behaviors for priority failures.
•Monitor and Tune — Track wait times by priority class. Adjust aging rates and base priorities based on observed behavior.

Example Priority Scheme DesignE-commerce platform with mixed workload

Input

Transaction types: checkout (real-time), inventory update (critical), product browse (user-facing), analytics (batch)

Output

Priority Assignment:
• Checkout: base=90, aging=5/sec, max_wait=2s
• Inventory: base=80, aging=3/sec, max_wait=5s  
• Browse: base=50, aging=2/sec, max_wait=10s
• Analytics: base=10, aging=1/sec, max_wait=120s

With aging, analytics reaches checkout's base priority (90) after (90-10)/1 = 80 seconds. Since analytics max_wait is 120s, fairness is guaranteed.

Avoid Priority Inflation

A common antipattern is marking everything as high priority. If 90% of transactions are 'HIGH' priority, the system effectively has no priority. Be disciplined: truly time-critical transactions should be a small minority. Use data to justify priority assignments.

Summary: Priority Schemes

We've explored priority schemes as mechanisms for preferring urgent transactions while maintaining system-wide fairness. Let's consolidate the key concepts:

Key Takeaways

•Priority enables urgency-based scheduling — Important transactions receive resources before less critical ones, enabling SLA differentiation.
•Priority inversion is dangerous — High-priority transactions blocked by low-priority holders defeats the purpose of priority. Priority inheritance solves this.
•Wound-Wait aborts younger transactions — Older (higher priority) requests force younger holders to abort. Prevents deadlock; preserves work of older transactions.
•Wait-Die aborts requesting younger transactions — Younger transactions abort themselves when conflicting with older holders. Simpler but may cause more aborts.
•Timestamp preservation is essential — Restarted transactions keep original timestamps to prevent repeated victimization and ensure eventual completion.
•Aging guarantees fairness — Priority increases with wait time, ensuring even lowest-priority transactions eventually reach highest effective priority.
•Real databases offer various priority mechanisms — Resource governors, lock timeouts, thread priorities, and workload classification provide priority control.
•Policy design requires balance — Too few priority levels lack expressiveness; too many create complexity. 3-5 well-defined levels usually suffice.

What's Next:

With priority schemes understood, we turn to timeout handling—the mechanism for limiting how long transactions wait for locks. Timeouts provide a safety net when other fairness mechanisms fail and are essential for meeting strict latency SLAs.

Page Complete

You now understand priority schemes in database concurrency control—how they work, how they interact with fairness, and how to prevent priority inversion. This knowledge enables you to configure and design priority-aware database systems that are both responsive and fair.

3 / 5

Loading learning content...

Database Management SystemsStarvation

Starvation in Concurrency Control

LevelAdvanced

Duration60 mins

TopicStarvation

3 / 5

Priority Schemes in Lock Management

Not All Transactions Are Created Equal

But priority creates risk. Unbounded priority leads to starvation. The challenge is designing priority systems that honor urgency while still guaranteeing eventual progress for everyone.

What You Will Learn

Priority Fundamentals

Formal Definition:

Each transaction T is assigned a priority value P(T) from an ordered domain. When a lock becomes available:

Among all waiting transactions with compatible lock requests, the one with the highest priority is granted the lock
If multiple transactions share the highest priority, a tiebreaker (often FCFS) determines the winner

Priority can be based on:

Priority Assignment Approaches
Approach	Priority Based On	Advantages	Disadvantages
Timestamp-based	Transaction start time	Simple, inherently fair to older transactions	Newer urgent transactions may wait
Application-defined	Explicit priority from application	Business logic controls urgency	Requires application awareness
User-class	Database user or role	Administrative control	Coarse-grained, may not reflect actual need
Transaction type	Read vs. write, query class	Optimizes for workload patterns	May not match application requirements
Resource investment	Work already done by transaction	Protects sunk costs	May prioritize problematic long transactions
Deadline-based	Time remaining until deadline	Honors real-time constraints	Requires deadline specification

Static vs. Dynamic Priority:

Static Priority:

Assigned once at transaction start
Never changes during transaction lifetime
Simple to implement
Risk: low-priority transactions can starve indefinitely

Dynamic Priority:

Changes during transaction execution
Common adjustments: aging (priority increases with wait time), resource investment (priority increases with work done)
More complex but safer
Guaranteed to prevent starvation if aging is applied

Priority Is a Double-Edged Sword

The Priority Inversion Problem

Classic Scenario:

Low-priority transaction L acquires lock on resource R
High-priority transaction H requests lock on R, must wait for L
Medium-priority transaction M starts executing (doesn't need R)
M runs uninterrupted while H waits for L

Result: H is delayed by M, even though H has higher priority than M.

Converting Mermaid diagram...

The Mars Pathfinder Incident:

Impact in Databases:

In database systems, priority inversion can cause:

Critical transactions missing deadlines
SLA violations despite adequate resources
Throughput paradoxes (system is fast on average, but slow for important work)
Unpredictable latency for high-priority applications

The following sections describe solutions to prevent priority inversion.

Priority Inversion Can Be Unbounded

Priority Inheritance Protocol

Algorithm:

Transaction H (high priority) requests lock held by L (low priority)
L's effective priority is elevated to P(H)
L runs at elevated priority, completing its critical section faster
L releases the lock; L's priority reverts to original
H acquires the lock immediately

Formal Properties:

Bound on blocking: High-priority transaction is blocked for at most one critical section per lower-priority lock holder
Transitive inheritance: If M inherits from H, and L blocks M, then L inherits from H

priority_inheritance.pseudo
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
31
32
33
34
35
36
37
38
39
40
41
42
class PriorityInheritanceLockManager:
    
    def request_lock(transaction, resource):
        current_holder = get_lock_holder(resource)
        
        if current_holder is None:
            grant_lock(transaction, resource)
            return
        
        # Priority inheritance: boost holder if needed
        if transaction.priority > current_holder.effective_priority:
            boost_priority(current_holder, transaction.priority)
        
        # Add to wait queue
        wait_queue[resource].add(transaction)
        
        # Block until lock available
        wait_for_lock_release(resource)
        
        # Grant to highest priority waiter
        grant_to_highest_priority_waiter(resource)
    
    def boost_priority(transaction, new_priority):
        transaction.effective_priority = new_priority
        transaction.inherited_from.append(new_priority)
        
        # Transitive: if this transaction is waiting, propagate
        if transaction.waiting_for:
            holder = get_lock_holder(transaction.waiting_for)
            if holder and new_priority > holder.effective_priority:
                boost_priority(holder, new_priority)
    
    def release_lock(transaction, resource):
        # Revert priority
        transaction.inherited_from.remove_last()
        if transaction.inherited_from:
            transaction.effective_priority = max(transaction.inherited_from)
        else:
            transaction.effective_priority = transaction.base_priority
        
        release_resource(resource)
        wake_waiters(resource)

Priority Inheritance Effects
Without Inheritance	With Inheritance
High waits for low and medium	High waits only for low's critical section
Inversion duration unbounded	Inversion duration bounded
Cannot guarantee deadlines	Can bound maximum wait time
Simple lock manager	Requires priority tracking and propagation

Priority Ceiling Protocol: An Alternative

Wound-Wait Protocol

Wound-Wait is a deadlock prevention protocol that uses timestamp-based priority to determine whether a requesting transaction should wait or force concession from the lock holder.

Timestamp as Priority:

Each transaction receives a timestamp at start. Older transactions (lower timestamp) have higher priority. This creates a total ordering of transactions.

Wound-Wait Rules:

When transaction Tᵢ requests a lock held by Tⱼ:

If Tᵢ is older (higher priority): Tᵢ wounds Tⱼ—Tⱼ is aborted and rolled back. Tᵢ gets the lock.
If Tᵢ is younger (lower priority): Tᵢ waits for Tⱼ to release the lock.

Converting Mermaid diagram...

Why Wound-Wait Prevents Deadlock:

Deadlock requires a cycle in the wait-for graph. In Wound-Wait:

Older transactions never wait for younger transactions (they wound instead)
Wait edges always point from younger to older
Since timestamps form a total order, a cycle is impossible

Wound-Wait Properties:

Property	Description
Deadlock-free	Yes, wait edges are unidirectional (young → old)
Starvation-free	Yes, older transactions always win; restarted transactions keep original timestamp
Abort rate	Younger transactions may be aborted; can be high under contention
Work lost	Younger transactions lose all work when wounded

Critical Detail: Timestamp Preservation

Wound-Wait Favors Older Transactions

Wait-Die Protocol

Wait-Die is the symmetric counterpart to Wound-Wait. Instead of older transactions forcing aborts, younger transactions abort themselves when they discover they can't proceed.

Wait-Die Rules:

When transaction Tᵢ requests a lock held by Tⱼ:

If Tᵢ is older (higher priority): Tᵢ waits for Tⱼ to complete.
If Tᵢ is younger (lower priority): Tᵢ dies—aborts itself and rolls back.

Converting Mermaid diagram...

Wound-Wait vs. Wait-Die Comparison
Property	Wound-Wait	Wait-Die
Older requests lock from younger	Wounds younger (abort)	Waits for younger
Younger requests lock from older	Waits for older	Dies (self-abort)
Who gets aborted	Younger (by older)	Younger (by itself)
Wait direction	Young waits for old	Old waits for young
Abort decision	Lock holder aborts requester	Requester aborts itself
Deadlock prevention	No young→old edges possible	No young→old wait edges
Typical abort count	Lower (only on direct conflict)	Higher (dies on any conflict)

Why Wait-Die Prevents Deadlock:

In Wait-Die:

Younger transactions never wait for older transactions (they die instead)
Wait edges always point from older to younger
Since older transactions are never blocked by younger ones in a wait position, cycles cannot form

Wait-Die Properties:

Property	Description
Deadlock-free	Yes, wait edges are unidirectional (old → young)
Starvation-free	Yes (with timestamp preservation)
Abort rate	Higher than Wound-Wait (younger aborts on any conflict)
Implementation	Simpler (no need to interrupt running transactions)

Choosing Between Wound-Wait and Wait-Die:

Wound-Wait: Better when older transactions should proceed quickly; aborts are "pushed" to younger transactions
Wait-Die: Better when abort decisions should be made by the requesting transaction; simpler implementation

Both Protocols Can Cause Unnecessary Aborts

Priority with Aging

How Aging Works:

Each transaction has a base priority (assigned at start)
Each transaction has a wait time counter (since lock request)
Effective priority = base priority + f(wait time)
The function f increases with wait time
Eventually, effective priority exceeds all possible base priorities

aging_priority.pseudo
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
31
32
33
34
35
36
37
38
class AgingPriorityScheduler:
    # Priority ranges
    BASE_PRIORITY_MIN = 0
    BASE_PRIORITY_MAX = 100
    AGING_THRESHOLD = 200  # Aged transactions reach this
    
    # Aging parameters
    AGING_RATE = 2  # Priority units per second
    
    def calculate_effective_priority(transaction):
        base = transaction.base_priority
        wait_seconds = seconds_since(transaction.lock_request_time)
        
        # Linear aging
        age_bonus = wait_seconds * AGING_RATE
        
        # Cap at threshold to prevent overflow
        effective = min(base + age_bonus, AGING_THRESHOLD)
        
        return effective
    
    def select_next_transaction(wait_queue):
        """Select highest effective priority transaction"""
        best = None
        best_priority = -1
        
        for txn in wait_queue:
            eff_priority = calculate_effective_priority(txn)
            
            if eff_priority > best_priority:
                best = txn
                best_priority = eff_priority
            elif eff_priority == best_priority:
                # Tiebreaker: FCFS
                if txn.lock_request_time < best.lock_request_time:
                    best = txn
        
        return best

Aging Guarantees:

With properly configured aging, we can prove starvation-freedom:

Theorem: If the aging rate is positive and unbounded, every waiting transaction will eventually be granted its lock.

Proof Sketch:

Let T be a transaction waiting for lock L
T's priority increases at rate r per time unit
Let P_max be the maximum base priority of any transaction
After waiting time t = (P_max - P_base(T)) / r, T's effective priority exceeds all base priorities
Since new transactions arrive with base priority ≤ P_max, T cannot be bypassed
T will be granted when the current holder releases ∎

Aging Functions:

Different aging functions provide different characteristics:

Aging Function Comparison
Function	Formula	Behavior	Use Case
Linear	base + rate × wait	Steady increase	General purpose
Quadratic	base + rate × wait²	Accelerating increase	Urgency increases with wait
Logarithmic	base + rate × log(wait)	Diminishing increase	Limit aged priority range
Step	base + step if wait > threshold	Discrete jump	Hard deadline enforcement
Exponential	base × exp(rate × wait)	Rapid escalation	Strict latency requirements

Aging Parameters Must Be Tuned

Priority Implementation in Real Databases

Modern database systems implement priority through various mechanisms. Understanding these implementations helps in configuring databases for optimal performance.

SQL Server Priority Mechanisms:

1. Resource Governor: Classifies workloads and assigns to resource pools with CPU, memory, and I/O limits.

-- Create classification function
CREATE FUNCTION dbo.WorkloadClassifier()
RETURNS SYSNAME WITH SCHEMABINDING
AS
BEGIN
    IF APP_NAME() LIKE '%Priority%'
        RETURN 'high_priority_group'
    RETURN 'default_group'
END

-- Create workload group with priority
CREATE WORKLOAD GROUP high_priority_group
WITH (
    IMPORTANCE = HIGH,
    REQUEST_MAX_CPU_TIME_SEC = 0,
    REQUEST_MEMORY_GRANT_TIMEOUT_SEC = 60
)

2. Lock Priority Hints: READPAST, NOWAIT, and deadlock priority.

-- Set deadlock priority (victim selection)
SET DEADLOCK_PRIORITY HIGH;  -- NORMAL, LOW

-- Skip locked rows instead of waiting
SELECT * FROM Orders WITH (READPAST) WHERE Status = 'Pending';

3. Query Priority: Part of SQL Server 2022+ workload management.

Designing Priority Policies

Effective priority policies require careful design. Here's a systematic approach to creating priority schemes that balance responsiveness with fairness.

Priority Policy Design Steps

•Identify Priority Classes — Group transactions by urgency: user-facing real-time, user-facing batch, system maintenance, background analytics. Typically 3-5 classes are sufficient.
•Assign Base Priorities — Higher priority for time-sensitive work. Leave gaps between levels for future refinement.
•Choose Aging Function — Select aging rate based on SLA requirements. Ensure lowest-priority transactions age to highest effective priority within deadline.
•Implement Inversion Prevention — Add priority inheritance to prevent high-priority transactions from being blocked by low-priority lock holders.
•Add Safeguards — Set maximum wait times, abort thresholds, and fallback behaviors for priority failures.
•Monitor and Tune — Track wait times by priority class. Adjust aging rates and base priorities based on observed behavior.

Example Priority Scheme DesignE-commerce platform with mixed workload

Input

Transaction types: checkout (real-time), inventory update (critical), product browse (user-facing), analytics (batch)

Output

Priority Assignment:
• Checkout: base=90, aging=5/sec, max_wait=2s
• Inventory: base=80, aging=3/sec, max_wait=5s  
• Browse: base=50, aging=2/sec, max_wait=10s
• Analytics: base=10, aging=1/sec, max_wait=120s

With aging, analytics reaches checkout's base priority (90) after (90-10)/1 = 80 seconds. Since analytics max_wait is 120s, fairness is guaranteed.

Avoid Priority Inflation

Summary: Priority Schemes

We've explored priority schemes as mechanisms for preferring urgent transactions while maintaining system-wide fairness. Let's consolidate the key concepts:

Key Takeaways

•Priority enables urgency-based scheduling — Important transactions receive resources before less critical ones, enabling SLA differentiation.
•Priority inversion is dangerous — High-priority transactions blocked by low-priority holders defeats the purpose of priority. Priority inheritance solves this.
•Wound-Wait aborts younger transactions — Older (higher priority) requests force younger holders to abort. Prevents deadlock; preserves work of older transactions.
•Wait-Die aborts requesting younger transactions — Younger transactions abort themselves when conflicting with older holders. Simpler but may cause more aborts.
•Timestamp preservation is essential — Restarted transactions keep original timestamps to prevent repeated victimization and ensure eventual completion.
•Aging guarantees fairness — Priority increases with wait time, ensuring even lowest-priority transactions eventually reach highest effective priority.
•Real databases offer various priority mechanisms — Resource governors, lock timeouts, thread priorities, and workload classification provide priority control.
•Policy design requires balance — Too few priority levels lack expressiveness; too many create complexity. 3-5 well-defined levels usually suffice.

What's Next:

Page Complete

3 / 5