Lock Variable

Question

What is Lock Variable solution to critical section problem?

Does it satisfy all the conditions like Mutual exclusion, Bounded waiting and Progress?

Comments

Yes, Lock Variable solution to critical section problem is use to solve all these 3 ME, progress and BW .

---

Sir, I think ME is not guaranteed in Lock variable solution to CS problem.

---

@Dinkar  Can you please lead me to a reference to support this? :)

---

Sir how mutual exclusion is satisfied ?

are you considering any modified version of lock variable solution ?

---

Can you tell me which lock variable does not support?

I know semaphore supports all. Peterson's supports all except may be bounded waiting. (Am I right?)

Can you tell me what lock variable does not support mutual exclusion? Because I think the the whole purpose of lock was to achieve mutual exclusion.

---

Yes, The whole purpose of use Lock is to to achieve Mutual Exclusion .

If there is no lock, there is No order means more than one process can enter into CS at a same time ..so ME does not satisfy ..

And peterson's algo supports all 3 --> ME, BW and progress ( as there is no deadlock ) .

From wiki 

The algorithm satisfies the three essential criteria to solve the critical section problem, The three criteria are mutual exclusion, progress, and bounded waiting

https://en.wikipedia.org/wiki/Peterson%27s_algorithm#The_algorithm

---

I was talking about the simplest implementation using Lock variable. It is like:

Initially Lock=0(indicating CS is free)

---

Entry section:

while(lock!=0);

set Lock=1;

---

CS

---

Exit section:

set Lock=0;

---

Here as you can see ME is not guaranteed. Peterson's solution, however, satisfies ME, there is no doubt.

---

In addition to locking a variable peterson is also using the array like interested[2] or something which helps to ensure progress .

 

if simply we use locking variable like using a flag variable

if flag is set to 0 CS if free you may enter

flag is 1 indicates CS is busy

 

but with some combination of preemption multiple processes may enter in cs here we are neither checking for strict alteration(Decker's) or if a process want to go or not into the CS (like in peterson's).

---

@ G.K.T  and @Pinaki Dash

Read this thread :

https://gateoverflow.in/72010/difference-between-dekkers-peterson-solutions-critical-section

https://cs.stackexchange.com/questions/12621/contrasting-peterson-s-and-dekker-s-algorithms ( see 2nd answer )

https://cs.stackexchange.com/questions/60235/is-bounded-waiting-ensured-in-given-version-of-dekkers-solution-for-critical-se ( see BW is satisfied in Dekker's algo too ) 

so it all means the use of Lock is to guarantee that it satisfies all three conditions :

1. ME
2. Progress 
3. Bounded waiting 

and both Peterson and Dekker's algo satisfy all 3 conditions.

---

@Bikram Sir, I was not talking about Peterson's or Dekker's. I was referring to the simplest algo using Lock variable only and nothing else, for which I have written the pseudocode above.

Thanks for all the references.

---

@pinaki

yes, i have seen it.. but the thing is we use lock to ensure Mutual exclusion property.

see the definition of lock , it is an object that can only be owned by a single thread at any given time .

so that means no two threads can acquire a same lock at same time , which leads to Mutual exclusion, is not it ?

And there are  2 operations we can perform on a lock:

• acquire: mark the lock as owned by the current thread; if some other thread already owns the lock then first wait until the lock is free. Lock typically includes a queue to keep track of multiple waiting threads.
• release: mark the lock as free (it must currently be owned by the calling thread).

So all it means ME is satisfied using Lock .. infact the purpose of lock is this .

And a good CS problem satisfy all 3 conditions like ME, BW and progress.

---

lock variable does NOT guarantee MUTUAL EXCLUSION BOSS. those who are watching, don’t go by this. i think bikram you are making a mistake.

Answer 1

Refer to this PDF: https://cseweb.ucsd.edu/classes/fa05/cse120/lectures/120-l5.pdf

Answer 2

Peterson and Dekker's algo, both solves :

ME, BW and progress these three conditions.

Also progress is satisfied so deadlock is not possible ( bcoz progress done in finite time where as deadlock is infinite waiting).

Reference :

1. https://cs.stackexchange.com/questions/12621/contrasting-peterson-s-and-dekker-s-algorithms ( see 2nd answer , the table)
2. https://cs.stackexchange.com/questions/60235/is-bounded-waiting-ensured-in-given-version-of-dekkers-solution-for-critical-se

Comments

I mistook Dekker's as strict alternation..

---

yes Dekker's satisfies all the three properties.

---

@Bikram Sir,

In my understanding Lock Variable does not hold Mutual Exclusion and Bounded Waiting it can only hold Progress.

(If_i_am_Wrong)

Please give an example on Lock Variable .

Answer 3

lock  variable solution does not satisfy Mutual exclusion.