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

1. I think every one understood why option (a) is correct and else options are wrong.
2. I would just like to add a point that would be beneficial. Option B and Option C are inter-related, as in if the processes are in FIFO then there will not be any starvation. So if FIFO then, the solution will be starvation free.

Answer 2

Let me explain why B is wrong

suppose p1 is in critical section (only one can enter into CS because of TSL) and many process(p2,p3,p4,p5....pn) is busy waiting in loop , let me pick one process from many process which are looping  and that picked process is p2, now

consider the case when p1 came out of CS then p3 enters and when p3 comes out then p4 enters because there is no mechanism maintained which ensures after how much time p2 will get turn similarly this goes on till pn and p2 will keep on starving hence it is not starvation free

Answer 3

Necessary criteria for critical section solution are

1. Mutual exclusion
2. Progress 
3. Bounded waiting

Usually test and set is taken as a system call but it is implemented as a hardware instruction.Test_and_Set is a special assembly language instruction that does two operations autonomously. That is, the instruction can not be interrupted in the middle and it is not necessary to disable interrupts

The definition of test-and -set is

test-and-set(x)

{

          t=x  // t is temporary variable

         x=1

        return t

}

given initial value x=0

let A,B,C be the processes trying to enter critical section .

A tries to enter the critical section since x=0 it will get the access, sets x value to 1 and enters critical section.

now, A is in critical section and B tries to enter critical section since x=1 B will be kept waiting on while loop so the system is deadlock free since it is mutually exclusive

If A completes the process and sets X=0 and leaves the critical section so B enters the critical section hence progress is possible 

Case 2:

we will reset all the values so Now X=0 again

Process A tries to enter the critical section since x=0 it will get the access, sets x value to 1 and enters critical section.

now, A is in critical section and B tries to enter critical section since x=1 B will be kept waiting on while loop. If CPU preempts the B. If C tries to enter the critical section since B is preempted C will enter the critical section if A leaves the critical section. so FIFO is not followed

FIFO is not followed then starvation is possible. 

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.
 

Comments

That was really helpful. But, i still have a lil bit doubt  regarding the progress. what if only one process tries to get access to the CS again and again? It is possible to do so. In that case how the progress is assured?

---

Progress: If no process is executing in its critical section and some processes wish to enter their critical sections, then only those processes that are not executing in their remainder section can participate in deciding which will enter its critical section next, and this selection cannot be postponed indefinitely.

Let's understand this definition sentence by sentence.

If no process is executing in its critical section

If there is a process executing in its critical section (even though not stated explicitly, this includes the leave section as well), then this means that some work is getting done. So we are making progress. Otherwise, if this was not the case...

and some processes wish to enter their critical sections

If no process wants to enter their critical sections, then there is no more work to do. Otherwise, if there is at least one process that wishes to enter its critical section...

then only those processes that are not executing in their remainder section

This means we are talking about those processes that are executing in either of the first two sections (remember, no process is executing in its critical section or the leave section)...

can participate in deciding which will enter its critical section next,

Since there is at least one process that wishes to enter its CS, somehow we must choose one of them to enter its CS. But who's going to make this decision? Those process who already requested permission to enter their critical sections have the right to participate in making this decision. In addition, those processes that may wish to enter their CSs but have not yet requested the permission to do so (this means that they are in executing in the first section) also have the right to participate in making this decision.

and this selection cannot be postponed indefinitely.

This states that it will take a limited amount of time to select a process to enter its CS. In particular, no deadlock or livelock will occur. So after this limited amount of time, a process will enter its CS and do some work, thereby making progress.

The example that u have given comes under bounded waiting

Bounded waiting: There exists a bound, or limit, on the number of times other processes are allowed to enter their critical sections after a process has made request to enter its critical section and before that request is granted.

---

Thank you very very much for this elaborate answer. This really cleared my misconceptions :)

Answer 4

.............