Prova svolta Comunicazioni elettriche

Memoria Virtuale

2. Nell’ambito degli algoritmi per la sostituzione della pagina per l’implementazione della me-

moria virtuale, si consideri la seguente sequenza di richieste di pagine:

2, 0, 3, 2, 1, 0, 3, 0, 4, 2, 3, 2

Indicare le pagine in memoria dopo l’esecuzione di ciascuna richiesta e le richieste che pro-

ducono inclusi quelli dovuti al caricamento delle pagine iniziali.

page fault,

Si assuma che la memoria fisica abbia il numero di indicato e che questi siano

page frame

inizialmente “vuoti”.

(a) Algoritmo LRU

i. Memoria fisica con 3 blocchi:

Solution:

Page faults indicated by *:

Memory content:

2* 0* 3* 2 1* 0* 3* 0 4* 2* 3* 2

2 2 2 2 2 2 3 3 3 2 2 2

0 0 0 1 1 1 1 4 4 4 4

3 3 3 0 0 0 0 0 3 3

ii. Memoria fisica con 4 blocchi:

Solution:

Page faults indicated by *:

Memory content:

2* 0* 3* 2 1* 0 3 0 4* 2* 3 2

2 2 2 2 2 2 2 2 4 4 4 4

0 0 0 0 0 0 0 0 0 0 0

3 3 3 3 3 3 3 3 3 3

1 1 1 1 1 2 2 2

(b) Algoritmo FIFO:

i. Memoria fisica con 3 blocchi:

Solution:

Page faults indicated by *:

Memory content:

2* 0* 3* 2 1* 0 3 0 4* 2* 3* 2

2 2 2 2 1 1 1 1 1 1 3 3

0 0 0 0 0 0 0 4 4 4 4

3 3 3 3 3 3 3 2 2 2

ii. Memoria fisica con 4 blocchi: 2

Solution:

Page faults indicated by *:

Memory content:

2* 0* 3* 2 1* 0 3 0 4* 2* 3 2

2 2 2 2 2 2 2 2 4 4 4 4

0 0 0 0 0 0 0 0 2 2 2

3 3 3 3 3 3 3 3 3 3

1 1 1 1 1 1 1 1

3

Sincronizzazione

3. Si consideri il seguente programma:

val=1;

int S1 = {2};

semaphore S2 = {2};

semaphore

P1() {

void {

while(1)

wait(S1); wait(S1);

wait(S2); wait(S2);

val+=2;

signal(S1); signal(S1);

signal(S2); signal(S2);

}

} P2() {

void {

while(1)

wait(S2); wait(S1);

wait(S1); wait(S2);

val*=2;

signal(S1); signal(S2);

signal(S2); signal(S1);

}

} main() {

void

parbegin(P1(),P2());

}

(a) Scrivere una traccia di esecuzione che porta al indicando il valore della variabile

deadlock

condivisa val.

Solution:

P1 P2

wait(S1)

wait(S1) wait(S2)

wait(S1)

wait(S2)

wait(S2)

val = 1,

Con perché i processi non riescono nemmeno ad accedere alla sezione

critica. 4

(b) Si può verificare starvation?

Solution: Assumendo un algoritmo di scheduling fair, il programma non soffre di

starvation. 5

Deadlock Detection

4. (a) Il seguente stato ha due o più processi in deadlock? Si giustifichi la risposta data.

R1 R2 R3

R1 R2 R3

R1 R2 R3 9 4 6

P1 0 2 1 P1 1 0 0

P2 1 1 3 P2 4 1 2 Resource Vector R

P3 1 3 0 P3 2 1 1 R1 R2 R3

P4 3 1 1 P4 0 0 2 2 2 1

Request Matrix Q Allocation Matrix A Available Vector V

Solution: {}

A marked =

1. non contiene righe di tutti zero.

W = V = [2, 2, 1]

2. ≤ {P

Q(P 1) W =⇒ marked = 1}

3. W = W + A(P 1) = [2, 2, 1] + [1, 0, 0] = [3, 2, 1]

4. ≤ {P

Q(P 4) W =⇒ marked = 1, P 4}

5. W = W + A(P 4) = [3, 2, 1] + [0, 0, 2] = [3, 2, 3]

6. ≤ {P

Q(P 2) W =⇒ marked = 1, P 2, P 4}

7. W = W + A(P 2) = [3, 2, 3] + [4, 1, 2] = [7, 3, 5]

8. ≤ {P

Q(P 3) W =⇒ marked = 1, P 2, P 3, P 4} =⇒

9. no deadlock

(b) Il seguente stato ha due o più processi in deadlock? Si giustifichi la risposta data.

R1 R2 R3

R1 R2 R3 R1 R2 R3 9 4 6

P1 0 2 3 P1 1 0 0

P2 2 1 1 P2 4 1 2 Resource Vector R

P3 1 3 0 P3 2 1 1 R1 R2 R3

P4 3 1 3 P4 0 0 2 2 2 1

Request Matrix Q Allocation Matrix A Available Vector V

Solution: {}

A marked =

1. non contiene righe di tutti zero.

W = V = [2, 2, 1]

2. ≤ {P

Q(P 2) W =⇒ marked = 2}

3. W = W + A(P 2) = [2, 2, 1] + [4, 1, 2] = [6, 3, 3]

4. 6

≤ {P

Q(P 1), Q(P 3), Q(P 4) W =⇒ marked = 1, P 2, P 3, P 4} =⇒

5. no

deadlock 7