SISTEMI OPERATIVI E LABORATORIO (Indirizzo Sistemi e Reti)
6 dicembre 2005
Cognome:____________________________________Nome:____________________________
Matricola:___________________________________________
ESERCIZIO 1, teoria (7 punti)
a) riportate lo pseudocodice che descrive l’implementazione dell’operazione di wait su un semaforo. A cosa serve la system call usata nello pseudocodice?
Vedere lucidi usati a lezione, sezione 7.4.2.
b) 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 hardware?
Perché evitano il busy-waiting
c) Descrivete brevemente i 3 che problemi possono comunque sorgere dall’uso errato dei semafori
Se non si bilanciano correttamente le operazioni di wait e signal si può verificare deadlock (due o più processi in attesa circolare), starvation (un processo non riesce mai ad accedere ad una risorsa di cui ha bisogno), o non e’ assicurata la mutua esclusione (due processi contemporaneamente all’interno di una sezione critica).
d) Se il valore corrente di una variabile semaforica è un numero positivo N, che informazione ci da tale valore?
E’ il numero di processi che possono “contemporaneamente superare” il semaforo senza venire bloccati.
e) Se il valore corrente di una variabile semaforica è un numero negativo -N, che informazione ci da tale valore?
E’ il numero di processi atualmente sospesi su quel semaforo
ESERCIZIO 2, teoria (7 punti)
Un sistema paginato ha una memoria fisica di 8k byte suddivisa in 16 frame. La page table di un processo ha la dimensione massima di un frame, e in questo caso contiene 100 (esadecimale) entry.
(a) Qual è, in esadecimale, l’offset massimo possibile in un indirizzo di questo sistema? 1FF.
(ossia 111111111 binario, ossia 511 decimale. infatti ogni frame è grande 8k/16 = 512 byte, e i byte vanno dallo 0-esimo al 511-esimo)
(b) Qual è la dimensione dello spazio di indirizzamento logico del sistema? 217 byte. (Infatti un processo può essere formato al massimo da 100 esadecimale = 28 entry, e una pagina è grande 29 byte)
(c) Il sistema deve usare un algoritmo di rimpiazzamento delle pagine? Motivate la vostra risposta.
Evidentemente si, visto che un processo può avere fino a 256 pagine, ma la RAM ne contiene al massimo 16.
(d) Se nel sistema considerato sono mediamente attivi 3 processi, qual è la quantità di memoria massima che viene sprecata a causa del meccanismo di allocazione dei processi in RAM (tascurando lo spazio necessario per memorizzare le page table dei processi)? Motivate la vostra risposta.
3*511 byte. Infatti, l’ultimo frame di ogni processo potrebbe essere utilizzato solo per un byte..
(e) Perché i moderni sistemi operativi usano una gestione paginata della memoria primaria?
(f) Perché implementano normalmente anche la memoria virtuale?
(g) Descrivete brevemente il problema più grave che si può presentare in un sistema operativo che implementi la memoria virtuale, e una possibile soluzione per limitare questo problema.
Per le ultime 3 domande vedere i lucidi del capitolo 10.
ESERCIZIO 3, Unix (6 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 vuole attendere la normale terminazione di figlio_2 e poi terminare egli stesso (notate che figlio_2 potrebbe terminare indifferentemente prima o dopo di figlio_1, poiché questo dipende della durata delle funzioni chiamate dai due processi figli). Se alla terminazione di figlio_2, figlio_1 non è ancora terminato, padre uccide figlio_1 e termina egli stesso.
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, terminated;
p1 = fork();
if ( p1 == 0) {
myfunction1(argv[1]);
exit(0);
} p2 = fork();
if ( p2 == 0) {
myfunction2(argv[2]);
exit(0);
}
terminated = wait(0);
if (terminated == p2) kill(p1, SIGKILL);
else wait(0);
}
b)
Assumiamo che Myfunction1 restituisca un qualche valore intero che dipende dall’elaborazione dell’argomento passatogli in input. In quali modi sarebbe possibile rendere disponibile questo valore intero a padre? (motivate la vostra risposta).
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.
(c)
suggerite a parole (o se preferite, con opportuno pseudo-codice) una modifica al programma, in modo che, sicuramente, il secondo figlio generato dal programma termini solo dopo che è terminato il primo.
E’ sufficiente usare un semaforo SEM inizializzato a 0. Prima delle rispettive exit(), il primo figlio esegue una signal(SEM) e il secondo figlio una wait(SEM) (dove la signal e la wait sono una qualche implementazione delle due operazioni semaforiche viste a teoria, e non sono le system call unix di uguale nome)
(d)
supponete che il codice di myfunction1 sia in realtà contenuto in un eseguibile /bin/myfunction1prog che accetta un unico argomento come input. Indicate le modifiche da apportare al programma perché si comporti esattamente come nelle richieste del punto (a).
E’ sufficiente lanciare myfunction1prog con una exec. Al posto della riga di chiamata di myfunction1 quindi è sufficiente mettere:
exec(“/bin/myfunction1prog”, “/bin/myfunction1prog”, argv[1], NULL);
ESERCIZIO 4, Teoria+Unix (7 punti)
Per le risposte a-e si vedano i lucidi relativiusati a lezione Se lo desiderate, aiutatevi nelle risposte con opportuni disegni
a) Quali sono i vantaggi dell’allocazione indicizzata dello spazio in memoria secondaria?
b) Quali sono invece gli svantaggi di questo tipo di allocazione?
c) A quale metodo di allocazione dello spazio in memoria primaria assomiglia la tecnica dell’allocazione indicizzata dello spazio su disco?
d) Descrivete le due varianti dell’allocazione indicizzata viste a lezione per gestire file di dimensione arbitraria.
e) Descrivete l’ulteriore variante utilizzata nei sistemi Unix
f) Considerate un sistema Unix con blocchi di 1024 byte e puntatori a i-node scritti su 4 byte.
Di un file di testo A lungo 300k byte è già presente in RAM il numero dell’i-node a cui è associato. Quanti accessi in memoria secondaria sono necessari per portare in RAM l’ultimo blocco del file? (motivate la vostra risposta)
4. I caratteri del file da 267K a 300K sono indirizzati con il secondo livello di indirizzamento indiretto. Quindi, sono necessari: 1 accesso al disco per leggere l’i-inode, 2 accessi per leggere i due blocchi dellla catena di indirizzamento indiretto, 1 accesso per leggere il blocco di dati.
g) Date l’esempio di 4 comandi Unix diversi che mostrano e / o modificano uno dei campi di un i-node (per ogni comando dato dite qual è il campo dell’i-node che viene visualizzato / modificato, e se necessario specificate chiaramente quali ipotesi occorre fare per ciascun comando affinché i campi dell’i-node siano effettivamente visualizzati/modificati.).
Assumete pure che siano presenti tutti i permessi necessari a lanciare correttamente i comandi.
In tutti i casi
ls –l nomefile // visualizza il campo dimensione di nomefile; se nomefile esiste touch nomefile // aggiorna il campo date di nomefile
cat tmpfile >> nomefile // modifica il campo dimensione di nomefile se tmpfile ha una dimensione diversa da 0
cp fileA fileB // viene modificato il campo date dell’i-node della current-dir.
