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
Pseudocodice simil python. Forse soluzione troppo lunga, si può migliorare.
monitor lwlrbb
Queue[generic_type] buffer
int numWriter, numReader, waitingReader, waitingWriters
condition ok2write, ok2read
int max;
lwlrbb (int max)
self.max = max
buffer = new List(max)
numWriter = 0
numReader = 0
waitingReader = 0
write_last = false;
@entry
void write(generic_type val)
if (buffer.size()>=MAX) and (waitingWriters>Max)
#wakeup for discard
ok2write.signal()
if (numWriter>0 or numReader>0) or (buffer.size>=MAX)
waitingWriters+=1
ok2write.wait()
waitingWriters-=1
if (waitingReader >=Max)
buffer.dequeue()
ok2write.signal()
return;
numWriter+=1
buffer.enqueue(val)
numWriter-=1
ok2write.signal()
if (waitingReader>0) ok2read.signal()
else if (waitingWriters>0) ok2write.signal()
@entry
generic_type read()
if (buffer.isEmpty()
if (waitingReader>Max):
#do not decrement waitingReader
ok2read.signal()
else
waitingReader+=1
ok2read.wait()
if (nwriter>0 or waitingWriters>0)
waitingReader +=1
ok2read.wait()
waitingReader-=1
if (waitingReader >= max)
ok2read.signal()
return null
else
numReader+=1
element = buffer.dequeue()
numReader-=1
if (waitingReader>0) ok2read.signal()
else if (waitingWriters>0) ok2write.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)