Prove scritte 2022

Prova 2022/06/01

Esercizio c2

Consegna

Esercizio c.2: Un servizio di message passing asincrono non fifo (nfasend/nfarecv) consegna in tempo finito tutti i messaggi spediti ma non è garantito che i messaggi vengano ricevuti nell'ordine nel quale sono stati spediti.

 void nfasend(msg_t msg, pid_t dest)
 msg_t nfarecv(pid_t sender)

Dato un servizio di message passing asincrono non fifo scrivere una libreria che implementi il servizio di message passing asincrono fifo:

 void asend(msg_t msg, pid_t dest)
 msg_t arecv(pid_t sender)

Nota: sia il servizio dato (non fifo) sia quello da implementare (fifo) consentono la ricezione solo da mittente specificato (non supportano ANY/*).

Soluzione proposta 1

void nfasend(msg_t msg, pid_t dest);
msg_t nfarecv(pid_t sender);


// array di grandezza di massimi numero di processi, inizializzato a 0
// utilizzato per contare il numero di messaggi inviati a un certo processo.
int num_sender[MAX_PROC];

//RICORDA che ogni sender ha il suo num_sender[...]

void asend(msg_t msg, pid_t dest) {
	src = getpid();
	nfasend(<msg, num_send[dest]>, dest);
	num_sender[dest]++;
}

// molto simile a num_sender, ma è utilizzato per contare il numero di messaggi ricevuti, in ordine.
int num_receiver[MAX_PROC];
// array heap ordinato sul int (per ogni heap in cima c'è il messaggio col minimo int).
min_heap<msg, int> messages[MAX_PROC];

//RICORDA che ogni receiver ha il suo proprio num_receiver[...] e messages[...]

msg_t arecv(pid_t sender) {
	p = getpid();
	
	if (messages[sender].size() > 0 && messages[sender].top() == num_receiver[sender]) {
		(msg, num_mess) = messages[sender].removeTop();
		num_receiver[sender]++;
		return msg;
	}

	(msg, num_mess) = nfarecv(sender);

	while (num_mess != num_receiver[sender]) {
		messages[sender].insert(msg, num_mess);
		(msg, num_mess) = nfarecv(sender);
	}

	num_receiver[sender]++;
	return msg;	
}