in Operating System edited by
24,532 views
61 votes
61 votes

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
in Operating System edited by
24.5k views

1 comment

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

13 Answers

51 votes
51 votes
Best answer

The answer is (A) only.

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$.

edited by

4 Comments

This is a condition of priority inversion and this is a spinlock a kind of deadlock but not the deadlock.
1
1
By definition of progress which can be found in any standard textbook :
By the time any process is done executing in CS, it can decide which process shall enter its CS next, by executing V(X), which resides in the exit section, and this is not postponed indefinitely. Hence progress is satisfied.
3
3

The terms “spinlock” and “busy waiting” are not interchangeable. Spinlock is a kind of implementation of mutex locks where busy waiting is possible. 

Reference: Galvin 10th edition, section – 6.5

1
1
25 votes
25 votes

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

1.Load Ro

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

edited by

3 Comments

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 ??
0
0
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)
1
1
edited by
Good soln but you wrote the TSL code completely wrong;

The condition should be While( variable !=0) or While(variable ==1)
0
0
12 votes
12 votes
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.
8 votes
8 votes

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.
 

3 Comments

But wouldnt there be a deadlock in tsl due to priority inversion?
0
0
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
3
3
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.
0
0
Answer:

Related questions