turn=i;
do
{
while ( turn != i); //if not i's turn , wait indefinately
// critical section
turn = j; //after i leaves critical section, lets j in
//remainder section
}while (1);//loop again
This solution requires alternating access to the critical section. If P1 wants to access the critical section twice (two loops) while P2 is all the while in its remainder section, then P1 has to wait indefinately. This does not satisfy the progress requirement. But there is bounded wait since eventually P2 will either finish or re-enter the critical section.
Algorithm 2
Flag is boolean array of 2 elements ( bool flag[2];) initialized to false
Process P1, P2 are associated to values 0 and 1 respectively
and i and j are either 1 or 0 such that j==1-i
both processes have this structure, all variable are globally known
do
{
flag[i] = true;//ready to enter CS
while (flag[j]); //if j also want the critical section then i should wait
// critical section
flag[i]= false; //after i leaves critical section, lets j in
//remainder section
}while (1);//loop again
Instead of relying on process i to let process j in, we have made i and j simply indicate whether they need the CS .That is why this algorithm needs two flag, one for i and one for j. This solves the problem of i not being allowed to have the CS twice in a row. In this setup he can have the CS twice in a row, but we still do not satisfy the progress requirement. If i and j both set the flags to true simultaneously then both process will be stuck in an infinate loop. We want a solution that does not rely on lucky timing.
Algorithm 3
Combine Algorithms 1 and 2
I am process i.
do
{
flag[i] = true; //i states that he is ready to enter (he wants) the CS
turn = j; // i generously lets j into CS, if both processes do this, turn will get the later value
while (flag[j] && turn == j); //if j also wants the critical section AND j has set turn to i
//BEFORE i set turn to j (so that my turn = j comes last) then i must wait.
// critical section
flag[i]= false; //after i leaves critical section, lets j in
//remainder section
}while (1);//loop again
This solution fulfills all 3 requirements. Notice we have bounded waiting because once i finishes its CS it lets j in. i will not enter the CS more than once while j is waiting. j's waiting comes to an end. Also we have progress because the once i leaves the critical section he no longer controls j's entry to the CS.
Like a post office or bakery where you take a number and wait to be served.
The process with the lowest number goes first. In case of tie, process with lowest PID goes first.
I am process i. max is a function that finds the largest number in the array.
bool choosing[n]=0;
int number [n]=0;
do{
choosing[i] = true; // I am about to take a number
number[i] = max(number[0], number[1], ...., number[n-1])+1;// I get the largest number of those that are out there
choosing[i]=false;// I finished taking a number
for(j=0;j<n;j++)// go through all the processes
{
while (choosing[j]);//make sure no one is currently taking a number
while ((number[j]!=0)&&((number[j],j)<(number[i],i))); // wait as long as another process has taken a number and
// its number is less than mine (or its PID is less)
}
//c.s.
number[i]=0;//indicate that i have left the C.S.
//remainder
}while(1);
Solution #1, readers preference
semaphore wrt=1,mutex=1;
readcount=0;
writer()
{
wait(wrt);
//writing is done
signal(wrt);
}
reader()
{
wait(mutex); //wait for other reader and if I get in, lock other reader
readcount++; // indicate That I am reading,
if(readcount==1) // If I am the only reader
wait(wrt); //make sure there is no writer
// other wise I can assume the other readers have already locked out the writer
signal(mutex);// let other readers in
///Do the Reading
///(Critical Section Area)
wait(mutex); //since readcount-- is not atomic, I need to prevent several readers from doing it simultaneously
readcount--;
if(readcount==0) // no more readers
signal(wrt); // let writer in
signal(mutex); // let readers in
}
Notice that a=1 is atomic but a-- is not atomic because it is really a = a - 1. So theoretically there could be a context switch between the a-1 and the asignmnet operation in which case, only one decrement of a will occur. Hence there is a need to use a wait (mutex) before readcount--. Otherwise it could happen that the writer is never siganlled to begin writing.
Although this algorithm solves the Readers-writers problem, it could result in a writer waiting indefinately. As long as there is a reader reading, even a reader who came later than the writer, the writer wil be locked out. Therefore this solution is called a reader preference solution. There are 2 other solutions.
Solution #2
int readcount, writecount; (initial value = 0)
semaphore mutex1, mutex2, mutex3, w, r ; (initial value = 1)
reader(){
wait(mutex3);
wait(r);
wait(mutex1);
readcount ++;
if(readcount == 1)
wait(w);
signal(mutex1);
signal(r);
signal(mutex3);
// do reading
wait(mutex1);
readcount--;
if (readcount == 0)
signal(w);
signal(mutex1);
}
writer()
{
wait(mutex2);
writecount++;
if( writecount == 1 )
wait(r);
signal(mutex2);
wait(w);
//writing is performed
signal(w);
wait(mutex2);
writecoun--;
if (writecount == 0)
signal(r);
signal(mutex2);
}
The second readers-writers problem may starve readers. Therefore, the third readers-writers problem is sometimes proposed. It adds the constraint that no thread shall be allowed to starve; that is, the operation of obtaining a lock on the shared data will always terminate in a bounded amount of time.
© Nachum Danzig 2010