Temu duga pengekodan: Laksanakan penjadual work-stealing

Gesaan dan konteks

Laksanakan penjadual dengan bilangan pekerja tetap N. API awamnya ialah submit(task), shutdown(), dan awaitTermination(). Setiap pekerja memiliki satu deque: pemilik mengambil tugas tempatan dalam susunan LIFO, manakala pekerja yang melahu mencuri dari hujung bertentangan dalam susunan FIFO. Tugas boleh mencipta lebih banyak tugas, tetapi penyerahan punca (root) baharu ditolak selepas penutupan bermula.

Anda boleh bermula dengan garis dasar ketepatan yang dilindungi mutex dan kemudian menerangkan bagaimana deque bebas kunci (lock-free) gaya Chase–Lev akan menggantikannya. Penjadual tidak boleh kehilangan atau melaksanakan tugas dua kali. Kegagalan tugas tidak boleh mematikan gelung pekerja. Tangani giliran kosong, ketiadaan mangsa curian, perlumbaan semasa penutupan dan pekerja yang menyekat (blocking).

Perkara yang diuji oleh penemu duga

Jawapan yang kukuh menyatakan sempadan konkurensi antara operasi pemilik dan pencurian berbanding sekadar menyebut "gunakan kolam benang (thread pool)." LIFO tempatan mengekalkan lokaliti dan tingkah laku depth-first; FIFO jarak jauh memberi pencuri tugas yang lebih lama dan selalunya lebih besar. Penemu duga juga memeriksa sama ada penyerahan, penghentian penerimaan, penyaliran (draining), dan penamatan pekerja membentuk mesin keadaan (state machine) yang eksplisit, dan sama ada anda boleh mengenal pasti titik penglinearisasian (linearization point) yang menjadikan tuntutan tugas itu unik.

Soalan penjelasan

1. Bolehkah tugas menyekat pada I/O? Jika ya, gunakan kolam I/O yang berasingan atau pampasan sekatan terbilang; mencuri lebih banyak tidak dapat membantu apabila setiap pekerja disekat.
2. Adakah submit mengembalikan future? Jika ya, takrifkan penyebaran pengecualian dan pembatalan; jawapan ini mengembalikan future, manakala pembatalan hanya menjamin bahawa kerja yang belum dituntut tidak akan dijalankan.
3. Adakah deque mesti bebas kunci dan tidak terbatas? Jika tidak, laksanakan deque berkunci dahulu dan naik taraf hanya apabila keperluan persaingan (contention) dan penambakan memori terbukti.
4. Adakah penutupan serta-merta atau anggun (graceful)? Jawapan ini adalah anggun: tolak punca baharu, salirkan tugas yang diterima, kemudian keluar.

Jawapan 30 saat

Saya memberikan setiap pekerja satu deque dan menggunakan LIFO pada hujung pemilik serta FIFO pada hujung curian. Saya terlebih dahulu membina garis dasar berkunci: submit memilih giliran dan mengejutkan pekerja; pekerja mengeluarkan (pop) kerja tempatan, kemudian mencuri dari giliran lain apabila kosong. Sesuatu tugas dilaksanakan hanya selepas satu operasi berjaya mengeluarkannya, jadi ia tidak boleh dituntut dua kali. Penutupan menghentikan penyerahan baharu, dan pekerja keluar hanya apabila penjadual sedang menyalir, tugas tertunggak adalah sifar, dan semua giliran adalah kosong. Ujian merangkumi penyerahan serentak, perlumbaan mencuri, penciptaan tugas anak, pengecualian, penutupan dan penantian melahu.

Analisis mendalam langkah demi langkah

Takrifkan keadaan accepting, draining, dan terminated. Semasa accepting, submit meletakkan tugas pada deque yang kurang beban, menambah pembilang tugas tertunggak secara atomik, dan mengejutkan pekerja. Semasa draining, sama ada tugas yang sedang berjalan boleh mencipta anak adalah sebahagian daripada kontrak; versi ini membenarkan anak dan terus menyalir sehingga kiraan mencapai sifar.

type Task = () => void;

class WorkStealingScheduler {
  private readonly queues: Array<Deque<Task>>;
  private accepting = true;
  private outstanding = 0;

  submit(task: Task): void {
    if (!this.accepting) throw new Error("scheduler is shutting down");
    const queue = this.chooseQueue();
    queue.pushBottom(task);
    this.outstanding += 1;
    this.wakeOneWorker();
  }

  run(workerId: number): void {
    while (true) {
      const task = this.queues[workerId].popBottom()
        ?? this.stealFromOtherQueues(workerId);
      if (!task) {
        if (!this.accepting && this.outstanding === 0) return;
        this.parkBriefly();
        continue;
      }
      try { task(); } finally { this.outstanding -= 1; }
    }
  }
}

Coretan kod ini sengaja menggunakan pseudokod benang tunggal untuk peralihan keadaan. Pelaksanaan sebenar mesti menggunakan satu protokol penyegerakan untuk submit, outstanding, penutupan dan pengejutan. Untuk mengelakkan perlumbaan kebangkitan terlepas (lost-wakeup) di mana tugas tiba sejurus selepas semakan kekosongan, gunakan pemboleh ubah keadaan (condition variable), semafor, atau peristiwa terbilang dan bukannya sleep mentah.

Garis dasar berkunci mengekalkan tiga invarian: tugas berjalan hanya selepas berjaya dikeluarkan daripada deque; tiada dua operasi boleh mengeluarkan tugas yang sama; dan outstanding adalah sama dengan kerja yang diterima tetapi belum selesai. Apabila tugas yang sedang berjalan mencipta anak, daftarkan anak sebelum mengurangkan induk, jika tidak, sifar sementara boleh mencetuskan penamatan pramatang.

Keadilan bergantung pada pemilihan mangsa dan saiz kelompok (batch) curian. Kerambangan tulen boleh menjadi herot untuk masa yang lama; round-robin tetap boleh menyegerakkan ramai pencuri pada satu giliran yang sibuk. Gunakan permulaan rawak, backoff apabila gagal mencuri, dan kelompok terhad. Tugas seragam yang kecil cenderung kepada curian tunggal atau kecil; beban kerja rekursif sering mendapat manfaat daripada mengambil bahagian yang lebih lama dan lebih besar.

Bebas kunci ialah pengoptimuman, bukan jawapan lalai. ForkJoinPool Oracle menggunakan work-stealing dan memaparkan kiraan curian untuk penalaan. Deque Chase–Lev memerlukan indeks atomik tambahan, susunan memori (memory ordering), pertumbuhan saiz, dan penambakan selamat. Tanpa model pemilik-tunggal/pelbagai-pencuri yang eksplisit dan pelan penambakan, kod "bebas kunci" yang ditulis sendiri lebih berkemungkinan menduplikasi kerja atau menggunakan storan yang telah dibebaskan berbanding garis dasar berkunci.

Kos jangkaan push/pop tempatan ialah O(1); curian ialah O(1) atau O(batch), manakala mengimbas V mangsa secara naif menelan kos O(V). Ruang ialah O(T + N), di mana T ialah kerja yang belum selesai dan N ialah bilangan pekerja. I/O menyekat membatalkan andaian bahawa pekerja yang melahu sentiasa boleh mencuri, jadi asingkan kerja menyekat atau hadkannya.

Contoh jawapan berkualiti tinggi

Saya akan memberikan versi betul yang berkunci terlebih dahulu dan kemudian membincangkan peningkatan bebas kunci. Setiap pekerja mempunyai deque peribadi; pemilik menggunakan LIFO di bahagian bawah dan pencuri menggunakan FIFO di bahagian atas, dengan penyegerakan pemilik dan curian yang berasingan. Sesuatu tugas mula dilaksanakan hanya selepas operasi pop atau curian berjaya, yang merupakan titik penglinearisasian tuntutannya.

Penyerahan dan penutupan adalah perkara yang berasingan. Penutupan menolak punca baharu, kemudian menunggu kerja tertunggak mencapai sifar. Jika tugas yang sedang berjalan boleh mencipta anak, kontrak penyaliran mesti membenarkan dan mengiranya secara eksplisit; jika tidak, tolak tugas tersebut dan biarkan tugas mengendalikan ralat. Pekerja menunggu pada pemboleh ubah keadaan atau semafor dan bukannya berpusing (spin), dan pengecualian tugas ditangkap dalam future dan metrik dan bukannya terlepas dari gelung pekerja.

Saya akan melepaskan tugas pendek dan panjang secara serentak menggunakan penghalang (barrier), memastikan pelaksanaan tepat sekali (exactly-once) dan kecurian sebenar, serta mengesahkan bahawa giliran disalirkan. Kemudian saya akan menyuntik penciptaan anak, penutupan semasa mencuri, kerja menyekat, pengecualian tugas dan panggilan penutupan berulang. Hanya jika persaingan dan ukuran mewajarkannya, saya akan menggantikan garis dasar dengan deque Chase–Lev yang susunan memori dan penambakannya telah ditentukan.

Kesilapan lazim

• Satu giliran global → setiap pekerja bersaing pada satu kunci → gunakan deque bagi setiap pekerja dan biarkan kecurian menangani ketidakseimbangan.
• Menyemak tidak kosong dan melakukan pop secara berasingan → pencuri lain mengubah giliran antara operasi → jadikan pengeluaran yang berjaya sebagai tuntutan atomik.
• Keluar apabila giliran kelihatan kosong semasa penutupan → induk yang sedang berjalan boleh mencipta anak sejurus selepas itu → gunakan keadaan penyaliran dan invarian tertunggak.
• Membiarkan pengecualian tugas terlepas daripada gelung pekerja → satu tugas yang rosak mengurangkan kepelbagaian tugas serentak (parallelism) → tangkapnya dalam future dan teruskan penjadualan.
• Menulis kod bebas kunci sendiri tanpa peraturan memori atau penambakan → kerja bertindih atau use-after-free → sahkan semantik berkunci terlebih dahulu dan ikuti algoritma yang terbukti.
• Sentiasa mencuri dari satu mangsa → giliran yang sibuk kekal dalam persaingan → gabungkan permulaan rawak, backoff dan kelompok terhad dengan metrik.

Soalan susulan dan jawapan

Bagaimanakah anda menghalang kerja yang menyekat daripada membantutkan semua pekerja?

Bagaimanakah anda membuktikan penutupan tidak boleh kehilangan tugas anak?

Bilakah kecurian kelompok lebih baik daripada kecurian tugas tunggal?

I/O menyekat sepatutnya berada dalam kolam berasingan atau mekanisme sekatan terurus yang dibilang; mencuri hanya memindahkan kerja yang sedang menunggu. Bukti penutupan menggunakan mesin keadaan dan invarian pembilang: hentikan punca baharu, daftarkan anak sebelum menyelesaikan induk, dan tamatkan hanya dalam keadaan penyaliran dengan sifar kerja tertunggak. Kecurian kelompok membantu apabila penciptaan tugas adalah padat dan setiap penyegerakan menelan kos yang tinggi; untuk giliran kecil atau tugas yang kecil, kos pemindahan dan keadilan boleh melebihi penjimatan yang diperoleh.