Formulario e FAQ Sistemi Real Time

Task aperiodici

Earliest Due Date (Jackson) [sync | L_max]

Task schedulati per ordine di deadline crescente. Test di Schedulabilità: ∀ = 1, …, ∑ ≤ =1

Earliest Deadline First (Horn) [preem | L_max]

Si rimuove l'ipotesi di attivazioni simultanee, scheduling per ordine di deadline crescente. Test di Schedulabilità: () ∀ = 1, … + ∑ ≤ =1

Bratley [no preem, no sync]

Ricerca in albero al fine di trovare sequenza fattibile.

Latest Deadline First [sync, prec | L_max]

Fra tutti i task che non hanno successori nel DAG, selezioni quello avente deadline più lunga. Così facendo, ottengo una lista da schedulare in ordine inverso.

EDF con vincoli di precedenza

Tempi di arrivo: i*1. Per ogni nodo iniziale si pone a = a_i

1. Finché esistono nodi del DAG non ancora modificati:
   1. Seleziono J t.c. predecessori modificati k** = max[ , max ( + )] ∀ | → b., ovvero J predecessore diretto di J_i k

Deadline: i*1. Per ogni nodo foglia si pone d = d_i

1. Finché esistono nodi del DAG non ancora modificati:
   1. Seleziono J t.c. tutti i successori modificati k** = min[ , min ( − )] ∀ | → b., ovvero J successore diretto di J_i k

Task periodici

Timeline Scheduling

Divisione asse temporale in time slots. Minor Cycle = MCD(T_i); Major Cycle = mcm(T_i)

Test Garanzia: C task slot k ≤ minor cycle_i

Rate Monotonic [prio. fisse, preem]

Assegna ad ogni task una priorità inversamente proporzionale al proprio periodo. *Ottimo nel senso che se un insieme non è schedulabile con RM, allora non lo è con nessun altro algoritmo a priorità fisse.

Test di Schedulabilità “Liu & Layland” (suff.) Test di Schedulabilità “Hyperbolic Bound” (suff.)

• 1 ∑ ≤ (2 − 1)
• ∏( + 1) ≤ 2 =1 =1

Test di Schedulabilità “Response Time Analysis” (nec.+suff.) – 1 (−1)() = + ∑ ⌈ ⌉ ≤ =1 [ Test di Schedulabilità “Processor Demand Criterion” (nec.+suff.) ]

Earliest Deadline First [prio. dinamiche, preem]

Schedula i task per deadline assoluta crescente. Test di Garanzia (nec.+suff.): ∑ ≤1=1

Deadline Monotonic [D ≠ T ]_i

Schedula task con la deadline relativa più corta. *Ottimo nel senso che se esiste un assegnamento statico di priorità in grado di schedulare un insieme di task periodici, allora esso è schedulabile con DM.

Test di Schedulabilità (suff.): Test di Schedulabilità RTA: (nec.+suff.)

• – 1 (−1) 1 () ∑ ≤ (2 − 1)
• = + ∑ ⌈ ⌉ ≤ =1 =1

Server aperiodici

Polling Server [prio. fissa]

Processo periodico dedicato alla gestione di task aperiodici. In assenza di richieste pendenti, il server si sospende fino al periodo successivo.

Test Garanzia Periodici: Test Schedulabilità PS+RM con PS massima priorità:

• 1 1 2 ∑ + ≤ ( + 1)(2 − 1)+1 ∑ ≤ [( ) − 1] + 1 =1 =1

Deferrable Server [prio. fissa]

Come PS ma conserva la propria capacità anche quando, al momento dell’attivazione, non ci sono richieste pendenti.

Test Garanzia Periodici DS+RM:

• 1 + 2 2 ∑ ≤ [( ) − 1] 2 + 1 =1

Sporadic Server [prio. fissa]

Gestore di capacità, consumata e ripristinata dinamicamente, in funzione delle richieste aperiodiche.

Regole: > 0) → = + 1. SE (&& (SS attivo), T istante in cui si verifica la condizione A = 0)