Come progettare al meglio una coda di lavoro con vincoli?

Question

Come progettare al meglio una coda di lavoro con vincoli?

#1 da (4 voti)
#2 da (2 voti)

8

Considera la seguente situazione:

Hai un programma che crea numerosi "lavori" che devono essere elaborati e li inserisce in una coda.
Hai altri programmi di lavoro che catturano il successivo "lavoro" in linea in modo che possano elaborare quel lavoro.
Ogni lavoro ha una categoria.
Potrebbe esserci un numero qualsiasi di categorie.
Due lavori che hanno la stessa categoria non possono essere elaborati contemporaneamente da lavoratori separati.
Un lavoratore può elaborare un lavoro alla volta.

Una coda tradizionale non funzionerebbe in questa situazione perché esiste la possibilità che più processi della stessa categoria vengano elaborati contemporaneamente, il che non è consentito.

Potresti fare in modo che il lavoratore verifichi il lavoro che afferra e vedere se quella categoria di lavori ha un altro lavoratore che sta attualmente elaborando su di esso, e in tal caso reinserire il lavoro nella coda per essere elaborato in un secondo momento. Questo sembra un modo inefficiente per risolvere questo problema. Esistono strutture dati o modelli di progettazione che possono risolvere questo problema?

Se hai bisogno di ulteriori chiarimenti, faccelo sapere.

design-patterns data-structures queue

posta merp 22.04.2016 - 19:28

fonte

2 risposte

Leggi altre domande sui tag design-patterns data-structures queue

Previene l'abuso sull'endpoint dell'API REST Ci sono attività che richiedono molto meno lavoro con Ruby rispetto a C # 4.0?

score 4 · Answer 1

Ci sono due parti per questo problema.

Uno: l'elenco sconosciuto di possibili categorie.

Due: comunicazione interprocesso tra i lavoratori per evitare che due processi della stessa categoria vengano elaborati contemporaneamente.

Se disponi di un elenco di categorie noto, puoi avere una coda e un lavoratore per categoria.

Con categorie sconosciute, puoi ancora avere una coda per categoria, ma avere un addetto alla coda per categoria richiede di monitorare tutte le code e attivare nuovi lavoratori quando viene visualizzata una nuova categoria.

Questo può essere ottenuto con un lavoratore "principale" che distribuisce i lavori

Tutti i lavori vanno nella coda "master".

l'operatore di categoria crea una coda privata e registra con il master come disponibile per il lavoro.

il lavoratore principale raccoglie i lavori, controlla la categoria, controlla i lavoratori disponibili e assegna il lavoro a uno di essi inserendolo nella sua coda privata.

Il master può tenere traccia della categoria assegnata al lavoratore.

il master preleva il lavoro successivo, è della stessa categoria e il lavoratore è ancora occupato, quindi inserisce i lavori in una coda di attesa specifica della categoria

master ottiene il lavoro successivo, è una nuova categoria, quindi lo assegna a un altro operatore di categoria.

L'operatore di categoria completa il lavoro e registra nuovamente il lavoro

il master controlla le code di attesa e la coda principale il prossimo lavoro e assegna agli operatori di categoria disponibili.

Se un lavoratore di una categoria si arresta in modo anomalo durante un lavoro, non si registra nuovamente. Quindi il master può avere una logica di timeout in cui si arrenderà e inizierà ad assegnare le categorie a un altro worker.

Devi anche fare attenzione a avere un solo master in qualsiasi momento. Ciò annulla un blocco esclusivo sulla coda principale di qualche tipo

score 2 · Answer 2

Lo svantaggio della tua proposta inefficiente arriva quando ci sono 2 lavori per una categoria. Ora si sta lavorando .. e tutti gli altri stanno facendo un'attesa impegnativa.

Puoi renderlo abbastanza buono facendo in modo che i lavoratori eseguano la scansione della coda per una prossima attività eseguibile, quindi restituiscono tutto tranne quella alla coda se ne trovano una. In alternativa, restituire tutto, quindi dormire. Se il sonno ha una certa casualità e un backoff esponenziale, la "busy waiting" non sarà troppo occupata.

Per un approccio più efficiente, un lavoratore che afferra un lavoro è responsabile di fare quella categoria fino a quando non viene lasciato nient'altro da quella categoria. Quindi torni ad essere un lavoratore regolare. Ma ci sono alcune sottigliezze.

Per vederle, supponiamo che possiamo try e release locks (entrambi non bloccanti) e le nostre operazioni di coda sono add , get e is_empty con get come blocco e attendi operazione.

Assumeremo una coda generale, quindi per ogni categoria una coda e un blocco.

Ecco il flusso di lavoro di base.

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()

dove

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()

Nota l'attenta stretta di mano di blocco qui. L'operatore verifica il blocco e, se bloccato, aggiunge il lavoro alla coda. Ma poi devi testare nuovamente il blocco per verificare che sia ancora responsabilità di qualcun altro fare effettivamente il lavoro. Nel caso in cui l'operatore della categoria abbia finito mentre stavi facendo la manipolazione della coda.

(Questo è il tipo di dettagli di blocco che spesso le persone sbagliano: l'errore è impossibile da riprodurre in modo affidabile, ma si verifica in modo casuale e indebito nella produzione ...)