Readers-Writers Problem | Operating System - Computer Science Engineering (CSE) PDF Download

Introduction and Readers Preference Solution

Consider a situation where we have a file shared between many people.

  • If one of the people tries editing the file, no other person should be reading or writing at the same time, otherwise changes will not be visible to him/her.
  • However if some person is reading the file, then others may read it at the same time.

Precisely in OS we call this situation as the readers-writers problem

Problem parameters:

  • One set of data is shared among a number of processes
  • Once a writer is ready, it performs its write. Only one writer may write at a time
  • If a process is writing, no other process can read it
  • If at least one reader is reading, no other process can write
  • Readers may not write and only read

Solution when Reader has the Priority over Writer
Here priority means, no reader should wait if the share is currently opened for reading.
Three variables are used: mutex, wrt, readcnt to implement solution

  1. semaphore mutex, wrt; // semaphore mutex is used to ensure mutual exclusion when readcnt is updated i.e. when any reader enters or exit from the critical section and semaphore wrt is used by both readers and writers
  2. int readcnt;  //    readcnt tells the number of processes performing read in the critical section, initially 0

Functions for sempahore:

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

Writer process:

  1. Writer requests the entry to critical section.
  2. If allowed i.e. wait() gives a true value, it enters and performs the write. If not allowed, it keeps on waiting.
  3. It exits the critical section.

// Program
do {
    // writer requests for critical section
    wait(wrt);  
    // performs the write
    // leaves the critical section
    signal(wrt);
} while(true);

Reader process:

  1. Reader requests the entry to critical section.
  2. If allowed:
    • it increments the count of number of readers inside the critical section. If this reader is the first reader entering, it locks the wrt semaphore to restrict the entry of writers if any reader is inside.
    • It then, signals mutex as any other reader is allowed to enter while others are already reading.
    • After performing reading, it exits the critical section. When exiting, it checks if no more reader is inside, it signals the semaphore “wrt” as now, writer can enter the critical section.
  3. If not allowed, it keeps on waiting.
    //Program
    do {  

       // Reader wants to enter the critical section
       wait(mutex);
       // The number of readers has now increased by 1
       readcnt++;                          
       // there is atleast one reader in the critical section
       // this ensure no writer can enter if there is even one reader
       // thus we give preference to readers here
       if (readcnt==1)    
          wait(wrt);                    
       // other readers can enter while this current reader is inside
       // the critical section
       signal(mutex);                  
       // current reader performs reading here
       wait(mutex);   // a reader wants to leave
       readcnt--;
       // that is, no reader is left in the critical section,
       if (readcnt == 0)
           signal(wrt);         // writers can enter
       signal(mutex); // reader leaves
    } while(true);

Thus, the semaphore ‘wrt‘ is queued on both readers and writers in a manner such that preference is given to readers if writers are also there. Thus, no reader is waiting simply because a writer has requested to enter the critical section.

Reader-Writers solution using Monitors

Considering a shared Database our objectives are:

  • Readers can access database only when there are no writers.
  • Writers can access database only when there are no readers or writers.
  • Only one thread can manipulate the state variables at a time.

Basic structure of a solution

  • Reader()
    1. Wait until no writers
    2. Access database
    3. Check out – wake up a waiting writer
  • Writer()
    1. Wait until no active readers or writers
    2. Access database
    3. Check out – wake up waiting readers or writer

Now let’s suppose that a writer is active and a mixture of readers and writers now show up.

Who should get in next?
Or suppose that a writer is waiting and an endless of stream of readers keep showing up.

Would it be fair for them to become active?
So we’ll implement a kind of back-and-forth form of fairness:

  • Once a reader is waiting, readers will get in next.
  • If a writer is waiting, one writer will get in next.

Implementation of the solution using monitors:

  1. The methods should be executed with mutual exclusion i.e. At each point in time, at most one thread may be executing any of its methods.
  2. Monitors also provide a mechanism for threads to temporarily give up exclusive access, in order to wait for some condition to be met, before regaining exclusive access and resuming their task.
  3. Monitors also have a mechanism for signaling other threads that such conditions have been met.
  4. So in this implementation only mutual exclusion is not enough. Threads attempting an operation may need to wait until some assertion P holds true.
  5. While a thread is waiting upon a condition variable, that thread is not considered to occupy the monitor, and so other threads may enter the monitor to change the monitor’s state.
The document Readers-Writers Problem | Operating System - Computer Science Engineering (CSE) is a part of the Computer Science Engineering (CSE) Course Operating System.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)
80 docs|33 tests

FAQs on Readers-Writers Problem - Operating System - Computer Science Engineering (CSE)

1. What is the Readers-Writers problem in computer science engineering?
Ans. The Readers-Writers problem is a synchronization problem in computer science engineering that involves multiple processes accessing a shared resource, where some processes only read the resource and others both read and write to it. The problem is to ensure that no reader is kept waiting forever and that no writer starves.
2. What is the difference between reader and writer processes in the Readers-Writers problem?
Ans. In the Readers-Writers problem, reader processes only read the shared resource and do not modify it. On the other hand, writer processes not only read the resource but also modify it. The main difference is that multiple reader processes can concurrently access the resource, while only one writer process can access it exclusively.
3. How does the Readers-Writers problem impact the performance of a system?
Ans. The Readers-Writers problem can impact the performance of a system by introducing synchronization overhead. It may cause delays and increase the waiting time for processes, especially when there are multiple writers competing for the resource. Inefficient solutions to the problem can lead to decreased system throughput and potential resource starvation.
4. What are the possible solutions to the Readers-Writers problem?
Ans. There are several possible solutions to the Readers-Writers problem, including the following: - Readers preference solution: Allows multiple readers to access the resource simultaneously and gives priority to readers over writers. - Writers preference solution: Gives priority to writers over readers, allowing only one writer to access the resource at a time. - No-starve solution: Ensures that neither readers nor writers starve by implementing a fair scheduling algorithm. - Writer-Reader solution: Allows multiple readers or one writer to access the resource, but not both simultaneously. - Reader-Writer Lock solution: Uses a lock mechanism to allow concurrent read access but exclusive write access to the resource.
5. What are the potential challenges in implementing a solution to the Readers-Writers problem?
Ans. Implementing a solution to the Readers-Writers problem can be challenging due to the following factors: - Ensuring fairness: It is crucial to design a solution that provides fair access to the shared resource, preventing starvation of any process. - Overhead and efficiency: Some solutions may introduce additional overhead and synchronization mechanisms, which can impact the overall performance of the system. - Deadlock and livelock: Incorrect implementations can lead to deadlock or livelock situations, where processes are unable to make progress or continuously contend for the resource without accomplishing their tasks. - Scalability: The solution should be scalable to support a large number of concurrent readers and writers efficiently, without compromising system performance.
80 docs|33 tests
Download as PDF
Explore Courses for Computer Science Engineering (CSE) exam
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Download the FREE EduRev App
Track your progress, build streaks, highlight & save important lessons and more!
Related Searches

Readers-Writers Problem | Operating System - Computer Science Engineering (CSE)

,

Free

,

past year papers

,

Semester Notes

,

Readers-Writers Problem | Operating System - Computer Science Engineering (CSE)

,

Sample Paper

,

practice quizzes

,

Extra Questions

,

pdf

,

Viva Questions

,

Important questions

,

Readers-Writers Problem | Operating System - Computer Science Engineering (CSE)

,

Objective type Questions

,

video lectures

,

ppt

,

MCQs

,

study material

,

Exam

,

Previous Year Questions with Solutions

,

shortcuts and tricks

,

Summary

,

mock tests for examination

;