Domenico Cotroneo » 8.Scheduling Multiprocessore e Real-Time

Sommario della lezione

Scheduling multiprocessore

• Problematiche di progettazione
• Dispatching: load sharing, gang scheduling

Scheduling real-time

• Sistemi real-time
• Politiche: earliest deadline first, rate monotonic

Sistemi Multiprocessore

Accoppiamento lasco
Collezione di sistemi autonomi collegati in rete, ogni processore ha la sua memoria e i suoi canali di I/O (ad es., cluster o supercomputer, non trattati in questo corso).

Accoppiamento stretto
Insieme di processori che condividono la stessa memoria e sono sotto il controllo di un singolo sistema operativo (ad es., SMP).

Grado di sincronizzazione nei sistemi multiprocessore

Problematiche di progetto

Assegnazione dei processi ai processori.

Uso del multitasking sui singoli processori.

Dispatching dei processi.

L’approccio da seguire dipende dal grado di sincronizzazione e dal numero di processori.

Assegnazione dei processi ai processori

Assegnazione statica: ogni processo o thread è assegnato permanentemente ad uno dei processori.

• Ogni processore avrà la sua coda di processi pronti.
• Overhead ridotto: l’assegnazione è fatta una volta per tutte.
• … ma il carico potrebbe non essere assegnato uniformemente ai processori.

Assegnazione dinamica: durante la sua vita un processo può eseguire su processori differenti, utilizzando:

• una sola coda condivisa dei processi pronti (load sharing);
• più code, una per processore, con dynamic load balancing, in cui i processi possono essere spostati da una coda all’altra (approccio adottato da Linux).

Dove esegue il meccanismo di assegnazione?

Approccio master/slave: il kernel esegue su un solo processore, detto master, responsabile dello scheduling; gli altri (slave) possono eseguire solo processi utente.

• Gli slave inoltrano le system call fatte dai processi al master.
• Vantaggi: approccio di semplice implementazione.
• Svantaggi: il master costituisce un single point of failure ed è un collo di bottiglia per le prestazioni.

Approccio peer: il kernel esegue su tutti i processori; ogni processore gestisce autonomamente lo scheduling.

• Approccio di difficile implementazione, in quanto richiede la sincronizzazione dei processori nell’accesso alle risorse comuni (ad es., la coda dei processi pronti).

Uso del multitasking sui singoli processori

I singoli processori devono essere multiprogrammati?
Nel caso di grado di sincronizzazione indipendente o coarse grain, è conveniente che ogni processore esegua più processi o thread in concorrenza.
Nel caso di sincronizzazione medium grain è meglio che processi o thread costituenti un’applicazione eseguano contemporaneamente su tutti i processori disponibili.

• In questo caso le sincronizzazioni tra i thread sono frequenti!
• La multiprogrammazione potrebbe complessivamente degradare le prestazioni.

Dispatching – uso dei thread

Nei sistemi mono-processore i thread sono usati per strutturare meglio i programmi e per consentire il paral-lelismo tra CPU e I/O nell’ambito di uno stesso processo.
Nei sistemi multiprocessore i thread possono essere usati per sfruttare a pieno il parallelismo presente in un processo.

• Più thread di una stessa applicazione possono eseguire su processori diversi, con notevoli guadagni prestazionali!
• Il reale guadagno dipende tuttavia dal grado di sincronizzazione tra i thread.

Thread dispatching:

• Load Sharing;
• Gang Scheduling.

Load Sharing

Approccio su cui è basato lo scheduler del Mach OS.
I thread “ready” sono memorizzati in un’unica coda globale, condivisa da tutti i processori.
Appena un processore diviene libero, preleva un thread dalla coda e lo esegue.
Diverse politiche di selezione dei thread dalla coda:

• First come first served: i thread sono posti in coda ed ese-guiti in ordine dai processori fino al completamento o blocco;
• Smallest number of threads first: viene data maggior priorità ai thread appartenenti ai processi con il minor numero di thread non schedulati;
• Preemptive smallest number of threads first: versione preemptive del precedente.

Load Sharing – vantaggi

Il carico è distribuito equamente tra i processori.

Non è necessario un controllo centralizzato dello scheduling (può essere adottato un approccio peer).

Quando un processore diviene disponibile, l’algoritmo di scheduling può essere eseguito direttamente dal quel processore.

Load Sharing – svantaggi

La coda condivisa occupa una regione di memoria che deve essere protetta da accessi concorrenti (mutua esclusione).

• Può costituire un collo di bottiglia per le prestazioni.

Non è detto che i thread bloccati o prelazionati riprendano l’esecuzione sullo stesso processore.

• Uso poco efficiente delle cache dei processori.

Siccome tutti i thread sono trattati allo stesso modo, è poco probabile che i thread di uno stesso processo vengano eseguiti contemporaneamente su più processori.

• Ciò può compromettere le prestazioni nel caso in cui il grado di sincronizzazione tra i thread sia medio o fine.

Gang (o Group) Scheduling

La politica di scheduling si applica a gruppi di thread.

Thread fortemente correlati tra loro eseguono in parallelo, con un notevole guadagno prestazionale:

• meno blocchi dovuti a sincronizzazione;
• meno context-switch;
• minor overhead di scheduling (la decisione dello scheduler coinvolge più thread e processori allo stesso tempo).

Politica utile per le applicazioni con grado di sincronizzazione medio e/o fine (ad es., rendering 3D).

Real-Time Systems

La correttezza del sistema non dipende solo dal risultato di una computazione ma anche dal tempo in cui il risultato viene prodotto.

In genere i processi real-time, o task, devono reagire ad eventi esterni al sistema in “tempo reale”.

In altre parole i task, a seguito di eventi esterni, devono compiere un’elaborazione entro un certo tempo D, denominato deadline.

Real-Time Systems

Con riferimento alla deadline si possono avere:

• Hard real-time task. Il task deve soddisfare la sua deadline. I risultati prodotti fuori deadline non hanno alcun significato: il servizio è fallito ! (in alcuni casi task che terminano fuori deadline possono causare fallimenti dell’intero sistema);
• Soft real-time task. Il task ha una deadline che è “desiderabile” ma non obbligatoria (ad es. Streaming multimediali real-time).

Real-Time Systems

I task possono essere:

• periodici (ad es.lettura ed elaborazione di dati provenienti da sensori). In tal caso la deadline si riferisce al periodo T con cui un task viene attivato;
• aperiodici. In tal caso la deadline si può riferire sia al tempo di inizio (starting deadline) sia al tempo in cui task deve terminare (finish deadline);
• sporadici. Task che si presentano al sistema in modo impredicibile (tipicamente task che corrispondono a richieste di utenti).

Alcuni esempi di Real-Time Systems

• Controllo remoto di un esperimento in laboratorio
• Controllo dei processi industriali
• Applicazioni di Robotica
• Controllo del traffico aereo
• Telecomunicazioni
• Sistemi di controllo e comando ad uso militare

Caratteristiche di un sistema RT

Determinism
Le operazioni sono eseguite entro un intervallo di tempo T predeterminato. Il tempo di attesa di un task nel sistema non può superare soglie predeterminate.
Spesso misurato come tempo che intercorre dalla ricezione di un interrupt a quando il servizio inizia.

Responsiveness
Il tempo di servizio di un task non può superare una certa soglia.

Caratteristiche di un sistema RT

User control
L’utente può specificare la priorità di un task, indicare se una pagina può essere soggetta a swapping o no e selezionare gli algoritmi da utilizzare (l’utente è parte attiva del sistema).

Reliability
Tecniche di ridondanza possono da sole non essere sufficienti per i sistemi RT. Il sistema, in presenza di fallimenti, deve degradare il servizio in maniera predeterminata.

Fail-soft operation
La capacità di un sistema di fallire “dolcemente”, cercando di preservare la consistenza dello stato e delle risorse del sistema.
Stability. Anche in presenza di guasti il sistema deve portare a termine i task a più alta priorità.

Requisiti di progetto di un sistema RT

Context-switch ottimizzato.

Il SO deve essere “snello” e veloce (l’overhead deve essere quanto più basso è possibile).

Un sistema delle interruzioni veloce ed affidabile (in modo da rispondere ad eventi esterni il più veloce possibile).

IPC ottimizzato.

Scheduling Preemptive basato su priorità.

Real-Time Scheduling

L'ordinamento dei task è fondamentale

Real-Time Scheduling

Static table-driven
Lo scheduling avviene a runtime in base ad una analisi statica preliminare per determinare uno schedule fattibile.

Static priority-driven preemptive
L’analisi statica viene usata per assegnare delle priorità ai task, in modo da usare uno scheduler tradizionale a priorità.

Dynamic planning-based
La fattibilità è determinata a run-time, all’arrivo dei task.

Dynamic best effort
Non viene fatta alcuna analisi di fattibilità. Il sistema prova a soddisfare tutte le deadline e abortisce i task la cui deadline è scaduta.

Es. di scheduling table-driven: Sistemi Time triggered

In un sistema time-triggered, il sequenziamento temporale dei vari tasks viene stabilito a priori da strumenti off-line e memorizzato in una Task Descriptor List (TDL) che contiene lo scheduling ciclico per tutti i task, considerando anche le relazioni di dipendenza.

Un dispatcher viene attivato da un clock sincrono che invoca le azioni che sono pianificate per l’istante corrente nelle TDL.

Per i task sporadici si stabilisce di controllare periodicamente l’eventuale presenza (i task sporadici vengono trattati come caso degenere di task periodici).

Algoritmi di scheduling RT

Dynamic best effort

• Earliest Deadline First

Static priority-driven preemptive

• Rate Monotonic
• Deadline Monotonic

Earliest Deadline First

• Ottimale per task periodici.
• Condizione sufficiente U≤1.
• Assegnazione delle priorità dinamica.
• Esegue i task che presentano la deadline più vicina (temporalmente).

Rate Monotonic

La priorità è assegnata in base al periodo del task (priorità massima ai task con periodo più corto)

Rate Monotonic

E’ possibile dimostrare che, utilizzando l’algoritmo RMS, esiste un limite superiore all’utilizzo del sistema al variare del numero di task n:

U ≤ n(2 ^1/n -1) Tende a ln 2 ≈ 0.693

Questo limite può essere utilizzato per effettuare dei test di schedulabilità di un insieme di task.

Esempio di test di schedulabilità

• Task P1: C1=20; T1=100; U1=C1/T1=0.2
• Task P2: C2=40; T2=150; U2=C2/T2=0.267
• Task P3: C3=100; T3=350; U3=C3/T3=0.286

Sono schedulabili?

U1 + U2 + U3=0.753 ≤ 3 (2^1/3-1)=0.779

OK

Rate Monotonic vs Optimal allocation

È meno efficiente dello scheduling ottimale....ma tuttavia è il più utilizzato

Rate Monotonic: perchè si utilizza?

La maggior parte dei sistemi RT ha anche componenti non RT (o soft RT) e pertanto con l’RMS si possono ottenere utilizzi medi maggiori del 90%.

L’algoritmo RMS è più stabile di quello EDF nel caso di sistemi in cui l’occorrenza di un errrore comporti la variazione delle deadline di alcuni task.

Scheduling Protocol

Deadline monotonic

• Permette D_i ≤ T_i
• Assegna le priorità in modo inversamente proporzionale alla lunghezza della deadline.
• E’ possibile anche in questi casi effettuare un test di schedulabilità.

Priority Inversion

Può accadere in qualunque scheduling a prelazione basato a priorità.

Indica quella circostanza in cui il sistema forza un task ad alta priorità ad attenderne uno a più bassa.

La durata di questa attesa può essere impredicibile.

Unbounded Priority Inversion

La durata di una priority inversion dipende da azioni non predicibili di altri task non correlati

Priority Inheritance

I task a bassa priorità ereditano la priorità dei task ad alta priorità bloccati sulla risorsa che condividono, nel tempo in cui permangono nella sezione critica

Priority Inheritance

I task a bassa priorità ereditano la priorità dei task ad alta priorità bloccati sulla risorsa che condividono, nel tempo in cui permangono nella sezione critica.