Prove scritte 2022

Prova 2022/06/01

Esercizio c1

Consegna

Esercizio c.1: Scrivere il monitor delay che fornisce due procedure entry:

 int wait_tick(int nticks)
 void tick(void)

La procedure entry tick è pensata per essere richiamata periodicamente (es. ogni secondo o ora o giorno) da un processo. Quando un processo chiama la wait_tick deve attendere un numero di chiamate della tick pari al parametro nticks. Per esempio se un processo chiama wait_tick(2) deve fermarsi e verrà riattivato alla seconda successiva chiamata di tick. La funzione wait_tick ha come valore di ritorno il numero di processi che erano bloccati al momento della tick che ha sbloccato il chiamante. Esempio: P chiama wait_tick(2) e si blocca. Q chiama wait_tick(3) e si blocca. T chiama tick() non succede nulla. R chiama wait_tick(2) e si blocca. T chiama tick(), viene sbloccata la wait_tick di P e il valore ritornato è 3. T chiama tick(), vengono sbloccate le wait_tick di Q e R e il valore ritornato per entrambi i processi è 2

Soluzione proprosta 1 (da controllare)

Soluzione proposta da Flecart

class MonitorDelay {
    int curr_time;
    int waiting_num;

    // min heap con il tempo di sblocco dei processi e la condizione su cui è fermato
    // il tempo di sblocco minore è messo in cima alla heap
    // la sintassi con pair è ispirata alla std::pair di c++
    heap<pair<int, condition>> waiting; 

    void init() {
        curr_time = 0;
        waiting = heap<pair<int, condition>>();
    }

    int entry wait_tick(int nticks) {
        if (nticks <= 0) {
            return waiting.size();
        } else {
            condition c = new condition();
            waiting.insert(make_pair(nticks + curr_time, c));
            c.wait();
            free(c);
        }
        return waiting_num;
    }


    void entry tick(void) {
        waiting_num = waiting.size();
        curr_time++;

        while (waiting.head().first <= curr_time) {
            condition c = waiting.head().second;
            waiting.deleteHead();
            c.signal();
        }
    }
}

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;	
}