operating system process synchronization

Question

var occupied  
var blocked    
Enter Region:
{
      If (occupied)
      {
                blocked= blocked +1
                sleep ( );        
      }
      else occupied= 1;
}
 

// (critical section)


Exit Region:
{   
    occupied= 0  
    If (blocked)
    {  
           wakeup (process);  
           blocked= blocked – 1;  
    }
 }

Now consider the following statements :
(1) Mutual Exclusion is guaranteed

(2) Deadlock free Algorithm

(3) Progress is guaranteed

Which of the above statements are False?

(a) Only 1      (b) 1 & 2     (c) 1 & 3      (d) none of the above

Answer 1

a) Checking Mutual Exclusion :

To check the mutual exclusion , we assume that the critical section is free initially.In other words let occupied = 0 initially.Let first process P₀ comes and performs the if() statement and then we find this is false.But before going to else which would be the next step , since we talk about concurrent processes , we may take preemption at the end of any statement.

So we are preempting P₀  as soon as it finishes executing if() statement then let P₁ starts its execution of entry code and hence the if() statement .Note that the shared variable occupied is not yet updated since we took preemption of P₀ just after completion of if() statement condition.So P₁ also checks the value of occupied variable and finds it false.

Having done that , we return to P₀ and execute from where it left i.e. the condition evaluated to be false so it sets occupied variable to '1' and enters the critical section.Now we come back to P₁ to perform the remaining portion of entry code from where it left.Since it executed if() statement earlier and the result of evaluation was false , it will be considered false only even though P₀ has set value of occupied to 1 .This is so simply because each instruction is executed exactly once except loop statement.So if() will not be performed again for P₁.So we will consider the result of earlier execution only false.So as a result it executes the else part and not the if() part and hence does occupied = 1 which was done by P₀ though then enters enter into the critical section successfully.

Hence we have P₀ and P₁ accessing critical section at the same time.Hence mutual exclusion fails.

b) Checking progress condition :

To check progress condition , we should ensure that when the critical section is free , and some process are interested to enter into critical section , then this should be allowed.Let us see whether this happens here or not.

Assuming occupied  = 0 , i.e.. critical section being free , then any one process can come and evaluate the if() statement and on finding false it will go to else part and enter into CS subsequently.And even if we take preemption which I have taken earlier , then also in fact more no of processes will be allowed .Thus we can allow process to critical section when it is free.

Hence it is free from deadlock and satisfies progress condition.Deadlock condition occurs in scenarios when preemption is taken such that no process can enter into critical section subsequently.But this is not happening here.

Hence , going by the options , only mutual exclusion is violated and hence statement 1 is false only.

Hence A) option should be correct.

Comments

@Habib , very good (just like stamping by Dhoni :p) ,thank you:)

So, u mean if it is concurrent process

P1 cannot enter C.S., then P1 preempt.

P2 cannot enter C.S., then P2 preempt.

P3 cannot enter C.S., then P3 preempt.

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

like that if there are n process, all can enter C.S. at the same time.rt?

But, it all of them leave C.S. after a certain period of time. So, starvation can occur for a process, but deadlock will not occur. rt?

---

Yes starvation may occur

Answer 2

In the first phase, one process comes inside C.S. When it comes inside C.S., no other process is allowed to come inside C.S. So, all process comes after the 1st process(which is iside C.S.) are blocked outside of C.S. So, we can say those waiting process are in sleep mode. Now, when the process completes it's task, it go outside C.S. and next waiting process can enter inside C.S.

So, all three statement are true.

Ans. D)

Comments

Plz check my answer @srestha..

---

@Srestha, i think u got confused that where is the CS ?

---

No, preemption condition made me wrong.