Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 Jun 22 '11 at 16:12
    
The link to the paper is broken. –  Aaron Sterling Jun 22 '11 at 17:02
1  
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 Jun 22 '11 at 20:03
    
The key word you missed in the FAQ was "theoretical". As some people find the question interesting, I'll leave it open. –  Dave Clarke Jun 22 '11 at 20:43
3  
@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 Jun 23 '11 at 11:02
show 2 more comments

1 Answer

up vote 6 down vote accepted

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)
share|improve this answer
    
Thank you, good explanation. I totally missed the point that CAS1 returns the old value, not the new one. –  axel22 Jun 23 '11 at 19:24
    
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 Jun 23 '11 at 19:58
    
@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 Jun 23 '11 at 22:29
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.