Sistemi di Calcolo

Corso di Laurea in Ingegneria Informatica e Automatica

Home | Avvisi | Diario Lezioni | Esercitazioni | Esami | Materiale Didattico | Valutazioni Studenti | Lezioni di Camil Demetrescu |

[T11] Esercitazione del 14 maggio 2021

Istruzioni per l’esercitazione:

Per maggiori informazioni fate riferimento al regolamento delle esercitazioni.

Esercizio 1 (un semplice allocatore di memoria)

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);
Esercizio 2 (ottimizzazioni per la cache)

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.

Esercizio 3 (Domande)

Domanda 1 Quale delle seguenti affermazioni è VERA?

Domanda 2 Quale delle seguenti affermazioni è VERA?

Domanda 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?

Soluzioni

Esercizio 1 (un semplice allocatore di memoria)

e1.c

void myfree(void* p) {
    header_t* q = (header_t*)((char*)p-4);
    q->next = free_list;
    free_list = q;
}
Esercizio 2 (ottimizzazioni per la cache)

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;
}
Esercizio 3 (Domande)
  1. 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).

  2. E. Nessuna delle precedenti

    Spiegazione: Tutte le altre risposte sono false. Infatti:

    • La frammentazione esterna si ha quando si avrebbe spazio libero sufficiente ad accogliere una richiesta di allocazione, ma poiché i blocchi liberi sono frammentati non è possibile accoglierla (ciascun blocco libero non è sufficientemente grande da soddisfare la richiesta di allocazione). Questa non ha niente a che vedere con il padding, perciò l’affermazione A è falsa.
    • L’allocatore 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.
    • Il meccanismo di paginazione della memoria, poiché alloca solo blocchi di dimensione fissa, non soffre del problema della frammentazione esterna, tuttavia soffre del problema della frammentazione interna (come tutti gli allocatori che possono allocare blocchi di memoria più grandi di quelli realmente richiesti). Dunque la risposta C è falsa.
    • Infine, l’area di swap permette di allocare più memoria virtuale di quanta ne sia disponibile in memoria fisica (in RAM). Non rappresenta un mezzo per contrastare la frammentazione interna, che invece rimane indipendentemente dall’area di swap. Dunque anche la risposta D è falsa.
  3. 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.

  4. 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       ===>|
    
  5. 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   =>|