testo b

SISTEMI OPERATIVI E LABORATORIO
(Indirizzo Sistemi e Reti)
5 luglio 2004
Cognome:____________________________________Nome:____________________________
Matricola:___________________________________________
Scelgo di svolgere (marcate solo una delle due scelte possibili):
[ ] solo la parte relativa al laboratorio UNIX
[ ] la parte relativa al laboratorio UNIX e la parte relativa alla teoria del corso
Ricordate che non potete usare calcolatrici o appunti. Siate sintetici nelle vostre risposte, anche
quando è richiesto di motivarle, sono sufficienti poche righe per rispondere correttamente.
ESERCIZI RELATIVI AL LABORATORIO UNIX
ESERCIZIO 1 (9 punti)
(a)
Indicate il contenuto di uno script shell (che chiameremo estrai) che, ricevuto in input il nome di un
file di testo esistente (che chiameremo infile), e il nome di un nuovo file (che chiameremo outfile),
inserisce in outfile la riga di infile che viene lessicograficamente per penultima. Lo script shell non
deve utilizzare file temporanei.
Ad esempio se il contenuto di un file pippo è il seguente:
pippo:
valeria
aldo
paola
bruno
dino
claudia
la chiamata di:
$>estrai pippo pluto
produce il seguente file pluto:
pluto:
bruno
estrai:
sort $1 | tail –2 |head –1 > $2
b) Che comando dobbiamo usare per rendere il file eseguibile da tutti gli utenti del sistema,
incluso il gruppo di appartenenza del proprietario del file, e il proprietario stesso?
chmod a+x estrai oppure chmod ugo+x estrai
c) Che comando dobbiamo usare per fare in modo che il comando estrai possa essere lanciato
da qualsiasi utente e funzionare correttamente anche quando il primo file passato in input è
leggibile solo dal proprietario di estrai?
Chmod +s estrai
d) Cosa succede se viene eseguito “estrai pippo pluto” e pluto è un file esistente (e
modificabile da chiunque)?
Il contenuto di pluto viene sostituito dalla seconda riga di pippo.
e) Illustrate i differenti effetti nel sistema di questi due comandi (assumete che prima
dell’esecuzione di uno dei comandi non esista nella cartella corrente un file di nome
“penultima”):
1) ln estrai penultima
2) cp estrai penultima
1) inserisce nella cartella in cui è lanciato una nuova entry con nome “penultima” a cui è associato il
lo stesso numero di i- node associato alla entry “estrai”. Il link counter di questo i- node è
incrementato di uno.
2) inserisce nella cartella in cui è lanciato una nuova entry con nome “penultima” a cui è associato il
un nuovo i- node il cui link counter è settato a uno. Viene eseguita una copia dei blocchi dei dati di
“estrai” e associata all’i- node di “penultima”.
ESERCIZIO 2 (9 punti)
Si consideri il seguente programma C:
1 main (int argc, char *argv[])
2 {
3 int myvar, p1, p2;
4 myvar = 0;
4 p1 = fork();
5 if (p1 == 0) {myvar = myvar+10;
6
printf(“%d”,myvar);
7
for(;;) sleep(1);}
8 p2 = fork();
9 if (p2 == 0) {myvar = myvar+10;
10
if (myvar == 0 } kill(p2,SIGKILL);
11
if (myvar == 20 } kill(p1,SIGKILL);
12
if (myvar == 10 } kill(getppid(),SIGKILL);
13
exit(0);
14
}
15 if (p1 == 0 || p2 == 0) myvar = myvar +1; // si ricorda che || è l’operatore logico or
16 printf(“%d”,myvar);
17 for (;;) system(“sleep 1);
18 printf(“ciao ciao!”);
19 }
si supponga che tutte le system call chiamate nel programma vengano correttamente eseguite.
a) qual è il valore stampato per la variabile myvar alle righe 6, e 16, assumendo che siano
eseguite?
Alla riga 6: 10; alla riga 16: 0;
b) Qual è l’effetto dell’esecuzione del codice del secondo processo figlio del programma?
Termina immediatamente il processo padre
c) Si supponga che nel sistema, prima dell’esecuzione del programma, siano presenti N
processi. Quanti processi saranno presenti nel sistema dopo la terminazione del secondo
figlio del programma?
N+1. Il processo p2 termina dopo aver ucciso il processo padre, mentre p1 cicla all’infinito.
d) Descrivete brevemente il funzionamento della system call kill. Insieme a quale altra system
call viene di solito usata la system call kill, e qual è la funzione di quest’altra system call?
Vedere i lucidi sulle system call a partire da pag. 16
e) Che cosa fa la system call getppid()?
Restituisce il process- id del processo padre del processo chiamante
f) Supponete che l’istruzione di riga 17 venga sostituita da: “wait(0);”. Indicate una modifica
al codice in modo tale che la scritta “ciao ciao!” venga sicuramente stampata.
Basta fare in modo che non venga eseguito il ramo then del condizionale di riga 12.
ESERCIZIO 3 (9 punti)
Per le risposte alle domande a-c vedere i lucidi usati a lezione, numero 5 e 11
a) Quali informazioni principali contiene un i- node?
b) Illustrate brevemente se volete potete aiutarvi con un semplice disegno) il modo nel quale,
attraverso un i- node, il SO memorizza in quali blocchi del disco sono allocati i dati del file
associato a quell’i- node.
c) Scegliete una dimensione adeguata per i blocchi dell’hard disk e per il numero di byte usati
per memorizzare il numero di un blocco (il puntatore al blocco), e in base ai valori scelti
riportare la formula che permette di calcolare la massima dimensione di un file in un SO
Unix con le caratteristiche scelte.
d) Elencate almeno una informazione utilizzata negli i- node portati in ram (gli in-core i-node)
che non e’ invece presente negli i- node su disco.
Il numero di istanze attive del file (reference counter)
e) Dove è memorizzato il path name assoluto di in file unix?
Da nessuna parte.
f) Si consideri un file system Unix in cui non sono presenti link simbolici. Sia N il numero di
tutti i nomi di tutti i file regolari presenti in qualsiasi directory del file system e sia I il
numero di -i node usati nel file system per file regolari (esclusi quindi gli -i node liberi).
Quale delle seguenti relazioni tra parentesi è sicuramente vera? ( N > I; N ? I; N = I; N ? I;
N < I) Motivate la vostra risposta.
N maggiore o uguale di I; poiché ad ogni i- node possono essere associati uno o più hard
link (nomi di file)..
ESERCIZI RELATIVI ALLA PARTE DI TEORIA DEL CORSO
ESERCIZIO 1 (9 punti)
(Le uniche conversioni in/dal decimale necessarie sono quelle per convertire una entry della PT.
Tutti i numeri decimali della PT coinvolti nell’esercizio sono facilmente convertibili in esadecimale.
L’esercizio è una variante numerica di quelli dati nel compito del 9 aprile 2003, e visti anche a
lezione.)
In un sistema con memoria virtuale le pagine hanno una dimensione di FFFF byte, la RAM è fatta
di 7FF frame, e lo spazio di indirizzamento logico massimo è di FF pagine.
a) Qual è la lunghezza in bit di un indirizzo logico? 24 bit (216 · 28 = 224 )
b) Qual è la lunghezza in bit di un indirizzo fisico? 27 bit (216 · 211 = 227 )
c) Si consideri la PT sottostante (attenzione: nella tabella i numeri sono tutti in base decimale), e si
dia l’indirizzo fisico in binario corrispondente al seguente indirizzo virtuale:
0F4B12: =
n. di pag. = 0F (15 decimale), offset = 4B12 ? 07E 4B12 = 000 0111 1110 0100 1011 0001 0010
n. pagina n. frame Valido/invalido
0
52
v
1
100
v
2
x
i
3
x
i
4
x
v
5
1
v
6
70
v
7
18
v
8
x
i
9
x
i
10
9
v
11
87
v
12
124
v
13
21
v
14
56
v
15
126
v
16
127
v
d) Perché può essere necessario paginare la tabella delle pagine?
Perché è troppo grande, e non può essere contenuta in un unico frame (o in un numero
sufficientemente piccolo di frame adiacenti).
e) Si dia un esempio di indirizzo logico generato dalla CPU che, rispetto alla tabella delle pagine
riportata, potrebbe essere correttamente tradotto in un corrispondente indirizzo fisico, ma che
genera un page fault perché la pagina indirizzata non è caricata in memoria.
030000: = N. di pagina = 03; offset = 0000 ? page fault
f) A cosa serve un algoritmo di rimpiazzamento delle pagine?
A scegliere la pagina vittima, ossia la pagina in ram che deve essere rimossa per far posto ad una
pagina mancante che ha provocato un page fault.
g) indicate e (descrivete il criterio di scelta della pagina vittima che adottano) due diversi algoritmi
di rimpiazzamento delle pagine.
LRU: sceglie la pagina riferita meno di recente
FIFO: sceglie la pagina portata in memoria meno di recente.
ESERCIZIO 2 (9 punti)
a) riportate lo pseudocodice che descrive l’implementazione dell’operazione di signal su un
semaforo. A cosa serve la system call usata nello pseudocodice?
Vedere lucidi usati a lezione, sezione 7.4.2. lucido 48
b) Descrivete brevemente il problema di base che può essere risolto mediante l’uso di semafori
Il problema della sezione critica, in cui più processi che devono usare un insieme di variabili
condivise devono farlo in maniera mutuamente esclusiva.
c) Elencate le tre proprietà fondamentali che deve avere una corretta soluzione al problema
descritto al punto c)
mutua esclusione, progresso, attesa limitata
d) Perche’ i semafori sono preferibili ad una soluzione come l’algoritmo di dekker, o
l’algoritmo del fornaio, o gli algoritmi che usano speciali istruzioni ha rdware?
Perché evitano il busy-waiting
e) Quali problemi possono comunque sorgere dall’uso errato dei semafori?
Se non si bilanciano correttamente le operazioni di wait e signal si può verificare deadlock,
starvation, o non e’ assicurata la mutua esclusione.
f) Che differenza c’e’ tra un semaforo binario e un semaforo contatore?
Con un semaforo contatore possiamo stabilire quanti processi, al piu’, possono usare
contemporaneamente una risorsa (un dispositivo, un ‘area di memoria condivisa). Un semaforo
binario è usato per implementare un uso mutuamente esclusivo della risorsa stessa.
ESERCIZIO 3 (9 punti)
a) Quattro processi arrivano al tempo indicato e consumano la quantità di CPU indicata nella tabella
sottostante)
Processo T. di arrivo Burst
P1
0
10
P2
1
6
P3
1
5
P4
11
3
Calcolare il turnaround medio per i processi nel caso dell’algoritmo di scheduling SJF preemtpive
(shortest remaining time first).
SJF preemptive:
(0)….P1 …(1) …. P3….(6)….P2….(12)….P4….(15)….P1…(24)
P1 = 24; P2 = 11; P3 = 5; P4 = 4; 44/4 = 11
b) Se ricalcolassimo il turnaround time per un algoritmo di scheduling SJF non preeptive,
otterremmo probabilmente un valore uguale, maggiore o minore del valore ottenuto al punto a)?
maggiore.
c) SJF preemptive garantisce l’assenza di starvation? e SJF non preemtpive? Perché?
No, no, perché potrebbero arrivare in coda di ready sempre nuovi processi con un CPU time
inferiore a processi già in coda e in attesa di essere schedulati.
d) elencate almeno altri due criteri che, oltre al turnaround time, vengono comunemente usati per
valutare la bontà di un algoritmo di scheduling.
Massimizzare l’uso della CPU, throughput, tempo di attesa (waiting time), tempo di risposta.
f) in quali tipi di sistemi viene normalmente usato l’algoritmo di scheduling round robin?
nei sistemi time sharing
g) cosa succede se il quanto di tempo usato nell’algoritmo di scheduling RR diventa arbitrariamente
grande?
Round robin si riduce ad un algoritmo FIFO.