Esercizi di preparazione¶
In questa sezione vengono riportate alcuni esercizi/domande che possono essere utilizzate come preparazione all’esame.
Domande¶
1 - Introduzione¶
Descrivere il concetto di interrupt e mostrare il suo utilizzo nei sistemi operativi.
Descrivere le principali strutture dati di un sistema operativo.
Descrivere i principali benefici e le criticità introdotte della multiprogrammazione.
Cosa sono le system call e quali relazioni hanno con le librerie di sistema?
Riportare esempi di supporti hardware necessari al sistema operativo per garantire la protezione delle risorse.
Quali sono gli obiettivi principali di un sistema operativo?
Perché la distinzione tra modo kernel e modo user è una forma di protezione?
Descrivere 3 servizi di sistema operativo e spiegare perché sono convenienti per gli utenti. Inoltre, perché è sconveniente che siano forniti da programmi user?
Descrivere le principali caratteristiche di un sistema batch e di un sistema batch multiprogrammato, discutendo anche in modo comparativo i vantaggi o svantaggi dell’uno verso l’altro.
2- Processi e thread¶
Descrivi il concetto di mode switch e di process switch.
Descrivi il concetto di processo. Quali sono i possibili stati di un processo?
Quando un processo viene creato tramite fork, cosa è condiviso tra processo parent e child?
Spiegare la differenza tra il processo e thread.
Quale è la differenza tra User-Level Thread e Kernel-Level Thread?
Quando un thread viene creato tramite pthread_create, cosa è condiviso tra thread parent e child?
3 - Sincronizzazione¶
Cos’è un’istruzione Read-Modify-Write?
Descrivere cosa è un lock e relative proprietà di correttezza e progresso.
Descrivere il Bakery algorithm.
Gli spinlock sono appropriati in un sistema single-core? Motiva la tua risposta.
4 - Scheduling¶
Cpu-scheduler: quali sono i criteri di valutazione di un CPU scheduler?
Quali sfide introducono le architetture multicore nell’ambito del CPU scheduling?
Quale è la differenza tra uno scheduler preemtive e uno non-preemptive?
Descrivere la politica Shortest Job First e discuterne vantaggi e svantaggi.
Descrivere la politica Round Robin e discuterne vantaggi e svantaggi.
Descrivere la politica di Fair-Share scheduling e quali problematiche risolve.
Descrivere lo scheduler Complete Fair Share in Linux.
Descrivere lo scheduler Multilevel Feedback Queue.
Quale è il vantaggio di avere time-slice differenti in uno scheduler basato su code multilivello con feedback?
Come è possibile parametrizzare uno scheduler basato su priorità per emulare gli scheduler Shortest Job First, First Come First Serve?
Descrivere lo scheduler di CPU round-robin virtuale, discutendone vantaggi e svantaggi rispetto allo scheduler round-robin.
Si descrivano gli scheduler di CPU Shortest-Process-Next (SPN) e la sua variante Shortest–Remaining-Time-Next (SRTN), evidenziandone i vantaggi e gli svantaggi.
5 - I/O Management¶
Quali sono le difficoltà che introduce il Direct Memory Access rispetto alla gestione dei processi?
Descrivere la tecnica di I/O buffering e la sua utilità.
Spiegare le criticità nel progettare politiche di I/O scheduling.
Descrivere le politiche First-Come-First-Served e Shortest-Seek-Time-First per disk scheduling e illustrarne vantaggi e svantaggi.
Descrivere la politica SCAN per disk scheduling e spiegarne vantaggi e limiti. Per le limitazioni descritte, riportare possibili soluzioni.
6 - File management¶
Cosa è un file e quali sono i suoi principali attributi?
Cosa è un file system e quali sono i suoi compiti principali?
Descrivere i metodi di accesso a file sequenziale, diretto ed indicizzato.
Descrivere le caratteristiche salienti del file system UNIX.
Cosa è un in-memory file system e riportarne alcuni esempi.
Descrivere i classici metodi di allocazione dei file sui dispositivi, discutendone vantaggi e svantaggi in modo comparato.
Descrivere cosa sono gli “hard link” ed i “soft link” in un file-system.
Si descriva il metodo di allocazione dei file a catena.
7 - Gestione della memoria¶
Descrivi la paginazione e la segmentazione mostrando vantaggi e svantaggi di ciascuna.
Mostra lo schema di paginazione a due livelli e il processo di traduzione di un indirizzo virtuale in fisico. Quali sono i vantaggi e gli svantaggi nell’uso di tale schema?
Cosa è e a cosa serve il translation lookside buffer?
Mostrare uno schema di segmentazione paginata con TLB e descriverne il funzionamento per la traduzione da indirizzo logico a fisico.
Che cosa è un buddy system?
Descrivi l’anomalia di Belady.
Descrivere l’algoritmo dell’orologio nell’ambito delle politiche di replacement delle pagine.
Descrivere gli aspetti principali di gestione della memoria virtuale.
Descrizione la gestione di un page fault nel caso di memoria virtuale basata su paginazione.
Descrivere le caratteristiche delle politiche di gestione del resident set di processo.
Descrivere il fenomeno del thrashing nel contesto della memoria virtuale.
Descrivere la tecnica di gestione delle memoria basata su partizioni dinamiche, indicando anche di quali supporti per il binding degli indirizzi questa necessita.
Descrivere l’algoritmo di selezione Least-Recently-Used (LRU) per sistemi di memoria virtuale basati su paginazione.
Si descriva la tecnica della paginazione, indicando quali siano le strutture dati fondamentali che un sistema operativo deve gestire per metterla in atto.
Descrivere l’algoritmo ottimo per la sostituzione delle pagine in ambiente di memoria virtuale. Si indichi infine se tale algoritmo soffra o meno dell’anomalia di Belady, motivando la risposta.
Descrivere la struttura e l’utilizzo della tabella delle pagine e la relazione tra questa ed i componenti hardware presenti su una architettura di processore convenzionale.
Esercizi di teoria¶
Warning
Alcuni esercizi possono deliberatamente ammettere più di una soluzione in funzione delle assunzioni fatte durante lo svolgimento. Di conseguenza, le soluzioni proposte potrebbe non essere le uniche ammissibili.
1 - Introduzione¶
Si consideri un programma di cui:
il 60% del tempo di esecuzione è parallelizzabile;
l’80% del tempo non parallelizzabile può essere ottimizzato tramite l’adozione di un algoritmo 16 volte più veloce.
Calcolare lo speedup ottenibile tramite:
la sola ottimizzazione a) con 2 e 4 core;
tramite la sola ottimizzazione b);
l’applicazione congiunta di a) e b) con 2 e 4 core.
Infine, riportare lo speedup massimo raggiungibile tramite ottimizzazione a) e b).
3 - Sincronizzazione¶
Una applicazione ha p thread produttori e c thread consumatori. L’applicazione lavora in due fasi. Nella prima fase i thread produttori Pi inseriscono in una coda vuota c elementi. Nella seconda fase i thread consumatori Ci estraggono ciascuno un elemento dalla coda a partire da C1 a Cc. Le due fasi si alternano per un tempo infinito. Scrivere in pseudocodice il corpo delle funzioni eseguite da un generico thread Pi e Ci assumendo che:
la coda è inizialmente vuota;
l’implementazione disponibile della coda NON è thread safe;
è ammesso solo l’utilizzo di semafori;
non è ammesso utilizzare altre variabili condivise ad eccezione di eventuali semafori e della coda.
4 - Scheduling¶
- Si consideri uno scenario con 4 processi {P1,…, P4} CPU-bound e generati in sequenza a partire da P1 a P4 con ritardi trascurabili.
Il processo Pi richiede 1/i secondi di CPU per completare la propria esecuzione. Considerando che il ritardo di context-switch sia trascurabile e che RR abbia una time slice pari a 125ms, si calcoli per gli algoritmi FCFS, SPN e RR il tempo di primo accesso alla CPU e il tempo di completamento per ciascun processo.
Mostra/Nascondi Soluzione
FCFS:
process
P1
P2
P3
P4
CPU Release Time
1.00
1.5
1.83
2.08
Processo
Primo Accesso
Completamento
P1
0
1
P2
1
1.5
P3
1.5
1.83
P4
1.83
2.08
SPN:
Assunzione 1: Lo scheduler viene attivato dopo l’arrivo di tutti i processi
process
P4
P3
P2
P1
CPU Release Time
0.25
0.58
1.08
2.08
Processo
Primo Accesso
Completamento
P1
1.08
2.08
P2
0.58
1.08
P3
0.25
0.58
P4
0
0.25
Assunzione 2: Lo scheduler è attivato all’arrivo del primo processo
process
P1
P4
P3
P2
CPU Release Time
1.00
1.25
1.58
2.08
Processo
Primo Accesso
Completamento
P1
0
1
P2
1.58
2.08
P3
1.25
1.58
P4
1
1.25
RR:
process
P1
P2
P3
P4
P1
P2
P3
P4
P1
P2
P3
P1
P2
P1
P1
P1
P1
CPU Release Time
0.125
0.250
0.375
0.500
0.625
0.750
0.875
1.000
1.125
1.250
1.333
1.458
1.583
2.083
Processo
Primo Accesso
Completamento
P1
0.000
2.08
P2
0.125
1.58
P3
0.250
1.33
P4
0.375
1.00
Si consideri uno scenario in cui uno scheduler Multilevel-feedback queue abbia 4 livelli di priorità, ed in cui il quanto di tempo assegnato ai processi al livello i sia di 1/2^i millisecondi. Si supponga che all’istante T0 nascano 2 processi A e B, entrambi CPU-bound. Il processo B richiede 10 millisecondi di tempo di CPU per completare la sua esecuzione. Si identifichi la durata massima (in termini di tempo di CPU) del processo A affinché il processo B possa completare la sua esecuzione entro il tempo T0+17 nei due casi in cui il primo processo ad essere schedulato in CPU sia A oppure B. Si supponga che il tempo di CPU per i context switch e per l’esecuzione dello scheduler sia nullo.
Si consideri uno scenario in cui al tempo T0 nasca un processo P0 puramente CPU-bound di durata (tempo di CPU) pari a 10 secondi ed al tempo T0 + 3 secondi P0 origini un altro processo P1 puramente CPU-bound di durata (tempo di CPU) pari a 6 secondi. Supponendo che le durate dei processi siano note al tempo della loro generazione, e che il tempo di CPU per eseguire uno scheduler sia trascurabile. si calcoli il tempo massimo di completamento del processo P1 nel caso in cui il sistema abbia come scheduler Shortest Process Next oppure Shortest-Remaining-Time Next.
5 - I/O Management¶
Si consideri inoltre uno scenario in cui arrivino al sistema operativo richieste per accedere alle seguenti tracce di un disco: 33 – 46 – 98 – 12 – 43 – 56 – 78 - 77 – 25. Si determini la sequenza effettiva di schedulazione delle operazioni verso il disco considerando che:
al più 4 richieste per volta possono essere immagazzinate nella coda di scheduling;
la testina sia inizialmente posta sulla traccia 100 del disco;
l’algoritmo utilizzato è SCAN.
6 - File management¶
Si consideri un file system con allocazione a catena ed accesso indicizzato. Dato un file:
contente 1M record;
il relativo indice ha taglia pari a 512 record e contiene 128 chiavi uniformemente distribuite nel file;
memorizzato su un dispositivo di massa, la cui taglia di un blocco è pari a 4096 record.
Calcolare la latenza massima e minima considerando che:
il tempo medio di accesso ad un blocco è 10ms;
l’accesso ad una chiave dell’indice in ram è pari a 1ms.
Mostra/Nascondi Soluzione
Assunzioni:
L’indice è memorizzato su disco
L’indice deve essere prima caricato in ram per poter essere utilizzato
RecordID e RiferimentoBlocco hanno pari taglia
Svolgimento:
Taglia di una chiave nell’indice = TagliaIndice/NumeroChiavi = 512R/128 = 4R
Taglia di un riferimento = 2R
Record utilizzabili all’interno di un blocco per memorizzare dati di file = Taglia di un blocco - Taglia di un riferimento = 4096-2 = 4094
Numero di blocchi per memorizzare il file = Numero di record nel file / record utilizzabili = ceil(10^6/4094) = 245
Distanza media tra due blocchi indicizzati = ceil(Numero di blocchi / numero di chiavi) = 2
Latenza minima: accesso ad un blocco indicizzato, indice già presente in RAM.
Risultato = Tempo di accesso a indice + Accesso al blocco indicizzato = 1ms +10ms = 11ms
Latenza massima: accesso al blocco più lontano da quello indicizzato, indice NON presente in RAM.
Risultato = Tempo di caricamento indice + Tempo di accesso a indice + (Numero di blocchi per indice)*(Tempo di accesso al blocco indicizzato) = +10ms + 1ms +2*10ms = 31ms
Si consideri un file system con allocazione indicizzata ospitato su un dispositivo i cui blocchi hanno taglia pari a 1024 record e un riferimento a blocco occupa 8 record. Il record di sistema ha:
128 entry per accesso diretto;
4 entry per accesso indiretto;
4 entry per accesso doppiamente indiretto.
Qual è la taglia massima di un file in record?
Si consideri inoltre senario dove un processo P apra un file F (attualmente non in uso da parte di alcun processo) e poi esegua 2 fork(). Indicare il numero delle sessioni di I/O verso il file F a valle dell’esecuzione delle 2 fork() da parte di P.
Si consideri un dispositivo di memoria di massa con blocchi di taglia pari a 4 KB, indici di blocchi di taglia pari a 4 byte, ed un record di sistema contenente in totale 12 indici di cui N diretti ed M indiretti. Si determini il valore di N ed M, qualora esista, che possa permettere di allocare file di taglia almeno pari a 4 GB.
Si supponga di avere un file system che supporta il metodo di allocazione a catena. Si supponga inoltre che il dispositivo di memoria di massa ove il file system è ospitato abbia blocchi di taglia pari a 4 K record, e che un indice (puntatore) di blocco di dispositivo sia espresso con 16 record. Si supponga inoltre di avere un file F di taglia pari a 16 M record. Si calcoli il numero di blocchi necessari ad allocare il file sul dispositivo di memoria di massa secondo lo schema a catena.
7 - Gestione della memoria¶
Si consideri il caso di memoria virtuale basata su paginazione a più livelli, indirizzi logici e fisici a N bit, pagine di 4MB e tabelle pari alla dimensione di una pagina. Rispondere alle seguenti domande considerando N pari a 40 bit e 48 bit.
Quanti bit servono per spiazzarsi all’interno di una pagina?
Quanti bit servono per identificare una pagina nel caso di N uguale a 40 bit e 48 bit?
Supponendo di utilizzare un numero di bit per entry in una tabella pari alla minima potenza di 2 necessaria a memorizzare un frame number, quante entry possono essere memorizzate in una tabella?
Quanti livelli sono necessari?
Qual è la struttura dell’indirizzo e l’utilizzo dei bit nel suddetto schema di paginazione?
Qual è il numero massimo di frame di memoria impegnati da un processo nel caso in cui il numero delle tabelle a qualsiasi livello correntemente usate per quel processo in suddetto schema di paginazione sia pari a 10?
Data una memoria principale di 4 frame, si determini quanti e quali page fault vengono generati dagli algoritmi FIFO, LRU e Ottimo per la sostituzione delle pagine in sistemi con memoria virtuale data la seguente traccia: 0 9 0 3 5 7 9 0 9 6 7 8 9 7 6 4
Mostra/Nascondi Soluzione
FIFO: #PageFault = 11
0
9
0
3
5
7
9
0
9
6
7
8
9
7
6
4
0
9
9
3
5
7
7
0
9
6
6
8
8
7
7
4
E
0
0
9
3
5
5
7
0
9
9
6
6
8
8
7
E
E
E
0
9
3
3
5
7
0
0
9
9
6
6
8
E
E
E
E
0
9
9
3
5
7
7
0
0
9
9
6
Least-Recently Used: #PageFault = 10
0
9
0
3
5
7
9
0
9
6
7
8
9
7
6
4
0
9
0
3
5
7
9
0
9
6
7
8
9
7
6
4
E
0
9
0
3
5
7
9
0
9
6
7
8
9
7
6
E
E
E
9
0
3
5
7
7
0
9
6
7
8
9
7
E
E
E
E
9
0
3
5
5
7
0
9
6
6
8
9
Optimal: #PageFault = 8
0
9
0
3
5
7
9
0
9
6
7
8
9
7
6
4
0
0
9
9
9
9
0
9
7
7
9
9
7
6
6
6
E
9
0
0
0
0
9
7
9
9
7
7
6
7
7
7
E
E
E
3
3
7
7
0
0
6
6
6
9
9
9
9
E
E
E
E
5
3
3
3
3
3
3
8
8
8
8
4
Considerando uno schema di paginazione a 3 livelli in cui la tabella di primo livello sia costituita da 4 K elementi, quella di secondo livello da 2 K elementi e quella di terzo livello da 1 K elementi, si determini il numero massimo di pagine gestibili all’interno dello spazio di indirizzamento di un processo.
Si consideri una sequenza di generazione di 4 processi, P4, P1, P2 e P3. P1 e P2 hanno taglia 1MB, P3 ha taglia 2 MB e P4 ha taglia 4 MB. Il sistema con multiprogrammazione è caratterizzato da:
una memoria di lavoro di 7 MB di cui 1 MB sia riservato per il sistema operativo
un meccanismo di allocazione dei processi basato su partizioni dinamiche.
Assumendo che P4 non termini prima di P3, si determini quale deve essere la relazione tra il tempo di completamento di P1 e P2 ed il tempo di nascita di P3 affinché, e sotto quali condizioni, ognuno dei 4 processi possa essere correttamente allocato in memoria all’atto della sua creazione.
Mostra/Nascondi Soluzione
7
P2
P3
6
P1
5
P4
4
3
2
1
MONITOR
Siano S_i e T_i rispettivamente l’istante di inizio e terminazione del processo i
Vincoli:
S_4 < S_1 < S_2 < S_3
T_4 > S_3
Soluzione:
S_3 > max(T_1, T_2)
Esercizi di programmazione¶
Warning
Alcuni esercizi possono deliberatamente ammettere più di una implementazione. Di conseguenza, le soluzioni proposte potrebbe non essere le uniche ammissibili.
1 - Riscaldamento¶
Scrivere un programma che:
prende una stringa da tastiera e la inserisce all’interno di un buffer allocato dinamicamente nella heap da parte della funzione scanf().
Copia poi tale stringa all’interno di un secondo buffer allocato sullo stack della taglia necessaria a contenerla.
Libera quindi il buffer allocato nella heap.
Stampa sullo schermo la stringa copiata nel buffer allocato sullo stack.
Scrivere un programma che:
prende una stringa passata come primo argomento (i.e.
char *argv[]) al programma stesso quando questo viene eseguito.Copia tale stringa all’interno di un buffer di dimensione fissa facendo attenzione a non superare il limite imposto dalla taglia, e stamparla quindi sullo schermo.
Rigira la stringa (primo carattere in ultima posizione, secondo carattere in penultima posizione, ecc.) senza fare utilizzo di un ulteriore buffer
Stampa anche questa stringa sullo schermo.
2 - Processi e threads¶
Scrivere un programma in C che:
prende inizialmente una stringa da input (può contenere anche spazi bianchi) e la salva in un buffer
fork-a un processo figlio che manda in stampa la stessa stringa acquisita dal processo padre.
Il processo padre termina solo dopo che il processo figlio ha terminato (verificare che tale ordine è rispettato stampando i PID dei processi).
Scrivere un programma in C che:
prende inizialmente una stringa da input (può contenere anche spazi bianchi) e la salva in un buffer
fork-are 2 processi figli che contribuiscono a stampare la stringa inversa della stringa acquisita dal processo padre.
Il processo padre termina solo dopo che i processi figli hanno terminato.
Scrivere un programma in C che:
prende inizialmente N (a piacere) stringhe rappresentanti N directory corrette
fork-a quindi N processi che andranno ad eseguire il comando ls su una directory differente.
Il processo padre termina dopo i processi figli
Svolgere l’esercizio 2.1 utilizzando threads piuttosto che processi.
Svolgere l’esercizio 2.2 utilizzando threads piuttosto che processi.
Implementare l’esercizio di teoria 3.1 in C.
3 - File¶
Nei sistemi operativi UNIX, /dev/urandom è un dispositivo a caratteri (char device) virtuale in grado di generare numeri casuali. Nello specifico, l’operazione di lettura dal relativo file produce byte casuali. Scrivere un programma C che genera un file con contenuto interamente randomico. Il programma:
prende come parametri da linea di comando: un numero N e una stringa S da usare come nome del file da creare;
crea un file S contenente N byte randomici;
utilizza il dispositivo /dev/random come sorgente di numeri pseudo-casuali.
Dato un file binario contenente un sequenza di 2^15 interi di tipo short, scrivere un programma che crea N processi o threads, i quali leggono il contenuto del file ed individuano il valore minimo e massimo contenuto nel file. Nel fornire una soluzione rispettare i seguenti vincoli:
ciascun intero non può essere letto da più di un thread/processo;
ciascun thread/processo può leggere il medesimo intero al più una volta;
ciascun thread/processo può allocare memoria nell’heap per al più 512 byte;
N è un parametro definito a tempo di compilazione o tramite linea di comando;
N è minore o uguale a 8;
è ammesso allocare di variabili globali (data) e locali (stack) per memorizzare tipi primitivi (puntatori, int, short, char, long, etc.) per al più 128 byte;
per generare il file utilizzare la soluzione dell’esercizio 3.1.
Scrivere un programma C invert che dato un file A ne inverte il contenuto e lo memorizza in nuovo file B. Il programma deve:
riportare il contenuto di A in memoria;
invertire la posizione di ciascun byte utilizzando un numero N di thread/processi concorrenti;
scrivere il risultato in un nuovo file B;
prendere A, B e N come argomenti da linea di comando.
Si scriva il codice di una funzione C con la seguente interfaccia
void tunnel(int descriptors[], int count)tale che, se eseguita, porti l’applicazione a gestire, per ogni file-descriptor dell’array descriptors l’inoltro del flusso dei dati in ingresso verso il canale di standard-output dell’applicazione. Il parametro count indica di quanti elementi è costituito l’array descriptors. L’inoltro dovrà essere attuato in modo concorrente per i diversi canali.Si scriva una funzione C con la seguente interfaccia
void file_check(char *file_name, int num_threads). Tale funzione dovrà lanciare num_thread nuovi threads, in modo che ciascuno di essi legga stringhe dallo standard input, e per ogni stringa letta verifichi l’occorrenza di tale stringa all’interno di ciascuna riga del file il cui path è identificato tramite il parametro file_name, e stampi la stringa su standard output in caso affermativo.Scrivere un programma C in cui dato un file A, una stringa B e un intero N, vengano creati N thread/processi che cerchino se all’interno del file A esiste una linea uguale a B.