Petunjuk dan konteks
Implementasikan semaphore asinkron untuk pool koneksi atau eksekutor tugas. Ini dimulai dengan kapasitas N; acquire() mengantre ketika tidak ada izin yang tersedia, dan release() mengembalikan satu izin. Penunggu dapat mengalami batas waktu (timeout) atau dibatalkan. Pembatalan tidak boleh meninggalkan entri antrean hantu atau mencegah penunggu lain untuk melanjutkan proses. Definisikan pelepasan duplikat, perilaku penutupan (close), dan keadilan (fairness).
Ini cocok untuk wawancara konkurensi, runtime, dan infrastruktur backend. API Semaphore milik Oracle mendefinisikan izin, pemilihan FIFO adil yang opsional, dan perolehan yang dapat diinterupsi. Dokumentasi asyncio milik Python menjelaskan penghitung yang berkurang saat acquire dan bertambah saat release, serta membedakan semaphore biasa dari bounded semaphore. Diskusi wawancara publik mencantumkan counting semaphore dan batas konkurensi sebagai topik wawancara sistem operasi. Sumber-sumber ini mendukung keterwakilan topik, tetapi tidak menetapkan petunjuk atau frekuensi wawancara yang pasti pada perusahaan tertentu. Kategorinya adalah coding karena keahlian intinya adalah invarian state, pembersihan antrean, race condition pembatalan, dan implementasi konkuren yang dapat diverifikasi.
Apa yang dievaluasi pewawancara
Pertama, apakah kandidat mendefinisikan kepemilikan izin? Pemanggilan acquire yang berhasil harus membuat token yang dapat dikembalikan tepat satu kali. Permintaan yang dibatalkan atau kehabisan batas waktu tidak memiliki token dan tidak boleh memanggil release.
Kedua, apakah keadilannya nyata? Setelah antrean tidak kosong, pelepasan baru tidak boleh membiarkan fast path berikutnya melewati elemen terdepan (head); jika tidak, beban tinggi dapat menyebabkan penunggu lama mengalami starvation. Keadilan FIFO memerlukan pemeriksaan antrean, penetapan izin, dan membangunkan penunggu dalam satu batasan sinkronisasi.
Ketiga, dapatkah mereka menangani perebutan (race condition) pembatalan dengan sinyal bangun (wakeup)? Seorang penunggu mungkin telah dipilih oleh release lalu mengalami timeout, atau mungkin mengalami timeout sebelum release menghapusnya. Kedua jalur harus bersaing pada satu transisi state dan menyelesaikan penunggu paling banyak satu kali.
Terakhir, apakah pengujian memeriksa batas konkurensi, urutan FIFO, pembersihan batas waktu, kemajuan setelah pembatalan, pelepasan duplikat, penutupan, dan kegagalan tugas alih-alih hanya menguji acquire/release sekuensial?
Pertanyaan klarifikasi yang perlu diajukan terlebih dahulu
- Apakah keadilan berupa FIFO ketat atau upaya terbaik (best effort)? FIFO ketat menghindari starvation tetapi dapat mengorbankan throughput.
- Apa yang dikembalikan oleh acquire? Token pelepasan atau lease (sewa) mengikat kepemilikan pada satu perolehan yang berhasil dan mengurangi pelepasan yang tidak disengaja.
- Bagaimana jika pembatalan terjadi setelah izin ditetapkan? Tentukan prioritas penyelesaian; setelah promise terselesaikan, pemanggil memiliki lease dan pembatalan hanya memengaruhi pekerjaan setelahnya.
- Apakah memanggil release lebih banyak daripada acquire merupakan error? Bounded semaphore harus menolak atau melaporkannya; menambah hitungan secara diam-diam melanggar kapasitas.
- Bagaimana cara close menyelesaikan penunggu? Close menolak permintaan baru dan mengakhiri penunggu dalam antrean dengan error Closed yang jelas; lease yang sedang dipegang masih dapat dilepaskan dengan aman.
Kerangka jawaban 30 detik
"Saya mempertahankan available, antrean penunggu FIFO, dan status tertutup, dengan setiap mutasi berada dalam satu critical section. Acquire dapat mengambil fast path hanya jika antrean kosong; begitu ada penunggu, pemanggil berikutnya akan mengantre. Release mencari penunggu aktif pertama, mentransfer satu izin, dan menyelesaikannya satu kali; hanya jika tidak ada penunggu aktif yang tersisa, ia akan menambah available. Setiap penunggu memiliki state pembatalan dan penyelesaian one-shot. Batas waktu dan release bersaing pada state yang sama. Acquire yang berhasil mengembalikan lease yang dapat dilepaskan satu kali. Pengujian memaksa skenario FIFO, pembatalan dan pelepasan pada batasan yang sama, pemulihan izin setelah batas waktu, pelepasan duplikat, penutupan, dan batas batas konkurensi."
Jawaban mendalam
1. Nyatakan invarian inti
Untuk kapasitas N, pertahankan available + held + reserved = N. available dapat langsung ditetapkan, held dimiliki oleh pemanggil melalui lease, dan reserved telah berpindah dari available ke penunggu terpilih yang callback-nya belum selesai dieksekusi.
Setiap penunggu memiliki tepat satu state terminal: pending, fulfilled, atau cancelled. Penunggu yang dibatalkan tidak memiliki izin; penunggu yang terpenuhi harus menghasilkan sebuah lease. Menutup semaphore tidak mengambil kembali lease yang sedang dipegang, tetapi mencegah perolehan baru.
2. Fast path dan antrean yang adil
Ketika waiters kosong dan semaphore terbuka, acquire dapat mengonsumsi available secara langsung. Ketika antrean tidak kosong, bahkan jika available > 0, pemanggil baru tetap mengantre; jika tidak, ia akan mendahului pemanggil yang lebih lama. Acquire dan release harus memeriksa antrean di bawah batasan sinkronisasi yang sama.
Node antrean menyimpan promise penunggu, state pembatalan, handle timer, dan fungsi penyelesaian one-shot. Hapus node yang telah selesai atau dibatalkan, atau pertahankan tombstone yang dilewati secara lazy oleh release di posisi terdepan. Kedua strategi memerlukan bukti bahwa penunggu aktif tidak akan tertahan secara permanen di belakang node yang tidak valid.
3. Transfer izin dalam release
Release pertama-tama memverifikasi bahwa lease belum pernah dilepaskan sebelumnya, kemudian memberikan izin kepada penunggu aktif pertama. Izin berubah dari held menjadi reserved dan eksekusi penyelesaian penunggu dipanggil; jangan menambah available lalu mencari secara asinkron, karena pemanggilan acquire baru dapat memotong antrean.
Jika elemen terdepan dibatalkan, lewati dan bersihkan node tersebut, lalu lanjutkan ke penunggu berikutnya. Hanya jika tidak ada penunggu aktif yang tersisa barulah available += 1. Bounded semaphore menolak pelepasan yang melebihi N agar bug pada pemanggil tidak dapat menyembunyikan kebocoran atau pengembalian ganda.
4. Race condition antara pembatalan dan batas waktu
Pembatalan dan release keduanya dapat mencoba menyelesaikan penunggu yang sama. Gunakan CAS one-shot, pemeriksaan state di dalam lock, atau mekanisme setara sehingga hanya satu yang menang. Jika pembatalan menang, hapus penunggu tanpa mengubah available karena ia tidak pernah memiliki izin. Jika release telah memesan izin, pembatalan tidak boleh mengembalikan izin tersebut sekaligus membiarkan release menyelesaikan penunggu yang sama.
Aturan sederhananya adalah release menandai penunggu sebagai fulfilled di dalam critical section sebelum menyelesaikannya. Setelah fulfilled, batas waktu hanya dapat mencatat bahwa pemanggil mengabaikan pekerjaan selanjutnya; pemanggil tetap melepaskan lease yang diterimanya. Desain yang lebih rumit dapat mengklaim kembali reservasi yang belum terkirim, tetapi reklamasi tersebut harus berada dalam state machine yang sama dan bukan disimpulkan dari promise yang ditolak.
5. Lease dan pelepasan duplikat
Kembalikan lease dengan flag released. lease.release() dapat bertransisi dari false ke true tepat satu kali. Pemanggilan duplikat mengembalikan hasil idempoten atau error yang jelas; ini tidak boleh menambahkan dua izin. Mengekspos metode release tanpa pemilik ke sembarang pemanggil akan menghilangkan asosiasi kepemilikan, kecuali jika API secara eksplisit menggunakan model penghitungan milik pemanggil.
6. Close, kegagalan, dan backpressure
Setelah close, tolak acquire baru dan selesaikan penunggu dalam antrean dengan error Closed. Tugas yang memegang lease dapat selesai dan melepaskannya; release tidak boleh membuang izin hanya karena semaphore ditutup, atau hitungan held akan menjadi tidak konsisten. Kegagalan tugas tetap melepaskan izin di finally.
Semaphore membatasi konkurensi, bukan panjang antrean. Antrean penunggu yang tidak terbatas mengubah backpressure menjadi pembengkakan memori. Kode produksi harus menetapkan jumlah tunggu maksimum, batas waktu, atau kebijakan penolakan, serta mencatat durasi tunggu, tingkat pembatalan, dan kedalaman antrean.
7. Kendalikan race condition dengan scheduler
Jangan membuktikan race condition menggunakan jeda waktu (sleep) nyata. Gunakan jam manual dan scheduler yang dapat dikendalikan untuk menjeda saat pengantrean, saat release memilih penunggu, dan saat callback batas waktu telah masuk antrean tetapi belum dieksekusi. Pada setiap langkah, lakukan assert terhadap available, held, jumlah penunggu aktif, dan kepemilikan lease.
Cakup inisialisasi N=0 yang tidak valid, FIFO ketat dengan N=1, izin ganda, pembatalan pada elemen terdepan dan penunggu di tengah, batas waktu dan pelepasan pada batasan yang sama, pelepasan duplikat, acquire sebelum dan sesudah penutupan, kegagalan tugas, dan ketiadaan starvation untuk pemanggil yang menunggu lama.
Contoh jawaban berkualitas tinggi
"Saya mengenkapsulasi kepemilikan izin di dalam sebuah lease. Semaphore menyimpan available, penunggu FIFO, dan status penutupan, serta semua transisi berbagi satu batasan sinkronisasi yang sama. Acquire mengambil fast path hanya ketika antrean kosong; begitu ada penunggu, pemanggilan berikutnya akan masuk antrean.
Release memverifikasi bahwa lease dilepaskan tepat satu kali, menemukan penunggu aktif pertama, mentransfer held ke reservasi penunggu tersebut, dan menyelesaikannya satu kali. Ia melewati dan membersihkan elemen terdepan yang dibatalkan; hanya saat tidak ada penunggu aktif barulah ia menambah available. Pembatalan dan batas waktu bersaing dengan release pada state penunggu yang sama, dan transisi one-shot memilih pemenangnya. Pembatalan sebelum acquire tidak memiliki izin, sedangkan acquire yang selesai memberi pemanggil sebuah lease yang tidak dapat digantikan oleh pembatalan.
Close menolak permintaan baru dan menyelesaikan penunggu dalam antrean, sementara lease yang sedang dipegang tetap dapat dilepaskan. Pengujian menggunakan jam manual dan scheduler untuk memaksa FIFO, pembatalan di depan dan di tengah, batas waktu dan pelepasan bersamaan, pelepasan duplikat, pembersihan finally setelah kegagalan, dan batas kapasitas konkurensi. Invarian penghitung membuktikan bahwa tidak ada izin yang hilang atau dibuat secara ilegal."
Kesalahan umum
- Mengambil fast path saat antrean tidak kosong → pemanggil baru melewati pemanggil lama dan menyebabkan starvation → antrekan setiap pemanggil selama penunggu masih ada.
- Menambah available saat penunggu dibatalkan → release mungkin telah memesan izinnya → buat pembatalan dan release bersaing pada satu state one-shot.
- Mengekspos release tanpa kepemilikan → pemanggilan duplikat menciptakan izin baru → kembalikan lease yang hanya dapat dilepaskan satu kali.
- Menambah available sebelum membangunkan elemen terdepan → pemanggil baru dapat memotong antrean → transfer secara langsung di bawah critical section yang sama.
- Memperlakukan batas waktu sebagai pembatalan lease yang telah diberikan → tugas mungkin masih berjalan → bedakan pembatalan saat menunggu dari izin yang telah diperoleh.
- Membiarkan antrean tidak terbatas → batas konkurensi berubah menjadi kebocoran memori → tetapkan batas antrean, batas waktu, atau kebijakan penolakan.
- Hanya menguji pemanggilan sekuensial → race condition pembatalan dan pelepasan duplikat terlewatkan → paksa interleaving dengan scheduler yang dapat dikendalikan.
- Membuang izin yang dipegang saat penutupan → penghitungan sumber daya tidak dapat konvergen → biarkan lease yang dipegang dilepaskan dalam finally.
Pertanyaan lanjutan dan jawaban
Apakah keadilan FIFO selalu lebih baik?
Tidak. FIFO mencegah starvation dan mudah dijelaskan, tetapi elemen terdepan yang berjalan lama atau hampir kehabisan batas waktu dapat menyebabkan head-of-line blocking. Implementasi yang mengutamakan throughput dapat mengizinkan fast path yang tidak adil, tetapi starvation, waktu tunggu maksimum, dan prioritas harus menjadi pilihan kontrak yang eksplisit, bukan asumsi tersirat.
Bagaimana cara Anda memperoleh beberapa izin sekaligus?
Catat jumlah yang diminta oleh setiap penunggu dan penuhi hanya ketika available cukup besar. FIFO ketat dapat menyebabkan permintaan satu izin di belakang elemen terdepan yang meminta multi-izin harus menunggu; mengizinkan bypass akan mengorbankan keadilan. Pilih satu kebijakan dan hitung izin yang dipesan, bukan objek penunggunya, dalam invarian.
Bagaimana jika suatu tugas dibatalkan di tengah-tengah pekerjaannya?
Semaphore memiliki izin, bukan interupsi tugas. Pemanggil harus menghentikan pekerjaan saat dibatalkan dan melepaskan lease di blok finally; jika pekerjaan tidak dapat diinterupsi, ia harus selesai sebelum melepaskan. Semaphore tidak boleh mengambil kembali izin yang masih digunakan.
Apa batasan antara semaphore dan mutex?
Semaphore mewakili jumlah sumber daya yang tersedia, dan pelaku (actor) yang berbeda dapat memperoleh dan melepaskan izin. Mutex mewakili kepemilikan eksklusif dan biasanya mengharuskan pemiliknya untuk membuka kunci. Semaphore bernilai satu dapat meniru eksklusi tetapi kehilangan pemeriksaan kepemilikan dan semantik prioritas, jadi pilihlah primitif yang sesuai dengan kontrak API.