Operasi membandingkan dan bertukar multi-kata yang praktis

Dalam makalah dengan judul yang sama dengan pertanyaan ini, penulis menggambarkan bagaimana membangun operasi CAS multi-kata linearizable nonblocking hanya menggunakan CAS kata tunggal. Mereka pertama kali memperkenalkan operasi penukaran ganda-bandingkan-tunggal - RDCSS, sebagai berikut:

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);
}

di mana RDCSSDescriptor_tadalah struktur dengan bidang-bidang berikut:

• a1 - alamat kondisi pertama
• o1 - nilai yang diharapkan di alamat pertama
• a2 - alamat kondisi kedua
• o2 - nilai yang diharapkan di alamat kedua
• n2 - nilai baru yang akan ditulis di alamat kedua

Deskriptor ini dibuat dan diinisialisasi sekali dalam utas yang memulai operasi RDCSS - tidak ada utas lain yang memiliki referensi sampai CAS1 pertama dalam fungsi RDCSSberhasil, membuat deskriptor dapat dijangkau (atau aktif dalam terminologi makalah ini).

Gagasan di balik algoritma adalah sebagai berikut - ganti lokasi memori kedua dengan deskriptor yang mengatakan apa yang ingin Anda lakukan. Kemudian, mengingat bahwa deskriptor hadir, periksa lokasi memori pertama untuk melihat apakah nilainya berubah. Jika belum, ganti deskriptor di lokasi memori kedua dengan nilai baru. Jika tidak, atur lokasi memori kedua kembali ke nilai lama.

Para penulis tidak menjelaskan mengapa garis dengan !!komentar itu perlu dalam makalah. Tampak bagi saya bahwa CAS1instruksi dalam Completefungsi akan selalu gagal setelah pemeriksaan ini, asalkan tidak ada modifikasi bersamaan. Dan jika ada modifikasi bersamaan antara cek dan CAS di Complete, maka utas yang melakukan pemeriksaan harus tetap gagal dengan CAS-nya Complete, karena modifikasi bersamaan tidak boleh menggunakan deskriptor yang sama d.

Pertanyaan saya adalah: Dapatkah pemeriksaan dalam fungsi RDCSSS, if (r == d->o2)...dihilangkan, dengan RDCSS masih mempertahankan semantik dari instruksi pembandingan ganda, pertukaran tunggal yang linierisasi dan bebas kunci ? (baris dengan !!komentar)

Jika tidak, dapatkah Anda menggambarkan skenario di mana garis ini sebenarnya diperlukan untuk memastikan kebenaran?

Terima kasih.

Dalam lingkungan runtime bersamaan hal-hal sederhana bisa terasa aneh ... harap ini bisa membantu.

Kami memiliki BUILT-IN ATOMIC CAS1 yang memiliki semantik ini:

int CAS1(int *addr, int oldval, int newval) {
  int currval = *addr;
  if (currval == oldval) *addr = newval;
  return currval;
}

Kita perlu mendefinisikan fungsi RDCSS ATOMIC menggunakan CAS1 dan memiliki semantik berikut:

int RDCSS(int *addr1, int oldval1, int *addr2, int oldval2, int newval2) {
  int res = *addr;
  if (res == oldval2 && *addr1 == oldval1) *addr2 = newval2;
  return res;
}

Secara intuitif: kita perlu mengubah nilai pada addr2 secara kontinyu hanya jika * addr1 == oldval1 ... jika utas lain mengubahnya, kita dapat membantu utas lainnya menyelesaikan operasi, maka kita bisa mencoba lagi.

Fungsi RDCSS akan digunakan (lihat artikel) untuk mendefinisikan CASN. Sekarang, kita mendefinisikan deskriptor RDCSS dengan cara berikut:

RDCSSDESCRI
int *addr1   
int oldval1
int *addr2   
int oldval2
int newval2

Kemudian kami mengimplementasikan RDCSS dengan cara berikut:

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);  
}

• LANGKAH1: pertama kita mencoba mengubah nilai * addr2 ke deskriptor d kita (milik), jika CAS1 berhasil maka res == d-> oldval2 (mis. Res BUKAN deskriptor)
• STEP2: periksa apakah res adalah deskriptor yaitu STEP1 gagal (utas lain diubah addr2) ... bantu utas lain menyelesaikan operasi
• STEP3: coba lagi STEP1 jika kami tidak berhasil menyimpan deskriptor kami d
• STEP4: jika kami mengambil nilai yang kami harapkan dari addr2 maka kami berhasil menyimpan deskriptor (pointer) kami di addr2 dan kami dapat menyelesaikan tugas kami menyimpan newval2 ke * addr2 iif * addr1 == oldval1

JAWABAN UNTUK PERTANYAAN ANDA

Jika kita menghilangkan STEP4 maka if (... && * addr1 == oldval1) * addr2 = newval2 bagian dari semantic RDCSS tidak akan pernah dieksekusi (... atau lebih baik: itu dapat dieksekusi dengan cara yang tidak dapat diramalkan oleh utas lain yang membantu yang sekarang).

Seperti yang Anda tunjukkan dalam komentar Anda, kondisi jika (res == d1-> oldval2) di STEP4 tidak diperlukan: bahkan jika kami menghilangkannya, kedua CAS1 dalam Complete () akan gagal karena * (d-> addr2)! = D . Tujuan utamanya adalah menghindari panggilan fungsi.

Contoh 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)