Prova teorica 2015.01.20

Testo: [1]

Esercizio c.1

Soluzione di S.G

/*
 * 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 count, rear, front, nw, nr;
	bool exitNull;
	conditions lw, lr;
	
	void lwlrbb(void){
		bb = new generic_type[MAX];
		exitNull = FALSE;
		rear = count = front = nw = nr = 0;
	}
	
	procedure entry void write(generic_type val){
		if(count == MAX){				// Il buffer è completamente pieno
			if(nw == MAX){				// ci sono già MAX scrittori che attendono di scrivere
				rear = (rear + 1) % MAX;	// Salto l'elemento da leggere da più tempo
				count--;
				lw.signal();			// il primo processo in attesa di scrivere puo' sbloccarsi.
			}
			nw++;
			lw.wait();
			nw--;
		}
		bb[front] = val;				// Il buffer non è pieno, scrivo
		count++;
		front = (front + 1) % MAX;
		lr.signal();
	}
	
	procedure entry generic_type read(void){
		generic_type retval;
		if(count == 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;
			}
		}			
		count--;				// Il buffer non è vuoto, leggo
		retval = bb[rear];
		rear = (rear + 1) % MAX;
		lw.signal();
	}
	
}

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

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

Ho implementato la coda. S.G (talk) 10:12, 22 November 2016 (CET)

---

Soluzione di BAGG

#define MAX 42

monitor lwlrbb {
    generic_type bb[] ;
    int count, front, rear ; 	/* rispettivamente: numero elementi, dove scrivere nel buffer, dove leggere nel buffer */
    int nw, nr ; 		/* rispettivamente numero di writer e reader */
    bool exit ; 		/* server ai reader per sapere se devono ritornare NULL al loro rientro nel monitor  */
    condition canr, canw ;

    lwlrbb(void) {
        bb = new generic_type[MAX] ;
        count = front = rear = nw = nr = exit = 0 ;
    }

    entry void write(generic_type val) {
        if(count == MAX) {			/* se count è MAX non si può scrivere  */
            if(nw == MAX) {			/* se la coda è piena devo fare spazio */	
                rear = (rear + 1)%MAX ;         /* rear indica il più vecchio elemento ancora da leggere, lo incremento --> salto l'elemento */
                count -= 1 ;
                nw += 1 ;			/* incremento prima perchè anche se la coda è piena ora dopo la signal ci sarà un posto...  */
                canw.signal() ;			/* ora il primo che aspettava può scrivere --> lo sveglio  */
                canw.wait() ;
                nw -= 1 ;
            } else {				/* se la coda non è piena devo comunque aspettare...  */
                nw += 1 ;
                canw.wait() ;
                nw -=1 ;
            }
        } 
	bb[front] = val ;					
        front = (front + 1)%MAX ;
        count += 1 ;
        canr.signal() ;				/* potrebbe esserci un reader che aspetta --> segnalo che ho scritto e si può leggere  */
    }

    entry generic_type read(void) {
        if(count == 0) {			/* se non c'è nulla da leggere allora devo aspettare  */
            if(nr == MAX) {			/* se la coda è piena setto exit, che i reader controllano per sapere se sono stati svegliati per ritornare NULL  */
                exit = 1 ;
                canr.signal() ;		        /* sveglio il condannato...  */
            } nr += 1 ;				/* mi accodo... */
            canr.wait() ;
            nr -= 1 ;
            if(exit) {				/* se sono il condannato resetto la variabile ed esco...  */
                 exit = 0 ;
                 return NULL ;
            }
        }
        generic_type r = bb[rear] ;
        rear = (rear + 1)%MAX ;
        count -= 1 ;
        canw.signal() ;				/* ho letto, quindi si è liberato un posto e almeno un writer può scrivere... */
        return r ;
    }
}

Soluzione di FedericoB

Essendo l'accesso al monitor in mutua esclusione non c'è da considerare il caso in cui ci siano più lettori in concorrenza.
La mia soluzione cerca di essere equa alternando scrittori a lettori.

monitor lwlrbb:
	
	Queue[generic_type] buffer
	int  waitingReaders, waitingWriters
	condition ok2write, ok2read 
	boolean exitNull;
	int max;
	
	lwlrbb (int max):
		self.max = max
		buffer = new List(max)
		waitingReaders = 0
		waitingWriters = 0
		exitNull = False
	
	@entry
	void write(generic_type val): 
		if (buffer.size()>=MAX) :
				if (waitingWriters>Max):
					buffer.dequeue() #discard element
					ok2write.signal()
			waitingWriters+=1
			ok2write.wait()
			waitingWriters-=1
		buffer.enqueue(val)
		if (waitingReaders>0) ok2read.signal()
		else if (waitingWriters>0) ok2write.signal()
	
	@entry
	generic_type read():
		if (buffer.isEmpty(): 
			if (waitingReaders>Max):
				exitNull = True #set flag to make the woke up reader return null
				ok2read.signal()
			waitingReaders++
			ok2read.wait()
			waitingReaders--
			if (exitNull):
				exitNull = False
				return null
		element = buffer.dequeue()
		if (waitingWriters>0) ok2write.signal()
		else if (waitingReaders>0) ok2read.signal()

Soluzione di sav, correggetemi se sbaglio

monitor lwlbb 
{
      buffer buf, wr  //buf = buffer di elementi e wr buffer di lettori
      condition oktoread, oktowrite
   
  Procedure entry read {
  
       if ( wr.len() < MAXLETTORI)
           if (buf.len() == 0)
                wr. enqueue(lettore)
                oktoread.wait(lettore)
                wr.dequeue(lettore)
                buf.dequeue()
           oktoread.signal()
       wr.dequeue()
       wr.enqueue(lettore)

}

   procedure entry write (val) {        //lo scrittore non resterà mai in attesa perché se non c'è spazio nel buffer toglie 
                                        //il primo elemento inserito e mette il suo nuovo e sblocca un eventuale lettore in attesa

        if (buf.len()< MAXBUFFER)
                 buf.enqueue(val)
                 oktoread.signal()
        buf.dequeue()
        buf.enqueue(val)
        oktoread.signal()
 }
}

Esercizio c.2

Soluzione di S.G

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)

Quindi una soluzione del genere potrebbe andar bene? S.G (talk) 09:23, 22 November 2016 (CET)

b = 0;

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

---

Soluzione di FedericoB

dualshift(a,b) |xxxxxxxx|yyyyyyyy| -> |0xxxxxxx|xyyyyyyy|
G=1
MUTEXIN
 do:
   L=0
   dualshift(G,L)
 while L==0;
MUTEXOUT
G=1

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)

Mi scuso per l'inconveniente, avendo seguito il corso di SO 2015/2016 ho pensato di creare una sezione PROVE SVOLTE che fosse ben visibile a tutti i corsi sia per gli anni precedenti sia per gli anni successi S.G (talk) 09:17, 22 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)

Mi scuso per l'inconveniente, avendo seguito il corso di SO 2015/2016 ho pensato di creare una sezione PROVE SVOLTE che fosse ben visibile a tutti i corsi sia per gli anni precedenti sia per gli anni successi. S.G (talk) 09:19, 22 November 2016 (CET)