Difference between revisions of "ProvaTeorica 2014.02.22"
(→Esercizio c.2: Aggiunta soluzione) |
(→Soluzione di FedericoB: Corretto nome di variabile nella spiegazione di una soluzione.) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 130: | Line 130: | ||
alpha assegna valori costanti quindi non è possibile utilizzarla per la test and set in quanto il suo risultato non può essere influenzato da parametri esterni. | alpha assegna valori costanti quindi non è possibile utilizzarla per la test and set in quanto il suo risultato non può essere influenzato da parametri esterni. | ||
| − | bravo(lock,vp) assegna a lock 4 e a | + | bravo(lock,vp) assegna a lock 4 e a vp la radice del vecchio lock |
Un possibile codice che utilizza bravo è il seguente: | Un possibile codice che utilizza bravo è il seguente: | ||
<pre> | <pre> | ||
| Line 141: | Line 141: | ||
} while (vp==2) | } while (vp==2) | ||
//sezione critica | //sezione critica | ||
| − | lock | + | vp=0 |
| + | bravo(vp,lock) //assegno a lock 0 | ||
} | } | ||
</pre> | </pre> | ||
| Line 154: | Line 155: | ||
} while (vp!=1) | } while (vp!=1) | ||
//sezione critica | //sezione critica | ||
| − | lock | + | vp=1 |
| + | charlie(vp,lock) //assegno a lock 1 | ||
} | } | ||
</pre> | </pre> | ||
Latest revision as of 13:49, 10 September 2017
Testo: [1]
Esercizio c.1
Soluzione di Coci
monitor bbwl {
condition oktowrite;
condition oktolog;
condition oktoread;
int logging = 0;
queue q;
procedure entry write (eltype elem) {
if (q.length() == MAXELEM || logging)
oktowrite.wait();
q.enqueue (elem);
logging = 1;
oktolog.signal();
}
procedure entry eltype log() {
if (q.length == 0)
oktolog.wait();
eltype tmp = q.top();
logging = 0;
oktoread.signal();
return tmp;
}
procedure entry eltype read() {
if (q.length == 0 || logging)
oktoread.wait();
eltype tmp = q.dequeue();
oktowrite.signal();
return tmp;
}
}
Soluzione di Save
condition oktowrite, oktoread, oktolog ;
queue buffer = MAXELEM ;
queue Llogger ;
monitor bbwl
{
procedure entry write (altype elem)
{
if (buffer.length >= MAXELEM)
oktorite.wait() ;
buffer.enqueue(elem);
oktolog.signal () ;
}
procedur entry logger() # logger deve tenere traccia di tutti i pacchetti transitati mettendoli in una sua memoria.
{
if (buffer.length == 0)
oktolog.wait();
Llogger.enqueue(buffer.front()) # restituisci il valore in testa di buffer e inseriscilo in coda a Llogger
ok toread.signal() ;
}
procedure entry read()
{
if (buffer.length == 0)
oktoread.wait();
buffer.dequeue() # restituisci il valore in testa di buffer e rimuovilo.
oktowrite.signal() ;
}
}
save
Esercizio c.2
Soluzione di Coci
alpha(x,y): <x=4, y=sqrt(x)>
il valore che viene salvato in y è sempre 2, quindi non va bene.
bravo(x,y): <y=sqrt(x), x=4>
xi yi xf yf 0 0 4 0 0 1 4 1 1 0 4 1 1 1 4 1
il valore iniziale di x viene salvato in y, quindi va bene.
charlie(x,y): <y=sqrt(x), x=4*y>
Anche questo va bene, per le stesse ragioni di bravo.
delta(z,t): <z=z xor t, t=z xor t>
zi ti zf tf 0 0 0 0 0 1 1 0 1 0 1 1 1 1 0 1
Il valore iniziale di z viene salvato in t, quindi va bene.
Soluzione di Diego.tului
alpha: non funziona perché y non andrà mai a 0, quindi non entrerà mai in CS.
bravo: funziona perché quando y va a 0 x rimane 4, e perciò finché x non ritorna 0 la CS è occupata.
charlie: dipende dal valore iniziale di x, perché se all'inizio x = 0 (y = 0, x = 4 * 0 = 0) quindi non ci sarà mutua esclusione.
delta: dipende dal valore iniziale di t, perché se all'inizio è 0, 0 xor 0 resta sempre 0, ergo come sopra.
Diego
Soluzione di FedericoB
alpha assegna valori costanti quindi non è possibile utilizzarla per la test and set in quanto il suo risultato non può essere influenzato da parametri esterni.
bravo(lock,vp) assegna a lock 4 e a vp la radice del vecchio lock Un possibile codice che utilizza bravo è il seguente:
int lock=0
process p
int vp;
while(1) {
do {
bravo(lock,vp)
} while (vp==2)
//sezione critica
vp=0
bravo(vp,lock) //assegno a lock 0
}
charlie(lock,vp) assegna a lock 4 moltiplicato per la radice del vecchio lock e a vp la radice del vecchio lock
int lock=1
process p
int vp;
while(1) {
do {
charlie(lock,vp)
} while (vp!=1)
//sezione critica
vp=1
charlie(vp,lock) //assegno a lock 1
}
Ho cambiato il valore iniziale del lock per evitare l'effetto assorbente dello zero. Inoltre ora quando il lock è impostato i processi in attesa avranno un vp completamente differente tra loro quindi ho dovuto utilizzare una diseguaglianza.
delta(z,t)
zi ti zf tf comb1 0 0 0 0 comb2 0 1 1 0 comb3 1 0 1 1 comb4 1 1 0 1
Impossibile perchè nessuna delle combinazioni di input e utilizzabile. La combinazioni 1 e 3 non cambiano il lock e quindi non ci sarebbe mutua esclusione. Utilizzando le combinazioni 2 e 3 (quindi con vp inizializzato a 1) non ci sarebbe comunque mutua esclusione perchè se inizializziamo lock a 0 viene messo dalla combinazione 2 a 1 e vp=0, il primo processo ottiene la sezione critica. Un altro processo si troverebbe il lock impostato a 1 e vp=1 per inizializzazione locale. Verrebbe quindi utilizzata la combinazione 4 che però riporterebbe il lock a 0 e quindi un terzo processo potrebbe entrare in sezione critica.
Esercizio g.1
Soluzione di Coci
Sia n=3 il numero di pagine mantenute in memoria
a) 123456789123456789...
MIN = MINNUM
11144777 2225588 333669
b) 145231231231231...
MINNUM
111232123
44444444
5555555
MIN
111111111
44222222
5333333
Alessandro
Soluzione di Diego.tului
Sia n=3 il numero di pagine mantenute in memoria
la soluzione di Alessandro secondo noi presenta dei problemi, la integriamo:
a) 1234431432431432431
111444444444444444
222221112221112221
3333333333333333