GATE CSE 2009 | Question: 33

Question

The enter_CS() and leave_CS() functions to implement critical section of a process are realized using test-and-set instruction as follows:

void enter_CS(X)
{
    while(test-and-set(X));
}

void leave_CS(X)
{
    X = 0;
}

In the above solution, $X$ is a memory location associated with the $CS$ and is initialized to $0$. Now consider the following statements:

1. The above solution to $CS$ problem is deadlock-free

2. The solution is starvation free

3. The processes enter $CS$ in FIFO order

4. More than one process can enter $CS$ at the same time

Which of the above statements are TRUE?

• A. (I) only
• B. (I) and (II)
• C. (II) and (III)
• D. (IV) only

Comments

test-and-set(X) returns the old value of X and sets X to 1

Answer 1

hope it might help.....

Answer 2

1. Soultion is Deadlock free.
True. As there is only one resource, deadlock can never happen. Deadlock happens when all the processes (in the deadlock) holds a resource and is waiting for some other resource to get free by some other process.

2. Solution is starvation free
False. As the process which get the resource X can hold it indefinitely. Unitll it calls leave_CS no other process can get X.

3. FIFO order
False. As the test-and-set(X) is called within a while loop, there is no guarantee on the execution flow if there are more than one process competing for the resource X.

4. More than one process can enter CS
False. As test-and-set(X) is an atomic operation this can never happen.

Hope this helps.

Answer 3

A might not be the answer . In case of priority inversion i.e

Let p0 with priority 0 is executing cs and then p1 with a priority 1 came and now wants to execute the cs. Now p0 have to be preempted from the cs.

Now the cpu is with p1 but TSL is with p0. Thus here is a case of SPIN LOCK, which is a kind of DEADLOCK.

Answer 4

The above solution is a simple test-and-set solution that makes sure that deadlock doesn’t occur, but it doesn’t use any queue to avoid starvation or to have FIFO order.