Riassunto analitico
Lavori recenti nella letteratura di problemi di scheduling multiprocessore soft real-time (SRT) cercano di definire upper bound ai ritardi accumulabili dal sistema per vari algoritmi di schedulazione, tra i quali, il più studiato, l'algoritmo di global earliest-deadline-first (G-EDF).
Raggiungere bound particolarmente stretti è importante per i problemi di scheduling SRT: se il ritardo è eccessivamente sovrastimato, alcuni carichi di lavoro schedulabili potrebbero non essere riconosciuti come tali e non essere eseguiti.
Vista la natura combinatoria delle configurazioni di assegnamento dei carichi di lavoro ai processori, spesso i bound più stringenti richiedono elevata complessità computazionale per essere calcolati.
Questa tesi affronta lo studio di un caso particolare del generico problema di schedulazione, in cui i carichi di lavoro sono regolari, non vi è preemption e i processori sono di uguale velocità.
La regolarità introdotta fa si che la politica di scheduling studiata, G-EDF, si sovrapponga ad altre politiche di scheduling basate su FIFO.
Si osserva che l'assegnamento dei job ai processori sotto queste condizioni è suddiviso in un periodo transitorio e, successivamente, si stabilizza in un andamento periodico.
I risultati ottenuti dimostrano che il ritardo è sempre inferiore alla lunghezza di un job e delineano varie condizioni in cui non è generato ritardo o il ritardo massimo è raggiunto alla fine del primo periodo.
Infine si congettura una formula che indichi con esattezza il ritardo massimo accumulabile nel sistema.
|
