CODEWITHSUNDEEP
concurrencyoperating-systemsemaphorebinary-semaphore
Siddharth
Siddharth

Reputation: 71

Starvation in test and set instruction

The following question has been asked in GATE Exam:
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:
I. The above solution to CS problem is deadlock-free
II. The solution is starvation free.
III. The processes enter CS in FIFO order.
IV More than one process can enter CS at the same time.
Which of the above statements is TRUE?

The correct answer is given as option I.
While I and IV options are clear to me I'm not able to understand how is starvation possible here.
If someone could help explain me it would be great. Thanks.

Upvotes: 1

Views: 1523

Answers (2)

Rain Win
Rain Win

Reputation: 57

When a process executing the while loop inside this enter_CS method, it keeps calling the test-and-set method with a time interval between each call. (this time interval may depend on how the operating system schedule each process to use CPU)

Suppose process_0 start to execute while loop when process_1 is already inside the critical section. If process_1 always exits and enters the critical section within this time interval, then process_0 will never succeed in entering cs. (the situation will get worse when the number of processes waiting for one critical section is huge)

Peterson Algorithm provide a 'flag' turn to avoid this starvation situation.

Upvotes: 3

Yogi
Yogi

Reputation: 476

The above code guarantees that if multiple processes are trying to acquire the lock one of them will get the lock. The acquisition of lock doesn't depend upon the arrival of the processes. Consider a scenario when there is always more than two processes try to acquire the lock, there is no guarantee that a particular process will eventually get the lock. I am hoping that acquisition in FIFO order is clear to you.

Upvotes: 0

Related Questions