Difference between revisions of "Prove scritte 2023"

From Sistemi Operativi
Jump to navigation Jump to search
(Created page with "= Parziale 2023/01/20 = == Esercizio c2 == Dato un servizio di message passing asincrono implementare un servizio di message passing sincrono a scambio che prevede una sola...")
 
 
(8 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
= Esame 2023/02/15 =
 +
 +
== Esercizio c1 ==
 +
 +
Scrivere il monitor redblack che fornisce una procedure entry: 
 +
 +
#define red 0
 +
#define black 1
 +
double rb(int color, double value)
 +
 +
I processi che usano il monitor redblack devono sincronizzarsi in modo che completino l'esecuzione di rb in modo alternato: se l'ultimo processo che ha completato rb aveva indicato il colore rosso il prossimo sia nero e viceversa. (in altre parole mai due processi che avevano chiamato rb con lo stesso colore possono proseguire uno dopo l'altro).
 +
 +
Il valore di ritorno di rb deve essere la media dei valori dei parametri "value" delle chiamate rb di colore "color" che sono state sbloccate.
 +
 +
Esempio: La chiamata rb(red, 2) non si blocca e ritorna 2, successivamente rb(red, 4) si blocca perché l'ultima sbloccata è rossa. Poi rb(black, 5) non si blocca perché l'ultima è rossa e ritorna 5 ma a questo punto si può sbloccare anche la chiamata precedente rb(red, 4) e il valore ritornato è 3 (la media fra 2 e 4).
 +
 +
=== Soluzione proposta 1 (da controllare)===
 +
Proposta da [[User: SpookyWiki |SpookyWiki]] ([[User talk:SpookyWiki|talk]]) 17:18, 25 May 2023 (CEST)
 +
 +
Assumo che per “il valore medio delle chiamate, per colore, sbloccate” voglia dire “il valore delle chiamate, per colore, che sono terminate”.
 +
 +
<syntaxhighlight lang=C>
 +
monitor redblack {
 +
Array<Double> sum[2]; //values[red] accede alla lista dei valori di red
 +
Array<int> count[2];
 +
int lastin;
 +
Array<condition> ok2col[2]; //condition[red] accede alla condition di red
 +
 +
redblack(){
 +
lastin=-1;
 +
count[red] = count[black = =;
 +
}
 +
 +
//vivere, vivere a colori e vivere, ...
 +
condition entry double rb(int color, int value) {
 +
if ( lastin == color ) { //l'ultima entry era di un colore opposto
 +
ok2col[color].wait();
 +
} //l'ultima entry era dello stesso colore, dobbiamo metterci in attesa
 +
sum[color] += value;
 +
count[color]++;
 +
lastin = color;
 +
double res = (sum[color]*1.0d) / count[color]; //questo ci assicura che la meccanica signal urgent non dia fastidio al risultato nel caso ci sia due processi di colore diverso in attesa
 +
//ok2col[1 - color].signal(); //diamo il segnale ai processi di colore opposto in attesa
 +
ok2col[!color].signal(); //c non ha true e false bensì false è l'intero 0 e true l'intero 1
 +
return res;
 +
}
 +
}
 +
</syntaxhighlight>
 +
 +
== Esercizio c2 ==
 +
 +
Dato un servizio di message passing asincrono implementare un servizio di message passing asincrono con contatore che ha tre primitive:
 +
#define ANY (pid_t) 0
 +
void casend(pid_t dest, T msg)
 +
T carecv(pid_t sender)
 +
int cacount(pid_t sender)
 +
Le primitive casend/carecv si devono comportare come la asend/arecv. La primitiva cacount deve avere come valore di ritorno il numero di messaggi che risultano in attesa di essere consegnati dal processo mittente indicato come paramentro.
 +
È possibile implementare un meccanismo di message passing completamente asincrono dato il servizio di message passing asincrono con contatore? (sì + come oppure no + perché).
 +
 +
== 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.
 +
 +
<nowiki>
 +
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 </nowiki>
 +
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 [[User: SpookyWiki |SpookyWiki]] ([[User talk:SpookyWiki|talk]]) 16:55, 25 May 2023 (CEST)
 +
 +
Se PA prima in readyqueue, 1ms di timeslice, la computazione finisce in 14ms senza attese
 +
 +
<nowiki>
 +
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 </nowiki>
 +
 +
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)
 +
<nowiki>
 +
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</nowiki>
 +
 +
PA inizia per primo, 2ms timeslice, performance uguali al caso con timeslice 1ms
 +
<nowiki>
 +
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 </nowiki>
 +
 +
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
 +
<nowiki>
 +
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 </nowiki>
 +
 +
caso CPU>IO
 +
<nowiki>
 +
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 </nowiki>
 +
 +
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
 +
<nowiki>
 +
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</nowiki>
 +
4ms
 +
<nowiki>
 +
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 </nowiki>
 +
 +
5ms
 +
<nowiki>
 +
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 </nowiki>
 +
 +
6ms
 +
<nowiki>
 +
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</nowiki>
 +
 +
7ms
 +
<nowiki>
 +
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</nowiki>
 +
 +
8ms
 +
<nowiki>
 +
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    </nowiki>
 +
 
= Parziale 2023/01/20 =
 
= 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 [[User: SpookyWiki |SpookyWiki]] ([[User talk:SpookyWiki|talk]]) 17:39, 17 May 2023 (CEST)
 +
 +
<syntaxhighlight lang=C>
 +
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;
 +
}
 +
 +
}
 +
</syntaxhighlight>
  
 
== Esercizio c2 ==  
 
== Esercizio c2 ==  
Line 9: Line 203:
  
 
=== Soluzione proposta 1 ===
 
=== Soluzione proposta 1 ===
−
Proposta da [[User: SpookyWiki |SpookyWiki]] ([[User talk:SpookyWiki|talk]]) 14:56, 17 May 2023 (CEST)
+
Proposta da [[User: SpookyWiki |SpookyWiki]] ([[User talk:SpookyWiki|talk]]) 16:55, 17 May 2023 (CEST)
  
 
<syntaxhighlight lang=C>
 
<syntaxhighlight lang=C>
Line 15: Line 209:
 
     asend(msg, dest);  
 
     asend(msg, dest);  
 
     return arecv(dest);  
 
     return arecv(dest);  
 +
}
 +
</syntaxhighlight>
 +
 +
= 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 [[User: SpookyWiki |SpookyWiki]] ([[User talk:SpookyWiki|talk]]) 18:45, 17 May 2023 (CEST)
 +
 +
<syntaxhighlight lang=C>
 +
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;
 +
}
 +
}
 
}
 
}
 
</syntaxhighlight>
 
</syntaxhighlight>

Latest revision as of 16:26, 25 May 2023

Esame 2023/02/15

Esercizio c1

Scrivere il monitor redblack che fornisce una procedure entry:  

#define red 0
#define black 1
double rb(int color, double value)

I processi che usano il monitor redblack devono sincronizzarsi in modo che completino l'esecuzione di rb in modo alternato: se l'ultimo processo che ha completato rb aveva indicato il colore rosso il prossimo sia nero e viceversa. (in altre parole mai due processi che avevano chiamato rb con lo stesso colore possono proseguire uno dopo l'altro).

Il valore di ritorno di rb deve essere la media dei valori dei parametri "value" delle chiamate rb di colore "color" che sono state sbloccate.

Esempio: La chiamata rb(red, 2) non si blocca e ritorna 2, successivamente rb(red, 4) si blocca perché l'ultima sbloccata è rossa. Poi rb(black, 5) non si blocca perché l'ultima è rossa e ritorna 5 ma a questo punto si può sbloccare anche la chiamata precedente rb(red, 4) e il valore ritornato è 3 (la media fra 2 e 4).

Soluzione proposta 1 (da controllare)

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

Assumo che per “il valore medio delle chiamate, per colore, sbloccate” voglia dire “il valore delle chiamate, per colore, che sono terminate”. 

monitor redblack {
	Array<Double> sum[2]; //values[red] accede alla lista dei valori di red
	Array<int> count[2];
	int lastin;
	Array<condition> ok2col[2]; //condition[red] accede alla condition di red
	
	redblack(){
		lastin=-1;
		count[red] = count[black = =;
	}

	//vivere, vivere a colori e vivere, ...
	condition entry double rb(int color, int value) {
		if ( lastin == color ) { //l'ultima entry era di un colore opposto
			ok2col[color].wait();
		} //l'ultima entry era dello stesso colore, dobbiamo metterci in attesa
		sum[color] += value;
		count[color]++;
		lastin = color;
		double res = (sum[color]*1.0d) / count[color]; //questo ci assicura che la meccanica signal urgent non dia fastidio al risultato nel caso ci sia due processi di colore diverso in attesa
		//ok2col[1 - color].signal(); //diamo il segnale ai processi di colore opposto in attesa
		ok2col[!color].signal(); //c non ha true e false bensì false è l'intero 0 e true l'intero 1
		return res;
	}
}

Esercizio c2

Dato un servizio di message passing asincrono implementare un servizio di message passing asincrono con contatore che ha tre primitive: 

#define ANY (pid_t) 0
void casend(pid_t dest, T msg)
T carecv(pid_t sender)
int cacount(pid_t sender)

Le primitive casend/carecv si devono comportare come la asend/arecv. La primitiva cacount deve avere come valore di ritorno il numero di messaggi che risultano in attesa di essere consegnati dal processo mittente indicato come paramentro. È possibile implementare un meccanismo di message passing completamente asincrono dato il servizio di message passing asincrono con contatore? (sì + come oppure no + perché).

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;
		}
	}
}
Retrieved from "https://so.v2.cs.unibo.it/wiki/index.php?title=Prove_scritte_2023&oldid=3006"