Semaphore

Question

Let m[0]....m[4] be mutexes (binary semaphores) and P[0].......P[4] be processes.  Suppose each process P[i] executes the following:

wait (m[i]; wait (m(i+1) mode 3]);
     ........... 
     release (m[i]); release (m(i+1) mod 3]);

Will it cause Starvation and deadlock?

If the code change like this

wait (m[i]; wait (m(i+1) mode 5]);
     ........... 
     release (m[i]); release (m(i+1) mod 5]);

Is there any change in answer in this question?

Answer 1

M0,M1,M2,M3,M4 ----- 5 binary semaphores

P0,P1,P2,P3,P4 ----- 5 processes

 

1)

	P0	P1	P2	P3	P4
wait(m[i])	wait(m[0])	wait(m[1])	wait(m[2])	wait(m[3])	wait(m[4])
wait(m[i+1] mod 3)	wait(m[1])	wait(m[2])	wait(m[0])	wait(m[1])	wait(m[2])

 

if every process executes wait(m[i]) then it will lead to dead lock.

 

2)

	P0	P1	P2	P3	P4
wait(m[i])	wait(m[0])	wait(m[1])	wait(m[2])	wait(m[3])	wait(m[4])
wait(m[i+1] mod 5)	wait(m[1])	wait(m[2])	wait(m[3])	wait(m[4])	wait(m[0])

 

if every process executes wait(m[i]) then it will also lead to dead lock.

 

---

 

even if you change the sentences as  wait(m[i+1] mod 3); wait(m[i]); instead of wait(m[i]); wait(m[i+1] mod 3); 

 

1)

	P0	P1	P2	P3	P4
wait(m[i+1] mod 3)	wait(m[1])	wait(m[2])	wait(m[0])	wait(m[1])	wait(m[2])
wait(m[i])	wait(m[0])	wait(m[1])	wait(m[2])	wait(m[3])	wait(m[4])

 

if every process executes wait(m[i+1] mod 3) then it will lead to dead lock.

 

2)

	P0	P1	P2	P3	P4
wait(m[i+1] mod 5)	wait(m[1])	wait(m[2])	wait(m[3])	wait(m[4])	wait(m[0])
wait(m[i])	wait(m[0])	wait(m[1])	wait(m[2])	wait(m[3])	wait(m[4])

 

if every process executes wait(m[i+1] mod 5) then it will lead to dead lock.

Comments

See according to the question, there are 2 wait operation at a time and after that they are releasing. So, why there are deadlock?
It is not told in the question all process will execute at a time
rt?

---

@srestha mam,

if you want to prove there is dead-lock, then you should give atleast one example where deadlock is happening?

if you want to prove there is no deadlock, then you should check every case and every case does not lead to dead-lock.

---

ok, u mean to be all deadlock free solution we need 9 mutex atleast like m[0],....,m[9]

As each process requires 2 processes? rt?

---

actually,it's depend upon how we are accessing them...

with 6 resources, also i can't get dead lock if my code is

wait(m[i]);

wait(m[i+1] mod 6); 

---

plz go detail

Not able to understand

u mean 

release (m[i]); release (m(i+1) mod 3]);

portion not be there for deadlock free?

---

replace 

wait (m[i]); wait (m(i+1) mode 3]);
     ........... 
     release (m[i]); release (m(i+1) mod 3]);

 

with 

 

wait (m[i]); wait (m(i+1) mode 6]);
     ........... 
     release (m[i]); release (m(i+1) mod 6]);

 

note that now you have six resources,m[0] to m[5]

 

then

2)

	P0	P1	P2	P3	P4
wait(m[i])	wait(m[0])	wait(m[1])	wait(m[2])	wait(m[3])	wait(m[4])
wait(m[i+1] mod 3)	wait(m[1])	wait(m[2])	wait(m[3])	wait(m[4])	wait(m[5])

 

if every process executes wait(m[i]) then also, First P4 can executed, then P3,P2,..P0.

 

---

	P0	P1	P2	P3	P4
wait(m[i])	wait(m[0])	wait(m[1])	wait(m[2])	wait(m[3])	wait(m[4])
wait(m[i+1] mod 6)	wait(m[1])	wait(m[2])	wait(m[3])	wait(m[4])	wait(m[5])

according to u then wait(m[5])  will be executed and that is why no deadlock.right?

---

yes, due to that reason, P4 enter in CS, make the operations, exit section executes,... if P4 Completes, blocked process on m4 is release ==>P3 enter into CS and etc...

---

@Shaik Masthan  

in the above given example by you if there are 6 process then there will be deadlock ?

---

yes @mitesh kumar

---

@Shaik Masthan in 2nd part $\rightarrow$ 1) of your answer (the $3rd$ table), none of the $wait(m[i+1] \ mod\ 3)$ statements are changing the mutex $m[4]$, then how come process $P_4$ is deadlocked?

---

@zeeshanmohnavi

let P0,P1,P2 executes the first condition, then it will lead to deadlock !

---

@Shaik Masthan Yes. In that order, it is a deadlock.

So, my understanding is - if there is an order of invocation of the given processes, any of which leads to deadlock, we can confirm, for the solution to this problem, that a deadlock exists.

You have a typo in 1st part $\rightarrow 2)$ wherein it should be $wait(m[i+1] \ mod \ 5)$ instead of $wait(m[i+1] \ mod \ 3)$. Please correct that.

---

So, my understanding is - if there is an order of invocation of the given processes, any of which leads to deadlock, we can confirm, for the solution to this problem, that a deadlock exists.

yes !

 

You have a typo in 1st part

thanks, corrected !