SISTEMI OPERATIVI E LABORATORIO (Indirizzo Sistemi e Reti)
9 dicembre 2004
Cognome:____________________________________Nome:____________________________
Matricola:___________________________________________
ESERCIZIO 1, teoria (6 punti)
Per tutte le risposte vedere i lucidi usati a lezione, sezione 7.4
a) riportate lo pseudocodice che descrive l’implementazione dell’operazione di wait su un semaforo. A cosa serve la system call usata nello pseudocodice?
b) Quali informazioni ci da il valore corrente della variabile semaforica?
c) I semafori servono per risolvere il problema della sezione critica, ma il codice di una wait è esso stesso una sezione critica. Come è possibile allora implementare correttamente questa system call?
d) Quale problema è comunque connesso all’uso di operazioni di sincronizzazione non strutturate come wait e signal?
ESERCIZIO 2, teoria (7 punti)
Si consideri un sistema in cui un indirizzo logico è scritto su 16 bit, e l’offset massimo possibile in un indirizzo è 127 (in decimale). La RAM della macchina è suddivisa in 256 frame.
(a) Quante entry può avere, al massimo la page table di un processo del sistema?
(b) Il sistema deve usare un algoritmo di rimpiazzamento delle pagine? Motivate la vostra risposta.
(c) Supponete che ogni entry di una qualsiasi page table del sistema sia lunga 2 byte. Quante entry deve contenere, come minimo, la page table di un processo del sistema per poter richiedere di essere a sua volta paginata? Motivate la vostra risposta.
(d) Considerate un sistema con memoria paginata che gira su una macchina in cui non è disponibile un TLB (una memoria associativa). Il sistema sarà più efficiente se usa normali tabelle delle pagine o se usa una inverted page table? Motivate la vostra risposta.
(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.
Soluzione:
(a) 512 entry (2^16 / 2^7).
(b) Si, perché lo spazio di indirizzamento fisico (256 * 2^7 = 2^15) è più piccolo dello spazio di indirizzamento logico (2^16).
(c) Una PT può dover essere paginata quando non può essere completamente contenuta in un frame. Poiché un frame è lungo 128 byte (l’offset massimo e’ infatti 127), può contenere al
massimo 128/2 = 64 entry di page table. Se la page table di un processo ha più di 64 entry, potrebbe dover essere paginata.
(d) Il sistema è più efficiente se usa normali page table, poiché il tempo medio di accesso alla RAM raddoppia, a causa della necessità di accedere alla page table, anch’essa memorizzata completamente in RAM. Ad ogni accesso in RAM, l’inverted page table deve invece essere scandita dall’inizio per trovare l’entry desiderata, e le prestazioni del sistema degradano in media di un fattore pari alla lunghezza della IPT/2.
(e) Per minimizzare i problemi che nascono da una allocazione contigua dello spazio in RAM, eliminando o quasi i problemi di frammentazione interna ed esterna.
(f) Per poter permettere l’esecuzione di processi la cui dimensione è superiore alla memoria primaria disponibile, e/o per permettere l’esecuzione “contemporanea” di un insieme di processi la cui occupazione globale è maggiore delle dimensioni della RAM.
(g) Il problema del trashing, quando la maggior parte dei processi genera un gran numero di page fault che devono essere gestiti dal SO, senza riuscire così a procedere nella normale computazione.
ESERCIZIO 3, Unix (7 punti) (a)
A partire dallo scheletro di programma C riportato qui sotto, scrivete un programma C che può essere eseguito passandogli in input uno o due argomenti. Nei due casi, il programma deve comportarsi come segue:
1 solo argomento in input: il programma si forka. Il processo figlio stampa su terminale l’argomento passato in input e termina. Il processo padre si mette in attesa della terminazione del processo figlio, dopodiché termina se stesso con una kill.
2 argomenti in input: il programma si forka due volte (attenzione, è il processo padre che deve forkarsi due volte, e non il figlio che deve chiamare a sua volta la fork). Il primo figlio generato stampa su terminale il primo argomento passato in input e termina. Il secondo figlio generato stampa su terminale il secondo argomento passato in input e termina. Il processo padre si mette in attesa della terminazione dei due processi figli, dopodiché termina se stesso con una kill.
Suggerimento:
Non è necessario considerare casi diversi da quelli sopra indicati (ossia che l’eseguibile sia lanciato senza argomenti o con 3 o più argomenti), ma se preferite, potete scrivere un programma più generale, dove il padre si forka n volte se sono passati in input n argomenti, e l’i-esimo figlio stampa l’argomento i-esimo. Il padre si mette poi in attesa della terminazione di tutti i figli.
#include <stdio.h>
#include <signal.h>
main(int argc, char **argv) {
int p1, p2, i;
for ( i = 1; i < argc; i++) /* creo i figli */
{
p1 = fork();
if ( p1 == 0)
{
printf("%s\n",argv[i]);
exit(0);
} }
for ( i = 1; i <=argc; i++) /* aspetto i figli */
wait(0);
kill(getpid(),SIGKILL); /* mi uccido */
}
(b)
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.
Risposta
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)
ESERCIZIO 4, Unix (7 punti)
Considerate la seguente porzione di file system Unix:
(a)
Sia tmp la working directory corrente, nella quale è contenuto un programma sorgente prog.c ed il corrispondente eseguibile myprog. Riportate i comandi Unix necessari ad eseguire le operazioni qui sotto elencate usando solo pathname relativi (ciascun comando deve tenere conto dei comandi che sono stati eseguiti prima di lui):
1. copiate prog.c nella directory source: cp prog.c ..
2. spostatevi nella directory bin (che diviene la nuova working directory): cd ../../bin 3. spostate in bin l’eseguibile myprog: mv ../sources/tmp/myprog .
myprograms
bin sources
tmp
4. controllate i permessi di myprog: ls –l myprog
5. rendete myprog eseguibile dal possessore del file e dal gruppo: chmod ug+x myprog 6. rendete la directory bin non scrivibile dagli altri utenti del sistema: chmod o-w . (b)
scrivete una combinazione di comandi Unix che generi un nuovo file num_proc contenente il numero istanze di myprog attualmente in esecuzione del sistema
ps agx | grep myprog | wc –l > num_proc (c)
Supponete che, inizialmente, la cartella sources contenesse solo la sotto-cartella tmp, e che la cartella tmp contenesse solo prog.c e myprog. Disegnate la struttura interna dei “file cartella”
sources e tmp dopo l’esecuzione dei comandi 1, 2 e 3 del punto (a). Segliete dei valori opportuni per gli i-node coinvolti.
35 .
25 ..
40 tmp
60 prog.c
40 .
35 ..
45 prog.c
0 myprog
sources: tmp:
