Log In
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 1k views

3 Answers

13 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

15 votes
2 answers
Draw the process state transition diagram of an OS in which (i) each process is in one of the five states: created, ready, running, blocked (i.e., sleep or wait), or terminated, and (ii) only non-preemptive scheduling is used by the OS. Label the transitions appropriately.
asked Sep 16, 2014 in Operating System Kathleen 2.3k views
20 votes
3 answers
The following solution to the single producer single consumer problem uses semaphores for synchronization. #define BUFFSIZE 100 buffer buf[BUFFSIZE]; int first = last = 0; semaphore b_full = 0; semaphore b_empty = BUFFSIZE void producer() { while(1) { produce an ... $p2$, immediately after $c1$ and immediately before $c2$ so that the program works correctly for multiple producers and consumers.
asked Sep 16, 2014 in Operating System Kathleen 2.5k views
26 votes
3 answers
A computer uses $32-bit$ virtual address, and $32-bit$ physical address. The physical memory is byte addressable, and the page size is $4$ $\text{kbytes}$ . It is decided to use two level page tables to translate from virtual address to physical ... entries that can be contained in each page? How many bits are available for storing protection and other information in each page table entry?
asked Sep 16, 2014 in Operating System Kathleen 4.8k views
20 votes
3 answers
The C language is: A context free language A context sensitive language A regular language Parsable fully only by a Turing machine
asked Sep 16, 2014 in Programming Kathleen 4k views