4

Computer Systems: a Programmer's Perspective says

The readers-writers problem has several variations, each based on the priorities of readers and writers.

  • The first readers-writers problem, which favors readers, requires that no reader be kept waiting unless a writer has already been granted permission to use the object. In other words, no reader should wait simply because a writer is waiting.

  • The second readers-writers problem, which favors writers, requires that once a writer is ready to write, it performs its write as soon as possible. Unlike the first problem, a reader that arrives after a writer must wait, even if the writer is also waiting.

Wikipedia says:

  • the first problem: no reader shall be kept waiting if the share is currently opened for reading. It prefers readers over writers, may starve writers in the queue

  • the second problem: no writer, once waiting i.e. added to the queue, shall be kept waiting longer than necessary. It prefers writers over readers, may starve readers.

Is it correct that:

  1. Regardless of which type of reader-writer problem, if there is a / are reader(s) in the critical region, a waiting reader can always enter the critical region, and a waiting writer can't, regardless of which one arrives earlier?

  2. Regardless of which type of reader-writer problem, if a writer is in critical region, no waiting reader or writer can enter the critical region?

  3. Is the first problem defined as: If no reader (regardless of whether a writer) is in critical region, a waiting reader shall have priority over a waiting writer, independently of which arrived earlier?

  4. Is the second problem defined as: If no reader (regardless of whether a writer) is in critical region, a waiting writer shall have priority over a waiting reader, independently of which arrived earlier?

0
4
  1. No, while in the first case any additional reader can always join other readers, potentially starving writers, in the second it can only join if no writer waits.

  2. Yes, a writer always needs full exclusivity.

  3. Yes. Waiting readers have priority in the first case (thus happens only when a writer finishes), while waiting writers have priority in the second one.

  4. Yes, in the second case writers always have priority.

1

Using engineering reasoning — rather than theoretically pondering abstract cases — analyze the likely operations of a proposed system and prioritize reads and writes based on the purpose of the system.

Basically there are three potential problems, failed writes, stale reads, and latency — aka correctness, consistency, and partition. To put it another way, the CAP theorem applies to any concurrent system not only formal databases.

For many systems failed writes and stale reads are less important than low latency. Google search, Wikipedia, and StackExchange are examples where liveness is paramount. Conversely, banking is an example where correctness and consistency are required no matter how long it takes.

The problem with the two problems described in the question is that there is a third element concurrency— monotonic time. Treating memory as a logical construct instead of a single address, allows approaches such as transactional memory and multi-version concurrency control where values are located in time and space, not just in space. They are not a silver bullet or even a free lunch of course. Just a set of tradeoffs.

In the end interesting systems prioritize some readers and some writers at the expense of some other readers and other writers. The bases for prioritizations and deprioritizations are actual system requirements and ultimately measurements of the system while in use. That’s probably why you are struggling with the text, it’s not really helpful if you are thinking seriously as an engineer.

0

It looks like your misunderstanding is in the term critical region. It is used somewhat casually and not very helpful. The point is that it is technically and/or logically impossible for a reader and a writer to use a resource at the same time. The resource could be a file or a communication channel. So readers and writers will have to wait for each other. The only choice you have as a designer is to favor particular types of users that are waiting for the resource to become available.

It is like a toilet in a busy bar. While it is occupied, it will be locked and no one waiting will be able to open the door and join the person that is in. Anyone will have to wait for the current user to come out. But you can make certain types of waiters jump the queue. Like when there is a queue and someone important comes along, you may want to put him in front or just ahead of the first person of lesser stature.

2
  • Readers can share, writers can't. Queue jumping happens not just in the waiting line but some (readers) can enter directly without waiting at all if there's no writer inside. – Erik Eidt Oct 31 '20 at 19:02
  • @ErikEidt This is a typical implementation detail of file access in particular but the question is about a general, abstract reader/writer problem that (the way I read it) regards access as exclusive. – Martin Maat Oct 31 '20 at 20:23
0

Bear in mind: you're talking about concurrent system. Which means at the same moment of (physical) time, more then one thread tries to do something with the same piece of memory. Thread can either read it or write in general.

So there are options:

  1. Both threads read them.
  2. 1st thread reads, 2nd one - writes.
  3. 1st writes, 2nd - reads.
  4. both write.

Let's see what happens:

  1. Reading in parallel is safe: sequence of bits at that memory location does not change at all; it remains the same. That what means to be safe - no unexpected change could ever happen meanwhile. So there is no reason to block 2nd thread until 1st thread finishes it's read.

  2. ..which also covers the 3): Since either mix of read-write activities is all the same, we don't care whether 1st thread reads and 2nd writes or the other way around; what we care about is the fact that read overlaps with writing. Why? Because it yields unpredictable result: while one thread could partially read memory, the other one meanwhile could change not yet read memory; then, once reading thread continues, it gonna read something different, which in general breaks consistency. Here goes conclusion: write operation requires exclusive access, which means it can't happen in parallel neither with other write operations on other threads, nor with reads.

  3. The conclusion above extends to the 1st thread writes and 2nd thread writes too case.

So, what's the problem behind that? The problem is how to implement such system, that will maintain reasonable balance between threads that like to read and threads that like to write and make sure they are served as soon as possible, without artificial delays (which increase latency - critically important feature for any nowadays distributed system in production).

3
  • Concurrency is logical simultaneous events not simultaneous events in absolute time. A single hardware threaded system can provide concurrency and such systems go back to early time sharing systems such as Multics. – ben rudgers Oct 31 '20 at 21:35
  • @benrudgers how does it matter with respect to what I've written? – Sereja Bogolubov Oct 31 '20 at 21:38
  • The bold text in the first paragraph of the answer. – ben rudgers Oct 31 '20 at 23:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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