Petunjuk dan kasus penggunaan
Implementasikan read-write lock yang thread-safe: beberapa reader dapat memegangnya secara bersamaan, sedangkan writer harus memegangnya secara eksklusif. Jelaskan kebijakan tunggu, aturan bangun, reentrancy, dan cara Anda mencegah kelaparan writer tanpa batas. Anda dapat menggunakan mutex dan variabel kondisi, tetapi bukan read-write lock bawaan.
Pertanyaan ini cocok untuk posisi backend, infrastruktur, dan konkurensi. Ini menguji invariansi sinkronisasi dan trade-off daripada bahasa pemrograman tertentu.
Apa yang dievaluasi oleh pewawancara
- Apakah Anda mendefinisikan invariansi terlebih dahulu: paling banyak satu writer aktif, dan tidak ada reader aktif saat writer memegang kunci.
- Apakah "keadilan" (fairness) menjadi aturan penerimaan yang dapat dieksekusi.
- Apakah Anda menangani spurious wakeups, jalur eksepsional, akuisisi rekursif, dan deadlock upgrade.
- Apakah Anda menyediakan kompleksitas, pengujian, dan batasan untuk menggunakan kembali pustaka standar produksi.
Klarifikasi sebelum menjawab
Konfirmasikan apakah akuisisi harus dapat diinterupsi atau memiliki batas waktu (timed), apakah suatu thread boleh masuk kembali (re-enter), apakah peningkatan (upgrade) dari baca ke tulis diperlukan, dan apakah keadilan berarti FIFO ketat atau progres writer pada akhirnya. Jika tidak ditentukan, usulkan desain minimal yang non-reentrant, non-upgradable, dengan preferensi writer, dan nyatakan batasan tersebut secara eksplisit.
Jawaban 30 detik
Beri nama state: activeReaders, activeWriter, dan waitingWriters. Reader hanya masuk jika tidak ada writer dan tidak ada writer dalam antrean; writer hanya masuk jika kedua hitungan aktif kosong. Lindungi setiap perubahan state dengan satu mutex, dan bangunkan satu writer atau kelompok reader saat pelepasan. Periksa kembali predikat dalam perulangan while setelah setiap variabel kondisi dibangunkan. Larang upgrade dari baca ke tulis kecuali API mendefinisikan protokol eksplisit.
Solusi langkah demi langkah
State dan invariansi
activeWriter adalah boolean, activeReaders adalah hitungan non-negatif, dan waitingWriters menghitung writer yang mengantre. Invariansi utamanya adalah activeWriter == true menyiratkan activeReaders == 0; seorang writer hanya dapat masuk jika keduanya kosong. Jumlah tunggu mengontrol kebijakan dan tidak berarti kunci sedang dipegang.
Akuisisi dan pelepasan
Reader menunggu !activeWriter && waitingWriters == 0; writer menunggu !activeWriter && activeReaders == 0. Periksa kembali setelah setiap pengembalian variabel kondisi untuk menangani spurious wakeups. Pada pelepasan writer, beri sinyal kepada satu writer jika ada yang mengantre; jika tidak, lakukan broadcast ke reader. Saat reader terakhir keluar, beri sinyal kepada writer.
~~~text readLock(): mutex.lock() while activeWriter or waitingWriters > 0: readersCondition.wait(mutex) activeReaders += 1 mutex.unlock()
writeLock(): mutex.lock() waitingWriters += 1 while activeWriter or activeReaders > 0: writersCondition.wait(mutex) waitingWriters -= 1 activeWriter = true mutex.unlock()
writeUnlock(): mutex.lock() activeWriter = false if waitingWriters > 0: writersCondition.signal() else: readersCondition.broadcast() mutex.unlock() ~~~
Keadilan dan throughput
| Kebijakan | Penerimaan reader | Keuntungan | Risiko |
|---|---|---|---|
| Preferensi writer | Tidak ada writer aktif dan waitingWriters == 0 | Membatasi kelaparan writer | Latensi reader meningkat saat terjadi lonjakan writer |
| Preferensi reader | Tidak ada writer aktif | Throughput baca tinggi | Writer dapat mengalami kelaparan |
| FIFO perkiraan | Diterima sesuai urutan antrean | Latensi lebih dapat diprediksi | Kompleksitas state dan antrean lebih tinggi |
Oracle mendokumentasikan bahwa mode non-fair dapat menunda reader atau writer tanpa batas waktu, sedangkan mode fair menggunakan kebijakan perkiraan urutan kedatangan dan biasanya mengorbankan throughput. Bedakan "tanpa kelaparan" dari FIFO ketat dalam wawancara.
Jawaban model
Saya akan mulai dengan implementasi non-reentrant dengan preferensi writer. Satu mutex melindungi semua penghitung. Reader bertambah hanya jika tidak ada writer yang aktif atau menunggu; writer menunggu sampai kedua hitungan aktif kosong. Setiap pengembalian variabel kondisi memeriksa kembali predikatnya dalam perulangan while. Saat pelepasan, beri sinyal ke writer jika ada yang mengantre, jika tidak, lakukan broadcast ke reader. Ini menjaga invariansi eksklusi dan mencegah aliran reader baru yang tak ada habisnya memotong antrean di depan writer.
Saya akan secara eksplisit menolak upgrade baca ke tulis: reader yang menunggu write lock dapat mencegah reader lain melepaskan kunci dan menyebabkan deadlock. Pemanggil harus melepaskan read lock dan bersaing kembali, atau menggunakan protokol upgrade terantre yang terpisah. Untuk interupsi, batas waktu, reentrancy, diagnostik, atau keadilan yang ketat, saya akan menggunakan primitif platform yang terdokumentasi dan menguji semantiknya daripada menyalin lock yang tidak lengkap ke dalam kode bisnis.
Kesalahan umum
- Mengganti
whiledenganif, memungkinkan spurious wakeup melewati predikat. - Mengabaikan writer yang mengantre dan menerima reader selamanya.
- Hanya membangunkan satu reader setelah pelepasan writer, atau melakukan broadcast tanpa syarat sehingga menciptakan thundering herd.
- Mengizinkan upgrade tanpa antrean upgrade, sehingga dua reader saling menunggu satu sama lain.
- Memperlakukan
tryLocksebagai jaminan keadilan. Oracle secara eksplisit mencatat bahwatryLockyang non-blocking dapat menyerobot (barge).
Pertanyaan lanjutan dan tanggapan
Bagaimana cara menguji invariansi?
Pertahankan snapshot pengujian atomik: pastikan (assert) nol reader saat writer masuk dan tidak ada writer saat reader masuk. Jalankan thread reader dan writer secara acak, dan catat urutan kejadian setiap kali asersi gagal.
Bagaimana cara menguji kelaparan writer?
Hasilkan reader secara terus-menerus saat satu writer sedang menunggu. Catat waktu dari antrean hingga penerimaan writer dan jumlah tunggu maksimum. Tujuannya adalah progres pada akhirnya, bukan janji milidetik tetap yang sembarangan.
Mengapa tidak menggunakan satu mutex biasa?
Mutex biasa lebih sederhana dan sering kali memiliki latensi yang lebih stabil. Read-write lock hanya dapat membantu jika operasi baca mendominasi dan critical section pembacaan cukup panjang untuk saling tumpang tindih. Pilihlah berdasarkan benchmark, bukan intuisi.
Bisakah dibuat reentrant?
Lacak thread writer dan hitungan kepemilikan, ditambah hitungan baca per-thread. Hal itu secara substansial memperluas aturan upgrade dan pelepasan. Jika reentrancy tidak diperlukan, melarangnya akan menjaga ruang state tetap lebih kecil.
Apa yang ditambahkan POSIX ke dalam diskusi ini?
POSIX mengekspos operasi read-lock dan write-lock terpisah dengan pengembalian kesalahan yang terdefinisi. Implementasi harus tetap menghormati aturan platform untuk prioritas dan perilaku rekursif; kebijakan kustom tidak boleh dihadirkan sebagai jaminan POSIX.
Kapan Anda harus berhenti menulisnya secara manual?
Ketika interupsi, batas waktu, diagnostik, reentrancy, atau portabilitas menjadi hal yang penting, prioritaskan primitif terverifikasi seperti Java ReentrantReadWriteLock atau POSIX pthread_rwlock_*, dan catat pilihan keadilan dalam peninjauan kode.