CAS (compare and swap) is a synchronization primitive to deal with race conditions as presented in Race conditions . This primitive checks whether a variable has the value previously read and in case it does, CAS changes the contents of that variable - all of this is applied atomically, i.e. no other thread can interrupt this set of actions. This is usually useful when reading a value, and we want to write the value changed, to see that the value has not changed since we have read it.
For example given the code:
P(){
do {
1. tmp = read(x)
2. tmp = tmp+1
3. } while (! CAS (x, tmp, tmp+1));
}
This is very similar to the code in the previous post, but now we capture the case when someone has written some different value and prevents some undesirable schedules.
For instance, let's consider the following schedule:
A.1
B.1
B.2
B.3
A.2
A.3
In the previous post A.3 wrote in x without noticing if someone else had changed x's value in the meanwhile. Now, with the CAS statement, once B has written a new value, the CAS statement fails forcing A to read the updated value before writing it incremented by one. (which is what we would expect!)
No comments:
Post a Comment