Home | Projects | Notes > Operating Systems > Synchronization Problem - Readers/Writers Problem

Synchronization Problem - Readers/Writers Problem

Introduction

• In dealing with the design synchronization and concurrency mechanisms, it is useful to be able to relate the problem at hand to known problems, and to be able to test any solution in terms of its ability to solve these known problems.

• One of the several problems that appear frequently is the readers/writers problem. (Another is, producer/consumer problem)

Readers/Writers Problem

• Definition

  There is a data area shared among a number of processes. The data area could be a file, a block of main memory, or even a bank of processor registers. There are a number of processes that only read the data area (readers) and a number that only write to the data area (writers). The condition that must be satisfied are as follows:

  1. Any number of readers may simultaneously read the file.

  2. Only one writer at a time may write to the file.

  3. If a writer is writing to the file, no reader may read it.

• Different variations of the problem include:

  • Readers have priority (can starve writers)

  • Writers have priority

  • Alternate priorities (i.e., don't allow too many new readers to enter if a writer is waiting, etc.)

Solutions to the Readers/Writers Problem Using Semaphore

• Readers Have Priority

  xxxxxxxxxx
  38
  1
  /* A solution to the Readers/Writers Problem using semaphore - Readers have priority */
  2
  
  3
  int readcount;
  4
  semaphore x = 1, wsem = 1;
  5
  
  6
  void reader()
  7
  {
  8
      while (true)
  9
      {
  10
          semWait(x);
  11
          readcount++;
  12
          if (readcount == 1)
  13
              semWait(wsem);
  14
          semSignal(x);
  15
          READUNIT();
  16
          semWait(x);
  17
          readcount--;
  18
          if (readcount == 0)
  19
              semSignal(wsem);
  20
          semSignal(x);
  21
      }
  22
  }
  23
  
  24
  void writer()
  25
  {
  26
      while (true)
  27
      {
  28
          semWait(wsem);
  29
          WRITEUNIT();
  30
          semSignal(wsem);
  31
      }
  32
  }
  33
  
  34
  void main()
  35
  {
  36
      readcount = 0;
  37
      parbegin(reader, writer);
  38
  }
  

• Writers Have Priority

  xxxxxxxxxx
  52
  1
  /* A solution to the Readers/Writers Problem using semaphore - Readers have priority */
  2
  
  3
  int readcount, writecount;
  4
  semaphore x = 1, y = 1, z = 1, wsem = 1, rsem = 1;
  5
  
  6
  void reader()
  7
  {
  8
      while (true)
  9
      {
  10
          semWait(z);
  11
          semWait(rsem);
  12
          semWait(x);
  13
          readcount++;
  14
          if (readcount == 1)
  15
              semWait(wsem);
  16
          semSignal(x);
  17
          semSignal(rsem);
  18
          semSignal(z);
  19
          READUNIT();
  20
          semWait(x);
  21
          readcount--;
  22
          if (readcount == 0)
  23
              semSignal(wsem);
  24
          semSignal(x);
  25
      }
  26
  }
  27
  
  28
  void writer()
  29
  {
  30
      while (true)
  31
      {
  32
          semWait(y);
  33
          writecount++;
  34
          if (writecount == 1)
  35
              semWait(rsem);
  36
          semSignal(y);
  37
          semWait(wsem);
  38
          WRITEUNIT();
  39
          semSignal(wsem);
  40
          semWait(y);
  41
          writecount--;
  42
          if (writecount == 0)
  43
              semSignal(rsem);
  44
          semSignal(y);
  45
      }
  46
  }
  47
  
  48
  void main()
  49
  {
  50
      readcount = writecount = 0;
  51
      parbegin (reader, writer);
  52
  }
  

  The semaphore rsem inhibits all readers while there is at least one writer desiring access to the data area.

  The variable writecounter controls the setting of rsem.

  The semaphore y controls the updating of writecount.

References

Stallings, W. (2018). Operating Systems: Internals and Design Principles (9th ed.). Pearson Education, Inc.