Sistemi Operativi

Raccolta di domande / risposte d’esame.

(Si ringrazia Mordicchio per le domande e per l’aiuto nello stilare le risposte.

Ti devo un caffè!)

 

D) Si descriva lo scheduler di CPU UNIX tradizionale, illustrando anche gli effetti della system call nice().
Lo scheduler CPU UNIX tradizionale è basato su code multiple con feedback, ognuna delle quali gestita tramite meccanismo Rund Robin e con un proprio livello di priorità. La priorità di ogni singolo processo va periodicamente calcolata tramite la formula base+cpu/2+nice, dove base è la priorità base del processo, cpu è il tempo di utilizzo previsto per la cpu e nice è un valore programmabile attraverso l’utilizzo della system call nice().

D) Si descriva lo scheduler di CPU in sistemi Windows.

Lo scheduler adottato nei sistemi di tipo Windows adotta 32 livelli di priorità divisi in due classi, “real time” e “variable”. La priorità può essere cambiata soltanto nella classe variable, a meno di utilizzare delle apposite system call. Ogni processo ha una priorità base ed i thread che lo costituiscono possono scendere fino a due livelli sotto. Dal momento che la priorità scende se il processo occupa l’intero quanto di tempo a sua disposizione e sale in caso contrario, questo algoritmo di scheduling è considerato meno reattivo dello scheduling utilizzato invece nei sistemi UNIX di tipo tradizionale.

D) Descrivere in modo dettagliato l’algoritmo di scheduling della CPU round robin (time slicing), discutendo l’impatto del timer-slice sull’esecuzione dei processi I/O bound.

Nel caso dell’algoritmo di scheduling di tipo Round Robin Time Slicing, i processi nello stato READY vengono mandati in esecuzione a turno per uno specifico quanto di tempo. Vi è prelazione. Dal momento che la scelta del time-slice ha impatto sul numero di quanti di tempo che occorrono per attivare una richiesta di I/O, questo algoritmo sfavorisce i processi I/O bound e non è adeguato per la gestione dei processi interattivi, in quanto causa sottoutilizzo dei dispositivi di I/O.

D) Si descrivano i meccanismi di paginazione a livelli multipli ed i vantaggi che essi offrono nei sistemi di memoria virtuale. Si consideri inoltre un sistema di paginazione a 2 livelli con indirizzi logici di 32 bit, dei quali 4 vengono usati per identificare la sezione e 6 per identificare la pagina. Si consideri inoltre un processo che abbia due zone di indirizzi logici contigui valide: la zona tra gli indirizzi [0,1GB) e la zona [2GB,3GB). Si identifichi il numero di sezioni valide nella tabella delle pagine ed il relativo indice di sezione.

La paginazione a livelli multipli prevede che per conoscere la posizione di un determinato frame in memoria si ricorra alla “directory delle pagine”, dove sono elencati gli indici dei frame, da cui si ricava prima il numero di pagina all’interno di detta director ed infine il suo offset all’interno della pagina stessa. Nel caso della memoria virtuale, questo meccanismo risulta essere particolarmente vantaggioso in quanto permette di caricare in memoria solo la parte di tabella delle pagine necessaria: in altre parole, la memoria virtuale è utilizzata per gestire la stessa tabella delle pagine.

SSSSPPPP PPOOOOOO OOOOOOOO OOOOOOOO

4 bit sezione S => 2^4 sezioni, 6 bit pagina P => 2^6 pagine ogni sezione, 22 bit offset O.

2^(32-4)=2^28= 268435456 byte = 256 MB => ogni sezione ospita al massimo 256 mb.

Per allocare da 0 a 1GB a partire dalla I sezione, abbiamo bisogno di 1024/256 = 4 sezioni.
Per allocare da 2GB a 3GB utilizziamo 2048/256 =8, 3072/256 = 12 sezioni.

In definitiva, le sezioni che utilizzeremo sono le sezioni I, II, III, IV, VIII, IX, X, XI, XII, cioè 9 sezioni;

0000 0001 0010 0011 0100 0101 0110 0111 1000.

D) Descrivere l’algoritmo dell’orologio per la selezione della vittima nei sistemi di memoria virtuale in ambiente paginato, discutendo anche la variante con bit addizionali. Indicare inoltre, motivando la risposta, se questo algoritmo soffre o meno dell’anomalia di Belady.

Nell’algoritmo dell’orologio si utilizza un reference bit (RB) associato ad ogni frame. Ogni volta che il frame a cui è riferito viene acceduto, tale bit viene settato ad 1. Quando si deve selezionare una vittima per la sostituzione, una “lancetta” scorre l’insieme dei RB settandoli a 0 finché non trova un RB già settato a 0. In quel caso il frame associato ad esso viene selezionato per la sostituzione. Periodicamente, un’altra lancetta denominata RESET setta a 0 i RB.
Esiste una variante di questo algoritmo che prevede l’utilizzo di un ulteriore bit, detto dirty bit (DB), che viene settato ad uno qualora il frame a cui è riferito sia stato modificato dal momento in cui è stato caricato in memoria. In questo caso, la combinazione per la vittima perfetta è DB =0, RB=0.
L’algoritmo dell’orologio soffre dell’anomalia di Belady in quanto nel caso peggiore degenera in un algoritmo di tipo FIFO, che ne soffre.

D) Descrivere la gestione della memoria secondo lo schema partizioni variabili.
D) Descrivere gli schemi di gestione della memoria basati su partizioni dinamiche.

In uno schema a partizioni variabili ogni processo occuperà in memoria la dimensione di cui ha effettivamente bisogno per avere a disposizione la sua immagine intera. Inizialmente i processi vengono allocati di seguito uno dopo l’altro, dunque si creano delle partizioni adiacenti di dimensioni differenti. Nel momoento in cui si rende necessaria l’allocazione di un processo ci si trova davanti a tre scelte: → first fit: si alloca il processo nel primo spazio sufficientemente grande per contenerlo; → best fit: si alloca il processo nello spazio più piccolo in grado di contenerlo; → worst fit: si alloca il processo nello spazio più grande che possa contenerlo, in modo che i frammenti lasciati liberi siano abbastanza grandi da contenere a loro volta dei processi.

D) Descrivere le tecniche di gestione del resident set nei sistemi di memoria virtuale in ambiente paginato.

Esistono tre metodi di gestione per la taglia del resident set: → fissa: alla creazione di un processo gli si assegna un numero fisso di frames, la sostituzione di pagine interesserà soltanto i frames del processo interessato; → variabile: il numero di frames assegnati ad un processo può variare nel tempo e possono venire interessati dalla sostituzione anche frames di processi differenti da quello interessato; → mista: il numero di frames assegnati al processo è variabile, ma la sostituzione di pagine è circoscritta al processo interessato.
La taglia del resident set viene rivalutata a seconda di due parametri: → working set: indica il numero di frames in un processo in un determinato istante in modo da farlo coincidere con la taglia del resident set, allo scopo di sfruttare il principio di località, generalmente non viene applicato in quanto particolarmente complesso; → frequenza di page fault: si considera per impostare la taglia del resident set, in modo da rientrare nella regione di stabilità.

D) Si descriva l’architettura dei buffer cache a sezioni multiple, indicando esplicitamente quali problemi essi risolvono rispetto all’organizzazione a sezione singola.

Questo tipo di architettura pervede che la cache sia divisa in due o più sezioni: → buffer cache a due sezioni: si divide la cache in due sezioni, chiamate OLD e NEW e si attribuisce ad ogni blocco un counter. Ogni volta che il blocco viene riferito e passa dalla sezione OLD alla sezione NEW il counter viene incrementato. Quando si rende necessaria la sostituzione di un blocco, cioè quando la sezione NEW o la sezione OLD sono piene, si sceglie come vittima il blocco con valore di counter minore; → buffer cache a tre sezioni: il meccanismo è lo stesso del buffer cache a due sezioni, con la differenza che in questo caso c’è un’ulteriore sezione tra OLD e NEW chiamata INTERMEDIATE; dunque il counter viene incrementato nel pssaggio INTERMEDIATE -> NEW oppure OLD -> INTERMEDIATE.
Con questi accorgimenti si migliore notevolmente l’efficienza, in quanto a differenza dei casi con algoritmi LRU o LFU non ci si ritrova in situazioni di stallo dove celle con un alto numero di riferimenti ma che non vengono riferite da tempo rimangono in memoria cache oppure dove si verifica un overflow dei numeri di riferimento.

D) Si descrivano i metodi di allocazione dei file, evidenziandone in modo comparativo vantaggi e svantaggi.

→ Allocazione contigua: alla creazione di un file vengono allocati tot blocchi contigui; la taglia massima del file dipende dal numero di blocchi occupati; l’RS (record di sistema) mantiene informazioni sul blocco iniziale e sul numero dei blocchi; per combattere la frammentazione esterna è necessario ricorrere alla ricompattazione.
→ Allocazione a catena: in ogni blocco è indicato il blocco successivo, quindi l’RS mantiene informazioni solo sul primo blocco del file; l’occupazione reale di memoria è sempre pari al numero di blocchi utilizzati; il costo di accesso è potenzialmente grande in quanto si deve caricare tutto il file per ottenere l’n-esimo blocco.
→ Allocazione indicizzata: l’RS mantiene un elenco di indici che si riferiscono ai blocchi del file; la taglia dell’RS è variabile e da essa dipende anche la dimensione massima di un file; è il metodo di accesso più veloce, in quanto per accedere all’n-esimo blocco non bisogna prima accedere agli n-1-esimi blocchi.
→ Allocazione indicizzata a livelli multipli: uguale come meccanismo al caso precedente, l’unica differenza è che nell’RS possono trovarsi anche degli indici a dei blocchi di indici; questo fa sì che l’accesso a file di piccole dimensioni sia estremamente veloce, ma sia costoso nel caso di file di grandi dimensioni.

 D) Si descriva il metodo di accesso ai file sequenziali indicizzati. Si consideri inoltre un file system con metodo di accesso sequenziale indicizzato, ed un file sequenziale indicizzato F di 2048 record. Il relativo file indice ha 256 chiavi, uniformemente distribuite sui 2048 record del file F. Inoltre, il dispositivo ove il file e’ allocato ha blocchi di taglia pari ha 128 record. Supponendo che il file indice abbia tempo di accesso alla singola chiave pari a 1 msec, che il tempo di caricamento in memoria di un qualsiasi blocco di dispositivo sia 10 msec, e che il
tempo di accesso/manipolazione delle chiavi in memoria volatile sia nullo, si determini la latenza massima di caricamento in memoria di un qualsiasi record del file F.

Il metodo di accesso sequenziale indicizzato, tipico dei file indicizzati sequenziali, è dotato di un “file di indici sequenziali” che indica l’ordine dei record al file a cui è associato.
chiavi uniformemente distribuite => 2048/256 chiavi =8 record per ogni chiave.
taglia 128 record = 2 blocchi per le chiavi, 16 per i record.
nel caso peggiore, stiamo cercando l’ultima chiave, dunque ne scorriamo 256.
Latenza massima = n° blocchi chiavi*tempo di caricamento in memoria + tempo di accesso singolo blocco*n° chiavi + tempo caricamento file = 2*10+1*256+10 = 286

D) Si descriva il metodo di accesso ai file sequenziali indicizzati. Si consideri inoltre un file system con metodo di accesso sequenziale indicizzato, ed un file sequenziale indicizzato F di 4096 record. Il relativo file indice ha 128 chiavi, uniformemente distribuite sui 4096 record del file F. Inoltre, il dispositivo ove il file e’ allocato ha blocchi di taglia pari a 512 record. Supponendo che il file indice abbia tempo di accesso alla singola chiave pari a 1 msec, che il tempo di caricamento in memoria di un qualsiasi blocco di dispositivo sia 10 msec, e che il
tempo di accesso/manipolazione delle chiavi in memoria volatile sia nullo, si determini la latenza massima di caricamento in memoria di un qualsiasi record del file F.

chiavi uniformemente distribuite => 4096/128 = 32 record per chiave
taglia 512 record => 4096/512 = 8 blocchi per il file, 1 per le chiavi.
nel caso peggiore dobbiamo scorrere 128 chiavi.
Latenza max = tempo caricamento * n° blocchi chiavi + tempo accesso*n° chiavi + tempo caricamento file = 10+128+10 = 148 msec

D) Si descriva il metodo di accesso ai file sequenziali indicizzati. Si consideri inoltre un file system con metodo di accesso sequenziale indicizzato, ed un file sequenziale indicizzato F di 4096 record. Il relativo file indice ha 256 chiavi, uniformemente distribuite sui 4096 record del file F. Inoltre, il dispositivo ove il file è allocato ha blocchi di taglia pari a 512 record. Supponendo che il file indice abbia tempo di accesso alla singola chiave pari a 0,5 msec, che il tempo di accesso/manipolazione delle chiavi in memoria volatile sia nulla, si determini la
latenza massima di caricamento in memoria di un qualsiasi record del file F.

chiavi uniformemente distribuite => 4096/256 = 16 record per chiavi
1 blocco per allocare le chiavi
nel caso peggiore devo scorrere per 256 chiavi
Latenza massima  = tempo caricamento * n° blocchi + tempo accesso * n°chiavi + tempo caricamento file = 0 + 0.5*256 +  0 =128

D) Si descriva il metodo di accesso ai file diretto. Si consideri inoltre un file system con metodo di accesso diretto, ed un file F di 1024 record. Inoltre, il dispositivo ove il file F e’ allocato secondo lo schema a catena, ha blocchi di taglia pari ha 128 record, due dei quali vengono usati per il riferimento al successivo blocco nella catena. Supponendo che il tempo di caricamento in memoria di un qualsiasi blocco di dispositivo sia 10 msec, e che il tempo di accesso/manipolazione dei riferimenti in memoria volatile sia nullo, si determini la latenza massima di caricamento in memoria di un qualsiasi record del file F.

Attraverso il metodo di accesso diretto si può accedere all’i-esimo record di un file senza accedere forzatamente ai precedenti, quindi il riposizionamento dell’indice di lettura/scrittura può avvenire in qualsiasi punto del file. È utilizzato tipicamente nei file diretti e nei file di tipo hash.
n° blocchi necessari per il file: 1024/(128-2)=9 (di cui l’ultimo non completamente riempito)
Nel caso peggiore, sto tentando di accedere all’ultimo blocco, quindi devo caricare tutti i blocchi precedenti, in quanto nel metodo di allocazione di file a catena il RS mantiene indicazioni solo sul primo blocco, mentre ogni blocco mantiene informazioni al blocco successivo negli ultimi due record:
Latenza max = n°blocchi*tempo caricamento = 9*10 msec= 90 msec

D) Si descriva il metodo di accesso ai file sequenziale. Si consideri inoltre un file system con metodo di accesso sequenziale ed un file a mucchio F di 1024 record. I primi 512 record hanno taglia pari a 16 byte ciascuno mentre i secondi 512 hanno taglia pari a 32 byte ciascuno. Inoltre, il dispositivo ove il file e’ allocato ha blocchi di taglia pari ha 1024 byte. Supponendo che il tempo di caricamento in memoria di un qualsiasi blocco di dispositivo sia 5 msec, e che il tempo di accesso/manipolazione dei record del file in memoria volatile sia nullo, si determini la latenza massima di caricamento in memoria di un qualsiasi record del file F.

Secondo questa metodologia, l’accesso ai file avviene sequenzialmente, ovvero l’indice di scrittura/lettura parte dal primo record e può essere incrementato di una unità di volta in volta, ma va riposizionato sempre e solo al primo record del file.
totale dimensione file = 512*16+512*32 = 26576 byte
n° blocchi necessari = dim/blocchi = 26576/1024 = 24 blocchi
Nel caso peggiore stiamo accedendo all’ultimo blocco di memoria: scorriamo tutti e 24 i blocchi.
Tempo latenza max. = 24*5 = 120 msec

D) Si consideri un insieme di N processi (P1, … , Pn), ciascuno dei quali scrive periodicamente un nuovo messaggio su una memoria condivisa M di n slot. Ciascun processo Pi scrive esclusivamente nell’i-esimo slot della memoria condivisa. Dopo aver scritto il proprio messaggio, Pi attende che venga consegnata una risposta sempre sull’i-esimo slot della memoria condivisa M. L’attesa della risposta e’ bloccante. Un ulteriore processo REPLY legge i messaggi prodotti dai processi Pi e depositati negli slot della memoria condivisa M secondo la regola del buffer circolare. La lettura e’ anche in questo caso bloccante. Ogni 2 nuovi messaggi letti, REPLY scambia il contenuto dei relativi slot di M ed abilita la lettura delle risposte da parte dei rispettivi processi Pi. Gli accessi in lettura/scrittura da parte dei processi (P1, … , Pn) potranno avvenire in concorrenza, mentre gli accessi in lettura/scrittura sullo stesso slot di M dovranno essere esclusivi. Si schematizzi la soluzione del suddetto problema di sincronizzazione, usando solo semafori, fornendo lo pseudo-codice delle procedure SCRIVI e RISPONDI usate rispettivamente da Pi e REPLY.

DATA
Semaphore P[n];
Semaphore R[i];
INIT
for i = 1 to n
P[i]<-0;
R[i]<-0;
i++;

SCRIVI
do
wait(P[i]);
< write message on M[i]>;
signal(R[i]);
wait(R[i]);
<read reply>;
until false;

RISPONDI
int i = 1;
do
wait(R[i]);
<read message from M[i]>;
next = (i+1)%n;
wait(P[next]);
<change M[i] to M[next]>;
signal(R[i]);
signa(R[next]);
i = (i+2)%n;
until false;

D) Si consideri un insieme di N processi (P1, … , Pn), ciascuno dei quali scrive periodicamente un nuovo messaggio su una memoria condivisa M di n slot. Ciascun processo Pi scrive esclusivamente nell’i-esimo slot della memoria condivisa. Dopo aver scritto il proprio messaggio, Pi attende che venga consegnata una risposta tramite un buffer R, a slot singolo. L’attesa della risposta e’ bloccante. Un ulteriore processo REPLY legge i messaggi prodotti dai processi Pi e depositati negli slot della memoria condivisa M. La lettura e’ anche in questo caso bloccante. Quando REPLY ha letto i messaggi provenienti da tutti i processi Pi, consegna la risposta tramite il buffer R, la quale dovra’ essere letta da ciascun processo Pi. Gli accessi in lettura/scrittura da parte dei processi (P1, … , Pn) potranno avvenire in concorrenza. Si schematizzi la soluzione del suddetto problema di sincronizzazione, usando solo semafori, fornendo lo pseudo-codice delle procedure SCRIVI e RISPONDI usate rispettivamente da Pi e REPLY.

DATA
Semaphore P[n];
Semaphore RW;
INIT
for i = 1 to n
P[i] <- 0;
RW[i] <- 0;
SCRIVI
int i = 1;
do
<scrivi messaggio in M[i]>;
signal(P[i])
wait(RW[i]);
<leggi la risposta da R>;
until false;
RISPONDI
for i = 1 to n
wait(P[i]);
<leggi messaggio in M[i]>;
i+1;
<scrivi risposta in R>;
signal(RW[i]);

D) Si consideri un insieme di N processi (P1, … , Pn), ciascuno dei quali scrive periodicamente un nuovo messaggio su una memoria condivisa M di n slot. Ciascun processo Pi legge esclusivamente nell’i-esimo slot della memoria condivisa. Dopo aver scritto un messaggio in un buffer condiviso R a slot singolo, Pi attende che venga consegnata una risposta tramite il corrispondente slot di M. L’attesa della risposta e’ bloccante. Un ulteriore processo REPLY legge i messaggi prodotti dai processi Pi e depositati sul buffer R e consegna le risposte negli slot della memoria condivisa M. La lettura e’ anche in questo caso bloccante. L’accesso al buffer R da parte dei processi Pi dovra’ avvenire secondo la regola circolare (a partire da P1 verso Pn). Gli accessi in lettura da parte dei processi (P1, … , Pn) potranno avvenire in concorrenza. Si schematizzi la soluzione del suddetto problema di sincronizzazione, usando solo semafori, fornendo lo pseudo-codice delle procedure SCRIVI e RISPONDI usate rispettivamente da Pi e REPLY.

DATA
Semaphore P[n];
Semaphore RW;
INIT
for i = 1 to n
P[i]<- 0;
RW <-0;
SCRIVI
do
<write message on R>;
signal(P[i]);
wait(R);
<read reply on M[i]>;
until false;
RISPONDI
do
wait(P[i]);
<read message on R>;
signal RW;
<write repky on M[i]>;
until false;

D) Si consideri un insieme di N processi (P1, …, Pn), ciascuno dei quali scrive periodicamente un nuovo messaggio su un buffer condiviso M a slot singolo. Dopo aver scritto il proprio messaggio, Pi attende che venga consegnata una risposta tramite un buffer condiviso R, a slot singolo. L’attesa della risposta e’ bloccante. Un ulteriore processo REPLY legge i messaggi prodotti dai processi Pi e depositati nel buffer condiviso M, anche in questo caso in modalita’ blocante. Per ogni nuovo messaggio, REPLY consegna la relativa risposta destinata al processo mittente del messaggio. Ogni processo Pi e’ abilitato a scrivere un nuovo messaggio su M solo dopo che tutti i processi Pi abbiano depositato il loro messaggio ed abbiano ricevuto la relativa risposta. Si schematizzi la soluzione del suddetto problema di sincronizzazione, usando solo semafori, fornendo lo pseudo-codice delle procedure SCRIVI e RISPONDI usate rispettivamente da Pi e REPLY.

DATA:
Semaphore P[n];
Semaphore RW;
INIT
for i = 1 to n
P[i] <- 0;
RW <- 0;
SCRIVI
int i;
for i = 1 to n
wait(P[i]);
<write message on M>;
signal(RW);
<read reply from R>;
next=  i+1;
if next=n => next=1; i =1;
RISPONDI
int i;
for i = 1 to n;
wait(P[i]);
<read message on M>;
<write reply into R>;
signal(RW);

D) Si scriva una funzione in tecnologia C-UNIX o C-Windows a scelta dello studente, che ricevendo in input un descrittore/handle ad un listening-socket accetti connessioni su tale socket, e ritorni il descrittore/handle del socket di comunicazione generato per effetto della connessione solo nel caso in cui il socket sorgente della connessione abbia port-number compreso nell’intervallo 1024-2048. La funzione dovra’ poter filtrare errori di connessione dovuti ad eventuali eventi asincroni.

int getConnection(int ds_sock){
struct socketaddr in.client;
int size = sizeof(client);
int descr;
descr = accept(ds_sock, &client, &size);
signal(SIGTERM, SIGIGN);
if ( (client.sin.port >= 1024) && (client.sin.port <=2048))
close(ds_sock);
return descr;
close(descr);
bzero((char*)&client, sizeof(client));
}

D) Si scriva una funzione in tecnologia C-UNIX o C-Windows a scelta dello studente, che ricevendo come parametri di input (i) un unsigned che indichi un valore di timeout, (ii) un IP-number espresso in notazione stringa e (iii) un portnumber espresso come un codice numerico, esegua le seguenti attivita’: invii un pacchetto UDP di 1024 byte a contenuto nullo verso la coppia <IP,port> sopra indicata, ed attenda un pacchetto UDP in risposta per al piu’ timeout secondi. In caso di mancata ricezione entro il timeout, la funzione deve ritornare valore -1. Altrimenti, la funzione deve ritornare il numero di byte che nel pacchetto di ritorno (tagliato a 1024 byte) sono diversi rispetto ai corrispettivi byte inviati. 

int getConnection(uint timeout, char* IP, short port){
char* buff[1024];
char* buff2[1024];
int socket = socket(AF_INET, SOCK_DGRAM, IPPROTO_UDP);
struct sockaddr_in dest;
struct sockaddr_in socket_in;
dest.sin_family = AF_INET;
dest.sin_addr = inet(aton(IP));
sendto(socket, &buff, 1024, 0, &dest, sizeof(dest));
alarm(timeout);
signal(SIGALARM, gestione_timeout);
int size=0; int i=0; int count = 0;
recvfrom(socket, &buff2, 1024, 0, &dest, &size);
signal(SIGALAMR, SIGIGN);
if(check==1) return -1;
for(i; i<1024; i++){
if(buff[i]-buff2[i]!=0) count++;
}
return count;
}
int gestione_timeout(){
check ==1;
}