Scheduling multiprocessore e real-time

Gli algoritmi di Scheduling della CPU - FCFS, SJF, priorità e round robinLo scheduler della CPU sceglie tra i processi pronti quello a cui dare il core (il dispatcher esegue il cambio, con latenza di dispatch); lo scheduling è non preemptive (il processo tiene la CPU finché termina o si blocca) o preemptive (la CPU gli può essere tolta, con rischio di race condition); i criteri sono utilizzo della CPU e throughput (da massimizzare), tempo di attesa, di turnaround (completamento meno arrivo) e di risposta (da minimizzare); FCFS è semplice ma soffre dell'effetto convoglio (esempio 24, 3, 3: attesa media 17 contro 3); SJF è ottimo per l'attesa media ma richiede la lunghezza del prossimo burst, stimata con la media esponenziale tau(n+1) = alfa t(n) + (1-alfa) tau(n); SRTF è la versione preemptive (esempio con attesa media 6,5 contro 7,75); round robin dà a ciascuno un quanto q e nessuno attende più di (n-1)q; la priorità causa starvation, risolta con l'aging; code multilivello e a feedback (MLFQ) combinano le politiche.Scheduling della CPU - FCFS, SJF, priorità e round robin → pensano a una sola CPU e a processi senza scadenze. Qui si tolgono due ipotesi: i compiti hanno una scadenza (real-time) e i processori sono più di uno. Gli esercizi con numeri su Rate Monotonic ed EDF sono in Esercizio - Rate monotonic ed EDF su due compiti periodici (slide di scheduling).

Scheduling real-time

Molte applicazioni devono reagire a un evento in tempo breve: il freno antibloccaggio (ABS), i robot industriali, i sistemi di difesa. Il sistema operativo adatto è un RTOS (real-time operating system), tipico dei sistemi embedded (Sistemi operativi embedded e real-time per l'IoTUn sistema embedded è un dispositivo con elettronica e software per una funzione specifica, spesso con vincoli di tempo reale; i microcontrollori (8, 16 o 32 bit, KB di RAM, senza MMU, mW) formano i sistemi profondamente embedded dell'IoT, divisi dall'IETF in classi 0, 1 e 2; i sistemi embedded hanno kernel configurabile, boot loader e root file system costruiti su un host con cross-compilazione; si può adattare un OS esistente (embedded Linux, uClinux senza MMU, Buildroot, Yocto) o usare un OS dedicato (TinyOS a componenti ed eventi, RIOT a microkernel con scheduler a priorità fissa preemptive senza tick, FreeRTOS, Zephyr, Contiki-NG con protothread); l'IoT ha requisiti di memoria minima, hardware eterogeneo, rete a basso consumo, efficienza energetica, tempo reale e sicurezza; nel laboratorio con RIOT si crea una shell, si leggono i thread con ps, si creano thread con priorità e si sincronizzano con un mutex.Sistemi operativi embedded e real-time per l'IoT →).

La latenza di evento (event latency) è il tempo tra il momento in cui l'evento avviene e quello in cui viene servito. Due latenze la determinano:

Due tipi di sistemi:

• soft real-time: i compiti critici hanno la priorità più alta, ma non c'è garanzia su quando verranno eseguiti; serve almeno uno scheduling a priorità con prelazione;
• hard real-time: un compito deve essere servito entro la scadenza; oltre alle condizioni del soft, bisogna dimostrare che le scadenze si rispettano.

Compiti periodici

Si considerano compiti che richiedono la CPU a intervalli regolari: ognuno ha un tempo di elaborazione (burst) $t$, una scadenza $d$ e un periodo $p$, con $0 \le t \le d \le p$ (spesso $d = p$: finire prima dell'inizio del periodo successivo). La frequenza è $1/p$. L'utilizzo del compito è $t/p$, quello dell'insieme è $\sum t_i/p_i$. Si pensi a un processo che legge un sensore o controlla i messaggi in arrivo. Il controllo di ammissione (admission control) decide se la scadenza può essere rispettata.

Priorità fisse: il controesempio e Rate Monotonic

Due compiti: $P_1$ con $p_1 = 50$, $t_1 = 20$; $P_2$ con $p_2 = 100$, $t_2 = 35$. Utilizzo: $20/50 + 35/100 = 0{,}40 + 0{,}35 = 75\%$: sembra possibile. Ma se si dà priorità più alta a $P_2$, esso finisce a 35, poi parte $P_1$ che finisce a 55, dopo la sua scadenza (50): fallisce. La priorità va assegnata bene.

Definizione (Rate Monotonic, RMS). Nello scheduling Rate Monotonic la priorità (fissa, con prelazione) è l'inverso del periodo: periodo più breve, priorità più alta.

Qui $p_1 < p_2$, quindi $P_1$ ha la priorità più alta:

$P_1$ finisce a 20 ($\le 50$); $P_2$ parte a 20, a 50 ha fatto 30 unità e viene prelazionato dal nuovo $P_1$; riprende a 70 e finisce a 75 ($\le 100$). Entrambe le scadenze sono rispettate.

RMS è ottimo tra gli algoritmi a priorità fissa, ma solo se l'utilizzo non supera il limite del caso peggiore per $N$ compiti:

$$U_{\max}(N) = N\left(2^{1/N} - 1\right) \qquad N=2: 0{,}828 \quad N=3: 0{,}780 \quad N=4: 0{,}757 \quad N\to\infty: \ln 2 \approx 0{,}693.$$

Per l'esempio precedente $75\% < 82{,}8\%$ e funziona. Un controesempio: $p_1 = 50$, $t_1 = 25$ e $p_2 = 80$, $t_2 = 35$, utilizzo $25/50 + 35/80 = 0{,}9375 > 0{,}828$. Con RMS ($P_1$ ha priorità):

$P_2$ finisce a 85, dopo la scadenza 80: la scadenza è mancata. Superare il limite non implica sempre il fallimento (il limite è solo sufficiente), ma qui avviene.

Earliest Deadline First

Definizione (EDF). Nello scheduling Earliest Deadline First le priorità sono dinamiche: si esegue il compito con la scadenza più vicina. Vale anche per compiti non periodici. Le scadenze sono garantite finché l'utilizzo totale è inferiore al 100%.

Stesso esempio (25/50 e 35/80):

• a $t=50$ arriva la seconda istanza di $P_1$ (scadenza 100), ma $P_2$ ha scadenza 80: continua, e finisce a 60;
• a $t=80$ arriva la seconda istanza di $P_2$ (scadenza 160): $P_1$ (scadenza 100) ha la precedenza e finisce a 85;
• a $t=100$ la terza istanza di $P_1$ (scadenza 150) prelaziona $P_2$ (scadenza 160): tutte le scadenze sono rispettate.

La prelazione avviene solo se la nuova scadenza è strettamente minore.

Ripartizione proporzionale

Si assegnano $T$ quote (shares) a tutti i processi; un'applicazione con $N$ quote ($N < T$) riceve la frazione $N/T$ del tempo di CPU. Con $T = 100$ e $N_A = 50$, $N_B = 15$, $N_C = 20$ ricevono il 50%, 15% e 20%. Un controllo di ammissione impedisce l'ingresso di un processo che non trova quote: un $D$ con $N_D = 30$ non entra, perché restano solo $100 - 50 - 15 - 20 = 15$ quote.

Scheduling con più processori

Con più CPU lo scheduling è più complesso. Le architetture: CPU multicore, core multithread, sistemi NUMA, multiprocessori eterogenei.

SMP e code di pronti

Nel multiprocessing simmetrico (SMP) ogni processore si schedula da solo. I thread pronti possono stare in una coda comune (richiede sincronizzazione sull'accesso alla coda) oppure ogni processore può avere la propria coda privata (più comune, ma richiede il bilanciamento del carico).

Core multithread

Si mettono più core nello stesso chip (più veloce e a basso consumo) e più thread hardware per core (chip multithreading, CMT; Intel lo chiama hyperthreading): un sistema a 4 core con 2 thread hardware ciascuno è visto dal sistema come $2 \times 4 = 8$ processori logici. Il vantaggio: quando un thread ha uno stallo di memoria (memory stall, la CPU è molto più veloce della memoria, v. Gerarchia di memoria e principio di localitàCaratteristiche delle memorie (posizione, capacità, unità di trasferimento, metodo di accesso, prestazioni, volatilità); compromesso costo-capacità-velocità e gerarchia a livelli; località temporale e spaziale con esempi; hit, miss e tempo medio di accesso con calcolo svolto.Gerarchia di memoria e principio di località →) il core passa a un altro thread hardware invece di restare fermo. Gli algoritmi sono a due livelli: il sistema sceglie quale thread software eseguire su un processore logico; il core sceglie quale thread hardware eseguire.

Bilanciamento del carico

In un sistema SMP bisogna mantenere tutti i processori occupati: il bilanciamento del carico (load balancing) distribuisce il lavoro in modo uniforme.

• push migration: un compito controlla periodicamente il carico di ogni processore e spinge i thread da quello sovraccarico agli altri;
• pull migration: un processore inattivo tira a sé un thread in attesa da uno occupato.

Affinità al processore

Quando un thread ha girato su un processore, la sua cache contiene i dati che ha usato (warm cache, cfr. Memoria cacheBlocchi, linee ed etichette; scomposizione dell'indirizzo; associazione diretta, completamente associativa e associativa a insiemi con calcolo dei campi; politiche di rimpiazzo (LRU, FIFO, casuale); politiche di scrittura (write-through, write-back con bit sporco, write-allocate); dimensione del blocco; cache multilivello e separate; come ridurre i miss; quesiti sui campi dell'indirizzo.Memoria cache →): spostarlo la fa perdere. Si parla di affinità al processore (processor affinity). Il bilanciamento può contraddirla.

Nei sistemi NUMA uno scheduler NUMA-aware assegna la memoria vicina alla CPU in cui gira il thread; Linux, Windows e FreeBSD recenti lo sono.

Esempi: Linux e Windows

• Linux usa per default il Completely Fair Scheduler (CFS), in via di sostituzione con EEVDF (Earliest Eligible Virtual Deadline First). Fa bilanciamento del carico ed è NUMA-aware. Un dominio di scheduling è un insieme di core bilanciabili tra loro, organizzati in base a ciò che condividono (per esempio la cache): si evita di far migrare i thread tra domini.
• Windows usa uno scheduling a priorità con prelazione: gira il thread di priorità più alta, finché si blocca, finisce il suo quanto o viene prelazionato da uno più importante. I thread real-time possono prelazionare gli altri. 32 livelli di priorità: classe variabile 1-15, real-time 16-31, priorità 0 per il thread di gestione della memoria; una coda per ogni priorità; se non c'è nessun thread pronto, gira il thread idle.

Esercizi collegati

• Esercizio - Rate monotonic ed EDF su due compiti periodici (slide di scheduling)
• Esercizio - Domande di teoria su sistemi operativi, scheduling e multiprocessore (eserciziario, esercizi 1, 2, 64 e 121)

Domande d'esame

1. Due compiti periodici hanno $p_1=30$, $t_1=10$, $p_2=40$, $t_2=20$. Sono schedulabili con RMS? E con EDF? Traccia. Utilizzo $10/30 + 20/40 = 0{,}333 + 0{,}5 = 0{,}833 > 0{,}828$: oltre il limite RMS per $N=2$, ma il limite è solo una condizione sufficiente, quindi serve la verifica diretta. Con RMS $P_1$ ha la priorità: $P_1$ 0-10, $P_2$ 10-30, $P_1$ 30-40, $P_2$ 40-60, $P_1$ 60-70, ... sull'iperperiodo 120 tutte le istanze finiscono entro la scadenza (la prima di $P_2$ a 30, la seconda a 60, la terza a 110): RMS funziona. Con EDF basta $U \le 1$: sì (qui la sequenza è identica).

2. Che differenza c'è tra push migration e pull migration? Perché il bilanciamento va contro l'affinità? Traccia. Push: un compito periodico sposta thread dai processori sovraccarichi agli altri; pull: un processore inattivo ne prende uno da uno occupato. Spostare un thread fa perdere il contenuto della cache del processore precedente, quindi riduce l'affinità.

3. Spiegare la differenza tra soft e hard real-time e il ruolo della latenza di dispatch. Traccia. Soft: priorità ai compiti critici, nessuna garanzia sulla scadenza. Hard: la scadenza deve essere rispettata, quindi il sistema deve fornire anche garanzie. La latenza di dispatch è il tempo per togliere un processo dalla CPU e far girare quello critico: deve essere piccola e limitata.