NWEN303 Concurrent Programming
8 Critical section Do It Yourself
Marco Servetto VUW
● ● ●
Critical Section The main Idea of the critical section:
A room, that can host only one person at the time, That person can
– assume the room is in a tied-up (coherent) state – mess up with the stuff in the room,
– leave the room in any tied-up (coherent) state.
Every language provide some way to do the critical section.
Certain parallel programming patterns intrinsically require to use critical sections. The problems arising from using (multiple, apparently unrelated) critical sections are pure hell.
But trying to re-implement support for the critical section correctly is just plain stupid.
However, someone in the past had to do it, at least once, and to prove it correct. Understanding how hard it was to reach such task, should convince us to not try to do it again.
● ●
●
●
●
–
–
–
Critical Section – requisites
Before trying to understand possible implementations for the critical section, we should understand what we mean by a correct support for it!
Statements from the critical section of two or more workers must not interleave. That is, no more then one worker is allowed at any time (Mutual Exclusion)
If some workers are trying to enter their critical sections, then one of them must eventually succeed (No Stuck)
If any worker tries to enter its critical section, than that worker must eventually succeed (No Individual Starvation)
●
–
Critical Section – assumptions
In order to make the task possible, we need to assume some minimal correctness properties of the various workers:
All shared variables are “volatile” in the Java sense
●
– –
Critical Section – assumptions
In order to make the task possible, we need to assume some minimal correctness properties of the various workers:
All shared variables are “volatile” in the Java sense
All the workers agree to properly perform some precise pre-protocol before entering the critical section and some post-protocol while exiting.
●
– –
–
Critical Section – assumptions
In order to make the task possible, we need to assume some minimal correctness properties of the various workers:
All shared variables are “volatile” in the Java sense
All the workers agree to properly perform some precise pre-protocol before entering the critical section and some post-protocol while exiting.
No worker sit in critical section for infinite time.
( however, workers can still go in loop forever outside of the critical section)
●
– –
–
–
Critical Section – assumptions
In order to make the task possible, we need to assume some minimal correctness properties of the various workers:
All shared variables are “volatile” in the Java sense
All the workers agree to properly perform some precise pre-protocol before entering the critical section and some post-protocol while exiting.
No worker sit in critical section for infinite time.
( however, workers can still go in loop forever outside of the critical section)
Operations inside the (pre/post)-protocol will not fail (for example with a run-time exception)
●
– –
–
–
–
Critical Section – assumptions
In order to make the task possible, we need to assume some minimal correctness properties of the various workers:
All shared variables are “volatile” in the Java sense
All the workers agree to properly perform some precise pre-protocol before entering the critical section and some post-protocol while exiting.
No worker sit in critical section for infinite time.
( however, workers can still go in loop forever outside of the critical section)
Operations inside the (pre/post)-protocol will not fail (for example with a run-time exception)
The number of tasks is fixed and well known.
Critical Section (pre/post)-protocol
static volatile Type var =/*initial value*/; …
//normal operations, it can loop forever
//pre-protocol
try {
//critical section operations, // termination assured
}
finally {/*post-protocol*/}
●
– –
–
–
–
●
Note: those assumptions are absolutely unrealistic and unreasonable! However, if we can not solve our problem with those assumptions, then we have no hope without them.
Critical Section – assumptions
In order to make the task possible, we need to assume some minimal correctness properties of the various workers:
All shared variables are “volatile” in the Java sense
All the workers agree to properly perform some precise pre-protocol before entering the critical section and some post-protocol while exiting.
No task sit in critical section for infinite time.
( however, workers can still go in loop forever outside of the critical section)
Operations inside the (pre/post)-protocol will not fail (for example with a run-time exception)
The number of workers is fixed and well known.
●
No worker sit in critical section for infinite time. -otherwise no way to avoid individual starvation
Why I need those assumptions
●
●
No worker sit in critical section for infinite time. -otherwise no way to avoid individual starvation
Workers agree (pre/post)-protocol -otherwise no point in protocol itself
Why I need those assumptions
●
●
●
No worker sit in critical section for infinite time. -otherwise no way to avoid individual starvation
Workers agree (pre/post)-protocol -otherwise no point in protocol itself
The number of workers is fixed and well known -otherwise need of precise semantic of collections
Why I need those assumptions
●
●
●
●
No worker sit in critical section for infinite time. -otherwise no way to avoid individual starvation
Workers agree (pre/post)-protocol -otherwise no point in protocol itself
The number of workers is fixed and well known -otherwise need of precise semantic of collections
all shared variables are “volatile” in the Java sense -otherwise impossible to ensure information sharing
Why I need those assumptions
●
●
●
●
●
No worker sit in critical section for infinite time. -otherwise no way to avoid individual starvation
Workers agree (pre/post)-protocol -otherwise no point in protocol itself
The number of workers is fixed and well known -otherwise need of precise semantic of collections
all shared variables are “volatile” in the Java sense -otherwise impossible to ensure information sharing
operations inside (pre/post)-protocol not fail -otherwise hard to reason on protocol properties
Why I need those assumptions
Critical Section Attempt 1
static volatile int turn =1; …while(true){
//normal operations, it can loop forever while(turn!=1){}//pre-protocol
try{//critical section operations, // termination assured
…while(true){
//normal operations, it can loop forever
while(turn!=2){}//pre-protocol try{//critical section operations,
// termination assured }finally{turn=1;/*post-protocol*/}
}
“Mutual Exclusion” holds?
“No Stuck” holds? (Door locked, Key in, no-one inside) “No Individual Starvation” holds?
}finally{turn=2;/*post-protocol*/} }
● ● ●
Critical Section Attempt 1
static volatile int turn =1; …while(true){
//normal operations, it can loop forever while(turn!=1){}//pre-protocol
try{//critical section operations, // termination assured
…while(true){
//normal operations, it can loop forever
while(turn!=2){}//pre-protocol try{//critical section operations,
// termination assured }finally{turn=1;/*post-protocol*/}
}
“Mutual Exclusion” holds? yes “No Stuck” holds?
“No Individual Starvation” holds?
}finally{turn=2;/*post-protocol*/} }
● ● ●
Critical Section Attempt 1
static volatile int turn =1; …while(true){
//normal operations, it can loop forever while(turn!=1){}//pre-protocol
try{//critical section operations, // termination assured
…while(true){
//normal operations, it can loop forever
while(turn!=2){}//pre-protocol try{//critical section operations,
// termination assured }finally{turn=1;/*post-protocol*/}
}
“Mutual Exclusion” holds? yes “No Stuck” holds? yes
“No Individual Starvation” holds?
}finally{turn=2;/*post-protocol*/} }
● ● ●
Critical Section Attempt 1
static volatile int turn =1; …while(true){
//normal operations, it can loop forever while(turn!=1){}//pre-protocol
try{//critical section operations, // termination assured
…while(true){
//normal operations, it can loop forever
while(turn!=2){}//pre-protocol try{//critical section operations,
// termination assured }finally{turn=1;/*post-protocol*/}
}
“Mutual Exclusion” holds? yes “No Stuck” holds? yes
“No Individual Starvation” holds? no if loop in normal operations
}finally{turn=2;/*post-protocol*/} }
●
●
●
Critical Section Attempt 2
static volatile boolean want1 =false; static volatile boolean want2 =false;
…while(true){
//normal operations, it can loop forever
while(want2){}//pre-protocol
want1=true;//pre-protocol
try{//critical section operations, // termination assured
…while(true){
//normal operations, it can loop forever
while(want1){}//pre-protocol
want2=true;//pre-protocol
try{//critical section operations, // termination assured
}finally{want1=false;/*post-prot*/} }finally{want2=false;/*post-prot*/} }}
“Mutual Exclusion” holds?
“No Stuck” holds?
“No Individual Starvation” holds?
●
● ●
Critical Section Attempt 2
static volatile boolean want1 =false; static volatile boolean want2 =false;
…while(true){
//normal operations, it can loop forever
while(want2){}//pre-protocol
want1=true;//pre-protocol
try{//critical section operations, // termination assured
…while(true){
//normal operations, it can loop forever
while(want1){}//pre-protocol
want2=true;//pre-protocol
try{//critical section operations, // termination assured
}finally{want1=false;/*post-prot*/} }finally{want2=false;/*post-prot*/} }}
“Mutual Exclusion” holds?
no, just imagine symmetric execution “No Stuck” holds?
“No Individual Starvation” holds?
●
–
● ●
Critical Section Attempt 2b
static volatile boolean want1 =true; static volatile boolean want2 =false;
…while(true){
//normal operations, it can loop forever
while(want2){}//pre-protocol
want1=true;//pre-protocol
try{//critical section operations, // termination assured
…while(true){
//normal operations, it can loop forever
while(want1){}//pre-protocol
want2=true;//pre-protocol
try{//critical section operations, // termination assured
}finally{want1=false;/*post-prot*/} }finally{want2=false;/*post-prot*/} }}
“Mutual Exclusion” holds?
“No Stuck” holds?
“No Individual Starvation” holds?
●
● ●
Critical Section Attempt 2b
static volatile boolean want1 =true; static volatile boolean want2 =false;
…while(true){
//normal operations, it can loop forever
while(want2){}//pre-protocol
want1=true;//pre-protocol
try{//critical section operations, // termination assured
…while(true){
//normal operations, it can loop forever
while(want1){}//pre-protocol
want2=true;//pre-protocol
try{//critical section operations, // termination assured
}finally{want1=false;/*post-prot*/} }finally{want2=false;/*post-prot*/} }}
“Mutual Exclusion” holds?
no, one round of left task, and then we are back to false false
●
–
● ●
“No Stuck” holds?
“No Individual Starvation” holds?
Critical Section Attempt 3
static volatile boolean want1 =false; static volatile boolean want2 =false;
…while(true){
//normal operations, it can loop forever
want1=true;//pre-protocol
while(want2){}//pre-protocol
try{//critical section operations, // termination assured
…while(true){
//normal operations, it can loop forever
want2=true;//pre-protocol
while(want1){}//pre-protocol
try{//critical section operations, // termination assured
}finally{want1=false;/*post-prot*/} }finally{want2=false;/*post-prot*/} }}
“Mutual Exclusion” holds?
“No Stuck” holds?
“No Individual Starvation” holds?
● ● ●
Critical Section Attempt 3
static volatile boolean want1 =false; static volatile boolean want2 =false;
…while(true){
//normal operations, it can loop forever
want1=true;//pre-protocol
while(want2){}//pre-protocol
try{//critical section operations, // termination assured
…while(true){
//normal operations, it can loop forever
want2=true;//pre-protocol
while(want1){}//pre-protocol
try{//critical section operations, // termination assured
}finally{want1=false;/*post-prot*/} }finally{want2=false;/*post-prot*/} }}
“Mutual Exclusion” holds? yes? “No Stuck” holds?
“No Individual Starvation” holds?
● ● ●
Critical Section Attempt 3
static volatile boolean want1 =false; static volatile boolean want2 =false;
…while(true){
//normal operations, it can loop forever
want1=true;//pre-protocol
while(want2){}//pre-protocol
try{//critical section operations, // termination assured
…while(true){
//normal operations, it can loop forever
want2=true;//pre-protocol
while(want1){}//pre-protocol
try{//critical section operations, // termination assured
}finally{want1=false;/*post-prot*/} }finally{want2=false;/*post-prot*/} }}
“Mutual Exclusion” holds? yes? “No Stuck” holds? No!
“No Individual Starvation” holds?
● ● ●
Critical Section Attempt 4
static volatile boolean want1 =false; static volatile boolean want2 =false;
…while(true){
//normal operations, it can loop forever
want2=true;//pre-protocol while(want1){//pre-protocol
want2=false;//pre-protocol
want2=true;}//pre-protocol try{//critical section operations,
// termination assured }finally{want1=false;/*post-prot*/} }finally{want2=false;/*post-prot*/}
}}
“Mutual Exclusion” holds?
“No Stuck” holds?
“No Individual Starvation” holds?
…while(true){
//normal operations, it can loop forever
want1=true;//pre-protocol while(want2){//pre-protocol
want1=false;//pre-protocol
want1=true;}//pre-protocol try{//critical section operations,
// termination assured
● ● ●
Critical Section Attempt 4
static volatile boolean want1 =false; static volatile boolean want2 =false;
…while(true){
//normal operations, it can loop forever
want2=true;//pre-protocol while(want1){//pre-protocol
want2=false;//pre-protocol
want2=true;}//pre-protocol try{//critical section operations,
// termination assured }finally{want1=false;/*post-prot*/} }finally{want2=false;/*post-prot*/}
}}
“Mutual Exclusion” holds? yes? “No Stuck” holds?
“No Individual Starvation” holds?
…while(true){
//normal operations, it can loop forever
want1=true;//pre-protocol while(want2){//pre-protocol
want1=false;//pre-protocol
want1=true;}//pre-protocol try{//critical section operations,
// termination assured
● ● ●
Critical Section Attempt 4
static volatile boolean want1 =false; static volatile boolean want2 =false;
…while(true){
//normal operations, it can loop forever
want2=true;//pre-protocol while(want1){//pre-protocol
want2=false;//pre-protocol
want2=true;}//pre-protocol try{//critical section operations,
// termination assured }finally{want1=false;/*post-prot*/} }finally{want2=false;/*post-prot*/}
}}
“Mutual Exclusion” holds? yes? “No Stuck” holds? yes
“No Individual Starvation” holds?
…while(true){
//normal operations, it can loop forever
want1=true;//pre-protocol while(want2){//pre-protocol
want1=false;//pre-protocol
want1=true;}//pre-protocol try{//critical section operations,
// termination assured
● ● ●
Critical Section Attempt 4
static volatile boolean want1 =false; static volatile boolean want2 =false;
…while(true){
//normal operations, it can loop forever
want2=true;//pre-protocol while(want1){//pre-protocol
want2=false;//pre-protocol
want2=true;}//pre-protocol try{//critical section operations,
// termination assured }finally{want1=false;/*post-prot*/} }finally{want2=false;/*post-prot*/}
}}
“Mutual Exclusion” holds? yes? “No Stuck” holds? yes
“No Individual Starvation” holds? no
-just imagine infinitely long symmetric execution
…while(true){
//normal operations, it can loop forever
want1=true;//pre-protocol while(want2){//pre-protocol
want1=false;//pre-protocol
want1=true;}//pre-protocol try{//critical section operations,
// termination assured
●
●
●
Critical Section Attempt 5 (Dekker’s)
static volatile boolean want1 =false; static volatile boolean want2 =false; static volatile int turn =1; …while(true){
//normal operations, it can loop forever want1=true;//pre-protocol
while(want2){//pre-protocol if(turn==2){//pre-protocol
want1=false;//pre-protocol while(turn!=1){}//pre-protocol want1=true;}}//pre-protocol
try{//critical section operations, // termination assured
}finally{turn=2;/*post-prot*/ want1=false;}/*post-prot*/
…while(true){
//normal operations, it can loop forever
want2=true;//pre-protocol while(want1){//pre-protocol
if(turn==1){//pre-protocol want2=false;//pre-protocol while(turn!=2){}//pre-protocol want2=true;}}//pre-protocol
try{//critical section operations, // termination assured
}finally{turn=1;/*post-prot*/ want2=false;}/*post-prot*/
}
}
Critical Section Attempt 5 (Dekker’s)
static volatile boolean want1 =false; static volatile boolean want2 =false; static volatile int turn =1; …while(true){
//normal operations, it can loop forever want1=true;//i want to enter
while(want2){//if the other do not want, I enter, even if is not my turn, otherwise if(turn==2){//if it not my turn
want1=false;//I surrender my desire to enter while(turn!=1){}//wait for my turn want1=true;}//now I want to enter again
}//if is my turn, and the other wants to enter, I wait for him to stop wanting to enter. try{//critical section operations,
// termination assured }finally{turn=2;/*now is not my turn any more*/
}
All the 3 properties holds. Proof is not trivial.
Is it simple but not obvious how to generalize to more workers.
want1=false;}/*and I do not want to enter*/
Critical Section Attempt 5 (Dekker’s)
So, there is a solution using only primitive features. However Is hard to encode, and slow.
Current architectures have atomic instructions allowing to encode the Critical Section.
Synchronized blocks use such native assembly operations, so they are much faster and general that Dekker inspired solutions.
Why we show you those attempts?
●
●
●
●
●
● ● ● ●
Deadlock Livelock Starvation Race condition
Next Lecture