Gesaan dan konteks
Laksanakan baris gilir berkapasiti tetap dengan satu penulis dan satu pembaca. push gagal apabila penuh dan pop gagal apabila kosong. Penemu duga mahu anda memanfaatkan kekangan SPSC, kemudian menerangkan indeks, keterlihatan, penggunaan semula slot, dan ujian sempadan dan bukannya menyalin baris gilir berbilang pengeluar.
Perkara yang diuji oleh penemu duga
Terasnya ialah invarians dan pertukaran (trade-off) konkurensi. Pengeluar mesti menulis hanya tail miliknya dan pengguna hanya head miliknya; setiap satu membaca indeks yang lain dan menggunakan operasi atomik untuk mewujudkan hubungan happens-before "tulis data, kemudian terbitkan indeks". cppreference mendokumenkan hubungan penyegerakan antara storan release dan muatan acquire; Java VarHandle begitu juga membezakan mod capaian acquire, release, dan volatile.
Soalan penjelasan untuk ditanya terlebih dahulu
Jelaskan sama ada elemen disalin atau dipindahkan, sama ada menulis ganti data lama dibenarkan, sama ada kapasiti dipilih semasa masa jalanan, sama ada API penyekat (blocking) diperlukan, sama ada terdapat tepat satu pengeluar dan pengguna, dan cara pemusnahan atau pengecualian dikendalikan. Jika kekangan bertukar menjadi MPSC atau MPMC, algoritma ini tidak boleh diguna semula tanpa perubahan.
Rangka kerja jawapan 30 saat
Katakan: "Saya mengekalkan pembilang head dan tail yang meningkat secara monoton dan memetakannya ke slot menggunakan modulo. Pengeluar membaca tail tempatannya dan head yang diterbitkan pengguna, memeriksa ruang, menulis ke slot, kemudian menerbitkan tail baharu dengan release. Pengguna memuatkan tail dengan acquire, memeriksa keadaan tidak kosong, memindahkan elemen, kemudian menerbitkan head baharu dengan release. Modulo mengendalikan kapasiti bukan kuasa dua; ujian merangkumi batas lilitan (wraparound), sempadan penuh/kosong, dan keterlihatan."
Analisis mendalam langkah demi langkah
1. Nyatakan invarians
Gunakan tail - head sebagai bilangan entri yang diduduki, dengan mengandaikan pembilang tanpa tanda (unsigned) yang cukup luas dengan batas lilitan semula jadi. Pengeluar tidak boleh membiarkan perbezaan melebihi kapasiti; pengguna tidak boleh membaca di luar head != tail. Setiap slot ditulis oleh pengeluar sekali sebelum ia digunakan.
2. Asingkan indeks tempatan dan kongsi
Pengeluar kerap mengemas kini tail, dan pengguna kerap mengemas kini head; masing-masing boleh menyimpan indeksnya sendiri dalam pemboleh ubah tempatan biasa. Membaca indeks pihak lain merentas bebenang menggunakan acquire, manakala menerbitkan indeks baharu sendiri menggunakan release, mengelakkan perlumbaan penulisan (write race) pada pembilang yang sama.
3. Terbitkan mengikut susunan tolak (push)
Pengeluar memuatkan head pengguna dan memeriksa tail - head < capacity. Ia menulis buffer[tail % capacity], kemudian menyimpan tail baharu dengan release-store. Pengguna hanya boleh membaca slot tersebut selepas muatan acquire memerhatikan tail baharu.
4. Gunakan semula slot mengikut susunan letus (pop)
Pengguna memuatkan tail yang diterbitkan oleh pengeluar dan memeriksa head != tail. Selepas memindahkan nilai slot, ia menyimpan head baharu dengan release-store. Pengeluar hanya boleh menggunakan semula slot tersebut selepas muatan acquire memerhatikan head baharu.
5. Kendalikan kapasiti dan batas lilitan (wraparound)
Kapasiti kuasa dua boleh menggunakan topeng bit, tetapi pelaksanaan mesti menyatakan andaian limpahan dan kelebaran bitnya. Bagi kapasiti biasa, % capacity lebih mudah untuk disahkan. Untuk pembilang yang berjalan lama, gunakan jenis unsigned yang luas dan bandingkan perbezaan dan bukannya memotong indeks menjadi integer kecil.
6. Tentukan kegagalan, jangka hayat, dan ujian
Kembalikan false apabila penuh dan empty apabila kosong; jangan lakukan spin. Jika penulisan elemen gagal, jangan terbitkan tail; pemindahan atau pemusnahan elemen memerlukan kekangan jenis atau peraturan pemulihan yang jelas. Uji kapasiti satu, kapasiti tambah satu, batas lilitan berulang, kelajuan pengeluar dan pengguna yang tidak sepadan, pinggir penuh/kosong, dan baki elemen semasa penutupan.
Contoh jawapan berkualiti tinggi
push(x):
t = tail.load(relaxed)
h = head.load(acquire)
if t - h == capacity: return false
buffer[t % capacity] = x
tail.store(t + 1, release)
return true
pop():
h = head.load(relaxed)
t = tail.load(acquire)
if h == t: return empty
x = move(buffer[h % capacity])
head.store(h + 1, release)
return xhead dan tail ialah pembilang atomik; pengeluar hanya menulis tail, dan pengguna hanya menulis head. Penulisan penimbal biasa berlaku sebelum penerbitan release bagi tail (happens-before), jadi muatan acquire pengguna menjadikan elemen tersebut kelihatan. Penerbitan release songsang bagi head membolehkan pengeluar menggunakan semula slot dengan selamat. Gunakan modulo untuk kapasiti bukan kuasa dua dan gunakan topeng hanya dengan andaian tambahan kuasa dua dan limpahan. Versi ini ialah SPSC, bukan baris gilir umum bagi pelbagai penulis atau pelbagai pembaca.
Kesilapan lazim dan penambahbaikan
- Kedua-dua bebenang menulis satu indeks: Nyatakan pemilikan SPSC dan beralih kepada algoritma khusus MPSC/MPMC apabila kekangan berubah.
- Menerbitkan sebelum menulis elemen: Tulis slot terlebih dahulu dan terbitkan indeks dengan release paling akhir.
- Menggunakan relaxed di semua tempat: Relaxed memberikan keatoman, bukan penerbitan data biasa; indeks rentas bebenang memerlukan acquire/release.
- Menganggap setiap kapasiti ialah kuasa dua: Gunakan modulo untuk kapasiti biasa dan bukannya topeng yang belum disahkan.
Soalan susulan dan respons
Mengapakah bacaan indeks tempatan boleh menggunakan relaxed?
Pengeluar hanya mengubah suai tail miliknya dan pengguna hanya head miliknya, jadi bacaan tempatan tidak menyegerak dengan bebenang lain. Membaca indeks pihak lain masih memerlukan acquire kerana ia juga memberikan keterlihatan.
Bilakah slot bernilai rujukan boleh digunakan semula?
Hanya selepas pengguna selesai memindahkan atau memusnahkan nilai dan menerbitkan head baharu dengan release. Pengeluar memuatkan nilai tersebut dengan acquire sebelum menulis ganti slot; melihat bahawa pengguna telah bermula adalah tidak mencukupi.
Bagaimanakah anda memperluaskannya kepada berbilang pengeluar?
Pelbagai pengeluar tidak boleh menulis tail yang sama secara langsung. Anda memerlukan tempahan jujukan berasaskan CAS, nombor jujukan setiap slot, atau kunci (lock), serta mesti membuktikan semula susunan tempahan, penerbitan, dan penggunaan semula slot. Jangan bentangkan kod SPSC sebagai baris gilir umum.
Bagaimanakah anda tahu bahawa pengoptimuman tersebut lebih pantas?
Bandingkan daya pemprosesan (throughput), kependaman p99, pertukaran konteks, dan ralat cache di bawah saiz elemen, afiniti bebenang, saiz kelompok, dan beban yang sama. Jika pengeluar sering mengejar pengguna, kapasiti, pembatasan kelompok (batching), atau tekanan balas (backpressure) mungkin lebih penting daripada melonggarkan susunan memori.