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
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
Cosa significa proporre a novembre le risposte a quesiti relativi a argomenti che spieghero' a marzo 2017?
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.