Informatica 2 – Prova di giovedì 24 febbraio...

Politecnico di Milano

Dipartimento di Elettronica e Informazione

prof. Cesare Alippi prof.ssa Anna Antola prof. Luciano Baresi prof. Luca Breveglieri

prof. Luigi Lavazza prof. Giuseppe Pelagatti prof.ssa Donatella Sciuto

Con Soluzioni

Informatica 2 – Prova di giovedì 24 febbraio 2005

Matricola_______ _______________________

Cognome_______ ___________________Nome _____________________

Istruzioni • Scrivere solo sui fogli distribuiti. Non separare questi fogli. • È vietato portare all’esame libri, eserciziari, appunti, calcolatrici e telefoni cellulari. Chiunque

fosse trovato in possesso di documentazione relativa al corso – anche se non strettamente at-tinente alle domande proposte – vedrà annullata la propria prova.

• Non è possibile lasciare l’aula conservando il tema della prova in corso. • Tempo a disposizione: 1h:40m (una parte) 2h:30m (completo).

I Parte II parte Completo

Esercizio 1

Esercizio 2

Esercizio 3

Esercizio 4

Esercizio 5

Esercizio 6

Esercizio 7

Esercizio 8

Voto finale

Informatica 2 – prova di giovedì 24 Febbraio 2005 Esercizio n. 1 -- pagina 2 di 19

Esercizio n. 1

Si consideri il programma seguente, dove il file “string” esiste e contiene la stringa “AABBCCC”:

00 int main ( ) { 01 int i, pid, fd; 02 int status = 0; 03 char c; 04 char V = ‘V’; 05 char Z = ‘Z’; 06 fd = open (“string”, O_RDWR); 07 i = 1; 08 do { 09 pid = fork ( ); 10 if (pid == 0) { 11 if (i == 2) { 12 read (fd, &c, 1); 13 } else if (i == 3) { 14 write (fd, &Z, 1); 15 } else { 16 write (fd, &V, 1); 17 } /∗ if ∗/ 18 read (fd, &c, 1); 19 exit (i); 20 } else if (i <= 2) 21 wait (&status); 22 i++; 23 /∗ ** ∗/ 24 } while (i <= 3); /∗ do ∗/ 25 read (fd, c, 1); 26 exit (0); 27 } /∗ main ∗/

Rispondere alle domande seguenti, sapendo che il processo padre ha PID 100, tutti i PID successivi sono liberi e il sistema operativo li assegna andando in successione:

• Ci sono 4 processi in totale: come sono organizzati gerarchicamente, cioè chi crea chi ? (padre con 3 figli)

• Quale (o quali) stringa contiene il file “string” quando tutti i processi sono terminati ? VABBZCC, VABBCZC

• Qual è il numero max di servizi write che il S.O. potrebbe avere contemporaneamente in corso ? 1 solo: write riga 16 e in seguito write riga 14; non sono mai contamporanee.

• Qual è il numero max di servizi read che il S.O. potrebbe avere contemporaneamente in corso ? 2: read riga 18 con i = 3 e read riga 24; read 18 parte per prima ma potrebbero essere parzialmente sovrapposte.

Completare le tabelle seguenti, facendo attenzione ai punti seguenti:

• tutte le chiamate ai servizi di sistema hanno sempre successo • la frase “prima dell’istruzione N” si riferisce all’istante in cui si inizia l’esecuzione dell’istruzione N

stessa • il padre ha PID 100, tutti i PID successivi sono liberi e il sistema operativo li assegna andando in

successione • quando si è certi che la variabile non esista, si riporta NE • quando si è certi che la variabile esista, ma non se ne riesce a stabilire il valore, si riporta X • quando non si riesce a stabilire se la variabile esista oppure no, si riporta U

Valore delle variabili nel processo padre i pid status

Prima dell’istruzione 07 X X 0


Prima dell’istruzione 18 (quando è eseguita da F1) 1 100 o 101 0

Prima dell’istruzione 18 (quando è eseguita da F3) U U U

Prima dell’istruzione 25 4 103 2

Valore delle variabili nel processo figlio n. 3 i pid status

Prima dell’istruzione 07 NE NE NE

Prima dell’istruzione 16 NE NE NE

Prima dell’istruzione 25 U U U


Esercizio n. 2

Un sistema dotato di memoria virtuale con paginazione e segmentazione tipo UNIX è caratterizzato dai se-guenti parametri: l’indirizzo logico è di 15 bit; l’indirizzo fisico è di 15 bit. La dimensione delle pagine è di 2048 byte.

• definire la struttura dell’indirizzo logico e di quello fisico indicando la lunghezza dei campi che li costitui-scono:

NPV: 4 ____________ Spiazzamento logico: 11 ____________

NPF: 4 ____________ Spiazzamento fisico: 11 _____________

• Nel sistema all’istante t0 è attivo un processo P che esegue il programma PGP ed un processo Q che e-segue il PGQ. Le dimensioni iniziali dei programmi sono le seguenti:

CP: 6K; DP: 6K; PP: 4K;

CQ: 2K; DQ: 2K; PQ: 2K;

All’istante t1> t0 il processo P ha effettuato una fork creando il processo R. Si supponga che la fork non duplichi il codice del processo pertanto, dopo la fork, il processo P e R condividono il segmento di codi-ce. Inserire in tabella 1a il significato delle varie pagine di memoria logica (notazione: CP0, CP1, DP0, PP0,…CQ0, …) all’istante t1.

Indirizzo di pagina virtuale

Processo P

Processo Q

Processo R

Indirizzo fisico

Pagine allocate t1

Indirizzo fisico

Pagine allocate t2

0 CP0 CQ0 CR0 (CP0) 0 CP0 (CR0) 0 CP0 (CR0)

1 CP1 DQ0 CR1 (CP1) 1 CP1 (CR1) 1 CP1 (CR1)

2 CP2 CR2 (CP2) 2 CP2 (CR2) 2 CP2 (CR2)

3 DP0 DR0 3 DP0 3 PP2 (t2)

4 DP1 DR1 4 DP1 4 PP3 (t2)

5 DP2 DR2 5 DP2 5 DP2

6 DP3 (t2) DR3 (t2) 6 PP0 6 PP0

7 7 PP1 7 PP1

8 8 CQ0 8 occupata (t2)

9 9 DQ0 9

A A PQ0 A

B B DR0 B DR3 (t2)

C PP3 (t2) C DR1 C DR1

D PP2 (t2) D DR2 D DR2

E PP1 PR1 E PR0 E PR0

F PP0 PQ0 PR0 F PR1 F PR1

1A) Struttura della Memoria Logica 1B) Memoria Fisica agli istanti t1 e t2

Riassumendo, all’istante t1 sono terminati i seguenti eventi:

a. lancio di P (fork di P ed exec di PGP)

b. lancio di Q (fork di Q ed exec di PGQ)

c. fork di P e creazione di R

• Indicare quanto spazio (in pagine) è disponibile per l’allocazione dinamica nei processi

P: 8______________________ Q 13 _____________________

• Sapendo che il numero di pagine residenti R è 8, che viene utilizzato l’algoritmo LRU e che le pagine meno utilizzate in ogni processo sono la prima pagina del segmento dati, quindi la seconda pagina del


segmento dati (le prime caricate sono le meno utilizzate) e ipotizzando che l’allocazione delle pagine vir-tuali nelle pagine fisiche sia avvenuta in sequenza senza buchi a partire dalla pagina fisica 0, indicare, completando tabella 1B (sinistra), l’allocazione fisica delle pagine dei tre processi all’istante t1. Si indica con occupata una pagina utilizzata da altro processo. Le pagine fisiche sono allocate in sequenza e senza buchi a partire dalla 0.

• Ad un certo istante t2 > t1 sono terminati i seguenti eventi:

d. terminazione del processo Q

e. allocazione delle pagina di indirizzo fisico 8 a un processo diverso da P e Q.

f. crescita della pila di P di 2 pagine

g. allocazione di 1 pagina di memoria per R (servizio BRK)

Completare la tabella 1B (destra) nelle medesime ipotesi delineate nel precedente punto e assumendo che, dovendo utilizzare una pagina fisica libera, venga sempre utilizzata la pagina fisica libera avente indirizzo di pagina minore.

• Indicare il contenuto della tabella delle pagine della MMU all'istante t2 completando la seguente tabella (usare P, Q e R come pid dei corrispondenti processi, oppure NS se nella corrispondente riga della tabella non è allocato alcun processo e quindi è non significativa, ‘-’ se la pagina è occupata da un processo di-verso da P,Q e R); ipotizzare che le righe della tabella siano state allocate ordinatamente man mano che venivano allocate le pagine di memoria virtuale e che gli eventi di cui al punto precedente influenzanti la MMU abbiano utilizzato le righe lasciate libere e che se richiesta una nuova riga si utilizzi la prima riga li-bera. Indicare anche il valore assunto dal bit di validità di pagina (1 significa che la pagina è caricata).

PID Num. Pag. Virt. Num. Pag. Fis. Bit Validità

P 0 0 1

P 1 1 1

P 2 2 1

P D (t2) 3 1

P C (t2) 4 1

P 5 5 1

P F 6 1

P E 7 1

- - 8 1

NS NS NS 0

NS NS NS 0

R 0 0 1

R 1 1 1

R 2 2 1

R 6 (t2) B 1

R 4 C 1

R 5 D 1

R F E 1

R E F 1


Esercizio n. 3

Si considerino i seguenti frammenti di programmi:

/* programma main1.c */ main ( ) { int pid; char TERM1 [30] = “...”; ... for (i=0; i<2; i++) { pid = fork ( ); if (pid == 0) {/* codice eseguito dai figli di P*/ read(stdin, &c,1); if (c==’q’) {write (stdout, TERM1, 30); exit (5); } else { execl (“/home/info2/risposta”,”risposta”, NULL); exit (-1); } } else {/* codice eseguito dal padre P */ if (i==1) pid = wait (&status); }/*end for*/

exit(0); } /* end main1.c */ ________________________________________________________

/* programma risposta.c */ main ( ) {char RISP[30] = “...”; ... read(stdin, &d,1);

write (stdout, RISP, 30); ...

} /* end risposta.c */

Un processo P esegue il programma main1, creando, tramite un ciclo, un processo figlio Q e un processo figlio R. I processi figli possono eseguire una mutazione di codice (si ipotizzi che la execl, quando eseguita, vada sempre a buon fine).

Nella tabella a pagina seguente sono indicati (nella prima colonna) alcuni eventi che si sono verificati durante l’esecuzione dei programmi da parte di P, Q e R; nella seconda colonna è aggiunta un’indicazione supplementare relativa a tali eventi. Si deve completare tale tabella indicando ordinatamente nella terza colonna tutti i moduli del S.O. che vengono eseguiti (completamente o in parte) in seguito all’evento, nella quarta colonna il contesto nel quale ciascun modulo è eseguito e, nelle ultime tre colonne, lo stato dei processi P, Q e R dopo che tutti i moduli hanno svolto la funzione e si ritorna al funzionamento in modo U.

Avvertenze per il riempimento della tabella:

1. non esistono altri processi nel sistema

2. il buffer del driver di standard output ha dimensione di 30 caratteri

3. la notazione 1 interrupt (2, 3, … interrupt) indica che si sono verificati 1 (2, 3, …) interrupt; nella risposta fare riferimento all'ultimo di tali interrupt

3. il modulo wait invoca sleep_on su un evento opportuno

4. la terminazione di un processo (exit) invoca wakeup per risvegliare il processo padre eventualmente in attesa.

5. se un processo viene risvegliato da wakeup e non ci sono altri processi pronti o in esecuzione, il processo viene immediatamente lanciato in esecuzione (in questo caso wakeup invoca change)


6. se viene invocata change e nessun processo è pronto, change non lancia in esecuzione alcun processo e il contesto è non specificato – n.s.

7. se, al momento di un cambiamento di contesto, piu' di un processo e' pronto all'esecuzione, viene scelto quello di maggiore priorita'. I tre processi considerati hanno le seguenti priorita': P > Q > R

8. indicare i moduli utilizzando la notazione seguente:

Notazione abbreviata Modulo (o frammento di modulo) di sistema

G_SVC Gestore SVC

R_Int(Disp) Routine di interrupt; Disp può valere CK=orologio, Sout=Standard output, Sin=Standard input, DMAin=disco_in_lettura, DMAout=disco_in_scrittura

<nome routine di sistema> puo’ essere: fork, write, read, wait, exit, open, preempt, change

Sleep_on(En) Sleep_on. Per indicare l’evento su cui viene sospeso il processo usare convenzionalmente E1, E2, E3, …

Wakeup(En) Wakeup. En indica l’evento, come in Sleep_on Codice Utente nessun modulo di sistema, il processo esegue codice utente


Stato dei processi dopo la gestione dell’evento Evento

(preceduto dal processo nel cui contesto l’evento

si verifica)

Informazioni aggiuntive

Moduli eseguiti per gestire

l’evento

Processo/i nel cui

contesto è eseguito

ogni modulo

P Q R

P:fork P ha esaurito il suo

quanto di tempo (n.b. la fork è stata eseguita)

G_SVC fork

Preempt Change

fork

P P P

P-Q Q

Pronto Esec U Non esiste

Q: read (stdin, &c,1); Lo standard input non è pronto

G_SVC read

Sleep_on(E1) Change Preempt

Fork

Q Q Q

Q-P P P

Esec U Attesa Non esiste

P:fork P non ha esaurito il suo quanto di tempo

G_SVC fork

P P Esec U Attesa Pronto

P: interrupt da standard input

P ha esaurito il suo quanto di tempo

R_int(sin) Wake_up(E1)

Preempt Change

Sleep_on(E1) read

P P P

P-Q Q Q

pronto Esec U Pronto

Q: write (stdout, TERM1, 30);

Write ha trasferito i 30 caratteri nel buffer

G_SVC write

Sleep_on(E2) Change

Q Q Q

Q-P

Esec U Attesa Pronto

P: wait

G_SVC wait

Sleep_on(E3) Change

fork

P P P

P-R R

Attesa Attesa

Esec U

R: read(stdin, &d,1); Lo standard input non è pronto

G_SVC read

Sleep_on(E4) Change

R R R

R-n.s.

Attesa Attesa Attesa

n.s.: 20 interrupt da standard output R_int(sout) n.s. Attesa Attesa

Attesa


n.s: interrupt da standard input

R_int(sin) Wake_up(E4)

Preempt Change

Sleep_on(E4) read

n.s. n.s. n.s

n.s.-R R R

Attesa Attesa

Esec U

R: 10 interrupt da standard output

L’ultimo è relativo all’ultimo carattere da

trasferire R ha esaurito il suo quanto di tempo

R_int(sout)

Wake_up(E2) Preempt Change

Sleep_on(E2) write

R R R

R-Q Q Q

Attesa Esec U Pronto

Q: exit

G_SVC

exit Wake_up(E3)

Change Sleep_on(E3)

wait

Q Q Q

Q-P P P

Esec U Non esiste Pronto

P: exit

G_SVC

exit Change

P P

P-R Non esiste Non esiste

Esec U


Esercizio n. 4

Si consideri il seguente programma:

/∗ include vari ∗/ int main ( ) {

/∗ dichiarazioni varie ∗/ pid = fork ( ); fd1 = open ("/etc/file2", O_RDONLY); if (pid == 0) { read (fd1, buf, 5); fd2 = open ("/etc/file1", O_RDONLY); read (fd2, buf, 2); exit (0);

} /∗ if ∗/ read (fd1, buf, 3); wait (&status);

} /∗ main ∗/

Un processo P esegue tale programma, creando a un certo momento un processo figlio chiamato Q. Comple-tare le tabella della pagina seguente alla fine della seguente sequenza di eventi:

• dopo l’esecuzione della funzione fork il processo P ha ripreso la sua esecuzione;

• P rimane in esecuzione sino all’invocazione della wait;

• il processo Q ha iniziato la sua esecuzione dopo che il processo P ha eseguito la wait;

• il processo Q ha eseguito la seconda funzione read e deve ancora eseguire la funzione exit.

• Completare la tabella globale dei file aperti e quelle dei file aperti dei processi P e Q.

Avvertenze per il riempimento delle tabelle:

• l’i-node associato alla directory radice ( / ) ha 2 come i-number ed è il primo i-node ad essere carica-to nella tabella degli i-node del volume;

• il blocco dei dati associato ad un catalogo (directory) contiene una tabella in cui nella prima colonna c’è il numero di i-node e nella seconda il nome del file o della directory;

• con Pos.Corr. si intende l’indicatore di posizione corrente all’interno del file;

• con Punt. si intende la posizione nella tabella degli i-node;

• con Num.Proc si intende l’indicatore del numero di processi che hanno aperto il file

• xxx indica che è presente un valore non significativo ai fini del problema

• le tabelle sono semplificate e contengono solamente le colonne delle quali è richiesto il riempimento


Tabella degli i-node numero i-node

tipo blocco

2 directory 44 3 directory 45 4 normal 46 5 normal 47

Blocco 44

n° i-node nome file / directory 3 etc 7 dev 14 lib ... ...

Blocco 45 n° i-node nome file / directory

4 file1 5 file2

Blocco 46

VOLUME

abcdefghilmnopqrstuvz

Tabella dei file aperti del processo P 0 xxx 1 xxx 2 xxx 3 4 5

Tabella dei file aperti del processo Q 0 xxx 1 xxx 2 xxx 3 4 5 6

Tabella globale dei file aperti indice Pos.Corr. Num

Proc Punt

0 xxx xxx xxx 1 xxx xxx xxx 2 3 4 5 6 7 8 9

Tabella degli i-node indice tipo blocco 0 dir 44 1 xxx xxx 2 dir 45 3 xxx xxx 4 norm 46 5 norm 47

Struttura dati del S.O. in memoria

Blocco 47 adfgtogorokokgèflsaèplafpl


Esercizio n. 5

Parte A

D1 Q1

D2 Q2

In1

In2Out

La figura rappresenta un circuito sequenziale costituito da due bistabili Master/Slave, nel quale per semplicità è stato omesso il segnale di clock; le funzioni di assegnamento di un nuovo valore ai bistabili sono:

D1 = In1; D2 = Q1 nand In2 = not (Q1 and In2)

Si chiede di completare il diagramma temporale riportato qui sotto. Si noti che: • si devono trascurare completamente il ritardo delle porte e il ritardo di commutazione dei bistabili; • i bistabili sono di tipo “master-slave”, in cui l’uscita commuta sul fronte di discesa del clock; • gli ingressi In1 e In2 possono variare dopo un fronte di discesa del clock, ma prima del fronte di salita.

C

Q1

Q2

In2

D1

D2

In1


C

Q1

Q2

In2

D1

D2

In1

Parte B

Dati i due seguenti valori numerici espressi in base 10

A = +79

B = −95

si chiede di:

(a) indicare il numero minimo di bit necessari a rappresentarli entrambi in complemento a 2:

n = 8

infatti con 8 bit si rappresentano i numeri da –27= -128 a +27-1=127

(b) codificare A e B in complemento a 2 con il numero di bit trovato in precedenza. Si mostrino tutti i pas-saggi necessari per ottenere la codifica:

A = 7910 = 01001111

-B = 9510 = 01011111

B = -9510 = 10100000+1 = 10100001

(c) eseguire in complemento a 2, con un numero di bit pari a quello trovato al punto a), le operazioni

A + B

A − B

mostrando tutti i passaggi necessari a ottenere il risultato, e indicare quali dei seguenti bit di flag (N (ne-gative), Z (zero), C (carry) e O (overflow)) assumano valore 1 a valle dell'operazione eseguita.

A+B = A-B =

01001111+ 01001111+


10100001=

11110000 (N)

01011111 =

10101110 (O)


Esercizio n. 6

Lo schema riportato qui di fianco illustra l’architettura Mic-1.

Facendo riferimento a questa architettura, scri-vere il microcodice dell’istruzione SUBVAR num che si vuole aggiungere alla macchina IJVM. L’istruzione sottrae la variabile indicata da num al valore presente in cima alla pila, memorizza il valore ottenuto nella variabile indicata da num e cancella il valore sulla cima della pila. num e' sempre un numero non negativo rap-presentato con un byte.

Formato istruzione:

• SUBVAR num • l’operando num occupa un byte, quindi la

dimensione complessiva dell’istruzione è di due byte (uno per il codice operativo e uno per num)

Soluzione: (DA VERIFICARE)

subvar1 H = LV subvar2 MAR = H + MBR, rd subvar3 H = TOS subvar4 MDR = H – MDR, wr subvar5 MAR = SP = SP – 1, rd subvar6 PC = PC + 1, fetch subvar7 TOS = MDR; goto MAIN 1

SHIFTER

H

OPC

TOS

CPP

LV

SP

PC

MDR

MAR

MBR

N

2

6

ALU

ZALU

SHIFT

MA

IN

MEM

OR

Y


Esercizio n. 7

Prima parte Completare la codifica in assembler IJVM della funzione C “funz” riportata qui sotto. Non sono ammesse ot-timizzazioni del codice prodotto. S’ipotizzi che sia già disponibile il seguente frammento di codice:

int f1 (int x,int y) {...};

int f2 (int x) {...};

.constant OBJREF 0 .end-constant .method f1 (x,y) ... .end-method .method f2 (x) ... .end-method

Funzione C Codifica IJVM

int funz (int a, int b) {

if (f1(a-b, a+b)== f2(b)) return(0);

else return(1);

} /* funz */

.method funz (a,b) LDCW OBJREF ILOAD a ILOAD b ISUB ILOAD a ILOAD b IADD INVOKEVIRTUAL f1 LDCW OBJREF ILOAD b INVOKEVIRTUAL f2 IFCMPEQ ZERO BIPUSH 1 IRETURN ZERO: BIPUSH 0 IRETURN .end-method


Seconda parte

Completare l’assemblaggio del metodo F seguente: .method F (X) .var A,B .end-var … il codice è riportato direttamente nella tabella relativa all’assemblaggio .end-method

Riportare nella prima tabella (Tabella dei Simboli) i simboli con i corrispondenti valori numerici. Indicare esplicitamente i simboli che non si possono risolvere all’interno del metodo. Completare nella seconda tabella il risultato dell’assemblaggio indicando nella prima colonna l’indirizzo del primo byte dell’istruzione, nella seconda il numero di byte compresi nell’istruzione e nella sesta il valore nu-merico degli operandi (laddove siano stati risolti). A titolo d’esempio sono compilate alcune righe in ambedue le tabelle

(1) (2) (3) (4) (5) (6) Indirizzo

primo byte Numero di byte

Eventuale etichetta

Opcode simbolico

Operando simbolico

Operando dopol'assemblaggio

0 2 D e s c r i t t o r e p a r a m e t r i 1

2 2 D e s c r i t t o r e v a r i a b i l i 2

4 2 ILOAD B 3

6 2 CICLO: BIPUSH 2 2

8 2 IADD

10 2 ISTORE A 2

12 2 ILOAD X 1

14 2 ILOAD A 2

16 2 ISUB

18 3 IFLT FINE +6

21 3 GOTO CICLO -15

24 1 FINE IRETURN

25

TABELLA INGOMBRO ISTRUZIONI

Opcode Operandi Ingombro(#byte)

BIPUSH byte 2 DUP - 1 GOTO label name 3 IADD, ISUB, IAND, … - 1 IFEQ, IFLT label name 3 IF_ICMPEQ label name 3 IINC variable name, byte 3 ILOAD, ISTORE variable name 2 INVOKEVIRTUAL method name 3 IRETURN - 1 LDC_W constant name 3 POP, SWAP - 1

TABELLA DEI SIMBOLI

Riferimento simbolico Valore numerico

X 1

A 2

B 3

CICLO 6

FINE 24


Esercizio n. 8

Si consideri un sistema di memoria (memoria + cache) caratterizzato dalle dimensioni seguenti: • memoria di 4 GigaByte (indirizzata a livello di byte); • cache di 256 KByte; • ogni blocco della cache contiene 64 Byte.

Si chiede di indicare la struttura degli indirizzi per la memoria cache nelle situazioni seguenti: • cache a indirizzamento diretto (direct mapped) • cache completamente associativa • cache set-associativa a 4 vie

Soluzione Memoria di lavoro: indirizzo di 32 bit Memoria cache: indirizzo di 18 bit Blocchi: indirizzo di 6 bit

(a) Cache a indirizzamento diretto • 6 bit per il byte nel blocco • 12 bit per l’indice del blocco nella cache • 14 bit di etichetta

(b) Cache completamente associativa • 6 bit per il byte nel blocco • 26 bit di etichetta

(c) Cache set-associativa a 4 vie • 6 bit per il byte nel blocco • 10 bit per l’indice del gruppo nella cache • 16 bit di etichetta

Seconda parte

Si consideri un sistema di memoria (memoria + cache) caratterizzato dalle dimensioni seguenti: • memoria di lavoro di 4 KByte, indirizzata a livello di singolo byte; • cache di 512 Byte; • ogni blocco della cache contiene 128 Byte.

Considerando la sequenza di richieste alla memoria riportata qui sotto, si chiede di completare la tabella che illustra il comportamento di una cache set-associativa a 2 vie nel rispetto delle indicazioni seguenti:

• Nella colonna “esito” riportare H (hit) se il blocco richiesto si trova nella cache, M (miss) se invece il blocco deve essere caricato dalla memoria.

• Nelle colonne “dati” deve essere riportato il numero del blocco della memoria che si trova nel corrispondente blocco della cache. Si noti che questi valori sono riportati come numeri decimali (ba-se dieci), mentre le etichette sono scritte in binario. Per questo motivo l’indirizzo 000 0001 0010 in-dividua un byte compreso nel blocco 00000due = 0dieci (che quindi ha come etichetta il valore binario 0000).

• Nella colonna “azione” deve essere indicato il blocco cui si accede (in caso di successo, H) o il blocco in cui vengono caricati i dati della memoria (in caso di fallimento, M).

• Nella cache ci sono quattro blocchi denotati dalle lettere A, B, C e D, che sono organizzati in due in-siemi: si ipotizzi che i blocchi A e B siano compresi nell’insieme 0 e che i blocchi C e D facciano in-vece parte dell’insieme 1.

• La politica di sostituzione adottata nella cache è quella LRU (Least Recently Used).

Note: dei 12 bit di indirizzo, 7 servono per individuare il byte nel blocco. Nella cache ci sono quattro blocchi organizzati in due gruppi, quindi l’8° bit (da destra) indica l’insieme, mentre i restanti 4 bit formano l’etichetta.

Blocco A Blocco B Blocco C Blocco D

Pas

so

Indirizzo richiesto

Esit

o

Val

ido

Etic

het

ta

Dat

i

Val

ido

Etic

het

ta

Dat

i

Val

ido

Etic

het

ta

Dat

i

Val

ido

Etic

het

ta

Dat

i

Azione

0 1 1000 16 0 0100 8 1 0001 3 0 0000 Situazione iniziale

1. 0010 1101 0010 M 1 1000 16 0 0001 1 0001 3 1 0010 5 Carica blocco 5 in D

2. 1000 1101 0100 M 1 1000 16 0 0001 1 1000 17 1 0010 5 Carica blocco 17 in C


3. 1000 1011 1111 H 1 1000 16 0 0001 1 1000 17 1 0010 11 Accesso a C

4. 0100 0000 1010 M 1 1000 16 1 0100 8 1 1000 17 1 0101 11 Carica blocco 8 in B

5. 1100 1101 0010 M 1 1000 16 1 0100 8 1 1000 17 1 1100 25 Carica blocco 25 in D

6. 1011 0100 0110 M 1 1011 22 1 0100 8 1 1000 17 1 1100 25 Carica blocco 22 in A

Informatica 2 – Prova di giovedì 24 febbraio...

Documents

Transcript of Informatica 2 – Prova di giovedì 24 febbraio...