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--;
		}
							// 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;
			}
		}
						// Il buffer non è vuoto
		i--;
		retval = bb[i];
		lw.signal();			// Riattivo uno scrittore in coda
		return retval;	
	}
}

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

è uno stack! buonded buffer deve implementare una coda. Renzo (talk) 19:29, 21 November 2016 (CET)

---

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

a è errato, pensateci meglio. Per B la variabile a va indicata come locale al processo P (generico) che deve avere un loop infinito. Renzo (talk) 19:25, 21 November 2016 (CET)

---

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

Cosa significa proporre a novembre le risposte a quesiti relativi a argomenti che spieghero' a marzo 2017?Renzo (talk) 19:20, 21 November 2016 (CET)

---

Esercizio g.2

a) Se un sistema ha una RAM molto ampia puo' non essere utile usare la memoria virtuale. In questo caso ha senso egualmente usare la paginazione di memoria? Perche'?

b) Perche' i metodi di sincronizzazione tipo test&set (detti anche spinlock) assumono grande rilevanza nella scrittura di sistemi operativi multiprocessore?

c) Confrontare gli alogritmi di scheduling roud robin e a priorita' statica. Indicare in quali casi sono da usare algoritmi di tipo round robin e quando quelli a priorita' statica.

Svolgimento

a) Paginazione è un metodo di gestione della memoria che permette che lo spazio degli indirizzi fisici di un processo non sia contiguo, inoltre ha i seguenti vantaggi: - riduce il fenomeno della frammentazione interna - minimizza (elimina) il fenomeno della frammentazione esterna

b) Perchè permette di risolve il problema della sezione critica in modo relativamente semplice. Infatti l'istruzione test&set è eseguita atomicamente, cioè come un'unita non soggetta a interruzzioni; quindi se si eseguono contemporaneamente due istruzioni test&set, ciascuna su processori diversi, queste vengono eseguite in modo sequenziale in un ordine arbitrario.

c) Scheduling a priorità statica associa una priorità a ogni processo e si assegna la CPU al processo con priorità più alta; i processi con priorità uguali si ordinano secondo una politica FCFS. Questo algoritmo può essere sia con prelazione sia senza prelazione, inoltre soffre dell'attesa indefinita (starvation). Infatti un flusso costante di processi con priorità maggiore può impedire a un processo con priorità più bassa di accedere alla CPU. E' possibile utilizzare questo algoritmo quando alcuni processi hanno più importanza di altri. es: nel caso di sistemi multimediali, come una smart TV, il processo di riproduzione video è più importante rispetto ad un processo gestore di posta, altrimenti il flusso video potrebbe essere discontinuo.

Scheduling circolare (round-robin) è un algoritmo con prelazione in cui ogni processo viene eseguito al massimo per un quanto di tempo. E' bene che il quanto di tempo sia maggiore del tempo necessario al cambio di contesto. Questo algoritmo a differenza dello scheduling a priorità statica non soffre di starvation. E' possibile utilizzare questo algoritmo in sistemi in cui si pretende un finto parallelismo. es: nel caso in cui più studenti accedano ad una determinata macchina del laboratorio.

S.G (talk) 11:24, 21 November 2016 (CET)

Cosa significa proporre a novembre le risposte a quesiti relativi a argomenti che spieghero' nel secondo semestre?Renzo (talk) 19:21, 21 November 2016 (CET)