Gesaan dan konteks
Laksanakan semafor tak segerak untuk kolam sambungan atau pelaksana tugasan. Ia bermula dengan kapasiti N; acquire() beratur apabila tiada permit tersedia, dan release() mengembalikan satu. Pemula tunggu mungkin mengalami tamat masa atau dibatalkan. Pembatalan tidak boleh meninggalkan entri baris gilir hantu atau menghalang pemula tunggu lain daripada maju. Tentukan pelepasan pendua, tingkah laku tutup, dan keadilan.
Ini sesuai untuk temu duga keserentakan, masa jalanan, dan infrastruktur bahagian belakang. API Semaphore milik Oracle mentakrifkan permit, pemilihan FIFO adil pilihan, dan pemerolehan yang boleh diganggu. Dokumentasi asyncio milik Python menerangkan pembilang yang berkurang semasa acquire dan meningkat semasa release, serta membezakan semafor biasa daripada semafor terbatas. Perbincangan temu duga awam menyenaraikan semafor pembilang dan had keserentakan sebagai topik temu duga sistem pengendalian. Sumber-sumber ini menyokong keterwakilan, tetapi tidak menetapkan gesaan atau kekerapan syarikat yang tetap. Kategorinya ialah coding kerana kemahiran terasnya ialah invarian keadaan, pembersihan baris gilir, perlumbaan pembatalan, dan pelaksanaan serentak yang boleh disahkan.
Perkara yang dinilai oleh penemu duga
Pertama, adakah calon mentakrifkan pemilikan permit? acquire yang berjaya mesti mencipta token yang boleh dikembalikan tepat sekali. Permintaan yang dibatalkan atau tamat masa tidak mempunyai token dan tidak boleh memanggil release.
Kedua, adakah keadilan itu benar? Sebaik sahaja baris gilir tidak kosong, release baharu tidak boleh membiarkan laluan pantas yang terkemudian memintas kepala baris gilir; jika tidak, beban tinggi boleh menyebabkan pemula tunggu yang lama kelaparan (starve). Keadilan FIFO memerlukan pemeriksaan baris gilir, penetapan permit, dan membangunkan pemula tunggu dalam satu sempadan penyegerakan.
Ketiga, bolehkah mereka mengendalikan perlumbaan pembatalan dengan pembangkitan (wakeup)? Pemula tunggu mungkin telah dipilih oleh release dan kemudian tamat masa, atau ia mungkin tamat masa sebelum release mengeluarkannya. Kedua-dua laluan mesti bersaing pada satu peralihan keadaan dan menyelesaikan pemula tunggu paling banyak sekali.
Akhir sekali, adakah ujian memeriksa had keserentakan, urutan FIFO, pembersihan tamat masa, kemajuan selepas pembatalan, pelepasan pendua, penutupan, dan kegagalan tugasan dan bukannya hanya acquire/release berurutan?
Soalan penjelasan untuk ditanya terlebih dahulu
- Adakah keadilan merupakan FIFO ketat atau usaha terbaik? FIFO ketat mengelakkan kebuluran (starvation) tetapi boleh mengorbankan daya pemprosesan.
- Apakah yang dikembalikan oleh acquire? Token pelepasan atau pajakan (lease) mengikat pemilikan kepada satu pemerolehan yang berjaya dan mengurangkan pelepasan yang tidak sengaja.
- Bagaimana jika pembatalan berlaku selepas permit diperuntukkan? Tentukan keutamaan penyelesaian; sebaik sahaja janji (promise) selesai, pemanggil memiliki pajakan dan pembatalan hanya menjejaskan kerja yang terkemudian.
- Adakah release lebih banyak kali daripada acquire merupakan ralat? Semafor terbatas harus menolak atau melaporkannya; meningkatkan kiraan secara senyap melanggar kapasiti.
- Bagaimanakah close menyelesaikan pemula tunggu? Close menolak permintaan baharu dan menamatkan pemula tunggu yang beratur dengan ralat Closed yang jelas; pajakan yang dipegang masih boleh dilepaskan dengan selamat.
Kerangka jawapan 30 saat
“Saya mengekalkan available, baris gilir pemula tunggu FIFO, dan keadaan tertutup, dengan setiap mutasi dalam satu bahagian kritikal. Acquire boleh mengambil laluan pantas hanya apabila baris gilir kosong; sebaik sahaja pemula tunggu wujud, pemanggil terkemudian beratur. Release mencari pemula tunggu hidup yang pertama, memindahkan satu permit, dan menyelesaikannya sekali; hanya apabila tiada pemula tunggu hidup wujud barulah ia meningkatkan available. Setiap pemula tunggu mempunyai keadaan pembatalan dan penyelesaian satu kali. Tamat masa dan release berlumba pada keadaan yang sama itu. Acquire yang berjaya mengembalikan pajakan yang boleh dilepaskan sekali. Ujian memaksa FIFO, pembatalan dan release pada sempadan yang sama, pemulihan permit selepas tamat masa, pelepasan pendua, close, dan had keserentakan.”
Jawapan mendalam
1. Nyatakan invarian teras
Untuk kapasiti N, kekalkan available + held + reserved = N. available boleh diperuntukkan serta-merta, held milik pemanggil melalui pajakan, dan reserved telah berpindah daripada tersedia kepada pemula tunggu terpilih yang panggil baliknya belum selesai lagi.
Setiap pemula tunggu mempunyai tepat satu keadaan terminal: tertangguh, dipenuhi, atau dibatalkan. Pemula tunggu yang dibatalkan tidak memiliki permit; pemula tunggu yang dipenuhi mesti menghasilkan pajakan. Menutup tidak menuntut semula pajakan yang dipegang, tetapi ia menghalang pemerolehan baharu.
2. Laluan pantas yang adil dan baris gilir
Apabila waiters kosong dan semafor dibuka, acquire boleh menggunakan available secara terus. Apabila baris gilir tidak kosong, walaupun available > 0, pemanggil baharu beratur; jika tidak, ia memintas pemanggil yang lebih lama. Acquire dan release mesti memeriksa baris gilir di bawah sempadan penyegerakan yang sama.
Nod baris gilir menyimpan janji pemula tunggu, keadaan pembatalan, pemegang pemasa, dan fungsi penyelesaian satu kali. Alih keluar nod yang telah selesai atau dibatalkan, atau kekalkan batu nisan (tombstones) yang dilangkau oleh release secara malas di kepala baris gilir. Mana-mana strategi memerlukan bukti bahawa pemula tunggu hidup tidak boleh kekal secara kekal di belakang nod yang tidak sah.
3. Pindahkan permit dalam release
Release mula-mula mengesahkan bahawa pajakan belum dilepaskan, kemudian memberikan permit kepada pemula tunggu hidup yang pertama. Permit bertukar daripada dipegang kepada ditempah dan penyelesaian pemula tunggu digunakan; jangan tingkatkan available dan cari secara tak segerak, kerana acquire baharu boleh memotong barisan.
Jika kepala dibatalkan, langkau dan bersihkannya, meneruskan ke pemula tunggu seterusnya. Hanya jika tiada pemula tunggu hidup wujud barulah available += 1. Semafor terbatas menolak pelepasan melebihi N supaya pepijat pemanggil tidak dapat menyembunyikan kebocoran atau pemulangan berganda.
4. Perlumbaan pembatalan dan tamat masa
Pembatalan dan release kedua-duanya boleh cuba menyelesaikan pemula tunggu yang sama. Gunakan CAS satu kali, pemeriksaan keadaan dalam kunci, atau mekanisme yang setara supaya hanya satu yang menang. Jika pembatalan menang, alih keluar pemula tunggu tanpa mengubah available kerana ia tidak pernah memiliki permit. Jika release telah menempah permit, pembatalan tidak boleh kedua-duanya mengembalikannya dan membiarkan release menyelesaikan pemula tunggu yang sama.
Peraturan mudah adalah untuk release menandakan pemula tunggu dipenuhi di dalam bahagian kritikal sebelum menyelesaikannya. Sebaik sahaja dipenuhi, tamat masa hanya boleh merekodkan bahawa pemanggil meninggalkan kerja yang terkemudian; pemanggil masih melepaskan pajakan yang diterimanya. Reka bentuk yang lebih terperinci mungkin menuntut semula tempahan yang tidak dihantar, tetapi tuntutan semula itu tergolong dalam mesin keadaan yang sama dan bukannya disimpulkan daripada janji yang ditolak.
5. Pajakan dan pelepasan pendua
Kembalikan pajakan dengan bendera released. lease.release() boleh beralih daripada false kepada true sekali. Panggilan pendua mengembalikan hasil idempoten atau ralat yang jelas; ia tidak boleh menambah dua permit. Mendedahkan kaedah pelepasan kosong kepada pemanggil sebarangan akan kehilangan perkaitan pemilikan melainkan API menggunakan model pembilangan milik pemanggil secara eksplisit.
6. Close, kegagalan, dan tekanan belakang (backpressure)
Selepas close, tolak acquire baharu dan selesaikan pemula tunggu yang beratur dengan Closed. Tugasan yang memegang pajakan boleh selesai dan dilepaskan; release tidak boleh membuang permit semata-mata kerana semafor ditutup, atau kiraan yang dipegang menjadi tidak dapat dijelaskan. Kegagalan tugasan masih melepaskan dalam finally.
Semafor mengehadkan keserentakan, bukan panjang baris gilir. Baris gilir pemula tunggu tanpa batas mengubah tekanan belakang menjadi pertumbuhan memori. Kod pengeluaran harus menetapkan kiraan menunggu maksimum, tamat masa, atau dasar penolakan, dan merekodkan tempoh menunggu, kadar pembatalan, dan kedalaman baris gilir.
7. Kawal perlumbaan dengan penjadual
Jangan buktikan perlumbaan dengan tidur (sleeps) sebenar. Gunakan jam manual dan penjadual yang boleh dikawal untuk menjeda pada baris gilir, release memilih pemula tunggu, dan panggilan balik tamat masa yang dibariskan tetapi belum dilaksanakan. Pada setiap langkah, asertifkan available, held, kiraan pemula tunggu hidup, dan pemilikan pajakan.
Lindungi pemulaan N=0 yang tidak sah, FIFO ketat dengan N=1, berbilang permit, pembatalan kepala dan pemula tunggu tengah, tamat masa dan release pada sempadan yang sama, pelepasan pendua, acquire sebelum dan selepas close, kegagalan tugasan, dan ketiadaan kebuluran untuk pemanggil yang menunggu lama.
Contoh jawapan berkualiti tinggi
“Saya merangkumkan pemilikan permit dalam pajakan. Semafor menyimpan available, pemula tunggu FIFO, dan keadaan tertutup, serta semua peralihan berkongsi satu sempadan penyegerakan. Acquire mengambil laluan pantas hanya apabila baris gilir kosong; sebaik sahaja pemula tunggu wujud, panggilan terkemudian beratur.
Release mengesahkan pajakan dilepaskan sekali, mencari pemula tunggu hidup yang pertama, memindahkan held kepada tempahan pemula tunggu itu, dan menyelesaikannya sekali. Ia melangkau dan membersihkan kepala yang dibatalkan; hanya tanpa pemula tunggu hidup barulah ia meningkatkan available. Pembatalan dan tamat masa berlumba dengan release pada keadaan pemula tunggu yang sama, dan peralihan satu kali memilih pemenang. Pembatalan sebelum acquire tidak memiliki permit, manakala acquire yang selesai memberikan pemanggil pajakan yang tidak boleh digantikan oleh pembatalan.
Close menolak permintaan baharu dan menyelesaikan pemula tunggu yang beratur, manakala pajakan yang dipegang masih boleh dilepaskan. Ujian menggunakan jam manual dan penjadual untuk memaksa FIFO, pembatalan kepala dan tengah, tamat masa dan release bersama, pelepasan pendua, pembersihan finally selepas kegagalan, dan had keserentakan. Invarian pembilang membuktikan bahawa tiada permit yang hilang atau dicipta.”
Kesilapan biasa
- Mengambil laluan pantas semasa baris gilir tidak kosong → pemanggil baharu memintas pemanggil lama dan menyebabkan mereka kelaparan → bariskan setiap pemanggil semasa pemula tunggu wujud.
- Meningkatkan available apabila pemula tunggu membatalkan → release mungkin telah menempah permitnya → perlumbaan pembatalan dan release pada satu keadaan satu kali.
- Mendedahkan pelepasan tanpa pemilik → panggilan pendua mencipta permit → kembalikan pajakan yang boleh dilepaskan sekali.
- Meningkatkan available sebelum membangunkan kepala → pemanggil baharu boleh memotong barisan → pindahkan secara terus di bawah bahagian kritikal yang sama.
- Menganggap tamat masa sebagai pengunduran (rollback) pajakan yang dihantar → tugasan mungkin masih berjalan → bezakan pembatalan menunggu daripada permit yang diperoleh.
- Membenarkan baris gilir tanpa batas → had keserentakan menjadi kebocoran memori → tetapkan had baris gilir, tamat masa, atau dasar penolakan.
- Hanya menguji panggilan berurutan → perlumbaan pembatalan dan pelepasan pendua terlepas pandang → paksa penyisipan (interleavings) dengan penjadual yang boleh dikawal.
- Membuang permit yang dipegang semasa close → kiraan sumber tidak boleh menumpu (converge) → biarkan pajakan yang dipegang dilepaskan dalam finally.
Soalan dan jawapan susulan
Adakah keadilan FIFO sentiasa lebih baik?
Tidak. FIFO menghalang kebuluran dan mudah diterangkan, tetapi kepala yang berjalan lama atau hampir tamat masa boleh mewujudkan sekatan kepala barisan (head-of-line blocking). Pelaksanaan yang mengutamakan daya pemprosesan mungkin membenarkan laluan pantas yang tidak adil, tetapi kebuluran, masa menunggu maksimum, dan keutamaan mestilah pilihan kontrak yang eksplisit dan bukannya sifat yang diandaikan.
Bagaimanakah anda memperoleh berbilang permit sekali gus?
Rekodkan kiraan yang diminta oleh setiap pemula tunggu dan penuhilah hanya apabila available cukup besar. FIFO ketat boleh menyebabkan permintaan satu permit di belakang kepala berbilang permit menunggu; membenarkan pintasan mengorbankan keadilan. Pilih satu dasar dan kira permit yang ditempah, bukan objek pemula tunggu, dalam invarian.
Bagaimana jika tugasan dibatalkan separuh jalan melalui kerjanya?
Semafor memiliki permit, bukan gangguan tugasan. Pemanggil harus menghentikan kerja semasa pembatalan dan melepaskan pajakan dalam finally; jika kerja tidak boleh diganggu, ia mesti selesai sebelum melepaskan. Semafor tidak boleh menuntut semula permit yang masih digunakan.
Apakah sempadan antara semafor dan mutex?
Semafor mewakili kiraan sumber yang tersedia, dan pelaku (actors) yang berbeza boleh memperoleh dan melepaskan permit. Mutex mewakili pemilikan eksklusif dan biasanya memerlukan pemilik untuk membuka kunci. Semafor bernilai satu boleh meniru pengecualian sambil kehilangan pemeriksaan pemilikan dan semantik keutamaan, jadi pilih primitif yang sepadan dengan kontrak API.