Prompt dan konteks
Pelbagai pengeluar (producers) dan pengguna (consumers) berkongsi giliran dalam memori berkapasiti tetap. Pengeluar tidak boleh menulis ganti item yang belum digunakan, dan pengguna tidak boleh membaca item yang belum diterbitkan. Laluan pantas harus mengelakkan mutex, manakala keadaan penuh dan kosong boleh menunggu. Reka susun atur slot, kedudukan enqueue/dequeue, aturan memori, dan tingkah laku penutupan.
Perkara yang dinilai oleh penemu duga
- Sama ada anda menggunakan kedudukan monotonik dan jujukan per slot untuk membezakan keadaan kosong, ditempah, diterbitkan dan digunakan.
- Sama ada CAS dan acquire/release memaparkan data muatan (payload) bukan atomik dengan betul.
- Sama ada anda mengendalikan kapasiti bukan kuasa dua (non-power-of-two), perebutan pengeluar dan pengguna, serta perkongsian palsu (false sharing).
- Sama ada anda menerangkan menunggu, tamat masa (timeouts), penutupan, penebusgunaan (reclamation), dan sempadan ABA.
Soalan penjelasan
- Adakah elemen merupakan objek bersaiz tetap, objek boleh alih, atau penunjuk dengan pemilikan luaran?
- Patutkah keadaan penuh dan kosong kembali serta-merta, menyekat (block), atau tamat masa?
- Selepas
close, bolehkah pengguna mengosongkan (drain) elemen yang telah dimasukkan ke dalam giliran? - Adakah masa jalanan (runtime) menyediakan
atomic::waitdannotifyC++20? - Adakah giliran tersebut bersifat setempat pada proses atau dikongsi merentas proses?
Jawapan 30 saat
Saya akan mengekalkan kedudukan enqueue dan dequeue yang meningkat secara monotonik, dengan jujukan yang terikat pada kedudukan mutlak dalam setiap slot. Pengeluar menempah kedudukan menggunakan CAS, menulis payload bukan atomik, dan melakukan release-store bagi jujukan yang diterbitkan. Pengguna melakukan acquire-load pada jujukan tersebut, membaca payload, kemudian melakukan release-store bagi jujukan boleh tulis seterusnya. Perbezaan jujukan membezakan keadaan penuh dan kosong. Laluan pantas yang gagal akan menunggu dengan atomic::wait atau backoff terhad, dan keadaan penutupan adalah sebahagian daripada kontrak hasil.
Jawapan mendalam
Langkah 1: Reka bentuk slot dan kedudukan
Untuk kapasiti N, kekalkan enqueuePos dan dequeuePos yang monotonik; petakan kedudukan kepada slot menggunakan modulo. Setiap slot mengandungi sequence dan payload. Jujukan ini membawa pusingan (round) slot, supaya indeks sahaja tidak akan tersilap menganggap data lama sebagai item baharu. Gunakan aritmetik modulo yang selamat untuk kapasiti bukan kuasa dua dan bukannya topeng bit (bit mask).
Langkah 2: Tempah kedudukan pengeluar
Pengeluar membaca jujukan untuk kedudukan calonnya. Jika ia bersamaan dengan nilai boleh tulis yang dijangkakan, slot tersebut tersedia dan pengeluar bersaing untuk enqueuePos dengan CAS. Jika CAS gagal, muat semula dan cuba lagi. Jika jujukan berada di belakang nilai yang dijangkakan, giliran mungkin penuh; kembalikan status penuh, tunggu, atau tamat masa daripada terus mara ke kedudukan masa hadapan.
Langkah 3: Terbitkan payload
Selepas menempah kedudukan, pengeluar secara eksklusif memiliki slot tersebut dan menulis payload. Ia kemudian melakukan release-store bagi jujukan yang bermaksud "diterbitkan pada kedudukan ini." Pengguna mesti melakukan acquire-load pada jujukan sebelum membaca payload bukan atomik; indeks atomik sahaja tidak membuktikan bahawa pemulaan objek dapat dilihat.
Langkah 4: Guna dan lepaskan
Pengguna juga menempah dequeuePos dengan CAS secara serupa. Ia hanya boleh membaca apabila jujukan slot bersamaan dengan nilai terbitan yang dijangkakan. Selepas membaca, ia melakukan release-store bagi jujukan untuk pusingan boleh tulis seterusnya. Pengeluar seterusnya melakukan acquire-load pada nilai tersebut sebelum menulis ganti slot.
Langkah 5: Tentukan aturan memori dan perkongsian palsu
CAS kedudukan menyediakan kemas kini indeks atomik; release/acquire pada jujukan penerbitan dan pelepasan mencipta hubungan happens-before bagi payload. Operasi relaxed sahaja boleh mendedahkan data yang belum diterbitkan. Letakkan kedudukan pengeluar dan pengguna, serta jujukan yang kerap diakses, pada cache line yang berasingan untuk mengurangkan pembatalan penulisan (write invalidation).
Langkah 6: Kendalikan menunggu dan penutupan
Apabila laluan pantas tidak dapat diteruskan, tunggu pada kedudukan atau jujukan dengan atomic::wait; enqueue atau dequeue yang berjaya memanggil notify_one atau notify_all. Gelung mesti mengendalikan tamat masa dan spurious wakeups. Terbitkan penutupan secara atomik: pengeluar menolak item baharu, manakala pengguna sama ada mengosongkan slot yang diterbitkan atau mengembalikan status ditutup mengikut kontrak.
Langkah 7: Uji perebutan dan kitaran hayat
Uji kapasiti satu, kapasiti bukan kuasa dua, bilangan pengeluar atau pengguna melebihi slot, selang-seli penuh/kosong yang panjang, dan kelewatan rawak. Gunakan nombor jujukan untuk menyemak tiada kehilangan, tiada duplikasi, skop FIFO, dan pengosongan semasa penutupan. Jalankan ThreadSanitizer dan ujian tekanan untuk perlumbaan data (data races). Jika payload ialah penunjuk, nyatakan pemilikan dan masa penebusgunaan.
Jawapan model
Setiap slot menyimpan payload dan jujukan monotonik; giliran menyimpan kedudukan enqueue dan dequeue yang monotonik. Pengeluar hanya menempah dengan CAS apabila jujukan bersamaan dengan nilai boleh tulis semasa, menulis payload, kemudian melakukan release-publish pada jujukan. Pengguna melakukan acquire-observe pada nilai yang diterbitkan, membaca payload, dan melakukan release-store pada nilai boleh tulis seterusnya. Pusingan jujukan membezakan slot kosong, penuh dan diguna semula; modulo mengendalikan kapasiti bukan kuasa dua. Cache line berasingan mengurangkan perkongsian palsu. Laluan pantas yang gagal menggunakan atomic::wait dengan gelung tamat masa dan spurious-wakeup. Penutupan menolak pengeluar baharu dan mengosongkan item yang diterbitkan mengikut kontrak. Ujian tekanan, ThreadSanitizer, dan semakan jujukan merangkumi perebutan dan kitaran hayat.
Kesilapan lazim
- Hanya menggunakan indeks head dan tail, yang tidak dapat membezakan pusingan slot dan data lapuk.
- Membenarkan pengguna membaca selepas pengeluar menempah tetapi sebelum ia menerbitkan payload.
- Menggunakan penerbitan relaxed tanpa keterlihatan acquire/release untuk payload.
- Terus menempah kedudukan selepas giliran penuh dan menulis ganti data yang belum digunakan.
- Mengabaikan spurious wakeups, tamat masa, dan penutupan dalam gelung
atomic::wait. - Melupakan kapasiti bukan kuasa dua, perkongsian palsu, atau penebusgunaan penunjuk.
Soalan susulan
Soalan susulan 1: Mengapakah setiap slot memerlukan jujukan?
Indeks diguna semula merentas pusingan. Jujukan mengikat slot pada kedudukan mutlak dan membezakan keadaan boleh tulis, diterbitkan, dan pusingan seterusnya, menghalang nilai lapuk daripada diterima.
Soalan susulan 2: Mengapa tidak menjadikan payload sahaja sebagai atomik?
Payload boleh menjadi objek komposit; indeks atomik tidak bermakna pemulaan objek dapat dilihat. Penerbitan release dan pemerhatian acquire mewujudkan keterlihatan bagi keseluruhan payload bukan atomik.
Soalan susulan 3: Berapa lamakah CAS yang gagal perlu berputar (spin)?
Tiada nilai sejagat. Putar seketika untuk perebutan singkat, kemudian beralih (yield) atau tunggu pemberitahuan. Selaraskan dasar dengan kiraan teras, kapasiti, dan ujian beban sasaran kependaman.
Soalan susulan 4: Bagaimanakah anda menutup giliran tanpa kehilangan item?
Hentikan pengeluar baharu terlebih dahulu, kemudian lakukan acquire-observe dan kosongkan slot yang diterbitkan. Pengguna mengembalikan status ditutup hanya selepas kedudukan bertemu dan tiada lagi pengeluar yang memegang slot yang ditempah.
Soalan susulan 5: Adakah ini sentiasa lock-free?
Laluan pantas mengelakkan mutex, tetapi atomic::wait boleh menyekat thread masa jalanan. Terangkan ia secara tepat sebagai struktur data lock-free dengan pilihan menunggu menyekat (blocking waits) dan bukannya menjanjikan setiap laluan adalah lock-free.
Soalan susulan 6: Bagaimanakah anda menguji risiko ABA?
Gunakan kedudukan monotonik dan jujukan pusingan dalam setiap slot, kemudian lakukan ujian tekanan wraparound, thread tertangguh, dan CAS berulang. Pemerhatian lama tidak boleh memperoleh kelayakan semula selepas slot telah mara ke pusingan baharu.