Temu Duga Pengekodan: Bagaimanakah anda melaksanakan penjadual tugas berkeutamaan yang boleh dibatalkan?

Arahan dan skop

Laksanakan Scheduler nod tunggal dengan schedule(taskId, runAt, priority, fn), cancel(taskId), dan next(). Pilih runAt terawal, kemudian priority tertinggi, kemudian jujukan penyerahan (sequence). Hanya satu versi taskId yang sah. Tugas yang dibatalkan tidak boleh dimulakan; apabila tiada apa-apa yang perlu dilaksanakan, next() mengembalikan petunjuk menunggu atau hasil kosong. Terangkan pemadaman malas (lazy deletion), kebersamaan pekerja (worker concurrency), pilihan jam, dan perlumbaan penutupan.

Bahan temu duga awam membentangkan penjadualan tugas sebagai masalah gabungan yang melibatkan baris gilir keutamaan, kolam pekerja, pembatalan, dan pengendalian kegagalan. Ia menguji kontrak kitaran hayat dan kebersamaan selain daripada struktur data timbunan (heap) itu sendiri.

Perkara yang diuji oleh penemu duga

Mesin keadaan untuk pending, running, cancelled, dan completed tanpa peralihan tidak sah.
Kunci penentu (runAt, -priority, sequence) yang tidak sekali-kali membandingkan objek tugas.
Pemeriksaan versi atau pemadaman malas supaya penggantian dan pembatalan tidak membocorkan kerja yang lapuk.
Perbezaan tepat antara membatalkan kerja dalam baris gilir dan menghentikan fungsi yang sedang berjalan.
Bukti bahawa had pekerja, susunan penutupan, dan pemilihan jam mengekalkan kontrak.

Penjelasan untuk ditanya terlebih dahulu

Adakah runAt tarikh akhir relatif monotonik atau masa jam dinding (wall-clock)? Andaikan jam monotonik untuk menunggu.
Adakah fn menerima pembatalan? Andaikan AbortSignal, dengan pemberhentian secara koperatif sahaja.
Adakah taskId pendua menggantikan atau gagal? Versi ini menggantikan versi lama.
Adakah cancel menghentikan fungsi yang sedang berjalan serta-merta? Tidak; ia menghalang larian yang belum dimulakan dan memberi isyarat kepada larian yang sedang berjalan.
Adakah close menunggu kerja yang sedang berjalan? Andaikan ia menolak kerja baharu dan menunggu pekerja selesai.

Jawapan 30 saat

Saya akan menyimpan (runAt, -priority, sequence, taskId, version) dalam min-heap dan menyimpan versi semasa untuk setiap ID tugas dalam peta (map). Penjadualan atau pembatalan mengemas kini peta dan membatalkan entri timbunan lama; next() mengesahkan versi dan keadaan berulang kali sebelum memindahkan tugas yang perlu dibayar ke running. Penghantar (dispatcher) menggunakan jam monotonik untuk menunggu kepala timbunan, kemudian menyerahkan kerja kepada kolam pekerja bersaiz tetap. Pembatalan dalam baris gilir ialah jaminan kukuh; pembatalan kod yang sedang berjalan adalah koperatif. Penutupan menolak penyerahan baharu, membangkitkan penghantar, dan menunggu pembersihan.

Panduan mendalam langkah demi langkah

Langkah 1: Tentukan kunci dan invarian

Gunakan (runAt, -priority, sequence) sebagai kunci timbunan. Jujukan monotonik menjadikan cap masa dan keutamaan yang sama bersifat deterministik. current[taskId] hanya menyimpan versi terbaharu. Versi lapuk mungkin kekal dalam timbunan buat sementara waktu, tetapi ia tidak boleh beralih daripada pending kepada running.

Langkah 2: Tentukan penggantian dalam schedule

Setiap schedule mencipta versi baharu, menyimpannya dalam peta, dan menolak entri timbunan baharu. Tiada carian linear melalui tatasusunan. Apabila entri dikeluarkan (popped), versinya dibandingkan dengan peta. Sisipan adalah O(log n) dan ID pendua tidak boleh menghasilkan dua pelaksanaan yang sah.

text

schedule(id, runAt, priority, fn):
    version = nextVersion(id)
    current[id] = {version, state: pending, fn, runAt, priority}
    heappush(heap, (runAt, -priority, nextSequence(), id, version))

Langkah 3: Laksanakan cancel dan pembersihan kepala timbunan

Pembatalan menandakan tugas tertangguh semasa sebagai cancelled dan membangkitkan penunggu. Apabila next() mengeluarkan kepala timbunan, ia memeriksa bahawa peta masih menunjuk kepada versi yang sama dan keadaannya adalah pending. Entri lapuk, dibatalkan, dan digantikan akan dibuang. Pemadaman malas mengelakkan imbasan O(n), tetapi nisbah entri lapuk mesti dipantau dan dibina semula secara berkala.

Langkah 4: Kawal kerja matang dengan had pekerja

Penghantar tidak boleh menyerahkan kerja masa hadapan kepada pekerja. Ia mengira kelewatan ke kepala timbunan dengan jam monotonik. Sebaik sahaja tiba masanya, ia menukar pending kepada running secara atomik dan meletakkan tugas itu ke dalam baris gilir pekerja bersaiz tetap. Kiraan pekerja atau semafor menguatkuasakan had kebersamaan.

Langkah 5: Asingkan pembatalan daripada penamatan fungsi

Jika tugas dalam baris gilir dibatalkan sebelum peralihan keadaan, fn tidak pernah dipanggil. Tugas yang sedang berjalan hanya boleh menerima AbortSignal; fungsi mesti memeriksanya atau menyerahkannya kepada I/O yang boleh dibatalkan. Rekod cancelRequested, dan jangan laporkan penyiapan sehingga fungsi tersebut benar-benar kembali.

Langkah 6: Susun penutupan terhadap perlumbaan

close mula-mula memasuki closing dan menolak jadual baharu, kemudian membatalkan pemasa dan membangkitkan penghantar. Penghantar berhenti menuntut tugas baharu sementara pekerja menyelesaikan kerja yang telah dituntut; hanya selepas itu penjadual menjadi closed. Jika kerja dalam baris gilir harus dibuang serta-merta, tandakan entri peta dibatalkan dan bukannya sekadar mengosongkan timbunan.

Langkah 7: Buktikan batas kekompleksan dan ruang

schedule biasa ialah O(log n), cancel ialah kemas kini keadaan O(1), dan next melakukan kerja timbunan O(log n). Setiap entri lapuk dikeluarkan paling banyak sekali, jadi pembersihan dilunaskan ke atas kemas kini atau pembatalan yang menciptanya. Bina semula daripada entri peta semasa apabila saiz timbunan melebihi gandaan tetap tugas hidup.

Langkah 8: Uji jalinan saling penting

Uji susunan stabil untuk kunci yang sama, penggantian sebelum entri lama mencapai kepala, pembatalan sejurus sebelum dan selepas menuntut tugas, tugas yang lebih awal mengganggu penantian, had pekerja, kegagalan fungsi, penyerahan semasa penutupan, dan lompatan jam monotonik. Uji pembezaan next() terhadap model rujukan yang diisih dan rekod pekerja aktif puncak.

Contoh jawapan berkualiti tinggi

Saya akan memisahkan keadaan daripada timbunan: peta menyimpan versi terbaharu untuk setiap taskId, manakala min-heap menyimpan (runAt, -priority, sequence, taskId, version). Penggantian menulis versi baharu dan pembatalan menandakan keadaan; kedua-duanya tidak mengubah suai tatasusunan timbunan secara langsung. Penghantar hanya menuntut tugas yang matang dan memasukkannya ke dalam baris gilir pekerja bersaiz tetap. Pengesahan versi menghalang entri yang dibatalkan dan lapuk daripada berjalan, manakala AbortSignal memberikan pembatalan koperatif kepada fungsi yang sedang berjalan. Penutupan menolak kerja baharu, berhenti menuntut tugas, membangkitkan penunggu, dan menunggu kerja yang dituntut selesai. Metrik menjejaki entri hidup berbanding saiz timbunan supaya pemadaman malas tidak berkembang tanpa had.

Kesilapan biasa

Mengisih mengikut keutamaan sahaja dan mengabaikan bahawa runAt masih pada masa hadapan.
Mengubah suai entri timbunan di tempatnya dan memecahkan invarian timbunan.
Memadamkan daripada peta sahaja, kemudian melaksanakan entri timbunan lama.
Menganggap panggilan cancel() yang berjaya sebagai bukti bahawa kod yang sedang berjalan telah berhenti.
Menggunakan masa jam dinding untuk menunggu dan mengalami masalah pembetulan jam.
Mengosongkan baris gilir pada close sambil membiarkan pemasa, penghantar, atau pekerja terus hidup.
Memulakan pekerja tanpa had dan menjadikan penjadual sebagai pelancar tanpa batas.

Soalan susulan dan jawapan

Bagaimanakah anda menghalang kebuluran (starvation) kerja berkeutamaan rendah?

Nyatakan bahawa keutamaan ketat ialah lalai dan boleh membulurkan tugas berkeutamaan rendah. Jika keadilan diperlukan, tingkatkan keutamaan berkesan dengan masa menunggu atau gunakan kuota berwajaran. Kedua-dua pilihan mengubah kunci susunan dan bukti kependaman, jadi tambahkan metrik dan ujian.

Bagaimanakah anda menghalang larian bertindih untuk tugas berulang?

Tambahkan kunci larian atau generasi pada keadaan tugas. Jika pencetus seterusnya tiba semasa ia sedang berjalan, pilih secara eksplisit sama ada langkau, gabungkan satu larian yang belum selesai, atau baris giliran versi baharu. Jangan sekali-kali menyerahkan tanpa syarat apabila pertindihan dilarang.

Bagaimanakah anda pulih selepas ranap proses?

Timbunan dalam ingatan hanya meliputi jangka hayat proses. Kekalkan versi, keadaan, dan masa larian seterusnya, bina semula timbunan semasa permulaan, dan tuntut dengan kemas kini bersyarat atau pajakan (lease). Pemulihan biasanya menyediakan pelaksanaan sekurang-kurangnya sekali (at-least-once), jadi fungsi tugas mestilah idempoten.

Bagaimanakah anda meluaskannya kepada berbilang nod?

Gantikan timbunan tempatan dengan baris gilir berindeks masa yang berterusan dan gunakan pajakan atau penulisan bersyarat untuk pemilikan. Biarkan pajakan yang tamat tempoh boleh dicuba semula selepas kegagalan nod. Bawa versi melalui pembatalan dan penggantian supaya pengguna menolak kerja lapuk, dan gunakan masa penyimpanan atau tetingkap toleransi yang jelas merentas nod.