Come affrontare adeguatamente la fame

6

Sto cercando di trovare un modo per evitare la fame nel mio programma, un problema produttore / consumatore (due thread, uno per ogni ruolo) con quattro livelli di priorità (quattro deque s).

In sostanza, il thread del consumatore rimuove sempre dalla massima priorità deque finché non viene lasciato nulla, piuttosto che rimuove la priorità media deque e così via.

Potrebbe esserci fame: cosa succede se la massima priorità deque è sempre piena di elementi, il thread di consumo è occupato per rimuoverli e gli elementi a bassa priorità non vengono mai prelevati?

Mi è stato detto di implementare una sorta di meccanismo di invecchiamento, controllando se gli elementi hanno speso troppo tempo in un deque : in questo caso, prendili, azzeri il loro timer e inseriscili in deque con priorità più alta.

Sembra bello, quindi ho iniziato a creare un thread del controller che potesse svolgere questo compito: durante la progettazione sono sorte alcune domande e non riesco a trovare una risposta.

Come posso procedere a scoprire il timeout ottimale dopo il quale il thread del controller rimuove l'elemento e lo inserisce in un deque con priorità più alta? Quanti elementi con timeout scaduto verranno rimossi (uno è troppo piccolo, tutti gli elementi potrebbero essere troppi se deque ha tutti gli elementi con timeout scaduto)?

EDIT : ho provato l'approccio di UmNyobe, ecco un possibile output (ogni numero è il numero di elementi in quel deque ; il numero più a sinistra è la massima priorità deque , più a destra il basso priority deque ):

// max prio deque has 3 elements, low prio has 7, others are empty

// first round: remove 4 elements with max prio and one with min prio
3 0 0 7 
2 0 0 7
1 0 0 7
0 0 0 7
0 0 0 6

// second round: remove one element with min prio
0 0 0 5

// third round: remove one element with min prio
0 0 0 4

// fourth round: remove one element with min prio
// and so on...
0 0 0 3

0 0 0 2

0 0 0 1

0 0 0 0

Sto implementando un proxy con priorità alle connessioni: ad esempio, il caricamento di un video di YouTube mostrerà subito il giocatore (perché ho dato la massima priorità, e rimuovendo 4 elementi con il prio max alla volta il video è presto mostrato) ma gli elementi stilistici della pagina impiegheranno un po 'di tempo per essere caricati (perché ho dato loro la priorità minima, e rimuovendo un elemento con basso prio alla volta, i pulsanti e le anteprime delle immagini impiegheranno un po' per apparire).

Forse dovrei invertire l'ordine di rimozione: ogni X round, rimuovi uno con max prio e quattro con basso prio, non lo so.

EDIT 2 : forse avrei dovuto indicare che gli elementi memorizzati in deque sono richieste di connessione. Quindi, le connessioni in sospeso per lo streaming video hanno il prio max e saranno rimosse 4 contemporaneamente da deque ; le connessioni in sospeso per gli elementi stilistici hanno un valore minimo e verranno rimosse 1 contemporaneamente.

Quello che voglio dire è che gli elementi memorizzati in deque non sono task, thread o altri lavori indipendenti che faranno qualcosa: sono ciò di cui è fatta una pagina web. Quindi, è meglio dare meno priorità agli elementi stilistici della pagina web, ma dovrebbero essere caricati poco dopo (immediatamente?). Vengono caricati gli elementi max prio.

    
posta elmazzun 13.07.2016 - 15:50
fonte

3 risposte

7

Il meccanismo di pianificazione che hai descritto è Pianificazione preventiva a priorità fissa .

Se sai che esiste la possibilità che la coda di priorità massima sia sempre piena, allora stai usando il meccanismo sbagliato, a causa della fame come hai descritto.

È possibile prevenire la fame utilizzando un altro programmatore. Ad esempio, puoi dire che elabori al massimo f(priority) elementi in una determinata coda prima di considerare l'elemento di una coda con priorità più bassa (questa è una programmazione Round-robin ).

  • f può essere lineare: f(p) = p . Elaboro al massimo 4 articoli di priorità 4 (in alto), quindi al massimo 3 di priorità 3, ..., 1 di priorità 1.
  • f può essere esponenziale: f(p) = 2^(p-1) . Elaboro al massimo 8 elementi di priorità 4 (in alto), quindi al massimo 4 di priorità 3, quindi al massimo 2 di priorità 2, ..., 1 di priorità 1.

Misuri questo round robin usando la frequenza prevista di esecuzione di ciascuna priorità.

Prendiamo il caso esponenziale e assumiamo che ci siano molte attività in attesa su ogni coda. Pianifichiamo 8 top, 4 upper-middle, 2 lower-middle, 1 low, 8 top, ecc ... Ogni round ha 8 + 4 + 2 + 1 = 15 task, quindi le attività prioritarie richiedono 8/15 di tempo per il consumatore , prossimo 4/15, prossimo 2/15, prossimo 1/15.

    
risposta data 13.07.2016 - 18:44
fonte
3

Fondamentalmente stai privilegiando una funzione di due variabili, come pricePaid*A + waitingTime*B . Questa è una strategia perfettamente sensata.

Supponiamo che tu stia vendendo biglietti e che il prezzo pagato dalla gente li collochi in una delle code: alta, media, bassa. Potresti considerarlo come una singola coda di priorità ordinata, dove la priorità è alta, media o bassa. All'interno di ciascun gruppo di priorità vengono ordinati in base al tempo, pertanto è possibile considerare l'orario di arrivo negativo come una priorità secondaria, in modo che, al momento di servirne uno, venga utilizzata la priorità più vecchia. Questo è quello che stai facendo ora. La tua priorità è una funzione di due variabili, come pricePaid*A + waitingTime*B dove A è così grande, o B è così piccola, che nessuna quantità di waitingTime può compensare il fatto che qualcun altro abbia pagato un prezzo più alto.

Tutto quello che sto dicendo è, non rendere A così grande, o B così piccolo. Per farlo, scegli la struttura dei dati in modo che quando rimuovi qualcuno da esso, scegli sempre quello con la priorità più alta.

Un altro modo per vederlo: avere una singola coda di priorità, ordinata per ora di arrivo. Tuttavia, ogni incremento di pricePaid equivale a essere arrivato qualche volta in anticipo. Come se qualcuno pagasse $ 20, è come se avessero pagato solo $ 10, ma sono arrivati una settimana prima. In questo modo, le persone che hanno pagato solo $ 10, ma sono arrivate due settimane prima, sarebbero state servite per prime.

    
risposta data 13.07.2016 - 16:54
fonte
2

La prima cosa da capire è che la situazione che descrivi (alcuni articoli non vengono mai elaborati) può sorgere solo se semplicemente non hai la capacità di gestire il volume delle richieste. Se hai la capacità di gestire il volume previsto di richieste in un determinato periodo di tempo, sarai in grado di gestire tutte le richieste. Questa è una tautologia. La modifica dell'ordine delle richieste non modificherà la tua capacità o il volume (a meno che l'ordine in cui vengono elaborati modifichi in qualche modo l'elaborazione).

Escludendo ciò, potresti avere una situazione in cui hai un orario di lavoro intenso e alcune transazioni con priorità inferiore devono attendere troppo a lungo. In questo caso, il tuo modello non è corretto. La struttura del tuo attuale approccio è corretta solo se gli elementi con la priorità più alta hanno sempre una priorità più alta rispetto agli altri elementi. Gli articoli prioritari più alti dovrebbero essere elaborati prima sopra gli articoli con priorità più bassa, a prescindere da cosa. Quello che stai dicendo qui è che vuoi gestire gli articoli con priorità più bassa prima degli elementi con priorità più alta se sono vecchi. Ciò implica che probabilmente dovresti strutturare la tua priorizzazione in base agli SLA. Cioè, ogni transazione ha un tempo di risposta previsto. A quel punto, si eseguono le transazioni in base a quando sono dovute. I tuoi attuali alti livelli di priorità si traducono quindi in SLA brevi e priorità inferiori in tempi di risposta più lunghi.

    
risposta data 14.07.2016 - 20:08
fonte

Leggi altre domande sui tag