Temu Duga Pengekodan: Bagaimanakah Anda Membina Penjadual Tugas Sedar Kebergantungan?

Keperluan dan skop

Laksanakan TaskScheduler dalam memori. Pemanggil menyerahkan ID tugas, ID kebergantungan, dan fungsi. Penjadual hanya boleh menuntut tugas selepas setiap kebergantungan berjaya. Sediakan operasi seperti submit, ready, complete, fail, dan cancel, serta laporkan kitaran kebergantungan yang tidak akan dapat dijalankan. Terangkan penyerahan pendua, penyebaran kegagalan, had keserentakan, penutupan, dan sempadan mula semula.

Masalah ini menggabungkan penjelajahan graf dengan mesin keadaan langsung. Jawapan yang kukuh menjelaskan semantik keadaan dan kegagalan sebelum memilih struktur data, kemudian mengekalkan darjah masuk (indegree), tepi songsang (reverse edges), dan baris gilir sedia. TopologicalSorter Python menganggap nod tanpa pendahulu yang belum selesai sebagai boleh diproses dan mendedahkan kitaran yang dikesan sebagai data diagnostik. Semantik tersebut membantu menentukan kontrak, tetapi pengisihan statik sahaja tidak mencukupi kerana tugas selesai, gagal, dan dibatalkan dari semasa ke semasa.

Perkara yang diuji oleh penemu duga

Membezakan pending, ready, running, succeeded, failed, blocked, dan cancelled.
Mengekalkan invarian darjah masuk dan kedampingan songsang berbanding mengimbas semula setiap tugas.
Melepaskan hanya tanggungan yang terjejas apabila kebergantungan selesai.
Menentukan penyebaran kitaran, kegagalan, dan pembatalan sebelum memilih API.
Menghadkan pekerja, menjamin satu tuntutan bagi setiap versi tugas, dan mengendalikan penyerahan pendua.
Memberikan batasan kerumitan dan ujian untuk selang-seli adversarial.

Soalan penjelasan

Adakah graf statik atau bolehkah tugas ditambah secara dinamik? Anggap semua tugas yang dirujuk diserahkan sebelum penjadualan bermula; hanya versi baharu boleh diserahkan semasa berjalan.
Apakah yang berlaku kepada keturunan selepas kebergantungan gagal? Jawapan ini menandakannya sebagai blocked; percubaan semula memerlukan generasi baharu yang eksplisit.
Adakah pembatalan melata ke setiap keturunan? Anggap ia membatalkan tugas itu sahaja; keturunan menjadi blocked apabila kebergantungan yang diperlukan dibatalkan.
Adakah kegagalan dicuba semula secara automatik? Tidak. Pemanggil menyerahkan generasi baharu dan mengurus keidempotanan untuk kesan sampingan.
Adakah ready() mengembalikan satu tugas atau satu kelompok? Kembalikan paling banyak maxConcurrency - running tugas dalam susunan deterministik.

Jawapan tiga puluh saat

Simpan keadaan setiap tugas, kiraan kebergantungan yang belum selesai, dan senarai kedampingan songsang. Sebelum penjadualan, jalankan algoritma Kahn atau DFS tiga warna dan kembalikan laluan kitaran apabila ia wujud. Letakkan tugas dengan darjah masuk sifar ke dalam baris gilir sedia yang stabil. Di bawah satu kunci, tuntut tugas dengan menukar ready kepada running; apabila berjaya, susutkan kiraan setiap tanggungan dan masukkan nod yang mencapai sifar ke dalam baris gilir. Kegagalan dan pembatalan menandakan keturunan yang terjejas sebagai blocked. Setiap panggilan balik membawa generasi supaya pekerja lapuk tidak dapat melepaskan tanggungan sebanyak dua kali. Kolam pekerja tetap atau semafor menguatkuasakan keserentakan.

Penyelesaian langkah demi langkah

Langkah 1: Tentukan keadaan dan sempadan

Keadaan bergerak ke hadapan: pending kepada ready, kemudian running, dan akhirnya succeeded atau failed. Pembatalan boleh berlaku semasa pending atau ready; pembatalan fungsi yang sedang berjalan adalah secara koperatif. blocked bermakna fungsi tersebut tidak berjalan kerana kebergantungan yang diperlukan tidak lagi boleh berjaya. Keadaan terminal tidak pernah kembali kepada ready, mengelakkan pelaksanaan pendua.

Simpan generation bagi setiap ID tugas. Penyerahan pendua boleh ditolak atau mencipta generasi baharu; jawapan ini memilih penggantian hanya semasa versi lama tidak berjalan. Versi yang sedang berjalan tidak boleh ditimpa secara senyap; kembalikan konflik atau tunggu panggilan balik terminalnya.

Langkah 2: Bina darjah masuk dan tepi songsang

Jadual tugas menyimpan remainingDeps; peta songsang menyimpan dependents[dependencyId]. Daftarkan setiap tepi sekali sahaja. Tugas dengan darjah masuk sifar memasuki baris gilir sedia semasa pemulaan, dan perubahan kemudiannya mengemas kini kiraan yang terjejas sahaja.

text

Task:
  id, generation, dependencies, dependents
  remainingDeps, state, fn, error

submit(task):
  validateUniqueDependencies(task)
  registerEdges(task)
  if task.remainingDeps == 0:
      task.state = READY
      readyQueue.push(task.id)

Kebergantungan yang tidak diketahui tidak boleh dianggap sebagai sudah selesai. Kekalkannya dalam keadaan waiting sehingga diserahkan, atau tolaknya dengan ralat UnknownDependency jika kontrak memerlukan graf tertutup.

Langkah 3: Laporkan kitaran sebelum pelaksanaan

Bagi graf statik, algoritma Kahn menyalin darjah masuk, memproses nod berdarjah masuk sifar, dan membuang tepi keluar daripadanya. Jika kurang daripada semua nod diproses, bakinya mengandungi kitaran. Kembalikan laluan konkrit seperti A → B → C → A, bukan sekadar nilai boolean.

Secara alternatif, DFS putih-kelabu-hitam mencari tepi kelabu-ke-kelabu dan membina semula kitaran melalui penunjuk induk. Jalankan pengesanan sebelum sebarang tugas menjadi running. Jangan benarkan penambahan tepi selepas pelaksanaan bermula melainkan kontrak mencipta versi graf baharu.

Langkah 4: Tuntut tugas dan kuat kuasakan keserentakan

ready() mengira slot yang tersedia, mengeluarkan tugas dalam susunan penyerahan yang stabil, dan menukar setiap keadaan kepada running dalam bahagian genting yang sama. Setelah dikembalikan, pemanggil lain tidak boleh menuntut tugas tersebut. complete(id, generation) mengesahkan kedua-dua generasi dan keadaan; panggilan balik yang lewat daripada pekerja lama mengembalikan konflik dan tidak boleh melepaskan tanggungan.

Gunakan bilangan pekerja tetap atau semafor untuk had keserentakan. Panjang baris gilir bukan bilangan tugas aktif: hanya tugas running yang menggunakan slot. Jika kelompok yang diminta melebihi slot yang tersedia, kembalikan nombor yang tersedia atau CapacityExceeded daripada meningkatkan keserentakan secara senyap.

Langkah 5: Sebarkan kejayaan, kegagalan, dan pembatalan

Apabila berjaya, jelajahi tanggungan langsung. Susutkan remainingDeps hanya untuk versi yang masih tergantung; masukkan nod ke dalam baris gilir apabila kiraan mencapai sifar. Apabila gagal, kontrak ini menandakan keturunan langsung dan transitif sebagai blocked serta merekodkan punca halangan pertama. Dasar kebergantungan alternatif hanya sah jika dinyatakan secara eksplisit.

Pembatalan mempengaruhi versi yang belum dimulakan. Fungsi yang sedang berjalan mungkin menerima AbortSignal, tetapi hanya fungsi tersebut boleh mengesahkan keluar secara koperatif. Keturunan menjadi blocked apabila kebergantungan yang diperlukan gagal atau dibatalkan; mereka tidak pernah berpura-pura bahawa kebergantungan itu berjaya.

Langkah 6: Jadikan penyerahan dan panggilan balik bersifat idempotan

Gunakan (taskId, generation) sebagai kunci keidempotanan. Panggilan complete, fail, atau cancel yang berulang mengembalikan keadaan terminal yang diketahui dan tidak menyusutkan tanggungan sebanyak dua kali. Apabila menggantikan versi tergantung, buang tepi songsang lamanya sebelum mendaftarkan yang baharu; menimpa objek itu sahaja meninggalkan tepi lapuk dan boleh menyebabkan tanggungan menunggu selama-lamanya.

Jika kemas kini tidak diperlukan, menolak ID pendua adalah lebih mudah. Nyatakan kompromi: pembina statik boleh menolak pendua, manakala aliran kerja jangka panjang biasanya memerlukan generasi, rekod audit, dan versi percubaan semula yang eksplisit.

Langkah 7: Penutupan, percubaan semula, dan pemulihan

close() menolak penyerahan baharu, menghentikan ready() daripada menuntut lebih banyak kerja, dan menunggu panggilan balik yang sedang berjalan atau tamat masa yang ditetapkan. Tugas dalam baris gilir dibatalkan atau dikekalkan mengikut kontrak; mengosongkan memori tanpa merekodkan sebab akan kehilangan maklumat. Percubaan semula mencipta generasi baharu dan menyemak semula snapshot kebergantungan daripada menukar failed kembali kepada ready.

Penjadual dalam memori tidak dapat pulih selepas ranap proses. Pengekalan memerlukan tugas, versi, keadaan, kebergantungan, dan pajakan. Pekerja pemulihan menuntut tugas dengan penulisan bersyarat, dan fungsi tugas mestilah idempotan. Pemulihan boleh menyediakan pelaksanaan sekurang-kurangnya sekali (at-least-once), bukan kesan sampingan tepat sekali (exactly-once).

Langkah 8: Kerumitan dan ujian

Pemulaan graf ialah O(V + E). Setiap penyelesaian mengimbas tepi keluar sahaja, jadi keseluruhan fasa penyebaran kekal O(V + E); baris gilir sedia berasaskan timbunan (heap) menuntut dalam O(log V). Ruang ialah O(V + E).

Uji graf kosong, cabang bebas, rantaian panjang, kitaran, kebergantungan tidak diketahui, dua kebergantungan selesai bersama-sama, penyebaran kegagalan, pembatalan keturunan, panggilan balik pendua, penyerahan pendua, kapasiti sifar, perlumbaan penutupan, dan panggilan balik lewat daripada generasi lama. Model keadaan kecil boleh membandingkan setiap set sedia dan menegaskan paling banyak satu peralihan pending → running bagi setiap versi.

Contoh jawapan

Saya akan membekukan graf terlebih dahulu, kemudian menyimpan keadaan, generasi, baki kiraan kebergantungan, dan kedampingan songsang bagi setiap tugas. Algoritma Kahn berserta penunjuk induk melaporkan kitaran yang konkrit. Tugas tanpa kebergantungan memasuki baris gilir sedia yang stabil. ready() menuntut sehingga baki slot keserentakan di bawah satu kunci dan segera menandakan tugas sebagai running. Panggilan balik penyelesaian mesti sepadan dengan generasi dan hanya boleh beralih sekali; kejayaan menyusutkan kiraan hiliran dan memasukkan nod yang mencapai sifar ke dalam baris gilir. Kegagalan dan pembatalan menghasilkan keturunan blocked dan bukannya kejayaan palsu. Panggilan balik pendua adalah idempotan, percubaan semula mencipta generasi baharu, dan penutupan menolak kerja baharu sebelum mengalirkan panggilan balik yang sedang berjalan. Fasa ini ialah O(V + E) dan ujian merangkumi sempadan keserentakan dan kesan sampingan.

Kesilapan biasa

Melakukan satu pengisihan topologi tanpa menentukan peralihan penyelesaian dan kegagalan secara langsung.
Mengimbas setiap nod untuk kesediaan selepas setiap penyelesaian berbanding menggunakan tepi songsang.
Mengembalikan nilai boolean kitaran sahaja, tanpa laluan diagnostik.
Meniadakan generasi daripada panggilan balik penyelesaian, membolehkan pekerja lapuk melepaskan tanggungan.
Menganggap kegagalan kebergantungan sebagai kejayaan dan menjalankan kerja hiliran tanpa prasyarat.
Mendakwa bahawa membatalkan fungsi yang sedang berjalan adalah secara paksa tanpa kontrak isyarat koperatif.
Meningkatkan bilangan pekerja untuk menyembunyikan tunggakan dan menghabiskan kapasiti hiliran.
Menggunakan semula keadaan gagal untuk percubaan semula tanpa semantik keidempotanan, kesan sampingan, atau pajakan.

Soalan susulan

Bagaimanakah anda mengendalikan graf yang terlalu besar untuk memori?

Simpan metadata tugas dan tepi secara tahan lama, dan muatkan hanya tetingkap aktif mengikut penyewa atau sekatan. Kekalkan kursor dalam memori. Tuntutan menggunakan penulisan bersyarat atau pajakan pendek, dan penyelesaian masih menyemak generasi. Terangkan kebergantungan rentas sekatan, ketekalan penomboran halaman, dan pelaksanaan pendua selepas tamat tempoh pajakan.

Bagaimanakah cabang yang gagal boleh diteruskan manakala nod tanggungan berhenti?

Labelkan tepi sebagai diperlukan atau pilihan. Tugas menjadi sedia hanya selepas semua kebergantungan yang diperlukan berjaya dan kebergantungan pilihan mencapai keadaan terminal. Rekodkan kegagalan pilihan dalam ringkasan input dan metrik dan bukannya menggugurkannya secara senyap; ini memperluaskan mesin keadaan dan ujian.

Bagaimanakah anda menambah kebergantungan secara dinamik?

Benarkan tepi baharu hanya semasa tugas berada dalam keadaan pending, menambah darjah masuk dalam bahagian genting yang sama. Tolak perubahan pada tugas ready atau running. Jika perubahan semasa berjalan diperlukan, cipta generasi baharu dan laksanakannya terhadap graf baharu selepas versi lama mencapai keadaan terminal.

Bagaimanakah anda membatalkan kebergantungan kongsi tanpa menjejaskan cabang yang tidak berkaitan?

Tukar hanya keadaan terminal kebergantungan tersebut, kemudian periksa hubungan tepi yang diperlukan di sepanjang tepi songsang. Cabang tanpa kebergantungan tersebut diteruskan; setiap tugas hiliran yang memerlukannya menjadi blocked. Audit siapa yang membatalkannya, bila, dan di sepanjang laluan penyebaran yang mana.

Bagaimanakah pelbagai proses pekerja mengelakkan pelaksanaan berganda?

Tuntut dengan kemas kini pangkalan data atomik atau pajakan dan sertakan generasi dalam syarat. Pajakan mungkin tamat tempoh dan membenarkan tuntutan lain, jadi fungsi tersebut mestilah idempotan atau boleh dikompensasikan. Kunci dalam memori melindungi satu proses sahaja.

Isyarat keterlihatan manakah yang penting?

Jejak kiraan kitaran, kiraan disekat, masa menunggu sedia, tempoh larian, konflik tuntutan, tamat tempoh pajakan, panggilan balik pendua, dan kependaman penyebaran bagi setiap tepi. Bahagikan mengikut jenis tugas dan penyewa supaya nilai purata tidak menyembunyikan tunggakan ekor, dan bezakan ralat konfigurasi graf daripada kegagalan fungsi.

Bagaimanakah anda membuktikan sesuatu tugas tidak dituntut dua kali?

Letakkan pemeriksaan keadaan, pengurangan slot, dan penulisan running dalam satu bahagian genting atau kemas kini bersyarat atomik, dan sertakan generasi dalam panggilan balik. Ujian model boleh menyelang-seli dua panggilan ready() dan menegaskan paling banyak satu peralihan pending → running bagi setiap versi; penyelesaian pendua mengembalikan keadaan terminal yang diketahui.