Process Synchronization – VIII – Readers-Writers Problem

In the previous post, we discussed the Bounded buffer problem. Let us now discuss the Readers-Writers problem, which is another interesting process synchronization problem. These classical synchronization problems are used to test nearly every new synchronization primitive.

Problem Statement

  • Let us imagine a system where several processes are executing concurrently.
  • There is a single database/file which is needed to be shared among all the processes.
  • There are two types of processes : 
    • Readers: Processes that only read the database (i.e. no modification happens to the database)
    • Writers: Processes that can read as well write in the database. (i.e. database may be updated as well)
    • This means that multiple readers can access the database concurrently. However, when multiple writers access the database, it may lead to inconsistencies. 
  • Synchronization problem
    • We want to design a solution that grants exclusive access to the shared database when a writer process accesses it. This means that the writers will have exclusive access to the shared database while writing to the database.
    • This is the requirement of the Readers-Writers problem.

Variants to the Readers-Writers Problem

Note that the Readers-Writers problem has various variations – which involve priorities. For example, consider the following: 
  • First Readers-Writers Problem (Readers Preference)
    • This variant gives priority to Readers.
    • This problem requires that no reader should be kept waiting unless a writer has already obtained permission to use the shared object
    • In other words, no reader should wait for other readers to finish simply because a writer is waiting.
  • Second Readers-Writers Problem (Writers Preference)
    • This variant gives priority to Writers.
    • It requires that once a writer is ready, that writer perform its write as soon as possible.
    • This means that if a writer is waiting to access the object, no new readers may start reading.

There is also a third Readers-Writers Problem, which adds the constraint that no thread shall be allowed to starve; that is, the operation of obtaining a lock on the shared data will always terminate in a bounded amount of time.

We need to design solutions carefully for both the variants; else it may lead to starvation. As an example,

  • Solution to First Readers-Writers Problem may lead to starvation for Writers. There can be a large number of readers, which will continue to access the shared database continually, one after the another.
  • For the case of the Second Readers-Writers Problem, the readers may starve. There might be multiple writers, which will continually access the shared database/file, one after the another. After each access, they may want to access it again, before any readers get a chance to access it. Hence, starvation for readers.
We will discuss starvation-free solution to the first variant in this post.

Solution to First Readers-Writers Problem

Let us first see the solution to the first Reader-Writers Problem:

Discussion of the Code

  •  The data items used are:
    • Variable read read_count
      • initialized to 0
      • Used to keep track of how many processes are currently reading the object (database/file).
    • Semaphore rw_mutex 
      • initialized to 1
      • common to both reader and writer processes
      • Used to ensure mutual exclusion for writer processes.
      • This semaphore is also used by the first reader that enters and the last reader that exits the critical section.
      • Note that readers who enter or exit while other readers are in their critical sections do not use this semaphore.
    • Semaphore mutex
      • initialized to 1
      • Used to ensure mutual exclusion when the variable read_count is updated.
  • Reader Process
    • The first step is to wait on semaphore “mutex”. When the lock becomes available, the variable read_count is updated by the process.
    • Note that whenever a Reader process wants to access the shared database/file, it first increases the read_count variable. When the reading is performed, it decreases the read_count variable.
    • When the first process comes to read, it waits on “mutex”, and then increments the read_count from 0 to 1.
    • If the read_count is 1, i.e., the first reader process is accessing the database/file, then the Reader process calls wait(rw_mutex), i.e. it acquires the access for all subsequent reader Processes on the shared database/file.
    • This blocks all writing requests to wait till the reader processes are finished.
    • The semaphore “mutex” is released by signal (mutex) call for subsequent Reading processes.
    • After this the reading is performed.
    • After finishing with the reading, the sempahore mutex is acquired again before decrementing the read_count.
    • If the read_count variable becomes 0 at this point, it means that all reader processes have finished with the reading (i.e. this process was the last reader), and therefore, a call to signal (rw_mutex) is made to signal any writing process waiting to access the shared database/file.
  • Writer Process
    • The writer process wishing to access the shared database/file waits on the semaphore rw_mutex to become available.
    • When it does, it acquires it, and then starts the writing process.
    • After finishing with the writing process, it releases the semaphore by call to signal (rw_mutex). This makes it available for other processes waiting to write/read in the shared database/file.

The above discussion should have made clear the following points:

  • If a writer is in the critical section (i.e. accessing the shared database/file) and n readers are waiting, then one reader is queued on rw_mutex, and n − 1 readers are queued on mutex.
  • When a writer executes signal (rw_mutex), we may resume the execution of either the waiting readers or a single waiting writer. The selection is made by the scheduler.

Reader-Writer Lock

Some systems have reader-writer lock, or a shared-exclusive lock, which is a generalized version of the Readers-Writers Problem.
  • As discussed previously, an RW Lock allows for concurrent access for Read-only operations, and exclusive access for Write operations.
  • Acquiring a reader–writer lock requires specifying the mode of the lock: either read or write access.
  • When a process wishes only to read shared data, it requests the reader–writer lock in read mode.
  • A process wishing to modify the shared data must request the lock in write mode.
  • Multiple processes are permitted to concurrently acquire a reader–writer lock in read mode, but only one process may acquire the lock for writing, as exclusive access is required for writers.

Uses of Reader-Writer locks:

  • Since the Reader-Writer Lock allows for concurrent access for Read-only operations, and exclusive access for Write operations,  it is preferred in applications where it is easy to identify which processes only read shared data and which processes only write shared data.
  • Reader–writer locks generally require more overhead to establish than semaphores or mutual-exclusion locks. Therefore, it is used in applications that have more readers than writers since the increased concurrency of allowing multiple readers compensates for the overhead involved in setting up the reader– writer lock.

In the next post, we shall discuss the Dining-Philosophers problem, which is a classical problem of synchronization and an example of a large class of concurrency-control problems. Until then, keep reading and sharing.

Source: 1, 2, 3, 4