uniroma1.*_main.c.cognome.nome. Sulle postazioni del laboratorio sarà /home/biar/Desktop/cognome.nome/.cognome.nome.zip (zip -r cognome.nome.zip cognome.nome/).cognome.nome.zip.Per maggiori informazioni fate riferimento al regolamento delle esercitazioni.
L’obiettivo dell’esercizio è implementare l’operazione di deallocazione di un semplice allocatore di memoria. L’operazione mymalloc è fornita e si richiede di scrivere l’operazione myfree nel file E1-free/e1.c. L’operazione deve prendere il blocco deallocato e inserirlo in testa alla lista di blocchi liberi puntata dalla variabile globale free_list come descritto nella dispensa del corso. I blocchi liberi dell’allocatore hanno una header di 4 byte che contiene la dimensione del blocco, seguita da un campo next come definito nel file e1.h:
e1.h (estratto)
#pragma pack(1)
typedef struct header_t {
unsigned size;
struct header_t* next;
} header_t;
Si ricorda che la direttiva del compilatore #pragma pack(1) evita l’inserimento di padding tra il campo size e il campo next, che quindi sono contigui in memoria. L’implementazione della mymalloc (che non deve essere modificata) è riportata di seguito:
e1.c
header_t* free_list = NULL;
void* mymalloc(size_t m) { // prende size del payload da allocare
header_t *p, *q = NULL;
m = ((m+3)/4)*4; // arrotonda al più piccolo multiplo di 4 maggiore o uguale a m
if (m < 8) m = 8; // garantisce spazio per il puntatore next
for (p=free_list; p != NULL; q = p, p = p->next) // cerca blocco libero first-fit
if (p->size >= m) break;
if (p == NULL) p = sbrk(4 + m); // nessun blocco libero, si espande l'heap
else // toglie nodo dalla lista dei blocchi liberi
if (q == NULL) free_list = free_list->next;
else q->next = q->next->next;
((header_t*)p)->size = m; // size misura il blocco a meno del campo size stesso
return (char*)p+4; // restituisce puntatore al payload
}
void myfree(void* p) { // prende puntatore al payload
// completare la funzione...
}
Si compili il programma con make. Se myfree è realizzata correttamente, l’output del programma di prova E1-free/e1_main.c deve essere il seguente (ovviamente gli indirizzi saranno diversi):
--- heap size: 76 byte
1 [0x10289f000][size=16 ][free]
2 [0x10289f014][size=24 ][used]
3 [0x10289f030][size=8 ][free]
4 [0x10289f03c][size=12 ][used]
=== free_list: 0x10289f000
* [0x10289f000][size=16 ][next=0x10289f030]
* [0x10289f030][size=8 ][next=0x0]
Se l’output è questo (a parte i valori degli indirizzi) inserire 1 nel form di consegna, e 0 altrimenti.
L’output elenca dapprima i blocchi presenti in heap e poi mostra il contenuto della lista di blocchi liberi dopo aver eseguito la seguente sequenza di operazioni:
void* p1 = mymalloc(16);
void* p2 = mymalloc(22);
void* p3 = mymalloc(8);
void* p4 = mymalloc(12);
myfree(p1);
myfree(p3);
void* p5 = mymalloc(4);
void* p6 = mymalloc(14);
myfree(p5);
myfree(p6);
Si consideri la seguente funzione in E2-cache/e2.c:
#define STRIDE 64
long f(const short *v, unsigned n){
long x = 0;
unsigned i, j;
for (i=0; i<STRIDE; ++i)
for (j=0; j<n; j+=STRIDE) x += v[i+j];
return x;
}
Scrivere nel file E2-cache/e2_opt.c una versione della funzione semanticamente equivalente che faccia un migliore uso delle cache. Compilare il programma con make ed eseguirlo con ./e2. Il programma riporterà il tempo di esecuzione in millisecondi della versione non ottimizzata e di quella ottimizzata insieme allo speedup ottenuto. Verificare che la versione ottimizzata calcoli lo stesso valore di quella non ottimizzata.
Domanda 1 Quale delle seguenti affermazioni è VERA?
malloc è una system callmalloc alloca tutti blocchi della stessa dimensionemalloc restituisce indirizzi fisicifree punta al payload del blocco allocato da mallocDomanda 2 Quale delle seguenti affermazioni è VERA?
malloc/free) non soffre di frammentazione esternaDomanda 3 Quale delle seguenti affermazioni è FALSA?
Domanda 4 Data la seguente porzione di codice. Quanti cicli di clock vengono richiesti da una semplice pipeline a 5 stadi (Fetch, Decode, Execute, Memory, Write-Back) per completare tutte le istruzioni assumendo che gli hazard vengano risolti con stalli?
movl $1, %eax
addl %eax, %ecx
addl $2, %edi
incl %esi
addl %esi, %edx
movl $3, %ebx
Domanda 5 Con riferimento alla domanda 4, è possibile ottimizzare il codice riordinando le istruzioni (senza cambiare la semantica) in modo da ridurre il numero di cicli di clock richiesti?
e1.c
void myfree(void* p) {
header_t* q = (header_t*)((char*)p-4);
q->next = free_list;
free_list = q;
}
e2_opt.c
#include "e2.h"
long f_opt(const short *v, unsigned n){
long x = 0;
unsigned i;
for (i=0; i<n; i+=1) x += v[i];
return x;
}
D. L’indirizzo passato alla free punta al payload del blocco allocato da malloc
Spiegazione: alla funzione free occorre passare l’indirizzo restituito dalla corrispondente malloc, che punta al payload del blocco (cioè la parte effettivamente utilizzabile per i dati) e non al header del blocco (che è gestito internamente da malloc/free in modo totalmente trasparente per il programmatore).
E. Nessuna delle precedenti
Spiegazione: Tutte le altre risposte sono false. Infatti:
malloc/free soffre di frammentazione esterna. Infatti, la malloc deve poter allocare blocchi di dimensioni diverse (dunque la free può lasciare buchi di dimensioni diverse) e, per ovvie ragioni, può restituire solo blocchi contigui di memoria. Dunque anche la risposta B è falsa.E. La dimensione di una linea di cache è pari alla dimensione di una pagina della memoria virtuale
Spiegazione: Non c’è alcuna relazione tra la dimensione delle linee di cache e la dimensione delle pagine della memoria virtuale.
A. 16
Spiegazione:
movl $1, %eax F D E M W
stallo * * * * *
stallo * * * * *
stallo * * * * *
addl %eax, %ecx F D E M W
addl $2, %edi F D E M W
incl %esi F D E M W
stallo * * * * *
stallo * * * * *
stallo * * * * *
addl %esi, %edx F D E M W
movl $3, %ebx F D E M W
|<=== 16 cicli ===>|
C. Sì è possibile ridurre il numero di cicli di clock a 10, ma non a meno
Spiegazione:
movl $1, %eax F D E M W
incl %esi F D E M W
addl $2, %edi F D E M W
movl $3, %ebx F D E M W
addl %eax, %ecx F D E M W
addl %esi, %edx F D E M W
|<= 10 cicli =>|