7.6k views

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?

1. (I) only
2. (I) and (II)
3. (II) and (III)
4. (IV) only

edited | 7.6k views
+1
test-and-set(X) returns the old value of X and sets X to 1

The solution satisfies:

1. Mutual Exclusion as test-and-set is an indivisible (atomic) instruction (makes option (IV) wrong)
2. Progress as at initially $X$ is $0$ and at least one process can enter critical section at any time.

But no guarantee that a process eventually will enter $CS$ and hence option (IV) is false. Also, no ordering of processes is maintained and hence III is also false.

So, eliminating all the $3$ choices remains $A$.

by Boss (19.9k points)
edited by
+11
1. Progress is not satisfied here. Suppose P1 is in leave_CS() and going to execute X=0 whereas P2 trying to enter critical section is iterating in the while loop. So this shows that P1 which is not interested in entering in to CS is blocking P2 which is interested to enter into CS. Hence Progress not satisfied.

2. Coming to option 2 of Starvation. Lets suppose P1,P2,P3 as three processes. Now P1 enters CS and P2,P3 are iterating the while loop. Now when P1 exexutes X=0,then immediately instead of P2, P3 gets into CS. This shows there is starvation.
0
how should we check for starvation in such questions?..Arjun sir can you please explain?
+6
I guess we call option A deadlock free just because there is only one resource - a memory location X and there cannot be a deadlock with only one resource, we need at least two resources for circular wait to occur. So I feel there is no need to evaluate whether individual requirements of deadlock occur or not. Am I right?
0
This makes more sense to me.
+1
Considering a case :

suppose process P1 wants to enter the Critical Section, so it will first set the Lock to 1 (occupied) using TSL...now a Higher priority process P2 arrives due to which P1 got preempted by the OS.

Now out of P1 or P2 which will enter the CS?? seems like a deadlock...
0
suppose p1 wants to enter into the critical section then it makes lock value as 0 to 1 now p1 is going into the critical section ,now if any higher priority process arrives then it will get critical section only if p1 leaves the critical section and makes lock value 0, it always follow atomic value into the critical section due to it is the problem of TSL..!
0
But the problem of priority inversion will not cause deadlock in TSL?
+7
@nirmal that is a spin lock not a deadlock because P2 wants critical section , and cpu is with P2

And p1 wants cpu and critical section is with P1 so there is lock between them but as the P2 is in run state and P1 is in ready queue so it is not deadlock

It is $\mathbf{spinlock}$
0
@prince_sindhiya  can  pls elaborate spinlock  ?
+4

Spin lock is explained by many one you can see the discussion below I  want to add a line to it spin lock is not a deadlock

Deadlock occurs when a set of processes are blocked which are not in ready or running state and waiting for some resources but as i mentioned in spin lock the process are not not in wait or block state .

+9

first part explanation of first comment (by  Gate Brahmachari) is wrong

why the people hitting like without reading that comment

+6
Progress satisfied here..as no process outside of its critical section blocking other process process to enter in its critical section
+2

@  Spin-lock is a type of locking protocol, not a problem.

In fact, Spin-locks are useful in some scenarios (mentioned in the given link)

The problem arising here due to the priority inversion (which i asked earlier) is actually a "Livelock" which is different from a Deadlock

0
@nirmal later i also came to know about it from Deepak poonia sir but whatever i told it was said to me by iiscian and i noted that in my copy , may be he was wrong

Thnxx Nirmal
0
No problem bro
+2
Progress is not satisfied here. Suppose P1 is in leave_CS() and going to execute X=0 whereas P2 trying to enter critical section is iterating in the while loop. So this shows that P1 which is not interested in entering in to CS is blocking P2 which is interested to enter into CS. Hence Progress not satisfied.

Absolutely wrong logic. progress is satisfies here
+1
yes progress satisfies here
+1
progress is satisfied here because there is no deadlock.
0
does (no deadlock) ALWAYS imply (progress)  ??
+1

@  I think not, Consider the case when system is OFF (no power supply), In this case there is no deadlock but there is no progress also, that is, processor is idle.

+3

How progress is satisfied here?

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

void leave_CS(X)
{
X = 0;
}

Structure of Each process is as below

do{
//some initialization code
enter_CS(X);

//critical region code..

leave_CS(X);

//Remainder Section(Some cleanup tasks performed by process say)
}while(TRUE);

Suppose, there are n processes.P1 was successful in executing enter_CS(X) completely and P1 is inside CS.

Since some process is there in CS-->Progress is satisfied.

Now, all other n-1 processes will loop in the while loop of enter_CS(X) method.

Now, P1 leaves and sets X=0.

Now no process is inside CS.

All n-1 processes are executing the entry_section code.Here also, we are guaranteed that in a finite amount of time, atleast one process will find X=0, and it will enter CS and remaining n-2 processes will again keep looping in the entry code.So, finite amount of time will be taken in deciding who will enter CS next.->Progress satisfied.!

0
But this type of situation is not considered as deadlock . Because when P1 turn will come it will start its execution and after it exits it will set x=0. After that p2 can execute.

I.It is a test and set(load the previous value of R0 and store 1 into it),instruction,atomic in nature.Only one process executing TSL can only enter CS as it makes the value of variable=1 and other process trying to enter the CS would find value of variable=1 and hence wont enter the CS.

TSL can be thought of as

2 Store 1

3.CMP R0,#0

4.JNZ step 1

1 and 2 as atomic.

ME is guaranteed.

II. TSl suffers unbounded waiting.This is because there is no strict alteration and number of processes are also not bounded.

Lets us suppose

1.TSL

2.while(TSl!=1);

3.CS

4. store variable=0

P1:12 CS| P2 wants to enter but has to wait due to variable being 1 |P1 :4 | P3 enters executes TSL 1 2  CS | P2 wants to enter but has to wait due to variable being 1 |P3 :4 |P4 enters

So poor P2 everytime has to starve unlucky guy.

III. From the above example only we see that P2 although came first was scheduled later so FCFS not maintained.

Iv. ME guaranteed,

A)I Only

by Active (3.6k points)
edited by
0
How it is deadlock free ? I mean here ME is satisfied , progress is not , because if P1 after coming out of CS got terminated before executing X=0; and all other process waiting for X=0 will starve . Hence a deadlock ??
+1
p1 will not be terminated/preempted for ever, (no semaphores here) it will run at some later stage and will execute x=0, so some other process can enter cs , and only one process will enter the cs as TSL is atomic op.

but we dont know which one will enter cs, hence starvation (no bounded waiting, order)
0
Good soln but you wrote the TSL code completely wrong;

The condition should be While( variable !=0) or While(variable ==1)
A) First one is true as it is simple test and set.
B) seems to be true but it is not as when a process is in spin lock all the thread of a process is waiting for this thread to complete job , whenever it is executed by cpu so in every context switch you are waiting for spin lock to over. means you are starving because you can complete other thread in parallel. This can be remove by introducing the waiting que but there is no que mention so system is starving.
c) No possible as no order or Que order is mention in the question.
d) Not possible.
by Active (3.8k points)

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.

by Boss (45.4k points)
0
But wouldnt there be a deadlock in tsl due to priority inversion?
+3
deadlock means both processes are in blocked state, but in priority inveraion only one is blocked and the other higher priority process is in ready state
0
But how its deadlock free? here cpu is required to process with lower priority to make lock variable free but cpu is busy to put process with higher priority in critical section and thus  both get locked which is nothing but the Spinlock. Then how its different than deadlock.
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.
by (81 points)
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
by Active (1.4k points)

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

by Loyal (5.7k points)
edited
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.
by (201 points)