Reader-Writer Problem

operating-systems concurrency

Definition

Reader-Writer Problem

The reader-writer problem addresses the challenge of synchronising multiple processes that access a shared resource (such as a database or file).

• Readers: Any number of processes may read from the resource simultaneously.
• Writers: Only one process at a time may write to the resource, and no readers may be active while a write is occurring.

Constraints

1. Multiple readers can access the resource at the same time.
2. Only one writer can access the resource at a time.
3. Writers require exclusive access (no other readers or writers).

Priority Variations

The solution to this problem depends on which type of process is given priority:

Reader Priority

Readers are never kept waiting unless a writer has already obtained permission to use the resource. This can lead to writer starvation if a continuous stream of readers arrives.

Writer Priority

Once a writer is ready to write, no new readers are allowed to start reading. This prevents the writer from waiting indefinitely but can lead to reader starvation.

Fairness (Z-Semaphore)

To prevent a long queue of readers from building up while a writer is waiting, an additional semaphore z can be used. This ensures that at most one reader can block on the resource semaphore at a time, allowing waiting writers to enter the critical section more quickly.

Implementation with Semaphores

Reader Priority

The following logic uses a binary semaphore wsem to control access to the resource and a counter rc to track active readers.

// Global variables
var rc: integer := 0; // Read count
var x: semaphore := 1; // Mutex for rc
var wsem: semaphore := 1; // Mutex for the resource
 
// Reader
loop
    wait(x);
    rc := rc + 1;
    if rc = 1 then wait(wsem); // First reader locks the resource
    signal(x);
    
    // --- READ OPERATION ---
    
    wait(x);
    rc := rc - 1;
    if rc = 0 then signal(wsem); // Last reader releases the resource
    signal(x);
end loop;
 
// Writer
loop
    wait(wsem);
    // --- WRITE OPERATION ---
    signal(wsem);
end loop;

Writer Priority

To prioritise writers, a second counter wc tracks waiting writers, and an additional semaphore rsem is used to block readers when a writer is interested.

// Global variables
var rc, wc: integer := 0;
var x, y, z, rsem, wsem: semaphore := 1;
 
// Reader
loop
    wait(z);                // Only one reader can wait on rsem
        wait(rsem);         // Blocks if a writer is active/waiting
            wait(x);        // Mutex for rc
                rc := rc + 1;
                if rc = 1 then wait(wsem);
            signal(x);
        signal(rsem);
    signal(z);
 
    // --- READ OPERATION ---
 
    wait(x);
        rc := rc - 1;
        if rc = 0 then signal(wsem);
    signal(x);
end loop;
 
// Writer
loop
    wait(y);                // Mutex for wc
        wc := wc + 1;
        if wc = 1 then wait(rsem);
    signal(y);
 
    wait(wsem);
    // --- WRITE OPERATION ---
    signal(wsem);
 
    wait(y);
        wc := wc - 1;
        if wc = 0 then signal(rsem);
    signal(y);
end loop;