Memahami std :: atomic :: bandingkan_exchange_weak () di C ++ 11

bool compare_exchange_weak (T& expected, T val, ..);

compare_exchange_weak()adalah salah satu primitif pertukaran-perbandingan yang disediakan dalam C ++ 11. Ini lemah dalam arti mengembalikan salah meskipun nilai objek sama dengan expected. Ini karena kegagalan palsu pada beberapa platform di mana urutan instruksi (bukan satu seperti pada x86) digunakan untuk mengimplementasikannya. Pada platform seperti itu, sakelar konteks, memuat ulang alamat yang sama (atau baris cache) oleh utas lain, dll dapat gagal pada primitif. Karena spuriousbukan nilai objek (tidak sama dengan expected) yang gagal dalam operasi. Sebaliknya, ini semacam masalah waktu.

Tapi yang membuat saya bingung adalah apa yang dikatakan dalam C ++ 11 Standard (ISO / IEC 14882),

29.6.5 .. Konsekuensi dari kegagalan palsu adalah bahwa hampir semua penggunaan perbandingan-dan-pertukaran yang lemah akan berada dalam satu lingkaran.

Mengapa harus dalam satu lingkaran di hampir semua penggunaan ? Apakah itu berarti kita akan mengulang ketika gagal karena kegagalan palsu? Jika itu masalahnya, mengapa kita repot-repot menggunakan compare_exchange_weak()dan menulis loop sendiri? Kita hanya bisa menggunakan compare_exchange_strong()yang menurut saya harus menyingkirkan kegagalan palsu untuk kita. Apa kasus penggunaan yang umum compare_exchange_weak()?

Pertanyaan lain terkait. Dalam bukunya "C ++ Concurrency In Action" Anthony berkata,

//Because compare_exchange_weak() can fail spuriously, it must typically
//be used in a loop:

bool expected=false;
extern atomic<bool> b; // set somewhere else
while(!b.compare_exchange_weak(expected,true) && !expected);

//In this case, you keep looping as long as expected is still false,
//indicating that the compare_exchange_weak() call failed spuriously.

Mengapa !expectedada dalam kondisi loop? Apakah itu ada untuk mencegah semua utas kelaparan dan tidak membuat kemajuan untuk beberapa waktu?

Edit: (satu pertanyaan terakhir)

Pada platform yang tidak memiliki instruksi CAS perangkat keras tunggal, versi lemah dan kuat diimplementasikan menggunakan LL / SC (seperti ARM, PowerPC, dll). Jadi, apakah ada perbedaan antara dua loop berikut? Mengapa, jika ada? (Bagi saya, mereka seharusnya memiliki kinerja yang serupa.)

// use LL/SC (or CAS on x86) and ignore/loop on spurious failures
while (!compare_exchange_weak(..))
{ .. }

// use LL/SC (or CAS on x86) and ignore/loop on spurious failures
while (!compare_exchange_strong(..)) 
{ .. }

Saya datang dengan pertanyaan terakhir yang kalian semua sebutkan bahwa mungkin ada perbedaan kinerja di dalam satu lingkaran. Ini juga disebutkan oleh Standar C ++ 11 (ISO / IEC 14882):

Saat bandingkan-dan-tukar dalam satu putaran, versi yang lemah akan menghasilkan kinerja yang lebih baik pada beberapa platform.

Tetapi seperti yang dianalisis di atas, dua versi dalam satu loop harus memberikan kinerja yang sama / serupa. Hal apa yang saya rindukan?

Mengapa melakukan pertukaran dalam satu lingkaran?

Biasanya, Anda ingin pekerjaan Anda selesai sebelum Anda melanjutkan, dengan demikian, Anda memasukkannya compare_exchange_weakke dalam loop sehingga mencoba untuk bertukar sampai berhasil (yaitu, kembali true).

Perhatikan bahwa juga compare_exchange_strongsering digunakan dalam satu lingkaran. Itu tidak gagal karena kegagalan palsu, tetapi gagal karena penulisan serentak.

Mengapa menggunakan weakalih-alih strong?

Cukup mudah: Kegagalan palsu tidak sering terjadi, jadi tidak ada kinerja yang besar. Sebaliknya, menoleransi kegagalan seperti itu memungkinkan implementasi weakversi yang jauh lebih efisien (dibandingkan dengan strong) pada beberapa platform: strongharus selalu memeriksa kegagalan palsu dan menutupinya. Ini mahal.

Jadi, weakdigunakan karena jauh lebih cepat daripada strongdi beberapa platform

Kapan sebaiknya Anda menggunakan weakdan kapan strong?

Status referensi mengisyaratkan kapan harus digunakan weakdan kapan harus menggunakan strong:

Saat bandingkan-dan-tukar dalam satu putaran, versi yang lemah akan menghasilkan kinerja yang lebih baik pada beberapa platform. Ketika perbandingan-dan-pertukaran yang lemah akan membutuhkan loop dan yang kuat tidak akan, yang kuat lebih disukai.

Jadi jawabannya tampaknya cukup sederhana untuk diingat: Jika Anda harus memasukkan loop hanya karena kegagalan palsu, jangan lakukan; gunakan strong. Jika Anda tetap memiliki loop, gunakan weak.

Mengapa !expecteddi contoh

Itu tergantung pada situasi dan semantik yang diinginkan, tetapi biasanya tidak diperlukan untuk kebenaran. Menghilangkannya akan menghasilkan semantik yang sangat mirip. Hanya dalam kasus di mana utas lain mungkin mengatur ulang nilainya menjadi false, semantik bisa menjadi sedikit berbeda (namun saya tidak dapat menemukan contoh yang berarti di mana Anda menginginkannya). Lihat komentar Tony D. untuk penjelasan rinci.

Ini hanyalah jalur cepat ketika utas lain menulis true: Kemudian kami membatalkan alih-alih mencoba menulis truelagi.

Tentang pertanyaan terakhir Anda

Tetapi seperti yang dianalisis di atas, dua versi dalam satu loop harus memberikan kinerja yang sama / serupa. Hal apa yang saya rindukan?

Dari Wikipedia :

Implementasi LL / SC yang sebenarnya tidak selalu berhasil jika tidak ada update bersamaan ke lokasi memori yang dimaksud. Setiap kejadian luar biasa antara dua operasi, seperti sakelar konteks, tautan muat lain, atau bahkan (pada banyak platform) operasi pemuatan atau penyimpanan lainnya, akan menyebabkan kondisi penyimpanan gagal secara palsu. Implementasi yang lebih lama akan gagal jika ada update yang disiarkan melalui bus memori.

Jadi, LL / SC akan gagal secara palsu pada sakelar konteks, misalnya. Sekarang, versi yang kuat akan membawa "loop kecilnya sendiri" untuk mendeteksi kegagalan palsu itu dan menutupinya dengan mencoba lagi. Perhatikan bahwa loop sendiri ini juga lebih rumit daripada loop CAS biasa, karena harus membedakan antara kegagalan palsu (dan menutupinya) dan kegagalan karena akses bersamaan (yang menghasilkan pengembalian dengan nilai false). Versi lemah tidak memiliki loop sendiri.

Karena Anda memberikan loop eksplisit di kedua contoh, tidak perlu memiliki loop kecil untuk versi yang kuat. Akibatnya, dalam contoh strongversi, pemeriksaan kegagalan dilakukan dua kali; sekali oleh compare_exchange_strong(yang lebih rumit karena harus membedakan kegagalan palsu dan akses bersamaan) dan sekali menurut loop Anda. Pemeriksaan mahal ini tidak perlu dan alasan mengapa weakakan lebih cepat di sini.

Perhatikan juga bahwa argumen Anda (LL / SC) hanyalah satu kemungkinan untuk menerapkan ini. Ada lebih banyak platform yang memiliki set instruksi yang berbeda. Selain itu (dan yang lebih penting), catatan yang std::atomicharus mendukung semua operasi untuk semua tipe data yang mungkin , jadi bahkan jika Anda mendeklarasikan sepuluh juta byte struct, Anda dapat menggunakannya compare_exchange. Bahkan ketika pada CPU yang memiliki CAS, Anda tidak dapat melakukan CAS sepuluh juta byte, sehingga kompilator akan menghasilkan instruksi lain (mungkin kunci perolehan, diikuti oleh perbandingan dan pertukaran non-atom, diikuti dengan pelepasan kunci). Sekarang, pikirkan berapa banyak hal yang dapat terjadi saat menukar sepuluh juta byte. Jadi, meskipun kesalahan palsu mungkin sangat jarang terjadi untuk pertukaran 8 byte, itu mungkin lebih umum dalam kasus ini.

Jadi secara singkat, C ++ memberi Anda dua semantik, satu "upaya terbaik" satu ( weak) dan "Saya pasti akan melakukannya, tidak peduli berapa banyak hal buruk yang mungkin terjadi di antara" satu ( strong). Bagaimana ini diterapkan pada berbagai jenis data dan platform adalah topik yang sangat berbeda. Jangan mengikat model mental Anda dengan implementasi pada platform spesifik Anda; perpustakaan standar dirancang untuk bekerja dengan lebih banyak arsitektur daripada yang mungkin Anda sadari. Satu-satunya kesimpulan umum yang dapat kita tarik adalah bahwa menjamin kesuksesan biasanya lebih sulit (dan karenanya mungkin memerlukan kerja tambahan) daripada hanya mencoba dan menyisakan ruang untuk kemungkinan kegagalan.

Saya mencoba menjawab ini sendiri, setelah melalui berbagai sumber online (misalnya, yang ini dan yang ini ), Standar C ++ 11, serta jawaban yang diberikan di sini.

Pertanyaan terkait digabungkan (misalnya, " mengapa! Diharapkan? " Digabungkan dengan "mengapa menempatkan bandingkan_exchange_weak () dalam satu lingkaran? ") Dan jawaban diberikan sesuai dengan itu.

Mengapa bandingkan_exchange_weak () harus berada dalam satu lingkaran di hampir semua penggunaan?

Pola Khas A

Anda perlu mencapai pembaruan atom berdasarkan nilai dalam variabel atom. Kegagalan menunjukkan bahwa variabel tidak diperbarui dengan nilai yang kami inginkan dan kami ingin mencobanya kembali. Perhatikan bahwa kami tidak terlalu peduli apakah ini gagal karena penulisan bersamaan atau kegagalan palsu. Tapi kami sangat peduli bahwa kamilah yang membuat perubahan ini.

expected = current.load();
do desired = function(expected);
while (!current.compare_exchange_weak(expected, desired));

Contoh dunia nyata adalah untuk beberapa utas menambahkan elemen ke daftar tertaut tunggal secara bersamaan. Setiap utas memuat penunjuk kepala terlebih dahulu, mengalokasikan node baru dan menambahkan kepala ke node baru ini. Akhirnya, ia mencoba menukar simpul baru dengan kepala.

Contoh lain adalah mengimplementasikan mutex menggunakan std::atomic<bool>. Paling banyak satu utas dapat masuk ke bagian kritis pada satu waktu, bergantung pada utas mana yang pertama kali disetel currentke truedan keluar dari loop.

Pola Khas B

Ini sebenarnya pola yang disebutkan dalam buku Anthony. Berlawanan dengan pola A, Anda ingin variabel atom diperbarui satu kali, tetapi Anda tidak peduli siapa yang melakukannya. Selama belum diupdate, coba lagi. Ini biasanya digunakan dengan variabel boolean. Misalnya, Anda perlu mengimplementasikan pemicu agar mesin status dapat bergerak. Benang mana yang menarik pelatuknya tidak peduli.

expected = false;
// !expected: if expected is set to true by another thread, it's done!
// Otherwise, it fails spuriously and we should try again.
while (!current.compare_exchange_weak(expected, true) && !expected);

Perhatikan bahwa kita biasanya tidak dapat menggunakan pola ini untuk mengimplementasikan mutex. Jika tidak, beberapa utas mungkin berada di dalam bagian kritis pada saat yang bersamaan.

Karena itu, seharusnya jarang digunakan di compare_exchange_weak()luar loop. Sebaliknya, ada kasus dimana versi kuat sedang digunakan. Misalnya,

bool criticalSection_tryEnter(lock)
{
  bool flag = false;
  return lock.compare_exchange_strong(flag, true);
}

compare_exchange_weak tidak tepat di sini karena ketika kembali karena kegagalan palsu, kemungkinan besar belum ada yang menempati bagian kritis.

Benang Kelaparan?

Satu hal yang perlu disebutkan adalah apa yang terjadi jika kegagalan palsu terus terjadi sehingga membuat utas kelaparan? Secara teoritis hal itu bisa terjadi pada platform bila compare_exchange_XXX()diimplementasikan sebagai urutan instruksi (misalnya, LL / SC). Akses yang sering dari baris cache yang sama antara LL dan SC akan menghasilkan kegagalan palsu yang terus menerus. Contoh yang lebih realistis adalah karena penjadwalan yang bodoh di mana semua utas bersamaan disisipkan dengan cara berikut.

Time
 |  thread 1 (LL)
 |  thread 2 (LL)
 |  thread 1 (compare, SC), fails spuriously due to thread 2's LL
 |  thread 1 (LL)
 |  thread 2 (compare, SC), fails spuriously due to thread 1's LL
 |  thread 2 (LL)
 v  ..

Bisakah itu terjadi?

Untungnya, itu tidak akan terjadi selamanya, berkat apa yang dibutuhkan C ++ 11:

Implementasi harus memastikan bahwa operasi perbandingan-dan-pertukaran yang lemah tidak secara konsisten mengembalikan nilai salah kecuali jika objek atom memiliki nilai yang berbeda dari yang diharapkan atau ada modifikasi bersamaan pada objek atom.

Mengapa kita repot-repot menggunakan bandingkan_exchange_weak () dan menulis loop sendiri? Kami hanya dapat menggunakan bandingkan_exchange_strong ().

Tergantung.

Kasus 1: Saat keduanya perlu digunakan di dalam loop. C ++ 11 mengatakan:

Saat bandingkan-dan-tukar dalam satu putaran, versi yang lemah akan menghasilkan kinerja yang lebih baik pada beberapa platform.

Pada x86 (setidaknya saat ini. Mungkin akan menggunakan skema yang sama seperti LL / SC suatu hari nanti untuk kinerja ketika lebih banyak inti diperkenalkan), versi lemah dan kuat pada dasarnya sama karena keduanya bermuara pada satu instruksi cmpxchg. Pada beberapa platform lain di mana compare_exchange_XXX()tidak diimplementasikan secara atomik (di sini berarti tidak ada perangkat keras primitif yang ada), versi lemah di dalam loop dapat memenangkan pertarungan karena yang kuat harus menangani kegagalan palsu dan mencoba lagi sesuai dengan itu.

Tapi,

jarang, kita dapat memilih compare_exchange_strong()lebih compare_exchange_weak()bahkan dalam satu lingkaran. Misalnya, ketika ada banyak hal yang harus dilakukan antara variabel atom yang dimuat dan nilai baru yang dihitung dipertukarkan (lihat di function()atas). Jika variabel atom itu sendiri tidak sering berubah, kita tidak perlu mengulangi perhitungan yang mahal untuk setiap kegagalan palsu. Sebaliknya, kita mungkin berharap bahwa compare_exchange_strong()"menyerap" kegagalan tersebut dan kita hanya mengulangi perhitungan jika gagal karena perubahan nilai riil.

Kasus 2: Ketika hanya compare_exchange_weak() perlu digunakan di dalam loop. C ++ 11 juga mengatakan:

Ketika perbandingan-dan-pertukaran yang lemah akan membutuhkan loop dan yang kuat tidak akan, yang kuat lebih disukai.

Ini biasanya terjadi ketika Anda melakukan loop hanya untuk menghilangkan kegagalan palsu dari versi yang lemah. Anda mencoba lagi hingga pertukaran berhasil atau gagal karena penulisan bersamaan.

expected = false;
// !expected: if it fails spuriously, we should try again.
while (!current.compare_exchange_weak(expected, true) && !expected);

Paling banter, itu menciptakan kembali roda dan melakukan hal yang sama compare_exchange_strong(). Lebih buruk? Pendekatan ini gagal memanfaatkan sepenuhnya mesin yang menyediakan perangkat keras untuk membandingkan dan menukar yang tidak palsu .

Terakhir, jika Anda mengulang untuk hal lain (mis., Lihat "Pola Khas A" di atas), maka ada peluang bagus yang compare_exchange_strong()juga akan dimasukkan ke dalam perulangan, yang membawa kita kembali ke kasus sebelumnya.

Mengapa harus dalam satu lingkaran di hampir semua penggunaan ?

Karena jika Anda tidak mengulang dan gagal secara palsu program Anda tidak melakukan sesuatu yang berguna - Anda tidak memperbarui objek atom dan Anda tidak tahu berapa nilainya saat ini (Koreksi: lihat komentar di bawah dari Cameron). Jika panggilan tidak memberikan hasil yang berguna, apa gunanya melakukannya?

Apakah itu berarti kita akan mengulang ketika gagal karena kegagalan palsu?

Iya.

Jika itu masalahnya, mengapa kita repot-repot menggunakan compare_exchange_weak()dan menulis loop sendiri? Kita hanya dapat menggunakan bandingkan_exchange_strong () yang menurut saya harus menyingkirkan kegagalan palsu bagi kita. Apa kasus penggunaan umum dari bandingkan_exchange_weak ()?

Pada beberapa arsitektur compare_exchange_weaklebih efisien, dan kegagalan palsu seharusnya jarang terjadi, jadi dimungkinkan untuk menulis algoritme yang lebih efisien menggunakan bentuk yang lemah dan loop.

Secara umum, mungkin lebih baik menggunakan versi yang kuat daripada jika algoritme Anda tidak perlu melakukan loop, karena Anda tidak perlu khawatir tentang kegagalan palsu. Jika ia perlu melakukan perulangan bahkan untuk versi yang kuat (dan banyak algoritme memang perlu melakukan perulangan), maka menggunakan bentuk yang lemah mungkin lebih efisien pada beberapa platform.

Mengapa !expectedada dalam kondisi loop?

Nilainya bisa saja disetel trueoleh utas lain, jadi Anda tidak ingin terus mengulang mencoba menyetelnya.

Edit:

Tetapi seperti yang dianalisis di atas, dua versi dalam satu loop harus memberikan kinerja yang sama / serupa. Hal apa yang saya rindukan?

Tentunya jelas bahwa pada platform yang memungkinkan terjadinya kegagalan palsu, penerapannya compare_exchange_strongharus lebih rumit, untuk memeriksa kegagalan palsu dan coba lagi.

Bentuk lemah hanya kembali pada kegagalan palsu, tidak mencoba lagi.

Baiklah, jadi saya butuh fungsi yang melakukan pergeseran kiri atom. Prosesor saya tidak memiliki operasi asli untuk ini, dan pustaka standar tidak memiliki fungsi untuk itu, jadi sepertinya saya menulis milik saya sendiri. Ini dia:

void atomicLeftShift(std::atomic<int>* var, int shiftBy)
{
    do {
        int oldVal = std::atomic_load(var);
        int newVal = oldVal << shiftBy;
    } while(!std::compare_exchange_weak(oldVal, newVal));
}

Sekarang, ada dua alasan mengapa perulangan mungkin dijalankan lebih dari satu kali.

1. Orang lain mengubah variabel saat saya melakukan shift kiri. Hasil perhitungan saya tidak boleh diterapkan pada variabel atom, karena itu akan secara efektif menghapus tulisan orang lain.
2. CPU saya bersendawa dan CAS yang lemah ternyata gagal.

Sejujurnya saya tidak peduli yang mana. Pemindahan gigi ke kiri cukup cepat sehingga saya sebaiknya melakukannya lagi, bahkan jika kegagalannya palsu.

Yang kurang cepat, bagaimanapun, adalah kode tambahan yang dibutuhkan CAS yang kuat untuk membungkus CAS yang lemah agar menjadi kuat. Kode itu tidak banyak membantu ketika CAS yang lemah berhasil ... tetapi ketika gagal, CAS yang kuat perlu melakukan beberapa pekerjaan detektif untuk menentukan apakah itu Kasus 1 atau Kasus 2. Pekerjaan detektif itu berbentuk loop kedua, efektif di dalam lingkaran saya sendiri. Dua loop bersarang. Bayangkan guru algoritme Anda sedang menatap Anda saat ini.

Dan seperti yang saya sebutkan sebelumnya, saya tidak peduli dengan hasil pekerjaan detektif itu! Bagaimanapun, saya akan mengulangi CAS. Jadi, menggunakan CAS yang kuat tidak menghasilkan apa-apa bagi saya, dan membuat saya kehilangan efisiensi yang kecil namun dapat diukur.

Dengan kata lain, CAS lemah digunakan untuk mengimplementasikan operasi pembaruan atom. CAS yang kuat digunakan jika Anda peduli dengan hasil CAS.

Saya pikir sebagian besar jawaban di atas membahas "kegagalan palsu" sebagai beberapa jenis masalah, kinerja VS kebenaran pengorbanan.

Ini dapat dilihat sebagai versi lemah lebih cepat pada sebagian besar waktu, tetapi jika terjadi kegagalan palsu, itu menjadi lebih lambat. Dan versi yang kuat adalah versi yang tidak memiliki kemungkinan gagal palsu, tetapi hampir selalu lebih lambat.

Bagi saya, perbedaan utamanya adalah bagaimana kedua versi ini menangani masalah ABA:

versi lemah hanya akan berhasil jika tidak ada yang menyentuh garis cache antara memuat dan menyimpan, sehingga 100% mendeteksi masalah ABA.

versi kuat akan gagal hanya jika perbandingan gagal, jadi tidak akan mendeteksi masalah ABA tanpa tindakan ekstra.

Jadi, secara teori, jika Anda menggunakan versi lemah pada arsitektur berurutan lemah, Anda tidak memerlukan mekanisme pendeteksian ABA dan implementasinya akan jauh lebih sederhana, sehingga memberikan performa yang lebih baik.

Namun, pada x86 (arsitektur berurutan kuat), versi lemah dan versi kuat adalah sama, dan keduanya mengalami masalah ABA.

Jadi, jika Anda menulis algoritme lintas platform sepenuhnya, Anda tetap perlu mengatasi masalah ABA, jadi tidak ada manfaat kinerja dari penggunaan versi lemah, tetapi ada hukuman kinerja untuk menangani kegagalan palsu.

Kesimpulannya - untuk alasan portabilitas dan kinerja, versi yang kuat selalu merupakan pilihan yang lebih baik atau setara.

Versi lemah hanya bisa menjadi pilihan yang lebih baik jika memungkinkan Anda melewati tindakan pencegahan ABA sepenuhnya atau algoritme Anda tidak peduli dengan ABA.