20210526c1 - Revision history

Flecart: /* Consegna */

2022-11-06T19:19:51Z

Consegna

Flecart: /* 2 fix errore */

2022-11-06T19:17:37Z

2 fix errore

Flecart: /* 2 */

2022-11-06T14:03:04Z

Flecart at 14:02, 6 November 2022

2022-11-06T14:02:09Z

Flecart at 14:00, 6 November 2022

2022-11-06T14:00:37Z

Flecart at 13:56, 6 November 2022

2022-11-06T13:56:05Z

Flecart at 13:55, 6 November 2022

2022-11-06T13:55:41Z

Flecart: Created page with "1:

 put è bloccato quando non c'è nessun processo che è in attesa di una get. Se ci sono delle put in attesa e riceve una get, questa get riceve tutte le put.  Get è..."

2022-11-06T13:43:07Z

Created page with "1: <pre> put è bloccato quando non c'è nessun processo che è in attesa di una get. Se ci sono delle put in attesa e riceve una get, questa get riceve tutte le put. Get è..."

New page

1:

<pre>
put è bloccato quando non c'è nessun processo che è in attesa di una get.
Se ci sono delle put in attesa e riceve una get, questa get riceve tutte le put.

Get è bloccato quando non c'è nessun put.
Quando arriva un put la get prende il singolo put

Si può vedere come sono fondamentali il numero di get e numero di put in ogni momento.

Sia np il numero di put, e ng il numero di get.

Si può concludere che se np==0 e ng == 0 allora il prossimo processo che chiama get o put
è bloccato.

se ng == 0 le put sono sempre bloccate.
se np == 0 le get sono sempre bloccate.

allora possiamo decrivere ad alto livello la soluzione

void put(T value) {
<np++>
<await ng != 0 -> dai value al primo get che mi sblocca>
<np-->
}

list of T get() {
<ng++>
<await np != 0 -> prendi tutti valori che le put ti danno>
<ng-->
return valori che hai trovato nell'await.
}

La parte complessa è la gestione del passaggio di valori fra le get e le put, possiamo risolverlo con
una coda condivisa, che rappresenta il passaggio dei valori

queue<int> coda, questo parametro sarà la struttura di dati condivisa per passarci i valori tra un processo
all'altro

void put(T value) {
< np++ >

<await ng != 0 ->
coda.add(value);
np--;
>
}

list of T get() {
queue<int> coda_locale;
<ng++>
<await np != 0 ->
<await np == 0 ->
coda_locale = coda; // prendi la coda globale solo quando tutte le put hanno finito
coda = empty(coda); // svuota la coda globale.
>
ng--;
>

return coda_locale;
}

Procediamo a tradurre ora tutte le soluzioni con await in soluzioni con semafori validi.

// SOLUZIONE PROPOSTA con paradigma di Andrews, creata con awaits.

semaphore semp(0); // arbitro i puts.
semaphore semgzero(0); // arbitro i gets/
semaphore semgone(0); // arbitro
semaphore mutex(1);
waitinggzero = 0; // chiamata da get, aspetto che il valore sia 0
waitinggone = 0; // chiamaga da get, aspetto che il valore sia 1
waitingp = 0; // aspetto put
list<T> coda; // lista condivisa

void put(T value) {
mutex.P();
np++;
SIGNAL();

mutex.P();
if (ng == 0) {
waitingp++;
mutex.V();
semp.P();
waitingp--;
}
coda.add(value);
np--;
SIGNAL();
}

list of T get() {
lista<T> lista_locale;

mutex.P();
ng++;
SIGNAL();

mutex.P();

// blocca finché non c'è un put
if (np == 0) {
waitinggone++;
mutex.V();
semgone.P();
waitinggone--;
}

// blocca finché i put non hanno aggiunto in coda
if (np != 0) {
waitinggzero++;
mutex.V();
semgzero.P();
waitinggzero--;
}

lista_locale = coda;
ng--;
SIGNAL();

return lista_locale;
}

void SIGNAL() {
if (waitinggone > 0 && np != 0)
semgone.V();
else if (waitingzero > 0 && np == 0) {
semgzero.V();
} else if (waitingp > 0 && ng != 0) {
semp.V();
} else {
mutex.V();
}
}
</pre>

Questa soluzione è sbagliata perché può succedere questo:

Ho 3 PUT in attesa di un get, arriva la get, le 3 put eseguono tutto e mettono a 0 ng, allora la get pensa che non cisiano
puts prima di lei, e si mette ad aspettare che arrivino altre put.

@@ Line 1: / Line 1: @@
 == Consegna ==
-TODO
+Esercizio c.1: Un buffer sincrono strampalato (bss) ha due procedure entry:
 == 1 ==

@@ Line 150: / Line 150: @@
 == 2 ==
 <syntaxhighlight lang=C>
 int num = 0; // se è positiva rappresenta numero di gets che aspettano, se negativa, numero di puts
 semaphore semput(0);
@@ Line 158: / Line 157: @@
 void put(T value) {
      mutex.P();
      if (num <= 0) {
@@ Line 167: / Line 167: @@
      global_list.add(value);
      if (num < 0)
          semput.V();
@@ Line 176: / Line 177: @@
-list of T get() {
+list<T> get() {
      list<T> local_list;
      mutex.P();
      if (num >= 0) {
          num++;
@@ Line 189: / Line 190: @@
          semget.P();
+     }
-     local_list = global_list;
+     // signal
-     global_list = list<T>(); // put empty list
+    if (num > 0) {
+        semget.V();
-    mutex.V();
+     } else {
      return local_list;
+}
 </syntaxhighlight>

@@ Line 149: / Line 149: @@
 == 2 ==
+<syntaxhighlight lang=C>
 int num = 0; // se è positiva rappresenta numero di gets che aspettano, se negativa, numero di puts
@@ Line 199: / Line 198: @@
+}
-</pre>
+</syntaxhighlight>

@@ Line 5: / Line 5: @@
 puts prima di lei, e si mette ad aspettare che arrivino altre put.
-:
+== 1 ==
 <pre>
@@ Line 145: / Line 145: @@
-:
+== 2 ==
 <pre>
@@ Line 153: / Line 153: @@
 semaphore semget(0);
 semaphore mutex(1);
 void put(T value) {

@@ Line 1: / Line 1: @@
 :
@@ Line 138: / Line 144: @@
 </pre>
 :

@@ Line 1: / Line 1: @@
 Questa soluzione è sbagliata perché può succedere questo:
@@ Line 4: / Line 9: @@
 Ho 3 PUT in attesa di un get, arriva la get, le 3 put eseguono tutto e mettono a 0 ng, allora la get pensa che non cisiano
 puts prima di lei, e si mette ad aspettare che arrivino altre put.
 <pre>

← Older revision		Revision as of 13:55, 6 November 2022
Line 142:		Line 142:
	Ho 3 PUT in attesa di un get, arriva la get, le 3 put eseguono tutto e mettono a 0 ng, allora la get pensa che non cisiano		Ho 3 PUT in attesa di un get, arriva la get, le 3 put eseguono tutto e mettono a 0 ng, allora la get pensa che non cisiano
	puts prima di lei, e si mette ad aspettare che arrivino altre put.		puts prima di lei, e si mette ad aspettare che arrivino altre put.
		+
		+	2:
		+
		+	<pre>
		+
		+	int num = 0; // se è positiva rappresenta numero di gets che aspettano, se negativa, numero di puts
		+	semaphore semput(0);
		+	semaphore semget(0);
		+	semaphore mutex(1);
		+
		+	void put(T value) {
		+	mutex.P();
		+	if (num <= 0) {
		+	num--;
		+	mutex.V();
		+	semput.P();
		+	num++;
		+	}
		+	global_list.add(value);
		+
		+	if (num < 0)
		+	semput.V();
		+	else
		+	semget.V();
		+
		+	return;
		+	}
		+
		+
		+	list of T get() {
		+	list<T> local_list;
		+	mutex.P();
		+
		+	if (num >= 0) {
		+	num++;
		+	mutex.V();
		+	semget.P();
		+	num--;
		+	} else {
		+	semput.V();
		+	semget.P();
		+	}
		+
		+	local_list = global_list;
		+	global_list = list<T>(); // put empty list
		+
		+	mutex.V();
		+
		+	return local_list;
		+	}
		+
		+	</pre>