OS Synchronization

Question

In process synchronozation , when we can say progress is satisfied and when progress not satisfied?

Explain with example.

(Donot give just definition, need clear difference when progress is satisfied and when not satisfied)

Answer 1

section1. Entry_try(cs);

section2. < CS >


section3. Leave_cs(cs);

section4. // some code which have nothing to do with critical section

Definition :

• If no process is executing in its critical section then,
• If there exist some processes that wish to enter their critical sections,
• then only those processes that are not executing in their section 4. can participate in the decision of which will enter its critical section next.
• This decision cannot be postponed indefinitely.

Indirectly, if no process is in the critical section, the algorithm must decide quickly who enters next if someone wants.

If above conditions are satisfied then we call progress is satisfied. Otherwise not.

Explanation :

If some process is inside the critical section, assume some progress is going on.

( now we assume CS is free  )

1. If no process wants to enter the critical section, means nothing left to do. (do not consider progress here)
2. Assume a process is executing section4. That means this process is executing something which has no relation at all to the critical section. This process must not involve in the decision of who will enter in the critical section next.
3. Only those process who wish to enter into the critical section and executing in section1 can participate in the decision of who will enter next in CS.
4. "the algorithm must decide quickly who enters next if someone wants.",
   1. Sometimes two or more processes while trying to enter into CS and executing some entry_try code , they get stuck in deciding who will enter first (or next). And it happens indefinitely, causing deadlock and NO PROGRESS at all.

 We will take two examples of two process solutions

1. Peterson's solution. (progress satisfied)
2. Strict alteration solution using turn variable. (progress not satisfied)

First Peterson's solution. (progress satisfied)

Assume p and q are the two processes. interested_flag[2] = {0,0}

1. If only p tries to enter into CS, p will definitely enter CS. why because, interested_flag[q] = FALSE
2. If only q tries to enter into CS, q will definitely enter CS. why because, interested_flag[p] = FALSE
3. If both p and q try simultaneously, one of them will definitely enter into section2 (CS) in finite time. The process who executed assigned turn first will enter CS first.

 Next, Strict alteration. (progress not satisfied)

1. Assume turn value becomes zero after few alteration. and now P0 no more wants to enter into CS. (P0 exits)
2. Then if P1 tries to enter into CS and arrive at section1. it never breaks the while loop and forever loops in there. So P0's decision not to execute in section1 or section2 is affecting P1's entry indefinitely.

Comments

Suppose P1 is executing till the end now turn  = 1 now if again P1 wants to execute will end up falling in infinite loop. Then comes P2, what is value of turn will it take 0 or 1

---

P2 come means what?

if it means after P2 executes then turn = 0, before P2 executes turn =1

---

P2 comes means  after executing P1 if P2 will come the  what will value of turn it will take to run  process P2