Esercizio - Domande di teoria su sistemi operativi, scheduling e multiprocessore (eserciziario, esercizi 1, 2, 64 e 121)

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD).

Esercizio 1 (quattro domande di teoria generale, dall'inglese): (a) Quando è appropriato che un sistema operativo rinunci all'efficienza e "sprechi" risorse? Perché un tale sistema non è davvero sprecone? (b) Qual è la difficoltà principale di chi scrive un sistema operativo per un ambiente real-time? (c) Considerate le varie definizioni di sistema operativo: un sistema operativo dovrebbe includere applicazioni come browser e programmi di posta? Si argomenti sia a favore sia contro. (d) In che modo la distinzione tra modalità kernel e utente è una forma rudimentale di protezione?

Esercizio 2. Un algoritmo di scheduling stabilisce un ordine di esecuzione. Dati $n$ processi su un processore, quanti diversi scheduling sono possibili? Formula in $n$.

Esercizio 3 è nel file Esercizio - Implementare il banchiere e calcolarne la complessità (eserciziario, esercizio 3 e laboratorio 6).

Esercizio 64. Tre processi $P_1, P_2, P_3$ arrivano uno dopo l'altro (in quest'ordine ma in tempi diversi) nella coda dei pronti, con un solo burst di CPU e nessun I/O. In quale caso il tempo medio di attesa del sistema è lo stesso con FCFS e con SJF preemptive?

Esercizio 121. Una CPU quad core esegue tre processi $P_0, P_1, P_2$ con tempi di esecuzione (sul core dei dati) di 5, 10, 20 ms. Si dica, motivando, il tempo di esecuzione totale nel caso peggiore e nel migliore, supponendo i processi tutti CPU-bound e che non migrino dal core dopo l'inizio. Ogni processo è un flusso sequenziale non parallelizzabile.

Teoria: Sistema operativo - ruolo, struttura e system callIl sistema operativo (operating system, OS) è il software che fa da intermediario tra utenti, programmi e hardware: alloca le risorse (CPU, memoria, dischi, dispositivi), esegue i programmi e li protegge l'uno dall'altro; la sua parte sempre in esecuzione è il kernel; l'hardware offre la modalità doppia (utente/kernel, un bit di modo) e gli interrupt, e il programma chiede un servizio al kernel con una system call, una trap che passa in modalità kernel; di solito si usa un'API (libc, POSIX, Windows API) che a sua volta invoca la system call (printf chiama write); la struttura può essere monolitica (UNIX/Linux, con moduli caricabili), a microkernel (Mach, QNX), ibrida (Windows, Darwin, Android sopra un kernel Linux modificato).Sistema operativo - ruolo, struttura e system call →, 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 →, Scheduling multiprocessore e real-timeNei sistemi real-time conta la scadenza: si misurano latenza di interrupt e latenza di dispatch; i sistemi soft real-time danno priorità ai compiti critici senza garanzie, quelli hard devono rispettare le scadenze; per compiti periodici (burst t, scadenza d, periodo p, con 0 <= t <= d <= p) l'utilizzo è la somma di t/p: Rate Monotonic (priorità fissa, minore il periodo maggiore la priorità) garantisce le scadenze se l'utilizzo non supera N(2^(1/N)-1) (83% per due compiti), Earliest Deadline First (priorità dinamica, scadenza più vicina) le garantisce se l'utilizzo è sotto il 100%; la ripartizione proporzionale assegna T quote con controllo di ammissione; con più processori si hanno code comuni o private (SMP), core con più thread hardware, bilanciamento del carico (push e pull migration), affinità al processore (soft e hard), scheduling NUMA-aware; Linux usa CFS/EEVDF con domini di scheduling, Windows 32 livelli di priorità.Scheduling multiprocessore e real-time →.

Esercizio 1

(a) Quando rinunciare all'efficienza. Nei sistemi mono-utente interattivi (un PC, uno smartphone) lo scopo è massimizzare l'uso del sistema da parte dell'utente, non della CPU. Un'interfaccia grafica consuma molti cicli di CPU che un'interfaccia testuale risparmierebbe, ma migliora l'interazione. Non è spreco perché le risorse "sprecate" sono quelle che sarebbero inattive comunque, e il risultato è un servizio migliore per chi usa il sistema.

(b) Real-time. Mantenere il sistema entro vincoli temporali fissi: se un compito non è completato in tempo il sistema può guastarsi (frenata, controllo di un robot). Chi scrive il sistema deve garantire che lo scheduling e le latenze non superino mai il tempo massimo ammesso (Scheduling multiprocessore e real-timeNei sistemi real-time conta la scadenza: si misurano latenza di interrupt e latenza di dispatch; i sistemi soft real-time danno priorità ai compiti critici senza garanzie, quelli hard devono rispettare le scadenze; per compiti periodici (burst t, scadenza d, periodo p, con 0 <= t <= d <= p) l'utilizzo è la somma di t/p: Rate Monotonic (priorità fissa, minore il periodo maggiore la priorità) garantisce le scadenze se l'utilizzo non supera N(2^(1/N)-1) (83% per due compiti), Earliest Deadline First (priorità dinamica, scadenza più vicina) le garantisce se l'utilizzo è sotto il 100%; la ripartizione proporzionale assegna T quote con controllo di ammissione; con più processori si hanno code comuni o private (SMP), core con più thread hardware, bilanciamento del carico (push e pull migration), affinità al processore (soft e hard), scheduling NUMA-aware; Linux usa CFS/EEVDF con domini di scheduling, Windows 32 livelli di priorità.Scheduling multiprocessore e real-time →).

(c) Applicazioni dentro il sistema operativo? A favore: un'applicazione integrata può sfruttare funzioni del kernel e ottenere prestazioni migliori di una esterna. Contro (di solito prevalgono): le applicazioni sono applicazioni, non parte del sistema operativo (che è il kernel più i programmi di sistema); ogni vantaggio di prestazione è annullato dalle vulnerabilità che il codice applicativo porta nel kernel (un errore in un browser integrato compromette tutto); il sistema diventa gonfio e più difficile da mantenere.

(d) Protezione rudimentale. Certe istruzioni (I/O, interrupt, configurazione della memoria) funzionano solo in modalità kernel; l'accesso ai dispositivi e il controllo degli interrupt sono riservati al kernel. In modalità utente la CPU ha poche capacità di danneggiare le risorse critiche: i programmi utente possono solo chiedere servizi tramite system call, che il kernel controlla (Sistema operativo - ruolo, struttura e system callIl sistema operativo (operating system, OS) è il software che fa da intermediario tra utenti, programmi e hardware: alloca le risorse (CPU, memoria, dischi, dispositivi), esegue i programmi e li protegge l'uno dall'altro; la sua parte sempre in esecuzione è il kernel; l'hardware offre la modalità doppia (utente/kernel, un bit di modo) e gli interrupt, e il programma chiede un servizio al kernel con una system call, una trap che passa in modalità kernel; di solito si usa un'API (libc, POSIX, Windows API) che a sua volta invoca la system call (printf chiama write); la struttura può essere monolitica (UNIX/Linux, con moduli caricabili), a microkernel (Mach, QNX), ibrida (Windows, Darwin, Android sopra un kernel Linux modificato).Sistema operativo - ruolo, struttura e system call →).

Esercizio 2

Un ordine di esecuzione di $n$ processi è una permutazione: il primo può essere scelto in $n$ modi, il secondo in $n-1$, ..., l'ultimo in 1. Gli scheduling possibili sono

$$n! = n\,(n-1)\,(n-2)\cdots 2 \cdot 1.$$

Per $n=3$: $3! = 6$ ($P_1P_2P_3$, $P_1P_3P_2$, $P_2P_1P_3$, $P_2P_3P_1$, $P_3P_1P_2$, $P_3P_2P_1$). Cresce molto in fretta ($10! = 3\,628\,800$): per questo si usano regole (FCFS, SJF) e non la ricerca esaustiva.

Esercizio 64

Condizione sufficiente: $b_1 \le b_2 \le b_3$, cioè i burst crescono nell'ordine di arrivo. Perché:

• quando $P_2$ arriva, il processo in esecuzione ($P_1$) ha un residuo $r_1 \le b_1 \le b_2$: SJF preemptive prelaziona solo se il nuovo burst è strettamente minore del residuo, quindi non interrompe $P_1$;
• lo stesso per $P_3$: $b_3 \ge b_2 \ge r_2$ e $b_3 \ge b_1 \ge r_1$, quindi nessuna prelazione;
• tra i processi in attesa, SJF sceglie il burst minore, che è sempre il più vecchio ($b_2 \le b_3$).

Quindi la sequenza SJF preemptive è identica a quella FCFS (nessuna prelazione, stesso ordine) e le attese medie coincidono. La condizione è sufficiente, non necessaria (anche con alcune uguaglianze o con arrivi molto distanziati si ottiene la stessa sequenza).

Esempio: $P_1$ (arrivo 0, burst 4), $P_2$ (1, 5), $P_3$ (2, 6). In entrambi i casi: $P_1$ 0-4, $P_2$ 4-9, $P_3$ 9-15; attese 0, 3, 7, media $10/3$.

Esercizio 121

• Caso peggiore: 35 ms. I tre processi finiscono tutti sullo stesso core e girano in sequenza: $5 + 10 + 20 = 35$ ms. (Strettamente il caso peggiore potrebbe anche essere un tempo infinito, se i processi non fossero mai schedulati: il testo chiede il caso con scheduling ragionevole.)
• Caso migliore: 20 ms. Ogni processo gira su un core diverso (ci sono 4 core per 3 processi): il tempo totale è il massimo dei tre, cioè 20 ms. Non si può scendere sotto 20 perché $P_2$ è un flusso sequenziale non parallelizzabile (legge di Amdahl: la parte seriale limita lo speedup).

Domande d'esame

Dati $n$ processi su una CPU, quanti scheduling sono possibili e perché? Traccia. $n!$, le permutazioni degli $n$ processi; senza prelazione. Con prelazione il numero di sequenze di esecuzione è infinito (dipende dal quanto), per questo si studiano politiche e non tutti gli ordini.