Readers Writers Problem in Operating System (OS)

August 21, 2019

Readers Writers Problem in Operating System

This is a synchronisation problem which is used to test newly proposed synchronisation scheme. The problem statement is, if a database or file is to be shared among several concurrent process, there can be broadly 2 types of users –

Readers – Reader are those processes/users which only read the data
Writers – Writers are those processes which also write, that is, they change the data .

It is allowed for 2 or more readers to access shared data, simultaneously as they are not making any change and even after the reading the file format remains the same.

But if one writer(Say w1) is editing or writing the file then it should locked and no other writer(Say w2) can make any changes until w1 has finished writing the file.

Writers are given to be exclusive access to shared database while writing to database. This is called Reader’s writer problem.

Highlights

If writer W1 has begun writing process then
- No additional writer can perform write function
- No reader is allowed to read
If 1 or more readers are reading then
- Other readers may read as well
- No writer may perform write function until all readers have finished reading

Explanations

In simple terms understand this as unlimited number of readers can read simultaneously. Only one writer can write at a time.

When a writer is writing no other writer can write to the file. A writer can not write when there are one or more than one readers reading. That is writer can only write when there is no readers or no writers accessing the resource.

Solution

Variables used –

Mutex – mutex (used for mutual exclusion, when readcount is changed)
1. initialised as 1
Semaphore – wrt (used by both readers and writers)
1. initialised as 1
readers_count – Counter of number of people reading the file
1. initialised as 0

Functions –

There are two functions –

wait() – performs as –, which basically decrements value of semaphore
signal() – performs as ++. which basically increments value of semaphore

How does Wait and Signal work

To understand how readers and writers work we first need to understand that how atomic operations wait and signal work

Writers problem

while(TRUE) 
{
   //if wait(wrt)returns true value, 
   //then can enter critical section
   //if not allowed then, it keeps on waiting
       wait(wrt);

/* writer does some write operation */

   //increments w value again to 1 
   //so other writers can writer
   signal(wrt);
}

Writer wants the access to critical section i.e. wants to perform the writing
First wait(wrt) value is checked
1. if returns true then gets access
  1. does the write process
  2. performs signal(wrt) and increments value
2. if returns false then
  1. doesn’t get write access.

Readers Problem

while(TRUE) 
{
     //a reader wishes to enter critical section
     //this mutex is used for mutual exclusion before readcount is changed
      wait(mutex);

     //now since he has entered increase the readers_count by 1
     readers_count++;

     // readers_count value now should be greater than or equal to 1

     // used ==1 not >=1 as we want to perform this only once.
     if(readers_count == 1)
           // decrementing w value so no writer can enter writer section 
           // as readers are reading
           // MCQ Question Fact - 
           // Readers have more priority then writers.
                   wait(wrt);

     //this will ensure that now, other readers can enter critical section
     signal(mutex);

     /* perform the reading operation */

     // a reader wants to leave after reading process
     wait(mutex);
     readers_count--;

     if(readers_count == 0)
            // if readers_count is 0 we must restore w value to 1 so writers can write
                    signal(wrt);

     // reader has now left
    signal(mutex);
}

Writer –

Mutex Semaphore ensure mutual exclusion when read count is updated.
Read_count -> tracks how many processes are currently reading the object.
mutex -> Functions as a mutual exclusion semaphore for writers. Also used by first or last reader that enters or exits the critical section.
If writer is in critical section and n readers are waiting, 1 reader is queued as mutex. And n-1 readers are queued or mutex.
When signal ( mutex ) is executed, then one of 2 thing can happen -> Either waiting readers execute or 1 single writing process is executed. This is needed by scheduler.

The above solution to reader writer problem can be generalized to provide reader- writer lock on some system. To acquire a reader writer lock, one must specify the mode of lock- either read or write access.

If a process wanting to only read shared data , request reader-writer lock in read mode. A process waiting to only write on shared data must request the lock in write mode.

This reader writer lock is effective in –

The application where reading and writing process are easily identifiable.
Application having more readers than writers. As reader-writer locks require more overhead to establish than semaphore than semaphore or mutual exclusion locks. So, with the help of multiple readers, it compensates for the overhead of setting up readers-writer lock.

1. Process Synchronization
2. Critical Section
3. Inter-Process Communication
4. UEFI(Unified Extensible Firmware Interface) and how is it different from BIOS
5. Mutex
6. Semaphore
7. Mutex vs. Semaphore
8. Atomic Operations in OS
9. Peterson’s Algorithm for Mutual Exclusion (Only important for Cisco and Arista Networs)
  Java
  C
  Python
10. Peterson’s Algorithm for Critical Section Problem (Only important for Cisco and Arista Networs)
11. Readers-Writers Problem

Readers Writers Problem in Operating System (OS)