ProvaTeorica 2014.02.22

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