Gesaan dan kes penggunaan
Laksanakan kunci baca-tulis yang selamat-bebenang: berbilang pembaca boleh memegangnya secara serentak, manakala seorang penulis mesti memegangnya secara eksklusif. Terangkan dasar menunggu, peraturan membangunkan, kebolehan masuk semula, dan cara anda mencegah kebuluran penulis yang berterusan. Anda boleh menggunakan mutex dan pemboleh ubah keadaan, tetapi bukan kunci baca-tulis terbina dalam.
Soalan ini sesuai untuk peranan bahagian belakang (backend), infrastruktur, dan keserentakan (concurrency). Ia menguji invarians dan pertukaran kompromi (trade-offs) penyelarasan dan bukannya bahasa pengaturcaraan tertentu.
Perkara yang dinilai oleh penemu duga
- Sama ada anda mentakrifkan invarians terlebih dahulu: paling banyak satu penulis aktif, dan tiada pembaca aktif semasa penulis memegang kunci.
- Sama ada "keadilan" menjadi peraturan penerimaan yang boleh dilaksanakan.
- Sama ada anda mengendalikan pengejut palsu (spurious wakeups), laluan luar biasa, pemerolehan rekursif, dan kebuntuan peningkatan taraf (upgrade deadlocks).
- Sama ada anda menyediakan kerumitan, ujian, dan sempadan untuk menggunakan semula pustaka standard pengeluaran.
Penjelasan sebelum menjawab
Sahkan sama ada pemerolehan mesti boleh diganggu atau bermasa (timed), sama ada bebenang boleh masuk semula, sama ada peningkatan taraf baca-ke-tulis diperlukan, dan sama ada keadilan bermaksud FIFO ketat atau kemajuan penulis pada akhirnya. Jika tidak dinyatakan, cadangkan reka bentuk minimum bukan-reentrant, tidak boleh dinaik taraf, dengan keutamaan penulis dan nyatakan sempadan itu secara eksplisit.
Jawapan 30 saat
Namakan keadaan: activeReaders, activeWriter, dan waitingWriters. Pembaca hanya masuk apabila tiada penulis dan tiada penulis yang beratur; penulis hanya masuk apabila kedua-dua kiraan aktif adalah kosong. Lindungi setiap perubahan keadaan dengan satu mutex, dan bangunkan sama ada satu penulis atau kumpulan pembaca semasa pelepasan. Periksa semula predikat dalam gelung while selepas setiap pemboleh ubah keadaan terjaga. Larang peningkatan taraf baca-ke-tulis melainkan API mentakrifkan protokol yang jelas.
Penyelesaian langkah demi langkah
Keadaan dan invarians
activeWriter ialah boolean, activeReaders ialah kiraan bukan negatif, dan waitingWriters mengira penulis yang beratur. Invarians utama ialah activeWriter == true membayangkan activeReaders == 0; seorang penulis hanya boleh masuk apabila kedua-duanya kosong. Kiraan menunggu mengawal dasar dan tidak bermakna kunci sedang dipegang.
Pemerolehan dan pelepasan
Pembaca menunggu !activeWriter && waitingWriters == 0; penulis menunggu !activeWriter && activeReaders == 0. Periksa semula selepas setiap pengembalian pemboleh ubah keadaan untuk mengendalikan pengejut palsu. Semasa pelepasan penulis, beri isyarat kepada seorang penulis jika ada yang beratur; jika tidak, siarkan (broadcast) kepada pembaca. Apabila pembaca terakhir keluar, beri isyarat kepada seorang penulis.
~~~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 daya pemprosesan (throughput)
| Dasar | Kemasukan pembaca | Faedah | Risiko |
|---|---|---|---|
| Keutamaan penulis | Tiada penulis aktif dan waitingWriters == 0 | Membataskan kebuluran penulis | Kependaman pembaca meningkat semasa lonjakan penulis |
| Keutamaan pembaca | Tiada penulis aktif | Daya pemprosesan bacaan tinggi | Penulis boleh mengalami kebuluran |
| FIFO Anggaran | Terima mengikut susunan giliran | Kependaman lebih mudah diramal | Lebih banyak kerumitan keadaan dan giliran |
Oracle mendokumentasikan bahawa mod tidak adil (non-fair) boleh menangguhkan pembaca atau penulis selama-lamanya, manakala mod adil (fair) menggunakan dasar anggaran susunan ketibaan dan biasanya mengorbankan daya pemprosesan. Bezakan "tiada kebuluran" daripada FIFO ketat dalam temu duga.
Jawapan model
Saya akan mulakan dengan pelaksanaan bukan-reentrant dengan keutamaan penulis. Satu mutex melindungi semua pembilang. Pembaca bertambah hanya apabila tiada penulis aktif atau menunggu; penulis menunggu sehingga kedua-dua kiraan aktif kosong. Setiap pengembalian pemboleh ubah keadaan menyemak semula predikatnya dalam gelung while. Semasa pelepasan, beri isyarat kepada penulis apabila ada yang beratur, jika tidak siarkan kepada pembaca. Ini mengekalkan invarians pengecualian dan menghalang aliran pembaca baharu yang berterusan daripada memotong giliran di hadapan penulis.
Saya akan secara eksplisit menolak peningkatan taraf baca-ke-tulis: pembaca yang menunggu kunci tulis boleh menghalang pembaca lain daripada melepaskan kunci dan menyebabkan kebuntuan (deadlock). Pemanggil harus melepaskan kunci baca dan bersaing semula, atau menggunakan protokol peningkatan taraf beratur yang berasingan. Untuk gangguan, had masa tamat, kebolehan masuk semula, diagnostik, atau keadilan yang ketat, saya akan menggunakan primitif platform yang didokumentasikan dan menguji semantiknya daripada menyalin kunci yang tidak lengkap ke dalam kod perniagaan.
Kesilapan biasa
- Menggantikan
whiledenganif, membenarkan pengejut palsu memintas predikat. - Mengabaikan penulis yang beratur dan membenarkan pembaca masuk selama-lamanya.
- Membangunkan hanya seorang pembaca selepas pelepasan penulis, atau menyiarkan tanpa syarat dan mewujudkan fenomena thundering herd.
- Membenarkan peningkatan taraf tanpa giliran peningkatan, menyebabkan dua pembaca saling menunggu antara satu sama lain.
- Menganggap
tryLocksebagai jaminan keadilan. Oracle menyatakan secara jelas bahawatryLockbukan sekatan boleh memotong laluan (barge).
Soalan susulan dan respons
Bagaimanakah anda menguji invarians?
Kekalkan snapshot ujian atomik: sahkan (assert) sifar pembaca semasa kemasukan penulis dan tiada penulis semasa kemasukan pembaca. Jalankan bebenang pembaca dan penulis secara rawak, dan rekod urutan peristiwa setiap kali penegasan gagal.
Bagaimanakah anda menguji kebuluran penulis?
Jana pembaca secara berterusan semasa seorang penulis menunggu. Rekod masa dari beratur hingga kemasukan penulis dan kiraan menunggu maksimum. Matlamatnya ialah kemajuan pada akhirnya, bukan janji milisaat tetap yang sewenang-wenangnya.
Mengapa tidak menggunakan satu mutex biasa?
Mutex biasa adalah lebih ringkas dan selalunya mempunyai kependaman yang lebih stabil. Kunci baca-tulis hanya boleh membantu apabila bacaan mendominasi dan bahagian genting (critical section) bacaan cukup panjang untuk bertindih. Buat pilihan berdasarkan tanda aras (benchmark), bukan gerak hati.
Bolehkah ia menjadi reentrant?
Jejaki bebenang penulis dan kiraan pegangan, serta kiraan bacaan bagi setiap bebenang. Ini meluaskan peraturan peningkatan taraf dan pelepasan secara substansial. Jika kebolehan masuk semula tidak diperlukan, melarangnya dapat memastikan ruang keadaan kekal lebih kecil.
Apakah yang ditambah oleh POSIX kepada perbincangan ini?
POSIX mendedahkan operasi kunci baca dan kunci tulis yang berasingan dengan pulangan ralat yang ditakrifkan. Pelaksanaan masih mesti menghormati peraturan platform untuk keutamaan dan tingkah laku rekursif; dasar tersuai tidak boleh dibentangkan sebagai jaminan POSIX.
Bilakah anda harus berhenti menulisnya secara manual?
Apabila gangguan, had masa tamat, diagnostik, kebolehan masuk semula, atau kebolehalihan menjadi penting, utamakan primitif yang disahkan seperti ReentrantReadWriteLock Java atau pthread_rwlock_* POSIX, dan rekodkan pilihan keadilan dalam semakan.