0

I'm wondering whether there is a simple solution to the reader writer problem, where we can give the readers priority, but not an absolute priority using semaphores. Basically I want achieve a ratio of 5 readers to 1 writer in the queue for the critical section.

In other words: if a reader and a writer wanted to enter the the critical section, the reader would have priority. And if another reader wanted to enter after this, they would also have priority. This would continue for five readers after which the writer would have priority.

For instance imagine if 10 readers and 2 writers wanted to enter the critical section. The order of entry would be:

  1. 5 readers
  2. 1 writer
  3. 5 readers
  4. 1 writer

I'd appreciate any help on this matter.

1 Answer 1

1

I was just involved in a design session two days ago where we intended to solve the very same problem. Here is what we came up with.

class WeightedSemaphore {

  Map<String,Semaphore> layer1
  Semaphore layer2

  //ratios passed, for your example:  read:5, write:1
  public configure(int realLeases, Map<String,Integer> ratios) {
     for (String key : ratio.keys) {
        layer1.put(key, new Semaphore(realLeases * ratios.get(key))
     }
     layer2 = new Semaphore(realLeases, fair)
  }

  public acquire(String key) {
     layer1.get(key).acquire();
     layer2.acquire();
  }

}

This is minimal pseudocode, but gets the main point across. The main idea was to design a 2 layer semaphore, where layer2 was a single semaphore with the real number of leases we wanted to support; and layer1 served to shape-the-mix of work that would ever be waiting on the layer2 semaphore.

This approach has 2 properties, that i think are pretty cool.

  1. Though it favors keys with a higher ratio, it doesn't exhibit starvation behaviors you see in many priority queue type systems.

  2. It doesn't waste capacity when there is no high-priority work to do. Any key can use the full capacity of the semaphore, but will step aside quickly when new work arrives.

Hope this helps.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.