+ Rispondi al Thread
Visualizzazione dei risultati da 1 a 7 su 7

Discussione: Gestione coda con priorità

  1. #1
    Luogo
    marte
    Post
    635
    Blogs
    2

    Gestione coda con priorità

    Ciao a tutti!
    Ho qualche problema nel capire come venga gestita la coda di priorità nel qualcaso che l'aggiunta dell'elemento sia infinita.
    Se io ad esempio ho una coda e ci aggiungo 3 elementi,li inserirò in base alla loro priorità ad esempio 3 2 1:
    codice:
    coda-> e.prio=3 -> e.prio=2 -> e.prio=1
    ok fin qui ci sono.
    ora io soddisfo il primo elemento della coda dato che ha priorità maggiore.ora supponiamo che tale elemento non abbia finito e debba rientrare nella coda,avendo priorità 3 dovrebbe tornare in testa alla coda, ma in questo modo non verranno mai soddisfatti gli altri elementi aventi priorità inferiore nella lista se non quando la priorità maggiore termini il proprio compito.
    Se invece la inserisco in fondo alla coda allora il discorso di priorità va a farsi friggere.Si otterrei un ordine di esecuzione ma non un reale ordine di priorità.
    Per spiegarmi meglio mostro come ho implementato la mia coda di priorità:

    -quando inserisco in coda per la prima volta inserisco in base alla priorità
    -eseguo x volte gli elementi della stessa priorità e li accodo alla lista
    -loop

    otterrò quindi:
    codice:
    p = priorita;
    e = esecuzioni;
    
    coda:inserisci elemento a prio = 2;
    coda->
    [0]a.p = 2 -- a.e=0 
    
    coda:inserisci elemento b prio = 1;
    coda->
    [0]a.p = 2 -- a.e=0 
    [1]b.p = 1 -- b.e=0 
    
    coda:inserisci elemento c prio = 3;
    coda->
    [0]c.p = 3 -- c.e=0 
    [1]a.p = 2 -- a.e=0 
    [2]b.p = 1 -- b.e=0 
    
    coda:inserisci elemento d prio = 3;
    coda->
    [0]d.p = 3 -- d.e=0 
    [1]c.p = 3 -- c.e=0 
    [2]a.p = 2 -- a.e=0 
    [3]b.p = 1 -- b.e=0 
    
    
    coda:execute loop
    coda->d.p = 3 -- d.e=0
    [0]c.p = 3 -- c.e=0 
    [1]a.p = 2 -- a.e=0 
    [2]b.p = 1 -- b.e=0 
    
    coda:execute loop
    coda->c.p = 3 -- c.e=0
    [0]d.p = 3 -- c.e=1 
    [1]a.p = 2 -- a.e=0 
    [2]b.p = 1 -- b.e=0 
    
    coda:execute loop
    coda->d.p = 3 -- d.e=1
    [0]c.p = 3 -- c.e=1 
    [1]a.p = 2 -- a.e=0 
    [2]b.p = 1 -- b.e=0 
    
    coda:execute loop
    coda->c.p = 3 -- c.e=1
    [0]d.p = 3 -- d.e=2 
    [1]a.p = 2 -- a.e=0 
    [2]b.p = 1 -- b.e=0
    
    coda:execute loop
    coda->d.p = 3 -- d.e=2
    [0]c.p = 3 -- c.e=2 
    [1]a.p = 2 -- a.e=0 
    [2]b.p = 1 -- b.e=0 
     
    coda:execute loop
    coda->c.p = 3 -- c.e=2
    [0]a.p = 2 -- a.e=0 
    [1]b.p = 1 -- b.e=0 
    [2]d.p = 3 -- d.e=0 
    
    coda:execute loop
    coda->a.p = 2 -- a.e=0
    [0]b.p = 1 -- b.e=0 
    [1]d.p = 3 -- d.e=0 
    [2]c.p = 3 -- c.e=0 
    
    coda:execute loop
    coda->a.p = 2 -- a.e=1
    [0]b.p = 1 -- b.e=0 
    [1]d.p = 3 -- d.e=0 
    [2]c.p = 3 -- c.e=0 
    
    coda:execute loop
    coda->b.p = 1 -- b.e=0
    [0]d.p = 3 -- d.e=0 
    [1]c.p = 3 -- c.e=0 
    [2]a.p = 2 -- a.e=0 
    
    infinite loop...
    ecco lo srotolamento della coda,esiste un algoritmo che fa al caso mio?
    Io l'ho gia scritto ma penso che esista già qualcosa di piu performante e bello.
    Spero su un pò di documentazione da leggere.
    Easy framework per il linguaggio C.
    vbextreme hack your life

  2. #2
    L'avatar di +m+
    +m+
    +m+ non è in linea Scribacchino
    Post
    922
    Scusa ma la domanda si può sintetizzare così: una lista "bruta" a priorità può starvare?
    Sì, ovviamente.

    Come si attenua il problema? Ad esempio se la priorità del task appena eseguito è massima, diminuendola fino a quella del task n-1 più prioritario.
    Oppure con RR o chi più ne ha ne metta, comprese liste a token e così via.
    Specificato il problema => si sceglie la strada più adatta

  3. #3
    Luogo
    marte
    Post
    635
    Blogs
    2
    bhé quello di abbassare la priorita non ci avevo pensato, io aumento una variabile per ogni esecuzione del codice ed arrivato al valore di priorita torno in coda,il mio metodo forse privilegia troppo infatti con 3 2 1 io eseguo prima tre volte 3 poi due volte 2 e una volta 1.
    Col tuo metodo otterrei una volta 3 una volta 2 una volta 3 una volta 2 una volta 1 una volta 3
    3 2 3 2 1 3
    .
    L'algoritmo consiste in un thread che si mette a riposo,appena si inserisce un elemento nella lista che sara una funzione ritornante -1 quando finisce 0 quando continua e >0 sara il tempo minimo in ms di attesa fino al sucessivo richiamo alla funzione.
    Un qualsiasi elemento con priorita <0 terminera il thread.
    La gestione del tempo é gia assai complicata, infatti deve riuscire a caocolare se puo addormentarsi e se si per quanto tempo,deve calcolara la media dei pseudo processi e decidere se anticipare l'esecuzione del processo a timer e modificarne quindi le proprieta.
    Il thread non avendo nessun controllo sulla funzione non puo sospendere o riavviare, puo solo decidere come gestire la coda.
    Provero anche il tuo consiglio per vedere se diventa piu reattiva la coda.
    Easy framework per il linguaggio C.
    vbextreme hack your life

  4. #4
    L'avatar di +m+
    +m+
    +m+ non è in linea Scribacchino
    Post
    922
    Bhè magari dettaglia meglio, perchè gli algoritmi di scheduling sono tanti e noti, da un bel po', per ogni situazione con pregi e difetti.

    In estrema sintesi: meccanismi a priorità dinamici, ovvero con inserimento di nuovi elementi, possono provocare starvation, c'è poco da fare.
    Poi in certi casi questo è ammissibile, in altri no.

    Se sei nel caso "no", ovvero gli elementi non possono starvare, allora devi eliminare direttamente il concetto di lista a priorità "bruta", per andare verso meccanismi più o meno fair, tipo il classico round robin, o anche un più stringente token di esecuzione (se ti serve una sorta di qos).

    Per la lista, come detto, ti serve una politica di aging, che aumenti (o diminuisca) la priorità

    Da quanto descrivi direi che non ha preemption

  5. #5
    Luogo
    marte
    Post
    635
    Blogs
    2
    no assolutamente,non ho la possibilità di interrompere il processo.
    il rr non fa al caso mio,è il primo che ho tentato di implementare,non avendo però accesso diretto al processo l'unico metodo era memorizzare il tempo di un processo,se superiore a 200ms memorizzare solo 200ms e se inferiore ripetere il processo fino al raggiungimento della media di tutti i processi.
    In buona sostanza venivano ripetuti piu volte i processi con priorità minore ma con tempo di velocità minore. E allora a quel punto poco sarebbe servita una coda di priorità,che nel mio caso è assolutamente necessaria.
    L'aging mi sembra molto un tappabuchi.Infatti se non ho capito male funziona che i processi vengono sempre rieseguiti in modo ordinato ma poi ogni tot si aumenta la priorità dei piu bassi.

    Penso che la tua prima soluzione forse è la migliore.
    Easy framework per il linguaggio C.
    vbextreme hack your life

  6. #6
    L'avatar di +m+
    +m+
    +m+ non è in linea Scribacchino
    Post
    922
    La mia risposta è proprio un esempio di politiche di aging, che possono aumentare o diminuire la priorità sulla base delle condizioni più fantasiose che ti possono venire in mente.
    In generale, comunque, l'idea è che una volta che "tizio" è stato eseguito, non possa rimanere indefinitamente come il candidato con maggiore priorità.
    C'è chi gli azzera la priorità, chi gliela dimezza, chi la mette < del "secondo candidato" (in questo modo viene eseguito comunque mooolte volte in più), algoritmi del banchiere, del fornaio, della lotteria... tra un po' pure del pescivendolo

    Comunque se non hai preemption la versione superbreve l'ho già esposto: qualsiasi politica "pura" porta (può portare) a starvation.
    Ci sono approcci di tutti i tipi, ad esempio scheduler a code multiple (gestite in round robin), ognuna delle quali con una "sua" politica più o meno strana, o addirittura il contrario (code a priorità con liste gestite RR)

    Ma alla fine, qual'è il tuo obiettivo (non è una domanda retorica, è LA domanda)?
    Vuoi tempo di attesa, di turnaround, throughput?
    Puoi stimare (alla SJF) il prossimo burst di esecuzione, magari come media mobile passata?
    Hai vincoli sullo scheduling medesimo (complessità e tempo impiegato)?
    Cosa puoi memorizzare? Ad esempio se puoi tenere traccia del tempo di attesa puoi aumentare la priorità all'aumentare di questa (aging)
    Cosa succede se un job non termina? Sei sicuro che lo farà sempre?

  7. #7
    Luogo
    marte
    Post
    635
    Blogs
    2
    il blocco di un job non arrecherebbe danni,verrebbe terminato il thread e riavviato se le condizioni lo permettono,ovvero che il lavoro che si stava eseguendo non era allacciato in nessun modo ai lavori in coda.
    In pratica é un thread che esegue funzioni piu o meno veloci.
    Come ben saprai non é molto semplice saltare fuori da una funzione e riuscire ad entrarci di nuovo dentro nell'esatta posizione, considera che le funzioni che uso sono di una libreria di terze parti e nn posso toccare il codice.
    A questo punto e con queste armi non é sensato parlare di tempi di esecuzione ma solo di priorita, assicurarsi quindi che tutti vengano eseguiti e che vengano rispettate le priorita.
    LA domanda dunque era come poter gestire le priorita in coda.aggiungerei che siano proporzionali le escuzioni in base alle priorita.
    Penso che la tua prima risposta vada benissimo,o comunque ho capito che ero sulla strada giusta ed in linea di massima ho capito la priorita.

    Posso memorizzare e cronometrare cio che voglio,ma l'algoritmo é gia molto complicato perche un lavoro potrebbe richiedere di essere riavviato tra 1s anche se ha priorita 1000.
    Come gia detto inizialmente valutavo anche i tempi di esecuzione ed attesa,ma variando da 100ms a 5s il risultato ottenuto é stato quello di rendere inutili le priorita.Io invece devo gestire la priorita a prescindere del tempo di esecuzione.

    Se ad esempio volessi scrivere su disco un terabyte di dati e volessi dargli la massima priorita fregandome del refresh grafico allora questo deve avvenire,di controparte se l'operazione non mi interessa e voglio assicurarmi di poter eseguire altri compiti allora questo deve avvenire.
    Priorita alle priorita dunque.
    Easy framework per il linguaggio C.
    vbextreme hack your life

+ Rispondi al Thread

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi