Prova teorica 2015.01.20

Testo: [1]

Esercizio c.1

/*
 * Esercizio c.1: Scrivere il monitor lwlrbb. Il monitor deve implementare le seguenti procedure entry:
 * void write(generic_type val);
 * generic_type read(void);
 * Il lwlrbb si comporta come un bounded buffer di MAX elementi che coordina l'attivita' di numerosi processi
 * produttori/scrittori e numerosi lettori/consumatori. lwlrbb ammette un numero massimo (sempre MAX) di lettori 
 * e scrittori in attesa. Se il buffer e' vuoto e ci sono piu' gia' MAX lettori in attesa, il lettore che e' in 
 * attesa da piu' tempo esce resituendo NULL. In ugual modo se il buffer e' completamente pieno e ci sono gia' MAX 
 * scrittori che attendono di scrivere viene perduto il valore che da piu' tempo nel buffer attende di venir letto, 
 * il primo processo in attesa di scrivere puo' cosi' scrivere il suo elemento nel buffer e sbloccarsi.
 */
#define MAX 

monitor lwlrbb{
	generic_type bb[];
	int i, nw, nr;
	bool exitNull;
	conditions lw, lr;
	
	void lwlrbb(void){
		bb = new generic_type[MAX];
		exitNull = FALSE;
		i = nw = nr = 0;
	}
	
	procedure entry void write(generic_type val){
		if(i == MAX){					// Il buffer è completamente pieno
			if(nw == MAX){				// ci sono già MAX scrittori che attendono di scrivere
								// spostamento a sinistra di tutti gli elementi, in modo da perdere
				for(j = 0; j<i; j++)		// il valore da più tempo nel buffer
					bb[j] = bb[j+1];
				i--;
				lw.signal();			// il primo processo in attesa di scrivere puo' scrivere e sbloccarsi.
			}
			nw++;
			lw.wait();
			nw--;
		}
		else{						// Il buffer non è pieno
			bb[i] = val;
			i++;
			lr.signal();
		}
	}
	
	procedure entry generic_type read(void){
		generic_type retval;
		if(i == 0){				// Il buffer è vuoto
			if(nr == MAX){			// ci sono gia MAX lettori in attesa
				exitNull = TRUE;	// quindi riattivio il lettore che e' in attesa da piu' tempo, restituendo NULL
				lr.signal();
			}
			nr++;				// incremento il contatore dei lettori in coda
			lr.wait();			// metto in attesa il lettore
							// Riprendo l'esecuzione da dove era stata interrotta
			nr--;				// decremento il contatore dei lettori in coda
			if(exitNull){			// Controllo se è una richiesta di uscita forzata
				exitNull = FALSE;
				return NULL;
			}
		}
		else{					// Il buffer non è vuoto
			i--;
			retval = bb[i];
			lw.signal();			// Riattivo uno scrittore in coda
		}	
	}
}

S.G (talk) 14:39, 18 November 2016 (CET)
Ho scritto una possibile soluzione dell'esercizio c.1. Iniziare qui una discussione

---

Esercizio c.2

a) Si consideri la funzione atomica dualshift(a,b) che opera su due operandi di tipo byte passati per indirizzo. L'operazione fa lo shift a destra dei due operandi. Il bit piu' significativo di a viene posto a zero, il bit piu' significativo di b diviene quello che all'atto della attivazione di dualshift era il bit meno significativo di a. es. se a vale 6 e b vale 4 dopo la chiamata di dualshift(a,b) a vale 3 e b 2. Se a vale 5 e b 6 dopo la chiamata dualshift (a,b) a vale 2 e b vale 131 (128+3). La funzione dualshift puo' essere usata al posto della test&set per la sincronizzazione fra processi? Dimostrare la risposta. b) Si consideri ora la funzione andor(a,b) che opera su due opera su due parametri di tipo booleano passati per indirizzo e cosi' definita: andor(a,b)=<c=a or b; b=a and b; a=c> Puo' la funzione andor essere usata al posto della test&set per la sincronizzazione fra processi? Dimostrare la risposta. Si ricorda che le operazioni di assegnazione di valori costanti a variabili vengono considerati atomici.

Svolgimento

a) Non è possibile utilizzare la funzione atomica dualshift(a,b) in quanto per la definizione di test&set(a,b)

test&set(a,b){
    a = b;
    b = X;   // Dove X è un valore costante
}

La funzione dualshift dovrebbe memorizzare (in qualche modo) il valore precedente di a (o b), e successivamente settare a (o b) ad un valore costante. Questo non accade perchè la stessa funzione divide per 2 i valori di a e b ogni volta che viene richiamata (caso particolare in cui venga copiato il bit meno significativo di a nel bit più significativo di b). Quindi è impossibile soddisfare la richiesta.

b) La funzione andor(a,b) può essere utilizzata al posto della test&set per la sincronizzazione fra processi. Dimostrazione. La funzione andor(a,b) è definita come segue:

andor(a, b){
	c = a | b;
	b = b & a;
	a = c;
}

Posto a = 0, non avremo altro che:

andor(a, b){
	c = b;
	b = 0;
	a = c;
}

Quindi la funzione andor, non è altro che una semplice test&set.

a = 0;
b = 1;

Process P {
	do{
		andor(a, b);
	} while(!a);
	//critical section
	b = 1;
	// non-critical section
}

S.G (talk) 14:39, 18 November 2016 (CET)
Ho scritto una possibile soluzione dell'esercizio c.2. Iniziare qui una discussione

---

Esercizio g.1

a) Sia data la seguente stringa di riferimenti: 123451234123121. mostrare il comportamento degli algoritmi MIN e LRU quando operano su una memoria di 3 frame. b) Data una memoria di 4 frame contenente la pagina 4 nel frame 1, la pagina 3 nel frame 2, la pagina 2 nel frame 3 e infine la pagina 1 nel frame 4. Mostrare una stringa di riferimenti di un programma che usi 5 pagine (esiste la pagina 5 non ancora mappata in memoria oltre alle 4 cariate nei frame) e che consenta alla fine dell'esecuzione di avere tutte le pagine nel frame di indice corrispondente. La pagina 1 nel frame 1, la pagina 2 nel frame 2 e cosi' via.

Esecuzione algoritmo MIN

-------------------------------------------------------------
| 1 | 2 | 3 | 4 | 5 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 1 | 2 | 1 |
-------------------------------------------------------------

-------------------------------------------------------------
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
-------------------------------------------------------------
|   | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
-------------------------------------------------------------
|   |   | 3 | 4 | 5 | 5 | 5 | 3 | 4 | 4 | 4 | 3 | 3 | 3 | 3 |
-------------------------------------------------------------

Esecuzione algoritmo LRU

-------------------------------------------------------------
| 1 | 2 | 3 | 4 | 5 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 1 | 2 | 1 |
-------------------------------------------------------------

-------------------------------------------------------------
| 1 | 1 | 1 | 4 | 4 | 4 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 |
-------------------------------------------------------------
|   | 2 | 2 | 2 | 5 | 5 | 5 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 |
-------------------------------------------------------------
|   |   | 3 | 3 | 3 | 1 | 1 | 1 | 4 | 4 | 4 | 3 | 3 | 3 | 3 |
-------------------------------------------------------------

Una possibile sequenza utilizzando l'algoritmo con sostituzione FIFO

-------------------------------------------------------------
| 4 | 3 | 2 | 1 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 |
-------------------------------------------------------------

S.G (talk) 12:19, 19 November 2016 (CET)
Ho scritto una possibile soluzione dell'esercizio g.1. Iniziare qui una discussione