Petunjuk dan konteks
Implementasikan antrean berkapasitas tetap dengan satu writer dan satu reader. push gagal saat penuh dan pop gagal saat kosong. Pewawancara ingin Anda memanfaatkan batasan SPSC, lalu menjelaskan indeks, visibilitas, reklamasi, dan uji batas alih-alih menyalin antrean multi-producer.
Apa yang sedang diuji oleh pewawancara
Intinya adalah invarian konkurensi dan trade-off. Producer hanya boleh menulis tail miliknya dan consumer hanya head miliknya; masing-masing membaca indeks lainnya dan menggunakan atomic untuk membentuk hubungan happens-before "tulis data, lalu publikasikan indeks". cppreference mendokumentasikan hubungan sinkronisasi antara store release dan load acquire; VarHandle pada Java juga membedakan mode akses acquire, release, dan volatile.
Pertanyaan klarifikasi untuk diajukan terlebih dahulu
Klarifikasi apakah elemen disalin atau dipindahkan, apakah menimpa data lama diizinkan, apakah kapasitas ditentukan saat runtime, apakah API pemblokir (blocking) diperlukan, apakah benar-benar ada tepat satu producer dan satu consumer, serta bagaimana penghancuran (destruction) atau exception ditangani. Jika batasannya berubah menjadi MPSC atau MPMC, algoritma ini tidak dapat digunakan kembali tanpa perubahan.
Kerangka jawaban 30 detik
Katakan: "Saya mempertahankan penghitung head dan tail yang meningkat secara monoton dan memetakannya ke slot dengan modulo. Producer membaca tail lokalnya dan head yang dipublikasikan oleh consumer, memeriksa ruang, menulis ke slot, lalu memublikasikan tail baru dengan release. Consumer memuat tail dengan acquire, memeriksa kondisi tidak kosong, memindahkan elemen, lalu memublikasikan head baru dengan release. Modulo menangani kapasitas yang bukan pangkat dua; pengujian mencakup wraparound, batas penuh/kosong, dan visibilitas."
Analisis mendalam langkah demi langkah
1. Nyatakan invarian
Gunakan tail - head sebagai jumlah entri yang terisi, dengan asumsi penghitung unsigned yang cukup lebar dengan wraparound alami. Producer tidak boleh membiarkan perbedaannya melebihi kapasitas; consumer tidak boleh membaca di luar head != tail. Setiap slot ditulis oleh producer satu kali sebelum dikonsumsi.
2. Pisahkan indeks lokal dan bersama
Producer sering memperbarui tail, dan consumer sering memperbarui head; masing-masing dapat menyimpan indeksnya sendiri dalam variabel lokal biasa. Membaca indeks pihak lain antar-thread menggunakan acquire, sedangkan memublikasikan indeks baru milik sendiri menggunakan release, menghindari race penulisan pada penghitung yang sama.
3. Publikasikan dalam urutan push
Producer memuat head milik consumer dan memeriksa tail - head < capacity. Producer menulis buffer[tail % capacity], lalu menyimpan tail baru dengan release-store. Consumer hanya boleh membaca slot tersebut setelah load acquire mengamati tail baru.
4. Reklamasi dalam urutan pop
Consumer memuat tail yang dipublikasikan oleh producer dan memeriksa head != tail. Setelah memindahkan nilai slot, consumer menyimpan head baru dengan release-store. Producer hanya boleh menggunakan kembali slot tersebut setelah load acquire mengamati head baru.
5. Tangani kapasitas dan wraparound
Kapasitas bernilai pangkat dua dapat menggunakan bit mask, tetapi implementasi harus menyatakan asumsi overflow dan lebar bitnya. Untuk kapasitas biasa, % capacity lebih mudah diverifikasi. Untuk penghitung yang berjalan lama, gunakan tipe unsigned yang lebar dan bandingkan selisihnya daripada memotong indeks menjadi integer kecil.
6. Definisikan kegagalan, masa pakai (lifetime), dan pengujian
Kembalikan false saat penuh dan empty saat kosong; jangan melakukan spinning. Jika penulisan elemen gagal, jangan publikasikan tail; pemindahan atau penghancuran elemen memerlukan batasan tipe eksplisit atau aturan pemulihan. Uji kapasitas satu, kapasitas plus satu, wraparound berulang, perbedaan kecepatan producer dan consumer, batas penuh/kosong, dan elemen yang tersisa saat shutdown.
Contoh jawaban berkualitas 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 adalah penghitung atomic; producer hanya menulis tail, dan consumer hanya menulis head. Penulisan buffer biasa terjadi sebelum (happens-before) publikasi release dari tail, sehingga load acquire consumer membuat elemen tersebut terlihat. Release terbalik dari head memungkinkan producer menggunakan kembali slot dengan aman. Gunakan modulo untuk kapasitas bukan pangkat dua dan gunakan mask hanya dengan asumsi tambahan pangkat dua dan overflow. Versi ini adalah SPSC, bukan antrean umum untuk banyak writer atau banyak reader.
Kesalahan umum dan perbaikan
- Kedua thread menulis satu indeks: Nyatakan kepemilikan SPSC dan beralihlah ke algoritma khusus MPSC/MPMC ketika batasan berubah.
- Memublikasikan sebelum menulis elemen: Tulis slot terlebih dahulu dan publikasikan indeks dengan release paling akhir.
- Menggunakan relaxed di semua tempat: Relaxed memberikan atomisitas, bukan publikasi data biasa; indeks lintas-thread memerlukan acquire/release.
- Mengasumsikan setiap kapasitas adalah pangkat dua: Gunakan modulo untuk kapasitas biasa alih-alih mask yang belum terverifikasi.
Pertanyaan lanjutan dan tanggapan
Mengapa pembacaan indeks lokal dapat menggunakan relaxed?
Producer hanya memodifikasi tail miliknya dan consumer hanya head miliknya, sehingga pembacaan lokal tidak perlu disinkronkan dengan thread lain. Membaca indeks pihak lain tetap memerlukan acquire karena hal itu juga memberikan visibilitas.
Kapan slot bernilai referensi dapat digunakan kembali?
Hanya setelah consumer selesai memindahkan atau menghancurkan nilai tersebut dan memublikasikan head baru dengan release. Producer memuat nilai tersebut dengan acquire sebelum menimpa slot; melihat bahwa consumer telah mulai saja tidak cukup.
Bagaimana Anda memperluasnya untuk banyak producer?
Banyak producer tidak dapat menulis tail yang sama secara langsung. Anda memerlukan reservasi urutan berbasis CAS, nomor urut per-slot, atau lock, dan harus membuktikan kembali urutan reservasi, publikasi, serta reklamasi. Jangan menyajikan kode SPSC sebagai antrean umum.
Bagaimana Anda tahu bahwa optimasi tersebut lebih cepat?
Bandingkan throughput, latensi p99, context switch, dan cache miss di bawah ukuran elemen, afinitas thread, ukuran batch, dan beban yang sama. Jika producer sering mengejar consumer, kapasitas, batching, atau backpressure mungkin lebih berpengaruh daripada melemahkan memory ordering.