Readers-Writers Problem

Common Variations of the Readers-Writers Problem

There are three common variations of the readers-writers problem:

First-come first-served: This is the simplest solution, and it provides priority to the writers. A writer will always be allowed to access the resource if there are no readers currently accessing it. If there are readers, the writer will have to wait until all readers have finished
 

Readers priority: This solution gives priority to readers. A reader will always be allowed to access the resource if there are no writers currently accessing it. If there is a writer, the reader will have to wait until the writer has finished
 

No starvation: This solution ensures that no process is starved out indefinitely and both readers and writers have fair access to the shared resource. A writer will not be blocked indefinitely by readers, and a reader will not be blocked indefinitely by writers

Reader process

1. The reader requests entry to the critical section
    
2. If permitted, 

• it increments the number of readers within the critical section. If this reader is the first to enter, the wrt semaphore is locked, preventing writers from entering if any other reader is present
   
• it then signals mutex, indicating that any new reader may enter while others are currently reading
   
• it leaves the critical section after reading. When departing, it checks to see whether there are any more readers within and if there are, it signals the semaphore "wrt," indicating that the writer can now enter the critical region
   

3. If it is not permitted, it will continue to wait

do {
   // The reader requests entry to the critical section
   wait(mutex);
   //Now,the number of readers has incremented by 1
   readCount++;                      
   // there is minimum one reader in the critical section
   // this ensures that no writer can enter if there is even one reader
   // hence readers are given preference here
   if (readCount==1)
   wait(wrt);                
   // other readers can enter while the current reader is inside the critical section
   signal(mutex);              
   // current reader performs reading
   wait(mutex);   // a reader wants to exit
   readCount--;
   // i.e., no reader is left in the critical section,
   if (readCount == 0)
    signal(wrt);         // writers can enter now
   signal(mutex); // reader exits
} while(true);

 As a result, the semaphore 'wrt' is queued on both readers and writers, with readers being prioritized if writers are also present. 

Writer process

1. The writer requests entry to the critical section
    
2. If permitted, i.e., wait() returns a true value, it enters and performs the write
    
3. If it is not allowed, it will continue to wait
    
4. It gets out of the critical section

do {
    // the writer requests entry to the critical section
    wait(wrt);  
    // performs the write
    // exits the critical section
    signal(wrt);
} while(true);

The Problem Statement

A database must be shared by numerous concurrent processes, some of which may want to read the database, while others may wish to update (read and write) the database.

We differentiate between these two processes by referring to the former as Readers and the latter as Writers.

• There will be no negative consequences if two readers access the shared data simultaneously
   
• If a writer and another thread (either a reader or a writer) access the common data simultaneously, chaos may follow

To avoid these problems, we need that the writers have exclusive access to the shared database.

This synchronization issue is known as the readers-writers problem.

Parameters of the problem

• Several processes share a single set of data
   
• When a writer is ready, it begins writing
   
• At any given moment, only one writer may work
   
• No other process can read what a process is writing
   
• No other process can write if at least one reader is reading
   
• Readers may not write and must rely only on what they read

The Solution

We will make use of two semaphores and an integer variable:

1. mutex, a semaphore (initialized to 1), is used to ensure mutual exclusion when readCount is updated, i.e., when any reader enters or exits from the critical section
 

2. wrt, a semaphore (initialized to 1) common to both reader and writer processes
 

3. readCount, an integer variable (initialized to 0) that keeps track of how many processes are currently reading the object

Functions for semaphore :

• wait(): decrements the value of the semaphore
   
• signal(): increments the value of the semaphore

Scalability in the Readers-Writers Problem

Scalability in the readers-writer problem means the ability of the solution to handle an increasing number of concurrent readers and writers. As the number of concurrent threads accessing the shared resource increases, the more difficult it would become to ensure efficient and equitable access to the resources.

Some common scalability solutions for the readers-writer problem are: 

• Read-write locks: Multiple readers but only one writer allowed
   
• Semaphores: Semaphores are variables that can be implemented to provide access control policies and ensure fair access for readers and writers
   
• Monitors: Provides synchronization mechanism and ensures fair access for readers and writers, even in case of failures

Frequently Asked Questions

What is basic idea of the reader-writer problem?

A situation where a data structure can be read and updated simultaneously by concurrent threads is known as a "classical reader-writer problem." The critical section is only accessible by one Writer at a time.

What is the first readers writer problem?

The first readers-writer problem is like a scenario where multiple people can read a book at the same time, but only one person can write or modify the book, and others have to wait their turn.

Can we solve Reader Writer problem using monitor justify?

Yes, we can solve reader-writer problem using monitors. The methods should be carried out by mutual exclusion, meaning that only one thread at a time should be carrying out any of the methods.

What is mutex in reader-writer problem?

A mutex, also known as a mutual exclusion lock, is a primitive for synchronisation that only permits one thread at a time to access a shared resource.  The read count variable, which counts the number of readers currently gaining access to the shared data, is protected by the mutex in the reader-writer problem. 

What is the reader writer problem in synchronization?

The reader-writer problem in synchronization involves managing access to a shared resource where multiple readers can access simultaneously but only one writer can access at a time, ensuring data consistency. Balancing concurrency and consistency is crucial to prevent race conditions and ensure efficient resource utilization in concurrent environments.

Conclusion

In this blog, we learned about the Readers-Writers Problem. We have covered the basic idea of the problem and its reasons. At last, we have seen the solution with the help of semaphores and its code

Recommended Readings:

• Introduction to Operating Systems
• Semaphores v/s Mutex
• Sleeping Barber Problem
• Semaphores in OS
• Demand Paging in OS
   

You can refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, System Design, and many more!
Also, check out some other topics such as, Operating Systems, Computer Networks, DBMS, etc. as well as some Contests and Test Series only on Coding Ninjas Studio. Enrol in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.