Renzo: Created page with "

 - Come mostrare che un algoritmo soffre dell'anomalia di Belady Creando una stringa di riferimenti tale che l'algoritmo generi piu' page fault aumentando il numero di fr..."

2016-06-14T10:00:28Z

Created page with "<pre> - Come mostrare che un algoritmo soffre dell'anomalia di Belady Creando una stringa di riferimenti tale che l'algoritmo generi piu' page fault aumentando il numero di fr..."

New page

<pre>
- Come mostrare che un algoritmo soffre dell'anomalia di Belady
Creando una stringa di riferimenti tale che l'algoritmo generi piu' page
fault aumentando il numero di frame.

- Come capire, in generale, se un algoritmo sia o no a stack; =
risoluzione dell'esercizio "Dato t=3Dtimetick() il numero di tick dalla =
accensione della macchina sia detto f=3Dt%NF (NF numero di frame =
disponibili). Qualora sia necessario liberare un frame, si decide di =
eliminare la pagina nel frame f. =C8 un algoritmo a stack?"
---------
Questo algoritmo non e' a stack.
t: 01234
stringa: 12334
Con 2 frame:
frame 0: 11334
frame 1: 2222
Con 3 frame:
frame 0: 11111
frame 1: 2224
frame 2: 333
come vede la pagina 2 e' presente nella memoria a 2 frame e non a 3.
Per mostrare che un algoritmo *non* e' a stack occorre trovare un esempio
che faccia divergere il comportamento aumentando il numero di frame.

- Esiste un qualche metodo per risolvere esercizi del tipo "Mostrare un =
semplice caso nel quale gli algoritmi LRU e MIN abbiano lo stesso numero =
di page fault" o ancora "Mostrare un esempio nel quale MRU compia meno =
page fault di LRU", o devo andare a tentativi?
--------
No. Non sono tentativi. Occorre analizzare come funzionano gli algoritmi
in questione e trovare il modo di "pilotarli" alla soluzione voluta.
Esempi, non tentativi, possono aiutare a capire il funzionamento.

- Nello scheduling per CPU a time slice a priorit=E0, nel caso la =
priorit=E0 sia la stessa, il processo lo scelgo random o scelgo quello =
"a indice minore" (ex.fra P1 e P2 scegliere P1)
--------
Comunque il comportamento di uno scheduler (o di un qualsiasi altro
algritmo) non sia determinato, occorre fare scelte plausibili, coerenti
per tutto lo svolgimento dell'esercizio. Possibilmente occorre esplicitare
la scelta fatta, per rendere piu' semplice la correzione.

-Non ho chiaro cosa sia il "consetto di localit=E0"
--------
Assomiglia in Informatica del concetto Fisico dell'inerzia.
Un algoritmo molto probailmente nel prox futuro si comportera' come nel
prossimo passato. Quindi tendera' (molto probabilemnte) ad accedere a
locazioni di memoria prossime a quelle usate in precedenza.
Non e' un dogma, ma nell'uso generale e' una proprieta' che statisticamente
e' spesso verificata.
Quindi operare per rendere efficiente il caso piu' frequente crea sistemi
piu' performanti.
Il principio di localita' rende possibile l'uso di cache o di memoria
virtuale.

- Avrei bisogno dello svolgimento dell'esercizio "Sia dato uno scheduler =
preemptive di tipo Shortest Remaining Time First con valore alfa=3D1/2 e =
valore iniziale T0=3D0 per ogni processo. Sia data la storia esecutiva =
dei processi: [ P1: 2ms CPU, 5ms IO un 2, 2ms CPU, 5ms IO un 1, 3ms CPU =
] [ P2: 4ms CPU, 5ms IO un 1, 4ms CPU, 5ms IO un 2, 3ms CPU ] [ P3: 5ms =
CPU, 5ms IO un 1, 6ms CPU, 5ms IO un 2, 3ms CPU ] [ P4: 3ms CPU, 5ms IO =
un 2, 3ms CPU, 5ms IO un 1, 4ms CPU ]; Mostrare diagramma di Gannt e =
calcolare il tempo totale di esecuzione ".
----------
Lo scheduler deve ad ogni esecuzione stimare tramite la media
esponenziale la lunghezza del prossimo CPU burst.
Questo consentira' di determinare lo "shortest time".
In piu' questo esercizio chiede di applicare l'algoritmo in modo
pre-emptive: cioe' se il processo corrente viene interrotto da
un interrupt che rende ready un nuovo processo occorre confrontare il
tempo rimasto (lunghezza del burst calcolata - tempo usato dal processo
interrotto prima dell'interrupt) e la lunghezza del CPU burst del processo
diventato ready. CHi ha il burst piu' breve, vince.

- Avrei bisogno dello svolgimento dell'esercizio "Sia dato l'algoritmo =
di rimpiazzamento MINNUM. Come pagina da rimpiazzare MINNUM sceglie =
sempre quella con=20
l'indirizzo logico piu' basso (numero di pagina minore).
a. mostrare una stringa di riferimenti di lunghezza infinita e che =
generi infiniti page fault tale che MIN e MINNUM si comportino=20
esattamente nello stesso modo
b. mostrare una stringa di riferimenti di lunghezza infinita tale che =
MINNUM generi un page fault ad ogni accesso in memoria mentre=20
MIN generi un numero finito di page fault
(in entrambi i punti l'insieme delle pagine utilizzate nelle stringhe di =
riferimenti deve essere finito"
-----------
Vale quanto detto sopra per gli algoritmi di rimpiazzamento.
Per il punto a. occorre trovare il modo per farli convergere, per fare in
modo che si comportino nello stesso modo. QUindi quando avviene il
page-fault MIN e MINNUM devono individuare la stessa pagina.
mi pare per esempio che la stringa 341342341341 (per sempre) con 3 frame,
generi il caso voluto (1 e 2 si scambiano nell'uso del terzo frame
perche' sono minori di 3 e 4 (MINNUM) e perche' vengono sempre acceduti
prima di 1 o 2 (MIN).
Per il secondo caso: 34(12), cioe' 34121212121212 per sempre, con 3 frame
fa infiniti page fault con MINNUM e soli 3 page fault con MIN.

- Avrei bisogno dello svolgimento dell'esercizio " Si consideri un =
i-node che contenga 7 indici diretti, 1 indice indiretto, uno a =
indirezione doppia e uno a=20
indirezione tripla.=20
Se la dimensione dei blocchi =E8 1KB e gli indirizzi di blocco sono a 32 =
bit,=20
a) qual =E8 la dimensione massima di un file?=20
b) Oltre all'inode, quanti blocchi devono essere acceduti per leggere un =
byte nel blocco 100000?=20
In entrambi i casi, la risposta non deve essere limitata al valore =
numerico, ma deve illustrare il ragionamento "
------
Questo ricordo bene di averlo svolto a lezione.
Occorre calcolare quanti indici stanno in un blocco. Se l'indice e' 32 bit
i.e. 4 byte, ci stanno 256 indici per blocco.
Al massimo un file sara' foramto da 7 blocchi dati acceduti direttamente +
256 acceduti con il blocco indiretto, 256* 256 con quello doppiamente
indiretto etc).
Dato il numero di blocchi, la lunghezza in byte si ottiene moltiplicando
per la lunghezza del blocco.
per b occorre far vedere di aver compreso l'allocazione indiretta.
(100000 / 1024 e' un numero > 7 ma non di 256. 256 * 1024 e' piu' di
256000. Basta un solo blocco indiretto? a voi l'ardua sentenza).

- Avrei bisogno dello svolgimento dell'esercizio " Si considerino le =
seguenti funzioni atomiche foo e bar e si verifichi se e' possibile =
usarle (o meno) al
posto della test&set per il supporto di sezioni critiche (i parametri =
sono passati per indirizzo):
2a) foo(x,y) =3D <x1=3Dx*2, y1=3Dy/2, x=3Dy1, y=3Dx1> (con x, y interi)
2b) bar(x,y) =3D <x =3D y
x
, y=3Dabs(floatrand())+1> (con x,y reali, floatrand genera un numero =
random in tutto il dominio
dei reali, abs e' la funzione valore assoluto"
-------------
Qui la tecnica e' vedere di creare un protocollo di entrata che consenta:
* di accedere a variabili condivise *solo* tramite la funzione atomica
fornita.
* di modificare le variabili condivise in modo che assumanoo valori che
indichino la critical section "occupata"
* esaminando solo variabili locali si possa stabilire se la CS fosse
libera o occupata prima della chiamata della funzione atomica.

la foo, dati i valori di x e y prima della chiamata di foo, assegna a
y il doppio del vecchio valore di x e a y la meta' del vecchio valore di x.
Questo ha l'aria di rendere possibile la creazione di critical section.

Se assegniamo alla variabile locale L il valore 1 e chiamiamo
foo(G,L) G varra' 0.5 (o 0 se i numeri sono interi), mentre ad L sara'
assegnato il doppio del valore di G (prima della foo).

QUindi se G valeva 0.5 o 0 sara' sempre un valore < 2.

Allora poniamo G=1 per indicare la CS "libera".
Il primo che chiama la foo riceve L == 2, tutti gli altri < 2

quindi il protocollo e':

CSIN:
do {
L=1;
foo(G,L)
while (L<2);

CSOUT:
G=1

Per il secondo 2b:
abs(floatrand()) genera un numero NON NEGATIVO.
basta scegliere un valore negativo per indicare la CS libera, solo il primo
che chiama la bar otterra' un valore negativo.
</pre>

Risposte a studenti giugno 2016 - Revision history

Renzo: Created page with "
- Come mostrare che un algoritmo soffre dell'anomalia di Belady Creando una stringa di riferimenti tale che l'algoritmo generi piu' page fault aumentando il numero di fr..."