readers writers problem - TarisMajor/5143-OpSystems GitHub Wiki

The Readers-Writers Problem is a classic synchronization problem in computer science that involves coordinating access to a shared resource (such as a database) by multiple threads, which can either read or write. The main challenge is to allow multiple readers to access the resource simultaneously while ensuring that only one writer can access the resource at a time.

1. Shared Resource: The resource (e.g., a database) needs to be accessed by multiple threads that either read or write data.
2. Readers: Multiple readers can access the resource concurrently without causing data inconsistency.
3. Writers: Only one writer can access the resource at a time to prevent data corruption.
4. Synchronization: Proper synchronization is required to ensure that readers and writers do not interfere with each other.

1. First Readers-Writers Problem (Readers Preference):

   • Objective: Ensure that no reader is kept waiting unless a writer has already gained access to the resource. This solution gives preference to readers.
   • Challenge: Writers may starve if there are always readers accessing the resource.

2. Second Readers-Writers Problem (Writers Preference):

   • Objective: Ensure that no writer is kept waiting once it has requested access. This solution gives preference to writers.
   • Challenge: Readers may starve if there are always writers wanting to access the resource.

3. Third Readers-Writers Problem (Fairness):

   • Objective: Ensure fair access to the resource by both readers and writers, preventing starvation of either. This solution ensures that neither readers nor writers are given undue preference.

1. Using Semaphores: Semaphores can be used to synchronize access to the shared resource, ensuring mutual exclusion for writers and allowing concurrent access for readers. The solution typically involves three semaphores: mutex, wrt, and readCount.

   Pseudocode for First Readers-Writers Problem (Readers Preference):

   // Shared variables and semaphore initialization
   Semaphore mutex = 1;
   Semaphore wrt = 1;
   int readCount = 0;
   
   // Reader process
   void reader() {
       wait(mutex); // Enter critical section
       readCount++;
       if (readCount == 1) {
           wait(wrt); // First reader locks the resource for writing
       }
       signal(mutex); // Exit critical section
   
       // Reading section (no lock required)
   
       wait(mutex); // Enter critical section
       readCount--;
       if (readCount == 0) {
           signal(wrt); // Last reader unlocks the resource for writing
       }
       signal(mutex); // Exit critical section
   }
   
   // Writer process
   void writer() {
       wait(wrt); // Lock the resource for writing
   
       // Writing section (exclusive lock)
   
       signal(wrt); // Unlock the resource for writing
   }

2. Using Monitors: Monitors provide a higher-level abstraction for synchronization by encapsulating the shared resource and synchronization mechanisms. Condition variables within the monitor can be used to manage access for readers and writers.

   Pseudocode for First Readers-Writers Problem (Readers Preference):

   class ReadersWriters {
       private int readCount = 0;
       private final Condition readCond, writeCond;
       private final Lock lock = new ReentrantLock();
   
       public ReadersWriters() {
           readCond = lock.newCondition();
           writeCond = lock.newCondition();
       }
   
       public void startRead() throws InterruptedException {
           lock.lock();
           try {
               readCount++;
               if (readCount == 1) {
                   writeCond.await(); // First reader blocks writers
               }
               readCond.signal(); // Notify other readers
           } finally {
               lock.unlock();
           }
       }
   
       public void endRead() throws InterruptedException {
           lock.lock();
           try {
               readCount--;
               if (readCount == 0) {
                   writeCond.signal(); // Last reader unblocks writers
               }
           } finally {
               lock.unlock();
           }
       }
   
       public void startWrite() throws InterruptedException {
           writeCond.await(); // Writer waits until no readers
       }
   
       public void endWrite() throws InterruptedException {
           writeCond.signal(); // Writer unblocks readers and writers
       }
   }

In this example, the ReadersWriters class uses condition variables and a lock to synchronize access between readers and writers. Readers can access the resource concurrently, while writers must wait until all readers are done.

• Operating System Concepts by Abraham Silberschatz, Peter B. Galvin, and Greg Gagne
• Readers-Writers Problem - GeeksforGeeks
• Modern Operating Systems by Andrew S. Tanenbaum
• Wikipedia - Readers-Writers Problem
• ChatGPT