Temu duga umum: Apakah masalah ABA dalam CAS, dan bagaimanakah anda mencegahnya?

Gesaan dan kes penggunaan

CAS menulis nilai baharu secara atomik apabila lokasi yang dikongsi masih sepadan dengan nilai yang dijangkakan. ABA berlaku apabila bebenang T1 membaca A, dijeda, bebenang T2 menukar A kepada B dan kembali kepada A, dan T1 berjaya kerana ia melihat A semula tanpa mengetahui perubahan perantaraan tersebut.

Tindanan, giliran (queues), dan kemas kini optimistik tanpa kunci boleh menghadapinya. AtomicReference.compareAndSet Oracle membandingkan rujukan, manakala AtomicStampedReference membandingkan rujukan dan cap integer bersama-sama; compare_exchange C++ ialah primitif biasa untuk struktur tanpa kunci. Kategori teras ialah general: prinsip dan pertukaran konkurensi, bebas daripada sintaks Java atau C++.

Perkara yang dinilai oleh penemu duga

• Sama ada anda boleh memberikan garis masa yang tepat yang menunjukkan bahawa "kembali kepada A" tidak bermaksud "tidak berubah."
• Sama ada anda memahami bahawa CAS memeriksa perwakilan yang dibekalkan, bukan sejarah penuh.
• Sama ada anda membezakan ABA daripada perlumbaan data (data races), keterlihatan, dan pepijat jangka hayat objek.
• Sama ada anda membandingkan tag versi, objek tidak boleh ubah (immutable), penuding bahaya (hazard pointers)/epok, dan kunci pada sempadan yang betul.
• Sama ada anda membincangkan limpahan (overflow), kos, penambakan semula, dan jaminan kemajuan.

Penjelasan sebelum menjawab

• Adakah CAS membandingkan nilai, rujukan, atau keadaan komposit berversi?
• Bolehkah objek kongsi ditambak semula atau alamat digunakan semula? ABA dan penambakan semula selalunya mesti direka bentuk bersama-sama.
• Adakah keperluannya kemajuan tanpa kunci atau sekadar ketepatan? Kunci mungkin lebih mudah dan lebih senang diaudit.
• Bolehkah cap versi membalut (wrap)? Tentukan lebar, jangka hayat, atau tingkah laku pembalutan.
• Adakah operasi mengemas kini skalar atau nod dan pautannya? Risiko bergantung pada invarian komposit.
• Model memori manakah yang terpakai? Keatoman semata-mata tidak menerbitkan setiap medan atau melindungi jangka hayat.

Rangka jawapan 30 saat

"ABA ialah apabila T1 membaca A, T2 melakukan A→B→A, dan T1 kemudiannya berjaya dengan A jangkaan yang sudah basi. CAS membuktikan bahawa perwakilan semasa sepadan; ia tidak membuktikan bahawa tiada peralihan berlaku. Saya akan menggabungkan rujukan dengan cap versi yang berubah secara monotonik, menggunakan penambakan selamat supaya alamat tidak digunakan semula semasa diperhatikan, atau memilih kunci. Saya terlebih dahulu menjelaskan jangka hayat objek, keperluan kemajuan, dan limpahan cap sebelum memilih AtomicStampedReference, penuding bertag, atau penguncian."

Jawapan mendalam langkah demi langkah

Langkah 1: Bina semula garis masa dengan tindanan tanpa kunci.

Kepala (head) ialah A -> B. T1 membaca head = A dan A.next, bersedia untuk melakukan CAS kepala kepada A.next. T1 dijeda; T2 meletupkan (pops) A, memproses B, dan menolak (pushes) A yang sama atau nod yang alamatnya digunakan semula. Perwakilan kepala ialah A semula, jadi T1 mungkin berjaya dengan penuding next daripada snapshot lama.

Langkah 2: Tunjukkan sebab keatoman CAS bukan kecacatannya.

CAS adalah atomik. Perwakilan yang dijangkakan cuma terlalu kecil: rujukan atau skalar tidak menyatakan apa-apa tentang bilangan peralihan yang berlaku atau sama ada nod itu masih mewakili keadaan logik yang sama.

Langkah 3: Asingkan konsep yang berkaitan.

Perlumbaan data ialah masalah capaian tidak disegerakkan pada peringkat bahasa; ABA boleh berlaku walaupun CAS adalah atomik dan capaian disegerakkan. Keterlihatan menentukan perkara yang boleh diperhatikan oleh bebenang. ABA membabitkan nilai semasa yang sama dengan sejarah yang berbeza. Penambakan semula menentukan sama ada penuding lama masih boleh dinyahrungkaikan (dereferenced) dengan selamat.

Langkah 4: Tambah rujukan dan cap versi.

state = (reference: A, stamp: 7)
T1 reads (A, 7)
T2 changes (A, 7) -> (B, 8) -> (A, 9)
T1 CAS expected (A, 7) -> (C, 8)  // fails

AtomicStampedReference.compareAndSet Java membandingkan rujukan dan cap bersama-sama. C++ boleh menggunakan atomik dwi-lebar, bit penuding bertag, atau CAS komposit yang disokong platform, tetapi platform sasaran mesti benar-benar menyediakan keatoman yang diperlukan.

Langkah 5: Kendalikan jangka hayat dan penggunaan semula alamat.

Cap mengesan perubahan perwakilan; ia tidak menjadikan penambakan semula selamat. Bahasa bukan GC mungkin memerlukan penuding bahaya, penambakan berasaskan epok, pengiraan rujukan, atau pembebasan tertangguh supaya bebenang tidak pernah menyahrungkaikan memori yang dilepaskan. Bahasa GC masih perlu mempertimbangkan penggunaan semula rujukan secara logik.

Langkah 6: Nilaikan limpahan cap.

Cap terhingga akhirnya akan membalut (wraps). Jika bebenang memegang snapshot lama cukup lama, nilai yang dibalut mungkin sepadan semula. Gunakan versi yang cukup lebar, hadkan jangka hayat snapshot, gunakan generasi yang tidak boleh digunakan semula dalam tetingkap tersebut, atau pilih penyegerakan yang lebih kukuh. "Menambah int" bukanlah bukti tanpa syarat.

Langkah 7: Bandingkan alternatif.

Kunci mengekalkan bacaan, kemas kini, dan jangka hayat komposit di dalam satu bahagian kritikal dan selalunya paling mudah untuk dibuktikan. Struktur data tidak boleh ubah menyatakan keadaan baharu dengan objek baharu. Transaksi atau lajur versi pangkalan data menyediakan semakan optimistik yang serupa pada sempadan ketahanan. Pilih berdasarkan pertikaian (contention), pendaman, kerumitan, dan keboleh-auditan.

Langkah 8: Uji ketepatan serentak.

Bina jadual terkawal yang menjeda T1, membiarkan T2 melaksanakan A→B→A, dan mengesahkan bahawa CAS tanpa versi boleh berjaya manakala CAS berversi gagal. Tambah ujian pertikaian, sempadan balutan cap, penambakan semula, dan percubaan semula. Ujian unit bebenang tunggal tidak boleh membuktikan ketepatan algoritma tanpa kunci.

Jawapan sampel berkualiti tinggi

"ABA ialah peralihan keadaan yang tersembunyi oleh perbandingan nilai. T1 membaca kepala tindanan A dan dijeda; T2 meletupkan A, melakukan A→B→A, dan menolak A kembali. T1 melihat A dan berjaya, berpotensi menulis penuding next daripada snapshot basinya. CAS kekal atomik; perwakilan yang dijangkakan tidak mempunyai maklumat versi. Saya akan menjadikan rujukan ditambah cap monotonik sebagai satu keadaan atomik—AtomicStampedReference dalam Java, atau CAS dwi-lebar/penuding bertag yang disahkan dalam C++—dan menggandingkannya dengan penuding bahaya atau penambakan epok di luar GC. Jika pertikaian rendah atau pembuktian dan penyelenggaraan menjadi keutamaan, saya akan menggunakan kunci. Saya akan mengesahkan dengan jadual A→B→A yang dipaksa dan ujian tekanan penambakan semula."

Kesilapan biasa

• Memanggil ABA sebagai kegagalan keatoman CAS → tersilap menyatakan sifat primitif → terangkan sejarah yang hilang.
• Hanya membandingkan nilai nod → versi berbeza boleh mempunyai nilai yang sama → bandingkan rujukan ditambah versi.
• Menambah cap tetapi mengabaikan penambakan semula → nod yang dilepaskan masih boleh dinyahrungkaikan → reka bentuk perlindungan jangka hayat.
• Menyamakan perlumbaan data dengan ABA → mengelirukan masalah model memori dan algoritma → takrifkannya secara berasingan.
• Mengabaikan pembalutan cap → sistem jangka panjang mengekalkan tetingkap padanan → takrifkan lebar atau had jangka hayat.
• Mendakwa API menyelesaikan setiap masalah → perbandingan atomik tidak menjamin invarian perniagaan → nyatakan sempadan komposit dan penambakan.
• Menggunakan helah bit penuding yang tidak boleh alih → penjajaran atau lebar atomik mungkin berbeza → sahkan platform sasaran.
• Hanya menguji satu bebenang → jalinan pencetus tidak pernah berlaku → tambah jeda terkawal dan tekanan.

Soalan susulan dan jawapan

Susulan 1: Mengapakah CAS boleh berjaya selepas A berubah kepada B dan kembali kepada A?

CAS biasa membandingkan perwakilan jangkaan semasa. Jika perwakilan itu hanya rujukan A atau nilai A, kesaksamaan sudah mencukupi; primitif tidak merekodkan B perantaraan.

Susulan 2: Adakah cap versi sentiasa menyelesaikan ABA?

Ia mengesan A→B→A selagi versi belum membalut dan kemas kini rujukan-tambah-cap adalah atomik. Limpahan, kemas kini komposit bukan atomik, atau nod yang dilepaskan memerlukan reka bentuk tambahan.

Susulan 3: Bagaimanakah AtomicReference dan AtomicStampedReference berbeza?

AtomicReference membandingkan dan mengemas kini rujukan secara atomik. AtomicStampedReference menganggap rujukan dan cap integer sebagai satu keadaan dan membandingkan kedua-duanya, menambahkan peruntukan dan kos pengurusan cap untuk pengesanan perubahan.

Susulan 4: Mengapakah nod tidak boleh ubah (immutable) membantu?

Nod tidak boleh ubah tidak mengubah next atau medan perniagaan di tempat asal; keadaan baharu diwakili oleh objek baharu, mengurangkan gangguan snapshot basi. Penambakan semula dan penggunaan semula rujukan secara logik masih memerlukan perhatian.

Susulan 5: Adakah penuding bahaya menyelesaikan ABA atau penambakan semula?

Ia terutamanya menghalang penambakan semula nod yang sedang dibaca oleh bebenang. Jika alamat masih boleh digunakan semula untuk nod logik yang berbeza, pemversian, pengetagan, atau pertahanan ABA yang lain tetap diperlukan.

Susulan 6: Mengapa tidak selalu menggunakan kunci?

Kunci biasanya paling mudah untuk dibuktikan dan diselenggara, tetapi ia boleh menyekat dan menambah pertikaian atau pembalikan keutamaan. Utamakannya apabila kesederhanaan mendominasi; terima kerumitan tanpa kunci hanya untuk keperluan kemajuan atau pendaman yang jelas.

Susulan 7: Bagaimanakah anda membuktikan tindanan yang dibaiki adalah betul?

Takrifkan keadaan kepala komposit, titik linearisasi CAS, jangka hayat nod, dan invarian. Uji jadual A→B→A, percubaan semula CAS, sempadan cap, dan tekanan penambakan semula, kemudian semak susunan penerbitan dan pemerolehan terhadap model memori sasaran.