Prova Teorica 2008.01.16

http://www.cs.unibo.it/~renzo/so/compiti/2008-01-16.tot.pdf

Esercizio 1

monitor guardaroba_russo
{
	Ritira = 0; Consegna = 1; Prendi = 2;
	queue waiting[2] = {0, 0};
	queue all;
	condition ok[3];
	count = 0;
	waitingAny = False; waitingMax = False;
	output;
	
	// Cancella la prima occorrenza di <Ritira> nella coda <all>
	deleteRitira();
	
	item prendi()
	{
		if (count == MAX)
		{
			if (waiting[Ritira].Count == 0)
			{
				waitingMax = True;
				ok[Prendi].wait();
			}
			return waiting[Ritira].dequeue();
		}
		else
		{
			if (all.Count == 0)
			{
				waitingAny = True;
				ok[Prendi].wait();
                                waitingAny = False;
			}
			return waiting[all.read()].dequeue();
		}
	}
	
	dai(item x)
	{
		if (waitingMax)
		{
			waitingMax = False;
			deleteRitira();
			output = x;
			// Se il dipendente e' stato riattivato tramite signal, la seguente va a vuoto
			ok[Ritira].signal();
		}
		else
		{
			output = x;
			// Se il dipendente e' stato riattivato tramite signal, la seguente va a vuoto
			ok[all.dequeue()].signal();		
		}
	}
	
	contrassegno consegna(giacca g)
	{
		all.enqueue(Consegna);
		waiting[Consegna].enqueue(g);
		if (waitingAny)
			ok[Prendi].signal();
		else
			ok[Consegna].wait();
		count++;
		return output;
	}
	
	giacca ritira(contrassegno c)
	{
		all.enqueue(Ritira);
		waiting[Ritira].enqueue(c);
		if (waitingAny || waitingMax)
			ok[Prendi].signal();
		else
			ok[Ritira].wait();
		count--;
		return output;
	}
}

• Si avrebbe deadlock, in quanto si potrebbe generare la situazione di avere il guardaroba pieno e il primo della coda che intende consegnare una giacca.
  • Salva l'adozione di una politica (iniqua) nel caso del guardaroba pieno. Segnatamente quella di rimandare alla fine della coda tutti i processi che consegnano la giacca.

Esercizio 3

• Ad input immutato, F(x, y) non puo' sostituire la Test&Set:

x	y	Test&Set: x y	F(x,y): x1 x y
0	0	1 0	0 0 undefined
0	1	1 0	0 1 undefined
1	0	1 1	1 0 0
1	1	1 1	1 1 0

• Mediante le seguenti modifiche diventa possibile:

x = x + 1	y = 1	F(x,y): x1 x y
1	1	1 1 0
1	1	1 1 0
2	1	2 1 1
2	1	2 1 1

• In termini di pseudocodice:

shared lock = 0;

process P
{
   int vp;
   while (True)
   {
      do
      {
         vp = 1;
         lock += 1;
         F(lock, vp);
      } while(vp);
      // <critical section>
      lock = 0;
      // </critical section>
   }
}