Prove scritte 2022

Prova 2022/06/01

Esercizio c1

Consegna

Esercizio c.1: Scrivere il monitor delayvalue con una sola procedure entry:

 int delay(int value);

Il monitor deve sospendere i primi NDELAY processi che chiamano la delay. Le successive chiamate di delay devono mantenere costante il numero di processi sospesi, ogni successiva chiamata devo riattivare il primo processo in attesa prima di sospendersi, la delay ritorna il valore passato come parametro dal processo che ne ha riattivato l'esecuzione. e.g. se NDELAY è 2:

 P1: delay(44) -> P1 si sospende
 P2: delay(40) -> P2 si sospende
 P3: delay(42) -> P1 si riattiva e ritorna 42, P3 si sospende
 P4: delay(22) -> P2 si riattiva e ritorna 22, P4 si sospende

Soluzione proposta 1

Soluzione proposta da Flecart, da controllare

Stack<semaphore> stack[MAX_PRIORITY];
int num_V = 0;
semaphore mutex(1);

void  PLP(int prio) {
    mutex.P();
    if (num_V > 0) {
        num_V--;
        mutex.V();
        return;
    }
    
    semaphore sem = semaphore(0);
    stack[prio].push(sem);
    mutex.V();
    sem.P();

    mutex.V();
}


void PLV() {
    mutex.P();
    
    for (int i = MAX_PRIORITY - 1; i >= 0; i--) {
        if (stack[i].size() > 0) {
            sem = stack[i].pop();
            sem.V();
            return;
        }
    }

    num_V++;

    mutex.V();
}

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