Perintah dan konteks
Anda memiliki stack lock-free dengan kontensi tinggi yang node-nodenya dihubungkan oleh pointer atomik. Sebuah thread membaca dan menghapus head menggunakan CAS sementara thread lain mungkin membebaskannya. Rancang reklamasi yang aman menggunakan model hazard_pointer C++26, yang memungkinkan pembaca konkuren tanpa lock global di sekitar stack.
Apa yang sedang diuji oleh pewawancara
Hazard pointer melindungi alamat yang sedang dibaca; pointer ini tidak membuat node tetap hidup selamanya. Pembaca memublikasikan hazard, memeriksa ulang apakah head atomik masih menunjuk node tersebut, dan baru setelah itu melakukan dereferensi. Node yang dihapus masuk ke retired list dan direklamasi hanya setelah memindai setiap hazard. Bahas acquire/release, pendaftaran dan keluar, biaya pemindaian, dan fakta bahwa ABA memerlukan perlindungan terpisah.
Pertanyaan klarifikasi untuk diajukan terlebih dahulu
Struktur data dan jaminan progres
Konfirmasikan apakah ini adalah Treiber stack, linked list, atau hash bucket, apakah diperlukan progres lock-free atau wait-free, dan apakah retired list lokal-thread (thread-local) dapat diterima.
Masa hidup thread
Tanyakan bagaimana thread memperoleh slot hazard dan bagaimana keluar membersihkan perlindungan serta mentransfer node yang telah di-retire. Thread yang crash tidak boleh meninggalkan rekaman yang tidak dapat direklamasi secara permanen.
Kebijakan ABA dan penandaan (tagging)
Tentukan apakah alamat dapat digunakan kembali dan apakah version counter atau tagged pointer tersedia. Hazard pointer mencegah pembebasan node yang dilindungi, tetapi tidak dengan sendirinya mencegah ABA membuat CAS berhasil secara keliru.
Kerangka jawaban 30 detik
"Pembaca memuat head secara atomik, memublikasikan alamat tersebut di slot hazard-nya, dan memuat head lagi; hanya nilai yang tidak berubah yang boleh didereferensi. Setelah CAS berhasil, node lama masuk ke retired list alih-alih dihapus. Pemindaian mengumpulkan semua alamat hazard dan hanya mereklamasi node yang telah di-retire yang tidak ada dalam set tersebut. Gunakan semantik acquire/release yang cocok, bersihkan slot sebelum thread keluar, dan tangani ABA dengan versi atau tag secara terpisah."
Jawaban mendalam langkah demi langkah
Langkah 1: Tentukan slot hazard dan retired list
Setiap thread yang mungkin mendereferensi node bersama memiliki slot hazard. Retired list menampung node yang dihapus dari struktur data tetapi belum aman untuk direklamasi. Pendaftaran dan kepemilikan slot harus eksplisit sehingga raw pointer sementara tidak dapat melewati perlindungan.
Langkah 2: Tetapkan jendela publish-and-validate
Muat head, publikasikan ke slot hazard dengan release atau pengurutan yang setara, lalu muat ulang head dengan acquire. Dereferensi field hanya jika kedua nilai cocok; jika tidak, bersihkan slot dan coba lagi. Ini menutup celah di mana thread lain dapat menghapus dan mereklamasi node tersebut.
Langkah 3: CAS dan penundaan reklamasi
Baca next dan lakukan compare-exchange pada head. Jika CAS gagal, bersihkan hazard dan coba lagi. Jika berhasil, tambahkan node lama ke retired list dan bersihkan slot hanya setelah pembaca tidak lagi memerlukan node tersebut. Tidak ada jalur yang boleh langsung menghapus node bersama.
Langkah 4: Pindai dan reklamasi
Pindai slot hazard setiap thread ke dalam set alamat yang dilindungi. Telusuri retired list dan hanya reklamasi node yang tidak ada dalam set tersebut. Sesuaikan ambang batas pemindaian dari jumlah slot dan panjang retired list. Protokol publish-and-validate dari pembaca yang patuh memastikan sebuah node tidak dapat menjadi tidak terlindungi sebelum pemindaian melihat hazard-nya.
Langkah 5: Tangani ABA dan pengurutan memori
Reklamasi yang ditunda mengurangi penggunaan kembali alamat tetapi tidak menghilangkan ABA. Jika sebuah node dapat dihapus dan dimasukkan kembali dengan cepat, gunakan version counter, tagged pointer, atau pertahanan ABA lainnya. Tentukan hubungan happens-before untuk head atomik, slot hazard, dan field node; operasi relaxed tidak boleh digunakan hanya demi kecepatan tanpa bukti.
Langkah 6: Tangani keluarnya thread dan pengecualian
Bersihkan hazard sebelum menghentikan pembacaan, lalu transfer node yang telah di-retire ke reclaimer aktif atau domain bersama. Registri memerlukan status pemilik yang dapat mendeteksi keluarnya thread dan menghindari slot yang ditinggalkan. Destruksi berjalan hanya setelah tidak ada pembaca yang dapat mencapai node; asumsi masa hidup objek biasa tidaklah cukup.
Langkah 7: Uji keamanan dan performa
Gunakan ThreadSanitizer, penjadwalan acak, dan uji stres untuk kegagalan CAS, pemindaian konkuren, keluarnya thread, penggunaan kembali, dan pengecualian. Tambahkan delayed-free sentinel untuk mendeteksi use-after-free. Ukur waktu pemindaian, puncak retired list, throughput, dan tail latency, lalu sesuaikan ambang batas batch alih-alih menambahkan lock global.
Contoh jawaban berkualitas tinggi
Saya akan memberikan setiap pembaca sebuah slot hazard. pop memuat head, memublikasikan hazard, memuat ulang head, dan baru setelah itu membaca next dan mencoba CAS; nilai yang berubah akan membersihkan slot dan mencoba lagi. Penghapusan yang berhasil akan memasukkan node ke retired list, dan pemindaian semua alamat hazard hanya mereklamasi node yang tidak dilindungi. Keluarnya thread akan membersihkan dan mentransfer slotnya. ABA menggunakan versi atau tagged pointer secara terpisah. Pengujian mencakup kontensi, kegagalan CAS, penggunaan kembali, keluarnya thread, dan pengecualian sambil memeriksa use-after-free dan biaya pemindaian.
Kesalahan umum
- Kesalahan: Mendereferensi head segera setelah pemuatan pertama. → Mengapa gagal: Node mungkin direklamasi sebelum perlindungan dipublikasikan. → Solusi: Publikasikan hazard dan validasi head lagi.
- Kesalahan: Menghapus setelah CAS berhasil. → Mengapa gagal: Pembaca lain mungkin masih berada di jendela perlindungannya. → Solusi: Retire terlebih dahulu, pindai, lalu reklamasi.
- Kesalahan: Mengasumsikan hazard pointer menyelesaikan ABA. → Mengapa gagal: Penundaan pembebasan tidak menjamin stabilitas versi logis. → Solusi: Tambahkan version counter atau tagged pointer.
- Kesalahan: Hanya menggunakan atomik relaxed. → Mengapa gagal: Publikasi dan validasi mungkin tidak terlihat dalam urutan yang diperlukan. → Solusi: Buktikan semantik acquire/release dan hubungan happens-before.
Pertanyaan lanjutan dan jawaban
Pertanyaan lanjutan 1: Mengapa memuat ulang head setelah memublikasikan?
Terdapat celah antara pemuatan pertama dan memublikasikan hazard di mana thread lain dapat menghapus dan mereklamasi node. Pemuatan ulang membuktikan bahwa node tersebut masih merupakan head saat ini di bawah perlindungan; jika tidak, coba lagi.
Pertanyaan lanjutan 2: Bisakah pemindaian melewatkan hazard yang dipublikasikan selama pemindaian?
Protokol mewajibkan pembaca untuk memublikasikan sebelum memvalidasi dan mencoba lagi saat validasi gagal. Dengan protokol tersebut, hanya node yang telah di-retire yang tidak ada dalam set terlindungi yang direklamasi; pembaca raw pointer yang tidak dilindungi berada di luar jaminan.
Pertanyaan lanjutan 3: Bisakah retired list tumbuh tanpa batas?
List dapat tumbuh ketika pembaca menahan hazard dalam waktu lama, thread berhenti, atau pemindaian terlalu jarang dilakukan. Tetapkan ambang batas, pantau puncaknya, bersihkan saat keluar, dan biarkan reclaimer memindai secara proaktif saat dibutuhkan.
Pertanyaan lanjutan 4: Kapan memilih hazard pointer dibandingkan epoch-based reclamation?
Hazard pointer secara tepat melindungi sejumlah kecil alamat dan cocok untuk jalur baca dinamis, tetapi pemindaian slot memakan CPU. Epoch reclamation melakukan batching secara efisien tetapi dapat tertahan oleh thread yang macet. Pilihlah berdasarkan jumlah pembaca, toleransi terhadap hambatan (stall), dan batas memori.