Common Concurrency Problem

Reader-Writers Problem

There is a data area shared among a number of processes. The data area could be a file, a block of main memory, or even a bank of processor registers. There are a number of processes that only read the data area (readers) and a number that only write to the data area (writers). The conditions that must be satisfied are as follows:

Any number of readers may simultaneously read the file.
Only one writer at a time may write to the file.
If a writer is writing to the file, no reader may read it.

Classic reader-priority skeleton (readers never wait if another reader is already in):

/* program readersandwriters */
int readcount;
semaphore x = 1, wsem = 1;
 
void reader() {
    while ( true ) {
        semWait( x );
        readcount++;
        if ( readcount == 1 ) semWait( wsem );    // first reader locks writers out
        semSignal( x );
        READUNIT();
        semWait( x );
        readcount--;
        if ( readcount == 0 ) semSignal( wsem );  // last reader lets writers in
        semSignal( x );
    }
}
 
void writer() {
    while ( true ) {
        semWait( wsem );
        WRITEUNIT();
        semSignal( wsem );
    }
}
 
void main() {
    readcount = 0;
    parbegin( reader, writer );
}

A continuous stream of readers starves writers, which the seven CS343 solutions below progressively fix.

CS343, seven solutions (Buhr §6.4.4)

All seven use a split binary semaphore (entry, rwait, wwait) with baton passing segregating 3 kinds of tasks: arrivers (on entry), waiting readers (on rwait), waiting writers (on wwait). The differences are in the entry and exit protocols that decide who gets the baton.

Shared state (solutions 1–3 share this skeleton):

uSemaphore entry(1), rwait(0), wwait(0);          // split binary semaphores
int rdel = 0, wdel = 0, rcnt = 0, wcnt = 0;       // auxiliary counters

Solution 1, naive (reader barging, writer starvation)

void Reader::main() {
    entry.P();                                    // pickup baton
    if ( wcnt > 0 ) {                             // resource in use by writer ?
        rdel += 1; entry.V();                     // put baton down
        rwait.P(); rdel -= 1;                     // passed baton
    }
    rcnt += 1;
    if ( rdel > 0 ) rwait.V();                    // daisy-chain waiting readers
    else            entry.V();
    // READ
    entry.P();
    rcnt -= 1;
    if ( rcnt == 0 && wdel > 0 ) wwait.V();       // last reader wakes a writer
    else                         entry.V();
}
void Writer::main() {
    entry.P();
    if ( rcnt > 0 || wcnt > 0 ) {
        wdel += 1; entry.V(); wwait.P(); wdel -= 1;
    }
    wcnt += 1; entry.V();
    // WRITE
    entry.P();
    wcnt -= 1;
    if      ( rdel > 0 ) rwait.V();               // prefer readers on exit
    else if ( wdel > 0 ) wwait.V();
    else                 entry.V();
}

Bug: reader only checks writer in the resource, not writers waiting. A continuous stream of arriving readers starves waiting writers.

Solution 2, writer priority (reader starvation)

Readers now defer if any writer is waiting; writer exit serves writers first:

// Reader entry (changed):
if ( wcnt > 0 || wdel > 0 ) {                     // waiting writers too
    rdel += 1; entry.V(); rwait.P(); rdel -= 1;
}
 
// Writer exit (changed):
if      ( wdel > 0 ) wwait.V();                   // writers first
else if ( rdel > 0 ) rwait.V();
else                 entry.V();

Works for the 80%-read / 20%-write case. Continuous writers ⇒ reader starvation.

Solution 3, alternation (Dekker-style fairness)

Readers wait when a writer waits, and writer exit favours readers. Combined with solution 2’s reader-entry, alternation emerges without an explicit flag:

// Writer exit (back to readers-first):
if      ( rdel > 0 ) rwait.V();
else if ( wdel > 0 ) wwait.V();
else                 entry.V();

Neither side barges on simultaneous waiting ⇒ fair under contention.

Solution 4, temporal order via shadow queue

Temporal barging problem: alternation is fine for simultaneous waiters but fails across time. Reader arrives at 2:00 but gets served before a writer that arrived at 1:30 ⇒ reader sees stale data. 12:30 write is never read. FIFO fixes this.

Collapse SBS so readers and writers wait on one semaphore, but keep a shadow queue recording the kind of each waiter:

uSemaphore entry(1), rwwait(0);                   // single wait sem
int rwdel = 0, rcnt = 0, wcnt = 0;
enum RW { READER, WRITER };
queue<RW> rw_id;                                  // shadow queue
 
void Reader::main() {
    entry.P();
    if ( wcnt > 0 || rwdel > 0 ) {                // anybody already queued
        rw_id.push( READER );
        rwdel += 1; entry.V(); rwwait.P(); rwdel -= 1;
        rw_id.pop();
    }
    rcnt += 1;
    if ( rwdel > 0 && rw_id.front() == READER )   // next-in-line is a reader
        rwwait.V();                               // let them in concurrently
    else entry.V();
    // READ
    entry.P(); rcnt -= 1;
    if ( rcnt == 0 && rwdel > 0 ) rwwait.V();     // last reader wakes whoever's next
    else entry.V();
}
// Writer::main symmetric — pushes WRITER, never daisy-chains after its block

Solution 5, writer chair

Cheat: allow readers to sometimes unblock a writer incorrectly; the writer checks again and moves to a dedicated chair (separate wwait semaphore). Chair always has priority on exit.

uSemaphore entry(1), rwwait(0), wwait(0);
int rwdel = 0, wdel = 0, rcnt = 0, wcnt = 0;
 
void Writer::main() {
    entry.P();
    if ( rcnt > 0 || wcnt > 0 ) {                 // first wait on bench
        rwdel += 1; entry.V(); rwwait.P(); rwdel -= 1;
        if ( rcnt > 0 ) {                         // might have been woken too early
            wdel += 1; entry.V(); wwait.P(); wdel -= 1;   // sit in chair
        }
    }
    wcnt += 1; entry.V();
    // WRITE — exit wakes chair first, bench second
}

Solution 6, private semaphores

Remaining temporal problem (all above): between entry.V() and Xwait.P() a task can be time-sliced. A later arriving task may put its baton down, get scheduled, and P first ⇒ freshness/staleness reappears.

Fix: give every waiter its own semaphore, queued in arrival order. The baton-passer Vs the head of the private-semaphore queue. If the target was preempted before its P, the V is remembered and the task doesn’t block on wakeup.

struct RWnode { RW rw; uSemaphore sem; RWnode( RW rw ) : rw(rw), sem(0) {} };
queue<RWnode *> rw_id;
 
void Reader::main() {
    entry.P();
    if ( wcnt > 0 || ! rw_id.empty() ) {
        RWnode r( READER );                       // stack-allocated private sem
        rw_id.push( &r );
        rwdel += 1; entry.V(); r.sem.P(); rwdel -= 1;
        rw_id.pop();
    }
    rcnt += 1;
    if ( rwdel > 0 && rw_id.front()->rw == READER )
        rw_id.front()->sem.V();                   // wake the *specific* next reader
    else entry.V();
    // ... exit protocol analogous
}

Solution 7, ad hoc two-lock

Coarser: one entry for temporal order, one lock for rcnt mutex, one wwait for the at-most-one waiting writer. Writer blocks holding the baton so arrivers queue on entry.

uSemaphore entry(1), lock(1), wwait(0);
int rcnt = 0, wdel = 0;
 
void Reader::main() {
    entry.P(); lock.P(); rcnt += 1; lock.V(); entry.V();
    // READ
    lock.P(); rcnt -= 1;
    if ( rcnt == 0 && wdel == 1 ) { lock.V(); wwait.V(); }
    else lock.V();
}
void Writer::main() {
    entry.P(); lock.P();
    if ( rcnt > 0 ) { wdel += 1; lock.V(); wwait.P(); wdel -= 1; }
    else lock.V();
    // WRITE
    entry.V();
}

Smaller code but harder to prove correct; doesn’t generalize to other synchronization patterns.

Monitor solution (Buhr §8.5)

Inside a _Monitor with internal scheduling, the same solution-3 no-barger semantics collapses to ~15 lines because uCondition gives you per-kind queues for free:

_Monitor ReadersWriter {
    int rcnt = 0, wcnt = 0;
    uCondition readers, writers;
public:
    void startRead() {
        if ( wcnt != 0 || ! writers.empty() ) readers.wait();
        rcnt += 1;
        readers.signal();                        // daisy-chain next reader
    }
    void endRead() {
        rcnt -= 1;
        if ( rcnt == 0 ) writers.signal();
    }
    void startWrite() {
        if ( wcnt != 0 || rcnt != 0 ) writers.wait();
        wcnt = 1;
    }
    void endWrite() {
        wcnt = 0;
        if ( ! readers.empty() ) readers.signal();
        else                     writers.signal();
    }
};

Same P/V bracketing discipline as the semaphore version: startX/endX must be paired by the caller. Fixing that requires a task with _Accept guards instead of a monitor.

Summary

#	Mechanism	Fairness
1	SBS, reader-first	writer starvation
2	SBS, writer-first	reader starvation
3	SBS, symmetric exit	alternation (simultaneous)
4	Shadow queue	FIFO
5	SBS + writer chair	bounded overtaking
6	Private per-waiter semaphore	strict temporal
7	Ad hoc two-lock	writer-biased, small

🛠️ Steven Gong

Table of Contents

Reader-Writers Problem

CS343, seven solutions (Buhr §6.4.4)

Solution 1, naive (reader barging, writer starvation)

Solution 2, writer priority (reader starvation)

Solution 3, alternation (Dekker-style fairness)

Solution 4, temporal order via shadow queue

Solution 5, writer chair

Solution 6, private semaphores

Solution 7, ad hoc two-lock

Monitor solution (Buhr §8.5)

Summary

Graph View

Backlinks

🛠️ Steven Gong

Table of Contents

Reader-Writers Problem

CS343, seven solutions (Buhr §6.4.4)

Solution 1, naive (reader barging, writer starvation)

Solution 2, writer priority (reader starvation)

Solution 3, alternation (Dekker-style fairness)

Solution 4, temporal order via shadow queue

Solution 5, writer chair

Solution 6, private semaphores

Solution 7, ad hoc two-lock

Monitor solution (Buhr §8.5)

Summary

Related

Graph View

Backlinks