Reader and Writer mutex

Question

I am looking over the classic Reader and Writer Problem

Just to give a quick overview:

• Many readers can be in CS (as long as no writers are)
• Only one writer can be in the CS (with no combination of other readers/writers)

So the solution is:

binary semaphore wrt, mutex = 1;

int No_of_Readers = 0;

Writer Process

wait(wrt);
write
signal(wrt);

Reader Process

wait(mutex);
No_of_Readers ++;
if (No_of_Readers == 1)
   wait(wrt);
signal(mutex);

Read
wait(mutex);
No_of_Readers --;
if (No_of_Readers == 0)
   signal(wrt);
signal(mutex);

My question is simple but I just don't understand it, what is the use of the binary semaphore mutex? why do we have to wait(mutex) when we enter Reader Process and then also wait(mutex) after we Read ?

If someone can give a clear explanation that would help me completely understand this algorithm I am just getting tripped up on that little part.

Answer 1

Lets begin with defining some terms.

Semaphore is one form of software implementation for process synchronization. It's an int value that is used by processes for the purpose of signalling. Only three atomic operations: initialize, increment and decrement, can be performed.
A binary semaphore is restricted type of semaphore which only takes three values, 0 and 1.

wait(): Process executing wait() is blocked if the value is zero. If the value is one then, the process is allowed in critical section and value is decremented to 0.
signal(): This checks if any process(es) are blocked (semaphore value equals 0). If yes, then a process is unblocked. If no, then value of semaphore is set to one.

Writer's Code
Writer process code is simple. wait() is used to enforce mutual exclusion. When wait(wrt) is executed wrt is decremented to 0 from 1. So, as long as there is on writer in the critical section, no other writer or reader process has access to the section. After performing it's task, signal() is implemented to allow other blocked process (if any) to execute over the critical section. signal(wrt) increments the value of wrt from 0 to 1.

Reader's Code
'mutex' variable is used for synchronization among different reader processes. No_of_Readers is a shared variable among reader processes. So, if more than one process is updating this variable then it's very likely that we will end up with wrong value. Thus, the first wait(mutex) and signal(mutex) is used to create a block, which only allows one reader to update (increment) the value of Number_of_Readers. When wait(mutex) is called the mutex is decremented to 0 (from 1). This makes sure that no other reader process will try to update the value of Number_of_Readers. After updating the value of Number_of_Readers siganl(mutex) is called. This increments the value of mutex releasing the section to be used by other readers.

if(Number_of_Readers == 1)

implies that the current reader process is the first reader process to access the main critical section. Thus it is his duty to make sure that the coming writer processes are blocked. Thus wait(wrt) is enforced. Subsequent readers coming don't need to do that, as the first reader has already signalled writers to be blocked.
In the second block of the code, Read operation is being performed by the process(es). After a process has performed it's reading task it will exit the code section. The third block of the code is exit portion. Here also wait(mutex) is implemented as we only want one reader process to update the value of Number_of_Readers. A reader process implementing this will decrement the value of mutex to 0 (from 1), signalling other reader processes not to update the value of the variable. After value is decremented, process checks for

if(Number_of_Readers == 0)

If this condition is satisfied, then it implies that the current reader process is the last one to exit. Thus, it is the responsibility of this process to signal(wrt). This will increment the value of 'wrt' to 1 allowing writer program to enter is required. Value not satisfying implies that there are still reader process(es) in the critical section and thus signal(wrt) is not executed. After Number_of_Readers is updated singal(mutex), increments the value of mutex (to 1), is called allowing other reader processes to access this value for updating.

Thus wait(wrt) and signal(wrt) are used to synchronize between 'Reader and Writer' processes. While wait(mutex) and singal(mutex) are used for synchronization among different 'Reader' processes. This makes sure that the value of Number_of_Readers value is not updated by many reader processes at the same time.

Answer 2

"No_of_Readers" is a shared variable hence, mutex is used to provide mutual exclusion to maintain data consistency.

Consider the statement : No_of_Readers ++; In high level language it is only one statement but in machine level it is a combination of more than one statements like shown below: ( Machine languages are architecture dependent so please do not go into the syntax)

    Statement 1: MOV No_of_Readers, R0
    Statement 2: INC R0
    Statement 3: MOV R0, No_of_Readers 

Consider the scenario where binary semaphore ( mutex) is not used.
Now suppose the first process P1 ( a reader ) executed Statement 1 and Statement 2.
Initially value of No_of_Readers was 0.
After execution of Statement 1 '0' value was moved to the register R0.
After Statement 2 R0 value became 1.

Note that this incremented value is not yet reflected into No_of_Readers.
After this P1 got preempted and another process P2 got into execution. P2 will find the value of No_of_Readers as '0' and will make it value '1'.

At this point P1 again gets a chance to execute and it resumes its execution from Statement 3. But as the registers value was incremented to 1 by P1, it will write '1' into No_of_Reader.

Here is where the problem is: Even though there are 2 readers but the variable No_Of_Readers has value = 1. This is data inconsistency.

To avoid this, the mutex is used.