Wawancara coding: Mengimplementasikan penjadwal work-stealing

Petunjuk dan konteks

Implementasikan penjadwal dengan jumlah tetap N worker. API publiknya adalah submit(task), shutdown(), dan awaitTermination(). Setiap worker memiliki deque: pemilik mengambil pekerjaan lokal dalam urutan LIFO, sementara worker yang idle mencuri dari ujung yang berlawanan dalam urutan FIFO. Tugas dapat membuat lebih banyak tugas, tetapi pengiriman root baru akan ditolak setelah shutdown dimulai.

Anda dapat memulai dengan dasar kebenaran (correctness baseline) yang dilindungi mutex dan kemudian menjelaskan bagaimana deque lock-free bergaya Chase–Lev akan menggantikannya. Penjadwal tidak boleh kehilangan atau mengeksekusi tugas dua kali. Kegagalan tugas tidak boleh mematikan loop worker. Tangani antrean kosong, tidak adanya korban pencurian (steal victim), race condition saat shutdown, dan worker yang memblokir (blocking).

Apa yang sedang diuji oleh pewawancara

Jawaban yang kuat menyebutkan batasan konkurensi antara operasi pemilik dan pencurian alih-alih hanya mengatakan "gunakan thread pool." LIFO lokal mempertahankan lokalitas dan perilaku depth-first; FIFO jarak jauh memberi pencuri pekerjaan yang lebih lama dan sering kali lebih besar. Pewawancara juga memeriksa apakah pengiriman, penghentian penerimaan, pengosongan (draining), dan keluarnya worker membentuk state machine yang eksplisit, dan apakah Anda dapat mengidentifikasi titik linearisasi yang membuat klaim tugas menjadi unik.

Pertanyaan klarifikasi

1. Bisakah tugas memblokir pada I/O? Jika ya, gunakan pool I/O terpisah atau kompensasi pemblokiran terhitung; pencurian tambahan tidak dapat membantu ketika setiap worker terblokir.
2. Apakah submit mengembalikan future? Jika ya, tentukan propagasi eksepsi dan pembatalan; jawaban ini mengembalikan future, sementara pembatalan hanya menjamin bahwa pekerjaan yang belum diklaim tidak akan berjalan.
3. Apakah deque harus lock-free dan tidak terbatas? Jika tidak, implementasikan deque yang terkunci terlebih dahulu dan tingkatkan hanya ketika persyaratan kontensi dan reklamasi memori terbukti.
4. Apakah shutdown bersifat langsung atau graceful? Jawaban ini bersifat graceful: tolak root baru, kosongkan pekerjaan yang telah diterima, lalu keluar.

Jawaban 30 detik

Saya memberikan deque kepada setiap worker dan menggunakan LIFO di ujung pemilik dan FIFO di ujung pencuri. Pertama, saya membangun baseline terkunci: submit memilih antrean dan membangunkan worker; worker melakukan pop pada pekerjaan lokal, lalu mencuri dari antrean lain saat kosong. Suatu tugas dieksekusi hanya setelah satu operasi berhasil menghapusnya, sehingga tidak dapat diklaim dua kali. Shutdown menghentikan pengiriman baru, dan worker keluar hanya ketika penjadwal sedang mengosongkan antrean (draining), pekerjaan yang belum selesai bernilai nol, dan semua antrean kosong. Pengujian mencakup submit konkuren, race condition saat mencuri, pembuatan tugas anak, eksepsi, shutdown, dan penantian saat idle.

Pembahasan mendalam langkah demi langkah

Definisikan status accepting, draining, dan terminated. Selama accepting, submit menempatkan pekerjaan pada deque yang berbeban ringan, menaikkan counter pekerjaan tertunda secara atomik, dan membangunkan worker. Selama draining, apakah tugas yang sedang berjalan boleh membuat tugas anak merupakan bagian dari kontrak; versi ini mengizinkan tugas anak dan terus mengosongkan antrean hingga hitungan mencapai nol.

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; }
    }
  }
}

Cuplikan kode ini sengaja dibuat berupa pseudocode single-threaded untuk transisi status. Implementasi nyata harus menggunakan satu protokol sinkronisasi untuk submit, outstanding, shutdown, dan membangunkan worker. Untuk menghindari race condition lost-wakeup di mana tugas tiba tepat setelah pengecekan kosong, gunakan condition variable, semafor, atau counted event daripada sleep biasa.

Baseline yang terkunci mempertahankan tiga invarian: sebuah tugas berjalan hanya setelah berhasil dihapus dari deque; tidak ada dua operasi yang dapat menghapus tugas yang sama; dan outstanding sama dengan pekerjaan yang diterima tetapi belum selesai. Ketika tugas yang sedang berjalan membuat tugas anak, daftarkan tugas anak sebelum mengurangi counter induk, jika tidak, nilai nol sesaat dapat memicu penghentian prematur.

Keadilan bergantung pada pemilihan korban dan ukuran batch pencurian. Keacakan murni bisa timpang untuk waktu yang lama; round-robin tetap dapat menyinkronkan banyak pencuri pada satu antrean yang padat. Gunakan permulaan acak, backoff saat gagal mencuri, dan batch terbatas. Tugas-tugas kecil yang seragam lebih cocok dengan pencurian tunggal atau kecil; beban kerja rekursif sering kali diuntungkan dengan mengambil potongan yang lebih lama dan lebih besar.

Lock-free adalah optimasi, bukan jawaban default. ForkJoinPool milik Oracle menggunakan work-stealing dan mengekspos jumlah pencurian untuk penyetelan. Deque Chase–Lev selain itu memerlukan indeks atomik, pengurutan memori (memory ordering), pertumbuhan ukuran, dan reklamasi memori yang aman. Tanpa model pemilik-tunggal/banyak-pencuri yang eksplisit dan rencana reklamasi, kode "lock-free" yang ditulis manual lebih rentan menduplikasi pekerjaan atau menggunakan memori yang sudah dibebaskan dibandingkan baseline yang terkunci.

Biaya push/pop lokal yang diharapkan adalah O(1); pencurian bernilai O(1) atau O(batch), sedangkan memindai V korban secara naif memakan biaya O(V). Ruang yang dibutuhkan adalah O(T + N), di mana T adalah pekerjaan yang belum selesai dan N adalah jumlah worker. I/O yang memblokir membatalkan asumsi bahwa worker yang idle selalu dapat mencuri, jadi isolasi pekerjaan pemblokir atau batasi jumlahnya.

Contoh jawaban berkualitas tinggi

Saya akan memberikan versi terkunci yang benar terlebih dahulu lalu mendiskusikan peningkatan ke lock-free. Setiap worker memiliki deque privat; pemilik menggunakan LIFO di bagian bawah dan pencuri menggunakan FIFO di bagian atas, dengan sinkronisasi terpisah antara pemilik dan pencuri. Sebuah tugas mulai dieksekusi hanya setelah pop atau pencurian berhasil, yang merupakan titik linearisasi klaimnya.

Pengiriman dan shutdown adalah masalah yang terpisah. Shutdown menolak root baru, lalu menunggu hingga pekerjaan yang belum selesai mencapai nol. Jika tugas yang sedang berjalan dapat membuat tugas anak, kontrak pengosongan (draining) harus secara eksplisit mengizinkan dan menghitungnya; jika tidak, tolak tugas tersebut dan biarkan tugas menangani errornya. Worker menunggu pada condition variable atau semafor alih-alih melakukan spin, dan eksepsi tugas ditangkap dalam future dan metrik alih-alih lolos dari loop worker.

Saya akan melepaskan tugas pendek dan panjang secara simultan menggunakan barrier, memastikan eksepsi exactly-once dan pencurian yang sebenarnya, serta memverifikasi bahwa antrean terkuras habis. Kemudian saya akan menginjeksi pembuatan tugas anak, shutdown selama pencurian, pekerjaan pemblokir, eksepsi tugas, dan panggilan shutdown yang berulang. Hanya jika kontensi dan hasil pengukuran membenarkannya, saya akan mengganti baseline dengan deque Chase–Lev yang pengurutan memori dan reklamasinya telah dispesifikasikan.

Kesalahan umum

• Satu antrean global → setiap worker bersaing pada satu lock → gunakan deque per-worker dan biarkan mekanisme pencurian menangani ketidakseimbangan.
• Mengecek tidak kosong dan melakukan pop secara terpisah → pencuri lain mengubah antrean di antara operasi → jadikan penghapusan yang berhasil sebagai klaim atomik.
• Keluar saat antrean terlihat kosong selama shutdown → induk yang sedang berjalan dapat membuat tugas anak segera setelahnya → gunakan status draining dan invarian pekerjaan tertunda.
• Membiarkan eksepsi tugas lolos dari loop worker → satu tugas buruk mengurangi paralelisme → tangkap dalam future dan lanjutkan penjadwalan.
• Menulis kode lock-free sendiri tanpa aturan memori atau reklamasi → pekerjaan duplikat atau use-after-free → validasi semantik terkunci terlebih dahulu dan ikuti algoritma yang terbukti.
• Selalu mencuri dari satu korban → antrean yang padat terus mengalami kontensi → kombinasikan permulaan acak, backoff, dan batch terbatas dengan metrik.

Pertanyaan lanjutan dan jawaban

Bagaimana cara Anda mencegah pekerjaan yang memblokir menghentikan semua worker?

Bagaimana cara Anda membuktikan bahwa shutdown tidak akan menghilangkan tugas anak?

Kapan pencurian batch lebih baik daripada pencurian tugas tunggal?

I/O yang memblokir harus ditempatkan di pool terpisah atau mekanisme managed-blocking terhitung; pencurian hanya memindahkan pekerjaan yang sedang menunggu. Pembuktian shutdown menggunakan state machine dan invarian counter: hentikan root baru, daftarkan tugas anak sebelum menyelesaikan induk, dan hentikan hanya dalam status draining dengan nol pekerjaan tertunda. Pencurian batch membantu ketika pembuatan tugas padat dan setiap sinkronisasi berbiaya mahal; untuk antrean kecil atau tugas-tugas kecil, biaya pemindahan dan keadilan dapat melebihi penghematannya.