The Gateway to Computer Science Excellence
+5 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() 
    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?
in Operating System by | 849 views

3 Answers

+11 votes

Solution will be

void enter-cs()
void leave-cs()

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.


@Ayush Upadhyaya what is the approach do you follow while considering all possible interleaving? I mean to find the deadlock condition in non atomic test and set is difficult in that pressure situation :(


@tusharp-just practice buddy.The more complicated a problem is to you, the more number of times you'll see it, then more comfortable you'll be with it.

Brother,here in case of non atomic execution,deadlock is occurring but i couldn't see any hold and wait condition..Here the main reason of deadlock is "the lost value of a variable". Can you help me with this..

@Ayush Upadhyaya



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
0 votes

deadlock free ony if test&set of mutex done atomically and also spin lock possible in case of priority inversion.

deadlock possible if test&set is not atomic.

starvation is possible. 



Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,487 answers
95,294 users