recategorized by
3,024 views
13 votes
13 votes

Consider the following proposal to the "readers and writers problem."

Shared variables and semaphores:

aw, ar, rw, rr : interger;
mutex, reading, writing: semaphore:
initial values of variables and states of semaphores:
ar=rr=aw=rw=0
reading_value = writing_value = 0
mutex_value = 1.                        Process writer;
Process reader;                             begin
begin                                    while true do
repeat                                   begin
         P(mutex);                              P(mutex);
         ar := ar+1;                            aw := aw + 1;
         grantread;                             grantwrite;
         V(mutex);                              V(mutex);
         P(reading);                            P(writing);
         read;                         Write;
         P(mutex);                     P(mutex);
         rr := rr - 1;                 rw := rw - 1;
         ar := ar - 1;                 ar := aw - 1;
         grantwrite;                   grantread;
         V(mutex);                     V(mutex);
         other-work;                   other-work;
until false                     end
end.                            end.

Procedure grantread;
begin
    if aw = 0
    then while (rr < ar) do
        begin rr := rr + 1;
            V (reading)
        end
end;
Procedure grantwrite;
begin
    if rr = 0
    then while (rw < aw) do
        begin rw := rw + 1;
            V (writing)
        end
end;
  1. Give the value of the shared variables and the states of semaphores when $12$ readers are reading and writers are writing.
  2. Can a group of readers make waiting writers starve? Can writers starve readers?
  3. Explain in two sentences why the solution is incorrect.
recategorized by

1 Answer

8 votes
8 votes

12 readers are reading means each reader has incremented the value of ar, making final value of ar to be 12.

Also each of the reader has executed grantread in which rr is incremented to the value of ar making value of rr to be 12 finally.

31 writers are waiting means each writer on arrival has incremented the value of aw, making final value of aw to be 31.

Value of rw is incremented in grantwrite only when value of rr is 0 but as 12 readers are already reading, this cannot happen, making value of rw to be 0.

Whenever read is granted in grantread, it means value of reading semaphore is incremented to number of reader process using V(reading). But before entering the read section, each reader decrements the reading semaphore by 1 using P(reading). The fact that 12 readers are reading means that 12 V(reading) operations were performed and the 12 reader processes before entering read section have performed P(reading) each to decrement the value of reading semaphore to 0 again.

Since 12 readers are already reading, value of rr is non-zero because of which V(writing) is not executed leaving the value of writing semaphore to be 0.

------------------------------------------------------------------------------------

NO, group of readers will not starve writers as readers execute V(reading) in grantread only when aw is 0 i.e. no writer is waiting allowing writer to execute first.

YES, writers can starve readers as writers execute V(writing) without caring about readers (ar).

-------------------------------------------------------------------------------------

The solution is incorrect because:

In reader-writer problem, only single process needs to write at a time.

But in proposed solution, consider the case: When one process is writing and another write process arrives then it is also granted write using V(writing) without caring about the first process which is still writing.

edited by

Related questions

24 votes
24 votes
1 answer
1
23 votes
23 votes
9 answers
3
makhdoom ghaya asked Nov 14, 2016
5,007 views
Show that the conclusion $(r \to q)$ follows from the premises$:p, (p \to q) \vee (p \wedge (r \to q))$
22 votes
22 votes
6 answers
4
makhdoom ghaya asked Nov 14, 2016
5,337 views
Give a regular expression over the alphabet $\{0, 1\}$ to denote the set of proper non-null substrings of the string $0110$.