Prove scritte 2022

Prova 2022/06/21

Esercizio c2

= Consegna

Esercizio c.2: Un servizio viene fornito in modalità client-server usando message passing asincrono. Al fine di aumentare l'efficienza si decide di usare molti server e un processo dispatcher in grado di distribuire le richieste agli N server. Quando un processo server è libero riceve dal dispatcher la prossima richiesta da elaborare: codice di ogni client (tanti!): ..... asend(<getpid(), request>, dispatcher) result = arecv(dispatcher) server process[i], i = 0, ..., N-1:

request = arecv(dispatcher)
result = compute(request)
asend(<getpid(), result>, dispatcher)

Scrivere il processo dispatcher. (il dispatcher conosce i pid di tutti i server).

Soluzione proposta (da controllare)

Soluzione proposta da Flecart

extern int N;
process dispatcher() {
    // indice che tiene conto a quale server dover mandare
    // per semplicità supponiamo che i server abbiano PID
    // da 0 a N - 1
    int i = 0; 

    // mappa server a pid del processo che lo ha richiesto.
    // chiave: pid del server
    // value: queue richiesta dispatchata al server in chiave
    map<int, queue<int>> mapper; 
    while (true) {
        res = arecv(ANY);
        
        // in questa parte l'importante è sapere
        // se la richiesta proviene dal  server o da un altro
        // processo, ho assunto che la disambiguazione 
        // fosse immediata, un altro modo per checkare questo
        // è vedere se il PID del messaggio rientri fra quelli
        // noti al dispatcher.
        if (<pid, request> = res) {
            mapper[i].enqueue(pid);
            asend(request, i /*il i-esimo server*/);
            i++;
            i %= N;
        } else if (<pid, response> = res) {
            requester_pid = mapper[pid].dequeue();
            asend(response, requester_pid);
        }
    }
}

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