Bagaimana cara terbaik merancang antrian pekerjaan dengan kendala?

Pertimbangkan situasi berikut:

• Anda memiliki program yang menciptakan banyak 'pekerjaan' yang perlu diproses dan menempatkannya dalam antrian.
• Anda memiliki program pekerja lain yang mengambil 'pekerjaan' berikutnya sehingga mereka dapat memproses pekerjaan itu.
• Setiap pekerjaan memiliki kategori.
• Mungkin ada sejumlah kategori.
• Dua pekerjaan yang memiliki kategori yang sama tidak dapat diproses secara bersamaan oleh pekerja yang terpisah.
• Seorang pekerja dapat memproses satu pekerjaan pada suatu waktu.

Antrian tradisional tidak akan berfungsi dalam situasi ini karena ada kemungkinan beberapa pekerjaan dari kategori yang sama akan diproses secara bersamaan, yang tidak diizinkan.

Anda bisa meminta pekerja memeriksa pekerjaan yang diambilnya dan melihat apakah kategori pekerjaan itu memiliki pekerja lain yang saat ini sedang memprosesnya, dan jika demikian kirimkan kembali pekerjaan ke dalam antrian untuk diproses di lain waktu. Ini sepertinya cara yang tidak efisien untuk menyelesaikan masalah ini. Apakah ada struktur data atau pola desain yang dapat menyelesaikan masalah ini?

Jika Anda perlu klarifikasi lebih lanjut, beri tahu saya.

Ada dua bagian untuk masalah ini.

Satu: daftar kategori yang tidak diketahui yang mungkin.

Dua: komunikasi antarproses antara pekerja untuk mencegah dua pekerjaan dari kategori yang sama diproses secara bersamaan.

Jika Anda memiliki daftar kategori yang dikenal, Anda dapat memiliki satu antrian dan satu pekerja per kategori.

Dengan kategori yang tidak diketahui, Anda masih dapat memiliki antrian per kategori, tetapi memiliki pekerja antrian per kategori mengharuskan Anda untuk memantau semua antrian dan memunculkan pekerja baru ketika kategori baru muncul.

Ini dapat dicapai dengan pekerja 'master' yang membagikan pekerjaan

Semua pekerjaan masuk dalam antrian 'master'.

pekerja kategori membuat antrian pribadi dan mendaftar dengan master yang tersedia untuk bekerja.

pekerja master mengambil pekerjaan, memeriksa kategori, memeriksa pekerja yang tersedia dan memberikan pekerjaan kepada salah satu dari mereka dengan memasukkannya ke dalam antrian pribadi mereka.

Master dapat melacak kategori yang ditugaskan untuk pekerja.

master mengambil pekerjaan berikutnya, kategori yang sama dan pekerja masih sibuk sehingga menempatkan pekerjaan dalam kategori antrian holding spesifik

master mendapatkan pekerjaan berikutnya, itu adalah kategori baru sehingga ditugaskan ke pekerja kategori lain.

Pekerja kategori menyelesaikan pekerjaan dan reregister untuk bekerja

master memeriksa memegang antrian dan master antrian pekerjaan berikutnya dan menugaskan pekerja kategori yang tersedia.

Jika pekerja kategori mogok selama pekerjaan itu tidak akan mendaftar ulang. Jadi master dapat memiliki beberapa logika batas waktu di mana ia akan menyerah dan mulai menugaskan kategori ke pekerja lain.

Anda juga harus berhati-hati untuk hanya memiliki satu pekerja master tunggal pada waktu tertentu. Ini menunjukkan kunci eksklusif pada antrian utama dari beberapa jenis

Kelemahan dari proposal Anda yang tidak efisien muncul ketika ada 2 pekerjaan untuk suatu kategori. Sekarang satu berfungsi..dan semua orang sibuk menunggu.

Anda dapat membuat ini cukup baik dengan meminta pekerja memindai melalui antrian untuk tugas selanjutnya yang dapat dilakukan, lalu mengembalikan semuanya kecuali itu ke antrian jika mereka menemukannya. Kembalikan semuanya secara bergantian, lalu tidur. Jika tidur memiliki keacakan dan eksponensial backoff, "menunggu sibuk" tidak akan terlalu sibuk.

Untuk pendekatan yang lebih efisien, seorang pekerja yang mengambil pekerjaan bertanggung jawab untuk melakukan kategori itu sampai tidak ada hal lain dari kategori itu yang tersisa untuk dilakukan. Kemudian Anda kembali menjadi pekerja biasa. Tetapi ada beberapa kehalusan.

Untuk melihatnya, mari kita asumsikan kita bisa trydan releasemengunci (keduanya bukan pemblokiran) dan operasi antrian kita adalah add, getdan is_emptydengan getmenjadi operasi blok dan tunggu.

Kami akan menganggap antrian umum, dan kemudian untuk setiap kategori antrian dan kunci.

Inilah aliran pekerja dasar.

while obj = get from main queue:
    if try category lock:
        do obj job
        do_whole_category_queue()
    else:
        add obj to category queue
        if try category lock:
            do_whole_category_queue()

dimana

procedure do_whole_category_queue
    while not category queue is_empty:
        obj = get from category queue
        do obj job
    release category lock
    if not is_empty category queue:
        if try category lock:
            do_whole_category_queue()

Perhatikan jabat tangan penguncian yang cermat di sini. Pekerja menguji kunci, dan jika terkunci menambah pekerjaan ke antrian. Tetapi kemudian Anda harus menguji kunci lagi untuk memverifikasi bahwa masih merupakan tanggung jawab orang lain untuk benar-benar melakukan pekerjaan itu. Kalau-kalau pekerja kategori selesai saat Anda sedang melakukan manipulasi antrian.

(Ini adalah semacam detail penguncian yang sering dikacaukan oleh orang. Kesalahan tidak mungkin untuk mereproduksi dengan andal, tetapi mengacaukan secara acak dan undebuggably dalam produksi ...)