Failures and antipatterns · Intermediate

Starvation: progress for some, indefinite waiting for others

Inspect fairness and per-request waiting when aggregate throughput conceals excluded work.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Aggregate progress can hide exclusion
  2. Repeated overtaking
  3. Fairness has costs
  4. Observe the wait distribution
  5. Ask Logeia about this articleCheck your understanding

Aggregate progress can hide exclusion

Starvation occurs when some participants keep making progress while another repeatedly fails to obtain a needed resource. It differs from a deadlock in which a wait cycle prevents the relevant participants from proceeding. Healthy aggregate throughput can coexist with one request never completing.

Inspect maximum wait and the age of individual queued requests as well as average latency. If newer requests repeatedly overtake older ones, the service can report attractive averages while a small group receives unacceptable treatment. A throughput metric does not establish a fairness property.

Repeated overtaking

Consider a running thread that immediately reacquires a lock after releasing it, repeatedly overtaking another waiter. Mutual exclusion can correctly protect shared data without guaranteeing a fair acquisition order. Safety of the critical section and fairness of access are distinct properties.

A priority queue has an analogous risk if high-priority work arrives continuously. Low-priority work may never be selected under the policy. When introducing priorities, define how old work eventually receives service instead of assuming that every finite individual task will necessarily finish.

Fairness has costs

Possible responses include explicit queue ordering, a synchronization primitive with a suitable fairness policy or aging that raises the priority of long-waiting work. Stronger ordering can cost throughput or make later work wait behind a slow item at the front.

Choose according to an acceptable waiting contract, not only peak speed. State which participants the policy treats fairly: all threads, requests within one user or a business-defined class. Different definitions can lead to different implementations, and a local fair lock does not automatically establish fairness across the entire service.

Observe the wait distribution

Vary concurrency and priority while recording how long each request waits and how often it is overtaken. A short run in which all requests finish is useful evidence, but not a proof of starvation freedom under every schedule. The policy’s assumptions still need analysis.

Timeouts can also hide excluded requests from a completion-only latency metric. Include expired and canceled work in the assessment. Otherwise a supposed fairness improvement may merely remove the worst observations from the reported distribution rather than delivering better service to those requests.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 18

Understand the systems behind the web · STEP 15

Choose a learning path