3,338 views
7 votes
7 votes

The functionality of atomic TEST-AND-SET assembly language instruction is given by the following C function

int TEST-AND-SET (int *x)
{
    int y;
    A1: y=*x;
    A2: *x=1;
    A3: return y;
}
  1. Complete the following C functions for implementing code for entering and leaving critical sections on the above TEST-AND-SET instruction.
    int mutex=0; 
    void enter-cs() 
    { 
        while(......................); 
        
    } 
    void leave-cs() 
    { .........................; 
        
    }
  2. Is the above solution to the critical section problem deadlock free and starvation-free?

  3. For the above solution, show by an example that mutual exclusion is not ensured if TEST-AND-SET instruction is not atomic?

3 Answers

20 votes
20 votes

Solution will be

void enter-cs()
{
    while(TestAndSet(&mutex));
}
void leave-cs()
{
    mutex=0;
}

Here there are two possible cases

Case (I)Test And Set is not ATOMIC: Consider a scenario where first, a process P1 comes, successfully executed enter-cs() and sets mutex to 1. Now, suppose another process P2 comes and executes while(TestAndSet(&mutex)) to gain access to CS. Suppose after executing line 

y=*x=1(mutex is one presently)

P2 gets preempted.

Now P1, resumes and sets mutex to 0.

Now P2 resumes, and executes remaining lines of TestAndSet,

*x=1 (mutex is assigned value 1, value 0 lost permanently)

return y; //1 will be returned.

Now, P2 and any other process which tries to execute enter-cs() will keep looping indefinitely. Now not even process P1 can come.

So, deadlock will occur eventually.

And Deadlock implies starvation so starvation is also there. (But starvation does not  imply deadlock).

Yes, in this case, the mutual exclusion will not hold.

Suppose initially mutex=0.

Process P1 comes and executes the first iteration of while loop of enter-cs-->TestAndSet(&mutex)

y=*x; //0 will be stored in y.

Suppose after executing this line of TestAndSet, P1 gets preempted and process P2 comes.

It also executes while loop of enter-cs() and executes TestAndSet(&mutex)

y=*x; //0 will be stored because mutex was not changed to 1.

*x=1; //mutex changed to 1.

return y. //0 will be returned.

Now P2 exits while loop and gains entry into CS.

Say, P1 resumes, and it executes the remaining line of TestAndSet and it returns 0.

P1, also exits while loop of enter-cs() and comes into CS.

Mutual exclusion is broken!!.

Case (II): TestAndSet is ATOMIC: Mutual exclusion will hold, because the first process to execute TestAndSet when mutex will be 0, will enter CS and rest all other processes will keep looping in the while loop of enter-cs().

Deadlock will not occur, because all other processes, which are looping in the while loop, will do so untill mutex!=0. When the process which is in the CS leaves, it sets mutex=0, and one of the waiting processes which successfully finds mutex=0 AND executes the TestAndSet when mutex=0, will gain access to CS.

Starvation will occur, because as you can see in the code, no piece of code can be seen which is responsible for providing access to waiting processes in a fair shared manner. It might happen that one process always finds mutex to be 1, while rest all other processes are able to enter and leave CS, one at a time.

If some code is added to the leave-section(), which ensures that the waiting processes are given chance to enter CS in the order the request was placed, then starvation won't occur. In short, here BOUNDED WAITING is not ensured. If BOUNDED WAITING is ensured, STARVATION will not occur.

0 votes
0 votes
entry condition : while( TESTANDSET(&mutex) )

exit condition : mutex=0;

 

yes above solution is deadlock free ony if reading and setting of mutex done atomically

I think it is not starvation free but I'm not sure about this

Related questions

16 votes
16 votes
2 answers
1
35 votes
35 votes
3 answers
4
Kathleen asked Sep 15, 2014
10,076 views
The C language is:A context free languageA context sensitive languageA regular languageParsable fully only by a Turing machine