Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Sistemi informatici > Schedulazione real-time > Flashcards

Schedulazione real-time Flashcards

1
Q

Parametri che caratterizzano un problema di schedulazione

A

J = {Ji } : insieme dei processi aperiodici
tau = { tau i } : insieme dei processi periodici
g : grafo dei vincoli di precedenza
M : misura di prestazione

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Misure di prestazione

A
  • Ammissibilità
  • Minimizzazione Lmax
  • Minimizzazione Nlate
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Lmax

A

Lateness massima: massimo tra le lateness Li di ogni processo i-esimo

Li = fi - di (tempo di fine - deadline)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Nlate

A

Numero di processi che terminano oltre la propria deadline

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Funzione h(t) e insieme delle possibili soluzioni

A
  • Dato un problema di schedulazione, la funzione h(t) restituisce, per ogni istante di tempo, il processo da eseguire.
  • Una qualsiasi soluzione del problema si dice schedulazione.
  • Tra tutte le schedulazioni, ne esistono alcune che soddisfano i vincoli temporali, dette schedulazioni ammissibili.
    Un problema che ammette una schedulazione ammissibile si dice problema schedulabile.
  • Tra le schedulazioni ammissibili, ce ne sono alcune ottime per una certa misura di prestazione
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Problemi schedulabili: implicazioni

A

MIN Lmax - > Schedulazione ammissibile ( Lmax < = 0 )
MIN Nlate - > Schedulazione ammissibile ( Nlate = 0 )
MIN Lmax - > MIN Nlate

Non valgono le implicazioni inverse

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Problemi non schedulabili: implicazioni

A

MIN Lmax - > Lmax > 0
MIN Nlate - > Nlate > 0

Nessuna relazione tra MIN Lmax e MIN Nlate

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Caratteristiche di problemi e algoritmi

A

Algoritmo Preemptive - Non Preemptive :
Dipende dal sistema operativo e dalla natura del problema; in alcuni casi la preemption non è necessaria

Problema Online - Offline :
In un problema Online non si conosce nulla dei processi prima dell’attivazione, i processi si attivano a Runtime. In un certo istante di tempo un problema può essere schedulabile, l’istante successivo no.
In un problema offline a priori si conosce tutto sui processi e si può già sapere se un problema è schedulabile

Algoritmo Dinamico - Statico :
In un algoritmo statico i processi hanno priorità definita a priori che non può essere cambiata. In un algoritmo dinamico la priorità assegnata ai processi può essere cambiata durante l’esecuzione.

Algoritmo Ottimale - Euristico :
Un algoritmo ottimale trova sempre la soluzione ottima. Un algoritmo euristico non dà la garanzia di trovare una soluzione ottima.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Algoritmi per la schedulazione di processi aperiodici

A
  1. Attivazione sincrona:
    - Senza vincoli di precedenza: EDD (Earliest Due Date)
    - Con vincoli di precedenza: LDF (Latest Deadline First)
  2. Attivazione asincrona:
    a. Preemptive:
    - Senza vincoli di precedenza: EDF (Earliest Deadline First)
    - Con vincoli di precedenza: EDF*
    b. Non-Preemptive:
    - Senza vincoli di precedenza: Batley
    - Con vincoli di precedenza: Spring
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

EDD

A

Earliest Due Date

  • Problema: n processi aperiodici, attivazione sincrona, senza vincoli di precedenza
  • Algoritmo: I processi vengono eseguiti in ordine non decrescente di deadline
  • Risultato: Minimizzazione di Lmax - > Ottimo per MIN Lmax
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

EDF

A

Earliest Deadline First

  • Problema: n processi aperiodici, attivazione asincrona, senza vincoli di precedenza, con preemption
  • Algoritmo: Ad ogni quanto temporale viene eseguito il processo ready con la deadline più piccola
  • Proprietà: Ottimo per minimizzazione di Lmax
  • Complessità: è un ordinamento di processi ready, se si usa un quicksort è O(n*log2(n))
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

EDF*

A
  • Problema: n processi aperiodici, attivazione asincrona, con vincoli di precedenza
  • Algoritmo:
    passo 1) problema trasformato in un problema ausiliario senza vincoli di precedenza, equivalente al primo
    passo 2) si applica EDF al problema ausiliario

Modifica del problema:

  • Aumento tempo di attivazione
  • Diminuisco deadline
a1* = MAX { a1, ai* + Ci } Vi diretto successore
d1* = MIN { d1, dk* - Ck } Vk diretto predecessore
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Batley/Spring

A
  • Problema: n processi aperiodici, attivazione asincrona, senza preempion
  • Sistemi senza preemption : primitivi, o problemi con attività non decomponibili
  • Sequenza di processi, ognuno dei quali eseguito dall’inizio alla fine
  • Approccio Branch and Bound:
  • Scelto primo processo da eseguire (in ordine ad esempio di numerazione)
  • Riporto istante in cui mi trovo dopo la sua esecuzione
  • Se ho violato delle scadenze torno indietro, altrimenti proseguo
  • Complessità O(2^n) , non è possibile avere complessità polinomiale
  • Si può migliorare velocità media di soluzione applicando dei criteri di scelta, ad esempio tempo di arrivo e deadline; in ogni caso, però, nel caso peggiore la soluzione si trova in tempo esponenziale
  • Si può decidere di restituire una soluzione entro un tempo prefissato, anche se questa è non accettabile
  • > Algoritmo euristico
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Fattore di utilizzazione

A
  • In problemi con processi periodici, non si può simulare la schedulazione per sapere se un problema è schedulabile
  • Un processo può essere schedulabile in una data attivazione, può non esserlo più nell’attivazione successiva
  • Si potrebbe simulare la schedulazione in un tempo pari al minimo comune multiplo dei periodi, ma questo approccio richiede, nel caso peggiore, un tempo pari al prodotto di tutti i periodi, troppo lungo
  • Si introduce quindi il fattore di utilizzazione U per un problema P:
    U(P) = ∑ Ci/Ti
    Che rappresenta quanto il processo i utilizza rispetto alla durata del suo periodo
  • Se U > 1 , il problema è non schedulabile, indipendentemente dall’algoritmo
  • In base all’algoritmo utilizzato, esiste una soglia massima di U, al di sotto della quale un problema è schedulabile con quell’algoritmo, mentre al di sopra di tale soglia, e con U < 1 , non si può concludere nulla riguardo alla schedulabilità.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Algoritmi schedulazione processi periodici

A
  • Priorità statica
  • Deadline = periodi: RM Rate Monotonic
  • Deadline < periodi: DM Deadline Monotonic
  • Priorità dinamica: EDF
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Def sezione critica

A

Intervallo di tempo lungo da 0 al massimo tra i periodi, nel quale tutti i processi partono con la stessa fase

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

RM

A
  • Rate Monotonic
  • Problema: n processi periodici, Ti = Di, priorità fissa
  • Algoritmo: RM assegna ad ogni processo una priorità pari a 1/Ti, ed esegue preferendo processi a priorità maggiore.
  • Proprietà: RM è ottimo per ammissibilità tra tutti gli algoritmi statici quando tutte le fasi sono uguali
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Condizione di Lyu e Layland

A
  • Condizione sufficiente per la schedulabilità con RM

- U(P) < = N*(2^1/N - 1)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Condizione di Bini e Buttazzo

A
  • Condizione sufficiente per la schedulabilità con RM

PI(i) (Ui +1) < = 2

20
Q

Condizione di schedulabilità con EDF (processi periodici)

A

U(P) < = 1

21
Q

EDF per processi periodici

A

EDF tratta ogni attivazione come se fosse un processo aperiodico

22
Q

DM

A
  • Deadline Monotonic
  • Problema: n processi periodici, priorità statica, Di < = Ti
  • Algoritmo: Le priorità assegnate sono inversamente proporzionali alle deadline relative
  • Proprietà: Ottimo per ammissibilità in tutti i problemi in cui tutte le fasi sono uguali
23
Q

RTA

A
  • Response Time Analysis
  • Misura tempo di risposta Ri di un processo i
  • Ri = Ci + Ii
  • Ii : interferenza dovuta ai processi a priorità maggiore
  • Ii = ∑(j=1, i-1) intsup(Ri/Tj) * Cj

Condizione sufficiente per la schedulabilità

  • Se Ri < = Di Vi allora problema schedulabile in sezione critica
  • Altrimenti: problema non schedulabile in sezione critica (potrebbe esserlo in un altro caso)
24
Q

Algoritmi schedulazione processi misti

A
  • Periodici sempre hard real time
  • Aperiodici hard real time : EDF
  • Aperiodici soft real time:
  • Senza server: Background Scheduling
  • Con server statico: RM + DS (Rate Monotonic + Deferrable Server)
  • Con server dinamico: EDF + TBS (Earliest Deadline First + Total Bandwidth Server)
25
Q

Obiettivo soft real time

A
  • Non è più fondamentale eseguire tutti i processi entro le proprie deadline
  • Obiettivo: minimizzare tempo di risposta medio
  • Tempo di risposta Ri
26
Q

Server: descrizione e vantaggio

A

Processo periodico fittizio, schedulato insieme agli altri periodici in modo che il tempo a lui riservato venga usato per eseguire un processo aperiodico

Vantaggio: assegnando priorità al processo server si può assegnare priorità ai processi aperiodici

27
Q

Background scheduling

A
  • Periodici schedulati con RM
  • Negli istanti di IDLE mandati in esecuzione gli aperiodici, senza considerare le deadline
  • Se si eseguono gli aperiodici in ordine di attivazione, si minimizza il tempo di risposta medio del singolo processo aperiodico
28
Q

RM + DS

A
  • Rate Monotonic + Deferrable Server
  • Inserito processo periodico fittizio: server
  • Server dimensionato (scelti Cs e Ts, e quindi Us) in modo da mantenere il problema schedulabile, minimizzando il tempo di risposta degli aperiodici
  • Regole:
    1) Se ad un istante di tempo t il processo server è prioritario ma non ci sono aperiodici, viene eseguito il periodico a priorità massima dopo il server
    2) Se il processo server non viene eseguito, questo mantiene la propria capacità
29
Q

Condizione di schedulabilità RM + DS

A

Up: fattore di utilizzazione dei processi periodici
Us: fattore di utilizzazione del processo server

Up < = n*(rad(Us+2/2Us+1) -1)

30
Q

Non esistenza server ottimo

A
  • Dimostrato da Tia-Lyu-Shankar
  • Non esiste un server ottimo per tutti i possibili problemi
  • In base al problema si dovrebbe scegliere un server diverso. I problemi però vengono scoperti a runtime, quindi si può solo scegliere un server che sperimentalmente si sa che funziona bene nella maggior parte dei casi
31
Q

EDF + TBS

A

TBS:

  • Assegnata deadline a processi aperiodici
  • Processi soft real time diventano hard real time
  • di = MAX{ai, di-1} + upper[Ci/Us}
  • Us < = 1 - Up
  • Processi schedulati con EDF
32
Q

TBS*

A
  • Miglioramento deadline assegnate agli aperiodici

- Processo iterativo

33
Q

Problema overload

A

Bisogna eseguire per più unità di tempo di quelle a disposizione

1) Capire di essere in overload
2) Scegliere quali processi terminare in tempo e quali non terminare

34
Q

Cause overload

A
  • Troppe attivazioni

- Stima sbagliata tempi di computazione

35
Q

Def carico

A

Carico ρ, frequenza di arrivo λ, costo temporale di ogni singola richiesta c:
ρ = λ * c

Per processi periodici corrisponde al fattore di utilizzazione U
Sovraccarico (overload) se ρ > 1

36
Q

Calcolo carico per un problema di schedulazione generico

A

ρ = MAX(t1,t2 app [ta, tb)) g(t1,t2)/t2-t1

dove g(t1,t2) è il costo di computazione richiesto nella finestra (t1,t2) scelta all'interno della finestra temporale [ta,tb), e corrisponde al numero di unità di tempo da usare per eseguire entro le deadline minori di t2 i processi attivi a t1.
Anziché considerare tutti i possibili intervalli, si considerano solo gli intervalli che hanno per estremi un istante di attivazione e una deadline.
37
Q

Tipi di processi in base al valore

A
  • Ad ogni processo si assegna un valore sulla base del tempo di fine del processo stesso: vi = vi(fi)
  • Se il tempo di fine di un processo è inferiore alla sua deadline il valore ottenuto è massimo e pari a vi.
  • Se il tempo di fine di un processo è superiore alla sua deadline il valore ottenuto è:
    -inf se il processo è critico: sforare la sua deadline provoca la rottura del sistema
    0 se il processo è firm: sforare la sua deadline non provoca danni gravi
38
Q

Criterio di scelta (obiettivo) di una schedulazione in presenza di overload

A
  • Si definisce Γ = Σ vi(fi)

- Obiettivo: schedulazione con Γ massimo.

39
Q

Definizione fattore competitivo

A
  • Definisco Γ* il valore massimo di Γ ottenibile in situazione di chiaroveggenza.
  • Γ* è ottimo: Γ < = Γ*
  • Fattore competitivo: Γ/Γ*
40
Q

Def algoritmo competitivo

A

Algoritmo competitivo ha fattore competitivo maggiore di 0.

EDF in condizioni di overload non è competitivo, perché nel caso peggiore non termina nemmeno un processo in tempo (Γ=0)

41
Q

Limite massimo al fattore competitivo

A

Il valore massimo del fattore competitivo dipende dal carico:

  • Carico tra 0 e 1: problema schedulabile, fattore competitivo pari a 1 grazie a EDF (ottimo per scheulabilità)
  • Carico tra 1 e 2: fattore competitivo massimo parte da 0,385 e scende fino a 0,25 grazie ad algoritmi ottimi.
  • Carico oltre 2: fattore competitivo massimo costante e pari a 0,25, ottenuto grazie all’algoritmo Dover, ottimo con carico superiore a 2.
42
Q

Dover: tipi di processi

A
  • Processi privilegiati: Processi parzialmente eseguiti, non scaduti, non terminati
  • Processi waiting: processi attivi, non scaduti, non ancora iniziati
  • Processo corrente: processo che EDF manderebbe in esecuzione all’istante t
    Un processo non può appartenere a più di una categoria
43
Q

Dover: LST

A

LSTi(t) : Last Starting Time del processo i al tempo t: ultimo istante di tempo in cui il processo i può iniziare per terminare in tempo

44
Q

Dover: def k

A

k = vimax/vimin (varia istante per istante)

vimax=max(vi)
vimin=min(vi)

vi*=vi/ci

vi: valore del processo

45
Q

Andamento soglia di schedulabità al variare di Us per n - > infinito
(RM+DS)

A

Se n - > infinito
U(LL) - > 0.69
U - > Us + ln( Us+2 / 2Us+1 )

Quindi:
Se Us=0, non c’è server, U=0.69 coincide con U(LL)

Per Us=0.2, U minimo. È più difficile schedulare con un server normale.
Oltre 0.2 U cresce

Per Us=0.4, U=0.69=U(LL)

Per Us=1 U=1

Quindi è più facile un problema con un fattore di utilizzazione del server abbastanza alto (maggiore di 0.4)

Sistemi informatici (5 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions