Esercizi OS Capitoli 1-6

Gli esercizi che seguono, in parte tratti dal libro di testo, sono utili per rivedere e misurare la propria padronanza degli argomenti presentati a lezione. Inoltre, sono un esempio del tipo di quesiti che verranno proposti alle prove intercorso e agli appelli.

Capitolo 1 1.1 Si descriva il meccanismo degli interrupt e se ne ponga in evidenza l’importanza in un sistema di calcolo. 1.2 Che cos’è una trap e a cosa serve? 1.3 Cosa si intende per kernel di un sistema operativo? 1.4 In ogni sistema di calcolo è presente una gerarchia di memoria. Se ne descriva una organizzazione tipica, evidenziando i tempi tipici di accesso per ogni livello, le caratteristiche di volatilità ed i costi. 1.5 Si spieghi come funziona l’accesso diretto alla memoria (DMA) e quale problema risolve. 1.6 Si spieghi cosa si intende per caching, perché è importante nella organizzazione di un sistema di calcolo e quali problemi può generare. 1.7 Si descrivano chiaramente e concisamente le caratteristiche di un sistema multiprocessore e le possibili organizzazioni architetturali. 1.8 Cosa si intende per sistema cluster? Perché si utilizzano tali architetture? 1.9 Perché i moderni sistemi operativi sono detti interrupt driver? 1.10 Quali sono i due meccanismi assolutamente necessari per implementare un sistema multiprogrammato in cui il sistema operativo e le risorse del sistema siano protetti dai programmi utenti e nessun programma utente possa prendere risorse (e.g. cpu) e non rilasciarle più? 1.11 Perché ha senso definire istruzioni privilegiate? 1.12 A cosa servono l’identificativo utente e l’identificativo di gruppo? Cosa si intende e a cosa serve un identificativo utente effettivo? 1.13 Rispetto al modello di computazione centralizzato, nel corso degli ultimi anni hanno preso corpo due differenti modelli di computazione distribuita. Quali? Se ne descrivano brevemente le organizzazioni tipiche. 1.14 Cos’è un bilanciatore di carico? 1.15 Cosa si intende per computazione batch? 1.16 In cosa si differenziano i sistemi hard real-time da quelli soft real-time?

Capitolo 2 2.1 Elencare cinque servizi che un sistema operativo offre esplicitamente agli utenti e tre servizi che offre implicitamente. 2.2 Cosa fa un interprete di comandi? Discutere vantaggi e svantaggi di interpreti grafici e a linea di comando (shell). 2.3 Discutere vantaggi e svantaggi di un interprete interamente implementato nel kernel del sistema operativo (i.e., built-in). 2.4 Cosa sono e a cosa servono sono le system call? 2.5 Cos’è un’ API e perché solitamente i programmatori preferiscono usare funzioni offerte dalle API piuttosto che direttamente chiamate di sistema offerte dal sistema operativo? Si illustri schematicamente e possibilmente con un esempio la relazione che esiste tra funzioni dell’API e system call. 2.6 Come avviene il passaggio dei parametri alle system call? Discutere vantaggi e svantaggi delle diverse tecniche. 2.7 Cosa sono Pthread e Win32? 2.8 Cos’è un programma di sistema? A cosa serve un programma come dtrace in Solaris (strace in Linux, ktrace in MacOS X…)? 2.9 Perché è importante distinguere tra politiche e meccanismi? Si forniscano esempi a supporto dell’affermazione. 2.10 Che vantaggi offre implementare un sistema operativo in un linguaggio ad alto livello? Quali sono i linguaggi maggiormente usati? L’implementazione in assembler offre qualche vantaggio? 2.11 Descrivere chiaramente e concisamente i seguenti approcci al disegno di un sistema operativo: stratificato, a moduli, e a microkernel. Si pongano in evidenza le relazioni tra gli approcci e le difficoltà insite in ognuno di essi. 2.12 Cosa sono le estensioni del kernel (kernel extension)? 2.13 Un microkernel quali primitive dovrebbe offrire? 2.14 Cosa si intende per Macchine Virtuali? Discutere i vantaggi offerti e le difficoltà relative all’implementazione. Inoltre, si descrivano brevemente VMware e il framework .NET 2.15 Cos’è un compilatore JIT? Come funziona e quale vantaggio offre? 2.16 Perché si parla di Java come di una tecnologia piuttosto che di un linguaggio di programmazione o di un sistema operativo? Come funziona a grandi linee una JVM? 2.17 Cosa significa generare un sistema operativo? Si descrivano tre modalità di generazione e se ne pongano in evidenza vantaggi e svantaggi?

2.18 Com’è organizzato solitamente un programma di bootstrap? Perché? 2.19 In quale contesto si usano le espressioni

1. host operating system 2. guest operation system?

2.20 Cos’è un daemon (demone)? 2.21 Cosa può rappresentare il codice che segue? #include <linux/init.h> #include <linux/module.h> MODULE_LICENSE("Dual BSD/GPL"); static int hello_init(void) { printk(KERN_ALERT "Buongiorno a tutti\n"); return 0; } static void hello_exit(void) { printk(KERN_ALERT "Arrivederci\n"); } module_init(hello_init); module_exit(hello_exit); 2.22 Si rappresenti graficamente la struttura dei sistemi operativi MacOS X e Solaris e se ne discutano brevemente le caratteristiche del disegno.

Capitolo 3 Rappresentazione, creazione e terminazione. 3.1 Descrivere, facendo uso di grafica:

1. l’immagine in memoria di un processo 2. il contenuto di un tipico PCB 3. diagramma di transizioni di stato

Circa il punto 3, quali sono le transizioni più frequenti? Tra quali stati avvengono? 3.2 Descrivere l’esecuzione tipica (i.e., ciclo di vita) di un processo attraverso un diagramma a code. 3.3 Quanti e quali schedulatori ci possono essere in un SO? 3.4 Cosa significano i seguenti temini:

1. swapping 2. context switch

3.5 Spiegare la differenza tra le chiamate di sistema fork() (Unix) e CreateProcess() (Windows XP). Quali chiamate di sistema si usano in Unix e Windows XP, rispettivamente, per far attendere il processo padre sino al termine dell’esecuzione del figlio. Comunicazione tra Processi 3.6 Memoria Condivisa (Shared memory) e Scambio di Messaggi (Message Passing). Discutere chiaramente e concisamente:

1. supporto richiesto dal SO da ognuna delle due forme di comunicazione 2. efficienza 3. limitazioni

3.7 Nella realizzazione di un sistema di scambio di messaggi occorre effettuare diverse scelte. Cosa si intende per:

1. comunicazione diretta (simmetrica e asimmetrica) 2. comunicazione indiretta 3. primitive sincrone, non bloccanti e asincrone 4. bufferizzazione

3.8 Quali primitive offre l’API definita dallo standard POSIX per la condivisione di memoria tra processi? 3.9 Il sistema operativo Mach è basato su messaggi: tutte le comunicazioni tra processi avvengono tramite messaggi. Discutere brevemente:

1. cos’è una porta e un set di mailbox 2. cosa sono msg_send(), msg_receive(), e msg_rpc() 3. cosa fa port_allocate() 4. cosa si intende per “problema della doppia copia dei messaggi” 5. come fa Mach ad eliminarlo ed a guadagnare in termini di efficienza

3.10 Un recente sistema operativo “usa” Mach ad un livello inferiore. Quale? 3.11 Cosa si intende per LPC? Come funziona? E’ accessibile direttamente dal programmatore tramite l’API Win32? Comunicazione Client-Server 3.12 Si spieghi brevemente:

1. cos’è un socket e come avviene la comunicazione tramite socket 2. come funziona RPC 3. come funziona RMI

Inoltre, si fornisca una motivazione chiara e concisa dei vantaggi che un programmatore ha nell’usare RPC ed RMI invece del meccanismo dei socket e delle due principali differenze che esistono tra RPC ed RMI. 3.13 Si spieghi, chiaramente e concisamente, cosa significano i seguenti termini e in quali contesti sono usati:

1. stub 2. marshalling 3. little-endian e big-endian 4. XDR 5. matchmaker 6. parcel 7. object serialization

3.14 Le comunicazione client-server avvengono solitamente tramite rete. Oltre ai problemi di malfunzionamento centralizzato vanno quindi considerati quelli dovuti alla rete. Nell’implementazione di un meccanismo di chiamata di procedura remota come si può garantire che un messaggio sia stato ricevuto almeno una volta ed esattamente una volta?

3.15 Cosa rappresentano le seguenti strutture di dati nei sistemi Unix? struct shmid_ds { struct ipc_perm shm_perm; /* operation perms */ size_t shm_segsz; /* size of segment (bytes) */ __kernel_time_t shm_atime; /* last attach time */ unsigned long __unused1; __kernel_time_t shm_dtime; /* last detach time */ unsigned long __unused2; __kernel_time_t shm_ctime; /* last change time */ unsigned long __unused3; __kernel_pid_t shm_cpid; /* pid of creator */ __kernel_pid_t shm_lpid; /* pid of last operator */ unsigned long shm_nattch; /* no. of current attaches */ unsigned long __unused4; unsigned long __unused5; }; struct ipc_perm { key_t key; ushort uid; /* owner euid and egid */ ushort gid; ushort cuid; /* creator euid and egid */ ushort cgid; ushort mode; /* access modes see mode flags below */ ushort seq; /* sequence number */ }; 3.16 Cosa si trova all’interno del file /usr/src/linux-2.4.21-226/include/asm-i386/unistd.h ? 3.17 Come si chiama il processo in un sistema Unix da cui discendono tutti i processi dell’utente?

Capitolo 4 Motivazioni e rappresentazione 4.1 Cos’è un thread e perché può essere conveniente avere applicazioni multithread? Si fornisca qualche esempio. 4.2 Una struttura di dati che rappresenta un blocco di controllo del thread, cosa dovrebbe contenere? Implementazione 4.3 Una libreria che offre thread al programmatore può essere implementata attraverso i modelli M-a-1, M-a-M, 1-a-1, e a due livelli (ibrido). Si pongano brevemente in evidenza i vantaggi e gli svantaggi dei differenti approcci. 4.4 Si descrivano le primitive offerte dalle API Pthread e Win32 per:

1. Creare un thread (significato dei parametri) 2. Permettere al thread padre di attendere che il thread figlio termini

4.5 Si descrivano le primitive offerte da Java per la creazione di thread. In particolare si spieghi:

1. come si crea un thread 2. come può il thread padre attendere il completamento del thread figlio

4.6 Nei modelli delle API Pthread e Win32, l’intera immagine di memoria del processo a cui i thread appartengono è condivisa dai thread. Nel modello dell’API Java come avviene la condivisione? (Suggerimento: si pensi all’esempio visto a lezione – thread figlio che calcola la somma di interi) 4.7 Discutere l’affermazione: “i thread Java in realtà non esistono”. Può avere un senso? Quale? Scrittura di codice (semplice) 4.8 Si scriva, usando tutte e tre le API (i.e., Pthread, Win32, e Java), un programma multithread che:

1. riceve in input un intero positivo N 2. esegue il prodotto degli interi da 1 a N in un thread separato 3. stampa a video il risultato

Questioni implementative 4.9 Spiegare brevemente (al più 4 righe per punto)

1. Quali problemi occorre affrontare nella implementazione delle chiamate di sistema fork() ed exec() in presenza di thread?

2. Secondo quali strategie può essere implementata la terminazione dei thread?

3. Quali problemi nascono nella gestione dei segnali?

4.10 Windows XP fornisce APC. Cosa sono e che differenza c’è tra APC e meccanismo dei segnali in UNIX? 4.11 Cosa è un pool di thread? Si fornisca un esempio di applicazione che può trarre vantaggio dall’uso di pool e se ne motivi la ragione. 4.12 Si spieghi brevemente come può essere gestita la comunicazione tra il kernel del sistema operativo e una libreria che offre thread al programmatore ed implementa il modello M-a-M o a due livelli. 4.13 Si spieghi brevemente:

1. Quale modello usa Windows XP per supportare i thread offerti al programmatore attraverso l’API Win32.

2. Quali strutture di dati vengono usate per rappresentare e gestire i thread.

4.14 Come funziona la chiamata di sistema clone() in Linux? Che differenza c’è tra i termini task, processi e thread?

Analisi e comprensione di codice 4.15 Cosa fa il seguente programma C? Si commenti il codice.

4.16 Cosa fa il seguente programma C? Si commenti il codice.

4.17 Cosa fa il seguente programma C? Si commenti il codice.

Capitolo 5 Diagrammi di Gantt e misura delle prestazioni. 5.1 Si consideri il seguente insieme di processi.

Processi Durata del CPU-burst (millisecondi)

Priorità

P1 9 3 P2 5 2 P3 7 4 P4 2 1 P5 11 3

I processi arrivano tutti all’istante 0, nell’ordine P1, P2, P3, P4, P5.

1. Si disegnino i diagrammi di Gantt che illustrano l’esecuzione dei processi usando gli algoritmi: A priorità (valore alto – priorità alta), FCFS, SJF e RR (quantum = 1)

2. Per ciascuno degli algoritmi si calcoli il tempo di completamento (turnaround time) di ogni

processo e il tempo di attesa (waiting time)

3. Quale algoritmo fornisce il minimo tempo medio di attesa? I processi arrivano in istanti diversi. Precisamente,

Processi Tempo d’arrivo Durata del CPU-burst Priorità P1 0 9 3 P2 1 5 2 P3 2 7 4 P4 4 2 1 P5 5 11 3

1. Si disegni il diagramma di Gantt che illustra l’esecuzione dei processi usando l’algoritmo

SJF preemptive (e.g., shortest-remaining-time-first) 2. Si calcoli il tempo medio di attesa.

5.2 I parametri solitamente utilizzati per valutare le performance degli algoritmi di schedulazione sono utilizzo della cpu, throughput, turnaround time, waiting time e response time.

1. Cosa rappresentano? 2. Quali parametri si cerca di massimizzare e quali di minimizzare? 3. Perché alcuni ricercatori sostengono che invece di minimizzare il valore medio del tempo di

risposta occorrerebbe minimizzare la varianza del tempo di risposta? 5.3 Schedulatore. Si spieghi:

1. Perché è importante che lo schedulatore selezioni un buon mix di processi CPU-bound e IO-

bound? 2. Da un punto di vista sperimentale, le durate dei cpu-burst è stata misurata ampiamente.

Come sono distribuiti? 3. Che cosa fa il dispatcher?

5.4 SJF

1. L’algoritmo SJF è ottimo nel senso che dà il minimo tempo medio d’attesa. Si provi tale affermazione.

2. Come si stimano le durate dei prossimi CPU-burst per implementare l’algoritmo SJF e qual

è il significato del parametro α nella formula di approssimazione?

3. Posto che α=1/2, τ0 = 8 e, per i=1,2,…, i cpu-burst reali ti siano (millisecondi): 7, 8, 9, 15,

15, 15, 12, … si riportino in un grafico le corrispondenti stime di τi. 5.5 A Priorità

1. Quale problema può comportare l’utilizzo di un algoritmo di schedulazione a priorità in un sistema di calcolo? Esistono contromisure?

5.6 FCFS

1. Si fornisca una esempio (sequenza processi, durata cpu-burst, richieste I/O) che riproduca

l’effetto convoglio.

5.7 Algoritmo RR

1. Si discutano brevemente i problemi nella scelta della durata del quanto di tempo (quantum, time slice).

2. Cosa si intende per processor sharing?

3. Si consideri il seguente insieme di processi

Processi Durata cpu-burst

(millisecondi) P1 5 P2 3 P3 1 P4 6

Graficare il tempo medio di turnaround dei processi, facendo variare la durata del quanto di tempo da 1 a 6 millisecondi (i.e,. sulle ascisse del grafico si trovano le durate del quanto 1,2, …,6 e sulle ordinate i valori medi del tempo di turnaround). Il tempo dovuto al context switch è idealmente pari a zero. Dall’analisi del grafico si può trarre qualche conclusione generale?

5.8 Algoritmi a code multiple

1. Come è strutturato un algoritmo di schedulazione a code multiple? Si fornisca un esempio. 2. Come funziona uno schedulatore a code multiple con feedback? Si fornisca un esempio. 3. Esiste relazione tra il meccanismo del feedback e il concetto dell’aging?

5.9 Schedulazione di processi su architetture multiprocessore Per ognuno dei punti che segue, si usino due righe per spiegare chiaramente e concisamente cosa significa:

1. processori omogenei 2. condivisione del carico (load sharing) 3. affinità soft e hard 4. bilanciamento del carico (load balancing) 5. push migration 6. pull migration

5.10 Si spieghi cosa si intende per hyperthreading technology e come può uno schedulatore ottimizzare le proprie scelte su architetture basate su questa tecnologia.

Sistemi operativi reali 5.11 Gli algoritmi di schedulazione dei sistemi operativi Solaris, Windows XP, e Linux sono tutti e tre basati su priorità, a code multiple e preemptive. I primi due differiscono dal terzo essenzialmente per due scelte (politiche) di fondo. Quali? 5.12 Si descriva parzialmente la tabella della priorità per la schedulazione dei processi interattivi in Solaris e se ne mettano in evidenza le idee sottostanti.

Valutazione degli algoritmi 5.13 I metodi di valutazione degli algoritmi di schedulazione sono principalmente quattro: modellazione deterministica, reti di code, simulazione e implementazione. E un software che realizza macchine virtuali può tornare utile? 5.14 Quali motivazioni si potrebbero addurre “sull’inutilità” dei metodi di modellazione deterministica e delle reti di code? Schedulazione dei Thread 5.15 Una libreria di Thread che implementa il modello molti-a-uno o molti-a-molti può offrire all’utente la scelta tra due opzioni di schedulazione dei thread che ha creato nella propria applicazione: locale o globale.

1. Come vengono denominati gli schemi che implementano le due modalità? 2. Quali funzioni e parametri offre l’ API Pthread Posix per la schedulazione dei thread?

Capitolo 6 6.1 Si costruisca un esempio di corsa critica diverso da quello presentato a lezione. 6.2 Si spieghi quali sono i vantaggi e gli svantaggi relativi alla progettazione di un kernel preemptive. 6.3 Si definisca il problema della sezione critica, la struttura generale di un protocollo per la sezione critica e le proprietà che deve soddisfare. 6.4 Si analizzi il seguente protocollo di sincronizzazione per due processi. Pi e Pj condividono la variabile turn (inizializzata a i o j). Codice per Pi do{ while (turn != i) no-op; sezione critica turn = j; sezione non critica }while(TRUE);

6.5 Si analizzi il seguente protocollo di sincronizzazione per due processi Pi e Pj condividono due variabili booleane flag[i] e flag[j] inizializzate a FALSE. Codice per Pi do{ flag[i]=TRUE; while (flag[j] ==TRUE) no-op; sezione critica flag[i]=FALSE; sezione non critica }while(TRUE); 6.6 Si analizzi il seguente protocollo di sincronizzazione per due processi Pi e Pj condividono due variabili booleane flag[i] e flag[j] inizializzate a FALSE e una variabile intera turn. Codice per Pi do{ flag[i]=TRUE; turn = i; while (flag[j] == TRUE && turn = j) no-op; sezione critica flag[i] = FALSE; sezione non critica } while(TRUE);

6.7 Algoritmo di Dekker. Si analizzi il seguente protocollo. Pi e Pj condividono due variabili booleane flag[i] e flag[j] inizializzate a FALSE e una variabile intera turn. do{ flag[i] = TRUE; while( flag[j]){ if (turn == j) { flag[i] = FALSE; while(turn == j ) ; // do nothing flag[i] = TRUE; } } // sezione critica turn = j; flag[i]=FALSE; // sezione non critica }while(TRUE)

6.8 Algoritmo di Eisenberg e McGuire. Si analizzi il seguente protocollo per la sezione critica. do { while (TRUE) { flag[i] = want_in; j = turn; while (j!=i) { if (flag[j] != idle) { j = turn; else j = (j+1) % n; } flag[i] = in_cs; j=0; while ( (j < n) && ( j == i || flag[j] != in_cs) ) j++; if ( ( j >= n ) && ( turn == i || flag[turn] == idle) ) break; } // sezione critica j = ( turn + 1) % n; while ( flag[j] == idle) j = (j+1) % n; turn = j; flag[i] = idle; // sezione non critica } while (TRUE);

6.9 Algoritmo del fornaio (Lamport). Si analizzi il seguente algoritmo per il problema della sezione critica (Nota che il processo Pi ha un identificativo numerico i, e date due coppie di interi (a,b) e (c,d) si definisce (a,b) < (c,d) se a<c o se a=c e b<d ). Perché si chiama algoritmo del fornaio? do{ choosing[i] = true; number[i] = max (number[0], number[1], …, number[n-1]) + 1; choosing[i] = false; for j = 0 to n-1 do while choosing[j] do no-op; while number[j] != 0 and (number[j],j) < (number[i],i) do no-op; // critical section number[i] = 0; // remainder section }while (true);

6.10 Si descriva un protocollo per n processi per il problema della sezione critica che fa uso dell’istruzione SWAP(a,b). 6.11 Si descriva una implementazione dei semafori senza attesa attiva. 6.12 Esistono restrizioni sul tipo di coda utilizzata nella implementazione di un semaforo senza attesa attiva? E se invece di una coda utilizzassimo uno stack, quali problemi potrebbero sorgere? 6.13 Si fornisca un esempio di applicazione, diverso da quello fornito a lezione, che può far uso di un semaforo contatore per gestire la sincronizzazione. 6.14 Si implementi un semaforo contatore avendo a disposizione un semaforo binario. 6.15 Si descriva la soluzione al problema produttore-consumatore che fa uso dei semafori. 6.16 Si descriva la soluzione al primo problema dei lettori e degli scrittori che fa uso dei semafori. Inoltre, si spieghi cos’è un lock di lettura-scrittura ed in quali applicazioni risulta più vantaggioso di un semplice semaforo. 6.17 Come potrebbe essere risolto il problema dei lettori e degli scrittori evitando che ci sia starvation o per i primi o per i secondi? Occorre usare qualche informazione in più? 6.18 Si descriva una soluzione al problema dei 5 filosofi a pranzo che fa uso di un Monitor. 6.19 Si descriva una implementazione generale di un monitor attraverso semafori. 6.20 Si implementi un semaforo contatore usando un monitor. 6.21 Mostrare che Monitor e Semafori sono primitive di sincronizzazione equivalenti. 6.22 Si fornisca una implementazione delle operazioni wait() e signal() di un semaforo facendo uso dell’istruzione TestAndSet(&lock) o Swap(a,b); 6.23 Cosa significa attesa attiva? Può essere evitata del tutto? Può essere utile? 6.24 Spiegare perché uno spinlock è inutile su architetture monoprocessore ma è spesso usato in architetture multiprocessore. 6.25 Spiegare le differenze esistenti tra l’operazione signal() su un semaforo e l’operazione signal() su una variabile condizione. 6.26 Si riguardi il codice che implementa un monitor attraverso l’uso di semafori. Se un processo P può invocare una signal() solo prima di lasciare il monitor, come può essere semplificata l’implementazione generale tramite semafori presentata a lezione?

6.27 Spiegare perché implementare primitive di sincronizzazione attraverso la disabilitazione degli interrupt è una strategia pericolosa su architetture monoprocessore se le primitive debbono essere usate a livello utente. 6.28 Spiegare perché la disabilitazione degli interrupt non è appropriata per implementare primitive di sincronizzazione su architetture multiprocessore. 6.29 Si costruisca un esempio che mostra come se wait() e signal() non sono eseguite atomicamente la mutua esclusione può essere violata. 6.30 Java fornisce monitor? Argomentare la risposta. 6.31 Cosa si intende per transazione atomica e quali tipi di problemi occorre gestire nella implementazione di transazioni atomiche? Cosa si intende per serializzabilità?