Difference between revisions of "ProvaTeorica 2014.02.22"

From Sistemi Operativi
Jump to navigation Jump to search
(Created page with "Testo: [http://www.cs.unibo.it/~renzo/so/compiti/2014.02.21.tot.pdf] Esercizio c.1 <syntaxhighlight lang="C"> monitor bbwl { condition oktowrite; condition oktolog; condi...")
 
(→‎Soluzione di FedericoB: Corretto nome di variabile nella spiegazione di una soluzione.)
 
(15 intermediate revisions by 4 users not shown)
Line 1: Line 1:
 
Testo: [http://www.cs.unibo.it/~renzo/so/compiti/2014.02.21.tot.pdf]
 
Testo: [http://www.cs.unibo.it/~renzo/so/compiti/2014.02.21.tot.pdf]
  
−
Esercizio c.1
+
==Esercizio c.1==
 +
 
 +
===Soluzione di Coci===
  
 
<syntaxhighlight lang="C">
 
<syntaxhighlight lang="C">
Line 38: Line 40:
  
 
</syntaxhighlight>
 
</syntaxhighlight>
 +
 +
===Soluzione di Save===
 +
 +
<syntaxhighlight lang="C">
 +
 +
 +
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() ;
 +
}
 +
}
 +
</syntaxhighlight>
 +
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>
 +
 +
<pre>
 +
xi yi xf yf
 +
0  0  4  0
 +
0  1  4  1
 +
1  0  4  1
 +
1  1  4  1
 +
</pre>
 +
 +
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>
 +
<pre>
 +
zi ti zf tf
 +
0  0  0  0
 +
0  1  1  0
 +
1  0  1  1
 +
1  1  0  1
 +
</pre>
 +
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:
 +
<pre>
 +
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
 +
}
 +
</pre>
 +
charlie(lock,vp) assegna a lock 4 moltiplicato per la radice del vecchio lock e a vp la radice del vecchio lock
 +
<pre>
 +
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
 +
}
 +
</pre>
 +
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)
 +
<pre>
 +
    zi ti zf tf
 +
comb1 0  0  0  0
 +
comb2 0  1  1  0
 +
comb3 1  0  1  1
 +
comb4 1  1  0  1
 +
</pre>
 +
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

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
Retrieved from "https://so.v2.cs.unibo.it/wiki/index.php?title=ProvaTeorica_2014.02.22&oldid=1961"