Prova teorica 2016.05.30
Esercizio g.1
a) Sia data una memoria di 3 frame. Trovate una stringa di riferimenti di lunghezza infinita tale che se confrontiamo FIFO e MIN, da un certo istante in poi il numero di page fault per FIFO sia almeno doppio di quello di MIN. Dimostrate che la proprieta’ sia verificata. b) Trovate una stringa di riferimenti di lunghezza infinita tale che se confrontiamo FIFO e MIN, da un certo istante in poi il numero di page fault per FIFO sia almeno triplo di quello di MIN. Dimostrate che la proprietà sia verificata. c) (extra/hint) E’ possibile soddisfare b con una memoria di 3 frame? Perché?
Soluzione di FedericoB
a) la stringa di riferimento 12341234123412341234...
FIFO 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 1 1 4 4 4 3 3 3 2 2 2 1 1 1 4 2 2 2 1 1 1 4 4 4 3 3 3 2 2 2 3 3 3 2 2 2 1 1 1 4 4 4 3 3 # # # # # # # # # # # # # MIN 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 4 3 4 4 4 4 4 4 4 4 4 1 1 1 1 # # # # #
b) la stringa di riferimento per il punto (a) genera il triplo dei page fault su FIFO rispetto a MIN.
c) Sì è possibile ma non è possibile farne il quadruplo.Questo perchè MIN è l'algoritmo teorico ottimale che genera meno page fault possibili. MIN sostituisce la pagina che più tardi nel futuro verrà richiesta. Data una stringa di riferimento che genera page fault ad ogni richiesta con FIFO, quindi in cui non ci sono mai richieste uguali consecutive, con MIN se dobbiamo ottenere un terzo dei page fault vuol dire avere un page fault minimo ogni 3 richieste. Con una memoria di 3 frame se una frame viene occupato dalla nuova pagina vuol dire che rimangono 2 frame in cui rimarranno pagine che verrano utilizzate nell'immediato futuro, quindi potremo avere 2 richieste che non genereranno page fault, ma sicuramente alla terza richiesta verrà generato. Se avessimo una memoria con 4 frame potremmo avere un quarto dei page fault rispetto a FIFO.
Esercizio g.2
Soluzione di FedericoB
1. A cosa serve il processo IDLE (che mette il processore in wait state se possibile o esegue un loop infinito)? Quando viene messo in esecuzione? Come si gestisce l’attivazione di IDLE negli scheduler a priorità e nel round-robin?
Il processore normalmente ad ogni istruzione incrementa il program counter di una posizione oppure esegue un salto. Quindi non è tecnicamente possibile non fargli eseguire nulla. Il processo IDLE serve proprio nelle situazioni in cui non sono presenti processi da eseguire. Lo stato di wait riduce il consumo energetico del processore, ne abbassa la frequenza. Negli scheduler a priorità il processo IDLE può essere un processo con priorità minima. Nel round robin invece conviene inserire il processo IDLE solo se si rileva che la coda ready è vuota. Altrimenti se fosse sempre presente nella coda ready saremmo costretti ad eseguire il processo IDLE ad ogni turn-around della coda circolare e questo decrementerebbe le prestazioni.
2. Lo stato unsafe è condizione necessaria ma non sufficiente perché possa verificarsi deadlock. Quali sono I passi logici necessari per dimostrare questa affermazione?
Bisogna dimostrare che se si verifica deadlock allora si è sicuramente verificato anche uno stato unsafe. Se si verifica deadlock vuol dire che ci sono processi in attesa di risorse. Uno stato unsafe è uno stato in cui il sistema non ha potuto soddisfare nessuna delle richieste perchè non ha risorse da assegnare, quindi i processi devono rimanere in attesa. Se non si fosse in uno stato di unsafe allora il sistema potrebbe garantire una risorsa a uno dei processi in deadlock e questo sbloccherebbe anche tutti gli altri.
3. Quali metodi di allocazione per file system ammettono la creazione di file di grandezza arbitrario?
4. Perché per utilizzare le capability come strumento di autorizzazione è sufficiente usare un metodo crittografico a singola chiave?