Indirizzo Sistemi e Reti) 12 aprile 2007 ESERCIZI RE

(1)

SISTEMI OPERATIVI E LABORATORIO

(Scritto anni precedenti all’A.A. 05/06 - Indirizzo Sistemi e Reti) 12 aprile 2007

Cognome:____________________________________Nome:____________________________

Matricola:___________________________________________

Ricordate che non potete usare calcolatrici o materiale didattico. Siate sintetici nelle vostre risposte, anche quando è richiesto di motivarle, sono sufficienti poche righe per rispondere correttamente. (Si ricorda che gli studenti degli anni precedenti devono sostenere l’intero scritto).

ESERCIZI RELATIVI ALLA PARTE DI TEORIA DEL CORSO

(il punteggio conseguito farà media con quello ottenuto nella parte di laboratorio. E’ comunque necessario prendere almeno 18 punti per considerare passata la parte di teoria.)

ESERCIZIO 1 (9 punti)

All’atto dell’installazione di un SO su una macchina, è possibile scegliere se usare pagine grandi 2¹² byte oppure grandi 2²² byte. La dimensione dello spazio di indirizzamento logico rimane comunque la stessa. La macchina su cui viene installato il SO usa 30 bit per scrivere un indirizzo fisico, e lo spazio di indirizzamento fisico è 4 volte più piccolo dello spazio di indirizzamento logico (nel seguito, motivate tutte le risposte che date).

a) Nel caso di pagine da 2²² byte, quanto può essere grossa, al massimo, la page table di un processo?

Si osservi innanzi tutto che lo spazio di indirizzamento logico è pari a 2³² byte.

Una page table può avere al massimo 2³² / 2²² entry, mentre il numero massimo di frame del sistema è pari a 2³⁰ / 2²² = 2⁸. Quindi, abbiamo bisogno di 1 byte per scrivere il numero di un frame, e una page table occuperà al massimo 2¹⁰ byte (escludendo eventuali bit di validità e dirty bit).

b) A seconda della dimensione delle pagine, il sistema potrebbe usare una paginazione a più livelli?

pagine da 2²² byte: un processo può occupare al massimo 2¹⁰ pagine, e tutta la page table di quel processo può sicuramente essere contenuta in un’unica pagina. Non è necessaria la paginazione su più livelli.

pagine da 2¹² byte: una page table può avere fino a 2²⁰ entry. Lo spazio di indirizzamento fisico è suddiviso in 2³⁰ / 2¹² = 2¹⁸ frame, e 3 byte sono sufficienti per scrivere il numero di un qualsiasi frame. Al massimo una page table occupa quindi 3 * 2²⁰ byte = pari a circa 3 Mbyte. (se anche si usassero esattamente 18 bit per scrivere il numero di un frame, sarebbero necessari più di 2 Mbyte per memorizzare la page table più grossa. Poiché un frame è molto più piccolo, la paginazione su più livelli potrebbe essere necessaria.

c) se il sistema adotta una paginazione su più livelli, i programmi gireranno in media più o meno velocemente che nel caso in cui venisse adottata una paginazione ad un solo livello?

(2)

Meno velocemente, perché in caso di TLB miss occorre accedere più volte alla RAM per tradurre un indirizzo logico in uno fisico. Se però la maggior parte dei processi può essere contenuta in un unico frame, allora è anche possibile che il numero di TLB miss diminuisca drasticamente, aumentando così le prestazioni.

d) Il sistema deve usare un algoritmo di rimpiazzamento delle pagine?

Si, perché lo spazio di indirizzamento logico è più grande di quello fisico.

e) Cosa fa un algoritmo di rimpiazzamento delle pagine?

Seleziona la pagina vittima da rimuovere, per far posto alla pagina che ha generato page fault.

f) Che tipo di codice genera il compilatore di questo sistema?

Codice dinamicamente rilocabile

g) Elencate brevemente gli svantaggi della paginazione della memoria.

Vedere i lucidi della sezione 8.4.1 e 8.4.2

a) riportate lo pseudocodice che descrive correttamente l’implementazione dell’operazione di wait su un semaforo.

Wait(semaphore S) : S.value--;

if S.value < 0 then

aggiungi questo processo a S.waiting block();

end;

b) Che effetto ha la system call usata nello pseudocodice?

Toglie la CPU al processo che la invoca e manda in esecuzione uno dei processi in Ready Queue. Il processo che ha chiamato block non viene rimesso nella Ready Queue

c) Che informazione ci da il valore corrente della variabile semaforica?

Se positivo, il numero di processi che possono eseguire la wait senza addormentarsi sul semaforo.

Se negativo, il valore assoluto conta quanti processi sono in attesa su quel semaforo.

d) Riportate lo pseudocodice di tre processi che devono avere il seguente comportamento: i processi A e B possono eseguire, rispettivamente, le procedure <A> e <B> (non importa in quale ordine)

(3)

solo dopo che un altro processo C ha eseguito la procedura <C>. Indicate il valore di inizializzazione del semaforo (o dei semafori) che usate per ottenere l’effetto richiesto.

Semaphore sync = 0;

A B C

… … … wait (sync) wait(sync) <C>

<A> <B> signal(sync)

… … signal(sync)

… … …

Un hard disk ha una dimensione di 2³⁶ byte, suddivisi in blocchi da 2Kbyte. Il sistema operativo che usa l’hard disk adotta una allocazione indicizzata dello spazio su disco, e usa 4 byte per scrivere il numero di un blocco. Sul disco è memorizzato un file A grande 400 Kbyte. Tutti gli attributi del file A sono già in RAM. (nel seguito, tutte le risposte date vanno adeguatamente motivate)

a) Quante operazioni di I/O su disco sono necessarie per leggere il byte numero 204.800 del file?

In un blocco indice possono essere contenuti 2048 / 4 = 512 puntatori a blocco. L’uso di un solo blocco indice è quindi sufficiente a memorizzare i numeri di tutti i blocchi in cui è memorizzato A, per cui sono necessarie 2 operazioni di I/O: lettura del blocco indice, lettura del centesimo blocco del file (in cui è contenuto il byte 204.800).

b) E’ noto che, nel file system memorizzato sull’hard disk, la quasi totalità dei file occupa un solo blocco di dati, e i file restanti occupano due blocchi di dati. In confronto alle altre tecniche di allocazione dello spazio su disco (contigua e concatenata, senza FAT), possiamo dire che viene sprecato tanto o poco spazio sull’hard disk, a causa dell’uso dell’allocazione indicizzata?

Viene sprecato tanto spazio, in quanto per ogni file viene usato anche un blocco indice, che è quasi completamente inutilizzato.

c) Sempre nelle ipotesi del punto b), In confronto alle altre tecniche di allocazione dello spazio su disco (contigua e concatenata), possiamo dire che l’accesso ai dati dei file è più lento o più veloce, a causa dell’uso dell’allocazione indicizzata?

Più lento. Infatti, per leggere i dati di un file occorre sempre prima leggere il suo blocco indice, e quindi sono comunque necessarie due letture su disco. Per le altre tecniche di allocazione invece, nella quasi totalità dei casi basterebbe una lettura su disco, e negli altri casi ne sarebbero sufficienti due.

d) Facendo riferimento ai dati numerici dell’esercizio, se il SO adotta una allocazione indicizzata gerarchica a due livelli (blocco indice esterno e blocchi indice interni che puntano ai blocchi di dati), qual è la dimensione massima che può avere un file del sistema? E se usa l’allocazione indicizzata concatenata?

Indicizzata gerarchica: 2⁹ * 2⁹* 2¹¹ byte = 2²⁹ byte (512 Mega byte)

(4)

Indicizzata concatenata: Illimitata (ovviamente è in realtà limitata dallo spazio effettivamente disponibile sul disco)

e) Considerate la sequente affermazione: lo spazio su disco occupato da una cartella dipende dal numero di file che contiene e dalla posizione di quella cartella nel file system (ossia, in pratica, dalla lunghezza del pathname assoluto della cartella). L’affermazione è vera o falsa? (motivate la vostra risposta).

Falsa, perché dipende solo dal numero di file che contiene. Il pathname di un file non è memorizzato da nessuna parte.

ESERCIZI RELATIVI AL LABORATORIO UNIX

(il punteggio conseguito farà media con quello ottenuto nella parte di teoria) ESERCIZIO 4 (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 altro file esistente (che chiameremo outfile), inserisce al fondo di outfile la prima e l’ultima riga di infile in ordine invertito. Lo script shell può utilizzare al massimo 2 file temporanei, che però devono essere rimossi dallo script shell quando non servono più.

Ad esempio se il contenuto di un file pippo è il seguente:

pippo:

valeria aldo roberta bruno sandro paola

la chiamata di:

$>estrai pippo pluto

produce il seguente output (dove “line1, line2” indicano il contenuto iniziale di pluto) :

pluto:

line1 line2 paola valeria

estrai:

(5)

head -1 $1 > primo tail -1 $1 > ultimo cat ultimo primo >> $2 rm primo ultimo

b) Modificate lo script shell in modo da non usare file temporanei

estrai:

tail -1 $1 >> $2 head -1 $1 >> $2

c) rendete estrai eseguibile dal proprietario e dal suo gruppo. Inoltre, il file non deve essere scrivibile o eseguibile dagli altri utenti del sistema.

chmod ug+x estrai chmod o-xw estrai

d) Che comando si può usare per fare in modo che il comando estrai rimanga in memoria RAM pronto per essere lanciato (ossia per migliorare lo start-up di estrai) anche dopo la sua terminazione (dovuta ad una precedente chiamata)?

Chmod +t estrai

e) che comando dobbiamo dare per spostare (attenzione, non per copiare) estrai nella directory che sta due livelli sopra a quella corrente? )(ossia, se estrai è contenuto in dir1 – la current directory – dir1 è contenuta in dir2 e dir2 è contenuta in dir3, vogliamo spostare estrai in dir3).

mv estrai ../..

ESERCIZIO 5 (9 punti) a)

A partire dallo scheletro di programma C riportato qui sotto, scrivete un programma C che si comporta come segue:

1. Il programma riceve in input due argomenti di tipo stringa (cioè verrà chiamato con:

myprog stringa1 stringa2).

2. Il programma si forka producendo due figli che chiameremo rispettivamente figlio_1 e figlio_2.

3. Figlio_1 esegue una funzione predefinita myfunction1 passando alla funzione, come argomento, il primo argomento passato in input a myprog. Alla terminazione di myfunction1, figlio_1 termina.

4. Figlio_2 esegue una funzione predefinita myfunction2 passando alla funzione, come argomento, il secondo argomento passato in input a myprog. Alla terminazione di myfunction2, figlio_2 termina.

5. Il processo padre si mette in attesa della terminazione dei due figli, e poi termina esso stesso.

(6)

Suggerimento: Avete molto spazio a disposizione nella pagina, ma il programma che dovete scrivere occupa molto meno spazio.

#include <stdio.h>

#include <signal.h>

#include<sys/types.h>

#include<sys/wait.h>

int myfunction1(char *arg)

{/* codice della funzione myfunction1 non ulteriormente specificato */}

int myfunction2(char *arg)

{/* codice della funzione myfunction2 non ulteriormente specificato*/}

main(int argc, char **argv) {

int p1, p2;

p1 = fork();

if ( p1 == 0) {

myfunction1(argv[1]);

exit(0);

} p2 = fork();

if ( p2 == 0) {

myfunction2(argv[2]);

exit(0);

}

wait(0);

}

b)

se il codice di myfunction1 e myfunction2 fosse contenuto in due file eseguibili separati, richiamati da figlio_1 e figlio_2 mediante delle opportune execl, il programma che avete scritto funzionerebbe ancora? (Motivate la vostra risposta)

Si, le exit(0) dei due figli non sarebbero più eseguite, ma i due processi figli terminerebbero normalmente e il padre uscirebbe comunque dalle due wait.

c)

Myfunction1 restituisce un qualche valore intero che dipende dall’elaborazione dell’argomento passatogli in input. Indicate almeno due modi con cui sarebbe possibile rendere disponibile questo valore intero a padre (motivate la vostra risposta).

(7)

I processi padre e figlio_1 hanno spazi di indirizzamento separati, per cui possono scambiarsi informazioni solo attraverso un file, una pipe, una coda di messaggi o un segmento di memoria condivisa.

a) viene eseguito il comando “mkdir newdir”. Qual è il valore del link counter dell’i-node associato a newdir (spiegate la vostra risposta)?

2. Uno per il nome newdir contenuto nella parent directory, e uno per l’alias “.” contenuto nella stessa newdir.

b) Che cosa ci dice, in generale, il valore del link counter di una directory (ad esempio, cosa deduciamo dal fatto che il link counter vale N)?

Quante sottodirectory contiene (se il link counter vale N, la directory contiene N-2 sottodirectory).

c) Supponete che in newdir venga creato un file di testo pippo. Cosa accade del link counter di newdir?

Nulla.

d) Il link counter di pippo vale 2. Vengono eseguiti, in sequenza, i comandi:

ln pippo newfile // si ricorda che “ln” è il comando per creare un nuovo hard link cp newfile pluto

Qual è ora il valore del link counter di pluto? (giustificate la vostra risposta).

1. Infatti, pluto è un nuovo file che contiene una copia del contenuto del file pippo (o newfile), e quindi viene creato con il link counter a 1.

e) un sistema Unix adotta blocchi dell’hard disk da 1024 byte, mentre il numero di un blocco è scritto in un puntatore da 4 byte. Qual è la dimensione massima di un file memorizzabile in questo sistema, seconda la normale allocazione gerarchica indicizzata usata da unix (è sufficiente riportare la formula, non il risultato finale)?

(1024 * 10) + (1024 * 256) + (1024 * 256²) + (1024 * 256³) byte

f) qual è il numero massimo di blocco che può indirizzare un puntatore del sistema (è sufficiente riportare la formula usata per calcolare il numero)?

2³²-1