Prove scritte 2023

Esame 2023/02/15

Esercizio g1

Siano dati due processi in esecuzione in un sistema monoprocessore e gestiti da uno scheduler round- robin.I due processi sono gli unici nel sistema e usano la stessa unità di I/O gestita in modo FIFO.

PA: 1ms CPU, 2ms I/O, 1ms CPU, 8ms I/O, 1ms CPU
PB: 2ms CPU, 1ms I/O, 8ms CPU, 1ms I/O, 1ms CPU 

Quale è il tempo minimo e quale il tempo massimo impiegato dal sistema per completare l’elaborazione dei due processi al variare della lunghezza del quanto di tempo e della posizione iniziale dei processi nella ready queue (PA precede PB o viceversa).

Soluzione proposta 1 (da controllare)

Proposta da SpookyWiki (talk) 16:55, 25 May 2023 (CEST)

Se PA prima in readyqueue, 1ms di timeslice, la computazione finisce in 14ms senza attese

CPU A B B A B B B B B B B B A B
IO    A A B A A A A A A A A B 

Se PB prima in readyQueue, 1ms di time slice, la computazione finisce a 15ms con 1 context switch per fine di timeslice e 1 attesa per IO (da parte di B)

CPU B A B     A B B B B B B B B A B
IO      A A B A A A A A A A A B

PA inizia per primo, 2ms timeslice, performance uguali al caso con timeslice 1ms

CPU A B B A B B B B B B B B A B
IO    A A B A A A A A A A A B 

PB inizia prima, timeslice 2ms, abbiamo due casi: nel caso di fine timeslice e riempimento di readyqueue allo stesso ms, Scheduler da la priorità a chi è già in CPU o no.

nel caso chi fosse già in CPU avesse la priorità, ci mettiamo 18ms, nel caso opposto 16

caso IO>CPU

CPU B B A B B A B B B B B B        A B
IO      B A A    A A A A A A A A B 

caso CPU>IO

CPU B B A B B B B A B B B B               A B 
IO      B A A           A A A A A A A A B 

visto che il caso IO>CPU è il migliore continueremo su quello

Aumentando il timeslice, il caso Pa prima di Pb non varia in quanto, essendo il primo job di pa un ms di cpu, i job dei due processi si sincronizzano perfettamente non andando mai in collisione. Invece, se eseguiamo prima pb avremo dei problemi quando Pb è in cpu per 8 secondi, ogni ms in più di timeslice comporta un ms in più di esecuzione, fino ad un timeslice di 8ms e un tempo di esecuzione di 22ms dato che si causerà attesa sull’esecuzione del terzo job di Pb.

Pb→ Pa

3ms

CPU B B A B B B A B B B B B       A B
IO      B A A     A A A A A A A A B 
ATT           A B         B B B

4ms

CPU B B A B B B B A B B B B         A B
IO      B A A       A A A A A A A A B 
ATT           A A B         B B B B 

5ms

CPU B B A B B B B B A B B B           A B
IO      B A A         A A A A A A A A B 
ATT           A A A B       B B B B B 

6ms

CPU B B A B B B B B B A B B             A B
IO      B A A           A A A A A A A A B 
ATT           A A A A B     B B B B B B

7ms

CPU B B A B B B B B B B A B               A B
IO      B A A             A A A A A A A A B 
ATT           A A A A A B   B B B B B B B

8ms

CPU B B A B B B B B B B B A B               A
IO      B A A             B A A A A A A A A 
ATT           A A A A A A    

Parziale 2023/01/20

Esercizio c1

Scrivere il monitor fullbuf che abbia le seguenti procedure entry:

void add(int value)
int get(void)

Le prime MAX chiamate della procedure entry add devono bloccare i processi chiamanti. In seguito deve sempre valere Na >= MAX indicando con Na il numero di processi bloccati in attesa di completare la funzione add. La funzione get deve attendere che Na > MAX, restituire la somma algebrica dei parametri value delle chiamate add in sospeso e riattivare il primo processo in attesa di completare la add (se la get richiede che Na > MAX, la get può riattivare un processo e al completamento della get si rimarrà garantito che Na >= MAX)

Soluzione proposta 1 (da controllare)

Proposta da SpookyWiki (talk) 17:39, 17 May 2023 (CEST)

monitor fullbuf {
	int MAX; //numero massimo di proc che devono essere bloccati sul buffer
	int Na;
	int mem;

	condition wait4get;
	condition wait4add;

	fullbuf(int max) {
		MAX = max;
		Na = 0;
		mem = 0;
	}

	procedure entry void add(int value) {
		Na++;                   //mi segnalo in attesa

		if( Na > MAX ) {        //se ci sono abbastanza processi in attesa
			wait4add.signal();  //attivo la get

		wait4get.wait();        //mi metto effettivamente in attesa
		mem = value;            //metto a disposizione il mio valore
	}

	procedure entry int get(void) {
		if ( !(Na > MAX) )      //se non ci sono abbastanza get in attesa
			wait4add.wait();    //mi metto in attesa

		int result = 0; 

		while( Na > MAX ) {     //finchè c'è un surplus di add in attesa
			wait4get.signal();  //riattivo il primo add in attesa
			result += mem;      //prendo il suo valore
			Na--;
		}
		return result;
	}

}

Esercizio c2

Dato un servizio di message passing asincrono implementare un servizio di message passing sincrono a scambio che prevede una sola chiamata:

T xchange(T msg, pid_t dest) 

dove T è un tipo generico (potrebbe essere int, string, struct mystruct). Il parametro dest non può essere ANY. Quando il processo P chiama xchange(m1, Q) e il processo Q chiama xchange(m2, P) entrambi i processi vengono riattivati, la xchange chiamata da P restituirà m2 mentre la xchange di Q restituirà m1.

Soluzione proposta 1

Proposta da SpookyWiki (talk) 16:55, 17 May 2023 (CEST)

T xchange(T msg, pid_t dest) { 
    asend(msg, dest); 
    return arecv(dest); 
}

Prova 2023/01/18

Esercizio c1

Scrivere il monitor synmsg che consenta uno scambio di messaggi fra due processi in maniera sincrona. Il processo produttore esegue il seguente codice.

producer: process:
 while True:
  msg_t msg = produce_new_msg()
  synmsg.send(&msg)

e il processo consumatore:

producer: process: while True:
 msg_t msg synmsg.recv(&msg) 
 consume_msg(&msg)

Come si vede le procedure entry hanno come parametro l'indirizzo del messaggio:

procedure entry void send(msg_t *msg)
procedure entry void recv(msg_t *msg)

Il monitor deve trasferire il contenuto del messaggio direttamente fra i processi usando la funzione:

void copymsg(msg_t *src, msg_t *dest)

(Il monitor non deve avere buffer di tipo msg_t ma solo variabili di tipo puntatore a msg_t.)

Soluzione proposta 1

Proposta da SpookyWiki (talk) 18:45, 17 May 2023 (CEST)

monitor synmsg {
	msg_t *address;

	int waiting2send;
	int waiting2recv;

	condition waiting4sender;
	condition waiting4recvr;

	synmsg() {
		address = NULL;
		waiting2send = 0;
		waiting2recv = 0;
	}

	procedure entry void send(msg_t *msg) {
		if ( waiting2recv == 0) {
			waiting2send++;
			waiting4recvr.wait();
			waiting2send--;
			copymsg(msg, address);
		} else {
			address = msg;
			waiting4sendr.signal()
			address = NULL;
		}
	}

	procedure entry void recv(msg_t *msg) {
		if ( waiting2send == 0) {
			waiting2recv++;
			waiting4sendr.wait();
			waiting2recv--;
			copymsg(address, msg);
		} else {
			address = msg;
			waiting4recvr.signal();
			address = NULL;
		}
	}
}