2
$\begingroup$

I need some help understanding the implementation of the one-writer many-readers problem shown below as I am new to this concept:

enter image description here

I have a rough idea that there will be starvation/deadlock among the readers as there is one writer that multiple readers are trying to access at once. Can anyone please provide some further insight regarding the problems with the implementation of this situation?

I am not looking for any coding, that was just the sample code (pseudocode) I am working with. I am looking for the problem of the implementation. Upon further research I have assumed the following (based on the line: if readcount == 1 then semWait(wrt); :

  • There is one writer and many readers
  • The readers have priority over the writers
  • The possible problem: The writers cannot write until the reader has finished reading therefore starvation occurs

However upon re-evaluation of the code I have also assumed the following based on the lines:

semWait(mutex);
readcount := readcount - 1;
if readcount == 0 then up
semSignal(mutex);

Could I not also say that only one reader may read at a time therefore the other readers will be starved?

Therefore would either of these be the correct way of interpreting the coding to the problem is of the implementation or would I be wrong?

Improve this question
$\endgroup$
  • $\begingroup$ Please don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$ – D.W.♦ Sep 2 '15 at 20:52
  • $\begingroup$ As far as the question: What are your thoughts? What possible problems have you considered, and what are your thoughts on whether they are or aren't present in this code? "provide further insight regarding the problems with this code" is a bit open-ended/vague. The more specific you can make your question, and the more you show us about what work you've done so far, the more likely that you will get helpful answers. $\endgroup$ – D.W.♦ Sep 2 '15 at 20:54
  • $\begingroup$ @D.W. I have edited the details in my question to meet some of the points you brought up in your first comment. I do apologise for using an image but I could not copy and paste the code as it was presented to me as an image already. $\endgroup$ – Osiris93 Sep 2 '15 at 21:06
  • 1
    $\begingroup$ Be specific about what you are asking. Do you want to know if the protocol you have described is correct? (i.e. satisfies the requirements of priority and not allowing simultaneous read/write). If so, note that even the simplest protocol where no one gets to read/write is correct. Are you asking whether your protocol is correct and is deadlock,starvation free? Note that formal proofs might be trickier than you expect. $\endgroup$ – Ariel Sep 2 '15 at 21:29
  • $\begingroup$ @Ariel The only information I was given about this coding sample was: "Explain the problem with implementation of the one-writer many-readers problem". That's all, the rest is a bit of a mystery to me, but based on the information it implies there is definitely a problem. Based on what I understand by the coding, I see it as many readers have priority over one writer and I am assuming that the writer may be starved. But I am not sure, it is all a guess based on what I know and the research I have found. What I'm looking for here is validation or correction on my assumption $\endgroup$ – Osiris93 Sep 2 '15 at 21:35
2
$\begingroup$

First,I would suggest (in the future as well) to write the pseudocode yourself (the commands for the readers/writers), It will be cleaner and easier to read than the image. Also, i would suggest briefly explaining the semantics of your operations (wait/signal/up, since you used all three in the code).

To your answer, readers not being able to read simultaneously does not mean starvation, although simultaneous reading ability is an additional requirement, at least in the classical formulation of the problem (moreover, readers can read simultaneously in this protocol). Starvation means that there exists a process stuck waiting while other processes share the resource (if one reader $r_1$ has to wait until $r_2$ is done, then he might read after $r_2$, who eventually will be done reading, so $r_1$ is not stuck).

This protocol (as it seems to me) is the same as the one described here (under First readers-writers problem). It is easy to see (as mentioned in the link) that writers can be starved here. Suppose $r_1,r_2$ are reading at the same time, so the count is $2$. Imagine a scenario where whenever $r_1,r_2$ read together, the first to finish (and decrements the counter to $1$) immediately requests reading again (so the counter is back to $2$). This way the counter will never reach $0$ and the writer will be starved (stuck waiting).

Improve this answer
$\endgroup$

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.