Prova Teorica 2008.09.17

CONCORRENZA

Esercizio 1

Monitor eu
{
	const int Urgent = 1;
	int Code;
	condition doctor, patient[2];
	queue doctorName, patientName[2];
	
	Name getdoctor(Name name, int code)
	{
		patientName[code].enqueue(name);

		if ((code == Urgent && doctorName.Count == 0) || (code != Urgent && doctorName.Count < 4))
			patient[code].wait();
		else
		{
			Code = code;
			doctor.signal();
		}
		return doctorName.dequeue();
	}
	
	Name getpatient(Name name)
	{
		doctorName.enqueue(name);
		
		if (patientName[Urgent].Count == 0 && (patientName[1 - Urgent].Count == 0 || doctorName.Count < 4))
			doctor.wait();
		else
		{
			Code = (patientName[Urgent].Count > 0)? Urgent : 1 - Urgent;
			patient[Code].signal();
		}
		return patientName[Code].dequeue();
	}
}

Esercizio 3

/* If (1) e (2) share the same expressive power than 
   I may implement (1) by means of (2) and vice versa. */

// (1) by means of (2)
void send2(Message m1, Message m2, Pid d1, Pid d2)
{
	asend(<SND, getpid(), d1, d2>, server);
	asend(m1, arecv(server));
	asend(m2, arecv(server));
}

Message receive2()
{
	asend(<RCV, getpid(), NULL, NULL>, server);
	return arecv(*);
}

Process server()
{
	DataBase dbSnd, dbRcv;
	while (true)
	{
		<flag, src, d1, d2> = arecv(*);
		if (flag == RCV)
		{
			<sender, d1, d2> = dbSnd.remove(<?, src, ?> || <?, ?, src>);
			if (sender)
			{
				asend(src, sender);
				if (d1 == src)
					d1 == NULL;
				else
					d2 == NULL;
				if (d1 || d2)
					dbSnd.insert(<sender, d1, d2>);
			}
			else
				dbRcv.insert(src);
		}
		else
		{
			if (dbRcv.remove(d1))
			{
				asend(d1, src);
				d1 = NULL;
			}
			if (dbRcv.remove(d2))
			{
				asend(d2, src);
				d2 = NULL;
			}
			if (d1 || d2)
				dbSnd.insert(<src, d1, d2>);
		}
	}
}

// (2) by means of (1)
void asend(Message msg, Pid dst)
{
	send2(<SND, getpid(), dst, msg>, NULL, server, NULL);
}

Message arecv(Pid sender)
{
	send2(<RCV, getpid(), sender, NULL>, NULL, server, NULL);
	return arecv(server);
}

Process server()
{
	DataBase dbRcv, dbSnd;
	while (true)
	{
		<flag, p1, p2, msg> = receive2();
		if (flag == RCV)
		{
			<, , msg> = dbSnd.remove(<p2, p1, ?>)
			if (msg)
				send2(msg, NULL, p1, NULL);
			else
				dbRcv.insert(<p1, p2>);
		}
		else
		{
			if (dbRcv.delete(<p2, p1>))
				send2(msg, NULL, p2, NULL);
			else
				dbSnd.insert(<p1, p2, msg>);
		}
	}
}

GENERALE

Esercizio 2

a) Stato SAFE, solo con la permutazione [1, 2, 3]:
i	Valuta A		IC = 4	COH = 3	Valuta B		IC = 4	COH = 3
	c[i]	p[i]	n[i]	avail[i]	c[i]	p[i]	n[i]	avail[i]
1	4	1	3	3	3	0	3	3
2	4	0	4	4	3	1	2	3
3	2	0	2	4	4	0	4	4
Verifica:
2	4	0	4	3	3	1	2	3
1 3
3 1
3	2	0	2	3	4	0	4	3
1 2
2 1
1	4	1	3	3	3	0	3	3
3	2	0	2	4	4	0	4	3
2
b)
	Allocated		Max		Need		Available
	A	B	A	B	A	B	A	B
P1	1	0	4	3	3	3	3	3
P2	0	1	4	3	4	2
P3	0	0	2	4	2	4
→ P1:A(1,1)
P1	2	1			2	2	2	2
→ P2:A(2,1)
P2	2	2			2	1	0	1
→ P1:A(2,2)
DEADLOCK: not enough resources available.