Prove scritte 2015
Jump to navigation
Jump to search
Esame 14/02/2015
Esercizio c.1 (da controllare)
monitor altcolbb {
generic_type valueBuf[MAX];
int front = rear = 0;
bool isFull = false;
condition ok2write[2]; //gli indici sono i colori (red=0, blue=1)
lastColor = None;
entry void write(color_t color, generic_type val) {
if (front == rear)
if(isFull)
ok2write[color].wait();
else
if (lastColor == color)
ok2write[color].wait();
valueBuf[front] = val;
front = (front+1) % MAX;
lastColor = color;
if (front == rear)
isFull = true;
else
ok2write[1-color].signal();
ok2read.signal();
}
entry generic_type read(void) {
if (rear == front)
if (!isFull)
ok2read.wait();
generic_type tmpValue = valueBuf[rear];
rear = (rear + 1) % MAX;
if (rear == front)
isFull = false;
color_t tmpColor = lastColor;
lastColor = None;
ok2write[tmpColor].signal(); //quando un lettore legge l'ultimo elemento
//dal buffer, ci possono solo essere scrittori
//in attesa che abbiano lo stesso colore
//dell'ultimo elemento.
else
ok2write[1-lastColor].signal();
return tmpValue;
}
}
Esercizio c.1 (da controllare)
#define MAX n
condition ok2read;
condition ok2write;
condition ok2red;
condition ok2blue;
queue buffer;
Procedure entry: void write(color_t color, generic_type val)
{
if(buffer.lenght() >= MAX)
ok2write.wait();
if((<color> == buffer.last()) == color)
{
if(color == red)
ok2red.wait();
else
ok2blue.wait();
}
buffer.enqueue(<color, val>);
ok2read.signal();
if(buffer.lenght() < MAX)
{
if(color == red)
ok2blue.signal();
else
ok2red.signal();
}
}
Procedure entry: generic_type read(void)
{
generic_type val;
if(buffer.lenght == 0)
ok2read.wait();
<val> = buffer.dequeue();
ok2write.signal()
return val;
}
Esercizio c.2 (da controllare)
- Verificato dall'utente ? in data ?
Il programma dispone di una mutex per l'accesso protetto alla variabile n, e dei due semafori s1 ed s2 per regolare l'alternanza tra i thread A e AB. Sulla base di essi, e del fatto che entrambi i thread eseguono 2 cicli, è possibile affermare (verificare) che
- L'alternanza dei due thread è A-AB-A-AB o
- L'alternanza dei due thread è AB-A-AB-A
Infatti se il thread A svolgesse due cicli consecutivamente, invocherebbe s1.P() due volte senza fare mai ricorso a s1.V() (ragionamento analogo per AB); pertanto è necessario attendere l'intervento dell'altro thread in attesa di una chiamata su s1.V().
Per concludere, i possibili valori di n al termine del programma saranno, in corrispondenza delle due diramazioni elencate sopra
- n = 12
- n = 5
Esercizio g.1
- Verificato dall'utente Acsor in data 23/08/2020. Ritengo sia: corretto
- Verificato dall'utente ? in data ?
Punto a)
MIN:
Stringa di riferimenti: 0 1 2 3 4 5 0 1 2 3 4 0 1 2 3 0 1 2 0 1 0
Frame 1: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Frame 2: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Frame 3: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
Frame 4: 3 4 5 5 5 5 3 4 4 4 4 3 3 3 3 3 3 3
FIFO:
Stringa di riferimenti: 0 1 2 3 4 5 0 1 2 3 4 0 1 2 3 0 1 2 0 1 0
Frame 1: 0 0 0 0 4 4 4 4 2 2 2 2 1 1 1 1 1 1 1 1 1
Frame 2: 1 1 1 1 5 5 5 5 3 3 3 3 2 2 2 2 2 2 2 2
Frame 3: 2 2 2 2 0 0 0 0 4 4 4 4 3 3 3 3 3 3 3
Frame 4: 3 3 3 3 1 1 1 1 0 0 0 0 0 0 0 0 0 0
Punto b)
Stringa di riferimenti: 0 1 2 3 4 0 1 2 3 0 1 4 2 0 3 4 1 2 3 4
Frame 1: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
Frame 2: 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2
Frame 3: 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 3 3
Frame 4: 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
Esercizio g.2 (da controllare)
- Verificato dall'utente ? in data ?
- ...
- Frammentazione interna: allocazioni di pagine la cui dimensione è strettamente maggiore di quella effettivamente richiesta. Frammentazione esterna: nessuno. Infatti ogni spazio (pagina) allocato e liberato è prima o poi riallocato.
- Se non viene utilizzato un sistema di caching, una lettura diretta a più blocchi di un file di grandi dimensioni richiede: la lettura della FAT, solitamente posta all'inizio di un volume (e dunque, su dischi rotazionali, in una traccia differente da quella attuale o da quella del blocco da leggere); la lettura del blocco stesso, e dunque lo spostamento della testina nella traccia e nel settore di interesse
- Uno scheduling a priorità statica può essere utile ad un processo interattivo, dove è necessario mantenersi all'interno di date soglie temporali o semplicemente svolgere un dato compito con meno ritardo possibile; esempi concreti: un processo che faccia streaming video; un processo appartenente ad un server il cui obiettivo primario è soddisfare le richieste dei propri client il prima possibile, ma dove può anche essere svolta qualche attività dai processi locali (es. programmi applicativi). In uno scheduling a priorità statica, se la presenza di processi ad alte priorità è costante, possono verificarsi indesiderati fenomeni di starvation nei confronti di processi meno prioritari.
- Domanda puramente nozionistica, la cui risposta può essere ricavata consultando note, lucidi o libri di testo.
Esame 20/01/2015
Esercizio c.1 (da controllare)
- Controllato dall'utente Acsor in data 21/08/2020
- Controllato dall'utente ? in data ?
- ...
#define MAX n
condition ok2read;
condition ok2write;
queue buffer;
int waiting_write = 0;
int waiting_read = 0;
Procedure entry: void write(generic_type val) {
if (buffer.lenght() >= MAX) {
if (waiting_write >= MAX) {
buffer.dequeue(); // il valore va perso
ok2write.signal();
}
waiting_write++;
ok2write.wait();
waiting_write--;
}
buffer.enqueue(val);
ok2read.signal();
}
Procedure entry: generic_type read(void) {
generic_type val;
if (buffer.lenght() == 0) {
if (waiting_read >= MAX)
ok2read.signal();
waiting_read++;
ok2read.wait();
waiting_read--:
}
val = buffer.length() == 0 ? NULL: buffer.dequeue();
ok2write.signal();
return val;
}
Esercizio g.1
- Controllato e corretto dall'utente Acsor in data 21/08/2020
Punto a)
Algoritmo MIN
Stringa di riferimenti: 1 2 3 4 5 1 2 3 4 1 2 3 1 2 1
Frame 1: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Frame 2: 2 2 2 2 2 2 2 2 2 2 2 2 2 2
Frame 3: 3 4 5 5 5 3 4 4 4 3 3 3 3
Algoritmo LRU
Stringa di riferimenti: 1 2 3 4 5 1 2 3 4 1 2 3 1 2 1
Frame 1: 1 1 1 4 4 4 2 2 2 1 1 1 1 1 1
Frame 2: 2 2 2 5 5 5 3 3 3 2 2 2 2 2
Frame 3: 3 3 3 1 1 1 4 4 4 3 3 3 3
Punto b)
Poiché non è specificato quale dei due algoritmi precedenti applicare, sono state considerate soluzioni per ognuno di essi
Algoritmo MIN (da controllare)
(È possibile ottenere una stringa più breve?)
4 3 2 1 5 3 2 1 4 5 3 2 1 3 2 4 5 1 2 4 3 1 5 4 2 1 3 4 ------------------------------------------------------- 4|4|4|4|5| 5 |5| 5 |1| 1 |1| 1 |1| 1 | 1 |3|3|3|3| 3 |3| 3 |3| 3 |5| 5 |5| 5 | 2 | |2|2|2| 2 |2| 2 |2| 2 |2| 2 |3| 3 | 3 | | |1|1| 1 |4| 4 |4| 4 |4| 4 |4| 4 | 4
Algoritmo LRU
Stringa di riferimenti: 4 3 2 1 5 3 2 4 1 5 4 3 1 2
Frame 1: 4 4 4 4 5 5 5 5 1 1 1 1 1 1
Frame 2: 3 3 3 3 3 3 3 3 5 5 5 5 2
Frame 3: 2 2 2 2 2 2 2 2 2 3 3 3
Frame 4: 1 1 1 1 4 4 4 4 4 4 4