Five of this site's other ten Concurrency entries each care about one of two things: can two or more processes ever be inside the same critical section at once (Peterson's algorithm, Lamport's bakery algorithm, Dekker's algorithm), or can a whole system of processes get permanently stuck waiting on each other (the Dining Philosophers Problem, the Producer-Consumer Problem). The other five, the Treiber Stack, the Michael-Scott Queue, Hazard Pointers, Epoch-Based Reclamation, and the Harris Linked List, care about neither — they have no critical section to protect and nothing that can deadlock, just lock-free structures that can be silently (or momentarily) corrupted under their own specific hazards. Courtois, Heymans & Parnas posed a third question in 1971: a block of shared data has readers, who only look at it and never conflict with each other, and writers, who need it entirely to themselves. Any number of readers may overlap; a writer may never overlap with anyone, reader or writer. Nothing here can deadlock the way the dining philosophers can — there's no cycle of processes each holding one resource and wanting another, just one shared resource and a yes/no admission rule. The question this page asks instead is starvation: the system as a whole keeps making progress (readers keep reading, writers keep writing), but can one specific class of request — readers, or writers — end up waiting forever anyway, skipped every single time the resource comes free? Same discipline as this site's other Concurrency pages: every claim below comes from exhaustively searching every reachable interleaving of a small state machine, not a hand-picked trace.
Pick an admission policy, how many readers there are and how many times each one tries to read, and how many times the single writer tries to write, then either step through by hand — each Step Ri/Step W button runs that process's next pending action, or reports it's blocked — or press Explore all schedules to search every reachable interleaving at once. Try Readers-preference at the defaults and step the writer's request in first, then keep stepping readers: every reader goes on ahead of it. Switch to Writers-preference and do the opposite — get a reader waiting first, then request the writer: the writer now cuts in. Switch to Fair (ticket order): whichever requested first goes first, every time.
There is one shared resource, R reader processes (any number of them may hold it at once),
and a single writer process (needs it alone, which also rules out two writers overlapping — a plain
mutual-exclusion requirement this page doesn't need to model separately with only one writer in play).
Every request — "I'd like to read" or "I'd like to write" — is either granted immediately, or made to wait.
The three policies below answer the same two questions differently: can a reader that shows up after a
writer is already waiting still go first? and can a writer that shows up after a reader is already
waiting still go first?
Readers-preference grants a reader's request any time no writer currently holds the resource — full stop, independent of whether a writer happens to be waiting. A writer is granted only once every current reader has finished and no other writer is active. The consequence falls straight out of the rule: every time a reader finishes, if any reader is ready to go — including one whose request arrived well after the writer's — it's free to start again, because the rule never distinguishes an old request from a new one. As long as fresh reader requests keep arriving before the current batch fully drains, the writer's wait has no built-in ceiling.
Writers-preference is the mirror image: a reader's request is granted only if no writer currently holds the resource and no writer is currently waiting either. A writer is granted once every current reader has finished and no other writer is active — same rule as readers-preference, applied to the other side. Once a writer's request is pending, every reader request that arrives afterward is turned away at the door, even if an earlier reader is still waiting too; the moment the resource frees up, the waiting writer (or the next one already queued behind it) goes first. A reader that's been waiting the whole time has no guarantee it ever gets a turn if writers keep arriving.
Fair (ticket order) borrows Lamport's bakery algorithm's idea directly: every request gets a ticket number at the moment it's made, and a request may only be granted once nothing with a smaller ticket is still waiting or active. A reader checks this against every pending writer; a writer checks it against every pending reader and writer (plus needing no reader currently active, same as the other two policies). Because a ticket is assigned once and never changes, and tickets only grow, a request that is already waiting can never be leapfrogged by one made later — which is exactly the move both preference policies make freely. That closes off the starvation argument above for both sides at once, by the same ordering guarantee the bakery algorithm already uses for two processes, just checked against every pending request instead of one specific rival.
Same ground rules as five of this site's other ten Concurrency pages (the Treiber Stack, the Michael-Scott Queue, Hazard Pointers, Epoch-Based Reclamation, and the Harris Linked List are the exceptions, built on hardware compare-and-swap instead): ordinary reads and writes to shared state (here, a reader count and a writer flag), interleaved arbitrarily by the scheduler.
function canAdmit(policy, s, isWriter) {
var writerPending = s.writerSub === 'waiting' || s.writerSub === 'writing';
if (policy === 'readers-pref') {
return isWriter ? (s.readersActive === 0 && !s.writerActive) : !s.writerActive;
}
if (policy === 'writers-pref') {
return isWriter ? (s.readersActive === 0 && !s.writerActive)
: (!s.writerActive && !writerPending);
}
// fair: granted only once nothing with an earlier ticket is still waiting or active
return nothingEarlierPending(s, isWriter);
}
function startRead(s) { s.readersActive++; }
function finishRead(s) { s.readersActive--; }
function startWrite(s) { s.writerActive = true; }
function finishWrite(s) { s.writerActive = false; }
The demo above runs this exact admission check as a step-by-step state machine — each reader's and the
writer's request, start, and finish are each their own click, independently interleavable in whatever order
you choose, not a simplified stand-in for it. nothingEarlierPending (full source in this page's
own script) is a plain linear scan comparing ticket numbers; see Complexity for what a
production implementation would use instead.
Readers-preference's writer-starvation has no ceiling — measured directly, not assumed.
Counting every reader-start that happens while the writer's own request is already sitting in the queue
(across every reachable schedule, worst case over all of them), the maximum is exactly
readers × attempts-each in every configuration checked, deadlock-free throughout
(stuck is 0 everywhere — this is purely a fairness failure, never a liveness-destroying one the
way Dining Philosophers' deadlock is):
| policy | readers | attempts each | reachable states | deadlocked | max reader-starts ahead of waiting writer |
|---|---|---|---|---|---|
| Readers-preference | 2 | 1 | 154 | 0 | 2 |
| Readers-preference | 2 | 2 | 723 | 0 | 4 |
| Readers-preference | 3 | 1 | 1,166 | 0 | 3 |
| Readers-preference | 3 | 2 | 11,996 | 0 | 6 |
| Readers-preference | 4 | 1 | 10,776 | 0 | 4 |
| Readers-preference | 4 | 2 | 245,385 | 0 | 8 |
| Writers-preference | any of the above | — | — | 0 | 0 |
| Fair (ticket order) | any of the above | — | — | 0 | 0 |
That count scales exactly with the reader side's own attempt budget, which is the point: there's no fixed number of readers-preference will eventually make the writer wait past. Give readers an unbounded supply of fresh requests and the bound this table shows grows without one.
Writers-preference has the mirror failure — measured the same way, on the reader side. Counting every writer-start that happens while a reader's own request is already waiting, fixing one reader and varying how many times the single writer tries:
| policy | readers | attempts (writer) | reachable states | deadlocked | max writer-starts ahead of waiting reader |
|---|---|---|---|---|---|
| Writers-preference | 1 | 1 | 20 | 0 | 1 |
| Writers-preference | 1 | 2 | 44 | 0 | 2 |
| Writers-preference | 1 | 3 | 76 | 0 | 3 |
| Readers-preference | 1 | 1 | 24 | 0 | 1 |
| Readers-preference | 1 | 2 | 52 | 0 | 2 |
| Readers-preference | 1 | 3 | 88 | 0 | 3 |
| Fair (ticket order) | any of the above | — | — | 0 | 0 |
Readers-preference shows up in this second table too, and that's worth calling out rather than hiding: its own rule only ever promises that a new reader request can't be blocked by a merely-waiting writer. It says nothing about protecting a reader that's already waiting from a writer that happens to grab the resource the instant no reader is currently active — so a writer can and does cut ahead of an already-waiting reader under readers-preference too, at exactly the same rate as under writers-preference. Readers-preference fixes one direction of the starvation problem and is silent on the other; only the fair policy closes both at once, confirmed at exactly 0 across every one of the fourteen configurations in both tables above.
Time: O(1) per admission check under readers-preference or
writers-preference — each is a fixed handful of counter/flag comparisons, no scan over other processes.
This page's own fair-policy reference implementation checks O(n) other tickets per request (a
plain linear scan, kept simple to read, the same naive-for-clarity tradeoff Lamport's bakery algorithm makes for its own ticket
comparison) — a production implementation would track a FIFO queue instead and check only its own position,
back to O(1) amortized per request. Space: O(n) — one ticket and
sub-state slot per process (n readers plus the one writer), plus a shared reader count and
writer flag that don't grow with n.
See Choosing a Mutual Exclusion Algorithm for Peterson's, Dekker's, and Lamport's bakery algorithm side by side — that guide doesn't cover this page, because readers-writers isn't a mutual-exclusion problem in the first place (any number of readers may legitimately overlap). And see the Dining Philosophers Problem for this site's other liveness failure: that page's deadlock means nobody ever moves again; this page's starvation means the system keeps moving, every reader and writer eventually gets served in every configuration this page's own exhaustive search reaches a terminal state for — it's only under an unbounded, ever-fresh stream of requests on one side that a preference policy's wait has no ceiling at all.