<p>In a concurrent runtime environment simple things can seem weird ... hope this can help.</p>

<p>We have a <strong>BUILT-IN ATOMIC CAS1</strong> having this semantic:</p>

<pre><code>int CAS1(int *addr, int oldval, int newval) {
  int currval = *addr;
  if (currval == oldval) *addr = newval;
  return currval;
}
</code></pre>

<p>We need to define an <strong>ATOMIC RDCSS function</strong> using <strong>CAS1</strong> and having the following semantic:</p>

<pre><code>int RDCSS(int *addr1, int oldval1, int *addr2, int oldval2, int newval2) {
  int res = *addr;
  if (res == oldval2 &amp;&amp; *addr1 == oldval1) *addr2 = newval2;
  return res;
}
</code></pre>

<p>Intuitively: we need to CONCURRENTLY change the value at addr2 only if *addr1 == oldval1 ... if another thread is changing it we can help the other thread to complete the operation, then we can retry.</p>

<p><strong>RDCSS</strong> function will be used (see article) to define CASN. Now, we define a <strong>RDCSS Descriptor</strong> in the following way:</p>

<pre><code>RDCSSDESCRI
int *addr1   
int oldval1
int *addr2   
int oldval2
int newval2
</code></pre>

<p>Then we implement RDCSS in the following way:</p>

<pre><code>int RDCSS( RDCSSDESCRI *d ) {
  do {
    res = CAS1(d-&gt;addr2, d-&gt;oldval2, d);  // STEP1
    if (IsDescriptor(res)) Complete(res); // STEP2
  } while (IsDescriptor(res);             // STEP3
  if (res == d-&gt;oldval2) Complete(d);     // STEP4
  return res;
}

void Complete( RDCSSDESCRI *d ) {
  int val = *(d-&gt;addr1);
  if (val == d-&gt;oldval1) CAS1(d-&gt;addr2, d, d-&gt;newval2);
    else CAS1(d-&gt;addr2, d, d-&gt;oldval2);  
}
</code></pre>

<ul>
<li>STEP1: first we try to change the value of *addr2 to our (own) descriptor d, if CAS1 succeeds then res == d->oldval2 (i.e. res is NOT a descriptor)</li>
<li>STEP2: check if res is a descriptor i.e. STEP1 failed (another thread changed addr2) ... help another thread completing the operation</li>
<li>STEP3: retry the STEP1 if we didn't succeed in storing our descriptor d</li>
<li>STEP4: if we fetched our expected value from addr2 then we succeeded in storing our descriptor (pointer) in addr2 and <strong>we can complete our task storing newval2 to *addr2 iif *addr1 == oldval1</strong></li>
</ul>

<p><strong>ANSWER TO YOUR QUESTION</strong></p>

<p>If we omit STEP4 then the <strong>if(... &amp;&amp; *addr1==oldval1) *addr2=newval2</strong> part of the RDCSS semantic will never be executed (... or better: it can be executed in an umpredictable way by other threads helping the current one).</p>

<p>As pointed out by you in your comment the condition <em>if(res == d1->oldval2)</em> at STEP4 is unnecessary: even if we omit it, both CAS1 in Complete() will fail because *(d->addr2)!=d. Its only purpouse is avoid a function call.</p>

<p>Example T1=thread1, T2=thread2:</p>

<pre><code>remember that addr1 / addr2 are in a shared data zone !!!

T1 enter RDCSS function
T2 enter RDCSS function
T2 complete STEP1 (and store the pointer to its descriptor d2 in addr2)
T1 at STEP1 the CAS1 fails and res = d2
T2 or T1 completes *(d2-&gt;addr2)=d2-&gt;newval2 (suppose that *(d2-&gt;addr1)==d2-&gt;oldval1)
T1 execute STEP1 and now CAS1 can fail because *addr2 == d2-&gt;newval2
   and maybe d2-&gt;newval2 != d1-&gt;oldval2, in every case at the end 
   res == d2-&gt;newval2 (fail) or
   res == d1-&gt;oldval2 (success)
T1 at STEP2 skips the call to Complete() (because now res is not a descriptor)
T1 at STEP3 exits the loop (because now res is not a descriptor)
T1 at STEP4 T1 is ready to store d1-&gt;newval2 to addr2, but only if
   *(d1-&gt;addr2)==d (we are working on our descriptor) and *(d1-&gt;addr1)==d1-&gt;oldval1
   ( Custom() function)
</code></pre>

CC BY-SA 3.0
2011-06-23T19:24:21.993Z
Thank you, good explanation. I totally missed the point that CAS1 returns the old value, not the new one.
axel22
CC BY-SA 3.0
2011-06-23T19:58:03.773Z
But, in the scenario, the last 2 lines say that: without the condition at STEP4, T1 can store the value, because `addr2` contains `d2->newval2`. But, it seems to me that the CAS1 in the `Complete` will just fail, because it expects the old value to be the descriptor `d1` - nothing will be written by T1. Right?
axel22
CC BY-SA 3.0
2011-06-23T22:29:51.397Z
@axel22: I missed the CAS1 in Complete() :-D. Yes you are right ... my example is wrong, the if condition is used only to avoid a function call, if we throw away the **if()** nothing changes. Obviously the **Complete(d)** at STEP4 is necessary. Now I modify the example.
Marzio De Biasi
CC BY-SA 3.0
2018-04-24T22:10:04.830Z
Avoiding a CAS we expect to fail is a cache optimization technique as far as I know, since on real hardware it usually has negative effects such as flushing cache lines and acquiring exclusive access to a cache line. I guess the author of the paper wanted the algorithm to be  as practical as possible in addition to being correct.
Tim Seguine
CC BY-SA 3.0
2011-06-23T17:05:11.583Z
2011-06-23T22:52:55.417Z
2011-06-23T22:52:55.417Z
Marzio De Biasi
<p>In the <a href="http://research.microsoft.com/en-us/um/people/tharris/papers/2002-disc.pdf" rel="nofollow">paper</a> with the same title as that of this question, the authors describe how to build a <a href="http://en.wikipedia.org/wiki/Non-blocking_algorithm" rel="nofollow">nonblocking</a> <a href="http://en.wikipedia.org/wiki/Linearizability" rel="nofollow">linearizable</a> <a href="http://en.wikipedia.org/wiki/Compare-and-swap" rel="nofollow">multi-word CAS</a> operation using only a single-word CAS. They first introduce the double-compare-single-swap operation - RDCSS, as follows:</p>

<pre><code>word_t RDCSS(RDCSSDescriptor_t *d) {
  do {
    r = CAS1(d-&gt;a2, d-&gt;o2, d);
    if (IsDescriptor(r)) Complete(r);
  } while (IsDescriptor(r));
  if (r == d-&gt;o2) Complete(d); // !!
  return r;
}

void Complete(RDCSSDescriptor_t *d) {
  v = *(d-&gt;a1);
  if (v == d-&gt;o1) CAS1(d-&gt;a2, d, d-&gt;n2);
  else CAS1(d-&gt;a2, d, d-&gt;o2);
}
</code></pre>

<p>where the <code>RDCSSDescriptor_t</code> is a structure with the following fields:</p>

<ul>
<li><code>a1</code> - address of the first condition</li>
<li><code>o1</code> - value expected at the first address</li>
<li><code>a2</code> - address of the second condition</li>
<li><code>o2</code> - value expected at the second address</li>
<li><code>n2</code> - the new value to be written at the second address</li>
</ul>

<p>This descriptor is created and initialized once in a thread which initiates the RDCSS operation - no other thread has a reference to it until the first CAS1 in the function <code>RDCSS</code> succeeds, making the descriptor reachable (or <em>active</em> in the terminology of the paper).</p>

<p>The idea behind the algorithm is the following - replace the second memory location with a descriptor saying what you want to do. Then, given that the descriptor is present, check the first memory location to see if its value changed. If it hasn't, replace the descriptor at the second memory location with the new value. Otherwise, set the second memory location back to the old value.</p>

<p>The authors do not explain why the line with the <code>!!</code> comment is necessary within the paper. It seems to me that the <code>CAS1</code> instructions in the <code>Complete</code> function will always fail after this check, provided that there is no concurrent modification. And if there was a concurrent modification between the check and the CAS in <code>Complete</code>, then the thread doing the check should still fail with its CAS in <code>Complete</code>, since the concurrent modification should not use the same descriptor <code>d</code>.</p>

<p>My question is: Can the check in the function <code>RDCSSS</code>, <code>if (r == d-&gt;o2)...</code> be omitted, with RDCSS still maintaining the semantics of a double compare, single swap instruction which is <strong>linearizable</strong> and <strong>lock-free</strong>?  (line with <code>!!</code> comment)</p>

<p>If not, can you describe the scenario where this line is actually necessary to ensure correctness?</p>

<p>Thank you.</p>

CC BY-SA 3.0
2011-06-22T16:12:50.830Z
Firstly, to understand what's going on, we'd need to see the data structure RDCSSDescriptor_t. Secondly, this is probably off topic here as it does not deal with theoretical computer science; it would be better to ask this on stackoverflow.com.
Dave Clarke
CC BY-SA 3.0
2011-06-22T17:02:50.007Z
The link to the paper is broken.
Aaron Sterling
CC BY-SA 3.0
2011-06-22T20:03:37.963Z
I apologize for the link - it should now work. I've updated the question to describe what the descriptor is. The reason I've not posted this on stackoverflow.com is that the FAQ says that this site is for research-level questions in computer science. I thought the questions of lock-freedom and linearizability of an algorithm qualify as such. I hope I understood the FAQ incorrectly.
axel22
CC BY-SA 3.0
2011-06-22T20:43:21.947Z
The key word you missed in the FAQ was "theoretical". As some people find the question interesting, I'll leave it open.
Dave Clarke
CC BY-SA 3.0
2011-06-22T23:11:37.470Z
@Dave Clarke: I am not sure what's not theoretical about this question. Can you elaborate your point of view ?
Mohammad Alaggan
CC BY-SA 3.0
2011-06-23T06:23:20.637Z
It sounds like a very practical question, implementing a multi-word CAS in terms of single-word CAS. Of course the way of analysing this could involve theoretical techniques.
Dave Clarke
CC BY-SA 3.0
2011-06-23T11:02:05.153Z
@Dave: I am not an expert in this sub-area, but to me this sounds like a very typical TCS question. You are given two models of computation (A: with a single-word CAS, B: with a multi-word CAS) and a complexity measure (number of CASs), and you are asked if you can simulate model B in model A, and with what worst-case overhead. (Here it might be a bit misleading that the simulation is given as a piece of C code instead of pseudocode; this might suggest to a theory person that this is related to real-world programming challenges.)
Jukka Suomela
<dc.parallel-comp><concurrency>
A practical multi-word compare-and-swap operation
axel22
# A practical multi-word compare-and-swap operation

(Asked by: username_0 on 2011-06-22)

In the paper with the same title as that of this question, the authors describe how to build a nonblocking linearizable multi-word CAS operation using only a single-word CAS. They first introduce the double-compare-single-swap operation - RDCSS, as follows:
word_t RDCSS(RDCSSDescriptor_t *d) {
  do {
    r = CAS1(d->a2, d->o2, d);
    if (IsDescriptor(r)) Complete(r);
  } while (IsDescriptor(r));
  if (r == d->o2) Complete(d); // !!
  return r;
}

void Complete(RDCSSDescriptor_t *d) {
  v = *(d->a1);
  if (v == d->o1) CAS1(d->a2, d, d->n2);
  else CAS1(d->a2, d, d->o2);
}

where the RDCSSDescriptor_t is a structure with the following fields:

a1 - address of the first condition
o1 - value expected at the first address
a2 - address of the second condition
o2 - value expected at the second address
n2 - the new value to be written at the second address

This descriptor is created and initialized once in a thread which initiates the RDCSS operation - no other thread has a reference to it until the first CAS1 in the function RDCSS succeeds, making the descriptor reachable (or active in the terminology of the paper).
The idea behind the algorithm is the following - replace the second memory location with a descriptor saying what you want to do. Then, given that the descriptor is present, check the first memory location to see if its value changed. If it hasn't, replace the descriptor at the second memory location with the new value. Otherwise, set the second memory location back to the old value.
The authors do not explain why the line with the !! comment is necessary within the paper. It seems to me that the CAS1 instructions in the Complete function will always fail after this check, provided that there is no concurrent modification. And if there was a concurrent modification between the check and the CAS in Complete, then the thread doing the check should still fail with its CAS in Complete, since the concurrent modification should not use the same descriptor d.
My question is: Can the check in the function RDCSSS, if (r == d->o2)... be omitted, with RDCSS still maintaining the semantics of a double compare, single swap instruction which is linearizable and lock-free?  (line with !! comment)
If not, can you describe the scenario where this line is actually necessary to ensure correctness?
Thank you.

**Tags:** dc.parallel-comp, concurrency

> **Comments:**
> **username_1**: Firstly, to understand what's going on, we'd need to see the data structure RDCSSDescriptor_t. Secondly, this is probably off topic here as it does not deal with theoretical computer science; it would be better to ask this on stackoverflow.com.  
> **username_2**: The link to the paper is broken.  
> **username_0**: I apologize for the link - it should now work. I've updated the question to describe what the descriptor is. The reason I've not posted this on stackoverflow.com is that the FAQ says that this site is for research-level questions in computer science. I thought the questions of lock-freedom and linearizability of an algorithm qualify as such. I hope I understood the FAQ incorrectly.  
> **username_1**: The key word you missed in the FAQ was "theoretical". As some people find the question interesting, I'll leave it open.  
> **username_3**: @username_1: I am not sure what's not theoretical about this question. Can you elaborate your point of view ?  
> **username_1**: It sounds like a very practical question, implementing a multi-word CAS in terms of single-word CAS. Of course the way of analysing this could involve theoretical techniques.  
> **username_4**: @Dave: I am not an expert in this sub-area, but to me this sounds like a very typical TCS question. You are given two models of computation (A: with a single-word CAS, B: with a multi-word CAS) and a complexity measure (number of CASs), and you are asked if you can simulate model B in model A, and with what worst-case overhead. (Here it might be a bit misleading that the simulation is given as a piece of C code instead of pseudocode; this might suggest to a theory person that this is related to real-world programming challenges.)  

---

## 1 answers

### Answer by username_5 on 2011-06-23. Score: 9 | Accepted answer

In a concurrent runtime environment simple things can seem weird ... hope this can help.
We have a BUILT-IN ATOMIC CAS1 having this semantic:
int CAS1(int *addr, int oldval, int newval) {
  int currval = *addr;
  if (currval == oldval) *addr = newval;
  return currval;
}

We need to define an ATOMIC RDCSS function using CAS1 and having the following semantic:
int RDCSS(int *addr1, int oldval1, int *addr2, int oldval2, int newval2) {
  int res = *addr;
  if (res == oldval2 && *addr1 == oldval1) *addr2 = newval2;
  return res;
}

Intuitively: we need to CONCURRENTLY change the value at addr2 only if *addr1 == oldval1 ... if another thread is changing it we can help the other thread to complete the operation, then we can retry.
RDCSS function will be used (see article) to define CASN. Now, we define a RDCSS Descriptor in the following way:
RDCSSDESCRI
int *addr1   
int oldval1
int *addr2   
int oldval2
int newval2

Then we implement RDCSS in the following way:
int RDCSS( RDCSSDESCRI *d ) {
  do {
    res = CAS1(d->addr2, d->oldval2, d);  // STEP1
    if (IsDescriptor(res)) Complete(res); // STEP2
  } while (IsDescriptor(res);             // STEP3
  if (res == d->oldval2) Complete(d);     // STEP4
  return res;
}

void Complete( RDCSSDESCRI *d ) {
  int val = *(d->addr1);
  if (val == d->oldval1) CAS1(d->addr2, d, d->newval2);
    else CAS1(d->addr2, d, d->oldval2);  
}


STEP1: first we try to change the value of *addr2 to our (own) descriptor d, if CAS1 succeeds then res == d->oldval2 (i.e. res is NOT a descriptor)
STEP2: check if res is a descriptor i.e. STEP1 failed (another thread changed addr2) ... help another thread completing the operation
STEP3: retry the STEP1 if we didn't succeed in storing our descriptor d
STEP4: if we fetched our expected value from addr2 then we succeeded in storing our descriptor (pointer) in addr2 and we can complete our task storing newval2 to *addr2 iif *addr1 == oldval1

ANSWER TO YOUR QUESTION
If we omit STEP4 then the if(... && *addr1==oldval1) *addr2=newval2 part of the RDCSS semantic will never be executed (... or better: it can be executed in an umpredictable way by other threads helping the current one).
As pointed out by you in your comment the condition if(res == d1->oldval2) at STEP4 is unnecessary: even if we omit it, both CAS1 in Complete() will fail because *(d->addr2)!=d. Its only purpouse is avoid a function call.
Example T1=thread1, T2=thread2:
remember that addr1 / addr2 are in a shared data zone !!!

T1 enter RDCSS function
T2 enter RDCSS function
T2 complete STEP1 (and store the pointer to its descriptor d2 in addr2)
T1 at STEP1 the CAS1 fails and res = d2
T2 or T1 completes *(d2->addr2)=d2->newval2 (suppose that *(d2->addr1)==d2->oldval1)
T1 execute STEP1 and now CAS1 can fail because *addr2 == d2->newval2
   and maybe d2->newval2 != d1->oldval2, in every case at the end 
   res == d2->newval2 (fail) or
   res == d1->oldval2 (success)
T1 at STEP2 skips the call to Complete() (because now res is not a descriptor)
T1 at STEP3 exits the loop (because now res is not a descriptor)
T1 at STEP4 T1 is ready to store d1->newval2 to addr2, but only if
   *(d1->addr2)==d (we are working on our descriptor) and *(d1->addr1)==d1->oldval1
   ( Custom() function)

> **Comments:**
> **username_0**: Thank you, good explanation. I totally missed the point that CAS1 returns the old value, not the new one.  
> **username_0**: But, in the scenario, the last 2 lines say that: without the condition at STEP4, T1 can store the value, because `addr2` contains `d2->newval2`. But, it seems to me that the CAS1 in the `Complete` will just fail, because it expects the old value to be the descriptor `d1` - nothing will be written by T1. Right?  
> **username_5**: @username_0: I missed the CAS1 in Complete() :-D. Yes you are right ... my example is wrong, the if condition is used only to avoid a function call, if we throw away the **if()** nothing changes. Obviously the **Complete(d)** at STEP4 is necessary. Now I modify the example.  
> **username_6**: Avoiding a CAS we expect to fail is a cache optimization technique as far as I know, since on real hardware it usually has negative effects such as flushing cache lines and acquiring exclusive access to a cache line. I guess the author of the paper wanted the algorithm to be  as practical as possible in addition to being correct.  

---

