Reader-Writer Problem

operating-systems concurrency

Definition

Reader-Writer Problem

The reader-writer problem synchronises multiple processes accessing a shared resource:

• Readers: Any number may read simultaneously
• Writers: Only one may write at a time, with exclusive access (no readers or other writers)

Constraints

Concurrent Reads

Multiple readers can access the resource simultaneously.

Exclusive Write

Only one writer can access the resource at a time.

Writer Exclusivity

Writers require exclusive access (no other readers or writers).

Priority Variations

Reader Priority

Readers never wait unless a writer has permission. Risk: writer starvation with continuous reader stream.

Writer Priority

Once a writer is ready, no new readers start. Risk: reader starvation.

Fairness (Z-Semaphore)

Additional semaphore z prevents reader queue buildup while writer waits, allowing writers to enter more quickly.

Implementation

Reader Priority Solution

int rc = 0;           // Read count
semaphore x = 1;      // Mutex for rc
semaphore wsem = 1;   // Resource mutex
 
// Reader
while (true) {
    wait(x);
    rc++;
    if (rc == 1) wait(wsem);  // First reader locks
    signal(x);
 
    // --- READ ---
 
    wait(x);
    rc--;
    if (rc == 0) signal(wsem); // Last reader releases
    signal(x);
}
 
// Writer
while (true) {
    wait(wsem);
    // --- WRITE ---
    signal(wsem);
}

Writer Priority Solution

int rc = 0, wc = 0;
semaphore x = 1, y = 1, z = 1, rsem = 1, wsem = 1;
 
// Reader
while (true) {
    wait(z);
        wait(rsem);
            wait(x);
                rc++;
                if (rc == 1) wait(wsem);
            signal(x);
        signal(rsem);
    signal(z);
 
    // --- READ ---
 
    wait(x);
        rc--;
        if (rc == 0) signal(wsem);
    signal(x);
}
 
// Writer
while (true) {
    wait(y);
        wc++;
        if (wc == 1) wait(rsem);
    signal(y);
 
    wait(wsem);
    // --- WRITE ---
    signal(wsem);
 
    wait(y);
        wc--;
        if (wc == 0) signal(rsem);
    signal(y);
}